渐进式解析 Redis 源码 - 双端链表

2018-10-27 阅读量

Redis 中链表广泛应用于列表键、发布订阅、慢查询、监视器等功能中…

大家知道，链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活调整链表的长度

Redis 链表结构如下：

// 链表结构
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;
// 链表节点结构
typedef struct listNode {
    // 前一个节点
    struct listNode *prev;
    // 后一个节点
    struct listNode *next;
    // 节点值
    void *value;
} listNode;

由上可见，Redis 的链表为一个双向链表，它的一些特性：

双端 链表节点带有 prev / next 节点指针，获取前置 / 后置节点的复杂度为 O(1)
无环 表头节点的 prev 和表尾节点的 next 都指向 NULL，对链表的访问都是以 NULL 为终点
head / tail 可以很容易的获取链表的表头/表尾节点数据，而且复杂度为 O(1)
链表长度计数器 链表使用 len 属性对自身进行计数，而且操作复杂度为 O(1)
多态 链表使用了 dup / free / match 三个属性去设置特定的函数，以适应存储不同类型数据的链表

另外，Redis 链表还为双端链表准备了 迭代器 功能，可以从两个方向对链表进行迭代遍历

// 迭代器结构
typedef struct listIter {
    // 下一个节点
    listNode *next;
    // 迭代方向
    int direction;
} listIter;
// 迭代方向
// 从头到尾
#define AL_START_HEAD 0
// 从尾到头
#define AL_START_TAIL 1

下面我们就 Redis 链表的一些典型的 API 进行解析~~~

源码解析

由于有些方法里的代码量比较大，我们这里按照典型的代码片段进行解析，同志们可以根据文章提示的代码位置和代码里面的关键词在源码中搜素，可能数据结构一些元素看不太懂什么意思，没关系，先混个脸熟，后面看完回头再看过来就明白了

结构体简单操作的 宏定义

/* adlist.h: line 57 */
// 获取 list 长度
#define listLength(l) ((l)->len)
// 获取 list 头指针
#define listFirst(l) ((l)->head)
// 获取 list 尾指针
#define listLast(l) ((l)->tail)
// 获取 节点 n 的前置节点
#define listPrevNode(n) ((n)->prev)
// 获取 节点 n 的后置节点
#define listNextNode(n) ((n)->next)
// 获取 节点 n 的值
#define listNodeValue(n) ((n)->value)
// 设置 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)

另外，

listCreate 链表创建函数，主要是申请内存，以及结构初始化

listRelease 链表释放函数，这里需要分为两部分，结构内节点遍历释放、free 内存释放

跟上两个函数相比，反观插入函数就会稍微复杂一些，主要提供了三种插入方式：

listAddNodeHead 头插法

/* adlist.c: line 88 */
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;
    // 申请节点内存空间
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    // 节点赋值
    node->value = value;
    if (list->len == 0) {
        // 空链
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        // 非空链表，直接从 头部插入
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    // 增加长度
    list->len++;
    return list;
}

listAddNodeTail 尾插法

/* adlist.c: line 114 */
list *listAddNodeTail(list *list, void *value)
{
    listNode *node;
    // 申请节点内存空间
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    // 节点赋值
    node->value = value;
    if (list->len == 0) {
        // 空链
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        // 非空直接从尾部插入
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    // 增加长度
    list->len++;
    return list;
}

listInsertNode 灵活插入法

/* adlist.c: line 134 */
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;
    // 申请节点内存空间
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    // 节点赋值
    node->value = value;
    if (after) {
        // 节点后方插入
        node->prev = old_node;
        node->next = old_node->next;
        // 如果是最后一个节点
        if (list->tail == old_node) {
            list->tail = node;
        }
    } else {
        // 节点前方插入
        node->next = old_node;
        node->prev = old_node->prev;
        // 如果是第一个节点
        if (list->head == old_node) {
            list->head = node;
        }
    }
    // 由于是双向链表，需要更新 前置节点的 next 属性，后置节点的 prev 属性
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    if (node->next != NULL) {
        node->next->prev = node;
    }
    list->len++;
    return list;
}

listDup 链表复制函数

/* adlist.c: line 250 */
list *listDup(list *orig)
{
    // 返回的复制结果
    list *copy;
    // 迭代器
    listIter iter;
    // 节点
    listNode *node;
    // 申请空间
    if ((copy = listCreate()) == NULL)
        return NULL;
    // 复制 复制、释放、匹配 操作函数
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    // 重置迭代器，默认从前向后迭代遍历，列表遍历主要依赖迭代器，统一配置 迭代方向
    listRewind(orig, &iter);
    // 遍历
    while((node = listNext(&iter)) != NULL) {
        void *value;
        // 默认 使用 list 的复制函数 复制节点，否则直接赋值
        if (copy->dup) {
            value = copy->dup(node->value);
            if (value == NULL) {
                listRelease(copy);
                return NULL;
            }
        } else
            value = node->value;
        // 尾插法插入 复制链表中
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            return NULL;
        }
    }
    return copy;
}

Redis 为连接另外提供了两个查找函数，逻辑比较简单
listSearchKey 根据给定的节点值查找节点，迭代遍历每个节点，使用 match 函数或者直接对比的方法进行查找 node
listIndex 根据序号查找节点，序号为正数为顺序查找，负数为逆序查找

本文作者： wettper
本文链接： http://www.web-lovers.com/redis-source-adlist.html
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！