zl

zl

关注
发信
关注(28)粉丝(399)

redis 压缩链表

redis 压缩链表

概述

压缩链表结构

<zlbytes> <zltail> <zllen> <entry1> <entry2> .. <entryN> <zlend>
zlbytes压缩链表占用的内存总字节数可以直接对内存大小进行调整, 无需遍历整个链表获取大小32 位#define ZIPLIST_BYTES(zl) (*((uint32_t *)(zl)))
zltail压缩链表尾节点的偏移量长度 1 字节, 0xFF; pop 操作无需遍历整个链表32 位#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t *)((zl)+sizeof(uint32_t))))
zllen压缩链表存储的节点总数zllen 大于 2^16 - 2 时, 需要遍历整个链表来获取长度16 位#define ZIPLIST_LENGTH(zl) (*((uint16_t *)((zl)+sizeof(uint32_t) * 2)))
entryN节点
zlend压缩链表结束符0xFF8 位#define ZIP_END 255

  • entryN

    • header 头部

      • 前置节点编码规则 (前置节点的长度, 从后向前遍历时用)

        如果前置节点长度小于 ZIP_BEGIN 字节(254), 则使用 1 个字节表示长度
        
如果前置节点大于等于 ZIP_BEGIN 字节(254), 则使用 5 个字节表示长度
        
	a) 第 1 个字节为 ZIP_BEGIN, 表示这是一个 5 字节长度
        
	b) 之后的 4 个字节表示长度

      • 当前节点编码规则 (当前节点的长度)

        整数

        1100 0000表示 2 字节长度0xc0 位或 0<<4
        1101 0000表示 4 字节长度0xc0 位或 1<<4
        1110 0000表示 8 字节长度0xc0 位或 2<<4
        1111 0000表示 3 字节长度0xc0 位或 3<<4
        1111 1110表示 1 字节长度0xfe
        1111 xxxx (除去 0000, 1111)表示 (xxxx - 1) 位长度
        1111 1111压缩链表结束符

        字符串

        00pp pppp1字节, 表示字符串长度小于等于 2^6 -1前 2 位不用来表示长度
        01pp pppp qqqq qqqq2字节, 表示字符串长度小于等于 2^14 - 1前 2 位不用来表示长度
        10pp pppp qqqq qqqq ...5字节, 表示字符串长度大于等于 2^14前 2 位不用来表示长度

    • body 数据部分

      // ziplist 节点信息的结构
      
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;
      注意
      ziplist 对于长度的存储编码, 当要使用长度的时候对长度进行解码, 放于 entry 实体的 prevrawlen 与 len 均为实际的长度值, prevrawlensize 与 lensize 为对实际长度进行编码所占的字节数

ziplist 宏定义 (src/ziplist.c)

ZIP_END压缩链表尾部标识#define ZIP_END 255
ZIP_BEGIN前置节点使用 5 字节表示长度的标识符#define ZIP_BIGLEN 254
ZIP_STR_MASK字符串类型的掩码#define ZIP_STR_MASK 0xc0
ZIP_INT_MASK整数类型的掩码#define ZIP_INT_MASK 0x30
ZIP_STR_06B字符串编码类型#define ZIP_STR_06B (0 << 6)
ZIP_STR_14B字符串编码类型#define ZIP_STR_14B (1 << 6)
ZIP_STR_32B字符串编码类型#define ZIP_STR_32B (2 << 6)
ZIP_INT_16B整数编码类型 (2字节)#define ZIP_INT_16B (0xc0 位或 0<<4)
ZIP_INT_32B整数编码类型 (4字节)#define ZIP_INT_32B (0xc0 位或 1<<4)
ZIP_INT_64B整数编码类型 (8字节)#define ZIP_INT_64B (0xc0 位或 2<<4)
ZIP_INT_24B整数编码类型 (3字节)#define ZIP_INT_24B (0xc0 位或 3<<4)
ZIP_INT_8B整数编码类型 (1字节)#define ZIP_INT_8B 0xfe
ZIP_INI_IMM_MASK对于 1111 xxxx 后4位表示编码类型的整数掩码#define ZIP_INT_IMM_MASK 0x0f
ZIP_INI_IMM_MIN4位整数编码的最小值#define ZIP_INT_IMM_MIN 0xf1
ZIP_INI_IMM_MAX4位整数编码的最大值#define ZIP_INT_IMM_MAX 0xfd
ZIP_INI_IMM_VAL计算4位整数编码#define ZIP_INT_IMM_VAL(v) (v & ZIP_INT_IMM_MASK)
INT24_MAX24位整数编码的最大值#define INT24_MAX 0x7fffff
INT24_MIN24位整数编码的最小值#define INT24_MIN (-INT24_MAX - 1)
ZIP_IS_STR查看指定编码是否是字符串编码#define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK)
ZIPLIST_BYTES获取压缩链表的 zlbytes 值#define ZIPLIST_BYTES(zl) (*((uint32_t *)(zl)))
ZIPLIST_TAIL_OFFSET获取压缩链表的 zltail 值#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t *)((zl)+sizeof(uint32_t))))
ZIPLIST_LENGTH获取压缩链表的 zllen 值#define ZIPLIST_LENGTH(zl) (*((uint16_t *)((zl)+sizeof(uint32_t) * 2)))
ZIPLIST_HEADER_SIZE压缩链表表头的大小#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
ZIPLIST_ENTRY_HEAD压缩链表头节点指针#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)
ZIPLIST_ENTRY_TAIL压缩链表尾节点指针#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
ZIPLIST_ENTRY_END压缩链表末端 zlend 的指针#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)
ZIPLIST_INCR_LENGTH增加压缩链表的 zlen 的值, 增加幅度为 incr#define ZIPLIST_INCR_LENGTH(zl,incr)
ZIP_ENTRY_ENCODING从 ptr 中获取编码类型, 并将其存入 encoding#define ZIP_ENTRY_ENCODING(ptr, encoding)
ZIP_DECODE_LENGTH从 ptr 中获取 encoding, lensize, len#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len)
ZIP_DECODE_PREVLENSIZE解码 ptr, 设置 prevlensize 的值#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize)
ZIP_DECODE_PREVLEN解码 ptr, 设置 prevlensize, prevlen#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen)

