Redis源码（1）基本数据结构（中）

// 字典定义
typedef struct dict {
    // 类型特定函数
    // 这一指针指向的结构体中存储了hash表常用的函数指针
    dictType *type;
    // 私有数据：保存了需要传给那些类型特定函数的可选参数（见后文）
    void *privdata;
    // 哈希表
    dictht ht[2];
    // 该值表示rehash进行到的下标索引位置
    // 当 rehash 不在进行时，值为 -1
    // 开始时值为0
    // 正在进行中时，值处于0到size之间
    int rehashidx;     
    int iterators; // 目前正在运行的安全迭代器的数量
} dict;

//每个字典都使用两个哈希表，从而实现渐进式 rehash 。
typedef struct dictht {
    // 哈希表数组(存储的是指向节点指针数组的指针)
    // 都使用指针的方式可以节省空间
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

//哈希表节点
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;

    // 如果条件允许的话，进行单步 rehash
    // T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d); 
    
    // 计算键在哈希表中的索引值
    // 如果值为 -1 ，那么表示键已经存在
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;
    // 如果字典正在 rehash ，那么将新键添加到 1 号哈希表
    // 否则，将新键添加到 0 号哈希表
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    // 为新节点分配空间
    entry = zmalloc(sizeof(*entry));
    // 将新节点插入到链表表头
    entry->next = ht->table[index];
    ht->table[index] = entry;
    // 更新哈希表已使用节点数量
    ht->used++;
    // 设置新节点的键
    // T = O(1)
    dictSetKey(d, entry, key);
    return entry;
}

// 指示字典是否启用 rehash 的标识
static int dict_can_resize = 1;
// 强制 rehash 的比率(强制不可被上面的标志所阻止)
static unsigned int dict_force_resize_ratio = 5;

int dictRehash(dict *d, int n) {
    // 只可以在 rehash 进行中时执行
    if (!dictIsRehashing(d)) return 0;
    // 进行 N 步迁移
    // T = O(N)
    while(n--) {
        dictEntry *de, *nextde;
        
        // 如果 0 号哈希表为空，那么表示 rehash 执行完毕
        // T = O(1)
        if (d->ht[0].used == 0) {
        // 释放 0 号哈希表
        zfree(d->ht[0].table);
        // 将原来的 1 号哈希表设置为新的 0 号哈希表
        d->ht[0] = d->ht[1];
        // 重置旧的 1 号哈希表
        _dictReset(&d->ht[1]);
        // 关闭 rehash 标识
        d->rehashidx = -1;
        // 返回 0 ，向调用者表示 rehash 已经完成
        return 0;
        }
    // 确保 rehashidx 没有越界
    assert(d->ht[0].size > (unsigned)d->rehashidx);
    
    // 略过数组中为空的索引，找到下一个非空索引
    // hash表的entry中第一个就是void* key，所以可以直接访问其是否为空
    // 来判断该出是否存在键值对
    while(d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++;
    // 指向该索引的链表表头节点
    de = d->ht[0].table[d->rehashidx];
    // 将链表中的所有节点迁移到新哈希表
    // T = O(1)
    while(de) {
            unsigned int h;    
            // 保存下个节点的指针
            nextde = de->next;           
            /* Get the index in the new hash table */
            // 计算新哈希表的哈希值，以及节点插入的索引位置
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            // 插入节点到新哈希表
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            // 更新计数器
            d->ht[0].used--;
            d->ht[1].used++;            
            // 继续处理下个节点
            de = nextde;
            }
        // 将刚迁移完的哈希表索引的指针设为空
        d->ht[0].table[d->rehashidx] = NULL;
        // 更新 rehash 索引
        d->rehashidx++;
        }
    return 1;
}

dictIterator *dictGetSafeIterator(dict *d) {
    dictIterator *i = dictGetIterator(d);
    // 设置安全迭代器标识
    i->safe = 1;
    return i;
}

dictIterator *dictGetIterator(dict *d)
{
    dictIterator *iter = zmalloc(sizeof(*iter));

    iter->d = d;
    iter->table = 0;
    iter->index = -1;
    iter->safe = 0;
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}