簡(jiǎn)介

壓縮列表ziplist本質(zhì)上就是一個(gè)字節數組，是Redis為了節約內存而設計的一種線(xiàn)性數據結構，可以包含多個(gè)元素，每個(gè)元素可以是一個(gè)字節數組或一個(gè)整數。
Redis的有序集合、散列和列表都直接或者間接使用了壓縮列表。當有序集合或散列表的元素個(gè)數比較少，且元素都是短字符串時(shí)，Redis便使用壓縮列表作為其底層數據存儲結構。列表使用快速鏈表（quicklist）數據結構存儲，而快速鏈表就是雙向鏈表與壓縮列表的組合。
ziplist 壓縮列表是一個(gè)特殊編碼的雙端鏈表（內存上連續），為了盡可能節省內存而設計的。ziplist 可以存儲字符串或者整數值，其中整數被編碼保存為實(shí)際的整數，而不是字符數組。ziplist 支持 O(1) 的時(shí)間復雜度在列表的兩端進(jìn)行 push 和 pop 操作。然而因為這些操作都需要對整個(gè) ziplist 進(jìn)行內存重分配（因為是一塊連續的內存），所以操作的實(shí)際復雜度和 ziplist 占用的內存大小有關(guān)。在 7.0 版本里，ziplist 已經(jīng)全面被 listpack 替換了（主要是因為連鎖更新較影響性能）

壓縮列表的存儲結構

Redis使用字節數組表示一個(gè)壓縮列表，壓縮列表結構如下所示：

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

壓縮列表各字段的含義如下：

• zlbytes：是一個(gè) 32 位無(wú)符號整數（4 bytes），記錄整個(gè) ziplist 占用的內存字節數，包含 4 個(gè)字節的 zlbytes 本身。
• zltail：是一個(gè) 32 位無(wú)符號整數（4 bytes），記錄 ziplist 到尾節點(diǎn)的位置偏移量。通過(guò)這個(gè)偏移量我們可以直接定位到表尾節點(diǎn)，例如進(jìn)行表尾的 pop 操作，不然得完整遍歷 ziplist。
• zllen：是一個(gè) 16 位無(wú)符號整數（2 bytes），記錄 ziplist 里的節點(diǎn)數量。由于它設計只用 2 個(gè)字節進(jìn)行存儲，2 字節實(shí)際最大可以表示為 2^16 - 1 即: 65535。當數字小于它時(shí)，則 zllen 的值就是實(shí)際的節點(diǎn)數量（O(1) 時(shí)間復雜度）, 也就是注釋里的 2^16 - 2 的含義。否則當 zllen 值為 65535 時(shí)即 2^16-1，用它作為一個(gè)標識，表示需要完整遍歷整個(gè)壓縮列表 O(N) 時(shí)間復雜度才能計算出真實(shí)的節點(diǎn)數量。所以 ziplist 不適合存儲過(guò)多元素（遍歷計算節點(diǎn)數量開(kāi)銷(xiāo)很大，且我們假設它只用于元素數量較少的場(chǎng)景）。
• entryX：壓縮列表存儲的元素，可以是字節數組或者整數，長(cháng)度不限。entry的編碼結構將在后面詳細介紹。
• zlend： 是一個(gè) 8 位無(wú)符號整數（1 byte），是一個(gè)特殊的標志位來(lái)標記壓縮列表的結尾，0xFF(十進(jìn)制表示為: 255)。其它正常節點(diǎn)不會(huì )有以這個(gè)字節開(kāi)頭的，在遍歷 ziplist 的時(shí)候通過(guò)這個(gè)標記來(lái)判斷是否遍歷結束。

元素的存儲結構

壓縮列表元素的存儲結構如下所示：

<prevlen> <encoding> <entry-data>

每一個(gè) ziplist entry 壓縮列表節點(diǎn)在實(shí)際的節點(diǎn)數據之前都會(huì )包含兩部分元數據，也叫 entry header。

