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

Code before:
        }
    }
    return 1;
}

/* Returns 1 if the table is expanded, 0 if not expanded. If 0 is returned and
 * 'malloc_failed' is provided, it is set to 1 if malloc failed and 0
 * otherwise. */
static int expand(hashtable *ht, size_t size, int *malloc_failed) {
    if (size < hashtableSize(ht)) {
        return 0;
    }
    return resize(ht, size, malloc_failed);
}

/* Finds an entry matching the key. If a match is found, returns a pointer to
 * the bucket containing the matching entry and points 'pos_in_bucket' to the
 * index within the bucket. Returns NULL if no matching entry was found.
 *
 * If 'table_index' is provided, it is set to the index of the table (0 or 1)
 * the returned bucket belongs to. */
#if HAVE_X86_SIMD
#include <immintrin.h>
ATTRIBUTE_TARGET_SSE2
#endif
static bucket *findBucket(hashtable *ht, uint64_t hash, const void *key, int *pos_in_bucket, int *table_index) {
    if (hashtableSize(ht) == 0) return 0;
    uint8_t h2 = highBits(hash);
    int table;

    /* Do some incremental rehashing. */
    rehashStepOnReadIfNeeded(ht);

    for (table = 0; table <= 1; table++) {
        if (ht->used[table] == 0) continue;
        size_t mask = expToMask(ht->bucket_exp[table]);
        size_t bucket_idx = hash & mask;
        /* Skip already rehashed buckets. */
        if (table == 0 && ht->rehash_idx >= 0 && bucket_idx < (size_t)ht->rehash_idx) {
            continue;
        }
        bucket *b = &ht->tables[table][bucket_idx];
        do {
#if HAVE_X86_SIMD
            if (__builtin_cpu_supports("sse2")) {
                /* Get the bucket's presence mask - indicates which positions are filled. */
                BUCKET_BITS_TYPE presence_mask = b->presence & ((1 << ENTRIES_PER_BUCKET) - 1);
                __m128i hash_vector = _mm_loadu_si128((__m128i *)b->hashes);
                __m128i h2_vector = _mm_set1_epi8(h2);
                /* Compare all hash values against the target hash simultaneously.
                 * The result is a vector of 16 bytes, where each byte is 0xFF if

Review comment (suggestion):
Let's do the `#include` near the top of the file with the other includes.

Regarding the attribute, if we add the SSE2 attribute here, the compiler is free to generate SSE2 instructions even for the code that is not explicitly using the `_mm` functions, right? It seems to me that all code marked with the attribute should be guarded with a runtime check, in general.

Code after:
    } else if (ht->type->instant_rehashing) {
        while (hashtableIsRehashing(ht)) {
            rehashStep(ht);
        }
    }
    return 1;
}

/* Returns 1 if the table is expanded, 0 if not expanded. If 0 is returned and
 * 'malloc_failed' is provided, it is set to 1 if malloc failed and 0
 * otherwise. */
static int expand(hashtable *ht, size_t size, int *malloc_failed) {
    if (size < hashtableSize(ht)) {
        return 0;
    }
    return resize(ht, size, malloc_failed);
}

/* Checks if a candidate entry in a bucket matches the given key.
 *
 * This function examines a specific position in a bucket to determine if the
 * entry at that position matches the provided key. If a match is found, it
 * updates the position and table index pointers and returns 1. Otherwise,
 * it returns 0. */
static inline int checkCandidateInBucket(hashtable *ht, bucket *b, int pos, const void *key, int table, int *pos_in_bucket, int *table_index) {
    /* It's a candidate. */
    void *entry = b->entries[pos];
    const void *elem_key = entryGetKey(ht, entry);
    if (compareKeys(ht, key, elem_key) == 0) {
        /* It's a match. */
        assert(pos_in_bucket != NULL);
        *pos_in_bucket = pos;
        if (table_index) *table_index = table;
        return 1;
    }
    return 0;
}

#if HAVE_X86_SIMD
ATTRIBUTE_TARGET_SSE2
static int findKeyInBucketSSE2(hashtable *ht, bucket *b, uint8_t h2, const void *key, int table, int *pos_in_bucket, int *table_index) {
    /* Get the bucket's presence mask - indicates which positions are filled. */
    BUCKET_BITS_TYPE presence_mask = b->presence & ((1 << ENTRIES_PER_BUCKET) - 1);
    __m128i hash_vector = _mm_loadu_si128((__m128i *)b->hashes);
    __m128i h2_vector = _mm_set1_epi8(h2);
    /* Compare all hash values against the target hash simultaneously.
     * The result is a vector of 16 bytes, where each byte is 0xFF if
     * the corresponding hash matches the target hash, and 0x00 if it
     * doesn't. */
    __m128i result = _mm_cmpeq_epi8(hash_vector, h2_vector);
    BUCKET_BITS_TYPE newmask = _mm_movemask_epi8(result);