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"
31#include "pxr/base/tf/functionRef.h"
37PXR_NAMESPACE_OPEN_SCOPE
41void Sdf_VisitPathTableInParallel(
void **,
size_t,
TfFunctionRef<
void(
void*&)>);
81template <
class MappedType>
87 typedef MappedType mapped_type;
88 typedef std::pair<key_type, mapped_type> value_type;
97 _Entry(
const _Entry&) =
delete;
98 _Entry& operator=(
const _Entry&) =
delete;
99 _Entry(value_type
const &value, _Entry *n)
102 , firstChild(
nullptr)
103 , nextSiblingOrParent(
nullptr,
false) {}
105 _Entry(value_type &&value, _Entry *n)
106 : value(std::move(value))
108 , firstChild(
nullptr)
109 , nextSiblingOrParent(
nullptr,
false) {}
113 _Entry *GetNextSibling() {
114 return nextSiblingOrParent.template BitsAs<bool>() ?
115 nextSiblingOrParent.Get() : 0;
119 _Entry
const *GetNextSibling()
const {
120 return nextSiblingOrParent.template BitsAs<bool>() ?
121 nextSiblingOrParent.Get() : 0;
126 _Entry *GetParentLink() {
127 return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
128 nextSiblingOrParent.Get();
132 _Entry
const *GetParentLink()
const {
133 return nextSiblingOrParent.template BitsAs<bool>() ? 0 :
134 nextSiblingOrParent.Get();
139 void SetSibling(_Entry *sibling) {
140 nextSiblingOrParent.Set(sibling,
true);
145 void SetParentLink(_Entry *parent) {
146 nextSiblingOrParent.Set(parent,
false);
150 void AddChild(_Entry *child) {
154 child->SetSibling(firstChild);
156 child->SetParentLink(
this);
160 void RemoveChild(_Entry *child) {
162 if (child == firstChild) {
163 firstChild = child->GetNextSibling();
167 _Entry *prev, *cur = firstChild;
170 cur = prev->GetNextSibling();
171 }
while (cur != child);
172 prev->nextSiblingOrParent = cur->nextSiblingOrParent;
195 typedef std::vector<_Entry *> _BucketVec;
201 template <
class,
class>
friend class Iterator;
202 template <
class ValType,
class EntryPtr>
206 using iterator_category = std::forward_iterator_tag;
207 using value_type = ValType;
208 using reference = ValType&;
209 using pointer = ValType*;
210 using difference_type = std::ptrdiff_t;
214 Iterator() =
default;
217 template <
class OtherVal,
class OtherEntryPtr>
218 Iterator(Iterator<OtherVal, OtherEntryPtr>
const &other)
219 : _entry(other._entry)
222 reference operator*()
const {
return dereference(); }
223 pointer operator->()
const {
return &(dereference()); }
225 Iterator& operator++() {
230 Iterator operator++(
int) {
231 Iterator result(*
this);
236 template <
class OtherVal,
class OtherEntryPtr>
237 bool operator==(Iterator<OtherVal, OtherEntryPtr>
const &other)
const {
241 template <
class OtherVal,
class OtherEntryPtr>
242 bool operator!=(Iterator<OtherVal, OtherEntryPtr>
const &other)
const {
243 return !equal(other);
249 Iterator GetNextSubtree()
const {
252 if (EntryPtr sibling = _entry->GetNextSibling()) {
254 result._entry = sibling;
258 for (EntryPtr p = _entry->GetParentLink(); p;
259 p = p->GetParentLink()) {
260 if (EntryPtr sibling = p->GetNextSibling()) {
261 result._entry = sibling;
272 bool HasChild()
const {
273 return bool(_entry->firstChild);
278 template <
class,
class>
friend class Iterator;
280 explicit Iterator(EntryPtr entry)
286 inline void increment() {
288 _entry = _entry->firstChild ? _entry->firstChild :
289 GetNextSubtree()._entry;
294 template <
class OtherVal,
class OtherEntryPtr>
295 bool equal(Iterator<OtherVal, OtherEntryPtr>
const &other)
const {
296 return _entry == other._entry;
300 ValType &dereference()
const {
301 return _entry->value;
308 typedef Iterator<value_type, _Entry *> iterator;
309 typedef Iterator<const value_type, const _Entry *> const_iterator;
327 New(value_type
const &value) {
329 ret._unlinkedEntry.reset(
new _Entry(value,
nullptr));
337 ret._unlinkedEntry.reset(
new _Entry(std::move(value),
nullptr));
344 return New({ key, mapped });
351 return _unlinkedEntry->value.first;
358 return _unlinkedEntry->value.first;
365 return _unlinkedEntry->value.second;
372 return _unlinkedEntry->value.second;
378 return static_cast<bool>(_unlinkedEntry);
383 explicit operator bool()
const {
390 _unlinkedEntry.reset();
394 std::unique_ptr<_Entry> _unlinkedEntry;
402 : _buckets(other._buckets.
size())
408 for (const_iterator i = other.
begin(),
end = other.
end();
410 iterator j = _InsertInTable(*i).first;
412 if (i._entry->firstChild && !j._entry->firstChild) {
413 j._entry->firstChild =
414 _InsertInTable(i._entry->firstChild->value).first._entry;
417 if (i._entry->nextSiblingOrParent.Get() &&
418 !j._entry->nextSiblingOrParent.Get()) {
419 j._entry->nextSiblingOrParent.Set(
420 _InsertInTable(i._entry->nextSiblingOrParent.
421 Get()->value).first._entry,
422 i._entry->nextSiblingOrParent.template BitsAs<bool>());
429 : _buckets(
std::move(other._buckets))
479 const_iterator
end()
const {
480 return const_iterator(0);
490 iterator i =
find(path);
506 _Entry *
const entry = i._entry;
507 _EraseSubtree(entry);
508 _RemoveFromParent(entry);
509 _EraseFromTable(entry);
517 for (_Entry *e = _buckets[_Hash(path)]; e; e = e->next) {
518 if (e->value.first == path)
530 for (_Entry
const *e = _buckets[_Hash(path)]; e; e = e->next) {
531 if (e->value.first == path)
532 return const_iterator(e);
541 std::pair<iterator, iterator>
543 std::pair<iterator, iterator> result;
544 result.first =
find(path);
545 result.second = result.first.GetNextSubtree();
552 std::pair<const_iterator, const_iterator>
554 std::pair<const_iterator, const_iterator> result;
555 result.first =
find(path);
556 result.second = result.first.GetNextSubtree();
566 inline size_t size()
const {
return _size; }
587 _UpdateTreeForNewEntry(result);
603 _UpdateTreeForNewEntry(result);
613 return insert(value_type(path, mapped_type())).first->second;
622 for (
size_t i = 0, n = _buckets.size(); i != n; ++i) {
623 _Entry *entry = _buckets[i];
625 _Entry *next = entry->next;
638 [](
void*& voidEntry) {
639 _Entry *entry =
static_cast<_Entry *
>(voidEntry);
641 _Entry *next = entry->next;
647 Sdf_VisitPathTableInParallel(
reinterpret_cast<void **
>(_buckets.data()),
648 _buckets.size(), visitFn);
654 _buckets.swap(other._buckets);
655 std::swap(_size, other._size);
656 std::swap(_mask, other._mask);
661 std::vector<size_t> sizes(_buckets.size(), 0u);;
662 for (
size_t i = 0, n = _buckets.size(); i != n; ++i) {
663 for (_Entry *entry = _buckets[i]; entry; entry = entry->next) {
681 for (iterator i=range.first; i!=range.second; ++i) {
683 i->first.ReplacePrefix(oldName, newName),
687 if (range.first != range.second)
696 template <
typename Callback>
699 [&visitFn](
void*& voidEntry) {
700 _Entry *entry =
static_cast<_Entry *
>(voidEntry);
702 visitFn(std::cref(entry->value.first),
703 std::ref(entry->value.second));
707 Sdf_VisitPathTableInParallel(
reinterpret_cast<void **
>(_buckets.data()),
708 _buckets.size(), lambda);
713 template <
typename Callback>
716 [&visitFn](
void*& voidEntry) {
717 const _Entry *entry =
static_cast<const _Entry *
>(voidEntry);
719 visitFn(std::cref(entry->value.first),
720 std::cref(entry->value.second));
724 Sdf_VisitPathTableInParallel(
726 reinterpret_cast<void **
>(
const_cast<_Entry**
>(_buckets.data())),
727 _buckets.size(), lambda);
741 _Entry *
const newEntry = iresult.first._entry;
742 SdfPath const &parentPath = _GetParentPath(newEntry->value.first);
745 insert(value_type(parentPath, mapped_type())).first;
747 parIter._entry->AddChild(newEntry);
753 template <
class MakeEntryFn>
755 MakeEntryFn &&makeEntry) {
761 _Entry **bucketHead = &(_buckets[_Hash(key)]);
762 for (_Entry *e = *bucketHead; e; e = e->next) {
763 if (e->value.first == key) {
772 bucketHead = &(_buckets[_Hash(key)]);
776 *bucketHead = std::forward<MakeEntryFn>(makeEntry)(*bucketHead);
786 return _InsertInTableImpl(
787 value.first, [&value](_Entry *next) {
788 return new _Entry(value, next);
793 return _InsertInTableImpl(
794 node.GetKey(), [&node](_Entry *next)
mutable {
795 node._unlinkedEntry->next = next;
796 return node._unlinkedEntry.release();
801 void _EraseFromTable(_Entry *entry) {
803 _Entry **cur = &_buckets[_Hash(entry->value.first)];
804 while (*cur != entry)
805 cur = &((*cur)->next);
815 void _EraseSubtree(_Entry *entry) {
817 if (_Entry *
const firstChild = entry->firstChild) {
818 _EraseSubtreeAndSiblings(firstChild);
819 _EraseFromTable(firstChild);
825 void _EraseSubtreeAndSiblings(_Entry *entry) {
827 _EraseSubtree(entry);
830 _Entry *sibling = entry->GetNextSibling();
831 _Entry *nextSibling = sibling ? sibling->GetNextSibling() :
nullptr;
833 _EraseSubtree(sibling);
834 _EraseFromTable(sibling);
835 sibling = nextSibling;
836 nextSibling = sibling ? sibling->GetNextSibling() :
nullptr;
842 void _RemoveFromParent(_Entry *entry) {
847 iterator parIter =
find(_GetParentPath(entry->value.first));
850 parIter._entry->RemoveChild(entry);
862 _mask = std::max(
size_t(7), (_mask << 1) + 1);
863 _BucketVec newBuckets(_mask + 1);
866 for (
size_t i = 0, n = _buckets.size(); i != n; ++i) {
867 _Entry *elem = _buckets[i];
870 _Entry *next = elem->next;
873 _Entry *&m = newBuckets[_Hash(elem->value.first)];
885 _buckets.swap(newBuckets);
889 bool _IsTooFull()
const {
890 return _size > _buckets.size();
894 inline size_t _Hash(
SdfPath const &path)
const {
895 return path.GetHash() & _mask;
905PXR_NAMESPACE_CLOSE_SCOPE
A path value used to locate objects in layers or scenegraphs.
SDF_API SdfPath GetParentPath() const
Return the path that identifies this path's namespace parent.
static SDF_API const SdfPath & AbsoluteRootPath()
The absolute path representing the top of the namespace hierarchy.
bool IsEmpty() const noexcept
Returns true if this is the empty path (SdfPath::EmptyPath()).
A mapping from SdfPath to MappedType, somewhat similar to map<SdfPath, MappedType> and TfHashMap<SdfP...
void ParallelForEach(Callback const &visitFn)
ParallelForEach: parallel iteration over all of the key-value pairs in the path table.
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...
mapped_type & operator[](SdfPath const &path)
Shorthand for the following, where t is an SdfPathTable<T>.
iterator find(SdfPath const &path)
Return an iterator to the element corresponding to path, or end() if there is none.
size_t size() const
Return the number of elements in the table.
void ParallelForEach(Callback const &visitFn) const
ParallelForEach: const version, runnable on a const path table and taking a (const SdfPath&,...
const_iterator begin() const
Return a const_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...
_IterBoolPair insert(NodeHandle &&node)
This is an overloaded member function, provided for convenience. It differs from the above function o...
bool empty() const
Return true if this table is empty.
std::pair< iterator, bool > _IterBoolPair
Result type for insert().
~SdfPathTable()
Destructor.
SdfPathTable(SdfPathTable const &other)
Copy constructor.
void ClearInParallel()
Equivalent to clear(), but destroy contained objects in parallel.
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,...
std::vector< size_t > GetBucketSizes() const
Return a vector of the count of elements in each bucket.
const_iterator find(SdfPath const &path) const
Return a const_iterator to the element corresponding to path, or end() if there is none.
bool erase(SdfPath const &path)
Remove the element with path path from the table as well as all elements whose paths are prefixed by ...
void swap(SdfPathTable &other)
Swap this table's contents with other.
void clear()
Remove all elements from the table, leaving size() == 0.
SdfPathTable & operator=(SdfPathTable const &other)
Copy assignment.
iterator end()
Return an iterator denoting the end of the table.
const_iterator end() const
Return a const_iterator denoting the end of the table.
iterator begin()
Return an iterator to the start of the table.
SdfPathTable & operator=(SdfPathTable &&other)
Move assignment.
void UpdateForRename(const SdfPath &oldName, const SdfPath &newName)
Replaces all prefixes from oldName to newName.
size_t count(SdfPath const &path) const
Return 1 if there is an element for path in the table, otherwise 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(SdfPathTable &&other)
Move constructor.
SdfPathTable()
Default constructor.
This class provides a non-owning reference to a type-erased callable object with a specified signatur...
This class stores a T * and a small integer in the space of a T *.
#define TF_CODING_ERROR(fmt, args)
Issue an internal programming error, but continue execution.
A handle owning a path table node that may be used to "reserve" a stable memory location for key & ma...
static NodeHandle New(key_type const &key, mapped_type const &mapped)
This is an overloaded member function, provided for convenience. It differs from the above function o...
mapped_type const & GetMapped() const
Return a const reference to this NodeHandle's mapped object.
key_type & GetMutableKey()
Return a mutable reference to this NodeHandle's key.
key_type const & GetKey() const
Return a const reference to this NodeHandle's key.
static NodeHandle New(value_type &&value)
This is an overloaded member function, provided for convenience. It differs from the above function o...
bool IsValid() const
Return true if this NodeHandle owns a path table entry, false otherwise.
void reset()
Delete any owned path table entry.
mapped_type & GetMutableMapped()
Return a mutable reference to this NodeHandle's mapped object.
static NodeHandle New(value_type const &value)
Create a new NodeHandle for a table entry.