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