1. prevlen: 前置節點(diǎn)的字節長(cháng)度，以支持我們從后往前遍歷（通過(guò)指針偏移量定位前一個(gè)節點(diǎn)）
2. encoding: 當前節點(diǎn) entry-data 節點(diǎn)數據部分的類(lèi)型和編碼，例如存儲的是整數還是字符串，類(lèi)型下還會(huì )細分多種編碼。

有時(shí)候節點(diǎn)可以不用有 entry-data，可以在 encoding 部分直接存儲節點(diǎn)數據。例如一些小整數，可以直接在 encoding 部分用幾位來(lái)存儲表示，對每一位都物盡其用。此時(shí)元素的存儲結構為：

<prevlen> <encoding>

當前節點(diǎn)的前節點(diǎn)字節長(cháng)度，prevlen 的編碼方式如下（同時(shí)我們將存儲 prevlen 所需的字節數為 prevlensize，即下面的 1 或者 5 字節）

• 如果前節點(diǎn)的字節長(cháng)度 小于 254 字節，那么 prevlen 使用 1 個(gè)字節來(lái)保存它，一個(gè) 8 位無(wú)符號的整數。

<prevlen from 0 to 253>    <encoding>    <entry>

• prevlen：前一個(gè)entry長(cháng)度，介于(0,253)
• encoding:當前節點(diǎn)的實(shí)際數據類(lèi)型以及長(cháng)度
• entry:當前節點(diǎn)的實(shí)際數據
• 如果前節點(diǎn)的字節長(cháng)度 大于等于254 字節，那么 prevlen 使用 5 個(gè)字節來(lái)保存它：

0xFE   <4 bytes unsigned little endian prevlen>    <encoding>     <entry>

• 0xFE: zlend 標識，值為 254（1 字節）
• <4 bytes unsigned little endian prevlen>: 當前節點(diǎn)的實(shí)際長(cháng)度（4 字節）
• <encoding>: 當前節點(diǎn)的實(shí)際數據類(lèi)型以及長(cháng)度
• <entry>: 當前節點(diǎn)的實(shí)際數據

壓縮列表元素編碼：

Redis 常見(jiàn)的encoding：

#define ZIP_STR_MASK 0xc0
#define ZIP_INT_MASK 0x30
#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)
#define ZIP_INT_16B (0xc0 | 0<<4)
#define ZIP_INT_32B (0xc0 | 1<<4)
#define ZIP_INT_64B (0xc0 | 2<<4)
#define ZIP_INT_24B (0xc0 | 3<<4)
#define ZIP_INT_8B 0xfe

解碼結構體

對于壓縮列表中的任意元素，獲取前一個(gè)元素的長(cháng)度、判斷存儲的數據類(lèi)型、獲取數據內容等都需要經(jīng)過(guò)復雜的解碼運算。解碼后的結果應該被緩存起來(lái)，為此定義了結構體zlentry，用于表示解碼后的壓縮列表元素，單純的用來(lái)臨時(shí)存儲解碼之后的元素信息。

typedef struct zlentry {
    unsigned int prevrawlensize;
    unsigned int prevrawlen;
    unsigned int lensize;
    unsigned int len;
    unsigned int headersize;
    unsigned char encoding;
    unsigned char *p;
} zlentry;

• prevrawlensize: 存儲下面 prevrawlen 所需要的字節數
• prevrawlen: 存儲前一個(gè)節點(diǎn)的字節長(cháng)度
• len: 存儲當前節點(diǎn)的字節長(cháng)度
• headersize: prevrawlensize + lensize 當前節點(diǎn)的頭部字節，其實(shí)是 prevlen + encoding 兩項占用的字節數
• encoding: 存儲當前節點(diǎn)的數據編碼格式
• p: 指向當前節點(diǎn)開(kāi)頭第一個(gè)字節的指針

函數zipEntry用來(lái)解碼壓縮列表的元素，填充為zlentry結構體。

static inline void zipEntry(unsigned char *p, zlentry *e) {
    ZIP_DECODE_PREVLEN(p, e->prevrawlensize, e->prevrawlen);
    ZIP_ENTRY_ENCODING(p + e->prevrawlensize, e->encoding);
    ZIP_DECODE_LENGTH(p + e->prevrawlensize, e->encoding, e->lensize, e->len);
    assert(e->lensize != 0);
    e->headersize = e->prevrawlensize + e->lensize;
    e->p = p;
}

