1. 首页
  2. 文章中心
  3. 数据结构与算法

skip-list

59 阅读 0 评论
我是靠谱客的博主 无限手链，最近开发中收集的这篇文章主要介绍skip-list，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1. 介绍

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

skip-list
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 是理想的 二分法效率）。

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

skip-list-random
这个随机函数在skiplist性能上很关键！

skip-list
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 %dn",maxLevel);
for(i=0;i<maxLevel;i++)
{
printf("level %d has %d elementsn",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 %dn",maxLevel);
for(i=0;i<maxLevel;i++)
{
printf("level %d has %d elementsn",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 continuen");
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 confirmn",i);
getchar();
}
else if(delRes == 1)
{
printf("element deleted,(%ld,%s)n",i,deletedVal);
}
free(deletedVal);
}
printf("del complete,press enter to continuen");
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 confirmn",i);
getchar();
}
else if(searchRes > 0)
{
if(strcmp(searchedVal,v)!=0)
{
printf("find element,key=%ld,v=%s(modified ?),need confirmn",i,searchedVal);
getchar();
}
else
{
printf("find element,(%ld,%s)n",i,searchedVal);
}
}
free(searchedVal);
}
printf("search complete,press enter to continuen");
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 %un",i,v,rank);
}
printf("ins complete,press enter to continuen");
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 confirmn",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 continuen");
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 confirmn");
getchar();
}
else
{
printf("del rank 20 element,(%ld,%s)n",(long)deletedKey,(char *)deletedVal);
}
}
printf("del complete,press enter to continuen");
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 %un",i,v,rank);
}
printf("ins complete,press enter to shown");
getchar();
debugPrint(psl);
printf("press enter to continuen");
getchar();
skipListSearchRangeByKey(psl,(void *)10,(void *)15,myapply1,(void *)psl);
printf("search range by rank,actual del ops,press enter to shown");
getchar();
debugPrint(psl);
printf("press enter to continuen");
getchar();
skipListSearchRangeByRank(psl,34,55,myapply2,(void *)psl);
printf("search range by key,press enter to shown");
getchar();
debugPrint(psl);
printf("press enter to continuen");
getchar();
skipListDeleteRangeByRank(psl, 5, 100);
printf("press enter to continuen");
getchar();
debugPrint2(psl);
skipListDestroy(psl);
return 0;
}

 

最后

以上就是无限手链为你收集整理的skip-list的全部内容，希望文章能够帮你解决skip-list所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(39)

相关文章

java绘图 -- The DOT Language缘起正文1. Introduction2. 子图和群集 Subgraphs and Clusters3. 词法和语义注释 Lexical and Semantic Notes4. 字符编码 Character encodings后记参考文献:
java绘图 -- The DOT Language缘起正文1. Introduction2. 子图和群集 Subgraphs and Clusters3. 词法和语义注释 Lexical and Semantic Notes4. 字符编码 Character encodings后记参考文献:
跳表（skipList）
跳表（skipList）
跳表与红黑树
跳表与红黑树
跳跃表Skip List的原理和实现(Java)
跳跃表Skip List的原理和实现(Java)
skip-list
skip-list
多项式
多项式
一元多项式的各种操作
一元多项式的各种操作
多项式的操作
多项式的操作

评论列表共有 0 条评论

立即
投稿
返回
顶部