Redis源码阅读之quicklist

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.

 * We use bit fields keep the quicklistNode at 32 bytes.

 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).

 * encoding: 2 bits, RAW=1, LZF=2.

 * container: 2 bits, NONE=1, ZIPLIST=2.

 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.

 * attempted_compress: 1 bit, boolean, used for verifying during testing.

 * extra: 10 bits, free for future use; pads out the remainder of 32 bits */

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;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.

 * 'sz' is byte length of 'compressed' field.

 * 'compressed' is LZF data with total (compressed) length 'sz'

 * NOTE: uncompressed length is stored in quicklistNode->sz.

 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */

typedef struct quicklistLZF {

    unsigned int sz; /* LZF size in bytes*/

    char compressed[];

} quicklistLZF;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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 : QL_FILL_BITS;              /* fill factor for individual nodes */

    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */

    unsigned int bookmark_count: QL_BM_BITS;

    quicklistBookmark bookmarks[];

} quicklist;