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