13 #ifndef OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
14 #define OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
17 #include <tbb/parallel_for.h>
18 #include <tbb/parallel_reduce.h>
29 template<
typename TreeOrLeafManagerT, Index LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
35 template<
typename TreeOrLeafManagerT, Index _LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
36 class DynamicNodeManager;
46 static bool valid(
size_t) {
return true; }
53 template<
typename NodeT>
59 NodeT&
operator()(
size_t n)
const { assert(n<mNodeCount);
return *(mNodes[n]); }
61 NodeT*&
operator[](
size_t n) { assert(n<mNodeCount);
return mNodes[n]; }
73 template <
typename RootT>
78 size_t nodeCount = root.childCount();
80 if (nodeCount != mNodeCount) {
82 mNodePtrs.reset(
new NodeT*[nodeCount]);
83 mNodes = mNodePtrs.get();
88 mNodeCount = nodeCount;
91 if (mNodeCount == 0)
return false;
95 NodeT** nodePtr = mNodes;
96 for (
auto iter = root.beginChildOn(); iter; ++iter) {
97 *nodePtr++ = &iter.getValue();
104 template <
typename ParentsT,
typename NodeFilterT>
105 bool initNodeChildren(ParentsT& parents,
const NodeFilterT& nodeFilter = NodeFilterT(),
bool serial =
false)
109 std::vector<Index32> nodeCounts;
111 nodeCounts.reserve(parents.nodeCount());
112 for (
size_t i = 0; i < parents.nodeCount(); i++) {
113 if (!nodeFilter.valid(i)) nodeCounts.push_back(0);
114 else nodeCounts.push_back(parents(i).childCount());
117 nodeCounts.resize(parents.nodeCount());
122 tbb::blocked_range<Index64>(0, parents.nodeCount(), 64),
123 [&](tbb::blocked_range<Index64>& range)
125 for (Index64 i = range.begin(); i < range.end(); i++) {
126 if (!nodeFilter.valid(i)) nodeCounts[i] = 0;
127 else nodeCounts[i] = parents(i).childCount();
135 for (
size_t i = 1; i < nodeCounts.size(); i++) {
136 nodeCounts[i] += nodeCounts[i-1];
139 const size_t nodeCount = nodeCounts.empty() ? 0 : nodeCounts.back();
143 if (nodeCount != mNodeCount) {
145 mNodePtrs.reset(
new NodeT*[nodeCount]);
146 mNodes = mNodePtrs.get();
151 mNodeCount = nodeCount;
154 if (mNodeCount == 0)
return false;
159 NodeT** nodePtr = mNodes;
160 for (
size_t i = 0; i < parents.nodeCount(); i++) {
161 if (!nodeFilter.valid(i))
continue;
162 for (
auto iter = parents(i).beginChildOn(); iter; ++iter) {
163 *nodePtr++ = &iter.getValue();
168 tbb::blocked_range<Index64>(0, parents.nodeCount()),
169 [&](tbb::blocked_range<Index64>& range)
171 Index64 i = range.begin();
172 NodeT** nodePtr = mNodes;
173 if (i > 0) nodePtr += nodeCounts[i-1];
174 for ( ; i < range.end(); i++) {
175 if (!nodeFilter.valid(i)) continue;
176 for (auto iter = parents(i).beginChildOn(); iter; ++iter) {
177 *nodePtr++ = &iter.getValue();
192 mEnd(end), mBegin(begin), mGrainSize(grainSize), mNodeList(nodeList) {}
195 mEnd(r.mEnd), mBegin(doSplit(r)), mGrainSize(r.mGrainSize),
196 mNodeList(r.mNodeList) {}
198 size_t size()
const {
return mEnd - mBegin; }
204 bool empty()
const {
return !(mBegin < mEnd);}
213 assert(this->isValid());
220 NodeT&
operator*()
const {
return mRange.mNodeList(mPos); }
224 size_t pos()
const {
return mPos; }
225 bool isValid()
const {
return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
227 bool test()
const {
return mPos < mRange.mEnd; }
229 operator bool()
const {
return this->test(); }
231 bool empty()
const {
return !this->test(); }
234 return (mPos != other.mPos) || (&mRange != &other.mRange);
249 size_t mEnd, mBegin, mGrainSize;
255 size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
264 return NodeRange(0, this->nodeCount(), *
this, grainsize);
267 template<
typename NodeOp>
268 void foreach(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
270 NodeTransformerCopy<NodeOp> transform(op);
271 transform.run(this->nodeRange(grainSize), threaded);
274 template<
typename NodeOp>
275 void reduce(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
277 NodeReducer<NodeOp> transform(op);
278 transform.run(this->nodeRange(grainSize), threaded);
283 template<
typename NodeOp>
286 NodeTransformer<NodeOp, OpWithIndex> transform(op);
287 transform.run(this->nodeRange(grainSize), threaded);
291 template<
typename NodeOp>
294 NodeReducer<NodeOp, OpWithIndex> transform(op);
295 transform.run(this->nodeRange(grainSize), threaded);
302 struct OpWithoutIndex
304 template <
typename T>
305 static void eval(T& node,
typename NodeRange::Iterator& iter) { node(*iter); }
312 template <
typename T>
313 static void eval(T& node,
typename NodeRange::Iterator& iter) { node(*iter, iter.pos()); }
317 template<
typename NodeOp,
typename OpT = OpWithoutIndex>
318 struct NodeTransformerCopy
320 NodeTransformerCopy(
const NodeOp& nodeOp) : mNodeOp(nodeOp)
323 void run(
const NodeRange& range,
bool threaded =
true)
325 threaded ? tbb::parallel_for(range, *
this) : (*this)(range);
327 void operator()(
const NodeRange& range)
const
329 for (
typename NodeRange::Iterator it = range.begin(); it; ++it) {
330 OpT::template eval(mNodeOp, it);
333 const NodeOp mNodeOp;
337 template<
typename NodeOp,
typename OpT = OpWithoutIndex>
338 struct NodeTransformer
340 NodeTransformer(
const NodeOp& nodeOp) : mNodeOp(nodeOp)
343 void run(
const NodeRange& range,
bool threaded =
true)
345 threaded ? tbb::parallel_for(range, *
this) : (*this)(range);
347 void operator()(
const NodeRange& range)
const
349 for (
typename NodeRange::Iterator it = range.begin(); it; ++it) {
350 OpT::template eval(mNodeOp, it);
353 const NodeOp& mNodeOp;
357 template<
typename NodeOp,
typename OpT = OpWithoutIndex>
360 NodeReducer(NodeOp& nodeOp) : mNodeOp(&nodeOp)
363 NodeReducer(
const NodeReducer& other, tbb::split)
364 : mNodeOpPtr(
std::make_unique<NodeOp>(*(other.mNodeOp),
tbb::split()))
365 , mNodeOp(mNodeOpPtr.get())
368 void run(
const NodeRange& range,
bool threaded =
true)
370 threaded ? tbb::parallel_reduce(range, *
this) : (*this)(range);
372 void operator()(
const NodeRange& range)
374 for (
typename NodeRange::Iterator it = range.begin(); it; ++it) {
375 OpT::template eval(*mNodeOp, it);
378 void join(
const NodeReducer& other)
380 mNodeOp->join(*(other.mNodeOp));
382 std::unique_ptr<NodeOp> mNodeOpPtr;
383 NodeOp *mNodeOp =
nullptr;
388 size_t mNodeCount = 0;
390 NodeT** mNodes =
nullptr;
401 template<
typename NodeT, Index LEVEL>
410 void clear() { mList.clear(); mNext.clear(); }
412 template <
typename RootT>
415 mList.initRootChildren(root);
416 mNext.initNodeChildren(mList, serial);
419 template<
typename ParentsT>
422 mList.initNodeChildren(parents,
NodeFilter(), serial);
423 mNext.initNodeChildren(mList, serial);
430 return i==NodeT::LEVEL ? mList.nodeCount() : mNext.nodeCount(i);
433 template<
typename NodeOp>
436 mNext.foreachBottomUp(op, threaded, grainSize);
437 mList.foreach(op, threaded, grainSize);
440 template<
typename NodeOp>
443 mList.foreach(op, threaded, grainSize);
444 mNext.foreachTopDown(op, threaded, grainSize);
447 template<
typename NodeOp>
450 mNext.reduceBottomUp(op, threaded, grainSize);
451 mList.reduce(op, threaded, grainSize);
454 template<
typename NodeOp>
457 mList.reduce(op, threaded, grainSize);
458 mNext.reduceTopDown(op, threaded, grainSize);
473 template<
typename NodeT>
480 void clear() { mList.
clear(); }
482 template <
typename RootT>
483 void initRootChildren(RootT& root,
bool =
false) { mList.initRootChildren(root); }
485 template<
typename ParentsT>
486 void initNodeChildren(ParentsT& parents,
bool serial =
false) { mList.initNodeChildren(parents, NodeFilter(), serial); }
488 Index64 nodeCount()
const {
return mList.nodeCount(); }
490 Index64 nodeCount(
Index)
const {
return mList.nodeCount(); }
492 template<
typename NodeOp>
493 void foreachBottomUp(
const NodeOp& op,
bool threaded,
size_t grainSize)
495 mList.foreach(op, threaded, grainSize);
498 template<
typename NodeOp>
499 void foreachTopDown(
const NodeOp& op,
bool threaded,
size_t grainSize)
501 mList.foreach(op, threaded, grainSize);
504 template<
typename NodeOp>
505 void reduceBottomUp(NodeOp& op,
bool threaded,
size_t grainSize)
507 mList.reduce(op, threaded, grainSize);
510 template<
typename NodeOp>
511 void reduceTopDown(NodeOp& op,
bool threaded,
size_t grainSize)
513 mList.reduce(op, threaded, grainSize);
517 NodeList<NodeT> mList;
529 template<
typename TreeOrLeafManagerT, Index _LEVELS>
533 static const Index LEVELS = _LEVELS;
534 static_assert(LEVELS > 0,
535 "expected instantiation of template specialization");
540 static_assert(RootNodeType::LEVEL >= LEVELS,
"number of levels exceeds root node height");
545 this->rebuild(serial);
555 void rebuild(
bool serial =
false) { mChain.initRootChildren(mRoot, serial); }
568 template<
typename NodeOp>
626 mChain.foreachBottomUp(op, threaded, grainSize);
630 template<
typename NodeOp>
634 mChain.foreachTopDown(op, threaded, grainSize);
640 template<
typename NodeOp>
700 mChain.reduceBottomUp(op, threaded, grainSize);
704 template<
typename NodeOp>
708 mChain.reduceTopDown(op, threaded, grainSize);
723 template <
typename OpT>
728 , mValidPtr(
std::make_unique<bool[]>(size))
729 , mValid(mValidPtr.get()) { }
733 , mValid(other.mValid) { }
735 template<
typename NodeT>
738 mValid[idx] = mOp(node, idx);
741 bool valid(
size_t idx)
const {
return mValid[idx]; }
743 const OpT&
op()
const {
return mOp; }
747 std::unique_ptr<bool[]> mValidPtr;
748 bool* mValid =
nullptr;
754 template <
typename OpT>
759 , mValidPtr(
std::make_unique<bool[]>(size))
760 , mValid(mValidPtr.get()) { }
764 , mValid(other.mValid) { }
767 : mOpPtr(
std::make_unique<OpT>(*(other.mOp),
tbb::split()))
769 , mValid(other.mValid) { }
771 template<
typename NodeT>
774 mValid[idx] = (*mOp)(node, idx);
779 mOp->join(*(other.mOp));
787 OpT&
op() {
return *mOp; }
790 std::unique_ptr<OpT> mOpPtr;
792 std::unique_ptr<bool[]> mValidPtr;
793 bool* mValid =
nullptr;
801 template<
typename NodeT, Index LEVEL>
810 template<
typename NodeOpT,
typename RootT>
811 void foreachTopDown(
const NodeOpT& op, RootT& root,
bool threaded,
size_t grainSize)
813 if (!op(root, 0))
return;
814 if (!mList.initRootChildren(root))
return;
816 mList.foreachWithIndex(filterOp, threaded, grainSize);
817 mNext.foreachTopDownRecurse(filterOp, mList, threaded, grainSize);
820 template<
typename FilterOpT,
typename ParentT>
823 if (!mList.initNodeChildren(parent, filterOp, !threaded))
return;
824 FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
825 mList.foreachWithIndex(childFilterOp, threaded, grainSize);
826 mNext.foreachTopDownRecurse(childFilterOp, mList, threaded, grainSize);
829 template<
typename NodeOpT,
typename RootT>
830 void reduceTopDown(NodeOpT& op, RootT& root,
bool threaded,
size_t grainSize)
832 if (!op(root, 0))
return;
833 if (!mList.initRootChildren(root))
return;
835 mList.reduceWithIndex(filterOp, threaded, grainSize);
836 mNext.reduceTopDownRecurse(filterOp, mList, threaded, grainSize);
839 template<
typename FilterOpT,
typename ParentT>
842 if (!mList.initNodeChildren(parent, filterOp, !threaded))
return;
843 FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
844 mList.reduceWithIndex(childFilterOp, threaded, grainSize);
845 mNext.reduceTopDownRecurse(childFilterOp, mList, threaded, grainSize);
857 template<
typename NodeT>
863 template<
typename NodeFilterOp,
typename ParentT>
864 void foreachTopDownRecurse(
const NodeFilterOp& nodeFilterOp, ParentT& parent,
bool threaded,
size_t grainSize)
866 if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded))
return;
867 mList.foreachWithIndex(nodeFilterOp.op(), threaded, grainSize);
870 template<
typename NodeFilterOp,
typename ParentT>
871 void reduceTopDownRecurse(NodeFilterOp& nodeFilterOp, ParentT& parent,
bool threaded,
size_t grainSize)
873 if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded))
return;
874 mList.reduceWithIndex(nodeFilterOp.op(), threaded, grainSize);
878 NodeList<NodeT> mList;
882 template<
typename TreeOrLeafManagerT, Index _LEVELS>
886 static const Index LEVELS = _LEVELS;
887 static_assert(LEVELS > 0,
888 "expected instantiation of template specialization");
893 static_assert(RootNodeType::LEVEL >= LEVELS,
"number of levels exceeds root node height");
967 template<
typename NodeOp>
970 mChain.foreachTopDown(op, mRoot, threaded, grainSize);
1031 template<
typename NodeOp>
1034 mChain.reduceTopDown(op, mRoot, threaded, grainSize);
1049 template<
typename TreeOrLeafManagerT>
1053 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1055 static const Index LEVELS = 0;
1057 NodeManager(TreeOrLeafManagerT& tree,
bool =
false) : mRoot(tree.root()) { }
1059 NodeManager(
const NodeManager&) =
delete;
1066 void rebuild(
bool =
false) { }
1069 const RootNodeType& root()
const {
return mRoot; }
1072 Index64 nodeCount()
const {
return 0; }
1076 template<
typename NodeOp>
1077 void foreachBottomUp(
const NodeOp& op,
bool,
size_t) { op(mRoot); }
1079 template<
typename NodeOp>
1080 void foreachTopDown(
const NodeOp& op,
bool,
size_t) { op(mRoot); }
1082 template<
typename NodeOp>
1083 void reduceBottomUp(NodeOp& op,
bool,
size_t) { op(mRoot); }
1085 template<
typename NodeOp>
1086 void reduceTopDown(NodeOp& op,
bool,
size_t) { op(mRoot); }
1089 RootNodeType& mRoot;
1098 template<
typename TreeOrLeafManagerT>
1099 class NodeManager<TreeOrLeafManagerT, 1>
1102 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1104 static_assert(RootNodeType::LEVEL > 0,
"expected instantiation of template specialization");
1105 static const Index LEVELS = 1;
1107 NodeManager(TreeOrLeafManagerT& tree,
bool serial =
false)
1108 : mRoot(tree.root())
1110 this->rebuild(serial);
1113 NodeManager(
const NodeManager&) =
delete;
1116 void clear() { mList0.clear(); }
1120 void rebuild(
bool =
false) { mList0.initRootChildren(mRoot); }
1123 const RootNodeType& root()
const {
return mRoot; }
1126 Index64 nodeCount()
const {
return mList0.nodeCount(); }
1130 Index64 nodeCount(
Index i)
const {
return i==0 ? mList0.nodeCount() : 0; }
1132 template<
typename NodeOp>
1133 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1135 mList0.foreach(op, threaded, grainSize);
1139 template<
typename NodeOp>
1140 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1143 mList0.foreach(op, threaded, grainSize);
1146 template<
typename NodeOp>
1147 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1149 mList0.reduce(op, threaded, grainSize);
1153 template<
typename NodeOp>
1154 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1157 mList0.reduce(op, threaded, grainSize);
1161 using NodeT1 = RootNodeType;
1162 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1164 using ListT0 = NodeList<NodeT0>;
1176 template<
typename TreeOrLeafManagerT>
1177 class NodeManager<TreeOrLeafManagerT, 2>
1180 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1182 static_assert(RootNodeType::LEVEL > 1,
"expected instantiation of template specialization");
1183 static const Index LEVELS = 2;
1185 NodeManager(TreeOrLeafManagerT& tree,
bool serial =
false) : mRoot(tree.root())
1187 this->rebuild(serial);
1190 NodeManager(
const NodeManager&) =
delete;
1193 void clear() { mList0.clear(); mList1.clear(); }
1197 void rebuild(
bool serial =
false)
1199 mList1.initRootChildren(mRoot);
1200 mList0.initNodeChildren(mList1, NodeFilter(), serial);
1204 const RootNodeType& root()
const {
return mRoot; }
1207 Index64 nodeCount()
const {
return mList0.nodeCount() + mList1.nodeCount(); }
1213 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() : 0;
1216 template<
typename NodeOp>
1217 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1219 mList0.foreach(op, threaded, grainSize);
1220 mList1.foreach(op, threaded, grainSize);
1224 template<
typename NodeOp>
1225 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1228 mList1.foreach(op, threaded, grainSize);
1229 mList0.foreach(op, threaded, grainSize);
1232 template<
typename NodeOp>
1233 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1235 mList0.reduce(op, threaded, grainSize);
1236 mList1.reduce(op, threaded, grainSize);
1240 template<
typename NodeOp>
1241 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1244 mList1.reduce(op, threaded, grainSize);
1245 mList0.reduce(op, threaded, grainSize);
1249 using NodeT2 = RootNodeType;
1250 using NonConstNodeT1 =
typename NodeT2::ChildNodeType;
1252 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1255 using ListT1 = NodeList<NodeT1>;
1256 using ListT0 = NodeList<NodeT0>;
1269 template<
typename TreeOrLeafManagerT>
1270 class NodeManager<TreeOrLeafManagerT, 3>
1273 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1275 static_assert(RootNodeType::LEVEL > 2,
"expected instantiation of template specialization");
1276 static const Index LEVELS = 3;
1278 NodeManager(TreeOrLeafManagerT& tree,
bool serial =
false) : mRoot(tree.root())
1280 this->rebuild(serial);
1283 NodeManager(
const NodeManager&) =
delete;
1286 void clear() { mList0.clear(); mList1.clear(); mList2.clear(); }
1290 void rebuild(
bool serial =
false)
1292 mList2.initRootChildren(mRoot);
1293 mList1.initNodeChildren(mList2, NodeFilter(), serial);
1294 mList0.initNodeChildren(mList1, NodeFilter(), serial);
1298 const RootNodeType& root()
const {
return mRoot; }
1301 Index64 nodeCount()
const {
return mList0.nodeCount()+mList1.nodeCount()+mList2.nodeCount(); }
1307 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount()
1308 : i==2 ? mList2.nodeCount() : 0;
1311 template<
typename NodeOp>
1312 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1314 mList0.foreach(op, threaded, grainSize);
1315 mList1.foreach(op, threaded, grainSize);
1316 mList2.foreach(op, threaded, grainSize);
1320 template<
typename NodeOp>
1321 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1324 mList2.foreach(op, threaded, grainSize);
1325 mList1.foreach(op, threaded, grainSize);
1326 mList0.foreach(op, threaded, grainSize);
1329 template<
typename NodeOp>
1330 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1332 mList0.reduce(op, threaded, grainSize);
1333 mList1.reduce(op, threaded, grainSize);
1334 mList2.reduce(op, threaded, grainSize);
1338 template<
typename NodeOp>
1339 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1342 mList2.reduce(op, threaded, grainSize);
1343 mList1.reduce(op, threaded, grainSize);
1344 mList0.reduce(op, threaded, grainSize);
1348 using NodeT3 = RootNodeType;
1349 using NonConstNodeT2 =
typename NodeT3::ChildNodeType;
1351 using NonConstNodeT1 =
typename NodeT2::ChildNodeType;
1353 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1356 using ListT2 = NodeList<NodeT2>;
1357 using ListT1 = NodeList<NodeT1>;
1358 using ListT0 = NodeList<NodeT0>;
1372 template<
typename TreeOrLeafManagerT>
1373 class NodeManager<TreeOrLeafManagerT, 4>
1376 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1378 static_assert(RootNodeType::LEVEL > 3,
"expected instantiation of template specialization");
1379 static const Index LEVELS = 4;
1381 NodeManager(TreeOrLeafManagerT& tree,
bool serial =
false) : mRoot(tree.root())
1383 this->rebuild(serial);
1386 NodeManager(
const NodeManager&) =
delete;
1389 void clear() { mList0.clear(); mList1.clear(); mList2.clear(); mList3.clear(); }
1393 void rebuild(
bool serial =
false)
1395 mList3.initRootChildren(mRoot);
1396 mList2.initNodeChildren(mList3, NodeFilter(), serial);
1397 mList1.initNodeChildren(mList2, NodeFilter(), serial);
1398 mList0.initNodeChildren(mList1, NodeFilter(), serial);
1402 const RootNodeType& root()
const {
return mRoot; }
1407 return mList0.nodeCount() + mList1.nodeCount()
1408 + mList2.nodeCount() + mList3.nodeCount();
1415 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() :
1416 i==2 ? mList2.nodeCount() : i==3 ? mList3.nodeCount() : 0;
1419 template<
typename NodeOp>
1420 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1422 mList0.foreach(op, threaded, grainSize);
1423 mList1.foreach(op, threaded, grainSize);
1424 mList2.foreach(op, threaded, grainSize);
1425 mList3.foreach(op, threaded, grainSize);
1429 template<
typename NodeOp>
1430 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1433 mList3.foreach(op, threaded, grainSize);
1434 mList2.foreach(op, threaded, grainSize);
1435 mList1.foreach(op, threaded, grainSize);
1436 mList0.foreach(op, threaded, grainSize);
1439 template<
typename NodeOp>
1440 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1442 mList0.reduce(op, threaded, grainSize);
1443 mList1.reduce(op, threaded, grainSize);
1444 mList2.reduce(op, threaded, grainSize);
1445 mList3.reduce(op, threaded, grainSize);
1449 template<
typename NodeOp>
1450 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1453 mList3.reduce(op, threaded, grainSize);
1454 mList2.reduce(op, threaded, grainSize);
1455 mList1.reduce(op, threaded, grainSize);
1456 mList0.reduce(op, threaded, grainSize);
1460 using NodeT4 = RootNodeType;
1461 using NonConstNodeT3 =
typename NodeT4::ChildNodeType;
1463 using NonConstNodeT2 =
typename NodeT3::ChildNodeType;
1465 using NonConstNodeT1 =
typename NodeT2::ChildNodeType;
1467 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1470 using ListT3 = NodeList<NodeT3>;
1471 using ListT2 = NodeList<NodeT2>;
1472 using ListT1 = NodeList<NodeT1>;
1473 using ListT0 = NodeList<NodeT0>;
1488 template<
typename TreeOrLeafManagerT>
1489 class DynamicNodeManager<TreeOrLeafManagerT, 1>
1492 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1494 static_assert(RootNodeType::LEVEL > 0,
"expected instantiation of template specialization");
1495 static const Index LEVELS = 1;
1497 explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1499 DynamicNodeManager(
const DynamicNodeManager&) =
delete;
1502 const RootNodeType& root()
const {
return mRoot; }
1504 template<
typename NodeOp>
1505 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1508 if (!op(mRoot, 0))
return;
1510 if (!mList0.initRootChildren(mRoot))
return;
1511 ForeachFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1512 mList0.foreachWithIndex(nodeOp, threaded, grainSize);
1515 template<
typename NodeOp>
1516 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1519 if (!op(mRoot, 0))
return;
1521 if (!mList0.initRootChildren(mRoot))
return;
1522 ReduceFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1523 mList0.reduceWithIndex(nodeOp, threaded, grainSize);
1527 using NodeT1 = RootNodeType;
1528 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1530 using ListT0 = NodeList<NodeT0>;
1542 template<
typename TreeOrLeafManagerT>
1543 class DynamicNodeManager<TreeOrLeafManagerT, 2>
1546 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1548 static_assert(RootNodeType::LEVEL > 1,
"expected instantiation of template specialization");
1549 static const Index LEVELS = 2;
1551 explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1553 DynamicNodeManager(
const DynamicNodeManager&) =
delete;
1556 const RootNodeType& root()
const {
return mRoot; }
1558 template<
typename NodeOp>
1559 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1562 if (!op(mRoot, 0))
return;
1564 if (!mList1.initRootChildren(mRoot))
return;
1565 ForeachFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1566 mList1.foreachWithIndex(nodeOp, threaded, grainSize);
1568 if (!mList0.initNodeChildren(mList1, nodeOp, !threaded))
return;
1569 mList0.foreachWithIndex(op, threaded, grainSize);
1572 template<
typename NodeOp>
1573 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1576 if (!op(mRoot, 0))
return;
1578 if (!mList1.initRootChildren(mRoot))
return;
1579 ReduceFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1580 mList1.reduceWithIndex(nodeOp, threaded, grainSize);
1582 if (!mList0.initNodeChildren(mList1, nodeOp, !threaded))
return;
1583 mList0.reduceWithIndex(op, threaded, grainSize);
1587 using NodeT2 = RootNodeType;
1588 using NonConstNodeT1 =
typename NodeT2::ChildNodeType;
1590 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1593 using ListT1 = NodeList<NodeT1>;
1594 using ListT0 = NodeList<NodeT0>;
1607 template<
typename TreeOrLeafManagerT>
1608 class DynamicNodeManager<TreeOrLeafManagerT, 3>
1611 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1613 static_assert(RootNodeType::LEVEL > 2,
"expected instantiation of template specialization");
1614 static const Index LEVELS = 3;
1616 explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1618 DynamicNodeManager(
const DynamicNodeManager&) =
delete;
1621 const RootNodeType& root()
const {
return mRoot; }
1623 template<
typename NodeOp>
1624 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1627 if (!op(mRoot, 0))
return;
1629 if (!mList2.initRootChildren(mRoot))
return;
1630 ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1631 mList2.foreachWithIndex(nodeOp2, threaded, grainSize);
1633 if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded))
return;
1634 ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1635 mList1.foreachWithIndex(nodeOp1, threaded, grainSize);
1637 if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded))
return;
1638 mList0.foreachWithIndex(op, threaded, grainSize);
1641 template<
typename NodeOp>
1642 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1645 if (!op(mRoot, 0))
return;
1647 if (!mList2.initRootChildren(mRoot))
return;
1648 ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1649 mList2.reduceWithIndex(nodeOp2, threaded, grainSize);
1651 if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded))
return;
1652 ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1653 mList1.reduceWithIndex(nodeOp1, threaded, grainSize);
1655 if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded))
return;
1656 mList0.reduceWithIndex(op, threaded, grainSize);
1660 using NodeT3 = RootNodeType;
1661 using NonConstNodeT2 =
typename NodeT3::ChildNodeType;
1663 using NonConstNodeT1 =
typename NodeT2::ChildNodeType;
1665 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1668 using ListT2 = NodeList<NodeT2>;
1669 using ListT1 = NodeList<NodeT1>;
1670 using ListT0 = NodeList<NodeT0>;
1684 template<
typename TreeOrLeafManagerT>
1685 class DynamicNodeManager<TreeOrLeafManagerT, 4>
1688 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1690 static_assert(RootNodeType::LEVEL > 3,
"expected instantiation of template specialization");
1691 static const Index LEVELS = 4;
1693 explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1695 DynamicNodeManager(
const DynamicNodeManager&) =
delete;
1698 const RootNodeType& root()
const {
return mRoot; }
1700 template<
typename NodeOp>
1701 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1704 if (!op(mRoot, 0))
return;
1706 if (!mList3.initRootChildren(mRoot))
return;
1707 ForeachFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1708 mList3.foreachWithIndex(nodeOp3, threaded, grainSize);
1710 if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded))
return;
1711 ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1712 mList2.foreachWithIndex(nodeOp2, threaded, grainSize);
1714 if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded))
return;
1715 ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1716 mList1.foreachWithIndex(nodeOp1, threaded, grainSize);
1718 if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded))
return;
1719 mList0.foreachWithIndex(op, threaded, grainSize);
1722 template<
typename NodeOp>
1723 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1726 if (!op(mRoot, 0))
return;
1728 if (!mList3.initRootChildren(mRoot))
return;
1729 ReduceFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1730 mList3.reduceWithIndex(nodeOp3, threaded, grainSize);
1732 if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded))
return;
1733 ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1734 mList2.reduceWithIndex(nodeOp2, threaded, grainSize);
1736 if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded))
return;
1737 ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1738 mList1.reduceWithIndex(nodeOp1, threaded, grainSize);
1740 if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded))
return;
1741 mList0.reduceWithIndex(op, threaded, grainSize);
1745 using NodeT4 = RootNodeType;
1746 using NonConstNodeT3 =
typename NodeT4::ChildNodeType;
1748 using NonConstNodeT2 =
typename NodeT3::ChildNodeType;
1750 using NonConstNodeT1 =
typename NodeT2::ChildNodeType;
1752 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1755 using ListT3 = NodeList<NodeT3>;
1756 using ListT2 = NodeList<NodeT2>;
1757 using ListT1 = NodeList<NodeT1>;
1758 using ListT0 = NodeList<NodeT0>;
This class is a link in a chain that each caches tree nodes of a specific type in a linear array.
Definition: NodeManager.h:803
typename CopyConstness< NodeT, NonConstChildNodeType >::Type ChildNodeType
Definition: NodeManager.h:806
void reduceTopDownRecurse(FilterOpT &filterOp, ParentT &parent, bool threaded, size_t grainSize)
Definition: NodeManager.h:840
void foreachTopDownRecurse(const FilterOpT &filterOp, ParentT &parent, bool threaded, size_t grainSize)
Definition: NodeManager.h:821
void reduceTopDown(NodeOpT &op, RootT &root, bool threaded, size_t grainSize)
Definition: NodeManager.h:830
typename NodeT::ChildNodeType NonConstChildNodeType
Definition: NodeManager.h:805
DynamicNodeManagerLink()=default
DynamicNodeManagerLink< ChildNodeType, LEVEL-1 > mNext
Definition: NodeManager.h:850
NodeList< NodeT > mList
Definition: NodeManager.h:849
void foreachTopDown(const NodeOpT &op, RootT &root, bool threaded, size_t grainSize)
Definition: NodeManager.h:811
Definition: NodeManager.h:884
void reduceTopDown(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:1032
RootNodeType & mRoot
Definition: NodeManager.h:1038
typename RootNodeType::ChildNodeType NonConstChildNodeType
Definition: NodeManager.h:891
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:968
DynamicNodeManagerLink< ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:1039
typename CopyConstness< TreeOrLeafManagerT, NonConstRootNodeType >::Type RootNodeType
Definition: NodeManager.h:890
typename CopyConstness< TreeOrLeafManagerT, NonConstChildNodeType >::Type ChildNodeType
Definition: NodeManager.h:892
DynamicNodeManager(const DynamicNodeManager &)=delete
typename TreeOrLeafManagerT::RootNodeType NonConstRootNodeType
Definition: NodeManager.h:889
DynamicNodeManager(TreeOrLeafManagerT &tree)
Definition: NodeManager.h:895
const NonConstRootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:900
Definition: NodeManager.h:209
const NodeRange & nodeRange() const
Definition: NodeManager.h:237
bool test() const
Return true if this iterator is not yet exhausted.
Definition: NodeManager.h:227
Iterator & operator=(const Iterator &)=default
bool isValid() const
Definition: NodeManager.h:225
bool empty() const
Return true if this iterator is exhausted.
Definition: NodeManager.h:231
Iterator(const Iterator &)=default
bool operator!=(const Iterator &other) const
Definition: NodeManager.h:232
NodeT * operator->() const
Return a pointer to the node to which this iterator is pointing.
Definition: NodeManager.h:222
size_t pos() const
Return the index into the list of the current node.
Definition: NodeManager.h:224
Iterator(const NodeRange &range, size_t pos)
Definition: NodeManager.h:211
NodeT & operator*() const
Return a reference to the node to which this iterator is pointing.
Definition: NodeManager.h:220
bool operator==(const Iterator &other) const
Definition: NodeManager.h:236
Iterator & operator++()
Advance to the next node.
Definition: NodeManager.h:218
Definition: NodeManager.h:188
Iterator begin() const
Definition: NodeManager.h:244
size_t size() const
Definition: NodeManager.h:198
bool is_divisible() const
Definition: NodeManager.h:206
NodeRange(size_t begin, size_t end, const NodeList &nodeList, size_t grainSize=1)
Definition: NodeManager.h:191
const NodeList & nodeList() const
Definition: NodeManager.h:202
Iterator end() const
Definition: NodeManager.h:246
bool empty() const
Definition: NodeManager.h:204
size_t grainsize() const
Definition: NodeManager.h:200
NodeRange(NodeRange &r, tbb::split)
Definition: NodeManager.h:194
This class caches tree nodes of a specific type in a linear array.
Definition: NodeManager.h:55
void reduce(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:275
NodeT *& operator[](size_t n)
Definition: NodeManager.h:61
Index64 nodeCount() const
Definition: NodeManager.h:63
NodeRange nodeRange(size_t grainsize=1) const
Return a TBB-compatible NodeRange.
Definition: NodeManager.h:262
void reduceWithIndex(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:292
std::unique_ptr< NodeT *[]> mNodePtrs
Definition: NodeManager.h:389
bool initNodeChildren(ParentsT &parents, const NodeFilterT &nodeFilter=NodeFilterT(), bool serial=false)
Definition: NodeManager.h:105
void foreachWithIndex(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:284
void clear()
Definition: NodeManager.h:65
NodeT & operator()(size_t n) const
Definition: NodeManager.h:59
bool initRootChildren(RootT &root)
Definition: NodeManager.h:74
This class is a link in a chain that each caches tree nodes of a specific type in a linear array.
Definition: NodeManager.h:403
typename CopyConstness< NodeT, NonConstChildNodeType >::Type ChildNodeType
Definition: NodeManager.h:406
NodeManagerLink()=default
void reduceTopDown(NodeOp &op, bool threaded, size_t grainSize)
Definition: NodeManager.h:455
Index64 nodeCount() const
Definition: NodeManager.h:426
void initNodeChildren(ParentsT &parents, bool serial=false)
Definition: NodeManager.h:420
void reduceBottomUp(NodeOp &op, bool threaded, size_t grainSize)
Definition: NodeManager.h:448
void foreachBottomUp(const NodeOp &op, bool threaded, size_t grainSize)
Definition: NodeManager.h:434
void foreachTopDown(const NodeOp &op, bool threaded, size_t grainSize)
Definition: NodeManager.h:441
NodeManagerLink< ChildNodeType, LEVEL-1 > mNext
Definition: NodeManager.h:463
typename NodeT::ChildNodeType NonConstChildNodeType
Definition: NodeManager.h:405
Index64 nodeCount(Index i) const
Definition: NodeManager.h:428
void clear()
Definition: NodeManager.h:410
void initRootChildren(RootT &root, bool serial=false)
Definition: NodeManager.h:413
NodeList< NodeT > mList
Definition: NodeManager.h:462
To facilitate threading over the nodes of a tree, cache node pointers in linear arrays,...
Definition: NodeManager.h:531
void reduceTopDown(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:705
RootNodeType & mRoot
Definition: NodeManager.h:713
NodeManager(TreeOrLeafManagerT &tree, bool serial=false)
Definition: NodeManager.h:542
typename RootNodeType::ChildNodeType NonConstChildNodeType
Definition: NodeManager.h:538
void rebuild(bool serial=false)
Clear and recache all the tree nodes from the tree. This is required if tree nodes have been added or...
Definition: NodeManager.h:555
Index64 nodeCount() const
Return the total number of cached nodes (excluding the root node)
Definition: NodeManager.h:561
NodeManager(const NodeManager &)=delete
void foreachTopDown(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:631
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:624
NodeManagerLink< ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:714
void reduceBottomUp(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:698
typename CopyConstness< TreeOrLeafManagerT, NonConstRootNodeType >::Type RootNodeType
Definition: NodeManager.h:537
typename CopyConstness< TreeOrLeafManagerT, NonConstChildNodeType >::Type ChildNodeType
Definition: NodeManager.h:539
Index64 nodeCount(Index i) const
Return the number of cached nodes at level i, where 0 corresponds to the lowest level.
Definition: NodeManager.h:565
typename TreeOrLeafManagerT::RootNodeType NonConstRootNodeType
Definition: NodeManager.h:536
void clear()
Clear all the cached tree nodes.
Definition: NodeManager.h:551
const RootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:558
void run(const char *ax, openvdb::GridBase &grid)
Run a full AX pipeline (parse, compile and execute) on a single OpenVDB Grid.
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:611
Index32 Index
Definition: openvdb/Types.h:50
uint64_t Index64
Definition: openvdb/Types.h:49
Definition: openvdb/Exceptions.h:13
typename std::remove_const< ToType >::type Type
Definition: openvdb/Types.h:317
Definition: NodeManager.h:725
void operator()(NodeT &node, size_t idx) const
Definition: NodeManager.h:736
ForeachFilterOp(const OpT &op, openvdb::Index64 size)
Definition: NodeManager.h:726
bool valid(size_t idx) const
Definition: NodeManager.h:741
ForeachFilterOp(const ForeachFilterOp &other)
Definition: NodeManager.h:731
const OpT & op() const
Definition: NodeManager.h:743
Definition: NodeManager.h:45
static bool valid(size_t)
Definition: NodeManager.h:46
Definition: NodeManager.h:756
void operator()(NodeT &node, size_t idx) const
Definition: NodeManager.h:772
bool valid(size_t idx) const
Definition: NodeManager.h:782
ReduceFilterOp(const ReduceFilterOp &other)
Definition: NodeManager.h:762
ReduceFilterOp(const ReduceFilterOp &other, tbb::split)
Definition: NodeManager.h:766
ReduceFilterOp(OpT &op, openvdb::Index64 size)
Definition: NodeManager.h:757
OpT & op()
Definition: NodeManager.h:787
void join(const ReduceFilterOp &other)
Definition: NodeManager.h:777
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:116
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:178