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 <stdexcept>
37 #include <tuple>
38 #include <type_traits>
39 #include <utility>
40 #include <vector>
41 
42 #include "robin_growth_policy.h"
43 
44 // Pixar modification, modify namespace for isolation.
45 #include "pxr/pxr.h"
46 
48 
49 namespace pxr_tsl {
50 
51 namespace detail_robin_hash {
52 
53 template <typename T>
54 struct make_void {
55  using type = void;
56 };
57 
58 template <typename T, typename = void>
59 struct has_is_transparent : std::false_type {};
60 
61 template <typename T>
63  typename make_void<typename T::is_transparent>::type>
64  : std::true_type {};
65 
66 template <typename U>
67 struct is_power_of_two_policy : std::false_type {};
68 
69 template <std::size_t GrowthFactor>
71  : std::true_type {};
72 
73 // Only available in C++17, we need to be compatible with C++11
74 template <class T>
75 const T& clamp(const T& v, const T& lo, const T& hi) {
76  return std::min(hi, std::max(lo, v));
77 }
78 
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);
85  }
86 
87  const bool is_same_signedness =
90  if (!is_same_signedness && (ret < T{}) != (value < U{})) {
91  PXR_TSL_RH_THROW_OR_TERMINATE(std::runtime_error, error_message);
92  }
93 
94  return ret;
95 }
96 
97 template <class T, class Deserializer>
98 static T deserialize_value(Deserializer& deserializer) {
99  // MSVC < 2017 is not conformant, circumvent the problem by removing the
100  // template keyword
101 #if defined(_MSC_VER) && _MSC_VER < 1910
102  return deserializer.Deserializer::operator()<T>();
103 #else
104  return deserializer.Deserializer::template operator()<T>();
105 #endif
106 }
107 
108 /**
109  * Fixed size type used to represent size_type values on serialization. Need to
110  * be big enough to represent a std::size_t on 32 and 64 bits platforms, and
111  * must be the same size on both platforms.
112  */
113 using slz_size_type = std::uint64_t;
116  "slz_size_type must be >= std::size_t");
117 
118 using truncated_hash_type = std::uint32_t;
119 
120 /**
121  * Helper class that stores a truncated hash if StoreHash is true and nothing
122  * otherwise.
123  */
124 template <bool StoreHash>
126  public:
127  bool bucket_hash_equal(std::size_t /*hash*/) const noexcept { return true; }
128 
129  truncated_hash_type truncated_hash() const noexcept { return 0; }
130 
131  protected:
132  void set_hash(truncated_hash_type /*hash*/) noexcept {}
133 };
134 
135 template <>
136 class bucket_entry_hash<true> {
137  public:
138  bool bucket_hash_equal(std::size_t hash) const noexcept {
139  return m_hash == truncated_hash_type(hash);
140  }
141 
142  truncated_hash_type truncated_hash() const noexcept { return m_hash; }
143 
144  protected:
145  void set_hash(truncated_hash_type hash) noexcept {
146  m_hash = truncated_hash_type(hash);
147  }
148 
149  private:
150  truncated_hash_type m_hash;
151 };
152 
153 /**
154  * Each bucket entry has:
155  * - A value of type `ValueType`.
156  * - An integer to store how far the value of the bucket, if any, is from its
157  * ideal bucket (ex: if the current bucket 5 has the value 'foo' and
158  * `hash('foo') % nb_buckets` == 3, `dist_from_ideal_bucket()` will return 2 as
159  * the current value of the bucket is two buckets away from its ideal bucket) If
160  * there is no value in the bucket (i.e. `empty()` is true)
161  * `dist_from_ideal_bucket()` will be < 0.
162  * - A marker which tells us if the bucket is the last bucket of the bucket
163  * array (useful for the iterator of the hash table).
164  * - If `StoreHash` is true, 32 bits of the hash of the value, if any, are also
165  * stored in the bucket. If the size of the hash is more than 32 bits, it is
166  * truncated. We don't store the full hash as storing the hash is a potential
167  * opportunity to use the unused space due to the alignment of the bucket_entry
168  * structure. We can thus potentially store the hash without any extra space
169  * (which would not be possible with 64 bits of the hash).
170  */
171 template <typename ValueType, bool StoreHash>
172 class bucket_entry : public bucket_entry_hash<StoreHash> {
174 
175  public:
176  using value_type = ValueType;
177  using distance_type = std::int16_t;
178 
179  bucket_entry() noexcept
180  : bucket_hash(),
181  m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
182  m_last_bucket(false) {
184  }
185 
186  bucket_entry(bool last_bucket) noexcept
187  : bucket_hash(),
188  m_dist_from_ideal_bucket(EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET),
189  m_last_bucket(last_bucket) {
191  }
192 
193  bucket_entry(const bucket_entry& other) noexcept(
195  : bucket_hash(other),
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;
202  }
203  }
204 
205  /**
206  * Never really used, but still necessary as we must call resize on an empty
207  * `std::vector<bucket_entry>`. and we need to support move-only types. See
208  * robin_hash constructor for details.
209  */
210  bucket_entry(bucket_entry&& other) noexcept(
211  std::is_nothrow_move_constructible<value_type>::value)
212  : bucket_hash(std::move(other)),
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;
219  }
220  }
221 
222  bucket_entry& operator=(const bucket_entry& other) noexcept(
224  if (this != &other) {
225  clear();
226 
227  bucket_hash::operator=(other);
228  if (!other.empty()) {
229  ::new (static_cast<void*>(std::addressof(m_value)))
230  value_type(other.value());
231  }
232 
233  m_dist_from_ideal_bucket = other.m_dist_from_ideal_bucket;
234  m_last_bucket = other.m_last_bucket;
235  }
236 
237  return *this;
238  }
239 
240  bucket_entry& operator=(bucket_entry&&) = delete;
241 
242  ~bucket_entry() noexcept { clear(); }
243 
244  void clear() noexcept {
245  if (!empty()) {
246  destroy_value();
247  m_dist_from_ideal_bucket = EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET;
248  }
249  }
250 
251  bool empty() const noexcept {
252  return m_dist_from_ideal_bucket == EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET;
253  }
254 
255  value_type& value() noexcept {
257  return *reinterpret_cast<value_type*>(std::addressof(m_value));
258  }
259 
260  const value_type& value() const noexcept {
262  return *reinterpret_cast<const value_type*>(std::addressof(m_value));
263  }
264 
266  return m_dist_from_ideal_bucket;
267  }
268 
269  bool last_bucket() const noexcept { return m_last_bucket; }
270 
271  void set_as_last_bucket() noexcept { m_last_bucket = true; }
272 
273  template <typename... Args>
275  truncated_hash_type hash,
276  Args&&... value_type_args) {
277  pxr_tsl_rh_assert(dist_from_ideal_bucket >= 0);
279 
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;
284 
286  }
287 
289  truncated_hash_type& hash, value_type& value) {
291 
292  using std::swap;
293  swap(value, this->value());
294  swap(dist_from_ideal_bucket, m_dist_from_ideal_bucket);
295 
296  if (StoreHash) {
297  const truncated_hash_type tmp_hash = this->truncated_hash();
298  this->set_hash(hash);
299  hash = tmp_hash;
300  } else {
301  // Avoid warning of unused variable if StoreHash is false
302  PXR_TSL_RH_UNUSED(hash);
303  }
304  }
305 
306  static truncated_hash_type truncate_hash(std::size_t hash) noexcept {
307  return truncated_hash_type(hash);
308  }
309 
310  private:
311  void destroy_value() noexcept {
313  value().~value_type();
314  }
315 
316  public:
319  static_assert(DIST_FROM_IDEAL_BUCKET_LIMIT <=
321  "DIST_FROM_IDEAL_BUCKET_LIMIT must be <= "
322  "std::numeric_limits<distance_type>::max() - 1.");
323 
324  private:
325  using storage = typename std::aligned_storage<sizeof(value_type),
326  alignof(value_type)>::type;
327 
328  distance_type m_dist_from_ideal_bucket;
329  bool m_last_bucket;
330  storage m_value;
331 };
332 
333 /**
334  * Internal common class used by `robin_map` and `robin_set`.
335  *
336  * ValueType is what will be stored by `robin_hash` (usually `std::pair<Key, T>`
337  * for map and `Key` for set).
338  *
339  * `KeySelect` should be a `FunctionObject` which takes a `ValueType` in
340  * parameter and returns a reference to the key.
341  *
342  * `ValueSelect` should be a `FunctionObject` which takes a `ValueType` in
343  * parameter and returns a reference to the value. `ValueSelect` should be void
344  * if there is no value (in a set for example).
345  *
346  * The strong exception guarantee only holds if the expression
347  * `std::is_nothrow_swappable<ValueType>::value &&
348  * std::is_nothrow_move_constructible<ValueType>::value` is true.
349  *
350  * Behaviour is undefined if the destructor of `ValueType` throws.
351  */
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 {
355  private:
356  template <typename U>
357  using has_mapped_type =
359 
360  static_assert(
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.");
365 
366  public:
367  template <bool IsConst>
369 
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;
374  using hasher = Hash;
375  using key_equal = KeyEqual;
376  using allocator_type = Allocator;
378  using const_reference = const value_type&;
379  using pointer = value_type*;
380  using const_pointer = const value_type*;
381  using iterator = robin_iterator<false>;
382  using const_iterator = robin_iterator<true>;
383 
384  private:
385  /**
386  * Either store the hash because we are asked by the `StoreHash` template
387  * parameter or store the hash because it doesn't cost us anything in size and
388  * can be used to speed up rehash.
389  */
390  static constexpr bool STORE_HASH =
391  StoreHash ||
394  (sizeof(std::size_t) == sizeof(truncated_hash_type) ||
396  // Don't store the hash for primitive types with default hash.
398  !std::is_same<Hash, std::hash<key_type>>::value));
399 
400  /**
401  * Only use the stored hash on lookup if we are explicitly asked. We are not
402  * sure how slow the KeyEqual operation is. An extra comparison may slow
403  * things down with a fast KeyEqual.
404  */
405  static constexpr bool USE_STORED_HASH_ON_LOOKUP = StoreHash;
406 
407  /**
408  * We can only use the hash on rehash if the size of the hash type is the same
409  * as the stored one or if we use a power of two modulo. In the case of the
410  * power of two modulo, we just mask the least significant bytes, we just have
411  * to check that the truncated_hash_type didn't truncated more bytes.
412  */
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);
416  return true;
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) <=
421  } else {
422  PXR_TSL_RH_UNUSED(bucket_count);
423  return false;
424  }
425  }
426 
427  using bucket_entry =
429  using distance_type = typename bucket_entry::distance_type;
430 
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>;
434 
435  public:
436  /**
437  * The 'operator*()' and 'operator->()' methods return a const reference and
438  * const pointer respectively to the stored value type.
439  *
440  * In case of a map, to get a mutable reference to the value associated to a
441  * key (the '.second' in the stored pair), you have to call 'value()'.
442  *
443  * The main reason for this is that if we returned a `std::pair<Key, T>&`
444  * instead of a `const std::pair<Key, T>&`, the user may modify the key which
445  * will put the map in a undefined state.
446  */
447  template <bool IsConst>
448  class robin_iterator {
449  friend class robin_hash;
450 
451  private:
452  using bucket_entry_ptr =
453  typename std::conditional<IsConst, const bucket_entry*,
455 
456  robin_iterator(bucket_entry_ptr bucket) noexcept : m_bucket(bucket) {}
457 
458  public:
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;
463  using pointer = value_type*;
464 
465  robin_iterator() noexcept {}
466 
467  // Copy constructor from iterator to const_iterator.
468  template <bool TIsConst = IsConst,
469  typename std::enable_if<TIsConst>::type* = nullptr>
471  : m_bucket(other.m_bucket) {}
472 
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;
477 
478  const typename robin_hash::key_type& key() const {
479  return KeySelect()(m_bucket->value());
480  }
481 
482  template <class U = ValueSelect,
484  IsConst>::type* = nullptr>
485  const typename U::value_type& value() const {
486  return U()(m_bucket->value());
487  }
488 
489  template <class U = ValueSelect,
491  !IsConst>::type* = nullptr>
492  typename U::value_type& value() const {
493  return U()(m_bucket->value());
494  }
495 
496  reference operator*() const { return m_bucket->value(); }
497 
498  pointer operator->() const { return std::addressof(m_bucket->value()); }
499 
501  while (true) {
502  if (m_bucket->last_bucket()) {
503  ++m_bucket;
504  return *this;
505  }
506 
507  ++m_bucket;
508  if (!m_bucket->empty()) {
509  return *this;
510  }
511  }
512  }
513 
515  robin_iterator tmp(*this);
516  ++*this;
517 
518  return tmp;
519  }
520 
521  friend bool operator==(const robin_iterator& lhs,
522  const robin_iterator& rhs) {
523  return lhs.m_bucket == rhs.m_bucket;
524  }
525 
526  friend bool operator!=(const robin_iterator& lhs,
527  const robin_iterator& rhs) {
528  return !(lhs == rhs);
529  }
530 
531  private:
532  bucket_entry_ptr m_bucket;
533  };
534 
535  public:
536 #if defined(__cplusplus) && __cplusplus >= 201402L
537  robin_hash(size_type bucket_count, const Hash& hash, const KeyEqual& equal,
538  const Allocator& alloc,
541  : Hash(hash),
542  KeyEqual(equal),
543  GrowthPolicy(bucket_count),
544  m_buckets_data(
545  [&]() {
546  if (bucket_count > max_bucket_count()) {
548  std::length_error,
549  "The map exceeds its maximum bucket count.");
550  }
551 
552  return bucket_count;
553  }(),
554  alloc),
555  m_buckets(m_buckets_data.empty() ? static_empty_bucket_ptr()
556  : m_buckets_data.data()),
557  m_bucket_count(bucket_count),
558  m_nb_elements(0),
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();
564  }
565 
568  }
569 #else
570  /**
571  * C++11 doesn't support the creation of a std::vector with a custom allocator
572  * and 'count' default-inserted elements. The needed contructor `explicit
573  * vector(size_type count, const Allocator& alloc = Allocator());` is only
574  * available in C++14 and later. We thus must resize after using the
575  * `vector(const Allocator& alloc)` constructor.
576  *
577  * We can't use `vector(size_type count, const T& value, const Allocator&
578  * alloc)` as it requires the value T to be copyable.
579  */
580  robin_hash(size_type bucket_count, const Hash& hash, const KeyEqual& equal,
581  const Allocator& alloc,
584  : Hash(hash),
585  KeyEqual(equal),
586  GrowthPolicy(bucket_count),
587  m_buckets_data(alloc),
588  m_buckets(static_empty_bucket_ptr()),
589  m_bucket_count(bucket_count),
590  m_nb_elements(0),
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.");
596  }
597 
598  if (m_bucket_count > 0) {
599  m_buckets_data.resize(m_bucket_count);
600  m_buckets = m_buckets_data.data();
601 
602  pxr_tsl_rh_assert(!m_buckets_data.empty());
603  m_buckets_data.back().set_as_last_bucket();
604  }
605 
608  }
609 #endif
610 
611  robin_hash(const robin_hash& other)
612  : Hash(other),
613  KeyEqual(other),
614  GrowthPolicy(other),
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) {}
625 
626  robin_hash(robin_hash&& other) noexcept(
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();
645  }
646 
647  robin_hash& operator=(const robin_hash& other) {
648  if (&other != this) {
649  Hash::operator=(other);
650  KeyEqual::operator=(other);
651  GrowthPolicy::operator=(other);
652 
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;
658 
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;
662 
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;
665  }
666 
667  return *this;
668  }
669 
671  other.swap(*this);
672  other.clear();
673 
674  return *this;
675  }
676 
678  return m_buckets_data.get_allocator();
679  }
680 
681  /*
682  * Iterators
683  */
684  iterator begin() noexcept {
685  std::size_t i = 0;
686  while (i < m_bucket_count && m_buckets[i].empty()) {
687  i++;
688  }
689 
690  return iterator(m_buckets + i);
691  }
692 
693  const_iterator begin() const noexcept { return cbegin(); }
694 
696  std::size_t i = 0;
697  while (i < m_bucket_count && m_buckets[i].empty()) {
698  i++;
699  }
700 
701  return const_iterator(m_buckets + i);
702  }
703 
704  iterator end() noexcept { return iterator(m_buckets + m_bucket_count); }
705 
706  const_iterator end() const noexcept { return cend(); }
707 
708  const_iterator cend() const noexcept {
709  return const_iterator(m_buckets + m_bucket_count);
710  }
711 
712  /*
713  * Capacity
714  */
715  bool empty() const noexcept { return m_nb_elements == 0; }
716 
717  size_type size() const noexcept { return m_nb_elements; }
718 
719  size_type max_size() const noexcept { return m_buckets_data.max_size(); }
720 
721  /*
722  * Modifiers
723  */
724  void clear() noexcept {
725  if (m_min_load_factor > 0.0f) {
726  clear_and_shrink();
727  } else {
728  for (auto& bucket : m_buckets_data) {
729  bucket.clear();
730  }
731 
732  m_nb_elements = 0;
733  m_grow_on_next_insert = false;
734  }
735  }
736 
737  template <typename P>
738  std::pair<iterator, bool> insert(P&& value) {
739  return insert_impl(KeySelect()(value), std::forward<P>(value));
740  }
741 
742  template <typename P>
744  if (hint != cend() &&
745  compare_keys(KeySelect()(*hint), KeySelect()(value))) {
746  return mutable_iterator(hint);
747  }
748 
749  return insert(std::forward<P>(value)).first;
750  }
751 
752  template <class InputIt>
753  void insert(InputIt first, InputIt last) {
754  if (std::is_base_of<
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());
760 
761  if (nb_elements_insert > 0 &&
762  nb_free_buckets < size_type(nb_elements_insert)) {
763  reserve(size() + size_type(nb_elements_insert));
764  }
765  }
766 
767  for (; first != last; ++first) {
768  insert(*first);
769  }
770  }
771 
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));
775  if (!it.second) {
776  it.first.value() = std::forward<M>(obj);
777  }
778 
779  return it;
780  }
781 
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);
787 
788  return it;
789  }
790 
791  return insert_or_assign(std::forward<K>(key), std::forward<M>(obj)).first;
792  }
793 
794  template <class... Args>
795  std::pair<iterator, bool> emplace(Args&&... args) {
796  return insert(value_type(std::forward<Args>(args)...));
797  }
798 
799  template <class... Args>
801  return insert_hint(hint, value_type(std::forward<Args>(args)...));
802  }
803 
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)...));
809  }
810 
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);
815  }
816 
817  return try_emplace(std::forward<K>(key), std::forward<Args>(args)...).first;
818  }
819 
820  /**
821  * Here to avoid `template<class K> size_type erase(const K& key)` being used
822  * when we use an `iterator` instead of a `const_iterator`.
823  */
825  erase_from_bucket(pos);
826 
827  /**
828  * Erase bucket used a backward shift after clearing the bucket.
829  * Check if there is a new value in the bucket, if not get the next
830  * non-empty.
831  */
832  if (pos.m_bucket->empty()) {
833  ++pos;
834  }
835 
836  m_try_shrink_on_next_insert = true;
837 
838  return pos;
839  }
840 
842 
844  if (first == last) {
845  return mutable_iterator(first);
846  }
847 
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) {
851  if (!it->empty()) {
852  it->clear();
853  m_nb_elements--;
854  }
855  }
856 
857  if (last_mutable == end()) {
858  m_try_shrink_on_next_insert = true;
859  return end();
860  }
861 
862  /*
863  * Backward shift on the values which come after the deleted values.
864  * We try to move the values closer to their ideal bucket.
865  */
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);
871 
872  const std::size_t ireturn_bucket =
873  ito_move_closer_value -
874  std::min(
875  ito_move_closer_value - icloser_bucket,
876  std::size_t(
877  m_buckets[ito_move_closer_value].dist_from_ideal_bucket()));
878 
879  while (ito_move_closer_value < m_bucket_count &&
880  m_buckets[ito_move_closer_value].dist_from_ideal_bucket() > 0) {
881  icloser_bucket =
882  ito_move_closer_value -
883  std::min(
884  ito_move_closer_value - icloser_bucket,
885  std::size_t(
886  m_buckets[ito_move_closer_value].dist_from_ideal_bucket()));
887 
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();
896 
897  ++icloser_bucket;
898  ++ito_move_closer_value;
899  }
900 
901  m_try_shrink_on_next_insert = true;
902 
903  return iterator(m_buckets + ireturn_bucket);
904  }
905 
906  template <class K>
907  size_type erase(const K& key) {
908  return erase(key, hash_key(key));
909  }
910 
911  template <class K>
912  size_type erase(const K& key, std::size_t hash) {
913  auto it = find(key, hash);
914  if (it != end()) {
915  erase_from_bucket(it);
916  m_try_shrink_on_next_insert = true;
917 
918  return 1;
919  } else {
920  return 0;
921  }
922  }
923 
924  void swap(robin_hash& other) {
925  using std::swap;
926 
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);
939  }
940 
941  /*
942  * Lookup
943  */
944  template <class K, class U = ValueSelect,
946  typename U::value_type& at(const K& key) {
947  return at(key, hash_key(key));
948  }
949 
950  template <class K, class U = ValueSelect,
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));
955  }
956 
957  template <class K, class U = ValueSelect,
959  const typename U::value_type& at(const K& key) const {
960  return at(key, hash_key(key));
961  }
962 
963  template <class K, class U = ValueSelect,
965  const typename U::value_type& at(const K& key, std::size_t hash) const {
966  auto it = find(key, hash);
967  if (it != cend()) {
968  return it.value();
969  } else {
970  PXR_TSL_RH_THROW_OR_TERMINATE(std::out_of_range, "Couldn't find key.");
971  }
972  }
973 
974  template <class K, class U = ValueSelect,
976  typename U::value_type& operator[](K&& key) {
977  return try_emplace(std::forward<K>(key)).first.value();
978  }
979 
980  template <class K>
981  size_type count(const K& key) const {
982  return count(key, hash_key(key));
983  }
984 
985  template <class K>
986  size_type count(const K& key, std::size_t hash) const {
987  if (find(key, hash) != cend()) {
988  return 1;
989  } else {
990  return 0;
991  }
992  }
993 
994  template <class K>
995  iterator find(const K& key) {
996  return find_impl(key, hash_key(key));
997  }
998 
999  template <class K>
1000  iterator find(const K& key, std::size_t hash) {
1001  return find_impl(key, hash);
1002  }
1003 
1004  template <class K>
1005  const_iterator find(const K& key) const {
1006  return find_impl(key, hash_key(key));
1007  }
1008 
1009  template <class K>
1010  const_iterator find(const K& key, std::size_t hash) const {
1011  return find_impl(key, hash);
1012  }
1013 
1014  template <class K>
1015  bool contains(const K& key) const {
1016  return contains(key, hash_key(key));
1017  }
1018 
1019  template <class K>
1020  bool contains(const K& key, std::size_t hash) const {
1021  return count(key, hash) != 0;
1022  }
1023 
1024  template <class K>
1025  std::pair<iterator, iterator> equal_range(const K& key) {
1026  return equal_range(key, hash_key(key));
1027  }
1028 
1029  template <class K>
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));
1033  }
1034 
1035  template <class K>
1036  std::pair<const_iterator, const_iterator> equal_range(const K& key) const {
1037  return equal_range(key, hash_key(key));
1038  }
1039 
1040  template <class K>
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));
1045  }
1046 
1047  /*
1048  * Bucket interface
1049  */
1050  size_type bucket_count() const { return m_bucket_count; }
1051 
1053  return std::min(GrowthPolicy::max_bucket_count(),
1054  m_buckets_data.max_size());
1055  }
1056 
1057  /*
1058  * Hash policy
1059  */
1060  float load_factor() const {
1061  if (bucket_count() == 0) {
1062  return 0;
1063  }
1064 
1065  return float(m_nb_elements) / float(bucket_count());
1066  }
1067 
1068  float min_load_factor() const { return m_min_load_factor; }
1069 
1070  float max_load_factor() const { return m_max_load_factor; }
1071 
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));
1075  }
1076 
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);
1081  }
1082 
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_);
1087  }
1088 
1089  void reserve(size_type count_) {
1090  rehash(size_type(std::ceil(float(count_) / max_load_factor())));
1091  }
1092 
1093  /*
1094  * Observers
1095  */
1096  hasher hash_function() const { return static_cast<const Hash&>(*this); }
1097 
1098  key_equal key_eq() const { return static_cast<const KeyEqual&>(*this); }
1099 
1100  /*
1101  * Other
1102  */
1104  return iterator(const_cast<bucket_entry*>(pos.m_bucket));
1105  }
1106 
1107  template <class Serializer>
1108  void serialize(Serializer& serializer) const {
1109  serialize_impl(serializer);
1110  }
1111 
1112  template <class Deserializer>
1113  void deserialize(Deserializer& deserializer, bool hash_compatible) {
1114  deserialize_impl(deserializer, hash_compatible);
1115  }
1116 
1117  private:
1118  template <class K>
1119  std::size_t hash_key(const K& key) const {
1120  return Hash::operator()(key);
1121  }
1122 
1123  template <class K1, class K2>
1124  bool compare_keys(const K1& key1, const K2& key2) const {
1125  return KeyEqual::operator()(key1, key2);
1126  }
1127 
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));
1132 
1133  return bucket;
1134  }
1135 
1136  template <class U = GrowthPolicy,
1138  nullptr>
1139  std::size_t next_bucket(std::size_t index) const noexcept {
1141 
1142  return (index + 1) & this->m_mask;
1143  }
1144 
1145  template <class U = GrowthPolicy,
1147  nullptr>
1148  std::size_t next_bucket(std::size_t index) const noexcept {
1150 
1151  index++;
1152  return (index != bucket_count()) ? index : 0;
1153  }
1154 
1155  template <class K>
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));
1159  }
1160 
1161  template <class K>
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;
1165 
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);
1173  }
1174 
1175  ibucket = next_bucket(ibucket);
1176  dist_from_ideal_bucket++;
1177  }
1178 
1179  return cend();
1180  }
1181 
1182  void erase_from_bucket(iterator pos) {
1183  pos.m_bucket->clear();
1184  m_nb_elements--;
1185 
1186  /**
1187  * Backward shift, swap the empty bucket, previous_ibucket, with the values
1188  * on its right, ibucket, until we cross another empty bucket or if the
1189  * other bucket has a distance_from_ideal_bucket == 0.
1190  *
1191  * We try to move the values closer to their ideal bucket.
1192  */
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);
1196 
1197  while (m_buckets[ibucket].dist_from_ideal_bucket() > 0) {
1198  pxr_tsl_rh_assert(m_buckets[previous_ibucket].empty());
1199 
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();
1206 
1207  previous_ibucket = ibucket;
1208  ibucket = next_bucket(ibucket);
1209  }
1210  }
1211 
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);
1216 
1217  std::size_t ibucket = bucket_for_hash(hash);
1218  distance_type dist_from_ideal_bucket = 0;
1219 
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);
1226  }
1227 
1228  ibucket = next_bucket(ibucket);
1229  dist_from_ideal_bucket++;
1230  }
1231 
1232  if (rehash_on_extreme_load()) {
1233  ibucket = bucket_for_hash(hash);
1234  dist_from_ideal_bucket = 0;
1235 
1236  while (dist_from_ideal_bucket <=
1237  m_buckets[ibucket].dist_from_ideal_bucket()) {
1238  ibucket = next_bucket(ibucket);
1239  dist_from_ideal_bucket++;
1240  }
1241  }
1242 
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)...);
1247  } else {
1248  insert_value(ibucket, dist_from_ideal_bucket,
1250  std::forward<Args>(value_type_args)...);
1251  }
1252 
1253  m_nb_elements++;
1254  /*
1255  * The value will be inserted in ibucket in any case, either because it was
1256  * empty or by stealing the bucket (robin hood).
1257  */
1258  return std::make_pair(iterator(m_buckets + ibucket), true);
1259  }
1260 
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);
1266  }
1267 
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);
1271  }
1272 
1273  /*
1274  * We don't use `value_type&& value` as last argument due to a bug in MSVC
1275  * when `value_type` is a pointer, The compiler is not able to see the
1276  * difference between `std::string*` and `std::string*&&` resulting in a
1277  * compilation error.
1278  *
1279  * The `value` will be in a moved state at the end of the function.
1280  */
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,
1285  value);
1286  ibucket = next_bucket(ibucket);
1287  dist_from_ideal_bucket++;
1288 
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 >=
1294  /**
1295  * The number of probes is really high, rehash the map on the next
1296  * insert. Difficult to do now as rehash may throw an exception.
1297  */
1298  m_grow_on_next_insert = true;
1299  }
1300 
1301  m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket,
1302  hash, value);
1303  }
1304 
1305  ibucket = next_bucket(ibucket);
1306  dist_from_ideal_bucket++;
1307  }
1308 
1309  m_buckets[ibucket].set_value_of_empty_bucket(dist_from_ideal_bucket, hash,
1310  std::move(value));
1311  }
1312 
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);
1317 
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()) {
1322  continue;
1323  }
1324 
1325  const std::size_t hash =
1326  use_stored_hash ? bucket.truncated_hash()
1327  : new_table.hash_key(KeySelect()(bucket.value()));
1328 
1329  new_table.insert_value_on_rehash(new_table.bucket_for_hash(hash), 0,
1331  std::move(bucket.value()));
1332  }
1333 
1334  new_table.m_nb_elements = m_nb_elements;
1335  new_table.swap(*this);
1336  }
1337 
1338  void clear_and_shrink() noexcept {
1339  GrowthPolicy::clear();
1340  m_buckets_data.clear();
1341  m_buckets = static_empty_bucket_ptr();
1342  m_bucket_count = 0;
1343  m_nb_elements = 0;
1344  m_load_threshold = 0;
1345  m_grow_on_next_insert = false;
1346  m_try_shrink_on_next_insert = false;
1347  }
1348 
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) {
1352  while (true) {
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));
1358  return;
1359  } else {
1360  m_buckets[ibucket].swap_with_value_in_bucket(dist_from_ideal_bucket,
1361  hash, value);
1362  }
1363  }
1364 
1365  dist_from_ideal_bucket++;
1366  ibucket = next_bucket(ibucket);
1367  }
1368  }
1369 
1370  /**
1371  * Grow the table if m_grow_on_next_insert is true or we reached the
1372  * max_load_factor. Shrink the table if m_try_shrink_on_next_insert is true
1373  * (an erase occurred) and we're below the min_load_factor.
1374  *
1375  * Return true if the table has been rehashed.
1376  */
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;
1381 
1382  return true;
1383  }
1384 
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);
1389 
1390  return true;
1391  }
1392  }
1393 
1394  return false;
1395  }
1396 
1397  template <class Serializer>
1398  void serialize_impl(Serializer& serializer) const {
1399  const slz_size_type version = SERIALIZATION_PROTOCOL_VERSION;
1400  serializer(version);
1401 
1402  // Indicate if the truncated hash of each bucket is stored. Use a
1403  // std::int16_t instead of a bool to avoid the need for the serializer to
1404  // support an extra 'bool' type.
1405  const std::int16_t hash_stored_for_bucket =
1406  static_cast<std::int16_t>(STORE_HASH);
1407  serializer(hash_stored_for_bucket);
1408 
1409  const slz_size_type nb_elements = m_nb_elements;
1410  serializer(nb_elements);
1411 
1412  const slz_size_type bucket_count = m_buckets_data.size();
1413  serializer(bucket_count);
1414 
1415  const float min_load_factor = m_min_load_factor;
1416  serializer(min_load_factor);
1417 
1418  const float max_load_factor = m_max_load_factor;
1419  serializer(max_load_factor);
1420 
1421  for (const bucket_entry& bucket : m_buckets_data) {
1422  if (bucket.empty()) {
1423  const std::int16_t empty_bucket =
1425  serializer(empty_bucket);
1426  } else {
1427  const std::int16_t dist_from_ideal_bucket =
1428  bucket.dist_from_ideal_bucket();
1429  serializer(dist_from_ideal_bucket);
1430  if (STORE_HASH) {
1431  const std::uint32_t truncated_hash = bucket.truncated_hash();
1432  serializer(truncated_hash);
1433  }
1434  serializer(bucket.value());
1435  }
1436  }
1437  }
1438 
1439  template <class Deserializer>
1440  void deserialize_impl(Deserializer& deserializer, bool hash_compatible) {
1441  pxr_tsl_rh_assert(m_buckets_data.empty()); // Current hash table must be empty
1442 
1443  const slz_size_type version =
1444  deserialize_value<slz_size_type>(deserializer);
1445  // For now we only have one version of the serialization protocol.
1446  // If it doesn't match there is a problem with the file.
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.");
1451  }
1452 
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) {
1457  std::runtime_error,
1458  "Can't deserialize a map with a different StoreHash "
1459  "than the one used during the serialization when "
1460  "hash compatibility is used");
1461  }
1462 
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);
1469 
1470  if (min_load_factor < MINIMUM_MIN_LOAD_FACTOR ||
1471  min_load_factor > MAXIMUM_MIN_LOAD_FACTOR) {
1473  std::runtime_error,
1474  "Invalid min_load_factor. Check that the serializer "
1475  "and deserializer support floats correctly as they "
1476  "can be converted implicitly to ints.");
1477  }
1478 
1479  if (max_load_factor < MINIMUM_MAX_LOAD_FACTOR ||
1480  max_load_factor > MAXIMUM_MAX_LOAD_FACTOR) {
1482  std::runtime_error,
1483  "Invalid max_load_factor. Check that the serializer "
1484  "and deserializer support floats correctly as they "
1485  "can be converted implicitly to ints.");
1486  }
1487 
1488  this->min_load_factor(min_load_factor);
1489  this->max_load_factor(max_load_factor);
1490 
1491  if (bucket_count_ds == 0) {
1492  pxr_tsl_rh_assert(nb_elements == 0);
1493  return;
1494  }
1495 
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 !=
1504  if (hash_stored_for_bucket) {
1505  PXR_TSL_RH_UNUSED(deserialize_value<std::uint32_t>(deserializer));
1506  }
1507 
1508  insert(deserialize_value<value_type>(deserializer));
1509  }
1510  }
1511 
1512  pxr_tsl_rh_assert(nb_elements == size());
1513  } else {
1514  m_bucket_count = numeric_cast<size_type>(
1515  bucket_count_ds, "Deserialized bucket_count is too big.");
1516 
1517  GrowthPolicy::operator=(GrowthPolicy(m_bucket_count));
1518  // GrowthPolicy should not modify the bucket count we got from
1519  // deserialization
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.");
1524  }
1525 
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();
1530 
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 !=
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);
1540  }
1541 
1542  bucket.set_value_of_empty_bucket(
1543  dist_from_ideal_bucket, truncated_hash,
1544  deserialize_value<value_type>(deserializer));
1545  }
1546  }
1547 
1548  if (!m_buckets_data.empty()) {
1549  m_buckets_data.back().set_as_last_bucket();
1550  }
1551  }
1552  }
1553 
1554  public:
1556 
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;
1560 
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;
1564 
1566  "MINIMUM_MAX_LOAD_FACTOR should be < MAXIMUM_MAX_LOAD_FACTOR");
1568  "MINIMUM_MIN_LOAD_FACTOR should be < MAXIMUM_MIN_LOAD_FACTOR");
1570  "MAXIMUM_MIN_LOAD_FACTOR should be < MINIMUM_MAX_LOAD_FACTOR");
1571 
1572  private:
1573  /**
1574  * Protocol version currenlty used for serialization.
1575  */
1576  static const slz_size_type SERIALIZATION_PROTOCOL_VERSION = 1;
1577 
1578  /**
1579  * Return an always valid pointer to an static empty bucket_entry with
1580  * last_bucket() == true.
1581  */
1582  bucket_entry* static_empty_bucket_ptr() noexcept {
1583  static bucket_entry empty_bucket(true);
1584  return &empty_bucket;
1585  }
1586 
1587  private:
1588  buckets_container_type m_buckets_data;
1589 
1590  /**
1591  * Points to m_buckets_data.data() if !m_buckets_data.empty() otherwise points
1592  * to static_empty_bucket_ptr. This variable is useful to avoid the cost of
1593  * checking if m_buckets_data is empty when trying to find an element.
1594  *
1595  * TODO Remove m_buckets_data and only use a pointer instead of a
1596  * pointer+vector to save some space in the robin_hash object. Manage the
1597  * Allocator manually.
1598  */
1599  bucket_entry* m_buckets;
1600 
1601  /**
1602  * Used a lot in find, avoid the call to m_buckets_data.size() which is a bit
1603  * slower.
1604  */
1605  size_type m_bucket_count;
1606 
1607  size_type m_nb_elements;
1608 
1609  size_type m_load_threshold;
1610 
1611  float m_min_load_factor;
1612  float m_max_load_factor;
1613 
1614  bool m_grow_on_next_insert;
1615 
1616  /**
1617  * We can't shrink down the map on erase operations as the erase methods need
1618  * to return the next iterator. Shrinking the map would invalidate all the
1619  * iterators and we could not return the next iterator in a meaningful way, On
1620  * erase, we thus just indicate on erase that we should try to shrink the hash
1621  * table on the next insert if we go below the min_load_factor.
1622  */
1623  bool m_try_shrink_on_next_insert;
1624 };
1625 
1626 } // namespace detail_robin_hash
1627 
1628 } // namespace pxr_tsl
1629 
1631 
1632 #endif
void set_hash(truncated_hash_type) noexcept
Definition: robin_hash.h:132
iterator insert_or_assign(const_iterator hint, K &&key, M &&obj)
Definition: robin_hash.h:783
static const distance_type EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET
Definition: robin_hash.h:317
static truncated_hash_type truncate_hash(std::size_t hash) noexcept
Definition: robin_hash.h:306
GLint first
Definition: glcorearb.h:405
iterator emplace_hint(const_iterator hint, Args &&...args)
Definition: robin_hash.h:800
robin_iterator & operator=(const robin_iterator &other)=default
iterator try_emplace_hint(const_iterator hint, K &&key, Args &&...args)
Definition: robin_hash.h:812
bucket_entry(bool last_bucket) noexcept
Definition: robin_hash.h:186
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:626
bool last_bucket() const noexcept
Definition: robin_hash.h:269
void deserialize(Deserializer &deserializer, bool hash_compatible)
Definition: robin_hash.h:1113
Definition: robin_hash.h:172
distance_type dist_from_ideal_bucket() const noexcept
Definition: robin_hash.h:265
std::int16_t distance_type
Definition: robin_hash.h:177
size_type count(const K &key, std::size_t hash) const
Definition: robin_hash.h:986
STATIC_INLINE size_t Hash(const char *s, size_t len)
Definition: farmhash.h:2038
std::pair< iterator, bool > insert_or_assign(K &&key, M &&obj)
Definition: robin_hash.h:773
void
Definition: png.h:1083
void clear() noexcept
Definition: robin_hash.h:244
#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:1631
bool bucket_hash_equal(std::size_t hash) const noexcept
Definition: robin_hash.h:138
truncated_hash_type truncated_hash() const noexcept
Definition: robin_hash.h:129
const GLdouble * v
Definition: glcorearb.h:837
friend bool operator==(const robin_iterator &lhs, const robin_iterator &rhs)
Definition: robin_hash.h:521
value_type & value() noexcept
Definition: robin_hash.h:255
GLsizei const GLfloat * value
Definition: glcorearb.h:824
robin_iterator(const robin_iterator<!TIsConst > &other) noexcept
Definition: robin_hash.h:470
robin_hash & operator=(const robin_hash &other)
Definition: robin_hash.h:647
void swap(robin_hash &other)
Definition: robin_hash.h:924
void swap(T &lhs, T &rhs)
Definition: pugixml.cpp:7172
void serialize(Serializer &serializer) const
Definition: robin_hash.h:1108
U::value_type & operator[](K &&key)
Definition: robin_hash.h:976
static constexpr float MINIMUM_MAX_LOAD_FACTOR
Definition: robin_hash.h:1558
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:1025
bool contains(const K &key) const
Definition: robin_hash.h:1015
const robin_hash::key_type & key() const
Definition: robin_hash.h:478
const T & clamp(const T &v, const T &lo, const T &hi)
Definition: robin_hash.h:75
uint64 value_type
Definition: GA_PrimCompat.h:29
std::pair< iterator, bool > emplace(Args &&...args)
Definition: robin_hash.h:795
iterator insert_hint(const_iterator hint, P &&value)
Definition: robin_hash.h:743
size_type count(const K &key) const
Definition: robin_hash.h:981
#define pxr_tsl_rh_assert(expr)
const_iterator cend() const noexcept
Definition: robin_hash.h:708
bucket_entry(const bucket_entry &other) noexcept(std::is_nothrow_copy_constructible< value_type >::value)
Definition: robin_hash.h:193
size_type erase(const K &key, std::size_t hash)
Definition: robin_hash.h:912
GLfloat f
Definition: glcorearb.h:1926
const value_type & value() const noexcept
Definition: robin_hash.h:260
bool contains(const K &key, std::size_t hash) const
Definition: robin_hash.h:1020
const_iterator end() const noexcept
Definition: robin_hash.h:706
std::uint64_t slz_size_type
Definition: robin_hash.h:113
std::pair< iterator, iterator > equal_range(const K &key, std::size_t hash)
Definition: robin_hash.h:1030
void swap_with_value_in_bucket(distance_type &dist_from_ideal_bucket, truncated_hash_type &hash, value_type &value)
Definition: robin_hash.h:288
std::uint32_t truncated_hash_type
Definition: robin_hash.h:118
robin_hash & operator=(robin_hash &&other)
Definition: robin_hash.h:670
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:580
#define PXR_TSL_RH_LIKELY(exp)
Definition: robin_hash.h:125
iterator find(const K &key, std::size_t hash)
Definition: robin_hash.h:1000
const_iterator begin() const noexcept
Definition: robin_hash.h:693
robin_hash(const robin_hash &other)
Definition: robin_hash.h:611
static const distance_type DIST_FROM_IDEAL_BUCKET_LIMIT
Definition: robin_hash.h:318
~bucket_entry() noexcept
Definition: robin_hash.h:242
std::pair< iterator, bool > insert(P &&value)
Definition: robin_hash.h:738
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: robin_hash.h:1036
size_type max_size() const noexcept
Definition: robin_hash.h:719
std::pair< iterator, bool > try_emplace(K &&key, Args &&...args)
Definition: robin_hash.h:805
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t hash) const
Definition: robin_hash.h:1041
bucket_entry(bucket_entry &&other) noexcept(std::is_nothrow_move_constructible< value_type >::value)
Definition: robin_hash.h:210
iterator erase(const_iterator pos)
Definition: robin_hash.h:841
static constexpr float MAXIMUM_MAX_LOAD_FACTOR
Definition: robin_hash.h:1559
const_iterator cbegin() const noexcept
Definition: robin_hash.h:695
#define PXR_TSL_RH_THROW_OR_TERMINATE(ex, msg)
ValueType value_type
Definition: robin_hash.h:176
const typename robin_hash::value_type value_type
Definition: robin_hash.h:460
const_iterator find(const K &key, std::size_t hash) const
Definition: robin_hash.h:1010
GT_API const UT_StringHolder version
iterator mutable_iterator(const_iterator pos)
Definition: robin_hash.h:1103
const U::value_type & at(const K &key, std::size_t hash) const
Definition: robin_hash.h:965
static constexpr float MINIMUM_MIN_LOAD_FACTOR
Definition: robin_hash.h:1562
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:145
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1441
bool empty() const noexcept
Definition: robin_hash.h:251
bool bucket_hash_equal(std::size_t) const noexcept
Definition: robin_hash.h:127
GLuint index
Definition: glcorearb.h:786
static constexpr float DEFAULT_MIN_LOAD_FACTOR
Definition: robin_hash.h:1561
iterator erase(const_iterator first, const_iterator last)
Definition: robin_hash.h:843
const U::value_type & at(const K &key) const
Definition: robin_hash.h:959
static constexpr float MAXIMUM_MIN_LOAD_FACTOR
Definition: robin_hash.h:1563
void set_value_of_empty_bucket(distance_type dist_from_ideal_bucket, truncated_hash_type hash, Args &&...value_type_args)
Definition: robin_hash.h:274
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:91
U::value_type & at(const K &key, std::size_t hash)
Definition: robin_hash.h:952
**If you just want to fire and args
Definition: thread.h:609
size_type size() const noexcept
Definition: robin_hash.h:717
const_iterator find(const K &key) const
Definition: robin_hash.h:1005
void set_as_last_bucket() noexcept
Definition: robin_hash.h:271
bucket_entry & operator=(const bucket_entry &other) noexcept(std::is_nothrow_copy_constructible< value_type >::value)
Definition: robin_hash.h:222
static constexpr float DEFAULT_MAX_LOAD_FACTOR
Definition: robin_hash.h:1557
Definition: core.h:1131
U::value_type & at(const K &key)
Definition: robin_hash.h:946
bucket_entry() noexcept
Definition: robin_hash.h:179
truncated_hash_type truncated_hash() const noexcept
Definition: robin_hash.h:142
#define const
Definition: zconf.h:214
friend bool operator!=(const robin_iterator &lhs, const robin_iterator &rhs)
Definition: robin_hash.h:526
allocator_type get_allocator() const
Definition: robin_hash.h:677
SIM_API const UT_StringHolder distance
size_type erase(const K &key)
Definition: robin_hash.h:907
void insert(InputIt first, InputIt last)
Definition: robin_hash.h:753
type
Definition: core.h:1059
static const size_type DEFAULT_INIT_BUCKETS_SIZE
Definition: robin_hash.h:1555
Definition: format.h:895