24 #ifndef PXR_TSL_ROBIN_HASH_H 25 #define PXR_TSL_ROBIN_HASH_H 38 #include <type_traits> 42 #include "robin_growth_policy.h" 47 PXR_NAMESPACE_OPEN_SCOPE
51 namespace detail_robin_hash {
58 template <
typename T,
typename =
void>
59 struct has_is_transparent : std::false_type {};
62 struct has_is_transparent<T,
63 typename make_void<typename T::is_transparent>::type>
67 struct is_power_of_two_policy : std::false_type {};
69 template <std::
size_t GrowthFactor>
70 struct is_power_of_two_policy<
pxr_tsl::rh::power_of_two_growth_policy<GrowthFactor>>
75 const T& clamp(
const T& v,
const T& lo,
const T& hi) {
76 return std::min(hi, std::max(lo, v));
79 template <
typename T,
typename U>
80 static T numeric_cast(U value,
81 const char* error_message =
"numeric_cast() failed.") {
82 T ret = static_cast<T>(value);
83 if (static_cast<U>(ret) != value) {
84 PXR_TSL_RH_THROW_OR_TERMINATE(std::runtime_error, error_message);
87 const bool is_same_signedness =
88 (std::is_unsigned<T>::value && std::is_unsigned<U>::value) ||
89 (std::is_signed<T>::value && std::is_signed<U>::value);
90 if (!is_same_signedness && (ret < T{}) != (value < U{})) {
91 PXR_TSL_RH_THROW_OR_TERMINATE(std::runtime_error, error_message);
97 template <
class T,
class Deserializer>
98 static T deserialize_value(Deserializer& deserializer) {
101 #if defined(_MSC_VER) && _MSC_VER < 1910 102 return deserializer.Deserializer::operator()<T>();
104 return deserializer.Deserializer::template operator()<T>();
113 using slz_size_type = std::uint64_t;
114 static_assert(std::numeric_limits<slz_size_type>::max() >=
115 std::numeric_limits<std::size_t>::max(),
116 "slz_size_type must be >= std::size_t");
118 using truncated_hash_type = std::uint32_t;
124 template <
bool StoreHash>
127 bool bucket_hash_equal(std::size_t )
const noexcept {
return true; }
129 truncated_hash_type truncated_hash()
const noexcept {
return 0; }
132 void set_hash(truncated_hash_type ) noexcept {}
138 bool bucket_hash_equal(std::size_t hash)
const noexcept {
139 return m_hash == truncated_hash_type(hash);
142 truncated_hash_type truncated_hash() const noexcept {
return m_hash; }
145 void set_hash(truncated_hash_type hash) noexcept {
146 m_hash = truncated_hash_type(hash);
150 truncated_hash_type m_hash;
171 template <
typename ValueType,
bool StoreHash>
176 using value_type = ValueType;
177 using distance_type = std::int16_t;
181 m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
182 m_last_bucket(
false) {
183 pxr_tsl_rh_assert(empty());
188 m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
189 m_last_bucket(last_bucket) {
190 pxr_tsl_rh_assert(empty());
194 std::is_nothrow_copy_constructible<value_type>::value)
196 m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
197 m_last_bucket(other.m_last_bucket) {
198 if (!other.empty()) {
199 ::new (static_cast<void*>(std::addressof(m_value)))
200 value_type(other.value());
201 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
211 std::is_nothrow_move_constructible<value_type>::value)
213 m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
214 m_last_bucket(other.m_last_bucket) {
215 if (!other.empty()) {
216 ::new (static_cast<void*>(std::addressof(m_value)))
217 value_type(std::move(other.value()));
218 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
223 std::is_nothrow_copy_constructible<value_type>::value) {
224 if (
this != &other) {
227 bucket_hash::operator=(other);
228 if (!other.empty()) {
229 ::new (static_cast<void*>(std::addressof(m_value)))
230 value_type(other.value());
233 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
234 m_last_bucket = other.m_last_bucket;
240 bucket_entry& operator=(bucket_entry&&) =
delete;
242 ~bucket_entry() noexcept { clear(); }
244 void clear() noexcept {
247 m_dist_from_ideal_bucket = EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET;
251 bool empty() const noexcept {
252 return m_dist_from_ideal_bucket == EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET;
255 value_type& value() noexcept {
256 pxr_tsl_rh_assert(!empty());
257 return *reinterpret_cast<value_type*>(std::addressof(m_value));
260 const value_type& value() const noexcept {
261 pxr_tsl_rh_assert(!empty());
262 return *reinterpret_cast<const value_type*>(std::addressof(m_value));
265 distance_type dist_from_ideal_bucket() const noexcept {
266 return m_dist_from_ideal_bucket;
269 bool last_bucket() const noexcept {
return m_last_bucket; }
271 void set_as_last_bucket() noexcept { m_last_bucket =
true; }
273 template <
typename... Args>
274 void set_value_of_empty_bucket(distance_type dist_from_ideal_bucket,
275 truncated_hash_type hash,
276 Args&&... value_type_args) {
277 pxr_tsl_rh_assert(dist_from_ideal_bucket >= 0);
278 pxr_tsl_rh_assert(empty());
280 ::new (static_cast<void*>(std::addressof(m_value)))
281 value_type(std::forward<Args>(value_type_args)...);
282 this->set_hash(hash);
283 m_dist_from_ideal_bucket = dist_from_ideal_bucket;
285 pxr_tsl_rh_assert(!empty());
288 void swap_with_value_in_bucket(distance_type& dist_from_ideal_bucket,
289 truncated_hash_type& hash, value_type& value) {
290 pxr_tsl_rh_assert(!empty());
293 swap(value, this->value());
294 swap(dist_from_ideal_bucket, m_dist_from_ideal_bucket);
297 const truncated_hash_type tmp_hash = this->truncated_hash();
298 this->set_hash(hash);
302 PXR_TSL_RH_UNUSED(hash);
306 static truncated_hash_type truncate_hash(std::size_t hash) noexcept {
307 return truncated_hash_type(hash);
311 void destroy_value() noexcept {
312 pxr_tsl_rh_assert(!empty());
313 value().~value_type();
317 static const distance_type EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1;
318 static const distance_type DIST_FROM_IDEAL_BUCKET_LIMIT = 4096;
319 static_assert(DIST_FROM_IDEAL_BUCKET_LIMIT <=
320 std::numeric_limits<distance_type>::max() - 1,
321 "DIST_FROM_IDEAL_BUCKET_LIMIT must be <= " 322 "std::numeric_limits<distance_type>::max() - 1.");
325 using storage =
typename std::aligned_storage<
sizeof(value_type),
326 alignof(value_type)>::type;
328 distance_type m_dist_from_ideal_bucket;
352 template <
class ValueType,
class KeySelect,
class ValueSelect,
class Hash,
353 class KeyEqual,
class Allocator,
bool StoreHash,
class GrowthPolicy>
354 class robin_hash :
private Hash,
private KeyEqual,
private GrowthPolicy {
356 template <
typename U>
357 using has_mapped_type =
358 typename std::integral_constant<bool, !std::is_same<U, void>::value>;
361 noexcept(std::declval<GrowthPolicy>().bucket_for_hash(std::size_t(0))),
362 "GrowthPolicy::bucket_for_hash must be noexcept.");
363 static_assert(noexcept(std::declval<GrowthPolicy>().clear()),
364 "GrowthPolicy::clear must be noexcept.");
367 template <
bool IsConst>
370 using key_type =
typename KeySelect::key_type;
371 using value_type = ValueType;
372 using size_type = std::size_t;
373 using difference_type = std::ptrdiff_t;
375 using key_equal = KeyEqual;
376 using allocator_type = Allocator;
377 using reference = value_type&;
378 using const_reference =
const value_type&;
379 using pointer = value_type*;
380 using const_pointer =
const value_type*;
390 static constexpr
bool STORE_HASH =
394 (
sizeof(std::size_t) ==
sizeof(truncated_hash_type) ||
395 is_power_of_two_policy<GrowthPolicy>::value) &&
397 (!std::is_arithmetic<key_type>::value ||
398 !std::is_same<Hash, std::hash<key_type>>::value));
405 static constexpr
bool USE_STORED_HASH_ON_LOOKUP = StoreHash;
413 static bool USE_STORED_HASH_ON_REHASH(size_type bucket_count) {
414 if (STORE_HASH &&
sizeof(std::size_t) ==
sizeof(truncated_hash_type)) {
415 PXR_TSL_RH_UNUSED(bucket_count);
417 }
else if (STORE_HASH && is_power_of_two_policy<GrowthPolicy>::value) {
418 pxr_tsl_rh_assert(bucket_count > 0);
419 return (bucket_count - 1) <=
420 std::numeric_limits<truncated_hash_type>::max();
422 PXR_TSL_RH_UNUSED(bucket_count);
429 using distance_type =
typename bucket_entry::distance_type;
431 using buckets_allocator =
typename std::allocator_traits<
432 allocator_type>::template rebind_alloc<bucket_entry>;
433 using buckets_container_type = std::vector<bucket_entry, buckets_allocator>;
447 template <
bool IsConst>
448 class robin_iterator {
449 friend class robin_hash;
452 using bucket_entry_ptr =
453 typename std::conditional<IsConst,
const bucket_entry*,
454 bucket_entry*>::type;
456 robin_iterator(bucket_entry_ptr bucket) noexcept : m_bucket(bucket) {}
459 using iterator_category = std::forward_iterator_tag;
460 using value_type =
const typename robin_hash::value_type;
461 using difference_type = std::ptrdiff_t;
462 using reference = value_type&;
463 using pointer = value_type*;
465 robin_iterator() noexcept {}
468 template <
bool TIsConst = IsConst,
469 typename std::enable_if<TIsConst>::type* =
nullptr>
470 robin_iterator(
const robin_iterator<!TIsConst>& other) noexcept
471 : m_bucket(other.m_bucket) {}
473 robin_iterator(
const robin_iterator& other) =
default;
474 robin_iterator(robin_iterator&& other) =
default;
475 robin_iterator& operator=(
const robin_iterator& other) =
default;
476 robin_iterator& operator=(robin_iterator&& other) =
default;
478 const typename robin_hash::key_type& key()
const {
479 return KeySelect()(m_bucket->value());
482 template <
class U = ValueSelect,
483 typename std::enable_if<has_mapped_type<U>::value &&
484 IsConst>::type* =
nullptr>
485 const typename U::value_type& value()
const {
486 return U()(m_bucket->value());
489 template <
class U = ValueSelect,
490 typename std::enable_if<has_mapped_type<U>::value &&
491 !IsConst>::type* =
nullptr>
492 typename U::value_type& value()
const {
493 return U()(m_bucket->value());
496 reference operator*()
const {
return m_bucket->value(); }
498 pointer operator->()
const {
return std::addressof(m_bucket->value()); }
500 robin_iterator& operator++() {
502 if (m_bucket->last_bucket()) {
508 if (!m_bucket->empty()) {
514 robin_iterator operator++(
int) {
515 robin_iterator tmp(*
this);
521 friend bool operator==(
const robin_iterator& lhs,
522 const robin_iterator& rhs) {
523 return lhs.m_bucket == rhs.m_bucket;
526 friend bool operator!=(
const robin_iterator& lhs,
527 const robin_iterator& rhs) {
528 return !(lhs == rhs);
532 bucket_entry_ptr m_bucket;
536 #if defined(__cplusplus) && __cplusplus >= 201402L 537 robin_hash(size_type bucket_count,
const Hash& hash,
const KeyEqual& equal,
538 const Allocator& alloc,
539 float min_load_factor = DEFAULT_MIN_LOAD_FACTOR,
540 float max_load_factor = DEFAULT_MAX_LOAD_FACTOR)
543 GrowthPolicy(bucket_count),
546 if (bucket_count > max_bucket_count()) {
547 PXR_TSL_RH_THROW_OR_TERMINATE(
549 "The map exceeds its maximum bucket count.");
555 m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr()
556 : m_buckets_data.data()),
557 m_bucket_count(bucket_count),
559 m_grow_on_next_insert(false),
560 m_try_shrink_on_next_insert(false) {
561 if (m_bucket_count > 0) {
562 pxr_tsl_rh_assert(!m_buckets_data.empty());
563 m_buckets_data.back().set_as_last_bucket();
566 this->min_load_factor(min_load_factor);
567 this->max_load_factor(max_load_factor);
580 robin_hash(size_type bucket_count,
const Hash& hash,
const KeyEqual& equal,
581 const Allocator& alloc,
582 float min_load_factor = DEFAULT_MIN_LOAD_FACTOR,
583 float max_load_factor = DEFAULT_MAX_LOAD_FACTOR)
586 GrowthPolicy(bucket_count),
587 m_buckets_data(alloc),
588 m_buckets(static_empty_bucket_ptr()),
589 m_bucket_count(bucket_count),
591 m_grow_on_next_insert(false),
592 m_try_shrink_on_next_insert(false) {
593 if (bucket_count > max_bucket_count()) {
594 PXR_TSL_RH_THROW_OR_TERMINATE(std::length_error,
595 "The map exceeds its maximum bucket count.");
598 if (m_bucket_count > 0) {
599 m_buckets_data.resize(m_bucket_count);
600 m_buckets = m_buckets_data.data();
602 pxr_tsl_rh_assert(!m_buckets_data.empty());
603 m_buckets_data.back().set_as_last_bucket();
606 this->min_load_factor(min_load_factor);
607 this->max_load_factor(max_load_factor);
615 m_buckets_data(other.m_buckets_data),
616 m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr()
617 : m_buckets_data.data()),
618 m_bucket_count(other.m_bucket_count),
619 m_nb_elements(other.m_nb_elements),
620 m_load_threshold(other.m_load_threshold),
621 m_min_load_factor(other.m_min_load_factor),
622 m_max_load_factor(other.m_max_load_factor),
623 m_grow_on_next_insert(other.m_grow_on_next_insert),
624 m_try_shrink_on_next_insert(other.m_try_shrink_on_next_insert) {}
627 std::is_nothrow_move_constructible<
628 Hash>::value&& std::is_nothrow_move_constructible<KeyEqual>::value&&
629 std::is_nothrow_move_constructible<GrowthPolicy>::value&&
630 std::is_nothrow_move_constructible<buckets_container_type>::value)
631 : Hash(std::move(static_cast<Hash&>(other))),
632 KeyEqual(std::move(static_cast<KeyEqual&>(other))),
633 GrowthPolicy(std::move(static_cast<GrowthPolicy&>(other))),
634 m_buckets_data(std::move(other.m_buckets_data)),
635 m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr()
636 : m_buckets_data.data()),
637 m_bucket_count(other.m_bucket_count),
638 m_nb_elements(other.m_nb_elements),
639 m_load_threshold(other.m_load_threshold),
640 m_min_load_factor(other.m_min_load_factor),
641 m_max_load_factor(other.m_max_load_factor),
642 m_grow_on_next_insert(other.m_grow_on_next_insert),
643 m_try_shrink_on_next_insert(other.m_try_shrink_on_next_insert) {
644 other.clear_and_shrink();
648 if (&other !=
this) {
649 Hash::operator=(other);
650 KeyEqual::operator=(other);
651 GrowthPolicy::operator=(other);
653 m_buckets_data = other.m_buckets_data;
654 m_buckets = m_buckets_data.empty() ? static_empty_bucket_ptr()
655 : m_buckets_data.data();
656 m_bucket_count = other.m_bucket_count;
657 m_nb_elements = other.m_nb_elements;
659 m_load_threshold = other.m_load_threshold;
660 m_min_load_factor = other.m_min_load_factor;
661 m_max_load_factor = other.m_max_load_factor;
663 m_grow_on_next_insert = other.m_grow_on_next_insert;
664 m_try_shrink_on_next_insert = other.m_try_shrink_on_next_insert;
677 allocator_type get_allocator()
const {
678 return m_buckets_data.get_allocator();
684 iterator begin() noexcept {
686 while (i < m_bucket_count && m_buckets[i].empty()) {
690 return iterator(m_buckets + i);
693 const_iterator begin() const noexcept {
return cbegin(); }
695 const_iterator cbegin() const noexcept {
697 while (i < m_bucket_count && m_buckets[i].empty()) {
701 return const_iterator(m_buckets + i);
704 iterator end() noexcept {
return iterator(m_buckets + m_bucket_count); }
706 const_iterator end() const noexcept {
return cend(); }
708 const_iterator cend() const noexcept {
709 return const_iterator(m_buckets + m_bucket_count);
715 bool empty() const noexcept {
return m_nb_elements == 0; }
717 size_type size() const noexcept {
return m_nb_elements; }
719 size_type max_size() const noexcept {
return m_buckets_data.max_size(); }
724 void clear() noexcept {
725 if (m_min_load_factor > 0.0f) {
728 for (
auto& bucket : m_buckets_data) {
733 m_grow_on_next_insert =
false;
737 template <
typename P>
738 std::pair<iterator, bool> insert(P&& value) {
739 return insert_impl(KeySelect()(value), std::forward<P>(value));
742 template <
typename P>
743 iterator insert_hint(const_iterator hint, P&& value) {
744 if (hint != cend() &&
745 compare_keys(KeySelect()(*hint), KeySelect()(value))) {
746 return mutable_iterator(hint);
749 return insert(std::forward<P>(value)).first;
752 template <
class InputIt>
753 void insert(InputIt first, InputIt last) {
755 std::forward_iterator_tag,
756 typename std::iterator_traits<InputIt>::iterator_category>::value) {
757 const auto nb_elements_insert = std::distance(first, last);
758 const size_type nb_free_buckets = m_load_threshold - size();
759 pxr_tsl_rh_assert(m_load_threshold >= size());
761 if (nb_elements_insert > 0 &&
762 nb_free_buckets < size_type(nb_elements_insert)) {
763 reserve(size() + size_type(nb_elements_insert));
767 for (; first != last; ++first) {
772 template <
class K,
class M>
773 std::pair<iterator, bool> insert_or_assign(K&& key, M&& obj) {
774 auto it = try_emplace(std::forward<K>(key), std::forward<M>(obj));
776 it.first.value() = std::forward<M>(obj);
782 template <
class K,
class M>
783 iterator insert_or_assign(const_iterator hint, K&& key, M&& obj) {
784 if (hint != cend() && compare_keys(KeySelect()(*hint), key)) {
785 auto it = mutable_iterator(hint);
786 it.value() = std::forward<M>(obj);
791 return insert_or_assign(std::forward<K>(key), std::forward<M>(obj)).first;
794 template <
class... Args>
795 std::pair<iterator, bool> emplace(Args&&... args) {
796 return insert(value_type(std::forward<Args>(args)...));
799 template <
class... Args>
800 iterator emplace_hint(const_iterator hint, Args&&... args) {
801 return insert_hint(hint, value_type(std::forward<Args>(args)...));
804 template <
class K,
class... Args>
805 std::pair<iterator, bool> try_emplace(K&& key, Args&&... args) {
806 return insert_impl(key, std::piecewise_construct,
807 std::forward_as_tuple(std::forward<K>(key)),
808 std::forward_as_tuple(std::forward<Args>(args)...));
811 template <
class K,
class... Args>
812 iterator try_emplace_hint(const_iterator hint, K&& key, Args&&... args) {
813 if (hint != cend() && compare_keys(KeySelect()(*hint), key)) {
814 return mutable_iterator(hint);
817 return try_emplace(std::forward<K>(key), std::forward<Args>(args)...).first;
825 erase_from_bucket(pos);
832 if (pos.m_bucket->empty()) {
836 m_try_shrink_on_next_insert =
true;
841 iterator
erase(const_iterator pos) {
return erase(mutable_iterator(pos)); }
843 iterator
erase(const_iterator first, const_iterator last) {
845 return mutable_iterator(first);
848 auto first_mutable = mutable_iterator(first);
849 auto last_mutable = mutable_iterator(last);
850 for (
auto it = first_mutable.m_bucket; it != last_mutable.m_bucket; ++it) {
857 if (last_mutable == end()) {
858 m_try_shrink_on_next_insert =
true;
866 std::size_t icloser_bucket =
867 static_cast<std::size_t>(first_mutable.m_bucket - m_buckets);
868 std::size_t ito_move_closer_value =
869 static_cast<std::size_t>(last_mutable.m_bucket - m_buckets);
870 pxr_tsl_rh_assert(ito_move_closer_value > icloser_bucket);
872 const std::size_t ireturn_bucket =
873 ito_move_closer_value -
875 ito_move_closer_value - icloser_bucket,
877 m_buckets[ito_move_closer_value].dist_from_ideal_bucket()));
879 while (ito_move_closer_value < m_bucket_count &&
880 m_buckets[ito_move_closer_value].dist_from_ideal_bucket() > 0) {
882 ito_move_closer_value -
884 ito_move_closer_value - icloser_bucket,
886 m_buckets[ito_move_closer_value].dist_from_ideal_bucket()));
888 pxr_tsl_rh_assert(m_buckets[icloser_bucket].empty());
889 const distance_type new_distance = distance_type(
890 m_buckets[ito_move_closer_value].dist_from_ideal_bucket() -
891 (ito_move_closer_value - icloser_bucket));
892 m_buckets[icloser_bucket].set_value_of_empty_bucket(
893 new_distance, m_buckets[ito_move_closer_value].truncated_hash(),
894 std::move(m_buckets[ito_move_closer_value].value()));
895 m_buckets[ito_move_closer_value].clear();
898 ++ito_move_closer_value;
901 m_try_shrink_on_next_insert =
true;
903 return iterator(m_buckets + ireturn_bucket);
907 size_type
erase(
const K& key) {
908 return erase(key, hash_key(key));
912 size_type
erase(
const K& key, std::size_t hash) {
913 auto it = find(key, hash);
915 erase_from_bucket(it);
916 m_try_shrink_on_next_insert =
true;
927 swap(static_cast<Hash&>(*
this), static_cast<Hash&>(other));
928 swap(static_cast<KeyEqual&>(*
this), static_cast<KeyEqual&>(other));
929 swap(static_cast<GrowthPolicy&>(*
this), static_cast<GrowthPolicy&>(other));
930 swap(m_buckets_data, other.m_buckets_data);
931 swap(m_buckets, other.m_buckets);
932 swap(m_bucket_count, other.m_bucket_count);
933 swap(m_nb_elements, other.m_nb_elements);
934 swap(m_load_threshold, other.m_load_threshold);
935 swap(m_min_load_factor, other.m_min_load_factor);
936 swap(m_max_load_factor, other.m_max_load_factor);
937 swap(m_grow_on_next_insert, other.m_grow_on_next_insert);
938 swap(m_try_shrink_on_next_insert, other.m_try_shrink_on_next_insert);
944 template <
class K,
class U = ValueSelect,
945 typename std::enable_if<has_mapped_type<U>::value>::type* =
nullptr>
946 typename U::value_type& at(
const K& key) {
947 return at(key, hash_key(key));
950 template <
class K,
class U = ValueSelect,
951 typename std::enable_if<has_mapped_type<U>::value>::type* =
nullptr>
952 typename U::value_type& at(
const K& key, std::size_t hash) {
953 return const_cast<typename U::value_type&>(
954 static_cast<const robin_hash*>(
this)->at(key, hash));
957 template <
class K,
class U = ValueSelect,
958 typename std::enable_if<has_mapped_type<U>::value>::type* =
nullptr>
959 const typename U::value_type& at(
const K& key)
const {
960 return at(key, hash_key(key));
963 template <
class K,
class U = ValueSelect,
964 typename std::enable_if<has_mapped_type<U>::value>::type* =
nullptr>
965 const typename U::value_type& at(
const K& key, std::size_t hash)
const {
966 auto it = find(key, hash);
970 PXR_TSL_RH_THROW_OR_TERMINATE(std::out_of_range,
"Couldn't find key.");
974 template <
class K,
class U = ValueSelect,
975 typename std::enable_if<has_mapped_type<U>::value>::type* =
nullptr>
976 typename U::value_type& operator[](K&& key) {
977 return try_emplace(std::forward<K>(key)).first.value();
981 size_type count(
const K& key)
const {
982 return count(key, hash_key(key));
986 size_type count(
const K& key, std::size_t hash)
const {
987 if (find(key, hash) != cend()) {
995 iterator find(
const K& key) {
996 return find_impl(key, hash_key(key));
1000 iterator find(
const K& key, std::size_t hash) {
1001 return find_impl(key, hash);
1005 const_iterator find(
const K& key)
const {
1006 return find_impl(key, hash_key(key));
1010 const_iterator find(
const K& key, std::size_t hash)
const {
1011 return find_impl(key, hash);
1015 bool contains(
const K& key)
const {
1016 return contains(key, hash_key(key));
1020 bool contains(
const K& key, std::size_t hash)
const {
1021 return count(key, hash) != 0;
1025 std::pair<iterator, iterator> equal_range(
const K& key) {
1026 return equal_range(key, hash_key(key));
1030 std::pair<iterator, iterator> equal_range(
const K& key, std::size_t hash) {
1031 iterator it = find(key, hash);
1032 return std::make_pair(it, (it == end()) ? it : std::next(it));
1036 std::pair<const_iterator, const_iterator> equal_range(
const K& key)
const {
1037 return equal_range(key, hash_key(key));
1041 std::pair<const_iterator, const_iterator> equal_range(
1042 const K& key, std::size_t hash)
const {
1043 const_iterator it = find(key, hash);
1044 return std::make_pair(it, (it == cend()) ? it : std::next(it));
1050 size_type bucket_count()
const {
return m_bucket_count; }
1052 size_type max_bucket_count()
const {
1053 return std::min(GrowthPolicy::max_bucket_count(),
1054 m_buckets_data.max_size());
1060 float load_factor()
const {
1061 if (bucket_count() == 0) {
1065 return float(m_nb_elements) / float(bucket_count());
1068 float min_load_factor()
const {
return m_min_load_factor; }
1070 float max_load_factor()
const {
return m_max_load_factor; }
1072 void min_load_factor(
float ml) {
1073 m_min_load_factor = clamp(ml,
float(MINIMUM_MIN_LOAD_FACTOR),
1074 float(MAXIMUM_MIN_LOAD_FACTOR));
1077 void max_load_factor(
float ml) {
1078 m_max_load_factor = clamp(ml,
float(MINIMUM_MAX_LOAD_FACTOR),
1079 float(MAXIMUM_MAX_LOAD_FACTOR));
1080 m_load_threshold = size_type(
float(bucket_count()) * m_max_load_factor);
1083 void rehash(size_type count_) {
1084 count_ = std::max(count_,
1085 size_type(std::ceil(
float(size()) / max_load_factor())));
1086 rehash_impl(count_);
1089 void reserve(size_type count_) {
1090 rehash(size_type(std::ceil(
float(count_) / max_load_factor())));
1096 hasher hash_function()
const {
return static_cast<const Hash&>(*
this); }
1098 key_equal key_eq()
const {
return static_cast<const KeyEqual&>(*
this); }
1103 iterator mutable_iterator(const_iterator pos) {
1104 return iterator(const_cast<bucket_entry*>(pos.m_bucket));
1107 template <
class Serializer>
1108 void serialize(Serializer& serializer)
const {
1109 serialize_impl(serializer);
1112 template <
class Deserializer>
1113 void deserialize(Deserializer& deserializer,
bool hash_compatible) {
1114 deserialize_impl(deserializer, hash_compatible);
1119 std::size_t hash_key(
const K& key)
const {
1120 return Hash::operator()(key);
1123 template <
class K1,
class K2>
1124 bool compare_keys(
const K1& key1,
const K2& key2)
const {
1125 return KeyEqual::operator()(key1, key2);
1128 std::size_t bucket_for_hash(std::size_t hash)
const {
1129 const std::size_t bucket = GrowthPolicy::bucket_for_hash(hash);
1130 pxr_tsl_rh_assert(bucket < m_bucket_count ||
1131 (bucket == 0 && m_bucket_count == 0));
1136 template <
class U = GrowthPolicy,
1137 typename std::enable_if<is_power_of_two_policy<U>::value>::type* =
1139 std::size_t next_bucket(std::size_t index)
const noexcept {
1140 pxr_tsl_rh_assert(index < bucket_count());
1142 return (index + 1) & this->m_mask;
1145 template <
class U = GrowthPolicy,
1146 typename std::enable_if<!is_power_of_two_policy<U>::value>::type* =
1148 std::size_t next_bucket(std::size_t index)
const noexcept {
1149 pxr_tsl_rh_assert(index < bucket_count());
1152 return (index != bucket_count()) ? index : 0;
1156 iterator find_impl(
const K& key, std::size_t hash) {
1157 return mutable_iterator(
1158 static_cast<const robin_hash*>(
this)->find(key, hash));
1162 const_iterator find_impl(
const K& key, std::size_t hash)
const {
1163 std::size_t ibucket = bucket_for_hash(hash);
1164 distance_type dist_from_ideal_bucket = 0;
1166 while (dist_from_ideal_bucket <=
1167 m_buckets[ibucket].dist_from_ideal_bucket()) {
1168 if (PXR_TSL_RH_LIKELY(
1169 (!USE_STORED_HASH_ON_LOOKUP ||
1170 m_buckets[ibucket].bucket_hash_equal(hash)) &&
1171 compare_keys(KeySelect()(m_buckets[ibucket].value()), key))) {
1172 return const_iterator(m_buckets + ibucket);
1175 ibucket = next_bucket(ibucket);
1176 dist_from_ideal_bucket++;
1182 void erase_from_bucket(iterator pos) {
1183 pos.m_bucket->clear();
1193 std::size_t previous_ibucket =
1194 static_cast<std::size_t>(pos.m_bucket - m_buckets);
1195 std::size_t ibucket = next_bucket(previous_ibucket);
1197 while (m_buckets[ibucket].dist_from_ideal_bucket() > 0) {
1198 pxr_tsl_rh_assert(m_buckets[previous_ibucket].empty());
1200 const distance_type new_distance =
1201 distance_type(m_buckets[ibucket].dist_from_ideal_bucket() - 1);
1202 m_buckets[previous_ibucket].set_value_of_empty_bucket(
1203 new_distance, m_buckets[ibucket].truncated_hash(),
1204 std::move(m_buckets[ibucket].value()));
1205 m_buckets[ibucket].clear();
1207 previous_ibucket = ibucket;
1208 ibucket = next_bucket(ibucket);
1212 template <
class K,
class... Args>
1213 std::pair<iterator, bool> insert_impl(
const K& key,
1214 Args&&... value_type_args) {
1215 const std::size_t hash = hash_key(key);
1217 std::size_t ibucket = bucket_for_hash(hash);
1218 distance_type dist_from_ideal_bucket = 0;
1220 while (dist_from_ideal_bucket <=
1221 m_buckets[ibucket].dist_from_ideal_bucket()) {
1222 if ((!USE_STORED_HASH_ON_LOOKUP ||
1223 m_buckets[ibucket].bucket_hash_equal(hash)) &&
1224 compare_keys(KeySelect()(m_buckets[ibucket].value()), key)) {
1225 return std::make_pair(iterator(m_buckets + ibucket),
false);
1228 ibucket = next_bucket(ibucket);
1229 dist_from_ideal_bucket++;
1232 if (rehash_on_extreme_load()) {
1233 ibucket = bucket_for_hash(hash);
1234 dist_from_ideal_bucket = 0;
1236 while (dist_from_ideal_bucket <=
1237 m_buckets[ibucket].dist_from_ideal_bucket()) {
1238 ibucket = next_bucket(ibucket);
1239 dist_from_ideal_bucket++;
1243 if (m_buckets[ibucket].empty()) {
1244 m_buckets[ibucket].set_value_of_empty_bucket(
1245 dist_from_ideal_bucket, bucket_entry::truncate_hash(hash),
1246 std::forward<Args>(value_type_args)...);
1248 insert_value(ibucket, dist_from_ideal_bucket,
1249 bucket_entry::truncate_hash(hash),
1250 std::forward<Args>(value_type_args)...);
1258 return std::make_pair(iterator(m_buckets + ibucket),
true);
1261 template <
class... Args>
1262 void insert_value(std::size_t ibucket, distance_type dist_from_ideal_bucket,
1263 truncated_hash_type hash, Args&&... value_type_args) {
1264 value_type value(std::forward<Args>(value_type_args)...);
1265 insert_value_impl(ibucket, dist_from_ideal_bucket, hash, value);
1268 void insert_value(std::size_t ibucket, distance_type dist_from_ideal_bucket,
1269 truncated_hash_type hash, value_type&& value) {
1270 insert_value_impl(ibucket, dist_from_ideal_bucket, hash, value);
1281 void insert_value_impl(std::size_t ibucket,
1282 distance_type dist_from_ideal_bucket,
1283 truncated_hash_type hash, value_type& value) {
1284 m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket, hash,
1286 ibucket = next_bucket(ibucket);
1287 dist_from_ideal_bucket++;
1289 while (!m_buckets[ibucket].empty()) {
1290 if (dist_from_ideal_bucket >
1291 m_buckets[ibucket].dist_from_ideal_bucket()) {
1292 if (dist_from_ideal_bucket >=
1293 bucket_entry::DIST_FROM_IDEAL_BUCKET_LIMIT) {
1298 m_grow_on_next_insert =
true;
1301 m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket,
1305 ibucket = next_bucket(ibucket);
1306 dist_from_ideal_bucket++;
1309 m_buckets[ibucket].set_value_of_empty_bucket(dist_from_ideal_bucket, hash,
1313 void rehash_impl(size_type count_) {
1314 robin_hash new_table(count_, static_cast<Hash&>(*
this),
1315 static_cast<KeyEqual&>(*
this), get_allocator(),
1316 m_min_load_factor, m_max_load_factor);
1318 const bool use_stored_hash =
1319 USE_STORED_HASH_ON_REHASH(new_table.bucket_count());
1320 for (
auto& bucket : m_buckets_data) {
1321 if (bucket.empty()) {
1325 const std::size_t hash =
1326 use_stored_hash ? bucket.truncated_hash()
1327 : new_table.hash_key(KeySelect()(bucket.value()));
1329 new_table.insert_value_on_rehash(new_table.bucket_for_hash(hash), 0,
1330 bucket_entry::truncate_hash(hash),
1331 std::move(bucket.value()));
1334 new_table.m_nb_elements = m_nb_elements;
1335 new_table.swap(*
this);
1338 void clear_and_shrink() noexcept {
1339 GrowthPolicy::clear();
1340 m_buckets_data.clear();
1341 m_buckets = static_empty_bucket_ptr();
1344 m_load_threshold = 0;
1345 m_grow_on_next_insert =
false;
1346 m_try_shrink_on_next_insert =
false;
1349 void insert_value_on_rehash(std::size_t ibucket,
1350 distance_type dist_from_ideal_bucket,
1351 truncated_hash_type hash, value_type&& value) {
1353 if (dist_from_ideal_bucket >
1354 m_buckets[ibucket].dist_from_ideal_bucket()) {
1355 if (m_buckets[ibucket].empty()) {
1356 m_buckets[ibucket].set_value_of_empty_bucket(dist_from_ideal_bucket,
1357 hash, std::move(value));
1360 m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket,
1365 dist_from_ideal_bucket++;
1366 ibucket = next_bucket(ibucket);
1377 bool rehash_on_extreme_load() {
1378 if (m_grow_on_next_insert || size() >= m_load_threshold) {
1379 rehash_impl(GrowthPolicy::next_bucket_count());
1380 m_grow_on_next_insert =
false;
1385 if (m_try_shrink_on_next_insert) {
1386 m_try_shrink_on_next_insert =
false;
1387 if (m_min_load_factor != 0.0f && load_factor() < m_min_load_factor) {
1388 reserve(size() + 1);
1397 template <
class Serializer>
1398 void serialize_impl(Serializer& serializer)
const {
1399 const slz_size_type version = SERIALIZATION_PROTOCOL_VERSION;
1400 serializer(version);
1405 const std::int16_t hash_stored_for_bucket =
1406 static_cast<std::int16_t>(STORE_HASH);
1407 serializer(hash_stored_for_bucket);
1409 const slz_size_type nb_elements = m_nb_elements;
1410 serializer(nb_elements);
1412 const slz_size_type bucket_count = m_buckets_data.size();
1413 serializer(bucket_count);
1415 const float min_load_factor = m_min_load_factor;
1416 serializer(min_load_factor);
1418 const float max_load_factor = m_max_load_factor;
1419 serializer(max_load_factor);
1421 for (
const bucket_entry& bucket : m_buckets_data) {
1422 if (bucket.empty()) {
1423 const std::int16_t empty_bucket =
1424 bucket_entry::EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET;
1425 serializer(empty_bucket);
1427 const std::int16_t dist_from_ideal_bucket =
1428 bucket.dist_from_ideal_bucket();
1429 serializer(dist_from_ideal_bucket);
1431 const std::uint32_t truncated_hash = bucket.truncated_hash();
1432 serializer(truncated_hash);
1434 serializer(bucket.value());
1439 template <
class Deserializer>
1440 void deserialize_impl(Deserializer& deserializer,
bool hash_compatible) {
1441 pxr_tsl_rh_assert(m_buckets_data.empty());
1443 const slz_size_type version =
1444 deserialize_value<slz_size_type>(deserializer);
1447 if (version != SERIALIZATION_PROTOCOL_VERSION) {
1448 PXR_TSL_RH_THROW_OR_TERMINATE(std::runtime_error,
1449 "Can't deserialize the ordered_map/set. " 1450 "The protocol version header is invalid.");
1453 const bool hash_stored_for_bucket =
1454 deserialize_value<std::int16_t>(deserializer) ? true :
false;
1455 if (hash_compatible && STORE_HASH != hash_stored_for_bucket) {
1456 PXR_TSL_RH_THROW_OR_TERMINATE(
1458 "Can't deserialize a map with a different StoreHash " 1459 "than the one used during the serialization when " 1460 "hash compatibility is used");
1463 const slz_size_type nb_elements =
1464 deserialize_value<slz_size_type>(deserializer);
1465 const slz_size_type bucket_count_ds =
1466 deserialize_value<slz_size_type>(deserializer);
1467 const float min_load_factor = deserialize_value<float>(deserializer);
1468 const float max_load_factor = deserialize_value<float>(deserializer);
1470 if (min_load_factor < MINIMUM_MIN_LOAD_FACTOR ||
1471 min_load_factor > MAXIMUM_MIN_LOAD_FACTOR) {
1472 PXR_TSL_RH_THROW_OR_TERMINATE(
1474 "Invalid min_load_factor. Check that the serializer " 1475 "and deserializer support floats correctly as they " 1476 "can be converted implicitly to ints.");
1479 if (max_load_factor < MINIMUM_MAX_LOAD_FACTOR ||
1480 max_load_factor > MAXIMUM_MAX_LOAD_FACTOR) {
1481 PXR_TSL_RH_THROW_OR_TERMINATE(
1483 "Invalid max_load_factor. Check that the serializer " 1484 "and deserializer support floats correctly as they " 1485 "can be converted implicitly to ints.");
1488 this->min_load_factor(min_load_factor);
1489 this->max_load_factor(max_load_factor);
1491 if (bucket_count_ds == 0) {
1492 pxr_tsl_rh_assert(nb_elements == 0);
1496 if (!hash_compatible) {
1497 reserve(numeric_cast<size_type>(nb_elements,
1498 "Deserialized nb_elements is too big."));
1499 for (slz_size_type ibucket = 0; ibucket < bucket_count_ds; ibucket++) {
1500 const distance_type dist_from_ideal_bucket =
1501 deserialize_value<std::int16_t>(deserializer);
1502 if (dist_from_ideal_bucket !=
1503 bucket_entry::EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET) {
1504 if (hash_stored_for_bucket) {
1505 PXR_TSL_RH_UNUSED(deserialize_value<std::uint32_t>(deserializer));
1508 insert(deserialize_value<value_type>(deserializer));
1512 pxr_tsl_rh_assert(nb_elements == size());
1514 m_bucket_count = numeric_cast<size_type>(
1515 bucket_count_ds,
"Deserialized bucket_count is too big.");
1517 GrowthPolicy::operator=(GrowthPolicy(m_bucket_count));
1520 if (m_bucket_count != bucket_count_ds) {
1521 PXR_TSL_RH_THROW_OR_TERMINATE(std::runtime_error,
1522 "The GrowthPolicy is not the same even " 1523 "though hash_compatible is true.");
1526 m_nb_elements = numeric_cast<size_type>(
1527 nb_elements,
"Deserialized nb_elements is too big.");
1528 m_buckets_data.resize(m_bucket_count);
1529 m_buckets = m_buckets_data.data();
1531 for (bucket_entry& bucket : m_buckets_data) {
1532 const distance_type dist_from_ideal_bucket =
1533 deserialize_value<std::int16_t>(deserializer);
1534 if (dist_from_ideal_bucket !=
1535 bucket_entry::EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET) {
1536 truncated_hash_type truncated_hash = 0;
1537 if (hash_stored_for_bucket) {
1538 pxr_tsl_rh_assert(hash_stored_for_bucket);
1539 truncated_hash = deserialize_value<std::uint32_t>(deserializer);
1542 bucket.set_value_of_empty_bucket(
1543 dist_from_ideal_bucket, truncated_hash,
1544 deserialize_value<value_type>(deserializer));
1548 if (!m_buckets_data.empty()) {
1549 m_buckets_data.back().set_as_last_bucket();
1555 static const size_type DEFAULT_INIT_BUCKETS_SIZE = 0;
1557 static constexpr
float DEFAULT_MAX_LOAD_FACTOR = 0.5f;
1558 static constexpr
float MINIMUM_MAX_LOAD_FACTOR = 0.2f;
1559 static constexpr
float MAXIMUM_MAX_LOAD_FACTOR = 0.95f;
1561 static constexpr
float DEFAULT_MIN_LOAD_FACTOR = 0.0f;
1562 static constexpr
float MINIMUM_MIN_LOAD_FACTOR = 0.0f;
1563 static constexpr
float MAXIMUM_MIN_LOAD_FACTOR = 0.15f;
1565 static_assert(MINIMUM_MAX_LOAD_FACTOR < MAXIMUM_MAX_LOAD_FACTOR,
1566 "MINIMUM_MAX_LOAD_FACTOR should be < MAXIMUM_MAX_LOAD_FACTOR");
1567 static_assert(MINIMUM_MIN_LOAD_FACTOR < MAXIMUM_MIN_LOAD_FACTOR,
1568 "MINIMUM_MIN_LOAD_FACTOR should be < MAXIMUM_MIN_LOAD_FACTOR");
1569 static_assert(MAXIMUM_MIN_LOAD_FACTOR < MINIMUM_MAX_LOAD_FACTOR,
1570 "MAXIMUM_MIN_LOAD_FACTOR should be < MINIMUM_MAX_LOAD_FACTOR");
1576 static const slz_size_type SERIALIZATION_PROTOCOL_VERSION = 1;
1582 bucket_entry* static_empty_bucket_ptr() noexcept {
1583 static bucket_entry empty_bucket(
true);
1584 return &empty_bucket;
1588 buckets_container_type m_buckets_data;
1599 bucket_entry* m_buckets;
1605 size_type m_bucket_count;
1607 size_type m_nb_elements;
1609 size_type m_load_threshold;
1611 float m_min_load_factor;
1612 float m_max_load_factor;
1614 bool m_grow_on_next_insert;
1623 bool m_try_shrink_on_next_insert;
1630 PXR_NAMESPACE_CLOSE_SCOPE
Internal common class used by robin_map and robin_set.
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...
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>.
Helper class that stores a truncated hash if StoreHash is true and nothing otherwise.
void swap(UsdStageLoadRules &l, UsdStageLoadRules &r)
Swap the contents of rules l and r.
The 'operator*()' and 'operator->()' methods return a const reference and const pointer respectively ...
VT_API bool operator==(VtDictionary const &, VtDictionary const &)
Equality comparison.
iterator erase(iterator pos)
Here to avoid template<class K> size_type erase(const K& key) being used when we use an iterator inst...