Fork me on GitHub

Redis 源码解读(1)

版本:redis 5.0.3

1. 解读 Redis 的 adlist /dict源码

1. adlist

相比一般的双向链表,adlist 的独特之处在于:

  1. list 的结构体中,存在 dup、free、match 三种函数指针。
  2. 涉及到内存管理的 zfree方法(在 zmalloc中)。此处先不整理,可以提前参考:zmallc.c源码解读
  3. 增加了迭代器的相关操作。

adlist.h

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
// adlist.h:
// 首先有这么三个结构体:

// 单个结点,指向前驱后继
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;
  • 解释free()函数:在 del、empty 等方法中,如果要释放一个结点的内存,会首先调用这个free 函数指针,如果指向的函数有定义,那么将执行这个定义,否则不执行。

adlist.c

1. 常规方法:

  • listCreate——创建新的 list。
  • listEmpty——清空元素。释放内存,指针置 null,长度置0,但 list 本身不删。
  • listRelease——清空 list。先执行 listEmpty,然后执行 zfree 方法。
  • listAddNodeHead——头插新结点。
    1. 新建结点,分配内存,若失败返回 null,成功则下一步;
    2. 判断长度,若为0,则该结点为 list 唯一结点,改变指针;
    3. 若长度不为0,头插入链表中,改变指针,返回指向该 list 的指针。
    4. 以下的常规方法逻辑不再重复解释。
  • listAddNodeTail——尾插新结点。
  • listInsertNode——中间插入新结点。并传入待插入位置的相邻结点,并告知是前驱还是后继,然后执行插入。
  • listDelNode——删除某结点。

2. 迭代器相关方法:

  • listGetIterator——新建迭代器。传入 list 以及指明方向(从头还是从尾开始),新建迭代器,并返回该迭代器。
  • listReleaseIterator——释放迭代器。传入迭代器,调用 zfree 释放其内存。
  • listRewind——迭代器指头。传入 list 及一个迭代器,让迭代器指向 list 的头部。
  • listRewindTail——迭代器指尾。同上,只是让迭代器指向 list 的尾部。
  • listNext——指向迭代器的下一处。同时更新迭代器的 next 指针指向位置。

3. adlist 的高级操作

  • listDup——制造 list 的副本。传入原始 list,先分配内存,然后复制 dup、free、match 函数指针,让迭代器指向 head;遍历链表的同时,对每个结点执行 dup 函数(若无 dup 函数,那么仅赋值就 ok 了)。
    • 深拷贝的过程。
  • listSearchKey——返回第一个匹配的结点。传入目标值key,迭代器指头,遍历链表的同时,对结点执行 match 函数(若无 match 函数,那么仅比较 value 就 ok 了)。
  • listIndex——按 list 中结点的脚标(从0开始计数)返回结点。
  • listRotate——链表最尾部结点移到head 处。
  • listJoin——拼接链表 l 和 o。将 链表 o 拼接到 l 的后边,将链表 o 的指针置 null,同时将 len 置0。

2. dict

跟我们常见的 HashMap 很接近,dict 独特之处在于:

  1. dictht(两张哈希表,一张新表、一张旧表) + dictType(dict 中操作函数的集合) + iterators(迭代器) 一起组成 dict 结构。
  2. 可通过dict_can_resize参数设置是否允许扩容,0表示不允许,1表示允许。
    1. 但存在例外,即使设为0,如果结点总数与桶数量的比值大于dict_force_resize_ratio(默认是5)时,也会触发扩容。

dict.h

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
// dict 结构体
typedef struct dict {
dictType *type; // 字典类型
void *privdata; // 私有数据的指针
dictht ht[2];
long rehashidx; // 若为 -1 表示尚未 rehash
unsigned long iterators; // 当前迭代器数量
} dict;


// dictht 结构体,一个 dict 中有两个 dictht,在进行 incremental rehashing 时会用到。
typedef struct dictht {
dictEntry **table; // dictEntry 实体
unsigned long size;
unsigned long sizemask;
unsigned long used; // 已使用量
} dictht;


// dictEntry 结构体,K-V 结构
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;


// dictType 结构体,操作函数的集合
typedef struct dictType {
uint64_t (*hashFunction)(const void *key); // 计算 hash 的函数
void *(*keyDup)(void *privdata, const void *key); // 复制 key 的函数
void *(*valDup)(void *privdata, const void *obj); // 复制 val 的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 比较 key 的函数
void (*keyDestructor)(void *privdata, void *key); // key 的析构函数
void (*valDestructor)(void *privdata, void *obj); // val 的析构函数
} dictType;


// dictIterator 结构体,
typedef struct dictIterator {
dict *d; // 当前字典
long index; // 脚标
// safe 若是1,说明是安全的迭代器,迭代时可以调用各种方法,
// safe 若是0,说明是不安全的迭代器,只能调用 dictNext()函数
int table, safe; // table 指示是新、旧表格
dictEntry *entry, *nextEntry;
/* unsafe iterator fingerprint for misuse detection. */
long long fingerprint;
} dictIterator;

dict.c

1. 内部方法

  • dictSetHashFunctionSeed——设置 hash 种子方法。传入 seed,将 seed 按照sizeof(dict_hash_function_seed)的 size 复制到dict_hash_function_seed中。
  • dictGetHashFunctionSeed——拿到上面 Set 后的 hash 种子。
  • dictGenHashFunction——根据 key、len,计算出索引值(调用 siphash.c)。
  • dictGenCaseHashFunction——简易 hash 算法。传入 buff 和 len(调用 siphash.c)。
1
// siphash.c,待补充

2. 对外 API

  • _dictReset——将传入的 dictht 变量重置为默认态(清空)。dictht 中的dictht->table=null,这里的 table 有歧义,实际上是 dictEntry置 null,将 size、sizemas、used 置0。
  • dictCreate——新建一个 hash table。开辟内存,执行_dictInit()方法。
  • _dictInit——dict 初始化。将传入的dictType(操作参数的集合)、privDataPtr(操作函数需要的参数)置入 dict 中,其他参数要么 reset,要么恢复默认值。
  • _dictNextPower——传入 size,返回大于等于 size ,同时是2的幂次的整数。
  • dictResize——调整 size。 确定将要调整后的 size, 调用dictExpand 函数。
  • dictExpand——将 size 调用_dictNextPower替换为 realSize。按照 realSize 初始化一个新表(即 dictht)。
-------------The End-------------