redis双向链表剖析

发表于 更新于 阅读次数：

说明

本篇文章介绍redis的双向链表。redis用很简洁的代码实现了每本数据结构书籍必有的双向链表结构。可以推荐给正在学习数据结构的同学看看这代码

实现

redis使用两个结构体实现了双向链表，即list和listNode。另外还有一个listIter用来实现遍历list每个节点的迭代器

listNode

1
2
3
4
5
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
  • 双向链表节点，只有三个变量，两个指向前后节点的指针，这两个指针就能串起来整个链表，另外还有一个存放value地址的指针

list

1
2
3
4
5
6
7
8
9
10
11
typedef struct list {
    listNode *head;         // 指向链表头节点
    listNode *tail;         // 指向链表尾节点

    // dup, free, match操作的函数指针，可自定义设置
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);

    unsigned long len;      // 链表长度
} list;
  • 双向链表结构体，实际上也可以很简单，只需要三个变量，两个指向链表头尾节点的指针，还有一个记录链表长度。
  • redis为了提供更强大的接口，实现了三个可以自定义的函数回调，用来实现特殊的需求
    • dup: 在listDup中使用，复制链表的时候，如果自定义该函数，则每个listNode的value变量会使用该回调进行复制，如果该函数返回NULL，则会导致整个复制链表过程失败
    • free：在listDelNode和listRelease中使用，如果自定义该函数，则释放listNode的时候就会先调用一次该函数以确保正确的可以释放value这个指针
    • match：在listSearchKey中使用，如果自定义该函数，则在search过程中，调用该函数进行匹配操作

listIter

1
2
3
4
5
6
7
8
9
// 链表迭代器，存放下一个节点以及一个代表方向(往前还是往后)的变量
typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

// list迭代器方向
#define AL_START_HEAD 0     // 从头开始往后遍历
#define AL_START_TAIL 1     // 从尾部开始往前遍历
  • 可以通过listGetIterator创建指定list，指定方向的一个迭代器，遍历完之后可以通过listReleaseIterator释放
  • 遍历过程中也可以通过listRewind和listRewindTail来重置迭代器状态
  • 迭代器可以控制方向（从后往前/从前往后），该方向可以通过宏变量指定
  • 迭代器遍历链表的一个简单例子
    1
    2
    3
    4
    iter = listGetIterator(list,<direction>);
    while ((node = listNext(iter)) != NULL) {
        doSomethingWith(listNodeValue(node));
    }

函数分析

函数 描述 时间复杂度
listCreate 创建一个空的链表 O(1)
listRelease 释放整个list，包括list的各个节点 O(N)，N为元素个数
listAddNodeHead 增加一个值为value的节点到list的头部 O(1)
listAddNodeTail 增加一个值为value的节点到list的尾部 O(1)
listInsertNode 增加一个节点到指定节点的前/后，after表示插入前还是后 O(1)
listDelNode 删除指定的节点，因为效率问题，没有判断node是否真的是该list的节点 O(1)
listGetIterator 创建指定list，指定方向的一个迭代器 O(1)
listNext 获取迭代器的下一个节点 O(1)
listRewind 重置迭代器为从头往后遍历 O(1)
listRewindTail 重置迭代器为从后往前遍历 O(1)
listReleaseIterator 释放迭代器内存 O(1)
listDup 完整的复制一个链表 O(N)，N为元素个数
listSearchKey 从list中查找指定节点 O(N)，N为元素个数
listIndex 返回list中下标为index的节点，index如果为正值，表示从头开始的小标，且下标从0开始，即0为head，如果index为负值，表示从后往前的下标，且下标从-1开始，即-1表示tail O(abs(index))
listRotate 顺时针旋转list，将list的tail节点从尾部移除，插入到list头部 O(1)

每个函数及宏的声明及作用，具体细节可以查看我注释的redis源码

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
31
32
// 一些get/set函数直接使用宏来实现，来增加效率
#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))      // 设置自定义dup函数
#define listSetFreeMethod(l,m) ((l)->free = (m))    // 设置自定义free函数
#define listSetMatchMethod(l,m) ((l)->match = (m))  // 设置自定义match函数

#define listGetDupMethod(l) ((l)->dup)      // 获取dup函数
#define listGetFree(l) ((l)->free)          // 获取free函数
#define listGetMatchMethod(l) ((l)->match)  // 获取match函数

/* Prototypes */
list *listCreate(void);                     // 创建一个空的链表结构
void listRelease(list *list);               // 释放整个list，包括list内的各个节点
list *listAddNodeHead(list *list, void *value);     // 增加一个值为value的节点到list的头部
list *listAddNodeTail(list *list, void *value);     // 增加一个值为value的节点到list的尾部
list *listInsertNode(list *list, listNode *old_node, void *value, int after);       // 增加一个节点到指定节点的前/后，after表示插入前还是后
void listDelNode(list *list, listNode *node);           // 删除指定的节点，因为效率问题，没有判断node是否真的是该list的节点
listIter *listGetIterator(list *list, int direction);   // 创建指定list，指定方向的一个迭代器
listNode *listNext(listIter *iter);                     // 获取迭代器的下一个节点
void listReleaseIterator(listIter *iter);               // 释放迭代器内存
list *listDup(list *orig);                              // 完整的复制一个链表
listNode *listSearchKey(list *list, void *key);         // 从list中查找指定节点
listNode *listIndex(list *list, long index);            // 返回list中下标为index的节点，index如果为正值，表示从头开始的小标，且下标从0开始，即0为head，如果index为负值，表示从后往前的下标，且下标从-1开始，即-1表示tail
void listRewind(list *list, listIter *li);              // 重置迭代器为从头往后遍历
void listRewindTail(list *list, listIter *li);          // 重置迭代器为从后往前遍历
void listRotate(list *list);                            // 顺时针旋转list，将list的tail节点从尾部移除，插入到list头部