24 #ifndef PXR_USD_SDF_PATH_TABLE_H
25 #define PXR_USD_SDF_PATH_TABLE_H
28 #include "pxr/usd/sdf/api.h"
29 #include "pxr/usd/sdf/path.h"
30 #include "pxr/base/tf/pointerAndBits.h"
32 #include <boost/iterator/iterator_facade.hpp>
33 #include <boost/noncopyable.hpp>
39 PXR_NAMESPACE_OPEN_SCOPE
43 void Sdf_ClearPathTableInParallel(
void **,
size_t,
void (*)(
void *));
83 template <
class MappedType>
89 typedef MappedType mapped_type;
90 typedef std::pair<key_type, mapped_type> value_type;
98 struct _Entry : boost::noncopyable {
99 _Entry(value_type
const &value, _Entry *n)
103 , nextSiblingOrParent(0,
false) {}
107 _Entry *GetNextSibling() {
108 return nextSiblingOrParent.template BitsAs<bool>() ?
109 nextSiblingOrParent.Get() : 0;
113 _Entry
const *GetNextSibling()
const {
114 return nextSiblingOrParent.template BitsAs<bool>() ?
115 nextSiblingOrParent.Get() : 0;
120 _Entry *GetParentLink() {
121 return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
122 nextSiblingOrParent.Get();
126 _Entry
const *GetParentLink()
const {
127 return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
128 nextSiblingOrParent.Get();
133 void SetSibling(_Entry *sibling) {
134 nextSiblingOrParent.Set(sibling,
true);
139 void SetParentLink(_Entry *parent) {
140 nextSiblingOrParent.Set(parent,
false);
144 void AddChild(_Entry *child) {
148 child->SetSibling(firstChild);
150 child->SetParentLink(
this);
154 void RemoveChild(_Entry *child) {
156 if (child == firstChild) {
157 firstChild = child->GetNextSibling();
161 _Entry *prev, *cur = firstChild;
164 cur = prev->GetNextSibling();
165 }
while (cur != child);
166 prev->nextSiblingOrParent = cur->nextSiblingOrParent;
189 typedef std::vector<_Entry *> _BucketVec;
195 template <
class,
class>
friend class Iterator;
196 template <
class ValType,
class EntryPtr>
198 public boost::iterator_facade<Iterator<ValType, EntryPtr>,
199 ValType, boost::forward_traversal_tag>
207 template <
class OtherVal,
class OtherEntryPtr>
208 Iterator(Iterator<OtherVal, OtherEntryPtr>
const &other)
209 : _entry(other._entry)
215 Iterator GetNextSubtree()
const {
218 if (EntryPtr sibling = _entry->GetNextSibling()) {
220 result._entry = sibling;
224 for (EntryPtr p = _entry->GetParentLink(); p;
225 p = p->GetParentLink()) {
226 if (EntryPtr sibling = p->GetNextSibling()) {
227 result._entry = sibling;
237 friend class boost::iterator_core_access;
239 template <
class,
class>
friend class Iterator;
241 explicit Iterator(EntryPtr entry)
249 inline void increment() {
251 _entry = _entry->firstChild ? _entry->firstChild :
252 GetNextSubtree()._entry;
257 template <
class OtherVal,
class OtherEntryPtr>
258 bool equal(Iterator<OtherVal, OtherEntryPtr>
const &other)
const {
259 return _entry == other._entry;
263 ValType &dereference()
const {
264 return _entry->value;
271 typedef Iterator<value_type, _Entry *> iterator;
272 typedef Iterator<const value_type, const _Entry *> const_iterator;
282 : _buckets(other._buckets.
size())
288 for (const_iterator i = other.
begin(),
end = other.
end();
290 iterator j = _InsertInTable(*i).first;
292 if (i._entry->firstChild && !j._entry->firstChild) {
293 j._entry->firstChild =
294 _InsertInTable(i._entry->firstChild->value).first._entry;
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>());
309 : _buckets(std::move(other._buckets))
359 const_iterator
end()
const {
360 return const_iterator(0);
370 iterator i =
find(path);
386 _Entry *
const entry = i._entry;
387 _EraseSubtree(entry);
388 _RemoveFromParent(entry);
389 _EraseFromTable(entry);
397 for (_Entry *e = _buckets[_Hash(path)]; e; e = e->next) {
398 if (e->value.first == path)
410 for (_Entry
const *e = _buckets[_Hash(path)]; e; e = e->next) {
411 if (e->value.first == path)
412 return const_iterator(e);
421 std::pair<iterator, iterator>
423 std::pair<iterator, iterator> result;
424 result.first =
find(path);
425 result.second = result.first.GetNextSubtree();
432 std::pair<const_iterator, const_iterator>
434 std::pair<const_iterator, const_iterator> result;
435 result.first =
find(path);
436 result.second = result.first.GetNextSubtree();
446 inline size_t size()
const {
return _size; }
467 _Entry *
const newEntry = result.first._entry;
468 SdfPath const &parentPath = _GetParentPath(value.first);
473 parIter._entry->AddChild(newEntry);
493 for (
size_t i = 0, n = _buckets.size(); i != n; ++i) {
494 _Entry *entry = _buckets[i];
496 _Entry *next = entry->next;
508 Sdf_ClearPathTableInParallel(reinterpret_cast<void **>(_buckets.data()),
509 _buckets.size(), _DeleteEntryChain);
515 _buckets.swap(other._buckets);
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) {
542 for (iterator i=range.first; i!=range.second; ++i) {
544 i->first.ReplacePrefix(oldName, newName),
548 if (range.first != range.second)
557 static void _DeleteEntryChain(
void *voidEntry) {
558 _Entry *entry =
static_cast<_Entry *
>(voidEntry);
560 _Entry *next = entry->next;
579 _Entry **bucketHead = &(_buckets[_Hash(value.first)]);
580 for (_Entry *e = *bucketHead; e; e = e->next)
581 if (e->value.first == value.first)
588 bucketHead = &(_buckets[_Hash(value.first)]);
595 *bucketHead =
new _Entry(value, *bucketHead);
605 void _EraseFromTable(_Entry *entry) {
607 _Entry **cur = &_buckets[_Hash(entry->value.first)];
608 while (*cur != entry)
609 cur = &((*cur)->next);
619 void _EraseSubtree(_Entry *entry) {
621 if (_Entry *
const firstChild = entry->firstChild) {
622 _EraseSubtreeAndSiblings(firstChild);
623 _EraseFromTable(firstChild);
629 void _EraseSubtreeAndSiblings(_Entry *entry) {
631 _EraseSubtree(entry);
634 _Entry *sibling = entry->GetNextSibling();
635 _Entry *nextSibling = sibling ? sibling->GetNextSibling() :
nullptr;
637 _EraseSubtree(sibling);
638 _EraseFromTable(sibling);
639 sibling = nextSibling;
640 nextSibling = sibling ? sibling->GetNextSibling() :
nullptr;
646 void _RemoveFromParent(_Entry *entry) {
651 iterator parIter =
find(_GetParentPath(entry->value.first));
654 parIter._entry->RemoveChild(entry);
666 _mask = std::max(
size_t(7), (_mask << 1) + 1);
667 _BucketVec newBuckets(_mask + 1);
670 for (
size_t i = 0, n = _buckets.size(); i != n; ++i) {
671 _Entry *elem = _buckets[i];
674 _Entry *next = elem->next;
677 _Entry *&m = newBuckets[_Hash(elem->value.first)];
689 _buckets.swap(newBuckets);
693 bool _IsTooFull()
const {
694 return _size > _buckets.size();
698 inline size_t _Hash(
SdfPath const &path)
const {
699 return path.GetHash() & _mask;
709 PXR_NAMESPACE_CLOSE_SCOPE
711 #endif // PXR_USD_SDF_PATH_TABLE_H
size_t size() const
Return the number of elements in the table.
void UpdateForRename(const SdfPath &oldName, const SdfPath &newName)
Replaces all prefixes from oldName to newName.
SdfPathTable & operator=(SdfPathTable &&other)
Move assignment.
SDF_API SdfPath GetParentPath() const
Return the path that identifies this path's namespace parent.
~SdfPathTable()
Destructor.
#define TF_CODING_ERROR(fmt, args)
Issue an internal programming error, but continue execution.
SdfPathTable & operator=(SdfPathTable const &other)
Copy assignment.
mapped_type & operator[](SdfPath const &path)
Shorthand for the following, where t is an SdfPathTable<T>.
std::pair< iterator, bool > _IterBoolPair
Result type for insert().
const_iterator end() const
Return a const_iterator denoting the end of the table.
const_iterator find(SdfPath const &path) const
Return a const_iterator to the element corresponding to path, or end() if there is none...
SdfPathTable(SdfPathTable const &other)
Copy constructor.
SdfPathTable(SdfPathTable &&other)
Move constructor.
std::vector< size_t > GetBucketSizes() const
Return a vector of the count of elements in each bucket.
size_t count(SdfPath const &path) const
Return 1 if there is an element for path in the table, otherwise 0.
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.
bool erase(SdfPath const &path)
Remove the element with path path from the table as well as all elements whose paths are prefixed by ...
A path value used to locate objects in layers or scenegraphs.
iterator begin()
Return an iterator to the start of the table.
_IterBoolPair insert(value_type const &value)
Insert value into the table, and additionally insert default entries for all ancestral paths of value...
void clear()
Remove all elements from the table, leaving size() == 0.
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...
SdfPathTable()
Default constructor.
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.
bool empty() const
Return true if this table is empty.
iterator find(SdfPath const &path)
Return an iterator to the element corresponding to path, or end() if there is none.
void if(!TfPyIsInitialized())
Invokes wrapFunc to wrap type T if T is not already wrapped.
PcpPropertyIndex is an index of all sites in scene description that contribute opinions to a specific...
A mapping from SdfPath to MappedType, somewhat similar to map<SdfPath, MappedType> and TfHashMap<SdfP...
const_iterator begin() const
Return a const_iterator to the start of the table.
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...
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...
bool IsEmpty() const noexcept
Returns true if this is the empty path (SdfPath::EmptyPath()).
void ClearInParallel()
Equivalent to clear(), but destroy contained objects in parallel.