redis源码分析——4、压缩列表ziplist实现

源码分析——4、压缩列表ziplist实现"/>

redis源码分析——4、压缩列表ziplist实现

ziplist原理简单，但实现起来较麻烦，尤其是连锁更新的时候，本文一起看看ziplist的具体实现

一、存储结构

1. ziplist：

   1. 内存布局
      ​

   2. 各字段含义

      • zlbytes：压缩列表的字节长度，占4个字节，因此压缩列表最长(2^32)-1字节；
      • zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，占4个字节；
      • zllen：压缩列表的元素数目，占两个字节；那么当压缩列表的元素数目超过(2^16)-1怎么处理呢？此时通过zllen字段无法获得压缩列表的元素数目，必须遍历整个压缩列表才能获取到元素数目；
      • entryX：压缩列表存储的若干个元素，可以为字节数组或者整数；entry的编码结构后面详述；
      • zlend：压缩列表的结尾，占一个字节，恒为0xFF。

   3. entry定义
      

      • **previous_entry_length：**1字节或5字节， 记录了压缩列表中前一个节点的长度，如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性的长度为 1 字节，如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性的长度为 5 字节： 其中属性的第一字节会被设置为 0xFE，后4字节表示前节点的真正长度。
      • **encoding：**属性记录了节点的 content 属性所保存数据的类型以及长度：
        

2. zipmap：

   1. 内存布局
   2. 各字段含义
      • zmlen: 1字节，表示当前map的大小，如果map的size>=254，则该值无效，需要遍历整体map来计算size；
      • len: 1字节或者5字节，用于表示key或者value的长度，当小于等于253时，用1字节表示，否则用后4字节表示；
      • key1: map的key；
      • len: value的长度，1字节或者5字节；
      • free: 1字节，用于表示value后面还有多少的空闲可以直接使用，以减少内存的分配；

二、结构体

1. ziplist:

   typedef struct zlentry {unsigned int prevrawlensize; /* Bytes used to encode the previous entry len*/unsigned int prevrawlen;     /* Previous entry len. */unsigned int lensize;        /* Bytes used to encode this entry type/len.For example strings have a 1, 2 or 5 bytesheader. Integers always use a single byte.*/unsigned int len;            /* Bytes used to represent the actual entry.For strings this is just the string lengthwhile for integers it is 1, 2, 3, 4, 8 or0 (for 4 bit immediate) depending on thenumber range. */unsigned int headersize;     /* prevrawlensize + lensize. */unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending onthe entry encoding. However for 4 bitsimmediate integers this can assume a rangeof values and must be range-checked. */unsigned char *p;            /* Pointer to the very start of the entry, thatis, this points to prev-entry-len field. */
   } zlentry;
   

2. zipmap:

   zipmap没有相关的结构体定义

三、 宏定义

1. zIplist：

   /*tail和end的区别*/
   /*entry end指的是最后的0XFF字节*/
   /*entry tail指的是尾元素，也就是不包含最后0XFF的元素*//* Return total bytes a ziplist is composed of. */
   /*获取ziplist的总字节数*/
   #define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))/* Return the offset of the last item inside the ziplist. */
   /*获取最后一个元素的偏移量*/
   #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))/* Return the length of a ziplist, or UINT16_MAX if the length cannot be* determined without scanning the whole ziplist. */
   /*获取ziplist的元素个数，如果返回的是UINT16_MAX，则需要完整遍历获取元素个数*/
   #define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))/* The size of a ziplist header: two 32 bit integers for the total* bytes count and last item offset. One 16 bit integer for the number* of items field. */
   /*ziplist的头，是固定值，包含zlbytes、zltail和zllen3个字段，共10字节*/
   #define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))/* Size of the "end of ziplist" entry. Just one byte. */
   /*ziplist的尾结点大小，占一字节，且为0小FF*/
   #define ZIPLIST_END_SIZE        (sizeof(uint8_t))/* Return the pointer to the first entry of a ziplist. */
   /*偏移到ziplist的第一个元素，其实就是跳过10字节的头部*/
   #define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)/* Return the pointer to the last entry of a ziplist, using the* last entry offset inside the ziplist header. */
   /*偏移到ziplist的最后一个节点，其实就是zl+lztail*/
   #define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))/* Return the pointer to the last byte of a ziplist, which is, the* end of ziplist FF entry. */
   /*偏移到ziplist的结尾0xFF，整个字节数组的最后一个字节*/
   #define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)/* Increment the number of items field in the ziplist header. Note that this* macro should never overflow the unsigned 16 bit integer, since entries are* always pushed one at a time. When UINT16_MAX is reached we want the count* to stay there to signal that a full scan is needed to get the number of* items inside the ziplist. */
   #define ZIPLIST_INCR_LENGTH(zl,incr) { \if (ZIPLIST_LENGTH(zl) < UINT16_MAX) \ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \
   }
   

