This document is for a version of USD that is under development. See this page for the current release.
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
pathTable.h
1//
2// Copyright 2016 Pixar
3//
4// Licensed under the terms set forth in the LICENSE.txt file available at
5// https://openusd.org/license.
6//
7#ifndef PXR_USD_SDF_PATH_TABLE_H
8#define PXR_USD_SDF_PATH_TABLE_H
9
10#include "pxr/pxr.h"
11#include "pxr/usd/sdf/api.h"
12#include "pxr/usd/sdf/path.h"
13#include "pxr/base/tf/pointerAndBits.h"
14#include "pxr/base/tf/functionRef.h"
15
16#include <algorithm>
17#include <utility>
18#include <vector>
19
20PXR_NAMESPACE_OPEN_SCOPE
21
22// Parallel visitation helper function.
23SDF_API
24void Sdf_VisitPathTableInParallel(void **, size_t, TfFunctionRef<void(void*&)>);
25
64template <class MappedType>
66{
67public:
68
69 typedef SdfPath key_type;
70 typedef MappedType mapped_type;
71 typedef std::pair<key_type, mapped_type> value_type;
72
73private:
74
75 // An _Entry represents an item in the table. It holds the item's value, a
76 // pointer (\a next) to the next item in the hash bucket's linked list, and
77 // two pointers (\a firstChild and \a nextSibling) that describe the tree
78 // structure.
79 struct _Entry {
80 _Entry(const _Entry&) = delete;
81 _Entry& operator=(const _Entry&) = delete;
82 _Entry(value_type const &value, _Entry *n)
83 : value(value)
84 , next(n)
85 , firstChild(nullptr)
86 , nextSiblingOrParent(nullptr, false) {}
87
88 _Entry(value_type &&value, _Entry *n)
89 : value(std::move(value))
90 , next(n)
91 , firstChild(nullptr)
92 , nextSiblingOrParent(nullptr, false) {}
93
94 // If this entry's nextSiblingOrParent field points to a sibling, return
95 // a pointer to it, otherwise return null.
96 _Entry *GetNextSibling() {
97 return nextSiblingOrParent.template BitsAs<bool>() ?
98 nextSiblingOrParent.Get() : 0;
99 }
100 // If this entry's nextSiblingOrParent field points to a sibling, return
101 // a pointer to it, otherwise return null.
102 _Entry const *GetNextSibling() const {
103 return nextSiblingOrParent.template BitsAs<bool>() ?
104 nextSiblingOrParent.Get() : 0;
105 }
106
107 // If this entry's nextSiblingOrParent field points to a parent, return
108 // a pointer to it, otherwise return null.
109 _Entry *GetParentLink() {
110 return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
111 nextSiblingOrParent.Get();
112 }
113 // If this entry's nextSiblingOrParent field points to a parent, return
114 // a pointer to it, otherwise return null.
115 _Entry const *GetParentLink() const {
116 return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
117 nextSiblingOrParent.Get();
118 }
119
120 // Set this entry's nextSiblingOrParent field to point to the passed
121 // sibling.
122 void SetSibling(_Entry *sibling) {
123 nextSiblingOrParent.Set(sibling, /* isSibling */ true);
124 }
125
126 // Set this entry's nextSiblingOrParent field to point to the passed
127 // parent.
128 void SetParentLink(_Entry *parent) {
129 nextSiblingOrParent.Set(parent, /* isSibling */ false);
130 }
131
132 // Add \a child as a child of this entry.
133 void AddChild(_Entry *child) {
134 // If there are already one or more children, make \a child be our
135 // new first child. Otherwise, add \a child as the first child.
136 if (firstChild)
137 child->SetSibling(firstChild);
138 else
139 child->SetParentLink(this);
140 firstChild = child;
141 }
142
143 void RemoveChild(_Entry *child) {
144 // Remove child from this _Entry's children.
145 if (child == firstChild) {
146 firstChild = child->GetNextSibling();
147 } else {
148 // Search the list to find the preceding child, then unlink the
149 // child to remove.
150 _Entry *prev, *cur = firstChild;
151 do {
152 prev = cur;
153 cur = prev->GetNextSibling();
154 } while (cur != child);
155 prev->nextSiblingOrParent = cur->nextSiblingOrParent;
156 }
157 }
158
159 // The value object mapped by this entry.
160 value_type value;
161
162 // The next field links together entries in chained hash table buckets.
163 _Entry *next;
164
165 // The firstChild and nextSiblingOrParent fields describe the tree
166 // structure of paths. An entry has one or more children when
167 // firstChild is non null. Its chlidren are stored in a singly linked
168 // list, where nextSiblingOrParent points to the next entry in the list.
169 //
170 // The end of the list is reached when the bit stored in
171 // nextSiblingOrParent is set false, indicating a pointer to the parent
172 // rather than another sibling.
173 _Entry *firstChild;
174 TfPointerAndBits<_Entry> nextSiblingOrParent;
175 };
176
177 // Hash table's list of buckets is a vector of _Entry ptrs.
178 typedef std::vector<_Entry *> _BucketVec;
179
180public:
181
182 // The iterator class, used to make both const and non-const
183 // iterators. Currently only forward traversal is supported.
184 template <class, class> friend class Iterator;
185 template <class ValType, class EntryPtr>
186 class Iterator
187 {
188 public:
189 using iterator_category = std::forward_iterator_tag;
190 using value_type = ValType;
191 using reference = ValType&;
192 using pointer = ValType*;
193 using difference_type = std::ptrdiff_t;
194
197 Iterator() = default;
198
200 template <class OtherVal, class OtherEntryPtr>
201 Iterator(Iterator<OtherVal, OtherEntryPtr> const &other)
202 : _entry(other._entry)
203 {}
204
205 reference operator*() const { return dereference(); }
206 pointer operator->() const { return &(dereference()); }
207
208 Iterator& operator++() {
209 increment();
210 return *this;
211 }
212
213 Iterator operator++(int) {
214 Iterator result(*this);
215 increment();
216 return result;
217 }
218
219 template <class OtherVal, class OtherEntryPtr>
220 bool operator==(Iterator<OtherVal, OtherEntryPtr> const &other) const {
221 return equal(other);
222 }
223
224 template <class OtherVal, class OtherEntryPtr>
225 bool operator!=(Iterator<OtherVal, OtherEntryPtr> const &other) const {
226 return !equal(other);
227 }
228
232 Iterator GetNextSubtree() const {
233 Iterator result(0);
234 if (_entry) {
235 if (EntryPtr sibling = _entry->GetNextSibling()) {
236 // Next subtree is next sibling, if present.
237 result._entry = sibling;
238 } else {
239 // Otherwise, walk up parents until we either find one with
240 // a next sibling or run out.
241 for (EntryPtr p = _entry->GetParentLink(); p;
242 p = p->GetParentLink()) {
243 if (EntryPtr sibling = p->GetNextSibling()) {
244 result._entry = sibling;
245 break;
246 }
247 }
248 }
249 }
250 return result;
251 }
252
255 bool HasChild() const {
256 return bool(_entry->firstChild);
257 }
258
259 protected:
260 friend class SdfPathTable;
261 template <class, class> friend class Iterator;
262
263 explicit Iterator(EntryPtr entry)
264 : _entry(entry) {}
265
266 // Fundamental functionality to implement the iterator.
267
268 // Iterator increment.
269 inline void increment() {
270 // Move to first child, if present. Otherwise move to next subtree.
271 _entry = _entry->firstChild ? _entry->firstChild :
272 GetNextSubtree()._entry;
273 }
274
275 // Equality comparison. A template, to allow comparison between const
276 // and non-const iterators.
277 template <class OtherVal, class OtherEntryPtr>
278 bool equal(Iterator<OtherVal, OtherEntryPtr> const &other) const {
279 return _entry == other._entry;
280 }
281
282 // Dereference.
283 ValType &dereference() const {
284 return _entry->value;
285 }
286
287 // Store pointer to current entry.
288 EntryPtr _entry;
289 };
290
291 typedef Iterator<value_type, _Entry *> iterator;
292 typedef Iterator<const value_type, const _Entry *> const_iterator;
293
295 typedef std::pair<iterator, bool> _IterBoolPair;
296
302 {
303 friend class SdfPathTable;
304
309 static NodeHandle
310 New(value_type const &value) {
311 NodeHandle ret;
312 ret._unlinkedEntry.reset(new _Entry(value, nullptr));
313 return ret;
314 }
315
317 static NodeHandle
318 New(value_type &&value) {
319 NodeHandle ret;
320 ret._unlinkedEntry.reset(new _Entry(std::move(value), nullptr));
321 return ret;
322 }
323
325 static NodeHandle
326 New(key_type const &key, mapped_type const &mapped) {
327 return New({ key, mapped });
328 }
329
333 key_type const &GetKey() const {
334 return _unlinkedEntry->value.first;
335 }
336
341 return _unlinkedEntry->value.first;
342 }
343
347 mapped_type const &GetMapped() const {
348 return _unlinkedEntry->value.second;
349 }
350
354 mapped_type &GetMutableMapped() {
355 return _unlinkedEntry->value.second;
356 }
357
360 bool IsValid() const {
361 return static_cast<bool>(_unlinkedEntry);
362 }
363
366 explicit operator bool() const {
367 return IsValid();
368 }
369
372 void reset() {
373 _unlinkedEntry.reset();
374 }
375
376 private:
377 std::unique_ptr<_Entry> _unlinkedEntry;
378 };
379
381 SdfPathTable() : _size(0), _mask(0) {}
382
385 : _buckets(other._buckets.size())
386 , _size(0) // size starts at 0, since we insert elements.
387 , _mask(other._mask)
388 {
389 // Walk all elements in the other container, inserting into this one,
390 // and creating the right child/sibling links along the way.
391 for (const_iterator i = other.begin(), end = other.end();
392 i != end; ++i) {
393 iterator j = _InsertInTable(*i).first;
394 // Ensure first child and next sibling links are created.
395 if (i._entry->firstChild && !j._entry->firstChild) {
396 j._entry->firstChild =
397 _InsertInTable(i._entry->firstChild->value).first._entry;
398 }
399 // Ensure the nextSibling/parentLink is created.
400 if (i._entry->nextSiblingOrParent.Get() &&
401 !j._entry->nextSiblingOrParent.Get()) {
402 j._entry->nextSiblingOrParent.Set(
403 _InsertInTable(i._entry->nextSiblingOrParent.
404 Get()->value).first._entry,
405 i._entry->nextSiblingOrParent.template BitsAs<bool>());
406 }
407 }
408 }
409
412 : _buckets(std::move(other._buckets))
413 , _size(other._size)
414 , _mask(other._mask)
415 {
416 other._size = 0;
417 other._mask = 0;
418 }
419
422 // Call clear to free all nodes.
423 clear();
424 }
425
428 if (this != &other)
429 SdfPathTable(other).swap(*this);
430 return *this;
431 }
432
435 if (this != &other)
436 SdfPathTable(std::move(other)).swap(*this);
437 return *this;
438 }
439
441 iterator begin() {
442 // Return an iterator pointing to the root if this table isn't empty.
443 if (empty())
444 return end();
446 }
447
449 const_iterator begin() const {
450 // Return an iterator pointing to the root if this table isn't empty.
451 if (empty())
452 return end();
454 }
455
457 iterator end() {
458 return iterator(0);
459 }
460
462 const_iterator end() const {
463 return const_iterator(0);
464 }
465
472 bool erase(SdfPath const &path) {
473 iterator i = find(path);
474 if (i == end())
475 return false;
476 erase(i);
477 return true;
478 }
479
486 void erase(iterator const &i) {
487 // Delete descendant nodes, if any. Then remove from parent, finally
488 // erase from hash table.
489 _Entry * const entry = i._entry;
490 _EraseSubtree(entry);
491 _RemoveFromParent(entry);
492 _EraseFromTable(entry);
493 }
494
497 iterator find(SdfPath const &path) {
498 if (!empty()) {
499 // Find the item in the list.
500 for (_Entry *e = _buckets[_Hash(path)]; e; e = e->next) {
501 if (e->value.first == path)
502 return iterator(e);
503 }
504 }
505 return end();
506 }
507
510 const_iterator find(SdfPath const &path) const {
511 if (!empty()) {
512 // Find the item in the list.
513 for (_Entry const *e = _buckets[_Hash(path)]; e; e = e->next) {
514 if (e->value.first == path)
515 return const_iterator(e);
516 }
517 }
518 return end();
519 }
520
524 std::pair<iterator, iterator>
526 std::pair<iterator, iterator> result;
527 result.first = find(path);
528 result.second = result.first.GetNextSubtree();
529 return result;
530 }
531
535 std::pair<const_iterator, const_iterator>
536 FindSubtreeRange(SdfPath const &path) const {
537 std::pair<const_iterator, const_iterator> result;
538 result.first = find(path);
539 result.second = result.first.GetNextSubtree();
540 return result;
541 }
542
544 size_t count(SdfPath const &path) const {
545 return find(path) != end();
546 }
547
549 inline size_t size() const { return _size; }
550
552 inline bool empty() const { return !size(); }
553
565 _IterBoolPair insert(value_type const &value) {
566 // Insert in table.
567 _IterBoolPair result = _InsertInTable(value);
568 if (result.second) {
569 // New element -- make sure the parent is inserted.
570 _UpdateTreeForNewEntry(result);
571 }
572 return result;
573 }
574
582 // Insert in table.
583 _IterBoolPair result = _InsertInTable(std::move(node));
584 if (result.second) {
585 // New element -- make sure the parent is inserted.
586 _UpdateTreeForNewEntry(result);
587 }
588 return result;
589 }
590
595 mapped_type &operator[](SdfPath const &path) {
596 return insert(value_type(path, mapped_type())).first->second;
597 }
598
603 void clear() {
604 // Note this leaves the size of _buckets unchanged.
605 for (size_t i = 0, n = _buckets.size(); i != n; ++i) {
606 _Entry *entry = _buckets[i];
607 while (entry) {
608 _Entry *next = entry->next;
609 delete entry;
610 entry = next;
611 }
612 _buckets[i] = 0;
613 }
614 _size = 0;
615 }
616
620 auto visitFn =
621 [](void*& voidEntry) {
622 _Entry *entry = static_cast<_Entry *>(voidEntry);
623 while (entry) {
624 _Entry *next = entry->next;
625 delete entry;
626 entry = next;
627 }
628 voidEntry = nullptr;
629 };
630 Sdf_VisitPathTableInParallel(reinterpret_cast<void **>(_buckets.data()),
631 _buckets.size(), visitFn);
632 _size = 0;
633 }
634
636 void swap(SdfPathTable &other) {
637 _buckets.swap(other._buckets);
638 std::swap(_size, other._size);
639 std::swap(_mask, other._mask);
640 }
641
643 std::vector<size_t> GetBucketSizes() const {
644 std::vector<size_t> sizes(_buckets.size(), 0u);;
645 for (size_t i = 0, n = _buckets.size(); i != n; ++i) {
646 for (_Entry *entry = _buckets[i]; entry; entry = entry->next) {
647 sizes[i]++;
648 }
649 }
650 return sizes;
651 }
652
656 void UpdateForRename(const SdfPath &oldName, const SdfPath &newName) {
657
658 if (oldName.GetParentPath() != newName.GetParentPath()) {
659 TF_CODING_ERROR("Unexpected arguments.");
660 return;
661 }
662
663 std::pair<iterator, iterator> range = FindSubtreeRange(oldName);
664 for (iterator i=range.first; i!=range.second; ++i) {
665 insert(value_type(
666 i->first.ReplacePrefix(oldName, newName),
667 i->second));
668 }
669
670 if (range.first != range.second)
671 erase(oldName);
672 }
673
679 template <typename Callback>
680 void ParallelForEach(Callback const& visitFn) {
681 auto lambda =
682 [&visitFn](void*& voidEntry) {
683 _Entry *entry = static_cast<_Entry *>(voidEntry);
684 while (entry) {
685 visitFn(std::cref(entry->value.first),
686 std::ref(entry->value.second));
687 entry = entry->next;
688 }
689 };
690 Sdf_VisitPathTableInParallel(reinterpret_cast<void **>(_buckets.data()),
691 _buckets.size(), lambda);
692 }
693
696 template <typename Callback>
697 void ParallelForEach(Callback const& visitFn) const {
698 auto lambda =
699 [&visitFn](void*& voidEntry) {
700 const _Entry *entry = static_cast<const _Entry *>(voidEntry);
701 while (entry) {
702 visitFn(std::cref(entry->value.first),
703 std::cref(entry->value.second));
704 entry = entry->next;
705 }
706 };
707 Sdf_VisitPathTableInParallel(
708 // Note: the const cast here is undone by the static cast above...
709 reinterpret_cast<void **>(const_cast<_Entry**>(_buckets.data())),
710 _buckets.size(), lambda);
711 }
712
713private:
714
715 // Helper to get parent paths.
716 static SdfPath _GetParentPath(SdfPath const &path) {
717 return path.GetParentPath();
718 }
719
720 void _UpdateTreeForNewEntry(_IterBoolPair const &iresult) {
721 // New element -- make sure the parent is inserted.
722 _Entry * const newEntry = iresult.first._entry;
723 SdfPath const &parentPath = _GetParentPath(newEntry->value.first);
724 if (!parentPath.IsEmpty()) {
725 iterator parIter =
726 insert(value_type(parentPath, mapped_type())).first;
727 // Add the new entry to the parent's children.
728 parIter._entry->AddChild(newEntry);
729 }
730 }
731
732 // Helper to insert \a value in the hash table. Is responsible for growing
733 // storage space when necessary. Does not consider the tree structure.
734 template <class MakeEntryFn>
735 _IterBoolPair _InsertInTableImpl(key_type const &key,
736 MakeEntryFn &&makeEntry) {
737 // If we have no storage at all so far, grow.
738 if (_mask == 0)
739 _Grow();
740
741 // Find the item, if present.
742 _Entry **bucketHead = &(_buckets[_Hash(key)]);
743 for (_Entry *e = *bucketHead; e; e = e->next) {
744 if (e->value.first == key) {
745 return _IterBoolPair(iterator(e), false);
746 }
747 }
748
749 // Not present. If the table is getting full then grow and re-find the
750 // bucket.
751 if (_IsTooFull()) {
752 _Grow();
753 bucketHead = &(_buckets[_Hash(key)]);
754 }
755
756 // Make an entry and insert it in the list.
757 *bucketHead = std::forward<MakeEntryFn>(makeEntry)(*bucketHead);
758
759 // One more element
760 ++_size;
761
762 // Return the new item
763 return _IterBoolPair(iterator(*bucketHead), true);
764 }
765
766 _IterBoolPair _InsertInTable(value_type const &value) {
767 return _InsertInTableImpl(
768 value.first, [&value](_Entry *next) {
769 return new _Entry(value, next);
770 });
771 }
772
773 _IterBoolPair _InsertInTable(NodeHandle &&node) {
774 return _InsertInTableImpl(
775 node.GetKey(), [&node](_Entry *next) mutable {
776 node._unlinkedEntry->next = next;
777 return node._unlinkedEntry.release();
778 });
779 }
780
781 // Erase \a entry from the hash table. Does not consider tree structure.
782 void _EraseFromTable(_Entry *entry) {
783 // Remove from table.
784 _Entry **cur = &_buckets[_Hash(entry->value.first)];
785 while (*cur != entry)
786 cur = &((*cur)->next);
787
788 // Unlink item and destroy it
789 --_size;
790 _Entry *tmp = *cur;
791 *cur = tmp->next;
792 delete tmp;
793 }
794
795 // Erase all the tree structure descendants of \a entry from the table.
796 void _EraseSubtree(_Entry *entry) {
797 // Delete descendant nodes, if any.
798 if (_Entry * const firstChild = entry->firstChild) {
799 _EraseSubtreeAndSiblings(firstChild);
800 _EraseFromTable(firstChild);
801 }
802 }
803
804 // Erase all the tree structure descendants and siblings of \a entry from
805 // the table.
806 void _EraseSubtreeAndSiblings(_Entry *entry) {
807 // Remove subtree.
808 _EraseSubtree(entry);
809
810 // And siblings.
811 _Entry *sibling = entry->GetNextSibling();
812 _Entry *nextSibling = sibling ? sibling->GetNextSibling() : nullptr;
813 while (sibling) {
814 _EraseSubtree(sibling);
815 _EraseFromTable(sibling);
816 sibling = nextSibling;
817 nextSibling = sibling ? sibling->GetNextSibling() : nullptr;
818 }
819 }
820
821 // Remove \a entry from its parent's list of children in the tree structure
822 // alone. Does not consider the table.
823 void _RemoveFromParent(_Entry *entry) {
824 if (entry->value.first == SdfPath::AbsoluteRootPath())
825 return;
826
827 // Find parent in table.
828 iterator parIter = find(_GetParentPath(entry->value.first));
829
830 // Remove this entry from the parent's children.
831 parIter._entry->RemoveChild(entry);
832 }
833
834 // Grow the table's number of buckets to the next larger size. Rehashes the
835 // elements into the new table, but leaves tree structure untouched. (The
836 // tree structure need not be modified).
837 void _Grow() {
838 TfAutoMallocTag2 tag2("Sdf", "SdfPathTable::_Grow");
839 TfAutoMallocTag tag(__ARCH_PRETTY_FUNCTION__);
840
841 // Allocate a new bucket list of twice the size. Minimum nonzero number
842 // of buckets is 8.
843 _mask = std::max(size_t(7), (_mask << 1) + 1);
844 _BucketVec newBuckets(_mask + 1);
845
846 // Move items to a new bucket list
847 for (size_t i = 0, n = _buckets.size(); i != n; ++i) {
848 _Entry *elem = _buckets[i];
849 while (elem) {
850 // Save pointer to next item
851 _Entry *next = elem->next;
852
853 // Get the bucket in the new list
854 _Entry *&m = newBuckets[_Hash(elem->value.first)];
855
856 // Insert the item at the head
857 elem->next = m;
858 m = elem;
859
860 // Next item
861 elem = next;
862 }
863 }
864
865 // Use the new buckets
866 _buckets.swap(newBuckets);
867 }
868
869 // Return true if the table should be made bigger.
870 bool _IsTooFull() const {
871 return _size > _buckets.size();
872 }
873
874 // Return the bucket index for \a path.
875 inline size_t _Hash(SdfPath const &path) const {
876 return path.GetHash() & _mask;
877 }
878
879private:
880 _BucketVec _buckets;
881 size_t _size;
882 size_t _mask;
883
884};
885
886PXR_NAMESPACE_CLOSE_SCOPE
887
888#endif // PXR_USD_SDF_PATH_TABLE_H
A path value used to locate objects in layers or scenegraphs.
Definition: path.h:274
SDF_API SdfPath GetParentPath() const
Return the path that identifies this path's namespace parent.
static SDF_API const SdfPath & AbsoluteRootPath()
The absolute path representing the top of the namespace hierarchy.
bool IsEmpty() const noexcept
Returns true if this is the empty path (SdfPath::EmptyPath()).
Definition: path.h:398
A mapping from SdfPath to MappedType, somewhat similar to map<SdfPath, MappedType> and TfHashMap<SdfP...
Definition: pathTable.h:66
void ParallelForEach(Callback const &visitFn)
ParallelForEach: parallel iteration over all of the key-value pairs in the path table.
Definition: pathTable.h:680
void erase(iterator const &i)
Remove the element pointed to by i from the table as well as all elements whose paths are prefixed by...
Definition: pathTable.h:486
mapped_type & operator[](SdfPath const &path)
Shorthand for the following, where t is an SdfPathTable<T>.
Definition: pathTable.h:595
iterator find(SdfPath const &path)
Return an iterator to the element corresponding to path, or end() if there is none.
Definition: pathTable.h:497
size_t size() const
Return the number of elements in the table.
Definition: pathTable.h:549
void ParallelForEach(Callback const &visitFn) const
ParallelForEach: const version, runnable on a const path table and taking a (const SdfPath&,...
Definition: pathTable.h:697
const_iterator begin() const
Return a const_iterator to the start of the table.
Definition: pathTable.h:449
_IterBoolPair insert(value_type const &value)
Insert value into the table, and additionally insert default entries for all ancestral paths of value...
Definition: pathTable.h:565
_IterBoolPair insert(NodeHandle &&node)
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: pathTable.h:581
bool empty() const
Return true if this table is empty.
Definition: pathTable.h:552
std::pair< iterator, bool > _IterBoolPair
Result type for insert().
Definition: pathTable.h:295
~SdfPathTable()
Destructor.
Definition: pathTable.h:421
SdfPathTable(SdfPathTable const &other)
Copy constructor.
Definition: pathTable.h:384
void ClearInParallel()
Equivalent to clear(), but destroy contained objects in parallel.
Definition: pathTable.h:619
std::pair< iterator, iterator > FindSubtreeRange(SdfPath const &path)
Return a pair of iterators [b, e), describing the maximal range such that for all i in the range,...
Definition: pathTable.h:525
std::vector< size_t > GetBucketSizes() const
Return a vector of the count of elements in each bucket.
Definition: pathTable.h:643
const_iterator find(SdfPath const &path) const
Return a const_iterator to the element corresponding to path, or end() if there is none.
Definition: pathTable.h:510
bool erase(SdfPath const &path)
Remove the element with path path from the table as well as all elements whose paths are prefixed by ...
Definition: pathTable.h:472
void swap(SdfPathTable &other)
Swap this table's contents with other.
Definition: pathTable.h:636
void clear()
Remove all elements from the table, leaving size() == 0.
Definition: pathTable.h:603
SdfPathTable & operator=(SdfPathTable const &other)
Copy assignment.
Definition: pathTable.h:427
iterator end()
Return an iterator denoting the end of the table.
Definition: pathTable.h:457
const_iterator end() const
Return a const_iterator denoting the end of the table.
Definition: pathTable.h:462
iterator begin()
Return an iterator to the start of the table.
Definition: pathTable.h:441
SdfPathTable & operator=(SdfPathTable &&other)
Move assignment.
Definition: pathTable.h:434
void UpdateForRename(const SdfPath &oldName, const SdfPath &newName)
Replaces all prefixes from oldName to newName.
Definition: pathTable.h:656
size_t count(SdfPath const &path) const
Return 1 if there is an element for path in the table, otherwise 0.
Definition: pathTable.h:544
std::pair< const_iterator, const_iterator > FindSubtreeRange(SdfPath const &path) const
Return a pair of const_iterators [b, e), describing the maximal range such that for all i in the rang...
Definition: pathTable.h:536
SdfPathTable(SdfPathTable &&other)
Move constructor.
Definition: pathTable.h:411
SdfPathTable()
Default constructor.
Definition: pathTable.h:381
This class provides a non-owning reference to a type-erased callable object with a specified signatur...
Definition: functionRef.h:19
Scoped (i.e.
Definition: mallocTag.h:249
This class stores a T * and a small integer in the space of a T *.
#define TF_CODING_ERROR(fmt, args)
Issue an internal programming error, but continue execution.
Definition: diagnostic.h:68
STL namespace.
A handle owning a path table node that may be used to "reserve" a stable memory location for key & ma...
Definition: pathTable.h:302
static NodeHandle New(key_type const &key, mapped_type const &mapped)
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: pathTable.h:326
mapped_type const & GetMapped() const
Return a const reference to this NodeHandle's mapped object.
Definition: pathTable.h:347
key_type & GetMutableKey()
Return a mutable reference to this NodeHandle's key.
Definition: pathTable.h:340
key_type const & GetKey() const
Return a const reference to this NodeHandle's key.
Definition: pathTable.h:333
static NodeHandle New(value_type &&value)
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: pathTable.h:318
bool IsValid() const
Return true if this NodeHandle owns a path table entry, false otherwise.
Definition: pathTable.h:360
void reset()
Delete any owned path table entry.
Definition: pathTable.h:372
mapped_type & GetMutableMapped()
Return a mutable reference to this NodeHandle's mapped object.
Definition: pathTable.h:354
static NodeHandle New(value_type const &value)
Create a new NodeHandle for a table entry.
Definition: pathTable.h:310