24 #ifndef PXR_BASE_TF_DENSE_HASH_MAP_H
25 #define PXR_BASE_TF_DENSE_HASH_MAP_H
35 #include <hboost/compressed_pair.hpp>
36 #include <hboost/iterator/iterator_facade.hpp>
37 #include <hboost/utility.hpp>
56 class EqualKey = std::equal_to<Key>,
57 unsigned Threshold = 128
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();
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;
142 template <
class ElementType,
class UnderlyingIterator>
143 class _IteratorBase :
144 public hboost::iterator_facade<
145 _IteratorBase<ElementType, UnderlyingIterator>,
147 hboost::bidirectional_traversal_tag>
155 template<
class OtherIteratorType>
156 _IteratorBase(
const OtherIteratorType &rhs)
157 : _iter(rhs._GetUnderlyingIterator()) {}
162 friend class hboost::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) {
260 insert(l.begin(), l.end());
278 if (iter->second != riter->second)
286 return !(*
this == rhs);
299 _vectorHashFnEqualFn.swap(rhs._vectorHashFnEqualFn);
306 return _vec().empty();
312 return _vec().size();
318 return _vec().begin();
330 return _vec().begin();
344 if (iter == _h->end())
347 return _vec().begin() + iter->second;
349 return _FindInVec(k);
358 if (iter == _h->end())
361 return _vec().begin() + iter->second;
363 return _FindInVec(k);
380 std::pair<typename _HashMap::iterator, bool>
res =
381 _h->insert(std::make_pair(v.first,
size()));
387 iterator iter = _FindInVec(v.first);
393 _vec().push_back(_InternalValueType(v.first, v.second));
394 _CreateTableIfNeeded();
402 template<
class IteratorType>
403 void insert(IteratorType i0, IteratorType i1) {
412 for(IteratorType iter = i0; iter != i1; ++iter)
419 template <
class Iterator>
423 _vec().assign(begin, end);
424 _CreateTableIfNeeded();
458 _h->erase(iter->first);
461 if (iter != std::prev(
end())) {
465 typename _Vector::iterator vi = iter._GetUnderlyingIterator();
468 vi->swap(_vec().back());
472 (*_h)[vi->GetValue().first] = vi - _vec().begin();
483 for(
iterator iter = i0; iter != i1; ++iter)
484 _h->erase(iter->first);
487 typename _Vector::const_iterator vremain = _vec().erase(
488 i0._GetUnderlyingIterator(), i1._GetUnderlyingIterator());
491 for(; vremain != _vec().end(); ++vremain)
492 (*_h)[vremain->GetValue().first] = vremain - _vec().begin();
502 _Vector(_vec()).swap(_vec());
510 if (sz < Threshold) {
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));
535 return _vectorHashFnEqualFn.first().first();
540 return _vectorHashFnEqualFn.first().second();
545 return _vectorHashFnEqualFn.second();
549 const _Vector &_vec()
const {
550 return _vectorHashFnEqualFn.first().first();
554 const HashFn &_hash()
const {
555 return _vectorHashFnEqualFn.first().second();
559 const EqualKey &_equ()
const {
560 return _vectorHashFnEqualFn.second();
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))
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))
588 inline void _CreateTableIfNeeded() {
589 if (
size() >= Threshold) {
596 inline void _CreateTable() {
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));
609 hboost::compressed_pair<
610 hboost::compressed_pair<_Vector, HashFn>,
612 _VectorHashFnEqualFn;
614 _VectorHashFnEqualFn _vectorHashFnEqualFn;
617 std::unique_ptr<_HashMap> _h;
622 #endif // PXR_BASE_TF_DENSE_HASH_MAP_H
_IteratorBase< const value_type, typename _Vector::const_iterator > const_iterator
_Base::const_iterator const_iterator
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)
TfDenseHashMap & operator=(std::initializer_list< value_type > l)
const_iterator begin() const
size_t count(const key_type &k) const
void erase(const iterator &iter)
TfDenseHashMap(const HashFn &hashFn=HashFn(), const EqualKey &equalKey=EqualKey())
bool operator!=(const TfDenseHashMap &rhs) const
void swap(TfDenseHashMap &rhs)
Data & operator[](const key_type &key)
std::pair< const Key, Data > value_type
const_iterator end() const
TfDenseHashMap(const TfDenseHashMap &rhs)
GLsizei GLsizei GLfloat distance
iterator find(const key_type &k)
size_t erase(const key_type &k)
TfDenseHashMap(std::initializer_list< value_type > l)
void insert_unique(Iterator begin, Iterator end)
std::pair< iterator, bool > insert_result
Return type for insert() method.
bool operator==(const TfDenseHashMap &rhs) const
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
#define PXR_NAMESPACE_CLOSE_SCOPE
const_iterator find(const key_type &k) const
bool equal(T1 a, T2 b, T3 t)
insert_result insert(const value_type &v)
void insert(IteratorType i0, IteratorType i1)
void erase(iterator i0, iterator i1)
TfDenseHashMap(Iterator begin, Iterator end)
TfDenseHashMap & operator=(TfDenseHashMap rhs)
_IteratorBase< value_type, typename _Vector::iterator > iterator