pathTable.h
1 //
2 // Copyright 2016 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 #ifndef PXR_USD_SDF_PATH_TABLE_H
25 #define PXR_USD_SDF_PATH_TABLE_H
26 
27 #include "pxr/pxr.h"
28 #include "pxr/usd/sdf/api.h"
29 #include "pxr/usd/sdf/path.h"
30 #include "pxr/base/tf/pointerAndBits.h"
31 #include "pxr/base/tf/functionRef.h"
32 
33 #include <boost/iterator/iterator_facade.hpp>
34 #include <boost/noncopyable.hpp>
35 
36 #include <algorithm>
37 #include <utility>
38 #include <vector>
39 
40 PXR_NAMESPACE_OPEN_SCOPE
41 
42 // Parallel visitation helper function.
43 SDF_API
44 void Sdf_VisitPathTableInParallel(void **, size_t, TfFunctionRef<void(void*&)>);
45 
84 template <class MappedType>
86 {
87 public:
88 
89  typedef SdfPath key_type;
90  typedef MappedType mapped_type;
91  typedef std::pair<key_type, mapped_type> value_type;
92 
93 private:
94 
95  // An _Entry represents an item in the table. It holds the item's value, a
96  // pointer (\a next) to the next item in the hash bucket's linked list, and
97  // two pointers (\a firstChild and \a nextSibling) that describe the tree
98  // structure.
99  struct _Entry : boost::noncopyable {
100  _Entry(value_type const &value, _Entry *n)
101  : value(value)
102  , next(n)
103  , firstChild(nullptr)
104  , nextSiblingOrParent(nullptr, false) {}
105 
106  _Entry(value_type &&value, _Entry *n)
107  : value(std::move(value))
108  , next(n)
109  , firstChild(nullptr)
110  , nextSiblingOrParent(nullptr, false) {}
111 
112  // If this entry's nextSiblingOrParent field points to a sibling, return
113  // a pointer to it, otherwise return null.
114  _Entry *GetNextSibling() {
115  return nextSiblingOrParent.template BitsAs<bool>() ?
116  nextSiblingOrParent.Get() : 0;
117  }
118  // If this entry's nextSiblingOrParent field points to a sibling, return
119  // a pointer to it, otherwise return null.
120  _Entry const *GetNextSibling() const {
121  return nextSiblingOrParent.template BitsAs<bool>() ?
122  nextSiblingOrParent.Get() : 0;
123  }
124 
125  // If this entry's nextSiblingOrParent field points to a parent, return
126  // a pointer to it, otherwise return null.
127  _Entry *GetParentLink() {
128  return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
129  nextSiblingOrParent.Get();
130  }
131  // If this entry's nextSiblingOrParent field points to a parent, return
132  // a pointer to it, otherwise return null.
133  _Entry const *GetParentLink() const {
134  return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
135  nextSiblingOrParent.Get();
136  }
137 
138  // Set this entry's nextSiblingOrParent field to point to the passed
139  // sibling.
140  void SetSibling(_Entry *sibling) {
141  nextSiblingOrParent.Set(sibling, /* isSibling */ true);
142  }
143 
144  // Set this entry's nextSiblingOrParent field to point to the passed
145  // parent.
146  void SetParentLink(_Entry *parent) {
147  nextSiblingOrParent.Set(parent, /* isSibling */ false);
148  }
149 
150  // Add \a child as a child of this entry.
151  void AddChild(_Entry *child) {
152  // If there are already one or more children, make \a child be our
153  // new first child. Otherwise, add \a child as the first child.
154  if (firstChild)
155  child->SetSibling(firstChild);
156  else
157  child->SetParentLink(this);
158  firstChild = child;
159  }
160 
161  void RemoveChild(_Entry *child) {
162  // Remove child from this _Entry's children.
163  if (child == firstChild) {
164  firstChild = child->GetNextSibling();
165  } else {
166  // Search the list to find the preceding child, then unlink the
167  // child to remove.
168  _Entry *prev, *cur = firstChild;
169  do {
170  prev = cur;
171  cur = prev->GetNextSibling();
172  } while (cur != child);
173  prev->nextSiblingOrParent = cur->nextSiblingOrParent;
174  }
175  }
176 
177  // The value object mapped by this entry.
178  value_type value;
179 
180  // The next field links together entries in chained hash table buckets.
181  _Entry *next;
182 
183  // The firstChild and nextSiblingOrParent fields describe the tree
184  // structure of paths. An entry has one or more children when
185  // firstChild is non null. Its chlidren are stored in a singly linked
186  // list, where nextSiblingOrParent points to the next entry in the list.
187  //
188  // The end of the list is reached when the bit stored in
189  // nextSiblingOrParent is set false, indicating a pointer to the parent
190  // rather than another sibling.
191  _Entry *firstChild;
192  TfPointerAndBits<_Entry> nextSiblingOrParent;
193  };
194 
195  // Hash table's list of buckets is a vector of _Entry ptrs.
196  typedef std::vector<_Entry *> _BucketVec;
197 
198 public:
199 
200  // The iterator class, used to make both const and non-const
201  // iterators. Currently only forward traversal is supported.
202  template <class, class> friend class Iterator;
203  template <class ValType, class EntryPtr>
204  class Iterator :
205  public boost::iterator_facade<Iterator<ValType, EntryPtr>,
206  ValType, boost::forward_traversal_tag>
207  {
208  public:
211  Iterator() {}
212 
214  template <class OtherVal, class OtherEntryPtr>
215  Iterator(Iterator<OtherVal, OtherEntryPtr> const &other)
216  : _entry(other._entry)
217  {}
218 
222  Iterator GetNextSubtree() const {
223  Iterator result(0);
224  if (_entry) {
225  if (EntryPtr sibling = _entry->GetNextSibling()) {
226  // Next subtree is next sibling, if present.
227  result._entry = sibling;
228  } else {
229  // Otherwise, walk up parents until we either find one with
230  // a next sibling or run out.
231  for (EntryPtr p = _entry->GetParentLink(); p;
232  p = p->GetParentLink()) {
233  if (EntryPtr sibling = p->GetNextSibling()) {
234  result._entry = sibling;
235  break;
236  }
237  }
238  }
239  }
240  return result;
241  }
242 
245  bool HasChild() const {
246  return bool(_entry->firstChild);
247  }
248 
249  protected:
250  friend class boost::iterator_core_access;
251  friend class SdfPathTable;
252  template <class, class> friend class Iterator;
253 
254  explicit Iterator(EntryPtr entry)
255  : _entry(entry) {}
256 
257  // Fundamental functionality to implement the iterator.
258  // boost::iterator_facade will invoke these as necessary to implement
259  // the full iterator public interface.
260 
261  // Iterator increment.
262  inline void increment() {
263  // Move to first child, if present. Otherwise move to next subtree.
264  _entry = _entry->firstChild ? _entry->firstChild :
265  GetNextSubtree()._entry;
266  }
267 
268  // Equality comparison. A template, to allow comparison between const
269  // and non-const iterators.
270  template <class OtherVal, class OtherEntryPtr>
271  bool equal(Iterator<OtherVal, OtherEntryPtr> const &other) const {
272  return _entry == other._entry;
273  }
274 
275  // Dereference.
276  ValType &dereference() const {
277  return _entry->value;
278  }
279 
280  // Store pointer to current entry.
281  EntryPtr _entry;
282  };
283 
284  typedef Iterator<value_type, _Entry *> iterator;
285  typedef Iterator<const value_type, const _Entry *> const_iterator;
286 
288  typedef std::pair<iterator, bool> _IterBoolPair;
289 
294  struct NodeHandle
295  {
296  friend class SdfPathTable;
297 
302  static NodeHandle
303  New(value_type const &value) {
304  NodeHandle ret;
305  ret._unlinkedEntry.reset(new _Entry(value, nullptr));
306  return ret;
307  }
308 
310  static NodeHandle
311  New(value_type &&value) {
312  NodeHandle ret;
313  ret._unlinkedEntry.reset(new _Entry(std::move(value), nullptr));
314  return ret;
315  }
316 
318  static NodeHandle
319  New(key_type const &key, mapped_type const &mapped) {
320  return New({ key, mapped });
321  }
322 
326  key_type const &GetKey() const {
327  return _unlinkedEntry->value.first;
328  }
329 
334  return _unlinkedEntry->value.first;
335  }
336 
340  mapped_type const &GetMapped() const {
341  return _unlinkedEntry->value.second;
342  }
343 
347  mapped_type &GetMutableMapped() {
348  return _unlinkedEntry->value.second;
349  }
350 
353  bool IsValid() const {
354  return static_cast<bool>(_unlinkedEntry);
355  }
356 
359  explicit operator bool() const {
360  return IsValid();
361  }
362 
365  void reset() {
366  _unlinkedEntry.reset();
367  }
368 
369  private:
370  std::unique_ptr<_Entry> _unlinkedEntry;
371  };
372 
374  SdfPathTable() : _size(0), _mask(0) {}
375 
378  : _buckets(other._buckets.size())
379  , _size(0) // size starts at 0, since we insert elements.
380  , _mask(other._mask)
381  {
382  // Walk all elements in the other container, inserting into this one,
383  // and creating the right child/sibling links along the way.
384  for (const_iterator i = other.begin(), end = other.end();
385  i != end; ++i) {
386  iterator j = _InsertInTable(*i).first;
387  // Ensure first child and next sibling links are created.
388  if (i._entry->firstChild && !j._entry->firstChild) {
389  j._entry->firstChild =
390  _InsertInTable(i._entry->firstChild->value).first._entry;
391  }
392  // Ensure the nextSibling/parentLink is created.
393  if (i._entry->nextSiblingOrParent.Get() &&
394  !j._entry->nextSiblingOrParent.Get()) {
395  j._entry->nextSiblingOrParent.Set(
396  _InsertInTable(i._entry->nextSiblingOrParent.
397  Get()->value).first._entry,
398  i._entry->nextSiblingOrParent.template BitsAs<bool>());
399  }
400  }
401  }
402 
405  : _buckets(std::move(other._buckets))
406  , _size(other._size)
407  , _mask(other._mask)
408  {
409  other._size = 0;
410  other._mask = 0;
411  }
412 
415  // Call clear to free all nodes.
416  clear();
417  }
418 
421  if (this != &other)
422  SdfPathTable(other).swap(*this);
423  return *this;
424  }
425 
428  if (this != &other)
429  SdfPathTable(std::move(other)).swap(*this);
430  return *this;
431  }
432 
434  iterator begin() {
435  // Return an iterator pointing to the root if this table isn't empty.
436  if (empty())
437  return end();
439  }
440 
442  const_iterator begin() const {
443  // Return an iterator pointing to the root if this table isn't empty.
444  if (empty())
445  return end();
447  }
448 
450  iterator end() {
451  return iterator(0);
452  }
453 
455  const_iterator end() const {
456  return const_iterator(0);
457  }
458 
465  bool erase(SdfPath const &path) {
466  iterator i = find(path);
467  if (i == end())
468  return false;
469  erase(i);
470  return true;
471  }
472 
479  void erase(iterator const &i) {
480  // Delete descendant nodes, if any. Then remove from parent, finally
481  // erase from hash table.
482  _Entry * const entry = i._entry;
483  _EraseSubtree(entry);
484  _RemoveFromParent(entry);
485  _EraseFromTable(entry);
486  }
487 
490  iterator find(SdfPath const &path) {
491  if (!empty()) {
492  // Find the item in the list.
493  for (_Entry *e = _buckets[_Hash(path)]; e; e = e->next) {
494  if (e->value.first == path)
495  return iterator(e);
496  }
497  }
498  return end();
499  }
500 
503  const_iterator find(SdfPath const &path) const {
504  if (!empty()) {
505  // Find the item in the list.
506  for (_Entry const *e = _buckets[_Hash(path)]; e; e = e->next) {
507  if (e->value.first == path)
508  return const_iterator(e);
509  }
510  }
511  return end();
512  }
513 
517  std::pair<iterator, iterator>
518  FindSubtreeRange(SdfPath const &path) {
519  std::pair<iterator, iterator> result;
520  result.first = find(path);
521  result.second = result.first.GetNextSubtree();
522  return result;
523  }
524 
528  std::pair<const_iterator, const_iterator>
529  FindSubtreeRange(SdfPath const &path) const {
530  std::pair<const_iterator, const_iterator> result;
531  result.first = find(path);
532  result.second = result.first.GetNextSubtree();
533  return result;
534  }
535 
537  size_t count(SdfPath const &path) const {
538  return find(path) != end();
539  }
540 
542  inline size_t size() const { return _size; }
543 
545  inline bool empty() const { return !size(); }
546 
558  _IterBoolPair insert(value_type const &value) {
559  // Insert in table.
560  _IterBoolPair result = _InsertInTable(value);
561  if (result.second) {
562  // New element -- make sure the parent is inserted.
563  _UpdateTreeForNewEntry(result);
564  }
565  return result;
566  }
567 
574  _IterBoolPair insert(NodeHandle &&node) {
575  // Insert in table.
576  _IterBoolPair result = _InsertInTable(std::move(node));
577  if (result.second) {
578  // New element -- make sure the parent is inserted.
579  _UpdateTreeForNewEntry(result);
580  }
581  return result;
582  }
583 
588  mapped_type &operator[](SdfPath const &path) {
589  return insert(value_type(path, mapped_type())).first->second;
590  }
591 
596  void clear() {
597  // Note this leaves the size of _buckets unchanged.
598  for (size_t i = 0, n = _buckets.size(); i != n; ++i) {
599  _Entry *entry = _buckets[i];
600  while (entry) {
601  _Entry *next = entry->next;
602  delete entry;
603  entry = next;
604  }
605  _buckets[i] = 0;
606  }
607  _size = 0;
608  }
609 
613  auto visitFn =
614  [](void*& voidEntry) {
615  _Entry *entry = static_cast<_Entry *>(voidEntry);
616  while (entry) {
617  _Entry *next = entry->next;
618  delete entry;
619  entry = next;
620  }
621  voidEntry = nullptr;
622  };
623  Sdf_VisitPathTableInParallel(reinterpret_cast<void **>(_buckets.data()),
624  _buckets.size(), visitFn);
625  _size = 0;
626  }
627 
629  void swap(SdfPathTable &other) {
630  _buckets.swap(other._buckets);
631  std::swap(_size, other._size);
632  std::swap(_mask, other._mask);
633  }
634 
636  std::vector<size_t> GetBucketSizes() const {
637  std::vector<size_t> sizes(_buckets.size(), 0u);;
638  for (size_t i = 0, n = _buckets.size(); i != n; ++i) {
639  for (_Entry *entry = _buckets[i]; entry; entry = entry->next) {
640  sizes[i]++;
641  }
642  }
643  return sizes;
644  }
645 
649  void UpdateForRename(const SdfPath &oldName, const SdfPath &newName) {
650 
651  if (oldName.GetParentPath() != newName.GetParentPath()) {
652  TF_CODING_ERROR("Unexpected arguments.");
653  return;
654  }
655 
656  std::pair<iterator, iterator> range = FindSubtreeRange(oldName);
657  for (iterator i=range.first; i!=range.second; ++i) {
658  insert(value_type(
659  i->first.ReplacePrefix(oldName, newName),
660  i->second));
661  }
662 
663  if (range.first != range.second)
664  erase(oldName);
665  }
666 
672  template <typename Callback>
673  void ParallelForEach(Callback const& visitFn) {
674  auto lambda =
675  [&visitFn](void*& voidEntry) {
676  _Entry *entry = static_cast<_Entry *>(voidEntry);
677  while (entry) {
678  visitFn(std::cref(entry->value.first),
679  std::ref(entry->value.second));
680  entry = entry->next;
681  }
682  };
683  Sdf_VisitPathTableInParallel(reinterpret_cast<void **>(_buckets.data()),
684  _buckets.size(), lambda);
685  }
686 
689  template <typename Callback>
690  void ParallelForEach(Callback const& visitFn) const {
691  auto lambda =
692  [&visitFn](void*& voidEntry) {
693  const _Entry *entry = static_cast<const _Entry *>(voidEntry);
694  while (entry) {
695  visitFn(std::cref(entry->value.first),
696  std::cref(entry->value.second));
697  entry = entry->next;
698  }
699  };
700  Sdf_VisitPathTableInParallel(
701  // Note: the const cast here is undone by the static cast above...
702  reinterpret_cast<void **>(const_cast<_Entry**>(_buckets.data())),
703  _buckets.size(), lambda);
704  }
705 
707 
708 private:
709 
710  // Helper to get parent paths.
711  static SdfPath _GetParentPath(SdfPath const &path) {
712  return path.GetParentPath();
713  }
714 
715  void _UpdateTreeForNewEntry(_IterBoolPair const &iresult) {
716  // New element -- make sure the parent is inserted.
717  _Entry * const newEntry = iresult.first._entry;
718  SdfPath const &parentPath = _GetParentPath(newEntry->value.first);
719  if (!parentPath.IsEmpty()) {
720  iterator parIter =
721  insert(value_type(parentPath, mapped_type())).first;
722  // Add the new entry to the parent's children.
723  parIter._entry->AddChild(newEntry);
724  }
725  }
726 
727  // Helper to insert \a value in the hash table. Is responsible for growing
728  // storage space when necessary. Does not consider the tree structure.
729  template <class MakeEntryFn>
730  _IterBoolPair _InsertInTableImpl(key_type const &key,
731  MakeEntryFn &&makeEntry) {
732  // If we have no storage at all so far, grow.
733  if (_mask == 0)
734  _Grow();
735 
736  // Find the item, if present.
737  _Entry **bucketHead = &(_buckets[_Hash(key)]);
738  for (_Entry *e = *bucketHead; e; e = e->next) {
739  if (e->value.first == key) {
740  return _IterBoolPair(iterator(e), false);
741  }
742  }
743 
744  // Not present. If the table is getting full then grow and re-find the
745  // bucket.
746  if (_IsTooFull()) {
747  _Grow();
748  bucketHead = &(_buckets[_Hash(key)]);
749  }
750 
751  // Make an entry and insert it in the list.
752  *bucketHead = std::forward<MakeEntryFn>(makeEntry)(*bucketHead);
753 
754  // One more element
755  ++_size;
756 
757  // Return the new item
758  return _IterBoolPair(iterator(*bucketHead), true);
759  }
760 
761  _IterBoolPair _InsertInTable(value_type const &value) {
762  return _InsertInTableImpl(
763  value.first, [&value](_Entry *next) {
764  return new _Entry(value, next);
765  });
766  }
767 
768  _IterBoolPair _InsertInTable(NodeHandle &&node) {
769  return _InsertInTableImpl(
770  node.GetKey(), [&node](_Entry *next) mutable {
771  node._unlinkedEntry->next = next;
772  return node._unlinkedEntry.release();
773  });
774  }
775 
776  // Erase \a entry from the hash table. Does not consider tree structure.
777  void _EraseFromTable(_Entry *entry) {
778  // Remove from table.
779  _Entry **cur = &_buckets[_Hash(entry->value.first)];
780  while (*cur != entry)
781  cur = &((*cur)->next);
782 
783  // Unlink item and destroy it
784  --_size;
785  _Entry *tmp = *cur;
786  *cur = tmp->next;
787  delete tmp;
788  }
789 
790  // Erase all the tree structure descendants of \a entry from the table.
791  void _EraseSubtree(_Entry *entry) {
792  // Delete descendant nodes, if any.
793  if (_Entry * const firstChild = entry->firstChild) {
794  _EraseSubtreeAndSiblings(firstChild);
795  _EraseFromTable(firstChild);
796  }
797  }
798 
799  // Erase all the tree structure descendants and siblings of \a entry from
800  // the table.
801  void _EraseSubtreeAndSiblings(_Entry *entry) {
802  // Remove subtree.
803  _EraseSubtree(entry);
804 
805  // And siblings.
806  _Entry *sibling = entry->GetNextSibling();
807  _Entry *nextSibling = sibling ? sibling->GetNextSibling() : nullptr;
808  while (sibling) {
809  _EraseSubtree(sibling);
810  _EraseFromTable(sibling);
811  sibling = nextSibling;
812  nextSibling = sibling ? sibling->GetNextSibling() : nullptr;
813  }
814  }
815 
816  // Remove \a entry from its parent's list of children in the tree structure
817  // alone. Does not consider the table.
818  void _RemoveFromParent(_Entry *entry) {
819  if (entry->value.first == SdfPath::AbsoluteRootPath())
820  return;
821 
822  // Find parent in table.
823  iterator parIter = find(_GetParentPath(entry->value.first));
824 
825  // Remove this entry from the parent's children.
826  parIter._entry->RemoveChild(entry);
827  }
828 
829  // Grow the table's number of buckets to the next larger size. Rehashes the
830  // elements into the new table, but leaves tree structure untouched. (The
831  // tree structure need not be modified).
832  void _Grow() {
833  TfAutoMallocTag2 tag2("Sdf", "SdfPathTable::_Grow");
834  TfAutoMallocTag tag(__ARCH_PRETTY_FUNCTION__);
835 
836  // Allocate a new bucket list of twice the size. Minimum nonzero number
837  // of buckets is 8.
838  _mask = std::max(size_t(7), (_mask << 1) + 1);
839  _BucketVec newBuckets(_mask + 1);
840 
841  // Move items to a new bucket list
842  for (size_t i = 0, n = _buckets.size(); i != n; ++i) {
843  _Entry *elem = _buckets[i];
844  while (elem) {
845  // Save pointer to next item
846  _Entry *next = elem->next;
847 
848  // Get the bucket in the new list
849  _Entry *&m = newBuckets[_Hash(elem->value.first)];
850 
851  // Insert the item at the head
852  elem->next = m;
853  m = elem;
854 
855  // Next item
856  elem = next;
857  }
858  }
859 
860  // Use the new buckets
861  _buckets.swap(newBuckets);
862  }
863 
864  // Return true if the table should be made bigger.
865  bool _IsTooFull() const {
866  return _size > _buckets.size();
867  }
868 
869  // Return the bucket index for \a path.
870  inline size_t _Hash(SdfPath const &path) const {
871  return path.GetHash() & _mask;
872  }
873 
874 private:
875  _BucketVec _buckets;
876  size_t _size;
877  size_t _mask;
878 
879 };
880 
881 PXR_NAMESPACE_CLOSE_SCOPE
882 
883 #endif // PXR_USD_SDF_PATH_TABLE_H
key_type const & GetKey() const
Return a const reference to this NodeHandle's key.
Definition: pathTable.h:326
const_iterator end() const
Return a const_iterator denoting the end of the table.
Definition: pathTable.h:455
size_t size() const
Return the number of elements in the table.
Definition: pathTable.h:542
void UpdateForRename(const SdfPath &oldName, const SdfPath &newName)
Replaces all prefixes from oldName to newName.
Definition: pathTable.h:649
SdfPathTable & operator=(SdfPathTable &&other)
Move assignment.
Definition: pathTable.h:427
size_t count(SdfPath const &path) const
Return 1 if there is an element for path in the table, otherwise 0.
Definition: pathTable.h:537
~SdfPathTable()
Destructor.
Definition: pathTable.h:414
#define TF_CODING_ERROR(fmt, args)
Issue an internal programming error, but continue execution.
Definition: diagnostic.h:85
SdfPathTable & operator=(SdfPathTable const &other)
Copy assignment.
Definition: pathTable.h:420
mapped_type & operator[](SdfPath const &path)
Shorthand for the following, where t is an SdfPathTable<T>.
Definition: pathTable.h:588
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:503
std::pair< iterator, bool > _IterBoolPair
Result type for insert().
Definition: pathTable.h:288
Scoped (i.e.
Definition: mallocTag.h:349
SDF_API SdfPath GetParentPath() const
Return the path that identifies this path's namespace parent.
This class provides a non-owning reference to a type-erased callable object with a specified signatur...
Definition: functionRef.h:36
static NodeHandle New(value_type &&value)
Definition: pathTable.h:311
SdfPathTable(SdfPathTable const &other)
Copy constructor.
Definition: pathTable.h:377
_IterBoolPair insert(NodeHandle &&node)
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: pathTable.h:574
void ParallelForEach(Callback const &visitFn) const
ParallelForEach: const version, runnable on a const path table and taking a (const SdfPath&,...
Definition: pathTable.h:690
SdfPathTable(SdfPathTable &&other)
Move constructor.
Definition: pathTable.h:404
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:529
void reset()
Delete any owned path table entry.
Definition: pathTable.h:365
mapped_type & GetMutableMapped()
Return a mutable reference to this NodeHandle's mapped object.
Definition: pathTable.h:347
void swap(UsdStageLoadRules &l, UsdStageLoadRules &r)
Swap the contents of rules l and r.
bool empty() const
Return true if this table is empty.
Definition: pathTable.h:545
iterator end()
Return an iterator denoting the end of the table.
Definition: pathTable.h:450
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:465
Scoped (i.e.
Definition: mallocTag.h:262
void ParallelForEach(Callback const &visitFn)
ParallelForEach: parallel iteration over all of the key-value pairs in the path table.
Definition: pathTable.h:673
const_iterator begin() const
Return a const_iterator to the start of the table.
Definition: pathTable.h:442
static NodeHandle New(key_type const &key, mapped_type const &mapped)
Definition: pathTable.h:319
A path value used to locate objects in layers or scenegraphs.
Definition: path.h:290
A handle owning a path table node that may be used to "reserve" a stable memory location for key & ma...
Definition: pathTable.h:294
iterator begin()
Return an iterator to the start of the table.
Definition: pathTable.h:434
_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:558
mapped_type const & GetMapped() const
Return a const reference to this NodeHandle's mapped object.
Definition: pathTable.h:340
void clear()
Remove all elements from the table, leaving size() == 0.
Definition: pathTable.h:596
SdfPathTable()
Default constructor.
Definition: pathTable.h:374
std::vector< size_t > GetBucketSizes() const
Return a vector of the count of elements in each bucket.
Definition: pathTable.h:636
static SDF_API const SdfPath & AbsoluteRootPath()
The absolute path representing the top of the namespace hierarchy.
void swap(SdfPathTable &other)
Swap this table's contents with other.
Definition: pathTable.h:629
iterator find(SdfPath const &path)
Return an iterator to the element corresponding to path, or end() if there is none.
Definition: pathTable.h:490
bool IsValid() const
Return true if this NodeHandle owns a path table entry, false otherwise.
Definition: pathTable.h:353
static NodeHandle New(value_type const &value)
Create a new NodeHandle for a table entry.
Definition: pathTable.h:303
A mapping from SdfPath to MappedType, somewhat similar to map<SdfPath, MappedType> and TfHashMap<SdfP...
Definition: pathTable.h:85
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:518
key_type & GetMutableKey()
Return a mutable reference to this NodeHandle's key.
Definition: pathTable.h:333
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:479
bool IsEmpty() const noexcept
Returns true if this is the empty path (SdfPath::EmptyPath()).
Definition: path.h:419
void ClearInParallel()
Equivalent to clear(), but destroy contained objects in parallel.
Definition: pathTable.h:612