typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

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

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;

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

// dictType实现泛型，在server.c里有各种dictType的定义
typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

typedef struct dictht {
    dictEntry **table; // 表项
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;


typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;
} dictIterator;

typedef void (dictScanFunction)(void *privdata, const dictEntry *de);
typedef void (dictScanBucketFunction)(void *privdata, dictEntry **bucketref);

/* This is the initial size of every hash table */
#define DICT_HT_INITIAL_SIZE     4

n.table = zcalloc(realsize*sizeof(dictEntry*)); // realsize个桶

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

uint64_t siphash(const uint8_t *in, const size_t inlen, const uint8_t *k);
uint64_t siphash_nocase(const uint8_t *in, const size_t inlen, const uint8_t *k);

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

typedef struct zlentry {
    unsigned int prevrawlensize; // 上一节点头部长度
    unsigned int prevrawlen;    // 上一节点内容部分的长度
    unsigned int lensize;       // 当前节点头部长度
    unsigned int len;           // 当前节点内容部分的长度
    unsigned int headersize;     // 上一节点头部长度 + 当前节点头部长度
    unsigned char encoding;      // 编码
    unsigned char *p;            /* points to prev-entry-len field
} zlentry;

/* Return total bytes a ziplist is composed of. */
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))

/* Return the offset of the last item inside the ziplist. */
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))

/* Return the length of a ziplist, or UINT16_MAX if the length cannot be
 * determined without scanning the whole ziplist. */
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))

