redis 源码阅读 - 内存编码篇 - 压缩列表 ziplist

2.压缩列表 ziplist.h 和 ziplist.c

数据结构定义

  • 有序整数集合

    typedef struct zlentry {
        // prevrawlen :前置节点的长度
        // prevrawlensize :编码 prevrawlen 所需的字节大小
        unsigned int prevrawlensize, prevrawlen;
        // len :当前节点值的长度
        // lensize :编码 len 所需的字节大小
        unsigned int lensize, len;
        // 当前节点 header 的大小
        // 等于 prevrawlensize + lensize
        unsigned int headersize;
        // 当前节点值所使用的编码类型
        unsigned char encoding;
        // 指向当前节点的指针
        unsigned char *p;
    } zlentry;
    
  • 布局
    在这里插入图片描述

    // <zlbytes> 是一个uint32_t,保存着 ziplist 使用的内存数量
    #define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
    
    // <zltail> 是一个uint32_t,保存着到达列表中最后一个节点的偏移量
    #define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
    // 最后一个节点
    #define ZIPLIST_ENTRY_TAIL(zl)  ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
    
    // <zllen> 是一个uint16_t, 保存着列表中的节点数量
    #define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
    
    // <zlend> 的长度为 1 字节,值为 255 ,标识列表的末尾
    #define ZIP_END 255
    #define ZIPLIST_ENTRY_END(zl)   ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
    
    // 返回 ziplist 表头的大小
    #define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t)*2+sizeof(uint16_t))
    // 第一个节点
    #define ZIPLIST_ENTRY_HEAD(zl)  ((zl)+ZIPLIST_HEADER_SIZE)
    
    
  • 编码

    // 节点 带有一个 header,包含 2 部分:
    // 前置节点 长度
    // 当前节点 长度 & type
    
    // 长度
    // 1) 小于254, 1个字节
    // 2) 大于等于254, 5个字节,第一个字节 = 254, 后四个字节保存长度
    #define ZIP_BIGLEN 254
    
    // type
    // string: 2位编码 + 长度
    // |00pppppp|: 0 - 63 
    // |01pppppp|qqqqqqqq|: 64 - 16383
    // |10pppppp|qqqqqqqq|mmmmmmmm|nnnnnnnn|oooooooo|: 16383 - 
    //
    // 整数 :1个字节编码
    // |11000000|:int16_t,2字节
    // |11010000|:int32_t,4字节
    // |11100000|:int64_t,8字节
    // |11110000|:int24_t,3字节
    // |11111110|:int8_t,1字节
    // |1111xxxx|:[0,12],0字节,xxxx - 1
    
    // string编码掩码
    #define ZIP_STR_MASK 0xc0
    #define ZIP_STR_06B (0 << 6)
    #define ZIP_STR_14B (1 << 6)
    #define ZIP_STR_32B (2 << 6)
    #define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK)
    // 整数编码掩码
    #define ZIP_INT_MASK 0x30
    #define ZIP_INT_16B (0xc0 | 0<<4)
    #define ZIP_INT_32B (0xc0 | 1<<4)
    #define ZIP_INT_64B (0xc0 | 2<<4)
    #define ZIP_INT_24B (0xc0 | 3<<4)
    #define ZIP_INT_8B 0xfe
    #define ZIP_INT_IMM_MASK 0x0f
    #define ZIP_INT_IMM_MIN 0xf1    /* 11110001 */
    #define ZIP_INT_IMM_MAX 0xfd    /* 11111101 */
    #define ZIP_INT_IMM_VAL(v) (v & ZIP_INT_IMM_MASK)
    #define INT24_MAX 0x7fffff
    #define INT24_MIN (-INT24_MAX - 1)
    

