[原]Redis源代码分析之三：散列表——Dict（下）
下面分析散列表常见操作，如插入、删除、替换等。散列表插入函数dictAdd实现如下：/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
int index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d);
/* Get the index of the new element, or -1 if
* the element already exists. */
if ((index = _dictKeyIndex(d, key)) == -1)
return DICT_ERR;
/* Allocates the memory and stores key */
ht = dictIsRehashing(d) ? &d->ht : &d->ht;
entry = zmalloc(sizeof(*entry));
entry->next = ht->table;
ht->table = entry;
ht->used++;
/* Set the hash entry fields. */
dictSetHashKey(d, entry, key);
dictSetHashVal(d, entry, val);
return DICT_OK;
}
如果散列表正在进行再哈希，那么调用_dictRehashStep()函数执行一步再哈希，以从原哈希表H1迁移到新哈希表H2。
如果该键的索引已经存在，返回错误。
下面为新项分配内存，如果进行了rehash，分配在ht，否则分配在ht。
最后调用dictSetHashKey和dictSetHashVal设置键和值。这两个宏的定义如下：#define dictSetHashKey(d, entry, _key_) do { \
if ((d)->type->keyDup) \
entry->key = (d)->type->keyDup((d)->privdata, _key_); \
else \
entry->key = (_key_); \
} while(0)
#define dictSetHashVal(d, entry, _val_) do { \
if ((d)->type->valDup) \
entry->val = (d)->type->valDup((d)->privdata, _val_); \
else \
entry->val = (_val_); \
} while(0)
这里调用了DictType中自定义的键值复制函数。
替换一个键值对的操作函数如下：/* Add an element, discarding the old if the key already exists.
* Return 1 if the key was added from scratch, 0 if there was already an
* element with such key and dictReplace() just performed a value update
* operation. */
int dictReplace(dict *d, void *key, void *val)
{
dictEntry *entry, auxentry;
/* Try to add the element. If the key
* does not exists dictAdd will suceed. */
if (dictAdd(d, key, val) == DICT_OK)
return 1;
/* It already exists, get the entry */
entry = dictFind(d, key);
/* Free the old value and set the new one */
/* 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 = *entry;
dictSetHashVal(d, entry, val);
dictFreeEntryVal(d, &auxentry);
return 0;
}
首先尝试添加新项，如果原来不存在此项，那么就相当于用新项替换了空想，直接返回成功。
如果原来已经存在了此键的项，那么首先用dictFind查找出此项，然后设置新值，释放原项。注意这里的顺序，因为新值可能和旧值完全一样，如果先释放原项可能会使引用计数不合法。
上面提到的dictFind查找函数实现如下：dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
unsigned int h, idx, table;
if (d->ht.size == 0) return NULL; /* We don't have a table at all */
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht.sizemask;
he = d->ht.table;
while(he) {
if (dictCompareHashKeys(d, key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
我们看到，首先调用一次哈希函数得到该键的索引h，然后在两个哈希表ht、ht中按链表查找。
最后，我们分析删除哈希表中一项的函数dictGenericDelete：/* Search and remove an element */
static int dictGenericDelete(dict *d, const void *key, int nofree)
{
unsigned int h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht.size == 0) return DICT_ERR; /* d->ht.table is NULL */
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht.sizemask;
he = d->ht.table;
prevHe = NULL;
while(he) {
if (dictCompareHashKeys(d, key, he->key)) {
/* Unlink the element from the list */
if (prevHe)
prevHe->next = he->next;
else
d->ht.table = he->next;
if (!nofree) {
dictFreeEntryKey(d, he);
dictFreeEntryVal(d, he);
}
zfree(he);
d->ht.used--;
return DICT_OK;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return DICT_ERR; /* not found */
}
查找要删除的项部分和dictFind函数相同，只是遍历链表的时候增加一个指针prevHe，即要找项的前一个项的指针。如果prevHe为空，说明He为链表第一项，那么简单地将其从链表头部摘下即可。否则，将索引指针指向新项。如果需要析构键、值自身的内存，则调用相关析构函数释放键、值的内存。最后释放项he的内存，更新引用计数，返回执行成功。
作者：Aegeaner 发表于2012-2-4 11:48:44 原文链接
页:
[1]