redis源码阅读--双端链表

em….链表是一种常用的数据结构。双端链表也是比较熟悉的了，redis的实现还是有必要研究一下的。

redis中双端链表的应用

redis的列表类型

双端lian链表是redis列表类型的底层实现之一，当对列表类型的键进行操作–例如rpush、lpop或者llen等命令，程序在底层操作的可能就是双端链表。

//这里之所以使用“可能”，是因为redis的列表其实使用两种数据结构作为底层实现：
//1. 双端链表
//2. 压缩列表
//因为双端链表占用的内存比压缩列表要多，所以当创建新的列表键时，列表会优先考虑使用压缩列表作为底层实现，并且在有需要的时候，才会从压缩列表实现转换到双端列表的实现。

redis自身功能

除了实现列表类型，双端链表还被redis内部模块所应用：

事务模块使用双端列表依序保存输入的命令
服务器模块使用双端链表来保存多个客户端
订阅/发送模块使用双端列表来保存订阅模式的多个客户端
事件模块使用双端链表来保存时间事件

双端链表的实现

双端链表的实现由list和listNode这两个数据结构构成。

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; //节点数量
}

这里的void表示双端列表对于节点保存的值的类型不做限制。
从数据结构的定义中可以看出：

1
2
3

+ list的遍历可以双向进行
+ list对链表头和表尾进行插入的复杂度都为0(1)---从而可以做到高效实现lpush，rpop，rpoplpush等命令
+ list带有保存节点数量的len属性，所以计算链表长度的复杂度仅为0（1），和之前sds一样读取长度不会成为性能瓶颈。

操作双端链表的函数如下：

list *listCreate(void);
void listRelease(list *list);
void listEmpty(list *list);
list *listAddNodeHead(list *list, void *value);
list *listAddNodeTail(list *list, void *value);
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);
void listJoin(list *l, list *o);

迭代器

redis还为双端链表实现了一个迭代器，这个迭代器可以从两个方向对双端列表进行迭代：

沿着next指针前进，从表头到表尾
沿着节点的prev指针前进，从表尾向表头

定义如下：

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

#define AL_START_HEAD 0
#define AL_START_TAIL 1

其中，direction记录迭代从哪里开始，AL_START_HEA表示从表头开始，AL_START_TAIL 1表示从表尾开始。

总结

redis实现了自己的双端链表，其主要的作用用来作为redis列表类型的底层实现以及作为通用数据结构，被其他功能模块所使用。总体来说，这部分的代码不是很复杂，基本的实现都是当初学习c语言实现过的一些类似的东西，但是redis的设计者为其加上一点点额外的东西感觉就可以使得这些熟悉的东西变得灵活又作用强大，比如那个len字段的设计，看起来好像挺理所应当，但是在开始设计时，确实很难意识到这一点，往往看到别人的代码这样用才恍然大悟，所以学习的道路还很漫长。