凌云的博客

行胜于言

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)