Repository: valkey-io/valkey
File: src/dict.c (C)

Code before:
    }
}

dictIterator *dictGetIterator(dict *d) {
    dictIterator *iter = zmalloc(sizeof(*iter));
    dictInitIterator(iter, d);
    return iter;
}

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

    i->safe = 1;
    return i;
}

/* Initialize a randomized iterator that skips a random number of entries
 * and then iterates over the entire dictionary, wrapping around to cover
 * all entries.
 * Use dictRandomIterNext to fetch the next element in the iterator.
 */
dictRandomIterator *dictGetRandomIterator(dict *d) {
    dictRandomIterator *it = zmalloc(sizeof(dictRandomIterator));
    it->d = d;
    const long size = dictSize(d);
    it->skip = rand() % (size == 0 ? 1 : size);
    it->index = 0;
    it->is_wrapped = 0;
    it->iter = dictGetSafeIterator(d);

    // Advance iter to skip entries
    unsigned long skipped = 0;
    while (skipped < it->skip && dictNext(it->iter)) {
        skipped++;
    }
    return it;
}

/* Return the next dictEntry in randomized iteration order.
 * Returns NULL when all entries have been visited exactly once. */
dictEntry *dictRandomIterNext(dictRandomIterator *it) {
    dictEntry *de = NULL;

    if (it->is_wrapped == 0) {
        de = dictNext(it->iter);
        if (de) return de;
        dictReleaseIterator(it->iter);
        it->is_wrapped = 1;
        it->iter = dictGetSafeIterator(it->d);
    }


Review comment (bug):
Should we maintain the skipped entries count? I think it will lead to incorrect iteration logic in the second half. What if there are more entries inserted above? We would most likely not perform a full iteration and skip some elements.

I think the logic would be more hardened if we maintain the random bucket index on which we start the iteration and then finish it when we hit that back again on wrap-around.

Code after:
    }
}

dictIterator *dictGetIterator(dict *d) {
    dictIterator *iter = zmalloc(sizeof(*iter));
    dictInitIterator(iter, d);
    return iter;
}

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

    i->safe = 1;
    return i;
}

dictEntry *dictNext(dictIterator *iter) {
    while (1) {
        if (iter->entry == NULL) {
            if (iter->index == -1 && iter->table == 0) {
                if (iter->safe)
                    dictPauseRehashing(iter->d);
                else
                    iter->fingerprint = dictFingerprint(iter->d);

                /* skip the rehashed slots in table[0] */
                if (dictIsRehashing(iter->d)) {
                    iter->index = iter->d->rehashidx - 1;
                }
            }
            iter->index++;
            if (iter->index >= (long)DICTHT_SIZE(iter->d->ht_size_exp[iter->table])) {
                if (dictIsRehashing(iter->d) && iter->table == 0) {
                    iter->table++;
                    iter->index = 0;
                } else {
                    break;
                }
            }
            iter->entry = iter->d->ht_table[iter->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 = dictGetNext(iter->entry);
            return iter->entry;
        }
    }
    return NULL;