Helper函数(可跳过,需要时阅读)

  • 一些宏

    #define ZIPLIST_INCR_LENGTH(zl,incr) { \
        if (ZIPLIST_LENGTH(zl) < UINT16_MAX) \
            ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl))+incr); \
    }
    #define ZIP_ENTRY_ENCODING(ptr, encoding) do {  \
        (encoding) = (ptr[0]); \
        if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
    } while(0)
    
    
  • Get int size

    static unsigned int zipIntSize(unsigned char encoding) {
        switch(encoding) {
        case ZIP_INT_8B:  return 1;
        case ZIP_INT_16B: return 2;
        case ZIP_INT_24B: return 3;
        case ZIP_INT_32B: return 4;
        case ZIP_INT_64B: return 8;
        default: return 0; /* 4 bit immediate */
        }
        assert(NULL);
        return 0;
    }
    
  • encode type & length

    static unsigned int zipEncodeLength(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
        unsigned char len = 1, buf[5];
        // 编码字符串
        if (ZIP_IS_STR(encoding)) {
            if (rawlen <= 0x3f) {
                if (!p) return len;
                buf[0] = ZIP_STR_06B | rawlen;
            } else if (rawlen <= 0x3fff) {
                len += 1;
                if (!p) return len;
                buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
                buf[1] = rawlen & 0xff;
            } else {
                len += 4;
                if (!p) return len;
                buf[0] = ZIP_STR_32B;
                buf[1] = (rawlen >> 24) & 0xff;
                buf[2] = (rawlen >> 16) & 0xff;
                buf[3] = (rawlen >> 8) & 0xff;
                buf[4] = rawlen & 0xff;
            }
        // 编码整数
        } else {
            if (!p) return len;
            buf[0] = encoding;
        }
        // 将编码后的长度写入 p 
        memcpy(p,buf,len);
        // 返回编码所需的字节数
        return len;
    }
    
  • decode type & length

    #define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {                    
        /* 取出值的编码类型 */                                                     
        ZIP_ENTRY_ENCODING((ptr), (encoding));                                     
        /* 字符串编码 */                                                           
        if ((encoding) < ZIP_STR_MASK) {                                           
            if ((encoding) == ZIP_STR_06B) {                                       
                (lensize) = 1;                                                     
                (len) = (ptr)[0] & 0x3f;                                           
            } else if ((encoding) == ZIP_STR_14B) {                                
                (lensize) = 2;                                                     
                (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1];                       
            } else if (encoding == ZIP_STR_32B) {                                 
                (lensize) = 5;                                                    
                (len) = ((ptr)[1] << 24) |                                         
                        ((ptr)[2] << 16) |                                         
                        ((ptr)[3] <<  8) |                                         
                        ((ptr)[4]);                                                
            } else {                                                               
                assert(NULL);                                                      
            }                                                                      
        /* 整数编码 */                                                             
        } else {                                                                   
            (lensize) = 1;                                                         
            (len) = zipIntSize(encoding);                                          
        }                                                                          
    } while(0);
    
  • 编码前置节点长度

    static unsigned int zipPrevEncodeLength(unsigned char *p, unsigned int len) {
        // 仅返回编码 len 所需的字节数量
        if (p == NULL) {
            return (len < ZIP_BIGLEN) ? 1 : sizeof(len)+1;
        // 写入并返回编码 len 所需的字节数量
        } else {
            // 1 字节
            if (len < ZIP_BIGLEN) {
                p[0] = len;
                return 1;
            // 5 字节
            } else {
                // 添加 5 字节长度标识
                p[0] = ZIP_BIGLEN;
                // 写入编码
                memcpy(p+1,&len,sizeof(len));
                // 如果有必要的话,进行大小端转换
                memrev32ifbe(p+1);
                // 返回编码长度
                return 1+sizeof(len);
            }
        }
    }
    static void zipPrevEncodeLengthForceLarge(unsigned char *p, unsigned int len) {
        if (p == NULL) return;
        // 设置 5 字节长度标识
        p[0] = ZIP_BIGLEN;
        // 写入 len
        memcpy(p+1,&len,sizeof(len));
        memrev32ifbe(p+1);
    }
    static int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
        unsigned int prevlensize;
        // 取出编码原来的前置节点长度所需的字节数
        // T = O(1)
        ZIP_DECODE_PREVLENSIZE(p, prevlensize);
        // 计算编码 len 所需的字节数,然后进行减法运算
        // T = O(1)
        return zipPrevEncodeLength(NULL, len) - prevlensize;
    }
    
  • 解码前置节点长度

    #define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do {                          
        if ((ptr)[0] < ZIP_BIGLEN) {                                               
            (prevlensize) = 1;                                                     
        } else {                                                                   
            (prevlensize) = 5;                                                     
        }                                                                          
    } while(0);
    
    #define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do {                     
        ZIP_DECODE_PREVLENSIZE(ptr, prevlensize);                                  
        if ((prevlensize) == 1) {                                                 
            (prevlen) = (ptr)[0];                                                  
        } else if ((prevlensize) == 5) {                                           
            assert(sizeof((prevlensize)) == 4);                                    
            memcpy(&(prevlen), ((char*)(ptr)) + 1, 4);                             
            memrev32ifbe(&prevlen);                                                
        }                                                                          
    } while(0);
    
  • Resize

    static unsigned char *ziplistResize(unsigned char *zl, unsigned int len) {
        // 用 zrealloc ,扩展时不改变现有元素
        zl = zrealloc(zl,len);
        // 更新 bytes 属性
        ZIPLIST_BYTES(zl) = intrev32ifbe(len);
        // 重新设置表末端
        zl[len-1] = ZIP_END;
        return zl;
    }
    
  • 更新前置节点长度

    static 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) {
            // 将 p 所指向的节点的信息保存到 cur 结构中
            cur = zipEntry(p);
            // 当前节点的长度
            rawlen = cur.headersize + cur.len;
            // 计算编码当前节点的长度所需的字节数
            rawlensize = zipPrevEncodeLength(NULL,rawlen);
            // 如果已经没有后续空间需要更新了,跳出
            if (p[rawlen] == ZIP_END) break;
            // 取出后续节点的信息,保存到 next 结构中
            next = zipEntry(p+rawlen);
            // 后续节点编码当前节点的空间已经足够,无须再进行任何处理,跳出
            if (next.prevrawlen == rawlen) break;
            if (next.prevrawlensize < rawlensize) {
                // next 空间的大小不足以编码 cur 的长度,需要对 next 节点的空间进行扩展
                // 记录 p 的偏移量
                offset = p-zl;
                // 计算需要增加的节点数量
                extra = rawlensize-next.prevrawlensize;
                // 扩展 zl 的大小
                zl = ziplistResize(zl,curlen+extra);
                // 还原指针 p
                p = zl+offset;
                // 记录下一节点的偏移量
                np = p+rawlen;
                noffset = np-zl;
                if ((zl+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) != np) {
                    ZIPLIST_TAIL_OFFSET(zl) =
                        intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+extra);
                }
                // | header | value |  ==>  | header |    | value |  ==>  | header      | value |
                //                                   |<-->|
                //                            为新 header 腾出的空间
                memmove(np+rawlensize,
                    np+next.prevrawlensize,
                    curlen-noffset-next.prevrawlensize-1);
                // 将新的前一节点长度值编码进新的 next 节点的 header
                zipPrevEncodeLength(np,rawlen);
                // 移动指针,继续处理下个节点
                p += rawlen;
                curlen += extra;
            } else {
                if (next.prevrawlensize > rawlensize) {
                    // 需要进行缩小,但不进行缩小操作
                    zipPrevEncodeLengthForceLarge(p+rawlen,rawlen);
                } else {
                    // 说明 cur 节点的长度正好可以编码到 next 节点的 header 中
                    zipPrevEncodeLength(p+rawlen,rawlen);
                }
                break;
            }
        }
        return zl;
    }
    
  • Get entry number

    unsigned int ziplistLen(unsigned char *zl) {
        unsigned int len = 0;
        // 节点数小于 UINT16_MAX
        if (intrev16ifbe(ZIPLIST_LENGTH(zl)) < UINT16_MAX) {
            len = intrev16ifbe(ZIPLIST_LENGTH(zl));
        // 节点数大于 UINT16_MAX 时,需要遍历整个列表才能计算出节点数
        } else {
            unsigned char *p = zl+ZIPLIST_HEADER_SIZE;
            while (*p != ZIP_END) {
                p += zipRawEntryLength(p);
                len++;
            }
            if (len < UINT16_MAX) ZIPLIST_LENGTH(zl) = intrev16ifbe(len);
        }
        return len;
    }
    size_t ziplistBlobLen(unsigned char *zl) {
        return intrev32ifbe(ZIPLIST_BYTES(zl));
    }
    

