Redis源码剖析——adlist
adlist是一个普通的双向链表
为什么叫adlist?
redis作者算是首创了这种命名风格,axxxxx,后面我们还会看到类似的文件命名方式,意即“一个xxxxx”。
虽然是普通的链表,但Redis的adlist绝对也是C下双向链表的实现范式。
基本结构和方法的原型声明与定义(adlist.h)
节点的定义,一前一后两个指针,void*的值以适配所有数据类型
迭代器的定义,其中direction域用于指示遍历方向,用迭代器所带来的解耦在后面会明显体现出来
一个双向链表的所有元信息集成于list中
dup为复制链表的方法;free为释放节点数据域(value)的方法;match方法用于指明在链表中搜索某个节点时判断是否匹配到。常规类型显然是不需要这些方法的,只有对于某些非原生类型需要指定这些方法。
head、tail分别是链表的头尾指针,len指示链表的长度。
想想自己曾写过的链表有这种设计吗?
下面是一些宏函数,非常简单但是非常实用
下面是所有方法的原型声明
最后注意这两个宏,这两个宏用于指明迭代器的遍历方向
实现(adlist.c)
整个实现唯一的依赖就是zmalloc,zmalloc用于redis的内存管理,使用时与glibc原生的malloc一样,后面会进行剖析
创建一个链表结构并做一些初始化,此时链表中还没有任何节点
释放整个链表,包括释放每个节点的数据域,此时free方法若是不为空则会调用free去释放数据域,释放完数据域后再释放节点本身
在头部插入一个节点,不多说
在尾部插入一个节点,不多说
在链表的指定节点的前或后插入一个新节点,入参after若不为0则在old_node后面插入,否则在前面。若是old_node本身是头或尾节点时,对应的前插或后插需要更新相应的头尾,同时要检查新插入节点的前后节点的存在性,并对指针进行相应更行。这段代码也是写得相当精炼了,非常干净漂亮,大多数人写这个过程会冗余不少判断。
删除指定节点,注意节点本身是头尾的时候应该更新list的head或tail,同时只要是删除操作就应考虑是否需要用free方法去释放数据域,最后调节链表的长度。
获取一个迭代器时通过direction参数来确定是正向迭代器还是反向迭代器,正向迭代器从头部开始顺序遍历,反向迭代器从尾部开始逆序访问;
释放迭代器可以直接zfree;
值得注意的是,这里的迭代器是左开右开区间
将迭代器重新定位到头部或尾部,并且会直接对迭代器的方向进行修改
返回迭代器的所指向的下一个节点并且迭代器往后(或往前)走一步,要注意一个迭代器的初始next指针指向head或者tail节点
同数组下标一样定位到链表中某个节点,若index >= 0,则head节点为index = 0,head->next index = 1,以此类推;若index < 0,tail节点为index = -1,tail->prev为 index = -2,以此类推;若index超出范围则返回NULL。
链表的右旋操作,即把尾节点移到链表头部
如果什么时候你需要用到一个双向链表,别忘了这儿有个现成的轮子~
- 原文作者:Fh
- 原文链接:http://fhstack.github.io/post/2019-03-24-redisyuanmapouxiadlist/
- 版权声明:本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可,非商业转载请注明出处(作者,原文链接),商业转载请联系作者获得授权。