Loading...
Searching...
No Matches
denseHashMap.h
Go to the documentation of this file.
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#ifndef PXR_BASE_TF_DENSE_HASH_MAP_H
25#define PXR_BASE_TF_DENSE_HASH_MAP_H
26
28
29#include "pxr/pxr.h"
31#include "pxr/base/tf/hashmap.h"
32
33#include <memory>
34#include <vector>
35
36PXR_NAMESPACE_OPEN_SCOPE
37
49template <
50 class Key,
51 class Data,
52 class HashFn,
53 class EqualKey = std::equal_to<Key>,
54 unsigned Threshold = 128
55>
56
58{
59public:
60
61 typedef std::pair<const Key, Data> value_type;
62 typedef Key key_type;
63 typedef Data mapped_type;
64
66
67private:
68
69 // This helper implements a std::pair with an assignment operator that
70 // uses placement new instead of assignment. The benefit here is that
71 // the two elements of the pair may be const.
72 //
73 struct _InternalValueType
74 {
75 _InternalValueType() {}
76
77 _InternalValueType(const Key &k, const Data &d)
78 : _value(k, d) {}
79
80 _InternalValueType &operator=(const _InternalValueType &rhs) {
81
82 if (this != &rhs) {
83 // Since value_type's first member is const we need to
84 // use placement new to put the new element in place. Just
85 // make sure we destruct the element we are about to overwrite.
86 _value.value_type::~value_type();
87 new (&_value) value_type(rhs.GetValue());
88 }
89
90 return *this;
91 }
92
93 value_type &GetValue() {
94 return _value;
95 }
96
97 const value_type &GetValue() const {
98 return _value;
99 }
100
101 void swap(_InternalValueType &rhs) {
102 using std::swap;
103
104 // We do this in order to take advantage of a potentially fast
105 // swap implementation.
106 Key tmp = _value.first;
107
108 _value.first.Key::~Key();
109 new (const_cast<Key *>(&_value.first)) Key(rhs._value.first);
110
111 rhs._value.first.Key::~Key();
112 new (const_cast<Key *>(&rhs._value.first)) Key(tmp);
113
114 swap(_value.second, rhs._value.second);
115 }
116
117 private:
118
119 // Data hold by _InternalValueType. Note that the key portion of
120 // value_type maybe const.
121 value_type _value;
122 };
123
124 // The vector type holding all data for this dense hash map.
125 typedef std::vector<_InternalValueType> _Vector;
126
127 // The hash map used when the map holds more than Threshold elements.
128 typedef TfHashMap<Key, size_t, HashFn, EqualKey> _HashMap;
129
130 // Note that we don't just use _Vector::iterator for accessing elements
131 // of the TfDenseHashMap. This is because the vector's iterator would
132 // expose the _InternalValueType _including_ its assignment operator
133 // that allows overwriting keys.
134 //
135 // Clearly not a good thing.
136 //
137 // Therefore we create an iterator that uses the map's value_type as
138 // externally visible type.
139 //
140 template <class ElementType, class UnderlyingIterator>
141 class _IteratorBase
142 {
143 public:
144 using iterator_category = std::bidirectional_iterator_tag;
145 using value_type = ElementType;
146 using reference = ElementType&;
147 using pointer = ElementType*;
148 using difference_type = typename UnderlyingIterator::difference_type;
149
150 // Empty ctor.
151 _IteratorBase() = default;
152
153 // Allow conversion of an iterator to a const_iterator.
154 template<class OtherIteratorType>
155 _IteratorBase(const OtherIteratorType &rhs)
156 : _iter(rhs._GetUnderlyingIterator()) {}
157
158 reference operator*() const { return dereference(); }
159 pointer operator->() const { return &(dereference()); }
160
161 _IteratorBase& operator++() {
162 increment();
163 return *this;
164 }
165
166 _IteratorBase& operator--() {
167 decrement();
168 return *this;
169 }
170
171 _IteratorBase operator++(int) {
172 _IteratorBase result(*this);
173 increment();
174 return result;
175 }
176
177 _IteratorBase operator--(int) {
178 _IteratorBase result(*this);
179 decrement();
180 return result;
181 }
182
183 template <class OtherIteratorType>
184 bool operator==(const OtherIteratorType& other) const {
185 return equal(other);
186 }
187
188 template <class OtherIteratorType>
189 bool operator!=(const OtherIteratorType& other) const {
190 return !equal(other);
191 }
192
193 private:
194
195 friend class TfDenseHashMap;
196
197 // Ctor from an underlying iterator.
198 _IteratorBase(const UnderlyingIterator &iter)
199 : _iter(iter) {}
200
201 template<class OtherIteratorType>
202 bool equal(const OtherIteratorType &rhs) const {
203 return _iter == rhs._iter;
204 }
205
206 void increment() {
207 ++_iter;
208 }
209
210 void decrement() {
211 --_iter;
212 }
213
214 ElementType &dereference() const {
215 // The dereference() method accesses the correct value_type (ie.
216 // the one with potentially const key_type. This way, clients don't
217 // see the assignment operator of _InternalValueType.
218 return _iter->GetValue();
219 }
220
221 UnderlyingIterator _GetUnderlyingIterator() const {
222 return _iter;
223 }
224
225 private:
226
227 UnderlyingIterator _iter;
228 };
229
231
232public:
233
236 typedef
237 _IteratorBase<value_type, typename _Vector::iterator>
239
242 typedef
243 _IteratorBase<const value_type, typename _Vector::const_iterator>
245
247 typedef std::pair<iterator, bool> insert_result;
248
249public:
250
254 const HashFn &hashFn = HashFn(),
255 const EqualKey &equalKey = EqualKey())
256 {
257 _hash() = hashFn;
258 _equ() = equalKey;
259 }
260
263 template <class Iterator>
264 TfDenseHashMap(Iterator begin, Iterator end) {
265 insert(begin, end);
266 }
267
270 TfDenseHashMap(std::initializer_list<value_type> l) {
271 insert(l.begin(), l.end());
272 }
273
277 : _storage(rhs._storage) {
278 if (rhs._h) {
279 _h = std::make_unique<_HashMap>(*rhs._h);
280 }
281 }
285
289 if (this != &rhs) {
290 TfDenseHashMap temp(rhs);
291 temp.swap(*this);
292 }
293 return *this;
294 }
295
299
302 TfDenseHashMap &operator=(std::initializer_list<value_type> l) {
303 clear();
304 insert(l.begin(), l.end());
305 return *this;
306 }
307
310 bool operator==(const TfDenseHashMap &rhs) const {
311
312 if (size() != rhs.size())
313 return false;
314
315 //XXX: Should we compare the HashFn and EqualKey too?
316 const_iterator tend = end(), rend = rhs.end();
317
318 for(const_iterator iter = begin(); iter != tend; ++iter) {
319 const_iterator riter = rhs.find(iter->first);
320 if (riter == rend)
321 return false;
322 if (iter->second != riter->second)
323 return false;
324 }
325
326 return true;
327 }
328
329 bool operator!=(const TfDenseHashMap &rhs) const {
330 return !(*this == rhs);
331 }
332
335 void clear() {
336 _vec().clear();
337 _h.reset();
338 }
339
342 void swap(TfDenseHashMap &rhs) {
343 _storage.swap(rhs._storage);
344 _h.swap(rhs._h);
345 }
346
349 bool empty() const {
350 return _vec().empty();
351 }
352
355 size_t size() const {
356 return _vec().size();
357 }
358
362 return _vec().begin();
363 }
364
368 return _vec().end();
369 }
370
374 return _vec().begin();
375 }
376
380 return _vec().end();
381 }
382
385 iterator find(const key_type &k) {
386 if (_h) {
387 typename _HashMap::const_iterator iter = _h->find(k);
388 if (iter == _h->end())
389 return end();
390
391 return _vec().begin() + iter->second;
392 } else {
393 return _FindInVec(k);
394 }
395 }
396
399 const_iterator find(const key_type &k) const {
400 if (_h) {
401 typename _HashMap::const_iterator iter = _h->find(k);
402 if (iter == _h->end())
403 return end();
404
405 return _vec().begin() + iter->second;
406 } else {
407 return _FindInVec(k);
408 }
409 }
410
413 size_t count(const key_type &k) const {
414 return find(k) != end();
415 }
416
420 insert_result insert(const value_type &v) {
421 if (_h) {
422 // Attempt to insert the new index. If this fails, we can't insert
423 // v.
424 std::pair<typename _HashMap::iterator, bool> res =
425 _h->insert(std::make_pair(v.first, size()));
426
427 if (!res.second)
428 return insert_result(_vec().begin() + res.first->second, false);
429 } else {
430 // Bail if already inserted.
431 iterator iter = _FindInVec(v.first);
432 if (iter != end())
433 return insert_result(iter, false);
434 }
435
436 // Insert at end and create table if necessary.
437 _vec().push_back(_InternalValueType(v.first, v.second));
438 _CreateTableIfNeeded();
439
440 return insert_result(std::prev(end()), true);
441 }
442
446 template<class IteratorType>
447 void insert(IteratorType i0, IteratorType i1) {
448 // Assume elements are more often than not unique, so if the sum of the
449 // current size and the size of the range is greater than or equal to
450 // the threshold, we create the table immediately so we don't do m*n
451 // work before creating the table.
452 if (size() + std::distance(i0, i1) >= Threshold)
453 _CreateTable();
454
455 // Insert elements.
456 for(IteratorType iter = i0; iter != i1; ++iter)
457 insert(*iter);
458 }
459
463 template <class Iterator>
464 void insert_unique(Iterator begin, Iterator end) {
465 // Special-case empty container.
466 if (empty()) {
467 _vec().assign(begin, end);
468 _CreateTableIfNeeded();
469 } else {
470 // Just insert, since duplicate checking will use the hash.
471 insert(begin, end);
472 }
473 }
474
480 Data &operator[](const key_type &key) {
481 return insert(value_type(key, Data())).first->second;
482 }
483
486 size_t erase(const key_type &k) {
487
488 iterator iter = find(k);
489 if (iter != end()) {
490 erase(iter);
491 return 1;
492 }
493 return 0;
494 }
495
498 void erase(const iterator &iter) {
499
500 // Erase key from hash table if applicable.
501 if (_h)
502 _h->erase(iter->first);
503
504 // If we are not removing that last element...
505 if (iter != std::prev(end())) {
506
507 // Need to get the underlying vector iterator directly, because
508 // we want to operate on the vector.
509 typename _Vector::iterator vi = iter._GetUnderlyingIterator();
510
511 // ... move the last element into the erased placed.
512 vi->swap(_vec().back());
513
514 // ... and update the moved element's index.
515 if (_h)
516 (*_h)[vi->GetValue().first] = vi - _vec().begin();
517 }
518
519 _vec().pop_back();
520 }
521
524 void erase(iterator i0, iterator i1) {
525
526 if (_h) {
527 for(iterator iter = i0; iter != i1; ++iter)
528 _h->erase(iter->first);
529 }
530
531 typename _Vector::const_iterator vremain = _vec().erase(
532 i0._GetUnderlyingIterator(), i1._GetUnderlyingIterator());
533
534 if (_h) {
535 for(; vremain != _vec().end(); ++vremain)
536 (*_h)[vremain->GetValue().first] = vremain - _vec().begin();
537 }
538 }
539
543
544 // Shrink the vector to best size.
545 _vec().shrink_to_fit();
546
547 if (!_h)
548 return;
549
550 size_t sz = size();
551
552 // If we have a hash map and are underneath the threshold, discard it.
553 if (sz < Threshold) {
554
555 _h.reset();
556
557 } else {
558
559 // Otherwise, allocate a new hash map with the optimal size.
560 _h.reset(new _HashMap(sz, _hash(), _equ()));
561 for(size_t i=0; i<sz; ++i)
562 _h->insert(std::make_pair(_vec()[i].GetValue().first, i));
563 }
564 }
565
568 void reserve(size_t n) {
569 _vec().reserve(n);
570 }
571
573
574private:
575
576 // Helper to access the storage vector.
577 _Vector &_vec() {
578 return _storage.vector;
579 }
580
581 // Helper to access the hash functor.
582 HashFn &_hash() {
583 return _storage;
584 }
585
586 // Helper to access the equality functor.
587 EqualKey &_equ() {
588 return _storage;
589 }
590
591 // Helper to access the storage vector.
592 const _Vector &_vec() const {
593 return _storage.vector;
594 }
595
596 // Helper to access the hash functor.
597 const HashFn &_hash() const {
598 return _storage;
599 }
600
601 // Helper to access the equality functor.
602 const EqualKey &_equ() const {
603 return _storage;
604 }
605
606 // Helper to linear-search the vector for a key.
607 inline iterator _FindInVec(const key_type &k) {
608 _Vector &vec = _vec();
609 EqualKey &equ = _equ();
610 typename _Vector::iterator iter = vec.begin(), end = vec.end();
611 for (; iter != end; ++iter) {
612 if (equ(iter->GetValue().first, k))
613 break;
614 }
615 return iter;
616 }
617
618 // Helper to linear-search the vector for a key.
619 inline const_iterator _FindInVec(const key_type &k) const {
620 _Vector const &vec = _vec();
621 EqualKey const &equ = _equ();
622 typename _Vector::const_iterator iter = vec.begin(), end = vec.end();
623 for (; iter != end; ++iter) {
624 if (equ(iter->GetValue().first, k))
625 break;
626 }
627 return iter;
628 }
629
630 // Helper to create the acceleration table if size dictates.
631 inline void _CreateTableIfNeeded() {
632 if (size() >= Threshold) {
633 _CreateTable();
634 }
635 }
636
637 // Unconditionally create the acceleration table if it doesn't already
638 // exist.
639 inline void _CreateTable() {
640 if (!_h) {
641 _h.reset(new _HashMap(Threshold, _hash(), _equ()));
642 for(size_t i=0; i < size(); ++i)
643 _h->insert(std::make_pair(_vec()[i].GetValue().first, i));
644 }
645 }
646
647 // Since sizeof(EqualKey) == 0 and sizeof(HashFn) == 0 in many cases
648 // we use the empty base optimization to not pay a size penalty.
649 // In C++20, explore using [[no_unique_address]] as an alternative
650 // way to get this optimization.
651 struct ARCH_EMPTY_BASES _CompressedStorage :
652 private EqualKey, private HashFn {
653 static_assert(!std::is_same<EqualKey, HashFn>::value,
654 "EqualKey and HashFn must be distinct types.");
655 _CompressedStorage() = default;
656 _CompressedStorage(const EqualKey& equalKey, const HashFn& hashFn)
657 : EqualKey(equalKey), HashFn(hashFn) {}
658
659 void swap(_CompressedStorage& other) {
660 using std::swap;
661 vector.swap(other.vector);
662 swap(static_cast<EqualKey&>(*this), static_cast<EqualKey&>(other));
663 swap(static_cast<HashFn&>(*this), static_cast<HashFn&>(other));
664 }
665 _Vector vector;
666 friend class TfDenseHashMap;
667 };
668 _CompressedStorage _storage;
669
670 // Optional hash map that maps from keys to vector indices.
671 std::unique_ptr<_HashMap> _h;
672};
673
674PXR_NAMESPACE_CLOSE_SCOPE
675
676#endif // PXR_BASE_TF_DENSE_HASH_MAP_H
Define function attributes.
#define ARCH_EMPTY_BASES
Macro to begin the definition of a class that is using private inheritance to take advantage of the e...
Definition: attributes.h:170
This is a space efficient container that mimics the TfHashMap API that uses a vector for storage when...
Definition: denseHashMap.h:58
Data & operator[](const key_type &key)
Indexing operator.
Definition: denseHashMap.h:480
size_t size() const
Returns the size of the map.
Definition: denseHashMap.h:355
TfDenseHashMap(std::initializer_list< value_type > l)
Construct from an initializer_list.
Definition: denseHashMap.h:270
const_iterator begin() const
Returns an const_iterator pointing to the beginning of the map.
Definition: denseHashMap.h:373
TfDenseHashMap(const HashFn &hashFn=HashFn(), const EqualKey &equalKey=EqualKey())
Ctor.
Definition: denseHashMap.h:253
size_t count(const key_type &k) const
Returns the number of elements with key k.
Definition: denseHashMap.h:413
_IteratorBase< const value_type, typename _Vector::const_iterator > const_iterator
An iterator type for this map.
Definition: denseHashMap.h:244
size_t erase(const key_type &k)
Erase element with key k.
Definition: denseHashMap.h:486
const_iterator find(const key_type &k) const
Finds the element with key k.
Definition: denseHashMap.h:399
void insert(IteratorType i0, IteratorType i1)
Insert a range into the hash map.
Definition: denseHashMap.h:447
iterator find(const key_type &k)
Finds the element with key k.
Definition: denseHashMap.h:385
TfDenseHashMap & operator=(TfDenseHashMap &&rhs)=default
Move assignment operator.
void shrink_to_fit()
Optimize storage space.
Definition: denseHashMap.h:542
bool empty() const
true if the map's size is 0.
Definition: denseHashMap.h:349
bool operator==(const TfDenseHashMap &rhs) const
Equality operator.
Definition: denseHashMap.h:310
void erase(const iterator &iter)
Erases element pointed to by iter.
Definition: denseHashMap.h:498
TfDenseHashMap(Iterator begin, Iterator end)
Construct with range.
Definition: denseHashMap.h:264
TfDenseHashMap & operator=(const TfDenseHashMap &rhs)
Copy assignment operator.
Definition: denseHashMap.h:288
_IteratorBase< value_type, typename _Vector::iterator > iterator
An iterator type for this map.
Definition: denseHashMap.h:238
std::pair< iterator, bool > insert_result
Return type for insert() method.
Definition: denseHashMap.h:247
insert_result insert(const value_type &v)
Returns a pair of <iterator, bool> where iterator points to the element in the list and bool is true ...
Definition: denseHashMap.h:420
void clear()
Erases all of the elements.
Definition: denseHashMap.h:335
iterator end()
Returns an const_iterator pointing to the end of the map.
Definition: denseHashMap.h:367
void insert_unique(Iterator begin, Iterator end)
Insert a range of unique elements into the container.
Definition: denseHashMap.h:464
const_iterator end() const
Returns an const_iterator pointing to the end of the map.
Definition: denseHashMap.h:379
void swap(TfDenseHashMap &rhs)
Swaps the contents of two maps.
Definition: denseHashMap.h:342
iterator begin()
Returns an const_iterator pointing to the beginning of the map.
Definition: denseHashMap.h:361
void erase(iterator i0, iterator i1)
Erases a range from the map.
Definition: denseHashMap.h:524
TfDenseHashMap(const TfDenseHashMap &rhs)
Copy Ctor.
Definition: denseHashMap.h:276
TfDenseHashMap(TfDenseHashMap &&rhs)=default
Move Ctor.
void reserve(size_t n)
Reserve space.
Definition: denseHashMap.h:568
TfDenseHashMap & operator=(std::initializer_list< value_type > l)
Assignment from an initializer_list.
Definition: denseHashMap.h:302