adlist是一个普通的双向链表

为什么叫adlist?

image.png
1553417242987884.png

redis作者算是首创了这种命名风格,axxxxx,后面我们还会看到类似的文件命名方式,意即“一个xxxxx”。

虽然是普通的链表,但Redis的adlist绝对也是C下双向链表的实现范式。

基本结构和方法的原型声明与定义(adlist.h)

image.png
1553418911476939.png

节点的定义,一前一后两个指针,void*的值以适配所有数据类型

image.png
1553419116552078.png

迭代器的定义,其中direction域用于指示遍历方向,用迭代器所带来的解耦在后面会明显体现出来

image.png
1553419282440517.png

一个双向链表的所有元信息集成于list中

dup为复制链表的方法;free为释放节点数据域(value)的方法;match方法用于指明在链表中搜索某个节点时判断是否匹配到。常规类型显然是不需要这些方法的,只有对于某些非原生类型需要指定这些方法。

head、tail分别是链表的头尾指针,len指示链表的长度。

想想自己曾写过的链表有这种设计吗?

下面是一些宏函数,非常简单但是非常实用

image.png
1553419889629353.png

下面是所有方法的原型声明

image.png
1553420059224731.png

最后注意这两个宏,这两个宏用于指明迭代器的遍历方向

image.png
1553420183361141.png

实现(adlist.c)

image.png
1553420472959544.png

整个实现唯一的依赖就是zmalloc,zmalloc用于redis的内存管理,使用时与glibc原生的malloc一样,后面会进行剖析


image.png
1553420794685555.png

创建一个链表结构并做一些初始化,此时链表中还没有任何节点


image.png
1553421046425811.png

释放整个链表,包括释放每个节点的数据域,此时free方法若是不为空则会调用free去释放数据域,释放完数据域后再释放节点本身


image.png
1553421164538571.png

在头部插入一个节点,不多说


image.png
1553421310285059.png

在尾部插入一个节点,不多说


image.png
1553421363261646.png

在链表的指定节点的前或后插入一个新节点,入参after若不为0则在old_node后面插入,否则在前面。若是old_node本身是头或尾节点时,对应的前插或后插需要更新相应的头尾,同时要检查新插入节点的前后节点的存在性,并对指针进行相应更行。这段代码也是写得相当精炼了,非常干净漂亮,大多数人写这个过程会冗余不少判断。


image.png
1553421764846887.png

删除指定节点,注意节点本身是头尾的时候应该更新list的head或tail,同时只要是删除操作就应考虑是否需要用free方法去释放数据域,最后调节链表的长度。


image.png
1553421928792582.png

获取一个迭代器时通过direction参数来确定是正向迭代器还是反向迭代器,正向迭代器从头部开始顺序遍历,反向迭代器从尾部开始逆序访问;

释放迭代器可以直接zfree;

值得注意的是,这里的迭代器是左开右开区间


image.png
1553422104507228.png

将迭代器重新定位到头部或尾部,并且会直接对迭代器的方向进行修改


image.png
1553422394922054.png

返回迭代器的所指向的下一个节点并且迭代器往后(或往前)走一步,要注意一个迭代器的初始next指针指向head或者tail节点


image.png
1553430122284899.png

同数组下标一样定位到链表中某个节点,若index >= 0,则head节点为index = 0,head->next index = 1,以此类推;若index < 0,tail节点为index = -1,tail->prev为 index = -2,以此类推;若index超出范围则返回NULL。


image.png
1553430352242295.png

链表的右旋操作,即把尾节点移到链表头部


如果什么时候你需要用到一个双向链表,别忘了这儿有个现成的轮子~