Seregon/ShadPKG

A tool for deriving PKG packet encryption keys for ps4 written in c++

C++/47.3 KB/No license
external/tsl/robin_hash.h
raw
ShadPKG / external / tsl / robin_hash.h
1/**
2 * MIT License
3 *
4 * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24#ifndef TSL_ROBIN_HASH_H
25#define TSL_ROBIN_HASH_H
26 
27#include <algorithm>
28#include <cassert>
29#include <cmath>
30#include <cstddef>
31#include <cstdint>
32#include <exception>
33#include <iterator>
34#include <limits>
35#include <memory>
36#include <new>
37#include <stdexcept>
38#include <tuple>
39#include <type_traits>
40#include <utility>
41#include <vector>
42 
43#include "robin_growth_policy.h"
44 
45namespace tsl {
46 
47namespace detail_robin_hash {
48 
49template <typename T>
50struct make_void {
51 using type = void;
52};
53 
54template <typename T, typename = void>
55struct has_is_transparent : std::false_type {};
56 
57template <typename T>
58struct has_is_transparent<T,
59 typename make_void<typename T::is_transparent>::type>
60 : std::true_type {};
61 
62template <typename U>
63struct is_power_of_two_policy : std::false_type {};
64 
65template <std::size_t GrowthFactor>
66struct is_power_of_two_policy<tsl::rh::power_of_two_growth_policy<GrowthFactor>>
67 : std::true_type {};
68 
69template <typename T, typename U>
70static T numeric_cast(U value,
71 const char* error_message = "numeric_cast() failed.") {
72 T ret = static_cast<T>(value);
73 if (static_cast<U>(ret) != value) {
74 TSL_RH_THROW_OR_TERMINATE(std::runtime_error, error_message);
75 }
76 
77 const bool is_same_signedness =
78 (std::is_unsigned<T>::value && std::is_unsigned<U>::value) ||
79 (std::is_signed<T>::value && std::is_signed<U>::value);
80 if (!is_same_signedness && (ret < T{}) != (value < U{})) {
81 TSL_RH_THROW_OR_TERMINATE(std::runtime_error, error_message);
82 }
83 
84 TSL_RH_UNUSED(error_message);
85 
86 return ret;
87}
88 
89template <class T, class Deserializer>
90static T deserialize_value(Deserializer& deserializer) {
91 // MSVC < 2017 is not conformant, circumvent the problem by removing the
92 // template keyword
93#if defined(_MSC_VER) && _MSC_VER < 1910
94 return deserializer.Deserializer::operator()<T>();
95#else
96 return deserializer.Deserializer::template operator()<T>();
97#endif
98}
99 
100/**
101 * Fixed size type used to represent size_type values on serialization. Need to
102 * be big enough to represent a std::size_t on 32 and 64 bits platforms, and
103 * must be the same size on both platforms.
104 */
105using slz_size_type = std::uint64_t;
106static_assert(std::numeric_limits<slz_size_type>::max() >=
107 std::numeric_limits<std::size_t>::max(),
108 "slz_size_type must be >= std::size_t");
109 
110using truncated_hash_type = std::uint32_t;
111 
112/**
113 * Helper class that stores a truncated hash if StoreHash is true and nothing
114 * otherwise.
115 */
116template <bool StoreHash>
117class bucket_entry_hash {
118 public:
119 bool bucket_hash_equal(std::size_t /*hash*/) const noexcept { return true; }
120 
121 truncated_hash_type truncated_hash() const noexcept { return 0; }
122 
123 protected:
124 void set_hash(truncated_hash_type /*hash*/) noexcept {}
125};
126 
127template <>
128class bucket_entry_hash<true> {
129 public:
130 bool bucket_hash_equal(std::size_t hash) const noexcept {
131 return m_hash == truncated_hash_type(hash);
132 }
133 
134 truncated_hash_type truncated_hash() const noexcept { return m_hash; }
135 
136 protected:
137 void set_hash(truncated_hash_type hash) noexcept {
138 m_hash = truncated_hash_type(hash);
139 }
140 
141 private:
142 truncated_hash_type m_hash;
143};
144 
145/**
146 * Each bucket entry has:
147 * - A value of type `ValueType`.
148 * - An integer to store how far the value of the bucket, if any, is from its
149 * ideal bucket (ex: if the current bucket 5 has the value 'foo' and
150 * `hash('foo') % nb_buckets` == 3, `dist_from_ideal_bucket()` will return 2 as
151 * the current value of the bucket is two buckets away from its ideal bucket) If
152 * there is no value in the bucket (i.e. `empty()` is true)
153 * `dist_from_ideal_bucket()` will be < 0.
154 * - A marker which tells us if the bucket is the last bucket of the bucket
155 * array (useful for the iterator of the hash table).
156 * - If `StoreHash` is true, 32 bits of the hash of the value, if any, are also
157 * stored in the bucket. If the size of the hash is more than 32 bits, it is
158 * truncated. We don't store the full hash as storing the hash is a potential
159 * opportunity to use the unused space due to the alignment of the bucket_entry
160 * structure. We can thus potentially store the hash without any extra space
161 * (which would not be possible with 64 bits of the hash).
162 */
163template <typename ValueType, bool StoreHash>
164class bucket_entry : public bucket_entry_hash<StoreHash> {
165 using bucket_hash = bucket_entry_hash<StoreHash>;
166 
167 public:
168 using value_type = ValueType;
169 using distance_type = std::int16_t;
170 
171 bucket_entry() noexcept
172 : bucket_hash(),
173 m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
174 m_last_bucket(false) {
175 tsl_rh_assert(empty());
176 }
177 
178 bucket_entry(bool last_bucket) noexcept
179 : bucket_hash(),
180 m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
181 m_last_bucket(last_bucket) {
182 tsl_rh_assert(empty());
183 }
184 
185 bucket_entry(const bucket_entry& other) noexcept(
186 std::is_nothrow_copy_constructible<value_type>::value)
187 : bucket_hash(other),
188 m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
189 m_last_bucket(other.m_last_bucket) {
190 if (!other.empty()) {
191 ::new (static_cast<void*>(std::addressof(m_value)))
192 value_type(other.value());
193 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
194 }
195 tsl_rh_assert(empty() == other.empty());
196 }
197 
198 /**
199 * Never really used, but still necessary as we must call resize on an empty
200 * `std::vector<bucket_entry>`. and we need to support move-only types. See
201 * robin_hash constructor for details.
202 */
203 bucket_entry(bucket_entry&& other) noexcept(
204 std::is_nothrow_move_constructible<value_type>::value)
205 : bucket_hash(std::move(other)),
206 m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
207 m_last_bucket(other.m_last_bucket) {
208 if (!other.empty()) {
209 ::new (static_cast<void*>(std::addressof(m_value)))
210 value_type(std::move(other.value()));
211 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
212 }
213 tsl_rh_assert(empty() == other.empty());
214 }
215 
216 bucket_entry& operator=(const bucket_entry& other) noexcept(
217 std::is_nothrow_copy_constructible<value_type>::value) {
218 if (this != &other) {
219 clear();
220 
221 bucket_hash::operator=(other);
222 if (!other.empty()) {
223 ::new (static_cast<void*>(std::addressof(m_value)))
224 value_type(other.value());
225 }
226 
227 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
228 m_last_bucket = other.m_last_bucket;
229 }
230 
231 return *this;
232 }
233 
234 bucket_entry& operator=(bucket_entry&&) = delete;
235 
236 ~bucket_entry() noexcept { clear(); }
237 
238 void clear() noexcept {
239 if (!empty()) {
240 destroy_value();
241 m_dist_from_ideal_bucket = EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET;
242 }
243 }
244 
245 bool empty() const noexcept {
246 return m_dist_from_ideal_bucket == EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET;
247 }
248 
249 value_type& value() noexcept {
250 tsl_rh_assert(!empty());
251 return *std::launder(
252 reinterpret_cast<value_type*>(std::addressof(m_value)));
253 }
254 
255 const value_type& value() const noexcept {
256 tsl_rh_assert(!empty());
257 return *std::launder(
258 reinterpret_cast<const value_type*>(std::addressof(m_value)));
259 }
260 
261 distance_type dist_from_ideal_bucket() const noexcept {
262 return m_dist_from_ideal_bucket;
263 }
264 
265 bool last_bucket() const noexcept { return m_last_bucket; }
266 
267 void set_as_last_bucket() noexcept { m_last_bucket = true; }
268 
269 template <typename... Args>
270 void set_value_of_empty_bucket(distance_type dist_from_ideal_bucket,
271 truncated_hash_type hash,
272 Args&&... value_type_args) {
273 tsl_rh_assert(dist_from_ideal_bucket >= 0);
274 tsl_rh_assert(empty());
275 
276 ::new (static_cast<void*>(std::addressof(m_value)))
277 value_type(std::forward<Args>(value_type_args)...);
278 this->set_hash(hash);
279 m_dist_from_ideal_bucket = dist_from_ideal_bucket;
280 
281 tsl_rh_assert(!empty());
282 }
283 
284 void swap_with_value_in_bucket(distance_type& dist_from_ideal_bucket,
285 truncated_hash_type& hash, value_type& value) {
286 tsl_rh_assert(!empty());
287 tsl_rh_assert(dist_from_ideal_bucket > m_dist_from_ideal_bucket);
288 
289 using std::swap;
290 swap(value, this->value());
291 swap(dist_from_ideal_bucket, m_dist_from_ideal_bucket);
292 
293 if (StoreHash) {
294 const truncated_hash_type tmp_hash = this->truncated_hash();
295 this->set_hash(hash);
296 hash = tmp_hash;
297 } else {
298 // Avoid warning of unused variable if StoreHash is false
299 TSL_RH_UNUSED(hash);
300 }
301 }
302 
303 static truncated_hash_type truncate_hash(std::size_t hash) noexcept {
304 return truncated_hash_type(hash);
305 }
306 
307 private:
308 void destroy_value() noexcept {
309 tsl_rh_assert(!empty());
310 value().~value_type();
311 }
312 
313 public:
314 static const distance_type EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1;
315 static const distance_type DIST_FROM_IDEAL_BUCKET_LIMIT = 8192;
316 static_assert(DIST_FROM_IDEAL_BUCKET_LIMIT <=
317 std::numeric_limits<distance_type>::max() - 1,
318 "DIST_FROM_IDEAL_BUCKET_LIMIT must be <= "
319 "std::numeric_limits<distance_type>::max() - 1.");
320 
321 private:
322 distance_type m_dist_from_ideal_bucket;
323 bool m_last_bucket;
324 alignas(value_type) unsigned char m_value[sizeof(value_type)];
325};
326 
327/**
328 * Internal common class used by `robin_map` and `robin_set`.
329 *
330 * ValueType is what will be stored by `robin_hash` (usually `std::pair<Key, T>`
331 * for map and `Key` for set).
332 *
333 * `KeySelect` should be a `FunctionObject` which takes a `ValueType` in
334 * parameter and returns a reference to the key.
335 *
336 * `ValueSelect` should be a `FunctionObject` which takes a `ValueType` in
337 * parameter and returns a reference to the value. `ValueSelect` should be void
338 * if there is no value (in a set for example).
339 *
340 * The strong exception guarantee only holds if the expression
341 * `std::is_nothrow_swappable<ValueType>::value &&
342 * std::is_nothrow_move_constructible<ValueType>::value` is true.
343 *
344 * Behaviour is undefined if the destructor of `ValueType` throws.
345 */
346template <class ValueType, class KeySelect, class ValueSelect, class Hash,
347 class KeyEqual, class Allocator, bool StoreHash, class GrowthPolicy>
348class robin_hash : private Hash, private KeyEqual, private GrowthPolicy {
349 private:
350 template <typename U>
351 using has_mapped_type =
352 typename std::integral_constant<bool, !std::is_same<U, void>::value>;
353 
354 static_assert(
355 noexcept(std::declval<GrowthPolicy>().bucket_for_hash(std::size_t(0))),
356 "GrowthPolicy::bucket_for_hash must be noexcept.");
357 static_assert(noexcept(std::declval<GrowthPolicy>().clear()),
358 "GrowthPolicy::clear must be noexcept.");
359 
360 public:
361 template <bool IsConst>
362 class robin_iterator;
363 
364 using key_type = typename KeySelect::key_type;
365 using value_type = ValueType;
366 using size_type = std::size_t;
367 using difference_type = std::ptrdiff_t;
368 using hasher = Hash;
369 using key_equal = KeyEqual;
370 using allocator_type = Allocator;
371 using reference = value_type&;
372 using const_reference = const value_type&;
373 using pointer = value_type*;
374 using const_pointer = const value_type*;
375 using iterator = robin_iterator<false>;
376 using const_iterator = robin_iterator<true>;
377 
378 private:
379 /**
380 * Either store the hash because we are asked by the `StoreHash` template
381 * parameter or store the hash because it doesn't cost us anything in size and
382 * can be used to speed up rehash.
383 */
384 static constexpr bool STORE_HASH =
385 StoreHash ||
386 ((sizeof(tsl::detail_robin_hash::bucket_entry<value_type, true>) ==
387 sizeof(tsl::detail_robin_hash::bucket_entry<value_type, false>)) &&
388 (sizeof(std::size_t) == sizeof(truncated_hash_type) ||
389 is_power_of_two_policy<GrowthPolicy>::value) &&
390 // Don't store the hash for primitive types with default hash.
391 (!std::is_arithmetic<key_type>::value ||
392 !std::is_same<Hash, std::hash<key_type>>::value));
393 
394 /**
395 * Only use the stored hash on lookup if we are explicitly asked. We are not
396 * sure how slow the KeyEqual operation is. An extra comparison may slow
397 * things down with a fast KeyEqual.
398 */
399 static constexpr bool USE_STORED_HASH_ON_LOOKUP = StoreHash;
400 
401 /**
402 * We can only use the hash on rehash if the size of the hash type is the same
403 * as the stored one or if we use a power of two modulo. In the case of the
404 * power of two modulo, we just mask the least significant bytes, we just have
405 * to check that the truncated_hash_type didn't truncated more bytes.
406 */
407 static bool USE_STORED_HASH_ON_REHASH(size_type bucket_count) {
408 if (STORE_HASH && sizeof(std::size_t) == sizeof(truncated_hash_type)) {
409 TSL_RH_UNUSED(bucket_count);
410 return true;
411 } else if (STORE_HASH && is_power_of_two_policy<GrowthPolicy>::value) {
412 return bucket_count == 0 ||
413 (bucket_count - 1) <=
414 std::numeric_limits<truncated_hash_type>::max();
415 } else {
416 TSL_RH_UNUSED(bucket_count);
417 return false;
418 }
419 }
420 
421 using bucket_entry =
422 tsl::detail_robin_hash::bucket_entry<value_type, STORE_HASH>;
423 using distance_type = typename bucket_entry::distance_type;
424 
425 using buckets_allocator = typename std::allocator_traits<
426 allocator_type>::template rebind_alloc<bucket_entry>;
427 using buckets_container_type = std::vector<bucket_entry, buckets_allocator>;
428 
429 public:
430 /**
431 * The 'operator*()' and 'operator->()' methods return a const reference and
432 * const pointer respectively to the stored value type.
433 *
434 * In case of a map, to get a mutable reference to the value associated to a
435 * key (the '.second' in the stored pair), you have to call 'value()'.
436 *
437 * The main reason for this is that if we returned a `std::pair<Key, T>&`
438 * instead of a `const std::pair<Key, T>&`, the user may modify the key which
439 * will put the map in a undefined state.
440 */
441 template <bool IsConst>
442 class robin_iterator {
443 friend class robin_hash;
444 
445 private:
446 using bucket_entry_ptr =
447 typename std::conditional<IsConst, const bucket_entry*,
448 bucket_entry*>::type;
449 
450 robin_iterator(bucket_entry_ptr bucket) noexcept : m_bucket(bucket) {}
451 
452 public:
453 using iterator_category = std::forward_iterator_tag;
454 using value_type = const typename robin_hash::value_type;
455 using difference_type = std::ptrdiff_t;
456 using reference = value_type&;
457 using pointer = value_type*;
458 
459 robin_iterator() noexcept {}
460 
461 // Copy constructor from iterator to const_iterator.
462 template <bool TIsConst = IsConst,
463 typename std::enable_if<TIsConst>::type* = nullptr>
464 robin_iterator(const robin_iterator<!TIsConst>& other) noexcept
465 : m_bucket(other.m_bucket) {}
466 
467 robin_iterator(const robin_iterator& other) = default;
468 robin_iterator(robin_iterator&& other) = default;
469 robin_iterator& operator=(const robin_iterator& other) = default;
470 robin_iterator& operator=(robin_iterator&& other) = default;
471 
472 const typename robin_hash::key_type& key() const {
473 return KeySelect()(m_bucket->value());
474 }
475 
476 template <class U = ValueSelect,
477 typename std::enable_if<has_mapped_type<U>::value &&
478 IsConst>::type* = nullptr>
479 const typename U::value_type& value() const {
480 return U()(m_bucket->value());
481 }
482 
483 template <class U = ValueSelect,
484 typename std::enable_if<has_mapped_type<U>::value &&
485 !IsConst>::type* = nullptr>
486 typename U::value_type& value() const {
487 return U()(m_bucket->value());
488 }
489 
490 reference operator*() const { return m_bucket->value(); }
491 
492 pointer operator->() const { return std::addressof(m_bucket->value()); }
493 
494 robin_iterator& operator++() {
495 while (true) {
496 if (m_bucket->last_bucket()) {
497 ++m_bucket;
498 return *this;
499 }
500 
501 ++m_bucket;
502 if (!m_bucket->empty()) {
503 return *this;
504 }
505 }
506 }
507 
508 robin_iterator operator++(int) {
509 robin_iterator tmp(*this);
510 ++*this;
511 
512 return tmp;
513 }
514 
515 friend bool operator==(const robin_iterator& lhs,
516 const robin_iterator& rhs) {
517 return lhs.m_bucket == rhs.m_bucket;
518 }
519 
520 friend bool operator!=(const robin_iterator& lhs,
521 const robin_iterator& rhs) {
522 return !(lhs == rhs);
523 }
524 
525 private:
526 bucket_entry_ptr m_bucket;
527 };
528 
529 public:
530 robin_hash(size_type bucket_count, const Hash& hash, const KeyEqual& equal,
531 const Allocator& alloc,
532 float min_load_factor = DEFAULT_MIN_LOAD_FACTOR,
533 float max_load_factor = DEFAULT_MAX_LOAD_FACTOR)
534 : Hash(hash),
535 KeyEqual(equal),
536 GrowthPolicy(bucket_count),
537 m_buckets_data(bucket_count, alloc),
538 m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr()
539 : m_buckets_data.data()),
540 m_bucket_count(bucket_count),
541 m_nb_elements(0),
542 m_grow_on_next_insert(false),
543 m_try_shrink_on_next_insert(false) {
544 if (bucket_count > max_bucket_count()) {
545 TSL_RH_THROW_OR_TERMINATE(std::length_error,
546 "The map exceeds its maximum bucket count.");
547 }
548 
549 if (m_bucket_count > 0) {
550 tsl_rh_assert(!m_buckets_data.empty());
551 m_buckets_data.back().set_as_last_bucket();
552 }
553 
554 this->min_load_factor(min_load_factor);
555 this->max_load_factor(max_load_factor);
556 }
557 
558 robin_hash(const robin_hash& other)
559 : Hash(other),
560 KeyEqual(other),
561 GrowthPolicy(other),
562 m_buckets_data(other.m_buckets_data),
563 m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr()
564 : m_buckets_data.data()),
565 m_bucket_count(other.m_bucket_count),
566 m_nb_elements(other.m_nb_elements),
567 m_load_threshold(other.m_load_threshold),
568 m_min_load_factor(other.m_min_load_factor),
569 m_max_load_factor(other.m_max_load_factor),
570 m_grow_on_next_insert(other.m_grow_on_next_insert),
571 m_try_shrink_on_next_insert(other.m_try_shrink_on_next_insert) {}
572 
573 robin_hash(robin_hash&& other) noexcept(
574 std::is_nothrow_move_constructible<
575 Hash>::value&& std::is_nothrow_move_constructible<KeyEqual>::value&&
576 std::is_nothrow_move_constructible<GrowthPolicy>::value&&
577 std::is_nothrow_move_constructible<buckets_container_type>::value)
578 : Hash(std::move(static_cast<Hash&>(other))),
579 KeyEqual(std::move(static_cast<KeyEqual&>(other))),
580 GrowthPolicy(std::move(static_cast<GrowthPolicy&>(other))),
581 m_buckets_data(std::move(other.m_buckets_data)),
582 m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr()
583 : m_buckets_data.data()),
584 m_bucket_count(other.m_bucket_count),
585 m_nb_elements(other.m_nb_elements),
586 m_load_threshold(other.m_load_threshold),
587 m_min_load_factor(other.m_min_load_factor),
588 m_max_load_factor(other.m_max_load_factor),
589 m_grow_on_next_insert(other.m_grow_on_next_insert),
590 m_try_shrink_on_next_insert(other.m_try_shrink_on_next_insert) {
591 other.clear_and_shrink();
592 }
593 
594 robin_hash& operator=(const robin_hash& other) {
595 if (&other != this) {
596 Hash::operator=(other);
597 KeyEqual::operator=(other);
598 GrowthPolicy::operator=(other);
599 
600 m_buckets_data = other.m_buckets_data;
601 m_buckets = m_buckets_data.empty() ? static_empty_bucket_ptr()
602 : m_buckets_data.data();
603 m_bucket_count = other.m_bucket_count;
604 m_nb_elements = other.m_nb_elements;
605 
606 m_load_threshold = other.m_load_threshold;
607 m_min_load_factor = other.m_min_load_factor;
608 m_max_load_factor = other.m_max_load_factor;
609 
610 m_grow_on_next_insert = other.m_grow_on_next_insert;
611 m_try_shrink_on_next_insert = other.m_try_shrink_on_next_insert;
612 }
613 
614 return *this;
615 }
616 
617 robin_hash& operator=(robin_hash&& other) {
618 other.swap(*this);
619 other.clear_and_shrink();
620 
621 return *this;
622 }
623 
624 allocator_type get_allocator() const {
625 return m_buckets_data.get_allocator();
626 }
627 
628 /*
629 * Iterators
630 */
631 iterator begin() noexcept {
632 std::size_t i = 0;
633 while (i < m_bucket_count && m_buckets[i].empty()) {
634 i++;
635 }
636 
637 return iterator(m_buckets + i);
638 }
639 
640 const_iterator begin() const noexcept { return cbegin(); }
641 
642 const_iterator cbegin() const noexcept {
643 std::size_t i = 0;
644 while (i < m_bucket_count && m_buckets[i].empty()) {
645 i++;
646 }
647 
648 return const_iterator(m_buckets + i);
649 }
650 
651 iterator end() noexcept { return iterator(m_buckets + m_bucket_count); }
652 
653 const_iterator end() const noexcept { return cend(); }
654 
655 const_iterator cend() const noexcept {
656 return const_iterator(m_buckets + m_bucket_count);
657 }
658 
659 /*
660 * Capacity
661 */
662 bool empty() const noexcept { return m_nb_elements == 0; }
663 
664 size_type size() const noexcept { return m_nb_elements; }
665 
666 size_type max_size() const noexcept { return m_buckets_data.max_size(); }
667 
668 /*
669 * Modifiers
670 */
671 void clear() noexcept {
672 if (m_min_load_factor > 0.0f) {
673 clear_and_shrink();
674 } else {
675 for (auto& bucket : m_buckets_data) {
676 bucket.clear();
677 }
678 
679 m_nb_elements = 0;
680 m_grow_on_next_insert = false;
681 }
682 }
683 
684 template <typename P>
685 std::pair<iterator, bool> insert(P&& value) {
686 return insert_impl(KeySelect()(value), std::forward<P>(value));
687 }
688 
689 template <typename P>
690 iterator insert_hint(const_iterator hint, P&& value) {
691 if (hint != cend() &&
692 compare_keys(KeySelect()(*hint), KeySelect()(value))) {
693 return mutable_iterator(hint);
694 }
695 
696 return insert(std::forward<P>(value)).first;
697 }
698 
699 template <class InputIt>
700 void insert(InputIt first, InputIt last) {
701 if (std::is_base_of<
702 std::forward_iterator_tag,
703 typename std::iterator_traits<InputIt>::iterator_category>::value) {
704 const auto nb_elements_insert = std::distance(first, last);
705 const size_type nb_free_buckets = m_load_threshold - size();
706 tsl_rh_assert(m_load_threshold >= size());
707 
708 if (nb_elements_insert > 0 &&
709 nb_free_buckets < size_type(nb_elements_insert)) {
710 reserve(size() + size_type(nb_elements_insert));
711 }
712 }
713 
714 for (; first != last; ++first) {
715 insert(*first);
716 }
717 }
718 
719 template <class K, class M>
720 std::pair<iterator, bool> insert_or_assign(K&& key, M&& obj) {
721 auto it = try_emplace(std::forward<K>(key), std::forward<M>(obj));
722 if (!it.second) {
723 it.first.value() = std::forward<M>(obj);
724 }
725 
726 return it;
727 }
728 
729 template <class K, class M>
730 iterator insert_or_assign(const_iterator hint, K&& key, M&& obj) {
731 if (hint != cend() && compare_keys(KeySelect()(*hint), key)) {
732 auto it = mutable_iterator(hint);
733 it.value() = std::forward<M>(obj);
734 
735 return it;
736 }
737 
738 return insert_or_assign(std::forward<K>(key), std::forward<M>(obj)).first;
739 }
740 
741 template <class... Args>
742 std::pair<iterator, bool> emplace(Args&&... args) {
743 return insert(value_type(std::forward<Args>(args)...));
744 }
745 
746 template <class... Args>
747 iterator emplace_hint(const_iterator hint, Args&&... args) {
748 return insert_hint(hint, value_type(std::forward<Args>(args)...));
749 }
750 
751 template <class K, class... Args>
752 std::pair<iterator, bool> try_emplace(K&& key, Args&&... args) {
753 return insert_impl(key, std::piecewise_construct,
754 std::forward_as_tuple(std::forward<K>(key)),
755 std::forward_as_tuple(std::forward<Args>(args)...));
756 }
757 
758 template <class K, class... Args>
759 iterator try_emplace_hint(const_iterator hint, K&& key, Args&&... args) {
760 if (hint != cend() && compare_keys(KeySelect()(*hint), key)) {
761 return mutable_iterator(hint);
762 }
763 
764 return try_emplace(std::forward<K>(key), std::forward<Args>(args)...).first;
765 }
766 
767 void erase_fast(iterator pos) {
768 erase_from_bucket(pos);
769 }
770 
771 /**
772 * Here to avoid `template<class K> size_type erase(const K& key)` being used
773 * when we use an `iterator` instead of a `const_iterator`.
774 */
775 iterator erase(iterator pos) {
776 erase_from_bucket(pos);
777 
778 /**
779 * Erase bucket used a backward shift after clearing the bucket.
780 * Check if there is a new value in the bucket, if not get the next
781 * non-empty.
782 */
783 if (pos.m_bucket->empty()) {
784 ++pos;
785 }
786 
787 return pos;
788 }
789 
790 iterator erase(const_iterator pos) { return erase(mutable_iterator(pos)); }
791 
792 iterator erase(const_iterator first, const_iterator last) {
793 if (first == last) {
794 return mutable_iterator(first);
795 }
796 
797 auto first_mutable = mutable_iterator(first);
798 auto last_mutable = mutable_iterator(last);
799 for (auto it = first_mutable.m_bucket; it != last_mutable.m_bucket; ++it) {
800 if (!it->empty()) {
801 it->clear();
802 m_nb_elements--;
803 }
804 }
805 
806 if (last_mutable == end()) {
807 m_try_shrink_on_next_insert = true;
808 return end();
809 }
810 
811 /*
812 * Backward shift on the values which come after the deleted values.
813 * We try to move the values closer to their ideal bucket.
814 */
815 std::size_t icloser_bucket =
816 static_cast<std::size_t>(first_mutable.m_bucket - m_buckets);
817 std::size_t ito_move_closer_value =
818 static_cast<std::size_t>(last_mutable.m_bucket - m_buckets);
819 tsl_rh_assert(ito_move_closer_value > icloser_bucket);
820 
821 const std::size_t ireturn_bucket =
822 ito_move_closer_value -
823 std::min(
824 ito_move_closer_value - icloser_bucket,
825 std::size_t(
826 m_buckets[ito_move_closer_value].dist_from_ideal_bucket()));
827 
828 while (ito_move_closer_value < m_bucket_count &&
829 m_buckets[ito_move_closer_value].dist_from_ideal_bucket() > 0) {
830 icloser_bucket =
831 ito_move_closer_value -
832 std::min(
833 ito_move_closer_value - icloser_bucket,
834 std::size_t(
835 m_buckets[ito_move_closer_value].dist_from_ideal_bucket()));
836 
837 tsl_rh_assert(m_buckets[icloser_bucket].empty());
838 const distance_type new_distance = distance_type(
839 m_buckets[ito_move_closer_value].dist_from_ideal_bucket() -
840 (ito_move_closer_value - icloser_bucket));
841 m_buckets[icloser_bucket].set_value_of_empty_bucket(
842 new_distance, m_buckets[ito_move_closer_value].truncated_hash(),
843 std::move(m_buckets[ito_move_closer_value].value()));
844 m_buckets[ito_move_closer_value].clear();
845 
846 ++icloser_bucket;
847 ++ito_move_closer_value;
848 }
849 
850 m_try_shrink_on_next_insert = true;
851 
852 return iterator(m_buckets + ireturn_bucket);
853 }
854 
855 template <class K>
856 size_type erase(const K& key) {
857 return erase(key, hash_key(key));
858 }
859 
860 template <class K>
861 size_type erase(const K& key, std::size_t hash) {
862 auto it = find(key, hash);
863 if (it != end()) {
864 erase_from_bucket(it);
865 return 1;
866 } else {
867 return 0;
868 }
869 }
870 
871 void swap(robin_hash& other) {
872 using std::swap;
873 
874 swap(static_cast<Hash&>(*this), static_cast<Hash&>(other));
875 swap(static_cast<KeyEqual&>(*this), static_cast<KeyEqual&>(other));
876 swap(static_cast<GrowthPolicy&>(*this), static_cast<GrowthPolicy&>(other));
877 swap(m_buckets_data, other.m_buckets_data);
878 swap(m_buckets, other.m_buckets);
879 swap(m_bucket_count, other.m_bucket_count);
880 swap(m_nb_elements, other.m_nb_elements);
881 swap(m_load_threshold, other.m_load_threshold);
882 swap(m_min_load_factor, other.m_min_load_factor);
883 swap(m_max_load_factor, other.m_max_load_factor);
884 swap(m_grow_on_next_insert, other.m_grow_on_next_insert);
885 swap(m_try_shrink_on_next_insert, other.m_try_shrink_on_next_insert);
886 }
887 
888 /*
889 * Lookup
890 */
891 template <class K, class U = ValueSelect,
892 typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
893 typename U::value_type& at(const K& key) {
894 return at(key, hash_key(key));
895 }
896 
897 template <class K, class U = ValueSelect,
898 typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
899 typename U::value_type& at(const K& key, std::size_t hash) {
900 return const_cast<typename U::value_type&>(
901 static_cast<const robin_hash*>(this)->at(key, hash));
902 }
903 
904 template <class K, class U = ValueSelect,
905 typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
906 const typename U::value_type& at(const K& key) const {
907 return at(key, hash_key(key));
908 }
909 
910 template <class K, class U = ValueSelect,
911 typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
912 const typename U::value_type& at(const K& key, std::size_t hash) const {
913 auto it = find(key, hash);
914 if (it != cend()) {
915 return it.value();
916 } else {
917 TSL_RH_THROW_OR_TERMINATE(std::out_of_range, "Couldn't find key.");
918 }
919 }
920 
921 template <class K, class U = ValueSelect,
922 typename std::enable_if<has_mapped_type<U>::value>::type* = nullptr>
923 typename U::value_type& operator[](K&& key) {
924 return try_emplace(std::forward<K>(key)).first.value();
925 }
926 
927 template <class K>
928 size_type count(const K& key) const {
929 return count(key, hash_key(key));
930 }
931 
932 template <class K>
933 size_type count(const K& key, std::size_t hash) const {
934 if (find(key, hash) != cend()) {
935 return 1;
936 } else {
937 return 0;
938 }
939 }
940 
941 template <class K>
942 iterator find(const K& key) {
943 return find_impl(key, hash_key(key));
944 }
945 
946 template <class K>
947 iterator find(const K& key, std::size_t hash) {
948 return find_impl(key, hash);
949 }
950 
951 template <class K>
952 const_iterator find(const K& key) const {
953 return find_impl(key, hash_key(key));
954 }
955 
956 template <class K>
957 const_iterator find(const K& key, std::size_t hash) const {
958 return find_impl(key, hash);
959 }
960 
961 template <class K>
962 bool contains(const K& key) const {
963 return contains(key, hash_key(key));
964 }
965 
966 template <class K>
967 bool contains(const K& key, std::size_t hash) const {
968 return count(key, hash) != 0;
969 }
970 
971 template <class K>
972 std::pair<iterator, iterator> equal_range(const K& key) {
973 return equal_range(key, hash_key(key));
974 }
975 
976 template <class K>
977 std::pair<iterator, iterator> equal_range(const K& key, std::size_t hash) {
978 iterator it = find(key, hash);
979 return std::make_pair(it, (it == end()) ? it : std::next(it));
980 }
981 
982 template <class K>
983 std::pair<const_iterator, const_iterator> equal_range(const K& key) const {
984 return equal_range(key, hash_key(key));
985 }
986 
987 template <class K>
988 std::pair<const_iterator, const_iterator> equal_range(
989 const K& key, std::size_t hash) const {
990 const_iterator it = find(key, hash);
991 return std::make_pair(it, (it == cend()) ? it : std::next(it));
992 }
993 
994 /*
995 * Bucket interface
996 */
997 size_type bucket_count() const { return m_bucket_count; }
998 
999 size_type max_bucket_count() const {
1000 return std::min(GrowthPolicy::max_bucket_count(),
1001 m_buckets_data.max_size());
1002 }
1003 
1004 /*
1005 * Hash policy
1006 */
1007 float load_factor() const {
1008 if (bucket_count() == 0) {
1009 return 0;
1010 }
1011 
1012 return float(m_nb_elements) / float(bucket_count());
1013 }
1014 
1015 float min_load_factor() const { return m_min_load_factor; }
1016 
1017 float max_load_factor() const { return m_max_load_factor; }
1018 
1019 void min_load_factor(float ml) {
1020 m_min_load_factor = std::clamp(ml, float(MINIMUM_MIN_LOAD_FACTOR),
1021 float(MAXIMUM_MIN_LOAD_FACTOR));
1022 }
1023 
1024 void max_load_factor(float ml) {
1025 m_max_load_factor = std::clamp(ml, float(MINIMUM_MAX_LOAD_FACTOR),
1026 float(MAXIMUM_MAX_LOAD_FACTOR));
1027 m_load_threshold = size_type(float(bucket_count()) * m_max_load_factor);
1028 tsl_rh_assert(bucket_count() == 0 || m_load_threshold < bucket_count());
1029 }
1030 
1031 void rehash(size_type count_) {
1032 count_ = std::max(count_,
1033 size_type(std::ceil(float(size()) / max_load_factor())));
1034 rehash_impl(count_);
1035 }
1036 
1037 void reserve(size_type count_) {
1038 rehash(size_type(std::ceil(float(count_) / max_load_factor())));
1039 }
1040 
1041 /*
1042 * Observers
1043 */
1044 hasher hash_function() const { return static_cast<const Hash&>(*this); }
1045 
1046 key_equal key_eq() const { return static_cast<const KeyEqual&>(*this); }
1047 
1048 /*
1049 * Other
1050 */
1051 iterator mutable_iterator(const_iterator pos) {
1052 return iterator(const_cast<bucket_entry*>(pos.m_bucket));
1053 }
1054 
1055 template <class Serializer>
1056 void serialize(Serializer& serializer) const {
1057 serialize_impl(serializer);
1058 }
1059 
1060 template <class Deserializer>
1061 void deserialize(Deserializer& deserializer, bool hash_compatible) {
1062 deserialize_impl(deserializer, hash_compatible);
1063 }
1064 
1065 private:
1066 template <class K>
1067 std::size_t hash_key(const K& key) const {
1068 return Hash::operator()(key);
1069 }
1070 
1071 template <class K1, class K2>
1072 bool compare_keys(const K1& key1, const K2& key2) const {
1073 return KeyEqual::operator()(key1, key2);
1074 }
1075 
1076 std::size_t bucket_for_hash(std::size_t hash) const {
1077 const std::size_t bucket = GrowthPolicy::bucket_for_hash(hash);
1078 tsl_rh_assert(bucket < m_bucket_count ||
1079 (bucket == 0 && m_bucket_count == 0));
1080 
1081 return bucket;
1082 }
1083 
1084 template <class U = GrowthPolicy,
1085 typename std::enable_if<is_power_of_two_policy<U>::value>::type* =
1086 nullptr>
1087 std::size_t next_bucket(std::size_t index) const noexcept {
1088 tsl_rh_assert(index < bucket_count());
1089 
1090 return (index + 1) & this->m_mask;
1091 }
1092 
1093 template <class U = GrowthPolicy,
1094 typename std::enable_if<!is_power_of_two_policy<U>::value>::type* =
1095 nullptr>
1096 std::size_t next_bucket(std::size_t index) const noexcept {
1097 tsl_rh_assert(index < bucket_count());
1098 
1099 index++;
1100 return (index != bucket_count()) ? index : 0;
1101 }
1102 
1103 template <class K>
1104 iterator find_impl(const K& key, std::size_t hash) {
1105 return mutable_iterator(
1106 static_cast<const robin_hash*>(this)->find(key, hash));
1107 }
1108 
1109 template <class K>
1110 const_iterator find_impl(const K& key, std::size_t hash) const {
1111 std::size_t ibucket = bucket_for_hash(hash);
1112 distance_type dist_from_ideal_bucket = 0;
1113 
1114 while (dist_from_ideal_bucket <=
1115 m_buckets[ibucket].dist_from_ideal_bucket()) {
1116 if (TSL_RH_LIKELY(
1117 (!USE_STORED_HASH_ON_LOOKUP ||
1118 m_buckets[ibucket].bucket_hash_equal(hash)) &&
1119 compare_keys(KeySelect()(m_buckets[ibucket].value()), key))) {
1120 return const_iterator(m_buckets + ibucket);
1121 }
1122 
1123 ibucket = next_bucket(ibucket);
1124 dist_from_ideal_bucket++;
1125 }
1126 
1127 return cend();
1128 }
1129 
1130 void erase_from_bucket(iterator pos) {
1131 pos.m_bucket->clear();
1132 m_nb_elements--;
1133 
1134 /**
1135 * Backward shift, swap the empty bucket, previous_ibucket, with the values
1136 * on its right, ibucket, until we cross another empty bucket or if the
1137 * other bucket has a distance_from_ideal_bucket == 0.
1138 *
1139 * We try to move the values closer to their ideal bucket.
1140 */
1141 std::size_t previous_ibucket =
1142 static_cast<std::size_t>(pos.m_bucket - m_buckets);
1143 std::size_t ibucket = next_bucket(previous_ibucket);
1144 
1145 while (m_buckets[ibucket].dist_from_ideal_bucket() > 0) {
1146 tsl_rh_assert(m_buckets[previous_ibucket].empty());
1147 
1148 const distance_type new_distance =
1149 distance_type(m_buckets[ibucket].dist_from_ideal_bucket() - 1);
1150 m_buckets[previous_ibucket].set_value_of_empty_bucket(
1151 new_distance, m_buckets[ibucket].truncated_hash(),
1152 std::move(m_buckets[ibucket].value()));
1153 m_buckets[ibucket].clear();
1154 
1155 previous_ibucket = ibucket;
1156 ibucket = next_bucket(ibucket);
1157 }
1158 m_try_shrink_on_next_insert = true;
1159 }
1160 
1161 template <class K, class... Args>
1162 std::pair<iterator, bool> insert_impl(const K& key,
1163 Args&&... value_type_args) {
1164 const std::size_t hash = hash_key(key);
1165 
1166 std::size_t ibucket = bucket_for_hash(hash);
1167 distance_type dist_from_ideal_bucket = 0;
1168 
1169 while (dist_from_ideal_bucket <=
1170 m_buckets[ibucket].dist_from_ideal_bucket()) {
1171 if ((!USE_STORED_HASH_ON_LOOKUP ||
1172 m_buckets[ibucket].bucket_hash_equal(hash)) &&
1173 compare_keys(KeySelect()(m_buckets[ibucket].value()), key)) {
1174 return std::make_pair(iterator(m_buckets + ibucket), false);
1175 }
1176 
1177 ibucket = next_bucket(ibucket);
1178 dist_from_ideal_bucket++;
1179 }
1180 
1181 while (rehash_on_extreme_load(dist_from_ideal_bucket)) {
1182 ibucket = bucket_for_hash(hash);
1183 dist_from_ideal_bucket = 0;
1184 
1185 while (dist_from_ideal_bucket <=
1186 m_buckets[ibucket].dist_from_ideal_bucket()) {
1187 ibucket = next_bucket(ibucket);
1188 dist_from_ideal_bucket++;
1189 }
1190 }
1191 
1192 if (m_buckets[ibucket].empty()) {
1193 m_buckets[ibucket].set_value_of_empty_bucket(
1194 dist_from_ideal_bucket, bucket_entry::truncate_hash(hash),
1195 std::forward<Args>(value_type_args)...);
1196 } else {
1197 insert_value(ibucket, dist_from_ideal_bucket,
1198 bucket_entry::truncate_hash(hash),
1199 std::forward<Args>(value_type_args)...);
1200 }
1201 
1202 m_nb_elements++;
1203 /*
1204 * The value will be inserted in ibucket in any case, either because it was
1205 * empty or by stealing the bucket (robin hood).
1206 */
1207 return std::make_pair(iterator(m_buckets + ibucket), true);
1208 }
1209 
1210 template <class... Args>
1211 void insert_value(std::size_t ibucket, distance_type dist_from_ideal_bucket,
1212 truncated_hash_type hash, Args&&... value_type_args) {
1213 value_type value(std::forward<Args>(value_type_args)...);
1214 insert_value_impl(ibucket, dist_from_ideal_bucket, hash, value);
1215 }
1216 
1217 void insert_value(std::size_t ibucket, distance_type dist_from_ideal_bucket,
1218 truncated_hash_type hash, value_type&& value) {
1219 insert_value_impl(ibucket, dist_from_ideal_bucket, hash, value);
1220 }
1221 
1222 /*
1223 * We don't use `value_type&& value` as last argument due to a bug in MSVC
1224 * when `value_type` is a pointer, The compiler is not able to see the
1225 * difference between `std::string*` and `std::string*&&` resulting in a
1226 * compilation error.
1227 *
1228 * The `value` will be in a moved state at the end of the function.
1229 */
1230 void insert_value_impl(std::size_t ibucket,
1231 distance_type dist_from_ideal_bucket,
1232 truncated_hash_type hash, value_type& value) {
1233 tsl_rh_assert(dist_from_ideal_bucket >
1234 m_buckets[ibucket].dist_from_ideal_bucket());
1235 m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket, hash,
1236 value);
1237 ibucket = next_bucket(ibucket);
1238 dist_from_ideal_bucket++;
1239 
1240 while (!m_buckets[ibucket].empty()) {
1241 if (dist_from_ideal_bucket >
1242 m_buckets[ibucket].dist_from_ideal_bucket()) {
1243 if (dist_from_ideal_bucket >
1244 bucket_entry::DIST_FROM_IDEAL_BUCKET_LIMIT) {
1245 /**
1246 * The number of probes is really high, rehash the map on the next
1247 * insert. Difficult to do now as rehash may throw an exception.
1248 */
1249 m_grow_on_next_insert = true;
1250 }
1251 
1252 m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket,
1253 hash, value);
1254 }
1255 
1256 ibucket = next_bucket(ibucket);
1257 dist_from_ideal_bucket++;
1258 }
1259 
1260 m_buckets[ibucket].set_value_of_empty_bucket(dist_from_ideal_bucket, hash,
1261 std::move(value));
1262 }
1263 
1264 void rehash_impl(size_type count_) {
1265 robin_hash new_table(count_, static_cast<Hash&>(*this),
1266 static_cast<KeyEqual&>(*this), get_allocator(),
1267 m_min_load_factor, m_max_load_factor);
1268 tsl_rh_assert(size() <= new_table.m_load_threshold);
1269 
1270 const bool use_stored_hash =
1271 USE_STORED_HASH_ON_REHASH(new_table.bucket_count());
1272 for (auto& bucket : m_buckets_data) {
1273 if (bucket.empty()) {
1274 continue;
1275 }
1276 
1277 const std::size_t hash =
1278 use_stored_hash ? bucket.truncated_hash()
1279 : new_table.hash_key(KeySelect()(bucket.value()));
1280 
1281 new_table.insert_value_on_rehash(new_table.bucket_for_hash(hash), 0,
1282 bucket_entry::truncate_hash(hash),
1283 std::move(bucket.value()));
1284 }
1285 
1286 new_table.m_nb_elements = m_nb_elements;
1287 new_table.swap(*this);
1288 }
1289 
1290 void clear_and_shrink() noexcept {
1291 GrowthPolicy::clear();
1292 m_buckets_data.clear();
1293 m_buckets = static_empty_bucket_ptr();
1294 m_bucket_count = 0;
1295 m_nb_elements = 0;
1296 m_load_threshold = 0;
1297 m_grow_on_next_insert = false;
1298 m_try_shrink_on_next_insert = false;
1299 }
1300 
1301 void insert_value_on_rehash(std::size_t ibucket,
1302 distance_type dist_from_ideal_bucket,
1303 truncated_hash_type hash, value_type&& value) {
1304 while (true) {
1305 if (dist_from_ideal_bucket >
1306 m_buckets[ibucket].dist_from_ideal_bucket()) {
1307 if (m_buckets[ibucket].empty()) {
1308 m_buckets[ibucket].set_value_of_empty_bucket(dist_from_ideal_bucket,
1309 hash, std::move(value));
1310 return;
1311 } else {
1312 m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket,
1313 hash, value);
1314 }
1315 }
1316 
1317 dist_from_ideal_bucket++;
1318 ibucket = next_bucket(ibucket);
1319 }
1320 }
1321 
1322 /**
1323 * Grow the table if m_grow_on_next_insert is true or we reached the
1324 * max_load_factor. Shrink the table if m_try_shrink_on_next_insert is true
1325 * (an erase occurred) and we're below the min_load_factor.
1326 *
1327 * Return true if the table has been rehashed.
1328 */
1329 bool rehash_on_extreme_load(distance_type curr_dist_from_ideal_bucket) {
1330 if (m_grow_on_next_insert ||
1331 curr_dist_from_ideal_bucket >
1332 bucket_entry::DIST_FROM_IDEAL_BUCKET_LIMIT ||
1333 size() >= m_load_threshold) {
1334 rehash_impl(GrowthPolicy::next_bucket_count());
1335 m_grow_on_next_insert = false;
1336 
1337 return true;
1338 }
1339 
1340 if (m_try_shrink_on_next_insert) {
1341 m_try_shrink_on_next_insert = false;
1342 if (m_min_load_factor != 0.0f && load_factor() < m_min_load_factor) {
1343 reserve(size() + 1);
1344 
1345 return true;
1346 }
1347 }
1348 
1349 return false;
1350 }
1351 
1352 template <class Serializer>
1353 void serialize_impl(Serializer& serializer) const {
1354 const slz_size_type version = SERIALIZATION_PROTOCOL_VERSION;
1355 serializer(version);
1356 
1357 // Indicate if the truncated hash of each bucket is stored. Use a
1358 // std::int16_t instead of a bool to avoid the need for the serializer to
1359 // support an extra 'bool' type.
1360 const std::int16_t hash_stored_for_bucket =
1361 static_cast<std::int16_t>(STORE_HASH);
1362 serializer(hash_stored_for_bucket);
1363 
1364 const slz_size_type nb_elements = m_nb_elements;
1365 serializer(nb_elements);
1366 
1367 const slz_size_type bucket_count = m_buckets_data.size();
1368 serializer(bucket_count);
1369 
1370 const float min_load_factor = m_min_load_factor;
1371 serializer(min_load_factor);
1372 
1373 const float max_load_factor = m_max_load_factor;
1374 serializer(max_load_factor);
1375 
1376 for (const bucket_entry& bucket : m_buckets_data) {
1377 if (bucket.empty()) {
1378 const std::int16_t empty_bucket =
1379 bucket_entry::EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET;
1380 serializer(empty_bucket);
1381 } else {
1382 const std::int16_t dist_from_ideal_bucket =
1383 bucket.dist_from_ideal_bucket();
1384 serializer(dist_from_ideal_bucket);
1385 if (STORE_HASH) {
1386 const std::uint32_t truncated_hash = bucket.truncated_hash();
1387 serializer(truncated_hash);
1388 }
1389 serializer(bucket.value());
1390 }
1391 }
1392 }
1393 
1394 template <class Deserializer>
1395 void deserialize_impl(Deserializer& deserializer, bool hash_compatible) {
1396 tsl_rh_assert(m_buckets_data.empty()); // Current hash table must be empty
1397 
1398 const slz_size_type version =
1399 deserialize_value<slz_size_type>(deserializer);
1400 // For now we only have one version of the serialization protocol.
1401 // If it doesn't match there is a problem with the file.
1402 if (version != SERIALIZATION_PROTOCOL_VERSION) {
1403 TSL_RH_THROW_OR_TERMINATE(std::runtime_error,
1404 "Can't deserialize the ordered_map/set. "
1405 "The protocol version header is invalid.");
1406 }
1407 
1408 const bool hash_stored_for_bucket =
1409 deserialize_value<std::int16_t>(deserializer) ? true : false;
1410 if (hash_compatible && STORE_HASH != hash_stored_for_bucket) {
1411 TSL_RH_THROW_OR_TERMINATE(
1412 std::runtime_error,
1413 "Can't deserialize a map with a different StoreHash "
1414 "than the one used during the serialization when "
1415 "hash compatibility is used");
1416 }
1417 
1418 const slz_size_type nb_elements =
1419 deserialize_value<slz_size_type>(deserializer);
1420 const slz_size_type bucket_count_ds =
1421 deserialize_value<slz_size_type>(deserializer);
1422 const float min_load_factor = deserialize_value<float>(deserializer);
1423 const float max_load_factor = deserialize_value<float>(deserializer);
1424 
1425 if (min_load_factor < MINIMUM_MIN_LOAD_FACTOR ||
1426 min_load_factor > MAXIMUM_MIN_LOAD_FACTOR) {
1427 TSL_RH_THROW_OR_TERMINATE(
1428 std::runtime_error,
1429 "Invalid min_load_factor. Check that the serializer "
1430 "and deserializer support floats correctly as they "
1431 "can be converted implicitly to ints.");
1432 }
1433 
1434 if (max_load_factor < MINIMUM_MAX_LOAD_FACTOR ||
1435 max_load_factor > MAXIMUM_MAX_LOAD_FACTOR) {
1436 TSL_RH_THROW_OR_TERMINATE(
1437 std::runtime_error,
1438 "Invalid max_load_factor. Check that the serializer "
1439 "and deserializer support floats correctly as they "
1440 "can be converted implicitly to ints.");
1441 }
1442 
1443 this->min_load_factor(min_load_factor);
1444 this->max_load_factor(max_load_factor);
1445 
1446 if (bucket_count_ds == 0) {
1447 tsl_rh_assert(nb_elements == 0);
1448 return;
1449 }
1450 
1451 if (!hash_compatible) {
1452 reserve(numeric_cast<size_type>(nb_elements,
1453 "Deserialized nb_elements is too big."));
1454 for (slz_size_type ibucket = 0; ibucket < bucket_count_ds; ibucket++) {
1455 const distance_type dist_from_ideal_bucket =
1456 deserialize_value<std::int16_t>(deserializer);
1457 if (dist_from_ideal_bucket !=
1458 bucket_entry::EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET) {
1459 if (hash_stored_for_bucket) {
1460 TSL_RH_UNUSED(deserialize_value<std::uint32_t>(deserializer));
1461 }
1462 
1463 insert(deserialize_value<value_type>(deserializer));
1464 }
1465 }
1466 
1467 tsl_rh_assert(nb_elements == size());
1468 } else {
1469 m_bucket_count = numeric_cast<size_type>(
1470 bucket_count_ds, "Deserialized bucket_count is too big.");
1471 // Recompute m_load_threshold, during max_load_factor() the bucket count
1472 // was still 0 which would trigger rehash on first insert
1473 m_load_threshold = size_type(float(bucket_count()) * m_max_load_factor);
1474 
1475 GrowthPolicy::operator=(GrowthPolicy(m_bucket_count));
1476 // GrowthPolicy should not modify the bucket count we got from
1477 // deserialization
1478 if (m_bucket_count != bucket_count_ds) {
1479 TSL_RH_THROW_OR_TERMINATE(std::runtime_error,
1480 "The GrowthPolicy is not the same even "
1481 "though hash_compatible is true.");
1482 }
1483 
1484 m_nb_elements = numeric_cast<size_type>(
1485 nb_elements, "Deserialized nb_elements is too big.");
1486 m_buckets_data.resize(m_bucket_count);
1487 m_buckets = m_buckets_data.data();
1488 
1489 for (bucket_entry& bucket : m_buckets_data) {
1490 const distance_type dist_from_ideal_bucket =
1491 deserialize_value<std::int16_t>(deserializer);
1492 if (dist_from_ideal_bucket !=
1493 bucket_entry::EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET) {
1494 truncated_hash_type truncated_hash = 0;
1495 if (hash_stored_for_bucket) {
1496 tsl_rh_assert(hash_stored_for_bucket);
1497 truncated_hash = deserialize_value<std::uint32_t>(deserializer);
1498 }
1499 
1500 bucket.set_value_of_empty_bucket(
1501 dist_from_ideal_bucket, truncated_hash,
1502 deserialize_value<value_type>(deserializer));
1503 }
1504 }
1505 
1506 if (!m_buckets_data.empty()) {
1507 m_buckets_data.back().set_as_last_bucket();
1508 }
1509 }
1510 }
1511 
1512 public:
1513 static const size_type DEFAULT_INIT_BUCKETS_SIZE = 0;
1514 
1515 static constexpr float DEFAULT_MAX_LOAD_FACTOR = 0.5f;
1516 static constexpr float MINIMUM_MAX_LOAD_FACTOR = 0.2f;
1517 static constexpr float MAXIMUM_MAX_LOAD_FACTOR = 0.95f;
1518 
1519 static constexpr float DEFAULT_MIN_LOAD_FACTOR = 0.0f;
1520 static constexpr float MINIMUM_MIN_LOAD_FACTOR = 0.0f;
1521 static constexpr float MAXIMUM_MIN_LOAD_FACTOR = 0.15f;
1522 
1523 static_assert(MINIMUM_MAX_LOAD_FACTOR < MAXIMUM_MAX_LOAD_FACTOR,
1524 "MINIMUM_MAX_LOAD_FACTOR should be < MAXIMUM_MAX_LOAD_FACTOR");
1525 static_assert(MINIMUM_MIN_LOAD_FACTOR < MAXIMUM_MIN_LOAD_FACTOR,
1526 "MINIMUM_MIN_LOAD_FACTOR should be < MAXIMUM_MIN_LOAD_FACTOR");
1527 static_assert(MAXIMUM_MIN_LOAD_FACTOR < MINIMUM_MAX_LOAD_FACTOR,
1528 "MAXIMUM_MIN_LOAD_FACTOR should be < MINIMUM_MAX_LOAD_FACTOR");
1529 
1530 private:
1531 /**
1532 * Protocol version currenlty used for serialization.
1533 */
1534 static const slz_size_type SERIALIZATION_PROTOCOL_VERSION = 1;
1535 
1536 /**
1537 * Return an always valid pointer to an static empty bucket_entry with
1538 * last_bucket() == true.
1539 */
1540 bucket_entry* static_empty_bucket_ptr() noexcept {
1541 static bucket_entry empty_bucket(true);
1542 tsl_rh_assert(empty_bucket.empty());
1543 return &empty_bucket;
1544 }
1545 
1546 private:
1547 buckets_container_type m_buckets_data;
1548 
1549 /**
1550 * Points to m_buckets_data.data() if !m_buckets_data.empty() otherwise points
1551 * to static_empty_bucket_ptr. This variable is useful to avoid the cost of
1552 * checking if m_buckets_data is empty when trying to find an element.
1553 *
1554 * TODO Remove m_buckets_data and only use a pointer instead of a
1555 * pointer+vector to save some space in the robin_hash object. Manage the
1556 * Allocator manually.
1557 */
1558 bucket_entry* m_buckets;
1559 
1560 /**
1561 * Used a lot in find, avoid the call to m_buckets_data.size() which is a bit
1562 * slower.
1563 */
1564 size_type m_bucket_count;
1565 
1566 size_type m_nb_elements;
1567 
1568 size_type m_load_threshold;
1569 
1570 float m_min_load_factor;
1571 float m_max_load_factor;
1572 
1573 bool m_grow_on_next_insert;
1574 
1575 /**
1576 * We can't shrink down the map on erase operations as the erase methods need
1577 * to return the next iterator. Shrinking the map would invalidate all the
1578 * iterators and we could not return the next iterator in a meaningful way, On
1579 * erase, we thus just indicate on erase that we should try to shrink the hash
1580 * table on the next insert if we go below the min_load_factor.
1581 */
1582 bool m_try_shrink_on_next_insert;
1583};
1584 
1585} // namespace detail_robin_hash
1586 
1587} // namespace tsl
1588 
1589#endif
1590