构造函数

unsigned char *ziplistNew(void) {
    // 1 字节是表末端 ZIP_END 的大小
    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;
}

解码entry

static 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;
}
static int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
    long long value;
    // 忽略太长或太短的字符串
    if (entrylen >= 32 || entrylen == 0) return 0;
    // 尝试转换
    if (string2ll((char*)entry,entrylen,&value)) {
        // 转换成功,以从小到大的顺序检查适合值 value 的编码方式
        if (value >= 0 && value <= 12) {
            *encoding = ZIP_INT_IMM_MIN+value;
        } else if (value >= INT8_MIN && value <= INT8_MAX) {
            *encoding = ZIP_INT_8B;
        } else if (value >= INT16_MIN && value <= INT16_MAX) {
            *encoding = ZIP_INT_16B;
        } else if (value >= INT24_MIN && value <= INT24_MAX) {
            *encoding = ZIP_INT_24B;
        } else if (value >= INT32_MIN && value <= INT32_MAX) {
            *encoding = ZIP_INT_32B;
        } else {
            *encoding = ZIP_INT_64B;
        }
        // 记录值到指针
        *v = value;
        // 返回转换成功标识
        return 1;
    }
    // 转换失败
    return 0;
}
static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding) {
    int16_t i16;
    int32_t i32;
    int64_t i64, ret = 0;
    if (encoding == ZIP_INT_8B) {
        ret = ((int8_t*)p)[0];
    } else if (encoding == ZIP_INT_16B) {
        memcpy(&i16,p,sizeof(i16));
        memrev16ifbe(&i16);
        ret = i16;
    } else if (encoding == ZIP_INT_32B) {
        memcpy(&i32,p,sizeof(i32));
        memrev32ifbe(&i32);
        ret = i32;
    } else if (encoding == ZIP_INT_24B) {
        i32 = 0;
        memcpy(((uint8_t*)&i32)+1,p,sizeof(i32)-sizeof(uint8_t));
        memrev32ifbe(&i32);
        ret = i32>>8;
    } else if (encoding == ZIP_INT_64B) {
        memcpy(&i64,p,sizeof(i64));
        memrev64ifbe(&i64);
        ret = i64;
    } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) {
        ret = (encoding & ZIP_INT_IMM_MASK)-1;
    } else {
        assert(NULL);
    }

    return ret;
}
static zlentry zipEntry(unsigned char *p) {
    zlentry e;
    // e.prevrawlensize 保存着编码前一个节点的长度所需的字节数
    // e.prevrawlen 保存着前一个节点的长度
    ZIP_DECODE_PREVLEN(p, e.prevrawlensize, e.prevrawlen);
    // p + e.prevrawlensize 将指针移动到列表节点本身
    // e.encoding 保存着节点值的编码类型
    // e.lensize 保存着编码节点值长度所需的字节数
    // e.len 保存着节点值的长度
    ZIP_DECODE_LENGTH(p + e.prevrawlensize, e.encoding, e.lensize, e.len);
    // 计算头结点的字节数
    e.headersize = e.prevrawlensize + e.lensize;
    // 记录指针
    e.p = p;
    return e;
}

