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