All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
hashmap.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 map implementations. The exposed API
25 // is similar to std::unordered_map 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 TF_HASHMAP_H
33 #define TF_HASHMAP_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_map>
40 #else
41 #include <unordered_map>
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 Mapped, class HashFn = __gnu_cxx::hash<Key>,
49  class EqualKey = __gnu_cxx::equal_to<Key>,
50  class Alloc = __gnu_cxx::allocator<Mapped> >
51 class TfHashMap :
52  private __gnu_cxx::hash_map<Key, Mapped, HashFn, EqualKey, Alloc> {
53  typedef __gnu_cxx::hash_map<Key, Mapped, HashFn, EqualKey, Alloc> _Base;
54 public:
55  typedef typename _Base::key_type key_type;
56  typedef typename _Base::mapped_type mapped_type;
57  typedef typename _Base::value_type value_type;
58  typedef typename _Base::hasher hasher;
59  typedef typename _Base::key_equal key_equal;
60  typedef typename _Base::size_type size_type;
61  typedef typename _Base::difference_type difference_type;
62  typedef typename _Base::pointer pointer;
63  typedef typename _Base::const_pointer const_pointer;
64  typedef typename _Base::reference reference;
65  typedef typename _Base::const_reference const_reference;
66  typedef typename _Base::iterator iterator;
67  typedef typename _Base::const_iterator const_iterator;
68  typedef typename _Base::allocator_type allocator_type;
69  // No local_iterator nor any methods using them.
70 
71  TfHashMap() : _Base() { }
72  explicit
73  TfHashMap(size_type n, const hasher& hf = hasher(),
74  const key_equal& eql = key_equal(),
75  const allocator_type& alloc = allocator_type()) :
76  _Base(n, hf, eql, alloc) { }
77  explicit
78  TfHashMap(const allocator_type& alloc) :
79  _Base(0, hasher(), key_equal(), alloc) { }
80  template<class InputIterator>
81  TfHashMap(InputIterator first, InputIterator last,
82  size_type n = 0, const hasher& hf = hasher(),
83  const key_equal& eql = key_equal(),
84  const allocator_type& alloc = allocator_type()) :
85  _Base(first, last, n, hf, eql, alloc) { }
86  TfHashMap(const TfHashMap& other) : _Base(other) { }
87 
88  TfHashMap& operator=(const TfHashMap& rhs) {
89  _Base::operator=(rhs);
90  return *this;
91  }
92 
93  iterator begin() { return _Base::begin(); }
94  const_iterator begin() const { return const_iterator(_Base::begin()); }
95  // size_type bucket(const key_type& key) const;
96  using _Base::bucket_count;
97  size_type bucket_size(size_type n) const { return _Base::elems_in_bucket(n); }
98  const_iterator cbegin() const { return const_iterator(_Base::begin()); }
99  const_iterator cend() const { return const_iterator(_Base::end()); }
100  using _Base::clear;
101  using _Base::count;
102  using _Base::empty;
103  iterator end() { return _Base::end(); }
104  const_iterator end() const { return const_iterator(_Base::end()); }
105  std::pair<iterator,iterator> equal_range(const key_type& key) {
106  return _Base::equal_range(key);
107  }
108  std::pair<const_iterator,const_iterator> equal_range(const key_type& key) const {
109  return _Base::equal_range(key);
110  }
111  size_type erase(const key_type& key) { return _Base::erase(key); }
112  void erase(const_iterator position) {
113  _Base::erase(_MakeIterator(position));
114  }
115  void erase(const_iterator first, const_iterator last) {
116  _Base::erase(_MakeIterator(first), _MakeIterator(last));
117  }
118  iterator find(const key_type& key) { return _Base::find(key); }
119  const_iterator find(const key_type& key) const {
120  return const_iterator(_Base::find(key));
121  }
122  using _Base::get_allocator;
123  hasher hash_function() const { return _Base::hash_funct(); }
124  using _Base::insert;
125  iterator insert(const_iterator, const value_type& v) {
126  return insert(v).first;
127  }
128  using _Base::key_eq;
129  float load_factor() const {
130  return static_cast<float>(static_cast<double>(size()) / bucket_count());
131  }
132  using _Base::max_bucket_count;
133  float max_load_factor() const { return 1.0; }
134  // void max_load_factor(float) { }
135  using _Base::max_size;
136  void rehash(size_type n) { _Base::resize(__gnu_cxx::__stl_next_prime(n)); }
137  void reserve(size_type n) { _Base::resize(n); }
138  using _Base::size;
139  void swap(TfHashMap& other) { _Base::swap(other); }
140  mapped_type& operator[](const key_type& k) { return _Base::operator[](k); }
141 
142  template<class Key2, class Mapped2, class HashFn2, class EqualKey2, class Alloc2>
143  friend bool
144  operator==(const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&,
145  const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&);
146 
147 private:
148  // _Base::erase() takes an iterator, not a const_iterator. We happen
149  // to know const_iterator and iterator have the same layout.
150  static const iterator& _MakeIterator(const const_iterator& i) {
151  return reinterpret_cast<const iterator&>(i);
152  }
153 };
154 
155 template<class Key, class Mapped, class HashFn = __gnu_cxx::hash<Key>,
156  class EqualKey = __gnu_cxx::equal_to<Key>,
157  class Alloc = __gnu_cxx::allocator<Mapped> >
158 class TfHashMultiMap :
159  private __gnu_cxx::hash_multimap<Key, Mapped, HashFn, EqualKey, Alloc> {
160  typedef __gnu_cxx::hash_multimap<Key, Mapped, HashFn, EqualKey, Alloc> _Base;
161 public:
162  typedef typename _Base::key_type key_type;
163  typedef typename _Base::mapped_type mapped_type;
164  typedef typename _Base::value_type value_type;
165  typedef typename _Base::hasher hasher;
166  typedef typename _Base::key_equal key_equal;
167  typedef typename _Base::size_type size_type;
168  typedef typename _Base::difference_type difference_type;
169  typedef typename _Base::pointer pointer;
170  typedef typename _Base::const_pointer const_pointer;
171  typedef typename _Base::reference reference;
172  typedef typename _Base::const_reference const_reference;
173  typedef typename _Base::iterator iterator;
174  typedef typename _Base::const_iterator const_iterator;
175  typedef typename _Base::allocator_type allocator_type;
176  // No local_iterator nor any methods using them.
177 
178  TfHashMultiMap() : _Base() { }
179  explicit
180  TfHashMultiMap(size_type n, const hasher& hf = hasher(),
181  const key_equal& eql = key_equal(),
182  const allocator_type& alloc = allocator_type()) :
183  _Base(n, hf, eql, alloc) { }
184  explicit
185  TfHashMultiMap(const allocator_type& alloc) :
186  _Base(0, hasher(), key_equal(), alloc) { }
187  template<class InputIterator>
188  TfHashMultiMap(InputIterator first, InputIterator last,
189  size_type n = 0, const hasher& hf = hasher(),
190  const key_equal& eql = key_equal(),
191  const allocator_type& alloc = allocator_type()) :
192  _Base(first, last, n, hf, eql, alloc) { }
193  TfHashMultiMap(const TfHashMultiMap& other) : _Base(other) { }
194 
195  TfHashMultiMap& operator=(const TfHashMultiMap& rhs) {
196  _Base::operator=(rhs);
197  return *this;
198  }
199 
200  iterator begin() { return _Base::begin(); }
201  const_iterator begin() const { return const_iterator(_Base::begin()); }
202  // size_type bucket(const key_type& key) const;
203  using _Base::bucket_count;
204  size_type bucket_size(size_type n) const { return _Base::elems_in_bucket(n); }
205  const_iterator cbegin() const { return const_iterator(_Base::begin()); }
206  const_iterator cend() const { return const_iterator(_Base::end()); }
207  using _Base::clear;
208  using _Base::count;
209  using _Base::empty;
210  iterator end() { return _Base::end(); }
211  const_iterator end() const { return const_iterator(_Base::end()); }
212  std::pair<iterator,iterator> equal_range(const key_type& key) {
213  return _Base::equal_range(key);
214  }
215  std::pair<const_iterator,const_iterator> equal_range(const key_type& key) const {
216  return _Base::equal_range(key);
217  }
218  size_type erase(const key_type& key) { return _Base::erase(key); }
219  void erase(const_iterator position) {
220  _Base::erase(_MakeIterator(position));
221  }
222  void erase(const_iterator first, const_iterator last) {
223  _Base::erase(_MakeIterator(first), _MakeIterator(last));
224  }
225  iterator find(const key_type& key) { return _Base::find(key); }
226  const_iterator find(const key_type& key) const {
227  return const_iterator(_Base::find(key));
228  }
229  using _Base::get_allocator;
230  hasher hash_function() const { return _Base::hash_funct(); }
231  using _Base::insert;
232  iterator insert(const_iterator, const value_type& v) {
233  return insert(v).first;
234  }
235  using _Base::key_eq;
236  float load_factor() const {
237  return static_cast<float>(static_cast<double>(size()) / bucket_count());
238  }
239  using _Base::max_bucket_count;
240  float max_load_factor() const { return 1.0; }
241  // void max_load_factor(float) { }
242  using _Base::max_size;
243  void rehash(size_type n) { _Base::resize(__gnu_cxx::__stl_next_prime(n)); }
244  void reserve(size_type n) { _Base::resize(n); }
245  using _Base::size;
246  void swap(TfHashMultiMap& other) { _Base::swap(other); }
247  mapped_type& operator[](const key_type& k) { return _Base::operator[](k); }
248 
249  template<class Key2, class Mapped2, class HashFn2, class EqualKey2, class Alloc2>
250  friend bool
251  operator==(const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&,
252  const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&);
253 
254 private:
255  // _Base::erase() takes an iterator, not a const_iterator. We happen
256  // to know const_iterator and iterator have the same layout.
257  static const iterator& _MakeIterator(const const_iterator& i) {
258  return reinterpret_cast<const iterator&>(i);
259  }
260 };
261 
262 #else
263 
264 template<class Key, class Mapped, class HashFn = std::hash<Key>,
265  class EqualKey = std::equal_to<Key>,
266  class Alloc = std::allocator<std::pair<const Key, Mapped> > >
267 class TfHashMap :
268  private std::unordered_map<Key, Mapped, HashFn, EqualKey, Alloc> {
269  typedef std::unordered_map<Key, Mapped, HashFn, EqualKey, Alloc> _Base;
270 public:
271  typedef typename _Base::key_type key_type;
272  typedef typename _Base::mapped_type mapped_type;
273  typedef typename _Base::value_type value_type;
274  typedef typename _Base::hasher hasher;
275  typedef typename _Base::key_equal key_equal;
276  typedef typename _Base::size_type size_type;
277  typedef typename _Base::difference_type difference_type;
278  typedef typename _Base::pointer pointer;
279  typedef typename _Base::const_pointer const_pointer;
280  typedef typename _Base::reference reference;
281  typedef typename _Base::const_reference const_reference;
282  typedef typename _Base::iterator iterator;
283  typedef typename _Base::const_iterator const_iterator;
284  typedef typename _Base::allocator_type allocator_type;
285  // No local_iterator nor any methods using them.
286 
287  TfHashMap() : _Base() { }
288  explicit
289  TfHashMap(size_type n, const hasher& hf = hasher(),
290  const key_equal& eql = key_equal(),
291  const allocator_type& alloc = allocator_type()) :
292  _Base(n, hf, eql, alloc) { }
293  explicit
294  TfHashMap(const allocator_type& alloc) : _Base(alloc) { }
295  template<class InputIterator>
296  TfHashMap(InputIterator first, InputIterator last,
297  size_type n = 0, const hasher& hf = hasher(),
298  const key_equal& eql = key_equal(),
299  const allocator_type& alloc = allocator_type()) :
300  _Base(first, last, n, hf, eql, alloc) { }
301  TfHashMap(const TfHashMap& other) : _Base(other) { }
302 
303  TfHashMap& operator=(const TfHashMap& rhs) {
304  _Base::operator=(rhs);
305  return *this;
306  }
307 
308  iterator begin() { return _Base::begin(); }
309  const_iterator begin() const { return _Base::begin(); }
310  // using _Base::bucket;
311  using _Base::bucket_count;
312  using _Base::bucket_size;
313  const_iterator cbegin() const { return _Base::cbegin(); }
314  const_iterator cend() const { return _Base::cend(); }
315  using _Base::clear;
316  using _Base::count;
317  using _Base::empty;
318  iterator end() { return _Base::end(); }
319  const_iterator end() const { return _Base::end(); }
320  using _Base::equal_range;
321  size_type erase(const key_type& key) { return _Base::erase(key); }
322  void erase(const_iterator position) { _Base::erase(position); }
323  void erase(const_iterator first, const_iterator last) {
324  _Base::erase(first, last);
325  }
326  using _Base::find;
327  using _Base::get_allocator;
328  using _Base::hash_function;
329  std::pair<iterator, bool> insert(const value_type& v) {
330  return _Base::insert(v);
331  }
332  iterator insert(const_iterator hint, const value_type& v) {
333  return _Base::insert(hint, v);
334  }
335  template<class InputIterator>
336  void insert(InputIterator first, InputIterator last) {
337  _Base::insert(first, last);
338  }
339  using _Base::key_eq;
340  using _Base::load_factor;
341  using _Base::max_bucket_count;
342  using _Base::max_load_factor;
343  // using _Base::max_load_factor;
344  using _Base::max_size;
345  using _Base::rehash;
346  using _Base::reserve;
347  using _Base::size;
348  void swap(TfHashMap& other) { _Base::swap(other); }
349  mapped_type& operator[](const key_type& k) { return _Base::operator[](k); }
350 
351  template<class Key2, class Mapped2, class HashFn2, class EqualKey2, class Alloc2>
352  friend bool
353  operator==(const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&,
354  const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&);
355 };
356 
357 template<class Key, class Mapped, class HashFn = std::hash<Key>,
358  class EqualKey = std::equal_to<Key>,
359  class Alloc = std::allocator<std::pair<const Key, Mapped> > >
360 class TfHashMultiMap :
361  private std::unordered_map<Key, Mapped, HashFn, EqualKey, Alloc> {
362  typedef std::unordered_map<Key, Mapped, HashFn, EqualKey, Alloc> _Base;
363 public:
364  typedef typename _Base::key_type key_type;
365  typedef typename _Base::mapped_type mapped_type;
366  typedef typename _Base::value_type value_type;
367  typedef typename _Base::hasher hasher;
368  typedef typename _Base::key_equal key_equal;
369  typedef typename _Base::size_type size_type;
370  typedef typename _Base::difference_type difference_type;
371  typedef typename _Base::pointer pointer;
372  typedef typename _Base::const_pointer const_pointer;
373  typedef typename _Base::reference reference;
374  typedef typename _Base::const_reference const_reference;
375  typedef typename _Base::iterator iterator;
376  typedef typename _Base::const_iterator const_iterator;
377  typedef typename _Base::allocator_type allocator_type;
378  // No local_iterator nor any methods using them.
379 
380  TfHashMultiMap() : _Base() { }
381  explicit
382  TfHashMultiMap(size_type n, const hasher& hf = hasher(),
383  const key_equal& eql = key_equal(),
384  const allocator_type& alloc = allocator_type()) :
385  _Base(n, hf, eql, alloc) { }
386  explicit
387  TfHashMultiMap(const allocator_type& alloc) : _Base(alloc) { }
388  template<class InputIterator>
389  TfHashMultiMap(InputIterator first, InputIterator last,
390  size_type n = 0, const hasher& hf = hasher(),
391  const key_equal& eql = key_equal(),
392  const allocator_type& alloc = allocator_type()) :
393  _Base(first, last, n, hf, eql, alloc) { }
394  TfHashMultiMap(const TfHashMultiMap& other) : _Base(other) { }
395 
396  TfHashMultiMap& operator=(const TfHashMultiMap& rhs) {
397  _Base::operator=(rhs);
398  return *this;
399  }
400 
401  iterator begin() { return _Base::begin(); }
402  const_iterator begin() const { return _Base::begin(); }
403  // using _Base::bucket;
404  using _Base::bucket_count;
405  using _Base::bucket_size;
406  const_iterator cbegin() const { return _Base::cbegin(); }
407  const_iterator cend() const { return _Base::cend(); }
408  using _Base::clear;
409  using _Base::count;
410  using _Base::empty;
411  iterator end() { return _Base::end(); }
412  const_iterator end() const { return _Base::end(); }
413  using _Base::equal_range;
414  size_type erase(const key_type& key) { return _Base::erase(key); }
415  void erase(const_iterator position) { _Base::erase(position); }
416  void erase(const_iterator first, const_iterator last) {
417  _Base::erase(first, last);
418  }
419  using _Base::find;
420  using _Base::get_allocator;
421  using _Base::hash_function;
422  std::pair<iterator, bool> insert(const value_type& v) {
423  return _Base::insert(v);
424  }
425  iterator insert(const_iterator hint, const value_type& v) {
426  return _Base::insert(hint, v);
427  }
428  template<class InputIterator>
429  void insert(InputIterator first, InputIterator last) {
430  _Base::insert(first, last);
431  }
432  using _Base::key_eq;
433  using _Base::load_factor;
434  using _Base::max_bucket_count;
435  using _Base::max_load_factor;
436  // using _Base::max_load_factor;
437  using _Base::max_size;
438  using _Base::rehash;
439  using _Base::reserve;
440  using _Base::size;
441  void swap(TfHashMultiMap& other) { _Base::swap(other); }
442  mapped_type& operator[](const key_type& k) { return _Base::operator[](k); }
443 
444  template<class Key2, class Mapped2, class HashFn2, class EqualKey2, class Alloc2>
445  friend bool
446  operator==(const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&,
447  const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&);
448 };
449 
450 #endif // ARCH_HAS_GNU_STL_EXTENSIONS
451 
452 template<class Key, class Mapped, class HashFn, class EqualKey, class Alloc>
453 inline void
454 swap(TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
455  TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
456 {
457  lhs.swap(rhs);
458 }
459 
460 template<class Key, class Mapped, class HashFn, class EqualKey, class Alloc>
461 inline bool
462 operator==(const TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
463  const TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
464 {
465  typedef typename TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>::_Base _Base;
466  return static_cast<const _Base&>(lhs) == static_cast<const _Base&>(rhs);
467 }
468 
469 template<class Key, class Mapped, class HashFn, class EqualKey, class Alloc>
470 inline bool
471 operator!=(const TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
472  const TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
473 {
474  return !(lhs == rhs);
475 }
476 
477 template<class Key, class Mapped, class HashFn, class EqualKey, class Alloc>
478 inline void
479 swap(TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
480  TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
481 {
482  lhs.swap(rhs);
483 }
484 
485 template<class Key, class Mapped, class HashFn, class EqualKey, class Alloc>
486 inline bool
487 operator==(const TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
488  const TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
489 {
490  typedef typename TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>::_Base _Base;
491  return static_cast<const _Base&>(lhs) == static_cast<const _Base&>(rhs);
492 }
493 
494 template<class Key, class Mapped, class HashFn, class EqualKey, class Alloc>
495 inline bool
496 operator!=(const TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
497  const TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
498 {
499  return !(lhs == rhs);
500 }
501 
502 PXR_NAMESPACE_CLOSE_SCOPE
503 
504 #endif // TF_HASHMAP_H
void swap(ArAssetInfo &lhs, ArAssetInfo &rhs)
Definition: assetInfo.h:60
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.