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 NodeTransformer<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);
282 template<
typename NodeOp>
285 NodeTransformer<NodeOp, OpWithIndex> transform(op);
286 transform.run(this->nodeRange(grainSize), threaded);
290 template<
typename NodeOp>
293 NodeReducer<NodeOp, OpWithIndex> transform(op);
294 transform.run(this->nodeRange(grainSize), threaded);
301 struct OpWithoutIndex
303 template <
typename T>
304 static void eval(T& node,
typename NodeRange::Iterator& iter) { node(*iter); }
311 template <
typename T>
312 static void eval(T& node,
typename NodeRange::Iterator& iter) { node(*iter, iter.pos()); }
316 template<
typename NodeOp,
typename OpT = OpWithoutIndex>
317 struct NodeTransformer
319 NodeTransformer(
const NodeOp& nodeOp) : mNodeOp(nodeOp)
322 void run(
const NodeRange& range,
bool threaded =
true)
324 threaded ? tbb::parallel_for(range, *
this) : (*this)(range);
326 void operator()(
const NodeRange& range)
const
328 for (
typename NodeRange::Iterator it = range.begin(); it; ++it) {
329 OpT::template eval(mNodeOp, it);
332 const NodeOp mNodeOp;
336 template<
typename NodeOp,
typename OpT = OpWithoutIndex>
339 NodeReducer(NodeOp& nodeOp) : mNodeOp(&nodeOp)
342 NodeReducer(
const NodeReducer& other, tbb::split)
343 : mNodeOpPtr(
std::make_unique<NodeOp>(*(other.mNodeOp),
tbb::split()))
344 , mNodeOp(mNodeOpPtr.get())
347 void run(
const NodeRange& range,
bool threaded =
true)
349 threaded ? tbb::parallel_reduce(range, *
this) : (*this)(range);
351 void operator()(
const NodeRange& range)
353 for (
typename NodeRange::Iterator it = range.begin(); it; ++it) {
354 OpT::template eval(*mNodeOp, it);
357 void join(
const NodeReducer& other)
359 mNodeOp->join(*(other.mNodeOp));
361 std::unique_ptr<NodeOp> mNodeOpPtr;
362 NodeOp *mNodeOp =
nullptr;
367 size_t mNodeCount = 0;
369 NodeT** mNodes =
nullptr;
380 template<
typename NodeT, Index LEVEL>
389 void clear() { mList.clear(); mNext.clear(); }
391 template <
typename RootT>
394 mList.initRootChildren(root);
395 mNext.initNodeChildren(mList, serial);
398 template<
typename ParentsT>
401 mList.initNodeChildren(parents,
NodeFilter(), serial);
402 mNext.initNodeChildren(mList, serial);
409 return i==NodeT::LEVEL ? mList.nodeCount() : mNext.nodeCount(i);
412 template<
typename NodeOp>
415 mNext.foreachBottomUp(op, threaded, grainSize);
416 mList.foreach(op, threaded, grainSize);
419 template<
typename NodeOp>
422 mList.foreach(op, threaded, grainSize);
423 mNext.foreachTopDown(op, threaded, grainSize);
426 template<
typename NodeOp>
429 mNext.reduceBottomUp(op, threaded, grainSize);
430 mList.reduce(op, threaded, grainSize);
433 template<
typename NodeOp>
436 mList.reduce(op, threaded, grainSize);
437 mNext.reduceTopDown(op, threaded, grainSize);
452 template<
typename NodeT>
459 void clear() { mList.
clear(); }
461 template <
typename RootT>
462 void initRootChildren(RootT& root,
bool =
false) { mList.initRootChildren(root); }
464 template<
typename ParentsT>
465 void initNodeChildren(ParentsT& parents,
bool serial =
false) { mList.initNodeChildren(parents, NodeFilter(), serial); }
467 Index64 nodeCount()
const {
return mList.nodeCount(); }
469 Index64 nodeCount(
Index)
const {
return mList.nodeCount(); }
471 template<
typename NodeOp>
472 void foreachBottomUp(
const NodeOp& op,
bool threaded,
size_t grainSize)
474 mList.foreach(op, threaded, grainSize);
477 template<
typename NodeOp>
478 void foreachTopDown(
const NodeOp& op,
bool threaded,
size_t grainSize)
480 mList.foreach(op, threaded, grainSize);
483 template<
typename NodeOp>
484 void reduceBottomUp(NodeOp& op,
bool threaded,
size_t grainSize)
486 mList.reduce(op, threaded, grainSize);
489 template<
typename NodeOp>
490 void reduceTopDown(NodeOp& op,
bool threaded,
size_t grainSize)
492 mList.reduce(op, threaded, grainSize);
496 NodeList<NodeT> mList;
508 template<
typename TreeOrLeafManagerT, Index _LEVELS>
512 static const Index LEVELS = _LEVELS;
513 static_assert(LEVELS > 0,
514 "expected instantiation of template specialization");
519 static_assert(RootNodeType::LEVEL >= LEVELS,
"number of levels exceeds root node height");
524 this->rebuild(serial);
534 void rebuild(
bool serial =
false) { mChain.initRootChildren(mRoot, serial); }
547 template<
typename NodeOp>
605 mChain.foreachBottomUp(op, threaded, grainSize);
609 template<
typename NodeOp>
613 mChain.foreachTopDown(op, threaded, grainSize);
619 template<
typename NodeOp>
679 mChain.reduceBottomUp(op, threaded, grainSize);
683 template<
typename NodeOp>
687 mChain.reduceTopDown(op, threaded, grainSize);
702 template <
typename OpT>
707 , mValidPtr(
std::make_unique<bool[]>(size))
708 , mValid(mValidPtr.get()) { }
712 , mValid(other.mValid) { }
714 template<
typename NodeT>
717 mValid[idx] = mOp(node, idx);
720 bool valid(
size_t idx)
const {
return mValid[idx]; }
722 const OpT&
op()
const {
return mOp; }
726 std::unique_ptr<bool[]> mValidPtr;
727 bool* mValid =
nullptr;
733 template <
typename OpT>
738 , mValidPtr(
std::make_unique<bool[]>(size))
739 , mValid(mValidPtr.get()) { }
743 , mValid(other.mValid) { }
746 : mOpPtr(
std::make_unique<OpT>(*(other.mOp),
tbb::split()))
748 , mValid(other.mValid) { }
750 template<
typename NodeT>
753 mValid[idx] = (*mOp)(node, idx);
758 mOp->join(*(other.mOp));
766 OpT&
op() {
return *mOp; }
769 std::unique_ptr<OpT> mOpPtr;
771 std::unique_ptr<bool[]> mValidPtr;
772 bool* mValid =
nullptr;
780 template<
typename NodeT, Index LEVEL>
786 template<
typename NodeOpT,
typename RootT>
787 void foreachTopDown(
const NodeOpT& op, RootT& root,
bool threaded,
size_t grainSize)
789 if (!op(root, 0))
return;
790 if (!mList.initRootChildren(root))
return;
792 mList.foreachWithIndex(filterOp, threaded, grainSize);
793 mNext.foreachTopDownRecurse(filterOp, mList, threaded, grainSize);
796 template<
typename FilterOpT,
typename ParentT>
799 if (!mList.initNodeChildren(parent, filterOp, !threaded))
return;
800 FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
801 mList.foreachWithIndex(childFilterOp, threaded, grainSize);
804 template<
typename NodeOpT,
typename RootT>
805 void reduceTopDown(NodeOpT& op, RootT& root,
bool threaded,
size_t grainSize)
807 if (!op(root, 0))
return;
808 if (!mList.initRootChildren(root))
return;
810 mList.reduceWithIndex(filterOp, threaded, grainSize);
811 mNext.reduceTopDownRecurse(filterOp, mList, threaded, grainSize);
814 template<
typename FilterOpT,
typename ParentT>
817 if (!mList.initNodeChildren(parent, filterOp, !threaded))
return;
818 FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
819 mList.reduceWithIndex(childFilterOp, threaded, grainSize);
831 template<
typename NodeT>
837 template<
typename NodeFilterOp,
typename ParentT>
838 void foreachTopDownRecurse(
const NodeFilterOp& nodeFilterOp, ParentT& parent,
bool threaded,
size_t grainSize)
840 if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded))
return;
841 mList.foreachWithIndex(nodeFilterOp.op(), threaded, grainSize);
844 template<
typename NodeFilterOp,
typename ParentT>
845 void reduceTopDownRecurse(NodeFilterOp& nodeFilterOp, ParentT& parent,
bool threaded,
size_t grainSize)
847 if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded))
return;
848 mList.reduceWithIndex(nodeFilterOp.op(), threaded, grainSize);
852 NodeList<NodeT> mList;
856 template<
typename TreeOrLeafManagerT, Index _LEVELS>
860 static const Index LEVELS = _LEVELS;
861 static_assert(LEVELS > 0,
862 "expected instantiation of template specialization");
864 static_assert(RootNodeType::LEVEL >= LEVELS,
"number of levels exceeds root node height");
931 template<
typename NodeOp>
934 mChain.foreachTopDown(op, mRoot, threaded, grainSize);
995 template<
typename NodeOp>
998 mChain.reduceTopDown(op, mRoot, threaded, grainSize);
1013 template<
typename TreeOrLeafManagerT>
1017 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1019 static const Index LEVELS = 0;
1021 NodeManager(TreeOrLeafManagerT& tree,
bool =
false) : mRoot(tree.root()) { }
1023 NodeManager(
const NodeManager&) =
delete;
1030 void rebuild(
bool =
false) { }
1033 const RootNodeType& root()
const {
return mRoot; }
1036 Index64 nodeCount()
const {
return 0; }
1040 template<
typename NodeOp>
1041 void foreachBottomUp(
const NodeOp& op,
bool,
size_t) { op(mRoot); }
1043 template<
typename NodeOp>
1044 void foreachTopDown(
const NodeOp& op,
bool,
size_t) { op(mRoot); }
1046 template<
typename NodeOp>
1047 void reduceBottomUp(NodeOp& op,
bool,
size_t) { op(mRoot); }
1049 template<
typename NodeOp>
1050 void reduceTopDown(NodeOp& op,
bool,
size_t) { op(mRoot); }
1053 RootNodeType& mRoot;
1062 template<
typename TreeOrLeafManagerT>
1063 class NodeManager<TreeOrLeafManagerT, 1>
1066 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1068 static_assert(RootNodeType::LEVEL > 0,
"expected instantiation of template specialization");
1069 static const Index LEVELS = 1;
1071 NodeManager(TreeOrLeafManagerT& tree,
bool serial =
false)
1072 : mRoot(tree.root())
1074 this->rebuild(serial);
1077 NodeManager(
const NodeManager&) =
delete;
1080 void clear() { mList0.clear(); }
1084 void rebuild(
bool =
false) { mList0.initRootChildren(mRoot); }
1087 const RootNodeType& root()
const {
return mRoot; }
1090 Index64 nodeCount()
const {
return mList0.nodeCount(); }
1094 Index64 nodeCount(
Index i)
const {
return i==0 ? mList0.nodeCount() : 0; }
1096 template<
typename NodeOp>
1097 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1099 mList0.foreach(op, threaded, grainSize);
1103 template<
typename NodeOp>
1104 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1107 mList0.foreach(op, threaded, grainSize);
1110 template<
typename NodeOp>
1111 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1113 mList0.reduce(op, threaded, grainSize);
1117 template<
typename NodeOp>
1118 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1121 mList0.reduce(op, threaded, grainSize);
1125 using NodeT1 = RootNodeType;
1126 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1128 using ListT0 = NodeList<NodeT0>;
1140 template<
typename TreeOrLeafManagerT>
1141 class NodeManager<TreeOrLeafManagerT, 2>
1144 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1146 static_assert(RootNodeType::LEVEL > 1,
"expected instantiation of template specialization");
1147 static const Index LEVELS = 2;
1149 NodeManager(TreeOrLeafManagerT& tree,
bool serial =
false) : mRoot(tree.root())
1151 this->rebuild(serial);
1154 NodeManager(
const NodeManager&) =
delete;
1157 void clear() { mList0.clear(); mList1.clear(); }
1161 void rebuild(
bool serial =
false)
1163 mList1.initRootChildren(mRoot);
1164 mList0.initNodeChildren(mList1, NodeFilter(), serial);
1168 const RootNodeType& root()
const {
return mRoot; }
1171 Index64 nodeCount()
const {
return mList0.nodeCount() + mList1.nodeCount(); }
1177 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() : 0;
1180 template<
typename NodeOp>
1181 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1183 mList0.foreach(op, threaded, grainSize);
1184 mList1.foreach(op, threaded, grainSize);
1188 template<
typename NodeOp>
1189 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1192 mList1.foreach(op, threaded, grainSize);
1193 mList0.foreach(op, threaded, grainSize);
1196 template<
typename NodeOp>
1197 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1199 mList0.reduce(op, threaded, grainSize);
1200 mList1.reduce(op, threaded, grainSize);
1204 template<
typename NodeOp>
1205 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1208 mList1.reduce(op, threaded, grainSize);
1209 mList0.reduce(op, threaded, grainSize);
1213 using NodeT2 = RootNodeType;
1214 using NonConstNodeT1 =
typename NodeT2::ChildNodeType;
1216 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1219 using ListT1 = NodeList<NodeT1>;
1220 using ListT0 = NodeList<NodeT0>;
1233 template<
typename TreeOrLeafManagerT>
1234 class NodeManager<TreeOrLeafManagerT, 3>
1237 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1239 static_assert(RootNodeType::LEVEL > 2,
"expected instantiation of template specialization");
1240 static const Index LEVELS = 3;
1242 NodeManager(TreeOrLeafManagerT& tree,
bool serial =
false) : mRoot(tree.root())
1244 this->rebuild(serial);
1247 NodeManager(
const NodeManager&) =
delete;
1250 void clear() { mList0.clear(); mList1.clear(); mList2.clear(); }
1254 void rebuild(
bool serial =
false)
1256 mList2.initRootChildren(mRoot);
1257 mList1.initNodeChildren(mList2, NodeFilter(), serial);
1258 mList0.initNodeChildren(mList1, NodeFilter(), serial);
1262 const RootNodeType& root()
const {
return mRoot; }
1265 Index64 nodeCount()
const {
return mList0.nodeCount()+mList1.nodeCount()+mList2.nodeCount(); }
1271 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount()
1272 : i==2 ? mList2.nodeCount() : 0;
1275 template<
typename NodeOp>
1276 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1278 mList0.foreach(op, threaded, grainSize);
1279 mList1.foreach(op, threaded, grainSize);
1280 mList2.foreach(op, threaded, grainSize);
1284 template<
typename NodeOp>
1285 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1288 mList2.foreach(op, threaded, grainSize);
1289 mList1.foreach(op, threaded, grainSize);
1290 mList0.foreach(op, threaded, grainSize);
1293 template<
typename NodeOp>
1294 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1296 mList0.reduce(op, threaded, grainSize);
1297 mList1.reduce(op, threaded, grainSize);
1298 mList2.reduce(op, threaded, grainSize);
1302 template<
typename NodeOp>
1303 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1306 mList2.reduce(op, threaded, grainSize);
1307 mList1.reduce(op, threaded, grainSize);
1308 mList0.reduce(op, threaded, grainSize);
1312 using NodeT3 = RootNodeType;
1313 using NonConstNodeT2 =
typename NodeT3::ChildNodeType;
1315 using NonConstNodeT1 =
typename NodeT2::ChildNodeType;
1317 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1320 using ListT2 = NodeList<NodeT2>;
1321 using ListT1 = NodeList<NodeT1>;
1322 using ListT0 = NodeList<NodeT0>;
1336 template<
typename TreeOrLeafManagerT>
1337 class NodeManager<TreeOrLeafManagerT, 4>
1340 using NonConstRootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1342 static_assert(RootNodeType::LEVEL > 3,
"expected instantiation of template specialization");
1343 static const Index LEVELS = 4;
1345 NodeManager(TreeOrLeafManagerT& tree,
bool serial =
false) : mRoot(tree.root())
1347 this->rebuild(serial);
1350 NodeManager(
const NodeManager&) =
delete;
1353 void clear() { mList0.clear(); mList1.clear(); mList2.clear(); mList3.clear(); }
1357 void rebuild(
bool serial =
false)
1359 mList3.initRootChildren(mRoot);
1360 mList2.initNodeChildren(mList3, NodeFilter(), serial);
1361 mList1.initNodeChildren(mList2, NodeFilter(), serial);
1362 mList0.initNodeChildren(mList1, NodeFilter(), serial);
1366 const RootNodeType& root()
const {
return mRoot; }
1371 return mList0.nodeCount() + mList1.nodeCount()
1372 + mList2.nodeCount() + mList3.nodeCount();
1379 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() :
1380 i==2 ? mList2.nodeCount() : i==3 ? mList3.nodeCount() : 0;
1383 template<
typename NodeOp>
1384 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1386 mList0.foreach(op, threaded, grainSize);
1387 mList1.foreach(op, threaded, grainSize);
1388 mList2.foreach(op, threaded, grainSize);
1389 mList3.foreach(op, threaded, grainSize);
1393 template<
typename NodeOp>
1394 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1397 mList3.foreach(op, threaded, grainSize);
1398 mList2.foreach(op, threaded, grainSize);
1399 mList1.foreach(op, threaded, grainSize);
1400 mList0.foreach(op, threaded, grainSize);
1403 template<
typename NodeOp>
1404 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1406 mList0.reduce(op, threaded, grainSize);
1407 mList1.reduce(op, threaded, grainSize);
1408 mList2.reduce(op, threaded, grainSize);
1409 mList3.reduce(op, threaded, grainSize);
1413 template<
typename NodeOp>
1414 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1417 mList3.reduce(op, threaded, grainSize);
1418 mList2.reduce(op, threaded, grainSize);
1419 mList1.reduce(op, threaded, grainSize);
1420 mList0.reduce(op, threaded, grainSize);
1424 using NodeT4 = RootNodeType;
1425 using NonConstNodeT3 =
typename NodeT4::ChildNodeType;
1427 using NonConstNodeT2 =
typename NodeT3::ChildNodeType;
1429 using NonConstNodeT1 =
typename NodeT2::ChildNodeType;
1431 using NonConstNodeT0 =
typename NodeT1::ChildNodeType;
1434 using ListT3 = NodeList<NodeT3>;
1435 using ListT2 = NodeList<NodeT2>;
1436 using ListT1 = NodeList<NodeT1>;
1437 using ListT0 = NodeList<NodeT0>;
1452 template<
typename TreeOrLeafManagerT>
1453 class DynamicNodeManager<TreeOrLeafManagerT, 1>
1456 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1457 static_assert(RootNodeType::LEVEL > 0,
"expected instantiation of template specialization");
1458 static const Index LEVELS = 1;
1460 explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1462 DynamicNodeManager(
const DynamicNodeManager&) =
delete;
1465 const RootNodeType& root()
const {
return mRoot; }
1467 template<
typename NodeOp>
1468 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1471 if (!op(mRoot, 0))
return;
1473 if (!mList0.initRootChildren(mRoot))
return;
1474 ForeachFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1475 mList0.foreachWithIndex(nodeOp, threaded, grainSize);
1478 template<
typename NodeOp>
1479 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1482 if (!op(mRoot, 0))
return;
1484 if (!mList0.initRootChildren(mRoot))
return;
1485 ReduceFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1486 mList0.reduceWithIndex(nodeOp, threaded, grainSize);
1490 using NodeT1 = RootNodeType;
1491 using NodeT0 =
typename NodeT1::ChildNodeType;
1493 using ListT0 = NodeList<NodeT0>;
1505 template<
typename TreeOrLeafManagerT>
1506 class DynamicNodeManager<TreeOrLeafManagerT, 2>
1509 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1510 static_assert(RootNodeType::LEVEL > 1,
"expected instantiation of template specialization");
1511 static const Index LEVELS = 2;
1513 explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1515 DynamicNodeManager(
const DynamicNodeManager&) =
delete;
1518 const RootNodeType& root()
const {
return mRoot; }
1520 template<
typename NodeOp>
1521 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1524 if (!op(mRoot, 0))
return;
1526 if (!mList1.initRootChildren(mRoot))
return;
1527 ForeachFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1528 mList1.foreachWithIndex(nodeOp, threaded, grainSize);
1530 if (!mList0.initNodeChildren(mList1, nodeOp, !threaded))
return;
1531 mList0.foreachWithIndex(op, threaded, grainSize);
1534 template<
typename NodeOp>
1535 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1538 if (!op(mRoot, 0))
return;
1540 if (!mList1.initRootChildren(mRoot))
return;
1541 ReduceFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1542 mList1.reduceWithIndex(nodeOp, threaded, grainSize);
1544 if (!mList0.initNodeChildren(mList1, nodeOp, !threaded))
return;
1545 mList0.reduceWithIndex(op, threaded, grainSize);
1549 using NodeT2 = RootNodeType;
1550 using NodeT1 =
typename NodeT2::ChildNodeType;
1551 using NodeT0 =
typename NodeT1::ChildNodeType;
1553 using ListT1 = NodeList<NodeT1>;
1554 using ListT0 = NodeList<NodeT0>;
1567 template<
typename TreeOrLeafManagerT>
1568 class DynamicNodeManager<TreeOrLeafManagerT, 3>
1571 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1572 static_assert(RootNodeType::LEVEL > 2,
"expected instantiation of template specialization");
1573 static const Index LEVELS = 3;
1575 explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1577 DynamicNodeManager(
const DynamicNodeManager&) =
delete;
1580 const RootNodeType& root()
const {
return mRoot; }
1582 template<
typename NodeOp>
1583 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1586 if (!op(mRoot, 0))
return;
1588 if (!mList2.initRootChildren(mRoot))
return;
1589 ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1590 mList2.foreachWithIndex(nodeOp2, threaded, grainSize);
1592 if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded))
return;
1593 ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1594 mList1.foreachWithIndex(nodeOp1, threaded, grainSize);
1596 if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded))
return;
1597 mList0.foreachWithIndex(op, threaded, grainSize);
1600 template<
typename NodeOp>
1601 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1604 if (!op(mRoot, 0))
return;
1606 if (!mList2.initRootChildren(mRoot))
return;
1607 ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1608 mList2.reduceWithIndex(nodeOp2, threaded, grainSize);
1610 if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded))
return;
1611 ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1612 mList1.reduceWithIndex(nodeOp1, threaded, grainSize);
1614 if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded))
return;
1615 mList0.reduceWithIndex(op, threaded, grainSize);
1619 using NodeT3 = RootNodeType;
1620 using NodeT2 =
typename NodeT3::ChildNodeType;
1621 using NodeT1 =
typename NodeT2::ChildNodeType;
1622 using NodeT0 =
typename NodeT1::ChildNodeType;
1624 using ListT2 = NodeList<NodeT2>;
1625 using ListT1 = NodeList<NodeT1>;
1626 using ListT0 = NodeList<NodeT0>;
1640 template<
typename TreeOrLeafManagerT>
1641 class DynamicNodeManager<TreeOrLeafManagerT, 4>
1644 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
1645 static_assert(RootNodeType::LEVEL > 3,
"expected instantiation of template specialization");
1646 static const Index LEVELS = 4;
1648 explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1650 DynamicNodeManager(
const DynamicNodeManager&) =
delete;
1653 const RootNodeType& root()
const {
return mRoot; }
1655 template<
typename NodeOp>
1656 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1659 if (!op(mRoot, 0))
return;
1661 if (!mList3.initRootChildren(mRoot))
return;
1662 ForeachFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1663 mList3.foreachWithIndex(nodeOp3, threaded, grainSize);
1665 if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded))
return;
1666 ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1667 mList2.foreachWithIndex(nodeOp2, threaded, grainSize);
1669 if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded))
return;
1670 ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1671 mList1.foreachWithIndex(nodeOp1, threaded, grainSize);
1673 if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded))
return;
1674 mList0.foreachWithIndex(op, threaded, grainSize);
1677 template<
typename NodeOp>
1678 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
1681 if (!op(mRoot, 0))
return;
1683 if (!mList3.initRootChildren(mRoot))
return;
1684 ReduceFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1685 mList3.reduceWithIndex(nodeOp3, threaded, grainSize);
1687 if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded))
return;
1688 ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1689 mList2.reduceWithIndex(nodeOp2, threaded, grainSize);
1691 if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded))
return;
1692 ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1693 mList1.reduceWithIndex(nodeOp1, threaded, grainSize);
1695 if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded))
return;
1696 mList0.reduceWithIndex(op, threaded, grainSize);
1700 using NodeT4 = RootNodeType;
1701 using NodeT3 =
typename NodeT4::ChildNodeType;
1702 using NodeT2 =
typename NodeT3::ChildNodeType;
1703 using NodeT1 =
typename NodeT2::ChildNodeType;
1704 using NodeT0 =
typename NodeT1::ChildNodeType;
1706 using ListT3 = NodeList<NodeT3>;
1707 using ListT2 = NodeList<NodeT2>;
1708 using ListT1 = NodeList<NodeT1>;
1709 using ListT0 = NodeList<NodeT0>;
1723 #endif // OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED