redis5.0源码浅析（六）-压缩列表
声明：本文中的注解 zltail ,zlend都是参照 《Redis设计与实现》的结构命名，并且理解本文章的前提 也是 理解 书中压缩列表部分。
本文主要分析 初始化方法和插入方法
//获取prevlensize值
//根据ptr[0]获取 prevlensize值，如果 ptr[0]<254,prevlensize=1字节 否则 prevlensize=4字节
#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do { \
if ((ptr)[0] < ZIP_BIG_PREVLEN) { \
(prevlensize) = 1; \
} else { \
(prevlensize) = 5; \
} \
} while(0);
//zip 的数据类型是 char *
/* Create a new empty ziplist. */
//初始化压缩列表结构，没有初始化 entryx部分
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;
}
/* Return total bytes a ziplist is composed of. */
//获取zlbytes指针
#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl))) // 什么用法？
/* Return the offset of the last item inside the ziplist. */
//获取zltail指针
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
/* Return the length of a ziplist, or UINT16_MAX if the length cannot be
* determined without scanning the whole ziplist. */
//获取zllen指针
#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))
__ziplistInsert是ziplist中最复杂的方法 ，流程图如下
prevlen表示记录前一个节点长度,prevlensize表示prevlen占用的字节数,encoding 表示编码
/* Insert item at "p". */
//插入的位置 是 找到一个 entry 开始位置
unsigned char *__ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen) {
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. */
//找出前一个entry的字节长度prevlen，记录prevlen的字节长度prevlensize
if (p[0] != ZIP_END) {
//如果p的位置不是尾部，即在头部或在中间位置。通过 prevlen的规则获取 prevlen
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
} else {
//如果是尾部 就要借助 zltail来获取prevlen
unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl);
if (ptail[0] != ZIP_END) {
prevlen = zipRawEntryLength(ptail);
}
}
//获取数据体长度
/* See if the entry can be encoded */
//检查 s是否可以编码成整数，不同大小的整数使用定长字节数存储,如果可以求出 value和encoding值
//如果不可以，value和encoding为初始值
if (zipTryEncoding(s,slen,&value,&encoding)) {
/* 'encoding' is set to the appropriate integer encoding */
reqlen = zipIntSize(encoding);
} else {
//不能编码成整理，使用s 的长度 slen
/* '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. */
//获取prevlensize和encoding长度，计算要写入的entry总字节长度
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. */
//计算预留字节数，方便以后判断是否执行连锁升级
//由于新插入的entry 可能长度较大 导致它后面的entry中的previous_entry_length存不下，需要升级。算出预留字节数。
int forcelarge = 0;
nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0;
//当插入的entry总字节数较小时，可能出现负值。
if (nextdiff == -4 && reqlen < 4) {
nextdiff = 0;
forcelarge = 1;
}
//扩展内存空间
//只有当插入的entry总字节数较大时，而旧的previous_entry_length字节数为1，出现正值。值为4
/* Store offset because a realloc may change the address of zl. */
//记录位移 因为 执行realloc后zl地址可能会改变
offset = p-zl;//为何要减？ p-zl是 p所在的偏移值
//扩展内存
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 */？？
//移动内存 空出位置
// p-nextdiff 多移动nextdiff长度, 多出的nextdiff字节脏数据后面会掉 ， 而且不需要移动 zlend，并单独处理 zlend， 减1 不移动 zlend.
memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff);
/* Encode this entry's raw length in the next entry. */
//存储 prevlen
if (forcelarge)
//5字节存储 prevlen
zipStorePrevEntryLengthLarge(p+reqlen,reqlen);
else
//1字节存储prevlen
zipStorePrevEntryLength(p+reqlen,reqlen);
/* Update offset for tail */
//修改zltail值
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen);
/* When the tail contains more than one entry, we need to take
* "nextdiff" in account as well. Otherwise, a change in the
* size of prevlen doesn't have an effect on the *tail* offset. */
//当 p+reqlen 位置后面的entry多余一个的时，我们需要将 nextdiff 记录在zltail中
//zipEntry获取新加入的entry后一个entry的属性
zipEntry(p+reqlen, &tail);
//如果不是最后一个entry, 需要将 nextdiff 记录在zltail中
if (p[reqlen+tail.headersize+tail.len] != ZIP_END) {
ZIPLIST_TAIL_OFFSET(zl) =
intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+nextdiff);
}
} else {
/* This element will be the new tail. */
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(p-zl);
}
/* When nextdiff != 0, the raw length of the next entry has changed, so
* we need to cascade the update throughout the ziplist */
//连锁更新
if (nextdiff != 0) {
offset = p-zl;
zl = __ziplistCascadeUpdate(zl,p+reqlen);
p = zl+offset;
}
/* Write the entry */
//写入要插入的entry的prevlen和encoding
p += zipStorePrevEntryLength(p,prevlen);
p += zipStoreEntryEncoding(p,encoding,slen);
//存储数据体
//string 和int 两种方式存储
if (ZIP_IS_STR(encoding)) {
memcpy(p,s,slen);
} else {
//用不同的编码存储value
//此时为整数编码，长度等于1字节.指针移动到content位置
zipSaveInteger(p,value,encoding);
}
//节点数加1
ZIPLIST_INCR_LENGTH(zl,1);
return zl;
}
//计算当前的prevlen字节数 与插入后需要的prevlen字节数差值。
int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
unsigned int prevlensize;
//获取p位置prevlen 的字节数
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
//使用len获取需要的prevlen字节数减去当前的 prevlen字节数。
return zipStorePrevEntryLength(NULL, len) - prevlensize;
}
//检查是否可以把字符串转化成整数， 可以则记录整数值和编码。
int zipTryEncoding(unsigned char *entry, unsigned int entrylen, long long *v, unsigned char *encoding) {
long long value;
if (entrylen >= 32 || entrylen == 0) return 0;
//如果 entry所有的字符都可以转成 longLong类型，转成longlong 类型赋值给value
if (string2ll((char*)entry,entrylen,&value)) {
/* Great, the string can be encoded. Check what's the smallest
* of our encoding types that can hold this 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;
}
/* Encode the length of the previous entry and write it to "p". Return the
* number of bytes needed to encode this length if "p" is NULL. */
//如果 p==NULL, 返回 存储 len 的PrevEntryLength字节长度。
//如果 p！=NULL 编码并写入len
unsigned int zipStorePrevEntryLength(unsigned char *p, unsigned int len) {
if (p == NULL) {
return (len < ZIP_BIG_PREVLEN) ? 1 : sizeof(len)+1;
} else {
//使用一个字节，不需要加前缀
if (len < ZIP_BIG_PREVLEN) {
p[0] = len;
return 1;
} else {
//使用5个字节需要加前缀
return zipStorePrevEntryLengthLarge(p,len);
}
}
}
// 加前缀5字节方式存储 前缀为 254即 FE
int zipStorePrevEntryLengthLarge(unsigned char *p, unsigned int len) {
if (p != NULL) {
p[0] = ZIP_BIG_PREVLEN;
memcpy(p+1,&len,sizeof(len));
memrev32ifbe(p+1);
}
return 1+sizeof(len);
}
//encoding记录了节点数据类型和长度
//如果*p ==null获取 encoding长度 单位：字节。
/如果*p !=null, 写入 节点数据类型和长度
unsigned int zipStoreEntryEncoding(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
unsigned char len = 1, buf[5];
//如果不是字符串 编码长度为1，如果是字符串编码长度 可能是 1,2,5其中之一。
//当写入字符调用这段代码encoding=0。可以命中字符串规则
if (ZIP_IS_STR(encoding)) {
/* Although encoding is given it may not be set for strings,
* so we determine it here using the raw length. */
//此部分存储 encode的算法 要结合 内联函数 ZIP_DECODE_LENGTH来理解
//根据rawlen 判断encode字节长度当字节数为1时 直接存储， 当字节数为2或5时 拆开存储
//0x3f =63 二进制 00111111
if (rawlen <= 0x3f) {
if (!p) return len;
//ZIP_STR_06B=0 二进制 0000 0000
//使用buf[0]的后6位存储数据长度。
buf[0] = ZIP_STR_06B | rawlen;// 假设rawlen=63, buf[0]=00111111 =63
//0x3fff=16383 二进制 0011 1111 1111 1111
} else if (rawlen <= 0x3fff) {
len += 1;
if (!p) return len;
//ZIP_STR_14B=64 二进制 0100 0000 0000 0000
// 使用buf[0]的后6位存储和buf[1]的8为存储数据长度
buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);// 假设rawlen=16383,buf[0]=00111111 =63
buf[1] = rawlen & 0xff;// 假设rawlen=63, buf[1]=11111111 =255
} else {
len += 4;
if (!p) return len;
//ZIP_STR_32B=128 二进制 10000000
//使用4个字节长度存储 数据长度
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 {
/* Implies integer encoding, so length is always 1. */
if (!p) return len;
buf[0] = encoding;
}
//因为ZIP_STR_MASK的最高位为11, (enc) & ZIP_STR_MASK< ZIP_STR_MASK成立的情况下 enc最高位一定小于11
#define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK)
//ZIP_STR_MASK 的值 是 0Xc0 2进制为 1100 0000
//规定 字符串encode最高位为 00，01，10
//ptr[0]是encode的第一个字节， ptr[0]中后6位可能保存了数据长度高位，&是为了抹除后6位的影响。
#define ZIP_ENTRY_ENCODING(ptr, encoding) do { \
(encoding) = (ptr[0]); \
if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
} while(0)
//解析encoding部分各属性，获取记录节点数据部分长度的字节数 lensize,获取节点数据长度的字节数 len,编码类型encoding
#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do { \
ZIP_ENTRY_ENCODING((ptr), (encoding));
//返回的 encoding 值是 0000 0000，1000 0000，0100 0000 ，1100 0000的其中之一
//因为规定 字符串encode最高位为 00，01，10。此处encoding 小于 1100 0000的就是字符串类型 \
if ((encoding) < ZIP_STR_MASK) {
\
//ZIP_STR_06B 二进制 0000 0000
if ((encoding) == ZIP_STR_06B) { \
(lensize) = 1;
//取出1字节中低6位代表的值 \
(len) = (ptr)[0] & 0x3f;
//ZIP_STR_14B 二进制 0100 0000 \
} else if ((encoding) == ZIP_STR_14B) { \
(lensize) = 2;
//取出第一个字节中低6，和第二个字节的8位组合的值。这里 | 代表组合第二个字节 \
(len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1]; \
//ZIP_STR_14B 二进制 1000 0000
} else if ((encoding) == ZIP_STR_32B) { \
(lensize) = 5;
//左移一位低位 补0，右移高位补0
\
//下面这么写相当于拼接4个部分
//prt[1]原来是1个字节占8位，左移24位相当于int型的前8位
(len) = ((ptr)[1] << 24) | \
((ptr)[2] << 16) | \
((ptr)[3] << 8) | \
((ptr)[4]); \
} else { \
panic("Invalid string encoding 0x%02X", (encoding)); \
} \
} else { \
(lensize) = 1; \
(len) = zipIntSize(encoding); \
} \
} while(0);
/* Return bytes needed to store integer encoded by 'encoding'. */
//根据encoding返回存储整数需要的字节数
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;
}
if (encoding >= ZIP_INT_IMM_MIN && encoding <= ZIP_INT_IMM_MAX)
return 0; /* 4 bit immediate */
panic("Invalid integer encoding 0x%02X", encoding);
return 0;
}
/* Return the offset of the last item inside the ziplist. */
//这段代码 如果作为值时使用，获取了 zltail的值。 如果 作为 被赋值的公式（左值）使用，则更新了 zltail的值
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))
#define ZIP_STR_MASK 0xc0 //二进制 11000000
//比较ziplist中指针 p和sstr长度为slen的实例数据是否相同。
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;
zipEntry(p, &entry);
if (ZIP_IS_STR(entry.encoding)) {
/* Raw compare */
if (entry.len == slen) {
return memcmp(p+entry.headersize,sstr,slen) == 0;
} else {
return 0;
}
} else {
/* Try to compare encoded values. Don't compare encoding because
* different implementations may encoded integers differently. */
if (zipTryEncoding(sstr,slen,&sval,&sencoding)) {
zval = zipLoadInteger(p+entry.headersize,entry.encoding);
return zval == sval;
}
}
return 0;
}
//计算ziplist zentrys中索引值为index的指针地址。当index值为0，返回第一个节点， 一个节点都没有返回NULL
// index>=0 从头部查找，index<0 从尾部查找
unsigned char *ziplistIndex(unsigned char *zl, int index) {
unsigned char *p;
unsigned int prevlensize, prevlen = 0;
if (index < 0) {
index = (-index)-1;
p = ZIPLIST_ENTRY_TAIL(zl);
if (p[0] != ZIP_END) {
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
while (prevlen > 0 && index--) {
p -= prevlen;
ZIP_DECODE_PREVLEN(p, prevlensize, prevlen);
}
}
} else {
p = ZIPLIST_ENTRY_HEAD(zl);
while (p[0] != ZIP_END && index--) {
p += zipRawEntryLength(p);
}
}
return (p[0] == ZIP_END || index > 0) ? NULL : p;
}
/* Find pointer to the entry equal to the specified entry. Skip 'skip' entries
* between every comparison. Returns NULL when the field could not be found. */
//查找指定 *vstr的节点开始位置指针
//从p 开始查找指定 *vstr的节点开始位置指针，如果找不到返回NULL（p必须是某个数据节点开始位置）
//skip用于跳过 ziplist中 键值对 的值 节点。当skip=1时，用于在哈希表中查找key是否存在
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr, unsigned int vlen, unsigned int skip)
hash实现中 ziplistIndex和ziplistFind常常组合使用，先从头部位置找到第一个节点，然后 从第一个节点查找 数据是field的节点
fptr = ziplistIndex(zl, ZIPLIST_HEAD);
fptr = ziplistFind(fptr, (unsigned char*)field, sdslen(field), 1);
/* Return the total number of bytes used by the entry pointed to by 'p'. */
//p指向节点开始位置，获取该节点的全部长度。
unsigned int zipRawEntryLength(unsigned char *p) {
//prevlensize
unsigned int prevlensize, encoding, lensize, len;
//根据[0]获取prevlensize长度
ZIP_DECODE_PREVLENSIZE(p, prevlensize);
//获取encoding, lensize, len
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
return prevlensize + lensize + len;
}