簡(jiǎn)介

The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values,where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1) time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist.

數(shù)據(jù)結(jié)構(gòu)

總體上ziplist由三部分組成ZIPLIST_HEADER 大小為(sizeof(uint32_t)*2+sizeof(uint16_t))仇矾。中間存儲(chǔ)entry贾陷，最后面存儲(chǔ)zip_end結(jié)束標(biāo)記

• ZIPLIST OVERALL LAYOUT:
• The general layout of the ziplist is as follows:
• <zlbytes><zltail><zllen><entry><entry><zlend>

1. zlbytes 一個(gè)uint32_t的數(shù)據(jù)婿屹，用來保存總大小
2. zltail 用來保存最后一個(gè)entry的偏移
   3.zllen 一個(gè)uint16_t用來保存entry的數(shù)量勾怒。所以我們ziplist頭的大小是兩個(gè)uint32_t和一個(gè)uint16_t
   4.entry編碼的存儲(chǔ)數(shù)據(jù)
   5.zlend uint8_t保存結(jié)束標(biāo)記 ZIP_END
   因?yàn)楹蛕ipmap一樣都是線性保存蒋纬。所以沒有抽象出具體的數(shù)據(jù)結(jié)構(gòu)

對(duì)于ziplist的初始化

#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl))) /*第一個(gè)uint32_t是保存的zlbytes*/
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t)))) /*第二個(gè)uint32_t保存的zltail*/
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))/*兩個(gè)uint32_t后面的uint_16_t保存的zllen*/
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))

/* Create a new empty ziplist. */
unsigned char *ziplistNew(void) {
    unsigned int bytes = ZIPLIST_HEADER_SIZE+1; //heaer + end
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes); //設(shè)置
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE); //當(dāng)前沒有數(shù)據(jù)偏移就是header_size 指向end代表空
    ZIPLIST_LENGTH(zl) = 0;//長(zhǎng)度為0
    zl[bytes-1] = ZIP_END;//末尾設(shè)置
    return zl;
}

了解了ziplist的線性結(jié)構(gòu)，對(duì)于初始化來說很好理解

數(shù)據(jù)編碼

typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;//上一個(gè)元素的數(shù)據(jù)的大小，保存上一個(gè)元素長(zhǎng)度的長(zhǎng)度
    unsigned int lensize, len;//保存當(dāng)前數(shù)據(jù)塊長(zhǎng)度的長(zhǎng)度，當(dāng)前數(shù)據(jù)塊的長(zhǎng)度
    unsigned int headersize;//prevrawlensize + lensize 就是保存前面數(shù)據(jù)信息和當(dāng)前數(shù)據(jù)信息的長(zhǎng)度
    unsigned char encoding;//編碼方式
    unsigned char *p;//開始位置
} zlentry;

ziplist有一個(gè)數(shù)據(jù)結(jié)構(gòu)zlentry 這個(gè)數(shù)據(jù)結(jié)構(gòu)并不是ziplist保存entry的數(shù)據(jù)結(jié)構(gòu)焰雕。這個(gè)數(shù)據(jù)結(jié)構(gòu)是通過對(duì)一個(gè)線性的entry進(jìn)行解碼出來的。他可以體現(xiàn)一個(gè)entry里面保存的數(shù)據(jù)芳杏。
prevrawlen：保存它上一個(gè)元素的數(shù)據(jù)大小矩屁。我們可以通過p-prevrawlen得到上一個(gè)entry的位置
len：保存當(dāng)前entry的總大小【粽裕可以確定自己的邊界
headersize：通過prevrawlensize+lensize來得到表示當(dāng)前header大小
encoding：數(shù)據(jù)的編碼方式吝秕，確定后面保存的數(shù)據(jù)該怎么獲取
p：保存自己的開始位置，根據(jù)p+headersize和得到我們數(shù)據(jù)開始的位置
通過這個(gè)數(shù)據(jù)結(jié)構(gòu)再加上我們前面zipmap的經(jīng)驗(yàn)空幻。我們基本可以猜測(cè)一下我們entry的線性結(jié)構(gòu)就是prevrawlensize+prevrawlen+lensize+len+encode烁峭，但是我們注意到我們的heaersize里面有沒有encoding的空間。所以我們encode的保存方式會(huì)放入len里面去秕铛，或者是根據(jù)encode來確定咱們len的長(zhǎng)度

