HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
robin_hash.h
Go to the documentation of this file.
1 /**
2  * MIT License
3  *
4  * Copyright (c) 2017 Thibaut Goetghebuer-Planchon <tessil@gmx.com>
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a copy
7  * of this software and associated documentation files (the "Software"), to deal
8  * in the Software without restriction, including without limitation the rights
9  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10  * copies of the Software, and to permit persons to whom the Software is
11  * furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in
14  * all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  * SOFTWARE.
23  */
24 #ifndef 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 
49 
50 namespace pxr_tsl {
51 
52 namespace detail_robin_hash {
53 
54 template <typename T>
55 struct make_void {
56  using type = void;
57 };
58 
59 template <typename T, typename = void>
60 struct has_is_transparent : std::false_type {};
61 
62 template <typename T>
64  typename make_void<typename T::is_transparent>::type>
65  : std::true_type {};
66 
67 template <typename U>
68 struct is_power_of_two_policy : std::false_type {};
69 
70 template <std::size_t GrowthFactor>
72  : std::true_type {};
73 
74 // Only available in C++17, we need to be compatible with C++11
75 template <class T>
76 const T& clamp(const T& v, const T& lo, const T& hi) {
77  return std::min(hi, std::max(lo, v));
78 }
79 
80 template <typename T, typename U>
81 static 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 =
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 
100 template <class T, class Deserializer>
101 static 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 
111 /**
112  * Fixed size type used to represent size_type values on serialization. Need to
113  * be big enough to represent a std::size_t on 32 and 64 bits platforms, and
114  * must be the same size on both platforms.
115  */
116 using slz_size_type = std::uint64_t;
119  "slz_size_type must be >= std::size_t");
120 
121 using truncated_hash_type = std::uint32_t;
122 
123 /**
124  * Helper class that stores a truncated hash if StoreHash is true and nothing
125  * otherwise.
126  */
127 template <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 
138 template <>
139 class 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 
156 /**
157  * Each bucket entry has:
158  * - A value of type `ValueType`.
159  * - An integer to store how far the value of the bucket, if any, is from its
160  * ideal bucket (ex: if the current bucket 5 has the value 'foo' and
161  * `hash('foo') % nb_buckets` == 3, `dist_from_ideal_bucket()` will return 2 as
162  * the current value of the bucket is two buckets away from its ideal bucket) If
163  * there is no value in the bucket (i.e. `empty()` is true)
164  * `dist_from_ideal_bucket()` will be < 0.
165  * - A marker which tells us if the bucket is the last bucket of the bucket
166  * array (useful for the iterator of the hash table).
167  * - If `StoreHash` is true, 32 bits of the hash of the value, if any, are also
168  * stored in the bucket. If the size of the hash is more than 32 bits, it is
169  * truncated. We don't store the full hash as storing the hash is a potential
170  * opportunity to use the unused space due to the alignment of the bucket_entry
171  * structure. We can thus potentially store the hash without any extra space
172  * (which would not be possible with 64 bits of the hash).
173  */
174 template <typename ValueType, bool StoreHash>
175 class bucket_entry : public bucket_entry_hash<StoreHash> {
177 
178  public:
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) {
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) {
194  }
195 
196  bucket_entry(const bucket_entry& other) noexcept(
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 
209  /**
210  * Never really used, but still necessary as we must call resize on an empty
211  * `std::vector<bucket_entry>`. and we need to support move-only types. See
212  * robin_hash constructor for details.
213  */
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(
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 {
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 {
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 
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>
290  truncated_hash_type hash,
291  Args&&... value_type_args) {
292  pxr_tsl_rh_assert(dist_from_ideal_bucket >= 0);
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 
301  }
302 
304  truncated_hash_type& hash, value_type& value) {
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 {
329  value().~value_type();
330  }
331 
332  public:
335  static_assert(DIST_FROM_IDEAL_BUCKET_LIMIT <=
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 
346 /**
347  * Internal common class used by `robin_map` and `robin_set`.
348  *
349  * ValueType is what will be stored by `robin_hash` (usually `std::pair<Key, T>`
350  * for map and `Key` for set).
351  *
352  * `KeySelect` should be a `FunctionObject` which takes a `ValueType` in
353  * parameter and returns a reference to the key.
354  *
355  * `ValueSelect` should be a `FunctionObject` which takes a `ValueType` in
356  * parameter and returns a reference to the value. `ValueSelect` should be void
357  * if there is no value (in a set for example).
358  *
359  * The strong exception guarantee only holds if the expression
360  * `std::is_nothrow_swappable<ValueType>::value &&
361  * std::is_nothrow_move_constructible<ValueType>::value` is true.
362  *
363  * Behaviour is undefined if the destructor of `ValueType` throws.
364  */
365 template <class ValueType, class KeySelect, class ValueSelect, class Hash,
366  class KeyEqual, class Allocator, bool StoreHash, class GrowthPolicy>
367 class robin_hash : private Hash, private KeyEqual, private GrowthPolicy {
368  private:
369  template <typename U>
370  using has_mapped_type =
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>
382 
383  using key_type = typename KeySelect::key_type;
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;
391  using const_reference = const value_type&;
392  using pointer = value_type*;
393  using const_pointer = const value_type*;
394  using iterator = robin_iterator<false>;
395  using const_iterator = robin_iterator<true>;
396 
397  private:
398  /**
399  * Either store the hash because we are asked by the `StoreHash` template
400  * parameter or store the hash because it doesn't cost us anything in size and
401  * can be used to speed up rehash.
402  */
403  static constexpr bool STORE_HASH =
404  StoreHash ||
407  (sizeof(std::size_t) == sizeof(truncated_hash_type) ||
409  // Don't store the hash for primitive types with default hash.
411  !std::is_same<Hash, std::hash<key_type>>::value));
412 
413  /**
414  * Only use the stored hash on lookup if we are explicitly asked. We are not
415  * sure how slow the KeyEqual operation is. An extra comparison may slow
416  * things down with a fast KeyEqual.
417  */
418  static constexpr bool USE_STORED_HASH_ON_LOOKUP = StoreHash;
419 
420  /**
421  * We can only use the hash on rehash if the size of the hash type is the same
422  * as the stored one or if we use a power of two modulo. In the case of the
423  * power of two modulo, we just mask the least significant bytes, we just have
424  * to check that the truncated_hash_type didn't truncated more bytes.
425  */
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) <=
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:
449  /**
450  * The 'operator*()' and 'operator->()' methods return a const reference and
451  * const pointer respectively to the stored value type.
452  *
453  * In case of a map, to get a mutable reference to the value associated to a
454  * key (the '.second' in the stored pair), you have to call 'value()'.
455  *
456  * The main reason for this is that if we returned a `std::pair<Key, T>&`
457  * instead of a `const std::pair<Key, T>&`, the user may modify the key which
458  * will put the map in a undefined state.
459  */
460  template <bool IsConst>
461  class robin_iterator {
462  friend class robin_hash;
463 
464  private:
465  using bucket_entry_ptr =
466  typename std::conditional<IsConst, const bucket_entry*,
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;
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>
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,
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,
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 
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 
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,
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 
576  }
577 #else
578  /**
579  * C++11 doesn't support the creation of a std::vector with a custom allocator
580  * and 'count' default-inserted elements. The needed contructor `explicit
581  * vector(size_type count, const Allocator& alloc = Allocator());` is only
582  * available in C++14 and later. We thus must resize after using the
583  * `vector(const Allocator& alloc)` constructor.
584  *
585  * We can't use `vector(size_type count, const T& value, const Allocator&
586  * alloc)` as it requires the value T to be copyable.
587  */
588  robin_hash(size_type bucket_count, const Hash& hash, const KeyEqual& equal,
589  const Allocator& alloc,
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 
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);
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 
679  other.swap(*this);
680  other.clear_and_shrink();
681 
682  return *this;
683  }
684 
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>
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>
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 
832  /**
833  * Here to avoid `template<class K> size_type erase(const K& key)` being used
834  * when we use an `iterator` instead of a `const_iterator`.
835  */
837  erase_from_bucket(pos);
838 
839  /**
840  * Erase bucket used a backward shift after clearing the bucket.
841  * Check if there is a new value in the bucket, if not get the next
842  * non-empty.
843  */
844  if (pos.m_bucket->empty()) {
845  ++pos;
846  }
847 
848  return pos;
849  }
850 
852 
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,
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,
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,
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,
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,
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 
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  */
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,
1147  nullptr>
1148  std::size_t next_bucket(std::size_t index) const noexcept {
1150 
1151  return (index + 1) & this->m_mask;
1152  }
1153 
1154  template <class U = GrowthPolicy,
1156  nullptr>
1157  std::size_t next_bucket(std::size_t index) const noexcept {
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 
1195  /**
1196  * Backward shift, swap the empty bucket, previous_ibucket, with the values
1197  * on its right, ibucket, until we cross another empty bucket or if the
1198  * other bucket has a distance_from_ideal_bucket == 0.
1199  *
1200  * We try to move the values closer to their ideal bucket.
1201  */
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,
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 >
1306  /**
1307  * The number of probes is really high, rehash the map on the next
1308  * insert. Difficult to do now as rehash may throw an exception.
1309  */
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,
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 
1383  /**
1384  * Grow the table if m_grow_on_next_insert is true or we reached the
1385  * max_load_factor. Shrink the table if m_try_shrink_on_next_insert is true
1386  * (an erase occurred) and we're below the min_load_factor.
1387  *
1388  * Return true if the table has been rehashed.
1389  */
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;
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 =
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) {
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) {
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) {
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 !=
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 !=
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:
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 
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");
1587 
1588  private:
1589  /**
1590  * Protocol version currenlty used for serialization.
1591  */
1592  static const slz_size_type SERIALIZATION_PROTOCOL_VERSION = 1;
1593 
1594  /**
1595  * Return an always valid pointer to an static empty bucket_entry with
1596  * last_bucket() == true.
1597  */
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 
1607  /**
1608  * Points to m_buckets_data.data() if !m_buckets_data.empty() otherwise points
1609  * to static_empty_bucket_ptr. This variable is useful to avoid the cost of
1610  * checking if m_buckets_data is empty when trying to find an element.
1611  *
1612  * TODO Remove m_buckets_data and only use a pointer instead of a
1613  * pointer+vector to save some space in the robin_hash object. Manage the
1614  * Allocator manually.
1615  */
1616  bucket_entry* m_buckets;
1617 
1618  /**
1619  * Used a lot in find, avoid the call to m_buckets_data.size() which is a bit
1620  * slower.
1621  */
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 
1633  /**
1634  * We can't shrink down the map on erase operations as the erase methods need
1635  * to return the next iterator. Shrinking the map would invalidate all the
1636  * iterators and we could not return the next iterator in a meaningful way, On
1637  * erase, we thus just indicate on erase that we should try to shrink the hash
1638  * table on the next insert if we go below the min_load_factor.
1639  */
1640  bool m_try_shrink_on_next_insert;
1641 };
1642 
1643 } // namespace detail_robin_hash
1644 
1645 } // namespace pxr_tsl
1646 
1648 
1649 #endif
void set_hash(truncated_hash_type) noexcept
Definition: robin_hash.h:135
iterator insert_or_assign(const_iterator hint, K &&key, M &&obj)
Definition: robin_hash.h:791
static const distance_type EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET
Definition: robin_hash.h:333
type
Definition: core.h:556
static truncated_hash_type truncate_hash(std::size_t hash) noexcept
Definition: robin_hash.h:322
GLint first
Definition: glcorearb.h:405
iterator emplace_hint(const_iterator hint, Args &&...args)
Definition: robin_hash.h:808
robin_iterator & operator=(const robin_iterator &other)=default
iterator try_emplace_hint(const_iterator hint, K &&key, Args &&...args)
Definition: robin_hash.h:820
bucket_entry(bool last_bucket) noexcept
Definition: robin_hash.h:189
robin_hash(robin_hash &&other) noexcept(std::is_nothrow_move_constructible< Hash >::value &&std::is_nothrow_move_constructible< KeyEqual >::value &&std::is_nothrow_move_constructible< GrowthPolicy >::value &&std::is_nothrow_move_constructible< buckets_container_type >::value)
Definition: robin_hash.h:634
bool last_bucket() const noexcept
Definition: robin_hash.h:284
void deserialize(Deserializer &deserializer, bool hash_compatible)
Definition: robin_hash.h:1122
Definition: robin_hash.h:175
distance_type dist_from_ideal_bucket() const noexcept
Definition: robin_hash.h:280
std::int16_t distance_type
Definition: robin_hash.h:180
size_type count(const K &key, std::size_t hash) const
Definition: robin_hash.h:994
STATIC_INLINE size_t Hash(const char *s, size_t len)
Definition: farmhash.h:2099
std::pair< iterator, bool > insert_or_assign(K &&key, M &&obj)
Definition: robin_hash.h:781
void
Definition: png.h:1083
void clear() noexcept
Definition: robin_hash.h:249
#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)
Definition: UT_ArraySet.h:1699
bool bucket_hash_equal(std::size_t hash) const noexcept
Definition: robin_hash.h:141
truncated_hash_type truncated_hash() const noexcept
Definition: robin_hash.h:132
const GLdouble * v
Definition: glcorearb.h:837
friend bool operator==(const robin_iterator &lhs, const robin_iterator &rhs)
Definition: robin_hash.h:534
value_type & value() noexcept
Definition: robin_hash.h:260
GLsizei const GLfloat * value
Definition: glcorearb.h:824
robin_iterator(const robin_iterator<!TIsConst > &other) noexcept
Definition: robin_hash.h:483
robin_hash & operator=(const robin_hash &other)
Definition: robin_hash.h:655
void swap(robin_hash &other)
Definition: robin_hash.h:932
void swap(T &lhs, T &rhs)
Definition: pugixml.cpp:7440
void serialize(Serializer &serializer) const
Definition: robin_hash.h:1117
U::value_type & operator[](K &&key)
Definition: robin_hash.h:984
static constexpr float MINIMUM_MAX_LOAD_FACTOR
Definition: robin_hash.h:1574
IMATH_HOSTDEVICE constexpr bool equal(T1 a, T2 b, T3 t) IMATH_NOEXCEPT
Definition: ImathFun.h:105
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)
Definition: robin_hash.h:1033
bool contains(const K &key) const
Definition: robin_hash.h:1023
const robin_hash::key_type & key() const
Definition: robin_hash.h:491
const T & clamp(const T &v, const T &lo, const T &hi)
Definition: robin_hash.h:76
uint64 value_type
Definition: GA_PrimCompat.h:29
std::pair< iterator, bool > emplace(Args &&...args)
Definition: robin_hash.h:803
iterator insert_hint(const_iterator hint, P &&value)
Definition: robin_hash.h:751
size_type count(const K &key) const
Definition: robin_hash.h:989
#define pxr_tsl_rh_assert(expr)
const_iterator cend() const noexcept
Definition: robin_hash.h:716
bucket_entry(const bucket_entry &other) noexcept(std::is_nothrow_copy_constructible< value_type >::value)
Definition: robin_hash.h:196
size_type erase(const K &key, std::size_t hash)
Definition: robin_hash.h:922
GLfloat f
Definition: glcorearb.h:1926
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:108
const value_type & value() const noexcept
Definition: robin_hash.h:270
bool contains(const K &key, std::size_t hash) const
Definition: robin_hash.h:1028
const_iterator end() const noexcept
Definition: robin_hash.h:714
std::uint64_t slz_size_type
Definition: robin_hash.h:116
std::pair< iterator, iterator > equal_range(const K &key, std::size_t hash)
Definition: robin_hash.h:1038
void swap_with_value_in_bucket(distance_type &dist_from_ideal_bucket, truncated_hash_type &hash, value_type &value)
Definition: robin_hash.h:303
std::uint32_t truncated_hash_type
Definition: robin_hash.h:121
robin_hash & operator=(robin_hash &&other)
Definition: robin_hash.h:678
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)
Definition: robin_hash.h:588
#define PXR_TSL_RH_LIKELY(exp)
Definition: robin_hash.h:128
iterator find(const K &key, std::size_t hash)
Definition: robin_hash.h:1008
const_iterator begin() const noexcept
Definition: robin_hash.h:701
robin_hash(const robin_hash &other)
Definition: robin_hash.h:619
static const distance_type DIST_FROM_IDEAL_BUCKET_LIMIT
Definition: robin_hash.h:334
~bucket_entry() noexcept
Definition: robin_hash.h:247
std::pair< iterator, bool > insert(P &&value)
Definition: robin_hash.h:746
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: robin_hash.h:1044
size_type max_size() const noexcept
Definition: robin_hash.h:727
std::pair< iterator, bool > try_emplace(K &&key, Args &&...args)
Definition: robin_hash.h:813
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t hash) const
Definition: robin_hash.h:1049
bucket_entry(bucket_entry &&other) noexcept(std::is_nothrow_move_constructible< value_type >::value)
Definition: robin_hash.h:214
iterator erase(const_iterator pos)
Definition: robin_hash.h:851
static constexpr float MAXIMUM_MAX_LOAD_FACTOR
Definition: robin_hash.h:1575
const_iterator cbegin() const noexcept
Definition: robin_hash.h:703
#define PXR_TSL_RH_THROW_OR_TERMINATE(ex, msg)
ValueType value_type
Definition: robin_hash.h:179
const typename robin_hash::value_type value_type
Definition: robin_hash.h:473
const_iterator find(const K &key, std::size_t hash) const
Definition: robin_hash.h:1018
GT_API const UT_StringHolder version
__hostdev__ uint64_t last(uint32_t i) const
Definition: NanoVDB.h:5976
iterator mutable_iterator(const_iterator pos)
Definition: robin_hash.h:1112
const U::value_type & at(const K &key, std::size_t hash) const
Definition: robin_hash.h:973
static constexpr float MINIMUM_MIN_LOAD_FACTOR
Definition: robin_hash.h:1578
IMATH_HOSTDEVICE constexpr int ceil(T x) IMATH_NOEXCEPT
Definition: ImathFun.h:119
void set_hash(truncated_hash_type hash) noexcept
Definition: robin_hash.h:148
IMATH_NAMESPACE::V2f IMATH_NAMESPACE::Box2i std::string this attribute is obsolete as of OpenEXR v3 float
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1425
bool empty() const noexcept
Definition: robin_hash.h:256
bool bucket_hash_equal(std::size_t) const noexcept
Definition: robin_hash.h:130
LeafData & operator=(const LeafData &)=delete
GLuint index
Definition: glcorearb.h:786
static constexpr float DEFAULT_MIN_LOAD_FACTOR
Definition: robin_hash.h:1577
iterator erase(const_iterator first, const_iterator last)
Definition: robin_hash.h:853
const U::value_type & at(const K &key) const
Definition: robin_hash.h:967
static constexpr float MAXIMUM_MIN_LOAD_FACTOR
Definition: robin_hash.h:1579
void set_value_of_empty_bucket(distance_type dist_from_ideal_bucket, truncated_hash_type hash, Args &&...value_type_args)
Definition: robin_hash.h:289
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:74
U::value_type & at(const K &key, std::size_t hash)
Definition: robin_hash.h:960
**If you just want to fire and args
Definition: thread.h:618
size_type size() const noexcept
Definition: robin_hash.h:725
const_iterator find(const K &key) const
Definition: robin_hash.h:1013
void set_as_last_bucket() noexcept
Definition: robin_hash.h:286
bucket_entry & operator=(const bucket_entry &other) noexcept(std::is_nothrow_copy_constructible< value_type >::value)
Definition: robin_hash.h:227
static constexpr float DEFAULT_MAX_LOAD_FACTOR
Definition: robin_hash.h:1573
U::value_type & at(const K &key)
Definition: robin_hash.h:954
bucket_entry() noexcept
Definition: robin_hash.h:182
truncated_hash_type truncated_hash() const noexcept
Definition: robin_hash.h:145
friend bool operator!=(const robin_iterator &lhs, const robin_iterator &rhs)
Definition: robin_hash.h:539
allocator_type get_allocator() const
Definition: robin_hash.h:685
SIM_API const UT_StringHolder distance
size_type erase(const K &key)
Definition: robin_hash.h:917
void insert(InputIt first, InputIt last)
Definition: robin_hash.h:761
static const size_type DEFAULT_INIT_BUCKETS_SIZE
Definition: robin_hash.h:1571
bool ValueType
Definition: NanoVDB.h:5729
Definition: format.h:1821