redis源码学习02:跳跃表插入结点
本文是本人在学习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