解碼主要分為下面幾個(gè)步驟：

解碼前節點(diǎn)長(cháng)度

根據 p 目前的指針，獲取 entry 的 prevlen 的值；

• 如果prevlen一個(gè)字節編碼，對應字節 (ptr)[0] 的值就是 prevlen。
• 如果prevlen五個(gè)字節編碼，具體的 prevlen 是存儲在后四個(gè)字節，后四個(gè)字節進(jìn)行位運算獲得實(shí)際的 prevlen

#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do {                     \
    ZIP_DECODE_PREVLENSIZE(ptr, prevlensize);                                  \
    if ((prevlensize) == 1) {                                                  \
        (prevlen) = (ptr)[0];                                                  \
    } else { /* prevlensize == 5 */                                            \
        (prevlen) = ((ptr)[4] << 24) |                                         \
                    ((ptr)[3] << 16) |                                         \
                    ((ptr)[2] <<  8) |                                         \
                    ((ptr)[1]);                                                \
    }                                                                          \
} while(0)

根據prevlensize的長(cháng)度判斷prevlen的長(cháng)度，如果(ptr)[0] < ZIP_BIG_PREVLEN時(shí)（ZIP_BIG_PREVLEN=254），則prevlen長(cháng)度為1，否則長(cháng)度為5。

#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do {                          \
    if ((ptr)[0] < ZIP_BIG_PREVLEN) {                                            \
        (prevlensize) = 1;                                                       \
    } else {                                                                     \
        (prevlensize) = 5;                                                       \
    }                                                                            \
  } while(0)

解碼encoding

p+prevrawlensize 位置的第一個(gè)字節，獲取 entry 當前的 encoding 屬性，保存在 encoding 變量中時(shí)間復雜度 O(1)。

#define ZIP_ENTRY_ENCODING(ptr, encoding) do {  \
    (encoding) = ((ptr)[0]); \
    if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
} while(0)

解碼長(cháng)度

p+prevrawlensize 根據 encoding 獲取 entry 的 len 相關(guān)屬性。 ptr[0]<11000000說(shuō)明是字節數組，前兩個(gè)比特為字節數組編碼類(lèi)型

進(jìn)制轉換：echo "ibase=16;obase=2;C0" | bc

#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {                    \
    if ((encoding) < ZIP_STR_MASK) {                                           \
        if ((encoding) == ZIP_STR_06B) {                                       \
            (lensize) = 1;                                                     \
            (len) = (ptr)[0] & 0x3f;                                           \
        } else if ((encoding) == ZIP_STR_14B) {                                \
            (lensize) = 2;                                                     \
            (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1];                       \
        } else if ((encoding) == ZIP_STR_32B) {                                \
            (lensize) = 5;                                                     \
            (len) = ((uint32_t)(ptr)[1] << 24) |                               \
                    ((uint32_t)(ptr)[2] << 16) |                               \
                    ((uint32_t)(ptr)[3] <<  8) |                               \
                    ((uint32_t)(ptr)[4]);                                      \
        } else {                                                               \
            (lensize) = 0;                                                     \
            (len) = 0;                                                         \
        }                                                                      \
    } else {                                                                   \
        (lensize) = 1;                                                         \
        if ((encoding) == ZIP_INT_8B)  (len) = 1;                              \
        else if ((encoding) == ZIP_INT_16B) (len) = 2;                         \
        else if ((encoding) == ZIP_INT_24B) (len) = 3;                         \
        else if ((encoding) == ZIP_INT_32B) (len) = 4;                         \
        else if ((encoding) == ZIP_INT_64B) (len) = 8;                         \
        else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)   \
            (len) = 0;                                                         \
        else                                                                   \
            (lensize) = (len) = 0;                                             \
    }                                                                          \
} while(0)

基本操作

主要介紹壓縮列表的基本操作，包括創(chuàng )建壓縮列表，遍歷元素，插入元素，刪除元素，修改元素等。

