前言
- 排行榜是每个游戏常有的功能，大部分情况下分为两种，一种是定时排行，另一种是实时排行。而排行榜的底层是使用
redis的zset数据结构，为啥不直接用redis，如果把redis整个都集成过来，会比较臃肿，如果游戏框架里并没有使用到redis，并不需要整个redis都搬过来。如果对跳表的实现感兴趣，就可以通过这篇博客了解一下redis zset的底层实现
源码地址
目录结构
正文
创建
zset接口 -slCreate1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32skiplist *slCreate(void) {
int j;
skiplist *sl;
sl = malloc(sizeof(*sl));
sl->level = 1;
sl->length = 0;
sl->header = slCreateNode(SKIPLIST_MAXLEVEL, 0, NULL);
for (j=0; j < SKIPLIST_MAXLEVEL; j++) {
sl->header->level[j].forward = NULL;
sl->header->level[j].span = 0;
}
sl->header->backward = NULL;
sl->tail = NULL;
return sl;
}
typedef struct skiplistNode {
slobj* obj;
double score;
struct skiplistNode *backward;
struct skiplistLevel {
struct skiplistNode *forward;
unsigned int span;
}level[];
} skiplistNode;
typedef struct skiplist {
struct skiplistNode *header, *tail;
unsigned long length;
int level;
} skiplist;- 上面是创建
skiplist数据结构的代码，看看skiplist结构体各字段含义。slCreateNode(SKIPLIST_MAXLEVEL, 0, NULL);创建一个节点，因为是头结点，所以一次性分配为最高的层。sl->level是所有节点中最高的层，也可以说是头结点的层高，因为起点是从头结点开始查找一个item的，头结点必须有最高的层数。sl->length所拥有的节点数。
- 上面是创建
插入一个节点，也就是插入排行榜中的一个
item,这里一定是新增，而不是更新排行榜中一个item1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53void slInsert(skiplist *sl, double score, slobj *obj) {
skiplistNode *update[SKIPLIST_MAXLEVEL], *x;
unsigned int rank[SKIPLIST_MAXLEVEL];
int i, level;
x = sl->header;
for (i = sl->level-1; i >= 0; i--) {
/* store rank that is crossed to reach the insert position */
rank[i] = i == (sl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
compareslObj(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 slInsert() should test in the hash table
* if the element is already inside or not. */
level = slRandomLevel();
if (level > sl->level) {
for (i = sl->level; i < level; i++) {
rank[i] = 0;
update[i] = sl->header;
update[i]->level[i].span = sl->length;
}
sl->level = level;
}
x = slCreateNode(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 < sl->level; i++) {
update[i]->level[i].span++;
}
x->backward = (update[0] == sl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
sl->tail = x;
sl->length++;
}skiplistNode *update[SKIPLIST_MAXLEVEL], *x;update存放的是需要调整的节点，这里分三种情况来说明这个函数所有的流程- 当插入
item是第一个item的时候，也就是头结点之后的第一个节点，update[i] = x;需要调整的就是头结点，当level不超过头结点的level的时候，就不会执行(level > sl->level)里的循环，帮第一个item创建一个节点，进入for (i = 0; i < level; i++)去调整节点，其实这里我之前困惑于为什么update[i]一定不是NULL？因为这里i是小于刚创建的节点level，所以肯定有相邻的层级调整，而且有且只有一个，所有update[i]一定不是NULL。for (i = level; i < sl->level; i++)随后高于随机节点的层数span需要自增，因为中间插入了一个节点。
- 当插入