1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
#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);
}
|