編碼類型

既然我們上面注意到encode并沒有被單獨(dú)列出來约郁，所以我們來看下我們具體的encode類型

#define ZIP_STR_MASK 0xc0 /*1100 0000*/
#define ZIP_INT_MASK 0x30 /*0011 000*/
#define ZIP_STR_06B (0 << 6) /*0000 0000*/
#define ZIP_STR_14B (1 << 6) /*0100 0000*/
#define ZIP_STR_32B (2 << 6) /*1000 0000*/
#define ZIP_INT_16B (0xc0 | 0<<4)/*1100 0000*/
#define ZIP_INT_32B (0xc0 | 1<<4)/*1101 0000*/
#define ZIP_INT_64B (0xc0 | 2<<4)/*1110 0000*/
#define ZIP_INT_24B (0xc0 | 3<<4)/*1111 0000*/
#define ZIP_INT_8B 0xfe /*1111 1110*/
/* 4 bit integer immediate encoding */
#define ZIP_INT_IMM_MASK 0x0f /*0000 1111*/
#define ZIP_INT_IMM_MIN 0xf1    /* 1111 0001 */
#define ZIP_INT_IMM_MAX 0xfd    /* 1111 1101 */
#define ZIP_INT_IMM_VAL(v) (v & ZIP_INT_IMM_MASK)

我們可以很直觀的發(fā)現(xiàn)我們的encode后面有個(gè)xxB耘柱，就是我們位的大小。其實(shí)我們就可以發(fā)現(xiàn)我們的encode包含了咱們的lensize的長(zhǎng)度棍现。所以更新下線性結(jié)構(gòu)為prevrawlensize+prevrawlen+encode+xxbit

我們會(huì)發(fā)現(xiàn)我們看到了6B 14B這些怪異的定義，一般來說我們的一個(gè)字節(jié)是8位镜遣，但是這里少了兩位己肮，那我們就來看下具體的實(shí)現(xiàn)。
其實(shí)我們細(xì)心就可以發(fā)現(xiàn)我們ZIP_STR_MASK 位1100 0000,其實(shí)意思就是我們的高兩位作為了我們的encode類型的存儲(chǔ)悲关。
ZIP_STR_06B 位0000 0000 ,他的encode的類型位置就是高兩位的00谎僻，這個(gè)時(shí)候我們還剩了6個(gè)字節(jié)沒有用，所以6B的來源就是這里寓辱，我們的低六位作為了存儲(chǔ)長(zhǎng)度艘绍。
同理ZIP_STR_14B 0100 0000 我們的類型標(biāo)致位為01 后面剩余了6個(gè)字節(jié)，然后在加上一個(gè)額外分配的uint8_t空間組成了14B
ZIP_STR_32B 1000 0000 32B 代表四個(gè)uint8_t來組成秫筏。沒有再使用剩余的6字節(jié)诱鞠，這個(gè)時(shí)候范圍已經(jīng)足夠表示了。
我們?cè)诳磥韎nt的
ZIP_INT_MASK 0011 0000 它使用第三位和第四位來保存類型
ZIP_INT_16B 1100 0000 既00 代表著后面的數(shù)據(jù)2字節(jié)
ZIP_INT_32B 1101 0000 即01 代表后面數(shù)據(jù)4字節(jié)
ZIP_INT_64B 1110 0000 即10 代表后面數(shù)據(jù)8字節(jié)
ZIP_INT_24B 1111 0000 即11 代表后面數(shù)據(jù)3字節(jié)
ZIP_INT_8B 1111 1110 看不出代表為代表后面數(shù)據(jù)為1字節(jié)
這個(gè)8B看起來很突兀这敬，不符合前面的標(biāo)準(zhǔn)航夺，而且不符合中間兩位的原則。所以我們需要來看一下
我們發(fā)現(xiàn)下面的定義/* 4 bit integer immediate encoding */ 其實(shí)我們str+int的encode定義中排除zip_int_8B我們會(huì)發(fā)現(xiàn)崔涂，其實(shí)只用了前四位阳掐，如果不把后四位一起用起來，是不是有點(diǎn)不符合咱們Redis各種節(jié)約內(nèi)存的做法喃冷蚂。嘿嘿缭保，事實(shí)上，它還是真的用起來了蝙茶。
低四位可以保存的數(shù)據(jù)為0-15艺骂，所以有開發(fā)的空間，這時(shí)候我們的int還需要一個(gè)定義所以會(huì)占用1個(gè)表示的空間隆夯，我們的高四位的字節(jié)已經(jīng)用完彻亲，所以低四位不能全為0這樣會(huì)造成沖突，所以至少低位有一位需要不一樣吮廉，Redis給出的是最低位+1苞尝，所以占用了一個(gè)表示空間，全為1111即15的表示會(huì)造成和高四位構(gòu)成一個(gè)結(jié)束標(biāo)記宦芦，所以再排除宙址，所以我們還剩下0-12的空間給我們用，所以就有了：
ZIP_INT_IMM_MASK 0000 1111
ZIP_INT_IMM_MIN 0000 0001
ZIP_INT_IMM_MAX 0000 1101
ZIP_INT_8B 000 1110
給一個(gè)源碼的解釋：