2. zipmap：

四、基本操作

1. ziplist:

   • 创建

     unsigned char *ziplistNew(void) {/* 空list只有header和end*/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;
     }
     

   • 插入

     unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {unsigned char *p;p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);return __ziplistInsert(zl,p,s,slen);
     }// 在p出插入长度为slen的s元素
     unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen;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 valuethat is easy to see if for some reasonwe use it uninitialized. */zlentry tail;/* Find out prevlen for the entry that is inserted. *//* 这里区分p是否的尾结点*//* p是尾结点也就是p[0]==0xFF的时候需要分两种情况1. list本身就是空，p没有前向结点2. list非空，p是最后的end结点，p的前向结点是tail entry*/if (p[0] != ZIP_END) {ZIP_DECODE_PREVLEN(p, prevlensize, prevlen); /* 不是尾结点，直接解析出前向结点长度*/} else {unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl); /* 取出list的尾结点 */if (ptail[0] != ZIP_END) { /* 则说明list非空，p是最后end，p有前向结点*/prevlen = zipRawEntryLength(ptail); /* 得到前向结点长度*/}}/* See if the entry can be encoded *//* 尝试能否转换成整数，否则就用字符串*/if (zipTryEncoding(s,slen,&value,&encoding)) {/* 'encoding' is set to the appropriate integer encoding */reqlen = zipIntSize(encoding);} else {/* 'encoding' is untouched, however zipStoreEntryEncoding 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. *//* 结点的size=前向结点长度字节数 + 本结点的长度字节数*//* 需要对前向结点长度和本结点进行encode得到编码后的字节数*/reqlen += zipStorePrevEntryLength(NULL,prevlen);reqlen += zipStoreEntryEncoding(NULL,encoding,slen);/* 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. *//* 新节点new插入到了p的位置，也就说是new是p的前向结点，即就是...->new->p->...所以需要判断p的prelen空间能否存的下new的长度，如果可以，则p不需要扩容，否则p的prelen字段需要扩容*/int forcelarge = 0;/* zipPrevLenByteDiff(p, reqlen)返回encode(reqlen)-encode(p->len)*/nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;/* nextdiff < 0 则说明p的prelen大于reqlen，也就说p无需扩容nextdiff的取值共有-4， 0， 4三种情况nextdiff==4则说明p->prelen不足以存new的len，p结点需要扩容nextdiff==0nextdiff==-4则说明p->prelen完全能容纳new的长度，不需要扩容*/if (nextdiff == -4 && reqlen < 4) {/* 这里是说p->prelen是5字节，而new->len只占1字节，也就是说多余了4字节 */nextdiff = 0;forcelarge = 1;}/* Store offset because a realloc may change the address of zl. */offset = p-zl;zl = ziplistResize(zl,curlen+reqlen+nextdiff); /* 新list的长度 = 旧list + 新节点 + 扩容字节*/p = zl+offset;/* Apply memory move when necessary and update tail offset. */if (p[0] != ZIP_END) {/* Subtract one because of the ZIP_END bytes */memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);/* Encode this entry's raw length in the next entry. */if (forcelarge)/* p->prelen多余了4字节，但是不缩小，强制填充*/zipStorePrevEntryLengthLarge(p+reqlen,reqlen);elsezipStorePrevEntryLength(p+reqlen,reqlen);/* Update offset for tail *//* 设置最后0xff结点 */ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);/* 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);/* p的下一个不是0xFF结点，则需要吧nextdiff也加到list*/if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);}} else {/* This element will be the new tail. */// 新元素是新的表尾节点，则覆盖0xff结点ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);}/* 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) {offset = p-zl;zl = __ziplistCascadeUpdate(zl,p+reqlen);p = zl+offset;}/* Write the entry *//* 存储新节点的prelen */p += zipStorePrevEntryLength(p,prevlen);/* 存储新节点的slen*/p += zipStoreEntryEncoding(p,encoding,slen);/*存储新节点的value*/if (ZIP_IS_STR(encoding)) {memcpy(p,s,slen);} else {zipSaveInteger(p,value,encoding);}/*list->length++，注意，如果超过了UINT16_MAX，则该调用实际为空*/ZIPLIST_INCR_LENGTH(zl,1);return zl;
     }
     

   • 删除

     unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {/* p指向的是要删除的结点，当p被删除后，p应该是指向了p->next，但是删除可能会引起内存重新分配，所以记录p的偏移位置，等删除p以后再根据offset还原，得到的就是p->next*/size_t offset = *p-zl;zl = __ziplistDelete(zl,*p,1);/* Store pointer to current element in p, because ziplistDelete will* do a realloc which might result in a different "zl"-pointer.* When the delete direction is back to front, we might delete the last* entry and end up with "p" pointing to ZIP_END, so check this. */*p = zl+offset;return zl;
     }unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {/*删除p开始的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++; /*统计真正要删除的元素个数*/}/* 注意，此时p已经指向了最后一个要删除元素的next，所以totlen就是总共要删除的字节数*/totlen = p-first.p; /* Bytes taken by the element(s) to delete. */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*	int zipStorePrevEntryLength(a, b) return b-a;*/nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);/* 如果nextdiff>0, 则说明小了，p不足以容纳first.prelen，需要扩容*//* Note that there is always space when p jumps backward: if* the new previous entry is large, one of the deleted elements* had a 5 bytes prevlen header, so there is for sure at least* 5 bytes free and we need just 4. *//* 注意的是我们是在删除元素，所以如果需要扩容，那么直接复用要删除的内存而不需要重新申请 */p -= nextdiff; /* 如果nextdiff>0，则等价于p向前移动了，否则就是向后移动了 */zipStorePrevEntryLength(p,first.prevrawlen);/* Update offset for tail *//* 设置链表的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);/* 如果p->next不是0xFF，则有内存移动，需要吧nextdiff算到总长度里面 */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 *//* 将p移动到first位置 */memmove(first.p,p,intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1); /* 需要注意的bytes是老链表的长度*/} else {/* The entire tail was deleted. No need to move memory. *//* 如果删除的结点一直到了链表的尾部，也就是first结点后的所有结点都删除，那么直接关系链表的tail就可以了*/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 *//* 注意的是虽然结点p修改正确了，但是由于p->prelen变化了，也就是p结点的header变了，这可能会导致p->next->prelen存不下p结点的长度* 进而导致后面结点连锁更新*/if (nextdiff != 0)zl = __ziplistCascadeUpdate(zl,p);}return zl;
     }
     

   • 遍历

     unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {((void) zl);/* "p" could be equal to ZIP_END, caused by ziplistDelete,* and we should return NULL. Otherwise, we should return NULL* when the *next* element is ZIP_END (there is no next entry). */if (p[0] == ZIP_END) {return NULL;}p += zipRawEntryLength(p);if (p[0] == ZIP_END) {return NULL;}return p;
     }unsigned int zipRawEntryLength(unsigned char *p) {unsigned int prevlensize, encoding, lensize, len;ZIP_DECODE_PREVLENSIZE(p, prevlensize);ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);return prevlensize + lensize + len;
     }
     

   • 连锁更新

     /* 连锁更新p后面的结点 */
     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) { // 循环到最后zipEntry(p, &cur);rawlen = cur.headersize + cur.len;rawlensize = zipStorePrevEntryLength(NULL,rawlen); // 得到存储当前结点所需要的字节数/* Abort if there is no next entry. */if (p[rawlen] == ZIP_END) break; /* p->next是0xff，则说明后面没有结点了 */zipEntry(p+rawlen, &next); /* 解析p->next *//* Abort when "prevlen" has not changed. */if (next.prevrawlen == rawlen) break; /* 如果字节数相等，则说明已经正常了，可以直接返回 */if (next.prevrawlensize < rawlensize) { /* 存储p所需要的字节数 > p->next的prelen，也就是说p->next需要扩容*//* The "prevlen" field of "next" needs more bytes to hold* the raw length of "cur". */offset = p-zl; /* 后面会重新分配内存，所以先记下p的offset */extra = rawlensize-next.prevrawlensize; /* 额外的字节数 */zl = ziplistResize(zl,curlen+extra); /* 重新申请内存 */p = zl+offset; /* p在新链表的位置 *//* Current pointer and offset for next element. */np = p+rawlen; /* p的新next*/noffset = np-zl; /* p->next的offset *//* Update tail offset when next element is not the tail element. *//* 如果np不是最后一个节点 */if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {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);zipStorePrevEntryLength(np,rawlen);/* Advance the cursor */p += rawlen;curlen += extra;} else {if (next.prevrawlensize > rawlensize) {/* This would result in shrinking, which we want to avoid.* So, set "rawlen" in the available bytes. *//* 字节空闲了，强制填充 */zipStorePrevEntryLengthLarge(p+rawlen,rawlen);} else {/* 空间刚好合适 */zipStorePrevEntryLength(p+rawlen,rawlen);}/* Stop here, as the raw length of "next" has not changed. */break;}}return zl;
     }
     

