数据结构

Sds (Simple Dynamic String)

用途

  1. 实现字符串对象(StringObject)
  2. 用作 char* 类型的替代品

数据结构(sds.h/sds.c)

3.2之前的实现

typedef char *sds;

struct sdshdr {
    // buf已占用长度
    unsigned int len;
    // buf剩余长度
    unsigned int free;
    // 字符串数据
    char buf[];
};
1
2
3
4
5
6
7
8
9
10

3.2之后的实现

针对不同长度范围定义了不同的结构,__attribute__ ((__packed__))告诉编译器取消字节对齐

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. */
// 字符串长度小于 1<<5 (32)
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
// 字符串长度小于 1<<8 (256)
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[];
};
// 字符串长度小于 1<<16 (65536)
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[];
};
// 字符串长度小于 1<<32 (4294967296)
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[];
};
// 字符串长度小于 1<<64 (18446744073709551616)
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[];
};
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

双端链表(adlist)

用途

  1. 链表对象(ListObject)的底层实现之一
  2. 为各个模块提供链表结构
    • 事务模块使用双端链表依序保存输入的命令
    • 服务器模块使用双端链表来保存多个客户端
    • 订阅/发送模块使用双端链表来保存订阅模式的多个客户端
    • 事件模块使用双端链表来保存时间事件(time event)

数据结构(adlist.h/adlist.c)

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

typedef struct listIter {
    listNode *next;
    // 迭代方向(AL_START_HEAD/AL_START_TAIL)
    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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

字典(dict)

用途

  1. 哈希对象(HashObject)的底层实现之一
  2. 实现数据库键空间(key space)

数据结构(dict.h/dict.c)

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

typedef struct dictType {
    // 哈希函数
    uint64_t (*hashFunction)(const void *key);
    // key复制函数
    void *(*keyDup)(void *privdata, const void *key);
    // val复制函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // key析构函数
    void (*keyDestructor)(void *privdata, void *key);
    // val析构函数
    void (*valDestructor)(void *privdata, void *obj);
} 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 {
    // 哈希表节点指针数组(bucket)
    dictEntry **table;
    // 指针数组的大小
    unsigned long size;
    // 指针数组的长度掩码(用于计算索引值)
    unsigned long sizemask;
    // 哈希表现有的节点数量
    unsigned long used;
} dictht;

typedef struct dict {
    // 特定类型的处理函数
    dictType *type;
    // 类型处理函数的私有数据
    void *privdata;
    // 哈希表(2个)
    dictht ht[2];
    // 记录rehash进度的标志,-1表示未进行
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 当前正在运作的安全迭代器数量
    unsigned long 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;
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64