創(chuàng )建壓縮列表

創(chuàng )建一個(gè)空的壓縮列表:只對 lbytes、zltail、zllen、zlend四個(gè)字段進(jìn)行初始化。初始化過(guò)程如下：

• 計算空ziplist的長(cháng)度并且申請內存，zlbytes和zltail的類(lèi)型是32位無(wú)符號整數，zllen是16位無(wú)符號整數，所以總長(cháng)度為：zlbytes(4) + zltail(4) + zllen(2) = 10 bytes
• 將總字節數寫(xiě)入內存。zl 既為 ziplist 的起始地址，其中值又負責記錄 ziplist 的總字節長(cháng)度，zlbytes 編碼存儲固定 4 字節，也就代表了一個(gè) ziplist 總字節最大為為 (2^32)-1 字節。
• 將到尾節點(diǎn)的偏移量寫(xiě)進(jìn)內存，因為是剛初始化的 ziplist，偏移量其實(shí)就是 HEADER_SIZE 值，此時(shí)它剛好指向 zlend，因此能夠以 O(1) 時(shí)間復雜度快速在尾部進(jìn)行 push 或 pop 操作。
• 寫(xiě)入節點(diǎn)數量：0
• 最后一個(gè)字節設置為 ZIP_END，標識 ziplist 結尾。

實(shí)現代碼如下：

unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    ZIPLIST_LENGTH(zl) = 0;
    zl[bytes-1] = ZIP_END;
    return zl;
}

插入元素

壓縮列表實(shí)現函數如下,其中：

• zl：壓縮列表。
• p: 元素插入位置
• s: 插入元素內容
• slen: 元素數據長(cháng)度。

unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen)

插入元素可以簡(jiǎn)要分為3個(gè)步驟：① 將元素內容編碼；② 重新分配空間；③ 復制數據。

編碼

編碼就是計算前節點(diǎn)的prelen字段，encoding字段和content字段的內容。計算prelen的前提條件就是明確元素的插入位置。
元素的插入位置主要包含兩種場(chǎng)景：

• 元素插入到中間位置。
• 元素插入到末尾。

場(chǎng)景一：元素插入到中間位置

當插入到ziplist的中間節點(diǎn)時(shí),解碼插入節點(diǎn)p的prevlen（函數ZIP_DECODE_PREVLEN）。

場(chǎng)景二：元素插入到末尾

當插入到ziplist的尾部時(shí)，通過(guò)zltail計算出ziplist的最后一個(gè)節點(diǎn)，再計算prevlen。首先我們應當獲取最后一個(gè)節點(diǎn)。
可以通過(guò)zltail獲取最后一個(gè)節點(diǎn)的內容。zl偏移zltail的偏移量就可以獲取最后一個(gè)節點(diǎn)的指針。

#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))

取出最后一個(gè)節點(diǎn)的長(cháng)度，作為新插入節點(diǎn)p的prevlen,最后一個(gè)節點(diǎn)的prevlen是節點(diǎn)headersize和將節點(diǎn)內容長(cháng)度之和。

static inline unsigned int zipRawEntryLengthSafe(unsigned char* zl, size_t zlbytes, unsigned char *p) {
    zlentry e;
    assert(zipEntrySafe(zl, zlbytes, p, &e, 0));
    return e.headersize + e.len;
}

元素編碼

編碼時(shí)嘗試將輸入字符串轉為整數：若可以轉為整數，則按照壓縮列表整數類(lèi)型編碼存儲，reqlen根據encoding確定保存節點(diǎn)值需要的字節數；
若不可以轉為整數，則按照字節數組方式存儲，reqlen為字符串的長(cháng)度。

reqlen字段為存儲當前元素需要的空間大小，所以由prevlen占用空間、當前節點(diǎn)的encoding和length、當前節點(diǎn)值占用的空間三部分之和構成。

計算公式：reqlen = prevlenSize + encodingSize + dataSize

