24 #ifndef PXR_TSL_ROBIN_HASH_H
25 #define PXR_TSL_ROBIN_HASH_H
39 #include <type_traits>
52 namespace detail_robin_hash {
59 template <
typename T,
typename =
void>
70 template <std::
size_t GrowthFactor>
76 const T&
clamp(
const T&
v,
const T& lo,
const T& hi) {
80 template <
typename T,
typename U>
81 static T numeric_cast(U
value,
82 const char* error_message =
"numeric_cast() failed.") {
84 if (static_cast<U>(ret) !=
value) {
88 const bool is_same_signedness =
91 if (!is_same_signedness && (ret < T{}) != (value < U{})) {
100 template <
class T,
class Deserializer>
101 static T deserialize_value(Deserializer& deserializer) {
104 #if defined(_MSC_VER) && _MSC_VER < 1910
105 return deserializer.Deserializer::operator()<
T>();
107 return deserializer.Deserializer::template operator()<
T>();
119 "slz_size_type must be >= std::size_t");
127 template <
bool StoreHash>
174 template <
typename ValueType,
bool StoreHash>
185 m_last_bucket(false) {
200 m_last_bucket(other.m_last_bucket) {
201 if (!other.empty()) {
202 ::new (static_cast<void*>(std::addressof(m_value)))
204 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
215 std::is_nothrow_move_constructible<
value_type>::value)
218 m_last_bucket(other.m_last_bucket) {
219 if (!other.empty()) {
220 ::new (static_cast<void*>(std::addressof(m_value)))
222 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
229 if (
this != &other) {
233 if (!other.empty()) {
234 ::new (static_cast<void*>(std::addressof(m_value)))
238 m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
239 m_last_bucket = other.m_last_bucket;
262 #if defined(__cplusplus) && __cplusplus >= 201703L
263 return *std::launder(
264 reinterpret_cast<value_type*>(std::addressof(m_value)));
266 return *
reinterpret_cast<value_type*
>(std::addressof(m_value));
272 #if defined(__cplusplus) && __cplusplus >= 201703L
273 return *std::launder(
274 reinterpret_cast<const value_type*>(std::addressof(m_value)));
276 return *
reinterpret_cast<const value_type*
>(std::addressof(m_value));
281 return m_dist_from_ideal_bucket;
288 template <
typename... Args>
291 Args&&... value_type_args) {
295 ::new (static_cast<void*>(std::addressof(m_value)))
296 value_type(std::forward<Args>(value_type_args)...);
310 swap(dist_from_ideal_bucket, m_dist_from_ideal_bucket);
327 void destroy_value() noexcept {
329 value().~value_type();
337 "DIST_FROM_IDEAL_BUCKET_LIMIT must be <= "
338 "std::numeric_limits<distance_type>::max() - 1.");
365 template <
class ValueType,
class KeySelect,
class ValueSelect,
class Hash,
366 class KeyEqual,
class Allocator,
bool StoreHash,
class GrowthPolicy>
369 template <
typename U>
370 using has_mapped_type =
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.");
380 template <
bool IsConst>
403 static constexpr
bool STORE_HASH =
411 !std::is_same<Hash, std::hash<key_type>>
::value));
418 static constexpr
bool USE_STORED_HASH_ON_LOOKUP = StoreHash;
431 return bucket_count == 0 ||
432 (bucket_count - 1) <=
444 using buckets_allocator =
typename std::allocator_traits<
446 using buckets_container_type = std::vector<bucket_entry, buckets_allocator>;
460 template <
bool IsConst>
461 class robin_iterator {
465 using bucket_entry_ptr =
469 robin_iterator(bucket_entry_ptr bucket) noexcept : m_bucket(bucket) {}
481 template <
bool TIsConst = IsConst,
484 : m_bucket(other.m_bucket) {}
492 return KeySelect()(m_bucket->value());
495 template <
class U = ValueSelect,
497 IsConst>
::type* =
nullptr>
499 return U()(m_bucket->value());
502 template <
class U = ValueSelect,
504 !IsConst>
::type* =
nullptr>
506 return U()(m_bucket->value());
515 if (m_bucket->last_bucket()) {
521 if (!m_bucket->empty()) {
536 return lhs.m_bucket == rhs.m_bucket;
541 return !(lhs == rhs);
545 bucket_entry_ptr m_bucket;
549 #if defined(__cplusplus) && __cplusplus >= 201402L
551 const Allocator& alloc,
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),
562 m_grow_on_next_insert(false),
563 m_try_shrink_on_next_insert(false) {
566 "The map exceeds its maximum bucket count.");
569 if (m_bucket_count > 0) {
571 m_buckets_data.back().set_as_last_bucket();
589 const Allocator& alloc,
594 GrowthPolicy(bucket_count),
595 m_buckets_data(alloc),
596 m_buckets(static_empty_bucket_ptr()),
597 m_bucket_count(bucket_count),
599 m_grow_on_next_insert(false),
600 m_try_shrink_on_next_insert(false) {
603 "The map exceeds its maximum bucket count.");
606 if (m_bucket_count > 0) {
607 m_buckets_data.resize(m_bucket_count);
608 m_buckets = m_buckets_data.data();
611 m_buckets_data.back().set_as_last_bucket();
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) {}
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();
656 if (&other !=
this) {
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;
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;
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;
680 other.clear_and_shrink();
686 return m_buckets_data.get_allocator();
694 while (i < m_bucket_count && m_buckets[i].
empty()) {
705 while (i < m_bucket_count && m_buckets[i].
empty()) {
723 bool empty() const noexcept {
return m_nb_elements == 0; }
733 if (m_min_load_factor > 0.0
f) {
736 for (
auto& bucket : m_buckets_data) {
741 m_grow_on_next_insert =
false;
745 template <
typename P>
747 return insert_impl(KeySelect()(value), std::forward<P>(value));
750 template <
typename P>
752 if (hint !=
cend() &&
753 compare_keys(KeySelect()(*hint), KeySelect()(value))) {
757 return insert(std::forward<P>(value)).first;
760 template <
class InputIt>
763 std::forward_iterator_tag,
764 typename std::iterator_traits<InputIt>::iterator_category>::value) {
769 if (nb_elements_insert > 0 &&
770 nb_free_buckets <
size_type(nb_elements_insert)) {
780 template <
class K,
class M>
782 auto it =
try_emplace(std::forward<K>(key), std::forward<M>(obj));
784 it.first.value() = std::forward<M>(obj);
790 template <
class K,
class M>
792 if (hint !=
cend() && compare_keys(KeySelect()(*hint), key)) {
794 it.value() = std::forward<M>(obj);
802 template <
class... Args>
807 template <
class... Args>
812 template <
class K,
class... 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)...));
819 template <
class K,
class... Args>
821 if (hint !=
cend() && compare_keys(KeySelect()(*hint), key)) {
825 return try_emplace(std::forward<K>(key), std::forward<Args>(
args)...).first;
829 erase_from_bucket(pos);
837 erase_from_bucket(pos);
844 if (pos.m_bucket->empty()) {
860 for (
auto it = first_mutable.m_bucket; it != last_mutable.m_bucket; ++it) {
867 if (last_mutable ==
end()) {
868 m_try_shrink_on_next_insert =
true;
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);
882 const std::size_t ireturn_bucket =
883 ito_move_closer_value -
885 ito_move_closer_value - icloser_bucket,
887 m_buckets[ito_move_closer_value].dist_from_ideal_bucket()));
889 while (ito_move_closer_value < m_bucket_count &&
890 m_buckets[ito_move_closer_value].dist_from_ideal_bucket() > 0) {
892 ito_move_closer_value -
894 ito_move_closer_value - icloser_bucket,
896 m_buckets[ito_move_closer_value].dist_from_ideal_bucket()));
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));
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();
908 ++ito_move_closer_value;
911 m_try_shrink_on_next_insert =
true;
913 return iterator(m_buckets + ireturn_bucket);
918 return erase(key, hash_key(key));
923 auto it =
find(key, hash);
925 erase_from_bucket(it);
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);
952 template <
class K,
class U = ValueSelect,
955 return at(key, hash_key(key));
958 template <
class K,
class U = ValueSelect,
965 template <
class K,
class U = ValueSelect,
968 return at(key, hash_key(key));
971 template <
class K,
class U = ValueSelect,
974 auto it =
find(key, hash);
982 template <
class K,
class U = ValueSelect,
985 return try_emplace(std::forward<K>(key)).first.value();
990 return count(key, hash_key(key));
1004 return find_impl(key, hash_key(key));
1009 return find_impl(key, hash);
1014 return find_impl(key, hash_key(key));
1019 return find_impl(key, hash);
1024 return contains(key, hash_key(key));
1029 return count(key, hash) != 0;
1038 std::pair<iterator, iterator>
equal_range(
const K& key, std::size_t hash) {
1040 return std::make_pair(it, (it ==
end()) ? it : std::next(it));
1044 std::pair<const_iterator, const_iterator>
equal_range(
const K& key)
const {
1050 const K& key, std::size_t hash)
const {
1052 return std::make_pair(it, (it ==
cend()) ? it : std::next(it));
1061 return std::min(GrowthPolicy::max_bucket_count(),
1062 m_buckets_data.max_size());
1095 rehash_impl(count_);
1113 return iterator(const_cast<bucket_entry*>(pos.m_bucket));
1116 template <
class Serializer>
1118 serialize_impl(serializer);
1121 template <
class Deserializer>
1123 deserialize_impl(deserializer, hash_compatible);
1128 std::size_t hash_key(
const K& key)
const {
1129 return Hash::operator()(key);
1132 template <
class K1,
class K2>
1133 bool compare_keys(
const K1& key1,
const K2& key2)
const {
1134 return KeyEqual::operator()(key1, key2);
1137 std::size_t bucket_for_hash(std::size_t hash)
const {
1138 const std::size_t bucket = GrowthPolicy::bucket_for_hash(hash);
1140 (bucket == 0 && m_bucket_count == 0));
1145 template <
class U = GrowthPolicy,
1148 std::size_t next_bucket(std::size_t
index)
const noexcept {
1151 return (
index + 1) & this->m_mask;
1154 template <
class U = GrowthPolicy,
1157 std::size_t next_bucket(std::size_t
index)
const noexcept {
1165 iterator find_impl(
const K& key, std::size_t hash) {
1167 static_cast<const robin_hash*>(
this)->
find(key, hash));
1172 std::size_t ibucket = bucket_for_hash(hash);
1173 distance_type dist_from_ideal_bucket = 0;
1175 while (dist_from_ideal_bucket <=
1176 m_buckets[ibucket].dist_from_ideal_bucket()) {
1178 (!USE_STORED_HASH_ON_LOOKUP ||
1179 m_buckets[ibucket].bucket_hash_equal(hash)) &&
1180 compare_keys(KeySelect()(m_buckets[ibucket].
value()), key))) {
1184 ibucket = next_bucket(ibucket);
1185 dist_from_ideal_bucket++;
1191 void erase_from_bucket(
iterator pos) {
1192 pos.m_bucket->clear();
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);
1206 while (m_buckets[ibucket].dist_from_ideal_bucket() > 0) {
1209 const distance_type new_distance =
1210 distance_type(m_buckets[ibucket].dist_from_ideal_bucket() - 1);
1212 new_distance, m_buckets[ibucket].truncated_hash(),
1213 std::move(m_buckets[ibucket].
value()));
1214 m_buckets[ibucket].
clear();
1216 previous_ibucket = ibucket;
1217 ibucket = next_bucket(ibucket);
1219 m_try_shrink_on_next_insert =
true;
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);
1227 std::size_t ibucket = bucket_for_hash(hash);
1228 distance_type dist_from_ideal_bucket = 0;
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);
1238 ibucket = next_bucket(ibucket);
1239 dist_from_ideal_bucket++;
1242 while (rehash_on_extreme_load(dist_from_ideal_bucket)) {
1243 ibucket = bucket_for_hash(hash);
1244 dist_from_ideal_bucket = 0;
1246 while (dist_from_ideal_bucket <=
1247 m_buckets[ibucket].dist_from_ideal_bucket()) {
1248 ibucket = next_bucket(ibucket);
1249 dist_from_ideal_bucket++;
1253 if (m_buckets[ibucket].
empty()) {
1256 std::forward<Args>(value_type_args)...);
1258 insert_value(ibucket, dist_from_ideal_bucket,
1260 std::forward<Args>(value_type_args)...);
1268 return std::make_pair(
iterator(m_buckets + ibucket),
true);
1271 template <
class... Args>
1272 void insert_value(std::size_t ibucket, distance_type dist_from_ideal_bucket,
1275 insert_value_impl(ibucket, dist_from_ideal_bucket, hash, value);
1278 void insert_value(std::size_t ibucket, distance_type dist_from_ideal_bucket,
1280 insert_value_impl(ibucket, dist_from_ideal_bucket, hash, value);
1291 void insert_value_impl(std::size_t ibucket,
1292 distance_type dist_from_ideal_bucket,
1295 m_buckets[ibucket].dist_from_ideal_bucket());
1298 ibucket = next_bucket(ibucket);
1299 dist_from_ideal_bucket++;
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 >
1310 m_grow_on_next_insert =
true;
1317 ibucket = next_bucket(ibucket);
1318 dist_from_ideal_bucket++;
1326 robin_hash new_table(count_, static_cast<Hash&>(*
this),
1328 m_min_load_factor, m_max_load_factor);
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()) {
1338 const std::size_t hash =
1339 use_stored_hash ? bucket.truncated_hash()
1340 : new_table.hash_key(KeySelect()(bucket.value()));
1342 new_table.insert_value_on_rehash(new_table.bucket_for_hash(hash), 0,
1344 std::move(bucket.value()));
1347 new_table.m_nb_elements = m_nb_elements;
1348 new_table.swap(*
this);
1351 void clear_and_shrink() noexcept {
1352 GrowthPolicy::clear();
1353 m_buckets_data.clear();
1354 m_buckets = static_empty_bucket_ptr();
1357 m_load_threshold = 0;
1358 m_grow_on_next_insert =
false;
1359 m_try_shrink_on_next_insert =
false;
1362 void insert_value_on_rehash(std::size_t ibucket,
1363 distance_type dist_from_ideal_bucket,
1366 if (dist_from_ideal_bucket >
1367 m_buckets[ibucket].dist_from_ideal_bucket()) {
1368 if (m_buckets[ibucket].
empty()) {
1370 hash, std::move(value));
1378 dist_from_ideal_bucket++;
1379 ibucket = next_bucket(ibucket);
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 >
1394 size() >= m_load_threshold) {
1395 rehash_impl(GrowthPolicy::next_bucket_count());
1396 m_grow_on_next_insert =
false;
1401 if (m_try_shrink_on_next_insert) {
1402 m_try_shrink_on_next_insert =
false;
1403 if (m_min_load_factor != 0.0
f &&
load_factor() < m_min_load_factor) {
1413 template <
class Serializer>
1414 void serialize_impl(Serializer& serializer)
const {
1416 serializer(version);
1421 const std::int16_t hash_stored_for_bucket =
1422 static_cast<std::int16_t
>(STORE_HASH);
1423 serializer(hash_stored_for_bucket);
1426 serializer(nb_elements);
1429 serializer(bucket_count);
1432 serializer(min_load_factor);
1435 serializer(max_load_factor);
1437 for (
const bucket_entry& bucket : m_buckets_data) {
1438 if (bucket.empty()) {
1439 const std::int16_t empty_bucket =
1441 serializer(empty_bucket);
1443 const std::int16_t dist_from_ideal_bucket =
1444 bucket.dist_from_ideal_bucket();
1445 serializer(dist_from_ideal_bucket);
1447 const std::uint32_t truncated_hash = bucket.truncated_hash();
1448 serializer(truncated_hash);
1450 serializer(bucket.value());
1455 template <
class Deserializer>
1456 void deserialize_impl(Deserializer& deserializer,
bool hash_compatible) {
1460 deserialize_value<slz_size_type>(deserializer);
1463 if (version != SERIALIZATION_PROTOCOL_VERSION) {
1465 "Can't deserialize the ordered_map/set. "
1466 "The protocol version header is invalid.");
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) {
1474 "Can't deserialize a map with a different StoreHash "
1475 "than the one used during the serialization when "
1476 "hash compatibility is used");
1480 deserialize_value<slz_size_type>(deserializer);
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);
1490 "Invalid min_load_factor. Check that the serializer "
1491 "and deserializer support floats correctly as they "
1492 "can be converted implicitly to ints.");
1499 "Invalid max_load_factor. Check that the serializer "
1500 "and deserializer support floats correctly as they "
1501 "can be converted implicitly to ints.");
1507 if (bucket_count_ds == 0) {
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 !=
1520 if (hash_stored_for_bucket) {
1524 insert(deserialize_value<value_type>(deserializer));
1530 m_bucket_count = numeric_cast<
size_type>(
1531 bucket_count_ds,
"Deserialized bucket_count is too big.");
1536 if (m_bucket_count != bucket_count_ds) {
1538 "The GrowthPolicy is not the same even "
1539 "though hash_compatible is true.");
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();
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 !=
1553 if (hash_stored_for_bucket) {
1555 truncated_hash = deserialize_value<std::uint32_t>(deserializer);
1558 bucket.set_value_of_empty_bucket(
1559 dist_from_ideal_bucket, truncated_hash,
1560 deserialize_value<value_type>(deserializer));
1564 if (!m_buckets_data.empty()) {
1565 m_buckets_data.back().set_as_last_bucket();
1582 "MINIMUM_MAX_LOAD_FACTOR should be < MAXIMUM_MAX_LOAD_FACTOR");
1584 "MINIMUM_MIN_LOAD_FACTOR should be < MAXIMUM_MIN_LOAD_FACTOR");
1586 "MAXIMUM_MIN_LOAD_FACTOR should be < MINIMUM_MAX_LOAD_FACTOR");
1592 static const slz_size_type SERIALIZATION_PROTOCOL_VERSION = 1;
1601 return &empty_bucket;
1605 buckets_container_type m_buckets_data;
1628 float m_min_load_factor;
1629 float m_max_load_factor;
1631 bool m_grow_on_next_insert;
1640 bool m_try_shrink_on_next_insert;
void set_hash(truncated_hash_type) noexcept
iterator insert_or_assign(const_iterator hint, K &&key, M &&obj)
static const distance_type EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET
static truncated_hash_type truncate_hash(std::size_t hash) noexcept
iterator emplace_hint(const_iterator hint, Args &&...args)
float load_factor() const
typename KeySelect::key_type key_type
size_type max_bucket_count() const
robin_iterator & operator=(const robin_iterator &other)=default
iterator try_emplace_hint(const_iterator hint, K &&key, Args &&...args)
bucket_entry(bool last_bucket) noexcept
std::forward_iterator_tag iterator_category
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)
bool last_bucket() const noexcept
void deserialize(Deserializer &deserializer, bool hash_compatible)
U::value_type & value() const
distance_type dist_from_ideal_bucket() const noexcept
std::int16_t distance_type
size_type count(const K &key, std::size_t hash) const
STATIC_INLINE size_t Hash(const char *s, size_t len)
std::pair< iterator, bool > insert_or_assign(K &&key, M &&obj)
#define PXR_TSL_RH_UNUSED(x)
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
bool bucket_hash_equal(std::size_t hash) const noexcept
truncated_hash_type truncated_hash() const noexcept
friend bool operator==(const robin_iterator &lhs, const robin_iterator &rhs)
value_type & value() noexcept
GLsizei const GLfloat * value
robin_iterator & operator++()
const U::value_type & value() const
robin_iterator(const robin_iterator<!TIsConst > &other) noexcept
robin_hash & operator=(const robin_hash &other)
reference operator*() const
void swap(robin_hash &other)
void swap(T &lhs, T &rhs)
void serialize(Serializer &serializer) const
U::value_type & operator[](K &&key)
static constexpr float MINIMUM_MAX_LOAD_FACTOR
IMATH_HOSTDEVICE constexpr bool equal(T1 a, T2 b, T3 t) IMATH_NOEXCEPT
ImageBuf OIIO_API min(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
std::pair< iterator, iterator > equal_range(const K &key)
bool contains(const K &key) const
void rehash(size_type count_)
robin_iterator() noexcept
const robin_hash::key_type & key() const
const T & clamp(const T &v, const T &lo, const T &hi)
std::pair< iterator, bool > emplace(Args &&...args)
iterator insert_hint(const_iterator hint, P &&value)
float max_load_factor() const
size_type count(const K &key) const
#define pxr_tsl_rh_assert(expr)
const_iterator cend() const noexcept
bucket_entry(const bucket_entry &other) noexcept(std::is_nothrow_copy_constructible< value_type >::value)
size_type erase(const K &key, std::size_t hash)
std::ptrdiff_t difference_type
GLint GLint GLsizei GLint GLenum GLenum type
const value_type & value() const noexcept
bool contains(const K &key, std::size_t hash) const
const_iterator end() const noexcept
robin_iterator< true > const_iterator
std::uint64_t slz_size_type
std::pair< iterator, iterator > equal_range(const K &key, std::size_t hash)
void swap_with_value_in_bucket(distance_type &dist_from_ideal_bucket, truncated_hash_type &hash, value_type &value)
std::uint32_t truncated_hash_type
void min_load_factor(float ml)
robin_hash & operator=(robin_hash &&other)
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)
#define PXR_TSL_RH_LIKELY(exp)
std::ptrdiff_t difference_type
iterator find(const K &key, std::size_t hash)
const_iterator begin() const noexcept
robin_hash(const robin_hash &other)
bool empty() const noexcept
static const distance_type DIST_FROM_IDEAL_BUCKET_LIMIT
std::pair< iterator, bool > insert(P &&value)
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
robin_iterator operator++(int)
size_type max_size() const noexcept
std::pair< Key, T > value_type
std::pair< iterator, bool > try_emplace(K &&key, Args &&...args)
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t hash) const
bucket_entry(bucket_entry &&other) noexcept(std::is_nothrow_move_constructible< value_type >::value)
iterator erase(const_iterator pos)
static constexpr float MAXIMUM_MAX_LOAD_FACTOR
const value_type & const_reference
const_iterator cbegin() const noexcept
const value_type * const_pointer
#define PXR_TSL_RH_THROW_OR_TERMINATE(ex, msg)
const typename robin_hash::value_type value_type
const_iterator find(const K &key, std::size_t hash) const
GT_API const UT_StringHolder version
float min_load_factor() const
iterator begin() noexcept
__hostdev__ uint64_t last(uint32_t i) const
iterator mutable_iterator(const_iterator pos)
const U::value_type & at(const K &key, std::size_t hash) const
static constexpr float MINIMUM_MIN_LOAD_FACTOR
IMATH_HOSTDEVICE constexpr int ceil(T x) IMATH_NOEXCEPT
void set_hash(truncated_hash_type hash) noexcept
IMATH_NAMESPACE::V2f IMATH_NAMESPACE::Box2i std::string this attribute is obsolete as of OpenEXR v3 float
hasher hash_function() const
robin_iterator< false > iterator
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
bool empty() const noexcept
bool bucket_hash_equal(std::size_t) const noexcept
LeafData & operator=(const LeafData &)=delete
static constexpr float DEFAULT_MIN_LOAD_FACTOR
iterator erase(const_iterator first, const_iterator last)
const U::value_type & at(const K &key) const
static constexpr float MAXIMUM_MIN_LOAD_FACTOR
void set_value_of_empty_bucket(distance_type dist_from_ideal_bucket, truncated_hash_type hash, Args &&...value_type_args)
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
#define PXR_NAMESPACE_CLOSE_SCOPE
U::value_type & at(const K &key, std::size_t hash)
**If you just want to fire and args
size_type size() const noexcept
const_iterator find(const K &key) const
void set_as_last_bucket() noexcept
bucket_entry & operator=(const bucket_entry &other) noexcept(std::is_nothrow_copy_constructible< value_type >::value)
iterator find(const K &key)
static constexpr float DEFAULT_MAX_LOAD_FACTOR
U::value_type & at(const K &key)
truncated_hash_type truncated_hash() const noexcept
friend bool operator!=(const robin_iterator &lhs, const robin_iterator &rhs)
allocator_type get_allocator() const
SIM_API const UT_StringHolder distance
size_type erase(const K &key)
void insert(InputIt first, InputIt last)
static const size_type DEFAULT_INIT_BUCKETS_SIZE
pointer operator->() const
void max_load_factor(float ml)
iterator erase(iterator pos)
size_type bucket_count() const
void reserve(size_type count_)
void erase_fast(iterator pos)