Redis源码4.0阅读日记（2）字典dict

骑猪看日落 2023-06-25 04:55 18阅读 0赞

dict.h

### 哈希表节点 ###

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);
        // 复制键的函数
        void *(*keyDup)(void *privdata, const void *key);
        // 复制值的函数
        void *(*valDup)(void *privdata, const void *obj);
        // 比较键的函数
        int (*keyCompare)(void *privdata, const void *key1, const void *key2);
        // 销毁 key 的函数
        void (*keyDestructor)(void *privdata, void *key);
        // 销毁值的函数
        void (*valDestructor)(void *privdata, void *obj);
    } dictType;

### 哈希表 ###

typedef struct dictht { 
        dictEntry **table; // 哈希表数组
        unsigned long size; // 哈希表大小
        unsigned long sizemask; // 哈希表大小掩码，用于计算索引值
        unsigned long used; // 该哈希表中已有节点的数量
    } dictht;

### 字典 ###

typedef struct dict { 
        dictType *type; // 字典类型，保存一些用于操作特定类型键值对的函数
        void *privdata; // 私有数据，保存需要传给那些类型特定函数的可选数据
        dictht ht[2];// 一个字典结构包括两个哈希表
        long rehashidx; /* rehash索引 不进行rehash时 值=-1*/
        unsigned long iterators; /* 当前正在使用的迭代器数量 */
    } dict;

dict.h - 宏指令

### hash function ###

#define dictHashKey(d, key) (d)->type->hashFunction(key)

### dictSetVal ###

#define dictSetVal(d, entry, _val_) do { \ if ((d)->type->valDup) \ (entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \ else \ (entry)->v.val = (_val_); \ } while(0)

## dictFreeVal ##

#define dictFreeVal(d, entry) \ if ((d)->type->valDestructor) \ (d)->type->valDestructor((d)->privdata, (entry)->v.val)

dict.c

### 创建字典 ###

dict *dictCreate(dictType *type,
            void *privDataPtr)
    { 
        dict *d = zmalloc(sizeof(*d));
        //字典初始化
        _dictInit(d,type,privDataPtr);
        return d;
    }

### 初始化ht ###

/* 初始化ht 分配 ht1 ht 0 * Initialize the hash table */
    int _dictInit(dict *d, dictType *type,
            void *privDataPtr)
    { 
        // 两个hash table 置空
        _dictReset(&d->ht[0]);
        _dictReset(&d->ht[1]);
        // 设定字典类型
        d->type = type;
        d->privdata = privDataPtr;
        // rehashidx = -1 未进行 rehash 操作
        d->rehashidx = -1;
        // 正在使用的迭代器数量
        d->iterators = 0;
        return DICT_OK;
    }

### 重置 ht 初始化置空 ###

/* 重置 ht 初始化置空 * Reset a hash table already initialized with ht_init(). * NOTE: This function should only be called by ht_destroy(). */
    static void _dictReset(dictht *ht)
    { 
        ht->table = NULL;
        ht->size = 0;
        ht->sizemask = 0;
        ht->used = 0;
    }

### ReHash 字典 ###

