Redis的链表结构 _Redis

1. redis中的链表
在redis中链表的应用非常广泛，例如列表键的底层实现之一就是链表。而且，在redis中的链表结构被实现成为双向链表，因此，在头部和尾部进行的操作就会非常快。通过列表键的命令感受一下双向链表
127.0.0.1:6379> LPUSH list a b c //依次在链表头部插入a、b、c(integer) 3127.0.0.1:6379> RPUSH list d e f //依次在链表尾部插入d、e、f(integer) 6127.0.0.1:6379> LRANGE list 0 -1 //查看list的值1) "c"2) "b"3) "a"4) "d"5) "e"6) "f"2. 链表的实现
2.1 链表节点的实现
每个链表节点由adlist.h/listNode来表示
typedef struct listNode { struct listNode *prev; //前驱节点，如果是list的头结点，则prev指向NULL struct listNode *next;//后继节点，如果是list尾部结点，则next指向NULL void *value; //万能指针，能够存放任何信息} listNode;listNode结构通过prev和next指针就组成了双向链表。刚才通过列表键生成的双向链表如下图

文章插图

使用双向链表的好处：

prev和next指针：获取某个节点的前驱节点和后继节点复杂度为O(1) 。

2.2%20表头的实现
redis还提供了一个表头，用于存放上面双向链表的信息，它由adlist.h/list结构表示：
typedef%20struct%20list%20{%20listNode%20*head;%20//链表头结点指针%20listNode%20*tail;%20//链表尾结点指针%20//下面的三个函数指针就像类中的成员函数一样%20void%20*(*dup)(void%20*ptr);%20//复制链表节点保存的值%20void%20(*free)(void%20*ptr);%20//释放链表节点保存的值%20int%20(*match)(void%20*ptr,%20void%20*key);%20//比较链表节点所保存的节点值和另一个输入的值是否相等%20unsigned%20long%20len;%20//链表长度计数器}%20list;
利用list表头管理链表信息的好处：
head和tail指针：对于链表的头结点和尾结点操作的复杂度为O(1) 。
len 链表长度计数器：获取链表中节点数量的复杂度为O(1) 。
dup、free和match指针：实现多态，链表节点listNode使用万能指针void *保存节点的值，而表头list使用dup、free和match指针来针对链表中存放的不同对象从而实现不同的方法
3. 链表结构源码剖析
3.1 adlist.h文件
针对list结构和listNode结构的赋值和查询操作使用宏进行封装，而且一下操作的复杂度均为O(1) 。
#define listLength(l) ((l)->len) //返回链表l节点数量
#define listFirst(l) ((l)->head) //返回链表l的头结点地址
#define listLast(l) ((l)->tail) //返回链表l的尾结点地址
#define listPrevNode(n) ((n)->prev) //返回节点n的前驱节点地址
#define listNextNode(n) ((n)->next) //返回节点n的后继节点地址
#define listNodeValue(n) ((n)->value) //返回节点n的节点值
#define listSetDupMethod(l,m) ((l)->dup = (m)) //设置链表l的复制函数为m方法
#define listSetFreeMethod(l,m) ((l)->free = (m)) //设置链表l的释放函数为m方法
#define listSetMatchMethod(l,m) ((l)->match = (m)) //设置链表l的比较函数为m方法
#define listGetDupMethod(l) ((l)->dup) //返回链表l的赋值函数
#define listGetFree(l) ((l)->free) //返回链表l的释放函数
#define listGetMatchMethod(l) ((l)->match) //返回链表l的比较函数
链表操作的函数原型（Prototypes）：
list *listCreate(void); //创建一个表头void listRelease(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);//在list中，根据after在old_node节点前后插入值为value的节点。void listDelNode(list *list, listNode *node); //从list删除node节点listIter *listGetIterator(list *list, int direction); //为list创建一个迭代器iteratorlistNode *listNext(listIter *iter); //返回迭代器iter指向的当前节点并更新iter void listReleaseIterator(listIter *iter); //释放iter迭代器list *listDup(list *orig); //拷贝表头为orig的链表并返回listNode *listSearchKey(list *list, void *key); //在list中查找value为key的节点并返回listNode *listIndex(list *list, long index); //返回下标为index的节点地址void listRewind(list *list, listIter *li); //将迭代器li重置为list的头结点并且设置为正向迭代void listRewindTail(list *list, listIter *li); //将迭代器li重置为list的尾结点并且设置为反向迭代void listRotate(list *list); //将尾节点插到头结点3.2 链表迭代器
在adlist.h文件中，使用C语言实现了迭代器，源码如下：