Redis 核心数据结构（一）

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

The general layout of the ziplist is as follows:

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

NOTE: all fields are stored in little endian, if not specified otherwise.

<prevlen> <encoding> <entry-data> (1)

The encoding field of the entry depends on the content of the
entry. When the entry is a string, the first 2 bits of the encoding first
byte will hold the type of encoding used to store the length of the string,
followed by the actual length of the string. When the entry is an integer
the first 2 bits are both set to 1. The following 2 bits are used to specify
what kind of integer will be stored after this header. An overview of the
different types and encodings is as follows. The first byte is always enough
to determine the kind of entry.

 |00pppppp| - 1 byte
      String value with length less than or equal to 63 bytes (6 bits).
      "pppppp" represents the unsigned 6 bit length.
 |01pppppp|qqqqqqqq| - 2 bytes
      String value with length less than or equal to 16383 bytes (14 bits).
      IMPORTANT: The 14 bit number is stored in big endian.
 |10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
      String value with length greater than or equal to 16384 bytes.
      Only the 4 bytes following the first byte represents the length
      up to 2^32-1. The 6 lower bits of the first byte are not used and
      are set to zero.
      IMPORTANT: The 32 bit number is stored in big endian.
 |11000000| - 3 bytes
      Integer encoded as int16_t (2 bytes).
 |11010000| - 5 bytes
      Integer encoded as int32_t (4 bytes).
 |11100000| - 9 bytes
      Integer encoded as int64_t (8 bytes).
 |11110000| - 4 bytes
      Integer encoded as 24 bit signed (3 bytes).
 |11111110| - 2 bytes
      Integer encoded as 8 bit signed (1 byte).
 |1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer.
      Unsigned integer from 0 to 12. The encoded value is actually from
      1 to 13 because 0000 and 1111 can not be used, so 1 should be
      subtracted from the encoded 4 bit value to obtain the right value.
 |11111111| - End of ziplist special entry.

list-max-ziplist-size -2

list-compress-depth 0 // 0 是特殊值，表示都不压缩，默认值。

/* Node, quicklist, and Iterator are the only data structures used currently. */

/* 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;

/* 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;

/* Bookmarks are padded with realloc at the end of of the quicklist struct.
 * They should only be used for very big lists if thousands of nodes were the
 * excess memory usage is negligible, and there's a real need to iterate on them
 * in portions.
 * When not used, they don't add any memory overhead, but when used and then
 * deleted, some overhead remains (to avoid resonance).
 * The number of bookmarks used should be kept to minimum since it also adds
 * overhead on node deletion (searching for a bookmark to update). */
typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;

/* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist.
 * 'count' is the number of total entries.
 * 'len' is the number of quicklist nodes.
 * 'compress' is: -1 if compression disabled, otherwise it's the number
 *                of quicklistNodes to leave uncompressed at ends of quicklist.
 * 'fill' is the user-requested (or default) fill factor.
 * 'bookmakrs are an optional feature that is used by realloc this struct,
 *      so that they don't consume memory when not used. */
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;

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-cli --raw

127.0.0.1:6379> RPUSH names diguage "D瓜哥" "https://www.diguage.com/"
2

127.0.0.1:6379> LRANGE names 0 -1
diguage
D瓜哥
https://www.diguage.com/

127.0.0.1:6379> TYPE names
list

127.0.0.1:6379> OBJECT encoding names
quicklist