1 | // Taken from |
2 | // https://github.com/skarupke/flat_hash_map/blob/2c4687431f978f02a3780e24b8b701d22aa32d9c/flat_hash_map.hpp |
3 | // with fixes applied: |
4 | // - https://github.com/skarupke/flat_hash_map/pull/25 |
5 | // - https://github.com/skarupke/flat_hash_map/pull/26 |
6 | // - replace size_t with uint64_t to fix it for 32bit |
7 | // - add "GCC diagnostic" pragma to ignore -Wshadow |
8 | // - make sherwood_v3_table::convertible_to_iterator public because GCC5 seems |
9 | // to have issues with it otherwise |
10 | // - fix compiler warnings in operator templated_iterator<const value_type> |
11 | |
12 | // Copyright Malte Skarupke 2017. |
13 | // Distributed under the Boost Software License, Version 1.0. |
14 | // (See http://www.boost.org/LICENSE_1_0.txt) |
15 | |
16 | #pragma once |
17 | |
18 | #include <c10/macros/Macros.h> |
19 | #include <algorithm> |
20 | #include <cmath> |
21 | #include <cstddef> |
22 | #include <cstdint> |
23 | #include <functional> |
24 | #include <iterator> |
25 | #include <stdexcept> |
26 | #include <type_traits> |
27 | #include <utility> |
28 | |
29 | C10_CLANG_DIAGNOSTIC_PUSH() |
30 | #if C10_CLANG_HAS_WARNING("-Wimplicit-int-float-conversion") |
31 | C10_CLANG_DIAGNOSTIC_IGNORE("-Wimplicit-int-float-conversion" ) |
32 | #endif |
33 | |
34 | #ifdef _MSC_VER |
35 | #define SKA_NOINLINE(...) __declspec(noinline) __VA_ARGS__ |
36 | #else |
37 | #define SKA_NOINLINE(...) __VA_ARGS__ __attribute__((noinline)) |
38 | #endif |
39 | |
40 | namespace ska { |
41 | struct prime_number_hash_policy; |
42 | struct power_of_two_hash_policy; |
43 | struct fibonacci_hash_policy; |
44 | |
45 | namespace detailv3 { |
46 | template <typename Result, typename Functor> |
47 | struct functor_storage : Functor { |
48 | functor_storage() = default; |
49 | functor_storage(const Functor& functor) : Functor(functor) {} |
50 | template <typename... Args> |
51 | Result operator()(Args&&... args) { |
52 | return static_cast<Functor&>(*this)(std::forward<Args>(args)...); |
53 | } |
54 | template <typename... Args> |
55 | Result operator()(Args&&... args) const { |
56 | return static_cast<const Functor&>(*this)(std::forward<Args>(args)...); |
57 | } |
58 | }; |
59 | template <typename Result, typename... Args> |
60 | struct functor_storage<Result, Result (*)(Args...)> { |
61 | typedef Result (*function_ptr)(Args...); |
62 | function_ptr function; |
63 | functor_storage(function_ptr function) : function(function) {} |
64 | Result operator()(Args... args) const { |
65 | return function(std::forward<Args>(args)...); |
66 | } |
67 | operator function_ptr&() { |
68 | return function; |
69 | } |
70 | operator const function_ptr&() { |
71 | return function; |
72 | } |
73 | }; |
74 | template <typename key_type, typename value_type, typename hasher> |
75 | struct KeyOrValueHasher : functor_storage<uint64_t, hasher> { |
76 | typedef functor_storage<uint64_t, hasher> hasher_storage; |
77 | KeyOrValueHasher() = default; |
78 | KeyOrValueHasher(const hasher& hash) : hasher_storage(hash) {} |
79 | uint64_t operator()(const key_type& key) { |
80 | return static_cast<hasher_storage&>(*this)(key); |
81 | } |
82 | uint64_t operator()(const key_type& key) const { |
83 | return static_cast<const hasher_storage&>(*this)(key); |
84 | } |
85 | uint64_t operator()(const value_type& value) { |
86 | return static_cast<hasher_storage&>(*this)(value.first); |
87 | } |
88 | uint64_t operator()(const value_type& value) const { |
89 | return static_cast<const hasher_storage&>(*this)(value.first); |
90 | } |
91 | template <typename F, typename S> |
92 | uint64_t operator()(const std::pair<F, S>& value) { |
93 | return static_cast<hasher_storage&>(*this)(value.first); |
94 | } |
95 | template <typename F, typename S> |
96 | uint64_t operator()(const std::pair<F, S>& value) const { |
97 | return static_cast<const hasher_storage&>(*this)(value.first); |
98 | } |
99 | }; |
100 | template <typename key_type, typename value_type, typename key_equal> |
101 | struct KeyOrValueEquality : functor_storage<bool, key_equal> { |
102 | typedef functor_storage<bool, key_equal> equality_storage; |
103 | KeyOrValueEquality() = default; |
104 | KeyOrValueEquality(const key_equal& equality) : equality_storage(equality) {} |
105 | bool operator()(const key_type& lhs, const key_type& rhs) { |
106 | return static_cast<equality_storage&>(*this)(lhs, rhs); |
107 | } |
108 | bool operator()(const key_type& lhs, const value_type& rhs) { |
109 | return static_cast<equality_storage&>(*this)(lhs, rhs.first); |
110 | } |
111 | bool operator()(const value_type& lhs, const key_type& rhs) { |
112 | return static_cast<equality_storage&>(*this)(lhs.first, rhs); |
113 | } |
114 | bool operator()(const value_type& lhs, const value_type& rhs) { |
115 | return static_cast<equality_storage&>(*this)(lhs.first, rhs.first); |
116 | } |
117 | template <typename F, typename S> |
118 | bool operator()(const key_type& lhs, const std::pair<F, S>& rhs) { |
119 | return static_cast<equality_storage&>(*this)(lhs, rhs.first); |
120 | } |
121 | template <typename F, typename S> |
122 | bool operator()(const std::pair<F, S>& lhs, const key_type& rhs) { |
123 | return static_cast<equality_storage&>(*this)(lhs.first, rhs); |
124 | } |
125 | template <typename F, typename S> |
126 | bool operator()(const value_type& lhs, const std::pair<F, S>& rhs) { |
127 | return static_cast<equality_storage&>(*this)(lhs.first, rhs.first); |
128 | } |
129 | template <typename F, typename S> |
130 | bool operator()(const std::pair<F, S>& lhs, const value_type& rhs) { |
131 | return static_cast<equality_storage&>(*this)(lhs.first, rhs.first); |
132 | } |
133 | template <typename FL, typename SL, typename FR, typename SR> |
134 | bool operator()(const std::pair<FL, SL>& lhs, const std::pair<FR, SR>& rhs) { |
135 | return static_cast<equality_storage&>(*this)(lhs.first, rhs.first); |
136 | } |
137 | }; |
138 | static constexpr int8_t min_lookups = 4; |
139 | template <typename T> |
140 | struct sherwood_v3_entry { |
141 | sherwood_v3_entry() = default; |
142 | sherwood_v3_entry(int8_t distance_from_desired) |
143 | : distance_from_desired(distance_from_desired) {} |
144 | ~sherwood_v3_entry() = default; |
145 | |
146 | bool has_value() const { |
147 | return distance_from_desired >= 0; |
148 | } |
149 | bool is_empty() const { |
150 | return distance_from_desired < 0; |
151 | } |
152 | bool is_at_desired_position() const { |
153 | return distance_from_desired <= 0; |
154 | } |
155 | template <typename... Args> |
156 | void emplace(int8_t distance, Args&&... args) { |
157 | new (std::addressof(value)) T(std::forward<Args>(args)...); |
158 | distance_from_desired = distance; |
159 | } |
160 | |
161 | void destroy_value() { |
162 | value.~T(); |
163 | distance_from_desired = -1; |
164 | } |
165 | |
166 | int8_t distance_from_desired = -1; |
167 | static constexpr int8_t special_end_value = 0; |
168 | union { |
169 | T value; |
170 | }; |
171 | }; |
172 | |
173 | inline int8_t log2(uint64_t value) { |
174 | static constexpr int8_t table[64] = { |
175 | 63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, |
176 | 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, |
177 | 62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, |
178 | 56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5}; |
179 | value |= value >> 1; |
180 | value |= value >> 2; |
181 | value |= value >> 4; |
182 | value |= value >> 8; |
183 | value |= value >> 16; |
184 | value |= value >> 32; |
185 | return table[((value - (value >> 1)) * 0x07EDD5E59A4E28C2) >> 58]; |
186 | } |
187 | |
188 | template <typename T, bool> |
189 | struct AssignIfTrue { |
190 | void operator()(T& lhs, const T& rhs) { |
191 | lhs = rhs; |
192 | } |
193 | void operator()(T& lhs, T&& rhs) { |
194 | lhs = std::move(rhs); |
195 | } |
196 | }; |
197 | template <typename T> |
198 | struct AssignIfTrue<T, false> { |
199 | void operator()(T&, const T&) {} |
200 | void operator()(T&, T&&) {} |
201 | }; |
202 | |
203 | inline uint64_t next_power_of_two(uint64_t i) { |
204 | --i; |
205 | i |= i >> 1; |
206 | i |= i >> 2; |
207 | i |= i >> 4; |
208 | i |= i >> 8; |
209 | i |= i >> 16; |
210 | i |= i >> 32; |
211 | ++i; |
212 | return i; |
213 | } |
214 | |
215 | // Implementation taken from http://en.cppreference.com/w/cpp/types/void_t |
216 | // (it takes CWG1558 into account and also works for older compilers) |
217 | template <typename... Ts> |
218 | struct make_void { |
219 | typedef void type; |
220 | }; |
221 | template <typename... Ts> |
222 | using void_t = typename make_void<Ts...>::type; |
223 | |
224 | template <typename T, typename = void> |
225 | struct HashPolicySelector { |
226 | typedef fibonacci_hash_policy type; |
227 | }; |
228 | template <typename T> |
229 | struct HashPolicySelector<T, void_t<typename T::hash_policy>> { |
230 | typedef typename T::hash_policy type; |
231 | }; |
232 | |
233 | template < |
234 | typename T, |
235 | typename FindKey, |
236 | typename ArgumentHash, |
237 | typename DetailHasher, |
238 | typename ArgumentEqual, |
239 | typename Equal, |
240 | typename ArgumentAlloc, |
241 | typename EntryAlloc> |
242 | class sherwood_v3_table : private EntryAlloc, |
243 | private DetailHasher, |
244 | private Equal { |
245 | using Entry = detailv3::sherwood_v3_entry<T>; |
246 | using AllocatorTraits = std::allocator_traits<EntryAlloc>; |
247 | using EntryPointer = typename AllocatorTraits::pointer; |
248 | |
249 | public: |
250 | struct convertible_to_iterator; |
251 | |
252 | using value_type = T; |
253 | using size_type = uint64_t; |
254 | using difference_type = std::ptrdiff_t; |
255 | using hasher = ArgumentHash; |
256 | using key_equal = ArgumentEqual; |
257 | using allocator_type = EntryAlloc; |
258 | using reference = value_type&; |
259 | using const_reference = const value_type&; |
260 | using pointer = value_type*; |
261 | using const_pointer = const value_type*; |
262 | |
263 | sherwood_v3_table() = default; |
264 | explicit sherwood_v3_table( |
265 | size_type bucket_count, |
266 | const ArgumentHash& hash = ArgumentHash(), |
267 | const ArgumentEqual& equal = ArgumentEqual(), |
268 | const ArgumentAlloc& alloc = ArgumentAlloc()) |
269 | : EntryAlloc(alloc), DetailHasher(hash), Equal(equal) { |
270 | rehash(bucket_count); |
271 | } |
272 | sherwood_v3_table(size_type bucket_count, const ArgumentAlloc& alloc) |
273 | : sherwood_v3_table( |
274 | bucket_count, |
275 | ArgumentHash(), |
276 | ArgumentEqual(), |
277 | alloc) {} |
278 | sherwood_v3_table( |
279 | size_type bucket_count, |
280 | const ArgumentHash& hash, |
281 | const ArgumentAlloc& alloc) |
282 | : sherwood_v3_table(bucket_count, hash, ArgumentEqual(), alloc) {} |
283 | explicit sherwood_v3_table(const ArgumentAlloc& alloc) : EntryAlloc(alloc) {} |
284 | template <typename It> |
285 | sherwood_v3_table( |
286 | It first, |
287 | It last, |
288 | size_type bucket_count = 0, |
289 | const ArgumentHash& hash = ArgumentHash(), |
290 | const ArgumentEqual& equal = ArgumentEqual(), |
291 | const ArgumentAlloc& alloc = ArgumentAlloc()) |
292 | : sherwood_v3_table(bucket_count, hash, equal, alloc) { |
293 | insert(first, last); |
294 | } |
295 | template <typename It> |
296 | sherwood_v3_table( |
297 | It first, |
298 | It last, |
299 | size_type bucket_count, |
300 | const ArgumentAlloc& alloc) |
301 | : sherwood_v3_table( |
302 | first, |
303 | last, |
304 | bucket_count, |
305 | ArgumentHash(), |
306 | ArgumentEqual(), |
307 | alloc) {} |
308 | template <typename It> |
309 | sherwood_v3_table( |
310 | It first, |
311 | It last, |
312 | size_type bucket_count, |
313 | const ArgumentHash& hash, |
314 | const ArgumentAlloc& alloc) |
315 | : sherwood_v3_table( |
316 | first, |
317 | last, |
318 | bucket_count, |
319 | hash, |
320 | ArgumentEqual(), |
321 | alloc) {} |
322 | sherwood_v3_table( |
323 | std::initializer_list<T> il, |
324 | size_type bucket_count = 0, |
325 | const ArgumentHash& hash = ArgumentHash(), |
326 | const ArgumentEqual& equal = ArgumentEqual(), |
327 | const ArgumentAlloc& alloc = ArgumentAlloc()) |
328 | : sherwood_v3_table(bucket_count, hash, equal, alloc) { |
329 | if (bucket_count == 0) |
330 | rehash(il.size()); |
331 | insert(il.begin(), il.end()); |
332 | } |
333 | sherwood_v3_table( |
334 | std::initializer_list<T> il, |
335 | size_type bucket_count, |
336 | const ArgumentAlloc& alloc) |
337 | : sherwood_v3_table( |
338 | il, |
339 | bucket_count, |
340 | ArgumentHash(), |
341 | ArgumentEqual(), |
342 | alloc) {} |
343 | sherwood_v3_table( |
344 | std::initializer_list<T> il, |
345 | size_type bucket_count, |
346 | const ArgumentHash& hash, |
347 | const ArgumentAlloc& alloc) |
348 | : sherwood_v3_table(il, bucket_count, hash, ArgumentEqual(), alloc) {} |
349 | sherwood_v3_table(const sherwood_v3_table& other) |
350 | : sherwood_v3_table( |
351 | other, |
352 | AllocatorTraits::select_on_container_copy_construction( |
353 | other.get_allocator())) {} |
354 | sherwood_v3_table(const sherwood_v3_table& other, const ArgumentAlloc& alloc) |
355 | : EntryAlloc(alloc), |
356 | DetailHasher(other), |
357 | Equal(other), |
358 | _max_load_factor(other._max_load_factor) { |
359 | rehash_for_other_container(other); |
360 | try { |
361 | insert(other.begin(), other.end()); |
362 | } catch (...) { |
363 | clear(); |
364 | deallocate_data(entries, num_slots_minus_one, max_lookups); |
365 | throw; |
366 | } |
367 | } |
368 | sherwood_v3_table(sherwood_v3_table&& other) noexcept |
369 | : EntryAlloc(std::move(other)), |
370 | DetailHasher(std::move(other)), |
371 | Equal(std::move(other)) { |
372 | swap_pointers(other); |
373 | } |
374 | sherwood_v3_table( |
375 | sherwood_v3_table&& other, |
376 | const ArgumentAlloc& alloc) noexcept |
377 | : EntryAlloc(alloc), |
378 | DetailHasher(std::move(other)), |
379 | Equal(std::move(other)) { |
380 | swap_pointers(other); |
381 | } |
382 | sherwood_v3_table& operator=(const sherwood_v3_table& other) { |
383 | if (this == std::addressof(other)) |
384 | return *this; |
385 | |
386 | clear(); |
387 | if (AllocatorTraits::propagate_on_container_copy_assignment::value) { |
388 | if (static_cast<EntryAlloc&>(*this) != |
389 | static_cast<const EntryAlloc&>(other)) { |
390 | reset_to_empty_state(); |
391 | } |
392 | AssignIfTrue< |
393 | EntryAlloc, |
394 | AllocatorTraits::propagate_on_container_copy_assignment::value>()( |
395 | *this, other); |
396 | } |
397 | _max_load_factor = other._max_load_factor; |
398 | static_cast<DetailHasher&>(*this) = other; |
399 | static_cast<Equal&>(*this) = other; |
400 | rehash_for_other_container(other); |
401 | insert(other.begin(), other.end()); |
402 | return *this; |
403 | } |
404 | sherwood_v3_table& operator=(sherwood_v3_table&& other) noexcept { |
405 | if (this == std::addressof(other)) |
406 | return *this; |
407 | else if (AllocatorTraits::propagate_on_container_move_assignment::value) { |
408 | clear(); |
409 | reset_to_empty_state(); |
410 | AssignIfTrue< |
411 | EntryAlloc, |
412 | AllocatorTraits::propagate_on_container_move_assignment::value>()( |
413 | *this, std::move(other)); |
414 | swap_pointers(other); |
415 | } else if ( |
416 | static_cast<EntryAlloc&>(*this) == static_cast<EntryAlloc&>(other)) { |
417 | swap_pointers(other); |
418 | } else { |
419 | clear(); |
420 | _max_load_factor = other._max_load_factor; |
421 | rehash_for_other_container(other); |
422 | for (T& elem : other) |
423 | emplace(std::move(elem)); |
424 | other.clear(); |
425 | } |
426 | static_cast<DetailHasher&>(*this) = std::move(other); |
427 | static_cast<Equal&>(*this) = std::move(other); |
428 | return *this; |
429 | } |
430 | ~sherwood_v3_table() { |
431 | clear(); |
432 | deallocate_data(entries, num_slots_minus_one, max_lookups); |
433 | } |
434 | |
435 | const allocator_type& get_allocator() const { |
436 | return static_cast<const allocator_type&>(*this); |
437 | } |
438 | const ArgumentEqual& key_eq() const { |
439 | return static_cast<const ArgumentEqual&>(*this); |
440 | } |
441 | const ArgumentHash& hash_function() const { |
442 | return static_cast<const ArgumentHash&>(*this); |
443 | } |
444 | |
445 | template <typename ValueType> |
446 | struct templated_iterator { |
447 | templated_iterator() = default; |
448 | templated_iterator(EntryPointer current) : current(current) {} |
449 | EntryPointer current = EntryPointer(); |
450 | |
451 | using iterator_category = std::forward_iterator_tag; |
452 | using value_type = ValueType; |
453 | using difference_type = ptrdiff_t; |
454 | using pointer = ValueType*; |
455 | using reference = ValueType&; |
456 | |
457 | friend bool operator==( |
458 | const templated_iterator& lhs, |
459 | const templated_iterator& rhs) { |
460 | return lhs.current == rhs.current; |
461 | } |
462 | friend bool operator!=( |
463 | const templated_iterator& lhs, |
464 | const templated_iterator& rhs) { |
465 | return !(lhs == rhs); |
466 | } |
467 | |
468 | templated_iterator& operator++() { |
469 | do { |
470 | ++current; |
471 | } while (current->is_empty()); |
472 | return *this; |
473 | } |
474 | templated_iterator operator++(int) { |
475 | templated_iterator copy(*this); |
476 | ++*this; |
477 | return copy; |
478 | } |
479 | |
480 | ValueType& operator*() const { |
481 | return current->value; |
482 | } |
483 | ValueType* operator->() const { |
484 | return std::addressof(current->value); |
485 | } |
486 | |
487 | // the template automatically disables the operator when value_type is |
488 | // already const, because that would cause a lot of compiler warnings |
489 | // otherwise. |
490 | template < |
491 | class target_type = const value_type, |
492 | class = typename std::enable_if< |
493 | std::is_same<target_type, const value_type>::value && |
494 | !std::is_same<target_type, value_type>::value>::type> |
495 | operator templated_iterator<target_type>() const { |
496 | return {current}; |
497 | } |
498 | }; |
499 | using iterator = templated_iterator<value_type>; |
500 | using const_iterator = templated_iterator<const value_type>; |
501 | |
502 | iterator begin() { |
503 | for (EntryPointer it = entries;; ++it) { |
504 | if (it->has_value()) |
505 | return {it}; |
506 | } |
507 | } |
508 | const_iterator begin() const { |
509 | for (EntryPointer it = entries;; ++it) { |
510 | if (it->has_value()) |
511 | return {it}; |
512 | } |
513 | } |
514 | const_iterator cbegin() const { |
515 | return begin(); |
516 | } |
517 | iterator end() { |
518 | return { |
519 | entries + static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups)}; |
520 | } |
521 | const_iterator end() const { |
522 | return { |
523 | entries + static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups)}; |
524 | } |
525 | const_iterator cend() const { |
526 | return end(); |
527 | } |
528 | |
529 | iterator find(const FindKey& key) { |
530 | uint64_t index = |
531 | hash_policy.index_for_hash(hash_object(key), num_slots_minus_one); |
532 | EntryPointer it = entries + ptrdiff_t(index); |
533 | for (int8_t distance = 0; it->distance_from_desired >= distance; |
534 | ++distance, ++it) { |
535 | if (compares_equal(key, it->value)) |
536 | return {it}; |
537 | } |
538 | return end(); |
539 | } |
540 | const_iterator find(const FindKey& key) const { |
541 | return const_cast<sherwood_v3_table*>(this)->find(key); |
542 | } |
543 | uint64_t count(const FindKey& key) const { |
544 | return find(key) == end() ? 0 : 1; |
545 | } |
546 | std::pair<iterator, iterator> equal_range(const FindKey& key) { |
547 | iterator found = find(key); |
548 | if (found == end()) |
549 | return {found, found}; |
550 | else |
551 | return {found, std::next(found)}; |
552 | } |
553 | std::pair<const_iterator, const_iterator> equal_range( |
554 | const FindKey& key) const { |
555 | const_iterator found = find(key); |
556 | if (found == end()) |
557 | return {found, found}; |
558 | else |
559 | return {found, std::next(found)}; |
560 | } |
561 | |
562 | template <typename Key, typename... Args> |
563 | std::pair<iterator, bool> emplace(Key&& key, Args&&... args) { |
564 | uint64_t index = |
565 | hash_policy.index_for_hash(hash_object(key), num_slots_minus_one); |
566 | EntryPointer current_entry = entries + ptrdiff_t(index); |
567 | int8_t distance_from_desired = 0; |
568 | for (; current_entry->distance_from_desired >= distance_from_desired; |
569 | ++current_entry, ++distance_from_desired) { |
570 | if (compares_equal(key, current_entry->value)) |
571 | return {{current_entry}, false}; |
572 | } |
573 | return emplace_new_key( |
574 | distance_from_desired, |
575 | current_entry, |
576 | std::forward<Key>(key), |
577 | std::forward<Args>(args)...); |
578 | } |
579 | |
580 | std::pair<iterator, bool> insert(const value_type& value) { |
581 | return emplace(value); |
582 | } |
583 | std::pair<iterator, bool> insert(value_type&& value) { |
584 | return emplace(std::move(value)); |
585 | } |
586 | template <typename... Args> |
587 | iterator emplace_hint(const_iterator, Args&&... args) { |
588 | return emplace(std::forward<Args>(args)...).first; |
589 | } |
590 | iterator insert(const_iterator, const value_type& value) { |
591 | return emplace(value).first; |
592 | } |
593 | iterator insert(const_iterator, value_type&& value) { |
594 | return emplace(std::move(value)).first; |
595 | } |
596 | |
597 | template <typename It> |
598 | void insert(It begin, It end) { |
599 | for (; begin != end; ++begin) { |
600 | emplace(*begin); |
601 | } |
602 | } |
603 | void insert(std::initializer_list<value_type> il) { |
604 | insert(il.begin(), il.end()); |
605 | } |
606 | |
607 | void rehash(uint64_t num_buckets) { |
608 | num_buckets = std::max( |
609 | num_buckets, |
610 | static_cast<uint64_t>( |
611 | std::ceil(num_elements / static_cast<double>(_max_load_factor)))); |
612 | if (num_buckets == 0) { |
613 | reset_to_empty_state(); |
614 | return; |
615 | } |
616 | auto new_prime_index = hash_policy.next_size_over(num_buckets); |
617 | if (num_buckets == bucket_count()) |
618 | return; |
619 | int8_t new_max_lookups = compute_max_lookups(num_buckets); |
620 | EntryPointer new_buckets( |
621 | AllocatorTraits::allocate(*this, num_buckets + new_max_lookups)); |
622 | EntryPointer special_end_item = |
623 | new_buckets + static_cast<ptrdiff_t>(num_buckets + new_max_lookups - 1); |
624 | for (EntryPointer it = new_buckets; it != special_end_item; ++it) |
625 | it->distance_from_desired = -1; |
626 | special_end_item->distance_from_desired = Entry::special_end_value; |
627 | std::swap(entries, new_buckets); |
628 | std::swap(num_slots_minus_one, num_buckets); |
629 | --num_slots_minus_one; |
630 | hash_policy.commit(new_prime_index); |
631 | int8_t old_max_lookups = max_lookups; |
632 | max_lookups = new_max_lookups; |
633 | num_elements = 0; |
634 | for (EntryPointer |
635 | it = new_buckets, |
636 | end = it + static_cast<ptrdiff_t>(num_buckets + old_max_lookups); |
637 | it != end; |
638 | ++it) { |
639 | if (it->has_value()) { |
640 | emplace(std::move(it->value)); |
641 | it->destroy_value(); |
642 | } |
643 | } |
644 | deallocate_data(new_buckets, num_buckets, old_max_lookups); |
645 | } |
646 | |
647 | void reserve(uint64_t num_elements_) { |
648 | uint64_t required_buckets = num_buckets_for_reserve(num_elements_); |
649 | if (required_buckets > bucket_count()) |
650 | rehash(required_buckets); |
651 | } |
652 | |
653 | // the return value is a type that can be converted to an iterator |
654 | // the reason for doing this is that it's not free to find the |
655 | // iterator pointing at the next element. if you care about the |
656 | // next iterator, turn the return value into an iterator |
657 | convertible_to_iterator erase(const_iterator to_erase) { |
658 | EntryPointer current = to_erase.current; |
659 | current->destroy_value(); |
660 | --num_elements; |
661 | for (EntryPointer next = current + ptrdiff_t(1); |
662 | !next->is_at_desired_position(); |
663 | ++current, ++next) { |
664 | current->emplace(next->distance_from_desired - 1, std::move(next->value)); |
665 | next->destroy_value(); |
666 | } |
667 | return {to_erase.current}; |
668 | } |
669 | |
670 | iterator erase(const_iterator begin_it, const_iterator end_it) { |
671 | if (begin_it == end_it) |
672 | return {begin_it.current}; |
673 | for (EntryPointer it = begin_it.current, end = end_it.current; it != end; |
674 | ++it) { |
675 | if (it->has_value()) { |
676 | it->destroy_value(); |
677 | --num_elements; |
678 | } |
679 | } |
680 | if (end_it == this->end()) |
681 | return this->end(); |
682 | ptrdiff_t num_to_move = std::min( |
683 | static_cast<ptrdiff_t>(end_it.current->distance_from_desired), |
684 | end_it.current - begin_it.current); |
685 | EntryPointer to_return = end_it.current - num_to_move; |
686 | for (EntryPointer it = end_it.current; !it->is_at_desired_position();) { |
687 | EntryPointer target = it - num_to_move; |
688 | target->emplace( |
689 | it->distance_from_desired - num_to_move, std::move(it->value)); |
690 | it->destroy_value(); |
691 | ++it; |
692 | num_to_move = std::min( |
693 | static_cast<ptrdiff_t>(it->distance_from_desired), num_to_move); |
694 | } |
695 | return {to_return}; |
696 | } |
697 | |
698 | uint64_t erase(const FindKey& key) { |
699 | auto found = find(key); |
700 | if (found == end()) |
701 | return 0; |
702 | else { |
703 | erase(found); |
704 | return 1; |
705 | } |
706 | } |
707 | |
708 | void clear() { |
709 | for (EntryPointer it = entries, |
710 | end = it + |
711 | static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups); |
712 | it != end; |
713 | ++it) { |
714 | if (it->has_value()) |
715 | it->destroy_value(); |
716 | } |
717 | num_elements = 0; |
718 | } |
719 | |
720 | void shrink_to_fit() { |
721 | rehash_for_other_container(*this); |
722 | } |
723 | |
724 | void swap(sherwood_v3_table& other) { |
725 | using std::swap; |
726 | swap_pointers(other); |
727 | swap(static_cast<ArgumentHash&>(*this), static_cast<ArgumentHash&>(other)); |
728 | swap( |
729 | static_cast<ArgumentEqual&>(*this), static_cast<ArgumentEqual&>(other)); |
730 | if (AllocatorTraits::propagate_on_container_swap::value) |
731 | swap(static_cast<EntryAlloc&>(*this), static_cast<EntryAlloc&>(other)); |
732 | } |
733 | |
734 | uint64_t size() const { |
735 | return num_elements; |
736 | } |
737 | uint64_t max_size() const { |
738 | return (AllocatorTraits::max_size(*this)) / sizeof(Entry); |
739 | } |
740 | uint64_t bucket_count() const { |
741 | return num_slots_minus_one ? num_slots_minus_one + 1 : 0; |
742 | } |
743 | size_type max_bucket_count() const { |
744 | return (AllocatorTraits::max_size(*this) - min_lookups) / sizeof(Entry); |
745 | } |
746 | uint64_t bucket(const FindKey& key) const { |
747 | return hash_policy.index_for_hash(hash_object(key), num_slots_minus_one); |
748 | } |
749 | float load_factor() const { |
750 | uint64_t buckets = bucket_count(); |
751 | if (buckets) |
752 | return static_cast<float>(num_elements) / bucket_count(); |
753 | else |
754 | return 0; |
755 | } |
756 | void max_load_factor(float value) { |
757 | _max_load_factor = value; |
758 | } |
759 | float max_load_factor() const { |
760 | return _max_load_factor; |
761 | } |
762 | |
763 | bool empty() const { |
764 | return num_elements == 0; |
765 | } |
766 | |
767 | private: |
768 | EntryPointer entries = empty_default_table(); |
769 | uint64_t num_slots_minus_one = 0; |
770 | typename HashPolicySelector<ArgumentHash>::type hash_policy; |
771 | int8_t max_lookups = detailv3::min_lookups - 1; |
772 | float _max_load_factor = 0.5f; |
773 | uint64_t num_elements = 0; |
774 | |
775 | EntryPointer empty_default_table() { |
776 | EntryPointer result = |
777 | AllocatorTraits::allocate(*this, detailv3::min_lookups); |
778 | EntryPointer special_end_item = |
779 | result + static_cast<ptrdiff_t>(detailv3::min_lookups - 1); |
780 | for (EntryPointer it = result; it != special_end_item; ++it) |
781 | it->distance_from_desired = -1; |
782 | special_end_item->distance_from_desired = Entry::special_end_value; |
783 | return result; |
784 | } |
785 | |
786 | static int8_t compute_max_lookups(uint64_t num_buckets) { |
787 | int8_t desired = detailv3::log2(num_buckets); |
788 | return std::max(detailv3::min_lookups, desired); |
789 | } |
790 | |
791 | uint64_t num_buckets_for_reserve(uint64_t num_elements_) const { |
792 | return static_cast<uint64_t>(std::ceil( |
793 | num_elements_ / std::min(0.5, static_cast<double>(_max_load_factor)))); |
794 | } |
795 | void rehash_for_other_container(const sherwood_v3_table& other) { |
796 | rehash( |
797 | std::min(num_buckets_for_reserve(other.size()), other.bucket_count())); |
798 | } |
799 | |
800 | void swap_pointers(sherwood_v3_table& other) { |
801 | using std::swap; |
802 | swap(hash_policy, other.hash_policy); |
803 | swap(entries, other.entries); |
804 | swap(num_slots_minus_one, other.num_slots_minus_one); |
805 | swap(num_elements, other.num_elements); |
806 | swap(max_lookups, other.max_lookups); |
807 | swap(_max_load_factor, other._max_load_factor); |
808 | } |
809 | |
810 | template <typename Key, typename... Args> |
811 | SKA_NOINLINE(std::pair<iterator, bool>) |
812 | emplace_new_key( |
813 | int8_t distance_from_desired, |
814 | EntryPointer current_entry, |
815 | Key&& key, |
816 | Args&&... args) { |
817 | using std::swap; |
818 | if (num_slots_minus_one == 0 || distance_from_desired == max_lookups || |
819 | num_elements + 1 > |
820 | (num_slots_minus_one + 1) * static_cast<double>(_max_load_factor)) { |
821 | grow(); |
822 | return emplace(std::forward<Key>(key), std::forward<Args>(args)...); |
823 | } else if (current_entry->is_empty()) { |
824 | current_entry->emplace( |
825 | distance_from_desired, |
826 | std::forward<Key>(key), |
827 | std::forward<Args>(args)...); |
828 | ++num_elements; |
829 | return {{current_entry}, true}; |
830 | } |
831 | value_type to_insert(std::forward<Key>(key), std::forward<Args>(args)...); |
832 | swap(distance_from_desired, current_entry->distance_from_desired); |
833 | swap(to_insert, current_entry->value); |
834 | iterator result = {current_entry}; |
835 | for (++distance_from_desired, ++current_entry;; ++current_entry) { |
836 | if (current_entry->is_empty()) { |
837 | current_entry->emplace(distance_from_desired, std::move(to_insert)); |
838 | ++num_elements; |
839 | return {result, true}; |
840 | } else if (current_entry->distance_from_desired < distance_from_desired) { |
841 | swap(distance_from_desired, current_entry->distance_from_desired); |
842 | swap(to_insert, current_entry->value); |
843 | ++distance_from_desired; |
844 | } else { |
845 | ++distance_from_desired; |
846 | if (distance_from_desired == max_lookups) { |
847 | swap(to_insert, result.current->value); |
848 | grow(); |
849 | return emplace(std::move(to_insert)); |
850 | } |
851 | } |
852 | } |
853 | } |
854 | |
855 | void grow() { |
856 | rehash(std::max(uint64_t(4), 2 * bucket_count())); |
857 | } |
858 | |
859 | void deallocate_data( |
860 | EntryPointer begin, |
861 | uint64_t num_slots_minus_one_, |
862 | int8_t max_lookups_) { |
863 | AllocatorTraits::deallocate( |
864 | *this, begin, num_slots_minus_one_ + max_lookups_ + 1); |
865 | } |
866 | |
867 | void reset_to_empty_state() { |
868 | deallocate_data(entries, num_slots_minus_one, max_lookups); |
869 | entries = empty_default_table(); |
870 | num_slots_minus_one = 0; |
871 | hash_policy.reset(); |
872 | max_lookups = detailv3::min_lookups - 1; |
873 | } |
874 | |
875 | template <typename U> |
876 | uint64_t hash_object(const U& key) { |
877 | return static_cast<DetailHasher&>(*this)(key); |
878 | } |
879 | template <typename U> |
880 | uint64_t hash_object(const U& key) const { |
881 | return static_cast<const DetailHasher&>(*this)(key); |
882 | } |
883 | template <typename L, typename R> |
884 | bool compares_equal(const L& lhs, const R& rhs) { |
885 | return static_cast<Equal&>(*this)(lhs, rhs); |
886 | } |
887 | |
888 | public: |
889 | struct convertible_to_iterator { |
890 | EntryPointer it; |
891 | |
892 | operator iterator() { |
893 | if (it->has_value()) |
894 | return {it}; |
895 | else |
896 | return ++iterator{it}; |
897 | } |
898 | operator const_iterator() { |
899 | if (it->has_value()) |
900 | return {it}; |
901 | else |
902 | return ++const_iterator{it}; |
903 | } |
904 | }; |
905 | }; |
906 | } // namespace detailv3 |
907 | |
908 | struct prime_number_hash_policy { |
909 | static uint64_t mod0(uint64_t) { |
910 | return 0llu; |
911 | } |
912 | static uint64_t mod2(uint64_t hash) { |
913 | return hash % 2llu; |
914 | } |
915 | static uint64_t mod3(uint64_t hash) { |
916 | return hash % 3llu; |
917 | } |
918 | static uint64_t mod5(uint64_t hash) { |
919 | return hash % 5llu; |
920 | } |
921 | static uint64_t mod7(uint64_t hash) { |
922 | return hash % 7llu; |
923 | } |
924 | static uint64_t mod11(uint64_t hash) { |
925 | return hash % 11llu; |
926 | } |
927 | static uint64_t mod13(uint64_t hash) { |
928 | return hash % 13llu; |
929 | } |
930 | static uint64_t mod17(uint64_t hash) { |
931 | return hash % 17llu; |
932 | } |
933 | static uint64_t mod23(uint64_t hash) { |
934 | return hash % 23llu; |
935 | } |
936 | static uint64_t mod29(uint64_t hash) { |
937 | return hash % 29llu; |
938 | } |
939 | static uint64_t mod37(uint64_t hash) { |
940 | return hash % 37llu; |
941 | } |
942 | static uint64_t mod47(uint64_t hash) { |
943 | return hash % 47llu; |
944 | } |
945 | static uint64_t mod59(uint64_t hash) { |
946 | return hash % 59llu; |
947 | } |
948 | static uint64_t mod73(uint64_t hash) { |
949 | return hash % 73llu; |
950 | } |
951 | static uint64_t mod97(uint64_t hash) { |
952 | return hash % 97llu; |
953 | } |
954 | static uint64_t mod127(uint64_t hash) { |
955 | return hash % 127llu; |
956 | } |
957 | static uint64_t mod151(uint64_t hash) { |
958 | return hash % 151llu; |
959 | } |
960 | static uint64_t mod197(uint64_t hash) { |
961 | return hash % 197llu; |
962 | } |
963 | static uint64_t mod251(uint64_t hash) { |
964 | return hash % 251llu; |
965 | } |
966 | static uint64_t mod313(uint64_t hash) { |
967 | return hash % 313llu; |
968 | } |
969 | static uint64_t mod397(uint64_t hash) { |
970 | return hash % 397llu; |
971 | } |
972 | static uint64_t mod499(uint64_t hash) { |
973 | return hash % 499llu; |
974 | } |
975 | static uint64_t mod631(uint64_t hash) { |
976 | return hash % 631llu; |
977 | } |
978 | static uint64_t mod797(uint64_t hash) { |
979 | return hash % 797llu; |
980 | } |
981 | static uint64_t mod1009(uint64_t hash) { |
982 | return hash % 1009llu; |
983 | } |
984 | static uint64_t mod1259(uint64_t hash) { |
985 | return hash % 1259llu; |
986 | } |
987 | static uint64_t mod1597(uint64_t hash) { |
988 | return hash % 1597llu; |
989 | } |
990 | static uint64_t mod2011(uint64_t hash) { |
991 | return hash % 2011llu; |
992 | } |
993 | static uint64_t mod2539(uint64_t hash) { |
994 | return hash % 2539llu; |
995 | } |
996 | static uint64_t mod3203(uint64_t hash) { |
997 | return hash % 3203llu; |
998 | } |
999 | static uint64_t mod4027(uint64_t hash) { |
1000 | return hash % 4027llu; |
1001 | } |
1002 | static uint64_t mod5087(uint64_t hash) { |
1003 | return hash % 5087llu; |
1004 | } |
1005 | static uint64_t mod6421(uint64_t hash) { |
1006 | return hash % 6421llu; |
1007 | } |
1008 | static uint64_t mod8089(uint64_t hash) { |
1009 | return hash % 8089llu; |
1010 | } |
1011 | static uint64_t mod10193(uint64_t hash) { |
1012 | return hash % 10193llu; |
1013 | } |
1014 | static uint64_t mod12853(uint64_t hash) { |
1015 | return hash % 12853llu; |
1016 | } |
1017 | static uint64_t mod16193(uint64_t hash) { |
1018 | return hash % 16193llu; |
1019 | } |
1020 | static uint64_t mod20399(uint64_t hash) { |
1021 | return hash % 20399llu; |
1022 | } |
1023 | static uint64_t mod25717(uint64_t hash) { |
1024 | return hash % 25717llu; |
1025 | } |
1026 | static uint64_t mod32401(uint64_t hash) { |
1027 | return hash % 32401llu; |
1028 | } |
1029 | static uint64_t mod40823(uint64_t hash) { |
1030 | return hash % 40823llu; |
1031 | } |
1032 | static uint64_t mod51437(uint64_t hash) { |
1033 | return hash % 51437llu; |
1034 | } |
1035 | static uint64_t mod64811(uint64_t hash) { |
1036 | return hash % 64811llu; |
1037 | } |
1038 | static uint64_t mod81649(uint64_t hash) { |
1039 | return hash % 81649llu; |
1040 | } |
1041 | static uint64_t mod102877(uint64_t hash) { |
1042 | return hash % 102877llu; |
1043 | } |
1044 | static uint64_t mod129607(uint64_t hash) { |
1045 | return hash % 129607llu; |
1046 | } |
1047 | static uint64_t mod163307(uint64_t hash) { |
1048 | return hash % 163307llu; |
1049 | } |
1050 | static uint64_t mod205759(uint64_t hash) { |
1051 | return hash % 205759llu; |
1052 | } |
1053 | static uint64_t mod259229(uint64_t hash) { |
1054 | return hash % 259229llu; |
1055 | } |
1056 | static uint64_t mod326617(uint64_t hash) { |
1057 | return hash % 326617llu; |
1058 | } |
1059 | static uint64_t mod411527(uint64_t hash) { |
1060 | return hash % 411527llu; |
1061 | } |
1062 | static uint64_t mod518509(uint64_t hash) { |
1063 | return hash % 518509llu; |
1064 | } |
1065 | static uint64_t mod653267(uint64_t hash) { |
1066 | return hash % 653267llu; |
1067 | } |
1068 | static uint64_t mod823117(uint64_t hash) { |
1069 | return hash % 823117llu; |
1070 | } |
1071 | static uint64_t mod1037059(uint64_t hash) { |
1072 | return hash % 1037059llu; |
1073 | } |
1074 | static uint64_t mod1306601(uint64_t hash) { |
1075 | return hash % 1306601llu; |
1076 | } |
1077 | static uint64_t mod1646237(uint64_t hash) { |
1078 | return hash % 1646237llu; |
1079 | } |
1080 | static uint64_t mod2074129(uint64_t hash) { |
1081 | return hash % 2074129llu; |
1082 | } |
1083 | static uint64_t mod2613229(uint64_t hash) { |
1084 | return hash % 2613229llu; |
1085 | } |
1086 | static uint64_t mod3292489(uint64_t hash) { |
1087 | return hash % 3292489llu; |
1088 | } |
1089 | static uint64_t mod4148279(uint64_t hash) { |
1090 | return hash % 4148279llu; |
1091 | } |
1092 | static uint64_t mod5226491(uint64_t hash) { |
1093 | return hash % 5226491llu; |
1094 | } |
1095 | static uint64_t mod6584983(uint64_t hash) { |
1096 | return hash % 6584983llu; |
1097 | } |
1098 | static uint64_t mod8296553(uint64_t hash) { |
1099 | return hash % 8296553llu; |
1100 | } |
1101 | static uint64_t mod10453007(uint64_t hash) { |
1102 | return hash % 10453007llu; |
1103 | } |
1104 | static uint64_t mod13169977(uint64_t hash) { |
1105 | return hash % 13169977llu; |
1106 | } |
1107 | static uint64_t mod16593127(uint64_t hash) { |
1108 | return hash % 16593127llu; |
1109 | } |
1110 | static uint64_t mod20906033(uint64_t hash) { |
1111 | return hash % 20906033llu; |
1112 | } |
1113 | static uint64_t mod26339969(uint64_t hash) { |
1114 | return hash % 26339969llu; |
1115 | } |
1116 | static uint64_t mod33186281(uint64_t hash) { |
1117 | return hash % 33186281llu; |
1118 | } |
1119 | static uint64_t mod41812097(uint64_t hash) { |
1120 | return hash % 41812097llu; |
1121 | } |
1122 | static uint64_t mod52679969(uint64_t hash) { |
1123 | return hash % 52679969llu; |
1124 | } |
1125 | static uint64_t mod66372617(uint64_t hash) { |
1126 | return hash % 66372617llu; |
1127 | } |
1128 | static uint64_t mod83624237(uint64_t hash) { |
1129 | return hash % 83624237llu; |
1130 | } |
1131 | static uint64_t mod105359939(uint64_t hash) { |
1132 | return hash % 105359939llu; |
1133 | } |
1134 | static uint64_t mod132745199(uint64_t hash) { |
1135 | return hash % 132745199llu; |
1136 | } |
1137 | static uint64_t mod167248483(uint64_t hash) { |
1138 | return hash % 167248483llu; |
1139 | } |
1140 | static uint64_t mod210719881(uint64_t hash) { |
1141 | return hash % 210719881llu; |
1142 | } |
1143 | static uint64_t mod265490441(uint64_t hash) { |
1144 | return hash % 265490441llu; |
1145 | } |
1146 | static uint64_t mod334496971(uint64_t hash) { |
1147 | return hash % 334496971llu; |
1148 | } |
1149 | static uint64_t mod421439783(uint64_t hash) { |
1150 | return hash % 421439783llu; |
1151 | } |
1152 | static uint64_t mod530980861(uint64_t hash) { |
1153 | return hash % 530980861llu; |
1154 | } |
1155 | static uint64_t mod668993977(uint64_t hash) { |
1156 | return hash % 668993977llu; |
1157 | } |
1158 | static uint64_t mod842879579(uint64_t hash) { |
1159 | return hash % 842879579llu; |
1160 | } |
1161 | static uint64_t mod1061961721(uint64_t hash) { |
1162 | return hash % 1061961721llu; |
1163 | } |
1164 | static uint64_t mod1337987929(uint64_t hash) { |
1165 | return hash % 1337987929llu; |
1166 | } |
1167 | static uint64_t mod1685759167(uint64_t hash) { |
1168 | return hash % 1685759167llu; |
1169 | } |
1170 | static uint64_t mod2123923447(uint64_t hash) { |
1171 | return hash % 2123923447llu; |
1172 | } |
1173 | static uint64_t mod2675975881(uint64_t hash) { |
1174 | return hash % 2675975881llu; |
1175 | } |
1176 | static uint64_t mod3371518343(uint64_t hash) { |
1177 | return hash % 3371518343llu; |
1178 | } |
1179 | static uint64_t mod4247846927(uint64_t hash) { |
1180 | return hash % 4247846927llu; |
1181 | } |
1182 | static uint64_t mod5351951779(uint64_t hash) { |
1183 | return hash % 5351951779llu; |
1184 | } |
1185 | static uint64_t mod6743036717(uint64_t hash) { |
1186 | return hash % 6743036717llu; |
1187 | } |
1188 | static uint64_t mod8495693897(uint64_t hash) { |
1189 | return hash % 8495693897llu; |
1190 | } |
1191 | static uint64_t mod10703903591(uint64_t hash) { |
1192 | return hash % 10703903591llu; |
1193 | } |
1194 | static uint64_t mod13486073473(uint64_t hash) { |
1195 | return hash % 13486073473llu; |
1196 | } |
1197 | static uint64_t mod16991387857(uint64_t hash) { |
1198 | return hash % 16991387857llu; |
1199 | } |
1200 | static uint64_t mod21407807219(uint64_t hash) { |
1201 | return hash % 21407807219llu; |
1202 | } |
1203 | static uint64_t mod26972146961(uint64_t hash) { |
1204 | return hash % 26972146961llu; |
1205 | } |
1206 | static uint64_t mod33982775741(uint64_t hash) { |
1207 | return hash % 33982775741llu; |
1208 | } |
1209 | static uint64_t mod42815614441(uint64_t hash) { |
1210 | return hash % 42815614441llu; |
1211 | } |
1212 | static uint64_t mod53944293929(uint64_t hash) { |
1213 | return hash % 53944293929llu; |
1214 | } |
1215 | static uint64_t mod67965551447(uint64_t hash) { |
1216 | return hash % 67965551447llu; |
1217 | } |
1218 | static uint64_t mod85631228929(uint64_t hash) { |
1219 | return hash % 85631228929llu; |
1220 | } |
1221 | static uint64_t mod107888587883(uint64_t hash) { |
1222 | return hash % 107888587883llu; |
1223 | } |
1224 | static uint64_t mod135931102921(uint64_t hash) { |
1225 | return hash % 135931102921llu; |
1226 | } |
1227 | static uint64_t mod171262457903(uint64_t hash) { |
1228 | return hash % 171262457903llu; |
1229 | } |
1230 | static uint64_t mod215777175787(uint64_t hash) { |
1231 | return hash % 215777175787llu; |
1232 | } |
1233 | static uint64_t mod271862205833(uint64_t hash) { |
1234 | return hash % 271862205833llu; |
1235 | } |
1236 | static uint64_t mod342524915839(uint64_t hash) { |
1237 | return hash % 342524915839llu; |
1238 | } |
1239 | static uint64_t mod431554351609(uint64_t hash) { |
1240 | return hash % 431554351609llu; |
1241 | } |
1242 | static uint64_t mod543724411781(uint64_t hash) { |
1243 | return hash % 543724411781llu; |
1244 | } |
1245 | static uint64_t mod685049831731(uint64_t hash) { |
1246 | return hash % 685049831731llu; |
1247 | } |
1248 | static uint64_t mod863108703229(uint64_t hash) { |
1249 | return hash % 863108703229llu; |
1250 | } |
1251 | static uint64_t mod1087448823553(uint64_t hash) { |
1252 | return hash % 1087448823553llu; |
1253 | } |
1254 | static uint64_t mod1370099663459(uint64_t hash) { |
1255 | return hash % 1370099663459llu; |
1256 | } |
1257 | static uint64_t mod1726217406467(uint64_t hash) { |
1258 | return hash % 1726217406467llu; |
1259 | } |
1260 | static uint64_t mod2174897647073(uint64_t hash) { |
1261 | return hash % 2174897647073llu; |
1262 | } |
1263 | static uint64_t mod2740199326961(uint64_t hash) { |
1264 | return hash % 2740199326961llu; |
1265 | } |
1266 | static uint64_t mod3452434812973(uint64_t hash) { |
1267 | return hash % 3452434812973llu; |
1268 | } |
1269 | static uint64_t mod4349795294267(uint64_t hash) { |
1270 | return hash % 4349795294267llu; |
1271 | } |
1272 | static uint64_t mod5480398654009(uint64_t hash) { |
1273 | return hash % 5480398654009llu; |
1274 | } |
1275 | static uint64_t mod6904869625999(uint64_t hash) { |
1276 | return hash % 6904869625999llu; |
1277 | } |
1278 | static uint64_t mod8699590588571(uint64_t hash) { |
1279 | return hash % 8699590588571llu; |
1280 | } |
1281 | static uint64_t mod10960797308051(uint64_t hash) { |
1282 | return hash % 10960797308051llu; |
1283 | } |
1284 | static uint64_t mod13809739252051(uint64_t hash) { |
1285 | return hash % 13809739252051llu; |
1286 | } |
1287 | static uint64_t mod17399181177241(uint64_t hash) { |
1288 | return hash % 17399181177241llu; |
1289 | } |
1290 | static uint64_t mod21921594616111(uint64_t hash) { |
1291 | return hash % 21921594616111llu; |
1292 | } |
1293 | static uint64_t mod27619478504183(uint64_t hash) { |
1294 | return hash % 27619478504183llu; |
1295 | } |
1296 | static uint64_t mod34798362354533(uint64_t hash) { |
1297 | return hash % 34798362354533llu; |
1298 | } |
1299 | static uint64_t mod43843189232363(uint64_t hash) { |
1300 | return hash % 43843189232363llu; |
1301 | } |
1302 | static uint64_t mod55238957008387(uint64_t hash) { |
1303 | return hash % 55238957008387llu; |
1304 | } |
1305 | static uint64_t mod69596724709081(uint64_t hash) { |
1306 | return hash % 69596724709081llu; |
1307 | } |
1308 | static uint64_t mod87686378464759(uint64_t hash) { |
1309 | return hash % 87686378464759llu; |
1310 | } |
1311 | static uint64_t mod110477914016779(uint64_t hash) { |
1312 | return hash % 110477914016779llu; |
1313 | } |
1314 | static uint64_t mod139193449418173(uint64_t hash) { |
1315 | return hash % 139193449418173llu; |
1316 | } |
1317 | static uint64_t mod175372756929481(uint64_t hash) { |
1318 | return hash % 175372756929481llu; |
1319 | } |
1320 | static uint64_t mod220955828033581(uint64_t hash) { |
1321 | return hash % 220955828033581llu; |
1322 | } |
1323 | static uint64_t mod278386898836457(uint64_t hash) { |
1324 | return hash % 278386898836457llu; |
1325 | } |
1326 | static uint64_t mod350745513859007(uint64_t hash) { |
1327 | return hash % 350745513859007llu; |
1328 | } |
1329 | static uint64_t mod441911656067171(uint64_t hash) { |
1330 | return hash % 441911656067171llu; |
1331 | } |
1332 | static uint64_t mod556773797672909(uint64_t hash) { |
1333 | return hash % 556773797672909llu; |
1334 | } |
1335 | static uint64_t mod701491027718027(uint64_t hash) { |
1336 | return hash % 701491027718027llu; |
1337 | } |
1338 | static uint64_t mod883823312134381(uint64_t hash) { |
1339 | return hash % 883823312134381llu; |
1340 | } |
1341 | static uint64_t mod1113547595345903(uint64_t hash) { |
1342 | return hash % 1113547595345903llu; |
1343 | } |
1344 | static uint64_t mod1402982055436147(uint64_t hash) { |
1345 | return hash % 1402982055436147llu; |
1346 | } |
1347 | static uint64_t mod1767646624268779(uint64_t hash) { |
1348 | return hash % 1767646624268779llu; |
1349 | } |
1350 | static uint64_t mod2227095190691797(uint64_t hash) { |
1351 | return hash % 2227095190691797llu; |
1352 | } |
1353 | static uint64_t mod2805964110872297(uint64_t hash) { |
1354 | return hash % 2805964110872297llu; |
1355 | } |
1356 | static uint64_t mod3535293248537579(uint64_t hash) { |
1357 | return hash % 3535293248537579llu; |
1358 | } |
1359 | static uint64_t mod4454190381383713(uint64_t hash) { |
1360 | return hash % 4454190381383713llu; |
1361 | } |
1362 | static uint64_t mod5611928221744609(uint64_t hash) { |
1363 | return hash % 5611928221744609llu; |
1364 | } |
1365 | static uint64_t mod7070586497075177(uint64_t hash) { |
1366 | return hash % 7070586497075177llu; |
1367 | } |
1368 | static uint64_t mod8908380762767489(uint64_t hash) { |
1369 | return hash % 8908380762767489llu; |
1370 | } |
1371 | static uint64_t mod11223856443489329(uint64_t hash) { |
1372 | return hash % 11223856443489329llu; |
1373 | } |
1374 | static uint64_t mod14141172994150357(uint64_t hash) { |
1375 | return hash % 14141172994150357llu; |
1376 | } |
1377 | static uint64_t mod17816761525534927(uint64_t hash) { |
1378 | return hash % 17816761525534927llu; |
1379 | } |
1380 | static uint64_t mod22447712886978529(uint64_t hash) { |
1381 | return hash % 22447712886978529llu; |
1382 | } |
1383 | static uint64_t mod28282345988300791(uint64_t hash) { |
1384 | return hash % 28282345988300791llu; |
1385 | } |
1386 | static uint64_t mod35633523051069991(uint64_t hash) { |
1387 | return hash % 35633523051069991llu; |
1388 | } |
1389 | static uint64_t mod44895425773957261(uint64_t hash) { |
1390 | return hash % 44895425773957261llu; |
1391 | } |
1392 | static uint64_t mod56564691976601587(uint64_t hash) { |
1393 | return hash % 56564691976601587llu; |
1394 | } |
1395 | static uint64_t mod71267046102139967(uint64_t hash) { |
1396 | return hash % 71267046102139967llu; |
1397 | } |
1398 | static uint64_t mod89790851547914507(uint64_t hash) { |
1399 | return hash % 89790851547914507llu; |
1400 | } |
1401 | static uint64_t mod113129383953203213(uint64_t hash) { |
1402 | return hash % 113129383953203213llu; |
1403 | } |
1404 | static uint64_t mod142534092204280003(uint64_t hash) { |
1405 | return hash % 142534092204280003llu; |
1406 | } |
1407 | static uint64_t mod179581703095829107(uint64_t hash) { |
1408 | return hash % 179581703095829107llu; |
1409 | } |
1410 | static uint64_t mod226258767906406483(uint64_t hash) { |
1411 | return hash % 226258767906406483llu; |
1412 | } |
1413 | static uint64_t mod285068184408560057(uint64_t hash) { |
1414 | return hash % 285068184408560057llu; |
1415 | } |
1416 | static uint64_t mod359163406191658253(uint64_t hash) { |
1417 | return hash % 359163406191658253llu; |
1418 | } |
1419 | static uint64_t mod452517535812813007(uint64_t hash) { |
1420 | return hash % 452517535812813007llu; |
1421 | } |
1422 | static uint64_t mod570136368817120201(uint64_t hash) { |
1423 | return hash % 570136368817120201llu; |
1424 | } |
1425 | static uint64_t mod718326812383316683(uint64_t hash) { |
1426 | return hash % 718326812383316683llu; |
1427 | } |
1428 | static uint64_t mod905035071625626043(uint64_t hash) { |
1429 | return hash % 905035071625626043llu; |
1430 | } |
1431 | static uint64_t mod1140272737634240411(uint64_t hash) { |
1432 | return hash % 1140272737634240411llu; |
1433 | } |
1434 | static uint64_t mod1436653624766633509(uint64_t hash) { |
1435 | return hash % 1436653624766633509llu; |
1436 | } |
1437 | static uint64_t mod1810070143251252131(uint64_t hash) { |
1438 | return hash % 1810070143251252131llu; |
1439 | } |
1440 | static uint64_t mod2280545475268481167(uint64_t hash) { |
1441 | return hash % 2280545475268481167llu; |
1442 | } |
1443 | static uint64_t mod2873307249533267101(uint64_t hash) { |
1444 | return hash % 2873307249533267101llu; |
1445 | } |
1446 | static uint64_t mod3620140286502504283(uint64_t hash) { |
1447 | return hash % 3620140286502504283llu; |
1448 | } |
1449 | static uint64_t mod4561090950536962147(uint64_t hash) { |
1450 | return hash % 4561090950536962147llu; |
1451 | } |
1452 | static uint64_t mod5746614499066534157(uint64_t hash) { |
1453 | return hash % 5746614499066534157llu; |
1454 | } |
1455 | static uint64_t mod7240280573005008577(uint64_t hash) { |
1456 | return hash % 7240280573005008577llu; |
1457 | } |
1458 | static uint64_t mod9122181901073924329(uint64_t hash) { |
1459 | return hash % 9122181901073924329llu; |
1460 | } |
1461 | static uint64_t mod11493228998133068689(uint64_t hash) { |
1462 | return hash % 11493228998133068689llu; |
1463 | } |
1464 | static uint64_t mod14480561146010017169(uint64_t hash) { |
1465 | return hash % 14480561146010017169llu; |
1466 | } |
1467 | static uint64_t mod18446744073709551557(uint64_t hash) { |
1468 | return hash % 18446744073709551557llu; |
1469 | } |
1470 | |
1471 | using mod_function = uint64_t (*)(uint64_t); |
1472 | |
1473 | mod_function next_size_over(uint64_t& size) const { |
1474 | // prime numbers generated by the following method: |
1475 | // 1. start with a prime p = 2 |
1476 | // 2. go to wolfram alpha and get p = NextPrime(2 * p) |
1477 | // 3. repeat 2. until you overflow 64 bits |
1478 | // you now have large gaps which you would hit if somebody called reserve() |
1479 | // with an unlucky number. |
1480 | // 4. to fill the gaps for every prime p go to wolfram alpha and get |
1481 | // ClosestPrime(p * 2^(1/3)) and ClosestPrime(p * 2^(2/3)) and put those in |
1482 | // the gaps |
1483 | // 5. get PrevPrime(2^64) and put it at the end |
1484 | static constexpr const uint64_t prime_list[] = { |
1485 | 2llu, |
1486 | 3llu, |
1487 | 5llu, |
1488 | 7llu, |
1489 | 11llu, |
1490 | 13llu, |
1491 | 17llu, |
1492 | 23llu, |
1493 | 29llu, |
1494 | 37llu, |
1495 | 47llu, |
1496 | 59llu, |
1497 | 73llu, |
1498 | 97llu, |
1499 | 127llu, |
1500 | 151llu, |
1501 | 197llu, |
1502 | 251llu, |
1503 | 313llu, |
1504 | 397llu, |
1505 | 499llu, |
1506 | 631llu, |
1507 | 797llu, |
1508 | 1009llu, |
1509 | 1259llu, |
1510 | 1597llu, |
1511 | 2011llu, |
1512 | 2539llu, |
1513 | 3203llu, |
1514 | 4027llu, |
1515 | 5087llu, |
1516 | 6421llu, |
1517 | 8089llu, |
1518 | 10193llu, |
1519 | 12853llu, |
1520 | 16193llu, |
1521 | 20399llu, |
1522 | 25717llu, |
1523 | 32401llu, |
1524 | 40823llu, |
1525 | 51437llu, |
1526 | 64811llu, |
1527 | 81649llu, |
1528 | 102877llu, |
1529 | 129607llu, |
1530 | 163307llu, |
1531 | 205759llu, |
1532 | 259229llu, |
1533 | 326617llu, |
1534 | 411527llu, |
1535 | 518509llu, |
1536 | 653267llu, |
1537 | 823117llu, |
1538 | 1037059llu, |
1539 | 1306601llu, |
1540 | 1646237llu, |
1541 | 2074129llu, |
1542 | 2613229llu, |
1543 | 3292489llu, |
1544 | 4148279llu, |
1545 | 5226491llu, |
1546 | 6584983llu, |
1547 | 8296553llu, |
1548 | 10453007llu, |
1549 | 13169977llu, |
1550 | 16593127llu, |
1551 | 20906033llu, |
1552 | 26339969llu, |
1553 | 33186281llu, |
1554 | 41812097llu, |
1555 | 52679969llu, |
1556 | 66372617llu, |
1557 | 83624237llu, |
1558 | 105359939llu, |
1559 | 132745199llu, |
1560 | 167248483llu, |
1561 | 210719881llu, |
1562 | 265490441llu, |
1563 | 334496971llu, |
1564 | 421439783llu, |
1565 | 530980861llu, |
1566 | 668993977llu, |
1567 | 842879579llu, |
1568 | 1061961721llu, |
1569 | 1337987929llu, |
1570 | 1685759167llu, |
1571 | 2123923447llu, |
1572 | 2675975881llu, |
1573 | 3371518343llu, |
1574 | 4247846927llu, |
1575 | 5351951779llu, |
1576 | 6743036717llu, |
1577 | 8495693897llu, |
1578 | 10703903591llu, |
1579 | 13486073473llu, |
1580 | 16991387857llu, |
1581 | 21407807219llu, |
1582 | 26972146961llu, |
1583 | 33982775741llu, |
1584 | 42815614441llu, |
1585 | 53944293929llu, |
1586 | 67965551447llu, |
1587 | 85631228929llu, |
1588 | 107888587883llu, |
1589 | 135931102921llu, |
1590 | 171262457903llu, |
1591 | 215777175787llu, |
1592 | 271862205833llu, |
1593 | 342524915839llu, |
1594 | 431554351609llu, |
1595 | 543724411781llu, |
1596 | 685049831731llu, |
1597 | 863108703229llu, |
1598 | 1087448823553llu, |
1599 | 1370099663459llu, |
1600 | 1726217406467llu, |
1601 | 2174897647073llu, |
1602 | 2740199326961llu, |
1603 | 3452434812973llu, |
1604 | 4349795294267llu, |
1605 | 5480398654009llu, |
1606 | 6904869625999llu, |
1607 | 8699590588571llu, |
1608 | 10960797308051llu, |
1609 | 13809739252051llu, |
1610 | 17399181177241llu, |
1611 | 21921594616111llu, |
1612 | 27619478504183llu, |
1613 | 34798362354533llu, |
1614 | 43843189232363llu, |
1615 | 55238957008387llu, |
1616 | 69596724709081llu, |
1617 | 87686378464759llu, |
1618 | 110477914016779llu, |
1619 | 139193449418173llu, |
1620 | 175372756929481llu, |
1621 | 220955828033581llu, |
1622 | 278386898836457llu, |
1623 | 350745513859007llu, |
1624 | 441911656067171llu, |
1625 | 556773797672909llu, |
1626 | 701491027718027llu, |
1627 | 883823312134381llu, |
1628 | 1113547595345903llu, |
1629 | 1402982055436147llu, |
1630 | 1767646624268779llu, |
1631 | 2227095190691797llu, |
1632 | 2805964110872297llu, |
1633 | 3535293248537579llu, |
1634 | 4454190381383713llu, |
1635 | 5611928221744609llu, |
1636 | 7070586497075177llu, |
1637 | 8908380762767489llu, |
1638 | 11223856443489329llu, |
1639 | 14141172994150357llu, |
1640 | 17816761525534927llu, |
1641 | 22447712886978529llu, |
1642 | 28282345988300791llu, |
1643 | 35633523051069991llu, |
1644 | 44895425773957261llu, |
1645 | 56564691976601587llu, |
1646 | 71267046102139967llu, |
1647 | 89790851547914507llu, |
1648 | 113129383953203213llu, |
1649 | 142534092204280003llu, |
1650 | 179581703095829107llu, |
1651 | 226258767906406483llu, |
1652 | 285068184408560057llu, |
1653 | 359163406191658253llu, |
1654 | 452517535812813007llu, |
1655 | 570136368817120201llu, |
1656 | 718326812383316683llu, |
1657 | 905035071625626043llu, |
1658 | 1140272737634240411llu, |
1659 | 1436653624766633509llu, |
1660 | 1810070143251252131llu, |
1661 | 2280545475268481167llu, |
1662 | 2873307249533267101llu, |
1663 | 3620140286502504283llu, |
1664 | 4561090950536962147llu, |
1665 | 5746614499066534157llu, |
1666 | 7240280573005008577llu, |
1667 | 9122181901073924329llu, |
1668 | 11493228998133068689llu, |
1669 | 14480561146010017169llu, |
1670 | 18446744073709551557llu}; |
1671 | static constexpr uint64_t (*const mod_functions[])(uint64_t) = { |
1672 | &mod0, |
1673 | &mod2, |
1674 | &mod3, |
1675 | &mod5, |
1676 | &mod7, |
1677 | &mod11, |
1678 | &mod13, |
1679 | &mod17, |
1680 | &mod23, |
1681 | &mod29, |
1682 | &mod37, |
1683 | &mod47, |
1684 | &mod59, |
1685 | &mod73, |
1686 | &mod97, |
1687 | &mod127, |
1688 | &mod151, |
1689 | &mod197, |
1690 | &mod251, |
1691 | &mod313, |
1692 | &mod397, |
1693 | &mod499, |
1694 | &mod631, |
1695 | &mod797, |
1696 | &mod1009, |
1697 | &mod1259, |
1698 | &mod1597, |
1699 | &mod2011, |
1700 | &mod2539, |
1701 | &mod3203, |
1702 | &mod4027, |
1703 | &mod5087, |
1704 | &mod6421, |
1705 | &mod8089, |
1706 | &mod10193, |
1707 | &mod12853, |
1708 | &mod16193, |
1709 | &mod20399, |
1710 | &mod25717, |
1711 | &mod32401, |
1712 | &mod40823, |
1713 | &mod51437, |
1714 | &mod64811, |
1715 | &mod81649, |
1716 | &mod102877, |
1717 | &mod129607, |
1718 | &mod163307, |
1719 | &mod205759, |
1720 | &mod259229, |
1721 | &mod326617, |
1722 | &mod411527, |
1723 | &mod518509, |
1724 | &mod653267, |
1725 | &mod823117, |
1726 | &mod1037059, |
1727 | &mod1306601, |
1728 | &mod1646237, |
1729 | &mod2074129, |
1730 | &mod2613229, |
1731 | &mod3292489, |
1732 | &mod4148279, |
1733 | &mod5226491, |
1734 | &mod6584983, |
1735 | &mod8296553, |
1736 | &mod10453007, |
1737 | &mod13169977, |
1738 | &mod16593127, |
1739 | &mod20906033, |
1740 | &mod26339969, |
1741 | &mod33186281, |
1742 | &mod41812097, |
1743 | &mod52679969, |
1744 | &mod66372617, |
1745 | &mod83624237, |
1746 | &mod105359939, |
1747 | &mod132745199, |
1748 | &mod167248483, |
1749 | &mod210719881, |
1750 | &mod265490441, |
1751 | &mod334496971, |
1752 | &mod421439783, |
1753 | &mod530980861, |
1754 | &mod668993977, |
1755 | &mod842879579, |
1756 | &mod1061961721, |
1757 | &mod1337987929, |
1758 | &mod1685759167, |
1759 | &mod2123923447, |
1760 | &mod2675975881, |
1761 | &mod3371518343, |
1762 | &mod4247846927, |
1763 | &mod5351951779, |
1764 | &mod6743036717, |
1765 | &mod8495693897, |
1766 | &mod10703903591, |
1767 | &mod13486073473, |
1768 | &mod16991387857, |
1769 | &mod21407807219, |
1770 | &mod26972146961, |
1771 | &mod33982775741, |
1772 | &mod42815614441, |
1773 | &mod53944293929, |
1774 | &mod67965551447, |
1775 | &mod85631228929, |
1776 | &mod107888587883, |
1777 | &mod135931102921, |
1778 | &mod171262457903, |
1779 | &mod215777175787, |
1780 | &mod271862205833, |
1781 | &mod342524915839, |
1782 | &mod431554351609, |
1783 | &mod543724411781, |
1784 | &mod685049831731, |
1785 | &mod863108703229, |
1786 | &mod1087448823553, |
1787 | &mod1370099663459, |
1788 | &mod1726217406467, |
1789 | &mod2174897647073, |
1790 | &mod2740199326961, |
1791 | &mod3452434812973, |
1792 | &mod4349795294267, |
1793 | &mod5480398654009, |
1794 | &mod6904869625999, |
1795 | &mod8699590588571, |
1796 | &mod10960797308051, |
1797 | &mod13809739252051, |
1798 | &mod17399181177241, |
1799 | &mod21921594616111, |
1800 | &mod27619478504183, |
1801 | &mod34798362354533, |
1802 | &mod43843189232363, |
1803 | &mod55238957008387, |
1804 | &mod69596724709081, |
1805 | &mod87686378464759, |
1806 | &mod110477914016779, |
1807 | &mod139193449418173, |
1808 | &mod175372756929481, |
1809 | &mod220955828033581, |
1810 | &mod278386898836457, |
1811 | &mod350745513859007, |
1812 | &mod441911656067171, |
1813 | &mod556773797672909, |
1814 | &mod701491027718027, |
1815 | &mod883823312134381, |
1816 | &mod1113547595345903, |
1817 | &mod1402982055436147, |
1818 | &mod1767646624268779, |
1819 | &mod2227095190691797, |
1820 | &mod2805964110872297, |
1821 | &mod3535293248537579, |
1822 | &mod4454190381383713, |
1823 | &mod5611928221744609, |
1824 | &mod7070586497075177, |
1825 | &mod8908380762767489, |
1826 | &mod11223856443489329, |
1827 | &mod14141172994150357, |
1828 | &mod17816761525534927, |
1829 | &mod22447712886978529, |
1830 | &mod28282345988300791, |
1831 | &mod35633523051069991, |
1832 | &mod44895425773957261, |
1833 | &mod56564691976601587, |
1834 | &mod71267046102139967, |
1835 | &mod89790851547914507, |
1836 | &mod113129383953203213, |
1837 | &mod142534092204280003, |
1838 | &mod179581703095829107, |
1839 | &mod226258767906406483, |
1840 | &mod285068184408560057, |
1841 | &mod359163406191658253, |
1842 | &mod452517535812813007, |
1843 | &mod570136368817120201, |
1844 | &mod718326812383316683, |
1845 | &mod905035071625626043, |
1846 | &mod1140272737634240411, |
1847 | &mod1436653624766633509, |
1848 | &mod1810070143251252131, |
1849 | &mod2280545475268481167, |
1850 | &mod2873307249533267101, |
1851 | &mod3620140286502504283, |
1852 | &mod4561090950536962147, |
1853 | &mod5746614499066534157, |
1854 | &mod7240280573005008577, |
1855 | &mod9122181901073924329, |
1856 | &mod11493228998133068689, |
1857 | &mod14480561146010017169, |
1858 | &mod18446744073709551557}; |
1859 | const uint64_t* found = std::lower_bound( |
1860 | std::begin(prime_list), std::end(prime_list) - 1, size); |
1861 | size = *found; |
1862 | return mod_functions[1 + found - prime_list]; |
1863 | } |
1864 | void commit(mod_function new_mod_function) { |
1865 | current_mod_function = new_mod_function; |
1866 | } |
1867 | void reset() { |
1868 | current_mod_function = &mod0; |
1869 | } |
1870 | |
1871 | uint64_t index_for_hash(uint64_t hash, uint64_t /*num_slots_minus_one*/) |
1872 | const { |
1873 | return current_mod_function(hash); |
1874 | } |
1875 | uint64_t keep_in_range(uint64_t index, uint64_t num_slots_minus_one) const { |
1876 | return index > num_slots_minus_one ? current_mod_function(index) : index; |
1877 | } |
1878 | |
1879 | private: |
1880 | mod_function current_mod_function = &mod0; |
1881 | }; |
1882 | |
1883 | struct power_of_two_hash_policy { |
1884 | uint64_t index_for_hash(uint64_t hash, uint64_t num_slots_minus_one) const { |
1885 | return hash & num_slots_minus_one; |
1886 | } |
1887 | uint64_t keep_in_range(uint64_t index, uint64_t num_slots_minus_one) const { |
1888 | return index_for_hash(index, num_slots_minus_one); |
1889 | } |
1890 | int8_t next_size_over(uint64_t& size) const { |
1891 | size = detailv3::next_power_of_two(size); |
1892 | return 0; |
1893 | } |
1894 | void commit(int8_t) {} |
1895 | void reset() {} |
1896 | }; |
1897 | |
1898 | struct fibonacci_hash_policy { |
1899 | uint64_t index_for_hash(uint64_t hash, uint64_t /*num_slots_minus_one*/) |
1900 | const { |
1901 | return (11400714819323198485ull * hash) >> shift; |
1902 | } |
1903 | uint64_t keep_in_range(uint64_t index, uint64_t num_slots_minus_one) const { |
1904 | return index & num_slots_minus_one; |
1905 | } |
1906 | |
1907 | int8_t next_size_over(uint64_t& size) const { |
1908 | size = std::max(uint64_t(2), detailv3::next_power_of_two(size)); |
1909 | return 64 - detailv3::log2(size); |
1910 | } |
1911 | void commit(int8_t shift_) { |
1912 | shift = shift_; |
1913 | } |
1914 | void reset() { |
1915 | shift = 63; |
1916 | } |
1917 | |
1918 | private: |
1919 | int8_t shift = 63; |
1920 | }; |
1921 | |
1922 | template < |
1923 | typename K, |
1924 | typename V, |
1925 | typename H = std::hash<K>, |
1926 | typename E = std::equal_to<K>, |
1927 | typename A = std::allocator<std::pair<K, V>>> |
1928 | class flat_hash_map |
1929 | : public detailv3::sherwood_v3_table< |
1930 | std::pair<K, V>, |
1931 | K, |
1932 | H, |
1933 | detailv3::KeyOrValueHasher<K, std::pair<K, V>, H>, |
1934 | E, |
1935 | detailv3::KeyOrValueEquality<K, std::pair<K, V>, E>, |
1936 | A, |
1937 | typename std::allocator_traits<A>::template rebind_alloc< |
1938 | detailv3::sherwood_v3_entry<std::pair<K, V>>>> { |
1939 | using Table = detailv3::sherwood_v3_table< |
1940 | std::pair<K, V>, |
1941 | K, |
1942 | H, |
1943 | detailv3::KeyOrValueHasher<K, std::pair<K, V>, H>, |
1944 | E, |
1945 | detailv3::KeyOrValueEquality<K, std::pair<K, V>, E>, |
1946 | A, |
1947 | typename std::allocator_traits<A>::template rebind_alloc< |
1948 | detailv3::sherwood_v3_entry<std::pair<K, V>>>>; |
1949 | |
1950 | public: |
1951 | using key_type = K; |
1952 | using mapped_type = V; |
1953 | |
1954 | using Table::Table; |
1955 | flat_hash_map() = default; |
1956 | |
1957 | inline V& operator[](const K& key) { |
1958 | return emplace(key, convertible_to_value()).first->second; |
1959 | } |
1960 | inline V& operator[](K&& key) { |
1961 | return emplace(std::move(key), convertible_to_value()).first->second; |
1962 | } |
1963 | V& at(const K& key) { |
1964 | auto found = this->find(key); |
1965 | if (found == this->end()) |
1966 | throw std::out_of_range("Argument passed to at() was not in the map." ); |
1967 | return found->second; |
1968 | } |
1969 | const V& at(const K& key) const { |
1970 | auto found = this->find(key); |
1971 | if (found == this->end()) |
1972 | throw std::out_of_range("Argument passed to at() was not in the map." ); |
1973 | return found->second; |
1974 | } |
1975 | |
1976 | using Table::emplace; |
1977 | std::pair<typename Table::iterator, bool> emplace() { |
1978 | return emplace(key_type(), convertible_to_value()); |
1979 | } |
1980 | template <typename M> |
1981 | std::pair<typename Table::iterator, bool> insert_or_assign( |
1982 | const key_type& key, |
1983 | M&& m) { |
1984 | auto emplace_result = emplace(key, std::forward<M>(m)); |
1985 | if (!emplace_result.second) |
1986 | emplace_result.first->second = std::forward<M>(m); |
1987 | return emplace_result; |
1988 | } |
1989 | template <typename M> |
1990 | std::pair<typename Table::iterator, bool> insert_or_assign( |
1991 | key_type&& key, |
1992 | M&& m) { |
1993 | auto emplace_result = emplace(std::move(key), std::forward<M>(m)); |
1994 | if (!emplace_result.second) |
1995 | emplace_result.first->second = std::forward<M>(m); |
1996 | return emplace_result; |
1997 | } |
1998 | template <typename M> |
1999 | typename Table::iterator insert_or_assign( |
2000 | typename Table::const_iterator, |
2001 | const key_type& key, |
2002 | M&& m) { |
2003 | return insert_or_assign(key, std::forward<M>(m)).first; |
2004 | } |
2005 | template <typename M> |
2006 | typename Table::iterator insert_or_assign( |
2007 | typename Table::const_iterator, |
2008 | key_type&& key, |
2009 | M&& m) { |
2010 | return insert_or_assign(std::move(key), std::forward<M>(m)).first; |
2011 | } |
2012 | |
2013 | friend bool operator==(const flat_hash_map& lhs, const flat_hash_map& rhs) { |
2014 | if (lhs.size() != rhs.size()) |
2015 | return false; |
2016 | for (const typename Table::value_type& value : lhs) { |
2017 | auto found = rhs.find(value.first); |
2018 | if (found == rhs.end()) |
2019 | return false; |
2020 | else if (value.second != found->second) |
2021 | return false; |
2022 | } |
2023 | return true; |
2024 | } |
2025 | friend bool operator!=(const flat_hash_map& lhs, const flat_hash_map& rhs) { |
2026 | return !(lhs == rhs); |
2027 | } |
2028 | |
2029 | private: |
2030 | struct convertible_to_value { |
2031 | operator V() const { |
2032 | return V(); |
2033 | } |
2034 | }; |
2035 | }; |
2036 | |
2037 | template < |
2038 | typename T, |
2039 | typename H = std::hash<T>, |
2040 | typename E = std::equal_to<T>, |
2041 | typename A = std::allocator<T>> |
2042 | class flat_hash_set |
2043 | : public detailv3::sherwood_v3_table< |
2044 | T, |
2045 | T, |
2046 | H, |
2047 | detailv3::functor_storage<uint64_t, H>, |
2048 | E, |
2049 | detailv3::functor_storage<bool, E>, |
2050 | A, |
2051 | typename std::allocator_traits<A>::template rebind_alloc< |
2052 | detailv3::sherwood_v3_entry<T>>> { |
2053 | using Table = detailv3::sherwood_v3_table< |
2054 | T, |
2055 | T, |
2056 | H, |
2057 | detailv3::functor_storage<uint64_t, H>, |
2058 | E, |
2059 | detailv3::functor_storage<bool, E>, |
2060 | A, |
2061 | typename std::allocator_traits<A>::template rebind_alloc< |
2062 | detailv3::sherwood_v3_entry<T>>>; |
2063 | |
2064 | public: |
2065 | using key_type = T; |
2066 | |
2067 | using Table::Table; |
2068 | flat_hash_set() = default; |
2069 | |
2070 | template <typename... Args> |
2071 | std::pair<typename Table::iterator, bool> emplace(Args&&... args) { |
2072 | return Table::emplace(T(std::forward<Args>(args)...)); |
2073 | } |
2074 | std::pair<typename Table::iterator, bool> emplace(const key_type& arg) { |
2075 | return Table::emplace(arg); |
2076 | } |
2077 | std::pair<typename Table::iterator, bool> emplace(key_type& arg) { |
2078 | return Table::emplace(arg); |
2079 | } |
2080 | std::pair<typename Table::iterator, bool> emplace(const key_type&& arg) { |
2081 | return Table::emplace(std::move(arg)); |
2082 | } |
2083 | std::pair<typename Table::iterator, bool> emplace(key_type&& arg) { |
2084 | return Table::emplace(std::move(arg)); |
2085 | } |
2086 | |
2087 | friend bool operator==(const flat_hash_set& lhs, const flat_hash_set& rhs) { |
2088 | if (lhs.size() != rhs.size()) |
2089 | return false; |
2090 | for (const T& value : lhs) { |
2091 | if (rhs.find(value) == rhs.end()) |
2092 | return false; |
2093 | } |
2094 | return true; |
2095 | } |
2096 | friend bool operator!=(const flat_hash_set& lhs, const flat_hash_set& rhs) { |
2097 | return !(lhs == rhs); |
2098 | } |
2099 | }; |
2100 | |
2101 | template <typename T> |
2102 | struct power_of_two_std_hash : std::hash<T> { |
2103 | typedef ska::power_of_two_hash_policy hash_policy; |
2104 | }; |
2105 | |
2106 | } // end namespace ska |
2107 | |
2108 | C10_CLANG_DIAGNOSTIC_POP() |
2109 | |