编码entry

static void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding) {
    int16_t i16;
    int32_t i32;
    int64_t i64;
    if (encoding == ZIP_INT_8B) {
        ((int8_t*)p)[0] = (int8_t)value;
    } else if (encoding == ZIP_INT_16B) {
        i16 = value;
        memcpy(p,&i16,sizeof(i16));
        memrev16ifbe(p);
    } else if (encoding == ZIP_INT_24B) {
        i32 = value<<8;
        memrev32ifbe(&i32);
        memcpy(p,((uint8_t*)&i32)+1,sizeof(i32)-sizeof(uint8_t));
    } else if (encoding == ZIP_INT_32B) {
        i32 = value;
        memcpy(p,&i32,sizeof(i32));
        memrev32ifbe(p);
    } else if (encoding == ZIP_INT_64B) {
        i64 = value;
        memcpy(p,&i64,sizeof(i64));
        memrev64ifbe(p);
    } else if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX) {
        /* Nothing to do, the value is stored in the encoding itself. */
    } else {
        assert(NULL);
    }
}

删除entry

static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num) {
    unsigned int i, totlen, deleted = 0;
    size_t offset;
    int nextdiff = 0;
    zlentry first, tail;
    // 计算被删除节点总共占用的内存字节数
    // 以及被删除节点的总个数
    first = zipEntry(p);
    for (i = 0; p[0] != ZIP_END && i < num; i++) {
        p += zipRawEntryLength(p);
        deleted++;
    }
    // totlen 是所有被删除节点总共占用的内存字节数
    totlen = p-first.p;
    if (totlen > 0) {
        if (p[0] != ZIP_END) {
            // 执行删除
            // 可能容纳不了新的前置节点,所以需要计算新旧前置节点之间的字节数差
            nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);
            // 如果有需要的话,将指针 p 后退 nextdiff 字节,为新 header 空出空间
            p -= nextdiff;
            // 将 first 的前置节点的长度编码至 p 中
            zipPrevEncodeLength(p,first.prevrawlen);
            // 更新到达表尾的偏移量
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);
            // 如果被删除节点之后,有多于一个节点
            // 那么程序需要将 nextdiff 记录的字节数也计算到表尾偏移量中
            // 这样才能让表尾偏移量正确对齐表尾节点
            tail = zipEntry(p);
            if (p[tail.headersize+tail.len] != ZIP_END) {
                ZIPLIST_TAIL_OFFSET(zl) =
                   intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
            }
            // 从表尾向表头移动数据,覆盖被删除节点的数据
            memmove(first.p,p,
                intrev32ifbe(ZIPLIST_BYTES(zl))-(p-zl)-1);
        } else {
            // 执行这里,表示被删除节点之后已经没有其他节点了
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe((first.p-zl)-first.prevrawlen);
        }
        // 缩小并更新 ziplist 的长度
        offset = first.p-zl;
        zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);
        ZIPLIST_INCR_LENGTH(zl,-deleted);
        p = zl+offset;
        // 如果 p 所指向的节点的大小已经变更,那么进行级联更新
        // 检查 p 之后的所有节点是否符合 ziplist 的编码要求
        if (nextdiff != 0)
            zl = __ziplistCascadeUpdate(zl,p);
    }
    return zl;
}
unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) {
    // 因为 __ziplistDelete 时会对 zl 进行内存重分配
    // 而内存充分配可能会改变 zl 的内存地址
    // 所以这里需要记录到达 *p 的偏移量
    // 这样在删除节点之后就可以通过偏移量来将 *p 还原到正确的位置
    size_t offset = *p-zl;
    zl = __ziplistDelete(zl,*p,1);
    *p = zl+offset;
    return zl;
}
unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num) {
    // 根据索引定位到节点
    unsigned char *p = ziplistIndex(zl,index);
    // 连续删除 num 个节点
    return (p == NULL) ? zl : __ziplistDelete(zl,p,num);
}

