Redis | 源码阅读 —— 链表
本文是参考 黄建宏 先生所写的 《Redis 设计与实现》 一书而来的，在此感谢 黄建宏 先生能写出这么优秀的书籍。本次来整理关于链表相关的数据结构。
链表不但是一种存储结构（数据结构的存储不外乎是顺序存储和链式存储两种），也是一种数据结构，它和数组相比，它的优点是方便节点的插入与节点的删除。在 Redis 中也存在链表这种数据结构，关于链表数据结构的定义和操作包含在 adlist.h 和 adlist.c 两个文件中。
链表相关数据结构
在 Redis 的源码中，链表的数据结构和相关的操作都包含在 adlist.h 和 adlist.c 两个文件当中，这两个文件是 Redis 中对底层链表的所有实现。在 adlist.h 文件中，有两个关于链表的重要数据结构，一个是双向链表的数据结构，另外一个是用于管理双向链表的数据结构。
双向链表的数据结构定义如下：
/**
* 双向链表
*/
typedef struct listNode {
// 前驱节点指针
struct listNode *prev;
// 后继节点指针
struct listNode *next;
// 数据域指针
// 数据域的指针是void类型的指针，说明该链表可以保存各种类型的数据
void *value;
} listNode;除了定义了基本的 listNode 数据结构外，还有一个用于管理双向链表的数据结构，定义如下：
/**
* 对listNode节点的管理
*/
typedef struct list {
// 指向listNode的头节点
listNode *head;
// 指针listNode的尾节点
listNode *tail;
// 节点复制函数
void *(*dup)(void *ptr);
// 节点释放函数
void (*free)(void *ptr);
// 节点比对函数
int (*match)(void *ptr, void *key);
// 管理的listNode节点的数量
unsigned long len;
} list;双向链表的定义是 listNode，其中包含 prev 和 next 两个指针，分别用来保存其前驱节点与后继节点，而它的节点值 val 是一个 void * 的类型，void * 这种类型在 C 语言当中算是一个 “万能” 类型，使用强制类型转换，可以将 void * 这种类型转换为任意的类型，也就是 listNode 数据结构的节点值可以保存任意的数据类型。
Redis 除了 listNode 还定义了 list 的数据结构，该数据结构是用于管理双向链表的数据结构，该数据结构中保存了所管理的 listNode 链的头节点位置、尾节点位置和管理的 listNode 链节点的数量，通过 list 数据结构可以快速定位到链表的表头、表尾。对于 Redis 的 list（列表） 这种数据类型（这里说的是我们操作 Redis 时的 list 数据类型，此 list 非数据结构的 list，文中混用较多，请根据上下文理解），就是使用 链表 这种数据结构，而 list 可以通过 正负索引 来定位其中的元素，那么通过 list 数据结构的 head 和 tail 就可以方便的定位到 list（列表） 数据类型的开始和结尾了。
了解过数据结构的同学都知道，链表的长度需要通过遍历链表的每个节点可以累加得到，这样它的时间复杂度为O(n)，而 Redis 的 list 中通过 len 保存了 listNode 链的节点的数量，这样将链表长度计算的时间复杂度从 O(n) 变为了 O(1)。
在 list 数据结构中保存着三个 函数指针，分别是 dup、free 和 match，它们的作用是用来保存链表的节点复制函数、节点释放函数和节点比对函数的地址。前面已经说过，listNode 的值是 void* 类型，也就是可以保存不同的数据类型，比如 char*、int、double，甚至可以是复杂的数据结构，这样不同的数据类型，在进行节点复制、节点释放和节点比较时，肯定使用不同的方式进行比较，因此 dup、free 和 match 根据不同的数据类型存放不同的数据类型的复制、释放和比对函数的地址。
链表管理操作的宏定义
链表的很多管理函数都是使用宏定义完成的，比如对 list 数据结构中成员的设置和获取，宏定义如下：
/* 返回list的长度 */
#define listLength(l) ((l)->len)
/* 返回list指向listNode的头指针 */
#define listFirst(l) ((l)->head)
/* 返回list指向listNode的尾指针 */
#define listLast(l) ((l)->tail)
/* 返回list指向的当前节点的前一个节点 */
#define listPrevNode(n) ((n)->prev)
/* 返回list指向的当前节点的后一个节点 */
#define listNextNode(n) ((n)->next)
/* 返回list指向的当前节点的值 */
#define listNodeValue(n) ((n)->value)再比如对 dup、free 和 match 的 getter 和 setter 的函数也是相关的宏定义，如下所示：
/* 将指定函数设置为list的赋值函数 */
#define listSetDupMethod(l,m) ((l)->dup = (m))
/* 将指定函数设置为list的释放函数 */
#define listSetFreeMethod(l,m) ((l)->free = (m))
/* 将指定函数设置为list的比对函数 */
#define listSetMatchMethod(l,m) ((l)->match = (m))
/* 返回list的赋值函数 */
#define listGetDupMethod(l) ((l)->dup)
/* 返回list的释放函数 */
#define listGetFree(l) ((l)->free)
/* 返回list的比对函数 */
#define listGetMatchMethod(l) ((l)->match)上面的函数都是针对 list 结构体都操作，而 list 数据结构是用于管理 nodeList 数据结构的，真正用于存储 list（列表）数据的是 nodeList 数据结构，而关于操作 listNode 数据结构的函数是真正的链表操作函数。
操作 nodeList 数据结构的函数
操作 nodeList 数据结构的函数是一些 C 语言的函数，而不再是宏定义，这些函数基本上完成了关于链表增删改查的全部操作。
/* 创建一个不包含任何节点的链表 */
list *listCreate(void);
/* 释放指定的list */
void listRelease(list *list);
/* 将值插入到链表的头部 */
list *listAddNodeHead(list *list, void *value);
/* 将值插入到链表的尾部 */
list *listAddNodeTail(list *list, void *value);
/* 将新的listNode插入到list中指定节点前面或后面 */
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
/* 删除list中的指定listNode */
void listDelNode(list *list, listNode *node);
/* 对指定链表创建副本 */
list *listDup(list *orig);
/* 查找指定的key，并返回listNode的指针 */
listNode *listSearchKey(list *list, void *key);
/* 返回指定索引的listNode的指针 */
listNode *listIndex(list *list, long index);
/* 尾节点变为新的头节点 */
void listRotate(list *list);以上的函数包含了链表的大部分操作，我们来具体看其中几个函数。
无环链表
Redis 的链表是无环的双向链表，这点可以通过 Redis 插入头节点和插入尾节点的函数看出，两个函数代码如下：
/**
* 将值插入到链表的头部
*/
list *listAddNodeHead(list *list, void *value)
{
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (list->len == 0) {
// list的头尾都指向node
list->head = list->tail = node;
// node的前驱和后继都为空
node->prev = node->next = NULL;
} else {
// 头节点没有前驱
node->prev = NULL;
// 头节点的后继为当前list的头节点
node->next = list->head;
// 当前头节点的前驱为新节点
list->head->prev = node;
// 修正新的头节点为新的node
list->head = node;
}
// 增加list的长度
list->len++;
return list;
}
/**
* 将值插入到链表的尾部
*/
list *listAddNodeTail(list *list, void *value)
{
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (list->len == 0) {
// list的头尾追昂node
list->head = list->tail = node;
// node的前驱和后继都为空
node->prev = node->next = NULL;
} else {
// 当前节点的前驱为list的尾节点
node->prev = list->tail;
// 当前节点的后继为空
node->next = NULL;
// list的尾节点的后继为新节点
list->tail->next = node;
// 修正新的尾节点为新的node
list->tail = node;
}
// 增加list的长度
list->len++;
return list;
}可以看到，头节点的前驱节点是 NULL，而尾节点的后继节点也是 NULL，这说明 Redis 的链表是无环的链表，也就是首尾没有相连。
迭代器
链表节点的复制、搜索都会涉及到链表的遍历，链表的遍历使用了迭代器的数据结构。迭代器的数据结构如下：
/**
* 迭代器
*/
typedef struct listIter {
// 下一个节点的指针
listNode *next;
// 控制方向
int direction;
} listIter;迭代器数据结构中的 next 保存了下一个节点的指针，因为它是双向链表，因此这里的 next 可能保存的是 listNode 中的 prev 或者 next 的指针。具体是 prev 还是 next 是由 direction 的来控制着。看代码，如下：
listIter *listGetIterator(list *list, int direction)
{
listIter *iter;
if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
if (direction == AL_START_HEAD)
iter->next = list->head;
else
iter->next = list->tail;
iter->direction = direction;
return iter;
}获取迭代器的指针中会对 direction 进行判断，direction 的值由两个宏进行定义，定义如下：
/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1关于迭代器的代码，就不在进行列举了。
最后
上面就是关于 Redis 中链表实现的代码了。Redis 的链表会用在包括但不限于 list（列表）的场景，比如发布订阅、慢查询等也会使用列表的数据结构。
喝水不忘打井人，没有黄老师的书籍做我 Redis 学习的指路明灯，恐怕对于学习 Redis 的源码我会艰难万分。再次感谢黄老师写的关于 Redis 的书籍，能够让好的技术遍地开花。