2. zipmap:

   • 创建

     /* Create a new empty zipmap. */
     unsigned char *zipmapNew(void) {unsigned char *zm = zmalloc(2);zm[0] = 0; /* Length */zm[1] = ZIPMAP_END;return zm;
     }
     

   • 插入

     /* Set key to value, creating the key if it does not already exist.* If 'update' is not NULL, *update is set to 1 if the key was* already preset, otherwise to 0. */
     unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {unsigned int zmlen, offset;unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);unsigned int empty, vempty;unsigned char *p;freelen = reqlen;if (update) *update = 0;p = zipmapLookupRaw(zm,key,klen,&zmlen);if (p == NULL) {/* Key not found: enlarge */zm = zipmapResize(zm, zmlen+reqlen);p = zm+zmlen-1;zmlen = zmlen+reqlen;/* Increase zipmap length (this is an insert) */if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;} else {/* Key found. Is there enough space for the new value? *//* Compute the total length: */if (update) *update = 1;freelen = zipmapRawEntryLength(p);if (freelen < reqlen) {/* Store the offset of this key within the current zipmap, so* it can be resized. Then, move the tail backwards so this* pair fits at the current position. */offset = p-zm;zm = zipmapResize(zm, zmlen-freelen+reqlen);p = zm+offset;/* The +1 in the number of bytes to be moved is caused by the* end-of-zipmap byte. Note: the *original* zmlen is used. */memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));zmlen = zmlen-freelen+reqlen;freelen = reqlen;}}/* We now have a suitable block where the key/value entry can* be written. If there is too much free space, move the tail* of the zipmap a few bytes to the front and shrink the zipmap,* as we want zipmaps to be very space efficient. */empty = freelen-reqlen;if (empty >= ZIPMAP_VALUE_MAX_FREE) {/* First, move the tail <empty> bytes to the front, then resize* the zipmap to be <empty> bytes smaller. */offset = p-zm;memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));zmlen -= empty;zm = zipmapResize(zm, zmlen);p = zm+offset;vempty = 0;} else {vempty = empty;}/* Just write the key + value and we are done. *//* Key: */p += zipmapEncodeLength(p,klen);memcpy(p,key,klen);p += klen;/* Value: */p += zipmapEncodeLength(p,vlen);*p++ = vempty;memcpy(p,val,vlen);return zm;
     }
     

   • 删除

     /* Remove the specified key. If 'deleted' is not NULL the pointed integer is* set to 0 if the key was not found, to 1 if it was found and deleted. */
     unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {unsigned int zmlen, freelen;unsigned char *p = zipmapLookupRaw(zm,key,klen,&zmlen);if (p) {freelen = zipmapRawEntryLength(p);memmove(p, p+freelen, zmlen-((p-zm)+freelen+1));zm = zipmapResize(zm, zmlen-freelen);/* Decrease zipmap length */if (zm[0] < ZIPMAP_BIGLEN) zm[0]--;if (deleted) *deleted = 1;} else {if (deleted) *deleted = 0;}return zm;
     }

   • 遍历

     /* Search a key and retrieve the pointer and len of the associated value.* If the key is found the function returns 1, otherwise 0. */
     int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen) {unsigned char *p;if ((p = zipmapLookupRaw(zm,key,klen,NULL)) == NULL) return 0;p += zipmapRawKeyLength(p);*vlen = zipmapDecodeLength(p);*value = p + ZIPMAP_LEN_BYTES(*vlen) + 1;return 1;
     }
     

