链表和链表节点的实现
adlist是Redis实现的双向链表文件。addlist.c主要是链表节点和相关属性方法的定义；addlist.h实现了该addlist.c中定义的方法。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/*
* 双端链表节点
*/
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;
我们可以看到Redis使用listNode来表示链表结构中的每个节点;它跟平常的链表节点一样，包含前后节点的指针以及一个万能指针来保存数据地址。
在list结构中，head指针指向有listNode组成的双向链表的第一个Node节点，tail执行双向链表的最后一个节点。而dup、free、match成员则是用于实现多态链表所需的类型特定函数，针对链表中存放的不同对象从而实现不同的方法。
Redis的链表实现特性可以总结如下：
- 双端：链表节点带有prev和next指针，获取某个节点的前置或者后置节点都是O(1)
- 无环：表头节点的prev指针和表尾节点的next指针都指向NULL
- 带表头指针和表尾指针，通过list结构的head和tail指针，可以很方便的顺序或者逆序遍历链表
- 链表计数器：通过list结构的len成员，可以O(1)获取listNode节点的个数
- 多态
Redis针对list结构和listNode结构的赋值和查询操作使用宏进行封装，以下的操作复杂度都是O(1)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/* Functions implemented as macros */
// 返回给定链表所包含的节点数量
// T = O(1)
#define listLength(l) ((l)->len)
// 返回给定链表的表头节点
// T = O(1)
#define listFirst(l) ((l)->head)
// 返回给定链表的表尾节点
// T = O(1)
#define listLast(l) ((l)->tail)
// 返回给定节点的前置节点
// T = O(1)
#define listPrevNode(n) ((n)->prev)
// 返回给定节点的后置节点
// T = O(1)
#define listNextNode(n) ((n)->next)
// 返回给定节点的值
// T = O(1)
#define listNodeValue(n) ((n)->value)
// 将链表 l 的值复制函数设置为 m
// T = O(1)
#define listSetDupMethod(l,m) ((l)->dup = (m))
// 将链表 l 的值释放函数设置为 m
// T = O(1)
#define listSetFreeMethod(l,m) ((l)->free = (m))
// 将链表的对比函数设置为 m
// T = O(1)
#define listSetMatchMethod(l,m) ((l)->match = (m))
// 返回给定链表的值复制函数
// T = O(1)
#define listGetDupMethod(l) ((l)->dup)
// 返回给定链表的值释放函数
// T = O(1)
#define listGetFree(l) ((l)->free)
// 返回给定链表的值对比函数
// T = O(1)
#define listGetMatchMethod(l) ((l)->match)
以下是链表操作的原型函数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/* Prototypes */
list *listCreate(void); //创建一个表头
void listRelease(list *list); //释放list表头和链表
list *listAddNodeHead(list *list, void *value); //将value添加到list链表的头部
list *listAddNodeTail(list *list, void *value); //将value添加到list链表的尾部
list *listInsertNode(list *list, listNode *old_node, void *value, int after); //在list中，根据after在old_node节点前后插入值为value的节点。
void listDelNode(list *list, listNode *node); //从list删除node节点
listIter *listGetIterator(list *list, int direction); //为list创建一个迭代器iterator
listNode *listNext(listIter *iter); //返回迭代器iter指向的当前节点并更新iter
void listReleaseIterator(listIter *iter); //释放iter迭代器
list *listDup(list *orig); //拷贝表头为orig的链表并返回
listNode *listSearchKey(list *list, void *key); //在list中查找value为key的节点并返回
listNode *listIndex(list *list, long index); //返回下标为index的节点地址
void listRewind(list *list, listIter *li); //将迭代器li重置为list的头结点并且设置为正向迭代
void listRewindTail(list *list, listIter *li); //将迭代器li重置为list的尾结点并且设置为反向迭代
void listRotate(list *list); //将尾节点插到头结点
在adlist.h文件中，使用C语言实现了迭代器（设计模式中的迭代器模式）：1
2
3
4
5
6
7
8
9
10
11
12
13/* Directions for iterators
*
* 迭代器进行迭代的方向
*/
// 从表头向表尾进行迭代
#define AL_START_HEAD 0
// 从表尾到表头进行迭代
#define AL_START_TAIL 1
typedef struct listIter {
listNode *next; //迭代器当前指向的节点
int direction; //迭代方向，可以取以下两个值：AL_START_HEAD和AL_START_TAIL
} listIter
迭代器的好处：
- 提供一种方法顺序访问一个聚合对象中各个元素，而又不需要暴露该对象的内部表示。
- 将指针操作进行统一封装，代码可读性增强。