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