

ddddfang's Blog.

skip-list

ddddfang's Blog.

skip-list

skip-list

字数统计: 5.8k阅读时长: 30 min

 2019/03/19   Share

• 
• 
• 
• 
• 

1. 介绍

http://blog.csdn.net/ict2014/article/details/17394259
类似 并联的链表，意图替代 红黑树 等 平衡树，与红黑树一样是一种 sorted set/map。 在类似排行榜的应用场景中很常见。插入、查找、删除 复杂度亦为 O(logN) （基于概率），内部排序。优势在于实现简单，不用rebalance。与普通链表最大区别在于 每个节点 随机 包含 x 个指向 后继结点的指针而不是固定一个，每次操作率先使用跨度最大的那个 next 指针来寻找后继节点。

https://www.jianshu.com/p/fcd18946994e
链表不可以使用二分查找，因为无法随机访问中间位置的节点。那让某些节点保存那个中间节点？因此可以说skiplist使用了二分查找的思想，但他是 “不完美” 的。理想情况下，skiplist 自顶向下搜索，每下降一层，搜索范围减少一半，达到类似二分查找的效果，效率O(logN)，最坏情况O(N)。
按 key 排序，（上图中 key 就是个 int）
插入时，找 maxlevel 个前驱，新建节点 with level 个next，插入节点。

关于随机生成多少个next节点呢？不可以使用平均分布，因为直觉上，level越大的出现概率应该越小才对，呈 1/2 递减的趋势（1/2 是理想的 二分法效率）。

这个图就是以1/2等比递减的平均每个节点保存两个指针（与红黑树相同），但redis貌似取的1/4等比递减，所以大致是下图这样，然后算得平均每个节点保存1.33个next指针（这个概率的算法见 http://blog.csdn.net/oDaiLiDong/article/details/52782753 ），比红黑树空间占用率还低，操作比红黑树还简单，真要替代红黑树啊。

这个随机函数在skiplist性能上很关键！

http://blog.csdn.net/oDaiLiDong/article/details/52782753
http://blog.csdn.net/Acceptedxukai/article/details/17333673
一个人写的redis 的sliplist相关代码的注释

2. skiplist.h

#ifndef _SKIPLIST_H
#define _SKIPLIST_H

//SKIPLIST_MAX_LEVEL 为 1 则退化为普通的链表
#define SKIPLIST_MAX_LEVEL    32
//理想的二分法的话,p应该是0.5,但是好像0.25-0.5之间性能都差不多
#define SKIPLIST_P    0.25

//gstreamer 里面貌似就是这么用的,basesink.h
typedef struct skipListNode        skipListNode;
typedef struct skipLink            skipLink;
typedef struct skipListManager    skipListManager;

//public 的 struct 放在了.h 文件里,如果是 private,可以将 struct 的定义放在.c
struct skipLink
{
    struct skipLink *next;    //直接指向下一个节点
    struct skipLink *prev;    //直接指向上一个节点
    unsigned int span;    //跨度(next)
};

struct skipListNode
{
    void *key;
    void *val;
    unsigned int level;    //本节点的 level
    skipLink link[0];    //
};

struct skipListManager
{
    unsigned int level;    //max level of skipListNode
    unsigned int count;    //list len
    int (*keyCmp)(const void *p1,const void *p2);    //key 比较函数
    void *(*keyDup)(const void *key);                //key 复制函数
    void *(*valDup)(const void *val);                //val 复制函数
    void (*keyDestructor)(void *key);                //key 销毁
    void (*valDestructor)(void *val);                //val 销毁
    skipLink head[SKIPLIST_MAX_LEVEL];
};

//注意这些接口如果 k/v 当作 int 来用应该使用 8bytes 长度的 int,
//因为我们在内部操作的 k/v 是当作指针来操作的,在64位机器上指针长度为 8bytes!
//这样如果 在栈上定义 4bytes 长度的 int, 有可能会发生踩内存!
//当然这些都是对使用者提出的要求

skipListManager *skipListCreate(int (*keyCmp)(const void *p1,const void *p2),
                                void *(*keyDup)(const void *key),
                                void *(*valDup)(const void *val),
                                void (*keyDestructor)(void *key),
                                void (*valDestructor)(void *val));
void skipListDestroy(skipListManager *pSL);
int skipListInsert(skipListManager *pSL, void *k, void *v,void **vOld,unsigned int *pRank);
int skipListSearch(skipListManager *pSL, void *k, void **v,unsigned int *pRank);
int skipListDelete(skipListManager *pSL, void *k, void **v);
int skipListSearchKth(skipListManager *pSL, unsigned int rank, void **k, void **v);
int skipListDeleteKth(skipListManager *pSL, unsigned int rank, void **k, void **v);


int skipListSearchRangeByKey(skipListManager *pSL, void *keyStart, void *keyEnd,
                        void apply(void *k, void *v,void *cl), void *cl);
int skipListSearchRangeByRank(skipListManager *pSL, unsigned int rankStart, unsigned int rankEnd,
                        void apply(void *k, void *v,void *cl), void *cl);
int skipListDeleteRangeByKey(skipListManager *pSL, void *keyStart, void *keyEnd);
int skipListDeleteRangeByRank(skipListManager *pSL, unsigned int rankStart, unsigned int rankEnd);

void debugPrint(skipListManager *pSL);
void debugPrint2(skipListManager *pSL);

#endif

3. skiplist.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "skiplist.h"

/********* internal default functions **********/
static int keyCmpDefault(const void *p1,const void *p2)
{
    return (int)((long)p1 - (long)p2);
    //return strcmp((const char *)p1,(const char *)p2);
}

