Redis 源码分析（adlist）

源码版本：redis-4.0.1
源码位置：

  • adlist.h：listNode、list 数据结构定义。
  • adlist.c：函数功能实现。

一、adlist 简介

Redis 中的链表实现称为 adlist（A generic doubly linked list implementation，即通用双端链表实现）。与普通的单链表相比，adlist 支持 向前 或 向后 双向遍历，这是由其数据结构中定义的 next 和 prev 两个指针决定的。下面我们将深入分析其数据结构实现及核心操作。

二、数据结构定义

adlist 主要包含两个核心结构体：listNode（节点）和 list（链表本身）。

typedef struct listNode {
    struct listNode *next;         // next 指针，指向下一个元素
    struct listNode *prev;         // prev 指针，指向上一个元素
    void *value;                   // void *类型的数据域
} listNode;

typedef struct list {
    struct listNode *head;               // head 指针，指向链表头部
    struct listNode *tail;               // tail 指针，指向链表尾部
    void *(*dup)(void *ptr);             // 自定义复制函数。若未定义，默认策略会让原链表和新链表共享同一个数据域
    void (*free)(void *ptr);             // 自定义 free 操作
    int (*match)(void *ptr, void *key);  // 搜索操作时比较两个 value 是否相等，默认策略是比较两个指针的值
    unsigned long len;                   // 记录链表长度，获取长度操作可 O(1) 返回
} list;

三、核心操作分析

我们将通过一个综合示例来分析 adlist 的常用操作，包括：创建、插入、查找、反转输出、复制、拼接。

1. 示例代码

int keyMatch(void *ptr, void *key) {
    return strcmp(ptr, key) == 0 ? 1 : 0;
}

void printList(list *li) {
    printf("li size is %d, elements:", listLength(li));
    listIter iter;
    listNode *node;
    listRewind(li, &iter);
    while ((node = listNext(&iter)) != NULL) {
        printf("%s ", (char*)node->value);
    }
    printf("\n");
}

int main(int argc, char **argv)
{
    char b[][10] = {"believe", "it", "or", "not"};
    listIter iter;
    listNode *node;
    list *li = listCreate();

    // 头插法插入元素
    for (int i = 0; i < sizeof(b)/sizeof(*b); ++i) {
        listAddNodeHead(li, b[i]);
    }

    printList(li);

    printf("\nSearch a key :\n");
    listSetMatchMethod(li, keyMatch);
    listNode *ln = listSearchKey(li, "believe");
    if (ln != NULL) {
        printf("find key is :%s\n", (char*)ln->value);
    } else {
        printf("not found\n");
    }

    printf("\nReverse output the list :\n");
    printf("li size is %d, elements:", listLength(li));
    listRewindTail(li, &iter);
    while ((node = listNext(&iter)) != NULL) {
        printf("%s ", (char*)node->value);
    }
    printf("\n");

    printf("\nduplicate a new list :\n");
    list *lidup = listDup(li);
    printList(lidup);


    printf("\nConnect two linked lists :\n");
    listJoin(li, lidup);
    printList(li);


    listRelease(li);

    return 0;
}

运行输出：

Out > 
li size is 4, elements:not or it believe 

Search a key :
find key is :believe

Reverse output the list :
li size is 4, elements:believe it or not 

duplicate a new list :
li size is 4, elements:not or it believe 

Connect two linked lists :
li size is 8, elements:not or it believe not or it believe

2. 创建链表

list *li = listCreate(); 用于创建一个新链表并返回指针。

list *listCreate(void)
{
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

3. 插入操作

主示例中使用了 listAddNodeHead(li, b[i]); 进行头插。与之对应的还有尾插函数 listAddNodeTail()。此处我们以源码中的尾插函数 listAddNodeHead 的对称逻辑——listAddNodeTail 为例进行分析：

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;
}

