跳表（skiplist）的代码实现

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

其结构如下所示：

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

具体的细节，可参考维基百科

本文作者将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[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;