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

《redis设计与实现》
空白 ziplist 示例图

area        |<---- ziplist header ---->|<-- end -->|

size          4 bytes   4 bytes 2 bytes  1 byte
            +---------+--------+-------+-----------+
component   | zlbytes | zltail | zllen | zlend     |
            |         |        |       |           |
value       |  1011   |  1010  |   0   | 1111 1111 |
            +---------+--------+-------+-----------+
                                       ^
                                       |
                               ZIPLIST_ENTRY_HEAD
                                       &
address                        ZIPLIST_ENTRY_TAIL
                                       &
                               ZIPLIST_ENTRY_END

非空 ziplist 示例图

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                        ZIPLIST_ENTRY_TAIL

1
2
3
4
5

typedef struct intset {
    uint32_t encoding; // 编码方式
    uint32_t length; // 元素数量
    int8_t contents[]; // 保存元素的数组
} intset;

1
2
3

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

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

// 跳跃表节点
typedef struct zskiplistNode {
    robj *obj; // 保存的对象
    double score; // 分值 跳跃表按照分值进行排序
    struct zskiplistNode *backward; // 上一节点
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned int span; // 跨度 记录两个节点之间的距离
    } level[]; // 层
} zskiplistNode;

// 跳跃表
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头、尾指针
    PORT_ULONG length; // 跳跃表长度
    int level; // 层数最大节点层数
} zskiplist;

 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

// 创建节点
zskiplistNode *zslCreateNode(int level, double score, robj *obj) {
    // 申请内存
    zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score; // 赋值分数
    zn->obj = obj; // 设定成员对象
    return zn;
}

// 创建跳跃表
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    // 申请内存
    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1; // 设置层数初始为1
    zsl->length = 0; // 设置长度初始为0

    // 创建头节点 层数为32 分数为0
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);

    // 将每层的forward指针指向null，跨度0
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    // 设定backward指向null
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}

 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
42
43
44
45
46
47
48
49

typedef struct dictEntry {
    void *key;// key 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;// 值，支持多种类型,使用联合。
    struct dictEntry *next;// 下一个点 采用链式来解决索引冲突问题
} dictEntry;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);// hash函数
    void *(*keyDup)(void *privdata, const void *key);// key复制函数
    void *(*valDup)(void *privdata, const void *obj);// value复制函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);// key比较函数
    void (*keyDestructor)(void *privdata, void *key);// key释放函数
    void (*valDestructor)(void *privdata, void *obj);// value释放函数
} dictType;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;// 指针的数组头的指针
    unsigned long size;// 大小
    unsigned long sizemask;// 大小的掩码 总是等于size-1
    unsigned long used;// 被使用的节点数
} dictht;// hash表

typedef struct dict {
    dictType *type;// 绑定的函数
    void *privdata;// 私有数据
    dictht ht[2];// hash表，一般只使用[0]，在rehash的时候使用[1]
    long rehashidx; // 记录rehash的进度，不进行rehash的时候为-1
    int iterators; /* number of iterators currently running */
} dict;// 字典

/* If safe is set to 1 this is a safe iterator, that means, you can call
 * dictAdd, dictFind, and other functions against the dictionary even while
 * iterating. Otherwise it is a non safe iterator, and only dictNext()
 * should be called while iterating. */
typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;
} dictIterator;// 迭代器