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

Code before:
    /* Populate and make sure there is no rehashing ongoing. */
    for (j = 0; j < 1000; j++) {
        TEST_ASSERT(hashtableAdd(ht, (void *)j));
    }
    while (hashtableIsRehashing(ht)) {
        TEST_ASSERT(!hashtableAdd(ht, (void *)0));
    }

    /* Delete all elements except for one so there are a lot of empty buckets. */
    hashtablePauseAutoShrink(ht);
    for (j = 0; j < 1000 - 1; j++) {
        TEST_ASSERT(hashtableDelete(ht, (void *)j));
    }
    hashtableResumeAutoShrink(ht);
    TEST_ASSERT(hashtableSize(ht) == 1);
    TEST_ASSERT(hashtableGetRehashingIndex(ht) == 0);

    /* Add elements to trigger rehashing, a rehash step will rehash a maximum of 10 buckets. */
    for (j = 0; j < 10; j++) {
        TEST_ASSERT(hashtableAdd(ht, (void *)j));
    }
    TEST_ASSERT(hashtableSize(ht) == 11);
    /* Only assert on 64-bit build. */
    if (sizeof(long) == 8) {
        TEST_ASSERT(hashtableGetRehashingIndex(ht) >= 90 && hashtableGetRehashingIndex(ht) <= 100);
    }

    hashtableRelease(ht);
    return 0;
}

int test_bucket_chain_length(int argc, char **argv, int flags) {
    UNUSED(argc);
    UNUSED(argv);
    UNUSED(flags);

    unsigned long count = 1000000;

    /* A set of longs, i.e. pointer-sized integer values. */
    hashtableType type = {0};
    hashtable *ht = hashtableCreate(&type);
    unsigned long j;
    for (j = 0; j < count; j++) {
        TEST_ASSERT(hashtableAdd(ht, (void *)j));
    }
    /* If it's rehashing, add a few more until rehashing is complete.
     * We also make sure that we won't resize during the rehashing. */
    while (hashtableIsRehashing(ht)) {
        TEST_ASSERT(!hashtableExpand(ht, count * 2));
        j++;
        TEST_ASSERT(hashtableAdd(ht, (void *)j));

Review comment (bug):
Did it fail on 32-bit?

In the 32-bit representation, there are up to 12 elements per bucket, so I guess it's already completed in 32-bit mode.

We can make it independent of 32/64 bit if we also allow that rehashing has completed. Do you need to check an upper bound, then we can use 150 instead of 100.

```suggestion
    /* Check that at least 90 buckets are rehashed or that rehashing is completed. */
    TEST_ASSERT(hashtableGetRehashingIndex(ht) >= 90 || hashtableGetRehashingIndex(ht) == -1);
```

Code after:
    /* Populate and make sure there is no rehashing ongoing. */
    for (j = 0; j < 1000; j++) {
        TEST_ASSERT(hashtableAdd(ht, (void *)j));
    }
    while (hashtableIsRehashing(ht)) {
        TEST_ASSERT(!hashtableAdd(ht, (void *)0));
    }

    /* Delete all elements except for one so there are a lot of empty buckets. */
    hashtablePauseAutoShrink(ht);
    for (j = 0; j < 1000 - 1; j++) {
        TEST_ASSERT(hashtableDelete(ht, (void *)j));
    }
    hashtableResumeAutoShrink(ht);
    TEST_ASSERT(hashtableSize(ht) == 1);
    TEST_ASSERT(hashtableGetRehashingIndex(ht) == 0);

    /* Add elements to trigger rehashing, a rehash step will rehash a maximum of 10 buckets. */
    for (j = 0; j < 10; j++) {
        TEST_ASSERT(hashtableAdd(ht, (void *)j));
    }
    TEST_ASSERT(hashtableSize(ht) == 11);
    /* Check that at least 90 buckets are rehashed or that rehashing is completed. */
    TEST_ASSERT(hashtableGetRehashingIndex(ht) >= 90 || hashtableGetRehashingIndex(ht) == -1);

    hashtableRelease(ht);
    return 0;
}

int test_bucket_chain_length(int argc, char **argv, int flags) {
    UNUSED(argc);
    UNUSED(argv);
    UNUSED(flags);

    unsigned long count = 1000000;

    /* A set of longs, i.e. pointer-sized integer values. */
    hashtableType type = {0};
    hashtable *ht = hashtableCreate(&type);
    unsigned long j;
    for (j = 0; j < count; j++) {
        TEST_ASSERT(hashtableAdd(ht, (void *)j));
    }
    /* If it's rehashing, add a few more until rehashing is complete.
     * We also make sure that we won't resize during the rehashing. */
    while (hashtableIsRehashing(ht)) {
        TEST_ASSERT(!hashtableExpand(ht, count * 2));
        j++;
        TEST_ASSERT(hashtableAdd(ht, (void *)j));
    }
    TEST_ASSERT(j < count * 2);