• The other header field of the entry itself depends on the contents of the
• entry. When the entry is a string, the first 2 bits of this header will hold
• the type of encoding used to store the length of the string, followed by the
• actual length of the string. When the entry is an integer the first 2 bits
• are both set to 1. The following 2 bits are used to specify what kind of
• integer will be stored after this header. An overview of the different
• types and encodings is as follows:
• |00pppppp| - 1 byte

•  String value with length less than or equal to 63 bytes (6 bits).
  

• |01pppppp|qqqqqqqq| - 2 bytes

•  String value with length less than or equal to 16383 bytes (14 bits).
  

• |10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes

•  String value with length greater than or equal to 16384 bytes.
  

• |11000000| - 1 byte

•  Integer encoded as int16_t (2 bytes).
  

• |11010000| - 1 byte

•  Integer encoded as int32_t (4 bytes).
  

• |11100000| - 1 byte

•  Integer encoded as int64_t (8 bytes).
  

• |11110000| - 1 byte

•  Integer encoded as 24 bit signed (3 bytes).
  

• |11111110| - 1 byte

•  Integer encoded as 8 bit signed (1 byte).
  

• |1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer.

•  Unsigned integer from 0 to 12. The encoded value is actually from
  

•  1 to 13 because 0000 and 1111 can not be used, so 1 should be
  

•  subtracted from the encoded 4 bit value to obtain the right value.
  

• |11111111| - End of ziplist.

現(xiàn)在我們對(duì)entry的表示結(jié)構(gòu)和編碼方式以及了解了调卑，后面的操作就是水到渠成了抡砂。直接來看Redis對(duì)于encode 和 len的操作

/* Extract the encoding from the byte pointed by 'ptr' and set it into
 * 'encoding'. */
/*獲取encode信息*/
#define ZIP_ENTRY_ENCODING(ptr, encoding) do {  \
    (encoding) = (ptr[0]);   /*第一個(gè)字節(jié)保存的是encode信息*/\
    if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK;/*str encode 使用的是高兩位 只要高兩位有0 肯定小于 ZIP_STR_MASK*/\
} while(0)

/* Return bytes needed to store integer encoded by 'encoding' */
/*獲取對(duì)encode是int的長(zhǎng)度*/
unsigned int zipIntSize(unsigned char encoding) {
    switch(encoding) {
    case ZIP_INT_8B:  return 1;
    case ZIP_INT_16B: return 2;
    case ZIP_INT_24B: return 3;
    case ZIP_INT_32B: return 4;
    case ZIP_INT_64B: return 8;
    default: return 0; /* 4 bit immediate */
    }
    assert(NULL);
    return 0;
}
#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {                    \
    ZIP_ENTRY_ENCODING((ptr), (encoding));/*獲取encode的類型*/                   \
    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) = ((ptr)[1] << 24) |                                         \
                    ((ptr)[2] << 16) |                                         \
                    ((ptr)[3] <<  8) |                                         \
                    ((ptr)[4]);                                                \
        } else {                                                               \
            assert(NULL);                                                      \
        }                                                                      \
    } else {                                                                   \
        (lensize) = 1;                                                         \
        (len) = zipIntSize(encoding);                                          \
    }                                                                          \
} while(0);

插入

