[redis设计与实现][4]基本数据结构——跳跃表

redis使用跳跃表和字典共同来实现有序集合键(sorted set)。

定义：

跳跃表节点：

[cce lang=”c”]

typedef struct zskiplistnode {

//成员对象

robj *obj;

//分值

double score;

//后退指针

struct zskiplistnode *backward;

//层结构

struct zskiplistlevel {

//前进指针

struct zskiplistnode *forward;

//跨度

unsigned int span;

} level[];

} zskiplistnode;

[/cce]

跳跃表定义：

typedef struct zskiplist {

//跳跃表头、尾指针

struct zskiplistnode *header, *tail;

//跳跃表长度

unsigned long length;

//跳跃表层数

int level;

} zskiplist;

zskiplist *zslcreate(void);

zskiplist *zslcreate(void) {

int j;

zskiplist *zsl;

zsl = zmalloc(sizeof(*zsl));

zsl->level = 1;

zsl->length = 0;

//创建头节点，头节点永远有最高层

//#define zskiplist_maxlevel 32 /* should be enough for 2^32 elements */

zsl->header = zslcreatenode(zskiplist_maxlevel,0,null);

//初始化头节点的每一层

for (j = 0; j < zskiplist_maxlevel; j++) {

zsl->header->level[j].forward = null;

zsl->header->level[j].span = 0;

}

zsl->header->backward = null;

zsl->tail = null;

return zsl;

zskiplistnode *zslcreatenode(int level, double score, robj *obj) {

zskiplistnode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistlevel));

zn->score = score;

zn->obj = obj;

return zn;

zskiplistnode *zslinsert(zskiplist *zsl, double score, robj *obj);

zskiplistnode *zslinsert(zskiplist *zsl, double score, robj *obj) {

zskiplistnode *update[zskiplist_maxlevel], *x;

unsigned int rank[zskiplist_maxlevel];

int i, level;

redisassert(!isnan(score));

x = zsl->header;

//遍历查找当前score对应的插入位置

for (i = zsl->level-1; i >= 0; i–) {

/* store rank that is crossed to reach the insert position */

rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];

while (x->level[i].forward &&

(x->level[i].forward->score < score ||

(x->level[i].forward->score == score &&

comparestringobjects(x->level[i].forward->obj,obj) < 0))) {

//累加跨度

rank[i] += x->level[i].span;

x = x->level[i].forward;

//当前层要更新的节点

update[i] = x;

/* we assume the key is not already inside, since we allow duplicated

* scores, and the re-insertion of score and redis object should never

* happen since the caller of zslinsert() should test in the hash table

* if the element is already inside or not. */

//随机一个当前节点的层数

level = zslrandomlevel();

//如果是最高层，需要修正

//在以前最高层以上的，跨度都修复为跳跃表原长度，前置节点都改为头结点

if (level > zsl->level) {

for (i = zsl->level; i < level; i++) {

rank[i] = 0;

update[i] = zsl->header;

update[i]->level[i].span = zsl->length;

//跳跃表的总层数改成最新的层数

zsl->level = level;

x = zslcreatenode(level,score,obj);

//每一层的链表构建

for (i = 0; i < level; i++) {

x->level[i].forward = update[i]->level[i].forward;

update[i]->level[i].forward = x;

/* update span covered by update[i] as x is inserted here */

//当前节点每层跨度计算

x->level[i].span = update[i]->level[i].span – (rank[0] – rank[i]);

//当前节点每层插入节点跨度修改

update[i]->level[i].span = (rank[0] – rank[i]) + 1;

/* increment span for untouched levels */

for (i = level; i < zsl->level; i++) {

update[i]->level[i].span++;

//修改当前节点的前置节点等

x->backward = (update[0] == zsl->header) ? null : update[0];

if (x->level[0].forward)

x->level[0].forward->backward = x;

else

zsl->tail = x;

zsl->length++;

return x;

int zslrandomlevel(void) {

int level = 1;

//#define zskiplist_p 0.25 /* skiplist p = 1/4 */

while ((random()&0xffff) < (zskiplist_p * 0xffff))

level += 1;

return (level

[/cce])>

)>

转载自：https://coolex.info/blog/450.html)>