Redis 中List 及 quicklist实现 2

上一篇中看了List的使用方式、quicklist中的各个结构体，这一篇来看看quicklist里面的几个核心函数，quicklistCreate函数、quicklistCreateNode函数、quicklistPush函数、quicklistPop函数。

接下来我们通过源码看一下quicklist中是如何借鉴STL中deque的这种实现思想来完成对于sdlist及ziplist有点的结合的，并且在时间和空间是如何做的均衡，来达到“quick”的效果。

我们打开quicklist.c文件，找到第94行。

首先完成了对于一个quicklist结构体的指针，然后对quicklist进行内存分配操作，之后再设置首尾指针，再指定quicklist的长度、数据项总和、压缩深度、ziplist的的大小限定（这个值可以有五个取值，-1：每个节点的ziplist字节数不能超过4kb,-2：每个节点的ziplist字节数不能超过8kb,-3：每个节点的ziplist字节数不能超过16kb,-4：每个节点的字节数不能超过32kb,-5：每个节点的字节数不能超过64kb, 默认是不能超过4kb的）

image.png

创建完quicklist之后，下一步就是创建quicklist节点了,看一下quicklist的第138行

这个过程和创建quicklist基本上是一致的，声明指针、申请内存、初始化ziplist指针、初始化数据项、ziplist的大小、初始化prev、next指针、初始化节点编码方式默认是QUICK_NODE_ENCODING_RAW、初始化数据的存放方式默认是QUICKLIST_NODE_CONTAINER_ZIPLIST，最后初始完压缩标示然后结束。

image.png

看完初始化操作之后，接下来是PUSH操作：

不管是LPUSH还是RPUSH都包含两个步骤，如果插入节点的ziplist大小没有超过限制直接用ziplistPush函数压入，如果ziplist的大小超过了限制，则新创建一个quicklist来进行压入。

image.png

然后来看一下这两个函数：

likely是linux提供的可选择的编译优化方法，可以讲分支专一的信息提供给编译器，然后减少指令跳转带来的性能下降（likely是编译器级别的优化）。

首先判断首/尾是否允许插入（首部节点的大小和fill参数做比较）然后如果允许插入世界调用ziplistpush插入，然后更新首部大小即可以了，如果节点满了，看一些else里面的内容，就需要重新创建一个节点，将新节点压入心创建的ziplist中，并且与新创建的quicklist节点关联起来，同时更新大小，然后创建一个新的ziplist节点，完成压入，更新数据项等。如果反悔的quicklist指针没变，则返回0，否则返回1。

image.png

接下来看一下quicklistPop函数，然后具体的逻辑其实是在quicklistPopCustom中实现的。

就是进行Pop操作，执行成功返回1，失败返回0，如果弹出的节点是字符串，那么data、sz存放弹出字符串值，如果弹出节点是整型，slong存放弹出节点的整型值。

image.png

然后具体看一下quicklistPopCustom函数，执行成功返回1，失败返回0，如果弹出的节点是字符串，那么data、sz存放弹出字符串值，如果弹出节点是整型，slong存放弹出节点的整型值。

首先判断弹出位置首部或者尾部，如果没有数据直接return 0，然后获取quicklist的节点（ziplist），再获取ziplist的节点，然后获取节点的值，如果是字符串值，通过_quicklistSaver深拷贝取出返回值，如果是整型的则字符串设置为NULL，弹出节点的整型值，删除该节点。

image.png

这里_quicklistSaver 深拷贝取值的原因是避免二次释放。

image.png

quicklist核心的API就这几个，但Redis实际上是实现了好多的，比如说：

1、比较两个quicklist结构数据的：quicklistCount

2、从节点node中取出LZF压缩编码后的数据：quicklistGetLzf

3、翻转quicklist：quicklistRotate

4、删除ziplist节点entry：quicklistDelEntry

5、在node节点前添加一个value：quicklistInsertBefore

6、在node节点后添加一个value：quicklistInsertAfter

7、将ziplist转换为quicklist：*quicklistCreateFromZiplist