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