ydb/util/generic/hash_primes.cpp

#include "hash_primes.h"
#include "array_size.h"
#include "algorithm.h"

/// Order of fields: reciprocal, reciprocal shift, adjacent hint, divisor
#if defined(_32_)
static constexpr ::NPrivate::THashDivisor PRIME_DIVISORS_HOLDER[]{
    {0x00000000u, 0u, -1, 0xffffffffu}, // guard value, not a valid divisor
    {0x24924925u, 2u, 0, 7u},
    {0xe1e1e1e2u, 4u, 1, 17u},
    {0x1a7b9612u, 4u, 2, 29u},
    {0x3521cfb3u, 5u, 3, 53u},
    {0x51d07eafu, 6u, 4, 97u},
    {0x53909490u, 7u, 5, 193u},
    {0x50f22e12u, 8u, 6, 389u},
    {0x54e3b41au, 9u, 7, 769u},
    {0x53c8eaeeu, 10u, 8, 1543u},
    {0x548eacc6u, 11u, 9, 3079u},
    {0x54f1e41eu, 12u, 10, 6151u},
    {0x554e390au, 13u, 11, 12289u},
    {0x5518ee41u, 14u, 12, 24593u},
    {0x554c7203u, 15u, 13, 49157u},
    {0x5549c781u, 16u, 14, 98317u},
    {0x55531c76u, 17u, 15, 196613u},
    {0x554fc734u, 18u, 16, 393241u},
    {0x555538e4u, 19u, 17, 786433u},
    {0x55550e39u, 20u, 18, 1572869u},
    {0x5555071du, 21u, 19, 3145739u},
    {0x5555271du, 22u, 20, 6291469u},
    {0x55554c72u, 23u, 21, 12582917u},
    {0x55554472u, 24u, 22, 25165843u},
    {0x5555531du, 25u, 23, 50331653u},
    {0x55555039u, 26u, 24, 100663319u},
    {0x55555339u, 27u, 25, 201326611u},
    {0x5555550fu, 28u, 26, 402653189u},
    {0x555552ddu, 29u, 27, 805306457u},
    {0x55555544u, 30u, 28, 1610612741u},
    {0x55555554u, 31u, 29, 3221225473u},
    {0x00000006u, 31u, 30, 4294967291u},
};
#else
static constexpr ::NPrivate::THashDivisor PRIME_DIVISORS_HOLDER[]{
    {0x0000000000000000ul, 0u, -1, 0xffffffffu}, // guard value, not a valid divisor
    {0x2492492492492493ul, 2u, 0, 7u},
    {0xe1e1e1e1e1e1e1e2ul, 4u, 1, 17u},
    {0x1a7b9611a7b9611bul, 4u, 2, 29u},
    {0x3521cfb2b78c1353ul, 5u, 3, 53u},
    {0x51d07eae2f8151d1ul, 6u, 4, 97u},
    {0x5390948f40feac70ul, 7u, 5, 193u},
    {0x50f22e111c4c56dful, 8u, 6, 389u},
    {0x54e3b4194ce65de1ul, 9u, 7, 769u},
    {0x53c8eaedea6e7f17ul, 10u, 8, 1543u},
    {0x548eacc5e1e6e3fcul, 11u, 9, 3079u},
    {0x54f1e41d7767d70cul, 12u, 10, 6151u},
    {0x554e39097a781d80ul, 13u, 11, 12289u},
    {0x5518ee4079ea6929ul, 14u, 12, 24593u},
    {0x554c72025d459231ul, 15u, 13, 49157u},
    {0x5549c78094504ff3ul, 16u, 14, 98317u},
    {0x55531c757b3c329cul, 17u, 15, 196613u},
    {0x554fc7339753b424ul, 18u, 16, 393241u},
    {0x555538e39097b3f4ul, 19u, 17, 786433u},
    {0x55550e38f25ecd82ul, 20u, 18, 1572869u},
    {0x5555071c83b421d2ul, 21u, 19, 3145739u},
    {0x5555271c78097a6aul, 22u, 20, 6291469u},
    {0x55554c71c757b425ul, 23u, 21, 12582917u},
    {0x55554471c7f25ec7ul, 24u, 22, 25165843u},
    {0x5555531c71cad098ul, 25u, 23, 50331653u},
    {0x55555038e3a1d098ul, 26u, 24, 100663319u},
    {0x55555338e3919098ul, 27u, 25, 201326611u},
    {0x5555550e38e39d0aul, 28u, 26, 402653189u},
    {0x555552dc71cbb1eeul, 29u, 27, 805306457u},
    {0x555555438e38e47cul, 30u, 28, 1610612741u},
    {0x555555538e38e391ul, 31u, 29, 3221225473u},
    {0x000000050000001aul, 31u, 30, 4294967291u},
};
#endif

static constexpr const ::NPrivate::THashDivisor* PRIME_DIVISORS = &PRIME_DIVISORS_HOLDER[1]; ///< Address of the first valid divisor
static constexpr size_t PRIME_DIVISORS_SIZE = Y_ARRAY_SIZE(PRIME_DIVISORS_HOLDER) - 1;       ///< Number of valid divisors without the guarding value

unsigned long HashBucketCount(unsigned long elementCount) {
    return HashBucketCountExt(elementCount)();
}

static inline ::NPrivate::THashDivisor HashBucketBoundedSearch(unsigned long elementCount) {
    const auto begin = PRIME_DIVISORS;
    const auto end = PRIME_DIVISORS + PRIME_DIVISORS_SIZE - 1; // adjust range so the last element will be returned if elementCount is bigger than all PRIME_DIVISORS
    return *LowerBoundBy(begin, end, elementCount, std::mem_fn(&::NPrivate::THashDivisor::Divisor));
}

Y_CONST_FUNCTION
::NPrivate::THashDivisor HashBucketCountExt(unsigned long elementCount) {
    if (elementCount <= PRIME_DIVISORS[0]()) {
        return PRIME_DIVISORS[0];
    }

    return HashBucketBoundedSearch(elementCount);
}

Y_CONST_FUNCTION
::NPrivate::THashDivisor HashBucketCountExt(unsigned long elementCount, int hint) {
    if (Y_LIKELY(static_cast<size_t>(hint) < PRIME_DIVISORS_SIZE)) {
        const int index = hint;
        const ::NPrivate::THashDivisor* cnd = PRIME_DIVISORS + index;
        if (Y_LIKELY(elementCount <= cnd->Divisor)) {
            const ::NPrivate::THashDivisor* prev = cnd - 1;
            static_assert(~PRIME_DIVISORS[-1].Divisor == 0, "Invalid guard");
            /*
            If index == 0 then PRIME_DIVISORS[0] should be returned.
            Otherwise `cnd` is correct value iff (prev->Divisor < elementCount).
            Ergo hint is correct if (index == 0 || prev->Divisor < elementCount);
            But we can set guard's value to -1 and check both conditions at once.
            */
            if (Y_LIKELY(prev->Divisor + 1u <= elementCount)) {
                return *cnd;
            }
        }
    }

    return HashBucketBoundedSearch(elementCount);
}