August's Box

Redis设计与实现笔记-章3.链表

Redis用C实现了链表,应用场景包括list(元素很多或包含元素都是较长字符串时),发布和订阅,慢查询,监视器等,另外客户端状态信息,客户端输出缓冲区都是用链表来保存。

链表的定义

adlist.h/listNode,listlink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;

从实现上来看,Redis实现了一个双端链表,并保存了列表的长度和头尾节点指针。另外,节点的value类型为void*,加上提供listSetDupMethodlistSetFreeMethodlistSetMatchMethod接口实现保存不同类型的值(多态)。

API和宏定义

针对双端链表的API,包含链表基本操作和链表迭代相关的接口

adlist.h/apilink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
list *listCreate(void);//创建链表
void listRelease(list *list);//释放链表
list *listAddNodeHead(list *list, void *value);//添加到head
list *listAddNodeTail(list *list, void *value);//添加到tail
list *listInsertNode(list *list, listNode *old_node, void *value, int after);//插入节点,after为0插入到之前,1为之后
void listDelNode(list *list, listNode *node);//删除节点
listIter *listGetIterator(list *list, int direction);//创建迭代器,direction:AL_START_HEAD, AL_START_TAIL
listNode *listNext(listIter *iter);//获取下一个节点
void listReleaseIterator(listIter *iter);//释放迭代器
list *listDup(list *orig);//复制链表
listNode *listSearchKey(list *list, void *key);//查找key,通过match查找,未设置按照key == value
listNode *listIndex(list *list, long index);//返回index位置的节点
void listRewind(list *list, listIter *li);//设置迭代器方向为AL_START_HEAD
void listRewindTail(list *list, listIter *li);//设置迭代器方向为AL_START_TAIL
void listRotate(list *list);//取tail节点放置到头部,仅在处理客户端时使用(clientsCron)

方便链表操作的宏定义
adlist.h/#definelink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define listLength(l) ((l)->len)
#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 listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))
#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

总结

总的来说,链表实现比较简单,提供了一些针对链表典型的基本操作(增删改查等)的API和宏。