ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/cf.schmorp.de/Deliantra-Client/flat_hash_map.hpp
Revision: 1.1
Committed: Sun Nov 18 01:43:12 2018 UTC (5 years, 7 months ago) by root
Branch: MAIN
CVS Tags: HEAD
Log Message:
*** empty log message ***

File Contents

# Content
1 // Copyright Malte Skarupke 2017.
2 // Distributed under the Boost Software License, Version 1.0.
3 // (See http://www.boost.org/LICENSE_1_0.txt)
4
5 #pragma once
6
7 #include <cstdint>
8 #include <cstddef>
9 #include <functional>
10 #include <cmath>
11 #include <algorithm>
12 #include <iterator>
13 #include <utility>
14 #include <type_traits>
15
16 #ifdef _MSC_VER
17 #define SKA_NOINLINE(...) __declspec(noinline) __VA_ARGS__
18 #else
19 #define SKA_NOINLINE(...) __VA_ARGS__ __attribute__((noinline))
20 #endif
21
22 namespace ska
23 {
24 struct prime_number_hash_policy;
25 struct power_of_two_hash_policy;
26 struct fibonacci_hash_policy;
27
28 namespace detailv3
29 {
30 template<typename Result, typename Functor>
31 struct functor_storage : Functor
32 {
33 functor_storage() = default;
34 functor_storage(const Functor & functor)
35 : Functor(functor)
36 {
37 }
38 template<typename... Args>
39 Result operator()(Args &&... args)
40 {
41 return static_cast<Functor &>(*this)(std::forward<Args>(args)...);
42 }
43 template<typename... Args>
44 Result operator()(Args &&... args) const
45 {
46 return static_cast<const Functor &>(*this)(std::forward<Args>(args)...);
47 }
48 };
49 template<typename Result, typename... Args>
50 struct functor_storage<Result, Result (*)(Args...)>
51 {
52 typedef Result (*function_ptr)(Args...);
53 function_ptr function;
54 functor_storage(function_ptr function)
55 : function(function)
56 {
57 }
58 Result operator()(Args... args) const
59 {
60 return function(std::forward<Args>(args)...);
61 }
62 operator function_ptr &()
63 {
64 return function;
65 }
66 operator const function_ptr &()
67 {
68 return function;
69 }
70 };
71 template<typename key_type, typename value_type, typename hasher>
72 struct KeyOrValueHasher : functor_storage<size_t, hasher>
73 {
74 typedef functor_storage<size_t, hasher> hasher_storage;
75 KeyOrValueHasher() = default;
76 KeyOrValueHasher(const hasher & hash)
77 : hasher_storage(hash)
78 {
79 }
80 size_t operator()(const key_type & key)
81 {
82 return static_cast<hasher_storage &>(*this)(key);
83 }
84 size_t operator()(const key_type & key) const
85 {
86 return static_cast<const hasher_storage &>(*this)(key);
87 }
88 size_t operator()(const value_type & value)
89 {
90 return static_cast<hasher_storage &>(*this)(value.first);
91 }
92 size_t operator()(const value_type & value) const
93 {
94 return static_cast<const hasher_storage &>(*this)(value.first);
95 }
96 template<typename F, typename S>
97 size_t operator()(const std::pair<F, S> & value)
98 {
99 return static_cast<hasher_storage &>(*this)(value.first);
100 }
101 template<typename F, typename S>
102 size_t operator()(const std::pair<F, S> & value) const
103 {
104 return static_cast<const hasher_storage &>(*this)(value.first);
105 }
106 };
107 template<typename key_type, typename value_type, typename key_equal>
108 struct KeyOrValueEquality : functor_storage<bool, key_equal>
109 {
110 typedef functor_storage<bool, key_equal> equality_storage;
111 KeyOrValueEquality() = default;
112 KeyOrValueEquality(const key_equal & equality)
113 : equality_storage(equality)
114 {
115 }
116 bool operator()(const key_type & lhs, const key_type & rhs)
117 {
118 return static_cast<equality_storage &>(*this)(lhs, rhs);
119 }
120 bool operator()(const key_type & lhs, const value_type & rhs)
121 {
122 return static_cast<equality_storage &>(*this)(lhs, rhs.first);
123 }
124 bool operator()(const value_type & lhs, const key_type & rhs)
125 {
126 return static_cast<equality_storage &>(*this)(lhs.first, rhs);
127 }
128 bool operator()(const value_type & lhs, const value_type & rhs)
129 {
130 return static_cast<equality_storage &>(*this)(lhs.first, rhs.first);
131 }
132 template<typename F, typename S>
133 bool operator()(const key_type & lhs, const std::pair<F, S> & rhs)
134 {
135 return static_cast<equality_storage &>(*this)(lhs, rhs.first);
136 }
137 template<typename F, typename S>
138 bool operator()(const std::pair<F, S> & lhs, const key_type & rhs)
139 {
140 return static_cast<equality_storage &>(*this)(lhs.first, rhs);
141 }
142 template<typename F, typename S>
143 bool operator()(const value_type & lhs, const std::pair<F, S> & rhs)
144 {
145 return static_cast<equality_storage &>(*this)(lhs.first, rhs.first);
146 }
147 template<typename F, typename S>
148 bool operator()(const std::pair<F, S> & lhs, const value_type & rhs)
149 {
150 return static_cast<equality_storage &>(*this)(lhs.first, rhs.first);
151 }
152 template<typename FL, typename SL, typename FR, typename SR>
153 bool operator()(const std::pair<FL, SL> & lhs, const std::pair<FR, SR> & rhs)
154 {
155 return static_cast<equality_storage &>(*this)(lhs.first, rhs.first);
156 }
157 };
158 static constexpr int8_t min_lookups = 4;
159 template<typename T>
160 struct sherwood_v3_entry
161 {
162 sherwood_v3_entry()
163 {
164 }
165 sherwood_v3_entry(int8_t distance_from_desired)
166 : distance_from_desired(distance_from_desired)
167 {
168 }
169 ~sherwood_v3_entry()
170 {
171 }
172 static sherwood_v3_entry * empty_default_table()
173 {
174 static sherwood_v3_entry result[min_lookups] = { {}, {}, {}, {special_end_value} };
175 return result;
176 }
177
178 bool has_value() const
179 {
180 return distance_from_desired >= 0;
181 }
182 bool is_empty() const
183 {
184 return distance_from_desired < 0;
185 }
186 bool is_at_desired_position() const
187 {
188 return distance_from_desired <= 0;
189 }
190 template<typename... Args>
191 void emplace(int8_t distance, Args &&... args)
192 {
193 new (std::addressof(value)) T(std::forward<Args>(args)...);
194 distance_from_desired = distance;
195 }
196
197 void destroy_value()
198 {
199 value.~T();
200 distance_from_desired = -1;
201 }
202
203 int8_t distance_from_desired = -1;
204 static constexpr int8_t special_end_value = 0;
205 union { T value; };
206 };
207
208 inline int8_t log2(size_t value)
209 {
210 static constexpr int8_t table[64] =
211 {
212 63, 0, 58, 1, 59, 47, 53, 2,
213 60, 39, 48, 27, 54, 33, 42, 3,
214 61, 51, 37, 40, 49, 18, 28, 20,
215 55, 30, 34, 11, 43, 14, 22, 4,
216 62, 57, 46, 52, 38, 26, 32, 41,
217 50, 36, 17, 19, 29, 10, 13, 21,
218 56, 45, 25, 31, 35, 16, 9, 12,
219 44, 24, 15, 8, 23, 7, 6, 5
220 };
221 value |= value >> 1;
222 value |= value >> 2;
223 value |= value >> 4;
224 value |= value >> 8;
225 value |= value >> 16;
226 value |= value >> 32;
227 return table[((value - (value >> 1)) * 0x07EDD5E59A4E28C2) >> 58];
228 }
229
230 template<typename T, bool>
231 struct AssignIfTrue
232 {
233 void operator()(T & lhs, const T & rhs)
234 {
235 lhs = rhs;
236 }
237 void operator()(T & lhs, T && rhs)
238 {
239 lhs = std::move(rhs);
240 }
241 };
242 template<typename T>
243 struct AssignIfTrue<T, false>
244 {
245 void operator()(T &, const T &)
246 {
247 }
248 void operator()(T &, T &&)
249 {
250 }
251 };
252
253 inline size_t next_power_of_two(size_t i)
254 {
255 --i;
256 i |= i >> 1;
257 i |= i >> 2;
258 i |= i >> 4;
259 i |= i >> 8;
260 i |= i >> 16;
261 i |= i >> 32;
262 ++i;
263 return i;
264 }
265
266 template<typename...> using void_t = void;
267
268 template<typename T, typename = void>
269 struct HashPolicySelector
270 {
271 typedef fibonacci_hash_policy type;
272 };
273 template<typename T>
274 struct HashPolicySelector<T, void_t<typename T::hash_policy>>
275 {
276 typedef typename T::hash_policy type;
277 };
278
279 template<typename T, typename FindKey, typename ArgumentHash, typename Hasher, typename ArgumentEqual, typename Equal, typename ArgumentAlloc, typename EntryAlloc>
280 class sherwood_v3_table : private EntryAlloc, private Hasher, private Equal
281 {
282 using Entry = detailv3::sherwood_v3_entry<T>;
283 using AllocatorTraits = std::allocator_traits<EntryAlloc>;
284 using EntryPointer = typename AllocatorTraits::pointer;
285 struct convertible_to_iterator;
286
287 public:
288
289 using value_type = T;
290 using size_type = size_t;
291 using difference_type = std::ptrdiff_t;
292 using hasher = ArgumentHash;
293 using key_equal = ArgumentEqual;
294 using allocator_type = EntryAlloc;
295 using reference = value_type &;
296 using const_reference = const value_type &;
297 using pointer = value_type *;
298 using const_pointer = const value_type *;
299
300 sherwood_v3_table()
301 {
302 }
303 explicit sherwood_v3_table(size_type bucket_count, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
304 : EntryAlloc(alloc), Hasher(hash), Equal(equal)
305 {
306 rehash(bucket_count);
307 }
308 sherwood_v3_table(size_type bucket_count, const ArgumentAlloc & alloc)
309 : sherwood_v3_table(bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
310 {
311 }
312 sherwood_v3_table(size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
313 : sherwood_v3_table(bucket_count, hash, ArgumentEqual(), alloc)
314 {
315 }
316 explicit sherwood_v3_table(const ArgumentAlloc & alloc)
317 : EntryAlloc(alloc)
318 {
319 }
320 template<typename It>
321 sherwood_v3_table(It first, It last, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
322 : sherwood_v3_table(bucket_count, hash, equal, alloc)
323 {
324 insert(first, last);
325 }
326 template<typename It>
327 sherwood_v3_table(It first, It last, size_type bucket_count, const ArgumentAlloc & alloc)
328 : sherwood_v3_table(first, last, bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
329 {
330 }
331 template<typename It>
332 sherwood_v3_table(It first, It last, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
333 : sherwood_v3_table(first, last, bucket_count, hash, ArgumentEqual(), alloc)
334 {
335 }
336 sherwood_v3_table(std::initializer_list<T> il, size_type bucket_count = 0, const ArgumentHash & hash = ArgumentHash(), const ArgumentEqual & equal = ArgumentEqual(), const ArgumentAlloc & alloc = ArgumentAlloc())
337 : sherwood_v3_table(bucket_count, hash, equal, alloc)
338 {
339 if (bucket_count == 0)
340 rehash(il.size());
341 insert(il.begin(), il.end());
342 }
343 sherwood_v3_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentAlloc & alloc)
344 : sherwood_v3_table(il, bucket_count, ArgumentHash(), ArgumentEqual(), alloc)
345 {
346 }
347 sherwood_v3_table(std::initializer_list<T> il, size_type bucket_count, const ArgumentHash & hash, const ArgumentAlloc & alloc)
348 : sherwood_v3_table(il, bucket_count, hash, ArgumentEqual(), alloc)
349 {
350 }
351 sherwood_v3_table(const sherwood_v3_table & other)
352 : sherwood_v3_table(other, AllocatorTraits::select_on_container_copy_construction(other.get_allocator()))
353 {
354 }
355 sherwood_v3_table(const sherwood_v3_table & other, const ArgumentAlloc & alloc)
356 : EntryAlloc(alloc), Hasher(other), Equal(other), _max_load_factor(other._max_load_factor)
357 {
358 rehash_for_other_container(other);
359 try
360 {
361 insert(other.begin(), other.end());
362 }
363 catch(...)
364 {
365 clear();
366 deallocate_data(entries, num_slots_minus_one, max_lookups);
367 throw;
368 }
369 }
370 sherwood_v3_table(sherwood_v3_table && other) noexcept
371 : EntryAlloc(std::move(other)), Hasher(std::move(other)), Equal(std::move(other))
372 {
373 swap_pointers(other);
374 }
375 sherwood_v3_table(sherwood_v3_table && other, const ArgumentAlloc & alloc) noexcept
376 : EntryAlloc(alloc), Hasher(std::move(other)), Equal(std::move(other))
377 {
378 swap_pointers(other);
379 }
380 sherwood_v3_table & operator=(const sherwood_v3_table & other)
381 {
382 if (this == std::addressof(other))
383 return *this;
384
385 clear();
386 if (AllocatorTraits::propagate_on_container_copy_assignment::value)
387 {
388 if (static_cast<EntryAlloc &>(*this) != static_cast<const EntryAlloc &>(other))
389 {
390 reset_to_empty_state();
391 }
392 AssignIfTrue<EntryAlloc, AllocatorTraits::propagate_on_container_copy_assignment::value>()(*this, other);
393 }
394 _max_load_factor = other._max_load_factor;
395 static_cast<Hasher &>(*this) = other;
396 static_cast<Equal &>(*this) = other;
397 rehash_for_other_container(other);
398 insert(other.begin(), other.end());
399 return *this;
400 }
401 sherwood_v3_table & operator=(sherwood_v3_table && other) noexcept
402 {
403 if (this == std::addressof(other))
404 return *this;
405 else if (AllocatorTraits::propagate_on_container_move_assignment::value)
406 {
407 clear();
408 reset_to_empty_state();
409 AssignIfTrue<EntryAlloc, AllocatorTraits::propagate_on_container_move_assignment::value>()(*this, std::move(other));
410 swap_pointers(other);
411 }
412 else if (static_cast<EntryAlloc &>(*this) == static_cast<EntryAlloc &>(other))
413 {
414 swap_pointers(other);
415 }
416 else
417 {
418 clear();
419 _max_load_factor = other._max_load_factor;
420 rehash_for_other_container(other);
421 for (T & elem : other)
422 emplace(std::move(elem));
423 other.clear();
424 }
425 static_cast<Hasher &>(*this) = std::move(other);
426 static_cast<Equal &>(*this) = std::move(other);
427 return *this;
428 }
429 ~sherwood_v3_table()
430 {
431 clear();
432 deallocate_data(entries, num_slots_minus_one, max_lookups);
433 }
434
435 const allocator_type & get_allocator() const
436 {
437 return static_cast<const allocator_type &>(*this);
438 }
439 const ArgumentEqual & key_eq() const
440 {
441 return static_cast<const ArgumentEqual &>(*this);
442 }
443 const ArgumentHash & hash_function() const
444 {
445 return static_cast<const ArgumentHash &>(*this);
446 }
447
448 template<typename ValueType>
449 struct templated_iterator
450 {
451 templated_iterator() = default;
452 templated_iterator(EntryPointer current)
453 : current(current)
454 {
455 }
456 EntryPointer current = EntryPointer();
457
458 using iterator_category = std::forward_iterator_tag;
459 using value_type = ValueType;
460 using difference_type = ptrdiff_t;
461 using pointer = ValueType *;
462 using reference = ValueType &;
463
464 friend bool operator==(const templated_iterator & lhs, const templated_iterator & rhs)
465 {
466 return lhs.current == rhs.current;
467 }
468 friend bool operator!=(const templated_iterator & lhs, const templated_iterator & rhs)
469 {
470 return !(lhs == rhs);
471 }
472
473 templated_iterator & operator++()
474 {
475 do
476 {
477 ++current;
478 }
479 while(current->is_empty());
480 return *this;
481 }
482 templated_iterator operator++(int)
483 {
484 templated_iterator copy(*this);
485 ++*this;
486 return copy;
487 }
488
489 ValueType & operator*() const
490 {
491 return current->value;
492 }
493 ValueType * operator->() const
494 {
495 return std::addressof(current->value);
496 }
497
498 operator templated_iterator<const value_type>() const
499 {
500 return { current };
501 }
502 };
503 using iterator = templated_iterator<value_type>;
504 using const_iterator = templated_iterator<const value_type>;
505
506 iterator begin()
507 {
508 for (EntryPointer it = entries;; ++it)
509 {
510 if (it->has_value())
511 return { it };
512 }
513 }
514 const_iterator begin() const
515 {
516 for (EntryPointer it = entries;; ++it)
517 {
518 if (it->has_value())
519 return { it };
520 }
521 }
522 const_iterator cbegin() const
523 {
524 return begin();
525 }
526 iterator end()
527 {
528 return { entries + static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups) };
529 }
530 const_iterator end() const
531 {
532 return { entries + static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups) };
533 }
534 const_iterator cend() const
535 {
536 return end();
537 }
538
539 iterator find(const FindKey & key)
540 {
541 size_t index = hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
542 EntryPointer it = entries + ptrdiff_t(index);
543 for (int8_t distance = 0; it->distance_from_desired >= distance; ++distance, ++it)
544 {
545 if (compares_equal(key, it->value))
546 return { it };
547 }
548 return end();
549 }
550 const_iterator find(const FindKey & key) const
551 {
552 return const_cast<sherwood_v3_table *>(this)->find(key);
553 }
554 size_t count(const FindKey & key) const
555 {
556 return find(key) == end() ? 0 : 1;
557 }
558 std::pair<iterator, iterator> equal_range(const FindKey & key)
559 {
560 iterator found = find(key);
561 if (found == end())
562 return { found, found };
563 else
564 return { found, std::next(found) };
565 }
566 std::pair<const_iterator, const_iterator> equal_range(const FindKey & key) const
567 {
568 const_iterator found = find(key);
569 if (found == end())
570 return { found, found };
571 else
572 return { found, std::next(found) };
573 }
574
575 template<typename Key, typename... Args>
576 std::pair<iterator, bool> emplace(Key && key, Args &&... args)
577 {
578 size_t index = hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
579 EntryPointer current_entry = entries + ptrdiff_t(index);
580 int8_t distance_from_desired = 0;
581 for (; current_entry->distance_from_desired >= distance_from_desired; ++current_entry, ++distance_from_desired)
582 {
583 if (compares_equal(key, current_entry->value))
584 return { { current_entry }, false };
585 }
586 return emplace_new_key(distance_from_desired, current_entry, std::forward<Key>(key), std::forward<Args>(args)...);
587 }
588
589 std::pair<iterator, bool> insert(const value_type & value)
590 {
591 return emplace(value);
592 }
593 std::pair<iterator, bool> insert(value_type && value)
594 {
595 return emplace(std::move(value));
596 }
597 template<typename... Args>
598 iterator emplace_hint(const_iterator, Args &&... args)
599 {
600 return emplace(std::forward<Args>(args)...).first;
601 }
602 iterator insert(const_iterator, const value_type & value)
603 {
604 return emplace(value).first;
605 }
606 iterator insert(const_iterator, value_type && value)
607 {
608 return emplace(std::move(value)).first;
609 }
610
611 template<typename It>
612 void insert(It begin, It end)
613 {
614 for (; begin != end; ++begin)
615 {
616 emplace(*begin);
617 }
618 }
619 void insert(std::initializer_list<value_type> il)
620 {
621 insert(il.begin(), il.end());
622 }
623
624 void rehash(size_t num_buckets)
625 {
626 num_buckets = std::max(num_buckets, static_cast<size_t>(std::ceil(num_elements / static_cast<double>(_max_load_factor))));
627 if (num_buckets == 0)
628 {
629 reset_to_empty_state();
630 return;
631 }
632 auto new_prime_index = hash_policy.next_size_over(num_buckets);
633 if (num_buckets == bucket_count())
634 return;
635 int8_t new_max_lookups = compute_max_lookups(num_buckets);
636 EntryPointer new_buckets(AllocatorTraits::allocate(*this, num_buckets + new_max_lookups));
637 EntryPointer special_end_item = new_buckets + static_cast<ptrdiff_t>(num_buckets + new_max_lookups - 1);
638 for (EntryPointer it = new_buckets; it != special_end_item; ++it)
639 it->distance_from_desired = -1;
640 special_end_item->distance_from_desired = Entry::special_end_value;
641 std::swap(entries, new_buckets);
642 std::swap(num_slots_minus_one, num_buckets);
643 --num_slots_minus_one;
644 hash_policy.commit(new_prime_index);
645 int8_t old_max_lookups = max_lookups;
646 max_lookups = new_max_lookups;
647 num_elements = 0;
648 for (EntryPointer it = new_buckets, end = it + static_cast<ptrdiff_t>(num_buckets + old_max_lookups); it != end; ++it)
649 {
650 if (it->has_value())
651 {
652 emplace(std::move(it->value));
653 it->destroy_value();
654 }
655 }
656 deallocate_data(new_buckets, num_buckets, old_max_lookups);
657 }
658
659 void reserve(size_t num_elements)
660 {
661 size_t required_buckets = num_buckets_for_reserve(num_elements);
662 if (required_buckets > bucket_count())
663 rehash(required_buckets);
664 }
665
666 // the return value is a type that can be converted to an iterator
667 // the reason for doing this is that it's not free to find the
668 // iterator pointing at the next element. if you care about the
669 // next iterator, turn the return value into an iterator
670 convertible_to_iterator erase(const_iterator to_erase)
671 {
672 EntryPointer current = to_erase.current;
673 current->destroy_value();
674 --num_elements;
675 for (EntryPointer next = current + ptrdiff_t(1); !next->is_at_desired_position(); ++current, ++next)
676 {
677 current->emplace(next->distance_from_desired - 1, std::move(next->value));
678 next->destroy_value();
679 }
680 return { to_erase.current };
681 }
682
683 iterator erase(const_iterator begin_it, const_iterator end_it)
684 {
685 if (begin_it == end_it)
686 return { begin_it.current };
687 for (EntryPointer it = begin_it.current, end = end_it.current; it != end; ++it)
688 {
689 if (it->has_value())
690 {
691 it->destroy_value();
692 --num_elements;
693 }
694 }
695 if (end_it == this->end())
696 return this->end();
697 ptrdiff_t num_to_move = std::min(static_cast<ptrdiff_t>(end_it.current->distance_from_desired), end_it.current - begin_it.current);
698 EntryPointer to_return = end_it.current - num_to_move;
699 for (EntryPointer it = end_it.current; !it->is_at_desired_position();)
700 {
701 EntryPointer target = it - num_to_move;
702 target->emplace(it->distance_from_desired - num_to_move, std::move(it->value));
703 it->destroy_value();
704 ++it;
705 num_to_move = std::min(static_cast<ptrdiff_t>(it->distance_from_desired), num_to_move);
706 }
707 return { to_return };
708 }
709
710 size_t erase(const FindKey & key)
711 {
712 auto found = find(key);
713 if (found == end())
714 return 0;
715 else
716 {
717 erase(found);
718 return 1;
719 }
720 }
721
722 void clear()
723 {
724 for (EntryPointer it = entries, end = it + static_cast<ptrdiff_t>(num_slots_minus_one + max_lookups); it != end; ++it)
725 {
726 if (it->has_value())
727 it->destroy_value();
728 }
729 num_elements = 0;
730 }
731
732 void shrink_to_fit()
733 {
734 rehash_for_other_container(*this);
735 }
736
737 void swap(sherwood_v3_table & other)
738 {
739 using std::swap;
740 swap_pointers(other);
741 swap(static_cast<ArgumentHash &>(*this), static_cast<ArgumentHash &>(other));
742 swap(static_cast<ArgumentEqual &>(*this), static_cast<ArgumentEqual &>(other));
743 if (AllocatorTraits::propagate_on_container_swap::value)
744 swap(static_cast<EntryAlloc &>(*this), static_cast<EntryAlloc &>(other));
745 }
746
747 size_t size() const
748 {
749 return num_elements;
750 }
751 size_t max_size() const
752 {
753 return (AllocatorTraits::max_size(*this)) / sizeof(Entry);
754 }
755 size_t bucket_count() const
756 {
757 return num_slots_minus_one ? num_slots_minus_one + 1 : 0;
758 }
759 size_type max_bucket_count() const
760 {
761 return (AllocatorTraits::max_size(*this) - min_lookups) / sizeof(Entry);
762 }
763 size_t bucket(const FindKey & key) const
764 {
765 return hash_policy.index_for_hash(hash_object(key), num_slots_minus_one);
766 }
767 float load_factor() const
768 {
769 size_t buckets = bucket_count();
770 if (buckets)
771 return static_cast<float>(num_elements) / bucket_count();
772 else
773 return 0;
774 }
775 void max_load_factor(float value)
776 {
777 _max_load_factor = value;
778 }
779 float max_load_factor() const
780 {
781 return _max_load_factor;
782 }
783
784 bool empty() const
785 {
786 return num_elements == 0;
787 }
788
789 private:
790 EntryPointer entries = Entry::empty_default_table();
791 size_t num_slots_minus_one = 0;
792 typename HashPolicySelector<ArgumentHash>::type hash_policy;
793 int8_t max_lookups = detailv3::min_lookups - 1;
794 float _max_load_factor = 0.5f;
795 size_t num_elements = 0;
796
797 static int8_t compute_max_lookups(size_t num_buckets)
798 {
799 int8_t desired = detailv3::log2(num_buckets);
800 return std::max(detailv3::min_lookups, desired);
801 }
802
803 size_t num_buckets_for_reserve(size_t num_elements) const
804 {
805 return static_cast<size_t>(std::ceil(num_elements / std::min(0.5, static_cast<double>(_max_load_factor))));
806 }
807 void rehash_for_other_container(const sherwood_v3_table & other)
808 {
809 rehash(std::min(num_buckets_for_reserve(other.size()), other.bucket_count()));
810 }
811
812 void swap_pointers(sherwood_v3_table & other)
813 {
814 using std::swap;
815 swap(hash_policy, other.hash_policy);
816 swap(entries, other.entries);
817 swap(num_slots_minus_one, other.num_slots_minus_one);
818 swap(num_elements, other.num_elements);
819 swap(max_lookups, other.max_lookups);
820 swap(_max_load_factor, other._max_load_factor);
821 }
822
823 template<typename Key, typename... Args>
824 SKA_NOINLINE(std::pair<iterator, bool>) emplace_new_key(int8_t distance_from_desired, EntryPointer current_entry, Key && key, Args &&... args)
825 {
826 using std::swap;
827 if (num_slots_minus_one == 0 || distance_from_desired == max_lookups || num_elements + 1 > (num_slots_minus_one + 1) * static_cast<double>(_max_load_factor))
828 {
829 grow();
830 return emplace(std::forward<Key>(key), std::forward<Args>(args)...);
831 }
832 else if (current_entry->is_empty())
833 {
834 current_entry->emplace(distance_from_desired, std::forward<Key>(key), std::forward<Args>(args)...);
835 ++num_elements;
836 return { { current_entry }, true };
837 }
838 value_type to_insert(std::forward<Key>(key), std::forward<Args>(args)...);
839 swap(distance_from_desired, current_entry->distance_from_desired);
840 swap(to_insert, current_entry->value);
841 iterator result = { current_entry };
842 for (++distance_from_desired, ++current_entry;; ++current_entry)
843 {
844 if (current_entry->is_empty())
845 {
846 current_entry->emplace(distance_from_desired, std::move(to_insert));
847 ++num_elements;
848 return { result, true };
849 }
850 else if (current_entry->distance_from_desired < distance_from_desired)
851 {
852 swap(distance_from_desired, current_entry->distance_from_desired);
853 swap(to_insert, current_entry->value);
854 ++distance_from_desired;
855 }
856 else
857 {
858 ++distance_from_desired;
859 if (distance_from_desired == max_lookups)
860 {
861 swap(to_insert, result.current->value);
862 grow();
863 return emplace(std::move(to_insert));
864 }
865 }
866 }
867 }
868
869 void grow()
870 {
871 rehash(std::max(size_t(4), 2 * bucket_count()));
872 }
873
874 void deallocate_data(EntryPointer begin, size_t num_slots_minus_one, int8_t max_lookups)
875 {
876 if (begin != Entry::empty_default_table())
877 {
878 AllocatorTraits::deallocate(*this, begin, num_slots_minus_one + max_lookups + 1);
879 }
880 }
881
882 void reset_to_empty_state()
883 {
884 deallocate_data(entries, num_slots_minus_one, max_lookups);
885 entries = Entry::empty_default_table();
886 num_slots_minus_one = 0;
887 hash_policy.reset();
888 max_lookups = detailv3::min_lookups - 1;
889 }
890
891 template<typename U>
892 size_t hash_object(const U & key)
893 {
894 return static_cast<Hasher &>(*this)(key);
895 }
896 template<typename U>
897 size_t hash_object(const U & key) const
898 {
899 return static_cast<const Hasher &>(*this)(key);
900 }
901 template<typename L, typename R>
902 bool compares_equal(const L & lhs, const R & rhs)
903 {
904 return static_cast<Equal &>(*this)(lhs, rhs);
905 }
906
907 struct convertible_to_iterator
908 {
909 EntryPointer it;
910
911 operator iterator()
912 {
913 if (it->has_value())
914 return { it };
915 else
916 return ++iterator{it};
917 }
918 operator const_iterator()
919 {
920 if (it->has_value())
921 return { it };
922 else
923 return ++const_iterator{it};
924 }
925 };
926
927 };
928 }
929
930 struct prime_number_hash_policy
931 {
932 static size_t mod0(size_t) { return 0llu; }
933 static size_t mod2(size_t hash) { return hash % 2llu; }
934 static size_t mod3(size_t hash) { return hash % 3llu; }
935 static size_t mod5(size_t hash) { return hash % 5llu; }
936 static size_t mod7(size_t hash) { return hash % 7llu; }
937 static size_t mod11(size_t hash) { return hash % 11llu; }
938 static size_t mod13(size_t hash) { return hash % 13llu; }
939 static size_t mod17(size_t hash) { return hash % 17llu; }
940 static size_t mod23(size_t hash) { return hash % 23llu; }
941 static size_t mod29(size_t hash) { return hash % 29llu; }
942 static size_t mod37(size_t hash) { return hash % 37llu; }
943 static size_t mod47(size_t hash) { return hash % 47llu; }
944 static size_t mod59(size_t hash) { return hash % 59llu; }
945 static size_t mod73(size_t hash) { return hash % 73llu; }
946 static size_t mod97(size_t hash) { return hash % 97llu; }
947 static size_t mod127(size_t hash) { return hash % 127llu; }
948 static size_t mod151(size_t hash) { return hash % 151llu; }
949 static size_t mod197(size_t hash) { return hash % 197llu; }
950 static size_t mod251(size_t hash) { return hash % 251llu; }
951 static size_t mod313(size_t hash) { return hash % 313llu; }
952 static size_t mod397(size_t hash) { return hash % 397llu; }
953 static size_t mod499(size_t hash) { return hash % 499llu; }
954 static size_t mod631(size_t hash) { return hash % 631llu; }
955 static size_t mod797(size_t hash) { return hash % 797llu; }
956 static size_t mod1009(size_t hash) { return hash % 1009llu; }
957 static size_t mod1259(size_t hash) { return hash % 1259llu; }
958 static size_t mod1597(size_t hash) { return hash % 1597llu; }
959 static size_t mod2011(size_t hash) { return hash % 2011llu; }
960 static size_t mod2539(size_t hash) { return hash % 2539llu; }
961 static size_t mod3203(size_t hash) { return hash % 3203llu; }
962 static size_t mod4027(size_t hash) { return hash % 4027llu; }
963 static size_t mod5087(size_t hash) { return hash % 5087llu; }
964 static size_t mod6421(size_t hash) { return hash % 6421llu; }
965 static size_t mod8089(size_t hash) { return hash % 8089llu; }
966 static size_t mod10193(size_t hash) { return hash % 10193llu; }
967 static size_t mod12853(size_t hash) { return hash % 12853llu; }
968 static size_t mod16193(size_t hash) { return hash % 16193llu; }
969 static size_t mod20399(size_t hash) { return hash % 20399llu; }
970 static size_t mod25717(size_t hash) { return hash % 25717llu; }
971 static size_t mod32401(size_t hash) { return hash % 32401llu; }
972 static size_t mod40823(size_t hash) { return hash % 40823llu; }
973 static size_t mod51437(size_t hash) { return hash % 51437llu; }
974 static size_t mod64811(size_t hash) { return hash % 64811llu; }
975 static size_t mod81649(size_t hash) { return hash % 81649llu; }
976 static size_t mod102877(size_t hash) { return hash % 102877llu; }
977 static size_t mod129607(size_t hash) { return hash % 129607llu; }
978 static size_t mod163307(size_t hash) { return hash % 163307llu; }
979 static size_t mod205759(size_t hash) { return hash % 205759llu; }
980 static size_t mod259229(size_t hash) { return hash % 259229llu; }
981 static size_t mod326617(size_t hash) { return hash % 326617llu; }
982 static size_t mod411527(size_t hash) { return hash % 411527llu; }
983 static size_t mod518509(size_t hash) { return hash % 518509llu; }
984 static size_t mod653267(size_t hash) { return hash % 653267llu; }
985 static size_t mod823117(size_t hash) { return hash % 823117llu; }
986 static size_t mod1037059(size_t hash) { return hash % 1037059llu; }
987 static size_t mod1306601(size_t hash) { return hash % 1306601llu; }
988 static size_t mod1646237(size_t hash) { return hash % 1646237llu; }
989 static size_t mod2074129(size_t hash) { return hash % 2074129llu; }
990 static size_t mod2613229(size_t hash) { return hash % 2613229llu; }
991 static size_t mod3292489(size_t hash) { return hash % 3292489llu; }
992 static size_t mod4148279(size_t hash) { return hash % 4148279llu; }
993 static size_t mod5226491(size_t hash) { return hash % 5226491llu; }
994 static size_t mod6584983(size_t hash) { return hash % 6584983llu; }
995 static size_t mod8296553(size_t hash) { return hash % 8296553llu; }
996 static size_t mod10453007(size_t hash) { return hash % 10453007llu; }
997 static size_t mod13169977(size_t hash) { return hash % 13169977llu; }
998 static size_t mod16593127(size_t hash) { return hash % 16593127llu; }
999 static size_t mod20906033(size_t hash) { return hash % 20906033llu; }
1000 static size_t mod26339969(size_t hash) { return hash % 26339969llu; }
1001 static size_t mod33186281(size_t hash) { return hash % 33186281llu; }
1002 static size_t mod41812097(size_t hash) { return hash % 41812097llu; }
1003 static size_t mod52679969(size_t hash) { return hash % 52679969llu; }
1004 static size_t mod66372617(size_t hash) { return hash % 66372617llu; }
1005 static size_t mod83624237(size_t hash) { return hash % 83624237llu; }
1006 static size_t mod105359939(size_t hash) { return hash % 105359939llu; }
1007 static size_t mod132745199(size_t hash) { return hash % 132745199llu; }
1008 static size_t mod167248483(size_t hash) { return hash % 167248483llu; }
1009 static size_t mod210719881(size_t hash) { return hash % 210719881llu; }
1010 static size_t mod265490441(size_t hash) { return hash % 265490441llu; }
1011 static size_t mod334496971(size_t hash) { return hash % 334496971llu; }
1012 static size_t mod421439783(size_t hash) { return hash % 421439783llu; }
1013 static size_t mod530980861(size_t hash) { return hash % 530980861llu; }
1014 static size_t mod668993977(size_t hash) { return hash % 668993977llu; }
1015 static size_t mod842879579(size_t hash) { return hash % 842879579llu; }
1016 static size_t mod1061961721(size_t hash) { return hash % 1061961721llu; }
1017 static size_t mod1337987929(size_t hash) { return hash % 1337987929llu; }
1018 static size_t mod1685759167(size_t hash) { return hash % 1685759167llu; }
1019 static size_t mod2123923447(size_t hash) { return hash % 2123923447llu; }
1020 static size_t mod2675975881(size_t hash) { return hash % 2675975881llu; }
1021 static size_t mod3371518343(size_t hash) { return hash % 3371518343llu; }
1022 static size_t mod4247846927(size_t hash) { return hash % 4247846927llu; }
1023 static size_t mod5351951779(size_t hash) { return hash % 5351951779llu; }
1024 static size_t mod6743036717(size_t hash) { return hash % 6743036717llu; }
1025 static size_t mod8495693897(size_t hash) { return hash % 8495693897llu; }
1026 static size_t mod10703903591(size_t hash) { return hash % 10703903591llu; }
1027 static size_t mod13486073473(size_t hash) { return hash % 13486073473llu; }
1028 static size_t mod16991387857(size_t hash) { return hash % 16991387857llu; }
1029 static size_t mod21407807219(size_t hash) { return hash % 21407807219llu; }
1030 static size_t mod26972146961(size_t hash) { return hash % 26972146961llu; }
1031 static size_t mod33982775741(size_t hash) { return hash % 33982775741llu; }
1032 static size_t mod42815614441(size_t hash) { return hash % 42815614441llu; }
1033 static size_t mod53944293929(size_t hash) { return hash % 53944293929llu; }
1034 static size_t mod67965551447(size_t hash) { return hash % 67965551447llu; }
1035 static size_t mod85631228929(size_t hash) { return hash % 85631228929llu; }
1036 static size_t mod107888587883(size_t hash) { return hash % 107888587883llu; }
1037 static size_t mod135931102921(size_t hash) { return hash % 135931102921llu; }
1038 static size_t mod171262457903(size_t hash) { return hash % 171262457903llu; }
1039 static size_t mod215777175787(size_t hash) { return hash % 215777175787llu; }
1040 static size_t mod271862205833(size_t hash) { return hash % 271862205833llu; }
1041 static size_t mod342524915839(size_t hash) { return hash % 342524915839llu; }
1042 static size_t mod431554351609(size_t hash) { return hash % 431554351609llu; }
1043 static size_t mod543724411781(size_t hash) { return hash % 543724411781llu; }
1044 static size_t mod685049831731(size_t hash) { return hash % 685049831731llu; }
1045 static size_t mod863108703229(size_t hash) { return hash % 863108703229llu; }
1046 static size_t mod1087448823553(size_t hash) { return hash % 1087448823553llu; }
1047 static size_t mod1370099663459(size_t hash) { return hash % 1370099663459llu; }
1048 static size_t mod1726217406467(size_t hash) { return hash % 1726217406467llu; }
1049 static size_t mod2174897647073(size_t hash) { return hash % 2174897647073llu; }
1050 static size_t mod2740199326961(size_t hash) { return hash % 2740199326961llu; }
1051 static size_t mod3452434812973(size_t hash) { return hash % 3452434812973llu; }
1052 static size_t mod4349795294267(size_t hash) { return hash % 4349795294267llu; }
1053 static size_t mod5480398654009(size_t hash) { return hash % 5480398654009llu; }
1054 static size_t mod6904869625999(size_t hash) { return hash % 6904869625999llu; }
1055 static size_t mod8699590588571(size_t hash) { return hash % 8699590588571llu; }
1056 static size_t mod10960797308051(size_t hash) { return hash % 10960797308051llu; }
1057 static size_t mod13809739252051(size_t hash) { return hash % 13809739252051llu; }
1058 static size_t mod17399181177241(size_t hash) { return hash % 17399181177241llu; }
1059 static size_t mod21921594616111(size_t hash) { return hash % 21921594616111llu; }
1060 static size_t mod27619478504183(size_t hash) { return hash % 27619478504183llu; }
1061 static size_t mod34798362354533(size_t hash) { return hash % 34798362354533llu; }
1062 static size_t mod43843189232363(size_t hash) { return hash % 43843189232363llu; }
1063 static size_t mod55238957008387(size_t hash) { return hash % 55238957008387llu; }
1064 static size_t mod69596724709081(size_t hash) { return hash % 69596724709081llu; }
1065 static size_t mod87686378464759(size_t hash) { return hash % 87686378464759llu; }
1066 static size_t mod110477914016779(size_t hash) { return hash % 110477914016779llu; }
1067 static size_t mod139193449418173(size_t hash) { return hash % 139193449418173llu; }
1068 static size_t mod175372756929481(size_t hash) { return hash % 175372756929481llu; }
1069 static size_t mod220955828033581(size_t hash) { return hash % 220955828033581llu; }
1070 static size_t mod278386898836457(size_t hash) { return hash % 278386898836457llu; }
1071 static size_t mod350745513859007(size_t hash) { return hash % 350745513859007llu; }
1072 static size_t mod441911656067171(size_t hash) { return hash % 441911656067171llu; }
1073 static size_t mod556773797672909(size_t hash) { return hash % 556773797672909llu; }
1074 static size_t mod701491027718027(size_t hash) { return hash % 701491027718027llu; }
1075 static size_t mod883823312134381(size_t hash) { return hash % 883823312134381llu; }
1076 static size_t mod1113547595345903(size_t hash) { return hash % 1113547595345903llu; }
1077 static size_t mod1402982055436147(size_t hash) { return hash % 1402982055436147llu; }
1078 static size_t mod1767646624268779(size_t hash) { return hash % 1767646624268779llu; }
1079 static size_t mod2227095190691797(size_t hash) { return hash % 2227095190691797llu; }
1080 static size_t mod2805964110872297(size_t hash) { return hash % 2805964110872297llu; }
1081 static size_t mod3535293248537579(size_t hash) { return hash % 3535293248537579llu; }
1082 static size_t mod4454190381383713(size_t hash) { return hash % 4454190381383713llu; }
1083 static size_t mod5611928221744609(size_t hash) { return hash % 5611928221744609llu; }
1084 static size_t mod7070586497075177(size_t hash) { return hash % 7070586497075177llu; }
1085 static size_t mod8908380762767489(size_t hash) { return hash % 8908380762767489llu; }
1086 static size_t mod11223856443489329(size_t hash) { return hash % 11223856443489329llu; }
1087 static size_t mod14141172994150357(size_t hash) { return hash % 14141172994150357llu; }
1088 static size_t mod17816761525534927(size_t hash) { return hash % 17816761525534927llu; }
1089 static size_t mod22447712886978529(size_t hash) { return hash % 22447712886978529llu; }
1090 static size_t mod28282345988300791(size_t hash) { return hash % 28282345988300791llu; }
1091 static size_t mod35633523051069991(size_t hash) { return hash % 35633523051069991llu; }
1092 static size_t mod44895425773957261(size_t hash) { return hash % 44895425773957261llu; }
1093 static size_t mod56564691976601587(size_t hash) { return hash % 56564691976601587llu; }
1094 static size_t mod71267046102139967(size_t hash) { return hash % 71267046102139967llu; }
1095 static size_t mod89790851547914507(size_t hash) { return hash % 89790851547914507llu; }
1096 static size_t mod113129383953203213(size_t hash) { return hash % 113129383953203213llu; }
1097 static size_t mod142534092204280003(size_t hash) { return hash % 142534092204280003llu; }
1098 static size_t mod179581703095829107(size_t hash) { return hash % 179581703095829107llu; }
1099 static size_t mod226258767906406483(size_t hash) { return hash % 226258767906406483llu; }
1100 static size_t mod285068184408560057(size_t hash) { return hash % 285068184408560057llu; }
1101 static size_t mod359163406191658253(size_t hash) { return hash % 359163406191658253llu; }
1102 static size_t mod452517535812813007(size_t hash) { return hash % 452517535812813007llu; }
1103 static size_t mod570136368817120201(size_t hash) { return hash % 570136368817120201llu; }
1104 static size_t mod718326812383316683(size_t hash) { return hash % 718326812383316683llu; }
1105 static size_t mod905035071625626043(size_t hash) { return hash % 905035071625626043llu; }
1106 static size_t mod1140272737634240411(size_t hash) { return hash % 1140272737634240411llu; }
1107 static size_t mod1436653624766633509(size_t hash) { return hash % 1436653624766633509llu; }
1108 static size_t mod1810070143251252131(size_t hash) { return hash % 1810070143251252131llu; }
1109 static size_t mod2280545475268481167(size_t hash) { return hash % 2280545475268481167llu; }
1110 static size_t mod2873307249533267101(size_t hash) { return hash % 2873307249533267101llu; }
1111 static size_t mod3620140286502504283(size_t hash) { return hash % 3620140286502504283llu; }
1112 static size_t mod4561090950536962147(size_t hash) { return hash % 4561090950536962147llu; }
1113 static size_t mod5746614499066534157(size_t hash) { return hash % 5746614499066534157llu; }
1114 static size_t mod7240280573005008577(size_t hash) { return hash % 7240280573005008577llu; }
1115 static size_t mod9122181901073924329(size_t hash) { return hash % 9122181901073924329llu; }
1116 static size_t mod11493228998133068689(size_t hash) { return hash % 11493228998133068689llu; }
1117 static size_t mod14480561146010017169(size_t hash) { return hash % 14480561146010017169llu; }
1118 static size_t mod18446744073709551557(size_t hash) { return hash % 18446744073709551557llu; }
1119
1120 using mod_function = size_t (*)(size_t);
1121
1122 mod_function next_size_over(size_t & size) const
1123 {
1124 // prime numbers generated by the following method:
1125 // 1. start with a prime p = 2
1126 // 2. go to wolfram alpha and get p = NextPrime(2 * p)
1127 // 3. repeat 2. until you overflow 64 bits
1128 // you now have large gaps which you would hit if somebody called reserve() with an unlucky number.
1129 // 4. to fill the gaps for every prime p go to wolfram alpha and get ClosestPrime(p * 2^(1/3)) and ClosestPrime(p * 2^(2/3)) and put those in the gaps
1130 // 5. get PrevPrime(2^64) and put it at the end
1131 static constexpr const size_t prime_list[] =
1132 {
1133 2llu, 3llu, 5llu, 7llu, 11llu, 13llu, 17llu, 23llu, 29llu, 37llu, 47llu,
1134 59llu, 73llu, 97llu, 127llu, 151llu, 197llu, 251llu, 313llu, 397llu,
1135 499llu, 631llu, 797llu, 1009llu, 1259llu, 1597llu, 2011llu, 2539llu,
1136 3203llu, 4027llu, 5087llu, 6421llu, 8089llu, 10193llu, 12853llu, 16193llu,
1137 20399llu, 25717llu, 32401llu, 40823llu, 51437llu, 64811llu, 81649llu,
1138 102877llu, 129607llu, 163307llu, 205759llu, 259229llu, 326617llu,
1139 411527llu, 518509llu, 653267llu, 823117llu, 1037059llu, 1306601llu,
1140 1646237llu, 2074129llu, 2613229llu, 3292489llu, 4148279llu, 5226491llu,
1141 6584983llu, 8296553llu, 10453007llu, 13169977llu, 16593127llu, 20906033llu,
1142 26339969llu, 33186281llu, 41812097llu, 52679969llu, 66372617llu,
1143 83624237llu, 105359939llu, 132745199llu, 167248483llu, 210719881llu,
1144 265490441llu, 334496971llu, 421439783llu, 530980861llu, 668993977llu,
1145 842879579llu, 1061961721llu, 1337987929llu, 1685759167llu, 2123923447llu,
1146 2675975881llu, 3371518343llu, 4247846927llu, 5351951779llu, 6743036717llu,
1147 8495693897llu, 10703903591llu, 13486073473llu, 16991387857llu,
1148 21407807219llu, 26972146961llu, 33982775741llu, 42815614441llu,
1149 53944293929llu, 67965551447llu, 85631228929llu, 107888587883llu,
1150 135931102921llu, 171262457903llu, 215777175787llu, 271862205833llu,
1151 342524915839llu, 431554351609llu, 543724411781llu, 685049831731llu,
1152 863108703229llu, 1087448823553llu, 1370099663459llu, 1726217406467llu,
1153 2174897647073llu, 2740199326961llu, 3452434812973llu, 4349795294267llu,
1154 5480398654009llu, 6904869625999llu, 8699590588571llu, 10960797308051llu,
1155 13809739252051llu, 17399181177241llu, 21921594616111llu, 27619478504183llu,
1156 34798362354533llu, 43843189232363llu, 55238957008387llu, 69596724709081llu,
1157 87686378464759llu, 110477914016779llu, 139193449418173llu,
1158 175372756929481llu, 220955828033581llu, 278386898836457llu,
1159 350745513859007llu, 441911656067171llu, 556773797672909llu,
1160 701491027718027llu, 883823312134381llu, 1113547595345903llu,
1161 1402982055436147llu, 1767646624268779llu, 2227095190691797llu,
1162 2805964110872297llu, 3535293248537579llu, 4454190381383713llu,
1163 5611928221744609llu, 7070586497075177llu, 8908380762767489llu,
1164 11223856443489329llu, 14141172994150357llu, 17816761525534927llu,
1165 22447712886978529llu, 28282345988300791llu, 35633523051069991llu,
1166 44895425773957261llu, 56564691976601587llu, 71267046102139967llu,
1167 89790851547914507llu, 113129383953203213llu, 142534092204280003llu,
1168 179581703095829107llu, 226258767906406483llu, 285068184408560057llu,
1169 359163406191658253llu, 452517535812813007llu, 570136368817120201llu,
1170 718326812383316683llu, 905035071625626043llu, 1140272737634240411llu,
1171 1436653624766633509llu, 1810070143251252131llu, 2280545475268481167llu,
1172 2873307249533267101llu, 3620140286502504283llu, 4561090950536962147llu,
1173 5746614499066534157llu, 7240280573005008577llu, 9122181901073924329llu,
1174 11493228998133068689llu, 14480561146010017169llu, 18446744073709551557llu
1175 };
1176 static constexpr size_t (* const mod_functions[])(size_t) =
1177 {
1178 &mod0, &mod2, &mod3, &mod5, &mod7, &mod11, &mod13, &mod17, &mod23, &mod29, &mod37,
1179 &mod47, &mod59, &mod73, &mod97, &mod127, &mod151, &mod197, &mod251, &mod313, &mod397,
1180 &mod499, &mod631, &mod797, &mod1009, &mod1259, &mod1597, &mod2011, &mod2539, &mod3203,
1181 &mod4027, &mod5087, &mod6421, &mod8089, &mod10193, &mod12853, &mod16193, &mod20399,
1182 &mod25717, &mod32401, &mod40823, &mod51437, &mod64811, &mod81649, &mod102877,
1183 &mod129607, &mod163307, &mod205759, &mod259229, &mod326617, &mod411527, &mod518509,
1184 &mod653267, &mod823117, &mod1037059, &mod1306601, &mod1646237, &mod2074129,
1185 &mod2613229, &mod3292489, &mod4148279, &mod5226491, &mod6584983, &mod8296553,
1186 &mod10453007, &mod13169977, &mod16593127, &mod20906033, &mod26339969, &mod33186281,
1187 &mod41812097, &mod52679969, &mod66372617, &mod83624237, &mod105359939, &mod132745199,
1188 &mod167248483, &mod210719881, &mod265490441, &mod334496971, &mod421439783,
1189 &mod530980861, &mod668993977, &mod842879579, &mod1061961721, &mod1337987929,
1190 &mod1685759167, &mod2123923447, &mod2675975881, &mod3371518343, &mod4247846927,
1191 &mod5351951779, &mod6743036717, &mod8495693897, &mod10703903591, &mod13486073473,
1192 &mod16991387857, &mod21407807219, &mod26972146961, &mod33982775741, &mod42815614441,
1193 &mod53944293929, &mod67965551447, &mod85631228929, &mod107888587883, &mod135931102921,
1194 &mod171262457903, &mod215777175787, &mod271862205833, &mod342524915839,
1195 &mod431554351609, &mod543724411781, &mod685049831731, &mod863108703229,
1196 &mod1087448823553, &mod1370099663459, &mod1726217406467, &mod2174897647073,
1197 &mod2740199326961, &mod3452434812973, &mod4349795294267, &mod5480398654009,
1198 &mod6904869625999, &mod8699590588571, &mod10960797308051, &mod13809739252051,
1199 &mod17399181177241, &mod21921594616111, &mod27619478504183, &mod34798362354533,
1200 &mod43843189232363, &mod55238957008387, &mod69596724709081, &mod87686378464759,
1201 &mod110477914016779, &mod139193449418173, &mod175372756929481, &mod220955828033581,
1202 &mod278386898836457, &mod350745513859007, &mod441911656067171, &mod556773797672909,
1203 &mod701491027718027, &mod883823312134381, &mod1113547595345903, &mod1402982055436147,
1204 &mod1767646624268779, &mod2227095190691797, &mod2805964110872297, &mod3535293248537579,
1205 &mod4454190381383713, &mod5611928221744609, &mod7070586497075177, &mod8908380762767489,
1206 &mod11223856443489329, &mod14141172994150357, &mod17816761525534927,
1207 &mod22447712886978529, &mod28282345988300791, &mod35633523051069991,
1208 &mod44895425773957261, &mod56564691976601587, &mod71267046102139967,
1209 &mod89790851547914507, &mod113129383953203213, &mod142534092204280003,
1210 &mod179581703095829107, &mod226258767906406483, &mod285068184408560057,
1211 &mod359163406191658253, &mod452517535812813007, &mod570136368817120201,
1212 &mod718326812383316683, &mod905035071625626043, &mod1140272737634240411,
1213 &mod1436653624766633509, &mod1810070143251252131, &mod2280545475268481167,
1214 &mod2873307249533267101, &mod3620140286502504283, &mod4561090950536962147,
1215 &mod5746614499066534157, &mod7240280573005008577, &mod9122181901073924329,
1216 &mod11493228998133068689, &mod14480561146010017169, &mod18446744073709551557
1217 };
1218 const size_t * found = std::lower_bound(std::begin(prime_list), std::end(prime_list) - 1, size);
1219 size = *found;
1220 return mod_functions[1 + found - prime_list];
1221 }
1222 void commit(mod_function new_mod_function)
1223 {
1224 current_mod_function = new_mod_function;
1225 }
1226 void reset()
1227 {
1228 current_mod_function = &mod0;
1229 }
1230
1231 size_t index_for_hash(size_t hash, size_t /*num_slots_minus_one*/) const
1232 {
1233 return current_mod_function(hash);
1234 }
1235 size_t keep_in_range(size_t index, size_t num_slots_minus_one) const
1236 {
1237 return index > num_slots_minus_one ? current_mod_function(index) : index;
1238 }
1239
1240 private:
1241 mod_function current_mod_function = &mod0;
1242 };
1243
1244 struct power_of_two_hash_policy
1245 {
1246 size_t index_for_hash(size_t hash, size_t num_slots_minus_one) const
1247 {
1248 return hash & num_slots_minus_one;
1249 }
1250 size_t keep_in_range(size_t index, size_t num_slots_minus_one) const
1251 {
1252 return index_for_hash(index, num_slots_minus_one);
1253 }
1254 int8_t next_size_over(size_t & size) const
1255 {
1256 size = detailv3::next_power_of_two(size);
1257 return 0;
1258 }
1259 void commit(int8_t)
1260 {
1261 }
1262 void reset()
1263 {
1264 }
1265
1266 };
1267
1268 struct fibonacci_hash_policy
1269 {
1270 size_t index_for_hash(size_t hash, size_t /*num_slots_minus_one*/) const
1271 {
1272 return (11400714819323198485ull * hash) >> shift;
1273 }
1274 size_t keep_in_range(size_t index, size_t num_slots_minus_one) const
1275 {
1276 return index & num_slots_minus_one;
1277 }
1278
1279 int8_t next_size_over(size_t & size) const
1280 {
1281 size = std::max(size_t(2), detailv3::next_power_of_two(size));
1282 return 64 - detailv3::log2(size);
1283 }
1284 void commit(int8_t shift)
1285 {
1286 this->shift = shift;
1287 }
1288 void reset()
1289 {
1290 shift = 63;
1291 }
1292
1293 private:
1294 int8_t shift = 63;
1295 };
1296
1297 template<typename K, typename V, typename H = std::hash<K>, typename E = std::equal_to<K>, typename A = std::allocator<std::pair<K, V> > >
1298 class flat_hash_map
1299 : public detailv3::sherwood_v3_table
1300 <
1301 std::pair<K, V>,
1302 K,
1303 H,
1304 detailv3::KeyOrValueHasher<K, std::pair<K, V>, H>,
1305 E,
1306 detailv3::KeyOrValueEquality<K, std::pair<K, V>, E>,
1307 A,
1308 typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<std::pair<K, V>>>
1309 >
1310 {
1311 using Table = detailv3::sherwood_v3_table
1312 <
1313 std::pair<K, V>,
1314 K,
1315 H,
1316 detailv3::KeyOrValueHasher<K, std::pair<K, V>, H>,
1317 E,
1318 detailv3::KeyOrValueEquality<K, std::pair<K, V>, E>,
1319 A,
1320 typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<std::pair<K, V>>>
1321 >;
1322 public:
1323
1324 using key_type = K;
1325 using mapped_type = V;
1326
1327 using Table::Table;
1328 flat_hash_map()
1329 {
1330 }
1331
1332 inline V & operator[](const K & key)
1333 {
1334 return emplace(key, convertible_to_value()).first->second;
1335 }
1336 inline V & operator[](K && key)
1337 {
1338 return emplace(std::move(key), convertible_to_value()).first->second;
1339 }
1340 V & at(const K & key)
1341 {
1342 auto found = this->find(key);
1343 if (found == this->end())
1344 throw std::out_of_range("Argument passed to at() was not in the map.");
1345 return found->second;
1346 }
1347 const V & at(const K & key) const
1348 {
1349 auto found = this->find(key);
1350 if (found == this->end())
1351 throw std::out_of_range("Argument passed to at() was not in the map.");
1352 return found->second;
1353 }
1354
1355 using Table::emplace;
1356 std::pair<typename Table::iterator, bool> emplace()
1357 {
1358 return emplace(key_type(), convertible_to_value());
1359 }
1360 template<typename M>
1361 std::pair<typename Table::iterator, bool> insert_or_assign(const key_type & key, M && m)
1362 {
1363 auto emplace_result = emplace(key, std::forward<M>(m));
1364 if (!emplace_result.second)
1365 emplace_result.first->second = std::forward<M>(m);
1366 return emplace_result;
1367 }
1368 template<typename M>
1369 std::pair<typename Table::iterator, bool> insert_or_assign(key_type && key, M && m)
1370 {
1371 auto emplace_result = emplace(std::move(key), std::forward<M>(m));
1372 if (!emplace_result.second)
1373 emplace_result.first->second = std::forward<M>(m);
1374 return emplace_result;
1375 }
1376 template<typename M>
1377 typename Table::iterator insert_or_assign(typename Table::const_iterator, const key_type & key, M && m)
1378 {
1379 return insert_or_assign(key, std::forward<M>(m)).first;
1380 }
1381 template<typename M>
1382 typename Table::iterator insert_or_assign(typename Table::const_iterator, key_type && key, M && m)
1383 {
1384 return insert_or_assign(std::move(key), std::forward<M>(m)).first;
1385 }
1386
1387 friend bool operator==(const flat_hash_map & lhs, const flat_hash_map & rhs)
1388 {
1389 if (lhs.size() != rhs.size())
1390 return false;
1391 for (const typename Table::value_type & value : lhs)
1392 {
1393 auto found = rhs.find(value.first);
1394 if (found == rhs.end())
1395 return false;
1396 else if (value.second != found->second)
1397 return false;
1398 }
1399 return true;
1400 }
1401 friend bool operator!=(const flat_hash_map & lhs, const flat_hash_map & rhs)
1402 {
1403 return !(lhs == rhs);
1404 }
1405
1406 private:
1407 struct convertible_to_value
1408 {
1409 operator V() const
1410 {
1411 return V();
1412 }
1413 };
1414 };
1415
1416 template<typename T, typename H = std::hash<T>, typename E = std::equal_to<T>, typename A = std::allocator<T> >
1417 class flat_hash_set
1418 : public detailv3::sherwood_v3_table
1419 <
1420 T,
1421 T,
1422 H,
1423 detailv3::functor_storage<size_t, H>,
1424 E,
1425 detailv3::functor_storage<bool, E>,
1426 A,
1427 typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<T>>
1428 >
1429 {
1430 using Table = detailv3::sherwood_v3_table
1431 <
1432 T,
1433 T,
1434 H,
1435 detailv3::functor_storage<size_t, H>,
1436 E,
1437 detailv3::functor_storage<bool, E>,
1438 A,
1439 typename std::allocator_traits<A>::template rebind_alloc<detailv3::sherwood_v3_entry<T>>
1440 >;
1441 public:
1442
1443 using key_type = T;
1444
1445 using Table::Table;
1446 flat_hash_set()
1447 {
1448 }
1449
1450 template<typename... Args>
1451 std::pair<typename Table::iterator, bool> emplace(Args &&... args)
1452 {
1453 return Table::emplace(T(std::forward<Args>(args)...));
1454 }
1455 std::pair<typename Table::iterator, bool> emplace(const key_type & arg)
1456 {
1457 return Table::emplace(arg);
1458 }
1459 std::pair<typename Table::iterator, bool> emplace(key_type & arg)
1460 {
1461 return Table::emplace(arg);
1462 }
1463 std::pair<typename Table::iterator, bool> emplace(const key_type && arg)
1464 {
1465 return Table::emplace(std::move(arg));
1466 }
1467 std::pair<typename Table::iterator, bool> emplace(key_type && arg)
1468 {
1469 return Table::emplace(std::move(arg));
1470 }
1471
1472 friend bool operator==(const flat_hash_set & lhs, const flat_hash_set & rhs)
1473 {
1474 if (lhs.size() != rhs.size())
1475 return false;
1476 for (const T & value : lhs)
1477 {
1478 if (rhs.find(value) == rhs.end())
1479 return false;
1480 }
1481 return true;
1482 }
1483 friend bool operator!=(const flat_hash_set & lhs, const flat_hash_set & rhs)
1484 {
1485 return !(lhs == rhs);
1486 }
1487 };
1488
1489
1490 template<typename T>
1491 struct power_of_two_std_hash : std::hash<T>
1492 {
1493 typedef ska::power_of_two_hash_policy hash_policy;
1494 };
1495
1496 } // end namespace ska