41 #ifndef OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED 42 #define OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED 44 #include <openvdb/Types.h> 45 #include <tbb/parallel_for.h> 46 #include <tbb/parallel_reduce.h> 57 template<
typename TreeOrLeafManagerT, Index LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
67 template<
typename NodeT>
72 using ListT = std::deque<value_type>;
76 void push_back(NodeT* node) { mList.push_back(node); }
78 NodeT&
operator()(
size_t n)
const { assert(n<mList.size());
return *(mList[n]); }
80 NodeT*&
operator[](
size_t n) { assert(n<mList.size());
return mList[n]; }
86 void resize(
size_t n) { mList.resize(n); }
93 mEnd(end), mBegin(begin), mGrainSize(grainSize), mNodeList(nodeList) {}
96 mEnd(r.mEnd), mBegin(doSplit(r)), mGrainSize(r.mGrainSize),
97 mNodeList(r.mNodeList) {}
99 size_t size()
const {
return mEnd - mBegin; }
105 bool empty()
const {
return !(mBegin < mEnd);}
114 assert(this->isValid());
121 NodeT&
operator*()
const {
return mRange.mNodeList(mPos); }
125 size_t pos()
const {
return mPos; }
126 bool isValid()
const {
return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
128 bool test()
const {
return mPos < mRange.mEnd; }
130 operator bool()
const {
return this->test(); }
132 bool empty()
const {
return !this->test(); }
135 return (mPos != other.mPos) || (&mRange != &other.mRange);
150 size_t mEnd, mBegin, mGrainSize;
156 size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
165 return NodeRange(0, this->nodeCount(), *
this, grainsize);
168 template<
typename NodeOp>
169 void foreach(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
171 NodeTransformer<NodeOp> transform(op);
172 transform.run(this->nodeRange(grainSize), threaded);
175 template<
typename NodeOp>
176 void reduce(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
178 NodeReducer<NodeOp> transform(op);
179 transform.run(this->nodeRange(grainSize), threaded);
185 template<
typename NodeOp>
186 struct NodeTransformer
188 NodeTransformer(
const NodeOp& nodeOp) : mNodeOp(nodeOp)
191 void run(
const NodeRange& range,
bool threaded =
true)
193 threaded ? tbb::parallel_for(range, *
this) : (*this)(range);
195 void operator()(
const NodeRange& range)
const 197 for (
typename NodeRange::Iterator it = range.begin(); it; ++it) mNodeOp(*it);
199 const NodeOp mNodeOp;
203 template<
typename NodeOp>
206 NodeReducer(NodeOp& nodeOp) : mNodeOp(&nodeOp), mOwnsOp(
false)
209 NodeReducer(
const NodeReducer& other, tbb::split) :
210 mNodeOp(
new NodeOp(*(other.mNodeOp), tbb::split())), mOwnsOp(
true)
213 ~NodeReducer() {
if (mOwnsOp)
delete mNodeOp; }
214 void run(
const NodeRange& range,
bool threaded =
true)
216 threaded ? tbb::parallel_reduce(range, *
this) : (*this)(range);
218 void operator()(
const NodeRange& range)
220 NodeOp &op = *mNodeOp;
221 for (
typename NodeRange::Iterator it = range.begin(); it; ++it) op(*it);
223 void join(
const NodeReducer& other)
225 mNodeOp->join(*(other.mNodeOp));
244 template<
typename NodeT, Index LEVEL>
252 void clear() { mList.clear(); mNext.clear(); }
254 template<
typename ParentT,
typename TreeOrLeafManagerT>
255 void init(ParentT& parent, TreeOrLeafManagerT& tree)
257 parent.getNodes(mList);
258 for (
size_t i=0, n=mList.nodeCount(); i<n; ++i) mNext.init(mList(i), tree);
261 template<
typename ParentT>
265 parent.getNodes(mList);
266 for (
size_t i=0, n=mList.nodeCount(); i<n; ++i) mNext.rebuild(mList(i));
273 return i==NodeT::LEVEL ? mList.nodeCount() : mNext.nodeCount(i);
276 template<
typename NodeOp>
279 mNext.foreachBottomUp(op, threaded, grainSize);
280 mList.foreach(op, threaded, grainSize);
283 template<
typename NodeOp>
286 mList.foreach(op, threaded, grainSize);
287 mNext.foreachTopDown(op, threaded, grainSize);
290 template<
typename NodeOp>
293 mNext.reduceBottomUp(op, threaded, grainSize);
294 mList.reduce(op, threaded, grainSize);
297 template<
typename NodeOp>
300 mList.reduce(op, threaded, grainSize);
301 mNext.reduceTopDown(op, threaded, grainSize);
316 template<
typename NodeT>
325 void clear() { mList.
clear(); }
327 template<
typename ParentT>
328 void rebuild(ParentT& parent) { mList.clear(); parent.getNodes(mList); }
330 Index64 nodeCount()
const {
return mList.nodeCount(); }
332 Index64 nodeCount(
Index)
const {
return mList.nodeCount(); }
334 template<
typename NodeOp>
335 void foreachBottomUp(
const NodeOp& op,
bool threaded,
size_t grainSize)
337 mList.foreach(op, threaded, grainSize);
340 template<
typename NodeOp>
341 void foreachTopDown(
const NodeOp& op,
bool threaded,
size_t grainSize)
343 mList.foreach(op, threaded, grainSize);
346 template<
typename NodeOp>
347 void reduceBottomUp(NodeOp& op,
bool threaded,
size_t grainSize)
349 mList.reduce(op, threaded, grainSize);
352 template<
typename NodeOp>
353 void reduceTopDown(NodeOp& op,
bool threaded,
size_t grainSize)
355 mList.reduce(op, threaded, grainSize);
358 template<
typename ParentT,
typename TreeOrLeafManagerT>
359 void init(ParentT& parent, TreeOrLeafManagerT& tree)
362 if (TreeOrLeafManagerT::DEPTH == 2 && NodeT::LEVEL == 0) {
363 tree.getNodes(mList);
365 parent.getNodes(mList);
382 template<
typename TreeOrLeafManagerT, Index _LEVELS>
386 static const Index LEVELS = _LEVELS;
387 static_assert(LEVELS > 0,
388 "expected instantiation of template specialization");
390 static_assert(RootNodeType::LEVEL >= LEVELS,
"number of levels exceeds root node height");
392 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { mChain.init(mRoot, tree); }
414 template<
typename NodeOp>
472 mChain.foreachBottomUp(op, threaded, grainSize);
476 template<
typename NodeOp>
480 mChain.foreachTopDown(op, threaded, grainSize);
486 template<
typename NodeOp>
546 mChain.reduceBottomUp(op, threaded, grainSize);
550 template<
typename NodeOp>
554 mChain.reduceTopDown(op, threaded, grainSize);
572 template<
typename TreeOrLeafManagerT>
576 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
577 static const Index LEVELS = 0;
579 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) {}
594 Index64 nodeCount()
const {
return 0; }
598 template<
typename NodeOp>
599 void foreachBottomUp(
const NodeOp& op,
bool,
size_t) { op(mRoot); }
601 template<
typename NodeOp>
602 void foreachTopDown(
const NodeOp& op,
bool,
size_t) { op(mRoot); }
604 template<
typename NodeOp>
605 void reduceBottomUp(NodeOp& op,
bool,
size_t) { op(mRoot); }
607 template<
typename NodeOp>
608 void reduceTopDown(NodeOp& op,
bool,
size_t) { op(mRoot); }
623 template<
typename TreeOrLeafManagerT>
627 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
628 static_assert(RootNodeType::LEVEL > 0,
"expected instantiation of template specialization");
629 static const Index LEVELS = 1;
631 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
634 if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
635 tree.getNodes(mList0);
637 mRoot.getNodes(mList0);
645 void clear() { mList0.
clear(); }
649 void rebuild() { mList0.clear(); mRoot.getNodes(mList0); }
655 Index64 nodeCount()
const {
return mList0.nodeCount(); }
659 Index64 nodeCount(
Index i)
const {
return i==0 ? mList0.nodeCount() : 0; }
661 template<
typename NodeOp>
662 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
664 mList0.foreach(op, threaded, grainSize);
668 template<
typename NodeOp>
669 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
672 mList0.foreach(op, threaded, grainSize);
675 template<
typename NodeOp>
676 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
678 mList0.reduce(op, threaded, grainSize);
682 template<
typename NodeOp>
683 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
686 mList0.reduce(op, threaded, grainSize);
691 using NodeT0 =
typename NodeT1::ChildNodeType;
707 template<
typename TreeOrLeafManagerT>
711 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
712 static_assert(RootNodeType::LEVEL > 1,
"expected instantiation of template specialization");
713 static const Index LEVELS = 2;
715 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
717 mRoot.getNodes(mList1);
720 if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
721 tree.getNodes(mList0);
723 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
731 void clear() { mList0.
clear(); mList1.clear(); }
738 mRoot.getNodes(mList1);
739 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
746 Index64 nodeCount()
const {
return mList0.nodeCount() + mList1.nodeCount(); }
752 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() : 0;
755 template<
typename NodeOp>
756 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
758 mList0.foreach(op, threaded, grainSize);
759 mList1.foreach(op, threaded, grainSize);
763 template<
typename NodeOp>
764 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
767 mList1.foreach(op, threaded, grainSize);
768 mList0.foreach(op, threaded, grainSize);
771 template<
typename NodeOp>
772 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
774 mList0.reduce(op, threaded, grainSize);
775 mList1.reduce(op, threaded, grainSize);
779 template<
typename NodeOp>
780 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
783 mList1.reduce(op, threaded, grainSize);
784 mList0.reduce(op, threaded, grainSize);
789 using NodeT1 =
typename NodeT2::ChildNodeType;
790 using NodeT0 =
typename NodeT1::ChildNodeType;
809 template<
typename TreeOrLeafManagerT>
813 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
814 static_assert(RootNodeType::LEVEL > 2,
"expected instantiation of template specialization");
815 static const Index LEVELS = 3;
817 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
819 mRoot.getNodes(mList2);
820 for (
size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
823 if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
824 tree.getNodes(mList0);
826 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
834 void clear() { mList0.
clear(); mList1.clear(); mList2.clear(); }
841 mRoot.getNodes(mList2);
842 for (
size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
843 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
850 Index64 nodeCount()
const {
return mList0.nodeCount()+mList1.nodeCount()+mList2.nodeCount(); }
856 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount()
857 : i==2 ? mList2.nodeCount() : 0;
860 template<
typename NodeOp>
861 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
863 mList0.foreach(op, threaded, grainSize);
864 mList1.foreach(op, threaded, grainSize);
865 mList2.foreach(op, threaded, grainSize);
869 template<
typename NodeOp>
870 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
873 mList2.foreach(op, threaded, grainSize);
874 mList1.foreach(op, threaded, grainSize);
875 mList0.foreach(op, threaded, grainSize);
878 template<
typename NodeOp>
879 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
881 mList0.reduce(op, threaded, grainSize);
882 mList1.reduce(op, threaded, grainSize);
883 mList2.reduce(op, threaded, grainSize);
887 template<
typename NodeOp>
888 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
891 mList2.reduce(op, threaded, grainSize);
892 mList1.reduce(op, threaded, grainSize);
893 mList0.reduce(op, threaded, grainSize);
898 using NodeT2 =
typename NodeT3::ChildNodeType;
899 using NodeT1 =
typename NodeT2::ChildNodeType;
900 using NodeT0 =
typename NodeT1::ChildNodeType;
921 template<
typename TreeOrLeafManagerT>
925 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
926 static_assert(RootNodeType::LEVEL > 3,
"expected instantiation of template specialization");
927 static const Index LEVELS = 4;
929 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
931 mRoot.getNodes(mList3);
932 for (
size_t i=0, n=mList3.nodeCount(); i<n; ++i) mList3(i).getNodes(mList2);
933 for (
size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
936 if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
937 tree.getNodes(mList0);
939 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
947 void clear() { mList0.
clear(); mList1.clear(); mList2.clear(); mList3.clear; }
954 mRoot.getNodes(mList3);
955 for (
size_t i=0, n=mList3.nodeCount(); i<n; ++i) mList3(i).getNodes(mList2);
956 for (
size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
957 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
966 return mList0.nodeCount() + mList1.nodeCount()
967 + mList2.nodeCount() + mList3.nodeCount();
974 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() :
975 i==2 ? mList2.nodeCount() : i==3 ? mList3.nodeCount() : 0;
978 template<
typename NodeOp>
979 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
981 mList0.foreach(op, threaded, grainSize);
982 mList1.foreach(op, threaded, grainSize);
983 mList2.foreach(op, threaded, grainSize);
984 mList3.foreach(op, threaded, grainSize);
988 template<
typename NodeOp>
989 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
992 mList3.foreach(op, threaded, grainSize);
993 mList2.foreach(op, threaded, grainSize);
994 mList1.foreach(op, threaded, grainSize);
995 mList0.foreach(op, threaded, grainSize);
998 template<
typename NodeOp>
999 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1001 mList0.reduce(op, threaded, grainSize);
1002 mList1.reduce(op, threaded, grainSize);
1003 mList2.reduce(op, threaded, grainSize);
1004 mList3.reduce(op, threaded, grainSize);
1008 template<
typename NodeOp>
1009 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1012 mList3.reduce(op, threaded, grainSize);
1013 mList2.reduce(op, threaded, grainSize);
1014 mList1.reduce(op, threaded, grainSize);
1015 mList0.reduce(op, threaded, grainSize);
1020 using NodeT3 =
typename NodeT4::ChildNodeType;
1021 using NodeT2 =
typename NodeT3::ChildNodeType;
1022 using NodeT1 =
typename NodeT2::ChildNodeType;
1023 using NodeT0 =
typename NodeT1::ChildNodeType;
1044 #endif // OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED This class caches tree nodes of a specific type in a linear array.
Definition: NodeManager.h:68
Iterator begin() const
Definition: NodeManager.h:145
NodeManagerLink< typename NodeT::ChildNodeType, LEVEL-1 > mNext
Definition: NodeManager.h:306
void resize(size_t n)
Definition: NodeManager.h:86
void foreachTopDown(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to all the nodes in the tree.
Definition: NodeManager.h:477
bool empty() const
Return true if this iterator is exhausted.
Definition: NodeManager.h:132
RootNodeType & mRoot
Definition: NodeManager.h:559
Iterator end() const
Definition: NodeManager.h:147
void reduceBottomUp(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:544
bool isValid() const
Definition: NodeManager.h:126
void reduceBottomUp(NodeOp &op, bool threaded, size_t grainSize)
Definition: NodeManager.h:291
NodeT * operator->() const
Return a pointer to the node to which this iterator is pointing.
Definition: NodeManager.h:123
NodeList< NodeT > mList
Definition: NodeManager.h:305
Index64 nodeCount(Index i) const
Return the number of cached nodes at level i, where 0 corresponds to the lowest level.
Definition: NodeManager.h:411
const NodeList & nodeList() const
Definition: NodeManager.h:103
NodeT & operator*() const
Return a reference to the node to which this iterator is pointing.
Definition: NodeManager.h:121
bool operator!=(const Iterator &other) const
Definition: NodeManager.h:133
void clear()
Definition: NodeManager.h:252
Iterator(const NodeRange &range, size_t pos)
Definition: NodeManager.h:112
NodeManagerLink()
Definition: NodeManager.h:248
NodeT *& operator[](size_t n)
Definition: NodeManager.h:80
ListT mList
Definition: NodeManager.h:233
virtual ~NodeManager()
Definition: NodeManager.h:394
const RootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:404
NodeRange(size_t begin, size_t end, const NodeList &nodeList, size_t grainSize=1)
Definition: NodeManager.h:92
void clear()
Clear all the cached tree nodes.
Definition: NodeManager.h:397
void reduceTopDown(NodeOp &op, bool threaded, size_t grainSize)
Definition: NodeManager.h:298
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:136
NodeRange(NodeRange &r, tbb::split)
Definition: NodeManager.h:95
std::deque< value_type > ListT
Definition: NodeManager.h:72
Index64 nodeCount(Index i) const
Definition: NodeManager.h:271
virtual ~NodeManagerLink()
Definition: NodeManager.h:250
NodeManagerLink< typename RootNodeType::ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:560
Definition: Exceptions.h:40
void clear()
Definition: NodeManager.h:84
const NodeRange & nodeRange() const
Definition: NodeManager.h:138
To facilitate threading over the nodes of a tree, cache node pointers in linear arrays, one for each level of the tree.
Definition: NodeManager.h:58
NodeT & operator()(size_t n) const
Definition: NodeManager.h:78
Index32 Index
Definition: Types.h:61
NodeList()
Definition: NodeManager.h:74
void init(ParentT &parent, TreeOrLeafManagerT &tree)
Definition: NodeManager.h:255
void reduceTopDown(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:551
uint64_t Index64
Definition: Types.h:60
Iterator & operator++()
Advance to the next node.
Definition: NodeManager.h:119
size_t size() const
Definition: NodeManager.h:99
Index64 nodeCount() const
Return the total number of cached nodes (excluding the root node)
Definition: NodeManager.h:407
This class is a link in a chain that each caches tree nodes of a specific type in a linear array...
Definition: NodeManager.h:245
typename TreeOrLeafManagerT::RootNodeType RootNodeType
Definition: NodeManager.h:389
NodeManager(TreeOrLeafManagerT &tree)
Definition: NodeManager.h:392
void rebuild()
Clear and recache all the tree nodes from the tree. This is required if tree nodes have been added or...
Definition: NodeManager.h:401
void push_back(NodeT *node)
Definition: NodeManager.h:76
NodeT0 * value_type
Definition: NodeManager.h:71
void foreachBottomUp(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that applies a user-supplied functor to all the nodes in the tree.
Definition: NodeManager.h:470
Definition: NodeManager.h:88
bool is_divisible() const
Definition: NodeManager.h:107
Index64 nodeCount() const
Definition: NodeManager.h:82
Index64 nodeCount() const
Definition: NodeManager.h:269
Mat3< typename promote< T0, T1 >::type > operator*(const Mat3< T0 > &m0, const Mat3< T1 > &m1)
Multiply m0 by m1 and return the resulting matrix.
Definition: Mat3.h:645
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:188
bool operator==(const Iterator &other) const
Definition: NodeManager.h:137
void rebuild(ParentT &parent)
Definition: NodeManager.h:262
size_t grainsize() const
Definition: NodeManager.h:101
bool empty() const
Definition: NodeManager.h:105
size_t pos() const
Return the index into the list of the current node.
Definition: NodeManager.h:125
NodeRange nodeRange(size_t grainsize=1) const
Return a TBB-compatible NodeRange.
Definition: NodeManager.h:163
void foreachTopDown(const NodeOp &op, bool threaded, size_t grainSize)
Definition: NodeManager.h:284
void foreachBottomUp(const NodeOp &op, bool threaded, size_t grainSize)
Definition: NodeManager.h:277
void reduce(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:176
bool test() const
Return true if this iterator is not yet exhausted.
Definition: NodeManager.h:128
Definition: NodeManager.h:109