quicklist是由ziplist构成的双向链表。ziplist需要可能对内存进行复制,在长度较长的时候,性能不佳。quicklist存储多个小ziplist,对除head
和tail
外的节点还进行了压缩,保证了push和pop性能的同时,又减少了内存的占用。
结构
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 typedef struct quicklistNode { struct quicklistNode *prev ; struct quicklistNode *next ; unsigned char *zl; unsigned int sz; unsigned int count : 16 ; unsigned int encoding : 2 ; unsigned int container : 2 ; unsigned int recompress : 1 ; unsigned int attempted_compress : 1 ; unsigned int extra : 10 ; } quicklistNode; typedef struct quicklistLZF { unsigned int sz; char compressed[]; } quicklistLZF; typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; unsigned long len; int fill : 16 ; unsigned int compress : 16 ; } quicklist;
quicklistLZF
:存储压缩后的ziplist
quicklist
: *
fill
:存放list-max-ziplist-size
参数 *
fill
取正值时,表示entry个数 * 取负值时,表示大小 *
compress
:存放list-compress-depth
参数
push
push时,先检查本次push是否会超过限制大小,quicklist->fill
,依次按照用户定义大小、默认个数(SIZE_SAFETY_LIMIT
)、用户定义个数检查。
* 如果没有超过,那么在head
的ziplist头部添加entry。 *
如果超过,那么创建新的ziplist,并在quicklist->head
前插入新node。最后压缩原来的quicklist->head
节点。
quicklistPushTail
也是类似的,但是在ziplist的尾部添加entry,且插入后是压缩原来的quicklist->tail
节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int quicklistPushHead (quicklist *quicklist, void *value, size_t sz) { quicklistNode *orig_head = quicklist->head; if (likely( _quicklistNodeAllowInsert(quicklist->head, quicklist->fill, sz))) { quicklist->head->zl = ziplistPush(quicklist->head->zl, value, sz, ZIPLIST_HEAD); quicklistNodeUpdateSz(quicklist->head); } else { quicklistNode *node = quicklistCreateNode(); node->zl = ziplistPush(ziplistNew(), value, sz, ZIPLIST_HEAD); quicklistNodeUpdateSz(node); _quicklistInsertNodeBefore(quicklist, quicklist->head, node); } quicklist->count++; quicklist->head->count++; return (orig_head != quicklist->head); }