if (zipTryEncoding(s,slen,&value,&encoding)) {
  reqlen = zipIntSize(encoding);
} else {
  reqlen = slen;
}
reqlen += zipStorePrevEntryLength(NULL,prevlen);
reqlen += zipStoreEntryEncoding(NULL,encoding,slen);

重新分配空間

當元素不是在尾部插入時(shí)，我們需要確保插入位置的后一個(gè)節點(diǎn)有足夠的空間來(lái)保存新插入節點(diǎn)的長(cháng)度，即保證后節點(diǎn)的prevlen足夠，例如，
AC插入后變成ABC，我們需要跟新C節點(diǎn)的prevlen信息。計算方法如下：

nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) :0；

nextdiff 的值代表的含義如下:

• 0 ：空間相等（剛好，不需要擴展）；
• 4 ：需要更多空間（需要擴展）。
• -4 空間富余（可以縮容）

函數zipPrevLenByteDiff實(shí)現如下：

int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
    unsigned int prevlensize;
    ZIP_DECODE_PREVLENSIZE(p, prevlensize);
    return zipStorePrevEntryLength(NULL, len) - prevlensize;
}

數據復制

內存空間分配使用memmove函數實(shí)現：

memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

當空間富裕且下一個(gè)節點(diǎn)的pevlen使用一個(gè)字節存儲長(cháng)度時(shí)，需要防止出現大量的連鎖跟新，后一個(gè)節點(diǎn)的prevlen不能直接縮成1，
還是需要使用4個(gè)字節保存。保存新插入節點(diǎn)的長(cháng)度到后一節點(diǎn)的代碼如下：

if (forcelarge)
  zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
  zipStorePrevEntryLength(p+reqlen,reqlen);

維護 zltail, 將新插入的節點(diǎn)長(cháng)度算到zltail里面，如果 nextdiff == 4 > 0，說(shuō)明后個(gè)節點(diǎn)的 prevSize 其實(shí)變大了的，
也需要把這部分增加落實(shí)到 zltail 算在偏移量里，這樣才能真的對齊表尾節點(diǎn)

ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
assert(zipEntrySafe(zl, newlen, p+reqlen, &tail, 1));
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
   ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}

刪除元素

壓縮列表的函數定定義如下，返回值為刪除元素之后壓縮列表的首地址，接口入參如下：

• zl: 壓縮列表的首地址。
• p: 待刪除的元素的首地址。

unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p)

函數ziplistDelete只是簡(jiǎn)單調用了__ziplistDelete函數實(shí)現，其中num表示需要刪除的元素數目，包含元素p。

unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
    size_t offset = *p-zl;
    zl = __ziplistDelete(zl,*p,1);
    *p = zl+offset;
    return zl;
}

刪除元素需要是三個(gè)步驟：

1. 計算待刪除元素的總長(cháng)度。
2. 數據復制。
3. 重新分配空間。

1. 計算待刪除元素的總長(cháng)度

計算長(cháng)度的函數zipRawEntryLengthSafe之前已經(jīng)講過(guò)。將需要刪除的元素解密之后，計算需要刪除的第num個(gè)元素的長(cháng)度。

zipEntry(p, &first); 
for (i = 0; p[0] != ZIP_END && i < num; i++) {
    p += zipRawEntryLengthSafe(zl, zlbytes, p);
    deleted++;
}
totlen = p-first.p;

2. 數據復制

在上一步之后，first和p之間的數據就是需要刪除的，其中first指向第一個(gè)需要刪除的節點(diǎn)，p指向最后一個(gè)需要保留
第一個(gè)節點(diǎn)或者列表尾。

刪除節點(diǎn)為中間節點(diǎn)

當刪除節點(diǎn)為中間節點(diǎn)時(shí)，在刪除當前節點(diǎn)之后，后面節點(diǎn)的prevlen存儲可能不夠。p指向的后面節點(diǎn)需要判斷是否有
足夠的prevlen是否夠。因為是刪除節點(diǎn)，包含刪除 first 節點(diǎn)，這里刪除的空間是肯定夠 p 節點(diǎn) prevlenSize 擴展的
將 p 向后移動(dòng) nextdiff 差值的長(cháng)度，減少需要刪除的內存，用來(lái)擴展第一個(gè)節點(diǎn)（都刪除后的）的 prevlen。

nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
p -= nextdiff;

將 first 的前一個(gè)節點(diǎn)的長(cháng)度編碼擴展到 p 當前的位置。

zipStorePrevEntryLength(p,first.prevrawlen);

更新列表末尾的偏移量，原本的 減去 所有被刪除的內存。

set_tail = intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen;

如果被刪除節點(diǎn)后有多于一個(gè)節點(diǎn)，那么需要將 nextdiff 也計算到表尾偏移量中。因為當前 p 指向的不是尾節點(diǎn)，
因此要加上 nextdiff 才能讓表尾偏移量正確。

assert(zipEntrySafe(zl, zlbytes, p, &tail, 1));
if (p[tail.headersize+tail.len] != ZIP_END) {
   set_tail = set_tail + nextdiff;
}

數據復制： 末尾向前面移動(dòng)數據，覆蓋被刪除節點(diǎn)。

size_t bytes_to_move = zlbytes-(p-zl)-1;
memmove(first.p,p,bytes_to_move);

刪除節點(diǎn)為末尾節點(diǎn)

p[0] == ZIP_END 到達末尾，說(shuō)明后面其實(shí)沒(méi)有節點(diǎn)，無(wú)需移動(dòng)內存,更新尾節點(diǎn)偏移量到前一個(gè)節點(diǎn)的地址，因為此時(shí)
first 前一個(gè)節點(diǎn)是尾節點(diǎn)。

set_tail = (first.p-zl)-first.prevrawlen;

3. 重新分配空間

重新分配空間與插入元素邏輯相似，代碼如下：

offset = first.p-zl;
zlbytes -= totlen - nextdiff;
zl = ziplistResize(zl, zlbytes);
p = zl+offset;

遍歷元素

壓縮列表遍歷分為前向(從頭到尾)和后向遍歷(從尾到頭)。前向遍歷的API定義如下：

• zl: 壓縮列表的首地址。
• p: 為需要查找的字符串的首地址。
• 返回p的前一個(gè)節點(diǎn)。

unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p)

后向遍歷的API定義如下：

unsigned char *ziplistNext(unsigned char *zl, unsigned char *p)

前向遍歷

• 如果p[0]==ZIP_END，則說(shuō)明前一個(gè)節點(diǎn)是壓縮列表的尾節點(diǎn)。
• 如果p == ZIPLIST_ENTRY_HEAD(zl) 說(shuō)明p是壓縮列表的第一個(gè)節點(diǎn)，前一個(gè)節點(diǎn)為NULL。
• 如果是查找的是中間節點(diǎn)，需要解析出 prevlen 往前進(jìn)行偏移，然后解析出對應節點(diǎn)。

unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
    unsigned int prevlensize, prevlen = 0;
    if (p[0] == ZIP_END) {
        p = ZIPLIST_ENTRY_TAIL(zl);
        return (p[0] == ZIP_END) ? NULL : p;
    } else if (p == ZIPLIST_ENTRY_HEAD(zl)) {
        return NULL;
    } else {
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
        assert(prevlen > 0);
        p-=prevlen;
        size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl));
        zipAssertValidEntry(zl, zlbytes, p);
        return p;
    }
}

后向遍歷

• 如果p[0] == ZIP_END，則表示當前ziplist為空，范圍NULL。
• 在 p 當前節點(diǎn)的基礎上，往后偏移 p 節點(diǎn)的字節長(cháng)度，即指向下一個(gè)節點(diǎn)。如果之后的 p 指向 ZIP_END 說(shuō)明已經(jīng)達到 ziplist 尾部，沒(méi)有下一個(gè)節點(diǎn)

unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
    ((void) zl);
    size_t zlbytes = intrev32ifbe(ZIPLIST_BYTES(zl));

    if (p[0] == ZIP_END) {
        return NULL;
    }

    p += zipRawEntryLength(p);
    if (p[0] == ZIP_END) {
        return NULL;
    }

    zipAssertValidEntry(zl, zlbytes, p);
    return p;
}