static void *keyDupDefault(const void *key)
{
    return (void *)key;
}

static void *valDupDefault(const void *val)
{
    unsigned int len = strlen((const char *)val);
    char *p = (char *)malloc(len+1);
    if(p)
    {
        memset(p,0,len+1);
        memcpy(p,val,len);
    }
    return (void *)p;
}

static void keyDestructorDefault(void *key)
{
    key = key;    //just tell compiler not to report warning
}

static void valDestructorDefault(void *val)
{
    if(val)
        free(val);
}

/********* skipLink related utils functions **********/
static inline void skipLinkInit(skipLink *pLink)
{
    pLink->next = pLink;
    pLink->prev = pLink;
    pLink->span = 0;
}

static inline void skipLinkAdd(skipLink *pInsertPos1,skipLink *pInsertPos2,skipLink *pTarget)
{
    pTarget->next = pInsertPos2;
    pTarget->prev = pInsertPos1;
    pInsertPos1->next = pTarget;
    pInsertPos2->prev = pTarget;
}

static inline void skipLinkDel(skipLink *pTarget)
{
    pTarget->next->prev = pTarget->prev;
    pTarget->prev->next = pTarget->next;
    pTarget->prev = pTarget;
    pTarget->next = pTarget;
}

#define skipLink2Node(ptr, type, member) \
    ((type *)((char *)(ptr) - (size_t)(&((type *)0)->member)))
#define skipLinkEmpty(link)    ((link) == (link)->next)
#define skipLinkHead(link)    ((link)->next)
#define skipLinkTail(link)    ((link)->prev)

/********* internal static functions **********/
static skipListNode *createSkipListNode(skipListManager *psl,void *k,void *v,unsigned int level)
{
    skipListNode *node = (skipListNode *)malloc(sizeof(skipListNode) + level * sizeof(skipLink));
    if(node != NULL)
    {
        node->level = level;
        node->key = (*(psl->keyDup))(k);
        node->val = (*(psl->valDup))(v);
    }
    return node;
}

static void destroySkipListNode(skipListManager *psl,skipListNode *pNode)
{
    (*(psl->keyDestructor))(pNode->key);
    (*(psl->valDestructor))(pNode->val);
    free(pNode);
}

//产生的 level 符合比例系数为 SKIPLIST_P 的等比分布.且最小为 1,最大为 SKIPLIST_MAX_LEVEL
static unsigned int randomLevel()
{
    unsigned int level = 1;
    while (((random() & 0xffff) < 0xffff * SKIPLIST_P) && (level < SKIPLIST_MAX_LEVEL))
        level++;
    return level;
}


/********* public skiplist interface functions **********/
skipListManager *skipListCreate(int (*keyCmp)(const void *p1,const void *p2),
                                void *(*keyDup)(const void *key),
                                void *(*valDup)(const void *val),
                                void (*keyDestructor)(void *key),
                                void (*valDestructor)(void *val))
{
    unsigned int i = 0;
    skipListManager *pSL = (skipListManager *)malloc(sizeof(skipListManager));
    if(pSL != NULL)
    {
        memset(pSL,0,sizeof(skipListManager));
        pSL->level = 1;    //
        pSL->count = 0;    //
        pSL->keyCmp = keyCmp ? keyCmp : keyCmpDefault;
        pSL->keyDup = keyDup ? keyDup : keyDupDefault;
        pSL->valDup = valDup ? valDup : valDupDefault;
        pSL->keyDestructor = keyDestructor ? keyDestructor : keyDestructorDefault;
        pSL->valDestructor = valDestructor ? valDestructor : valDestructorDefault;

        for(i = 0; i < SKIPLIST_MAX_LEVEL; i++)
            skipLinkInit(&pSL->head[i]);
    }
    return pSL;
}

void skipListDestroy(skipListManager *pSL)
{
    skipLink *plink = NULL;
    skipListNode *skipNode = NULL;

    if(!pSL)
        return;
    while(!skipLinkEmpty(&pSL->head[0]))
    {
        plink = skipLinkHead(&pSL->head[0]);
        skipNode = skipLink2Node(plink, skipListNode, link[0]);    //get entry
        skipLinkDel(plink);    //remove from link list
        destroySkipListNode(pSL,skipNode);
        pSL->count--;
    }
    free(pSL);
}

