14 #ifndef OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
15 #define OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
18 #include <tbb/parallel_for.h>
19 #include <tbb/parallel_reduce.h>
30 template<
typename TreeOrLeafManagerT, Index LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
40 template<
typename NodeT>
45 using ListT = std::deque<value_type>;
49 void push_back(NodeT* node) { mList.push_back(node); }
51 NodeT&
operator()(
size_t n)
const { assert(n<mList.size());
return *(mList[n]); }
53 NodeT*&
operator[](
size_t n) { assert(n<mList.size());
return mList[n]; }
59 void resize(
size_t n) { mList.resize(n); }
66 mEnd(end), mBegin(begin), mGrainSize(grainSize), mNodeList(nodeList) {}
69 mEnd(r.mEnd), mBegin(doSplit(r)), mGrainSize(r.mGrainSize),
70 mNodeList(r.mNodeList) {}
72 size_t size()
const {
return mEnd - mBegin; }
78 bool empty()
const {
return !(mBegin < mEnd);}
87 assert(this->isValid());
94 NodeT&
operator*()
const {
return mRange.mNodeList(mPos); }
98 size_t pos()
const {
return mPos; }
99 bool isValid()
const {
return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
101 bool test()
const {
return mPos < mRange.mEnd; }
103 operator bool()
const {
return this->test(); }
105 bool empty()
const {
return !this->test(); }
108 return (mPos != other.mPos) || (&mRange != &other.mRange);
123 size_t mEnd, mBegin, mGrainSize;
129 size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
138 return NodeRange(0, this->nodeCount(), *
this, grainsize);
141 template<
typename NodeOp>
142 void foreach(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
144 NodeTransformer<NodeOp> transform(op);
145 transform.run(this->nodeRange(grainSize), threaded);
148 template<
typename NodeOp>
149 void reduce(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
151 NodeReducer<NodeOp> transform(op);
152 transform.run(this->nodeRange(grainSize), threaded);
158 template<
typename NodeOp>
159 struct NodeTransformer
161 NodeTransformer(
const NodeOp& nodeOp) : mNodeOp(nodeOp)
164 void run(
const NodeRange& range,
bool threaded =
true)
166 threaded ? tbb::parallel_for(range, *
this) : (*this)(range);
168 void operator()(
const NodeRange& range)
const
170 for (
typename NodeRange::Iterator it = range.begin(); it; ++it) mNodeOp(*it);
172 const NodeOp mNodeOp;
176 template<
typename NodeOp>
179 NodeReducer(NodeOp& nodeOp) : mNodeOp(&nodeOp), mOwnsOp(false)
182 NodeReducer(
const NodeReducer& other, tbb::split) :
183 mNodeOp(new NodeOp(*(other.mNodeOp),
tbb::split())), mOwnsOp(true)
186 ~NodeReducer() {
if (mOwnsOp)
delete mNodeOp; }
187 void run(
const NodeRange& range,
bool threaded =
true)
189 threaded ? tbb::parallel_reduce(range, *
this) : (*this)(range);
191 void operator()(
const NodeRange& range)
193 NodeOp &op = *mNodeOp;
194 for (
typename NodeRange::Iterator it = range.begin(); it; ++it) op(*it);
196 void join(
const NodeReducer& other)
198 mNodeOp->join(*(other.mNodeOp));
217 template<
typename NodeT, Index LEVEL>
225 void clear() { mList.clear(); mNext.clear(); }
227 template<
typename ParentT,
typename TreeOrLeafManagerT>
228 void init(ParentT& parent, TreeOrLeafManagerT& tree)
230 parent.getNodes(mList);
231 for (
size_t i=0, n=mList.nodeCount(); i<n; ++i) mNext.init(mList(i), tree);
234 template<
typename ParentT>
238 parent.getNodes(mList);
239 for (
size_t i=0, n=mList.nodeCount(); i<n; ++i) mNext.rebuild(mList(i));
246 return i==NodeT::LEVEL ? mList.nodeCount() : mNext.nodeCount(i);
249 template<
typename NodeOp>
252 mNext.foreachBottomUp(op, threaded, grainSize);
253 mList.foreach(op, threaded, grainSize);
256 template<
typename NodeOp>
259 mList.foreach(op, threaded, grainSize);
260 mNext.foreachTopDown(op, threaded, grainSize);
263 template<
typename NodeOp>
266 mNext.reduceBottomUp(op, threaded, grainSize);
267 mList.reduce(op, threaded, grainSize);
270 template<
typename NodeOp>
273 mList.reduce(op, threaded, grainSize);
274 mNext.reduceTopDown(op, threaded, grainSize);
289 template<
typename NodeT>
295 virtual ~NodeManagerLink() {}
298 void clear() { mList.
clear(); }
300 template<
typename ParentT>
301 void rebuild(ParentT& parent) { mList.clear(); parent.getNodes(mList); }
303 Index64 nodeCount()
const {
return mList.nodeCount(); }
305 Index64 nodeCount(
Index)
const {
return mList.nodeCount(); }
307 template<
typename NodeOp>
308 void foreachBottomUp(
const NodeOp& op,
bool threaded,
size_t grainSize)
310 mList.foreach(op, threaded, grainSize);
313 template<
typename NodeOp>
314 void foreachTopDown(
const NodeOp& op,
bool threaded,
size_t grainSize)
316 mList.foreach(op, threaded, grainSize);
319 template<
typename NodeOp>
320 void reduceBottomUp(NodeOp& op,
bool threaded,
size_t grainSize)
322 mList.reduce(op, threaded, grainSize);
325 template<
typename NodeOp>
326 void reduceTopDown(NodeOp& op,
bool threaded,
size_t grainSize)
328 mList.reduce(op, threaded, grainSize);
331 template<
typename ParentT,
typename TreeOrLeafManagerT>
332 void init(ParentT& parent, TreeOrLeafManagerT& tree)
335 if (TreeOrLeafManagerT::DEPTH == 2 && NodeT::LEVEL == 0) {
336 tree.getNodes(mList);
338 parent.getNodes(mList);
343 NodeList<NodeT> mList;
355 template<
typename TreeOrLeafManagerT, Index _LEVELS>
359 static const Index LEVELS = _LEVELS;
360 static_assert(LEVELS > 0,
361 "expected instantiation of template specialization");
363 static_assert(RootNodeType::LEVEL >= LEVELS,
"number of levels exceeds root node height");
365 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { mChain.init(mRoot, tree); }
387 template<
typename NodeOp>
445 mChain.foreachBottomUp(op, threaded, grainSize);
449 template<
typename NodeOp>
453 mChain.foreachTopDown(op, threaded, grainSize);
459 template<
typename NodeOp>
519 mChain.reduceBottomUp(op, threaded, grainSize);
523 template<
typename NodeOp>
527 mChain.reduceTopDown(op, threaded, grainSize);
545 template<
typename TreeOrLeafManagerT>
546 class NodeManager<TreeOrLeafManagerT, 0>
549 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
550 static const Index LEVELS = 0;
552 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) {}
554 virtual ~NodeManager() {}
564 const RootNodeType& root()
const {
return mRoot; }
567 Index64 nodeCount()
const {
return 0; }
571 template<
typename NodeOp>
572 void foreachBottomUp(
const NodeOp& op,
bool,
size_t) { op(mRoot); }
574 template<
typename NodeOp>
575 void foreachTopDown(
const NodeOp& op,
bool,
size_t) { op(mRoot); }
577 template<
typename NodeOp>
578 void reduceBottomUp(NodeOp& op,
bool,
size_t) { op(mRoot); }
580 template<
typename NodeOp>
581 void reduceTopDown(NodeOp& op,
bool,
size_t) { op(mRoot); }
587 NodeManager(
const NodeManager&) {}
596 template<
typename TreeOrLeafManagerT>
597 class NodeManager<TreeOrLeafManagerT, 1>
600 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
601 static_assert(RootNodeType::LEVEL > 0,
"expected instantiation of template specialization");
602 static const Index LEVELS = 1;
604 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
607 if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
608 tree.getNodes(mList0);
610 mRoot.getNodes(mList0);
615 virtual ~NodeManager() {}
618 void clear() { mList0.clear(); }
622 void rebuild() { mList0.clear(); mRoot.getNodes(mList0); }
625 const RootNodeType& root()
const {
return mRoot; }
628 Index64 nodeCount()
const {
return mList0.nodeCount(); }
632 Index64 nodeCount(
Index i)
const {
return i==0 ? mList0.nodeCount() : 0; }
634 template<
typename NodeOp>
635 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
637 mList0.foreach(op, threaded, grainSize);
641 template<
typename NodeOp>
642 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
645 mList0.foreach(op, threaded, grainSize);
648 template<
typename NodeOp>
649 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
651 mList0.reduce(op, threaded, grainSize);
655 template<
typename NodeOp>
656 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
659 mList0.reduce(op, threaded, grainSize);
663 using NodeT1 = RootNodeType;
664 using NodeT0 =
typename NodeT1::ChildNodeType;
665 using ListT0 = NodeList<NodeT0>;
671 NodeManager(
const NodeManager&) {}
680 template<
typename TreeOrLeafManagerT>
681 class NodeManager<TreeOrLeafManagerT, 2>
684 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
685 static_assert(RootNodeType::LEVEL > 1,
"expected instantiation of template specialization");
686 static const Index LEVELS = 2;
688 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
690 mRoot.getNodes(mList1);
693 if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
694 tree.getNodes(mList0);
696 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
701 virtual ~NodeManager() {}
704 void clear() { mList0.clear(); mList1.clear(); }
711 mRoot.getNodes(mList1);
712 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
716 const RootNodeType& root()
const {
return mRoot; }
719 Index64 nodeCount()
const {
return mList0.nodeCount() + mList1.nodeCount(); }
725 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() : 0;
728 template<
typename NodeOp>
729 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
731 mList0.foreach(op, threaded, grainSize);
732 mList1.foreach(op, threaded, grainSize);
736 template<
typename NodeOp>
737 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
740 mList1.foreach(op, threaded, grainSize);
741 mList0.foreach(op, threaded, grainSize);
744 template<
typename NodeOp>
745 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
747 mList0.reduce(op, threaded, grainSize);
748 mList1.reduce(op, threaded, grainSize);
752 template<
typename NodeOp>
753 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
756 mList1.reduce(op, threaded, grainSize);
757 mList0.reduce(op, threaded, grainSize);
761 using NodeT2 = RootNodeType;
762 using NodeT1 =
typename NodeT2::ChildNodeType;
763 using NodeT0 =
typename NodeT1::ChildNodeType;
765 using ListT1 = NodeList<NodeT1>;
766 using ListT0 = NodeList<NodeT0>;
773 NodeManager(
const NodeManager&) {}
782 template<
typename TreeOrLeafManagerT>
783 class NodeManager<TreeOrLeafManagerT, 3>
786 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
787 static_assert(RootNodeType::LEVEL > 2,
"expected instantiation of template specialization");
788 static const Index LEVELS = 3;
790 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
792 mRoot.getNodes(mList2);
793 for (
size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
796 if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
797 tree.getNodes(mList0);
799 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
804 virtual ~NodeManager() {}
807 void clear() { mList0.clear(); mList1.clear(); mList2.clear(); }
814 mRoot.getNodes(mList2);
815 for (
size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
816 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
820 const RootNodeType& root()
const {
return mRoot; }
823 Index64 nodeCount()
const {
return mList0.nodeCount()+mList1.nodeCount()+mList2.nodeCount(); }
829 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount()
830 : i==2 ? mList2.nodeCount() : 0;
833 template<
typename NodeOp>
834 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
836 mList0.foreach(op, threaded, grainSize);
837 mList1.foreach(op, threaded, grainSize);
838 mList2.foreach(op, threaded, grainSize);
842 template<
typename NodeOp>
843 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
846 mList2.foreach(op, threaded, grainSize);
847 mList1.foreach(op, threaded, grainSize);
848 mList0.foreach(op, threaded, grainSize);
851 template<
typename NodeOp>
852 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
854 mList0.reduce(op, threaded, grainSize);
855 mList1.reduce(op, threaded, grainSize);
856 mList2.reduce(op, threaded, grainSize);
860 template<
typename NodeOp>
861 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
864 mList2.reduce(op, threaded, grainSize);
865 mList1.reduce(op, threaded, grainSize);
866 mList0.reduce(op, threaded, grainSize);
870 using NodeT3 = RootNodeType;
871 using NodeT2 =
typename NodeT3::ChildNodeType;
872 using NodeT1 =
typename NodeT2::ChildNodeType;
873 using NodeT0 =
typename NodeT1::ChildNodeType;
875 using ListT2 = NodeList<NodeT2>;
876 using ListT1 = NodeList<NodeT1>;
877 using ListT0 = NodeList<NodeT0>;
885 NodeManager(
const NodeManager&) {}
894 template<
typename TreeOrLeafManagerT>
895 class NodeManager<TreeOrLeafManagerT, 4>
898 using RootNodeType =
typename TreeOrLeafManagerT::RootNodeType;
899 static_assert(RootNodeType::LEVEL > 3,
"expected instantiation of template specialization");
900 static const Index LEVELS = 4;
902 NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
904 mRoot.getNodes(mList3);
905 for (
size_t i=0, n=mList3.nodeCount(); i<n; ++i) mList3(i).getNodes(mList2);
906 for (
size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
909 if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
910 tree.getNodes(mList0);
912 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
917 virtual ~NodeManager() {}
920 void clear() { mList0.clear(); mList1.clear(); mList2.clear(); mList3.clear; }
927 mRoot.getNodes(mList3);
928 for (
size_t i=0, n=mList3.nodeCount(); i<n; ++i) mList3(i).getNodes(mList2);
929 for (
size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
930 for (
size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
934 const RootNodeType& root()
const {
return mRoot; }
939 return mList0.nodeCount() + mList1.nodeCount()
940 + mList2.nodeCount() + mList3.nodeCount();
947 return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() :
948 i==2 ? mList2.nodeCount() : i==3 ? mList3.nodeCount() : 0;
951 template<
typename NodeOp>
952 void foreachBottomUp(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
954 mList0.foreach(op, threaded, grainSize);
955 mList1.foreach(op, threaded, grainSize);
956 mList2.foreach(op, threaded, grainSize);
957 mList3.foreach(op, threaded, grainSize);
961 template<
typename NodeOp>
962 void foreachTopDown(
const NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
965 mList3.foreach(op, threaded, grainSize);
966 mList2.foreach(op, threaded, grainSize);
967 mList1.foreach(op, threaded, grainSize);
968 mList0.foreach(op, threaded, grainSize);
971 template<
typename NodeOp>
972 void reduceBottomUp(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
974 mList0.reduce(op, threaded, grainSize);
975 mList1.reduce(op, threaded, grainSize);
976 mList2.reduce(op, threaded, grainSize);
977 mList3.reduce(op, threaded, grainSize);
981 template<
typename NodeOp>
982 void reduceTopDown(NodeOp& op,
bool threaded =
true,
size_t grainSize=1)
985 mList3.reduce(op, threaded, grainSize);
986 mList2.reduce(op, threaded, grainSize);
987 mList1.reduce(op, threaded, grainSize);
988 mList0.reduce(op, threaded, grainSize);
992 using NodeT4 = RootNodeType;
993 using NodeT3 =
typename NodeT4::ChildNodeType;
994 using NodeT2 =
typename NodeT3::ChildNodeType;
995 using NodeT1 =
typename NodeT2::ChildNodeType;
996 using NodeT0 =
typename NodeT1::ChildNodeType;
998 using ListT3 = NodeList<NodeT3>;
999 using ListT2 = NodeList<NodeT2>;
1000 using ListT1 = NodeList<NodeT1>;
1001 using ListT0 = NodeList<NodeT0>;
1010 NodeManager(
const NodeManager&) {}
1017 #endif // OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED