Redis 5.0数据结构之压缩列表ziplist源码详解（二）

由于篇幅过长，ziplist的源码分析分为两篇，本篇是第二篇，涉及到ziplist的添加元素、查找元素、删除元素以及连锁更新实现的源码分析。
Redis 5.0数据结构之压缩列表ziplist源码详解（一）

前文已经提及了压缩列表ziplist的主要设计初衷是尽量节约空间，因此设计出了一系列的压缩编码，将ziplist设计成了内存地址连续，使用基地址+偏移量的方式来访问压缩列表内节点，并且说明了压缩列表节点结构具有的属性以及相应的作用，通过源码分析了对于节点内各属性的编码的实现细节。

接下来将继续通过源码解析ziplist的各操作是如何实现的。

添加元素

添加元素是调用ziplistPush函数，其中参数where参数决定新元素插入位置。

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);
}

实际完成添加元素工作的是__ziplistInsert函数，源码如下：

// 将值长度为slen的节点存放到zl压缩列表的位置p处
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
   
	// 因为涉及到位运算 大小端转换
	// Redis默认小端存储 如果在大端存储的机器上允许 需要大小端转换 
	// reqlen为当前节点所需长度
    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. */
    // 非尾部插入
    if (p[0] != ZIP_END) {
   
    	// 获取prevlen 宏定义函数见下
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    // 尾部插入
    } else {
   
    	// 获取尾节点
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        // 如果ziplist不为空
        if (ptail[0] != ZIP_END) {
   
        	// 则prevlen就是尾节点的长度
            prevlen = zipRawEntryLength(ptail);
        }
    }

    /* See if the entry can be encoded */
    // 尝试对value整数编码
    if (zipTryEncoding(s,slen,&value,&encoding)) {
   
        /* 'encoding' is set to the appropriate integer encoding */
        // 记录整数编码所需长度
        reqlen = zipIntSize(encoding);
    // 没法整数编码 则value保存的是字符串
    } 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. */
    // 需要空间存放上一个节点的长度和当前节点长度
    // 分别获取并累加到reqlen中
    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. */
    // forcelarge用于判断prevrawlen编码时需要使用哪个函数处理
    // forcelarge为0时 使用zipStorePrevEntryLength编码 该函数用于处理len小于254的情况
  	// forcelarge为1时 使用zipStorePrevEntryLengthLarge编码 该函数处理len大于等于254的情况  
    int forcelarge = 0;
    // 由于是插入操作 相当于新节点的下一个节点的前置节点更换了 需要判断下一个节点的prevlen是否够用
    // prevlen的值只有两种可能 分别是1或5 zipPrevLenByteDiff函数见下文注释
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
    // 此时有两种情况需要改变 即新节点len为1 下一个节点prevlen为5 或者相反
    // 判断成立的情况是 新节点len为1 下一个节点prevlen为5
    // 需要记录使用zipStorePrevEntryLengthLarge存储prevlen 并且记录nextdiff不需要扩容
    if (nextdiff == -4 && reqlen < 4) {
   
        nextdiff = 0;
        forcelarge = 1;
    }

    /* Store offset because a realloc may change the address of zl. */
    // 保存偏移量 因为realloc也可能改变ziplist的地址
    offset = p-zl;
    // 重设ziplist的大小
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);
    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&#