/* ReHash 字典的扩容解决链表过长 * ReHash 字典的缩容解决键值少，节省空间 * 字典键值对存放在 ht[0] * 1 参照要执行的操作和字典中键值对的个数,为ht[1] 哈希表分配空间， * 2 将保存在 ht[0] 中的键值对重新计算哈希值和索引，然后存放到ht[1]中 * 3 当 ht[0] 中的数据全部迁移到 ht[1] 后，将 ht[1] 设为 ht[0] ，并将ht[1]新创建一个空白哈希表 -> 步骤1 * * Performs N steps of incremental rehashing. Returns 1 if there are still * keys to move from the old to the new hash table, otherwise 0 is returned. * * Note that a rehashing step consists in moving a bucket (that may have more * than one key as we use chaining) from the old to the new hash table, however * since part of the hash table may be composed of empty spaces, it is not * guaranteed that this function will rehash even a single bucket, since it * will visit at max N*10 empty buckets in total, otherwise the amount of * work it does would be unbound and the function may block for a long time. */
    int dictRehash(dict *d, int n) { 
        int empty_visits = n*10; /* Max number of empty buckets to visit. */
        if (!dictIsRehashing(d)) return 0;
    
        while(n-- && d->ht[0].used != 0) { 
            dictEntry *de, *nextde;
    
            /* Note that rehashidx can't overflow as we are sure there are more * elements because ht[0].used != 0 */
            assert(d->ht[0].size > (unsigned long)d->rehashidx);
            while(d->ht[0].table[d->rehashidx] == NULL) { 
                d->rehashidx++;
                if (--empty_visits == 0) return 1;
            }
            //获取 ht0 de
            de = d->ht[0].table[d->rehashidx];
            // de 计算 全部赋值给 ht 1
            /* Move all the keys in this bucket from the old to the new hash HT */
            while(de) { 
                uint64_t h;
    
                nextde = de->next;
                /* 计算新表中的hash值 索引位置*/
                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;
            d->rehashidx++;
        }
    
        /* 如果完成了，进行第3步，ht1 设置为ht0，ht1 重置为空 * 检查是否整个表迁移完成 rehash ht[0].used==0 已全部rehash到 ht[1] */
        if (d->ht[0].used == 0) { 
            // 清除ht[0]
            zfree(d->ht[0].table);
    // ht[1] 转移到 ht[0]
            d->ht[0] = d->ht[1];
    // ht[1] reset 置空
            _dictReset(&d->ht[1]);
    // 完成rehash dictCreate
            d->rehashidx = -1;
            // 全部迁移之后，返回0
            return 0;
        }
    
        /* More to rehash...否则（仍有数据需要从 ht0 -> ht1 ）返回1 */
        return 1;
    }

### 向字典中添加键值对 ###

/* 向字典中添加键值对 */
    int dictAdd(dict *d, void *key, void *val)
    { 
        // 表节点
        dictEntry *entry = dictAddRaw(d,key,NULL);
    
        if (!entry) return DICT_ERR;
        dictSetVal(d, entry, val);
        return DICT_OK;
    }

### dictAddRaw ###

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
    { 
        long index;
        dictEntry *entry;
        dictht *ht;
        //如果 rehashing 那么先 rehashing
        if (dictIsRehashing(d)) _dictRehashStep(d);
    
        /* 获取新建的键值对的索引值，如果发现已经存在则返回-1 */
        if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
            return NULL;
    
        /* Allocate the memory and store the new entry. * Insert the element in top, with the assumption that in a database * system it is more likely that recently added entries are accessed * more frequently. */
        // 如果正在rehashing 就添加到 ht[1] 否则添加到 ht[0]
        ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
        // 申请新节点的内存
        entry = zmalloc(sizeof(*entry));
        // 开链法，将新节点索引添加到节点的next
        entry->next = ht->table[index];
        ht->table[index] = entry;
        ht->used++;
    
        /* 设置节点key */
        dictSetKey(d, entry, key);
        return entry;
    }

### dictReplace (Add or Overwrite: 添加 1 或重写 0) ###

int dictReplace(dict *d, void *key, void *val)
    { 
        dictEntry *entry, *existing, auxentry;
    
        /* Try to add the element. If the key * does not exists dictAdd will suceed. */
        entry = dictAddRaw(d,key,&existing);
        if (entry) { 
            dictSetVal(d, entry, val);
            return 1;
        }
    
        /* Set the new value and free the old one. Note that it is important * to do that in this order, as the value may just be exactly the same * as the previous one. In this context, think to reference counting, * you want to increment (set), and then decrement (free), and not the * reverse. */
        auxentry = *existing;
        dictSetVal(d, existing, val);
        dictFreeVal(d, &auxentry);
        return 0;
    }

### 查找删除一个元素 dictGenericDelete ###

static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) { 
        uint64_t h, idx;
        dictEntry *he, *prevHe;
        int table;
        //ht 0/1 都为空返回 NULL
        if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
    
        if (dictIsRehashing(d)) _dictRehashStep(d);
        h = dictHashKey(d, key);
    
        for (table = 0; table <= 1; table++) { 
            idx = h & d->ht[table].sizemask;
            he = d->ht[table].table[idx];
            prevHe = NULL;
            while(he) { 
                if (key==he->key || dictCompareKeys(d, key, he->key)) { 
                    /* Unlink the element from the list */
                    if (prevHe)
                        prevHe->next = he->next;
                    else
                        d->ht[table].table[idx] = he->next;
                    if (!nofree) { 
                        dictFreeKey(d, he);
                        dictFreeVal(d, he);
                        zfree(he);
                    }
                    d->ht[table].used--;
                    return he;
                }
                prevHe = he;
                he = he->next;
            }
            if (!dictIsRehashing(d)) break;
        }
        return NULL; /* not found */
    }

### 移除字典中的一个元素 dictDelete ###

int dictDelete(dict *ht, const void *key) { 
        return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
    }

### 查找删除一个元素 dictGenericDelete ###

### dictRelease 删除1 整个字典 ###

int dictRelease(dict *d, dictht *ht, void(callback)(void *)) { 
        unsigned long i;
    
        /* 释放所有的元素 * Free all the elements */
        for (i = 0; i < ht->size && ht->used > 0; i++) { 
            dictEntry *he, *nextHe;
    
            if (callback && (i & 65535) == 0) callback(d->privdata);
    
            if ((he = ht->table[i]) == NULL) continue;
            while(he) { 
                nextHe = he->next;
                dictFreeKey(d, he);
                dictFreeVal(d, he);
                zfree(he);
                ht->used--;
                he = nextHe;
            }
        }
        /* Free the table and the allocated cache structure */
        zfree(ht->table);
        /* Re-initialize the table */
        _dictReset(ht);
        return DICT_OK; /* never fails */
    }

### 删除 并且 释放 整个 hash table dictRelease ###

/* 删除 并且 释放 整个 hash table * Clear & Release the hash table */
    void dictRelease(dict *d)
    { 
        _dictClear(d,&d->ht[0],NULL);
        _dictClear(d,&d->ht[1],NULL);
        zfree(d);
    }

### dictFind 返回节点索引的key对应的键值对 ###

dictEntry *dictFind(dict *d, const void *key)
    { 
        dictEntry *he;
        uint64_t h, idx, table;
        // 字典为空 返回 NULL
        if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
        // 如果在rehashing 先 rehashing
        if (dictIsRehashing(d)) _dictRehashStep(d);
    
        // 根据 dict 获得type 对应的 hashfunction 计算哈希值
        h = dictHashKey(d, key);
        for (table = 0; table <= 1; table++) { 
            idx = h & d->ht[table].sizemask;
            // 得到该索引值下存放的键值对链表
            he = d->ht[table].table[idx];
            while(he) { 
                // 找到 key 则返回
                if (key==he->key || dictCompareKeys(d, key, he->key))
                    return he;
                he = he->next;
            }
            // 如果没有进行 rehash 直接返回
            if (!dictIsRehashing(d)) return NULL;
        }
        return NULL;
    }

### 获取key对应的value dictFetchValue ###

void *dictFetchValue(dict *d, const void *key) { 
        dictEntry *he;
        // he = d->ht[table].table[idx];
        he = dictFind(d,key);
        return he ? dictGetVal(he) : NULL;
    }