HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
denseHashMap.h
Go to the documentation of this file.
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 #ifndef PXR_BASE_TF_DENSE_HASH_MAP_H
8 #define PXR_BASE_TF_DENSE_HASH_MAP_H
9 
10 /// \file tf/denseHashMap.h
11 
12 #include "pxr/pxr.h"
14 #include "pxr/base/tf/hashmap.h"
15 
16 #include <memory>
17 #include <vector>
18 
20 
21 /// \class TfDenseHashMap
22 ///
23 /// This is a space efficient container that mimics the TfHashMap API that
24 /// uses a vector for storage when the size of the map is small.
25 ///
26 /// When the map gets bigger than \p Threshold a TfHashMap is allocated
27 /// that is used to accelerate lookup in the vector.
28 ///
29 /// \warning This differs from a TfHashMap in so far that inserting and
30 /// removing elements invalidate all iterators of the container.
31 ///
32 template <
33  class Key,
34  class Data,
35  class HashFn,
36  class EqualKey = std::equal_to<Key>,
37  unsigned Threshold = 128
38 >
39 
41 {
42 public:
43 
44  typedef std::pair<const Key, Data> value_type;
45  typedef Key key_type;
46  typedef Data mapped_type;
47 
48 ////////////////////////////////////////////////////////////////////////////////
49 
50 private:
51 
52  // This helper implements a std::pair with an assignment operator that
53  // uses placement new instead of assignment. The benefit here is that
54  // the two elements of the pair may be const.
55  //
56  struct _InternalValueType
57  {
58  _InternalValueType() {}
59 
60  _InternalValueType(const Key &k, const Data &d)
61  : _value(k, d) {}
62 
63  _InternalValueType &operator=(const _InternalValueType &rhs) {
64 
65  if (this != &rhs) {
66  // Since value_type's first member is const we need to
67  // use placement new to put the new element in place. Just
68  // make sure we destruct the element we are about to overwrite.
69  _value.value_type::~value_type();
70  new (&_value) value_type(rhs.GetValue());
71  }
72 
73  return *this;
74  }
75 
76  value_type &GetValue() {
77  return _value;
78  }
79 
80  const value_type &GetValue() const {
81  return _value;
82  }
83 
84  void swap(_InternalValueType &rhs) {
85  using std::swap;
86 
87  // We do this in order to take advantage of a potentially fast
88  // swap implementation.
89  Key tmp = _value.first;
90 
91  _value.first.Key::~Key();
92  new (const_cast<Key *>(&_value.first)) Key(rhs._value.first);
93 
94  rhs._value.first.Key::~Key();
95  new (const_cast<Key *>(&rhs._value.first)) Key(tmp);
96 
97  swap(_value.second, rhs._value.second);
98  }
99 
100  private:
101 
102  // Data hold by _InternalValueType. Note that the key portion of
103  // value_type maybe const.
104  value_type _value;
105  };
106 
107  // The vector type holding all data for this dense hash map.
108  typedef std::vector<_InternalValueType> _Vector;
109 
110  // The hash map used when the map holds more than Threshold elements.
112 
113  // Note that we don't just use _Vector::iterator for accessing elements
114  // of the TfDenseHashMap. This is because the vector's iterator would
115  // expose the _InternalValueType _including_ its assignment operator
116  // that allows overwriting keys.
117  //
118  // Clearly not a good thing.
119  //
120  // Therefore we create an iterator that uses the map's value_type as
121  // externally visible type.
122  //
123  template <class ElementType, class UnderlyingIterator>
124  class _IteratorBase
125  {
126  public:
127  using iterator_category = std::bidirectional_iterator_tag;
128  using value_type = ElementType;
129  using reference = ElementType&;
130  using pointer = ElementType*;
131  using difference_type = typename UnderlyingIterator::difference_type;
132 
133  // Empty ctor.
134  _IteratorBase() = default;
135 
136  // Allow conversion of an iterator to a const_iterator.
137  template<class OtherIteratorType>
138  _IteratorBase(const OtherIteratorType &rhs)
139  : _iter(rhs._GetUnderlyingIterator()) {}
140 
141  reference operator*() const { return dereference(); }
142  pointer operator->() const { return &(dereference()); }
143 
144  _IteratorBase& operator++() {
145  increment();
146  return *this;
147  }
148 
149  _IteratorBase& operator--() {
150  decrement();
151  return *this;
152  }
153 
154  _IteratorBase operator++(int) {
155  _IteratorBase result(*this);
156  increment();
157  return result;
158  }
159 
160  _IteratorBase operator--(int) {
161  _IteratorBase result(*this);
162  decrement();
163  return result;
164  }
165 
166  template <class OtherIteratorType>
167  bool operator==(const OtherIteratorType& other) const {
168  return equal(other);
169  }
170 
171  template <class OtherIteratorType>
172  bool operator!=(const OtherIteratorType& other) const {
173  return !equal(other);
174  }
175 
176  private:
177 
178  friend class TfDenseHashMap;
179 
180  // Ctor from an underlying iterator.
181  _IteratorBase(const UnderlyingIterator &iter)
182  : _iter(iter) {}
183 
184  template<class OtherIteratorType>
185  bool equal(const OtherIteratorType &rhs) const {
186  return _iter == rhs._iter;
187  }
188 
189  void increment() {
190  ++_iter;
191  }
192 
193  void decrement() {
194  --_iter;
195  }
196 
197  ElementType &dereference() const {
198  // The dereference() method accesses the correct value_type (ie.
199  // the one with potentially const key_type. This way, clients don't
200  // see the assignment operator of _InternalValueType.
201  return _iter->GetValue();
202  }
203 
204  UnderlyingIterator _GetUnderlyingIterator() const {
205  return _iter;
206  }
207 
208  private:
209 
210  UnderlyingIterator _iter;
211  };
212 
213 ////////////////////////////////////////////////////////////////////////////////
214 
215 public:
216 
217  /// An iterator type for this map. Note that it provides access to the
218  /// This::value_type only.
219  typedef
220  _IteratorBase<value_type, typename _Vector::iterator>
222 
223  /// An iterator type for this map. Note that it provides access to the
224  /// This::value_type only.
225  typedef
226  _IteratorBase<const value_type, typename _Vector::const_iterator>
228 
229  /// Return type for insert() method.
230  typedef std::pair<iterator, bool> insert_result;
231 
232 public:
233 
234  /// Ctor.
235  ///
236  explicit TfDenseHashMap(
237  const HashFn &hashFn = HashFn(),
238  const EqualKey &equalKey = EqualKey())
239  {
240  _hash() = hashFn;
241  _equ() = equalKey;
242  }
243 
244  /// Construct with range.
245  ///
246  template <class Iterator>
247  TfDenseHashMap(Iterator begin, Iterator end) {
248  insert(begin, end);
249  }
250 
251  /// Construct from an initializer_list.
252  ///
253  TfDenseHashMap(std::initializer_list<value_type> l) {
254  insert(l.begin(), l.end());
255  }
256 
257  /// Copy Ctor.
258  ///
260  : _storage(rhs._storage) {
261  if (rhs._h) {
262  _h = std::make_unique<_HashMap>(*rhs._h);
263  }
264  }
265  /// Move Ctor.
266  ///
267  TfDenseHashMap(TfDenseHashMap &&rhs) = default;
268 
269  /// Copy assignment operator.
270  ///
272  if (this != &rhs) {
273  TfDenseHashMap temp(rhs);
274  temp.swap(*this);
275  }
276  return *this;
277  }
278 
279  /// Move assignment operator.
280  ///
281  TfDenseHashMap &operator=(TfDenseHashMap &&rhs) = default;
282 
283  /// Assignment from an initializer_list.
284  ///
285  TfDenseHashMap &operator=(std::initializer_list<value_type> l) {
286  clear();
287  insert(l.begin(), l.end());
288  return *this;
289  }
290 
291  /// Equality operator.
292  ///
293  bool operator==(const TfDenseHashMap &rhs) const {
294 
295  if (size() != rhs.size())
296  return false;
297 
298  //XXX: Should we compare the HashFn and EqualKey too?
299  const_iterator tend = end(), rend = rhs.end();
300 
301  for(const_iterator iter = begin(); iter != tend; ++iter) {
302  const_iterator riter = rhs.find(iter->first);
303  if (riter == rend)
304  return false;
305  if (iter->second != riter->second)
306  return false;
307  }
308 
309  return true;
310  }
311 
312  bool operator!=(const TfDenseHashMap &rhs) const {
313  return !(*this == rhs);
314  }
315 
316  /// Erases all of the elements
317  ///
318  void clear() {
319  _vec().clear();
320  _h.reset();
321  }
322 
323  /// Swaps the contents of two maps.
324  ///
325  void swap(TfDenseHashMap &rhs) {
326  _storage.swap(rhs._storage);
327  _h.swap(rhs._h);
328  }
329 
330  /// \c true if the \c map's size is 0.
331  ///
332  bool empty() const {
333  return _vec().empty();
334  }
335 
336  /// Returns the size of the map.
337  ///
338  size_t size() const {
339  return _vec().size();
340  }
341 
342  /// Returns an const_iterator pointing to the beginning of the map.
343  ///
345  return _vec().begin();
346  }
347 
348  /// Returns an const_iterator pointing to the end of the map.
349  ///
351  return _vec().end();
352  }
353 
354  /// Returns an const_iterator pointing to the beginning of the map.
355  ///
357  return _vec().begin();
358  }
359 
360  /// Returns an const_iterator pointing to the end of the map.
361  ///
362  const_iterator end() const {
363  return _vec().end();
364  }
365 
366  /// Finds the element with key \p k.
367  ///
368  iterator find(const key_type &k) {
369  if (_h) {
370  typename _HashMap::const_iterator iter = _h->find(k);
371  if (iter == _h->end())
372  return end();
373 
374  return _vec().begin() + iter->second;
375  } else {
376  return _FindInVec(k);
377  }
378  }
379 
380  /// Finds the element with key \p k.
381  ///
382  const_iterator find(const key_type &k) const {
383  if (_h) {
384  typename _HashMap::const_iterator iter = _h->find(k);
385  if (iter == _h->end())
386  return end();
387 
388  return _vec().begin() + iter->second;
389  } else {
390  return _FindInVec(k);
391  }
392  }
393 
394  /// Returns the number of elements with key \p k. Which is either 0 or 1.
395  ///
396  size_t count(const key_type &k) const {
397  return find(k) != end();
398  }
399 
400  /// Returns a pair of <iterator, bool> where iterator points to the element
401  /// in the list and bool is true if a new element was inserted.
402  ///
404  if (_h) {
405  // Attempt to insert the new index. If this fails, we can't insert
406  // v.
407  std::pair<typename _HashMap::iterator, bool> res =
408  _h->insert(std::make_pair(v.first, size()));
409 
410  if (!res.second)
411  return insert_result(_vec().begin() + res.first->second, false);
412  } else {
413  // Bail if already inserted.
414  iterator iter = _FindInVec(v.first);
415  if (iter != end())
416  return insert_result(iter, false);
417  }
418 
419  // Insert at end and create table if necessary.
420  _vec().push_back(_InternalValueType(v.first, v.second));
421  _CreateTableIfNeeded();
422 
423  return insert_result(std::prev(end()), true);
424  }
425 
426  /// Insert a range into the hash map. Note that \p i0 and \p i1 can't
427  /// point into the hash map.
428  ///
429  template<class IteratorType>
430  void insert(IteratorType i0, IteratorType i1) {
431  // Assume elements are more often than not unique, so if the sum of the
432  // current size and the size of the range is greater than or equal to
433  // the threshold, we create the table immediately so we don't do m*n
434  // work before creating the table.
435  if (size() + std::distance(i0, i1) >= Threshold)
436  _CreateTable();
437 
438  // Insert elements.
439  for(IteratorType iter = i0; iter != i1; ++iter)
440  insert(*iter);
441  }
442 
443  /// Insert a range of unique elements into the container. [begin, end)
444  /// *must not* contain any duplicate elements.
445  ///
446  template <class Iterator>
447  void insert_unique(Iterator begin, Iterator end) {
448  // Special-case empty container.
449  if (empty()) {
450  _vec().assign(begin, end);
451  _CreateTableIfNeeded();
452  } else {
453  // Just insert, since duplicate checking will use the hash.
454  insert(begin, end);
455  }
456  }
457 
458  /// Indexing operator. Inserts a default constructed DataType() for \p key
459  /// if there is no value for \p key already.
460  ///
461  /// Returns a reference to the value type for \p key.
462  ///
463  Data &operator[](const key_type &key) {
464  return insert(value_type(key, Data())).first->second;
465  }
466 
467  /// Erase element with key \p k. Returns the number of elements erased.
468  ///
469  size_t erase(const key_type &k) {
470 
471  iterator iter = find(k);
472  if (iter != end()) {
473  erase(iter);
474  return 1;
475  }
476  return 0;
477  }
478 
479  /// Erases element pointed to by \p iter.
480  ///
481  void erase(const iterator &iter) {
482 
483  // Erase key from hash table if applicable.
484  if (_h)
485  _h->erase(iter->first);
486 
487  // If we are not removing that last element...
488  if (iter != std::prev(end())) {
489 
490  // Need to get the underlying vector iterator directly, because
491  // we want to operate on the vector.
492  typename _Vector::iterator vi = iter._GetUnderlyingIterator();
493 
494  // ... move the last element into the erased placed.
495  vi->swap(_vec().back());
496 
497  // ... and update the moved element's index.
498  if (_h)
499  (*_h)[vi->GetValue().first] = vi - _vec().begin();
500  }
501 
502  _vec().pop_back();
503  }
504 
505  /// Erases a range from the map.
506  ///
507  void erase(iterator i0, iterator i1) {
508 
509  if (_h) {
510  for(iterator iter = i0; iter != i1; ++iter)
511  _h->erase(iter->first);
512  }
513 
514  typename _Vector::const_iterator vremain = _vec().erase(
515  i0._GetUnderlyingIterator(), i1._GetUnderlyingIterator());
516 
517  if (_h) {
518  for(; vremain != _vec().end(); ++vremain)
519  (*_h)[vremain->GetValue().first] = vremain - _vec().begin();
520  }
521  }
522 
523  /// Optimize storage space.
524  ///
525  void shrink_to_fit() {
526 
527  // Shrink the vector to best size.
528  _vec().shrink_to_fit();
529 
530  if (!_h)
531  return;
532 
533  size_t sz = size();
534 
535  // If we have a hash map and are underneath the threshold, discard it.
536  if (sz < Threshold) {
537 
538  _h.reset();
539 
540  } else {
541 
542  // Otherwise, allocate a new hash map with the optimal size.
543  _h.reset(new _HashMap(sz, _hash(), _equ()));
544  for(size_t i=0; i<sz; ++i)
545  _h->insert(std::make_pair(_vec()[i].GetValue().first, i));
546  }
547  }
548 
549  /// Reserve space.
550  ///
551  void reserve(size_t n) {
552  _vec().reserve(n);
553  }
554 
555 ////////////////////////////////////////////////////////////////////////////////
556 
557 private:
558 
559  // Helper to access the storage vector.
560  _Vector &_vec() {
561  return _storage.vector;
562  }
563 
564  // Helper to access the hash functor.
565  HashFn &_hash() {
566  return _storage;
567  }
568 
569  // Helper to access the equality functor.
570  EqualKey &_equ() {
571  return _storage;
572  }
573 
574  // Helper to access the storage vector.
575  const _Vector &_vec() const {
576  return _storage.vector;
577  }
578 
579  // Helper to access the hash functor.
580  const HashFn &_hash() const {
581  return _storage;
582  }
583 
584  // Helper to access the equality functor.
585  const EqualKey &_equ() const {
586  return _storage;
587  }
588 
589  // Helper to linear-search the vector for a key.
590  inline iterator _FindInVec(const key_type &k) {
591  _Vector &vec = _vec();
592  EqualKey &equ = _equ();
593  typename _Vector::iterator iter = vec.begin(), end = vec.end();
594  for (; iter != end; ++iter) {
595  if (equ(iter->GetValue().first, k))
596  break;
597  }
598  return iter;
599  }
600 
601  // Helper to linear-search the vector for a key.
602  inline const_iterator _FindInVec(const key_type &k) const {
603  _Vector const &vec = _vec();
604  EqualKey const &equ = _equ();
605  typename _Vector::const_iterator iter = vec.begin(), end = vec.end();
606  for (; iter != end; ++iter) {
607  if (equ(iter->GetValue().first, k))
608  break;
609  }
610  return iter;
611  }
612 
613  // Helper to create the acceleration table if size dictates.
614  inline void _CreateTableIfNeeded() {
615  if (size() >= Threshold) {
616  _CreateTable();
617  }
618  }
619 
620  // Unconditionally create the acceleration table if it doesn't already
621  // exist.
622  inline void _CreateTable() {
623  if (!_h) {
624  _h.reset(new _HashMap(Threshold, _hash(), _equ()));
625  for(size_t i=0; i < size(); ++i)
626  _h->insert(std::make_pair(_vec()[i].GetValue().first, i));
627  }
628  }
629 
630  // Since sizeof(EqualKey) == 0 and sizeof(HashFn) == 0 in many cases
631  // we use the empty base optimization to not pay a size penalty.
632  // In C++20, explore using [[no_unique_address]] as an alternative
633  // way to get this optimization.
634  struct ARCH_EMPTY_BASES _CompressedStorage :
635  private EqualKey, private HashFn {
637  "EqualKey and HashFn must be distinct types.");
638  _CompressedStorage() = default;
639  _CompressedStorage(const EqualKey& equalKey, const HashFn& hashFn)
640  : EqualKey(equalKey), HashFn(hashFn) {}
641 
642  void swap(_CompressedStorage& other) {
643  using std::swap;
644  vector.swap(other.vector);
645  swap(static_cast<EqualKey&>(*this), static_cast<EqualKey&>(other));
646  swap(static_cast<HashFn&>(*this), static_cast<HashFn&>(other));
647  }
648  _Vector vector;
649  friend class TfDenseHashMap;
650  };
651  _CompressedStorage _storage;
652 
653  // Optional hash map that maps from keys to vector indices.
654  std::unique_ptr<_HashMap> _h;
655 };
656 
658 
659 #endif // PXR_BASE_TF_DENSE_HASH_MAP_H
GLint first
Definition: glcorearb.h:405
_IteratorBase< const value_type, typename _Vector::const_iterator > const_iterator
Definition: denseHashMap.h:227
_Base::const_iterator const_iterator
Definition: hashmap.h:266
void shrink_to_fit()
Definition: denseHashMap.h:525
void swap(UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &a, UT::ArraySet< Key, MULTI, MAX_LOAD_FACTOR_256, Clearer, Hash, KeyEqual > &b)
Definition: UT_ArraySet.h:1699
TfDenseHashMap & operator=(std::initializer_list< value_type > l)
Definition: denseHashMap.h:285
const GLdouble * v
Definition: glcorearb.h:837
const_iterator begin() const
Definition: denseHashMap.h:356
GLsizei const GLfloat * value
Definition: glcorearb.h:824
size_t count(const key_type &k) const
Definition: denseHashMap.h:396
void erase(const iterator &iter)
Definition: denseHashMap.h:481
IMATH_HOSTDEVICE constexpr bool equal(T1 a, T2 b, T3 t) IMATH_NOEXCEPT
Definition: ImathFun.h:105
TfDenseHashMap(const HashFn &hashFn=HashFn(), const EqualKey &equalKey=EqualKey())
Definition: denseHashMap.h:236
bool operator!=(const TfDenseHashMap &rhs) const
Definition: denseHashMap.h:312
**But if you need a result
Definition: thread.h:622
void swap(TfDenseHashMap &rhs)
Definition: denseHashMap.h:325
Data & operator[](const key_type &key)
Definition: denseHashMap.h:463
std::pair< const Key, Data > value_type
Definition: denseHashMap.h:44
const_iterator end() const
Definition: denseHashMap.h:362
GLdouble n
Definition: glcorearb.h:2008
TfDenseHashMap(const TfDenseHashMap &rhs)
Definition: denseHashMap.h:259
GLuint GLuint end
Definition: glcorearb.h:475
iterator find(const key_type &k)
Definition: denseHashMap.h:368
IMATH_HOSTDEVICE constexpr Color4< T > operator*(S a, const Color4< T > &v) IMATH_NOEXCEPT
Reverse multiplication: S * Color4.
Definition: ImathColor.h:732
size_t erase(const key_type &k)
Definition: denseHashMap.h:469
GLint i1
Definition: glad.h:2724
TfDenseHashMap(std::initializer_list< value_type > l)
Definition: denseHashMap.h:253
iterator end()
Definition: denseHashMap.h:350
Definition: path.h:273
void reserve(size_t n)
Definition: denseHashMap.h:551
void insert_unique(Iterator begin, Iterator end)
Definition: denseHashMap.h:447
std::pair< iterator, bool > insert_result
Return type for insert() method.
Definition: denseHashMap.h:230
GLsizeiptr size
Definition: glcorearb.h:664
bool operator==(const TfDenseHashMap &rhs) const
Definition: denseHashMap.h:293
GLenum void ** pointer
Definition: glcorearb.h:810
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1425
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:74
const_iterator find(const key_type &k) const
Definition: denseHashMap.h:382
insert_result insert(const value_type &v)
Definition: denseHashMap.h:403
void insert(IteratorType i0, IteratorType i1)
Definition: denseHashMap.h:430
void erase(iterator i0, iterator i1)
Definition: denseHashMap.h:507
TfDenseHashMap & operator=(const TfDenseHashMap &rhs)
Definition: denseHashMap.h:271
TfDenseHashMap(Iterator begin, Iterator end)
Definition: denseHashMap.h:247
SIM_API const UT_StringHolder distance
iterator begin()
Definition: denseHashMap.h:344
that also have some descendant prim *whose name begins with which in turn has a child named baz where *the predicate and *a name There is also one special expression reference
size_t size() const
Definition: denseHashMap.h:338
bool empty() const
Definition: denseHashMap.h:332
_IteratorBase< value_type, typename _Vector::iterator > iterator
Definition: denseHashMap.h:221