ziplist api (src/ziplist.c)

zipIntSize保存 encoding 所需的字节数 (仅针对整数编码类型)static unsigned int zipIntSize(unsigned char encoding)
zipEncodeLength将长度 rawlen 按照 encoding 进行编码, 并存到指针 p 中static unsigned int zipEncodeLength(unsigned char *p, unsigned char encoding, unsigned int rawlen)
zipPrevEncodeLength编码前置节点 len, 存入节点指针 pstatic unsigned int zipPrevEncodeLength(unsigned char *p, unsigned int len)
zipPrevEncodeLengthForceLarge编码前置节点 len 用 5 个字节存储, 存入节点指针 pstatic void zipPrevEncodeLengthForceLarge(unsigned char *p, unsigned int len)
zipPrevLenByteDiff计算编码 len 所需的字节数, 与原 p 中存储的 prevlensize 进行减法static int zipPrevLenByteDiff(unsigned char *p, unsigned int len)
zipRawEntryLength返回节点所占用的字节数static unsigned int zipRawEntryLength(unsigned char *p)
zipTryEncoding尝试将字符串转换为整数, 若转换成功, 存储到 v, 并将编码方式存储到 encodingstatic int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding)
zipSaveInteger以 encoding 指定的编码方式, 将整数值 value 写入到 pstatic void zipSaveInteger(unsigned char *p, int64_t value, unsigned char encoding)
zipLoadInteger以 encoding 指定的编码方式, 读取并返回 p 中的整数值static int64_t zipLoadInteger(unsigned char *p, unsigned char encoding)
zipEntry获取指定指针 p 的节点static zlentry zipEntry(unsigned char *p)
ziplistNew创建并返回一个新的 ziplistunsigned char *ziplistNew(void)
ziplistResize调整 ziplist 到指定的 len 长度static unsigned char *ziplistResize(unsigned char *zl, unsigned int len)
__ziplistCascadeUpdate当一个节点添加到某个节点之前时, 有可能相应节点的 header 空间不足够, 为了处理由此产生的迭代更新; 对于长度变小的收缩情况不做考虑static unsigned char *__ziplistCascadeUpdate(unsigned char *zl, unsigned char *p)
__ziplistDelete在 zl 中, 从指定位置 p 开始, 连续删除 num 个节点static unsigned char *__ziplistDelete(unsigned char *zl, unsigned char *p, unsigned int num)
__ziplistInsert将字符串 s 插入到 zl 的指定位置 pstatic unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen)
ziplistPush向 zl 头部或尾部压入字符串 sunsigned char *ziplistPush(unsigned char *zl, unsigned char *s, unsigned int slen, int where)
ziplistIndex根据给定的 index, 获取 zl 节点unsigned char *ziplistIndex(unsigned char *zl, int index)
ziplistNext返回给定节点 p 的下个节点unsigned char *ziplistNext(unsigned char *zl, unsigned char *p)
ziplistPrev返回给定节点 p 的前置节点unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p)
ziplistGet获取指定节点 p 的值, 若是字符串, 字符串指针存储在 *sstr, 字符串长度存储在 *slen; 若是整数, 将值存储在 *svalunsigned int ziplistGet(unsigned char *p, unsigned char **sstr, unsigned int *slen, long long *sval)
ziplistInsert将字符串 s 插入到 zl 的指定位置 punsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen)
ziplistDelete删除 zl 中指定位置 p 的节点, 并更新 punsigned char *ziplistDelete(unsigned char *zl, unsigned char **p)
ziplistDeleteRange删除 zl 中从 index 开始, 连续 num 个节点unsigned char *ziplistDeleteRange(unsigned char *zl, unsigned int index, unsigned int num)
ziplistCompare将 p 所指向的节点值与给定的字符串 sstr 进行比较, 相等返回1, 不相等返回0unsigned int ziplistCompare(unsigned char *p, unsigned char *sstr, unsigned int slen)
ziplistFind从指定节点 p 开始, 每次跳过 skip 个节点, 将节点值与字符串 vstr 比较, 找到相等的节点, 返回unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip)
ziplistLen返回 zl 的节点数, 若节点数小于 2^16 - 2 时, 直接取 zllen, 若大于此值, 则进行遍历计算长度unsigned int ziplistLen(unsigned char *zl)
ziplistBlobLen返回 zl 占用的字节总数 zlbytessize_t ziplistBlobLen(unsigned char *zl)
ziplistRepr打印 zl 的一些信息 (zlbytes, zllen, zltail, entryN)void ziplistRepr(unsigned char *zl)
05-02 08:56
Powered by LMLPHP ©2024 zl 0.089383