Redis源码阅读 - Redis数据结构压缩链表(ziplist)

#define ZIP_STR_MASK 0xc0   // 最高2位（7、8位）用于标识字符串 1100 0000， 字符串不会以11作为最高位，如果前两位是11代表是数字
#define ZIP_INT_MASK 0x30   // 5位和6位标识整数  0011 0000      最高两位必须是11
#define ZIP_STR_06B (0 << 6)  // 第一个字节后6位：表示字符串长度（0~63）
#define ZIP_STR_14B (1 << 6)  // 14位存储字符串长度   0100 0000
#define ZIP_STR_32B (2 << 6)  // 32位存储字符串长度   1000 0000
#define ZIP_INT_16B (0xc0 | 0<<4)   // 2字节整数，。 1100 0000
#define ZIP_INT_32B (0xc0 | 1<<4)   // 4字节整数  1101 0000
#define ZIP_INT_64B (0xc0 | 2<<4)   // 8字节整数  1110 0000
#define ZIP_INT_24B (0xc0 | 3<<4)    // 3字节整数
#define ZIP_INT_8B 0xfe             // 1字节整数
#define ZIP_INT_IMM_MASK 0x0f       // 四位小整数。最小是0，最大12 0001 表示整数0。也叫立即数
#define ZIP_INT_IMM_MIN 0xf1    // 11110001 立即数的最小值表示法 
#define ZIP_INT_IMM_MAX 0xfd    // 11111101 立即数的最大值表示法

unsigned char *ziplistNew(void) {  // 创建一个空的ziplist
    unsigned int bytes = ZIPLIST_HEADER_SIZE+ZIPLIST_END_SIZE;  // 初始申请内存大小只有头和尾, 共11字节。
    unsigned char *zl = zmalloc(bytes);
    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);    // 把总大小赋值给zl的前4个字节，利用宏定义
    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);  // 把头大小赋给第二个4字节，存储最后一个元素的偏移量
    ZIPLIST_LENGTH(zl) = 0;   // 此时没有数据，长度存储0
    zl[bytes-1] = ZIP_END;
    return zl;
}