插入entry

unsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where) {
    // 根据 where 参数的值,决定将值推入到表头还是表尾
    unsigned char *p;
    p = (where == ZIPLIST_HEAD) ? ZIPLIST_ENTRY_HEAD(zl) : ZIPLIST_ENTRY_END(zl);
    // 返回添加新值后的 ziplist
    return __ziplistInsert(zl,p,s,slen);
}

static unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
    // 记录当前 ziplist 的长度
    size_t curlen = intrev32ifbe(ZIPLIST_BYTES(zl)), reqlen, prevlen = 0;
    size_t offset;
    int nextdiff = 0;
    unsigned char encoding = 0;
    long long value = 123456789; 
    zlentry entry, tail;
    if (p[0] != ZIP_END) {
        // 非空,记录前置节点长度
        entry = zipEntry(p);
        prevlen = entry.prevrawlen;
    } else {
        // 检查非空
        unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
        if (ptail[0] != ZIP_END) {
            // 表尾节点为新节点的前置节点
            prevlen = zipRawEntryLength(ptail);
        }
    }

    // 优先编码整数
    // 1)value 将保存转换后的整数值
    // 2)encoding 则保存适用于 value 的编码方式
    // 无论使用什么编码, reqlen 都保存节点值的长度
    if (zipTryEncoding(s,slen,&value,&encoding)) {
        reqlen = zipIntSize(encoding);
    } else {
        reqlen = slen;
    }
    // 计算编码前置节点的长度所需的大小
    reqlen += zipPrevEncodeLength(NULL,prevlen);
    // 计算编码当前节点值所需的大小
    reqlen += zipEncodeLength(NULL,encoding,slen);

    // 更改p的前置节点长度编码
    nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;

    // 记录旧偏移
    offset = p-zl;
    // curlen 是 ziplist 原来的长度
    // reqlen 是整个新节点的长度
    // nextdiff 是新节点的后继节点扩展 header 的长度(要么 0 字节,要么 4 个字节)
    zl = ziplistResize(zl,curlen+reqlen+nextdiff);
    p = zl+offset;

    if (p[0] != ZIP_END) {
        // 移动现有元素,为新元素的插入空间腾出位置
        memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);

        // 后置节点 编码 前置节点长度
        zipPrevEncodeLength(p+reqlen,reqlen);

        // 更新到达表尾的偏移量,将新节点的长度也算上
        ZIPLIST_TAIL_OFFSET(zl) =
            intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);

        // 如果新节点的后面有多于一个节点
        // 那么程序需要将 nextdiff 记录的字节数也计算到表尾偏移量中
        // 这样才能让表尾偏移量正确对齐表尾节点
        tail = zipEntry(p+reqlen);
        if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
            ZIPLIST_TAIL_OFFSET(zl) =
                intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
        }
    } else {
        // 新元素是新的表尾节点
        ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
    }

    // 递归更新后置节点的前置节点长度
    if (nextdiff != 0) {
        offset = p-zl;
        zl = __ziplistCascadeUpdate(zl,p+reqlen);
        p = zl+offset;
    }

    // 写入三个值,分别是前置节点长度,自身长度和value
    p += zipPrevEncodeLength(p,prevlen);
    p += zipEncodeLength(p,encoding,slen);
    if (ZIP_IS_STR(encoding)) {
        memcpy(p,s,slen);
    } else {
        zipSaveInteger(p,value,encoding);
    }

    // 更新列表的节点数量计数器
    ZIPLIST_INCR_LENGTH(zl,1);

    return zl;
}

