redis设计与实现——链表

发表于

redis设计与实现——链表

链表是数据结构中一种很常见的实现类型，redis也不例外，其主要实现在adlist.h和adlist.c里。

链表与链表节点的实现

如下所示，每个链表节点都用listNode结构来表示，并且用list来持有整个链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct listNode {
    struct listNode *prev; // 前置节点
    struct listNode *next; // 后置节点
    void *value; /节点值
} listNode;

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;

由此可见，redis的链表是一个双端的(具备prev和next指针)、无环的(表头节点的prev和表尾节点的next都指向NULL)、带链表长度计数器(len属性)、多态(使用void*指针来保存节点值)。

链表和链表节点的API

函数 作用
listEmpty 移除链表所有元素，但不销毁list本身
listRelease 销毁整个链表
listAddNodeHead 添加一个节点到链表头
listAddNodeTail 添加一个节点到链表尾
listInsertNode 可选地将新节点插入到指定节点的前面或者后面
listDelNode 删除一个节点
listGetIterator 返回链表头部或者尾部的迭代器
listReleaseIterator 销毁迭代器
listNext 返回迭代器的下一个链表节点
listDup 拷贝整个链表
listSearchKey 在列表中搜索与给定键匹配的节点。（需要实现定义match函数）
listIndex 返回链表中特定索引的节点，可以使用负数
listRotate 反转链表——将尾部节点插入到头部
listJoin 合并两个链表，并把其中一个置空