Redis 5 数据结构（六）linkedlist

分类：Redis| 发布时间：2019-05-07 12:32:00

概述

本文是 Redis 5 数据结构系列的第六篇，主要讲解 双向链表 的结构和实现细节。

虽然在 Redis 5 中,已经用 quicklist 取代了 linkedlist 来保存列表对象，但是 Redis 的其他地方依然广泛使用到了 linkedlist。

linkedlist 的实现

双向链表的源码在 src/adlist.h 和 src/adlist.c。

linkedlist 结构的定义如下：

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;

listNode 中使用了一个 void 类型的指针保存其内存，由于链表内部并不知道 value 保存的内容的真实情况，因此需要用户指定三个函数用于处理这个 value，这三个函数分别是：

dup 复制一个 value，若没有提供此函数，链表内部在需要复制的时候直接复制 value 指针的值
free 释放一个 value，若没有提供此函数，则不进行 free 操作
match 比较两个 value 的值，返回非 0 值表示两个 value 相等，若不提供此函数则直接比较两个 value 指针是否相等

list 结构里面维护了一个表示其节点个数的变量 len，因此 Redis 在查询 list 的长度时可以直接使用这个值，而不用遍历整个列表。

下图给出了一个由 list 和 listNode 结构组成的双向链表的示例：

linkedlist API

list *listCreate(void);

创建一个链表

void listRelease(list *list);

释放一个链表

void listEmpty(list *list);

清空一个链表的内容，和 listRelease 的区别在于这个函数不会释放 list 结构本身。

#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)

在 adlist.h 提供了以上的宏用于设置和获取 list，由于意图很明显就不一一说明了。

list *listAddNodeHead(list *list, void *value);

添加节点到链表头

list *listAddNodeTail(list *list, void *value);

添加节点到链表尾

list *listInsertNode(list *list, listNode *old_node, void *value, int after);

在指定位置插入节点，after 用于指示插入到 old_node 的前面还是后面

after:

0 表示插入到 old_node 的前面
非 0 表示插入到 old_node 的后面

void listDelNode(list *list, listNode *node);

删除一个节点

#define AL_START_HEAD 0
#define AL_START_TAIL 1

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

listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);

这三个函数用于方便的遍历整个列表，direction 为 AL_START_HEAD 表示从头到尾便利，为 AL_START_TAIL 表示从尾到头遍历。通常会如下使用：

iter = listGetIterator(list,<direction>);
while ((node = listNext(iter)) != NULL) {
    doSomethingWith(listNodeValue(node));
}

void listRewind(list *list, listIter *li);

将迭代器重置为从头到尾遍历，并将当前位置移动到表头

void listRewindTail(list *list, listIter *li);

将迭代器重置为从尾到头遍历，并将当前位置移动到表尾

list *listDup(list *orig);

复制整个链表，若由于内存不足复制失败时会返回 NULL，否则返回新复制的链表。新的链表会使用和原链表相同的 dup、free、match 函数，并在复制过程中使用 dup 函数进行节点内容的复制，若没有提供 dup 函数，则直接复制 value 指针。

listNode *listSearchKey(list *list, void *key);

使用 list 的 match 方法对每个节点的 value 和 key 进行比较，返回匹配的节点，若 match 为 NULL，则直接比较 value 和 key 指针的值。

listNode *listIndex(list *list, long index);

返回索引为 index 的节点，index 大于等于 0 时表示以 0 为起点的索引值，这是 0 表示表头，1 表示表头的下一个节点，依次类推。若 index 为负数，表示从表尾开始算，-1 表示最后一个节点，-2 表示倒数第二的节点，依次类推。

若索引值超过范围则返回 NULL。

void listRotate(list *list);

对链表进行一次旋转操作，也就是将最后一个节点从链表移除并插入到链表的开头。

void listJoin(list *l, list *o);

将 o 链表拼接到 l 链表的后面，操作完成后 o 链表将变成空链表。

总结

Redis 由于是用 C 语言写的，因此造了一套双向链表的轮子
节点的内容保存在一个 void 指针里面，并且需要向链表提供 dup、free 和 match 函数，通过这种方式使得 Redis 的双向链表可以保存任意内容
Redis 的双向链表维护了一个 length 变量用于保存链表的节点数，因此查询链表节点个数的时间复杂度为 O(1)

凌云的博客

行胜于言