redis源码学习02:跳跃表插入结点

database

本文是本人在学习redis源码时的笔记,本文主要是对跳跃表插入结点代码的中文注释,如有错误欢迎指正。

有关跳跃表的原理可以上网搜材料,有很多。

首先看下redis源码里有关跳跃表的相关结构体:

typedef struct zskiplistNode { // 跳跃表节点

sds ele; // zset元素

double score; // zset分值

struct zskiplistNode *backward; // 单前level的后一个node

struct zskiplistLevel { // 创建节点的函数里会根据level数量申请相应的内存空间,放在结构体后面的作用是只需要一次内存申请操作,而且是连续的内存空间

struct zskiplistNode *forward;

unsigned long span; // 该结点在某一层与下一个结点之间的元素个数

} level[];

} zskiplistNode;

typedef struct zskiplist { // 跳跃表

struct zskiplistNode *header, *tail; // 头结点和尾结点,创建跳跃表时,tail为null

unsigned long length; // level1所有元素个数

int level; // 总层级数

} zskiplist;

 

创建一个结点:

// 创建一个跳跃表节点,设置分值和元素值

zskiplistNode *zslCreateNode(int level, double score, sds ele) {

zskiplistNode *zn =

zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel)); // 申请空间,同时根据level数量申请level的空间

zn->score = score;

zn->ele = ele;

return zn;

}

 

随机生成层级数:

// 为新的跳跃表生成随机level,1<=level<=ZSKIPLIST_MAXLEVEL,使用类似于幂律的分布,较高的级别不太可能返回。

// 抛硬币

int zslRandomLevel(void) {

int level = 1;

while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))

level += 1;

return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;

}

 

下面是跳跃表结点的插入代码,该函数只是对跳跃表插入的操作,redis的zset使用的是跳跃表,在zset的添加元素函数里会先判断元素是否存在,所以该函数是假设元素不存的情况下进行的处理,而且调用完该函数后跳跃表获得了sds的所有权:

// 插入一个新元素,跳跃表将获得ele所有权

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {

zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; // update:每一层结点在该node后插入元素

unsigned int rank[ZSKIPLIST_MAXLEVEL]; // 每个结点所有层的span总和

int i, level;

serverAssert(!isnan(score)); // score只能是数值, NaN (Not-A-Number)

x = zsl->header;

for (i = zsl->level-1; i >= 0; i--) { // 遍历每一层

/* store rank that is crossed to reach the insert position */// 通过score找到插入的位置

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 &&

sdscmp(x->level[i].forward->ele,ele) < 0)))

{

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

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

}

update[i] = x; // 记录插入的位置

}

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

* scores, reinserting the same element should never happen since the

* caller of zslInsert() should test in the hash table if the element is

* already inside or not. */

// 我们假设元素不在内部,因为我们允许重复分数,重新插入相同的元素应该永远不会发生,如果元素在内部,则zslInsert()的调用者应该在哈希表中进行测试已经在里面或没有。

level = zslRandomLevel(); // 使用幂次定律计算节点的层级

if (level > zsl->level) { // 如果计算出的层级比当前跳跃表的层级更高

for (i = zsl->level; i < level; i++) { // 对新添加的level进行处理

rank[i] = 0;

update[i] = zsl->header; // 每一层的头结点都相同

update[i]->level[i].span = zsl->length; // 新加入的层跨度为所有元素数量

}

zsl->level = level; // 更新跳跃表的层级

}

x = zslCreateNode(level,score,ele); // 创建新结点

for (i = 0; i < level; i++) { // 从第1层开始插入元素,第1层肯定要插入新元素

// 这两行代码交换旧结点的forward指针,将新结点插入到update之后

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 */

// 更新每个结点的span

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++) { // 对新添加的level计算span

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

}

x->backward = (update[0] == zsl->header) ? NULL : update[0]; // 更新新结点的backward

if (x->level[0].forward) // 更新新结点下个结点的backward

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

else

zsl->tail = x; // 如果插入的是最后一个位置则更新tail

zsl->length++; // 整个跳跃表的元素数量

return x;

}

 

以上是 redis源码学习02:跳跃表插入结点 的全部内容, 来源链接: utcz.com/z/534275.html

回到顶部