IOSS 2.0

robin_hash.h
Go to the documentation of this file.
1 /**
2 * MIT License
3 *
4 * Copyright (c) 2017 Tessil
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 all
14 * 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 "robin_growth_policy.h"
28 #include <algorithm>
29 #include <cassert>
30 #include <cmath>
31 #include <cstddef>
32 #include <cstdint>
33 #include <exception>
34 #include <iterator>
35 #include <limits>
36 #include <memory>
37 #include <stdexcept>
38 #include <tuple>
39 #include <type_traits>
40 #include <utility>
41 #include <vector>
42
43 namespace tsl {
44
45 namespace detail_robin_hash {
46
47 template <typename T> struct make_void
48 {
49 using type = void;
50 };
51
52 template <typename T, typename = void> struct has_is_transparent : std::false_type
53 {
54 };
55
56 template <typename T>
57 struct has_is_transparent<T, typename make_void<typename T::is_transparent>::type>
58 : std::true_type
59 {
60 };
61
62 template <typename U> struct is_power_of_two_policy : std::false_type
63 {
64 };
65
66 template <std::size_t GrowthFactor>
67 struct is_power_of_two_policy<tsl::rh::power_of_two_growth_policy<GrowthFactor>>
68 : std::true_type
69 {
70 };
71
72 // Only available in C++17, we need to be compatible with C++11
73 template <class T> const T &clamp(const T &v, const T &lo, const T &hi)
74 {
75 return std::min(hi, std::max(lo, v));
76 }
77
78 template <typename T, typename U>
79 static T numeric_cast(U value, const char *error_message = "numeric_cast() failed.")
80 {
81 T ret = static_cast<T>(value);
82 if (static_cast<U>(ret) != value) {
83 TSL_RH_THROW_OR_TERMINATE(std::runtime_error, error_message);
84 }
85
86 const bool is_same_signedness = (std::is_unsigned<T>::value && std::is_unsigned<U>::value) ||
87 (std::is_signed<T>::value && std::is_signed<U>::value);
88 if (!is_same_signedness && (ret < T{}) != (value < U{})) {
89 TSL_RH_THROW_OR_TERMINATE(std::runtime_error, error_message);
90 }
91
92 return ret;
93 }
94
95 using truncated_hash_type = std::uint_least32_t;
96
97 /**
98 * Helper class that stores a truncated hash if StoreHash is true and nothing otherwise.
99 */
100 template <bool StoreHash> class bucket_entry_hash
101 {
102 public:
103 bool bucket_hash_equal(std::size_t /*hash*/) const noexcept { return true; }
104
105 truncated_hash_type truncated_hash() const noexcept { return 0; }
106
107 protected:
108 void set_hash(truncated_hash_type /*hash*/) noexcept {}
109 };
110
111 template <> class bucket_entry_hash<true>
112 {
113 public:
114 bool bucket_hash_equal(std::size_t hash) const noexcept
115 {
116 return m_hash == truncated_hash_type(hash);
117 }
118
119 truncated_hash_type truncated_hash() const noexcept { return m_hash; }
120
121 protected:
122 void set_hash(truncated_hash_type hash) noexcept { m_hash = truncated_hash_type(hash); }
123
124 private:
125 truncated_hash_type m_hash;
126 };
127
128 /**
129 * Each bucket entry has:
130 * - A value of type `ValueType`.
131 * - An integer to store how far the value of the bucket, if any, is from its ideal bucket
132 * (ex: if the current bucket 5 has the value 'foo' and `hash('foo') % nb_buckets` == 3,
133 * `dist_from_ideal_bucket()` will return 2 as the current value of the bucket is two
134 * buckets away from its ideal bucket)
135 * If there is no value in the bucket (i.e. `empty()` is true) `dist_from_ideal_bucket()` will
136 * be < 0.
137 * - A marker which tells us if the bucket is the last bucket of the bucket array (useful for
138 * the iterator of the hash table).
139 * - If `StoreHash` is true, 32 bits of the hash of the value, if any, are also stored in the
140 * bucket. If the size of the hash is more than 32 bits, it is truncated. We don't store the
141 * full hash as storing the hash is a potential opportunity to use the unused space due to the
142 * alignement of the bucket_entry structure. We can thus potentially store the hash without any
143 * extra space (which would not be possible with 64 bits of the hash).
144 */
145 template <typename ValueType, bool StoreHash>
146 class bucket_entry : public bucket_entry_hash<StoreHash>
147 {
148 using bucket_hash = bucket_entry_hash<StoreHash>;
149
150 public:
151 using value_type = ValueType;
152 using distance_type = std::int_least16_t;
153
154 bucket_entry() noexcept
155 : bucket_hash(), m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
156 m_last_bucket(false)
157 {
158 tsl_rh_assert(empty());
159 }
160
161 explicit bucket_entry(bool lst_bucket) noexcept
162 : bucket_hash(), m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
163 m_last_bucket(lst_bucket)
164 {
165 tsl_rh_assert(empty());
166 }
167
168 bucket_entry(const bucket_entry &other) noexcept(
169 std::is_nothrow_copy_constructible<value_type>::value)
170 : bucket_hash(other), m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
171 m_last_bucket(other.m_last_bucket)
172 {
173 if (!other.empty()) {
174 ::new (static_cast<void *>(std::addressof(m_value))) value_type(other.value());
175 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
176 }
177 }
178
179 /**
180 * Never really used, but still necessary as we must call resize on an empty
181 * `std::vector<bucket_entry>`. and we need to support move-only types. See robin_hash
182 * constructor for details.
183 */
184 bucket_entry(bucket_entry &&other) noexcept(
185 std::is_nothrow_move_constructible<value_type>::value)
186 : bucket_hash(std::move(other)),
187 m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
188 m_last_bucket(other.m_last_bucket)
189 {
190 if (!other.empty()) {
191 ::new (static_cast<void *>(std::addressof(m_value))) value_type(std::move(other.value()));
192 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
193 }
194 }
195
196 bucket_entry &operator=(const bucket_entry &other) noexcept(
197 std::is_nothrow_copy_constructible<value_type>::value)
198 {
199 if (this != &other) {
200 clear();
201
202 bucket_hash::operator=(other);
203 if (!other.empty()) {
204 ::new (static_cast<void *>(std::addressof(m_value))) value_type(other.value());
205 }
206
207 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
208 m_last_bucket = other.m_last_bucket;
209 }
210
211 return *this;
212 }
213
214 bucket_entry &operator=(bucket_entry &&) = delete;
215
216 ~bucket_entry() noexcept { clear(); }
217
218 void clear() noexcept
219 {
220 if (!empty()) {
221 destroy_value();
222 m_dist_from_ideal_bucket = EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET;
223 }
224 }
225
226 bool empty() const noexcept
227 {
228 return m_dist_from_ideal_bucket == EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET;
229 }
230
231 value_type &value() noexcept
232 {
233 tsl_rh_assert(!empty());
234 return *reinterpret_cast<value_type *>(std::addressof(m_value));
235 }
236
237 const value_type &value() const noexcept
238 {
239 tsl_rh_assert(!empty());
240 return *reinterpret_cast<const value_type *>(std::addressof(m_value));
241 }
242
243 distance_type dist_from_ideal_bucket() const noexcept { return m_dist_from_ideal_bucket; }
244
245 bool last_bucket() const noexcept { return m_last_bucket; }
246
247 void set_as_last_bucket() noexcept { m_last_bucket = true; }
248
249 template <typename... Args>
250 void set_value_of_empty_bucket(distance_type dist_frm_ideal_bucket, truncated_hash_type hash,
251 Args &&... value_type_args)
252 {
253 tsl_rh_assert(dist_frm_ideal_bucket >= 0);
254 tsl_rh_assert(empty());
255
256 ::new (static_cast<void *>(std::addressof(m_value)))
257 value_type(std::forward<Args>(value_type_args)...);
258 this->set_hash(hash);
259 m_dist_from_ideal_bucket = dist_frm_ideal_bucket;
260
261 tsl_rh_assert(!empty());
262 }
263
264 void swap_with_value_in_bucket(distance_type & dist_frm_ideal_bucket,
265 truncated_hash_type &hash, value_type &my_value)
266 {
267 tsl_rh_assert(!empty());
268
269 using std::swap;
270 swap(my_value, this->value());
271 swap(dist_frm_ideal_bucket, m_dist_from_ideal_bucket);
272
273 // Avoid warning of unused variable if StoreHash is false
274 (void)hash;
275 if (StoreHash) {
276 const truncated_hash_type tmp_hash = this->truncated_hash();
277 this->set_hash(hash);
278 hash = tmp_hash;
279 }
280 }
281
282 static truncated_hash_type truncate_hash(std::size_t hash) noexcept
283 {
284 return truncated_hash_type(hash);
285 }
286
287 private:
288 void destroy_value() noexcept
289 {
290 tsl_rh_assert(!empty());
291 value().~value_type();
292 }
293
294 private:
295 using storage = typename std::aligned_storage<sizeof(value_type), alignof(value_type)>::type;
296
297 static const distance_type EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1;
298
299 distance_type m_dist_from_ideal_bucket;
300 bool m_last_bucket;
301 storage m_value;
302 };
303
304 /**
305 * Internal common class used by `robin_map` and `robin_set`.
306 *
307 * ValueType is what will be stored by `robin_hash` (usually `std::pair<Key, T>` for map and
308 * `Key` for set).
309 *
310 * `KeySelect` should be a `FunctionObject` which takes a `ValueType` in parameter and returns a
311 * reference to the key.
312 *
313 * `ValueSelect` should be a `FunctionObject` which takes a `ValueType` in parameter and returns
314 * a reference to the value. `ValueSelect` should be void if there is no value (in a set for
315 * example).
316 *
317 * The strong exception guarantee only holds if the expression
318 * `std::is_nothrow_swappable<ValueType>\:\:value &&
319 * std::is_nothrow_move_constructible<ValueType>\:\:value` is true.
320 *
321 * Behaviour is undefined if the destructor of `ValueType` throws.
322 */
323 template <class ValueType, class KeySelect, class ValueSelect, class Hash, class KeyEqual,
324 class Allocator, bool StoreHash, class GrowthPolicy>
325 class robin_hash : private Hash, private KeyEqual, private GrowthPolicy
326 {
327 private:
328 template <typename U>
329 using has_mapped_type = typename std::integral_constant<bool, !std::is_same<U, void>::value>;
330
331 static_assert(noexcept(std::declval<GrowthPolicy>().bucket_for_hash(std::size_t(0))),
332 "GrowthPolicy::bucket_for_hash must be noexcept.");
333 static_assert(noexcept(std::declval<GrowthPolicy>().clear()),
334 "GrowthPolicy::clear must be noexcept.");
335
336 public:
337 template <bool IsConst> class robin_iterator;
338
339 using key_type = typename KeySelect::key_type;
340 using value_type = ValueType;
341 using size_type = std::size_t;
342 using difference_type = std::ptrdiff_t;
343 using hasher = Hash;
344 using key_equal = KeyEqual;
345 using allocator_type = Allocator;
346 using reference = value_type &;
347 using const_reference = const value_type &;
348 using pointer = value_type *;
349 using const_pointer = const value_type *;
350 using iterator = robin_iterator<false>;
351 using const_iterator = robin_iterator<true>;
352
353 private:
354 /**
355 * Either store the hash because we are asked by the `StoreHash` template parameter
356 * or store the hash because it doesn't cost us anything in size and can be used to speed up
357 * rehash.
358 */
359 static constexpr bool STORE_HASH =
360 StoreHash || ((sizeof(tsl::detail_robin_hash::bucket_entry<value_type, true>) ==
361 sizeof(tsl::detail_robin_hash::bucket_entry<value_type, false>)) &&
362 (sizeof(std::size_t) == sizeof(truncated_hash_type) ||
363 is_power_of_two_policy<GrowthPolicy>::value) &&
364 // Don't store the hash for primitive types with default hash.
365 (!std::is_arithmetic<key_type>::value ||
366 !std::is_same<Hash, std::hash<key_type>>::value));
367
368 /**
369 * Only use the stored hash on lookup if we are explictly asked. We are not sure how slow
370 * the KeyEqual operation is. An extra comparison may slow things down with a fast KeyEqual.
371 */
372 static constexpr bool USE_STORED_HASH_ON_LOOKUP = StoreHash;
373
374 /**
375 * We can only use the hash on rehash if the size of the hash type is the same as the stored
376 * one or if we use a power of two modulo. In the case of the power of two modulo, we just
377 * mask the least significant bytes, we just have to check that the truncated_hash_type didn't
378 * truncated more bytes.
379 */
380 static bool USE_STORED_HASH_ON_REHASH(size_type my_bucket_count)
381 {
382 (void)my_bucket_count;
383 if (STORE_HASH && sizeof(std::size_t) == sizeof(truncated_hash_type)) {
384 return true;
385 }
386 else if (STORE_HASH && is_power_of_two_policy<GrowthPolicy>::value) {
387 tsl_rh_assert(my_bucket_count > 0);
388 return (my_bucket_count - 1) <= std::numeric_limits<truncated_hash_type>::max();
389 }
390 else {
391 return false;
392 }
393 }
394
395 using bucket_entry = tsl::detail_robin_hash::bucket_entry<value_type, STORE_HASH>;
396 using distance_type = typename bucket_entry::distance_type;
397
398 using buckets_allocator =
399 typename std::allocator_traits<allocator_type>::template rebind_alloc<bucket_entry>;
400 using buckets_container_type = std::vector<bucket_entry, buckets_allocator>;
401
402 public:
403 /**
404 * The 'operator*()' and 'operator->()' methods return a const reference and const pointer
405 * respectively to the stored value type.
406 *
407 * In case of a map, to get a mutable reference to the value associated to a key (the
408 * '.second' in the stored pair), you have to call 'value()'.
409 *
410 * The main reason for this is that if we returned a `std::pair<Key, T>&` instead
411 * of a `const std::pair<Key, T>&`, the user may modify the key which will put the map in a
412 * undefined state.
413 */
414 template <bool IsConst> class robin_iterator
415 {
416 friend class robin_hash;
417
418 private:
419 using bucket_entry_ptr =
420 typename std::conditional<IsConst, const bucket_entry *, bucket_entry *>::type;
421
422 explicit robin_iterator(bucket_entry_ptr bucket) noexcept : m_bucket(bucket) {}
423
424 public:
425 using iterator_category = std::forward_iterator_tag;
426 using value_type = const typename robin_hash::value_type;
427 using difference_type = std::ptrdiff_t;
428 using reference = value_type &;
429 using pointer = value_type *;
430
431 robin_iterator() noexcept {}
432
433 // Copy constructor from iterator to const_iterator.
434 template <bool TIsConst = IsConst, typename std::enable_if<TIsConst>::type * = nullptr>
435 robin_iterator(const robin_iterator<!TIsConst> &other) noexcept : m_bucket(other.m_bucket)
436 {
437 }
438
439 robin_iterator(const robin_iterator &other) = default;
440 robin_iterator(robin_iterator &&other) = default;
441 robin_iterator &operator=(const robin_iterator &other) = default;
442 robin_iterator &operator=(robin_iterator &&other) = default;
443
444 const typename robin_hash::key_type &key() const { return KeySelect()(m_bucket->value()); }
445
446 template <class U = ValueSelect,
447 typename std::enable_if<has_mapped_type<U>::value && IsConst>::type * = nullptr>
448 const typename U::value_type &value() const
449 {
450 return U()(m_bucket->value());
451 }
452
453 template <class U = ValueSelect,
454 typename std::enable_if<has_mapped_type<U>::value && !IsConst>::type * = nullptr>
455 typename U::value_type &value()
456 {
457 return U()(m_bucket->value());
458 }
459
460 reference operator*() const { return m_bucket->value(); }
461
462 pointer operator->() const { return std::addressof(m_bucket->value()); }
463
464 robin_iterator &operator++()
465 {
466 while (true) {
467 if (m_bucket->last_bucket()) {
468 ++m_bucket;
469 return *this;
470 }
471
472 ++m_bucket;
473 if (!m_bucket->empty()) {
474 return *this;
475 }
476 }
477 }
478
479 robin_iterator operator++(int)
480 {
481 robin_iterator tmp(*this);
482 ++*this;
483
484 return tmp;
485 }
486
487 friend bool operator==(const robin_iterator &lhs, const robin_iterator &rhs)
488 {
489 return lhs.m_bucket == rhs.m_bucket;
490 }
491
492 friend bool operator!=(const robin_iterator &lhs, const robin_iterator &rhs)
493 {
494 return !(lhs == rhs);
495 }
496
497 private:
498 bucket_entry_ptr m_bucket;
499 };
500
501 public:
502 #if defined(__cplusplus) && __cplusplus >= 201402L
503 robin_hash(size_type my_bucket_count, const Hash &hash, const KeyEqual &equal,
504 const Allocator &alloc, float min_load_factor = DEFAULT_MIN_LOAD_FACTOR,
505 float max_load_factor = DEFAULT_MAX_LOAD_FACTOR)
506 : Hash(hash), KeyEqual(equal), GrowthPolicy(my_bucket_count),
507 m_buckets_data(
508 [&]() {
509 if (my_bucket_count > max_bucket_count()) {
510 TSL_RH_THROW_OR_TERMINATE(std::length_error,
511 "The map exceeds its maximum bucket count.");
512 }
513
514 return my_bucket_count;
515 }(),
516 alloc),
517 m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr() : m_buckets_data.data()),
518 m_bucket_count(my_bucket_count), m_nb_elements(0), m_grow_on_next_insert(false),
519 m_try_skrink_on_next_insert(false)
520 {
521 if (m_bucket_count > 0) {
522 tsl_rh_assert(!m_buckets_data.empty());
523 m_buckets_data.back().set_as_last_bucket();
524 }
525
526 this->min_load_factor(min_load_factor);
527 this->max_load_factor(max_load_factor);
528 }
529 #else
530 /**
531 * C++11 doesn't support the creation of a std::vector with a custom allocator and 'count'
532 * default-inserted elements. The needed contructor `explicit vector(size_type count, const
533 * Allocator& alloc = Allocator());` is only available in C++14 and later. We thus must resize
534 * after using the `vector(const Allocator& alloc)` constructor.
535 *
536 * We can't use `vector(size_type count, const T& value, const Allocator& alloc)` as it
537 * requires the value T to be copyable.
538 */
539 robin_hash(size_type my_bucket_count, const Hash &my_hash, const KeyEqual &equal,
540 const Allocator &alloc, float my_min_load_factor = DEFAULT_MIN_LOAD_FACTOR,
541 float my_max_load_factor = DEFAULT_MAX_LOAD_FACTOR)
542 : Hash(my_hash), KeyEqual(equal), GrowthPolicy(my_bucket_count), m_buckets_data(alloc),
543 m_buckets(static_empty_bucket_ptr()), m_bucket_count(my_bucket_count), m_nb_elements(0),
544 m_grow_on_next_insert(false), m_try_skrink_on_next_insert(false)
545 {
546 if (my_bucket_count > max_bucket_count()) {
547 TSL_RH_THROW_OR_TERMINATE(std::length_error,
548 "The map exceeds its maxmimum bucket count.");
549 }
550
551 if (m_bucket_count > 0) {
552 m_buckets_data.resize(m_bucket_count);
553 m_buckets = m_buckets_data.data();
554
555 tsl_rh_assert(!m_buckets_data.empty());
556 m_buckets_data.back().set_as_last_bucket();
557 }
558
559 this->min_load_factor(my_min_load_factor);
560 this->max_load_factor(my_max_load_factor);
561 }
562 #endif
563
564 robin_hash(const robin_hash &other)
565 : Hash(other), KeyEqual(other), GrowthPolicy(other), m_buckets_data(other.m_buckets_data),
566 m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr() : m_buckets_data.data()),
567 m_bucket_count(other.m_bucket_count), m_nb_elements(other.m_nb_elements),
568 m_load_threshold(other.m_load_threshold), m_max_load_factor(other.m_max_load_factor),
569 m_grow_on_next_insert(other.m_grow_on_next_insert),
570 m_min_load_factor(other.m_min_load_factor),
571 m_try_skrink_on_next_insert(other.m_try_skrink_on_next_insert)
572 {
573 }
574
575 robin_hash(robin_hash &&other) noexcept(
576 std::is_nothrow_move_constructible<Hash>::value &&std::is_nothrow_move_constructible<
577 KeyEqual>::value &&std::is_nothrow_move_constructible<GrowthPolicy>::value
578 && std::is_nothrow_move_constructible<buckets_container_type>::value)
579 : Hash(std::move(static_cast<Hash &>(other))),
580 KeyEqual(std::move(static_cast<KeyEqual &>(other))),
581 GrowthPolicy(std::move(static_cast<GrowthPolicy &>(other))),
582 m_buckets_data(std::move(other.m_buckets_data)),
583 m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr() : m_buckets_data.data()),
584 m_bucket_count(other.m_bucket_count), m_nb_elements(other.m_nb_elements),
585 m_load_threshold(other.m_load_threshold), m_max_load_factor(other.m_max_load_factor),
586 m_grow_on_next_insert(other.m_grow_on_next_insert),
587 m_min_load_factor(other.m_min_load_factor),
588 m_try_skrink_on_next_insert(other.m_try_skrink_on_next_insert)
589 {
590 other.GrowthPolicy::clear();
591 other.m_buckets_data.clear();
592 other.m_buckets = static_empty_bucket_ptr();
593 other.m_bucket_count = 0;
594 other.m_nb_elements = 0;
595 other.m_load_threshold = 0;
596 other.m_grow_on_next_insert = false;
597 other.m_try_skrink_on_next_insert = false;
598 }
599
600 robin_hash &operator=(const robin_hash &other)
601 {
602 if (&other != this) {
603 Hash:: operator=(other);
604 KeyEqual:: operator=(other);
605 GrowthPolicy::operator=(other);
606
607 m_buckets_data = other.m_buckets_data;
608 m_buckets = m_buckets_data.empty() ? static_empty_bucket_ptr() : m_buckets_data.data();
609 m_bucket_count = other.m_bucket_count;
610 m_nb_elements = other.m_nb_elements;
611
612 m_load_threshold = other.m_load_threshold;
613 m_max_load_factor = other.m_max_load_factor;
614 m_grow_on_next_insert = other.m_grow_on_next_insert;
615
616 m_min_load_factor = other.m_min_load_factor;
617 m_try_skrink_on_next_insert = other.m_try_skrink_on_next_insert;
618 }
619
620 return *this;
621 }
622
623 robin_hash &operator=(robin_hash &&other)
624 {
625 other.swap(*this);
626 other.clear();
627
628 return *this;
629 }
630
631 allocator_type get_allocator() const { return m_buckets_data.get_allocator(); }
632
633 /*
634 * Iterators
635 */
636 iterator begin() noexcept
637 {
638 std::size_t i = 0;
639 while (i < m_bucket_count && m_buckets[i].empty()) {
640 i++;
641 }
642
643 return iterator(m_buckets + i);
644 }
645
646 const_iterator begin() const noexcept { return cbegin(); }
647
648 const_iterator cbegin() const noexcept
649 {
650 std::size_t i = 0;
651 while (i < m_bucket_count && m_buckets[i].empty()) {
652 i++;
653 }
654
655 return const_iterator(m_buckets + i);
656 }
657
658 iterator end() noexcept { return iterator(m_buckets + m_bucket_count); }
659
660 const_iterator end() const noexcept { return cend(); }
661
662 const_iterator cend() const noexcept { return const_iterator(m_buckets + m_bucket_count); }
663
664 /*
665 * Capacity
666 */
667 bool empty() const noexcept { return m_nb_elements == 0; }
668
669 size_type size() const noexcept { return m_nb_elements; }
670
671 size_type max_size() const noexcept { return m_buckets_data.max_size(); }
672
673 /*
674 * Modifiers
675 */
676 void clear() noexcept
677 {
678 for (auto &bucket : m_buckets_data) {
679 bucket.clear();
680 }
681
682 m_nb_elements = 0;
683 m_grow_on_next_insert = false;
684 }
685
686 template <typename P> std::pair<iterator, bool> insert(P &&value)
687 {
688 return insert_impl(KeySelect()(value), std::forward<P>(value));
689 }
690
691 template <typename P> iterator insert_hint(const_iterator hint, P &&value)
692 {
693 if (hint != cend() && compare_keys(KeySelect()(*hint), KeySelect()(value))) {
694 return mutable_iterator(hint);
695 }
696
697 return insert(std::forward<P>(value)).first;
698 }
699
700 template <class InputIt> void insert(InputIt first, InputIt last)
701 {
702 if (std::is_base_of<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 && nb_free_buckets < size_type(nb_elements_insert)) {
709 reserve(size() + size_type(nb_elements_insert));
710 }
711 }
712
713 for (; first != last; ++first) {
714 insert(*first);
715 }
716 }
717
718 template <class K, class M> std::pair<iterator, bool> insert_or_assign(K &&key, M &&obj)
719 {
720 auto it = try_emplace(std::forward<K>(key), std::forward<M>(obj));
721 if (!it.second) {
722 it.first.value() = std::forward<M>(obj);
723 }
724
725 return it;
726 }
727
728 template <class K, class M> iterator insert_or_assign(const_iterator hint, K &&key, M &&obj)
729 {
730 if (hint != cend() && compare_keys(KeySelect()(*hint), key)) {
731 auto it = mutable_iterator(hint);
732 it.value() = std::forward<M>(obj);
733
734 return it;
735 }
736
737 return insert_or_assign(std::forward<K>(key), std::forward<M>(obj)).first;
738 }
739
740 template <class... Args> std::pair<iterator, bool> emplace(Args &&... args)
741 {
742 return insert(value_type(std::forward<Args>(args)...));
743 }
744
745 template <class... Args> iterator emplace_hint(const_iterator hint, Args &&... args)
746 {
747 return insert_hint(hint, value_type(std::forward<Args>(args)...));
748 }
749
750 template <class K, class... Args>
751 std::pair<iterator, bool> try_emplace(K &&key, Args &&... args)
752 {
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 {
761 if (hint != cend() && compare_keys(KeySelect()(*hint), key)) {
762 return mutable_iterator(hint);
763 }
764
765 return try_emplace(std::forward<K>(key), std::forward<Args>(args)...).first;
766 }
767
768 /**
769 * Here to avoid `template<class K> size_type erase(const K& key)` being used when
770 * we use an `iterator` instead of a `const_iterator`.
771 */
772 iterator erase(iterator pos)
773 {
774 erase_from_bucket(pos);
775
776 /**
777 * Erase bucket used a backward shift after clearing the bucket.
778 * Check if there is a new value in the bucket, if not get the next non-empty.
779 */
780 if (pos.m_bucket->empty()) {
781 ++pos;
782 }
783
784 m_try_skrink_on_next_insert = true;
785
786 return pos;
787 }
788
789 iterator erase(const_iterator pos) { return erase(mutable_iterator(pos)); }
790
791 iterator erase(const_iterator first, const_iterator last)
792 {
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 return end();
808 }
809
810 /*
811 * Backward shift on the values which come after the deleted values.
812 * We try to move the values closer to their ideal bucket.
813 */
814 std::size_t icloser_bucket = static_cast<std::size_t>(first_mutable.m_bucket - m_buckets);
815 std::size_t ito_move_closer_value =
816 static_cast<std::size_t>(last_mutable.m_bucket - m_buckets);
817 tsl_rh_assert(ito_move_closer_value > icloser_bucket);
818
819 const std::size_t ireturn_bucket =
820 ito_move_closer_value -
821 std::min(ito_move_closer_value - icloser_bucket,
822 std::size_t(m_buckets[ito_move_closer_value].dist_from_ideal_bucket()));
823
824 while (ito_move_closer_value < m_bucket_count &&
825 m_buckets[ito_move_closer_value].dist_from_ideal_bucket() > 0) {
826 icloser_bucket =
827 ito_move_closer_value -
828 std::min(ito_move_closer_value - icloser_bucket,
829 std::size_t(m_buckets[ito_move_closer_value].dist_from_ideal_bucket()));
830
831 tsl_rh_assert(m_buckets[icloser_bucket].empty());
832 const distance_type new_distance =
833 distance_type(m_buckets[ito_move_closer_value].dist_from_ideal_bucket() -
834 (ito_move_closer_value - icloser_bucket));
835 m_buckets[icloser_bucket].set_value_of_empty_bucket(
836 new_distance, m_buckets[ito_move_closer_value].truncated_hash(),
837 std::move(m_buckets[ito_move_closer_value].value()));
838 m_buckets[ito_move_closer_value].clear();
839
840 ++icloser_bucket;
841 ++ito_move_closer_value;
842 }
843
844 m_try_skrink_on_next_insert = true;
845
846 return iterator(m_buckets + ireturn_bucket);
847 }
848
849 template <class K> size_type erase(const K &key) { return erase(key, hash_key(key)); }
850
851 template <class K> size_type erase(const K &key, std::size_t my_hash)
852 {
853 auto it = find(key, my_hash);
854 if (it != end()) {
855 erase_from_bucket(it);
856 m_try_skrink_on_next_insert = true;
857
858 return 1;
859 }
860 else {
861 return 0;
862 }
863 }
864
865 void swap(robin_hash &other)
866 {
867 using std::swap;
868
869 swap(static_cast<Hash &>(*this), static_cast<Hash &>(other));
870 swap(static_cast<KeyEqual &>(*this), static_cast<KeyEqual &>(other));
871 swap(static_cast<GrowthPolicy &>(*this), static_cast<GrowthPolicy &>(other));
872 swap(m_buckets_data, other.m_buckets_data);
873 swap(m_buckets, other.m_buckets);
874 swap(m_bucket_count, other.m_bucket_count);
875 swap(m_nb_elements, other.m_nb_elements);
876 swap(m_load_threshold, other.m_load_threshold);
877 swap(m_max_load_factor, other.m_max_load_factor);
878 swap(m_grow_on_next_insert, other.m_grow_on_next_insert);
879 swap(m_min_load_factor, other.m_min_load_factor);
880 swap(m_try_skrink_on_next_insert, other.m_try_skrink_on_next_insert);
881 }
882
883 /*
884 * Lookup
885 */
886 template <class K, class U = ValueSelect,
887 typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
888 typename U::value_type &at(const K &key)
889 {
890 return at(key, hash_key(key));
891 }
892
893 template <class K, class U = ValueSelect,
894 typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
895 typename U::value_type &at(const K &key, std::size_t my_hash)
896 {
897 return const_cast<typename U::value_type &>(
898 static_cast<const robin_hash *>(this)->at(key, my_hash));
899 }
900
901 template <class K, class U = ValueSelect,
902 typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
903 const typename U::value_type &at(const K &key) const
904 {
905 return at(key, hash_key(key));
906 }
907
908 template <class K, class U = ValueSelect,
909 typename std::enable_if<has_mapped_type<U>::value>::type * = nullptr>
910 const typename U::value_type &at(const K &key, std::size_t my_hash) const
911 {
912 auto it = find(key, my_hash);
913 if (it != cend()) {
914 return it.value();
915 }
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 {
925 return try_emplace(std::forward<K>(key)).first.value();
926 }
927
928 template <class K> size_type count(const K &key) const { return count(key, hash_key(key)); }
929
930 template <class K> size_type count(const K &key, std::size_t my_hash) const
931 {
932 if (find(key, my_hash) != cend()) {
933 return 1;
934 }
935 else {
936 return 0;
937 }
938 }
939
940 template <class K> iterator find(const K &key) { return find_impl(key, hash_key(key)); }
941
942 template <class K> iterator find(const K &key, std::size_t my_hash)
943 {
944 return find_impl(key, my_hash);
945 }
946
947 template <class K> const_iterator find(const K &key) const
948 {
949 return find_impl(key, hash_key(key));
950 }
951
952 template <class K> const_iterator find(const K &key, std::size_t my_hash) const
953 {
954 return find_impl(key, my_hash);
955 }
956
957 template <class K> std::pair<iterator, iterator> equal_range(const K &key)
958 {
959 return equal_range(key, hash_key(key));
960 }
961
962 template <class K>
963 std::pair<iterator, iterator> equal_range(const K &key, std::size_t my_hash)
964 {
965 iterator it = find(key, my_hash);
966 return std::make_pair(it, (it == end()) ? it : std::next(it));
967 }
968
969 template <class K> std::pair<const_iterator, const_iterator> equal_range(const K &key) const
970 {
971 return equal_range(key, hash_key(key));
972 }
973
974 template <class K>
975 std::pair<const_iterator, const_iterator> equal_range(const K &key, std::size_t my_hash) const
976 {
977 const_iterator it = find(key, my_hash);
978 return std::make_pair(it, (it == cend()) ? it : std::next(it));
979 }
980
981 /*
982 * Bucket interface
983 */
984 size_type bucket_count() const { return m_bucket_count; }
985
986 size_type max_bucket_count() const
987 {
988 return std::min(GrowthPolicy::max_bucket_count(), m_buckets_data.max_size());
989 }
990
991 /*
992 * Hash policy
993 */
994 float load_factor() const
995 {
996 if (bucket_count() == 0) {
997 return 0;
998 }
999
1000 return float(m_nb_elements) / float(bucket_count());
1001 }
1002
1003 float min_load_factor() const { return m_min_load_factor; }
1004
1005 float max_load_factor() const { return m_max_load_factor; }
1006
1007 void min_load_factor(float ml)
1008 {
1009 m_min_load_factor =
1010 clamp(ml, float(MINIMUM_MIN_LOAD_FACTOR), float(MAXIMUM_MIN_LOAD_FACTOR));
1011 }
1012
1013 void max_load_factor(float ml)
1014 {
1015 m_max_load_factor =
1016 clamp(ml, float(MINIMUM_MAX_LOAD_FACTOR), float(MAXIMUM_MAX_LOAD_FACTOR));
1017 m_load_threshold = size_type(float(bucket_count()) * m_max_load_factor);
1018 }
1019
1020 void rehash(size_type new_count)
1021 {
1022 new_count = std::max(new_count, size_type(std::ceil(float(size()) / max_load_factor())));
1023 rehash_impl(new_count);
1024 }
1025
1026 void reserve(size_type new_count)
1027 {
1028 rehash(size_type(std::ceil(float(new_count) / max_load_factor())));
1029 }
1030
1031 /*
1032 * Observers
1033 */
1034 hasher hash_function() const { return static_cast<const Hash &>(*this); }
1035
1036 key_equal key_eq() const { return static_cast<const KeyEqual &>(*this); }
1037
1038 /*
1039 * Other
1040 */
1041 iterator mutable_iterator(const_iterator pos)
1042 {
1043 return iterator(const_cast<bucket_entry *>(pos.m_bucket));
1044 }
1045
1046 private:
1047 template <class K> std::size_t hash_key(const K &key) const { return Hash::operator()(key); }
1048
1049 template <class K1, class K2> bool compare_keys(const K1 &key1, const K2 &key2) const
1050 {
1051 return KeyEqual::operator()(key1, key2);
1052 }
1053
1054 std::size_t bucket_for_hash(std::size_t my_hash) const
1055 {
1056 const std::size_t bucket = GrowthPolicy::bucket_for_hash(my_hash);
1057 tsl_rh_assert(bucket < m_bucket_count || (bucket == 0 && m_bucket_count == 0));
1058
1059 return bucket;
1060 }
1061
1062 template <class U = GrowthPolicy,
1063 typename std::enable_if<is_power_of_two_policy<U>::value>::type * = nullptr>
1064 std::size_t next_bucket(std::size_t index) const noexcept
1065 {
1066 tsl_rh_assert(index < bucket_count());
1067
1068 return (index + 1) & this->m_mask;
1069 }
1070
1071 template <class U = GrowthPolicy,
1072 typename std::enable_if<!is_power_of_two_policy<U>::value>::type * = nullptr>
1073 std::size_t next_bucket(std::size_t index) const noexcept
1074 {
1075 tsl_rh_assert(index < bucket_count());
1076
1077 index++;
1078 return (index != bucket_count()) ? index : 0;
1079 }
1080
1081 template <class K> iterator find_impl(const K &key, std::size_t my_hash)
1082 {
1083 return mutable_iterator(static_cast<const robin_hash *>(this)->find(key, my_hash));
1084 }
1085
1086 template <class K> const_iterator find_impl(const K &key, std::size_t my_hash) const
1087 {
1088 std::size_t ibucket = bucket_for_hash(my_hash);
1089 distance_type dist_from_ideal_bucket = 0;
1090
1091 while (dist_from_ideal_bucket <= m_buckets[ibucket].dist_from_ideal_bucket()) {
1092 if (TSL_RH_LIKELY(
1093 (!USE_STORED_HASH_ON_LOOKUP || m_buckets[ibucket].bucket_hash_equal(my_hash)) &&
1094 compare_keys(KeySelect()(m_buckets[ibucket].value()), key))) {
1095 return const_iterator(m_buckets + ibucket);
1096 }
1097
1098 ibucket = next_bucket(ibucket);
1099 dist_from_ideal_bucket++;
1100 }
1101
1102 return cend();
1103 }
1104
1105 void erase_from_bucket(iterator pos)
1106 {
1107 pos.m_bucket->clear();
1108 --m_nb_elements;
1109
1110 /**
1111 * Backward shift, swap the empty bucket, previous_ibucket, with the values on its right,
1112 * ibucket, until we cross another empty bucket or if the other bucket has a
1113 * distance_from_ideal_bucket == 0.
1114 *
1115 * We try to move the values closer to their ideal bucket.
1116 */
1117 std::size_t previous_ibucket = static_cast<std::size_t>(pos.m_bucket - m_buckets);
1118 std::size_t ibucket = next_bucket(previous_ibucket);
1119
1120 while (m_buckets[ibucket].dist_from_ideal_bucket() > 0) {
1121 tsl_rh_assert(m_buckets[previous_ibucket].empty());
1122
1123 const distance_type new_distance =
1124 distance_type(m_buckets[ibucket].dist_from_ideal_bucket() - 1);
1125 m_buckets[previous_ibucket].set_value_of_empty_bucket(
1126 new_distance, m_buckets[ibucket].truncated_hash(),
1127 std::move(m_buckets[ibucket].value()));
1128 m_buckets[ibucket].clear();
1129
1130 previous_ibucket = ibucket;
1131 ibucket = next_bucket(ibucket);
1132 }
1133 }
1134
1135 template <class K, class... Args>
1136 std::pair<iterator, bool> insert_impl(const K &key, Args &&... value_type_args)
1137 {
1138 const std::size_t my_hash = hash_key(key);
1139
1140 std::size_t ibucket = bucket_for_hash(my_hash);
1141 distance_type dist_from_ideal_bucket = 0;
1142
1143 while (dist_from_ideal_bucket <= m_buckets[ibucket].dist_from_ideal_bucket()) {
1144 if ((!USE_STORED_HASH_ON_LOOKUP || m_buckets[ibucket].bucket_hash_equal(my_hash)) &&
1145 compare_keys(KeySelect()(m_buckets[ibucket].value()), key)) {
1146 return std::make_pair(iterator(m_buckets + ibucket), false);
1147 }
1148
1149 ibucket = next_bucket(ibucket);
1150 dist_from_ideal_bucket++;
1151 }
1152
1153 if (rehash_on_extreme_load()) {
1154 ibucket = bucket_for_hash(my_hash);
1155 dist_from_ideal_bucket = 0;
1156
1157 while (dist_from_ideal_bucket <= m_buckets[ibucket].dist_from_ideal_bucket()) {
1158 ibucket = next_bucket(ibucket);
1159 dist_from_ideal_bucket++;
1160 }
1161 }
1162
1163 if (m_buckets[ibucket].empty()) {
1164 m_buckets[ibucket].set_value_of_empty_bucket(dist_from_ideal_bucket,
1165 bucket_entry::truncate_hash(my_hash),
1166 std::forward<Args>(value_type_args)...);
1167 }
1168 else {
1169 insert_value(ibucket, dist_from_ideal_bucket, bucket_entry::truncate_hash(my_hash),
1170 std::forward<Args>(value_type_args)...);
1171 }
1172
1173 ++m_nb_elements;
1174 /*
1175 * The value will be inserted in ibucket in any case, either because it was
1176 * empty or by stealing the bucket (robin hood).
1177 */
1178 return std::make_pair(iterator(m_buckets + ibucket), true);
1179 }
1180
1181 template <class... Args>
1182 void insert_value(std::size_t ibucket, distance_type dist_from_ideal_bucket,
1183 truncated_hash_type my_hash, Args &&... value_type_args)
1184 {
1185 value_type value(std::forward<Args>(value_type_args)...);
1186 insert_value_impl(ibucket, dist_from_ideal_bucket, my_hash, value);
1187 }
1188
1189 void insert_value(std::size_t ibucket, distance_type dist_from_ideal_bucket,
1190 truncated_hash_type my_hash, value_type &&value)
1191 {
1192 insert_value_impl(ibucket, dist_from_ideal_bucket, my_hash, value);
1193 }
1194
1195 /*
1196 * We don't use `value_type&& value` as last argument due to a bug in MSVC when `value_type`
1197 * is a pointer, The compiler is not able to see the difference between `std::string*` and
1198 * `std::string*&&` resulting in compile error.
1199 *
1200 * The `value` will be in a moved state at the end of the function.
1201 */
1202 void insert_value_impl(std::size_t ibucket, distance_type dist_from_ideal_bucket,
1203 truncated_hash_type my_hash, value_type &value)
1204 {
1205 m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket, my_hash, value);
1206 ibucket = next_bucket(ibucket);
1207 dist_from_ideal_bucket++;
1208
1209 while (!m_buckets[ibucket].empty()) {
1210 if (dist_from_ideal_bucket > m_buckets[ibucket].dist_from_ideal_bucket()) {
1211 if (dist_from_ideal_bucket >= REHASH_ON_HIGH_NB_PROBES__NPROBES &&
1212 load_factor() >= REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR) {
1213 /**
1214 * The number of probes is really high, rehash the map on the next insert.
1215 * Difficult to do now as rehash may throw an exception.
1216 */
1217 m_grow_on_next_insert = true;
1218 }
1219
1220 m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket, my_hash, value);
1221 }
1222
1223 ibucket = next_bucket(ibucket);
1224 dist_from_ideal_bucket++;
1225 }
1226
1227 m_buckets[ibucket].set_value_of_empty_bucket(dist_from_ideal_bucket, my_hash,
1228 std::move(value));
1229 }
1230
1231 void rehash_impl(size_type new_count)
1232 {
1233 robin_hash new_table(new_count, static_cast<Hash &>(*this), static_cast<KeyEqual &>(*this),
1234 get_allocator(), m_min_load_factor, m_max_load_factor);
1235
1236 const bool use_stored_hash = USE_STORED_HASH_ON_REHASH(new_table.bucket_count());
1237 for (auto &bucket : m_buckets_data) {
1238 if (bucket.empty()) {
1239 continue;
1240 }
1241
1242 const std::size_t my_hash = use_stored_hash
1243 ? bucket.truncated_hash()
1244 : new_table.hash_key(KeySelect()(bucket.value()));
1245
1246 new_table.insert_value_on_rehash(new_table.bucket_for_hash(my_hash), 0,
1247 bucket_entry::truncate_hash(my_hash),
1248 std::move(bucket.value()));
1249 }
1250
1251 new_table.m_nb_elements = m_nb_elements;
1252 new_table.swap(*this);
1253 }
1254
1255 void insert_value_on_rehash(std::size_t ibucket, distance_type dist_from_ideal_bucket,
1256 truncated_hash_type my_hash, value_type &&value)
1257 {
1258 while (true) {
1259 if (dist_from_ideal_bucket > m_buckets[ibucket].dist_from_ideal_bucket()) {
1260 if (m_buckets[ibucket].empty()) {
1261 m_buckets[ibucket].set_value_of_empty_bucket(dist_from_ideal_bucket, my_hash,
1262 std::move(value));
1263 return;
1264 }
1265 else {
1266 m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket, my_hash, value);
1267 }
1268 }
1269
1270 ++dist_from_ideal_bucket;
1271 ibucket = next_bucket(ibucket);
1272 }
1273 }
1274
1275 /**
1276 * Grow the table if m_grow_on_next_insert is true or we reached the max_load_factor.
1277 * Shrink the table if m_try_skrink_on_next_insert is true (an erase occured) and
1278 * we're below the min_load_factor.
1279 *
1280 * Return true if the table has been rehashed.
1281 */
1282 bool rehash_on_extreme_load()
1283 {
1284 if (m_grow_on_next_insert || size() >= m_load_threshold) {
1285 rehash_impl(GrowthPolicy::next_bucket_count());
1286 m_grow_on_next_insert = false;
1287
1288 return true;
1289 }
1290
1291 if (m_try_skrink_on_next_insert) {
1292 m_try_skrink_on_next_insert = false;
1293 if (m_min_load_factor != 0.0f && load_factor() < m_min_load_factor) {
1294 reserve(size() + 1);
1295
1296 return true;
1297 }
1298 }
1299
1300 return false;
1301 }
1302
1303 public:
1304 static const size_type DEFAULT_INIT_BUCKETS_SIZE = 0;
1305
1306 static constexpr float DEFAULT_MAX_LOAD_FACTOR = 0.5f;
1307 static constexpr float MINIMUM_MAX_LOAD_FACTOR = 0.2f;
1308 static constexpr float MAXIMUM_MAX_LOAD_FACTOR = 0.95f;
1309
1310 static constexpr float DEFAULT_MIN_LOAD_FACTOR = 0.0f;
1311 static constexpr float MINIMUM_MIN_LOAD_FACTOR = 0.0f;
1312 static constexpr float MAXIMUM_MIN_LOAD_FACTOR = 0.15f;
1313
1314 static_assert(MINIMUM_MAX_LOAD_FACTOR < MAXIMUM_MAX_LOAD_FACTOR,
1315 "MINIMUM_MAX_LOAD_FACTOR should be < MAXIMUM_MAX_LOAD_FACTOR");
1316 static_assert(MINIMUM_MIN_LOAD_FACTOR < MAXIMUM_MIN_LOAD_FACTOR,
1317 "MINIMUM_MIN_LOAD_FACTOR should be < MAXIMUM_MIN_LOAD_FACTOR");
1318 static_assert(MAXIMUM_MIN_LOAD_FACTOR < MINIMUM_MAX_LOAD_FACTOR,
1319 "MAXIMUM_MIN_LOAD_FACTOR should be < MINIMUM_MAX_LOAD_FACTOR");
1320
1321 private:
1322 static const distance_type REHASH_ON_HIGH_NB_PROBES__NPROBES = 128;
1323 static constexpr float REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR = 0.15f;
1324
1325 /**
1326 * Return an always valid pointer to an static empty bucket_entry with last_bucket() == true.
1327 */
1328 bucket_entry *static_empty_bucket_ptr()
1329 {
1330 static bucket_entry empty_bucket(true);
1331 return &empty_bucket;
1332 }
1333
1334 private:
1335 buckets_container_type m_buckets_data;
1336
1337 /**
1338 * Points to m_buckets_data.data() if !m_buckets_data.empty() otherwise points to
1339 * static_empty_bucket_ptr. This variable is useful to avoid the cost of checking if
1340 * m_buckets_data is empty when trying to find an element.
1341 *
1342 * TODO Remove m_buckets_data and only use a pointer instead of a pointer+vector to save some
1343 * space in the robin_hash object. Manage the Allocator manually.
1344 */
1345 bucket_entry *m_buckets;
1346
1347 /**
1348 * Used a lot in find, avoid the call to m_buckets_data.size() which is a bit slower.
1349 */
1350 size_type m_bucket_count;
1351
1352 size_type m_nb_elements;
1353
1354 size_type m_load_threshold;
1355 float m_max_load_factor;
1356
1357 bool m_grow_on_next_insert;
1358
1359 float m_min_load_factor;
1360
1361 /**
1362 * We can't shrink down the map on erase operations as the erase methods need to return the
1363 * next iterator. Shrinking the map would invalidate all the iterators and we could not return
1364 * the next iterator in a meaningful way, On erase, we thus just indicate on erase that we
1365 * should try to shrink the hash table on the next insert if we go below the min_load_factor.
1366 */
1367 bool m_try_skrink_on_next_insert;
1368 };
1369
1370 } // namespace detail_robin_hash
1371
1372 } // namespace tsl
1373
1374 #endif
tsl::detail_robin_hash::robin_hash::insert_value
void insert_value(std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, value_type &&value)
Definition: robin_hash.h:1189
tsl::detail_robin_hash::bucket_entry::bucket_entry
bucket_entry(const bucket_entry &other) noexcept(std::is_nothrow_copy_constructible< value_type >::value)
Definition: robin_hash.h:168
tsl::detail_robin_hash::robin_hash::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: robin_hash.h:969
tsl
Definition: bhopscotch_map.h:37
tsl::detail_robin_hash::robin_hash::erase
size_type erase(const K &key, std::size_t my_hash)
Definition: robin_hash.h:851
tsl::detail_robin_hash::is_power_of_two_policy
Definition: robin_hash.h:62
tsl::detail_robin_hash::robin_hash::find_impl
const_iterator find_impl(const K &key, std::size_t my_hash) const
Definition: robin_hash.h:1086
tsl::detail_robin_hash::robin_hash::bucket_for_hash
std::size_t bucket_for_hash(std::size_t my_hash) const
Definition: robin_hash.h:1054
tsl::detail_robin_hash::robin_hash::m_load_threshold
size_type m_load_threshold
Definition: robin_hash.h:1354
tsl::detail_robin_hash::robin_hash::hash_function
hasher hash_function() const
Definition: robin_hash.h:1034
tsl::detail_robin_hash::robin_hash::size
size_type size() const noexcept
Definition: robin_hash.h:669
tsl::detail_robin_hash::robin_hash::max_load_factor
float max_load_factor() const
Definition: robin_hash.h:1005
tsl::detail_robin_hash::robin_hash::find
const_iterator find(const K &key, std::size_t my_hash) const
Definition: robin_hash.h:952
tsl::detail_robin_hash::bucket_entry::storage
typename std::aligned_storage< sizeof(value_type), alignof(value_type)>::type storage
Definition: robin_hash.h:295
tsl::detail_robin_hash::bucket_entry::dist_from_ideal_bucket
distance_type dist_from_ideal_bucket() const noexcept
Definition: robin_hash.h:243
tsl::detail_robin_hash::robin_hash::DEFAULT_MIN_LOAD_FACTOR
static constexpr float DEFAULT_MIN_LOAD_FACTOR
Definition: robin_hash.h:1310
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::has_mapped_type
typename std::integral_constant< bool, !std::is_same< U, void >::value > has_mapped_type
Definition: robin_hash.h:329
tsl::detail_robin_hash::robin_hash::emplace
std::pair< iterator, bool > emplace(Args &&... args)
Definition: robin_hash.h:740
tsl::detail_robin_hash::make_void::type
void type
Definition: robin_hash.h:49
tsl::detail_robin_hash::make_void
Definition: robin_hash.h:47
robin_growth_policy.h
tsl::detail_robin_hash::robin_hash::insert_or_assign
iterator insert_or_assign(const_iterator hint, K &&key, M &&obj)
Definition: robin_hash.h:728
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::pointer
value_type * pointer
Definition: robin_hash.h:348
tsl::detail_robin_hash::robin_hash::robin_iterator::value
U::value_type & value()
Definition: robin_hash.h:455
tsl::detail_robin_hash::bucket_entry::set_as_last_bucket
void set_as_last_bucket() noexcept
Definition: robin_hash.h:247
tsl::detail_robin_hash::clamp
const T & clamp(const T &v, const T &lo, const T &hi)
Definition: robin_hash.h:73
tsl::detail_robin_hash::robin_hash::STORE_HASH
static constexpr bool STORE_HASH
Definition: robin_hash.h:359
tsl::detail_robin_hash::robin_hash::erase
size_type erase(const K &key)
Definition: robin_hash.h:849
tsl::detail_robin_hash::robin_hash::robin_iterator::robin_iterator
robin_iterator(bucket_entry_ptr bucket) noexcept
Definition: robin_hash.h:422
tsl::detail_robin_hash::bucket_entry::last_bucket
bool last_bucket() const noexcept
Definition: robin_hash.h:245
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::difference_type
std::ptrdiff_t difference_type
Definition: robin_hash.h:342
tsl::detail_robin_hash::bucket_entry_hash::bucket_hash_equal
bool bucket_hash_equal(std::size_t) const noexcept
Definition: robin_hash.h:103
tsl::detail_robin_hash::bucket_entry::m_value
storage m_value
Definition: robin_hash.h:301
tsl::detail_robin_hash::bucket_entry::bucket_entry
bucket_entry() noexcept
Definition: robin_hash.h:154
tsl::detail_robin_hash::bucket_entry::~bucket_entry
~bucket_entry() noexcept
Definition: robin_hash.h:216
tsl::detail_robin_hash::robin_hash::empty
bool empty() const noexcept
Definition: robin_hash.h:667
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::size_type
std::size_t size_type
Definition: robin_hash.h:341
tsl::detail_robin_hash::bucket_entry_hash< true >::m_hash
truncated_hash_type m_hash
Definition: robin_hash.h:125
TSL_RH_LIKELY
#define TSL_RH_LIKELY(exp)
Definition: robin_growth_policy.h:68
tsl::detail_robin_hash::bucket_entry_hash::set_hash
void set_hash(truncated_hash_type) noexcept
Definition: robin_hash.h:108
tsl::detail_robin_hash::robin_hash::robin_iterator::pointer
value_type * pointer
Definition: robin_hash.h:429
tsl::detail_robin_hash::robin_hash::m_buckets
bucket_entry * m_buckets
Definition: robin_hash.h:1345
tsl::detail_robin_hash::bucket_entry::m_last_bucket
bool m_last_bucket
Definition: robin_hash.h:300
tsl::detail_robin_hash::robin_hash::robin_hash
robin_hash(size_type my_bucket_count, const Hash &my_hash, const KeyEqual &equal, const Allocator &alloc, float my_min_load_factor=DEFAULT_MIN_LOAD_FACTOR, float my_max_load_factor=DEFAULT_MAX_LOAD_FACTOR)
Definition: robin_hash.h:539
tsl::detail_robin_hash::robin_hash::robin_iterator::difference_type
std::ptrdiff_t difference_type
Definition: robin_hash.h:427
tsl::detail_robin_hash::robin_hash::m_grow_on_next_insert
bool m_grow_on_next_insert
Definition: robin_hash.h:1357
tsl::detail_robin_hash::robin_hash::robin_iterator::robin_iterator
robin_iterator(const robin_iterator<!TIsConst > &other) noexcept
Definition: robin_hash.h:435
tsl::detail_robin_hash::robin_hash::operator=
robin_hash & operator=(robin_hash &&other)
Definition: robin_hash.h:623
tsl::detail_robin_hash::truncated_hash_type
std::uint_least32_t truncated_hash_type
Definition: robin_hash.h:95
tsl::detail_robin_hash::robin_hash::compare_keys
bool compare_keys(const K1 &key1, const K2 &key2) const
Definition: robin_hash.h:1049
tsl::detail_robin_hash::robin_hash::at
U::value_type & at(const K &key)
Definition: robin_hash.h:888
tsl::detail_robin_hash::robin_hash::max_size
size_type max_size() const noexcept
Definition: robin_hash.h:671
tsl::detail_robin_hash::robin_hash::robin_iterator::operator*
reference operator*() const
Definition: robin_hash.h:460
tsl::detail_robin_hash::robin_hash::hash_key
std::size_t hash_key(const K &key) const
Definition: robin_hash.h:1047
tsl::detail_robin_hash::robin_hash::m_min_load_factor
float m_min_load_factor
Definition: robin_hash.h:1359
tsl::detail_robin_hash::robin_hash::rehash
void rehash(size_type new_count)
Definition: robin_hash.h:1020
tsl::detail_robin_hash::robin_hash::insert_hint
iterator insert_hint(const_iterator hint, P &&value)
Definition: robin_hash.h:691
tsl::detail_robin_hash::robin_hash::find
const_iterator find(const K &key) const
Definition: robin_hash.h:947
tsl::detail_robin_hash::bucket_entry::value_type
ValueType value_type
Definition: robin_hash.h:151
tsl::detail_robin_hash::bucket_entry::set_value_of_empty_bucket
void set_value_of_empty_bucket(distance_type dist_frm_ideal_bucket, truncated_hash_type hash, Args &&... value_type_args)
Definition: robin_hash.h:250
tsl::detail_robin_hash::robin_hash::begin
const_iterator begin() const noexcept
Definition: robin_hash.h:646
tsl_rh_assert
#define tsl_rh_assert(expr)
Definition: robin_growth_policy.h:40
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_reference
const value_type & const_reference
Definition: robin_hash.h:347
tsl::detail_robin_hash::robin_hash::rehash_on_extreme_load
bool rehash_on_extreme_load()
Definition: robin_hash.h:1282
tsl::detail_robin_hash::robin_hash::erase_from_bucket
void erase_from_bucket(iterator pos)
Definition: robin_hash.h:1105
tsl::detail_robin_hash::robin_hash::clear
void clear() noexcept
Definition: robin_hash.h:676
tsl::detail_robin_hash::robin_hash::REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR
static constexpr float REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR
Definition: robin_hash.h:1323
tsl::detail_robin_hash::robin_hash::USE_STORED_HASH_ON_REHASH
static bool USE_STORED_HASH_ON_REHASH(size_type my_bucket_count)
Definition: robin_hash.h:380
tsl::detail_robin_hash::robin_hash::robin_iterator
Definition: robin_hash.h:337
tsl::detail_robin_hash::robin_hash::robin_iterator::operator++
robin_iterator operator++(int)
Definition: robin_hash.h:479
tsl::detail_robin_hash::robin_hash::reserve
void reserve(size_type new_count)
Definition: robin_hash.h:1026
tsl::detail_robin_hash::robin_hash::equal_range
std::pair< iterator, iterator > equal_range(const K &key, std::size_t my_hash)
Definition: robin_hash.h:963
tsl::detail_robin_hash::bucket_entry::m_dist_from_ideal_bucket
distance_type m_dist_from_ideal_bucket
Definition: robin_hash.h:299
tsl::detail_robin_hash::robin_hash::robin_iterator::bucket_entry_ptr
typename std::conditional< IsConst, const bucket_entry *, bucket_entry * >::type bucket_entry_ptr
Definition: robin_hash.h:420
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::value_type
std::pair< Key, T > value_type
Definition: robin_hash.h:340
tsl::detail_robin_hash::robin_hash::equal_range
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t my_hash) const
Definition: robin_hash.h:975
tsl::detail_robin_hash::robin_hash::at
const U::value_type & at(const K &key, std::size_t my_hash) const
Definition: robin_hash.h:910
tsl::detail_robin_hash::robin_hash::find
iterator find(const K &key)
Definition: robin_hash.h:940
tsl::detail_robin_hash::robin_hash::insert_impl
std::pair< iterator, bool > insert_impl(const K &key, Args &&... value_type_args)
Definition: robin_hash.h:1136
tsl::detail_robin_hash::bucket_entry::swap_with_value_in_bucket
void swap_with_value_in_bucket(distance_type &dist_frm_ideal_bucket, truncated_hash_type &hash, value_type &my_value)
Definition: robin_hash.h:264
tsl::detail_robin_hash::robin_hash::cbegin
const_iterator cbegin() const noexcept
Definition: robin_hash.h:648
tsl::detail_robin_hash::bucket_entry::bucket_hash
bucket_entry_hash< StoreHash > bucket_hash
Definition: robin_hash.h:148
tsl::detail_robin_hash::robin_hash::insert_value
void insert_value(std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, Args &&... value_type_args)
Definition: robin_hash.h:1182
tsl::detail_robin_hash::robin_hash::operator[]
U::value_type & operator[](K &&key)
Definition: robin_hash.h:923
tsl::detail_robin_hash::robin_hash::count
size_type count(const K &key) const
Definition: robin_hash.h:928
tsl::detail_robin_hash::robin_hash::robin_iterator::operator!=
friend bool operator!=(const robin_iterator &lhs, const robin_iterator &rhs)
Definition: robin_hash.h:492
tsl::detail_robin_hash::robin_hash::insert
void insert(InputIt first, InputIt last)
Definition: robin_hash.h:700
tsl::detail_robin_hash::robin_hash::MINIMUM_MAX_LOAD_FACTOR
static constexpr float MINIMUM_MAX_LOAD_FACTOR
Definition: robin_hash.h:1307
tsl::detail_robin_hash::has_is_transparent
Definition: robin_hash.h:52
tsl::detail_robin_hash::robin_hash::DEFAULT_INIT_BUCKETS_SIZE
static const size_type DEFAULT_INIT_BUCKETS_SIZE
Definition: robin_hash.h:1304
tsl::detail_robin_hash::robin_hash::cend
const_iterator cend() const noexcept
Definition: robin_hash.h:662
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_equal
KeyEqual key_equal
Definition: robin_hash.h:344
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_pointer
const value_type * const_pointer
Definition: robin_hash.h:349
TSL_RH_THROW_OR_TERMINATE
#define TSL_RH_THROW_OR_TERMINATE(ex, msg)
Definition: robin_growth_policy.h:57
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::hasher
Hash hasher
Definition: robin_hash.h:343
tsl::detail_robin_hash::robin_hash::m_max_load_factor
float m_max_load_factor
Definition: robin_hash.h:1355
tsl::detail_robin_hash::bucket_entry::operator=
bucket_entry & operator=(const bucket_entry &other) noexcept(std::is_nothrow_copy_constructible< value_type >::value)
Definition: robin_hash.h:196
tsl::detail_robin_hash::robin_hash::robin_iterator::value_type
const typename robin_hash::value_type value_type
Definition: robin_hash.h:426
tsl::detail_robin_hash::robin_hash::erase
iterator erase(iterator pos)
Definition: robin_hash.h:772
tsl::detail_robin_hash::robin_hash
Definition: robin_hash.h:325
tsl::detail_robin_hash::robin_hash::mutable_iterator
iterator mutable_iterator(const_iterator pos)
Definition: robin_hash.h:1041
tsl::detail_robin_hash::robin_hash::emplace_hint
iterator emplace_hint(const_iterator hint, Args &&... args)
Definition: robin_hash.h:745
tsl::detail_robin_hash::robin_hash::robin_hash
robin_hash(const robin_hash &other)
Definition: robin_hash.h:564
tsl::detail_robin_hash::robin_hash::next_bucket
std::size_t next_bucket(std::size_t index) const noexcept
Definition: robin_hash.h:1064
tsl::detail_robin_hash::robin_hash::m_buckets_data
buckets_container_type m_buckets_data
Definition: robin_hash.h:1335
tsl::detail_robin_hash::bucket_entry_hash< true >::set_hash
void set_hash(truncated_hash_type hash) noexcept
Definition: robin_hash.h:122
tsl::detail_robin_hash::robin_hash::robin_iterator::robin_iterator
robin_iterator() noexcept
Definition: robin_hash.h:431
tsl::detail_robin_hash::robin_hash::robin_iterator::value
const U::value_type & value() const
Definition: robin_hash.h:448
tsl::detail_robin_hash::bucket_entry::distance_type
std::int_least16_t distance_type
Definition: robin_hash.h:152
tsl::detail_robin_hash::robin_hash::insert_or_assign
std::pair< iterator, bool > insert_or_assign(K &&key, M &&obj)
Definition: robin_hash.h:718
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::buckets_allocator
typename std::allocator_traits< allocator_type >::template rebind_alloc< bucket_entry > buckets_allocator
Definition: robin_hash.h:399
tsl::detail_robin_hash::robin_hash::static_empty_bucket_ptr
bucket_entry * static_empty_bucket_ptr()
Definition: robin_hash.h:1328
tsl::detail_robin_hash::robin_hash::robin_iterator::key
const robin_hash::key_type & key() const
Definition: robin_hash.h:444
tsl::detail_robin_hash::robin_hash::DEFAULT_MAX_LOAD_FACTOR
static constexpr float DEFAULT_MAX_LOAD_FACTOR
Definition: robin_hash.h:1306
tsl::detail_robin_hash::robin_hash::end
const_iterator end() const noexcept
Definition: robin_hash.h:660
tsl::detail_robin_hash::robin_hash::count
size_type count(const K &key, std::size_t my_hash) const
Definition: robin_hash.h:930
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::const_iterator
robin_iterator< true > const_iterator
Definition: robin_hash.h:351
tsl::detail_robin_hash::robin_hash::swap
void swap(robin_hash &other)
Definition: robin_hash.h:865
tsl::detail_robin_hash::numeric_cast
static T numeric_cast(U value, const char *error_message="numeric_cast() failed.")
Definition: robin_hash.h:79
tsl::detail_robin_hash::robin_hash::MINIMUM_MIN_LOAD_FACTOR
static constexpr float MINIMUM_MIN_LOAD_FACTOR
Definition: robin_hash.h:1311
tsl::detail_robin_hash::robin_hash::min_load_factor
float min_load_factor() const
Definition: robin_hash.h:1003
tsl::detail_robin_hash::robin_hash::USE_STORED_HASH_ON_LOOKUP
static constexpr bool USE_STORED_HASH_ON_LOOKUP
Definition: robin_hash.h:372
tsl::detail_robin_hash::bucket_entry::clear
void clear() noexcept
Definition: robin_hash.h:218
tsl::detail_robin_hash::robin_hash::min_load_factor
void min_load_factor(float ml)
Definition: robin_hash.h:1007
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::allocator_type
Allocator allocator_type
Definition: robin_hash.h:345
tsl::detail_robin_hash::robin_hash::max_load_factor
void max_load_factor(float ml)
Definition: robin_hash.h:1013
tsl::detail_robin_hash::robin_hash::distance_type
typename bucket_entry::distance_type distance_type
Definition: robin_hash.h:396
anonymous_namespace{Ioss_Field.C}::error_message
void error_message(const Ioss::Field &field, Ioss::Field::BasicType requested_type)
Definition: Ioss_Field.C:64
tsl::detail_robin_hash::bucket_entry::empty
bool empty() const noexcept
Definition: robin_hash.h:226
tsl::detail_robin_hash::robin_hash::find_impl
iterator find_impl(const K &key, std::size_t my_hash)
Definition: robin_hash.h:1081
tsl::detail_robin_hash::robin_hash::try_emplace_hint
iterator try_emplace_hint(const_iterator hint, K &&key, Args &&... args)
Definition: robin_hash.h:759
tsl::detail_robin_hash::robin_hash::rehash_impl
void rehash_impl(size_type new_count)
Definition: robin_hash.h:1231
tsl::detail_robin_hash::bucket_entry::bucket_entry
bucket_entry(bucket_entry &&other) noexcept(std::is_nothrow_move_constructible< value_type >::value)
Definition: robin_hash.h:184
tsl::detail_robin_hash::bucket_entry_hash::truncated_hash
truncated_hash_type truncated_hash() const noexcept
Definition: robin_hash.h:105
tsl::detail_robin_hash::bucket_entry_hash
Definition: robin_hash.h:100
tsl::detail_robin_hash::robin_hash::robin_iterator::operator->
pointer operator->() const
Definition: robin_hash.h:462
tsl::detail_robin_hash::robin_hash::at
U::value_type & at(const K &key, std::size_t my_hash)
Definition: robin_hash.h:895
tsl::detail_robin_hash::robin_hash::end
iterator end() noexcept
Definition: robin_hash.h:658
tsl::detail_robin_hash::bucket_entry::value
const value_type & value() const noexcept
Definition: robin_hash.h:237
anonymous_namespace{cth_pressure_map.C}::data
std::vector< char > data
Definition: cth_pressure_map.C:74
tsl::detail_robin_hash::robin_hash::robin_iterator::reference
value_type & reference
Definition: robin_hash.h:428
tsl::rh::power_of_two_growth_policy
Definition: robin_growth_policy.h:81
tsl::detail_robin_hash::robin_hash::robin_iterator::operator++
robin_iterator & operator++()
Definition: robin_hash.h:464
tsl::detail_robin_hash::bucket_entry::truncate_hash
static truncated_hash_type truncate_hash(std::size_t hash) noexcept
Definition: robin_hash.h:282
tsl::detail_robin_hash::robin_hash::erase
iterator erase(const_iterator first, const_iterator last)
Definition: robin_hash.h:791
tsl::detail_robin_hash::robin_hash::robin_iterator::operator=
robin_iterator & operator=(const robin_iterator &other)=default
tsl::detail_robin_hash::robin_hash::robin_iterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: robin_hash.h:425
tsl::detail_robin_hash::robin_hash::get_allocator
allocator_type get_allocator() const
Definition: robin_hash.h:631
tsl::detail_robin_hash::robin_hash::m_bucket_count
size_type m_bucket_count
Definition: robin_hash.h:1350
tsl::detail_robin_hash::robin_hash::MAXIMUM_MAX_LOAD_FACTOR
static constexpr float MAXIMUM_MAX_LOAD_FACTOR
Definition: robin_hash.h:1308
tsl::detail_robin_hash::robin_hash::max_bucket_count
size_type max_bucket_count() const
Definition: robin_hash.h:986
tsl::detail_robin_hash::bucket_entry::value
value_type & value() noexcept
Definition: robin_hash.h:231
tsl::detail_robin_hash::robin_hash::robin_iterator::m_bucket
bucket_entry_ptr m_bucket
Definition: robin_hash.h:498
tsl::detail_robin_hash::robin_hash::equal_range
std::pair< iterator, iterator > equal_range(const K &key)
Definition: robin_hash.h:957
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::reference
value_type & reference
Definition: robin_hash.h:346
tsl::detail_robin_hash::robin_hash::operator=
robin_hash & operator=(const robin_hash &other)
Definition: robin_hash.h:600
tsl::detail_robin_hash::bucket_entry::EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET
static const distance_type EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET
Definition: robin_hash.h:297
tsl::detail_robin_hash::robin_hash::m_nb_elements
size_type m_nb_elements
Definition: robin_hash.h:1352
tsl::detail_robin_hash::bucket_entry
Definition: robin_hash.h:146
tsl::detail_robin_hash::robin_hash::m_try_skrink_on_next_insert
bool m_try_skrink_on_next_insert
Definition: robin_hash.h:1367
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::key_type
typename KeySelect::key_type key_type
Definition: robin_hash.h:339
tsl::detail_robin_hash::bucket_entry::destroy_value
void destroy_value() noexcept
Definition: robin_hash.h:288
tsl::detail_robin_hash::bucket_entry_hash< true >::truncated_hash
truncated_hash_type truncated_hash() const noexcept
Definition: robin_hash.h:119
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::buckets_container_type
std::vector< bucket_entry, buckets_allocator > buckets_container_type
Definition: robin_hash.h:400
tsl::detail_robin_hash::robin_hash::find
iterator find(const K &key, std::size_t my_hash)
Definition: robin_hash.h:942
tsl::detail_robin_hash::robin_hash::insert_value_on_rehash
void insert_value_on_rehash(std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, value_type &&value)
Definition: robin_hash.h:1255
tsl::detail_robin_hash::robin_hash::bucket_count
size_type bucket_count() const
Definition: robin_hash.h:984
tsl::detail_robin_hash::robin_hash::REHASH_ON_HIGH_NB_PROBES__NPROBES
static const distance_type REHASH_ON_HIGH_NB_PROBES__NPROBES
Definition: robin_hash.h:1322
tsl::detail_robin_hash::robin_hash::insert_value_impl
void insert_value_impl(std::size_t ibucket, distance_type dist_from_ideal_bucket, truncated_hash_type my_hash, value_type &value)
Definition: robin_hash.h:1202
tsl::detail_robin_hash::bucket_entry::bucket_entry
bucket_entry(bool lst_bucket) noexcept
Definition: robin_hash.h:161
tsl::detail_robin_hash::robin_hash::try_emplace
std::pair< iterator, bool > try_emplace(K &&key, Args &&... args)
Definition: robin_hash.h:751
tsl::detail_robin_hash::bucket_entry_hash< true >::bucket_hash_equal
bool bucket_hash_equal(std::size_t hash) const noexcept
Definition: robin_hash.h:114
tsl::detail_robin_hash::robin_hash::robin_iterator::operator==
friend bool operator==(const robin_iterator &lhs, const robin_iterator &rhs)
Definition: robin_hash.h:487
tsl::detail_robin_hash::robin_hash::MAXIMUM_MIN_LOAD_FACTOR
static constexpr float MAXIMUM_MIN_LOAD_FACTOR
Definition: robin_hash.h:1312
tsl::detail_robin_hash::robin_hash::begin
iterator begin() noexcept
Definition: robin_hash.h:636
tsl::detail_robin_hash::robin_hash::erase
iterator erase(const_iterator pos)
Definition: robin_hash.h:789
tsl::detail_robin_hash::robin_hash::at
const U::value_type & at(const K &key) const
Definition: robin_hash.h:903
tsl::detail_robin_hash::robin_hash< std::pair< Key, T >, KeySelect, ValueSelect, Hash, KeyEqual, Allocator, StoreHash, GrowthPolicy >::iterator
robin_iterator< false > iterator
Definition: robin_hash.h:350
tsl::detail_robin_hash::robin_hash::robin_hash
robin_hash(robin_hash &&other) noexcept(std::is_nothrow_move_constructible< Hash >::value &&std::is_nothrow_move_constructible< KeyEqual >::value &&std::is_nothrow_move_constructible< GrowthPolicy >::value &&std::is_nothrow_move_constructible< buckets_container_type >::value)
Definition: robin_hash.h:575
tsl::detail_robin_hash::robin_hash::key_eq
key_equal key_eq() const
Definition: robin_hash.h:1036
tsl::detail_robin_hash::robin_hash::insert
std::pair< iterator, bool > insert(P &&value)
Definition: robin_hash.h:686
tsl::detail_robin_hash::robin_hash::load_factor
float load_factor() const
Definition: robin_hash.h:994