Redis源码学习（31），字典学习，dict.c（一）

  创建一个新的 hash table

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

	
	int _dictInit(dict *d, dictType *type,
	        void *privDataPtr)
	{
	    _dictReset(&d->ht[0]);
	    _dictReset(&d->ht[1]);
	    d->type = type;
	    d->privdata = privDataPtr;
	    d->rehashidx = -1;
	    d->iterators = 0;
	    return DICT_OK;
	}

	
	static void _dictReset(dictht *ht)
	{
	    ht->table = NULL;
	    ht->size = 0;
	    ht->sizemask = 0;
	    ht->used = 0;
	}

1. 先申明一个字典结构体，并分配相应内存。
2. 调用 _dictInit 初始化字典。
3. 调用 _dictReset 初始化字典中两个哈希表。
4. 将哈希表中几个属性字段都设置为初始值。

  增加一个哈希节点到哈希表中。

int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key);

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;
	
	// 如果字典在进行 rahase 中，则进行一步 rahash
    if (dictIsRehashing(d)) _dictRehashStep(d);

    
    // 获取建的索引
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

    
    // 如果在 rehash 中 则返回第二个 hash 表中
    // 将新的哈希节点加入第二个 hash 表中
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    
    //设置哈希建
    dictSetKey(d, entry, key);
    return entry;
}

static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

1. 调用 dictAddRaw 增加一个哈希节点
2. 计算键的索引值，如果该值已经存在则返回错误
3. 如果正在进行 rehash 的话，会向第二个哈希表中新增节点
4. 调用宏定义方法 dictSetKey 设置哈希节点的键
5. 调用宏定义方法 dictSetVal 设置哈希节点的值

1. 增加新的哈希节点的时候，如果节点已存在则会报错。
2. 调用 dictHashKey 计算键的哈希值。
3. 再用哈希值与字典掩码计算出索引位置。
4. 遍历两个哈希表，判断键是否已存在。
5. 如果字典正在 rehash 中的话，则新增的节点会加到第二个哈希表中。
6. 如果字典正在 rehash 中的话， 则会进行一步的 rehash 的动作。