Redis的设计和实现笔记-第三章链表

Redis的链表

因为C语言并没有内置的链表数据结构，所以Redis自己实现了链表。链表是列表数据结构的底层实现对象。Redis除了链表键外，发布与订阅，慢查询，监视器等功能也用到链表。Redis服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区。

链表的定义

typedef struct listNode {
    // 前置节点
    struct listNode * prev;
    // 后置节点
    struct listNode * next;
    // 节点的值
    void * value;
}listNode;

同时定义了list结构来方便操作链表

typedef struct list {
    // 表头节点
    listNode * head;
    // 表尾节点
    listNode * tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr,void *key);
} list;

通过list可以方便的操作一个链表的头尾指针，获取链表长度。dup、free和match成员则是用于实现多态链表所需的类型特定函数。

dup函数用于复制链表节点所保存的值。
free函数用于释放链表节点所保存的值
match函数用于对比链表节点所保存的值和另一个输入值是否相等。

Redis链表的特性

双向链表。通过prev和next指针可以方便的访问前置和后置节点。
无环。头节点和尾节点都指向null，对链表的访问以null为终点。
通过头节点和尾节点指针，可以直接访问头尾节点。
通过len属性可以直接过去到链表长度。
多态。通过dup和free和match三个指针函数，可以实现操作不同的数据类型。 Ps：但是最起码在一个list内的数据类型应该是一致的。从代码来看应该是不支持在一个list内使用不同的数据类型的。