get entry by index

unsigned char *ziplistIndex(unsigned char *zl, int index) {
    unsigned char *p;
    zlentry entry;
    // 处理负数索引
    if (index < 0) {
        index = (-index)-1;
        // 定位到表尾节点
        p = ZIPLIST_ENTRY_TAIL(zl);
        if (p[0] != ZIP_END) {
            // 从表尾向表头遍历
            entry = zipEntry(p);
            while (entry.prevrawlen > 0 && index--) {
                // 前移指针
                p -= entry.prevrawlen;
                entry = zipEntry(p);
            }
        }
    // 处理正数索引
    } else {
        // 定位到表头节点
        p = ZIPLIST_ENTRY_HEAD(zl);
        while (p[0] != ZIP_END && index--) {
            // 后移指针
            p += zipRawEntryLength(p);
        }
    }
    // 返回结果
    return (p[0] == ZIP_END || index > 0) ? NULL : p;
}

next entry

unsigned char *ziplistNext(unsigned char *zl, unsigned char *p) {
    ((void) zl);
    // p 已经指向列表末端
    if (p[0] == ZIP_END) {
        return NULL;
    }
    // 指向后一节点
    p += zipRawEntryLength(p);
    if (p[0] == ZIP_END) {
        // p 已经是表尾节点,没有后置节点
        return NULL;
    }
    return p;
}

prev entry

unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p) {
    zlentry entry;
    // 表尾需要单独处理
    if (p[0] == ZIP_END) {
        p = ZIPLIST_ENTRY_TAIL(zl);
        // 尾端节点也指向列表末端,那么列表为空
        return (p[0] == ZIP_END) ? NULL : p;
    // 如果 p 指向列表头,那么说明迭代已经完成
    } else if (p == ZIPLIST_ENTRY_HEAD(zl)) {
        return NULL;
    // 既不是表头也不是表尾,从表尾向表头移动指针
    } else {
        // 计算前一个节点的节点数
        entry = zipEntry(p);
        assert(entry.prevrawlen > 0);
        // 移动指针,指向前一个节点
        return p-entry.prevrawlen;
    }
}

get value in entry

unsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval) {
    zlentry entry;
    if (p == NULL || p[0] == ZIP_END) return 0;
    if (sstr) *sstr = NULL;
    // 取出 p 所指向的节点的各项信息,并保存到结构 entry 中
    entry = zipEntry(p);
    // 节点的值为字符串,将字符串长度保存到 *slen ,字符串保存到 *sstr
    if (ZIP_IS_STR(entry.encoding)) {
        if (sstr) {
            *slen = entry.len;
            *sstr = p+entry.headersize;
        }
    // 节点的值为整数,解码值,并将值保存到 *sval
    } else {
        if (sval) {
            *sval = zipLoadInteger(p+entry.headersize,entry.encoding);
        }
    }
    return 1;
}

compare entry

unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen) {
    zlentry entry;
    unsigned char sencoding;
    long long zval, sval;
    if (p[0] == ZIP_END) return 0;
    // 取出节点
    entry = zipEntry(p);
    if (ZIP_IS_STR(entry.encoding)) {
        // 节点值为字符串,进行字符串对比
        if (entry.len == slen) {
            return memcmp(p+entry.headersize,sstr,slen) == 0;
        } else {
            return 0;
        }
    } else {
        // 节点值为整数,进行整数对比
        if (zipTryEncoding(sstr,slen,&sval,&sencoding)) {
          zval = zipLoadInteger(p+entry.headersize,entry.encoding);
          return zval == sval;
        }
    }
    return 0;
}

get entry by value

unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip) {
    int skipcnt = 0;
    unsigned char vencoding = 0;
    long long vll = 0;
    // 只要未到达列表末端,就一直迭代
    while (p[0] != ZIP_END) {
        unsigned int prevlensize, encoding, lensize, len;
        unsigned char *q;
        ZIP_DECODE_PREVLENSIZE(p, prevlensize);
        ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
        q = p + prevlensize + lensize;
        if (skipcnt == 0) {
            // 对比字符串值
            if (ZIP_IS_STR(encoding)) {
                if (len == vlen && memcmp(q, vstr, vlen) == 0) {
                    return p;
                }
            } else {
                // 因为传入值有可能被编码了,
                // 所以当第一次进行值对比时,程序会对传入值进行解码
                // 这个解码操作只会进行一次
                if (vencoding == 0) {
                    if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
                        vencoding = UCHAR_MAX;
                    }
                    assert(vencoding);
                }
                // 对比整数值
                if (vencoding != UCHAR_MAX) {
                    long long ll = zipLoadInteger(q, encoding);
                    if (ll == vll) {
                        return p;
                    }
                }
            }
            skipcnt = skip;
        } else {
            skipcnt--;
        }
        // 后移指针,指向后置节点
        p = q + len;
    }
    // 没有找到指定的节点
    return NULL;
}

热门文章

暂无图片
编程学习 ·

exe4j详细使用教程(附下载安装链接)

一、exe4j介绍 ​ exe4j是一个帮助你集成Java应用程序到Windows操作环境的java可执行文件生成工具&#xff0c;无论这些应用是用于服务器&#xff0c;还是图形用户界面&#xff08;GUI&#xff09;或命令行的应用程序。如果你想在任务管理器中及Windows XP分组的用户友好任务栏…
暂无图片
编程学习 ·

AUTOSAR从入门到精通100讲(126)-浅谈车载充电系统通信方案

01 引言 本文深入研究车载充电系统策略,设计出一套基于电动汽车电池管理系统与车载充电机的CAN通信协议,可供电动汽车设计人员参考借鉴。 02 电动汽车充电系统通讯网络 电动汽车整车控制系统中采用的是CAN总线通信方式,由一个整车内部高速CAN网络、内部低速CAN网络和一个充电…
暂无图片
编程学习 ·

CMake(九):生成器表达式

当运行CMake时&#xff0c;开发人员倾向于认为它是一个简单的步骤&#xff0c;需要读取项目的CMakeLists.txt文件&#xff0c;并生成相关的特定于生成器的项目文件集(例如Visual Studio解决方案和项目文件&#xff0c;Xcode项目&#xff0c;Unix Makefiles或Ninja输入文件)。然…
暂无图片
编程学习 ·

47.第十章 网络协议和管理配置 -- 网络配置(八)

