iterator , This implementation can be found in many high-level languages , Its function is to traverse the container

Iterator structure ：

typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;    // safe  Is it a safe iterator  
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;
} dictIterator;

adopt safe To distinguish between safe=1 For safe iterators

entry And nextEntry The two pointers point to Hash Two parent-child nodes after conflict . If in safe mode , Deleted entry node , nextEntry Fields can ensure that data in subsequent iterations is not lost

Types of iterators

Ordinary iterators ： Just traverse the data

Secure iterator ： Delete data while traversing

Operation of iterator ：

Acquisition iterator

Get the normal iterator ：

dictIterator *dictGetIterator(dict *d)
{
    dictIterator *iter = zmalloc(sizeof(*iter));

    iter->d = d;
    iter->table = 0;
    iter->index = -1;
    iter->safe = 0;
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}

It is not allowed to operate on data , Because when traversing the iterator, you get dictGetIterator Will get dictFingerprint , The fingerprint of the whole dictionary , If the traversal is completed, the fingerprint changes , Will lead to mistakes .

Then you may ask , Why is it not single threaded , Why can traversal be modified by others ？ Actually , If you look carefully , Any insertion we make into the dictionary , Search and so on , Will be called rehashstep, This may lead to changes in dictionary fingerprints .

Get the safe iterator ：

In fact, it's just a relatively ordinary iterator setting safe Mark is 1

dictIterator *dictGetSafeIterator(dict *d) {
    dictIterator *i = dictGetIterator(d);

    i->safe = 1;
    return i;
}

The operation of adding, deleting, modifying and looking up the dictionary will call dictRehashStep Function for progressive rehash operation , But we see that

static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

Actually ,rehash When , Will determine whether it is in safe iterator mode , If so, it won't rehash, So it will not lead to repeated traversal .

Iterator traversal

dictEntry *dictNext(dictIterator *iter)
{
    while (1) {
        if (iter->entry == NULL) {
            dictht *ht = &iter->d->ht[iter->table];
            if (iter->index == -1 && iter->table == 0) {
                if (iter->safe)
                    iter->d->iterators++;
                else
                    iter->fingerprint = dictFingerprint(iter->d);
            }
            iter->index++;
            if (iter->index >= (long) ht->size) {
                if (dictIsRehashing(iter->d) && iter->table == 0) {
                    iter->table++;
                    iter->index = 0;
                    ht = &iter->d->ht[1];
                } else {
                    break;
                }
            }
            iter->entry = ht->table[iter->index];
        } else {
            iter->entry = iter->nextEntry;
        }
        if (iter->entry) {
            /* We need to save the 'next' here, the iterator user
             * may delete the entry we are returning. */
            iter->nextEntry = iter->entry->next;
            return iter->entry;
        }
    }
    return NULL;
}

If it's safe mode ： First traversal iterators Meeting ++ , Indicates that the dictionary is traversing safely , Will be banned rehash

If it's not safe mode ： For the first time, record the fingerprint information of the dictionary .

Acquisition of dictionary fingerprints ： In fact, it is to transform the dictionary into a 64 Bit array , It can also be understood as a hash

long long dictFingerprint(dict *d) {
    long long integers[6], hash = 0;
    int j;

    integers[0] = (long) d->ht[0].table;
    integers[1] = d->ht[0].size;
    integers[2] = d->ht[0].used;
    integers[3] = (long) d->ht[1].table;
    integers[4] = d->ht[1].size;
    integers[5] = d->ht[1].used;

    /* We hash N integers by summing every successive integer with the integer
     * hashing of the previous sum. Basically:
     *
     * Result = hash(hash(hash(int1)+int2)+int3) ...
     *
     * This way the same set of integers in a different order will (likely) hash
     * to a different number. */
    for (j = 0; j < 6; j++) {
        hash += integers[j];
        /* For the hashing step we use Tomas Wang's 64 bit integer hash. */
        hash = (~hash) + (hash << 21); // hash = (hash << 21) - hash - 1;
        hash = hash ^ (hash >> 24);
        hash = (hash + (hash << 3)) + (hash << 8); // hash * 265
        hash = hash ^ (hash >> 14);
        hash = (hash + (hash << 2)) + (hash << 4); // hash * 21
        hash = hash ^ (hash >> 28);
        hash = hash + (hash << 31);
    }
    return hash;
}

Release iterators

void dictReleaseIterator(dictIterator *iter)
{
    if (!(iter->index == -1 && iter->table == 0)) {
        if (iter->safe)
            iter->d->iterators--;
        else
            assert(iter->fingerprint == dictFingerprint(iter->d));
    }
    zfree(iter);
}

Release the iterator in safe mode iterators++ The value of is subtracted , If it's not safe mode , Then it is necessary to judge whether the dictionary is modified in the process of traversal , Modification triggers assertion .

Finally, release the iterator .