版本：redis 5.0.3

1. 解读 Redis 的 adlist /dict源码

1. adlist

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

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

adlist.h

// 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 独特之处在于：

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

dict.h

// 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）。

// 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)。