//ret: (0) -> update, (1)->insert, (-1) -> insert fail
int skipListInsert(skipListManager *pSL, void *k, void *v,void **vOld,unsigned int *pRank)
{
    unsigned int newLevel;
    int curLevel;
    unsigned int rank[SKIPLIST_MAX_LEVEL];    //存储节点的排名信息,除了 header 为0外,其他节点从1起始
    skipLink *pLink = NULL;
    skipLink *pLinkNext = NULL;
    skipListNode *pSkipNodeNext = NULL;

    skipLink *update[SKIPLIST_MAX_LEVEL];    //存储插入节点的前驱结点

    curLevel = SKIPLIST_MAX_LEVEL - 1;    //从可能的最高 level 开始搜
    pLink = &pSL->head[curLevel];
    pLinkNext = pLink->next;
    while(curLevel >= 0)
    {
        //从顶开始搜,顶层初始化为 0(说明没降过级),降级不改变排名,因此使用上一级的 rank
        rank[curLevel] = (curLevel == SKIPLIST_MAX_LEVEL-1)?0:rank[curLevel+1];

        while(    (pLinkNext != &pSL->head[curLevel])    //首先保证 curLevel 这条链表非空
            &&    (pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[curLevel])) != NULL
            &&    (*(pSL->keyCmp))(pSkipNodeNext->key,k) < 0    )    //pSkipNodeNext->key < k
        {
            //一旦enter此while循环,排名必然增长啊
            rank[curLevel] += pLink->span;

            pLink = pLinkNext;
            pLinkNext = pLink->next;
        }
        //1.pLink = &pSL->head[curLevel] 导致退出,这一层为空,或者新插入的节点k是最大的
        //2.pSkipNodeNext->key >= key 导致退出
        update[curLevel] = pLink;    //表示如果 new 出来的 level 达到这个高度的话,这一层就插在这个位置后
        if(curLevel-- > 0)
        {    //curLevel 原来已经为0的话,-- 肯定变成-1了,安全起见就不要执行下面这些了
            pLink--;    //去更低的 level 搜索
            pLinkNext = pLink->next;
        }
    }
    //走到这里,pLink 和 pLinkNext 之间理论上就是 level 0 层 新node 应该插入的位置
    //而 rank 应该是其前驱结点的排名
    pLink = update[0];            //所以这一句应该不写也可
    pLinkNext = pLink->next;    //所以这一句应该不写也可
    if(pLinkNext != &pSL->head[0])
    {
        pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[0]);
        if(!(*(pSL->keyCmp))(pSkipNodeNext->key,k))    //found this (k,v)already exists,update
        {
            if(vOld)    //you MUST free val yourself
                *vOld = pSkipNodeNext->val;
            else        //here I free them for you
                (*(pSL->valDestructor))(pSkipNodeNext->val);
            pSkipNodeNext->val = (*(pSL->valDup))(v);
            if(pRank)
                *pRank = rank[0]+1;
            return 0;    //更新.不改变排位信息
        }
    }

    newLevel = randomLevel();
    skipListNode *pskipNodeNew = createSkipListNode(pSL,k,v,newLevel);
    if(!pskipNodeNew)
        return -1;
    if(newLevel > pSL->level)    //
        pSL->level = newLevel;

    for(curLevel=0;curLevel<SKIPLIST_MAX_LEVEL;curLevel++)
    {
        if(curLevel<newLevel)
        {
            skipLinkAdd(update[curLevel],update[curLevel]->next,&(pskipNodeNew->link[curLevel]));
            //rank[curLevel] + update[curLevel]->span 是后继结点的原排名,新排名是 原排名+1, rank[0]+1 是新插入节点的排名
            pskipNodeNew->link[curLevel].span = rank[curLevel] + update[curLevel]->span - rank[0];    //后继结点的新排名-新插入节点的排名
            update[curLevel]->span = rank[0] - rank[curLevel] + 1;    //更新前驱结点跨度=新插入节点的排名-前驱结点的排名,后继结点的跨度不变
        }
        else
        {
            //所有前驱结点跨度++
            update[curLevel]->span++;
        }
    }
    if(pRank)
        *pRank = rank[0]+1;
    pSL->count++;
    return 1;
}

//ret: (0) -> no such node, (1)->found it, (-1)->search error
int skipListSearch(skipListManager *pSL, void *k, void **v,unsigned int *pRank)
{
    int curLevel;
    int rank;
    skipLink *pLink = NULL;
    skipLink *pLinkNext = NULL;
    skipListNode *pSkipNodeNext = NULL;

    curLevel = SKIPLIST_MAX_LEVEL - 1;
    pLink = &pSL->head[curLevel];
    pLinkNext = pLink->next;
    rank = 0;
    while(curLevel >= 0)
    {
        while(    (pLinkNext != &pSL->head[curLevel])    //首先保证 curLevel 这条链表非空
            &&    (pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[curLevel])) != NULL
            &&    (*(pSL->keyCmp))(pSkipNodeNext->key,k) < 0    )    //pSkipNodeNext->key < k
        {
            rank += pLink->span;

            pLink = pLinkNext;
            pLinkNext = pLink->next;
        }
        if(curLevel-- > 0)
        {    //curLevel 原来已经为0的话,-- 肯定变成-1了,安全起见就不要执行下面这些了
            pLink--;    //去更低的 level 搜索,rank 不变
            pLinkNext = pLink->next;
        }
    }
    if(pLinkNext != &pSL->head[0])
    {
        pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[0]);
        if(!(*(pSL->keyCmp))(pSkipNodeNext->key,k))    //find it !
        {
            if(v)    //you MUST free val yourself
                *v = (*(pSL->valDup))(pSkipNodeNext->val);
            if(pRank)
                *pRank = rank+1;    //此时的 rank 拿着的还是前驱结点的排名
            return 1;
        }
    }
    if(pRank)
        *pRank = rank;    //直接返回前驱结点的排名
    return 0;
}

