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