首页 > 代码库 > 跳表的C语言实现，不同于redis版本

跳表的C语言实现，不同于redis版本

2024-07-25 17:05:14   226人阅读

本来跳表的原理是很简单的（相对于红黑树），但是国庆节断断续续搞了5天才把它写完……

写之前我了解到的跳表都是纯粹基于链式结构的，写的过程中看了一下redis的实现，发现它的每一个键列都是用数组来表示的。仔细想了想发现这种实现除了跳表的最大层数会被固定（因为是用的数组）之外，在性能、代码简洁性方面都是非常好的。而且实际使用中，可能也并不希望跳表的层数毫无限制地增长。

不过最后我自己的实现还是按照纯粹链式结构实现，因为数组的方式redis已经实现过了。

关于跳表原理网上很多，这里不再赘述，代码疏漏之处恳请指出。上一张图表示我代码中的跳表逻辑结构：


跳表API定义——skip_list.h

#ifndef SKIP_LIST_H_INCLUDED
#define SKIP_LIST_H_INCLUDED

typedef struct skip_list_s *skip_list_t;

/**
 * @return	新建的的空跳表实例
 */
skip_list_t
skip_list_create();

/**
 * 销毁跳表实例，不会销毁跳表中包含的值。
 */
void
skip_list_destroy(skip_list_t sl);

/**
 * 查询跳表中key对应的值。
 * 返回NULL不代表跳表中一定不包含key，以skip_list_contains(sl, key)结果为准。
 * @param	key		要查询的键，允许key在跳表中不存在。
 * @return	跳表中key对应的值
 */
void*
skip_list_get(skip_list_t sl, int key);

/**
 * 向跳表中添加一个键值对，这将使得skip_list_contains(sl, key)==1。
 * 如果跳表中已经存在相同的键，则替换其旧值，否则创建一个新的键值对。
 * @param	value	key对应的新的值，允许为NULL。
 * @return	跳表中key原来对应的值
 */
void*
skip_list_put(skip_list_t sl, int key, void *value);

/**
 * 从跳表中删除一个键值对，这将使得skip_list_contains(sl, key)==0。
 * @param	key		要删除的键，允许key在跳表中不存在。
 * @return	跳表中key对应的值
 */
void*
skip_list_remove(skip_list_t sl, int key);

/**
 * @return	跳表中存在key则1，否则0
 */
int
skip_list_contains(skip_list_t sl, int key);

/**
 * @return	跳表中键的数量
 */
int
skip_list_count(skip_list_t sl);

/**
 * 检索跳表中键的集合，结果按照键升序排列
 * @param	[out] keys		用于存储键集合
 * @param	[int] length	keys数组的长度
 * @return	键的数量（=MIN(length, 跳表中所有键的数量)）
 */
int
skip_list_key_set(skip_list_t sl, int keys[], int length);

/**
 * 检索跳表中值的集合，结果按照键升序排列
 * @param	[out] values	用于存储值集合
 * @param	[int] length	values数组的长度
 * @return	值的数量（=MIN(length, 跳表中所有键的数量)）
 */
int
skip_list_value_set(skip_list_t sl, void *values[], int length);

#endif // SKIP_LIST_H_INCLUDED

跳表API测试——main.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "skip_list.h"

#define COUNT	10

