redis源码分析教程之压缩链表ziplist详解

//由元素2，5组成的压缩链表[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] |  |  | | | | zlbytes zltail entries "2" "5" end//字符串"Hello World"编码后的内容[02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]

[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [02 0b 48 65 6c 6c 6f 20 57 6f 72 6c 64] [ff] |  |  | | |   |   | zlbytes zltail entries "2" "5"   "Hello World"  end

//定义由zlbytes，zltail跟zllen组成的压缩链表的头大小#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))//创建一个压缩链表，并且返回指向该链表的指针unsigned char *ziplistNew(void) { //这里之所以+1是因为尾元素占用一个字节，这也是一个压缩链表最小尺寸 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;}

//四个参数依次是：压缩链表，插入位置（新元素插入p元素后面），元素值，元素长度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; zlentry tail; //1. 这段逻辑目的就是获取前置元素的长度 if (p[0] != ZIP_END) { //如果插入位置的元素不是尾元素,则获取该元素的长度 //这里为了后面使用方便进行了拆分，prevlensize保存encoding字段的长度，prevlen保存元素本身的长度 ZIP_DECODE_PREVLEN(p, prevlensize, prevlen); } else { //如果插入位置的元素是尾元素，那么需要把新元素插入链表尾端 //获取到链表最后一个元素（注：最后一个元素不等于尾元素） unsigned char *ptail = ZIPLIST_ENTRY_TAIL(zl); if (ptail[0] != ZIP_END) {  //如果最后一个元素不是尾元素，则该元素为新元素的前置元素，获取该元素长度  prevlen = zipRawEntryLength(ptail); } //否则说明链表还没有任何元素，即新元素的前置元素长度为0 } //2. 对新元素进行编码，获取新元素的总大小 if (zipTryEncoding(s,slen,&value,&encoding)) { //如果是数字，则按数字进行编码 reqlen = zipIntSize(encoding); } else { //元素长度即为字符串长度 reqlen = slen; } //新元素总长度为值的长度加上前置元素跟encoding元素的长度 reqlen += zipStorePrevEntryLength(NULL,prevlen); reqlen += zipStoreEntryEncoding(NULL,encoding,slen); //如果插入的位置不是链表尾，则要对新元素的后续元素的prevlen字段进行判断 //根据上面的编码规则，该字段可能需要扩容 int forcelarge = 0; nextdiff = (p[0] != ZIP_END) ? zipPrevLenByteDiff(p,reqlen) : 0; if (nextdiff == -4 && reqlen < 4) { nextdiff = 0; forcelarge = 1; } //按照新计算出的数组大小进行扩容，由于新数组的地址可能会改变，因此这里记录旧的偏移量 offset = p-zl; zl = ziplistResize(zl,curlen+reqlen+nextdiff); //在新数组上计算插入位置 p = zl+offset; //如果新插入的元素不是在链表末尾 if (p[0] != ZIP_END) { //把新元素后继元素复制到新的数组中，-1为尾元素 memmove(p+reqlen,p-nextdiff,curlen-offset-1+nextdiff); //新元素的后继元素的prevlen字段 if (forcelarge)  zipStorePrevEntryLengthLarge(p+reqlen,reqlen); else  zipStorePrevEntryLength(p+reqlen,reqlen); //更新最后一个元素的偏移量 ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))+reqlen); //当新元素的后继元素不止有一个时，新的尾元素偏移量需要加上nextdiff zipEntry(p+reqlen, &tail); 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); } //nextdiff !=0表示后继元素的长度发生变化，因此我们需要级联更新后继元素的后继元素 if (nextdiff != 0) { offset = p-zl; zl = __ziplistCascadeUpdate(zl,p+reqlen); p = zl+offset; } //把新元素写入链表 p += zipStorePrevEntryLength(p,prevlen); p += zipStoreEntryEncoding(p,encoding,slen); if (ZIP_IS_STR(encoding)) { memcpy(p,s,slen); } else { zipSaveInteger(p,value,encoding); } //压缩链表存储元素数量+1 ZIPLIST_INCR_LENGTH(zl,1); return zl;}

//参数依次为：压缩链表，删除元素的其实位置，删除元素的个数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; //读取p指向的元素保存在first中 zipEntry(p, &first); for (i = 0; p[0] != ZIP_END && i < num; i++) {  //统计总共删除的长度  p += zipRawEntryLength(p);  //统计实际删除元素的个数  deleted++; } //需要删除元素的字节数 totlen = p-first.p; if (totlen > 0) {  if (p[0] != ZIP_END) {   //判断元素大小是否有改变   nextdiff = zipPrevLenByteDiff(p,first.prevrawlen);   //修改删除元素之后的元素的prevlen字段   p -= nextdiff;   zipStorePrevEntryLength(p,first.prevrawlen);   //更新末尾元素的偏移量   ZIPLIST_TAIL_OFFSET(zl) =intrev32ifbe(intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))-totlen);   //当删除元素的后继元素不止有一个时，新的末尾元素偏移量需要加上nextdiff   zipEntry(p, &tail);   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);  }  //resize数组大小  offset = first.p-zl;  zl = ziplistResize(zl, intrev32ifbe(ZIPLIST_BYTES(zl))-totlen+nextdiff);  //修改链表元素个数  ZIPLIST_INCR_LENGTH(zl,-deleted);  p = zl+offset;  //nextdiff != 0表示元素大小发生变化，需要进行级联更新  if (nextdiff != 0)   zl = __ziplistCascadeUpdate(zl,p); } return zl;}

//参数依次为：压缩链表，要查找元素的值，要查找元素的长度，每次比较之间跳过的元素个数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;  //查询链表当前元素的prevlen字段  ZIP_DECODE_PREVLENSIZE(p, prevlensize);  //查询链表当前元素的encoding字段  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 {    //如果当前元素为数字且vencoding为0    if (vencoding == 0) {     //尝试对要查找的值进行数字编码     if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {      //如果编码失败，则说明要查找的元素根本不是数字      //然后把vencoding设置为最大值，起一个标记作用      //也就是说后面就不用尝试把要查找的值编码成数字了      vencoding = UCHAR_MAX;     }     assert(vencoding);    }    //如果vencoding != UCHAR_MAX，则说明要查找的元素成功编码为数字    if (vencoding != UCHAR_MAX) {     //按数字取出当前链表中的元素     long long ll = zipLoadInteger(q, encoding);     if (ll == vll) {      //如果两个数字相等，则返回元素指针      return p;     }    }   }   //重置需要跳过的元素个数   skipcnt = skip;  } else {   //跳过元素   skipcnt--;  }  //遍历下个元素  p = q + len; } //遍历完整个链表，没有找到元素 return NULL;}