All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 SDF_PATHTABLE_H
25 #define SDF_PATHTABLE_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 
32 #include <boost/iterator/iterator_facade.hpp>
33 #include <boost/noncopyable.hpp>
34 
35 #include <algorithm>
36 #include <utility>
37 #include <vector>
38 
39 PXR_NAMESPACE_OPEN_SCOPE
40 
41 // Helper function for clearing path tables.
42 SDF_API
43 void Sdf_ClearPathTableInParallel(void **, size_t, void (*)(void *));
44 
83 template <class MappedType>
85 {
86 public:
87 
88  typedef SdfPath key_type;
89  typedef MappedType mapped_type;
90  typedef std::pair<key_type, mapped_type> value_type;
91 
92 private:
93 
94  // An _Entry represents an item in the table. It holds the item's value, a
95  // pointer (\a next) to the next item in the hash bucket's linked list, and
96  // two pointers (\a firstChild and \a nextSibling) that describe the tree
97  // structure.
98  struct _Entry : boost::noncopyable {
99  _Entry(value_type const &value, _Entry *n)
100  : value(value)
101  , next(n)
102  , firstChild(0)
103  , nextSiblingOrParent(0, false) {}
104 
105  // If this entry's nextSiblingOrParent field points to a sibling, return
106  // a pointer to it, otherwise return null.
107  _Entry *GetNextSibling() {
108  return nextSiblingOrParent.template BitsAs<bool>() ?
109  nextSiblingOrParent.Get() : 0;
110  }
111  // If this entry's nextSiblingOrParent field points to a sibling, return
112  // a pointer to it, otherwise return null.
113  _Entry const *GetNextSibling() const {
114  return nextSiblingOrParent.template BitsAs<bool>() ?
115  nextSiblingOrParent.Get() : 0;
116  }
117 
118  // If this entry's nextSiblingOrParent field points to a parent, return
119  // a pointer to it, otherwise return null.
120  _Entry *GetParentLink() {
121  return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
122  nextSiblingOrParent.Get();
123  }
124  // If this entry's nextSiblingOrParent field points to a parent, return
125  // a pointer to it, otherwise return null.
126  _Entry const *GetParentLink() const {
127  return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
128  nextSiblingOrParent.Get();
129  }
130 
131  // Set this entry's nextSiblingOrParent field to point to the passed
132  // sibling.
133  void SetSibling(_Entry *sibling) {
134  nextSiblingOrParent.Set(sibling, /* isSibling */ true);
135  }
136 
137  // Set this entry's nextSiblingOrParent field to point to the passed
138  // parent.
139  void SetParentLink(_Entry *parent) {
140  nextSiblingOrParent.Set(parent, /* isSibling */ false);
141  }
142 
143  // Add \a child as a child of this entry.
144  void AddChild(_Entry *child) {
145  // If there are already one or more children, make \a child be our
146  // new first child. Otherwise, add \a child as the first child.
147  if (firstChild)
148  child->SetSibling(firstChild);
149  else
150  child->SetParentLink(this);
151  firstChild = child;
152  }
153 
154  void RemoveChild(_Entry *child) {
155  // Remove child from this _Entry's children.
156  if (child == firstChild) {
157  firstChild = child->GetNextSibling();
158  } else {
159  // Search the list to find the preceding child, then unlink the
160  // child to remove.
161  _Entry *prev, *cur = firstChild;
162  do {
163  prev = cur;
164  cur = prev->GetNextSibling();
165  } while (cur != child);
166  prev->nextSiblingOrParent = cur->nextSiblingOrParent;
167  }
168  }
169 
170  // The value object mapped by this entry.
171  value_type value;
172 
173  // The next field links together entries in chained hash table buckets.
174  _Entry *next;
175 
176  // The firstChild and nextSiblingOrParent fields describe the tree
177  // structure of paths. An entry has one or more children when
178  // firstChild is non null. Its chlidren are stored in a singly linked
179  // list, where nextSiblingOrParent points to the next entry in the list.
180  //
181  // The end of the list is reached when the bit stored in
182  // nextSiblingOrParent is set false, indicating a pointer to the parent
183  // rather than another sibling.
184  _Entry *firstChild;
185  TfPointerAndBits<_Entry> nextSiblingOrParent;
186  };
187 
188  // Hash table's list of buckets is a vector of _Entry ptrs.
189  typedef std::vector<_Entry *> _BucketVec;
190 
191 public:
192 
193  // The iterator class, used to make both const and non-const
194  // iterators. Currently only forward traversal is supported.
195  template <class, class> friend class Iterator;
196  template <class ValType, class EntryPtr>
197  class Iterator :
198  public boost::iterator_facade<Iterator<ValType, EntryPtr>,
199  ValType, boost::forward_traversal_tag>
200  {
201  public:
204  Iterator() {}
205 
207  template <class OtherVal, class OtherEntryPtr>
208  Iterator(Iterator<OtherVal, OtherEntryPtr> const &other)
209  : _entry(other._entry)
210  {}
211 
215  Iterator GetNextSubtree() const {
216  Iterator result(0);
217  if (_entry) {
218  if (EntryPtr sibling = _entry->GetNextSibling()) {
219  // Next subtree is next sibling, if present.
220  result._entry = sibling;
221  } else {
222  // Otherwise, walk up parents until we either find one with
223  // a next sibling or run out.
224  for (EntryPtr p = _entry->GetParentLink(); p;
225  p = p->GetParentLink()) {
226  if (EntryPtr sibling = p->GetNextSibling()) {
227  result._entry = sibling;
228  break;
229  }
230  }
231  }
232  }
233  return result;
234  }
235 
236  protected:
237  friend class boost::iterator_core_access;
238  friend class SdfPathTable;
239  template <class, class> friend class Iterator;
240 
241  explicit Iterator(EntryPtr entry)
242  : _entry(entry) {}
243 
244  // Fundamental functionality to implement the iterator.
245  // boost::iterator_facade will invoke these as necessary to implement
246  // the full iterator public interface.
247 
248  // Iterator increment.
249  inline void increment() {
250  // Move to first child, if present. Otherwise move to next subtree.
251  _entry = _entry->firstChild ? _entry->firstChild :
252  GetNextSubtree()._entry;
253  }
254 
255  // Equality comparison. A template, to allow comparison between const
256  // and non-const iterators.
257  template <class OtherVal, class OtherEntryPtr>
258  bool equal(Iterator<OtherVal, OtherEntryPtr> const &other) const {
259  return _entry == other._entry;
260  }
261 
262  // Dereference.
263  ValType &dereference() const {
264  return _entry->value;
265  }
266 
267  // Store pointer to current entry.
268  EntryPtr _entry;
269  };
270 
271  typedef Iterator<value_type, _Entry *> iterator;
272  typedef Iterator<const value_type, const _Entry *> const_iterator;
273 
275  typedef std::pair<iterator, bool> _IterBoolPair;
276 
278  SdfPathTable() : _size(0), _mask(0) {}
279 
282  : _buckets(other._buckets.size())
283  , _size(0) // size starts at 0, since we insert elements.
284  , _mask(other._mask)
285  {
286  // Walk all elements in the other container, inserting into this one,
287  // and creating the right child/sibling links along the way.
288  for (const_iterator i = other.begin(), end = other.end();
289  i != end; ++i) {
290  iterator j = _InsertInTable(*i).first;
291  // Ensure first child and next sibling links are created.
292  if (i._entry->firstChild && !j._entry->firstChild) {
293  j._entry->firstChild =
294  _InsertInTable(i._entry->firstChild->value).first._entry;
295  }
296  // Ensure the nextSibling/parentLink is created.
297  if (i._entry->nextSiblingOrParent.Get() &&
298  !j._entry->nextSiblingOrParent.Get()) {
299  j._entry->nextSiblingOrParent.Set(
300  _InsertInTable(i._entry->nextSiblingOrParent.
301  Get()->value).first._entry,
302  i._entry->nextSiblingOrParent.template BitsAs<bool>());
303  }
304  }
305  }
306 
309  : _buckets(std::move(other._buckets))
310  , _size(other._size)
311  , _mask(other._mask)
312  {
313  other._size = 0;
314  other._mask = 0;
315  }
316 
319  // Call clear to free all nodes.
320  clear();
321  }
322 
325  if (this != &other)
326  SdfPathTable(other).swap(*this);
327  return *this;
328  }
329 
332  if (this != &other)
333  SdfPathTable(std::move(other)).swap(*this);
334  return *this;
335  }
336 
338  iterator begin() {
339  // Return an iterator pointing to the root if this table isn't empty.
340  if (empty())
341  return end();
343  }
344 
346  const_iterator begin() const {
347  // Return an iterator pointing to the root if this table isn't empty.
348  if (empty())
349  return end();
351  }
352 
354  iterator end() {
355  return iterator(0);
356  }
357 
359  const_iterator end() const {
360  return const_iterator(0);
361  }
362 
369  bool erase(SdfPath const &path) {
370  iterator i = find(path);
371  if (i == end())
372  return false;
373  erase(i);
374  return true;
375  }
376 
383  void erase(iterator const &i) {
384  // Delete descendant nodes, if any. Then remove from parent, finally
385  // erase from hash table.
386  _Entry * const entry = i._entry;
387  _EraseSubtree(entry);
388  _RemoveFromParent(entry);
389  _EraseFromTable(entry);
390  }
391 
394  iterator find(SdfPath const &path) {
395  if (!empty()) {
396  // Find the item in the list.
397  for (_Entry *e = _buckets[_Hash(path)]; e; e = e->next) {
398  if (e->value.first == path)
399  return iterator(e);
400  }
401  }
402  return end();
403  }
404 
407  const_iterator find(SdfPath const &path) const {
408  if (!empty()) {
409  // Find the item in the list.
410  for (_Entry const *e = _buckets[_Hash(path)]; e; e = e->next) {
411  if (e->value.first == path)
412  return const_iterator(e);
413  }
414  }
415  return end();
416  }
417 
421  std::pair<iterator, iterator>
422  FindSubtreeRange(SdfPath const &path) {
423  std::pair<iterator, iterator> result;
424  result.first = find(path);
425  result.second = result.first.GetNextSubtree();
426  return result;
427  }
428 
432  std::pair<const_iterator, const_iterator>
433  FindSubtreeRange(SdfPath const &path) const {
434  std::pair<const_iterator, const_iterator> result;
435  result.first = find(path);
436  result.second = result.first.GetNextSubtree();
437  return result;
438  }
439 
441  size_t count(SdfPath const &path) const {
442  return find(path) != end();
443  }
444 
446  inline size_t size() const { return _size; }
447 
449  inline bool empty() const { return !size(); }
450 
462  _IterBoolPair insert(value_type const &value) {
463  // Insert in table.
464  _IterBoolPair result = _InsertInTable(value);
465  if (result.second) {
466  // New element -- make sure the parent is inserted.
467  _Entry * const newEntry = result.first._entry;
468  SdfPath const &parentPath = _GetParentPath(value.first);
469  if (!parentPath.IsEmpty()) {
470  iterator parIter =
471  insert(value_type(parentPath, mapped_type())).first;
472  // Add the new entry to the parent's children.
473  parIter._entry->AddChild(newEntry);
474  }
475  }
476  return result;
477  }
478 
484  return insert(value_type(path, mapped_type())).first->second;
485  }
486 
491  void clear() {
492  // Note this leaves the size of _buckets unchanged.
493  for (size_t i = 0, n = _buckets.size(); i != n; ++i) {
494  _Entry *entry = _buckets[i];
495  while (entry) {
496  _Entry *next = entry->next;
497  delete entry;
498  entry = next;
499  }
500  _buckets[i] = 0;
501  }
502  _size = 0;
503  }
504 
508  Sdf_ClearPathTableInParallel(reinterpret_cast<void **>(_buckets.data()),
509  _buckets.size(), _DeleteEntryChain);
510  _size = 0;
511  }
512 
514  void swap(SdfPathTable &other) {
515  _buckets.swap(other._buckets);
516  std::swap(_size, other._size);
517  std::swap(_mask, other._mask);
518  }
519 
521  std::vector<size_t> GetBucketSizes() const {
522  std::vector<size_t> sizes(_buckets.size(), 0u);;
523  for (size_t i = 0, n = _buckets.size(); i != n; ++i) {
524  for (_Entry *entry = _buckets[i]; entry; entry = entry->next) {
525  sizes[i]++;
526  }
527  }
528  return sizes;
529  }
530 
534  void UpdateForRename(const SdfPath &oldName, const SdfPath &newName) {
535 
536  if (oldName.GetParentPath() != newName.GetParentPath()) {
537  TF_CODING_ERROR("Unexpected arguments.");
538  return;
539  }
540 
541  std::pair<iterator, iterator> range = FindSubtreeRange(oldName);
542  for (iterator i=range.first; i!=range.second; ++i) {
543  insert(value_type(
544  i->first.ReplacePrefix(oldName, newName),
545  i->second));
546  }
547 
548  if (range.first != range.second)
549  erase(oldName);
550  }
551 
553 
554 private:
555 
556  // Helper to delete entries.
557  static void _DeleteEntryChain(void *voidEntry) {
558  _Entry *entry = static_cast<_Entry *>(voidEntry);
559  while (entry) {
560  _Entry *next = entry->next;
561  delete entry;
562  entry = next;
563  }
564  }
565 
566  // Helper to get parent paths.
567  static SdfPath _GetParentPath(SdfPath const &path) {
568  return path.GetParentPath();
569  }
570 
571  // Helper to insert \a value in the hash table. Is responsible for growing
572  // storage space when necessary. Does not consider the tree structure.
573  _IterBoolPair _InsertInTable(value_type const &value) {
574  // If we have no storage at all so far, grow.
575  if (_mask == 0)
576  _Grow();
577 
578  // Find the item, if present.
579  _Entry **bucketHead = &(_buckets[_Hash(value.first)]);
580  for (_Entry *e = *bucketHead; e; e = e->next)
581  if (e->value.first == value.first)
582  return _IterBoolPair(iterator(e), false);
583 
584  // Not present. If the table is getting full then grow and re-find the
585  // bucket.
586  if (_IsTooFull()) {
587  _Grow();
588  bucketHead = &(_buckets[_Hash(value.first)]);
589  }
590 
591  TfAutoMallocTag2 tag2("Sdf", "SdfPathTable::_FindOrCreate");
592  TfAutoMallocTag tag(__ARCH_PRETTY_FUNCTION__);
593 
594  // Create a new item and insert it in the list
595  *bucketHead = new _Entry(value, *bucketHead);
596 
597  // One more element
598  ++_size;
599 
600  // Return the new item
601  return _IterBoolPair(iterator(*bucketHead), true);
602  }
603 
604  // Erase \a entry from the hash table. Does not consider tree structure.
605  void _EraseFromTable(_Entry *entry) {
606  // Remove from table.
607  _Entry **cur = &_buckets[_Hash(entry->value.first)];
608  while (*cur != entry)
609  cur = &((*cur)->next);
610 
611  // Unlink item and destroy it
612  --_size;
613  _Entry *tmp = *cur;
614  *cur = tmp->next;
615  delete tmp;
616  }
617 
618  // Erase all the tree structure descendants of \a entry from the table.
619  void _EraseSubtree(_Entry *entry) {
620  // Delete descendant nodes, if any.
621  if (_Entry * const firstChild = entry->firstChild) {
622  _EraseSubtreeAndSiblings(firstChild);
623  _EraseFromTable(firstChild);
624  }
625  }
626 
627  // Erase all the tree structure descendants and siblings of \a entry from
628  // the table.
629  void _EraseSubtreeAndSiblings(_Entry *entry) {
630  // Remove subtree.
631  _EraseSubtree(entry);
632 
633  // And siblings.
634  if (_Entry * const nextSibling = entry->GetNextSibling()) {
635  _EraseSubtreeAndSiblings(nextSibling);
636  _EraseFromTable(nextSibling);
637  }
638  }
639 
640  // Remove \a entry from its parent's list of children in the tree structure
641  // alone. Does not consider the table.
642  void _RemoveFromParent(_Entry *entry) {
643  if (entry->value.first == SdfPath::AbsoluteRootPath())
644  return;
645 
646  // Find parent in table.
647  iterator parIter = find(_GetParentPath(entry->value.first));
648 
649  // Remove this entry from the parent's children.
650  parIter._entry->RemoveChild(entry);
651  }
652 
653  // Grow the table's number of buckets to the next larger size. Rehashes the
654  // elements into the new table, but leaves tree structure untouched. (The
655  // tree structure need not be modified).
656  void _Grow() {
657  TfAutoMallocTag2 tag2("Sdf", "SdfPathTable::_Grow");
658  TfAutoMallocTag tag(__ARCH_PRETTY_FUNCTION__);
659 
660  // Allocate a new bucket list of twice the size. Minimum nonzero number
661  // of buckets is 8.
662  _mask = std::max(size_t(7), (_mask << 1) + 1);
663  _BucketVec newBuckets(_mask + 1);
664 
665  // Move items to a new bucket list
666  for (size_t i = 0, n = _buckets.size(); i != n; ++i) {
667  _Entry *elem = _buckets[i];
668  while (elem) {
669  // Save pointer to next item
670  _Entry *next = elem->next;
671 
672  // Get the bucket in the new list
673  _Entry *&m = newBuckets[_Hash(elem->value.first)];
674 
675  // Insert the item at the head
676  elem->next = m;
677  m = elem;
678 
679  // Next item
680  elem = next;
681  }
682  }
683 
684  // Use the new buckets
685  _buckets.swap(newBuckets);
686  }
687 
688  // Return true if the table should be made bigger.
689  bool _IsTooFull() const {
690  return _size > _buckets.size();
691  }
692 
693  // Return the bucket index for \a path.
694  inline size_t _Hash(SdfPath const &path) const {
695  return path.GetHash() & _mask;
696  }
697 
698 private:
699  _BucketVec _buckets;
700  size_t _size;
701  size_t _mask;
702 
703 };
704 
705 PXR_NAMESPACE_CLOSE_SCOPE
706 
707 #endif // SDF_PATHTABLE_H
size_t size() const
Return the number of elements in the table.
Definition: pathTable.h:446
void UpdateForRename(const SdfPath &oldName, const SdfPath &newName)
Replaces all prefixes from oldName to newName.
Definition: pathTable.h:534
SdfPathTable & operator=(SdfPathTable &&other)
Move assignment.
Definition: pathTable.h:331
void if(!TfPyIsInitialized())
Invokes wrapFunc to wrap type T if T is not already wrapped.
Definition: pyUtils.h:210
SDF_API SdfPath GetParentPath() const
Return the path that identifies this path&#39;s namespace parent.
~SdfPathTable()
Destructor.
Definition: pathTable.h:318
#define TF_CODING_ERROR(fmt, args)
Issue an internal programming error, but continue execution.
Definition: diagnostic.h:87
SdfPathTable & operator=(SdfPathTable const &other)
Copy assignment.
Definition: pathTable.h:324
mapped_type & operator[](SdfPath const &path)
Shorthand for the following, where t is an SdfPathTable&lt;T&gt;.
Definition: pathTable.h:483
std::pair< iterator, bool > _IterBoolPair
Result type for insert().
Definition: pathTable.h:275
Scoped (i.e.
Definition: mallocTag.h:349
const_iterator end() const
Return a const_iterator denoting the end of the table.
Definition: pathTable.h:359
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:407
SdfPathTable(SdfPathTable const &other)
Copy constructor.
Definition: pathTable.h:281
SdfPathTable(SdfPathTable &&other)
Move constructor.
Definition: pathTable.h:308
std::vector< size_t > GetBucketSizes() const
Return a vector of the count of elements in each bucket.
Definition: pathTable.h:521
size_t count(SdfPath const &path) const
Return 1 if there is an element for path in the table, otherwise 0.
Definition: pathTable.h:441
void swap(UsdStageLoadRules &l, UsdStageLoadRules &r)
Swap the contents of rules l and r.
iterator end()
Return an iterator denoting the end of the table.
Definition: pathTable.h:354
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:369
Scoped (i.e.
Definition: mallocTag.h:262
A path value used to locate objects in layers or scenegraphs.
Definition: path.h:287
iterator begin()
Return an iterator to the start of the table.
Definition: pathTable.h:338
_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:462
void clear()
Remove all elements from the table, leaving size() == 0.
Definition: pathTable.h:491
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:433
SdfPathTable()
Default constructor.
Definition: pathTable.h:278
static SDF_API const SdfPath & AbsoluteRootPath()
The absolute path representing the top of the namespace hierarchy.
void swap(SdfPathTable &other)
Swap this table&#39;s contents with other.
Definition: pathTable.h:514
bool empty() const
Return true if this table is empty.
Definition: pathTable.h:449
iterator find(SdfPath const &path)
Return an iterator to the element corresponding to path, or end() if there is none.
Definition: pathTable.h:394
PcpPropertyIndex is an index of all sites in scene description that contribute opinions to a specific...
Definition: propertyIndex.h:65
A mapping from SdfPath to MappedType, somewhat similar to map&lt;SdfPath, MappedType&gt; and TfHashMap&lt;SdfP...
Definition: pathTable.h:84
const_iterator begin() const
Return a const_iterator to the start of the table.
Definition: pathTable.h:346
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:422
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:383
bool IsEmpty() const noexcept
Returns true if this is the empty path (SdfPath::EmptyPath()).
Definition: path.h:409
void ClearInParallel()
Equivalent to clear(), but destroy contained objects in parallel.
Definition: pathTable.h:507