Redis 源码阅读 --- adlist

Redis 双向链表相关源码阅读笔记，源码文件 adlist.h & adlist.c。

1. 小结

Redis 中的 list 是随处可见的普通双向链表：

链表头节点的 prev 指针和链表尾节点的 next 指针都指向 NULL，因此链表是无环的，遍历以 NULL 结尾
如果想释放链表节点 value 所占用的内存空间，需要提供相应的 free 函数。

2. list 数据结构

list 相关数据结构如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


typedef struct listNode {
    struct listNode *prev; /* list->head->prev == NULL */
    struct listNode *next; /* list->tail->next == NULL */
    void *value;
} listNode;

typedef struct listIter {
    listNode *next; /* 迭代器当前所指节点，为什么不叫 now ？ */
    int direction;  /* 迭代访问的方向 */
} listIter;

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;

3. list 构造函数

分配内存执行失败时，返回 NULL
执行成功时返回所构造空链表的指针

1

list *listCreate(void);

4. list 析构函数

4.1. lsitEpmty – 不健全的析构函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


void listEmpty(list *list)
{
    unsigned long len;
    listNode *current, *next;

    current = list->head;
    len = list->len;
    while(len--) {
        next = current->next;
        /* 如果 list 中的 free 函数已设置，调用其，释放节点值 */
        if (list->free) list->free(current->value);
        /* 释放当前节点的指针 */
        zfree(current);
        current = next;
    }
    list->head = list->tail = NULL; /* 将首尾节点置为 NULL */
    list->len = 0;  
}

listEmpty 函数释放了链表中的每个节点，但是并未释放指向该链表的指针本身
如果节点中的 value 需要释放，则应该提供 free 函数

4.2. listRelease – 析构函数完全体

1
2
3
4
5


void listRelease(list *list)
{
    listEmpty(list);
    zfree(list);    /* 释放指向该链表的指针 */
}

5. 增删操作

5.1. listAddNodeHead

添加节点至链表头部，其值为 value，为新增节点申请内存失败时，不改变原链表，返回 NULL。

1

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

5.2. listAddNodeTail

添加节点至链表尾部，其值为 value，为新增节点申请内存失败时，不改变原链表，返回 NULL。

1

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

5.3. listInsertNode

1

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

根据给定的值指针 value，构造一个新的 listnode，随后将该节点插入到链表的指定位置：

$after \ne 0$，插入到 old_node 之后
$after = 0$，插入到 old_node 之前

函数的返回值：

新增节点申请内存失败时，返回 NULL，不改变原链表
申请内存成功时，返回修改好的链表指针 list

Tips: 插入节点时，可以先更新插入节点的指针，然后再更新插入节点相邻节点的指针

5.4. listDelNode

删除给定节点，并释放其所占内存空间

1

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

6. 迭代器相关

6.1. listGetIterator

返回迭代器指针。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

函数的返回值：

申请内存失败时，返回 NULL
申请内存成功时，根据方向参数初始化迭代器，并返回其指针 iter
- direction == AL_START_HEAD 时，返回正序迭代器
- direction == AL_START_TAIL 时，返回逆序迭代器

6.2. listReleaseIterator

释放迭代器所占内存。

1
2
3


void listReleaseIterator(listIter *iter) {
    zfree(iter);
}

6.3. listRewind

将给定迭代器重置为正序迭代器

1
2
3
4


void listRewind(list *list, listIter *li) {
    li->next = list->head;
    li->direction = AL_START_HEAD;
}

6.4. listRewindTail

将给定迭代器重置为逆序迭代器

1
2
3
4


void listRewindTail(list *list, listIter *li) {
    li->next = list->tail;
    li->direction = AL_START_TAIL;
}

6.5. listNext

如果迭代器当前所指节点非空，则根据方向参数更新迭代器的 next 指针，最后返回迭代器当前所指节点。

1

listNode *listNext(listIter *iter);

7. Utils

7.1. listDup – 复制

1

list *listDup(list *orig);

完全复制给定的链表 orig，函数的返回值为：

执行失败时，返回 NULL
执行成功时，返回复制链表指针 copy
不论该函数是否执行成功，原链表都不会被修改

7.2. listSearchKey

1

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

根据给定的值指针，寻找值相等的链表节点，该函数的返回值为：

成功找到时，返回第一个值相等的链表节点指针 (正序)
未找到时，返回 NULL

7.3. listIndex

1

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

根据给定的索引值，返回相应的链表节点

从 0 开始计算索引，支持负数索引
当索引值 index $\notin[-len, len - 1]$ 时，返回 NULL

7.4. 旋转

1
2
3
4


/* Rotate the list removing the tail node and inserting it to the head. */
void listRotateTailToHead(list *list);
/* Rotate the list removing the head node and inserting it to the tail. */
void listRotateHeadToTail(list *list);

7.5. listJoin – 拼接

将链表 o 拼接到链表 l 之后，随后将链表 o 置为空链表，并未释放链表指针。

1
2


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

Table of Contents