HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
pathTable.h
Go to the documentation of this file.
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"
15 
16 #include <algorithm>
17 #include <utility>
18 #include <vector>
19 
21 
22 // Parallel visitation helper function.
23 SDF_API
24 void Sdf_VisitPathTableInParallel(void **, size_t, TfFunctionRef<void(void*&)>);
25 
26 /// \class SdfPathTable
27 ///
28 /// A mapping from SdfPath to \a MappedType, somewhat similar to map<SdfPath,
29 /// MappedType> and TfHashMap<SdfPath, MappedType>, but with key
30 /// differences. Notably:
31 ///
32 /// Works exclusively with absolute paths.
33 ///
34 /// Inserting a path \a p also implicitly inserts all of \a p's ancestors.
35 ///
36 /// Erasing a path \a p also implicitly erases all of \a p's descendants.
37 ///
38 /// The table has an order: it's a preordering of the paths in the table, but
39 /// with arbitrary sibling order. Given a path \a p in the table, all other
40 /// paths in the table with \a p as a prefix appear contiguously, immediately
41 /// following \a p. For example, suppose a table contains the paths:
42 ///
43 /// {'/a/b/c', '/a', '/a/d', '/', '/a/b'}
44 ///
45 /// Then there are two possible valid orderings:
46 ///
47 /// ['/', '/a', '/a/d', '/a/b', '/a/b/c']
48 /// ['/', '/a', '/a/b', '/a/b/c', '/a/d']
49 ///
50 /// In addition to the ordinary map and TfHashMap methods, this class
51 /// provides a method \a FindSubtreeRange, which, given a path \a p, returns
52 /// a pair of iterators [\a b, \a e) defining a range such that for every
53 /// iterator \a i in [\a b, \a e), i->first is either equal to \a p or is
54 /// prefixed by \a p.
55 ///
56 /// Iterator Invalidation
57 ///
58 /// Like most other node-based containers, iterators are only invalidated when
59 /// the element they refer to is removed from the table. Note however, that
60 /// since removing the element with path \a p also implicitly removes all
61 /// elements with paths prefixed by \a p, a call to erase(\a i) may invalidate
62 /// many iterators.
63 ///
64 template <class MappedType>
66 {
67 public:
68 
69  typedef SdfPath key_type;
70  typedef MappedType mapped_type;
71  typedef std::pair<key_type, mapped_type> value_type;
72 
73 private:
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.
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 
180 public:
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 
195  /// The standard requires default construction but places practically no
196  /// requirements on the semantics of default-constructed iterators.
197  Iterator() = default;
198 
199  /// Copy constructor (also allows for converting non-const to const).
200  template <class OtherVal, class OtherEntryPtr>
202  : _entry(other._entry)
203  {}
204 
205  reference operator*() const { return dereference(); }
206  pointer operator->() const { return &(dereference()); }
207 
209  increment();
210  return *this;
211  }
212 
214  Iterator result(*this);
215  increment();
216  return result;
217  }
218 
219  template <class OtherVal, class OtherEntryPtr>
221  return equal(other);
222  }
223 
224  template <class OtherVal, class OtherEntryPtr>
226  return !equal(other);
227  }
228 
229  /// Return an iterator \a e, defining a maximal range [\a *this, \a e)
230  /// such that for all \a i in the range, \a i->first is \a
231  /// (*this)->first or is prefixed by \a (*this)->first.
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 
253  /// Returns true if incrementing this iterator would move to a child
254  /// entry, false otherwise.
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 :
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 
294  /// Result type for insert().
295  typedef std::pair<iterator, bool> _IterBoolPair;
296 
297  /// A handle owning a path table node that may be used to "reserve" a stable
298  /// memory location for key & mapped object. A node handle may be inserted
299  /// into a table later, and if that insertion is successful, the underlying
300  /// key & mapped object remain at the same memory location.
301  struct NodeHandle
302  {
303  friend class SdfPathTable;
304 
305  /// Create a new NodeHandle for a table entry. This NodeHandle can
306  /// later be inserted into an SdfPathTable. If inserted successfully,
307  /// the key and value addresses remain valid. NodeHandles may be
308  /// created concurrently without additional synchronization.
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 
316  /// \overload
317  static NodeHandle
319  NodeHandle ret;
320  ret._unlinkedEntry.reset(new _Entry(std::move(value), nullptr));
321  return ret;
322  }
323 
324  /// \overload
325  static NodeHandle
326  New(key_type const &key, mapped_type const &mapped) {
327  return New({ key, mapped });
328  }
329 
330  /// Return a const reference to this NodeHandle's key. This NodeHandle
331  /// must be valid to call this member function (see
332  /// NodeHandle::IsValid).
333  key_type const &GetKey() const {
334  return _unlinkedEntry->value.first;
335  }
336 
337  /// Return a mutable reference to this NodeHandle's key. This
338  /// NodeHandle must be valid to call this member function (see
339  /// NodeHandle::IsValid).
341  return _unlinkedEntry->value.first;
342  }
343 
344  /// Return a const reference to this NodeHandle's mapped object. This
345  /// NodeHandle must be valid to call this member function (see
346  /// NodeHandle::IsValid).
347  mapped_type const &GetMapped() const {
348  return _unlinkedEntry->value.second;
349  }
350 
351  /// Return a mutable reference to this NodeHandle's mapped object. This
352  /// NodeHandle must be valid to call this member function (see
353  /// NodeHandle::IsValid).
355  return _unlinkedEntry->value.second;
356  }
357 
358  /// Return true if this NodeHandle owns a path table entry, false
359  /// otherwise.
360  bool IsValid() const {
361  return static_cast<bool>(_unlinkedEntry);
362  }
363 
364  /// Return true if this NodeHandle owns a path table entry, false
365  /// otherwise.
366  explicit operator bool() const {
367  return IsValid();
368  }
369 
370  /// Delete any owned path table entry. After calling this function,
371  /// IsValid() returns false.
372  void reset() {
373  _unlinkedEntry.reset();
374  }
375 
376  private:
377  std::unique_ptr<_Entry> _unlinkedEntry;
378  };
379 
380  /// Default constructor.
381  SdfPathTable() : _size(0), _mask(0) {}
382 
383  /// Copy constructor.
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 
410  /// Move constructor.
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 
420  /// Destructor.
422  // Call clear to free all nodes.
423  clear();
424  }
425 
426  /// Copy assignment.
428  if (this != &other)
429  SdfPathTable(other).swap(*this);
430  return *this;
431  }
432 
433  /// Move assignment.
435  if (this != &other)
436  SdfPathTable(std::move(other)).swap(*this);
437  return *this;
438  }
439 
440  /// Return an iterator to the start of the table.
442  // Return an iterator pointing to the root if this table isn't empty.
443  if (empty())
444  return end();
446  }
447 
448  /// Return a const_iterator to the start of the table.
450  // Return an iterator pointing to the root if this table isn't empty.
451  if (empty())
452  return end();
454  }
455 
456  /// Return an iterator denoting the end of the table.
458  return iterator(0);
459  }
460 
461  /// Return a const_iterator denoting the end of the table.
462  const_iterator end() const {
463  return const_iterator(0);
464  }
465 
466  /// Remove the element with path \a path from the table as well as all
467  /// elements whose paths are prefixed by \a path. Return true if any
468  /// elements were removed, false otherwise.
469  ///
470  /// Note that since descendant paths are also erased, size() may be
471  /// decreased by more than one after calling this function.
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 
480  /// Remove the element pointed to by \p i from the table as well as all
481  /// elements whose paths are prefixed by \a i->first. \a i must be a valid
482  /// iterator for this table.
483  ///
484  /// Note that since descendant paths are also erased, size() may be
485  /// decreased by more than one after calling this function.
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 
495  /// Return an iterator to the element corresponding to \a path, or \a end()
496  /// if there is none.
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 
508  /// Return a const_iterator to the element corresponding to \a path, or
509  /// \a end() if there is none.
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 
521  /// Return a pair of iterators [\a b, \a e), describing the maximal range
522  /// such that for all \a i in the range, \a i->first is \a b->first or
523  /// is prefixed by \a b->first.
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 
532  /// Return a pair of const_iterators [\a b, \a e), describing the maximal
533  /// range such that for all \a i in the range, \a i->first is \a b->first or
534  /// is prefixed by \a b->first.
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 
543  /// Return 1 if there is an element for \a path in the table, otherwise 0.
544  size_t count(SdfPath const &path) const {
545  return find(path) != end();
546  }
547 
548  /// Return the number of elements in the table.
549  inline size_t size() const { return _size; }
550 
551  /// Return true if this table is empty.
552  inline bool empty() const { return !size(); }
553 
554  /// Insert \a value into the table, and additionally insert default entries
555  /// for all ancestral paths of \a value.first that do not already exist in
556  /// the table.
557  ///
558  /// Return a pair of iterator and bool. The iterator points to the inserted
559  /// element, the bool indicates whether insertion was successful. The bool
560  /// is true if \a value was successfully inserted and false if an element
561  /// with path \a value.first was already present in the map.
562  ///
563  /// Note that since ancestral paths are also inserted, size() may be
564  /// increased by more than one after calling this function.
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 
575  /// \overload
576  ///
577  /// Insert the entry held by \p node into this table. If the insertion is
578  /// successful, the contents of \p node are moved-from and indeterminate.
579  /// Otherwise if the insertion is unsuccessful, the contents of \p node are
580  /// unmodified.
581  _IterBoolPair insert(NodeHandle &&node) {
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 
591  /// Shorthand for the following, where \a t is an SdfPathTable<T>.
592  /// \code
593  /// t.insert(value_type(path, mapped_type())).first->second
594  /// \endcode
596  return insert(value_type(path, mapped_type())).first->second;
597  }
598 
599  /// Remove all elements from the table, leaving size() == 0. Note that this
600  /// function will not shrink the number of buckets used for the hash table.
601  /// To do that, swap this instance with a default constructed instance.
602  /// See also \a TfReset.
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 
617  /// Equivalent to clear(), but destroy contained objects in parallel. This
618  /// requires that running the contained objects' destructors is thread-safe.
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 
635  /// Swap this table's contents with \a other.
636  void swap(SdfPathTable &other) {
637  _buckets.swap(other._buckets);
638  std::swap(_size, other._size);
639  std::swap(_mask, other._mask);
640  }
641 
642  /// Return a vector of the count of elements in each bucket.
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 
653  /// Replaces all prefixes from \p oldName to \p newName.
654  /// Note that \p oldName and \p newName need to be silbing paths (ie.
655  /// their parent paths must be the same).
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) {
666  i->first.ReplacePrefix(oldName, newName),
667  i->second));
668  }
669 
670  if (range.first != range.second)
671  erase(oldName);
672  }
673 
674  /// ParallelForEach: parallel iteration over all of the key-value pairs
675  /// in the path table. The type of \p visitFn should be a callable,
676  /// taking a (const SdfPath&, mapped_type&), representing the loop
677  /// body. Note: since this function is run in parallel, visitFn is
678  /// responsible for synchronizing access to any non-pathtable state.
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 
694  /// ParallelForEach: const version, runnable on a const path table and
695  /// taking a (const SdfPath&, const mapped_type&) input.
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  };
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 
713 private:
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 
879 private:
880  _BucketVec _buckets;
881  size_t _size;
882  size_t _mask;
883 
884 };
885 
887 
888 #endif // PXR_USD_SDF_PATH_TABLE_H
void ParallelForEach(Callback const &visitFn) const
Definition: pathTable.h:697
GLuint GLsizei const GLuint const GLintptr const GLsizeiptr * sizes
Definition: glcorearb.h:2621
GLint first
Definition: glcorearb.h:405
pointer operator->() const
Definition: pathTable.h:206
const_iterator begin() const
Return a const_iterator to the start of the table.
Definition: pathTable.h:449
_IterBoolPair insert(NodeHandle &&node)
Definition: pathTable.h:581
static SDF_API const SdfPath & AbsoluteRootPath()
~SdfPathTable()
Destructor.
Definition: pathTable.h:421
GLenum GLint * range
Definition: glcorearb.h:1925
key_type & GetMutableKey()
Definition: pathTable.h:340
SdfPathTable()
Default constructor.
Definition: pathTable.h:381
SdfPathTable & operator=(SdfPathTable const &other)
Copy assignment.
Definition: pathTable.h:427
const_iterator end() const
Return a const_iterator denoting the end of the table.
Definition: pathTable.h:462
bool operator!=(Iterator< OtherVal, OtherEntryPtr > const &other) const
Definition: pathTable.h:225
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)
Definition: UT_ArraySet.h:1699
const_iterator find(SdfPath const &path) const
Definition: pathTable.h:510
SdfPathTable & operator=(SdfPathTable &&other)
Move assignment.
Definition: pathTable.h:434
GLsizei const GLfloat * value
Definition: glcorearb.h:824
GLsizei const GLchar *const * path
Definition: glcorearb.h:3341
mapped_type const & GetMapped() const
Definition: pathTable.h:347
#define TF_CODING_ERROR
void ClearInParallel()
Definition: pathTable.h:619
Iterator GetNextSubtree() const
Definition: pathTable.h:232
SdfPath key_type
Definition: pathTable.h:69
bool IsEmpty() const noexcept
Returns true if this is the empty path (SdfPath::EmptyPath()).
Definition: path.h:398
void ParallelForEach(Callback const &visitFn)
Definition: pathTable.h:680
void UpdateForRename(const SdfPath &oldName, const SdfPath &newName)
Definition: pathTable.h:656
**But if you need a result
Definition: thread.h:622
FMT_CONSTEXPR auto find(Ptr first, Ptr last, T value, Ptr &out) -> bool
Definition: core.h:2138
static NodeHandle New(value_type &&value)
Definition: pathTable.h:318
Iterator(Iterator< OtherVal, OtherEntryPtr > const &other)
Copy constructor (also allows for converting non-const to const).
Definition: pathTable.h:201
static NodeHandle New(key_type const &key, mapped_type const &mapped)
Definition: pathTable.h:326
size_t GetHash() const
Equality operator.
Definition: path.h:957
OutGridT const XformOp bool bool
Iterator(EntryPtr entry)
Definition: pathTable.h:263
iterator find(SdfPath const &path)
Definition: pathTable.h:497
mapped_type & GetMutableMapped()
Definition: pathTable.h:354
GLdouble n
Definition: glcorearb.h:2008
GLint ref
Definition: glcorearb.h:124
#define __ARCH_PRETTY_FUNCTION__
Definition: functionLite.h:29
std::forward_iterator_tag iterator_category
Definition: pathTable.h:189
std::ptrdiff_t difference_type
Definition: pathTable.h:193
void erase(iterator const &i)
Definition: pathTable.h:486
GLuint GLuint end
Definition: glcorearb.h:475
bool operator==(Iterator< OtherVal, OtherEntryPtr > const &other) const
Definition: pathTable.h:220
static NodeHandle New(value_type const &value)
Definition: pathTable.h:310
MappedType mapped_type
Definition: pathTable.h:70
SdfPathTable(SdfPathTable const &other)
Copy constructor.
Definition: pathTable.h:384
std::pair< iterator, iterator > FindSubtreeRange(SdfPath const &path)
Definition: pathTable.h:525
key_type const & GetKey() const
Definition: pathTable.h:333
Definition: path.h:273
friend class Iterator
Definition: pathTable.h:184
void clear()
Definition: pathTable.h:603
Iterator< const value_type, const _Entry * > const_iterator
Definition: pathTable.h:292
GLint j
Definition: glad.h:2733
iterator begin()
Return an iterator to the start of the table.
Definition: pathTable.h:441
#define SDF_API
Definition: api.h:23
GLsizeiptr size
Definition: glcorearb.h:664
reference operator*() const
Definition: pathTable.h:205
Iterator & operator++()
Definition: pathTable.h:208
PXR_NAMESPACE_CLOSE_SCOPE PXR_NAMESPACE_OPEN_SCOPE
Definition: path.h:1425
size_t size() const
Return the number of elements in the table.
Definition: pathTable.h:549
bool equal(Iterator< OtherVal, OtherEntryPtr > const &other) const
Definition: pathTable.h:278
bool HasChild() const
Definition: pathTable.h:255
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
Iterator operator++(int)
Definition: pathTable.h:213
SdfPathTable(SdfPathTable &&other)
Move constructor.
Definition: pathTable.h:411
ImageBuf OIIO_API max(Image_or_Const A, Image_or_Const B, ROI roi={}, int nthreads=0)
#define PXR_NAMESPACE_CLOSE_SCOPE
Definition: pxr.h:74
std::pair< const_iterator, const_iterator > FindSubtreeRange(SdfPath const &path) const
Definition: pathTable.h:536
if(num_boxed_items<=0)
Definition: UT_RTreeImpl.h:697
SDF_API SdfPath GetParentPath() const
bool erase(SdfPath const &path)
Definition: pathTable.h:472
mapped_type & operator[](SdfPath const &path)
Definition: pathTable.h:595
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.
Definition: pathTable.h:552
std::pair< iterator, bool > _IterBoolPair
Result type for insert().
Definition: pathTable.h:295
std::pair< key_type, mapped_type > value_type
Definition: pathTable.h:71
Iterator< value_type, _Entry * > iterator
Definition: pathTable.h:291
_IterBoolPair insert(value_type const &value)
Definition: pathTable.h:565
std::vector< size_t > GetBucketSizes() const
Return a vector of the count of elements in each bucket.
Definition: pathTable.h:643
ValType & dereference() const
Definition: pathTable.h:283
bool IsValid() const
Definition: pathTable.h:360
void swap(SdfPathTable &other)
Swap this table's contents with other.
Definition: pathTable.h:636
iterator end()
Return an iterator denoting the end of the table.
Definition: pathTable.h:457