说实话，当我看见这两个文件的时候，内心深处的想法是崩溃的（哦谢特麻惹法克），你说你一个redis搞那么多list干啥。。。但是当我看到它的注释的时候，心里稍微好受了一点
|
1 2 |
/* quicklist.c - A doubly linked list of ziplists */ |
真香！！！貌似这东西是一个双向链表，而链表的每个元素就是之前介绍过的ziplist，这样梳理一下，貌似一个东西刚刚讲过，还热乎，另一个是常规双向链表，有搞头了，嘿嘿嘿~~~
目前来讲的话这边提供了五中数据结构quicklistNode, quicklistLZF, quicklist,quicklistIter, quicklistEntry，它们的具体定义以及说明如下：
quicklistNode
|
1 2 3 4 5 6 7 8 9 10 11 12 |
typedef struct quicklistNode { struct quicklistNode *prev; struct quicklistNode *next; unsigned char *zl; unsigned int sz; /* 未被压缩的情况下：ziplist size in bytes */ unsigned int count : 16; /* count of items in ziplist */ unsigned int encoding : 2; /* RAW==1 or LZF==2 */ unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */ unsigned int recompress : 1; /* was this node previous compressed? */ unsigned int attempted_compress : 1; /* node can't compress; too small */ unsigned int extra : 10; /* more bits to steal for future usage */ } quicklistNode; |
struct quicklistNode共占用32字节，定义中可以明确地看到使用了bit fields这种东西，字段当中：
字段 描述
count:16 ziplist当中的items
encoding:2 这里需要注意的是quicklist会使用一种名叫LZF的压缩算法来对ziplist压缩，如果压缩，该字段值为2；如果不压缩，该字段值为1。算法的具体实现见lzf的3个文件(lzf.h,lzf_c.c, lzf_d.c)。
container 存放数据的容器：1位NONE；2位ziplist，现阶段应该都是这个。
recompress:1 表示该节点是否为临时解压，若是，稍后会被压缩回去
attempted_compress:1 节点太小，不能被压缩
extra:10 保留当整个节点没有被LZF压缩的时候，quicklistNode当中的zl会指向一个ziplist，但是，当该节点压缩之后，quicklistNode当中的zl会指向一个quicklistLZF结构体，其中的sz保存压缩后的字节数：
|
1 2 3 4 |
typedef struct quicklistLZF { unsigned int sz; /* LZF size in bytes*/ char compressed[]; } quicklistLZF; |
quicklist是一个40字节的结构体，其结构如下，其中各个字段的值如代码中所示
|
1 2 3 4 5 6 7 8 9 10 |
typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; /* total count of all entries in all ziplists */ unsigned long len; /* number of quicklistNodes */ int fill : 16; /* 每一个节点中最多包含的元素个数-5到0xFFFF */ unsigned int compress : 16; /* depth of end nodes not to compress;0=off */ } quicklist; /* Optimization levels for size-based filling */ static const size_t optimization_level[] = {4096, 8192, 16384, 32768, 65536}; |
其中需要多说一下的字段是fill和compress，链表会根据fill字段的值来决定每个节点当中存放的元素个数，会参照上面的optimization_level的数组
| fill值 | 描述 |
| 整数m | 每个节点上的ziplist最多包含m个数据项 |
| n = [-5,-1] | 根据(-n)-1的值来确定下标，取下标对应的optimization_level数组中的元素来当做最大的数据项，默认值为-2 |
而compress字段表示当前quicklist当中两端各有多少个节点不压缩，若取0，则表示整个链表不压缩；若取2，则两端各有2个节点不进行压缩。
剩下的就是quicklistIter和quicklistEntry了，代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
typedef struct quicklistIter { const quicklist *quicklist; quicklistNode *current; unsigned char *zi; long offset; /* offset in current ziplist */ int direction; } quicklistIter; typedef struct quicklistEntry { const quicklist *quicklist; quicklistNode *node; unsigned char *zi; unsigned char *value; long long longval; unsigned int sz; int offset; } quicklistEntry; |
由于这个链表当中涉及到压缩，但是如果被压缩的数据量过小的话，产生的结果可能比被压缩之前的数据还要占用空间，所以redis是定义了一些宏来避免这种情况的发生
|
1 2 3 |
#define SIZE_SAFETY_LIMIT 8192 #define MIN_COMPRESS_BYTES 48 #define MIN_COMPRESS_IMPROVE 8 |
由于quicklist结构的特殊性（大链表套小链表，期间还存在压缩解压等操作），其操作的代码也就比较繁琐（不算测试部分1400+行），但是如果将各个字段的含义搞明白之后，看起来就有人犹豫了，都是些结合其自身元素特性的一些组合，这里也就不再赘述了。
转载请注明原文链接：redis源码阅读之quicklist
