[原]Redis源代码分析之三：散列表——Dict（下）

winston

下面分析散列表常见操作，如插入、删除、替换等。
散列表插入函数dictAdd实现如下：/* Add an element to the target hash table */

2. int dictAdd(dict *d, void *key, void *val)
3. {
4.     int index;
5.     dictEntry *entry;
6.     dictht *ht;
8.     if (dictIsRehashing(d)) _dictRehashStep(d);
10.     /* Get the index of the new element, or -1 if
11.      * the element already exists. */
12.     if ((index = _dictKeyIndex(d, key)) == -1)
13.         return DICT_ERR;
15.     /* Allocates the memory and stores key */
16.     ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
17.     entry = zmalloc(sizeof(*entry));
18.     entry->next = ht->table[index];
19.     ht->table[index] = entry;
20.     ht->used++;
22.     /* Set the hash entry fields. */
23.     dictSetHashKey(d, entry, key);
24.     dictSetHashVal(d, entry, val);
25.     return DICT_OK;
26. }

复制代码

如果散列表正在进行再哈希，那么调用_dictRehashStep()函数执行一步再哈希，以从原哈希表H1迁移到新哈希表H2。
如果该键的索引已经存在，返回错误。
下面为新项分配内存，如果进行了rehash，分配在ht[1]，否则分配在ht[0]。
最后调用dictSetHashKey和dictSetHashVal设置键和值。这两个宏的定义如下：#define dictSetHashKey(d, entry, _key_) do { \

2.     if ((d)->type->keyDup) \
3.         entry->key = (d)->type->keyDup((d)->privdata, _key_); \
4.     else \
5.         entry->key = (_key_); \
6. } while(0)
8. #define dictSetHashVal(d, entry, _val_) do { \
9.     if ((d)->type->valDup) \
10.         entry->val = (d)->type->valDup((d)->privdata, _val_); \
11.     else \
12.         entry->val = (_val_); \
13. } while(0)

复制代码

这里调用了DictType中自定义的键值复制函数。
替换一个键值对的操作函数如下：/* Add an element, discarding the old if the key already exists.

2. * Return 1 if the key was added from scratch, 0 if there was already an
3. * element with such key and dictReplace() just performed a value update
4. * operation. */
5. int dictReplace(dict *d, void *key, void *val)
6. {
7.     dictEntry *entry, auxentry;
9.     /* Try to add the element. If the key
10.      * does not exists dictAdd will suceed. */
11.     if (dictAdd(d, key, val) == DICT_OK)
12.         return 1;
13.     /* It already exists, get the entry */
14.     entry = dictFind(d, key);
15.     /* Free the old value and set the new one */
16.     /* Set the new value and free the old one. Note that it is important
17.      * to do that in this order, as the value may just be exactly the same
18.      * as the previous one. In this context, think to reference counting,
19.      * you want to increment (set), and then decrement (free), and not the
20.      * reverse. */
21.     auxentry = *entry;
22.     dictSetHashVal(d, entry, val);
23.     dictFreeEntryVal(d, &auxentry);
24.     return 0;
25. }

复制代码

首先尝试添加新项，如果原来不存在此项，那么就相当于用新项替换了空想，直接返回成功。
如果原来已经存在了此键的项，那么首先用dictFind查找出此项，然后设置新值，释放原项。注意这里的顺序，因为新值可能和旧值完全一样，如果先释放原项可能会使引用计数不合法。
上面提到的dictFind查找函数实现如下：dictEntry *dictFind(dict *d, const void *key)

2. {
3.     dictEntry *he;
4.     unsigned int h, idx, table;
6.     if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */
7.     if (dictIsRehashing(d)) _dictRehashStep(d);
8.     h = dictHashKey(d, key);
9.     for (table = 0; table <= 1; table++) {
10.         idx = h & d->ht[table].sizemask;
11.         he = d->ht[table].table[idx];
12.         while(he) {
13.             if (dictCompareHashKeys(d, key, he->key))
14.                 return he;
15.             he = he->next;
16.         }
17.         if (!dictIsRehashing(d)) return NULL;
18.     }
19.     return NULL;
20. }

复制代码

我们看到，首先调用一次哈希函数得到该键的索引h，然后在两个哈希表ht[0]、ht[1]中按链表查找。


最后，我们分析删除哈希表中一项的函数dictGenericDelete：/* Search and remove an element */

2. static int dictGenericDelete(dict *d, const void *key, int nofree)
3. {
4.     unsigned int h, idx;
5.     dictEntry *he, *prevHe;
6.     int table;
8.     if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */
9.     if (dictIsRehashing(d)) _dictRehashStep(d);
10.     h = dictHashKey(d, key);
12.     for (table = 0; table <= 1; table++) {
13.         idx = h & d->ht[table].sizemask;
14.         he = d->ht[table].table[idx];
15.         prevHe = NULL;
16.         while(he) {
17.             if (dictCompareHashKeys(d, key, he->key)) {
18.                 /* Unlink the element from the list */
19.                 if (prevHe)
20.                     prevHe->next = he->next;
21.                 else
22.                     d->ht[table].table[idx] = he->next;
23.                 if (!nofree) {
24.                     dictFreeEntryKey(d, he);
25.                     dictFreeEntryVal(d, he);
26.                 }
27.                 zfree(he);
28.                 d->ht[table].used--;
29.                 return DICT_OK;
30.             }
31.             prevHe = he;
32.             he = he->next;
33.         }
34.         if (!dictIsRehashing(d)) break;
35.     }
36.     return DICT_ERR; /* not found */
37. }

复制代码

查找要删除的项部分和dictFind函数相同，只是遍历链表的时候增加一个指针prevHe，即要找项的前一个项的指针。如果prevHe为空，说明He为链表第一项，那么简单地将其从链表头部摘下即可。否则，将索引指针指向新项。如果需要析构键、值自身的内存，则调用相关析构函数释放键、值的内存。最后释放项he的内存，更新引用计数，返回执行成功。

作者：Aegeaner 发表于2012-2-4 11:48:44 原文链接