1. redis中的链表
在redis中链表的应用非常广泛,例如列表键的底层实现之一就是链表。而且,在redis中的链表结构被实现成为双向链表,因此,在头部和尾部进行的操作就会非常快。
|
|
2. 链表的实现
2.1 链表节点的实现
每个链表节点由adlist.h/listNode来表示
listNode结构通过prev和next指针就组成了双向链表。刚才通过列表键生成的双向链表如下图:
使用双向链表的好处:
prev和next指针:获取某个节点的前驱节点和后继节点复杂度为O(1)。
2.2 表头的实现
redis还提供了一个表头,用于存放上面双向链表的信息,它由adlist.h/list结构表示:
将表头和双向链表连接起来,如图:
利用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)。
3.2 链表迭代器
在adlist.h文件中,使用C语言实现了迭代器,源码如下:
在listDup函数中就使用了迭代器,listDup函数的定义如下:
迭代器的好处:
- 提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。
- 将指针操作进行了统一封装,代码可读性增强。
###3.3 adlist.c文件
刚才所有函数的定义如下: