7 #ifndef PXR_BASE_TF_DENSE_HASH_MAP_H
8 #define PXR_BASE_TF_DENSE_HASH_MAP_H
36 class EqualKey = std::equal_to<Key>,
37 unsigned Threshold = 128
56 struct _InternalValueType
58 _InternalValueType() {}
60 _InternalValueType(
const Key &k,
const Data &d)
63 _InternalValueType &
operator=(
const _InternalValueType &rhs) {
69 _value.value_type::~value_type();
84 void swap(_InternalValueType &rhs) {
89 Key tmp = _value.first;
91 _value.first.Key::~Key();
92 new (
const_cast<Key *
>(&_value.first)) Key(rhs._value.first);
94 rhs._value.first.Key::~Key();
95 new (
const_cast<Key *
>(&rhs._value.first)) Key(tmp);
97 swap(_value.second, rhs._value.second);
108 typedef std::vector<_InternalValueType> _Vector;
123 template <
class ElementType,
class UnderlyingIterator>
127 using iterator_category = std::bidirectional_iterator_tag;
131 using difference_type =
typename UnderlyingIterator::difference_type;
134 _IteratorBase() =
default;
137 template<
class OtherIteratorType>
138 _IteratorBase(
const OtherIteratorType &rhs)
139 : _iter(rhs._GetUnderlyingIterator()) {}
142 pointer operator->()
const {
return &(dereference()); }
144 _IteratorBase& operator++() {
149 _IteratorBase& operator--() {
154 _IteratorBase operator++(
int) {
155 _IteratorBase
result(*
this);
160 _IteratorBase operator--(
int) {
161 _IteratorBase
result(*
this);
166 template <
class OtherIteratorType>
167 bool operator==(
const OtherIteratorType& other)
const {
171 template <
class OtherIteratorType>
172 bool operator!=(
const OtherIteratorType& other)
const {
173 return !
equal(other);
181 _IteratorBase(
const UnderlyingIterator &iter)
184 template<
class OtherIteratorType>
185 bool equal(
const OtherIteratorType &rhs)
const {
186 return _iter == rhs._iter;
197 ElementType &dereference()
const {
201 return _iter->GetValue();
204 UnderlyingIterator _GetUnderlyingIterator()
const {
210 UnderlyingIterator _iter;
220 _IteratorBase<value_type, typename _Vector::iterator>
226 _IteratorBase<const value_type, typename _Vector::const_iterator>
237 const HashFn &hashFn = HashFn(),
238 const EqualKey &equalKey = EqualKey())
246 template <
class Iterator>
254 insert(l.begin(), l.end());
260 : _storage(rhs._storage) {
262 _h = std::make_unique<_HashMap>(*rhs._h);
287 insert(l.begin(), l.end());
305 if (iter->second != riter->second)
313 return !(*
this == rhs);
326 _storage.swap(rhs._storage);
333 return _vec().empty();
339 return _vec().size();
345 return _vec().begin();
357 return _vec().begin();
371 if (iter == _h->end())
374 return _vec().begin() + iter->second;
376 return _FindInVec(k);
385 if (iter == _h->end())
388 return _vec().begin() + iter->second;
390 return _FindInVec(k);
407 std::pair<typename _HashMap::iterator, bool> res =
408 _h->insert(std::make_pair(v.first,
size()));
414 iterator iter = _FindInVec(v.first);
420 _vec().push_back(_InternalValueType(v.first, v.second));
421 _CreateTableIfNeeded();
429 template<
class IteratorType>
439 for(IteratorType iter = i0; iter !=
i1; ++iter)
446 template <
class Iterator>
450 _vec().assign(begin, end);
451 _CreateTableIfNeeded();
485 _h->erase(iter->first);
488 if (iter != std::prev(
end())) {
492 typename _Vector::iterator vi = iter._GetUnderlyingIterator();
495 vi->swap(_vec().back());
499 (*_h)[vi->GetValue().first] = vi - _vec().begin();
511 _h->erase(iter->first);
514 typename _Vector::const_iterator vremain = _vec().erase(
515 i0._GetUnderlyingIterator(), i1._GetUnderlyingIterator());
518 for(; vremain != _vec().end(); ++vremain)
519 (*_h)[vremain->GetValue().first] = vremain - _vec().begin();
528 _vec().shrink_to_fit();
536 if (sz < Threshold) {
543 _h.reset(
new _HashMap(sz, _hash(), _equ()));
544 for(
size_t i=0; i<sz; ++i)
545 _h->insert(std::make_pair(_vec()[i].GetValue().
first, i));
561 return _storage.vector;
575 const _Vector &_vec()
const {
576 return _storage.vector;
580 const HashFn &_hash()
const {
585 const EqualKey &_equ()
const {
591 _Vector &vec = _vec();
592 EqualKey &equ = _equ();
593 typename _Vector::iterator iter = vec.begin(),
end = vec.end();
594 for (; iter !=
end; ++iter) {
595 if (equ(iter->GetValue().first, k))
603 _Vector
const &vec = _vec();
604 EqualKey
const &equ = _equ();
605 typename _Vector::const_iterator iter = vec.begin(),
end = vec.end();
606 for (; iter !=
end; ++iter) {
607 if (equ(iter->GetValue().first, k))
614 inline void _CreateTableIfNeeded() {
615 if (
size() >= Threshold) {
622 inline void _CreateTable() {
624 _h.reset(
new _HashMap(Threshold, _hash(), _equ()));
625 for(
size_t i=0; i <
size(); ++i)
626 _h->insert(std::make_pair(_vec()[i].GetValue().
first, i));
634 struct ARCH_EMPTY_BASES _CompressedStorage :
635 private EqualKey,
private HashFn {
637 "EqualKey and HashFn must be distinct types.");
638 _CompressedStorage() =
default;
639 _CompressedStorage(
const EqualKey& equalKey,
const HashFn& hashFn)
640 : EqualKey(equalKey), HashFn(hashFn) {}
642 void swap(_CompressedStorage& other) {
644 vector.swap(other.vector);
645 swap(static_cast<EqualKey&>(*
this), static_cast<EqualKey&>(other));
646 swap(static_cast<HashFn&>(*
this), static_cast<HashFn&>(other));
651 _CompressedStorage _storage;
654 std::unique_ptr<_HashMap> _h;
659 #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
GLsizei const GLfloat * value
size_t count(const key_type &k) const
void erase(const iterator &iter)
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
**But if you need a result
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)
IMATH_HOSTDEVICE constexpr Color4< T > operator*(S a, const Color4< T > &v) IMATH_NOEXCEPT
Reverse multiplication: S * Color4.
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
that also have some descendant prim *whose name begins with which in turn has a child named baz where *the predicate and *a name There is also one special expression reference
_IteratorBase< value_type, typename _Vector::iterator > iterator