函数首先申请一个 listNode 节点，然后通过 list->len == 0 判断是否为首节点。根据不同情况调整指针指向，将元素插入链表尾部并增加长度。循环插入所有元素后，链表结构如下图所示：

这里写图片描述

4. 查找

listNode *ln = listSearchKey(li, "believe"); 用于查找指定值的节点。默认匹配原则是比较指针是否相等，但可以通过自定义 match 函数来改变比较逻辑。例如本例中需要比较字符串内容，因此自定义了 keyMatch 函数：

// match 函数的声明是：int (*match)(void *ptr, void *key); 

int keyMatch(void *ptr, void *key) {
    return strcmp(ptr, key) == 0 ? 1 : 0;
}

通过 listSetMatchMethod(li, keyMatch); 指定匹配函数。下面是 listSearchKey() 的具体实现：

listNode *listSearchKey(list *list, void *key)
{
    listIter iter;
    listNode *node;

    listRewind(list, &iter);
    while((node = listNext(&iter)) != NULL) {
        if (list->match) {
            if (list->match(node->value, key)) {   // 如果用户自定义了比较函数，直接使用
                return node;
            }
        } else {
            if (key == node->value) {             // 默认比较策略是比较指针
                return node;
            }
        }
    }
    return NULL;
}

5. 反转遍历

由于 adlist 是双端链表，反转遍历操作十分简单。只需将迭代器初始化成从链表尾部开始遍历即可：

listRewindTail(li, &iter);    // 将迭代器从尾部开始迭代

6. 复制

list *lidup = listDup(li); 会创建一条新链表返回给用户。需要注意的是默认的复制策略：如果用户不自定义 dup() 函数，默认返回的复制链表和原始链表会共用相同的数据节点。这意味着修改一个链表的节点数据会影响另一个链表。

默认策略示例（浅拷贝）：

list *lidup = listDup(li);                      // 使用默认的复制操作
strncpy(listIndex(lidup, 0)->value, "abc", 3);  // 修改复制返回的链表的值
printList(lidup);
printList(li);

Out > 
li size is 4, elements:abc or it believe 
li size is 4, elements:abc or it believe     // 可以看到原始链表也受了影响，not 修改为了 abc

若自定义 dup 函数，实现深拷贝，即可避免这个问题：

void *strDup(void *ptr) {
    return sdsnew(ptr);
}

listSetDupMethod(li, strDup);                // 设置自定义的 dup 函数
list *lidup = listDup(li);
strncpy(listIndex(lidup, 0)->value, "abc", 3);
printList(lidup);
printList(li);

Out >
li size is 4, elements:abc or it believe 
li size is 4, elements:not or it believe    // 原始值没有变化

7. 拼接

listJoin(li, lidup); 可以将两个链表连接在一起：

void listJoin(list *l, list *o) {
    if (o->head)
        o->head->prev = l->tail;      // 将第二个链表链在第一个链表后边

    if (l->tail)
        l->tail->next = o->head;
    else
        l->head = o->head;

    l->tail = o->tail;
    l->len += o->len;

    /* Setup other as an empty list. */
    o->head = o->tail = NULL;
    o->len = 0;
}

8. 释放

listRelease(li); 函数负责释放链表。它首先会调用 listEmpty() 函数释放所有 listNode，最后再释放 list 结构体本身的空间。

四、总结

adlist 的实现相对简单，本文分析了其创建、插入、查找、反转、复制及拼接等操作，有助于熟悉其 API 和底层数据结构原理。需要注意的是，由于链表在新增节点时（无论头插还是尾插）每次都需要申请新的内存空间，长期使用容易造成内存碎片。在实际生产环境中，可根据具体场景考虑是否有优化空间。

说明：本文基于 Redis 4.0.1 源码进行分析。Redis 后续版本（如 6.x、7.x）在列表实现上引入了 quicklist 和 listpack 等结构进行优化，但 adlist 仍存在于代码库中用于特定场景。阅读较新版本源码时请注意数据结构的变化。