redis源码分析:链表实现

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
611
文章
12
评论
2020年2月14日23:04:22 评论

一、链表定义

链表在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. 从尾部开始返回对应索引位置上面的元素

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

历史上的今天
二月
14
马谦马谦马谦
  • 本文由 发表于 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: