跳表（skiplist）是一个非常优秀的数据结构，实现简单，插入、删除、查找的复杂度均为O(logN)。LevelDB的核心数据结构是用跳表实现的，redis的sorted set数据结构也是有跳表实现的。

其结构如下所示：

所有操作均从上向下逐层查找，越上层一次next操作跨度越大。其实现是典型的空间换时间。

具体的细节，可参考维基百科http://en.wikipedia.org/wiki/Skip_list

本文作者将redis的sorted set代码进行整理，将跳表部分的实现抽取出来，供参考。

skiplist.h

#ifndef __SKIPLIST_H
#define __SKIPLIST_H

#define SKIPLIST_MAXLEVEL 8

typedef struct skiplistNode {
? ? double score;
? ? struct skiplistNode *backward;
? ? struct skiplistLevel {
? ? ? ? struct skiplistNode *forward;
? ? }level[];
}skiplistNode;

typedef struct skiplist {
? ? struct skiplistNode *header, *tail;
? ? unsigned long length;
? ? int level;
}skiplist;

#endif

skiplist.c

#include "skiplist.h"
#include
#include

skiplistNode *slCreateNode(int level, double score) {
? ? skiplistNode * sn = malloc(sizeof(*sn) + level*sizeof(struct skiplistLevel));
? ? sn->score = score;
? ? return sn;
}

skiplist *slCreate(void) {
? ? int j;
? ? skiplist *sl;

? ? sl = malloc(sizeof(*sl));
? ? sl->level = 1;
? ? sl->length = 0;
? ? sl->header = slCreateNode(SKIPLIST_MAXLEVEL, 0);
? ? for(j = 0; j < SKIPLIST_MAXLEVEL; j++) {
? ? ? ? sl->header->level[j].forward = NULL;
? ? }
? ? sl->header->backward = NULL;
? ? sl->tail = NULL;
? ? return sl;
}

void slFreeNode(skiplistNode *sn) {
? ? free(sn);
}

void slFree(skiplist *sl) {
? ? skiplistNode *node = sl->header->level[0].forward, *next;

? ? free(sl->header);
? ? while(node) {
? ? ? ? next = node->level[0].forward;
? ? ? ? slFreeNode(node);
? ? ? ? node = next;
? ? }
? ? free(sl);
}

int slRandomLevel(void) {
? ? int level = 1;
? ? while((rand()&0xFFFF) < (0.5 * 0xFFFF))
? ? ? ? level += 1;
? ? return (level < SKIPLIST_MAXLEVEL) ? level : SKIPLIST_MAXLEVEL;
}

skiplistNode *slInsert(skiplist *sl, double score) {
? ? skiplistNode *update[SKIPLIST_MAXLEVEL];
? ? skiplistNode *node;

? ? node = sl->header;
? ? int i, level;
? ? for ( i = sl->level-1; i >= 0; i--) {
? ? ? ? while(node->level[i].forward && node->level[i].forward->score < score) {
? ? ? ? ? ? node = node->level[i].forward;
? ? ? ? }
? ? ? ? update[i] = node;
? ? }
? ? level = slRandomLevel();
? ? if (level > sl->level) {
? ? ? ? for (i = sl->level; i< level ;i++) {
? ? ? ? ? ? update[i] = sl->header;
? ? ? ? }
? ? ? ? sl->level = level;
? ? }
? ? node = slCreateNode(level, score);
? ? for (i = 0; i < level; i++) {
? ? ? ? node->level[i].forward = update[i]->level[i].forward;
? ? ? ? update[i]->level[i].forward = node;
? ? }

? ? node->backward = (update[0] == sl->header? NULL : update[0]);
? ? if (node->level[0].forward)
? ? ? ? node->level[0].forward->backward = node;
? ? else
? ? ? ? sl->tail = node;
? ? sl->length++;
? ? return node;
}

void slDeleteNode(skiplist *sl, skiplistNode *x, skiplistNode **update){
? ? int i;
? ? for (i = 0; i < sl->level; i++) {
? ? ? ? if (update[i]->level[i].forward == x) {
? ? ? ? ? ? update[i]->level[i].forward = x->level[i].forward;
? ? ? ? }
? ? }
? ? if (x->level[0].forward) {
? ? ? ? x->level[0].forward->backward = x->backward;
? ? } else {
? ? ? ? sl->tail = x->backward;
? ? }
? ? while (sl->level > 1 && sl->header->level[sl->level-1].forward == NULL)
? ? ? ? sl->level--;
? ? sl->length--;
}

int slDelete(skiplist *sl, double score) {
? ? skiplistNode *update[SKIPLIST_MAXLEVEL], *node;
? ? int i;

? ? node = sl->header;
? ? for(i = sl->level-1; i >= 0; i--) {
? ? ? ? while (node->level[i].forward && node->level[i].forward->score < score) {
? ? ? ? ? ? node = node->level[i].forward;
? ? ? ? }
? ? ? ? update[i] = node;
? ? }
? ? node = node->level[0].forward;
? ? if (node && score == node->score) {
? ? ? ? slDeleteNode(sl, node, update);
? ? ? ? slFreeNode(node);
? ? ? ? return 1;
? ? } else {
? ? ? ? return 0;
? ? }
? ? return 0;
}

int slSearch(skiplist *sl, double score) {
? ? skiplistNode *node;
? ? int i;