現(xiàn)在我們把編碼方面理清楚了之后大咱，直接來看插入操作。
首先我們的ziplist本質(zhì)上是一個(gè)雙向鏈表注益，保存了next信息和prev信息碴巾，其實(shí)next信息是利用內(nèi)存的連續(xù)性來保存的，不需要我們進(jìn)行額外的操作丑搔。prev信息是通過我們前面說的prevrawlen來存儲(chǔ)的這個(gè)字段的編碼方式和zipmap的存儲(chǔ)長(zhǎng)度方式一致就在這里不重復(fù)說了厦瓢。
插入本身除了把自己進(jìn)行編碼放入內(nèi)存之后，還有一個(gè)重要的操作就是維護(hù)上下文的鏈表關(guān)系啤月，由于內(nèi)存的連續(xù)煮仇，所以我們不需要維護(hù)next，但是我們需要維護(hù)prev.
我們的插入操作是在某個(gè)節(jié)點(diǎn)后插入谎仲，這時(shí)候我們是先要拿到一個(gè)節(jié)點(diǎn)這時(shí)候其實(shí)我們就有節(jié)點(diǎn)的信息（沒有的時(shí)候?qū)儆诳臻g的浙垫，也算是有節(jié)點(diǎn)信息吧），我們?cè)诓迦氲臅r(shí)候保存這個(gè)信息就足夠了郑诺。直接來看插入代碼

* Insert item at "p". */
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen; //list的大小
    unsigned int prevlensize, prevlen = 0;
    size_t offset;
    int nextdiff = 0;
    unsigned char encoding = 0;
    long long value = 123456789; /* initialized to avoid warning. Using a value
                                    that is easy to see if for some reason
                                    we use it uninitialized. */
    zlentry tail;

    /* Find out prevlen for the entry that is inserted. */
    if (p[0] != ZIP_END) {//首先看這個(gè)插入的節(jié)點(diǎn)是不是空節(jié)點(diǎn)
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);//返回插入節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的信息
    } else {
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);//找到尾節(jié)點(diǎn) （當(dāng)我們插入尾部的時(shí)候）
        if (ptail[0] != ZIP_END) {
            prevlen = zipRawEntryLength(ptail);//找到尾節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)的大小
        }
    }

    /* See if the entry can be encoded */
    if (zipTryEncoding(s,slen,&value,&encoding)) {//是否能夠轉(zhuǎn)換成int存儲(chǔ)
        /* 'encoding' is set to the appropriate integer encoding */
        reqlen = zipIntSize(encoding);
    } else {
        /* 'encoding' is untouched, however zipEncodeLength will use the
         * string length to figure out how to encode it. */
        reqlen = slen;
    }
    /* We need space for both the length of the previous entry and
     * the length of the payload. */
    reqlen += zipPrevEncodeLength(NULL,prevlen);//加上保存prevlen所需要的空間
    reqlen += zipEncodeLength(NULL,encoding,slen);//加上保存encode需要的空間

    /* When the insert position is not equal to the tail, we need to
     * make sure that the next entry can hold this entry's length in
     * its prevlen field. */
    int forcelarge = 0;
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;//如果不為空夹姥，我需要知道兩個(gè)length之間的差距(因?yàn)槲覀儾迦朐谇懊嫠栽瓉淼男枰膒revlen)
   //nextdiff只0 4 -4  //0代表兩個(gè)需要大小一樣 4 代表新的保存空間需要更大 -4 代表原來保存的位置太大了
    //reqlen
    if (nextdiff == -4 && reqlen < 4) {
        /*
         在一般的情況下不會(huì)觸發(fā)  nextdiff == -4  reqlen < 4 的情況 因?yàn)槿绻覀兊膔eqlen中prvelen 來源于p所以 prvlen=5 relen至少也是5
         但是喃 在updatecase里面當(dāng)節(jié)點(diǎn)變化的時(shí)候 當(dāng)前節(jié)點(diǎn)保存上一個(gè)節(jié)點(diǎn)的長(zhǎng)度的空間過大的時(shí)候 我們不會(huì)選擇縮小我們保存prvlen的空間 所以照成了這個(gè)情況
         繼續(xù)不縮小空間 還是用大的寫
         */
        
        nextdiff = 0;
        forcelarge = 1;
    }

    /* Store offset because a realloc may change the address of zl. */
    offset = p-zl;//保存原來的偏移
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);//總是增大
    p = zl+offset;//轉(zhuǎn)回到原來的偏移

    /* Apply memory move when necessary and update tail offset. */
    if (p[0] != ZIP_END) {
        /* Subtract one because of the ZIP_END bytes */
        //p+reqlen 如果新數(shù)據(jù)放入后的尾部
        //p+diff diff=0時(shí)很明顯
        //diff = -4  說明我們?cè)瓉肀４娴膌en太大了 我們的實(shí)際存儲(chǔ)肯定是第六位開始的（前面五個(gè)字節(jié)為len）原來前四個(gè)保存長(zhǎng)度的沒拷貝
        //diff = 4 說明我們?cè)瓉肀４娴膌en太小了 我們多拷貝了四個(gè)字節(jié)走 我們的實(shí)際數(shù)據(jù)拷貝么有問題
        //實(shí)際上就是留出后面保存prevlen的長(zhǎng)度
        memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

        /* Encode this entry's raw length in the next entry. */
        if (forcelarge)
            zipPrevEncodeLengthForceLarge(p+reqlen,reqlen);
        else
            zipPrevEncodeLength(p+reqlen,reqlen);//我們的move的時(shí)候把存放len的位置留出來了

        /* Update offset for tail */
        ZIPLIST_TAIL_OFFSET(zl) =
            intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);//更新新尾節(jié)點(diǎn)的位置 沒加diff的原因在下面

        /* When the tail contains more than one entry, we need to take
         * "nextdiff" in account as well. Otherwise, a change in the
         * size of prevlen doesn't have an effect on the *tail* offset. */
        zipEntry(p+reqlen, &tail);//
        if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {//找到下一個(gè)節(jié)點(diǎn) 我們這個(gè)節(jié)點(diǎn)后面沒有了的話 那就是代表被插入的節(jié)點(diǎn)就是尾節(jié)點(diǎn)了，diff的變化對(duì)他沒影響辙诞，否則的話就需要更新  可以加上 if(nextdiff !=0 )再來做操作
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
        }
    } else {
        /* This element will be the new tail. */
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);//設(shè)置 tail的偏移
    }

    /* When nextdiff != 0, the raw length of the next entry has changed, so
     * we need to cascade the update throughout the ziplist */
    if (nextdiff != 0) {//如果 不等于0 我們的節(jié)點(diǎn)會(huì)被改變 主要是存儲(chǔ)prvelen改變了 我們需要對(duì)后面的進(jìn)行循環(huán)改變 這部分代碼可以放入到 p[0] !ZIP_END里面去 最后再來匯總 因?yàn)?nextdiff產(chǎn)生的條件是p[0] !=ZIP_END
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);//更新
        p = zl+offset;
    }

    /* Write the entry */
    p += zipPrevEncodeLength(p,prevlen);//保存prevlen的大小
    p += zipEncodeLength(p,encoding,slen);//保存自己的大小
    if (ZIP_IS_STR(encoding)) {//保存數(shù)據(jù)
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }
    ZIPLIST_INCR_LENGTH(zl,1);
    return zl;
}

unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
    size_t offset, noffset, extra;
    unsigned char *np;
    zlentry cur, next;

    while (p[0] != ZIP_END) {//循環(huán)結(jié)束條件到達(dá)終點(diǎn)
        zipEntry(p, &cur);//獲取字節(jié)的情況
        rawlen = cur.headersize + cur.len;
        rawlensize = zipPrevEncodeLength(NULL,rawlen);//獲取自己需要的大小

        /* Abort if there is no next entry. */
        if (p[rawlen] == ZIP_END) break;//自己后面沒人了 不用改變了
        zipEntry(p+rawlen, &next);//獲取字節(jié)后面大小的信息

        /* Abort when "prevlen" has not changed. */
        if (next.prevrawlen == rawlen) break;//大小沒變

        if (next.prevrawlensize < rawlensize) {//存儲(chǔ)空間不夠了
            /* The "prevlen" field of "next" needs more bytes to hold
             * the raw length of "cur". */
            offset = p-zl;//保存偏移
            extra = rawlensize-next.prevrawlensize;//diff
            zl = ziplistResize(zl,curlen+extra);//resize
            p = zl+offset;//還原p

            /* Current pointer and offset for next element. */
            np = p+rawlen;//下一個(gè)節(jié)點(diǎn)的位置
            noffset = np-zl;//下一個(gè)節(jié)點(diǎn)對(duì)于的偏移

            /* Update tail offset when next element is not the tail element. */
            if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {//如果后面還有節(jié)點(diǎn) 就必須要更新tail的位置信息
                ZIPLIST_TAIL_OFFSET(zl) =
                    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
            }

            /* Move the tail to the back. */
            memmove(np+rawlensize,
                np+next.prevrawlensize,
                curlen-noffset-next.prevrawlensize-1);//數(shù)據(jù)移動(dòng)
            zipPrevEncodeLength(np,rawlen);//編碼len

            /* Advance the cursor */
            p += rawlen;//到下一個(gè)位置
            curlen += extra;//len變成了
        } else {
            if (next.prevrawlensize > rawlensize) {//多了
                /* This would result in shrinking, which we want to avoid.
                 * So, set "rawlen" in the available bytes. */
                zipPrevEncodeLengthForceLarge(p+rawlen,rawlen);//懶些 用大的保存小的減少操作
            } else {
                zipPrevEncodeLength(p+rawlen,rawlen);//大小合適 保存下收工
            }

            /* Stop here, as the raw length of "next" has not changed. */
            break;
        }
    }
    return zl;
}

