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

Code before:
        if (elemptr) {
            *elemptr = b->entries[iter->pos_in_bucket];
        }
        return 1;
    }
    return 0;
}

/* --- Random entries --- */

/* Points 'found' to a random entry in the hash table and returns 1. Returns 0
 * if the table is empty. */
int hashtableRandomEntry(hashtable *ht, void **found) {
    void *samples[WEAK_RANDOM_SAMPLE_SIZE];
    unsigned count = hashtableSampleEntries(ht, &samples[0], WEAK_RANDOM_SAMPLE_SIZE);
    if (count == 0) return 0;
    unsigned idx = random() % count;
    *found = samples[idx];
    return 1;
}

/* Points 'found' to a random entry in the hash table and returns 1. Returns 0
 * if the table is empty. This one is more fair than hashtableRandomEntry(). */
int hashtableFairRandomEntry(hashtable *ht, void **found) {
    void *samples[FAIR_RANDOM_SAMPLE_SIZE];
    unsigned count = hashtableSampleEntries(ht, &samples[0], FAIR_RANDOM_SAMPLE_SIZE);
    if (count == 0) return 0;
    unsigned idx = random() % count;
    *found = samples[idx];
    return 1;
}

/* This function samples a sequence of entries starting at a random location in
 * the hash table.
 *
 * The sampled entries are stored in the array 'dst' which must have space for
 * at least 'count' entries.
 *
 * The function returns the number of sampled entries, which is 'count' except
 * if 'count' is greater than the total number of entries in the hash table. */
unsigned hashtableSampleEntries(hashtable *ht, void **dst, unsigned count) {
    /* Adjust count. */
    if (count > hashtableSize(ht)) count = hashtableSize(ht);
    scan_samples samples;
    samples.size = count;
    samples.seen = 0;
    samples.entries = dst;
    size_t cursor = randomSizeT();
    while (samples.seen < count) {
        cursor = hashtableScan(ht, cursor, sampleEntriesScanFn, &samples);
    }

Review comment (suggestion):
This `hashtableSize(ht) >= hashtableBuckets(ht)` expression in my testing barely ever evaluates to false and when it does, we're typically already (or about to be) in the process of rehashing the hashtable to a smaller size. It doesn't hurt to reduce the sampling rate during this time, just figured it was worth a note in case this logic was intended to be different.

Code after:
        if (elemptr) {
            *elemptr = b->entries[iter->pos_in_bucket];
        }
        return 1;
    }
    return 0;
}

/* --- Random entries --- */

/* Points 'found' to a random entry in the hash table and returns 1. Returns 0
 * if the table is empty. */
int hashtableRandomEntry(hashtable *ht, void **found) {
    void *samples[WEAK_RANDOM_SAMPLE_SIZE];
    unsigned count = hashtableSampleEntries(ht, &samples[0], WEAK_RANDOM_SAMPLE_SIZE);
    if (count == 0) return 0;
    unsigned idx = random() % count;
    *found = samples[idx];
    return 1;
}

/* Points 'found' to a random entry in the hash table and returns 1. Returns 0
 * if the table is empty. This one is more fair than hashtableRandomEntry(). */
int hashtableFairRandomEntry(hashtable *ht, void **found) {
    /* Sample less if it's very sparse. */
    size_t num_samples = hashtableSize(ht) >= hashtableBuckets(ht) ? FAIR_RANDOM_SAMPLE_SIZE : WEAK_RANDOM_SAMPLE_SIZE;
    void *samples[num_samples];
    unsigned count = hashtableSampleEntries(ht, &samples[0], num_samples);
    if (count == 0) return 0;
    unsigned idx = random() % count;
    *found = samples[idx];
    return 1;
}

/* This function samples a sequence of entries starting at a random location in
 * the hash table.
 *
 * The sampled entries are stored in the array 'dst' which must have space for
 * at least 'count' entries.
 *
 * The function returns the number of sampled entries, which is 'count' except
 * if 'count' is greater than the total number of entries in the hash table. */
unsigned hashtableSampleEntries(hashtable *ht, void **dst, unsigned count) {
    /* Adjust count. */
    if (count > hashtableSize(ht)) count = hashtableSize(ht);
    scan_samples samples;
    samples.size = count;
    samples.seen = 0;
    samples.entries = dst;
    while (samples.seen < count) {
        hashtableScan(ht, randomSizeT(), sampleEntriesScanFn, &samples);