//ret: (0) -> no such node, (1)->delete ok, (-1)->delete error
int skipListDelete(skipListManager *pSL, void *k, void **v)
{
    unsigned int remainLevel;
    int curLevel;
    skipLink *pLink = NULL;
    skipLink *pLinkNext = NULL;
    skipListNode *pSkipNodeNext = NULL;

    skipLink *update[SKIPLIST_MAX_LEVEL];

    curLevel = SKIPLIST_MAX_LEVEL - 1;
    pLink = &pSL->head[curLevel];
    pLinkNext = pLink->next;
    while(curLevel >= 0)
    {
        while(    (pLinkNext != &pSL->head[curLevel])    //首先保证 curLevel 这条链表非空
            &&    (pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[curLevel])) != NULL
            &&    (*(pSL->keyCmp))(pSkipNodeNext->key,k) < 0    )    //pSkipNodeNext->key < k
        {
            pLink = pLinkNext;
            pLinkNext = pLink->next;
        }
        update[curLevel] = pLink;    //记录本节点前驱结点
        if(curLevel-- > 0)
        {    //curLevel 原来已经为0的话,-- 肯定变成-1了,安全起见就不要执行下面这些了
            pLink--;    //去更低的 level 搜索
            pLinkNext = pLink->next;
        }
    }
    pLink = update[0];            //这一句不写也可
    pLinkNext = pLink->next;    //这一句不写也可
    if(pLinkNext != &pSL->head[0])
    {
        pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[0]);
        if(!(*(pSL->keyCmp))(pSkipNodeNext->key,k))    //find it !
        {
            remainLevel = pSL->level;
            //走到这里说明 pLinkNext 正是待删节点 第0层的 link
            for(curLevel = 0; curLevel < SKIPLIST_MAX_LEVEL; curLevel++)
            {
                if(curLevel < pSkipNodeNext->level)    //将此节点从 link 中删除
                {
                    if(pLinkNext->next == &pSL->head[curLevel])    //说明这个高度就没有其他节点了
                        remainLevel = curLevel;    //curLevel 对应的 level 是 curLevel+1
                    update[curLevel]->span += pLinkNext->span - 1;    //前驱结点继承本节点的跨度
                    skipLinkDel(pLinkNext);
                    pLinkNext++;    //去更高一层删除
                }
                else
                {
                    //前驱结点跨度--
                    update[curLevel]->span--;
                }
            }
            if(v)    //you MUST free val yourself
                *v = pSkipNodeNext->val;
            else    //here I free them for you
                (*(pSL->valDestructor))(pSkipNodeNext->val);
            (*(pSL->keyDestructor))(pSkipNodeNext->key);
            free(pSkipNodeNext);
            pSL->level = remainLevel;
            pSL->count--;
            return 1;
        }
    }
    return 0;
}

//查找第k个元素 (0) -> no such node, (1)-> search ok, (-1) -> error
int skipListSearchKth(skipListManager *pSL, unsigned int rank, void **k, void **v)
{
    int curLevel;
    int r;
    skipLink *pLink = NULL;
    skipListNode *pSkipNode = NULL;

    if(rank > pSL->count || rank <= 0)
        return 0;    //no such node

    curLevel = SKIPLIST_MAX_LEVEL - 1;
    pLink = &pSL->head[curLevel];
    r = 0;
    while(curLevel >= 0)
    {
        //r + pLink->span 是 pLink 后一个节点的 rank
        while((pLink->next != &pSL->head[curLevel]) && (r + pLink->span < rank))
        {
            r += pLink->span;
            pLink = pLink->next;
        }
        if(curLevel-- > 0)
            pLink--;    //去更低的 level 搜索,rank 不变,curLevel 原已为0时不执行这句
    }
    //走到这里 pLink 应该身处 level 0 且排名为 rank-1
    pLink = pLink->next;
    if(pLink != &pSL->head[0])
    {
        pSkipNode = skipLink2Node(pLink, skipListNode, link[0]);
        if(k)    //you MUST free key yourself
            *k = (*(pSL->keyDup))(pSkipNode->key);
        if(v)    //you MUST free val yourself
            *v = (*(pSL->valDup))(pSkipNode->val);
        return 1;
    }
    return 0;
}

//删除第k个元素
int skipListDeleteKth(skipListManager *pSL, unsigned int rank, void **k, void **v)
{
    int r;
    int curLevel;
    unsigned int remainLevel;
    skipLink *pLink = NULL;
    skipListNode *pSkipNode = NULL;

    skipLink *update[SKIPLIST_MAX_LEVEL];

    if(rank > pSL->count || rank <= 0)
        return 0;    //no such node

    curLevel = SKIPLIST_MAX_LEVEL - 1;
    pLink = &pSL->head[curLevel];
    r = 0;
    while(curLevel >= 0)
    {
        while((pLink->next != &pSL->head[curLevel]) && (r + pLink->span < rank))
        {
            r += pLink->span;
            pLink = pLink->next;
        }
        update[curLevel] = pLink;    //记录前驱结点
        if(curLevel-- > 0)
        {    //curLevel 原来已经为0的话,-- 肯定变成-1了,安全起见就不要执行下面这些了
            pLink--;    //去更低的 level 搜索
        }
    }
    pLink = pLink->next;    //待删节点
    if(pLink != &pSL->head[0])
    {
        remainLevel = pSL->level;
        pSkipNode = skipLink2Node(pLink, skipListNode, link[0]);
        for(curLevel = 0; curLevel < SKIPLIST_MAX_LEVEL; curLevel++)
        {
            if(curLevel < pSkipNode->level)    //将此节点从 link 中删除
            {
                if(pLink->next == &pSL->head[curLevel])    //说明这个高度就没有其他节点了
                    remainLevel = curLevel;    //curLevel 对应的 level 是 curLevel+1
                update[curLevel]->span += pLink->span - 1;    //前驱结点继承本节点的跨度
                skipLinkDel(pLink);
                pLink++;    //去更高一层删除
            }
            else
            {
                //前驱结点跨度--
                update[curLevel]->span--;
            }
        }
        if(k)    //you MUST free key yourself
            *k = pSkipNode->key;
        else    //here I free them for you
            (*(pSL->keyDestructor))(pSkipNode->key);
        if(v)    //you MUST free val yourself
            *v = pSkipNode->val;
        else    //here I free them for you
            (*(pSL->valDestructor))(pSkipNode->val);
        free(pSkipNode);
        pSL->level = remainLevel;
        pSL->count--;
        return 1;
    }
    return 0;
}

