1/* This is our hash table structure. Every dictionary has two of this as we
 2 * implement incremental rehashing, for the old to the new table. */
 3typedef struct dictht {
 4    dictEntry **table;
 5    unsigned long size;
 6    unsigned long sizemask;
 7    unsigned long used;
 8} dictht;
 9
10typedef struct dict {
11    dictType *type;
12    void *privdata;
13    dictht ht[2];
14    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
15    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
16} dict;

 1/* Create a new hash table */
 2dict *dictCreate(dictType *type,
 3        void *privDataPtr)
 4{
 5    dict *d = zmalloc(sizeof(*d));
 6
 7    _dictInit(d,type,privDataPtr);
 8    return d;
 9}
10
11/* Initialize the hash table */
12int _dictInit(dict *d, dictType *type,
13        void *privDataPtr)
14{
15    _dictReset(&d->ht[0]);
16    _dictReset(&d->ht[1]);
17    d->type = type;
18    d->privdata = privDataPtr;
19    d->rehashidx = -1;
20    d->pauserehash = 0;
21    return DICT_OK;
22}

 1dictEntry *dictFind(dict *d, const void *key)
 2{
 3    dictEntry *he;
 4    uint64_t h, idx, table;
 5
 6    if (dictSize(d) == 0) return NULL; /* dict is empty */
 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 (key==he->key || dictCompareKeys(d, key, he->key))
14                return he;
15            he = he->next;
16        }
17        if (!dictIsRehashing(d)) return NULL;
18    }
19    return NULL;
20}

 1/* This function performs just a step of rehashing, and only if hashing has
 2 * not been paused for our hash table. When we have iterators in the
 3 * middle of a rehashing we can't mess with the two hash tables otherwise
 4 * some element can be missed or duplicated.
 5 *
 6 * This function is called by common lookup or update operations in the
 7 * dictionary so that the hash table automatically migrates from H1 to H2
 8 * while it is actively used. */
 9static void _dictRehashStep(dict *d) {
10    if (d->pauserehash == 0) dictRehash(d,1);
11}
12
13/* Performs N steps of incremental rehashing. Returns 1 if there are still
14 * keys to move from the old to the new hash table, otherwise 0 is returned.
15 *
16 * Note that a rehashing step consists in moving a bucket (that may have more
17 * than one key as we use chaining) from the old to the new hash table, however
18 * since part of the hash table may be composed of empty spaces, it is not
19 * guaranteed that this function will rehash even a single bucket, since it
20 * will visit at max N*10 empty buckets in total, otherwise the amount of
21 * work it does would be unbound and the function may block for a long time. */
22int dictRehash(dict *d, int n) {
23    int empty_visits = n*10; /* Max number of empty buckets to visit. */
24    if (!dictIsRehashing(d)) return 0;
25
26    while(n-- && d->ht[0].used != 0) {
27        dictEntry *de, *nextde;
28
29        /* Note that rehashidx can't overflow as we are sure there are more
30         * elements because ht[0].used != 0 */
31        assert(d->ht[0].size > (unsigned long)d->rehashidx);
32        while(d->ht[0].table[d->rehashidx] == NULL) {
33            d->rehashidx++;
34            if (--empty_visits == 0) return 1;
35        }
36        de = d->ht[0].table[d->rehashidx];
37        /* Move all the keys in this bucket from the old to the new hash HT */
38        while(de) {
39            uint64_t h;
40
41            nextde = de->next;
42            /* Get the index in the new hash table */
43            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
44            de->next = d->ht[1].table[h];
45            d->ht[1].table[h] = de;
46            d->ht[0].used--;
47            d->ht[1].used++;
48            de = nextde;
49        }
50        d->ht[0].table[d->rehashidx] = NULL;
51        d->rehashidx++;
52    }
53
54    /* Check if we already rehashed the whole table... */
55    if (d->ht[0].used == 0) {
56        zfree(d->ht[0].table);
57        d->ht[0] = d->ht[1];
58        _dictReset(&d->ht[1]);
59        d->rehashidx = -1;
60        return 0;
61    }
62
63    /* More to rehash... */
64    return 1;
65}

 1/* Add an element to the target hash table */
 2int dictAdd(dict *d, void *key, void *val)
 3{
 4    dictEntry *entry = dictAddRaw(d,key,NULL);
 5
 6    if (!entry) return DICT_ERR;
 7    dictSetVal(d, entry, val);
 8    return DICT_OK;
 9}
10
11/* Low level add or find:
12 * This function adds the entry but instead of setting a value returns the
13 * dictEntry structure to the user, that will make sure to fill the value
14 * field as they wish.
15 *
16 * This function is also directly exposed to the user API to be called
17 * mainly in order to store non-pointers inside the hash value, example:
18 *
19 * entry = dictAddRaw(dict,mykey,NULL);
20 * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
21 *
22 * Return values:
23 *
24 * If key already exists NULL is returned, and "*existing" is populated
25 * with the existing entry if existing is not NULL.
26 *
27 * If key was added, the hash entry is returned to be manipulated by the caller.
28 */
29dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
30{
31    long index;
32    dictEntry *entry;
33    dictht *ht;
34
35    if (dictIsRehashing(d)) _dictRehashStep(d);
36
37    /* Get the index of the new element, or -1 if
38     * the element already exists. */
39    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
40        return NULL;
41
42    /* Allocate the memory and store the new entry.
43     * Insert the element in top, with the assumption that in a database
44     * system it is more likely that recently added entries are accessed
45     * more frequently. */
46    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
47    entry = zmalloc(sizeof(*entry));
48    entry->next = ht->table[index];
49    ht->table[index] = entry;
50    ht->used++;
51
52    /* Set the hash entry fields. */
53    dictSetKey(d, entry, key);
54    return entry;
55}
56
57/* Add or Overwrite:
58 * Add an element, discarding the old value if the key already exists.
59 * Return 1 if the key was added from scratch, 0 if there was already an
60 * element with such key and dictReplace() just performed a value update
61 * operation. */
62int dictReplace(dict *d, void *key, void *val)
63{
64    dictEntry *entry, *existing, auxentry;
65
66    /* Try to add the element. If the key
67     * does not exists dictAdd will succeed. */
68    entry = dictAddRaw(d,key,&existing);
69    if (entry) {
70        dictSetVal(d, entry, val);
71        return 1;
72    }
73
74    /* Set the new value and free the old one. Note that it is important
75     * to do that in this order, as the value may just be exactly the same
76     * as the previous one. In this context, think to reference counting,
77     * you want to increment (set), and then decrement (free), and not the
78     * reverse. */
79    auxentry = *existing;
80    dictSetVal(d, existing, val);
81    dictFreeVal(d, &auxentry);
82    return 0;
83}

 1/* Expand the hash table if needed */
 2static int _dictExpandIfNeeded(dict *d)
 3{
 4    /* Incremental rehashing already in progress. Return. */
 5    if (dictIsRehashing(d)) return DICT_OK;
 6
 7    /* If the hash table is empty expand it to the initial size. */
 8    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
 9
10    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
11     * table (global setting) or we should avoid it but the ratio between
12     * elements/buckets is over the "safe" threshold, we resize doubling
13     * the number of buckets. */
14    if (d->ht[0].used >= d->ht[0].size &&
15        (dict_can_resize ||
16         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio) &&
17        dictTypeExpandAllowed(d))
18    {
19        return dictExpand(d, d->ht[0].used + 1);
20    }
21    return DICT_OK;
22}