24 #ifndef PXR_BASE_TF_DENSE_HASH_MAP_H
25 #define PXR_BASE_TF_DENSE_HASH_MAP_H
30 #include "pxr/base/tf/hashmap.h"
35 #include <boost/compressed_pair.hpp>
36 #include <boost/iterator/iterator_facade.hpp>
37 #include <boost/utility.hpp>
39 PXR_NAMESPACE_OPEN_SCOPE
56 class EqualKey = std::equal_to<Key>,
57 unsigned Threshold = 128
63 typedef std::pair<const Key, Data> value_type;
65 typedef Data mapped_type;
75 struct _InternalValueType
77 _InternalValueType() {}
79 _InternalValueType(
const Key &k,
const Data &d)
82 _InternalValueType &
operator=(
const _InternalValueType &rhs) {
88 _value.value_type::~value_type();
89 new (&_value) value_type(rhs.GetValue());
95 value_type &GetValue() {
99 const value_type &GetValue()
const {
103 void swap(_InternalValueType &rhs) {
108 Key tmp = _value.first;
110 _value.first.Key::~Key();
111 new (
const_cast<Key *
>(&_value.first)) Key(rhs._value.first);
113 rhs._value.first.Key::~Key();
114 new (
const_cast<Key *
>(&rhs._value.first)) Key(tmp);
116 swap(_value.second, rhs._value.second);
127 typedef std::vector<_InternalValueType> _Vector;
130 typedef TfHashMap<Key, size_t, HashFn, EqualKey> _HashMap;
142 template <
class ElementType,
class UnderlyingIterator>
143 class _IteratorBase :
144 public boost::iterator_facade<
145 _IteratorBase<ElementType, UnderlyingIterator>,
147 boost::bidirectional_traversal_tag>
155 template<
class OtherIteratorType>
156 _IteratorBase(
const OtherIteratorType &rhs)
157 : _iter(rhs._GetUnderlyingIterator()) {}
162 friend class boost::iterator_core_access;
165 _IteratorBase(
const UnderlyingIterator &iter)
168 template<
class OtherIteratorType>
169 bool equal(
const OtherIteratorType &rhs)
const {
170 return _iter == rhs._iter;
181 ElementType &dereference()
const {
185 return _iter->GetValue();
188 UnderlyingIterator _GetUnderlyingIterator()
const {
194 UnderlyingIterator _iter;
204 _IteratorBase<value_type, typename _Vector::iterator>
210 _IteratorBase<const value_type, typename _Vector::const_iterator>
221 const HashFn &hashFn = HashFn(),
222 const EqualKey &equalKey = EqualKey())
230 template <
class Iterator>
238 insert(l.begin(), l.end());
244 : _vectorHashFnEqualFn(rhs._vectorHashFnEqualFn) {
246 _h.reset(
new _HashMap(*rhs._h));
272 insert(l.begin(), l.end());
290 if (iter->second != riter->second)
298 return !(*
this == rhs);
311 _vectorHashFnEqualFn.swap(rhs._vectorHashFnEqualFn);
318 return _vec().empty();
324 return _vec().size();
330 return _vec().begin();
342 return _vec().begin();
355 typename _HashMap::const_iterator iter = _h->find(k);
356 if (iter == _h->end())
359 return _vec().begin() + iter->second;
361 return _FindInVec(k);
369 typename _HashMap::const_iterator iter = _h->find(k);
370 if (iter == _h->end())
373 return _vec().begin() + iter->second;
375 return _FindInVec(k);
392 std::pair<typename _HashMap::iterator, bool> res =
393 _h->insert(std::make_pair(v.first,
size()));
399 iterator iter = _FindInVec(v.first);
405 _vec().push_back(_InternalValueType(v.first, v.second));
406 _CreateTableIfNeeded();
414 template<
class IteratorType>
415 void insert(IteratorType i0, IteratorType i1) {
420 if (
size() + std::distance(i0, i1) >= Threshold)
424 for(IteratorType iter = i0; iter != i1; ++iter)
431 template <
class Iterator>
435 _vec().assign(begin, end);
436 _CreateTableIfNeeded();
449 return insert(value_type(key, Data())).first->second;
470 _h->erase(iter->first);
473 if (iter != std::prev(
end())) {
477 typename _Vector::iterator vi = iter._GetUnderlyingIterator();
480 vi->swap(_vec().back());
484 (*_h)[vi->GetValue().first] = vi - _vec().begin();
495 for(
iterator iter = i0; iter != i1; ++iter)
496 _h->erase(iter->first);
499 typename _Vector::const_iterator vremain = _vec().erase(
500 i0._GetUnderlyingIterator(), i1._GetUnderlyingIterator());
503 for(; vremain != _vec().end(); ++vremain)
504 (*_h)[vremain->GetValue().first] = vremain - _vec().begin();
513 _vec().shrink_to_fit();
521 if (sz < Threshold) {
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));
546 return _vectorHashFnEqualFn.first().first();
551 return _vectorHashFnEqualFn.first().second();
556 return _vectorHashFnEqualFn.second();
560 const _Vector &_vec()
const {
561 return _vectorHashFnEqualFn.first().first();
565 const HashFn &_hash()
const {
566 return _vectorHashFnEqualFn.first().second();
570 const EqualKey &_equ()
const {
571 return _vectorHashFnEqualFn.second();
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))
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))
599 inline void _CreateTableIfNeeded() {
600 if (
size() >= Threshold) {
607 inline void _CreateTable() {
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));
620 boost::compressed_pair<
621 boost::compressed_pair<_Vector, HashFn>,
623 _VectorHashFnEqualFn;
625 _VectorHashFnEqualFn _vectorHashFnEqualFn;
628 std::unique_ptr<_HashMap> _h;
631 PXR_NAMESPACE_CLOSE_SCOPE
633 #endif // PXR_BASE_TF_DENSE_HASH_MAP_H
iterator end()
Returns an const_iterator pointing to the end of the map.
Data & operator[](const key_type &key)
Indexing operator.
void swap(TfDenseHashMap &rhs)
Swaps the contents of two maps.
void erase(const iterator &iter)
Erases element pointed to by iter.
bool empty() const
true if the map's size is 0.
size_t erase(const key_type &k)
Erase element with key k.
_IteratorBase< value_type, typename _Vector::iterator > iterator
An iterator type for this map.
iterator begin()
Returns an const_iterator pointing to the beginning of the map.
void erase(iterator i0, iterator i1)
Erases a range from the map.
std::pair< iterator, bool > insert_result
Return type for insert() method.
void reserve(size_t n)
Reserve space.
const_iterator find(const key_type &k) const
Finds the element with key k.
void clear()
Erases all of the elements.
TfDenseHashMap(Iterator begin, Iterator end)
Construct with range.
void swap(UsdStageLoadRules &l, UsdStageLoadRules &r)
Swap the contents of rules l and r.
TfDenseHashMap(const TfDenseHashMap &rhs)
Copy Ctor.
iterator find(const key_type &k)
Finds the element with key k.
This is a space efficient container that mimics the TfHashMap API that uses a vector for storage when...
TfDenseHashMap(std::initializer_list< value_type > l)
Construct from an initializer_list.
size_t count(const key_type &k) const
Returns the number of elements with key k.
A path value used to locate objects in layers or scenegraphs.
void insert_unique(Iterator begin, Iterator end)
Insert a range of unique elements into the container.
TfDenseHashMap & operator=(std::initializer_list< value_type > l)
Assignment from an initializer_list.
const_iterator end() const
Returns an const_iterator pointing to the end of the map.
TfDenseHashMap(const HashFn &hashFn=HashFn(), const EqualKey &equalKey=EqualKey())
Ctor.
size_t size() const
Returns the size of the map.
_IteratorBase< const value_type, typename _Vector::const_iterator > const_iterator
An iterator type for this map.
bool operator==(const TfDenseHashMap &rhs) const
Equality operator.
const_iterator begin() const
Returns an const_iterator pointing to the beginning of the map.
void insert(IteratorType i0, IteratorType i1)
Insert a range into the hash map.
TfDenseHashMap & operator=(const TfDenseHashMap &rhs)
Copy assignment operator.
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 ...
void shrink_to_fit()
Optimize storage space.