Redis源代码分析之三:散列表——Dict(下)

时间:2022-03-21 04:50:09

下面分析散列表常见操作,如插入、删除、替换等。

散列表插入函数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[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;

/* Set the hash entry fields. */
dictSetHashKey(d, entry, key);
dictSetHashVal(d, entry, val);
return DICT_OK;
}

如果散列表正在进行再哈希,那么调用_dictRehashStep()函数执行一步再哈希,以从原哈希表H1迁移到新哈希表H2。

如果该键的索引已经存在,返回错误。

下面为新项分配内存,如果进行了rehash,分配在ht[1],否则分配在ht[0]。

最后调用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[0].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[table].sizemask;
he = d->ht[table].table[idx];
while(he) {
if (dictCompareHashKeys(d, key, he->key))
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}

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


最后,我们分析删除哈希表中一项的函数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[0].size == 0) return DICT_ERR; /* d->ht[0].table is 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 (dictCompareHashKeys(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) {
dictFreeEntryKey(d, he);
dictFreeEntryVal(d, he);
}
zfree(he);
d->ht[table].used--;
return DICT_OK;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return DICT_ERR; /* not found */
}

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