int main() {
	skip_list_t sl;
	int i, tmp, *keys;

	keys = (int*)malloc(COUNT*sizeof(int));

	srand(time(NULL));

	sl = skip_list_create();

	for(i=0; i<COUNT; i++) {
		keys[i] = rand();
		tmp = rand();
		printf("put %5d : %5d, return %5d", keys[i], tmp, (int)skip_list_put(sl, keys[i], (void*)tmp));
		printf(", count=%d\n", skip_list_count(sl));
	}

	puts("*****************************************");

	for(i=0; i<COUNT; i++) {
		printf("put %5d : %5d, return %d\n", keys[i], keys[i], (int)skip_list_put(sl, keys[i], (void*)keys[i]));
	}

	puts("*****************************************");

	skip_list_key_set(sl, keys, COUNT);
	printf("key set : ");
	for(i=0; i<COUNT-1; i++) {
		printf("%d, ", keys[i]);
	}
	printf("%d\n", keys[COUNT-1]);

	puts("*****************************************");

	for(i=0; i<COUNT; i++) {
		printf("get %5d, return %d\n", keys[i], (int)skip_list_get(sl, keys[i]));
	}

	puts("*****************************************");

	for(i=0; i<COUNT; i++) {
		printf("constains %5d, return %d\n", keys[i], skip_list_contains(sl, keys[i]));
	}

	puts("*****************************************");

	for(i=0; i<COUNT; i++) {
		printf("remove %5d, return %5d", keys[i], (int)skip_list_remove(sl, keys[i]));
		printf(", count=%d\n", skip_list_count(sl));
	}

	puts("*****************************************");

	for(i=0; i<COUNT; i++) {
		printf("constains %5d, %d\n", keys[i], skip_list_contains(sl, keys[i]));
	}

	skip_list_destroy(sl);

	free(keys);

	return 0;
}

跳表API实现——skip_list.c

#include "skip_list.h"
#include <stdlib.h>

typedef struct data_s *data_t;

typedef struct node_s *node_t;

//表示节点中存储的键值对
struct data_s {
	int key;
	void *value;
};

//表示跳表中的节点
struct node_s {
	node_t right;
	node_t down;
	data_t data;	//注意同一列的所有节点都指向同一个data
};

//按照二叉查找树的概率分布随机生成一个节点高度
static inline int
rand_level() {
	int level = 1;
	while(rand()&1) {
		level++;
	}
	return level;
}

//从node右边开始逐层向下查找key对应的键值对
//在某一层找到以后立即返回，以提高查找速度
//node不能为NULL
static inline data_t
search_data(node_t node, int key) {
	for(; node; node = node->down) {
		for(; node->right && key > node->right->data->key; node = node->right);
		//此时node->data->key < key <= node->right->data->key
		if(node->right && key == node->right->data->key) {
			return node->right->data;
		}
	}
	return NULL;
}

//从node右边开始逐层向下查找key对应的键值对，并将垂直路径记录在upadte数组中
//必须走到最底层以后才返回，以便记录完整的update路径
//node和update不能为NULL
static inline data_t
search_data_update(node_t node, int key, node_t *update) {
	for(;; node = node->down) {
		for(; node->right && key > node->right->data->key; node = node->right);
		//node->data->key < key <= node->right->data->key
		//保证当前node一定在目标key的左边，以便remove时更新
		*update++ = node;
		if(!node->down) {
			break;
		}
	}
	if(node->right && key == node->right->data->key) {
		return node->right->data;
	}
	return NULL;
}

//在跳表最顶层上面增加一些空层
//top_left不能为NULL，性能可以改进
static inline int
gain_empty_top_lines(node_t top_left, int count) {
	int i;
	for(i = 0; i < count; i++) {
		node_t tmp;
		tmp = (node_t)malloc(sizeof(struct node_s));
		tmp->right = top_left->right;
		tmp->down = top_left->down;
		top_left->right = NULL;
		top_left->down = tmp;
	}
	return i;
}

//清除跳表最顶层的几个空层
//top_left不能为NULL，性能可以改进
static inline int
clean_empty_top_lines(node_t top_left) {
	int count;
	for(count = 0; !top_left->right; count++) {
		node_t tmp = top_left->down;
		if(!tmp) {
			break;
		}
		top_left->right = tmp->right;
		top_left->down = tmp->down;
		free(tmp);
	}
	return count;
}

//在跳表中为新的键值对增加一列位置
//data和update不能为NULL
static inline void
add_key_column(data_t data, node_t *update, int length) {
	int i;
	for(i=0; i<length; i++) {
		node_t tmp;
		tmp = (node_t)malloc(sizeof(struct node_s));
		tmp->data = http://www.mamicode.com/data;>

跳表的C语言实现，不同于redis版本


联系
我们