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 TF_DENSE_HASH_MAP_H
25 #define TF_DENSE_HASH_MAP_H
26 
28 
29 #include "pxr/pxr.h"
30 #include "pxr/base/tf/hashmap.h"
31 
32 #include <memory>
33 #include <vector>
34 
35 #include <boost/compressed_pair.hpp>
36 #include <boost/operators.hpp>
37 #include <boost/iterator/iterator_facade.hpp>
38 #include <boost/utility.hpp>
39 
40 PXR_NAMESPACE_OPEN_SCOPE
41 
53 template <
54  class Key,
55  class Data,
56  class HashFn,
57  class EqualKey = std::equal_to<Key>,
58  unsigned Threshold = 128
59 >
61  private boost::equality_comparable<
62  TfDenseHashMap<Key, Data, HashFn, EqualKey, Threshold>
63  >
64 {
65 public:
66 
67  typedef std::pair<const Key, Data> value_type;
68  typedef Key key_type;
69  typedef Data mapped_type;
70 
72 
73 private:
74 
75  // This helper implements a std::pair with an assignment operator that
76  // uses placement new instead of assignment. The benefit here is that
77  // the two elements of the pair may be const.
78  //
79  struct _InternalValueType
80  {
81  _InternalValueType() {}
82 
83  _InternalValueType(const Key &k, const Data &d)
84  : _value(k, d) {}
85 
86  _InternalValueType &operator=(const _InternalValueType &rhs) {
87 
88  if (this != &rhs) {
89  // Since value_type's first member is const we need to
90  // use placement new to put the new element in place. Just
91  // make sure we destruct the element we are about to overwrite.
92  _value.value_type::~value_type();
93  new (&_value) value_type(rhs.GetValue());
94  }
95 
96  return *this;
97  }
98 
99  value_type &GetValue() {
100  return _value;
101  }
102 
103  const value_type &GetValue() const {
104  return _value;
105  }
106 
107  void swap(_InternalValueType &rhs) {
108  using std::swap;
109 
110  // We do this in order to take advantage of a potentially fast
111  // swap implementation.
112  Key tmp = _value.first;
113 
114  _value.first.Key::~Key();
115  new (const_cast<Key *>(&_value.first)) Key(rhs._value.first);
116 
117  rhs._value.first.Key::~Key();
118  new (const_cast<Key *>(&rhs._value.first)) Key(tmp);
119 
120  swap(_value.second, rhs._value.second);
121  }
122 
123  private:
124 
125  // Data hold by _InternalValueType. Note that the key portion of
126  // value_type maybe const.
127  value_type _value;
128  };
129 
130  // The vector type holding all data for this dense hash map.
131  typedef std::vector<_InternalValueType> _Vector;
132 
133  // The hash map used when the map holds more than Threshold elements.
134  typedef TfHashMap<Key, size_t, HashFn, EqualKey> _HashMap;
135 
136  // Note that we don't just use _Vector::iterator for accessing elements
137  // of the TfDenseHashMap. This is because the vector's iterator would
138  // expose the _InternalValueType _including_ its assignment operator
139  // that allows overwriting keys.
140  //
141  // Clearly not a good thing.
142  //
143  // Therefore we use boost::iterator_facade to create an iterator that uses
144  // the map's value_type as externally visible type.
145  //
146  template <class ElementType, class UnderlyingIterator>
147  class _IteratorBase :
148  public boost::iterator_facade<
149  _IteratorBase<ElementType, UnderlyingIterator>,
150  ElementType,
151  boost::bidirectional_traversal_tag>
152  {
153  public:
154 
155  // Empty ctor.
156  _IteratorBase() {}
157 
158  // Allow conversion of an iterator to a const_iterator.
159  template<class OtherIteratorType>
160  _IteratorBase(const OtherIteratorType &rhs)
161  : _iter(rhs._GetUnderlyingIterator()) {}
162 
163  private:
164 
165  friend class TfDenseHashMap;
166  friend class boost::iterator_core_access;
167 
168  // Ctor from an underlying iterator.
169  _IteratorBase(const UnderlyingIterator &iter)
170  : _iter(iter) {}
171 
172  template<class OtherIteratorType>
173  bool equal(const OtherIteratorType &rhs) const {
174  return _iter == rhs._iter;
175  }
176 
177  void increment() {
178  ++_iter;
179  }
180 
181  void decrement() {
182  --_iter;
183  }
184 
185  ElementType &dereference() const {
186  // The dereference() method accesses the correct value_type (ie.
187  // the one with potentially const key_type. This way, clients don't
188  // see the assignment operator of _InternalValueType.
189  return _iter->GetValue();
190  }
191 
192  UnderlyingIterator _GetUnderlyingIterator() const {
193  return _iter;
194  }
195 
196  private:
197 
198  UnderlyingIterator _iter;
199  };
200 
202 
203 public:
204 
207  typedef
208  _IteratorBase<value_type, typename _Vector::iterator>
210 
213  typedef
214  _IteratorBase<const value_type, typename _Vector::const_iterator>
216 
218  typedef std::pair<iterator, bool> insert_result;
219 
220 public:
221 
224  explicit TfDenseHashMap(
225  const HashFn &hashFn = HashFn(),
226  const EqualKey &equalKey = EqualKey())
227  {
228  _hash() = hashFn;
229  _equ() = equalKey;
230  }
231 
234  template <class Iterator>
235  TfDenseHashMap(Iterator begin, Iterator end) {
236  insert(begin, end);
237  }
238 
241  TfDenseHashMap(std::initializer_list<value_type> l) {
242  insert(l.begin(), l.end());
243  }
244 
248  : _vectorHashFnEqualFn(rhs._vectorHashFnEqualFn) {
249  if (rhs._h)
250  _h.reset(new _HashMap(*rhs._h));
251  }
252 
256  swap(rhs);
257  return *this;
258  }
259 
262  TfDenseHashMap &operator=(std::initializer_list<value_type> l) {
263  clear();
264  insert(l.begin(), l.end());
265  return *this;
266  }
267 
270  bool operator==(const TfDenseHashMap &rhs) const {
271 
272  if (size() != rhs.size())
273  return false;
274 
275  //XXX: Should we compare the HashFn and EqualKey too?
276  const_iterator tend = end(), rend = rhs.end();
277 
278  for(const_iterator iter = begin(); iter != tend; ++iter) {
279  const_iterator riter = rhs.find(iter->first);
280  if (riter == rend)
281  return false;
282  if (iter->second != riter->second)
283  return false;
284  }
285 
286  return true;
287  }
288 
291  void clear() {
292  _vec().clear();
293  _h.reset();
294  }
295 
298  void swap(TfDenseHashMap &rhs) {
299  _vectorHashFnEqualFn.swap(rhs._vectorHashFnEqualFn);
300  _h.swap(rhs._h);
301  }
302 
305  bool empty() const {
306  return _vec().empty();
307  }
308 
311  size_t size() const {
312  return _vec().size();
313  }
314 
318  return _vec().begin();
319  }
320 
324  return _vec().end();
325  }
326 
330  return _vec().begin();
331  }
332 
335  const_iterator end() const {
336  return _vec().end();
337  }
338 
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 
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 
369  size_t count(const key_type &k) const {
370  return find(k) != end();
371  }
372 
376  insert_result insert(const value_type &v) {
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 
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 
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 
436  Data &operator[](const key_type &key) {
437  return insert(value_type(key, Data())).first->second;
438  }
439 
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 
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 
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 
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 
525  void reserve(size_t n) {
526  _vec().reserve(n);
527  }
528 
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  boost::compressed_pair<
610  boost::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 
620 PXR_NAMESPACE_CLOSE_SCOPE
621 
622 #endif // TF_DENSE_HASH_MAP_H
iterator end()
Returns an const_iterator pointing to the end of the map.
Definition: denseHashMap.h:323
Data & operator[](const key_type &key)
Indexing operator.
Definition: denseHashMap.h:436
void swap(TfDenseHashMap &rhs)
Swaps the contents of two maps.
Definition: denseHashMap.h:298
void erase(const iterator &iter)
Erases element pointed to by iter.
Definition: denseHashMap.h:454
bool empty() const
true if the map&#39;s size is 0.
Definition: denseHashMap.h:305
size_t erase(const key_type &k)
Erase element with key k.
Definition: denseHashMap.h:442
_IteratorBase< value_type, typename _Vector::iterator > iterator
An iterator type for this map.
Definition: denseHashMap.h:209
iterator begin()
Returns an const_iterator pointing to the beginning of the map.
Definition: denseHashMap.h:317
void erase(iterator i0, iterator i1)
Erases a range from the map.
Definition: denseHashMap.h:480
std::pair< iterator, bool > insert_result
Return type for insert() method.
Definition: denseHashMap.h:218
void reserve(size_t n)
Reserve space.
Definition: denseHashMap.h:525
const_iterator find(const key_type &k) const
Finds the element with key k.
Definition: denseHashMap.h:355
void clear()
Erases all of the elements.
Definition: denseHashMap.h:291
TfDenseHashMap(Iterator begin, Iterator end)
Construct with range.
Definition: denseHashMap.h:235
TfDenseHashMap & operator=(TfDenseHashMap rhs)
Assignment operator.
Definition: denseHashMap.h:255
void swap(UsdStageLoadRules &l, UsdStageLoadRules &r)
Swap the contents of rules l and r.
TfDenseHashMap(const TfDenseHashMap &rhs)
Copy Ctor.
Definition: denseHashMap.h:247
iterator find(const key_type &k)
Finds the element with key k.
Definition: denseHashMap.h:341
This is a space efficient container that mimics the TfHashMap API that uses a vector for storage when...
Definition: denseHashMap.h:60
TfDenseHashMap(std::initializer_list< value_type > l)
Construct from an initializer_list.
Definition: denseHashMap.h:241
size_t count(const key_type &k) const
Returns the number of elements with key k.
Definition: denseHashMap.h:369
void insert_unique(Iterator begin, Iterator end)
Insert a range of unique elements into the container.
Definition: denseHashMap.h:420
TfDenseHashMap & operator=(std::initializer_list< value_type > l)
Assignment from an initializer_list.
Definition: denseHashMap.h:262
const_iterator end() const
Returns an const_iterator pointing to the end of the map.
Definition: denseHashMap.h:335
TfDenseHashMap(const HashFn &hashFn=HashFn(), const EqualKey &equalKey=EqualKey())
Ctor.
Definition: denseHashMap.h:224
size_t size() const
Returns the size of the map.
Definition: denseHashMap.h:311
_IteratorBase< const value_type, typename _Vector::const_iterator > const_iterator
An iterator type for this map.
Definition: denseHashMap.h:215
bool operator==(const TfDenseHashMap &rhs) const
Equality operator.
Definition: denseHashMap.h:270
const_iterator begin() const
Returns an const_iterator pointing to the beginning of the map.
Definition: denseHashMap.h:329
void insert(IteratorType i0, IteratorType i1)
Insert a range into the hash map.
Definition: denseHashMap.h:403
insert_result insert(const value_type &v)
Returns a pair of &lt;iterator, bool&gt; where iterator points to the element in the list and bool is true ...
Definition: denseHashMap.h:376
void shrink_to_fit()
Optimize storage space.
Definition: denseHashMap.h:498