Debian Codegraph @

third_party/hat-trie/tsl/array-hash/array_growth_policy.h

raw
1 /**
2 * MIT License
3 *
4 * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <[email protected]>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24 #ifndef TSL_ARRAY_GROWTH_POLICY_H
25 #define TSL_ARRAY_GROWTH_POLICY_H
26
27
28 #include <algorithm>
29 #include <array>
30 #include <climits>
31 #include <cmath>
32 #include <cstddef>
33 #include <iterator>
34 #include <limits>
35 #include <ratio>
36 #include <stdexcept>
37
38
39 #ifdef __EXCEPTIONS
40 # define THROW(_e, _m) throw _e(_m)
41 #else
42 # include <stdio.h>
43 # ifndef NDEBUG
44 # define THROW(_e, _m) do { fprintf(stderr, _m); std::terminate(); } while(0)
45 # else
46 # define THROW(_e, _m) std::terminate()
47 # endif
48 #endif
49
50
51 namespace tsl {
52 namespace ah {
53
54 /**
55 * Grow the hash table by a factor of GrowthFactor keeping the bucket count to a power of two. It allows
56 * the table to use a mask operation instead of a modulo operation to map a hash to a bucket.
57 *
58 * GrowthFactor must be a power of two >= 2.
59 */
60 template<std::size_t GrowthFactor>
61 class power_of_two_growth_policy {
62 public:
63 /**
64 * Called on the hash table creation and on rehash. The number of buckets for the table is passed in parameter.
65 * This number is a minimum, the policy may update this value with a higher value if needed (but not lower).
66 *
67 * If 0 is given, min_bucket_count_in_out must still be 0 after the policy creation and
68 * bucket_for_hash must always return 0 in this case.
69 */
70 explicit power_of_two_growth_policy(std::size_t& min_bucket_count_in_out) {
71 if(min_bucket_count_in_out > max_bucket_count()) {
72 THROW(std::length_error, "The hash table exceeds its maximum size.");
73 }
74
75 if(min_bucket_count_in_out > 0) {
76 min_bucket_count_in_out = round_up_to_power_of_two(min_bucket_count_in_out);
77 m_mask = min_bucket_count_in_out - 1;
78 }
79 else {
80 m_mask = 0;
81 }
82 }
83
84 /**
85 * Return the bucket [0, bucket_count()) to which the hash belongs.
86 * If bucket_count() is 0, it must always return 0.
87 */
88 std::size_t bucket_for_hash(std::size_t hash) const noexcept {
89 return hash & m_mask;
90 }
91
92 /**
93 * Return the number of buckets that should be used on next growth.
94 */
95 std::size_t next_bucket_count() const {
96 if((m_mask + 1) > max_bucket_count() / GrowthFactor) {
97 THROW(std::length_error, "The hash table exceeds its maximum size.");
98 }
99
100 return (m_mask + 1) * GrowthFactor;
101 }
102
103 /**
104 * Return the maximum number of buckets supported by the policy.
105 */
106 std::size_t max_bucket_count() const {
107 // Largest power of two.
108 return (std::numeric_limits<std::size_t>::max() / 2) + 1;
109 }
110
111 /**
112 * Reset the growth policy as if it was created with a bucket count of 0.
113 * After a clear, the policy must always return 0 when bucket_for_hash is called.
114 */
115 void clear() noexcept {
116 m_mask = 0;
117 }
118
119 private:
120 static std::size_t round_up_to_power_of_two(std::size_t value) {
121 if(is_power_of_two(value)) {
122 return value;
123 }
124
125 if(value == 0) {
126 return 1;
127 }
128
129 --value;
130 for(std::size_t i = 1; i < sizeof(std::size_t) * CHAR_BIT; i *= 2) {
131 value |= value >> i;
132 }
133
134 return value + 1;
135 }
136
137 static constexpr bool is_power_of_two(std::size_t value) {
138 return value != 0 && (value & (value - 1)) == 0;
139 }
140
141 protected:
142 static_assert(is_power_of_two(GrowthFactor) && GrowthFactor >= 2, "GrowthFactor must be a power of two >= 2.");
143
144 std::size_t m_mask;
145 };
146
147
148 /**
149 * Grow the hash table by GrowthFactor::num / GrowthFactor::den and use a modulo to map a hash
150 * to a bucket. Slower but it can be useful if you want a slower growth.
151 */
152 template<class GrowthFactor = std::ratio<3, 2>>
153 class mod_growth_policy {
154 public:
155 explicit mod_growth_policy(std::size_t& min_bucket_count_in_out) {
156 if(min_bucket_count_in_out > max_bucket_count()) {
157 THROW(std::length_error, "The hash table exceeds its maximum size.");
158 }
159
160 if(min_bucket_count_in_out > 0) {
161 m_mod = min_bucket_count_in_out;
162 }
163 else {
164 m_mod = 1;
165 }
166 }
167
168 std::size_t bucket_for_hash(std::size_t hash) const noexcept {
169 return hash % m_mod;
170 }
171
172 std::size_t next_bucket_count() const {
173 if(m_mod == max_bucket_count()) {
174 THROW(std::length_error, "The hash table exceeds its maximum size.");
175 }
176
177 const double next_bucket_count = std::ceil(double(m_mod) * REHASH_SIZE_MULTIPLICATION_FACTOR);
178 if(!std::isnormal(next_bucket_count)) {
179 THROW(std::length_error, "The hash table exceeds its maximum size.");
180 }
181
182 if(next_bucket_count > double(max_bucket_count())) {
183 return max_bucket_count();
184 }
185 else {
186 return std::size_t(next_bucket_count);
187 }
188 }
189
190 std::size_t max_bucket_count() const {
191 return MAX_BUCKET_COUNT;
192 }
193
194 void clear() noexcept {
195 m_mod = 1;
196 }
197
198 private:
199 static constexpr double REHASH_SIZE_MULTIPLICATION_FACTOR = 1.0 * GrowthFactor::num / GrowthFactor::den;
200 static const std::size_t MAX_BUCKET_COUNT =
201 std::size_t(double(
202 std::numeric_limits<std::size_t>::max() / REHASH_SIZE_MULTIPLICATION_FACTOR
203 ));
204
205 static_assert(REHASH_SIZE_MULTIPLICATION_FACTOR >= 1.1, "Growth factor should be >= 1.1.");
206
207 std::size_t m_mod;
208 };
209
210
211
212 namespace detail {
213
214 static constexpr const std::array<std::size_t, 40> PRIMES = {{
215 1ul, 5ul, 17ul, 29ul, 37ul, 53ul, 67ul, 79ul, 97ul, 131ul, 193ul, 257ul, 389ul, 521ul, 769ul, 1031ul,
216 1543ul, 2053ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
217 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul,
218 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
219 }};
220
221 template<unsigned int IPrime>
222 static constexpr std::size_t mod(std::size_t hash) { return hash % PRIMES[IPrime]; }
223
224 // MOD_PRIME[iprime](hash) returns hash % PRIMES[iprime]. This table allows for faster modulo as the
225 // compiler can optimize the modulo code better with a constant known at the compilation.
226 static constexpr const std::array<std::size_t(*)(std::size_t), 40> MOD_PRIME = {{
227 &mod<0>, &mod<1>, &mod<2>, &mod<3>, &mod<4>, &mod<5>, &mod<6>, &mod<7>, &mod<8>, &mod<9>, &mod<10>,
228 &mod<11>, &mod<12>, &mod<13>, &mod<14>, &mod<15>, &mod<16>, &mod<17>, &mod<18>, &mod<19>, &mod<20>,
229 &mod<21>, &mod<22>, &mod<23>, &mod<24>, &mod<25>, &mod<26>, &mod<27>, &mod<28>, &mod<29>, &mod<30>,
230 &mod<31>, &mod<32>, &mod<33>, &mod<34>, &mod<35>, &mod<36>, &mod<37> , &mod<38>, &mod<39>
231 }};
232
233 }
234
235 /**
236 * Grow the hash table by using prime numbers as bucket count. Slower than tsl::ah::power_of_two_growth_policy in
237 * general but will probably distribute the values around better in the buckets with a poor hash function.
238 *
239 * To allow the compiler to optimize the modulo operation, a lookup table is used with constant primes numbers.
240 *
241 * With a switch the code would look like:
242 * \code
243 * switch(iprime) { // iprime is the current prime of the hash table
244 * case 0: hash % 5ul;
245 * break;
246 * case 1: hash % 17ul;
247 * break;
248 * case 2: hash % 29ul;
249 * break;
250 * ...
251 * }
252 * \endcode
253 *
254 * Due to the constant variable in the modulo the compiler is able to optimize the operation
255 * by a series of multiplications, substractions and shifts.
256 *
257 * The 'hash % 5' could become something like 'hash - (hash * 0xCCCCCCCD) >> 34) * 5' in a 64 bits environment.
258 */
259 class prime_growth_policy {
260 public:
261 explicit prime_growth_policy(std::size_t& min_bucket_count_in_out) {
262 auto it_prime = std::lower_bound(detail::PRIMES.begin(),
263 detail::PRIMES.end(), min_bucket_count_in_out);
264 if(it_prime == detail::PRIMES.end()) {
265 THROW(std::length_error, "The hash table exceeds its maximum size.");
266 }
267
268 m_iprime = static_cast<unsigned int>(std::distance(detail::PRIMES.begin(), it_prime));
269 if(min_bucket_count_in_out > 0) {
270 min_bucket_count_in_out = *it_prime;
271 }
272 else {
273 min_bucket_count_in_out = 0;
274 }
275 }
276
277 std::size_t bucket_for_hash(std::size_t hash) const noexcept {
278 return detail::MOD_PRIME[m_iprime](hash);
279 }
280
281 std::size_t next_bucket_count() const {
282 if(m_iprime + 1 >= detail::PRIMES.size()) {
283 THROW(std::length_error, "The hash table exceeds its maximum size.");
284 }
285
286 return detail::PRIMES[m_iprime + 1];
287 }
288
289 std::size_t max_bucket_count() const {
290 return detail::PRIMES.back();
291 }
292
293 void clear() noexcept {
294 m_iprime = 0;
295 }
296
297 private:
298 unsigned int m_iprime;
299
300 static_assert(std::numeric_limits<decltype(m_iprime)>::max() >= detail::PRIMES.size(),
301 "The type of m_iprime is not big enough.");
302 };
303
304 }
305 }
306
307 #endif