Redis 3.0.4 链表

redis链表的实现是双向链表.

每个链表节点的结构如下：

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;

结构里面包含了迭代器，迭代器的结构

//迭代器
typedef struct listIter {
    listNode *next;
    int direction; //表明迭代方向
} listIter;
#define AL_START_HEAD 0 //正向迭代器
#define AL_START_TAIL 1 //反向迭代器

将表头和节点结合起来，结构如图

adlist.c里定义了一些简单的对链表的操作，函数中如查找key，copy链表都是通过迭代器进行操作。

redis的链表实现特性：

1. 双端：链表中有pre和next指针，获取某个节点的next节点或者pre节点的时间复杂度都是O(1);
2. 无环：表头节点的pre和next都是指向null，对于链表的遍历都是以null结束；
3. 带有表头指针和表尾指针：通过list结构的head和tail指针，获取list的表头节点和表尾节点的时间复杂度都是O(1);
4. 带有长度计数器：list结构中有len属性，可以获取链表的长度，时间复杂度是O(1);
5. 多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性设置类型特定函数，所以链表可以用于保存各种不同类型的值。

链表被广泛用于实现Redis的各种功能，比如链表键、发布与订阅、慢查询、监视器等。