15#ifndef PXR_BASE_TF_HASHMAP_H
16#define PXR_BASE_TF_HASHMAP_H
19#include "pxr/base/arch/defines.h"
21#if defined(ARCH_HAS_GNU_STL_EXTENSIONS)
22#include <ext/hash_map>
24#include <unordered_map>
27PXR_NAMESPACE_OPEN_SCOPE
29#if defined(ARCH_HAS_GNU_STL_EXTENSIONS)
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> >
35 private __gnu_cxx::hash_map<Key, Mapped, HashFn, EqualKey, Alloc> {
36 typedef __gnu_cxx::hash_map<Key, Mapped, HashFn, EqualKey, Alloc> _Base;
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;
54 TfHashMap() : _Base() { }
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) { }
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) { }
71 TfHashMap& operator=(
const TfHashMap& rhs) {
72 _Base::operator=(rhs);
76 iterator begin() {
return _Base::begin(); }
77 const_iterator begin()
const {
return const_iterator(_Base::begin()); }
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()); }
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);
91 std::pair<const_iterator,const_iterator> equal_range(
const key_type& key)
const {
92 return _Base::equal_range(key);
94 size_type erase(
const key_type& key) {
return _Base::erase(key); }
95 void erase(const_iterator position) {
96 _Base::erase(_MakeIterator(position));
98 void erase(const_iterator first, const_iterator last) {
99 _Base::erase(_MakeIterator(first), _MakeIterator(last));
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));
105 using _Base::get_allocator;
106 hasher hash_function()
const {
return _Base::hash_funct(); }
108 iterator insert(const_iterator,
const value_type& v) {
109 return insert(v).first;
112 float load_factor()
const {
113 return static_cast<float>(
static_cast<double>(size()) / bucket_count());
115 using _Base::max_bucket_count;
116 float max_load_factor()
const {
return 1.0; }
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); }
122 void swap(TfHashMap& other) { _Base::swap(other); }
123 mapped_type& operator[](
const key_type& k) {
return _Base::operator[](k); }
125 template<
class Key2,
class Mapped2,
class HashFn2,
class EqualKey2,
class Alloc2>
127 operator==(
const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&,
128 const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&);
133 static const iterator& _MakeIterator(
const const_iterator& i) {
134 return reinterpret_cast<const iterator&
>(i);
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;
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;
161 TfHashMultiMap() : _Base() { }
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) { }
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) { }
178 TfHashMultiMap& operator=(
const TfHashMultiMap& rhs) {
179 _Base::operator=(rhs);
183 iterator begin() {
return _Base::begin(); }
184 const_iterator begin()
const {
return const_iterator(_Base::begin()); }
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()); }
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);
198 std::pair<const_iterator,const_iterator> equal_range(
const key_type& key)
const {
199 return _Base::equal_range(key);
201 size_type erase(
const key_type& key) {
return _Base::erase(key); }
202 void erase(const_iterator position) {
203 _Base::erase(_MakeIterator(position));
205 void erase(const_iterator first, const_iterator last) {
206 _Base::erase(_MakeIterator(first), _MakeIterator(last));
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));
212 using _Base::get_allocator;
213 hasher hash_function()
const {
return _Base::hash_funct(); }
215 iterator insert(const_iterator,
const value_type& v) {
216 return insert(v).first;
219 float load_factor()
const {
220 return static_cast<float>(
static_cast<double>(size()) / bucket_count());
222 using _Base::max_bucket_count;
223 float max_load_factor()
const {
return 1.0; }
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); }
229 void swap(TfHashMultiMap& other) { _Base::swap(other); }
230 mapped_type& operator[](
const key_type& k) {
return _Base::operator[](k); }
232 template<
class Key2,
class Mapped2,
class HashFn2,
class EqualKey2,
class Alloc2>
234 operator==(
const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&,
235 const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&);
240 static const iterator& _MakeIterator(
const const_iterator& i) {
241 return reinterpret_cast<const iterator&
>(i);
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> > >
251 private std::unordered_map<Key, Mapped, HashFn, EqualKey, Alloc> {
252 typedef std::unordered_map<Key, Mapped, HashFn, EqualKey, Alloc> _Base;
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;
270 TfHashMap() : _Base() { }
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) { }
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) { }
286 TfHashMap& operator=(
const TfHashMap& rhs) {
287 _Base::operator=(rhs);
291 iterator begin() {
return _Base::begin(); }
292 const_iterator begin()
const {
return _Base::begin(); }
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(); }
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);
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);
315 iterator insert(const_iterator hint,
const value_type& v) {
316 return _Base::insert(hint, v);
318 template<
class InputIterator>
319 void insert(InputIterator first, InputIterator last) {
320 _Base::insert(first, last);
323 using _Base::load_factor;
324 using _Base::max_bucket_count;
325 using _Base::max_load_factor;
327 using _Base::max_size;
329 using _Base::reserve;
331 void swap(TfHashMap& other) { _Base::swap(other); }
332 mapped_type& operator[](
const key_type& k) {
return _Base::operator[](k); }
334 template<
class Key2,
class Mapped2,
class HashFn2,
class EqualKey2,
class Alloc2>
336 operator==(
const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&,
337 const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&);
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;
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;
363 TfHashMultiMap() : _Base() { }
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) { }
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) { }
379 TfHashMultiMap& operator=(
const TfHashMultiMap& rhs) {
380 _Base::operator=(rhs);
384 iterator begin() {
return _Base::begin(); }
385 const_iterator begin()
const {
return _Base::begin(); }
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(); }
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);
403 using _Base::get_allocator;
404 using _Base::hash_function;
405 iterator insert(
const value_type& v) {
406 return _Base::insert(v);
408 iterator insert(const_iterator hint,
const value_type& v) {
409 return _Base::insert(hint, v);
411 template<
class InputIterator>
412 void insert(InputIterator first, InputIterator last) {
413 _Base::insert(first, last);
416 using _Base::load_factor;
417 using _Base::max_bucket_count;
418 using _Base::max_load_factor;
420 using _Base::max_size;
422 using _Base::reserve;
424 void swap(TfHashMultiMap& other) { _Base::swap(other); }
425 mapped_type& operator[](
const key_type& k) {
return _Base::operator[](k); }
427 template<
class Key2,
class Mapped2,
class HashFn2,
class EqualKey2,
class Alloc2>
429 operator==(
const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&,
430 const TfHashMap<Key2, Mapped2, HashFn2, EqualKey2, Alloc2>&);
435template<
class Key,
class Mapped,
class HashFn,
class EqualKey,
class Alloc>
437swap(TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
438 TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
443template<
class Key,
class Mapped,
class HashFn,
class EqualKey,
class Alloc>
445operator==(
const TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
446 const TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
448 typedef typename TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>::_Base _Base;
449 return static_cast<const _Base&
>(lhs) ==
static_cast<const _Base&
>(rhs);
452template<
class Key,
class Mapped,
class HashFn,
class EqualKey,
class Alloc>
454operator!=(
const TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
455 const TfHashMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
457 return !(lhs == rhs);
460template<
class Key,
class Mapped,
class HashFn,
class EqualKey,
class Alloc>
462swap(TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
463 TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
468template<
class Key,
class Mapped,
class HashFn,
class EqualKey,
class Alloc>
470operator==(
const TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
471 const TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
473 typedef typename TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>::_Base _Base;
474 return static_cast<const _Base&
>(lhs) ==
static_cast<const _Base&
>(rhs);
477template<
class Key,
class Mapped,
class HashFn,
class EqualKey,
class Alloc>
479operator!=(
const TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& lhs,
480 const TfHashMultiMap<Key, Mapped, HashFn, EqualKey, Alloc>& rhs)
482 return !(lhs == rhs);
485PXR_NAMESPACE_CLOSE_SCOPE