/*
 * ZIPLIST ENTRIES 列表项
 * ===============
 *
 * Every entry in the ziplist is prefixed by metadata that contains two pieces
 * of information. First, the length of the previous entry is stored to be
 * able to traverse the list from back to front. Second, the entry encoding is
 * provided. It represents the entry type, integer or string, and in the case
 * of strings it also represents the length of the string payload.
 * So a complete entry is stored like this:
 * ziplist的每一entry都带了一个metadata前缀，metadata里有2个信息。一个是，上一entry
 * 的长度，用于从后向前遍历列表；另一个是entry的编码encoding，编码记录了entry类型
 * （整数/字符串），如果是字符串的话那么还记录了字符串的长度。
 * 所有完整的entry的存储结构如下：
 * <prevlen> <encoding> <entry-data>
 *
 * Sometimes the encoding represents the entry itself, like for small integers
 * as we'll see later. In such a case the <entry-data> part is missing, and we
 * could have just:
 * 有时候编码已经表示了entry本身，例如小整数，这种情况下，entry-data是没有的：
 * <prevlen> <encoding>
 *
 * The length of the previous entry, <prevlen>, is encoded in the following way:
 * If this length is smaller than 254 bytes, it will only consume a single
 * byte representing the length as an unsinged 8 bit integer. When the length
 * is greater than or equal to 254, it will consume 5 bytes. The first byte is
 * set to 254 (FE) to indicate a larger value is following. The remaining 4
 * bytes take the length of the previous entry as value.
 * prevlen被用如下方式编码： 
 * 如果长度小于254字节，用1个字节就足够表示了；当长度大于等于254，那么需要5字节，
 * 第1个字节被设为254(0xFE)，表示余下4字节才是真正存了长度信息的。
 * (这里说明下，不是以255为分界的原因是，255是用来表达ziplist的结尾的，有特殊含义。)
 * So practically an entry is encoded in the following way:
 * 所以entry实际上是这样编码的：
 *
 * <prevlen from 0 to 253> <encoding> <entry>
 *
 * Or alternatively if the previous entry length is greater than 253 bytes
 * the following encoding is used:
 * 或者这样（上一entry长度大于等于254字节时）：
 *
 * 0xFE <4 bytes unsigned little endian prevlen> <encoding> <entry>
 *
 * 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.
 * encoding字段的最左2bits，保存了编码类型，00/01/10是字符串类型，11是整数类型。
 * 如果是11，那么接下来的2bits，保存了整数子类型。
 * encoding的总长度是动态的，取决于encoding首字节里的定义。
 *
 * |00pppppp| - 1 byte
 *      String value with length less than or equal to 63 bytes (6 bits).
 *      "pppppp" represents the unsigned 6 bit length.
 *      00：字符串长度小于等于63字节（6bits能表示的范围），长度信息存在pppppp里。
 * |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.
 *      01：字符串长度小于等于16383字节（14bits能表示的范围）
 *      注意，这个14bits数字是用大端字节序的
 * |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 32^2-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.
 *      10：字符串长度大于16384字节。
 *      不过这次pppppp没有被使用，而是置0，另外加了4个字节来存长度
 *      注意，4字节的长度是用大端字节序的
 * |11 00 0000| - 3 bytes
 *      Integer encoded as int16_t (2 bytes).
 *      双字节的整数
 * |11 01 0000| - 5 bytes
 *      Integer encoded as int32_t (4 bytes).
 *      4字节的整数
 * |11 10 0000| - 9 bytes
 *      Integer encoded as int64_t (8 bytes).
 *      8字节的整数
 * |11 11 0000| - 4 bytes
 *      Integer encoded as 24 bit signed (3 bytes).
 *      3字节的整数
 * |11 11 1110| - 2 bytes
 *      Integer encoded as 8 bit signed (1 byte).
 *      1字节的整数
 * |11 11 xxxx| - (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.
 *      后4bits如果不是0000/1110，那么就是表示[0，12]范围内的某一个数。
 *      因为0000有特殊用途了，所以这4bits实际上是存了[1,13]范围的总共13个数。
 *      为了能表示[0,12]，需要做一个-1的操作。所以实际是存[0001, 1101]
 * |11 11 1111| - End of ziplist special entry.
 *      这个就不是什么整数了，而是ziplist的end标识
 *
 * Like for the ziplist header, all the integers are represented in little
 * endian byte order, even when this code is compiled in big endian systems.
 * 所有证书都用小端字节序，即使是在大端字节序系统里编译也是。
 *
 * EXAMPLES OF ACTUAL ZIPLISTS
 * ===========================
 * 实例：
 *
 *  [0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff]
 *        |             |          |       |       |     |
 *     zlbytes        zltail    entries   "2"     "5"   end
 * （这个图是前3个[]用大端字节序表示的，[]里的最左边字节才是最低位的）
 * zlbytes是0x0000000f，表示这个ziplist占内存15字节。
 * zltail是0x0000000c，表示从ziplist起始位置到最后1个entry（02 f6），距离是12字节。
 * zllen是0x0002，表示总共存了2个元素。
 * 接下里的就是元素列表了，[00 f3]，00是prevlen，因为是首个元素，所以为0；
 * f3是encoding，|1111 0011|，根据上面的编码规则，可以知道这是个小整数，
 * 0011需要再减1，得到2。
 * 接下来是[02 f6]，02是prevlen，表示上一entry占2个字节；
 * f6是encoding，|1111 0110|，根据上面的编码规则，可以知道这是个小整数，
 * 0110需要再减1，得到5。
 * 最后，[ff]表示ziplist到此结束。
 *
 * 再演示怎么编码一个短字符串"Hello World"。
 * 把下面这串东西插入到上面的[02 f6]后面：
 *
 * [02] [0b] [48 65 6c 6c 6f 20 57 6f 72 6c 64]
 *
 * [02]表示prevlen；[0b]是encoding |0000 1011|，前2bits表示这是个字符串，
 * 后6bits表示字符串长度11字节；
 * 后面的那串就是正文"Hello World"了。
 */

typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count; // 总entry个数
    unsigned long len; // quicklistNodes个数
    int fill : 16; // list-max-ziplist-size
    unsigned int compress : 16; // list-compress-depth
} quicklist;