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