四、连锁更新

1. ziplist:

   /* When an entry is inserted, we need to set the prevlen field of the next* entry to equal the length of the inserted entry. It can occur that this* length cannot be encoded in 1 byte and the next entry needs to be grow* a bit larger to hold the 5-byte encoded prevlen. This can be done for free,* because this only happens when an entry is already being inserted (which* causes a realloc and memmove). However, encoding the prevlen may require* that this entry is grown as well. This effect may cascade throughout* the ziplist when there are consecutive entries with a size close to* ZIP_BIG_PREVLEN, so we need to check that the prevlen can be encoded in* every consecutive entry.** Note that this effect can also happen in reverse, where the bytes required* to encode the prevlen field can shrink. This effect is deliberately ignored,* because it can cause a "flapping" effect where a chain prevlen fields is* first grown and then shrunk again after consecutive inserts. Rather, the* field is allowed to stay larger than necessary, because a large prevlen* field implies the ziplist is holding large entries anyway.** The pointer "p" points to the first entry that does NOT need to be* updated, i.e. consecutive fields MAY need an update. */
   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) {zipEntry(p, &cur);rawlen = cur.headersize + cur.len;rawlensize = zipStorePrevEntryLength(NULL,rawlen);/* Abort if there is no next entry. */if (p[rawlen] == ZIP_END) break;zipEntry(p+rawlen, &next);/* Abort when "prevlen" has not changed. */if (next.prevrawlen == rawlen) break;if (next.prevrawlensize < rawlensize) {/* The "prevlen" field of "next" needs more bytes to hold* the raw length of "cur". */offset = p-zl;extra = rawlensize-next.prevrawlensize;zl = ziplistResize(zl,curlen+extra);p = zl+offset;/* Current pointer and offset for next element. */np = p+rawlen;noffset = np-zl;/* Update tail offset when next element is not the tail element. */if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {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);zipStorePrevEntryLength(np,rawlen);/* Advance the cursor */p += rawlen;curlen += extra;} else {if (next.prevrawlensize > rawlensize) {/* This would result in shrinking, which we want to avoid.* So, set "rawlen" in the available bytes. */zipStorePrevEntryLengthLarge(p+rawlen,rawlen);} else {zipStorePrevEntryLength(p+rawlen,rawlen);}/* Stop here, as the raw length of "next" has not changed. */break;}}return zl;
   }
   

   原文出处：.html