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

Code before:
    bucket *b = ht->tables[0] + idx;
    while (b != NULL) {
        bucket *next = getChildBucket(b);
        rehashBucketShrink(ht, b);
        b = next;
    }

    rehashStepFinalize(ht);
}

/* Performs one step of incremental rehashing.
 *
 * Note that a rehashing step consists in moving a bucket and all its child buckets,
 * (that may have more than one key as we use bucket and bucket chaining) from the
 * old to the new hash table, however since part of the hash table may be composed
 * of empty buckets, to speed up the rehashing of empty buckets, we will visit at
 * max n empty buckets in total. */
static void rehashStep(hashtable *ht) {
    assert(hashtableIsRehashing(ht));

    /* In shrinking case, there is a case that the ht0 can be very empty, but the
     * table size is huge, when doing one step rehash, if there are a lot of empty
     * buckets, we can rehash more buckets to make the rehash faster. */
    int empty_visits = 10;
    bucket *b = ht->tables[0] + ht->rehash_idx;
    while (b == NULL) {
        rehashStepFinalize(ht);
        if (!hashtableIsRehashing(ht)) return;
        if (--empty_visits == 0) return;
        b = ht->tables[0] + ht->rehash_idx;
    }

    if (ht->bucket_exp[1] < ht->bucket_exp[0]) {
        rehashStepShrink(ht);
        return;
    }
    rehashStepExpand(ht);
}

/* Called internally on lookup and other reads to the table. */
static inline void rehashStepOnReadIfNeeded(hashtable *ht) {
    if (!hashtableIsRehashing(ht) || ht->pause_rehash) return;
    if (resize_policy != HASHTABLE_RESIZE_ALLOW) return;
    rehashStep(ht);
}

/* When inserting or deleting, we first do a find (read) and rehash one step if
 * resize policy is set to ALLOW, so here we only do it if resize policy is
 * AVOID. The reason for doing it on insert and delete is to ensure that we
 * finish rehashing before we need to resize the table again. */
static inline void rehashStepOnWriteIfNeeded(hashtable *ht) {

Review comment (suggestion):
b is never NULL here. This code will never run.

The condition for empty bucket is `b->presence == 0 && !b->chained`.

But I think we can do this in rehashStepShrink instead, where we already have a bucket variable. I don't like that this code is spread out in so many functions now.

```C
/* Processes one bucket chain during incremental table shrinkage. */
static void rehashStepShrink(hashtable *ht) {
    bucket *b;
    /* find a non-empty bucket, skipping up to 10 empty buckets */
    int empty_visits = 10;
    while (true) {
        size_t idx = ht->rehash_idx;
        b = ht->tables[0] + idx;
        if (b->presence != 0 || b->chained) break; /* non-empty bucket */
        rehashStepFinalize(ht);
        if (!hashtableIsRehashing(ht)) return;
        if (--empty_visits == 0) return;
    }
    while (b != NULL) {
        bucket *next = getChildBucket(b);
        rehashBucketShrink(ht, b);
        b = next;
    }
    rehashStepFinalize(ht);
}
```

Code after:

    /* Find a non-empty bucket, skipping up to 10 empty buckets.
     *
     * In shrinking case, there is a case that the ht0 can be very empty, but the
     * table size is huge, when doing one step rehash, if there are a lot of empty
     * buckets, we can rehash more buckets to make the rehash faster. */
    int empty_visits = 10;
    while (true) {
        size_t idx = ht->rehash_idx;
        b = ht->tables[0] + idx;
        if (b->presence != 0 || b->chained) break; /* non-empty bucket */
        rehashStepFinalize(ht);
        if (!hashtableIsRehashing(ht)) return; /* rehashing completed */
        if (--empty_visits == 0) return;       /* too many empty buckets */
    }

    /* Rehash all the entries in this bucket chain from the old to the new hash HT */
    while (b != NULL) {
        bucket *next = getChildBucket(b);
        rehashBucketShrink(ht, b);
        b = next;
    }

    rehashStepFinalize(ht);
}

/* Performs one step of incremental rehashing.
 *
 * Note that a rehashing step consists in moving a bucket and all its child buckets,
 * (that may have more than one key as we use bucket and bucket chaining) from the
 * old to the new hash table. */
static void rehashStep(hashtable *ht) {
    assert(hashtableIsRehashing(ht));
    if (ht->bucket_exp[1] < ht->bucket_exp[0]) {
        rehashStepShrink(ht);
        return;
    }
    rehashStepExpand(ht);
}

/* Called internally on lookup and other reads to the table. */
static inline void rehashStepOnReadIfNeeded(hashtable *ht) {
    if (!hashtableIsRehashing(ht) || ht->pause_rehash) return;
    if (resize_policy != HASHTABLE_RESIZE_ALLOW) return;
    rehashStep(ht);
}

/* When inserting or deleting, we first do a find (read) and rehash one step if
 * resize policy is set to ALLOW, so here we only do it if resize policy is
 * AVOID. The reason for doing it on insert and delete is to ensure that we
 * finish rehashing before we need to resize the table again. */