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

浏览数：32 / 时间：2015年06月08日

本来跳表的原理是很简单的（相对于红黑树），但是国庆节断断续续搞了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 = data;
		tmp->right = update[i]->right;
		update[i]->right = tmp;
	}
	for(i=0; i<length-1; i++) {
		update[i]->right->down = update[i+1]->right;
	}
	update[length-1]->right->down = NULL;
}

//在跳表中删除key所在的列
//update不能为NULL
static inline void
remove_key_column(int key, node_t *update, int length) {
	int i;
	for(i = 0; i < length; i++) {
		node_t right = update[i]->right;
		if(right && right->data->key == key) {
			update[i]->right = right->right;
			free(right);
		}
	}
}

//释放节点并返回它的下一个（右边或下边）节点
static inline node_t
free_and_next(node_t node, node_t next) {
	free(node);
	return next;
}

struct skip_list_s {
	struct node_s top_left;	//跳表左上角的节点
	int level;	//跳表层数
	int count;	//跳表中键值对的数量
};

skip_list_t
skip_list_create() {
	skip_list_t sl;
	sl = (skip_list_t)malloc(sizeof(struct skip_list_s));
	sl->top_left.right = NULL;
	sl->top_left.down = NULL;
	sl->level = 1;
	sl->count = 0;
	return sl;
}

void
skip_list_destroy(skip_list_t sl) {
	node_t left, node;
	for(left = &sl->top_left; left->down; left = left->down) {
		for(node = left->right; node; node = free_and_next(node, node->right));
	}
	for(node = left->right; node; node = free_and_next(node, node->right));
	for(left = sl->top_left.down; left; left = free_and_next(left, left->down));
	free(sl);
}

void*
skip_list_get(skip_list_t sl, int key) {
	data_t data;
	data = search_data(&sl->top_left, key);
	if(data) {
		return data->value;
	}
	return NULL;
}


void*
skip_list_put(skip_list_t sl, int key, void *value) {
	void *old_value = NULL;
	data_t data;
	data = search_data(&sl->top_left, key);
	if(data) {
		old_value = data->value;
		data->value = value;
	} else {
		node_t *update;
		int target_level;
		target_level = rand_level();
		if(target_level > sl->level) {
			sl->level += gain_empty_top_lines(&sl->top_left, target_level-sl->level);
		}
		update = (node_t*)malloc(sizeof(node_t)*sl->level);
		search_data_update(&sl->top_left, key, update);
		data = (data_t)malloc(sizeof(struct data_s));
		data->key = key;
		data->value = value;
		//target_level<=sl->level
		add_key_column(data, update+(sl->level-target_level), target_level);
		free(update);
		sl->count++;
	}
	return old_value;
}

void*
skip_list_remove(skip_list_t sl, int key) {
	void *old_value = NULL;
	node_t *update;
	data_t data;
	update = (node_t*)malloc(sizeof(node_t)*sl->level);
	data = search_data_update(&sl->top_left, key, update);
	if(data) {
		//删除key所在列
		remove_key_column(key, update, sl->level);
		//清除掉删除key所在列以后上面出现的空行
		sl->level -= clean_empty_top_lines(&sl->top_left);
		old_value = data->value;
		free(data);
		sl->count--;
	}
	free(update);
	return old_value;
}

int
skip_list_contains(skip_list_t sl, int key) {
	return !!search_data(&sl->top_left, key);
}


int
skip_list_count(skip_list_t sl) {
	return sl->count;
}

int
skip_list_key_set(skip_list_t sl, int keys[], int length) {
	int i;
	node_t left, node;
	for(left = &sl->top_left; left->down; left = left->down);
	for(i = 0, node = left->right; i<length && node; i++, node = node->right) {
		keys[i] = node->data->key;
	}
	return i;
}

int
skip_list_value_set(skip_list_t sl, void *values[], int length) {
	int i;
	node_t left, node;
	for(left = &sl->top_left; left->down; left = left->down);
	for(i = 0, node = left->right; i<length && node; i++, node = node->right) {
		values[i] = node->data->value;
	}
	return i;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