//在(keyStart,keyEnd) 与 (rankStart,rankEnd)的交集上 search, 同时,不考虑范围非法的情况
static int skipListIterRange(skipListManager *pSL, void *keyStart, void *keyEnd,
                                unsigned int rankStart, unsigned int rankEnd,
                                void iterApply(skipListNode *pSkipNode,void *cl), void *cl)
{
    int curLevel;
    int rank;
    skipLink *pLink = NULL;
    skipLink *pLinkNext = NULL;
    skipListNode *pSkipNodeNext = NULL;

    curLevel = SKIPLIST_MAX_LEVEL - 1;
    pLink = &pSL->head[curLevel];
    pLinkNext = pLink->next;
    rank = 0;
    while(curLevel >= 0)
    {
        while(    (pLinkNext != &pSL->head[curLevel])    //首先保证 curLevel 这条链表非空
            &&    (pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[curLevel])) != NULL
            &&    ((*(pSL->keyCmp))(pSkipNodeNext->key,keyStart) < 0 || rank + pLink->span < rankStart))
        {
            rank += pLink->span;

            pLink = pLinkNext;
            pLinkNext = pLink->next;
        }
        if(curLevel-- > 0)
        {    //curLevel 原来已经为0的话,-- 肯定变成-1了,安全起见就不要执行下面这些了
            pLink--;    //去更低的 level 搜索,rank 不变
            pLinkNext = pLink->next;
        }
    }
    //走到这里 pLinkNext 就是第一个在范围内的节点,其排名为 rank + pLink->span
    //且 curLevel= -1,我们身处最底层次的那个链表上
    rank += pLink->span;
    curLevel = 0;    //到这里 curLevel 看起来没啥用了,我们就让他来计数吧

    while(    (pLinkNext != &pSL->head[0])    //首先保证 curLevel 这条链表非空
        &&    (pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[0])) != NULL
        &&    (*(pSL->keyCmp))(pSkipNodeNext->key,keyEnd) <= 0
        &&    rank++ <= rankEnd    )
    {
        pLink = pLinkNext->next;    //反正走到这里 pLink 就没多大作用了,用它备份 pLinkNext 的下一个节点
        iterApply(pSkipNodeNext, cl);    //外面传进来的那个apply函数指针可以放在cl里面啊
        //用 pLink 确保链表不会断掉,因为我们允许 apply 吧 pSkipNodeNext 删掉(虽然不如直接调用 skipListDeleteRange 来的高效)!
        pLinkNext = pLink;
        curLevel++;
    }
    return curLevel;
}

typedef struct
{
    void *p1;
    void *p2;
} privateData;

static void iterApplySearch(skipListNode *pSkipNode,void *cl)
{
    typedef void (*usrApply)(void *k, void *v,void *cl);
    privateData *pcl = (privateData *)cl;

    usrApply apply = (usrApply)(pcl->p1);
    void *userCl = pcl->p2;
    apply(pSkipNode->key,pSkipNode->val,userCl);
}

//查找某个范围的元素,对所有符合条件的元素只读式调用 apply 函数
int skipListSearchRangeByKey(skipListManager *pSL, void *keyStart, void *keyEnd,
                        void apply(void *k, void *v,void *cl), void *cl)
{
    privateData localCl;
    localCl.p1 = (void *)apply;
    localCl.p2 = cl;
    return skipListIterRange(pSL, keyStart, keyEnd, 1, pSL->count, iterApplySearch, &localCl);
}

//查找某个范围的元素,对所有符合条件的元素只读式调用 apply 函数
int skipListSearchRangeByRank(skipListManager *pSL, unsigned int rankStart, unsigned int rankEnd,
                        void apply(void *k, void *v,void *cl), void *cl)
{
    privateData localCl;
    localCl.p1 = (void *)apply;
    localCl.p2 = cl;
    skipLink *pLink = NULL;
    skipListNode *pSkipNodeFirst = NULL;
    skipListNode *pSkipNodeLast = NULL;

    if(skipLinkEmpty(&pSL->head[0]))
        return 0;
    pLink = skipLinkHead(&pSL->head[0]);
    pSkipNodeFirst = skipLink2Node(pLink, skipListNode, link[0]);
    pLink = skipLinkTail(&pSL->head[0]);
    pSkipNodeLast = skipLink2Node(pLink, skipListNode, link[0]);
    return skipListIterRange(pSL, pSkipNodeFirst->key, pSkipNodeLast->key, rankStart, rankEnd, iterApplySearch, &localCl);
}


