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  /// Assignment operator.
250  ///
252  swap(rhs);
253  return *this;
254  }
255 
256  /// Assignment from an initializer_list.
257  ///
258  TfDenseHashMap &operator=(std::initializer_list<value_type> l) {
259  clear();
260  insert(l.begin(), l.end());
261  return *this;
262  }
263 
264  /// Equality operator.
265  ///
266  bool operator==(const TfDenseHashMap &rhs) const {
267 
268  if (size() != rhs.size())
269  return false;
270 
271  //XXX: Should we compare the HashFn and EqualKey too?
272  const_iterator tend = end(), rend = rhs.end();
273 
274  for(const_iterator iter = begin(); iter != tend; ++iter) {
275  const_iterator riter = rhs.find(iter->first);
276  if (riter == rend)
277  return false;
278  if (iter->second != riter->second)
279  return false;
280  }
281 
282  return true;
283  }
284 
285  bool operator!=(const TfDenseHashMap &rhs) const {
286  return !(*this == rhs);
287  }
288 
289  /// Erases all of the elements
290  ///
291  void clear() {
292  _vec().clear();
293  _h.reset();
294  }
295 
296  /// Swaps the contents of two maps.
297  ///
298  void swap(TfDenseHashMap &rhs) {
299  _vectorHashFnEqualFn.swap(rhs._vectorHashFnEqualFn);
300  _h.swap(rhs._h);
301  }
302 
303  /// \c true if the \c map's size is 0.
304  ///
305  bool empty() const {
306  return _vec().empty();
307  }
308 
309  /// Returns the size of the map.
310  ///
311  size_t size() const {
312  return _vec().size();
313  }
314 
315  /// Returns an const_iterator pointing to the beginning of the map.
316  ///
318  return _vec().begin();
319  }
320 
321  /// Returns an const_iterator pointing to the end of the map.
322  ///
324  return _vec().end();
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  ///
335  const_iterator end() const {
336  return _vec().end();
337  }
338 
339  /// Finds the element with key \p k.
340  ///
341  iterator find(const key_type &k) {
342  if (_h) {
343  typename _HashMap::const_iterator iter = _h->find(k);
344  if (iter == _h->end())
345  return end();
346 
347  return _vec().begin() + iter->second;
348  } else {
349  return _FindInVec(k);
350  }
351  }
352 
353  /// Finds the element with key \p k.
354  ///
355  const_iterator find(const key_type &k) const {
356  if (_h) {
357  typename _HashMap::const_iterator iter = _h->find(k);
358  if (iter == _h->end())
359  return end();
360 
361  return _vec().begin() + iter->second;
362  } else {
363  return _FindInVec(k);
364  }
365  }
366 
367  /// Returns the number of elements with key \p k. Which is either 0 or 1.
368  ///
369  size_t count(const key_type &k) const {
370  return find(k) != end();
371  }
372 
373  /// Returns a pair of <iterator, bool> where iterator points to the element
374  /// in the list and bool is true if a new element was inserted.
375  ///
377  if (_h) {
378  // Attempt to insert the new index. If this fails, we can't insert
379  // v.
380  std::pair<typename _HashMap::iterator, bool> res =
381  _h->insert(std::make_pair(v.first, size()));
382 
383  if (!res.second)
384  return insert_result(_vec().begin() + res.first->second, false);
385  } else {
386  // Bail if already inserted.
387  iterator iter = _FindInVec(v.first);
388  if (iter != end())
389  return insert_result(iter, false);
390  }
391 
392  // Insert at end and create table if necessary.
393  _vec().push_back(_InternalValueType(v.first, v.second));
394  _CreateTableIfNeeded();
395 
396  return insert_result(std::prev(end()), true);
397  }
398 
399  /// Insert a range into the hash map. Note that \p i0 and \p i1 can't
400  /// point into the hash map.
401  ///
402  template<class IteratorType>
403  void insert(IteratorType i0, IteratorType i1) {
404  // Assume elements are more often than not unique, so if the sum of the
405  // current size and the size of the range is greater than or equal to
406  // the threshold, we create the table immediately so we don't do m*n
407  // work before creating the table.
408  if (size() + std::distance(i0, i1) >= Threshold)
409  _CreateTable();
410 
411  // Insert elements.
412  for(IteratorType iter = i0; iter != i1; ++iter)
413  insert(*iter);
414  }
415 
416  /// Insert a range of unique elements into the container. [begin, end)
417  /// *must not* contain any duplicate elements.
418  ///
419  template <class Iterator>
420  void insert_unique(Iterator begin, Iterator end) {
421  // Special-case empty container.
422  if (empty()) {
423  _vec().assign(begin, end);
424  _CreateTableIfNeeded();
425  } else {
426  // Just insert, since duplicate checking will use the hash.
427  insert(begin, end);
428  }
429  }
430 
431  /// Indexing operator. Inserts a default constructed DataType() for \p key
432  /// if there is no value for \p key already.
433  ///
434  /// Returns a reference to the value type for \p key.
435  ///
436  Data &operator[](const key_type &key) {
437  return insert(value_type(key, Data())).first->second;
438  }
439 
440  /// Erase element with key \p k. Returns the number of elements erased.
441  ///
442  size_t erase(const key_type &k) {
443 
444  iterator iter = find(k);
445  if (iter != end()) {
446  erase(iter);
447  return 1;
448  }
449  return 0;
450  }
451 
452  /// Erases element pointed to by \p iter.
453  ///
454  void erase(const iterator &iter) {
455 
456  // Erase key from hash table if applicable.
457  if (_h)
458  _h->erase(iter->first);
459 
460  // If we are not removing that last element...
461  if (iter != std::prev(end())) {
462 
463  // Need to get the underlying vector iterator directly, because
464  // we want to operate on the vector.
465  typename _Vector::iterator vi = iter._GetUnderlyingIterator();
466 
467  // ... move the last element into the erased placed.
468  vi->swap(_vec().back());
469 
470  // ... and update the moved element's index.
471  if (_h)
472  (*_h)[vi->GetValue().first] = vi - _vec().begin();
473  }
474 
475  _vec().pop_back();
476  }
477 
478  /// Erases a range from the map.
479  ///
480  void erase(iterator i0, iterator i1) {
481 
482  if (_h) {
483  for(iterator iter = i0; iter != i1; ++iter)
484  _h->erase(iter->first);
485  }
486 
487  typename _Vector::const_iterator vremain = _vec().erase(
488  i0._GetUnderlyingIterator(), i1._GetUnderlyingIterator());
489 
490  if (_h) {
491  for(; vremain != _vec().end(); ++vremain)
492  (*_h)[vremain->GetValue().first] = vremain - _vec().begin();
493  }
494  }
495 
496  /// Optimize storage space.
497  ///
498  void shrink_to_fit() {
499 
500  // Shrink the vector to best size.
501  //XXX: When switching to c++0x we should call _vec().shrink_to_fit().
502  _Vector(_vec()).swap(_vec());
503 
504  if (!_h)
505  return;
506 
507  size_t sz = size();
508 
509  // If we have a hash map and are underneath the threshold, discard it.
510  if (sz < Threshold) {
511 
512  _h.reset();
513 
514  } else {
515 
516  // Otherwise, allocate a new hash map with the optimal size.
517  _h.reset(new _HashMap(sz, _hash(), _equ()));
518  for(size_t i=0; i<sz; ++i)
519  _h->insert(std::make_pair(_vec()[i].GetValue().first, i));
520  }
521  }
522 
523  /// Reserve space.
524  ///
525  void reserve(size_t n) {
526  _vec().reserve(n);
527  }
528 
529 ////////////////////////////////////////////////////////////////////////////////
530 
531 private:
532 
533  // Helper to access the storage vector.
534  _Vector &_vec() {
535  return _vectorHashFnEqualFn.first().first();
536  }
537 
538  // Helper to access the hash functor.
539  HashFn &_hash() {
540  return _vectorHashFnEqualFn.first().second();
541  }
542 
543  // Helper to access the equality functor.
544  EqualKey &_equ() {
545  return _vectorHashFnEqualFn.second();
546  }
547 
548  // Helper to access the storage vector.
549  const _Vector &_vec() const {
550  return _vectorHashFnEqualFn.first().first();
551  }
552 
553  // Helper to access the hash functor.
554  const HashFn &_hash() const {
555  return _vectorHashFnEqualFn.first().second();
556  }
557 
558  // Helper to access the equality functor.
559  const EqualKey &_equ() const {
560  return _vectorHashFnEqualFn.second();
561  }
562 
563  // Helper to linear-search the vector for a key.
564  inline iterator _FindInVec(const key_type &k) {
565  _Vector &vec = _vec();
566  EqualKey &equ = _equ();
567  typename _Vector::iterator iter = vec.begin(), end = vec.end();
568  for (; iter != end; ++iter) {
569  if (equ(iter->GetValue().first, k))
570  break;
571  }
572  return iter;
573  }
574 
575  // Helper to linear-search the vector for a key.
576  inline const_iterator _FindInVec(const key_type &k) const {
577  _Vector const &vec = _vec();
578  EqualKey const &equ = _equ();
579  typename _Vector::const_iterator iter = vec.begin(), end = vec.end();
580  for (; iter != end; ++iter) {
581  if (equ(iter->GetValue().first, k))
582  break;
583  }
584  return iter;
585  }
586 
587  // Helper to create the acceleration table if size dictates.
588  inline void _CreateTableIfNeeded() {
589  if (size() >= Threshold) {
590  _CreateTable();
591  }
592  }
593 
594  // Unconditionally create the acceleration table if it doesn't already
595  // exist.
596  inline void _CreateTable() {
597  if (!_h) {
598  _h.reset(new _HashMap(Threshold, _hash(), _equ()));
599  for(size_t i=0; i < size(); ++i)
600  _h->insert(std::make_pair(_vec()[i].GetValue().first, i));
601  }
602  }
603 
604  // Vector holding all elements along with the EqualKey functor. Since
605  // sizeof(EqualKey) == 0 in many cases we use a compressed_pair to not
606  // pay a size penalty.
607 
608  typedef
609  hboost::compressed_pair<
610  hboost::compressed_pair<_Vector, HashFn>,
611  EqualKey>
612  _VectorHashFnEqualFn;
613 
614  _VectorHashFnEqualFn _vectorHashFnEqualFn;
615 
616  // Optional hash map that maps from keys to vector indices.
617  std::unique_ptr<_HashMap> _h;
618 };
619 
621 
622 #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
GLsizeiptr size
Definition: glew.h:1681
void shrink_to_fit()
Definition: denseHashMap.h:498
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:258
const_iterator begin() const
Definition: denseHashMap.h:329
size_t count(const key_type &k) const
Definition: denseHashMap.h:369
void erase(const iterator &iter)
Definition: denseHashMap.h:454
const GLint * first
Definition: glew.h:1528
TfDenseHashMap(const HashFn &hashFn=HashFn(), const EqualKey &equalKey=EqualKey())
Definition: denseHashMap.h:220
GLdouble l
Definition: glew.h:9122
bool operator!=(const TfDenseHashMap &rhs) const
Definition: denseHashMap.h:285
const GLdouble * v
Definition: glew.h:1391
void swap(TfDenseHashMap &rhs)
Definition: denseHashMap.h:298
Data & operator[](const key_type &key)
Definition: denseHashMap.h:436
std::pair< const Key, Data > value_type
Definition: denseHashMap.h:63
const_iterator end() const
Definition: denseHashMap.h:335
TfDenseHashMap(const TfDenseHashMap &rhs)
Definition: denseHashMap.h:243
GLuint GLuint end
Definition: glew.h:1253
GLsizei n
Definition: glew.h:4040
GLsizei GLsizei GLfloat distance
Definition: glew.h:13640
iterator find(const key_type &k)
Definition: denseHashMap.h:341
size_t erase(const key_type &k)
Definition: denseHashMap.h:442
TfDenseHashMap(std::initializer_list< value_type > l)
Definition: denseHashMap.h:237
iterator end()
Definition: denseHashMap.h:323
void reserve(size_t n)
Definition: denseHashMap.h:525
void insert_unique(Iterator begin, Iterator end)
Definition: denseHashMap.h:420
std::pair< iterator, bool > insert_result
Return type for insert() method.
Definition: denseHashMap.h:214
bool operator==(const TfDenseHashMap &rhs) const
Definition: denseHashMap.h:266
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1346
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:91
const_iterator find(const key_type &k) const
Definition: denseHashMap.h:355
bool equal(T1 a, T2 b, T3 t)
Definition: ImathFun.h:143
insert_result insert(const value_type &v)
Definition: denseHashMap.h:376
void insert(IteratorType i0, IteratorType i1)
Definition: denseHashMap.h:403
void erase(iterator i0, iterator i1)
Definition: denseHashMap.h:480
TfDenseHashMap(Iterator begin, Iterator end)
Definition: denseHashMap.h:231
iterator begin()
Definition: denseHashMap.h:317
size_t size() const
Definition: denseHashMap.h:311
GLuint res
Definition: glew.h:11507
TfDenseHashMap & operator=(TfDenseHashMap rhs)
Definition: denseHashMap.h:251
bool empty() const
Definition: denseHashMap.h:305
_IteratorBase< value_type, typename _Vector::iterator > iterator
Definition: denseHashMap.h:205