redis linkedlist

Posted on

redis中的双向链表源码剖析

1 基本结构

从下面的源码可以看出，这是个双向链表，包含

  • listNode : 节点
  • listIter : 迭代器
  • list : 链表

我们不难看出，listNode使用 void * 来存放数据，因此数据类型不限定, 而迭代器则使用 direction 标明迭代方向, 在 list 中，三个函数指针表示了三种不同的操作:

  • duplicate, 复制
  • free, 释放
  • match, 比较

之所以使用这三个函数指针，是因为value的真实类型不同，所进行的操作也不同，使用函数指针可以为不同类型的链表指定不同的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

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;

该链表操作分割如下

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
list *listCreate(void); //创建链表
void listRelease(list *list); //释放链表
void listEmpty(list *list); //清空链表

//在头部添加节点
list *listAddNodeHead(list *list, void *value);

//在尾部添加节点
list *listAddNodeTail(list *list, void *value);

//在某个位置添加节点
list *listInsertNode(list *list, listNode *old_node, void *value, int after);

//删除节点
void listDelNode(list *list, listNode *node);

//获取迭代器，可指定迭代方向
//如果是往后迭代，那么返回指向头部的迭代器
//如果是往前迭代，那么返回指向尾部的迭代器
listIter *listGetIterator(list *list, int direction);

//让迭代器指向下一个节点
listNode *listNext(listIter *iter);

//释放迭代器
void listReleaseIterator(listIter *iter);

//复制链表
list *listDup(list *orig);

//根据value搜素某个节点，在比较的时候使用list中的match指针指向的函数
listNode *listSearchKey(list *list, void *key);

//获得第N个节点，index可为负数
listNode *listIndex(list *list, long index);

//创建一个指向头部的迭代器
void listRewind(list *list, listIter *li);

//创建一个指向尾部的迭代器
void listRewindTail(list *list, listIter *li);

//将头尾节点互换，旋转链表
void listRotate(list *list);

//将链表 o 放在链表 l 的尾部
void listJoin(list *l, list *o);

/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1