ふわふわ時間

0%

Redis 源码之 adlist

Redis 底层链表结构相关源码阅读笔记。


源码文件 /src/adlist.h & /src/adlist.c

adlist 数据结构

adlist 其实是一个双向链表,我们首先介绍其链表节点、链表迭代器和链表的数据结构。

链表节点

1
2
3
4
5
typedef struct listNode {
struct listNode *prev; // 指向前一节点
struct listNode *next; // 指向后一节点
void *value; // 指向当前节点的值
} listNode;

链表迭代器

1
2
3
4
5
6
7
8
typedef struct listIter {
listNode *next; // 迭代器当前所指节点,为什么不叫 now ?
int direction; // 迭代访问的方向
} listIter;

/* Directions for iterators */
#define AL_START_HEAD 0 // 从首到尾
#define AL_START_TAIL 1 // 从尾到首

链表

1
2
3
4
5
6
7
8
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;

辅助函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* Functions implemented as macros */
#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 基本操作

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
list *listCreate(void)
{
struct list *list; // 指向一个链表的指针

if ((list = zmalloc(sizeof(*list))) == NULL)
return NULL;
list->head = list->tail = NULL; // 首尾节点默认为 NULL
list->len = 0;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}

返回值: * 分配内存执行失败时,返回 NULL * 执行成功时返回指向已构造的空链表的指针。

析构函数

  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 函数释放了链表中的每个节点,但是并未释放指向该链表的指针本身。

  2. listRelease —— 析构函数完全体

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

添加

  1. listAddNodeHead

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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; // 首节点的 prev 指针指向 NULL
    node->next = list->head;
    list->head->prev = node;
    list->head = node;
    }
    list->len++;
    return list;
    }

    可以看出,该函数的作用是,根据给定的值指针 value,构造一个新的 listnode,并将该节点插入到给定链表 list 的首部,其返回值为:

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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; // 尾节点的 next 指针指向 NULL
    list->tail->next = node;
    list->tail = node;
    }
    list->len++;
    return list;
    }

    该函数的作用是:根据给定的值指针 value,构造一个新的 listnode,并将该节点插入到给定链表 list 的尾部,其返回值为:

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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) { // atfer 非 0,新节点插入在指定节点之后
    node->prev = old_node;
    node->next = old_node->next;
    if (list->tail == old_node) { // 指定节点为尾节点
    list->tail = node; // 更新链表的尾节点指针为新插入节点
    }
    } else { // after 为 0,新节点插入在指定节点之前
    node->next = old_node;
    node->prev = old_node->prev;
    if (list->head == old_node) { // 指定节点为首节点
    list->head = node; // 更新链表的首节点指针为新插入节点
    }
    }
    if (node->prev != NULL) {
    node->prev->next = node; // 更新插入节点的前一节点的 next 指针
    }
    if (node->next != NULL) {
    node->next->prev = node; // 更新插入节点的后一节点的 prev 指针
    }
    list->len++;
    return list;
    }

    该函数的作用是:根据给定的值指针 value,构造一个新的 listnode,随后将该节点插入到链表的指定位置:

    • \(after \ne 0\),插入到 old_node 之后
    • \(after = 0\),插入到 old_node 之前

    函数的返回值为:

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

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

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void listDelNode(list *list, listNode *node)
{
if (node->prev)
node->prev->next = node->next;
else
list->head = node->next; // 删除节点为首节点,更新链表首节点指针
if (node->next)
node->next->prev = node->prev;
else
list->tail = node->prev; // 删除节点为尾节点,更新链表尾节点指针
if (list->free) list->free(node->value);
zfree(node); // 释放该节点所占内存空间
list->len--;
}

该函数的作用是:删除给定节点,并释放其所占内存空间。

迭代器相关

  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 时,返回逆序迭代器
  2. listReleaseIterator

    1
    2
    3
    void listReleaseIterator(listIter *iter) {
    zfree(iter);
    }

    该函数的作用是:释放迭代器所占内存。

  3. listRewind

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

    该函数的作用是:将给定迭代器重置为正序迭代器。

  4. listRewindTail

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

    该函数的作用是:将给定迭代器重置为逆序迭代器。

  5. listNext

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    listNode *listNext(listIter *iter)
    {
    listNode *current = iter->next; // 迭代器当前所指节点

    if (current != NULL) {
    if (iter->direction == AL_START_HEAD)
    iter->next = current->next;
    else
    iter->next = current->prev;
    }
    return current;
    }

    该函数的作用是:如果迭代器当前所指节点非空,则根据方向参数更新迭代器的 next 指针,最后返回迭代器当前所指节点。

复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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); // iter 重置为正序迭代器
while((node = listNext(&iter)) != NULL) { // 遍历原链表
void *value;

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

该函数的作用为:完全复制给定的链表 orig,函数的返回值为: * 执行失败时,返回 NULL * 执行成功时,返回复制链表指针 copy

注意:不论该函数是否执行成功,原链表都不会被修改。

查找

  1. listSearchKey

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    listNode *listSearchKey(list *list, void *key)
    {
    listIter iter;
    listNode *node;

    listRewind(list, &iter); // 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; // 未找到,返回 NUll
    }

    该函数的作用是:根据给定的值指针,寻找值相等的链表节点,该函数的返回值为:

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    listNode *listIndex(list *list, long index) {
    listNode *n;

    if (index < 0) { // 支持负数索引
    index = (-index)-1;
    n = list->tail;
    while(index-- && n) n = n->prev;
    } else {
    n = list->head;
    while(index-- && n) n = n->next;
    }
    return n;
    }

    该函数的作用是:根据给定的索引值,返回相应的链表节点

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

旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void listRotate(list *list) {
listNode *tail = list->tail;

if (listLength(list) <= 1) return;

/* Detach current tail */
list->tail = tail->prev;
list->tail->next = NULL;
/* Move it as head */
list->head->prev = tail;
tail->prev = NULL;
tail->next = list->head;
list->head = tail;
}

该函数的作用是:删除链表原尾节点,将原尾节点插入到首部,作为新的首节点。

拼接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void listJoin(list *l, list *o) {
if (o->head) // 链表 o 不为空
o->head->prev = l->tail;

if (l->tail) // 链表 l 不为空
l->tail->next = o->head;
else
l->head = o->head;

if (o->tail) l->tail = o->tail;
l->len += o->len;

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

该函数的作用是:将链表 o 拼接到链表 l 之后,随后将链表 o 置为空链表,并未释放链表指针。