24 #ifndef PXR_USD_SDF_PATH_TABLE_H
25 #define PXR_USD_SDF_PATH_TABLE_H
33 #include <hboost/iterator/iterator_facade.hpp>
83 template <
class MappedType>
99 _Entry(
const _Entry&) =
delete;
100 _Entry&
operator=(
const _Entry&) =
delete;
104 , firstChild(
nullptr)
105 , nextSiblingOrParent(
nullptr,
false) {}
108 :
value(std::move(value))
110 , firstChild(
nullptr)
111 , nextSiblingOrParent(
nullptr,
false) {}
115 _Entry *GetNextSibling() {
116 return nextSiblingOrParent.template BitsAs<bool>() ?
117 nextSiblingOrParent.Get() : 0;
121 _Entry
const *GetNextSibling()
const {
122 return nextSiblingOrParent.template BitsAs<bool>() ?
123 nextSiblingOrParent.Get() : 0;
128 _Entry *GetParentLink() {
129 return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
130 nextSiblingOrParent.Get();
134 _Entry
const *GetParentLink()
const {
135 return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
136 nextSiblingOrParent.Get();
141 void SetSibling(_Entry *sibling) {
142 nextSiblingOrParent.Set(sibling,
true);
147 void SetParentLink(_Entry *parent) {
148 nextSiblingOrParent.Set(parent,
false);
152 void AddChild(_Entry *child) {
156 child->SetSibling(firstChild);
158 child->SetParentLink(
this);
162 void RemoveChild(_Entry *child) {
164 if (child == firstChild) {
165 firstChild = child->GetNextSibling();
169 _Entry *prev, *cur = firstChild;
172 cur = prev->GetNextSibling();
173 }
while (cur != child);
174 prev->nextSiblingOrParent = cur->nextSiblingOrParent;
197 typedef std::vector<_Entry *> _BucketVec;
204 template <
class ValType,
class EntryPtr>
206 public hboost::iterator_facade<Iterator<ValType, EntryPtr>,
207 ValType, hboost::forward_traversal_tag>
215 template <
class OtherVal,
class OtherEntryPtr>
226 if (EntryPtr sibling =
_entry->GetNextSibling()) {
232 for (EntryPtr p =
_entry->GetParentLink(); p;
233 p = p->GetParentLink()) {
234 if (EntryPtr sibling = p->GetNextSibling()) {
247 return bool(
_entry->firstChild);
271 template <
class OtherVal,
class OtherEntryPtr>
306 ret._unlinkedEntry.reset(
new _Entry(value,
nullptr));
314 ret._unlinkedEntry.reset(
new _Entry(std::move(
value),
nullptr));
321 return New({ key, mapped });
328 return _unlinkedEntry->value.first;
335 return _unlinkedEntry->value.first;
342 return _unlinkedEntry->value.second;
349 return _unlinkedEntry->value.second;
355 return static_cast<bool>(_unlinkedEntry);
360 explicit operator bool()
const {
367 _unlinkedEntry.reset();
371 std::unique_ptr<_Entry> _unlinkedEntry;
379 : _buckets(other._buckets.
size())
389 if (i._entry->firstChild && !j._entry->firstChild) {
390 j._entry->firstChild =
391 _InsertInTable(i._entry->firstChild->value).first._entry;
394 if (i._entry->nextSiblingOrParent.Get() &&
395 !j._entry->nextSiblingOrParent.Get()) {
396 j._entry->nextSiblingOrParent.Set(
397 _InsertInTable(i._entry->nextSiblingOrParent.
399 i._entry->nextSiblingOrParent.template BitsAs<bool>());
406 : _buckets(std::move(other._buckets))
483 _Entry *
const entry = i._entry;
484 _EraseSubtree(entry);
485 _RemoveFromParent(entry);
486 _EraseFromTable(entry);
494 for (_Entry *e = _buckets[_Hash(path)]; e; e = e->next) {
495 if (e->value.first == path)
507 for (_Entry
const *e = _buckets[_Hash(path)]; e; e = e->next) {
508 if (e->value.first == path)
518 std::pair<iterator, iterator>
520 std::pair<iterator, iterator>
result;
521 result.first =
find(path);
522 result.second = result.first.GetNextSubtree();
529 std::pair<const_iterator, const_iterator>
531 std::pair<const_iterator, const_iterator>
result;
532 result.first =
find(path);
533 result.second = result.first.GetNextSubtree();
543 inline size_t size()
const {
return _size; }
564 _UpdateTreeForNewEntry(result);
580 _UpdateTreeForNewEntry(result);
599 for (
size_t i = 0,
n = _buckets.size(); i !=
n; ++i) {
600 _Entry *entry = _buckets[i];
602 _Entry *next = entry->next;
615 [](
void*& voidEntry) {
616 _Entry *entry =
static_cast<_Entry *
>(voidEntry);
618 _Entry *next = entry->next;
625 _buckets.size(), visitFn);
631 _buckets.swap(other._buckets);
638 std::vector<size_t>
sizes(_buckets.size(), 0u);;
639 for (
size_t i = 0,
n = _buckets.size(); i !=
n; ++i) {
640 for (_Entry *entry = _buckets[i]; entry; entry = entry->next) {
658 for (
iterator i=range.first; i!=range.second; ++i) {
660 i->first.ReplacePrefix(oldName, newName),
664 if (range.first != range.second)
673 template <
typename Callback>
676 [&visitFn](
void*& voidEntry) {
677 _Entry *entry =
static_cast<_Entry *
>(voidEntry);
679 visitFn(std::cref(entry->value.first),
685 _buckets.size(), lambda);
690 template <
typename Callback>
693 [&visitFn](
void*& voidEntry) {
694 const _Entry *entry =
static_cast<const _Entry *
>(voidEntry);
696 visitFn(std::cref(entry->value.first),
697 std::cref(entry->value.second));
703 reinterpret_cast<void **>(const_cast<_Entry**>(_buckets.data())),
704 _buckets.size(), lambda);
718 _Entry *
const newEntry = iresult.first._entry;
719 SdfPath const &parentPath = _GetParentPath(newEntry->value.first);
724 parIter._entry->AddChild(newEntry);
730 template <
class MakeEntryFn>
732 MakeEntryFn &&makeEntry) {
738 _Entry **bucketHead = &(_buckets[_Hash(key)]);
739 for (_Entry *e = *bucketHead; e; e = e->next) {
740 if (e->value.first == key) {
749 bucketHead = &(_buckets[_Hash(key)]);
753 *bucketHead = std::forward<MakeEntryFn>(makeEntry)(*bucketHead);
763 return _InsertInTableImpl(
764 value.first, [&value](_Entry *next) {
765 return new _Entry(value, next);
770 return _InsertInTableImpl(
771 node.GetKey(), [&node](_Entry *next)
mutable {
772 node._unlinkedEntry->next = next;
773 return node._unlinkedEntry.release();
778 void _EraseFromTable(_Entry *entry) {
780 _Entry **cur = &_buckets[_Hash(entry->value.first)];
781 while (*cur != entry)
782 cur = &((*cur)->next);
792 void _EraseSubtree(_Entry *entry) {
794 if (_Entry *
const firstChild = entry->firstChild) {
795 _EraseSubtreeAndSiblings(firstChild);
796 _EraseFromTable(firstChild);
802 void _EraseSubtreeAndSiblings(_Entry *entry) {
804 _EraseSubtree(entry);
807 _Entry *sibling = entry->GetNextSibling();
808 _Entry *nextSibling = sibling ? sibling->GetNextSibling() :
nullptr;
810 _EraseSubtree(sibling);
811 _EraseFromTable(sibling);
812 sibling = nextSibling;
813 nextSibling = sibling ? sibling->GetNextSibling() :
nullptr;
819 void _RemoveFromParent(_Entry *entry) {
824 iterator parIter =
find(_GetParentPath(entry->value.first));
827 parIter._entry->RemoveChild(entry);
834 TfAutoMallocTag2 tag2(
"Sdf",
"SdfPathTable::_Grow");
839 _mask =
std::max(
size_t(7), (_mask << 1) + 1);
840 _BucketVec newBuckets(_mask + 1);
843 for (
size_t i = 0,
n = _buckets.size(); i !=
n; ++i) {
844 _Entry *elem = _buckets[i];
847 _Entry *next = elem->next;
850 _Entry *&m = newBuckets[_Hash(elem->value.first)];
862 _buckets.swap(newBuckets);
866 bool _IsTooFull()
const {
867 return _size > _buckets.size();
871 inline size_t _Hash(
SdfPath const &path)
const {
884 #endif // PXR_USD_SDF_PATH_TABLE_H
void ParallelForEach(Callback const &visitFn) const
GLuint GLsizei const GLuint const GLintptr const GLsizeiptr * sizes
const_iterator begin() const
Return a const_iterator to the start of the table.
_IterBoolPair insert(NodeHandle &&node)
static SDF_API const SdfPath & AbsoluteRootPath()
~SdfPathTable()
Destructor.
key_type & GetMutableKey()
SdfPathTable()
Default constructor.
SdfPathTable & operator=(SdfPathTable const &other)
Copy assignment.
const_iterator end() const
Return a const_iterator denoting the end of the table.
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)
const_iterator find(SdfPath const &path) const
SdfPathTable & operator=(SdfPathTable &&other)
Move assignment.
GLsizei const GLfloat * value
GLsizei const GLchar *const * path
mapped_type const & GetMapped() const
Iterator GetNextSubtree() const
bool IsEmpty() const noexcept
Returns true if this is the empty path (SdfPath::EmptyPath()).
void ParallelForEach(Callback const &visitFn)
void UpdateForRename(const SdfPath &oldName, const SdfPath &newName)
**But if you need a result
static NodeHandle New(value_type &&value)
Iterator(Iterator< OtherVal, OtherEntryPtr > const &other)
Copy constructor (also allows for converting non-const to const).
static NodeHandle New(key_type const &key, mapped_type const &mapped)
size_t GetHash() const
Equality operator.
friend class hboost::iterator_core_access
iterator find(SdfPath const &path)
mapped_type & GetMutableMapped()
#define __ARCH_PRETTY_FUNCTION__
void erase(iterator const &i)
static NodeHandle New(value_type const &value)
SdfPathTable(SdfPathTable const &other)
Copy constructor.
std::pair< iterator, iterator > FindSubtreeRange(SdfPath const &path)
key_type const & GetKey() const
Iterator< const value_type, const _Entry * > const_iterator
iterator begin()
Return an iterator to the start of the table.
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
size_t size() const
Return the number of elements in the table.
bool equal(Iterator< OtherVal, OtherEntryPtr > const &other) const
size_t count(SdfPath const &path) const
Return 1 if there is an element for path in the table, otherwise 0.
SdfPathTable(SdfPathTable &&other)
Move constructor.
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
#define PXR_NAMESPACE_CLOSE_SCOPE
std::pair< const_iterator, const_iterator > FindSubtreeRange(SdfPath const &path) const
SDF_API SdfPath GetParentPath() const
bool erase(SdfPath const &path)
mapped_type & operator[](SdfPath const &path)
PXR_NAMESPACE_OPEN_SCOPE SDF_API void Sdf_VisitPathTableInParallel(void **, size_t, TfFunctionRef< void(void *&)>)
bool empty() const
Return true if this table is empty.
std::pair< iterator, bool > _IterBoolPair
Result type for insert().
std::pair< key_type, mapped_type > value_type
Iterator< value_type, _Entry * > iterator
_IterBoolPair insert(value_type const &value)
std::vector< size_t > GetBucketSizes() const
Return a vector of the count of elements in each bucket.
ValType & dereference() const
FMT_CONSTEXPR auto find(Ptr first, Ptr last, T value, Ptr &out) -> bool
void swap(SdfPathTable &other)
Swap this table's contents with other.
iterator end()
Return an iterator denoting the end of the table.