24 #ifndef PXR_BASE_TF_DENSE_HASH_MAP_H
25 #define PXR_BASE_TF_DENSE_HASH_MAP_H
36 #include <hboost/iterator/iterator_facade.hpp>
55 class EqualKey = std::equal_to<Key>,
56 unsigned Threshold = 128
64 private HashFn,
private EqualKey
80 struct _InternalValueType
82 _InternalValueType() {}
84 _InternalValueType(
const Key &k,
const Data &d)
87 _InternalValueType &operator=(
const _InternalValueType &rhs) {
93 _value.value_type::~value_type();
108 void swap(_InternalValueType &rhs) {
113 Key tmp = _value.first;
115 _value.first.Key::~Key();
116 new (
const_cast<Key *
>(&_value.first)) Key(rhs._value.first);
118 rhs._value.first.Key::~Key();
119 new (
const_cast<Key *
>(&rhs._value.first)) Key(tmp);
121 swap(_value.second, rhs._value.second);
132 typedef std::vector<_InternalValueType> _Vector;
147 template <
class ElementType,
class UnderlyingIterator>
148 class _IteratorBase :
149 public hboost::iterator_facade<
150 _IteratorBase<ElementType, UnderlyingIterator>,
152 hboost::bidirectional_traversal_tag>
160 template<
class OtherIteratorType>
161 _IteratorBase(
const OtherIteratorType &rhs)
162 : _iter(rhs._GetUnderlyingIterator()) {}
167 friend class hboost::iterator_core_access;
170 _IteratorBase(
const UnderlyingIterator &iter)
173 template<
class OtherIteratorType>
174 bool equal(
const OtherIteratorType &rhs)
const {
175 return _iter == rhs._iter;
186 ElementType &dereference()
const {
190 return _iter->GetValue();
193 UnderlyingIterator _GetUnderlyingIterator()
const {
199 UnderlyingIterator _iter;
209 _IteratorBase<value_type, typename _Vector::iterator>
215 _IteratorBase<const value_type, typename _Vector::const_iterator>
226 const HashFn &hashFn = HashFn(),
227 const EqualKey &equalKey = EqualKey()) :
229 EqualKey(equalKey) {}
233 template <
class Iterator>
241 insert(l.begin(), l.end());
249 _vector(rhs._vector),
250 _h(rhs._h ? std::make_unique<
_HashMap>(*rhs._h) : nullptr) {}
274 insert(l.begin(), l.end());
292 if (iter->second != riter->second)
300 return !(*
this == rhs);
314 swap(_hash(), rhs._hash());
315 swap(_equ(), rhs._equ());
316 _vector.swap(rhs._vector);
323 return _vec().empty();
329 return _vec().size();
335 return _vec().begin();
347 return _vec().begin();
361 if (iter == _h->end())
364 return _vec().begin() + iter->second;
366 return _FindInVec(k);
375 if (iter == _h->end())
378 return _vec().begin() + iter->second;
380 return _FindInVec(k);
397 std::pair<typename _HashMap::iterator, bool> res =
398 _h->insert(std::make_pair(v.first,
size()));
404 iterator iter = _FindInVec(v.first);
410 _vec().push_back(_InternalValueType(v.first, v.second));
411 _CreateTableIfNeeded();
419 template<
class IteratorType>
429 for(IteratorType iter = i0; iter !=
i1; ++iter)
436 template <
class Iterator>
440 _vec().assign(begin, end);
441 _CreateTableIfNeeded();
475 _h->erase(iter->first);
478 if (iter != std::prev(
end())) {
482 typename _Vector::iterator vi = iter._GetUnderlyingIterator();
485 vi->swap(_vec().back());
489 (*_h)[vi->GetValue().first] = vi - _vec().begin();
501 _h->erase(iter->first);
504 typename _Vector::const_iterator vremain = _vec().erase(
505 i0._GetUnderlyingIterator(), i1._GetUnderlyingIterator());
508 for(; vremain != _vec().end(); ++vremain)
509 (*_h)[vremain->GetValue().first] = vremain - _vec().begin();
518 _vec().shrink_to_fit();
526 if (sz < Threshold) {
533 _h.reset(
new _HashMap(sz, _hash(), _equ()));
534 for(
size_t i=0; i<sz; ++i)
535 _h->insert(std::make_pair(_vec()[i].GetValue().
first, i));
565 const _Vector &_vec()
const {
570 const HashFn &_hash()
const {
575 const EqualKey &_equ()
const {
580 inline iterator _FindInVec(
const key_type &k) {
581 _Vector &vec = _vec();
582 EqualKey &equ = _equ();
583 typename _Vector::iterator iter = vec.begin(),
end = vec.end();
584 for (; iter !=
end; ++iter) {
585 if (equ(iter->GetValue().first, k))
592 inline const_iterator _FindInVec(
const key_type &k)
const {
593 _Vector
const &vec = _vec();
594 EqualKey
const &equ = _equ();
595 typename _Vector::const_iterator iter = vec.begin(),
end = vec.end();
596 for (; iter !=
end; ++iter) {
597 if (equ(iter->GetValue().first, k))
604 inline void _CreateTableIfNeeded() {
605 if (
size() >= Threshold) {
612 inline void _CreateTable() {
614 _h.reset(
new _HashMap(Threshold, _hash(), _equ()));
615 for(
size_t i=0; i <
size(); ++i)
616 _h->insert(std::make_pair(_vec()[i].GetValue().
first, i));
624 std::unique_ptr<_HashMap> _h;
629 #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)
void swap(T &lhs, T &rhs)
IMATH_HOSTDEVICE constexpr bool equal(T1 a, T2 b, T3 t) IMATH_NOEXCEPT
TfDenseHashMap(const HashFn &hashFn=HashFn(), const EqualKey &equalKey=EqualKey())
bool operator!=(const TfDenseHashMap &rhs) const
OIIO_FORCEINLINE vbool4 insert(const vbool4 &a, bool val)
Helper: substitute val for a[i].
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)
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
insert_result insert(const value_type &v)
void insert(IteratorType i0, IteratorType i1)
void erase(iterator i0, iterator i1)
TfDenseHashMap & operator=(const TfDenseHashMap &rhs)
TfDenseHashMap(Iterator begin, Iterator end)
SIM_API const UT_StringHolder distance
FMT_CONSTEXPR auto find(Ptr first, Ptr last, T value, Ptr &out) -> bool
_IteratorBase< value_type, typename _Vector::iterator > iterator
PcpNodeRef_ChildrenIterator begin(const PcpNodeRef::child_const_range &r)
Support for range-based for loops for PcpNodeRef children ranges.