redis 源码分析:链表实现

马谦马谦马谦 Redis评论555字数 1358阅读 4 分 31 秒阅读模式

一、链表定义

链表在 redis 中的使用十分广泛,例如列表的底层实现之一就是链表,包括发布、订阅等等功能都是有用到链表的。 redis 中链表在 adlist.hadlist.c 中实现,只用了 300+行代码,十分简单。

redis 中的链表是一个双向不循环的链表,两个核心的数据结构是 listNodelist,其中 listNode 的定义如下:

listNode 是链表节点定义,链表节点和平常用到差别不大,由一个数据域和两个分别指向前后节点的指针组成。

list 的定义为:

它和普通链表定义的不同点在于:除了包含首尾指针以及链表长度以外,链表的结构还包含了 3 个函数指针结构:

  • dup: 用于拷贝节点的函数。
  • free: 用于释放节点的函数。
  • match: 用于对比节点是否相等的函数。

链表的宏观结构:

redis源码分析:链表实现

二、链表操作

2.1 链表创建和释放

初始化的过程主要是创建链表对象,并初始化值:

释放链表:

2.2 插入节点

插入节点提供了三个函数,分别是从头部插入、从尾部插入以及从指定位置插入。

头插法:

尾插法,和头插法基本一致:

插入节点到指定位置:

2.3 删除节点

三、链表遍历

redis 在实现链表的时候,给链表的遍历单独创建了一套结构和方法。其中遍历的结构是 listIter,它包含了一个 listNode *的指针域和遍历方向 direction

direction 的作用是标记遍历方向是从头部往尾部遍历还是从尾部往头部遍历,获取一个 listIter 的方法:

配合 listNode 获取下一个节点的函数:

注意 listNext 函数只是获取当前 iter 指向的节点,并把 iter 指向下一个节点。为什么要把遍历操作单独抽离出来呢?

主要有以下几个目的:

  1. 外部遍历时不用重复编写遍历代码。前面已经说过,链表在 redis 很多场景都用到了,所有的结构共用一套遍历实现就可以了。
  2. 外部遍历的时候无需访问 list 的内部元素,充分做到了面向对象的理念。

四、其他

4.1 链表拷贝

4.2 链表查找

4.3 返回指定位置上的元素

传入索引,返回对应位置上的元素,支持从尾部索引:

五、总结

收获很大,主要是两个地方感触很深:

  1. 链表的遍历
  2. 从尾部开始返回对应索引位置上面的元素

其实实现并不算难,只是实现的思路和想法很新颖,很值得学习!

 
马谦马谦马谦
  • 本文由 马谦马谦马谦 发表于 2020 年 2 月 14 日 23:04:22
  • 转载请务必保留本文链接:https://www.dyxmq.cn/databases/redis/linked-list-in-redis.html
匿名

发表评论

匿名网友
:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:
确定

拖动滑块以完成验证