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