ziplist, redis内部定义的双链表, 可实现t_hash, t_zset对象。
ziplist数据结构： 总长度(uint32_t) + 尾结点偏移量(uint32_t) + 结点数(uint16_t) + 键结点 + 值结点 + 键结点 + 值结点 + 结点等.... + 键结点 + 尾结点 + END(255).
结点数据结构：prevlensize(pre_encoding+前一个结点长度的字节数) + lensize(encodeing+len的字节数) + len(实际数据的字节数), 实现正向或反向查询
结点数一般 <= UINT16_MAX - 1, 否则只能循环所有结点，获得结点数.
查询时间复杂度 = o(n)
t_hash.c 查询
/* Get the value from a ziplist encoded hash, identified by field. * Returns -1 when the field cannot be found. */ int hashTypeGetFromZiplist(robj *o, robj *field, unsigned char **vstr, unsigned int *vlen, long long *vll) { unsigned char *zl, *fptr = NULL, *vptr = NULL; int ret; serverAssert(o->encoding == OBJ_ENCODING_ZIPLIST); field = getDecodedObject(field); zl = o->ptr; fptr = ziplistIndex(zl, ZIPLIST_HEAD); //从首结点查询 if (fptr != NULL) { fptr = ziplistFind(fptr, field->ptr, sdslen(field->ptr), 1); //找到键结点 if (fptr != NULL) { /* Grab pointer to the value (fptr points to the field) */ vptr = ziplistNext(zl, fptr); //找到值结点 serverAssert(vptr != NULL); } } decrRefCount(field); if (vptr != NULL) { ret = ziplistGet(vptr, vstr, vlen, vll); //通过值结点，获取相关数据(vstr或vll) serverAssert(ret); return 0; } return -1; }
ziplist.c实现ziplistFind(), 获取键对应的指针
/* 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. */ 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) { /* Compare current entry with specified entry */ if (ZIP_IS_STR(encoding)) { if (len == vlen && memcmp(q, vstr, vlen) == 0) { //如果是字符串，则字符比较 return p; } } else { /* Find out if the searched field can be encoded. Note that * we do it only the first time, once done vencoding is set * to non-zero and vll is set to the integer value. */ if (vencoding == 0) { if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) { /* If the entry can't be encoded we set it to * UCHAR_MAX so that we don't retry again the next * time. */ vencoding = UCHAR_MAX; } /* Must be non-zero by now */ assert(vencoding); } /* Compare current entry with specified entry, do it only * if vencoding != UCHAR_MAX because if there is no encoding * possible for the field it can't be a valid integer. */ if (vencoding != UCHAR_MAX) { long long ll = zipLoadInteger(q, encoding); if (ll == vll) { //数值比较 return p; } } } /* Reset skip count */ skipcnt = skip; } else { /* Skip entry */ skipcnt--; } /* Move to next entry */ p = q + len; } return NULL; }
t_zset.c 查询
unsigned char *zzlFind(unsigned char *zl, robj *ele, double *score) { unsigned char *eptr = ziplistIndex(zl,0), *sptr; //eptr: 头结点 ele = getDecodedObject(ele); while (eptr != NULL) { //循环查询 sptr = ziplistNext(zl,eptr); //数值对应的结点 serverAssertWithInfo(NULL,ele,sptr != NULL); if (ziplistCompare(eptr,ele->ptr,sdslen(ele->ptr))) { //比较键 /* Matching element, pull out score. */ if (score != NULL) *score = zzlGetScore(sptr); //获取积分数值 decrRefCount(ele); return eptr; //返回键结点指针 } /* Move to next element. */ eptr = ziplistNext(zl,sptr); //下一个键结点 } decrRefCount(ele); return NULL; }
t_hash.c 删除, 时间复杂度 = o(n) + o(m), //n = 结点数, m = 被删除的结点后续结点数(需要调整结构)
/* Delete an element from a hash. * Return 1 on deleted and 0 on not found. */ int hashTypeDelete(robj *o, robj *field) { int deleted = 0; if (o->encoding == OBJ_ENCODING_ZIPLIST) { unsigned char *zl, *fptr; field = getDecodedObject(field); zl = o->ptr; //ziplist fptr = ziplistIndex(zl, ZIPLIST_HEAD); //头结点 if (fptr != NULL) { fptr = ziplistFind(fptr, field->ptr, sdslen(field->ptr), 1); //找到field对应的键结点 if (fptr != NULL) { zl = ziplistDelete(zl,&fptr); //删除键结点 zl = ziplistDelete(zl,&fptr); //删除值结点 o->ptr = zl; deleted = 1; } } decrRefCount(field); } else if (o->encoding == OBJ_ENCODING_HT) { if (dictDelete((dict*)o->ptr, field) == C_OK) { deleted = 1; /* Always check if the dictionary needs a resize after a delete. */ if (htNeedsResize(o->ptr)) dictResize(o->ptr); } } else { serverPanic("Unknown hash encoding"); } return deleted; } /* Delete a single entry from the ziplist, pointed to by *p. * Also update *p in place, to be able to iterate over the * ziplist, while deleting entries. */ unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p) { size_t offset = *p-zl; zl = __ziplistDelete(zl,*p,1); //p结点后续结点调整结构(如果需要) /* Store pointer to current element in p, because ziplistDelete will * do a realloc which might result in a different "zl"-pointer. * When the delete direction is back to front, we might delete the last * entry and end up with "p" pointing to ZIP_END, so check this. */ *p = zl+offset; return zl; }
...