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, 8 months ago) by root
Branch: MAIN
CVS Tags: HEAD
Log Message:
*** empty log message ***

File Contents

# User Rev Content
1 root 1.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