//删除某个范围的元素
int skipListDeleteRangeByKey(skipListManager *pSL, void *keyStart, void *keyEnd)
{
    int curLevel;
    int cnt;
    unsigned int remainLevel;
    skipLink *pLink = NULL;
    skipLink *pLinkNext = NULL;
    skipListNode *pSkipNodeNext = NULL;

    skipLink *update[SKIPLIST_MAX_LEVEL];

    curLevel = SKIPLIST_MAX_LEVEL - 1;
    pLink = &pSL->head[curLevel];
    pLinkNext = pLink->next;
    while(curLevel >= 0)
    {
        while(    (pLinkNext != &pSL->head[curLevel])    //首先保证 curLevel 这条链表非空
            &&    (pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[curLevel])) != NULL
            &&    (*(pSL->keyCmp))(pSkipNodeNext->key,keyStart) < 0    )    //pSkipNodeNext->key < k
        {
            pLink = pLinkNext;
            pLinkNext = pLink->next;
        }
        update[curLevel] = pLink;    //记录本节点前驱结点
        if(curLevel-- > 0)
        {    //curLevel 原来已经为0的话,-- 肯定变成-1了,安全起见就不要执行下面这些了
            pLink--;    //去更低的 level 搜索
            pLinkNext = pLink->next;
        }
    }
    pLinkNext = update[0]->next;    //这一句不写也可,pLinkNext 现在就是第一个在范围内的节点
    cnt = 0;
    while(    (pLinkNext != &pSL->head[0])    //首先保证 curLevel 这条链表非空
        &&    (pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[0])) != NULL
        &&    (*(pSL->keyCmp))(pSkipNodeNext->key,keyEnd) <= 0 )
    {
        pLink = pLinkNext->next;    //保存下一个节点
        //删节点
        remainLevel = pSL->level;
        for(curLevel = 0; curLevel < SKIPLIST_MAX_LEVEL; curLevel++)
        {
            if(curLevel < pSkipNodeNext->level)    //将此节点从 link 中删除
            {
                if(pLinkNext->next == &pSL->head[curLevel])    //说明这个高度就没有其他节点了
                    remainLevel = curLevel;    //curLevel 对应的 level 是 curLevel+1
                update[curLevel]->span += pLinkNext->span - 1;    //前驱结点继承本节点的跨度
                skipLinkDel(pLinkNext);
                pLinkNext++;    //去更高一层删除
            }
            else
            {
                //前驱结点跨度--
                update[curLevel]->span--;
            }
        }
        (*(pSL->valDestructor))(pSkipNodeNext->val);
        (*(pSL->keyDestructor))(pSkipNodeNext->key);
        free(pSkipNodeNext);
        pSL->level = remainLevel;
        pSL->count--;
        cnt++;
        pLinkNext = pLink;    //
    }
    return cnt;
}

//删除某个范围的元素
int skipListDeleteRangeByRank(skipListManager *pSL, unsigned int rankStart, unsigned int rankEnd)
{
    int rank;
    int curLevel;
    unsigned int remainLevel;
    int cnt;
    skipLink *pLink = NULL;
    skipLink *pLinkNext = NULL;
    skipListNode *pSkipNodeNext = NULL;

    skipLink *update[SKIPLIST_MAX_LEVEL];

    curLevel = SKIPLIST_MAX_LEVEL - 1;
    pLink = &pSL->head[curLevel];
    pLinkNext = pLink->next;
    rank = 0;
    while(curLevel >= 0)
    {
        while(    (pLinkNext != &pSL->head[curLevel])    //首先保证 curLevel 这条链表非空
            &&    (pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[curLevel])) != NULL
            &&    (rank + pLink->span < rankStart)    )    //
        {
            rank += pLink->span;
            pLink = pLinkNext;
            pLinkNext = pLink->next;
        }
        update[curLevel] = pLink;    //记录本节点前驱结点
        if(curLevel-- > 0)
        {    //curLevel 原来已经为0的话,-- 肯定变成-1了,安全起见就不要执行下面这些了
            pLink--;    //去更低的 level 搜索
            pLinkNext = pLink->next;
        }
    }
    pLinkNext = update[0]->next;    //这一句不写也可,pLinkNext 现在就是第一个在范围内的节点
    rank += update[0]->span;        //rank 现在是 pLinkNext 的 rank
    cnt = 0;
    while(    (pLinkNext != &pSL->head[0])    //首先保证 curLevel 这条链表非空
        &&    (pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[0])) != NULL
        &&    (rank++ <= rankEnd) )
    {
        pLink = pLinkNext->next;    //保存下一个节点
        //删节点
        remainLevel = pSL->level;
        for(curLevel = 0; curLevel < SKIPLIST_MAX_LEVEL; curLevel++)
        {
            if(curLevel < pSkipNodeNext->level)    //将此节点从 link 中删除
            {
                if(pLinkNext->next == &pSL->head[curLevel])    //说明这个高度就没有其他节点了
                    remainLevel = curLevel;    //curLevel 对应的 level 是 curLevel+1
                update[curLevel]->span += pLinkNext->span - 1;    //前驱结点继承本节点的跨度
                skipLinkDel(pLinkNext);
                pLinkNext++;    //去更高一层删除
            }
            else
            {
                //前驱结点跨度--
                update[curLevel]->span--;
            }
        }
        (*(pSL->valDestructor))(pSkipNodeNext->val);
        (*(pSL->keyDestructor))(pSkipNodeNext->key);
        free(pSkipNodeNext);
        pSL->level = remainLevel;
        pSL->count--;
        cnt++;
        pLinkNext = pLink;    //
    }
    return cnt;
}


