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 的书籍，能够让好的技术遍地开花。

喜欢就点在看哦~