/* Delete "num" entries, starting at "p". Returns pointer to the ziplist. */
unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
    unsigned int i, totlen, deleted = 0;
    size_t offset;
    int nextdiff = 0;
    zlentry first, tail;

    zipEntry(p, &first);
    for (i = 0; p[0] != ZIP_END && i < num; i++) {
        p += zipRawEntryLength(p);
        deleted++;
    }

    totlen = p-first.p;
    if (totlen > 0) {
        if (p[0] != ZIP_END) {
            /* Storing `prevrawlen` in this entry may increase or decrease the
             * number of bytes required compare to the current `prevrawlen`.
             * There always is room to store this, because it was previously
             * stored by an entry that is now being deleted. */
            nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
            p -= nextdiff;
            zipPrevEncodeLength(p,first.prevrawlen);

            /* Update offset for tail */
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);

            /* When the tail contains more than one entry, we need to take
             * "nextdiff" in account as well. Otherwise, a change in the
             * size of prevlen doesn't have an effect on the *tail* offset. */
            zipEntry(p, &tail);
            if (p[tail.headersize+tail.len] != ZIP_END) {
                ZIPLIST_TAIL_OFFSET(zl) =
                   intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
            }

            /* Move tail to the front of the ziplist */
            memmove(first.p,p,
                intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
        } else {
            /* The entire tail was deleted. No need to move memory. */
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe((first.p-zl)-first.prevrawlen);
        }

        /* Resize and update length */
        offset = first.p-zl;
        zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
        ZIPLIST_INCR_LENGTH(zl,-deleted);
        p = zl+offset;

        /* When nextdiff != 0, the raw length of the next entry has changed, so
         * we need to cascade the update throughout the ziplist */
        if (nextdiff != 0)
            zl = __ziplistCascadeUpdate(zl,p);
    }
    return zl;
}
unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), rawlen, rawlensize;
    size_t offset, noffset, extra;
    unsigned char *np;
    zlentry cur, next;

    while (p[0] != ZIP_END) {//循環(huán)結(jié)束條件到達(dá)終點(diǎn)
        zipEntry(p, &cur);//獲取字節(jié)的情況
        rawlen = cur.headersize + cur.len;
        rawlensize = zipPrevEncodeLength(NULL,rawlen);//獲取自己需要的大小

        /* Abort if there is no next entry. */
        if (p[rawlen] == ZIP_END) break;//自己后面沒人了 不用改變了
        zipEntry(p+rawlen, &next);//獲取字節(jié)后面大小的信息

        /* Abort when "prevlen" has not changed. */
        if (next.prevrawlen == rawlen) break;//大小沒變

        if (next.prevrawlensize < rawlensize) {//存儲(chǔ)空間不夠了
            /* The "prevlen" field of "next" needs more bytes to hold
             * the raw length of "cur". */
            offset = p-zl;//保存偏移
            extra = rawlensize-next.prevrawlensize;//diff
            zl = ziplistResize(zl,curlen+extra);//resize
            p = zl+offset;//還原p

            /* Current pointer and offset for next element. */
            np = p+rawlen;//下一個(gè)節(jié)點(diǎn)的位置
            noffset = np-zl;//下一個(gè)節(jié)點(diǎn)對(duì)于的偏移

            /* Update tail offset when next element is not the tail element. */
            if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {//如果后面還有節(jié)點(diǎn) 就必須要更新tail的位置信息
                ZIPLIST_TAIL_OFFSET(zl) =
                    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
            }

            /* Move the tail to the back. */
            memmove(np+rawlensize,
                np+next.prevrawlensize,
                curlen-noffset-next.prevrawlensize-1);//數(shù)據(jù)移動(dòng)
            zipPrevEncodeLength(np,rawlen);//編碼len

            /* Advance the cursor */
            p += rawlen;//到下一個(gè)位置
            curlen += extra;//len變成了
        } else {
            if (next.prevrawlensize > rawlensize) {//多了
                /* This would result in shrinking, which we want to avoid.
                 * So, set "rawlen" in the available bytes. */
                zipPrevEncodeLengthForceLarge(p+rawlen,rawlen);//懶些 用大的保存小的減少操作
            } else {
                zipPrevEncodeLength(p+rawlen,rawlen);//大小合適 保存下收工
            }

            /* Stop here, as the raw length of "next" has not changed. */
            break;
        }
    }
    return zl;
}

