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