内存节省到极致！！！Redis中的压缩表,值得了解...

//返回整个压缩列表的总字节
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))

//返回压缩列表的tail_offset变量，方便获取最后一个节点的位置
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))

//返回压缩列表的节点数量
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

//返回压缩列表的表头的字节数
//（内存字节数zlbytes，最后一个节点地址ztail_offset,节点总数量zllength）
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))

//返回压缩列表最后结尾的字节数
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))

//返回压缩列表首节点地址
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)

//返回压缩列表尾节点地址
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))

//返回压缩列表最后结尾的地址
#define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

/* We use this function to receive information about a ziplist entry.
 * Note that this is not how the data is actually encoded, is just what we
 * get filled by a function in order to operate more easily. */
typedef struct zlentry {
    unsigned int prevrawlensize; //记录prevrawlen需要的字节数
    unsigned int prevrawlen;    //记录上个节点的长度
    unsigned int lensize;        //记录len需要的字节数
    unsigned int len;           //记录节点长度
    unsigned int headersize;   //prevrawlensize+lensize 
    unsigned char encoding;   //编码格式
    unsigned char *p;       //具体的数据指针
} zlentry;

unsigned char *ziplistNew(void) {
    //表头加末端大小
    unsigned int bytes = ZIPLIST_HEADER_SIZE+1;

    //为上面两部分（表头和末端）分配空间
    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 *__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循环，当到最后一个节点的时候结束循环
    while (p[0] != ZIP_END) {
        //将节点数据保存在cur中
        zipEntry(p, &cur);
        //取前节点长度编码所占字节数，和当前节点长度编码所占字节数，在加上当前节点的value长度
        //rawlen = prev_entry_len + encoding + value
        rawlen = cur.headersize + cur.len;
        rawlensize = zipStorePrevEntryLength(NULL,rawlen);

        //如果没有下一个节点则跳出循环
        if (p[rawlen] == ZIP_END) break;
        //取出后面一个节点放在next中
        zipEntry(p+rawlen, &next);

        //当next的prevrawlen，即保存的上一个节点等于rawlen，说明不需要调整，现在的长度合适
        if (next.prevrawlen == rawlen) break;

        //如果next对前一个节点长度的编码所需的字节数next.prevrawlensize小于上一个节点长度进行编码所需要的长度
        //因此要对next节点的header部分进行扩展，以便能够表示前一个节点的长度
        if (next.prevrawlensize < rawlensize) {
            //记录当前指针的偏移量
            offset = p-zl;
            ///需要扩展的字节数
            extra = rawlensize-next.prevrawlensize;
            //调整压缩列表的空间大小            
            zl = ziplistResize(zl,curlen+extra);
            //还原p指向的位置
            p = zl+offset;

           //next节点的新地址
            np = p+rawlen;
            //记录next节点的偏移量
            noffset = np-zl;

          //更新压缩列表的表头tail_offset成员，如果next节点是尾节点就不用更新
            if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
                ZIPLIST_TAIL_OFFSET(zl) =
                    intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
            }

           //移动next节点到新地址，为前驱节点cur腾出空间
            memmove(np+rawlensize,
                np+next.prevrawlensize,
                curlen-noffset-next.prevrawlensize-1);
            //将next节点的header以rawlen长度进行重新编码，更新prevrawlensize和prevrawlen
            zipStorePrevEntryLength(np,rawlen);

            //更新p指针，移动到next节点，处理next的next节点
            p += rawlen;
            //更新压缩列表的总字节数
            curlen += extra;
        } else {
            // 如果需要的内存反而更少了则强制保留现有内存不进行缩小
            // 仅浪费一点内存却省去了大量移动复制操作而且后续增大时也无需再扩展
            if (next.prevrawlensize > rawlensize) {
                zipStorePrevEntryLengthLarge(p+rawlen,rawlen);
            } else {
             
                zipStorePrevEntryLength(p+rawlen,rawlen);
            }

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