跳表（skiplist）的代码实现

跳表（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 <stdlib.h>

#include <stdio.h>

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.forward && node->level.forward->score < score