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