HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
robin_map.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_MAP_H
25 #define PXR_TSL_ROBIN_MAP_H
26 
27 #include <cstddef>
28 #include <functional>
29 #include <initializer_list>
30 #include <memory>
31 #include <type_traits>
32 #include <utility>
33 
34 #include "robin_hash.h"
35 
36 // Pixar modification, modify namespace for isolation.
37 #include "pxr/pxr.h"
38 
40 
41 namespace pxr_tsl {
42 
43 /**
44  * Implementation of a hash map using open-addressing and the robin hood hashing
45  * algorithm with backward shift deletion.
46  *
47  * For operations modifying the hash map (insert, erase, rehash, ...), the
48  * strong exception guarantee is only guaranteed when the expression
49  * `std::is_nothrow_swappable<std::pair<Key, T>>::value &&
50  * std::is_nothrow_move_constructible<std::pair<Key, T>>::value` is true,
51  * otherwise if an exception is thrown during the swap or the move, the hash map
52  * may end up in a undefined state. Per the standard a `Key` or `T` with a
53  * noexcept copy constructor and no move constructor also satisfies the
54  * `std::is_nothrow_move_constructible<std::pair<Key, T>>::value` criterion (and
55  * will thus guarantee the strong exception for the map).
56  *
57  * When `StoreHash` is true, 32 bits of the hash are stored alongside the
58  * values. It can improve the performance during lookups if the `KeyEqual`
59  * function takes time (if it engenders a cache-miss for example) as we then
60  * compare the stored hashes before comparing the keys. When
61  * `pxr_tsl::rh::power_of_two_growth_policy` is used as `GrowthPolicy`, it may also
62  * speed-up the rehash process as we can avoid to recalculate the hash. When it
63  * is detected that storing the hash will not incur any memory penalty due to
64  * alignment (i.e. `sizeof(pxr_tsl::detail_robin_hash::bucket_entry<ValueType,
65  * true>) == sizeof(pxr_tsl::detail_robin_hash::bucket_entry<ValueType, false>)`)
66  * and `pxr_tsl::rh::power_of_two_growth_policy` is used, the hash will be stored
67  * even if `StoreHash` is false so that we can speed-up the rehash (but it will
68  * not be used on lookups unless `StoreHash` is true).
69  *
70  * `GrowthPolicy` defines how the map grows and consequently how a hash value is
71  * mapped to a bucket. By default the map uses
72  * `pxr_tsl::rh::power_of_two_growth_policy`. This policy keeps the number of
73  * buckets to a power of two and uses a mask to map the hash to a bucket instead
74  * of the slow modulo. Other growth policies are available and you may define
75  * your own growth policy, check `pxr_tsl::rh::power_of_two_growth_policy` for the
76  * interface.
77  *
78  * `std::pair<Key, T>` must be swappable.
79  *
80  * `Key` and `T` must be copy and/or move constructible.
81  *
82  * If the destructor of `Key` or `T` throws an exception, the behaviour of the
83  * class is undefined.
84  *
85  * Iterators invalidation:
86  * - clear, operator=, reserve, rehash: always invalidate the iterators.
87  * - insert, emplace, emplace_hint, operator[]: if there is an effective
88  * insert, invalidate the iterators.
89  * - erase: always invalidate the iterators.
90  */
91 template <class Key, class T, class Hash = std::hash<Key>,
92  class KeyEqual = std::equal_to<Key>,
93  class Allocator = std::allocator<std::pair<Key, T>>,
94  bool StoreHash = false,
95  class GrowthPolicy = pxr_tsl::rh::power_of_two_growth_policy<2>>
96 class robin_map {
97  private:
98  template <typename U>
100 
101  class KeySelect {
102  public:
103  using key_type = Key;
104 
105  const key_type& operator()(
106  const std::pair<Key, T>& key_value) const noexcept {
107  return key_value.first;
108  }
109 
110  key_type& operator()(std::pair<Key, T>& key_value) noexcept {
111  return key_value.first;
112  }
113  };
114 
115  class ValueSelect {
116  public:
117  using value_type = T;
118 
119  const value_type& operator()(
120  const std::pair<Key, T>& key_value) const noexcept {
121  return key_value.second;
122  }
123 
124  value_type& operator()(std::pair<Key, T>& key_value) noexcept {
125  return key_value.second;
126  }
127  };
128 
130  ValueSelect, Hash, KeyEqual,
131  Allocator, StoreHash, GrowthPolicy>;
132 
133  public:
134  using key_type = typename ht::key_type;
135  using mapped_type = T;
136  using value_type = typename ht::value_type;
137  using size_type = typename ht::size_type;
139  using hasher = typename ht::hasher;
140  using key_equal = typename ht::key_equal;
142  using reference = typename ht::reference;
144  using pointer = typename ht::pointer;
146  using iterator = typename ht::iterator;
148 
149  public:
150  /*
151  * Constructors
152  */
153  robin_map() : robin_map(ht::DEFAULT_INIT_BUCKETS_SIZE) {}
154 
155  explicit robin_map(size_type bucket_count, const Hash& hash = Hash(),
156  const KeyEqual& equal = KeyEqual(),
157  const Allocator& alloc = Allocator())
158  : m_ht(bucket_count, hash, equal, alloc) {}
159 
160  robin_map(size_type bucket_count, const Allocator& alloc)
161  : robin_map(bucket_count, Hash(), KeyEqual(), alloc) {}
162 
163  robin_map(size_type bucket_count, const Hash& hash, const Allocator& alloc)
164  : robin_map(bucket_count, hash, KeyEqual(), alloc) {}
165 
166  explicit robin_map(const Allocator& alloc)
167  : robin_map(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {}
168 
169  template <class InputIt>
170  robin_map(InputIt first, InputIt last,
172  const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(),
173  const Allocator& alloc = Allocator())
174  : robin_map(bucket_count, hash, equal, alloc) {
175  insert(first, last);
176  }
177 
178  template <class InputIt>
179  robin_map(InputIt first, InputIt last, size_type bucket_count,
180  const Allocator& alloc)
181  : robin_map(first, last, bucket_count, Hash(), KeyEqual(), alloc) {}
182 
183  template <class InputIt>
184  robin_map(InputIt first, InputIt last, size_type bucket_count,
185  const Hash& hash, const Allocator& alloc)
186  : robin_map(first, last, bucket_count, hash, KeyEqual(), alloc) {}
187 
188  robin_map(std::initializer_list<value_type> init,
190  const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(),
191  const Allocator& alloc = Allocator())
192  : robin_map(init.begin(), init.end(), bucket_count, hash, equal, alloc) {}
193 
194  robin_map(std::initializer_list<value_type> init, size_type bucket_count,
195  const Allocator& alloc)
196  : robin_map(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(),
197  alloc) {}
198 
199  robin_map(std::initializer_list<value_type> init, size_type bucket_count,
200  const Hash& hash, const Allocator& alloc)
201  : robin_map(init.begin(), init.end(), bucket_count, hash, KeyEqual(),
202  alloc) {}
203 
204  robin_map& operator=(std::initializer_list<value_type> ilist) {
205  m_ht.clear();
206 
207  m_ht.reserve(ilist.size());
208  m_ht.insert(ilist.begin(), ilist.end());
209 
210  return *this;
211  }
212 
213  allocator_type get_allocator() const { return m_ht.get_allocator(); }
214 
215  /*
216  * Iterators
217  */
218  iterator begin() noexcept { return m_ht.begin(); }
219  const_iterator begin() const noexcept { return m_ht.begin(); }
220  const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
221 
222  iterator end() noexcept { return m_ht.end(); }
223  const_iterator end() const noexcept { return m_ht.end(); }
224  const_iterator cend() const noexcept { return m_ht.cend(); }
225 
226  /*
227  * Capacity
228  */
229  bool empty() const noexcept { return m_ht.empty(); }
230  size_type size() const noexcept { return m_ht.size(); }
231  size_type max_size() const noexcept { return m_ht.max_size(); }
232 
233  /*
234  * Modifiers
235  */
236  void clear() noexcept { m_ht.clear(); }
237 
238  std::pair<iterator, bool> insert(const value_type& value) {
239  return m_ht.insert(value);
240  }
241 
242  template <class P, typename std::enable_if<std::is_constructible<
243  value_type, P&&>::value>::type* = nullptr>
244  std::pair<iterator, bool> insert(P&& value) {
245  return m_ht.emplace(std::forward<P>(value));
246  }
247 
248  std::pair<iterator, bool> insert(value_type&& value) {
249  return m_ht.insert(std::move(value));
250  }
251 
253  return m_ht.insert_hint(hint, value);
254  }
255 
256  template <class P, typename std::enable_if<std::is_constructible<
257  value_type, P&&>::value>::type* = nullptr>
259  return m_ht.emplace_hint(hint, std::forward<P>(value));
260  }
261 
263  return m_ht.insert_hint(hint, std::move(value));
264  }
265 
266  template <class InputIt>
267  void insert(InputIt first, InputIt last) {
268  m_ht.insert(first, last);
269  }
270 
271  void insert(std::initializer_list<value_type> ilist) {
272  m_ht.insert(ilist.begin(), ilist.end());
273  }
274 
275  template <class M>
276  std::pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj) {
277  return m_ht.insert_or_assign(k, std::forward<M>(obj));
278  }
279 
280  template <class M>
281  std::pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj) {
282  return m_ht.insert_or_assign(std::move(k), std::forward<M>(obj));
283  }
284 
285  template <class M>
287  return m_ht.insert_or_assign(hint, k, std::forward<M>(obj));
288  }
289 
290  template <class M>
292  return m_ht.insert_or_assign(hint, std::move(k), std::forward<M>(obj));
293  }
294 
295  /**
296  * Due to the way elements are stored, emplace will need to move or copy the
297  * key-value once. The method is equivalent to
298  * insert(value_type(std::forward<Args>(args)...));
299  *
300  * Mainly here for compatibility with the std::unordered_map interface.
301  */
302  template <class... Args>
303  std::pair<iterator, bool> emplace(Args&&... args) {
304  return m_ht.emplace(std::forward<Args>(args)...);
305  }
306 
307  /**
308  * Due to the way elements are stored, emplace_hint will need to move or copy
309  * the key-value once. The method is equivalent to insert(hint,
310  * value_type(std::forward<Args>(args)...));
311  *
312  * Mainly here for compatibility with the std::unordered_map interface.
313  */
314  template <class... Args>
316  return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
317  }
318 
319  template <class... Args>
320  std::pair<iterator, bool> try_emplace(const key_type& k, Args&&... args) {
321  return m_ht.try_emplace(k, std::forward<Args>(args)...);
322  }
323 
324  template <class... Args>
325  std::pair<iterator, bool> try_emplace(key_type&& k, Args&&... args) {
326  return m_ht.try_emplace(std::move(k), std::forward<Args>(args)...);
327  }
328 
329  template <class... Args>
330  iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args) {
331  return m_ht.try_emplace_hint(hint, k, std::forward<Args>(args)...);
332  }
333 
334  template <class... Args>
336  return m_ht.try_emplace_hint(hint, std::move(k),
337  std::forward<Args>(args)...);
338  }
339 
340  iterator erase(iterator pos) { return m_ht.erase(pos); }
341  iterator erase(const_iterator pos) { return m_ht.erase(pos); }
343  return m_ht.erase(first, last);
344  }
345  size_type erase(const key_type& key) { return m_ht.erase(key); }
346 
347  /**
348  * Erase the element at position 'pos'. In contrast to the regular erase()
349  * function, erase_fast() does not return an iterator. This allows it to be
350  * faster especially in hash tables with a low load factor, where finding the
351  * next nonempty bucket would be costly.
352  */
353  void erase_fast(iterator pos) { return m_ht.erase_fast(pos); }
354 
355  /**
356  * Use the hash value 'precalculated_hash' instead of hashing the key. The
357  * hash value should be the same as hash_function()(key). Useful to speed-up
358  * the lookup to the value if you already have the hash.
359  */
360  size_type erase(const key_type& key, std::size_t precalculated_hash) {
361  return m_ht.erase(key, precalculated_hash);
362  }
363 
364  /**
365  * This overload only participates in the overload resolution if the typedef
366  * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
367  * to Key.
368  */
369  template <
370  class K, class KE = KeyEqual,
372  size_type erase(const K& key) {
373  return m_ht.erase(key);
374  }
375 
376  /**
377  * @copydoc erase(const K& key)
378  *
379  * Use the hash value 'precalculated_hash' instead of hashing the key. The
380  * hash value should be the same as hash_function()(key). Useful to speed-up
381  * the lookup to the value if you already have the hash.
382  */
383  template <
384  class K, class KE = KeyEqual,
386  size_type erase(const K& key, std::size_t precalculated_hash) {
387  return m_ht.erase(key, precalculated_hash);
388  }
389 
390  void swap(robin_map& other) { other.m_ht.swap(m_ht); }
391 
392  /*
393  * Lookup
394  */
395  T& at(const Key& key) { return m_ht.at(key); }
396 
397  /**
398  * Use the hash value 'precalculated_hash' instead of hashing the key. The
399  * hash value should be the same as hash_function()(key). Useful to speed-up
400  * the lookup if you already have the hash.
401  */
402  T& at(const Key& key, std::size_t precalculated_hash) {
403  return m_ht.at(key, precalculated_hash);
404  }
405 
406  const T& at(const Key& key) const { return m_ht.at(key); }
407 
408  /**
409  * @copydoc at(const Key& key, std::size_t precalculated_hash)
410  */
411  const T& at(const Key& key, std::size_t precalculated_hash) const {
412  return m_ht.at(key, precalculated_hash);
413  }
414 
415  /**
416  * This overload only participates in the overload resolution if the typedef
417  * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
418  * to Key.
419  */
420  template <
421  class K, class KE = KeyEqual,
423  T& at(const K& key) {
424  return m_ht.at(key);
425  }
426 
427  /**
428  * @copydoc at(const K& key)
429  *
430  * Use the hash value 'precalculated_hash' instead of hashing the key. The
431  * hash value should be the same as hash_function()(key). Useful to speed-up
432  * the lookup if you already have the hash.
433  */
434  template <
435  class K, class KE = KeyEqual,
437  T& at(const K& key, std::size_t precalculated_hash) {
438  return m_ht.at(key, precalculated_hash);
439  }
440 
441  /**
442  * @copydoc at(const K& key)
443  */
444  template <
445  class K, class KE = KeyEqual,
447  const T& at(const K& key) const {
448  return m_ht.at(key);
449  }
450 
451  /**
452  * @copydoc at(const K& key, std::size_t precalculated_hash)
453  */
454  template <
455  class K, class KE = KeyEqual,
457  const T& at(const K& key, std::size_t precalculated_hash) const {
458  return m_ht.at(key, precalculated_hash);
459  }
460 
461  T& operator[](const Key& key) { return m_ht[key]; }
462  T& operator[](Key&& key) { return m_ht[std::move(key)]; }
463 
464  size_type count(const Key& key) const { return m_ht.count(key); }
465 
466  /**
467  * Use the hash value 'precalculated_hash' instead of hashing the key. The
468  * hash value should be the same as hash_function()(key). Useful to speed-up
469  * the lookup if you already have the hash.
470  */
471  size_type count(const Key& key, std::size_t precalculated_hash) const {
472  return m_ht.count(key, precalculated_hash);
473  }
474 
475  /**
476  * This overload only participates in the overload resolution if the typedef
477  * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
478  * to Key.
479  */
480  template <
481  class K, class KE = KeyEqual,
483  size_type count(const K& key) const {
484  return m_ht.count(key);
485  }
486 
487  /**
488  * @copydoc count(const K& key) const
489  *
490  * Use the hash value 'precalculated_hash' instead of hashing the key. The
491  * hash value should be the same as hash_function()(key). Useful to speed-up
492  * the lookup if you already have the hash.
493  */
494  template <
495  class K, class KE = KeyEqual,
497  size_type count(const K& key, std::size_t precalculated_hash) const {
498  return m_ht.count(key, precalculated_hash);
499  }
500 
501  iterator find(const Key& key) { return m_ht.find(key); }
502 
503  /**
504  * Use the hash value 'precalculated_hash' instead of hashing the key. The
505  * hash value should be the same as hash_function()(key). Useful to speed-up
506  * the lookup if you already have the hash.
507  */
508  iterator find(const Key& key, std::size_t precalculated_hash) {
509  return m_ht.find(key, precalculated_hash);
510  }
511 
512  const_iterator find(const Key& key) const { return m_ht.find(key); }
513 
514  /**
515  * @copydoc find(const Key& key, std::size_t precalculated_hash)
516  */
517  const_iterator find(const Key& key, std::size_t precalculated_hash) const {
518  return m_ht.find(key, precalculated_hash);
519  }
520 
521  /**
522  * This overload only participates in the overload resolution if the typedef
523  * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
524  * to Key.
525  */
526  template <
527  class K, class KE = KeyEqual,
529  iterator find(const K& key) {
530  return m_ht.find(key);
531  }
532 
533  /**
534  * @copydoc find(const K& key)
535  *
536  * Use the hash value 'precalculated_hash' instead of hashing the key. The
537  * hash value should be the same as hash_function()(key). Useful to speed-up
538  * the lookup if you already have the hash.
539  */
540  template <
541  class K, class KE = KeyEqual,
543  iterator find(const K& key, std::size_t precalculated_hash) {
544  return m_ht.find(key, precalculated_hash);
545  }
546 
547  /**
548  * @copydoc find(const K& key)
549  */
550  template <
551  class K, class KE = KeyEqual,
553  const_iterator find(const K& key) const {
554  return m_ht.find(key);
555  }
556 
557  /**
558  * @copydoc find(const K& key)
559  *
560  * Use the hash value 'precalculated_hash' instead of hashing the key. The
561  * hash value should be the same as hash_function()(key). Useful to speed-up
562  * the lookup if you already have the hash.
563  */
564  template <
565  class K, class KE = KeyEqual,
567  const_iterator find(const K& key, std::size_t precalculated_hash) const {
568  return m_ht.find(key, precalculated_hash);
569  }
570 
571  bool contains(const Key& key) const { return m_ht.contains(key); }
572 
573  /**
574  * Use the hash value 'precalculated_hash' instead of hashing the key. The
575  * hash value should be the same as hash_function()(key). Useful to speed-up
576  * the lookup if you already have the hash.
577  */
578  bool contains(const Key& key, std::size_t precalculated_hash) const {
579  return m_ht.contains(key, precalculated_hash);
580  }
581 
582  /**
583  * This overload only participates in the overload resolution if the typedef
584  * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
585  * to Key.
586  */
587  template <
588  class K, class KE = KeyEqual,
590  bool contains(const K& key) const {
591  return m_ht.contains(key);
592  }
593 
594  /**
595  * @copydoc contains(const K& key) const
596  *
597  * Use the hash value 'precalculated_hash' instead of hashing the key. The
598  * hash value should be the same as hash_function()(key). Useful to speed-up
599  * the lookup if you already have the hash.
600  */
601  template <
602  class K, class KE = KeyEqual,
604  bool contains(const K& key, std::size_t precalculated_hash) const {
605  return m_ht.contains(key, precalculated_hash);
606  }
607 
608  std::pair<iterator, iterator> equal_range(const Key& key) {
609  return m_ht.equal_range(key);
610  }
611 
612  /**
613  * Use the hash value 'precalculated_hash' instead of hashing the key. The
614  * hash value should be the same as hash_function()(key). Useful to speed-up
615  * the lookup if you already have the hash.
616  */
617  std::pair<iterator, iterator> equal_range(const Key& key,
618  std::size_t precalculated_hash) {
619  return m_ht.equal_range(key, precalculated_hash);
620  }
621 
622  std::pair<const_iterator, const_iterator> equal_range(const Key& key) const {
623  return m_ht.equal_range(key);
624  }
625 
626  /**
627  * @copydoc equal_range(const Key& key, std::size_t precalculated_hash)
628  */
629  std::pair<const_iterator, const_iterator> equal_range(
630  const Key& key, std::size_t precalculated_hash) const {
631  return m_ht.equal_range(key, precalculated_hash);
632  }
633 
634  /**
635  * This overload only participates in the overload resolution if the typedef
636  * KeyEqual::is_transparent exists. If so, K must be hashable and comparable
637  * to Key.
638  */
639  template <
640  class K, class KE = KeyEqual,
642  std::pair<iterator, iterator> equal_range(const K& key) {
643  return m_ht.equal_range(key);
644  }
645 
646  /**
647  * @copydoc equal_range(const K& key)
648  *
649  * Use the hash value 'precalculated_hash' instead of hashing the key. The
650  * hash value should be the same as hash_function()(key). Useful to speed-up
651  * the lookup if you already have the hash.
652  */
653  template <
654  class K, class KE = KeyEqual,
656  std::pair<iterator, iterator> equal_range(const K& key,
657  std::size_t precalculated_hash) {
658  return m_ht.equal_range(key, precalculated_hash);
659  }
660 
661  /**
662  * @copydoc equal_range(const K& key)
663  */
664  template <
665  class K, class KE = KeyEqual,
667  std::pair<const_iterator, const_iterator> equal_range(const K& key) const {
668  return m_ht.equal_range(key);
669  }
670 
671  /**
672  * @copydoc equal_range(const K& key, std::size_t precalculated_hash)
673  */
674  template <
675  class K, class KE = KeyEqual,
677  std::pair<const_iterator, const_iterator> equal_range(
678  const K& key, std::size_t precalculated_hash) const {
679  return m_ht.equal_range(key, precalculated_hash);
680  }
681 
682  /*
683  * Bucket interface
684  */
685  size_type bucket_count() const { return m_ht.bucket_count(); }
686  size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
687 
688  /*
689  * Hash policy
690  */
691  float load_factor() const { return m_ht.load_factor(); }
692 
693  float min_load_factor() const { return m_ht.min_load_factor(); }
694  float max_load_factor() const { return m_ht.max_load_factor(); }
695 
696  /**
697  * Set the `min_load_factor` to `ml`. When the `load_factor` of the map goes
698  * below `min_load_factor` after some erase operations, the map will be
699  * shrunk when an insertion occurs. The erase method itself never shrinks
700  * the map.
701  *
702  * The default value of `min_load_factor` is 0.0f, the map never shrinks by
703  * default.
704  */
705  void min_load_factor(float ml) { m_ht.min_load_factor(ml); }
706  void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
707 
708  void rehash(size_type count_) { m_ht.rehash(count_); }
709  void reserve(size_type count_) { m_ht.reserve(count_); }
710 
711  /*
712  * Observers
713  */
714  hasher hash_function() const { return m_ht.hash_function(); }
715  key_equal key_eq() const { return m_ht.key_eq(); }
716 
717  /*
718  * Other
719  */
720 
721  /**
722  * Convert a const_iterator to an iterator.
723  */
725  return m_ht.mutable_iterator(pos);
726  }
727 
728  /**
729  * Serialize the map through the `serializer` parameter.
730  *
731  * The `serializer` parameter must be a function object that supports the
732  * following call:
733  * - `template<typename U> void operator()(const U& value);` where the types
734  * `std::int16_t`, `std::uint32_t`, `std::uint64_t`, `float` and
735  * `std::pair<Key, T>` must be supported for U.
736  *
737  * The implementation leaves binary compatibility (endianness, IEEE 754 for
738  * floats, ...) of the types it serializes in the hands of the `Serializer`
739  * function object if compatibility is required.
740  */
741  template <class Serializer>
742  void serialize(Serializer& serializer) const {
743  m_ht.serialize(serializer);
744  }
745 
746  /**
747  * Deserialize a previously serialized map through the `deserializer`
748  * parameter.
749  *
750  * The `deserializer` parameter must be a function object that supports the
751  * following call:
752  * - `template<typename U> U operator()();` where the types `std::int16_t`,
753  * `std::uint32_t`, `std::uint64_t`, `float` and `std::pair<Key, T>` must be
754  * supported for U.
755  *
756  * If the deserialized hash map type is hash compatible with the serialized
757  * map, the deserialization process can be sped up by setting
758  * `hash_compatible` to true. To be hash compatible, the Hash, KeyEqual and
759  * GrowthPolicy must behave the same way than the ones used on the serialized
760  * map and the StoreHash must have the same value. The `std::size_t` must also
761  * be of the same size as the one on the platform used to serialize the map.
762  * If these criteria are not met, the behaviour is undefined with
763  * `hash_compatible` sets to true.
764  *
765  * The behaviour is undefined if the type `Key` and `T` of the `robin_map` are
766  * not the same as the types used during serialization.
767  *
768  * The implementation leaves binary compatibility (endianness, IEEE 754 for
769  * floats, size of int, ...) of the types it deserializes in the hands of the
770  * `Deserializer` function object if compatibility is required.
771  */
772  template <class Deserializer>
773  static robin_map deserialize(Deserializer& deserializer,
774  bool hash_compatible = false) {
775  robin_map map(0);
776  map.m_ht.deserialize(deserializer, hash_compatible);
777 
778  return map;
779  }
780 
781  friend bool operator==(const robin_map& lhs, const robin_map& rhs) {
782  if (lhs.size() != rhs.size()) {
783  return false;
784  }
785 
786  for (const auto& element_lhs : lhs) {
787  const auto it_element_rhs = rhs.find(element_lhs.first);
788  if (it_element_rhs == rhs.cend() ||
789  element_lhs.second != it_element_rhs->second) {
790  return false;
791  }
792  }
793 
794  return true;
795  }
796 
797  friend bool operator!=(const robin_map& lhs, const robin_map& rhs) {
798  return !operator==(lhs, rhs);
799  }
800 
801  friend void swap(robin_map& lhs, robin_map& rhs) { lhs.swap(rhs); }
802 
803  private:
804  ht m_ht;
805 };
806 
807 /**
808  * Same as `pxr_tsl::robin_map<Key, T, Hash, KeyEqual, Allocator, StoreHash,
809  * pxr_tsl::rh::prime_growth_policy>`.
810  */
811 template <class Key, class T, class Hash = std::hash<Key>,
812  class KeyEqual = std::equal_to<Key>,
813  class Allocator = std::allocator<std::pair<Key, T>>,
814  bool StoreHash = false>
815 using robin_pg_map = robin_map<Key, T, Hash, KeyEqual, Allocator, StoreHash,
817 
818 } // end namespace pxr_tsl
819 
821 
822 #endif
iterator insert(const_iterator hint, P &&value)
Definition: robin_map.h:258
bool contains(const Key &key) const
Definition: robin_map.h:571
iterator end() noexcept
Definition: robin_map.h:222
GLint first
Definition: glcorearb.h:405
iterator emplace_hint(const_iterator hint, Args &&...args)
Definition: robin_hash.h:808
T & at(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:437
iterator try_emplace_hint(const_iterator hint, K &&key, Args &&...args)
Definition: robin_hash.h:820
size_type erase(const key_type &key, std::size_t precalculated_hash)
Definition: robin_map.h:360
robin_map(InputIt first, InputIt last, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: robin_map.h:184
void deserialize(Deserializer &deserializer, bool hash_compatible)
Definition: robin_hash.h:1122
void clear() noexcept
Definition: robin_map.h:236
std::pair< iterator, bool > insert(P &&value)
Definition: robin_map.h:244
size_type erase(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:386
iterator find(const Key &key, std::size_t precalculated_hash)
Definition: robin_map.h:508
iterator emplace_hint(const_iterator hint, Args &&...args)
Definition: robin_map.h:315
const T & at(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:457
iterator erase(const_iterator pos)
Definition: robin_map.h:341
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
std::pair< iterator, bool > emplace(Args &&...args)
Definition: robin_map.h:303
std::pair< iterator, iterator > equal_range(const K &key)
Definition: robin_map.h:642
bool contains(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:604
hasher hash_function() const
Definition: robin_map.h:714
bool contains(const K &key) const
Definition: robin_map.h:590
std::pair< iterator, iterator > equal_range(const Key &key, std::size_t precalculated_hash)
Definition: robin_map.h:617
GLsizei const GLfloat * value
Definition: glcorearb.h:824
const_iterator find(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:517
iterator mutable_iterator(const_iterator pos)
Definition: robin_map.h:724
float max_load_factor() const
Definition: robin_map.h:694
std::pair< iterator, iterator > equal_range(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:656
T & operator[](const Key &key)
Definition: robin_map.h:461
size_type count(const Key &key) const
Definition: robin_map.h:464
void swap(robin_hash &other)
Definition: robin_hash.h:932
robin_map(std::initializer_list< value_type > init, size_type bucket_count=ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: robin_map.h:188
size_type erase(const key_type &key)
Definition: robin_map.h:345
void serialize(Serializer &serializer) const
Definition: robin_hash.h:1117
const_iterator find(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:567
IMATH_HOSTDEVICE constexpr bool equal(T1 a, T2 b, T3 t) IMATH_NOEXCEPT
Definition: ImathFun.h:105
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
iterator find(const K &key, std::size_t precalculated_hash)
Definition: robin_map.h:543
std::pair< const_iterator, const_iterator > equal_range(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:629
size_type count(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:471
size_type erase(const K &key)
Definition: robin_map.h:372
std::pair< iterator, bool > emplace(Args &&...args)
Definition: robin_hash.h:803
size_type bucket_count() const
Definition: robin_map.h:685
iterator insert_hint(const_iterator hint, P &&value)
Definition: robin_hash.h:751
allocator_type get_allocator() const
Definition: robin_map.h:213
iterator find(const Key &key)
Definition: robin_map.h:501
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Definition: robin_map.h:667
size_type count(const K &key) const
Definition: robin_hash.h:989
friend bool operator==(const robin_map &lhs, const robin_map &rhs)
Definition: robin_map.h:781
const T & at(const K &key) const
Definition: robin_map.h:447
const_iterator cend() const noexcept
Definition: robin_hash.h:716
void serialize(Serializer &serializer) const
Definition: robin_map.h:742
robin_map(std::initializer_list< value_type > init, size_type bucket_count, const Allocator &alloc)
Definition: robin_map.h:194
typename ht::key_type key_type
Definition: robin_map.h:134
robin_map(size_type bucket_count, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: robin_map.h:155
iterator try_emplace(const_iterator hint, const key_type &k, Args &&...args)
Definition: robin_map.h:330
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:677
GLint GLint GLsizei GLint GLenum GLenum type
Definition: glcorearb.h:108
std::pair< iterator, bool > insert_or_assign(const key_type &k, M &&obj)
Definition: robin_map.h:276
typename ht::value_type value_type
Definition: robin_map.h:136
robin_map(size_type bucket_count, const Allocator &alloc)
Definition: robin_map.h:160
void reserve(size_type count_)
Definition: robin_map.h:709
void max_load_factor(float ml)
Definition: robin_map.h:706
robin_map(InputIt first, InputIt last, size_type bucket_count=ht::DEFAULT_INIT_BUCKETS_SIZE, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual(), const Allocator &alloc=Allocator())
Definition: robin_map.h:170
T & at(const K &key)
Definition: robin_map.h:423
const_iterator find(const Key &key) const
Definition: robin_map.h:512
GLuint GLuint end
Definition: glcorearb.h:475
const_iterator cend() const noexcept
Definition: robin_map.h:224
iterator insert_or_assign(const_iterator hint, const key_type &k, M &&obj)
Definition: robin_map.h:286
const_iterator find(const K &key) const
Definition: robin_map.h:553
iterator insert(const_iterator hint, value_type &&value)
Definition: robin_map.h:262
std::pair< iterator, bool > insert(P &&value)
Definition: robin_hash.h:746
size_type max_size() const noexcept
Definition: robin_map.h:231
void swap(robin_map &other)
Definition: robin_map.h:390
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
void rehash(size_type count_)
Definition: robin_map.h:708
friend bool operator!=(const robin_map &lhs, const robin_map &rhs)
Definition: robin_map.h:797
bool empty() const noexcept
Definition: robin_map.h:229
size_type size() const noexcept
Definition: robin_map.h:230
const_iterator cbegin() const noexcept
Definition: robin_hash.h:703
void insert(std::initializer_list< value_type > ilist)
Definition: robin_map.h:271
size_type count(const K &key) const
Definition: robin_map.h:483
robin_map(const Allocator &alloc)
Definition: robin_map.h:166
iterator find(const K &key)
Definition: robin_map.h:529
static robin_map deserialize(Deserializer &deserializer, bool hash_compatible=false)
Definition: robin_map.h:773
robin_map(size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: robin_map.h:163
std::pair< iterator, bool > insert(value_type &&value)
Definition: robin_map.h:248
std::pair< iterator, bool > try_emplace(const key_type &k, Args &&...args)
Definition: robin_map.h:320
bool contains(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:578
__hostdev__ uint64_t last(uint32_t i) const
Definition: NanoVDB.h:5976
const_iterator begin() const noexcept
Definition: robin_map.h:219
iterator mutable_iterator(const_iterator pos)
Definition: robin_hash.h:1112
std::pair< iterator, bool > try_emplace(key_type &&k, Args &&...args)
Definition: robin_map.h:325
iterator erase(iterator pos)
Definition: robin_map.h:340
float min_load_factor() const
Definition: robin_map.h:693
T & at(const Key &key, std::size_t precalculated_hash)
Definition: robin_map.h:402
std::pair< iterator, iterator > equal_range(const Key &key)
Definition: robin_map.h:608
const T & at(const Key &key) const
Definition: robin_map.h:406
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1425
friend void swap(robin_map &lhs, robin_map &rhs)
Definition: robin_map.h:801
std::pair< iterator, bool > insert(const value_type &value)
Definition: robin_map.h:238
T & operator[](Key &&key)
Definition: robin_map.h:462
const_iterator end() const noexcept
Definition: robin_map.h:223
T & at(const Key &key)
Definition: robin_map.h:395
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:74
iterator erase(const_iterator first, const_iterator last)
Definition: robin_map.h:342
void insert(InputIt first, InputIt last)
Definition: robin_map.h:267
void min_load_factor(float ml)
Definition: robin_map.h:705
**If you just want to fire and args
Definition: thread.h:618
size_type size() const noexcept
Definition: robin_hash.h:725
const_iterator cbegin() const noexcept
Definition: robin_map.h:220
robin_map & operator=(std::initializer_list< value_type > ilist)
Definition: robin_map.h:204
U::value_type & at(const K &key)
Definition: robin_hash.h:954
const T & at(const Key &key, std::size_t precalculated_hash) const
Definition: robin_map.h:411
size_type count(const K &key, std::size_t precalculated_hash) const
Definition: robin_map.h:497
robin_map(std::initializer_list< value_type > init, size_type bucket_count, const Hash &hash, const Allocator &alloc)
Definition: robin_map.h:199
float load_factor() const
Definition: robin_map.h:691
allocator_type get_allocator() const
Definition: robin_hash.h:685
robin_map(InputIt first, InputIt last, size_type bucket_count, const Allocator &alloc)
Definition: robin_map.h:179
iterator try_emplace(const_iterator hint, key_type &&k, Args &&...args)
Definition: robin_map.h:335
iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj)
Definition: robin_map.h:291
key_equal key_eq() const
Definition: robin_map.h:715
size_type max_bucket_count() const
Definition: robin_map.h:686
std::pair< iterator, bool > insert_or_assign(key_type &&k, M &&obj)
Definition: robin_map.h:281
iterator begin() noexcept
Definition: robin_map.h:218
iterator insert(const_iterator hint, const value_type &value)
Definition: robin_map.h:252
std::pair< const_iterator, const_iterator > equal_range(const Key &key) const
Definition: robin_map.h:622
robin_map< Key, T, Hash, KeyEqual, Allocator, StoreHash, pxr_tsl::rh::prime_growth_policy > robin_pg_map
Definition: robin_map.h:816
void erase_fast(iterator pos)
Definition: robin_map.h:353