All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
hashset.h
1//
2// Copyright 2016 Pixar
3//
4// Licensed under the terms set forth in the LICENSE.txt file available at
5// https://openusd.org/license.
6//
7// Wrap one of various unordered set implementations. The exposed API
8// is similar to std::unordered_set but is missing some methods and
9// erase(const_iterator) returns nothing.
10//
11// Wrapping provides a convenient way to switch between implementations.
12// The GNU extension (currently) has the best overall performance but
13// isn't standard. Otherwise we use the C++11 standard implementation.
14
15#ifndef PXR_BASE_TF_HASHSET_H
16#define PXR_BASE_TF_HASHSET_H
17
18#include "pxr/pxr.h"
19#include "pxr/base/arch/defines.h"
20
21#if defined(ARCH_HAS_GNU_STL_EXTENSIONS)
22#include <ext/hash_set>
23#else
24#include <unordered_set>
25#endif // ARCH_HAS_GNU_STL_EXTENSIONS
26
27PXR_NAMESPACE_OPEN_SCOPE
28
29#if defined(ARCH_HAS_GNU_STL_EXTENSIONS)
30
31template<class Key, class HashFn = __gnu_cxx::hash<Key>,
32 class EqualKey = __gnu_cxx::equal_to<Key>,
33 class Alloc = __gnu_cxx::allocator<Key> >
34class TfHashSet :
35 private __gnu_cxx::hash_set<Key, HashFn, EqualKey, Alloc> {
36 typedef __gnu_cxx::hash_set<Key, HashFn, EqualKey, Alloc> _Base;
37public:
38 typedef typename _Base::key_type key_type;
39 typedef typename _Base::value_type value_type;
40 typedef typename _Base::hasher hasher;
41 typedef typename _Base::key_equal key_equal;
42 typedef typename _Base::size_type size_type;
43 typedef typename _Base::difference_type difference_type;
44 typedef typename _Base::pointer pointer;
45 typedef typename _Base::const_pointer const_pointer;
46 typedef typename _Base::reference reference;
47 typedef typename _Base::const_reference const_reference;
48 typedef typename _Base::iterator iterator;
49 typedef typename _Base::const_iterator const_iterator;
50 typedef typename _Base::allocator_type allocator_type;
51 // No local_iterator nor any methods using them.
52
53 TfHashSet() : _Base() { }
54 explicit
55 TfHashSet(size_type n, const hasher& hf = hasher(),
56 const key_equal& eql = key_equal(),
57 const allocator_type& alloc = allocator_type()) :
58 _Base(n, hf, eql, alloc) { }
59 explicit
60 TfHashSet(const allocator_type& alloc) :
61 _Base(0, hasher(), key_equal(), alloc) { }
62 template<class InputIterator>
63 TfHashSet(InputIterator first, InputIterator last,
64 size_type n = 0, const hasher& hf = hasher(),
65 const key_equal& eql = key_equal(),
66 const allocator_type& alloc = allocator_type()) :
67 _Base(first, last, n, hf, eql, alloc) { }
68 TfHashSet(const TfHashSet& other) : _Base(other) { }
69
70 TfHashSet& operator=(const TfHashSet& rhs) {
71 _Base::operator=(rhs);
72 return *this;
73 }
74
75 iterator begin() { return _Base::begin(); }
76 const_iterator begin() const { return const_iterator(_Base::begin()); }
77 // size_type bucket(const key_type& key) const;
78 using _Base::bucket_count;
79 size_type bucket_size(size_type n) const { return _Base::elems_in_bucket(n); }
80 const_iterator cbegin() const { return const_iterator(_Base::begin()); }
81 const_iterator cend() const { return const_iterator(_Base::end()); }
82 using _Base::clear;
83 using _Base::count;
84 using _Base::empty;
85 iterator end() { return _Base::end(); }
86 const_iterator end() const { return const_iterator(_Base::end()); }
87 std::pair<iterator,iterator> equal_range(const key_type& key) {
88 return _Base::equal_range(key);
89 }
90 std::pair<const_iterator,const_iterator> equal_range(const key_type& key) const {
91 return _Base::equal_range(key);
92 }
93 size_type erase(const key_type& key) { return _Base::erase(key); }
94 void erase(const_iterator position) {
95 _Base::erase(_MakeIterator(position));
96 }
97 void erase(const_iterator first, const_iterator last) {
98 _Base::erase(_MakeIterator(first), _MakeIterator(last));
99 }
100 iterator find(const key_type& key) { return _Base::find(key); }
101 const_iterator find(const key_type& key) const {
102 return const_iterator(_Base::find(key));
103 }
104 using _Base::get_allocator;
105 hasher hash_function() const { return _Base::hash_funct(); }
106 using _Base::insert;
107 iterator insert(const_iterator, const value_type& v) {
108 return insert(v).first;
109 }
110 using _Base::key_eq;
111 float load_factor() const {
112 return static_cast<float>(static_cast<double>(size()) / bucket_count());
113 }
114 using _Base::max_bucket_count;
115 float max_load_factor() const { return 1.0; }
116 // void max_load_factor(float) { }
117 using _Base::max_size;
118 void rehash(size_type n) { _Base::resize(__gnu_cxx::__stl_next_prime(n)); }
119 void reserve(size_type n) { _Base::resize(n); }
120 using _Base::size;
121 void swap(TfHashSet& other) { _Base::swap(other); }
122
123 template<class Key2, class HashFn2, class EqualKey2, class Alloc2>
124 friend bool
125 operator==(const TfHashSet<Key2, HashFn2, EqualKey2, Alloc2>&,
126 const TfHashSet<Key2, HashFn2, EqualKey2, Alloc2>&);
127
128private:
129 // _Base::erase() takes an iterator, not a const_iterator. We happen
130 // to know const_iterator and iterator have the same layout.
131 static const iterator& _MakeIterator(const const_iterator& i) {
132 return reinterpret_cast<const iterator&>(i);
133 }
134};
135
136template<class Key, class HashFn = __gnu_cxx::hash<Key>,
137 class EqualKey = __gnu_cxx::equal_to<Key>,
138 class Alloc = __gnu_cxx::allocator<Key> >
139class TfHashMultiSet :
140 private __gnu_cxx::hash_multiset<Key, HashFn, EqualKey, Alloc> {
141 typedef __gnu_cxx::hash_multiset<Key, HashFn, EqualKey, Alloc> _Base;
142public:
143 typedef typename _Base::key_type key_type;
144 typedef typename _Base::value_type value_type;
145 typedef typename _Base::hasher hasher;
146 typedef typename _Base::key_equal key_equal;
147 typedef typename _Base::size_type size_type;
148 typedef typename _Base::difference_type difference_type;
149 typedef typename _Base::pointer pointer;
150 typedef typename _Base::const_pointer const_pointer;
151 typedef typename _Base::reference reference;
152 typedef typename _Base::const_reference const_reference;
153 typedef typename _Base::iterator iterator;
154 typedef typename _Base::const_iterator const_iterator;
155 typedef typename _Base::allocator_type allocator_type;
156 // No local_iterator nor any methods using them.
157
158 TfHashMultiSet() : _Base() { }
159 explicit
160 TfHashMultiSet(size_type n, const hasher& hf = hasher(),
161 const key_equal& eql = key_equal(),
162 const allocator_type& alloc = allocator_type()) :
163 _Base(n, hf, eql, alloc) { }
164 explicit
165 TfHashMultiSet(const allocator_type& alloc) :
166 _Base(0, hasher(), key_equal(), alloc) { }
167 template<class InputIterator>
168 TfHashMultiSet(InputIterator first, InputIterator last,
169 size_type n = 0, const hasher& hf = hasher(),
170 const key_equal& eql = key_equal(),
171 const allocator_type& alloc = allocator_type()) :
172 _Base(first, last, n, hf, eql, alloc) { }
173 TfHashMultiSet(const TfHashMultiSet& other) : _Base(other) { }
174
175 TfHashMultiSet& operator=(const TfHashMultiSet& rhs) {
176 _Base::operator=(rhs);
177 return *this;
178 }
179
180 iterator begin() { return _Base::begin(); }
181 const_iterator begin() const { return const_iterator(_Base::begin()); }
182 // size_type bucket(const key_type& key) const;
183 using _Base::bucket_count;
184 size_type bucket_size(size_type n) const { return _Base::elems_in_bucket(n); }
185 const_iterator cbegin() const { return const_iterator(_Base::begin()); }
186 const_iterator cend() const { return const_iterator(_Base::end()); }
187 using _Base::clear;
188 using _Base::count;
189 using _Base::empty;
190 iterator end() { return _Base::end(); }
191 const_iterator end() const { return const_iterator(_Base::end()); }
192 std::pair<iterator,iterator> equal_range(const key_type& key) {
193 return _Base::equal_range(key);
194 }
195 std::pair<const_iterator,const_iterator> equal_range(const key_type& key) const {
196 return _Base::equal_range(key);
197 }
198 size_type erase(const key_type& key) { return _Base::erase(key); }
199 void erase(const_iterator position) {
200 _Base::erase(_MakeIterator(position));
201 }
202 void erase(const_iterator first, const_iterator last) {
203 _Base::erase(_MakeIterator(first), _MakeIterator(last));
204 }
205 iterator find(const key_type& key) { return _Base::find(key); }
206 const_iterator find(const key_type& key) const {
207 return const_iterator(_Base::find(key));
208 }
209 using _Base::get_allocator;
210 hasher hash_function() const { return _Base::hash_funct(); }
211 using _Base::insert;
212 iterator insert(const_iterator, const value_type& v) {
213 return insert(v).first;
214 }
215 using _Base::key_eq;
216 float load_factor() const {
217 return static_cast<float>(static_cast<double>(size()) / bucket_count());
218 }
219 using _Base::max_bucket_count;
220 float max_load_factor() const { return 1.0; }
221 // void max_load_factor(float) { }
222 using _Base::max_size;
223 void rehash(size_type n) { _Base::resize(__gnu_cxx::__stl_next_prime(n)); }
224 void reserve(size_type n) { _Base::resize(n); }
225 using _Base::size;
226 void swap(TfHashMultiSet& other) { _Base::swap(other); }
227
228 template<class Key2, class HashFn2, class EqualKey2, class Alloc2>
229 friend bool
230 operator==(const TfHashMultiSet<Key2, HashFn2, EqualKey2, Alloc2>&,
231 const TfHashMultiSet<Key2, HashFn2, EqualKey2, Alloc2>&);
232
233private:
234 // _Base::erase() takes an iterator, not a const_iterator. We happen
235 // to know const_iterator and iterator have the same layout.
236 static const iterator& _MakeIterator(const const_iterator& i) {
237 return reinterpret_cast<const iterator&>(i);
238 }
239};
240
241#else
242
243template<class Key, class HashFn = std::hash<Key>,
244 class EqualKey = std::equal_to<Key>,
245 class Alloc = std::allocator<Key> >
246class TfHashSet :
247 private std::unordered_set<Key, HashFn, EqualKey, Alloc> {
248 typedef std::unordered_set<Key, HashFn, EqualKey, Alloc> _Base;
249public:
250 typedef typename _Base::key_type key_type;
251 typedef typename _Base::value_type value_type;
252 typedef typename _Base::hasher hasher;
253 typedef typename _Base::key_equal key_equal;
254 typedef typename _Base::size_type size_type;
255 typedef typename _Base::difference_type difference_type;
256 typedef typename _Base::pointer pointer;
257 typedef typename _Base::const_pointer const_pointer;
258 typedef typename _Base::reference reference;
259 typedef typename _Base::const_reference const_reference;
260 typedef typename _Base::iterator iterator;
261 typedef typename _Base::const_iterator const_iterator;
262 typedef typename _Base::allocator_type allocator_type;
263 // No local_iterator nor any methods using them.
264
265 TfHashSet() : _Base() { }
266 explicit
267 TfHashSet(size_type n, const hasher& hf = hasher(),
268 const key_equal& eql = key_equal(),
269 const allocator_type& alloc = allocator_type()) :
270 _Base(n, hf, eql, alloc) { }
271 explicit
272 TfHashSet(const allocator_type& alloc) : _Base(alloc) { }
273 template<class InputIterator>
274 TfHashSet(InputIterator first, InputIterator last,
275 size_type n = 0, const hasher& hf = hasher(),
276 const key_equal& eql = key_equal(),
277 const allocator_type& alloc = allocator_type()) :
278 _Base(first, last, n, hf, eql, alloc) { }
279 TfHashSet(const TfHashSet& other) : _Base(other) { }
280
281 TfHashSet& operator=(const TfHashSet& rhs) {
282 _Base::operator=(rhs);
283 return *this;
284 }
285
286 iterator begin() { return _Base::begin(); }
287 const_iterator begin() const { return _Base::begin(); }
288 // using _Base::bucket;
289 using _Base::bucket_count;
290 using _Base::bucket_size;
291 const_iterator cbegin() const { return _Base::cbegin(); }
292 const_iterator cend() const { return _Base::cend(); }
293 using _Base::clear;
294 using _Base::count;
295 using _Base::empty;
296 iterator end() { return _Base::end(); }
297 const_iterator end() const { return _Base::end(); }
298 using _Base::equal_range;
299 size_type erase(const key_type& key) { return _Base::erase(key); }
300 void erase(const_iterator position) { _Base::erase(position); }
301 void erase(const_iterator first, const_iterator last) {
302 _Base::erase(first, last);
303 }
304 using _Base::find;
305 using _Base::get_allocator;
306 using _Base::hash_function;
307 std::pair<iterator, bool> insert(const value_type& v) {
308 return _Base::insert(v);
309 }
310 iterator insert(const_iterator hint, const value_type& v) {
311 return _Base::insert(hint, v);
312 }
313 template<class InputIterator>
314 void insert(InputIterator first, InputIterator last) {
315 _Base::insert(first, last);
316 }
317 using _Base::key_eq;
318 using _Base::load_factor;
319 using _Base::max_bucket_count;
320 using _Base::max_load_factor;
321 // using _Base::max_load_factor;
322 using _Base::max_size;
323 using _Base::rehash;
324 using _Base::reserve;
325 using _Base::size;
326 void swap(TfHashSet& other) { _Base::swap(other); }
327
328 template<class Key2, class HashFn2, class EqualKey2, class Alloc2>
329 friend bool
330 operator==(const TfHashSet<Key2, HashFn2, EqualKey2, Alloc2>&,
331 const TfHashSet<Key2, HashFn2, EqualKey2, Alloc2>&);
332};
333
334template<class Key, class HashFn = std::hash<Key>,
335 class EqualKey = std::equal_to<Key>,
336 class Alloc = std::allocator<Key> >
337class TfHashMultiSet :
338 private std::unordered_multiset<Key, HashFn, EqualKey, Alloc> {
339 typedef std::unordered_multiset<Key, HashFn, EqualKey, Alloc> _Base;
340public:
341 typedef typename _Base::key_type key_type;
342 typedef typename _Base::value_type value_type;
343 typedef typename _Base::hasher hasher;
344 typedef typename _Base::key_equal key_equal;
345 typedef typename _Base::size_type size_type;
346 typedef typename _Base::difference_type difference_type;
347 typedef typename _Base::pointer pointer;
348 typedef typename _Base::const_pointer const_pointer;
349 typedef typename _Base::reference reference;
350 typedef typename _Base::const_reference const_reference;
351 typedef typename _Base::iterator iterator;
352 typedef typename _Base::const_iterator const_iterator;
353 typedef typename _Base::allocator_type allocator_type;
354 // No local_iterator nor any methods using them.
355
356 TfHashMultiSet() : _Base() { }
357 explicit
358 TfHashMultiSet(size_type n, const hasher& hf = hasher(),
359 const key_equal& eql = key_equal(),
360 const allocator_type& alloc = allocator_type()) :
361 _Base(n, hf, eql, alloc) { }
362 explicit
363 TfHashMultiSet(const allocator_type& alloc) : _Base(alloc) { }
364 template<class InputIterator>
365 TfHashMultiSet(InputIterator first, InputIterator last,
366 size_type n = 0, const hasher& hf = hasher(),
367 const key_equal& eql = key_equal(),
368 const allocator_type& alloc = allocator_type()) :
369 _Base(first, last, n, hf, eql, alloc) { }
370 TfHashMultiSet(const TfHashMultiSet& other) : _Base(other) { }
371
372 TfHashMultiSet& operator=(const TfHashMultiSet& rhs) {
373 _Base::operator=(rhs);
374 return *this;
375 }
376
377 iterator begin() { return _Base::begin(); }
378 const_iterator begin() const { return _Base::begin(); }
379 // using _Base::bucket;
380 using _Base::bucket_count;
381 using _Base::bucket_size;
382 const_iterator cbegin() const { return _Base::cbegin(); }
383 const_iterator cend() const { return _Base::cend(); }
384 using _Base::clear;
385 using _Base::count;
386 using _Base::empty;
387 iterator end() { return _Base::end(); }
388 const_iterator end() const { return _Base::end(); }
389 using _Base::equal_range;
390 size_type erase(const key_type& key) { return _Base::erase(key); }
391 void erase(const_iterator position) { _Base::erase(position); }
392 void erase(const_iterator first, const_iterator last) {
393 _Base::erase(first, last);
394 }
395 using _Base::find;
396 using _Base::get_allocator;
397 using _Base::hash_function;
398 iterator insert(const value_type& v) {
399 return _Base::insert(v);
400 }
401 iterator insert(const_iterator hint, const value_type& v) {
402 return _Base::insert(hint, v);
403 }
404 template<class InputIterator>
405 void insert(InputIterator first, InputIterator last) {
406 _Base::insert(first, last);
407 }
408 using _Base::key_eq;
409 using _Base::load_factor;
410 using _Base::max_bucket_count;
411 using _Base::max_load_factor;
412 // using _Base::max_load_factor;
413 using _Base::max_size;
414 using _Base::rehash;
415 using _Base::reserve;
416 using _Base::size;
417 void swap(TfHashMultiSet& other) { _Base::swap(other); }
418
419 template<class Key2, class HashFn2, class EqualKey2, class Alloc2>
420 friend bool
421 operator==(const TfHashMultiSet<Key2, HashFn2, EqualKey2, Alloc2>&,
422 const TfHashMultiSet<Key2, HashFn2, EqualKey2, Alloc2>&);
423};
424
425#endif // ARCH_HAS_GNU_STL_EXTENSIONS
426
427template<class Key, class HashFn, class EqualKey, class Alloc>
428inline void
429swap(TfHashSet<Key, HashFn, EqualKey, Alloc>& lhs,
430 TfHashSet<Key, HashFn, EqualKey, Alloc>& rhs)
431{
432 lhs.swap(rhs);
433}
434
435template<class Key, class HashFn, class EqualKey, class Alloc>
436inline bool
437operator==(const TfHashSet<Key, HashFn, EqualKey, Alloc>& lhs,
438 const TfHashSet<Key, HashFn, EqualKey, Alloc>& rhs)
439{
440 typedef typename TfHashSet<Key, HashFn, EqualKey, Alloc>::_Base _Base;
441 return static_cast<const _Base&>(lhs) == static_cast<const _Base&>(rhs);
442}
443
444template<class Key, class HashFn, class EqualKey, class Alloc>
445inline bool
446operator!=(const TfHashSet<Key, HashFn, EqualKey, Alloc>& lhs,
447 const TfHashSet<Key, HashFn, EqualKey, Alloc>& rhs)
448{
449 return !(lhs == rhs);
450}
451
452template<class Key, class HashFn, class EqualKey, class Alloc>
453inline void
454swap(TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& lhs,
455 TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& rhs)
456{
457 lhs.swap(rhs);
458}
459
460template<class Key, class HashFn, class EqualKey, class Alloc>
461inline bool
462operator==(const TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& lhs,
463 const TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& rhs)
464{
465 typedef typename TfHashMultiSet<Key, HashFn, EqualKey, Alloc>::_Base _Base;
466 return static_cast<const _Base&>(lhs) == static_cast<const _Base&>(rhs);
467}
468
469template<class Key, class HashFn, class EqualKey, class Alloc>
470inline bool
471operator!=(const TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& lhs,
472 const TfHashMultiSet<Key, HashFn, EqualKey, Alloc>& rhs)
473{
474 return !(lhs == rhs);
475}
476
477PXR_NAMESPACE_CLOSE_SCOPE
478
479#endif // PXR_BASE_TF_HASHSET_H