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