/********* some skiplist debug functions **********/
void debugPrint(skipListManager *pSL)
{
    unsigned int rank;
    int i;
    int maxLevel = 0;
    int levelStat[SKIPLIST_MAX_LEVEL] = {0};
    skipLink *pLink = NULL;
    skipLink *pLinkNext = NULL;
    skipListNode *pSkipNodeNext = NULL;
    skipLink *pLinkNextTmp = NULL;

    pLink = &pSL->head[0];
    pLinkNext = pLink->next;
    pLinkNextTmp = pLinkNext;

    rank = 1;
    while(pLinkNext != &pSL->head[0])
    {
        pSkipNodeNext = skipLink2Node(pLinkNext, skipListNode, link[0]);

        //更新统计信息
        if(pSkipNodeNext->level > maxLevel)
            maxLevel = pSkipNodeNext->level;
        levelStat[pSkipNodeNext->level - 1]++;

        //打印这个节点的信息
        printf("rank %u, (%ld,%s)",rank,(long)(pSkipNodeNext->key),(char *)(pSkipNodeNext->val));
        for(i=0;i<pSkipNodeNext->level;i++)
        {
            printf(" <span %u>",pLinkNextTmp->span);
            pLinkNextTmp++;
        }
        printf("\n");

        //next
        pLink = pLinkNext;
        pLinkNext = pLink->next;
        pLinkNextTmp = pLinkNext;
        rank++;
    }
    printf("maxlevel is %d\n",maxLevel);
    for(i=0;i<maxLevel;i++)
    {
        printf("level %d has %d elements\n",i+1,levelStat[i]);
    }
}

static void iterApplyDebug(skipListNode *pSkipNode,void *cl)
{
    int i;
    privateData *pcl = (privateData *)cl;
    int *maxLevel = (int *)(pcl->p1);
    int *levelStat = (int *)(pcl->p2);
    skipLink *pSkipNodeTmp = &pSkipNode->link[0];

    //统计信息
    if(pSkipNode->level > *maxLevel)
        *maxLevel = pSkipNode->level;
    levelStat[pSkipNode->level - 1]++;

    //打印这个节点的信息
    printf("(%ld,%s)",(long)(pSkipNode->key),(char *)(pSkipNode->val));
    for(i=0;i<pSkipNode->level;i++)
    {
        printf(" <span %u>",pSkipNodeTmp->span);
        pSkipNodeTmp++;
    }
    printf("\n");
}

void debugPrint2(skipListManager *pSL)
{
    int i;
    static int maxLevel = 0;
    static int levelStat[SKIPLIST_MAX_LEVEL] = {0};
    privateData localCl;
    localCl.p1 = (void *)&maxLevel;
    localCl.p2 = (void *)levelStat;

    skipLink *pLink = NULL;
    skipListNode *pSkipNodeFirst = NULL;
    skipListNode *pSkipNodeLast = NULL;

    if(skipLinkEmpty(&pSL->head[0]))
        return;
    pLink = skipLinkHead(&pSL->head[0]);
    pSkipNodeFirst = skipLink2Node(pLink, skipListNode, link[0]);
    pLink = skipLinkTail(&pSL->head[0]);
    pSkipNodeLast = skipLink2Node(pLink, skipListNode, link[0]);
    skipListIterRange(pSL, pSkipNodeFirst->key, pSkipNodeLast->key, 1, pSL->count, iterApplyDebug, &localCl);

    printf("maxlevel is %d\n",maxLevel);
    for(i=0;i<maxLevel;i++)
    {
        printf("level %d has %d elements\n",i+1,levelStat[i]);
    }
    return;
}

4. test.c

//以下是skiplist的测试
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "skiplist.h"


int skipList_test1()
{
    char v[50] = {0};
    long i=0;
    skipListManager *psl = skipListCreate(NULL,NULL,NULL,NULL,NULL);

    for(i=0;i<1000;i++)
    {
        sprintf(v,"val_%ld",i);
        printf("ins (%ld,%s)\n",i,v);
        skipListInsert(psl, (void *)i, (void *)v,NULL,NULL);
    }
    printf("ins complete,press enter to continue\n");
    getchar();

    skipListDelete(psl, (void *)560, NULL);

    for(i=555;i<575;i++)
    {
        char *deletedVal = NULL;
        int delRes = skipListDelete(psl, (void *)i, (void *)&deletedVal);
        if(delRes == 0)
        {
            printf("cannot find element,key=%ld,need confirm\n",i);
            getchar();
        }
        else if(delRes == 1)
        {
            printf("element deleted,(%ld,%s)\n",i,deletedVal);
        }
        free(deletedVal);
    }
    printf("del complete,press enter to continue\n");
    getchar();

    skipListInsert(psl, (void *)123, "hello fang~ ",NULL,NULL);

    for(i=0;i<1000;i++)
    {
        sprintf(v,"val_%ld",i);
        char *searchedVal = NULL;
        int searchRes = skipListSearch(psl, (void *)i, (void *)&searchedVal,NULL);
        if(searchRes == 0)
        {
            printf("cannot find element,key=%ld,need confirm\n",i);
            getchar();
        }
        else if(searchRes > 0)
        {
            if(strcmp(searchedVal,v)!=0)
            {
                printf("find element,key=%ld,v=%s(modified ?),need confirm\n",i,searchedVal);
                getchar();
            }
            else
            {
                printf("find element,(%ld,%s)\n",i,searchedVal);
            }
        }
        free(searchedVal);
    }
    printf("search complete,press enter to continue\n");
    getchar();
    debugPrint(psl);
    skipListDestroy(psl);
    return 0;
}

