您是小站的第 27972 位访客,欢迎~

您现在的位置是: 网站首页 > 程序设计  > redis 

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

2021年9月10日 00:19 191人围观

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

一、存储结构

  1. ziplist:

  2. 内存布局 ​

    1. 各字段含义

    2. zlbytes:压缩列表的字节长度,占4个字节,因此压缩列表最长(2^32)-1字节;

    3. zltail:压缩列表尾元素相对于压缩列表起始地址的偏移量,占4个字节;
    4. zllen:压缩列表的元素数目,占两个字节;那么当压缩列表的元素数目超过(2^16)-1怎么处理呢?此时通过zllen字段无法获得压缩列表的元素数目,必须遍历整个压缩列表才能获取到元素数目;
    5. entryX:压缩列表存储的若干个元素,可以为字节数组或者整数;entry的编码结构后面详述;
    6. zlend:压缩列表的结尾,占一个字节,恒为0xFF
  3. entry定义

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

  5. 内存布局

搜狗截图20210815222521

  1. 各字段含义
    • 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 bytes 
                                       header. Integers always use a single byte.*/ 
       unsigned int len;            /* Bytes used to represent the actual entry. 
                                       For strings this is just the string length 
                                       while for integers it is 1, 2, 3, 4, 8 or 
                                       0 (for 4 bit immediate) depending on the 
                                       number range. */ 
       unsigned int headersize;     /* prevrawlensize + lensize. */ 
       unsigned char encoding;      /* Set to ZIP_STR_* or ZIP_INT_* depending on 
                                       the entry encoding. However for 4 bits 
                                       immediate integers this can assume a range 
                                       of values and must be range-checked. */ 
       unsigned char *p;            /* Pointer to the very start of the entry, that 
                                       is, this points to prev-entry-len field. */ 
   } zlentry; 
  1. 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); \ 
   } 
  1. zipmap:

四、基本操作

  1. ziplist:

  2. 创建

     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 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. */ 
         /* 这里区分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==0 
            nextdiff==-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); 
             else 
                 zipStorePrevEntryLength(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; 
     } 
  1. zipmap:

  2. 创建

     /* 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; 
   }