4.3.3 route 命令 路由表管理命令 路由表主要构成: Destination: 目标网络ID,表示可以到达的目标网络ID,0.0.0.0/0 表示所有未知网络,又称为默认路由,优先级最低Genmask:目标网络对应的netmaskIface: 到达对应网络,应该从当前主机哪个网卡发送出来Gateway: 到达非直连的网络,…
暂无图片
编程学习 ·

元宇宙技术基础

请看图&#xff1a; 1、通过AR、VR等交互技术提升游戏的沉浸感 回顾游戏的发展历程&#xff0c;沉浸感的提升一直是技术突破的主要方向。从《愤怒的小鸟》到CSGO,游戏建模方式从2D到3D的提升使游戏中的物体呈现立体感。玩家在游戏中可以只有切换视角&#xff0c;进而提升沉浸…
暂无图片
编程学习 ·

flink的伪分布式搭建

一 flink的伪分布式搭建 1.1 执行架构图 1.Flink程序需要提交给 Job Client2.Job Client将作业提交给 Job Manager3.Job Manager负责协调资源分配和作业执行。 资源分配完成后&#xff0c;任务将提交给相应的 Task Manage。4.Task Manager启动一个线程以开始执行。Task Manage…
暂无图片
编程学习 ·

十进制正整数与二进制字符串的转换(C++)

Function one&#xff1a; //十进制数字转成二进制字符串 string Binary(int x) {string s "";while(x){if(x % 2 0) s 0 s;else s 1 s;x / 2;}return s; } Function two&#xff1a; //二进制字符串变为十进制数字 int Decimal(string s) {int num 0, …
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统&#xff1a; 微信小程序——辩论管理前台涉及技术&#xff1a;WXML 和 WXS…
暂无图片
编程学习 ·

树莓派驱动DHT11温湿度传感器

1&#xff0c;直接使用python库 代码如下 import RPi.GPIO as GPIO import dht11 import time import datetimeGPIO.setwarnings(True) GPIO.setmode(GPIO.BCM)instance dht11.DHT11(pin14)try:while True:result instance.read()if result.is_valid():print(ok)print(&quo…
暂无图片
编程学习 ·

ELK简介

ELK简介 ELK是三个开源软件的缩写&#xff0c;Elasticsearch、Logstash、Kibana。它们都是开源软件。不过现在还新增了一个 Beats&#xff0c;它是一个轻量级的日志收集处理工具(Agent)&#xff0c;Beats 占用资源少&#xff0c;适合于在各个服务器上搜集日志后传输给 Logstas…
暂无图片
编程学习 ·

Linux 基础

通常大数据框架都部署在 Linux 服务器上&#xff0c;所以需要具备一定的 Linux 知识。Linux 书籍当中比较著名的是 《鸟哥私房菜》系列&#xff0c;这个系列很全面也很经典。但如果你希望能够快速地入门&#xff0c;这里推荐《Linux 就该这么学》&#xff0c;其网站上有免费的电…
暂无图片
编程学习 ·

Windows2022 无线网卡装不上驱动

想来 Windows2022 和 windows10/11 的驱动应该差不多通用的&#xff0c;但是死活装不上呢&#xff1f; 搜一下&#xff0c;有人提到 “默认安装时‘无线LAN服务’是关闭的&#xff0c;如果需要开启&#xff0c;只需要在“添加角色和功能”中&#xff0c;选择开启“无线LAN服务…
暂无图片
编程学习 ·

【嵌入式面试宝典】版本控制工具Git常用命令总结

目录 创建仓库 查看信息 版本回退 版本检出 远程库 Git 创建仓库 git initgit add <file> 可反复多次使用&#xff0c;添加多个文件git commit -m <message> 查看信息 git status 仓库当前的状态git diff 差异对比git log 历史记录&#xff0c;提交日志--pret…
暂无图片
编程学习 ·

用Postman生成测试报告

newman newman是一款基于nodejs开发的可以运行postman脚本的工具&#xff0c;使用Newman&#xff0c;可以直接从命令运行和测试postman集合。 安装nodejs 下载地址&#xff1a;https://nodejs.org/en/download/ 选择自己系统相对应的版本内容进行下载&#xff0c;然后傻瓜式安…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…