int skipList_test2()
{
    unsigned int rank;
    char v[50] = {0};
    long i=0;
    skipListManager *psl = skipListCreate(NULL,NULL,NULL,NULL,NULL);

    for(i=0;i<1000;i++)
    {
        sprintf(v,"val_%ld",i);
        //这里吧i当作指针传入其实都是有风险的,因为 skipListInsert 可能操作 以i起始的 8 bytes(但是i其实只占用4bytes)
        skipListInsert(psl, (void *)i, (void *)v,NULL,&rank);
        printf("ins (%ld,%s) in pos %u\n",i,v,rank);
    }
    printf("ins complete,press enter to continue\n");
    getchar();

    skipListDelete(psl, (void *)560, NULL);
    for(i=1;i<=1000;i++)
    {
        void *searchedKey = 0;
        void *searchedVal = NULL;
        int searchRes = skipListSearchKth(psl,i,&searchedKey,&searchedVal);
        if(searchRes == 0)
        {
            printf("cannot find element,rank=%ld,need confirm\n",i);
            getchar();
        }
        else if(searchRes > 0)
        {
            printf("find element,rank %ld is (%ld,%s)\n",i,(long)searchedKey,(char *)searchedVal);
        }
        free(searchedVal);
    }
    printf("search complete,press enter to continue\n");
    getchar();

    for(i=1;i<=15;i++)
    {
        void *deletedKey = 0;
        void *deletedVal = NULL;
        int deleteRes = skipListDeleteKth(psl, 20, &deletedKey, &deletedVal);
        if(deleteRes == 0)
        {
            printf("cannot find element,need confirm\n");
            getchar();
        }
        else
        {
            printf("del rank 20 element,(%ld,%s)\n",(long)deletedKey,(char *)deletedVal);
        }
    }
    printf("del complete,press enter to continue\n");
    getchar();
    debugPrint(psl);
    skipListDestroy(psl);
    return 0;
}

static void myapply1(void *k, void *v,void *cl)
{
    printf("hi,(%ld,%s)\n",(long)k,(char *)v);
}
static void myapply2(void *k, void *v,void *cl)
{
    if(cl == NULL)
    {
        //
    }
    skipListManager *psl = cl;
    //printf("hi,(%ld,%s)\n",(long)k,(char *)v);
    skipListDelete(psl, k, NULL);
}

int skipList_test3()
{
    unsigned int rank;
    char v[50] = {0};
    long i=0;
    skipListManager *psl = skipListCreate(NULL,NULL,NULL,NULL,NULL);

    for(i=0;i<100;i++)
    {
        sprintf(v,"val_%ld",i);
        skipListInsert(psl, (void *)i, (void *)v,NULL,&rank);
        printf("ins (%ld,%s) in pos %u\n",i,v,rank);
    }
    printf("ins complete,press enter to show\n");
    getchar();
    debugPrint(psl);
    printf("press enter to continue\n");
    getchar();

    skipListSearchRangeByKey(psl,(void *)10,(void *)15,myapply1,(void *)psl);
    printf("search range by rank,actual del ops,press enter to show\n");
    getchar();
    debugPrint(psl);
    printf("press enter to continue\n");
    getchar();

    skipListSearchRangeByRank(psl,34,55,myapply2,(void *)psl);
    printf("search range by key,press enter to show\n");
    getchar();
    debugPrint(psl);
    printf("press enter to continue\n");
    getchar();


    skipListDeleteRangeByRank(psl, 5, 100);
    printf("press enter to continue\n");
    getchar();

    debugPrint2(psl);
    skipListDestroy(psl);
    return 0;
}

原文作者：ddddfang

原文链接：https://ddddfang.github.io/2019/03/19/skip-list/

发表日期：March 19th 2019, 6:46:40 pm

更新日期：March 19th 2019, 7:14:30 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

• Previous Post
  union-find-set

Powered by Hexotheme Archer

PV: :)

CATALOG

1. 1. 1. 介绍
2. 2. 2. skiplist.h
3. 3. 3. skiplist.c
4. 4. 4. test.c



• Archive
• Tag
• Cate

Total : 42

2019

• 03/19union-find-set
• 03/19skip-list
• 03/08cpp-shared_ptr
• 02/19swig
• 02/18cpp---sequential-container
• 02/15caffe-ubuntu14-gpu
• 02/15cpp---key-val-set
• 02/14learn-caffe-code
• 02/14cpp---define
• 02/13cpp---sort
• 02/13max-heap
• 02/11hash-table
• 02/11binary-search
• 01/31bit-set
• 01/31gitbook
• 01/30list
• 01/30rb-tree
• 01/30caffe
• 01/30cmake
• 01/30docker-apps
• 01/30printf-可变参数
• 01/30sort-related
• 01/30docker-hub
• 01/30杂谈
• 01/30docker-file
• 01/29makefile2
• 01/28perforce
• 01/28makefile
• 01/28static-dynamic-library
• 01/28使用github
• 01/28vim
• 01/23ubuntu-release
• 01/23dd
• 01/23disk ===> fdisk mount df
• 01/23sed
• 01/23shell
• 01/23xxd
• 01/22gdb
• 01/11git
• 01/11docker-basic
• 01/03ffmpeg学习资料
• 01/03hexo-blog

binary-search bitmap caffe c++ 单例模式 common misc makefile 宏 顺序容器 智能指针 排序 shell linux command docker blog ffmpeg gdb gitbook p4 printf 可变参数 static and dynamic library 第k小的数 ubuntu setup 并查集 git draw.io markdown vscode office2016 密钥 键值对集合 链表 最大堆(大顶堆) swig python c vim 红黑树 skip-list hash-table



缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是archer根目录）执行以下命令：
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置：

jsonContent:
  meta: false
  pages: false
  posts:
    title: true
    date: true
    path: true
    text: false
    raw: false
    content: false
    slug: false
    updated: false
    comments: false
    link: false
    permalink: false
    excerpt: false
    categories: true
    tags: true

algorithm-and-data-struct caffe common-misc cpp linux-daily ffmpeg

