24#ifndef PXR_BASE_TF_DENSE_HASH_MAP_H
25#define PXR_BASE_TF_DENSE_HASH_MAP_H
31#include "pxr/base/tf/hashmap.h"
36PXR_NAMESPACE_OPEN_SCOPE
53 class EqualKey = std::equal_to<Key>,
54 unsigned Threshold = 128
61 typedef std::pair<const Key, Data> value_type;
63 typedef Data mapped_type;
73 struct _InternalValueType
75 _InternalValueType() {}
77 _InternalValueType(
const Key &k,
const Data &d)
80 _InternalValueType &operator=(
const _InternalValueType &rhs) {
86 _value.value_type::~value_type();
87 new (&_value) value_type(rhs.GetValue());
93 value_type &GetValue() {
97 const value_type &GetValue()
const {
101 void swap(_InternalValueType &rhs) {
106 Key tmp = _value.first;
108 _value.first.Key::~Key();
109 new (
const_cast<Key *
>(&_value.first)) Key(rhs._value.first);
111 rhs._value.first.Key::~Key();
112 new (
const_cast<Key *
>(&rhs._value.first)) Key(tmp);
114 swap(_value.second, rhs._value.second);
125 typedef std::vector<_InternalValueType> _Vector;
128 typedef TfHashMap<Key, size_t, HashFn, EqualKey> _HashMap;
140 template <
class ElementType,
class UnderlyingIterator>
144 using iterator_category = std::bidirectional_iterator_tag;
145 using value_type = ElementType;
146 using reference = ElementType&;
147 using pointer = ElementType*;
148 using difference_type =
typename UnderlyingIterator::difference_type;
151 _IteratorBase() =
default;
154 template<
class OtherIteratorType>
155 _IteratorBase(
const OtherIteratorType &rhs)
156 : _iter(rhs._GetUnderlyingIterator()) {}
158 reference operator*()
const {
return dereference(); }
159 pointer operator->()
const {
return &(dereference()); }
161 _IteratorBase& operator++() {
166 _IteratorBase& operator--() {
171 _IteratorBase operator++(
int) {
172 _IteratorBase result(*
this);
177 _IteratorBase operator--(
int) {
178 _IteratorBase result(*
this);
183 template <
class OtherIteratorType>
184 bool operator==(
const OtherIteratorType& other)
const {
188 template <
class OtherIteratorType>
189 bool operator!=(
const OtherIteratorType& other)
const {
190 return !equal(other);
198 _IteratorBase(
const UnderlyingIterator &iter)
201 template<
class OtherIteratorType>
202 bool equal(
const OtherIteratorType &rhs)
const {
203 return _iter == rhs._iter;
214 ElementType &dereference()
const {
218 return _iter->GetValue();
221 UnderlyingIterator _GetUnderlyingIterator()
const {
227 UnderlyingIterator _iter;
237 _IteratorBase<value_type, typename _Vector::iterator>
243 _IteratorBase<const value_type, typename _Vector::const_iterator>
254 const HashFn &hashFn = HashFn(),
255 const EqualKey &equalKey = EqualKey())
263 template <
class Iterator>
271 insert(l.begin(), l.end());
277 : _storage(rhs._storage) {
279 _h = std::make_unique<_HashMap>(*rhs._h);
304 insert(l.begin(), l.end());
322 if (iter->second != riter->second)
330 return !(*
this == rhs);
343 _storage.swap(rhs._storage);
350 return _vec().empty();
356 return _vec().size();
362 return _vec().begin();
374 return _vec().begin();
387 typename _HashMap::const_iterator iter = _h->find(k);
388 if (iter == _h->end())
391 return _vec().begin() + iter->second;
393 return _FindInVec(k);
401 typename _HashMap::const_iterator iter = _h->find(k);
402 if (iter == _h->end())
405 return _vec().begin() + iter->second;
407 return _FindInVec(k);
413 size_t count(
const key_type &k)
const {
424 std::pair<typename _HashMap::iterator, bool> res =
425 _h->insert(std::make_pair(v.first,
size()));
431 iterator iter = _FindInVec(v.first);
437 _vec().push_back(_InternalValueType(v.first, v.second));
438 _CreateTableIfNeeded();
446 template<
class IteratorType>
447 void insert(IteratorType i0, IteratorType i1) {
452 if (
size() + std::distance(i0, i1) >= Threshold)
456 for(IteratorType iter = i0; iter != i1; ++iter)
463 template <
class Iterator>
468 _CreateTableIfNeeded();
481 return insert(value_type(key, Data())).first->second;
502 _h->erase(iter->first);
505 if (iter != std::prev(
end())) {
509 typename _Vector::iterator vi = iter._GetUnderlyingIterator();
512 vi->swap(_vec().back());
516 (*_h)[vi->GetValue().first] = vi - _vec().begin();
527 for(
iterator iter = i0; iter != i1; ++iter)
528 _h->erase(iter->first);
531 typename _Vector::const_iterator vremain = _vec().erase(
532 i0._GetUnderlyingIterator(), i1._GetUnderlyingIterator());
535 for(; vremain != _vec().end(); ++vremain)
536 (*_h)[vremain->GetValue().first] = vremain - _vec().begin();
545 _vec().shrink_to_fit();
553 if (sz < Threshold) {
560 _h.reset(
new _HashMap(sz, _hash(), _equ()));
561 for(
size_t i=0; i<sz; ++i)
562 _h->insert(std::make_pair(_vec()[i].GetValue().first, i));
578 return _storage.vector;
592 const _Vector &_vec()
const {
593 return _storage.vector;
597 const HashFn &_hash()
const {
602 const EqualKey &_equ()
const {
607 inline iterator _FindInVec(
const key_type &k) {
608 _Vector &vec = _vec();
609 EqualKey &equ = _equ();
610 typename _Vector::iterator iter = vec.begin(),
end = vec.end();
611 for (; iter !=
end; ++iter) {
612 if (equ(iter->GetValue().first, k))
620 _Vector
const &vec = _vec();
621 EqualKey
const &equ = _equ();
622 typename _Vector::const_iterator iter = vec.begin(),
end = vec.end();
623 for (; iter !=
end; ++iter) {
624 if (equ(iter->GetValue().first, k))
631 inline void _CreateTableIfNeeded() {
632 if (
size() >= Threshold) {
639 inline void _CreateTable() {
641 _h.reset(
new _HashMap(Threshold, _hash(), _equ()));
642 for(
size_t i=0; i <
size(); ++i)
643 _h->insert(std::make_pair(_vec()[i].GetValue().first, i));
652 private EqualKey,
private HashFn {
653 static_assert(!std::is_same<EqualKey, HashFn>::value,
654 "EqualKey and HashFn must be distinct types.");
655 _CompressedStorage() =
default;
656 _CompressedStorage(
const EqualKey& equalKey,
const HashFn& hashFn)
657 : EqualKey(equalKey), HashFn(hashFn) {}
659 void swap(_CompressedStorage& other) {
661 vector.swap(other.vector);
662 swap(
static_cast<EqualKey&
>(*
this),
static_cast<EqualKey&
>(other));
663 swap(
static_cast<HashFn&
>(*
this),
static_cast<HashFn&
>(other));
668 _CompressedStorage _storage;
671 std::unique_ptr<_HashMap> _h;
674PXR_NAMESPACE_CLOSE_SCOPE
Define function attributes.
#define ARCH_EMPTY_BASES
Macro to begin the definition of a class that is using private inheritance to take advantage of the e...
This is a space efficient container that mimics the TfHashMap API that uses a vector for storage when...
Data & operator[](const key_type &key)
Indexing operator.
size_t size() const
Returns the size of the map.
TfDenseHashMap(std::initializer_list< value_type > l)
Construct from an initializer_list.
const_iterator begin() const
Returns an const_iterator pointing to the beginning of the map.
TfDenseHashMap(const HashFn &hashFn=HashFn(), const EqualKey &equalKey=EqualKey())
Ctor.
size_t count(const key_type &k) const
Returns the number of elements with key k.
_IteratorBase< const value_type, typename _Vector::const_iterator > const_iterator
An iterator type for this map.
size_t erase(const key_type &k)
Erase element with key k.
const_iterator find(const key_type &k) const
Finds the element with key k.
void insert(IteratorType i0, IteratorType i1)
Insert a range into the hash map.
iterator find(const key_type &k)
Finds the element with key k.
TfDenseHashMap & operator=(TfDenseHashMap &&rhs)=default
Move assignment operator.
void shrink_to_fit()
Optimize storage space.
bool empty() const
true if the map's size is 0.
bool operator==(const TfDenseHashMap &rhs) const
Equality operator.
void erase(const iterator &iter)
Erases element pointed to by iter.
TfDenseHashMap(Iterator begin, Iterator end)
Construct with range.
TfDenseHashMap & operator=(const TfDenseHashMap &rhs)
Copy assignment operator.
_IteratorBase< value_type, typename _Vector::iterator > iterator
An iterator type for this map.
std::pair< iterator, bool > insert_result
Return type for insert() method.
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 clear()
Erases all of the elements.
iterator end()
Returns an const_iterator pointing to the end of the map.
void insert_unique(Iterator begin, Iterator end)
Insert a range of unique elements into the container.
const_iterator end() const
Returns an const_iterator pointing to the end of the map.
void swap(TfDenseHashMap &rhs)
Swaps the contents of two maps.
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.
TfDenseHashMap(const TfDenseHashMap &rhs)
Copy Ctor.
TfDenseHashMap(TfDenseHashMap &&rhs)=default
Move Ctor.
void reserve(size_t n)
Reserve space.
TfDenseHashMap & operator=(std::initializer_list< value_type > l)
Assignment from an initializer_list.