This document is for a version of USD that is under development. See this page for the current release.
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
robin_set.h
1
24#ifndef PXR_TSL_ROBIN_SET_H
25#define PXR_TSL_ROBIN_SET_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
39PXR_NAMESPACE_OPEN_SCOPE
40
41namespace pxr_tsl {
42
91template <class Key, class Hash = std::hash<Key>,
92 class KeyEqual = std::equal_to<Key>,
93 class Allocator = std::allocator<Key>, bool StoreHash = false,
94 class GrowthPolicy = pxr_tsl::rh::power_of_two_growth_policy<2>>
95class robin_set {
96 private:
97 template <typename U>
98 using has_is_transparent = pxr_tsl::detail_robin_hash::has_is_transparent<U>;
99
100 class KeySelect {
101 public:
102 using key_type = Key;
103
104 const key_type& operator()(const Key& key) const noexcept { return key; }
105
106 key_type& operator()(Key& key) noexcept { return key; }
107 };
108
109 using ht = detail_robin_hash::robin_hash<Key, KeySelect, void, Hash, KeyEqual,
110 Allocator, StoreHash, GrowthPolicy>;
111
112 public:
113 using key_type = typename ht::key_type;
114 using value_type = typename ht::value_type;
115 using size_type = typename ht::size_type;
116 using difference_type = typename ht::difference_type;
117 using hasher = typename ht::hasher;
118 using key_equal = typename ht::key_equal;
119 using allocator_type = typename ht::allocator_type;
120 using reference = typename ht::reference;
121 using const_reference = typename ht::const_reference;
122 using pointer = typename ht::pointer;
123 using const_pointer = typename ht::const_pointer;
124 using iterator = typename ht::iterator;
125 using const_iterator = typename ht::const_iterator;
126
127 /*
128 * Constructors
129 */
130 robin_set() : robin_set(ht::DEFAULT_INIT_BUCKETS_SIZE) {}
131
132 explicit robin_set(size_type bucket_count, const Hash& hash = Hash(),
133 const KeyEqual& equal = KeyEqual(),
134 const Allocator& alloc = Allocator())
135 : m_ht(bucket_count, hash, equal, alloc) {}
136
137 robin_set(size_type bucket_count, const Allocator& alloc)
138 : robin_set(bucket_count, Hash(), KeyEqual(), alloc) {}
139
140 robin_set(size_type bucket_count, const Hash& hash, const Allocator& alloc)
141 : robin_set(bucket_count, hash, KeyEqual(), alloc) {}
142
143 explicit robin_set(const Allocator& alloc)
144 : robin_set(ht::DEFAULT_INIT_BUCKETS_SIZE, alloc) {}
145
146 template <class InputIt>
147 robin_set(InputIt first, InputIt last,
148 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
149 const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(),
150 const Allocator& alloc = Allocator())
151 : robin_set(bucket_count, hash, equal, alloc) {
152 insert(first, last);
153 }
154
155 template <class InputIt>
156 robin_set(InputIt first, InputIt last, size_type bucket_count,
157 const Allocator& alloc)
158 : robin_set(first, last, bucket_count, Hash(), KeyEqual(), alloc) {}
159
160 template <class InputIt>
161 robin_set(InputIt first, InputIt last, size_type bucket_count,
162 const Hash& hash, const Allocator& alloc)
163 : robin_set(first, last, bucket_count, hash, KeyEqual(), alloc) {}
164
165 robin_set(std::initializer_list<value_type> init,
166 size_type bucket_count = ht::DEFAULT_INIT_BUCKETS_SIZE,
167 const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(),
168 const Allocator& alloc = Allocator())
169 : robin_set(init.begin(), init.end(), bucket_count, hash, equal, alloc) {}
170
171 robin_set(std::initializer_list<value_type> init, size_type bucket_count,
172 const Allocator& alloc)
173 : robin_set(init.begin(), init.end(), bucket_count, Hash(), KeyEqual(),
174 alloc) {}
175
176 robin_set(std::initializer_list<value_type> init, size_type bucket_count,
177 const Hash& hash, const Allocator& alloc)
178 : robin_set(init.begin(), init.end(), bucket_count, hash, KeyEqual(),
179 alloc) {}
180
181 robin_set& operator=(std::initializer_list<value_type> ilist) {
182 m_ht.clear();
183
184 m_ht.reserve(ilist.size());
185 m_ht.insert(ilist.begin(), ilist.end());
186
187 return *this;
188 }
189
190 allocator_type get_allocator() const { return m_ht.get_allocator(); }
191
192 /*
193 * Iterators
194 */
195 iterator begin() noexcept { return m_ht.begin(); }
196 const_iterator begin() const noexcept { return m_ht.begin(); }
197 const_iterator cbegin() const noexcept { return m_ht.cbegin(); }
198
199 iterator end() noexcept { return m_ht.end(); }
200 const_iterator end() const noexcept { return m_ht.end(); }
201 const_iterator cend() const noexcept { return m_ht.cend(); }
202
203 /*
204 * Capacity
205 */
206 bool empty() const noexcept { return m_ht.empty(); }
207 size_type size() const noexcept { return m_ht.size(); }
208 size_type max_size() const noexcept { return m_ht.max_size(); }
209
210 /*
211 * Modifiers
212 */
213 void clear() noexcept { m_ht.clear(); }
214
215 std::pair<iterator, bool> insert(const value_type& value) {
216 return m_ht.insert(value);
217 }
218
219 std::pair<iterator, bool> insert(value_type&& value) {
220 return m_ht.insert(std::move(value));
221 }
222
223 iterator insert(const_iterator hint, const value_type& value) {
224 return m_ht.insert_hint(hint, value);
225 }
226
227 iterator insert(const_iterator hint, value_type&& value) {
228 return m_ht.insert_hint(hint, std::move(value));
229 }
230
231 template <class InputIt>
232 void insert(InputIt first, InputIt last) {
233 m_ht.insert(first, last);
234 }
235
236 void insert(std::initializer_list<value_type> ilist) {
237 m_ht.insert(ilist.begin(), ilist.end());
238 }
239
247 template <class... Args>
248 std::pair<iterator, bool> emplace(Args&&... args) {
249 return m_ht.emplace(std::forward<Args>(args)...);
250 }
251
259 template <class... Args>
260 iterator emplace_hint(const_iterator hint, Args&&... args) {
261 return m_ht.emplace_hint(hint, std::forward<Args>(args)...);
262 }
263
264 iterator erase(iterator pos) { return m_ht.erase(pos); }
265 iterator erase(const_iterator pos) { return m_ht.erase(pos); }
266 iterator erase(const_iterator first, const_iterator last) {
267 return m_ht.erase(first, last);
268 }
269 size_type erase(const key_type& key) { return m_ht.erase(key); }
270
277 void erase_fast(iterator pos) { return m_ht.erase_fast(pos); }
278
284 size_type erase(const key_type& key, std::size_t precalculated_hash) {
285 return m_ht.erase(key, precalculated_hash);
286 }
287
293 template <
294 class K, class KE = KeyEqual,
295 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
296 size_type erase(const K& key) {
297 return m_ht.erase(key);
298 }
299
307 template <
308 class K, class KE = KeyEqual,
309 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
310 size_type erase(const K& key, std::size_t precalculated_hash) {
311 return m_ht.erase(key, precalculated_hash);
312 }
313
314 void swap(robin_set& other) { other.m_ht.swap(m_ht); }
315
316 /*
317 * Lookup
318 */
319 size_type count(const Key& key) const { return m_ht.count(key); }
320
326 size_type count(const Key& key, std::size_t precalculated_hash) const {
327 return m_ht.count(key, precalculated_hash);
328 }
329
335 template <
336 class K, class KE = KeyEqual,
337 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
338 size_type count(const K& key) const {
339 return m_ht.count(key);
340 }
341
349 template <
350 class K, class KE = KeyEqual,
351 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
352 size_type count(const K& key, std::size_t precalculated_hash) const {
353 return m_ht.count(key, precalculated_hash);
354 }
355
356 iterator find(const Key& key) { return m_ht.find(key); }
357
363 iterator find(const Key& key, std::size_t precalculated_hash) {
364 return m_ht.find(key, precalculated_hash);
365 }
366
367 const_iterator find(const Key& key) const { return m_ht.find(key); }
368
372 const_iterator find(const Key& key, std::size_t precalculated_hash) const {
373 return m_ht.find(key, precalculated_hash);
374 }
375
381 template <
382 class K, class KE = KeyEqual,
383 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
384 iterator find(const K& key) {
385 return m_ht.find(key);
386 }
387
395 template <
396 class K, class KE = KeyEqual,
397 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
398 iterator find(const K& key, std::size_t precalculated_hash) {
399 return m_ht.find(key, precalculated_hash);
400 }
401
405 template <
406 class K, class KE = KeyEqual,
407 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
408 const_iterator find(const K& key) const {
409 return m_ht.find(key);
410 }
411
419 template <
420 class K, class KE = KeyEqual,
421 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
422 const_iterator find(const K& key, std::size_t precalculated_hash) const {
423 return m_ht.find(key, precalculated_hash);
424 }
425
426 bool contains(const Key& key) const { return m_ht.contains(key); }
427
433 bool contains(const Key& key, std::size_t precalculated_hash) const {
434 return m_ht.contains(key, precalculated_hash);
435 }
436
442 template <
443 class K, class KE = KeyEqual,
444 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
445 bool contains(const K& key) const {
446 return m_ht.contains(key);
447 }
448
456 template <
457 class K, class KE = KeyEqual,
458 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
459 bool contains(const K& key, std::size_t precalculated_hash) const {
460 return m_ht.contains(key, precalculated_hash);
461 }
462
463 std::pair<iterator, iterator> equal_range(const Key& key) {
464 return m_ht.equal_range(key);
465 }
466
472 std::pair<iterator, iterator> equal_range(const Key& key,
473 std::size_t precalculated_hash) {
474 return m_ht.equal_range(key, precalculated_hash);
475 }
476
477 std::pair<const_iterator, const_iterator> equal_range(const Key& key) const {
478 return m_ht.equal_range(key);
479 }
480
484 std::pair<const_iterator, const_iterator> equal_range(
485 const Key& key, std::size_t precalculated_hash) const {
486 return m_ht.equal_range(key, precalculated_hash);
487 }
488
494 template <
495 class K, class KE = KeyEqual,
496 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
497 std::pair<iterator, iterator> equal_range(const K& key) {
498 return m_ht.equal_range(key);
499 }
500
508 template <
509 class K, class KE = KeyEqual,
510 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
511 std::pair<iterator, iterator> equal_range(const K& key,
512 std::size_t precalculated_hash) {
513 return m_ht.equal_range(key, precalculated_hash);
514 }
515
519 template <
520 class K, class KE = KeyEqual,
521 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
522 std::pair<const_iterator, const_iterator> equal_range(const K& key) const {
523 return m_ht.equal_range(key);
524 }
525
529 template <
530 class K, class KE = KeyEqual,
531 typename std::enable_if<has_is_transparent<KE>::value>::type* = nullptr>
532 std::pair<const_iterator, const_iterator> equal_range(
533 const K& key, std::size_t precalculated_hash) const {
534 return m_ht.equal_range(key, precalculated_hash);
535 }
536
537 /*
538 * Bucket interface
539 */
540 size_type bucket_count() const { return m_ht.bucket_count(); }
541 size_type max_bucket_count() const { return m_ht.max_bucket_count(); }
542
543 /*
544 * Hash policy
545 */
546 float load_factor() const { return m_ht.load_factor(); }
547
548 float min_load_factor() const { return m_ht.min_load_factor(); }
549 float max_load_factor() const { return m_ht.max_load_factor(); }
550
560 void min_load_factor(float ml) { m_ht.min_load_factor(ml); }
561 void max_load_factor(float ml) { m_ht.max_load_factor(ml); }
562
563 void rehash(size_type count_) { m_ht.rehash(count_); }
564 void reserve(size_type count_) { m_ht.reserve(count_); }
565
566 /*
567 * Observers
568 */
569 hasher hash_function() const { return m_ht.hash_function(); }
570 key_equal key_eq() const { return m_ht.key_eq(); }
571
572 /*
573 * Other
574 */
575
579 iterator mutable_iterator(const_iterator pos) {
580 return m_ht.mutable_iterator(pos);
581 }
582
583 friend bool operator==(const robin_set& lhs, const robin_set& rhs) {
584 if (lhs.size() != rhs.size()) {
585 return false;
586 }
587
588 for (const auto& element_lhs : lhs) {
589 const auto it_element_rhs = rhs.find(element_lhs);
590 if (it_element_rhs == rhs.cend()) {
591 return false;
592 }
593 }
594
595 return true;
596 }
597
611 template <class Serializer>
612 void serialize(Serializer& serializer) const {
613 m_ht.serialize(serializer);
614 }
615
642 template <class Deserializer>
643 static robin_set deserialize(Deserializer& deserializer,
644 bool hash_compatible = false) {
645 robin_set set(0);
646 set.m_ht.deserialize(deserializer, hash_compatible);
647
648 return set;
649 }
650
651 friend bool operator!=(const robin_set& lhs, const robin_set& rhs) {
652 return !operator==(lhs, rhs);
653 }
654
655 friend void swap(robin_set& lhs, robin_set& rhs) { lhs.swap(rhs); }
656
657 private:
658 ht m_ht;
659};
660
665template <class Key, class Hash = std::hash<Key>,
666 class KeyEqual = std::equal_to<Key>,
667 class Allocator = std::allocator<Key>, bool StoreHash = false>
668using robin_pg_set = robin_set<Key, Hash, KeyEqual, Allocator, StoreHash,
670
671} // end namespace pxr_tsl
672
673PXR_NAMESPACE_CLOSE_SCOPE
674
675#endif
The 'operator*()' and 'operator->()' methods return a const reference and const pointer respectively ...
Definition: robin_hash.h:461
Internal common class used by robin_map and robin_set.
Definition: robin_hash.h:367
iterator erase(iterator pos)
Here to avoid template<class K> size_type erase(const K& key) being used when we use an iterator inst...
Definition: robin_hash.h:836
Grow the hash table by using prime numbers as bucket count.
Implementation of a hash set using open-addressing and the robin hood hashing algorithm with backward...
Definition: robin_set.h:95
std::pair< iterator, iterator > equal_range(const Key &key, std::size_t precalculated_hash)
Use the hash value 'precalculated_hash' instead of hashing the key.
Definition: robin_set.h:472
bool contains(const Key &key, std::size_t precalculated_hash) const
Use the hash value 'precalculated_hash' instead of hashing the key.
Definition: robin_set.h:433
const_iterator find(const K &key, std::size_t precalculated_hash) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:422
const_iterator find(const Key &key, std::size_t precalculated_hash) const
Use the hash value 'precalculated_hash' instead of hashing the key.
Definition: robin_set.h:372
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:522
void erase_fast(iterator pos)
Erase the element at position 'pos'.
Definition: robin_set.h:277
std::pair< const_iterator, const_iterator > equal_range(const Key &key, std::size_t precalculated_hash) const
Use the hash value 'precalculated_hash' instead of hashing the key.
Definition: robin_set.h:484
std::pair< iterator, iterator > equal_range(const K &key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:497
bool contains(const K &key, std::size_t precalculated_hash) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:459
void min_load_factor(float ml)
Set the min_load_factor to ml.
Definition: robin_set.h:560
size_type count(const Key &key, std::size_t precalculated_hash) const
Use the hash value 'precalculated_hash' instead of hashing the key.
Definition: robin_set.h:326
const_iterator find(const K &key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:408
std::pair< const_iterator, const_iterator > equal_range(const K &key, std::size_t precalculated_hash) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:532
size_type erase(const key_type &key, std::size_t precalculated_hash)
Use the hash value 'precalculated_hash' instead of hashing the key.
Definition: robin_set.h:284
iterator find(const Key &key, std::size_t precalculated_hash)
Use the hash value 'precalculated_hash' instead of hashing the key.
Definition: robin_set.h:363
iterator mutable_iterator(const_iterator pos)
Convert a const_iterator to an iterator.
Definition: robin_set.h:579
iterator emplace_hint(const_iterator hint, Args &&... args)
Due to the way elements are stored, emplace_hint will need to move or copy the key-value once.
Definition: robin_set.h:260
iterator find(const K &key, std::size_t precalculated_hash)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:398
bool contains(const K &key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:445
size_type count(const K &key) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:338
std::pair< iterator, bool > emplace(Args &&... args)
Due to the way elements are stored, emplace will need to move or copy the key-value once.
Definition: robin_set.h:248
static robin_set deserialize(Deserializer &deserializer, bool hash_compatible=false)
Deserialize a previously serialized set through the deserializer parameter.
Definition: robin_set.h:643
size_type erase(const K &key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:296
iterator find(const K &key)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:384
size_type erase(const K &key, std::size_t precalculated_hash)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:310
std::pair< iterator, iterator > equal_range(const K &key, std::size_t precalculated_hash)
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:511
size_type count(const K &key, std::size_t precalculated_hash) const
This overload only participates in the overload resolution if the typedef KeyEqual::is_transparent ex...
Definition: robin_set.h:352
void serialize(Serializer &serializer) const
Serialize the set through the serializer parameter.
Definition: robin_set.h:612
MIT License.