上一篇中看了List的使用方式、quicklist中的各個結(jié)構(gòu)體，這一篇來看看quicklist里面的幾個核心函數(shù)，quicklistCreate函數(shù)、quicklistCreateNode函數(shù)、quicklistPush函數(shù)、quicklistPop函數(shù)。

接下來我們通過源碼看一下quicklist中是如何借鑒STL中deque的這種實(shí)現(xiàn)思想來完成對于sdlist及ziplist有點(diǎn)的結(jié)合的，并且在時間和空間是如何做的均衡，來達(dá)到“quick”的效果。

我們打開quicklist.c文件，找到第94行。

首先完成了對于一個quicklist結(jié)構(gòu)體的指針，然后對quicklist進(jìn)行內(nèi)存分配操作，之后再設(shè)置首尾指針，再指定quicklist的長度、數(shù)據(jù)項(xiàng)總和、壓縮深度、ziplist的的大小限定（這個值可以有五個取值，-1：每個節(jié)點(diǎn)的ziplist字節(jié)數(shù)不能超過4kb,-2：每個節(jié)點(diǎn)的ziplist字節(jié)數(shù)不能超過8kb,-3：每個節(jié)點(diǎn)的ziplist字節(jié)數(shù)不能超過16kb,-4：每個節(jié)點(diǎn)的字節(jié)數(shù)不能超過32kb,-5：每個節(jié)點(diǎn)的字節(jié)數(shù)不能超過64kb, 默認(rèn)是不能超過4kb的）

image.png

創(chuàng)建完quicklist之后，下一步就是創(chuàng)建quicklist節(jié)點(diǎn)了,看一下quicklist的第138行

這個過程和創(chuàng)建quicklist基本上是一致的，聲明指針、申請內(nèi)存、初始化ziplist指針、初始化數(shù)據(jù)項(xiàng)、ziplist的大小、初始化prev、next指針、初始化節(jié)點(diǎn)編碼方式默認(rèn)是QUICK_NODE_ENCODING_RAW、初始化數(shù)據(jù)的存放方式默認(rèn)是QUICKLIST_NODE_CONTAINER_ZIPLIST，最后初始完壓縮標(biāo)示然后結(jié)束。

image.png

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

不管是LPUSH還是RPUSH都包含兩個步驟，如果插入節(jié)點(diǎn)的ziplist大小沒有超過限制直接用ziplistPush函數(shù)壓入，如果ziplist的大小超過了限制，則新創(chuàng)建一個quicklist來進(jìn)行壓入。

image.png

然后來看一下這兩個函數(shù)：

likely是linux提供的可選擇的編譯優(yōu)化方法，可以講分支專一的信息提供給編譯器，然后減少指令跳轉(zhuǎn)帶來的性能下降（likely是編譯器級別的優(yōu)化）。

首先判斷首/尾是否允許插入（首部節(jié)點(diǎn)的大小和fill參數(shù)做比較）然后如果允許插入世界調(diào)用ziplistpush插入，然后更新首部大小即可以了，如果節(jié)點(diǎn)滿了，看一些else里面的內(nèi)容，就需要重新創(chuàng)建一個節(jié)點(diǎn)，將新節(jié)點(diǎn)壓入心創(chuàng)建的ziplist中，并且與新創(chuàng)建的quicklist節(jié)點(diǎn)關(guān)聯(lián)起來，同時更新大小，然后創(chuàng)建一個新的ziplist節(jié)點(diǎn)，完成壓入，更新數(shù)據(jù)項(xiàng)等。如果反悔的quicklist指針沒變，則返回0，否則返回1。

image.png

接下來看一下quicklistPop函數(shù)，然后具體的邏輯其實(shí)是在quicklistPopCustom中實(shí)現(xiàn)的。

就是進(jìn)行Pop操作，執(zhí)行成功返回1，失敗返回0，如果彈出的節(jié)點(diǎn)是字符串，那么data、sz存放彈出字符串值，如果彈出節(jié)點(diǎn)是整型，slong存放彈出節(jié)點(diǎn)的整型值。

image.png

然后具體看一下quicklistPopCustom函數(shù)，執(zhí)行成功返回1，失敗返回0，如果彈出的節(jié)點(diǎn)是字符串，那么data、sz存放彈出字符串值，如果彈出節(jié)點(diǎn)是整型，slong存放彈出節(jié)點(diǎn)的整型值。

首先判斷彈出位置首部或者尾部，如果沒有數(shù)據(jù)直接return 0，然后獲取quicklist的節(jié)點(diǎn)（ziplist），再獲取ziplist的節(jié)點(diǎn)，然后獲取節(jié)點(diǎn)的值，如果是字符串值，通過_quicklistSaver深拷貝取出返回值，如果是整型的則字符串設(shè)置為NULL，彈出節(jié)點(diǎn)的整型值，刪除該節(jié)點(diǎn)。

image.png

這里_quicklistSaver 深拷貝取值的原因是避免二次釋放。

image.png

quicklist核心的API就這幾個，但Redis實(shí)際上是實(shí)現(xiàn)了好多的，比如說：

1、比較兩個quicklist結(jié)構(gòu)數(shù)據(jù)的：quicklistCount

2、從節(jié)點(diǎn)node中取出LZF壓縮編碼后的數(shù)據(jù)：quicklistGetLzf

3、翻轉(zhuǎn)quicklist：quicklistRotate

4、刪除ziplist節(jié)點(diǎn)entry：quicklistDelEntry

5、在node節(jié)點(diǎn)前添加一個value：quicklistInsertBefore

6、在node節(jié)點(diǎn)后添加一個value：quicklistInsertAfter

7、將ziplist轉(zhuǎn)換為quicklist：*quicklistCreateFromZiplist