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