总结 Redis 双端链表的实现。
函数指针
Redis 链表结构内置了三个指向操作函数的函数指针，先梳理下函数指针用法。
定义
函数体在编译期间会被存入进程代码段内存的一片连续区域中，而函数名就是该区域的起始地址。可将该地址赋值给函数指针，通过指针间接调用函数。
1
2
3
4
5
6
7
| int sum(int x, int y) { return x + y;}
int main() {
int (*p)(int, int) = sum;
printf("%p\n%p\n", sum, p);
printf("%d\n%d\n%d\n", p(1, 1), (*p)(1, 1), (****p)(1, 1));
}
|
地址相同：
用法
比如 qsort 库函数第四个参数便是函数指针：int (* cmp)(const void *, const void *));，用于自定义排序规则：
1
2
3
4
5
6
7
8
9
10
11
12
13
| int less(const void *a, const void *b) {
return *(int *) a > *(int *) b;
}
int more(const void *a, const void *b) {
return *(int *) a < *(int *) b;
}
int main() {
int nums[5] = {4, 1, 5, 3, 2};
qsort(nums, 5, sizeof(int), less); debug(nums);
qsort(nums, 5, sizeof(int), more); debug(nums);
}
|
排序结果：
注：void * 为泛型指针，类似 Go 的 interface，本节链表节点的值为 void* 类型，可存储任意类型的值。
区分
根据 () 逐个拆解：
1
2
3
| int (*p)(int);
int *(*p)(int);
int (**p)(int);
|
Redis 双端链表
优缺点
- 优点：增删节点无需内存重排，直接操作复杂度为
O(1)。维护了 len 字段，取长度操作为 O(1)
- 缺点：由于各节点在内存上不连续，遍历搜索复杂度为
O(N)。但可以通过空间换时间，使用 O(N) 空间的哈希表，可将搜索复杂度降为 O(1)，这点在链表实现 LRU 时有应用。
结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
typedef struct list {
listNode *head;
listNode *tail;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
unsigned long len;
} list;
|
注意节点的结构标记是 listNode，前驱和后继节点为自引用结构。同时声明该类型的同名变量 listNode
内存布局
list API 实现
记录几个重要 API 实现，源码：adlist.c
O(1) 操作
1
2
3
4
5
6
7
8
9
| #define listFirst(l) ((l)->head)
#define listLast(l) ((l)->tail)
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)
#define listSetDupMethod(l, m) ((l)->dup = (m))
#define listGetDupMethod(l) ((l)->dup)
|
注意取 list 字段值的简单操作都是宏定义，且对参数 n 加括号避免了展开优先级错乱的问题。
listCreate
1
2
3
4
5
6
7
8
9
|
list *listCreate(void) {
struct list *list;
if ((list = zmalloc(sizeof(*list))) == NULL)
return NULL;
return list;
}
|
注意 zmalloc 分配内存后返回 void* 指针，可赋值给其他任意类型的指针，在 C 中无需显式强转，但 C++ 中必须显式转换。
listInsertNode
1
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
|
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (after) {
node->prev = old_node;
node->next = old_node->next;
if (list->tail == old_node) {
list->tail = node;
}
} else {
node->next = old_node;
node->prev = old_node->prev;
if (list->head == old_node) {
list->head = node;
}
}
if (node->prev != NULL) {
node->prev->next = node;
}
if (node->next != NULL) {
node->next->prev = node;
}
list->len++;
return list;
}
|
和刷 LeetCode 时链表题一样，直接画图最好理解。对链表的操作需检查：
- 链表是否为空
- 操作的节点是否为头尾节点
- 调整节点前后指针指向时顺序是否正确
listIter
Redis 为链表封装了一个迭代器：
1
2
3
4
| typedef struct listIter {
listNode *next;
int direction;
} listIter;
|
用于链表的搜索等操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| listNode *listSearchKey(list *list, void *key) {
listIter *iter;
listNode *node;
iter = listGetIterator(list, AL_START_HEAD);
while ((node = listNext(iter)) != NULL) {
if (list->match) {
if (list->match(node->value, key)) {
listReleaseIterator(iter);
return node;
}
} else {
if (key == node->value) {
listReleaseIterator(iter);
return node;
}
}
}
listReleaseIterator(iter);
return NULL;
}
|
此处用到了 match 函数指针，其内部会对类型均为 void* 的 value, key 做类型转换，返回值是否相等的结果。
listIter 负责迭代，list 负责存储，避免了手动迭代中各种临时变量带来的开销，按功能分离模块的设计很优秀。
总结
Redis list 是双向无环链表，节点值类型是 void*，类似于 Go 的 interface，所以在比较节点值时需调用自定义比较函数，故引入了三个函数指针。Redis 还将迭代功能的实现分离到了 listIter，比较巧妙。