// 在指针p处插入一个新数据 s， 它的长度是 slen
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen, newlen;  // 记录ziplist当前的大小，需要的长度 和 插入后新的总长度
    unsigned int prevlensize, prevlen = 0;
    size_t offset;
    int nextdiff = 0;
    unsigned char encoding = 0;
    long long value = 123456789; /* 为了防止警告，我们将其初始化。使用一个容易看出的值，以防万一我们因某种原因未初始化就使用它 */
    zlentry tail;

    if (p[0] != ZIP_END) {  // 如果指针p不指向终止符，获取到指针p的前一个元素的长度prevlen 和 prevlen的大小
        ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
    } else {
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);   // 如果p指向终止符，获取最后一个元素的指针
        if (ptail[0] != ZIP_END) {    // 如果最后一个元素不是终止符，说明这个ziplist不为空，获取最后一个元素的总内存大小。
            prevlen = zipRawEntryLengthSafe(zl, curlen, ptail);
        }  // 如果ziplist为空，那什么都不做的，即初始化的prevlen为0
    }

    if (zipTryEncoding(s,slen,&value,&encoding)) {    // 如果这个新数据是纯数字组成的字符串，尝试进行编码
        reqlen = zipIntSize(encoding);                // 计算存储这个整数需要的空间
    } else {
        reqlen = slen;                                // 如果不能编码为整数，那这个字符串的实际长度就是需要的空间
    }
 
    reqlen += zipStorePrevEntryLength(NULL,prevlen);   // 加上存储前一个元素需要的空间
    reqlen += zipStoreEntryEncoding(NULL,encoding,slen);  // 加上 encoding 字段需要占用的字节数

    int forcelarge = 0;    // 当插入位置不等于尾部时，我们需要确保下一个条目的prevlen字段能够容纳当前条目的长度
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;  // 如果插入位置在尾部则nextdiff=0，如果不在尾部则通过函数计算 前一个当前条目占用的内存 和 下一个条目元素prevlen字段的差值

    if (nextdiff == -4 && reqlen < 4) {    // 如果下一个节点的 prevlen 需要从 5 字节缩小为 1 字节， 但是新条目的总长度小于4(这里是一个阈值权衡只有当当前元素的体量 ≥ 4 时，这次结构变化才被认为“值得”)。
        nextdiff = 0;    // 不需要调整 next 节点大小
        forcelarge = 1;  // 强制 next 节点继续使用 5 字节 prevlen
    }  // 当前插入的 entry 太小，“不值得”为了它去收缩 next 的 prevlen（5→1）  因此直接放弃这次“节省 4 字节”的机会。

    offset = p-zl;   // 存储p指针的偏移量，因为重新分配可能会改变zl的地址
    newlen = curlen+reqlen+nextdiff;   // 新的ziplist总大小
    zl = ziplistResize(zl,newlen);
    p = zl+offset;

    if (p[0] != ZIP_END) {    // 如果p没有指向终止符
        memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);   // 把p位置以后的元素向后移动
        if (forcelarge)   // 更新“新插入节点后面那个节点”的 prevlen
            zipStorePrevEntryLengthLarge(p+reqlen,reqlen);   // 正常规则（1 or 5 byte）
        else
            zipStorePrevEntryLength(p+reqlen,reqlen);   // 强制 5 byte
        ZIPLIST_TAIL_OFFSET(zl) =
            intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);   // 更新 tail 偏移

        assert(zipEntrySafe(zl, newlen, p+reqlen, &tail, 1));
        if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {       // 处理 nextdiff 对 tail 的影响
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
        }
    } else {
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);   // 如果插在尾部，新插入节点就是 tail
    }

    if (nextdiff != 0) {    //  当 nextdiff != 0 时，说明后续节点的 prevlen 发生了变化，可能引发连锁更新，这里就递归修复整个链表
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);  // 进行级联更新
        p = zl+offset;
    }

    p += zipStorePrevEntryLength(p,prevlen);     // 把新 entry 真正写入到 ziplist 中
    p += zipStoreEntryEncoding(p,encoding,slen);
    if (ZIP_IS_STR(encoding)) {
        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) {   
    // ziplist级联更新，当中间一个元素变化时，它后面的元素可能全跟着一起变化，因为后面的元素都要保存前一个元素的长度， p传入变化的那个元素的地址
    zlentry cur;
    size_t prevlen, prevlensize, prevoffset; /* Informat of the last changed entry. */
    size_t firstentrylen; /* Used to handle insert at head. */
    size_t rawlen, curlen = intrev32ifbe(ZIPLIST_BYTES(zl));
    size_t extra = 0, cnt = 0, offset;
    size_t delta = 4; /* Extra bytes needed to update a entry's prevlen (5-1). */
    unsigned char *tail = zl + intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl));  // 记录最后一个元素的指针

    if (p[0] == ZIP_END) return zl;      // 如果ziplist为空直接返回，不需要更新
    zipEntry(p, &cur); /* no need for "safe" variant since the input pointer was validated by the function that returned it. */
    firstentrylen = prevlen = cur.headersize + cur.len;
    prevlensize = zipStorePrevEntryLength(NULL, prevlen);
    prevoffset = p - zl;
    p += prevlen;

    while (p[0] != ZIP_END) {   // 从传入p指针的下一个元素开始循环
        assert(zipEntrySafe(zl, curlen, p, &cur, 0));
        if (cur.prevrawlen == prevlen) break;

        if (cur.prevrawlensize >= prevlensize) {   // 如果p变小了，那说明当前的空间是足够的，即使由5字节变为了1字节，也不进行释放直接填充新的长度信息
            if (cur.prevrawlensize == prevlensize) {
                zipStorePrevEntryLength(p, prevlen);
            } else {
                zipStorePrevEntryLengthLarge(p, prevlen);
            }
            break;
        }
        assert(cur.prevrawlen == 0 || cur.prevrawlen + delta == prevlen);
        rawlen = cur.headersize + cur.len;    // 获取当前cur的实际长度
        prevlen = rawlen + delta;             // 计算下一个元素应该存储的长度，即当前元素的长度
        prevlensize = zipStorePrevEntryLength(NULL, prevlen);  // 计算存储当前元素长度需要的空间
        prevoffset = p - zl;
        p += rawlen;
        extra += delta;  // extra 统计需要额外增加的空间
        cnt++;           // 统计需要进行更新的元素数量
    }

    if (extra == 0) return zl;  // 如果不需要额外扩充说明当前空间满足的，不需要更新
    if (tail == zl + prevoffset) {  // 本次级联更新中，最后一个被更新的 entry，如果正好就是 ziplist 的尾元素
        if (extra - delta != 0) {  // 如果尾部是唯一一个被更新的元素，就需要更新偏移，否则就需要更新偏移
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra-delta);
        }
    } else {
        ZIPLIST_TAIL_OFFSET(zl) =  // 更新最后一个元素的偏移
            intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
    }

    offset = p - zl; // “p”指向原始ziplist中第一个未更改的字节
    zl = ziplistResize(zl, curlen + extra);
    p = zl + offset;
    memmove(p + extra, p, curlen - offset - 1);  // 把不需要修改的内容向后移动
    p += extra;

    while (cnt) {   // 需要修改的元素做遍历，逐个调整
        zipEntry(zl + prevoffset, &cur); /* no need for "safe" variant since we already iterated on all these entries above. */
        rawlen = cur.headersize + cur.len;
        memmove(p - (rawlen - cur.prevrawlensize), 
                zl + prevoffset + cur.prevrawlensize, 
                rawlen - cur.prevrawlensize);
        p -= (rawlen + delta);
        if (cur.prevrawlen == 0) {
            zipStorePrevEntryLength(p, firstentrylen);
        } else {
            zipStorePrevEntryLength(p, cur.prevrawlen+delta);
        }
        prevoffset -= cur.prevrawlen;
        cnt--;
    }
    return zl;
}