刪除

ziplist的刪除操作特別簡(jiǎn)潔佃声，因?yàn)樗鞘褂眠吔鐏肀４鎛ext,所以直接把自身內(nèi)容刪除就好了.

unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
    unsigned int i, totlen, deleted = 0;
    size_t offset;
    int nextdiff = 0;
    zlentry first, tail;

    zipEntry(p, &first);
    for (i = 0; p[0] != ZIP_END && i < num; i++) {//萬一你的num寫多了喃
        p += zipRawEntryLength(p); //偏移到下一個(gè)節(jié)點(diǎn)
        deleted++;
    }

    totlen = p-first.p;
    if (totlen > 0) { //看下到底偏移沒
        if (p[0] != ZIP_END) {//后面還有節(jié)點(diǎn)
            /* Storing `prevrawlen` in this entry may increase or decrease the
             * number of bytes required compare to the current `prevrawlen`.
             * There always is room to store this, because it was previously
             * stored by an entry that is now being deleted. */
            nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);//后面的節(jié)點(diǎn)需要去保存刪除的第一個(gè)節(jié)點(diǎn)的prvlen
            p -= nextdiff; //多了的話就刪了 少了的話就哪要?jiǎng)h除的補(bǔ)上
            zipPrevEncodeLength(p,first.prevrawlen);//設(shè)置len

            /* Update offset for tail */
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);//更新tail的位置

            /* When the tail contains more than one entry, we need to take
             * "nextdiff" in account as well. Otherwise, a change in the
             * size of prevlen doesn't have an effect on the *tail* offset. */
            zipEntry(p, &tail);
            if (p[tail.headersize+tail.len] != ZIP_END) {//如果后面還有節(jié)點(diǎn)需要再加上nextdiff m
                ZIPLIST_TAIL_OFFSET(zl) =
                   intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
            }

            /* Move tail to the front of the ziplist */
            memmove(first.p,p,
                intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);//把后面的數(shù)據(jù)移上來
        } else {
            /* The entire tail was deleted. No need to move memory. */
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe((first.p-zl)-first.prevrawlen);//沒有節(jié)點(diǎn)就直接移動(dòng)數(shù)據(jù)
        }

        /* Resize and update length */
        offset = first.p-zl;//保存偏移
        zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);//回收空間
        ZIPLIST_INCR_LENGTH(zl,-deleted);//改變len
        p = zl+offset;//找到p

        /* When nextdiff != 0, the raw length of the next entry has changed, so
         * we need to cascade the update throughout the ziplist */
        if (nextdiff != 0)//和inset一樣 如果有大小變化后面需要更新
            zl = __ziplistCascadeUpdate(zl,p);
    }
    return zl;
}

總結(jié)

ziplist 作為一個(gè)復(fù)雜的雙向list，他本身所需要的自我開銷特別的少倘要，就只有prevlen encode 其他保存的都是我們的數(shù)據(jù)信息圾亏。所以再節(jié)約內(nèi)存上會(huì)特別好。但是由于看不出具體的數(shù)據(jù)結(jié)構(gòu)封拧，會(huì)導(dǎo)致在操作上變得特別的復(fù)雜