OpenVDB  8.0.1
NodeManager.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
12 
13 #ifndef OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
14 #define OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
15 
16 #include <openvdb/Types.h>
17 #include <tbb/parallel_for.h>
18 #include <tbb/parallel_reduce.h>
19 #include <deque>
20 
21 
22 namespace openvdb {
24 namespace OPENVDB_VERSION_NAME {
25 namespace tree {
26 
27 // Produce linear arrays of all tree nodes, to facilitate efficient threading
28 // and bottom-up processing.
29 template<typename TreeOrLeafManagerT, Index LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
30 class NodeManager;
31 
32 
33 // Produce linear arrays of all tree nodes lazily, to facilitate efficient threading
34 // of topology-changing top-down workflows.
35 template<typename TreeOrLeafManagerT, Index _LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
36 class DynamicNodeManager;
37 
38 
40 
41 
42 // This is a dummy node filtering class used by the NodeManager class to match
43 // the internal filtering interface used by the DynamicNodeManager.
44 struct NodeFilter
45 {
46  static bool valid(size_t) { return true; }
47 }; // struct NodeFilter
48 
49 
53 template<typename NodeT>
54 class NodeList
55 {
56 public:
57  NodeList() = default;
58 
59  NodeT& operator()(size_t n) const { assert(n<mNodeCount); return *(mNodes[n]); }
60 
61  NodeT*& operator[](size_t n) { assert(n<mNodeCount); return mNodes[n]; }
62 
63  Index64 nodeCount() const { return mNodeCount; }
64 
65  void clear()
66  {
67  mNodePtrs.reset();
68  mNodes = nullptr;
69  mNodeCount = 0;
70  }
71 
72  // initialize this node list from the provided root node
73  template <typename RootT>
74  bool initRootChildren(RootT& root)
75  {
76  // Allocate (or deallocate) the node pointer array
77 
78  size_t nodeCount = root.childCount();
79 
80  if (nodeCount != mNodeCount) {
81  if (nodeCount > 0) {
82  mNodePtrs.reset(new NodeT*[nodeCount]);
83  mNodes = mNodePtrs.get();
84  } else {
85  mNodePtrs.reset();
86  mNodes = nullptr;
87  }
88  mNodeCount = nodeCount;
89  }
90 
91  if (mNodeCount == 0) return false;
92 
93  // Populate the node pointers
94 
95  NodeT** nodePtr = mNodes;
96  for (auto iter = root.beginChildOn(); iter; ++iter) {
97  *nodePtr++ = &iter.getValue();
98  }
99 
100  return true;
101  }
102 
103  // initialize this node list from another node list containing the parent nodes
104  template <typename ParentsT, typename NodeFilterT>
105  bool initNodeChildren(ParentsT& parents, const NodeFilterT& nodeFilter = NodeFilterT(), bool serial = false)
106  {
107  // Compute the node counts for each node
108 
109  std::vector<Index32> nodeCounts;
110  if (serial) {
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());
115  }
116  } else {
117  nodeCounts.resize(parents.nodeCount());
118  tbb::parallel_for(
119  // with typical node sizes and SSE enabled, there are only a handful
120  // of instructions executed per-operation with a default grainsize
121  // of 1, so increase to 64 to reduce parallel scheduling overhead
122  tbb::blocked_range<Index64>(0, parents.nodeCount(), /*grainsize=*/64),
123  [&](tbb::blocked_range<Index64>& range)
124  {
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();
128  }
129  }
130  );
131  }
132 
133  // Turn node counts into a cumulative histogram and obtain total node count
134 
135  for (size_t i = 1; i < nodeCounts.size(); i++) {
136  nodeCounts[i] += nodeCounts[i-1];
137  }
138 
139  const size_t nodeCount = nodeCounts.empty() ? 0 : nodeCounts.back();
140 
141  // Allocate (or deallocate) the node pointer array
142 
143  if (nodeCount != mNodeCount) {
144  if (nodeCount > 0) {
145  mNodePtrs.reset(new NodeT*[nodeCount]);
146  mNodes = mNodePtrs.get();
147  } else {
148  mNodePtrs.reset();
149  mNodes = nullptr;
150  }
151  mNodeCount = nodeCount;
152  }
153 
154  if (mNodeCount == 0) return false;
155 
156  // Populate the node pointers
157 
158  if (serial) {
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();
164  }
165  }
166  } else {
167  tbb::parallel_for(
168  tbb::blocked_range<Index64>(0, parents.nodeCount()),
169  [&](tbb::blocked_range<Index64>& range)
170  {
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();
178  }
179  }
180  }
181  );
182  }
183 
184  return true;
185  }
186 
187  class NodeRange
188  {
189  public:
190 
191  NodeRange(size_t begin, size_t end, const NodeList& nodeList, size_t grainSize=1):
192  mEnd(end), mBegin(begin), mGrainSize(grainSize), mNodeList(nodeList) {}
193 
194  NodeRange(NodeRange& r, tbb::split):
195  mEnd(r.mEnd), mBegin(doSplit(r)), mGrainSize(r.mGrainSize),
196  mNodeList(r.mNodeList) {}
197 
198  size_t size() const { return mEnd - mBegin; }
199 
200  size_t grainsize() const { return mGrainSize; }
201 
202  const NodeList& nodeList() const { return mNodeList; }
203 
204  bool empty() const {return !(mBegin < mEnd);}
205 
206  bool is_divisible() const {return mGrainSize < this->size();}
207 
208  class Iterator
209  {
210  public:
211  Iterator(const NodeRange& range, size_t pos): mRange(range), mPos(pos)
212  {
213  assert(this->isValid());
214  }
215  Iterator(const Iterator&) = default;
216  Iterator& operator=(const Iterator&) = default;
218  Iterator& operator++() { ++mPos; return *this; }
220  NodeT& operator*() const { return mRange.mNodeList(mPos); }
222  NodeT* operator->() const { return &(this->operator*()); }
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(); }
232  bool operator!=(const Iterator& other) const
233  {
234  return (mPos != other.mPos) || (&mRange != &other.mRange);
235  }
236  bool operator==(const Iterator& other) const { return !(*this != other); }
237  const NodeRange& nodeRange() const { return mRange; }
238 
239  private:
240  const NodeRange& mRange;
241  size_t mPos;
242  };// NodeList::NodeRange::Iterator
243 
244  Iterator begin() const {return Iterator(*this, mBegin);}
245 
246  Iterator end() const {return Iterator(*this, mEnd);}
247 
248  private:
249  size_t mEnd, mBegin, mGrainSize;
250  const NodeList& mNodeList;
251 
252  static size_t doSplit(NodeRange& r)
253  {
254  assert(r.is_divisible());
255  size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
256  r.mEnd = middle;
257  return middle;
258  }
259  };// NodeList::NodeRange
260 
262  NodeRange nodeRange(size_t grainsize = 1) const
263  {
264  return NodeRange(0, this->nodeCount(), *this, grainsize);
265  }
266 
267  template<typename NodeOp>
268  void foreach(const NodeOp& op, bool threaded = true, size_t grainSize=1)
269  {
270  NodeTransformer<NodeOp> transform(op);
271  transform.run(this->nodeRange(grainSize), threaded);
272  }
273 
274  template<typename NodeOp>
275  void reduce(NodeOp& op, bool threaded = true, size_t grainSize=1)
276  {
277  NodeReducer<NodeOp> transform(op);
278  transform.run(this->nodeRange(grainSize), threaded);
279  }
280 
281  // identical to foreach except the operator() method has a node index
282  template<typename NodeOp>
283  void foreachWithIndex(const NodeOp& op, bool threaded = true, size_t grainSize=1)
284  {
285  NodeTransformer<NodeOp, OpWithIndex> transform(op);
286  transform.run(this->nodeRange(grainSize), threaded);
287  }
288 
289  // identical to reduce except the operator() method has a node index
290  template<typename NodeOp>
291  void reduceWithIndex(NodeOp& op, bool threaded = true, size_t grainSize=1)
292  {
293  NodeReducer<NodeOp, OpWithIndex> transform(op);
294  transform.run(this->nodeRange(grainSize), threaded);
295  }
296 
297 private:
298 
299  // default execution in the NodeManager ignores the node index
300  // given by the iterator position
301  struct OpWithoutIndex
302  {
303  template <typename T>
304  static void eval(T& node, typename NodeRange::Iterator& iter) { node(*iter); }
305  };
306 
307  // execution in the DynamicNodeManager matches that of the LeafManager in
308  // passing through the node index given by the iterator position
309  struct OpWithIndex
310  {
311  template <typename T>
312  static void eval(T& node, typename NodeRange::Iterator& iter) { node(*iter, iter.pos()); }
313  };
314 
315  // Private struct of NodeList that performs parallel_for
316  template<typename NodeOp, typename OpT = OpWithoutIndex>
317  struct NodeTransformer
318  {
319  NodeTransformer(const NodeOp& nodeOp) : mNodeOp(nodeOp)
320  {
321  }
322  void run(const NodeRange& range, bool threaded = true)
323  {
324  threaded ? tbb::parallel_for(range, *this) : (*this)(range);
325  }
326  void operator()(const NodeRange& range) const
327  {
328  for (typename NodeRange::Iterator it = range.begin(); it; ++it) {
329  OpT::template eval(mNodeOp, it);
330  }
331  }
332  const NodeOp mNodeOp;
333  };// NodeList::NodeTransformer
334 
335  // Private struct of NodeList that performs parallel_reduce
336  template<typename NodeOp, typename OpT = OpWithoutIndex>
337  struct NodeReducer
338  {
339  NodeReducer(NodeOp& nodeOp) : mNodeOp(&nodeOp)
340  {
341  }
342  NodeReducer(const NodeReducer& other, tbb::split)
343  : mNodeOpPtr(std::make_unique<NodeOp>(*(other.mNodeOp), tbb::split()))
344  , mNodeOp(mNodeOpPtr.get())
345  {
346  }
347  void run(const NodeRange& range, bool threaded = true)
348  {
349  threaded ? tbb::parallel_reduce(range, *this) : (*this)(range);
350  }
351  void operator()(const NodeRange& range)
352  {
353  for (typename NodeRange::Iterator it = range.begin(); it; ++it) {
354  OpT::template eval(*mNodeOp, it);
355  }
356  }
357  void join(const NodeReducer& other)
358  {
359  mNodeOp->join(*(other.mNodeOp));
360  }
361  std::unique_ptr<NodeOp> mNodeOpPtr;
362  NodeOp *mNodeOp = nullptr;
363  };// NodeList::NodeReducer
364 
365 
366 protected:
367  size_t mNodeCount = 0;
368  std::unique_ptr<NodeT*[]> mNodePtrs;
369  NodeT** mNodes = nullptr;
370 };// NodeList
371 
372 
374 
375 
380 template<typename NodeT, Index LEVEL>
382 {
383 public:
384  using NonConstChildNodeType = typename NodeT::ChildNodeType;
386 
387  NodeManagerLink() = default;
388 
389  void clear() { mList.clear(); mNext.clear(); }
390 
391  template <typename RootT>
392  void initRootChildren(RootT& root, bool serial = false)
393  {
394  mList.initRootChildren(root);
395  mNext.initNodeChildren(mList, serial);
396  }
397 
398  template<typename ParentsT>
399  void initNodeChildren(ParentsT& parents, bool serial = false)
400  {
401  mList.initNodeChildren(parents, NodeFilter(), serial);
402  mNext.initNodeChildren(mList, serial);
403  }
404 
405  Index64 nodeCount() const { return mList.nodeCount() + mNext.nodeCount(); }
406 
408  {
409  return i==NodeT::LEVEL ? mList.nodeCount() : mNext.nodeCount(i);
410  }
411 
412  template<typename NodeOp>
413  void foreachBottomUp(const NodeOp& op, bool threaded, size_t grainSize)
414  {
415  mNext.foreachBottomUp(op, threaded, grainSize);
416  mList.foreach(op, threaded, grainSize);
417  }
418 
419  template<typename NodeOp>
420  void foreachTopDown(const NodeOp& op, bool threaded, size_t grainSize)
421  {
422  mList.foreach(op, threaded, grainSize);
423  mNext.foreachTopDown(op, threaded, grainSize);
424  }
425 
426  template<typename NodeOp>
427  void reduceBottomUp(NodeOp& op, bool threaded, size_t grainSize)
428  {
429  mNext.reduceBottomUp(op, threaded, grainSize);
430  mList.reduce(op, threaded, grainSize);
431  }
432 
433  template<typename NodeOp>
434  void reduceTopDown(NodeOp& op, bool threaded, size_t grainSize)
435  {
436  mList.reduce(op, threaded, grainSize);
437  mNext.reduceTopDown(op, threaded, grainSize);
438  }
439 
440 protected:
443 };// NodeManagerLink class
444 
445 
447 
448 
452 template<typename NodeT>
453 class NodeManagerLink<NodeT, 0>
454 {
455 public:
456  NodeManagerLink() = default;
457 
459  void clear() { mList.clear(); }
460 
461  template <typename RootT>
462  void initRootChildren(RootT& root, bool /*serial*/ = false) { mList.initRootChildren(root); }
463 
464  template<typename ParentsT>
465  void initNodeChildren(ParentsT& parents, bool serial = false) { mList.initNodeChildren(parents, NodeFilter(), serial); }
466 
467  Index64 nodeCount() const { return mList.nodeCount(); }
468 
469  Index64 nodeCount(Index) const { return mList.nodeCount(); }
470 
471  template<typename NodeOp>
472  void foreachBottomUp(const NodeOp& op, bool threaded, size_t grainSize)
473  {
474  mList.foreach(op, threaded, grainSize);
475  }
476 
477  template<typename NodeOp>
478  void foreachTopDown(const NodeOp& op, bool threaded, size_t grainSize)
479  {
480  mList.foreach(op, threaded, grainSize);
481  }
482 
483  template<typename NodeOp>
484  void reduceBottomUp(NodeOp& op, bool threaded, size_t grainSize)
485  {
486  mList.reduce(op, threaded, grainSize);
487  }
488 
489  template<typename NodeOp>
490  void reduceTopDown(NodeOp& op, bool threaded, size_t grainSize)
491  {
492  mList.reduce(op, threaded, grainSize);
493  }
494 
495 protected:
496  NodeList<NodeT> mList;
497 };// NodeManagerLink class
498 
499 
501 
502 
508 template<typename TreeOrLeafManagerT, Index _LEVELS>
510 {
511 public:
512  static const Index LEVELS = _LEVELS;
513  static_assert(LEVELS > 0,
514  "expected instantiation of template specialization"); // see specialization below
515  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
517  using NonConstChildNodeType = typename RootNodeType::ChildNodeType;
519  static_assert(RootNodeType::LEVEL >= LEVELS, "number of levels exceeds root node height");
520 
521  NodeManager(TreeOrLeafManagerT& tree, bool serial = false)
522  : mRoot(tree.root())
523  {
524  this->rebuild(serial);
525  }
526 
527  NodeManager(const NodeManager&) = delete;
528 
530  void clear() { mChain.clear(); }
531 
534  void rebuild(bool serial = false) { mChain.initRootChildren(mRoot, serial); }
535 
537  const RootNodeType& root() const { return mRoot; }
538 
540  Index64 nodeCount() const { return mChain.nodeCount(); }
541 
544  Index64 nodeCount(Index i) const { return mChain.nodeCount(i); }
545 
547  template<typename NodeOp>
603  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
604  {
605  mChain.foreachBottomUp(op, threaded, grainSize);
606  op(mRoot);
607  }
608 
609  template<typename NodeOp>
610  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
611  {
612  op(mRoot);
613  mChain.foreachTopDown(op, threaded, grainSize);
614  }
615 
617 
619  template<typename NodeOp>
677  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
678  {
679  mChain.reduceBottomUp(op, threaded, grainSize);
680  op(mRoot);
681  }
682 
683  template<typename NodeOp>
684  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
685  {
686  op(mRoot);
687  mChain.reduceTopDown(op, threaded, grainSize);
688  }
690 
691 protected:
694 };// NodeManager class
695 
696 
698 
699 
700 // Wraps a user-supplied DynamicNodeManager operator and stores the return
701 // value of the operator() method to the index of the node in a bool array
702 template <typename OpT>
704 {
705  explicit ForeachFilterOp(const OpT& op, openvdb::Index64 size)
706  : mOp(op)
707  , mValidPtr(std::make_unique<bool[]>(size))
708  , mValid(mValidPtr.get()) { }
709 
711  : mOp(other.mOp)
712  , mValid(other.mValid) { }
713 
714  template<typename NodeT>
715  void operator()(NodeT& node, size_t idx) const
716  {
717  mValid[idx] = mOp(node, idx);
718  }
719 
720  bool valid(size_t idx) const { return mValid[idx]; }
721 
722  const OpT& op() const { return mOp; }
723 
724 private:
725  const OpT& mOp;
726  std::unique_ptr<bool[]> mValidPtr;
727  bool* mValid = nullptr;
728 }; // struct ForeachFilterOp
729 
730 
731 // Wraps a user-supplied DynamicNodeManager operator and stores the return
732 // value of the operator() method to the index of the node in a bool array
733 template <typename OpT>
735 {
737  : mOp(&op)
738  , mValidPtr(std::make_unique<bool[]>(size))
739  , mValid(mValidPtr.get()) { }
740 
742  : mOp(other.mOp)
743  , mValid(other.mValid) { }
744 
745  ReduceFilterOp(const ReduceFilterOp& other, tbb::split)
746  : mOpPtr(std::make_unique<OpT>(*(other.mOp), tbb::split()))
747  , mOp(mOpPtr.get())
748  , mValid(other.mValid) { }
749 
750  template<typename NodeT>
751  void operator()(NodeT& node, size_t idx) const
752  {
753  mValid[idx] = (*mOp)(node, idx);
754  }
755 
756  void join(const ReduceFilterOp& other)
757  {
758  mOp->join(*(other.mOp));
759  }
760 
761  bool valid(size_t idx) const
762  {
763  return mValid[idx];
764  }
765 
766  OpT& op() { return *mOp; }
767 
768 private:
769  std::unique_ptr<OpT> mOpPtr;
770  OpT* mOp = nullptr;
771  std::unique_ptr<bool[]> mValidPtr;
772  bool* mValid = nullptr;
773 }; // struct ReduceFilterOp
774 
775 
780 template<typename NodeT, Index LEVEL>
782 {
783 public:
785 
786  template<typename NodeOpT, typename RootT>
787  void foreachTopDown(const NodeOpT& op, RootT& root, bool threaded, size_t grainSize)
788  {
789  if (!op(root, /*index=*/0)) return;
790  if (!mList.initRootChildren(root)) return;
791  ForeachFilterOp<NodeOpT> filterOp(op, mList.nodeCount());
792  mList.foreachWithIndex(filterOp, threaded, grainSize);
793  mNext.foreachTopDownRecurse(filterOp, mList, threaded, grainSize);
794  }
795 
796  template<typename FilterOpT, typename ParentT>
797  void foreachTopDownRecurse(const FilterOpT& filterOp, ParentT& parent, bool threaded, size_t grainSize)
798  {
799  if (!mList.initNodeChildren(parent, filterOp, !threaded)) return;
800  FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
801  mList.foreachWithIndex(childFilterOp, threaded, grainSize);
802  }
803 
804  template<typename NodeOpT, typename RootT>
805  void reduceTopDown(NodeOpT& op, RootT& root, bool threaded, size_t grainSize)
806  {
807  if (!op(root, /*index=*/0)) return;
808  if (!mList.initRootChildren(root)) return;
809  ReduceFilterOp<NodeOpT> filterOp(op, mList.nodeCount());
810  mList.reduceWithIndex(filterOp, threaded, grainSize);
811  mNext.reduceTopDownRecurse(filterOp, mList, threaded, grainSize);
812  }
813 
814  template<typename FilterOpT, typename ParentT>
815  void reduceTopDownRecurse(FilterOpT& filterOp, ParentT& parent, bool threaded, size_t grainSize)
816  {
817  if (!mList.initNodeChildren(parent, filterOp, !threaded)) return;
818  FilterOpT childFilterOp(filterOp.op(), mList.nodeCount());
819  mList.reduceWithIndex(childFilterOp, threaded, grainSize);
820  }
821 
822 protected:
824  DynamicNodeManagerLink<typename NodeT::ChildNodeType, LEVEL-1> mNext;
825 };// DynamicNodeManagerLink class
826 
827 
831 template<typename NodeT>
832 class DynamicNodeManagerLink<NodeT, 0>
833 {
834 public:
835  DynamicNodeManagerLink() = default;
836 
837  template<typename NodeFilterOp, typename ParentT>
838  void foreachTopDownRecurse(const NodeFilterOp& nodeFilterOp, ParentT& parent, bool threaded, size_t grainSize)
839  {
840  if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded)) return;
841  mList.foreachWithIndex(nodeFilterOp.op(), threaded, grainSize);
842  }
843 
844  template<typename NodeFilterOp, typename ParentT>
845  void reduceTopDownRecurse(NodeFilterOp& nodeFilterOp, ParentT& parent, bool threaded, size_t grainSize)
846  {
847  if (!mList.initNodeChildren(parent, nodeFilterOp, !threaded)) return;
848  mList.reduceWithIndex(nodeFilterOp.op(), threaded, grainSize);
849  }
850 
851 protected:
852  NodeList<NodeT> mList;
853 };// DynamicNodeManagerLink class
854 
855 
856 template<typename TreeOrLeafManagerT, Index _LEVELS>
858 {
859 public:
860  static const Index LEVELS = _LEVELS;
861  static_assert(LEVELS > 0,
862  "expected instantiation of template specialization"); // see specialization below
863  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
864  static_assert(RootNodeType::LEVEL >= LEVELS, "number of levels exceeds root node height");
865 
866  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
867 
869 
871  const RootNodeType& root() const { return mRoot; }
872 
931  template<typename NodeOp>
932  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
933  {
934  mChain.foreachTopDown(op, mRoot, threaded, grainSize);
935  }
936 
995  template<typename NodeOp>
996  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
997  {
998  mChain.reduceTopDown(op, mRoot, threaded, grainSize);
999  }
1000 
1001 protected:
1003  DynamicNodeManagerLink<typename RootNodeType::ChildNodeType, LEVELS-1> mChain;
1004 };// DynamicNodeManager class
1005 
1006 
1007 
1009 
1010 
1013 template<typename TreeOrLeafManagerT>
1014 class NodeManager<TreeOrLeafManagerT, 0>
1015 {
1016 public:
1017  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1019  static const Index LEVELS = 0;
1020 
1021  NodeManager(TreeOrLeafManagerT& tree, bool /*serial*/ = false) : mRoot(tree.root()) { }
1022 
1023  NodeManager(const NodeManager&) = delete;
1024 
1026  void clear() {}
1027 
1030  void rebuild(bool /*serial*/ = false) { }
1031 
1033  const RootNodeType& root() const { return mRoot; }
1034 
1036  Index64 nodeCount() const { return 0; }
1037 
1038  Index64 nodeCount(Index) const { return 0; }
1039 
1040  template<typename NodeOp>
1041  void foreachBottomUp(const NodeOp& op, bool, size_t) { op(mRoot); }
1042 
1043  template<typename NodeOp>
1044  void foreachTopDown(const NodeOp& op, bool, size_t) { op(mRoot); }
1045 
1046  template<typename NodeOp>
1047  void reduceBottomUp(NodeOp& op, bool, size_t) { op(mRoot); }
1048 
1049  template<typename NodeOp>
1050  void reduceTopDown(NodeOp& op, bool, size_t) { op(mRoot); }
1051 
1052 protected:
1053  RootNodeType& mRoot;
1054 }; // NodeManager<0>
1055 
1056 
1058 
1059 
1062 template<typename TreeOrLeafManagerT>
1063 class NodeManager<TreeOrLeafManagerT, 1>
1064 {
1065 public:
1066  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1068  static_assert(RootNodeType::LEVEL > 0, "expected instantiation of template specialization");
1069  static const Index LEVELS = 1;
1070 
1071  NodeManager(TreeOrLeafManagerT& tree, bool serial = false)
1072  : mRoot(tree.root())
1073  {
1074  this->rebuild(serial);
1075  }
1076 
1077  NodeManager(const NodeManager&) = delete;
1078 
1080  void clear() { mList0.clear(); }
1081 
1084  void rebuild(bool /*serial*/ = false) { mList0.initRootChildren(mRoot); }
1085 
1087  const RootNodeType& root() const { return mRoot; }
1088 
1090  Index64 nodeCount() const { return mList0.nodeCount(); }
1091 
1094  Index64 nodeCount(Index i) const { return i==0 ? mList0.nodeCount() : 0; }
1095 
1096  template<typename NodeOp>
1097  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1098  {
1099  mList0.foreach(op, threaded, grainSize);
1100  op(mRoot);
1101  }
1102 
1103  template<typename NodeOp>
1104  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1105  {
1106  op(mRoot);
1107  mList0.foreach(op, threaded, grainSize);
1108  }
1109 
1110  template<typename NodeOp>
1111  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1112  {
1113  mList0.reduce(op, threaded, grainSize);
1114  op(mRoot);
1115  }
1116 
1117  template<typename NodeOp>
1118  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1119  {
1120  op(mRoot);
1121  mList0.reduce(op, threaded, grainSize);
1122  }
1123 
1124 protected:
1125  using NodeT1 = RootNodeType;
1126  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1127  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type;
1128  using ListT0 = NodeList<NodeT0>;
1129 
1130  NodeT1& mRoot;
1131  ListT0 mList0;
1132 }; // NodeManager<1>
1133 
1134 
1136 
1137 
1140 template<typename TreeOrLeafManagerT>
1141 class NodeManager<TreeOrLeafManagerT, 2>
1142 {
1143 public:
1144  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1146  static_assert(RootNodeType::LEVEL > 1, "expected instantiation of template specialization");
1147  static const Index LEVELS = 2;
1148 
1149  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1150  {
1151  this->rebuild(serial);
1152  }
1153 
1154  NodeManager(const NodeManager&) = delete;
1155 
1157  void clear() { mList0.clear(); mList1.clear(); }
1158 
1161  void rebuild(bool serial = false)
1162  {
1163  mList1.initRootChildren(mRoot);
1164  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1165  }
1166 
1168  const RootNodeType& root() const { return mRoot; }
1169 
1171  Index64 nodeCount() const { return mList0.nodeCount() + mList1.nodeCount(); }
1172 
1175  Index64 nodeCount(Index i) const
1176  {
1177  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() : 0;
1178  }
1179 
1180  template<typename NodeOp>
1181  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1182  {
1183  mList0.foreach(op, threaded, grainSize);
1184  mList1.foreach(op, threaded, grainSize);
1185  op(mRoot);
1186  }
1187 
1188  template<typename NodeOp>
1189  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1190  {
1191  op(mRoot);
1192  mList1.foreach(op, threaded, grainSize);
1193  mList0.foreach(op, threaded, grainSize);
1194  }
1195 
1196  template<typename NodeOp>
1197  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1198  {
1199  mList0.reduce(op, threaded, grainSize);
1200  mList1.reduce(op, threaded, grainSize);
1201  op(mRoot);
1202  }
1203 
1204  template<typename NodeOp>
1205  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1206  {
1207  op(mRoot);
1208  mList1.reduce(op, threaded, grainSize);
1209  mList0.reduce(op, threaded, grainSize);
1210  }
1211 
1212 protected:
1213  using NodeT2 = RootNodeType;
1214  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1215  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // upper level
1216  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1217  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1218 
1219  using ListT1 = NodeList<NodeT1>; // upper level
1220  using ListT0 = NodeList<NodeT0>; // lower level
1221 
1222  NodeT2& mRoot;
1223  ListT1 mList1;
1224  ListT0 mList0;
1225 }; // NodeManager<2>
1226 
1227 
1229 
1230 
1233 template<typename TreeOrLeafManagerT>
1234 class NodeManager<TreeOrLeafManagerT, 3>
1235 {
1236 public:
1237  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1239  static_assert(RootNodeType::LEVEL > 2, "expected instantiation of template specialization");
1240  static const Index LEVELS = 3;
1241 
1242  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1243  {
1244  this->rebuild(serial);
1245  }
1246 
1247  NodeManager(const NodeManager&) = delete;
1248 
1250  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); }
1251 
1254  void rebuild(bool serial = false)
1255  {
1256  mList2.initRootChildren(mRoot);
1257  mList1.initNodeChildren(mList2, NodeFilter(), serial);
1258  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1259  }
1260 
1262  const RootNodeType& root() const { return mRoot; }
1263 
1265  Index64 nodeCount() const { return mList0.nodeCount()+mList1.nodeCount()+mList2.nodeCount(); }
1266 
1269  Index64 nodeCount(Index i) const
1270  {
1271  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount()
1272  : i==2 ? mList2.nodeCount() : 0;
1273  }
1274 
1275  template<typename NodeOp>
1276  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1277  {
1278  mList0.foreach(op, threaded, grainSize);
1279  mList1.foreach(op, threaded, grainSize);
1280  mList2.foreach(op, threaded, grainSize);
1281  op(mRoot);
1282  }
1283 
1284  template<typename NodeOp>
1285  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1286  {
1287  op(mRoot);
1288  mList2.foreach(op, threaded, grainSize);
1289  mList1.foreach(op, threaded, grainSize);
1290  mList0.foreach(op, threaded, grainSize);
1291  }
1292 
1293  template<typename NodeOp>
1294  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1295  {
1296  mList0.reduce(op, threaded, grainSize);
1297  mList1.reduce(op, threaded, grainSize);
1298  mList2.reduce(op, threaded, grainSize);
1299  op(mRoot);
1300  }
1301 
1302  template<typename NodeOp>
1303  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1304  {
1305  op(mRoot);
1306  mList2.reduce(op, threaded, grainSize);
1307  mList1.reduce(op, threaded, grainSize);
1308  mList0.reduce(op, threaded, grainSize);
1309  }
1310 
1311 protected:
1312  using NodeT3 = RootNodeType;
1313  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1314  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper level
1315  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1316  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // mid level
1317  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1318  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1319 
1320  using ListT2 = NodeList<NodeT2>; // upper level of internal nodes
1321  using ListT1 = NodeList<NodeT1>; // lower level of internal nodes
1322  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1323 
1324  NodeT3& mRoot;
1325  ListT2 mList2;
1326  ListT1 mList1;
1327  ListT0 mList0;
1328 }; // NodeManager<3>
1329 
1330 
1332 
1333 
1336 template<typename TreeOrLeafManagerT>
1337 class NodeManager<TreeOrLeafManagerT, 4>
1338 {
1339 public:
1340  using NonConstRootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1342  static_assert(RootNodeType::LEVEL > 3, "expected instantiation of template specialization");
1343  static const Index LEVELS = 4;
1344 
1345  NodeManager(TreeOrLeafManagerT& tree, bool serial = false) : mRoot(tree.root())
1346  {
1347  this->rebuild(serial);
1348  }
1349 
1350  NodeManager(const NodeManager&) = delete; // disallow copy-construction
1351 
1353  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); mList3.clear(); }
1354 
1357  void rebuild(bool serial = false)
1358  {
1359  mList3.initRootChildren(mRoot);
1360  mList2.initNodeChildren(mList3, NodeFilter(), serial);
1361  mList1.initNodeChildren(mList2, NodeFilter(), serial);
1362  mList0.initNodeChildren(mList1, NodeFilter(), serial);
1363  }
1364 
1366  const RootNodeType& root() const { return mRoot; }
1367 
1369  Index64 nodeCount() const
1370  {
1371  return mList0.nodeCount() + mList1.nodeCount()
1372  + mList2.nodeCount() + mList3.nodeCount();
1373  }
1374 
1377  Index64 nodeCount(Index i) const
1378  {
1379  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() :
1380  i==2 ? mList2.nodeCount() : i==3 ? mList3.nodeCount() : 0;
1381  }
1382 
1383  template<typename NodeOp>
1384  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1385  {
1386  mList0.foreach(op, threaded, grainSize);
1387  mList1.foreach(op, threaded, grainSize);
1388  mList2.foreach(op, threaded, grainSize);
1389  mList3.foreach(op, threaded, grainSize);
1390  op(mRoot);
1391  }
1392 
1393  template<typename NodeOp>
1394  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1395  {
1396  op(mRoot);
1397  mList3.foreach(op, threaded, grainSize);
1398  mList2.foreach(op, threaded, grainSize);
1399  mList1.foreach(op, threaded, grainSize);
1400  mList0.foreach(op, threaded, grainSize);
1401  }
1402 
1403  template<typename NodeOp>
1404  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1405  {
1406  mList0.reduce(op, threaded, grainSize);
1407  mList1.reduce(op, threaded, grainSize);
1408  mList2.reduce(op, threaded, grainSize);
1409  mList3.reduce(op, threaded, grainSize);
1410  op(mRoot);
1411  }
1412 
1413  template<typename NodeOp>
1414  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1415  {
1416  op(mRoot);
1417  mList3.reduce(op, threaded, grainSize);
1418  mList2.reduce(op, threaded, grainSize);
1419  mList1.reduce(op, threaded, grainSize);
1420  mList0.reduce(op, threaded, grainSize);
1421  }
1422 
1423 protected:
1424  using NodeT4 = RootNodeType;
1425  using NonConstNodeT3 = typename NodeT4::ChildNodeType;
1426  using NodeT3 = typename CopyConstness<RootNodeType, NonConstNodeT3>::Type; // upper level
1427  using NonConstNodeT2 = typename NodeT3::ChildNodeType;
1428  using NodeT2 = typename CopyConstness<RootNodeType, NonConstNodeT2>::Type; // upper mid level
1429  using NonConstNodeT1 = typename NodeT2::ChildNodeType;
1430  using NodeT1 = typename CopyConstness<RootNodeType, NonConstNodeT1>::Type; // lower mid level
1431  using NonConstNodeT0 = typename NodeT1::ChildNodeType;
1432  using NodeT0 = typename CopyConstness<RootNodeType, NonConstNodeT0>::Type; // lower level
1433 
1434  using ListT3 = NodeList<NodeT3>; // upper level of internal nodes
1435  using ListT2 = NodeList<NodeT2>; // upper mid level of internal nodes
1436  using ListT1 = NodeList<NodeT1>; // lower mid level of internal nodes
1437  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1438 
1439  NodeT4& mRoot;
1440  ListT3 mList3;
1441  ListT2 mList2;
1442  ListT1 mList1;
1443  ListT0 mList0;
1444 }; // NodeManager<4>
1445 
1446 
1448 
1449 
1452 template<typename TreeOrLeafManagerT>
1453 class DynamicNodeManager<TreeOrLeafManagerT, 1>
1454 {
1455 public:
1456  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1457  static_assert(RootNodeType::LEVEL > 0, "expected instantiation of template specialization");
1458  static const Index LEVELS = 1;
1459 
1460  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1461 
1462  DynamicNodeManager(const DynamicNodeManager&) = delete;
1463 
1465  const RootNodeType& root() const { return mRoot; }
1466 
1467  template<typename NodeOp>
1468  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1469  {
1470  // root
1471  if (!op(mRoot, /*index=*/0)) return;
1472  // list0
1473  if (!mList0.initRootChildren(mRoot)) return;
1474  ForeachFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1475  mList0.foreachWithIndex(nodeOp, threaded, grainSize);
1476  }
1477 
1478  template<typename NodeOp>
1479  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1480  {
1481  // root
1482  if (!op(mRoot, /*index=*/0)) return;
1483  // list0
1484  if (!mList0.initRootChildren(mRoot)) return;
1485  ReduceFilterOp<NodeOp> nodeOp(op, mList0.nodeCount());
1486  mList0.reduceWithIndex(nodeOp, threaded, grainSize);
1487  }
1488 
1489 protected:
1490  using NodeT1 = RootNodeType;
1491  using NodeT0 = typename NodeT1::ChildNodeType;
1492 
1493  using ListT0 = NodeList<NodeT0>;
1494 
1495  NodeT1& mRoot;
1496  ListT0 mList0;
1497 };// DynamicNodeManager<1> class
1498 
1499 
1501 
1502 
1505 template<typename TreeOrLeafManagerT>
1506 class DynamicNodeManager<TreeOrLeafManagerT, 2>
1507 {
1508 public:
1509  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1510  static_assert(RootNodeType::LEVEL > 1, "expected instantiation of template specialization");
1511  static const Index LEVELS = 2;
1512 
1513  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1514 
1515  DynamicNodeManager(const DynamicNodeManager&) = delete;
1516 
1518  const RootNodeType& root() const { return mRoot; }
1519 
1520  template<typename NodeOp>
1521  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1522  {
1523  // root
1524  if (!op(mRoot, /*index=*/0)) return;
1525  // list1
1526  if (!mList1.initRootChildren(mRoot)) return;
1527  ForeachFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1528  mList1.foreachWithIndex(nodeOp, threaded, grainSize);
1529  // list0
1530  if (!mList0.initNodeChildren(mList1, nodeOp, !threaded)) return;
1531  mList0.foreachWithIndex(op, threaded, grainSize);
1532  }
1533 
1534  template<typename NodeOp>
1535  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1536  {
1537  // root
1538  if (!op(mRoot, /*index=*/0)) return;
1539  // list1
1540  if (!mList1.initRootChildren(mRoot)) return;
1541  ReduceFilterOp<NodeOp> nodeOp(op, mList1.nodeCount());
1542  mList1.reduceWithIndex(nodeOp, threaded, grainSize);
1543  // list0
1544  if (!mList0.initNodeChildren(mList1, nodeOp, !threaded)) return;
1545  mList0.reduceWithIndex(op, threaded, grainSize);
1546  }
1547 
1548 protected:
1549  using NodeT2 = RootNodeType;
1550  using NodeT1 = typename NodeT2::ChildNodeType; // upper level
1551  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
1552 
1553  using ListT1 = NodeList<NodeT1>; // upper level of internal nodes
1554  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1555 
1556  NodeT2& mRoot;
1557  ListT1 mList1;
1558  ListT0 mList0;
1559 };// DynamicNodeManager<2> class
1560 
1561 
1563 
1564 
1567 template<typename TreeOrLeafManagerT>
1568 class DynamicNodeManager<TreeOrLeafManagerT, 3>
1569 {
1570 public:
1571  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1572  static_assert(RootNodeType::LEVEL > 2, "expected instantiation of template specialization");
1573  static const Index LEVELS = 3;
1574 
1575  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1576 
1577  DynamicNodeManager(const DynamicNodeManager&) = delete;
1578 
1580  const RootNodeType& root() const { return mRoot; }
1581 
1582  template<typename NodeOp>
1583  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1584  {
1585  // root
1586  if (!op(mRoot, /*index=*/0)) return;
1587  // list2
1588  if (!mList2.initRootChildren(mRoot)) return;
1589  ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1590  mList2.foreachWithIndex(nodeOp2, threaded, grainSize);
1591  // list1
1592  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1593  ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1594  mList1.foreachWithIndex(nodeOp1, threaded, grainSize);
1595  // list0
1596  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1597  mList0.foreachWithIndex(op, threaded, grainSize);
1598  }
1599 
1600  template<typename NodeOp>
1601  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1602  {
1603  // root
1604  if (!op(mRoot, /*index=*/0)) return;
1605  // list2
1606  if (!mList2.initRootChildren(mRoot)) return;
1607  ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1608  mList2.reduceWithIndex(nodeOp2, threaded, grainSize);
1609  // list1
1610  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1611  ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1612  mList1.reduceWithIndex(nodeOp1, threaded, grainSize);
1613  // list0
1614  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1615  mList0.reduceWithIndex(op, threaded, grainSize);
1616  }
1617 
1618 protected:
1619  using NodeT3 = RootNodeType;
1620  using NodeT2 = typename NodeT3::ChildNodeType; // upper level
1621  using NodeT1 = typename NodeT2::ChildNodeType; // mid level
1622  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
1623 
1624  using ListT2 = NodeList<NodeT2>; // upper level of internal nodes
1625  using ListT1 = NodeList<NodeT1>; // lower level of internal nodes
1626  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1627 
1628  NodeT3& mRoot;
1629  ListT2 mList2;
1630  ListT1 mList1;
1631  ListT0 mList0;
1632 };// DynamicNodeManager<3> class
1633 
1634 
1636 
1637 
1640 template<typename TreeOrLeafManagerT>
1641 class DynamicNodeManager<TreeOrLeafManagerT, 4>
1642 {
1643 public:
1644  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
1645  static_assert(RootNodeType::LEVEL > 3, "expected instantiation of template specialization");
1646  static const Index LEVELS = 4;
1647 
1648  explicit DynamicNodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { }
1649 
1650  DynamicNodeManager(const DynamicNodeManager&) = delete;
1651 
1653  const RootNodeType& root() const { return mRoot; }
1654 
1655  template<typename NodeOp>
1656  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
1657  {
1658  // root
1659  if (!op(mRoot, /*index=*/0)) return;
1660  // list3
1661  if (!mList3.initRootChildren(mRoot)) return;
1662  ForeachFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1663  mList3.foreachWithIndex(nodeOp3, threaded, grainSize);
1664  // list2
1665  if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded)) return;
1666  ForeachFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1667  mList2.foreachWithIndex(nodeOp2, threaded, grainSize);
1668  // list1
1669  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1670  ForeachFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1671  mList1.foreachWithIndex(nodeOp1, threaded, grainSize);
1672  // list0
1673  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1674  mList0.foreachWithIndex(op, threaded, grainSize);
1675  }
1676 
1677  template<typename NodeOp>
1678  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1679  {
1680  // root
1681  if (!op(mRoot, /*index=*/0)) return;
1682  // list3
1683  if (!mList3.initRootChildren(mRoot)) return;
1684  ReduceFilterOp<NodeOp> nodeOp3(op, mList3.nodeCount());
1685  mList3.reduceWithIndex(nodeOp3, threaded, grainSize);
1686  // list2
1687  if (!mList2.initNodeChildren(mList3, nodeOp3, !threaded)) return;
1688  ReduceFilterOp<NodeOp> nodeOp2(op, mList2.nodeCount());
1689  mList2.reduceWithIndex(nodeOp2, threaded, grainSize);
1690  // list1
1691  if (!mList1.initNodeChildren(mList2, nodeOp2, !threaded)) return;
1692  ReduceFilterOp<NodeOp> nodeOp1(op, mList1.nodeCount());
1693  mList1.reduceWithIndex(nodeOp1, threaded, grainSize);
1694  // list0
1695  if (!mList0.initNodeChildren(mList1, nodeOp1, !threaded)) return;
1696  mList0.reduceWithIndex(op, threaded, grainSize);
1697  }
1698 
1699 protected:
1700  using NodeT4 = RootNodeType;
1701  using NodeT3 = typename NodeT4::ChildNodeType; // upper level
1702  using NodeT2 = typename NodeT3::ChildNodeType; // upper mid level
1703  using NodeT1 = typename NodeT2::ChildNodeType; // lower mid level
1704  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
1705 
1706  using ListT3 = NodeList<NodeT3>; // upper level of internal nodes
1707  using ListT2 = NodeList<NodeT2>; // upper mid level of internal nodes
1708  using ListT1 = NodeList<NodeT1>; // lower mid level of internal nodes
1709  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1710 
1711  NodeT4& mRoot;
1712  ListT3 mList3;
1713  ListT2 mList2;
1714  ListT1 mList1;
1715  ListT0 mList0;
1716 };// DynamicNodeManager<4> class
1717 
1718 
1719 } // namespace tree
1720 } // namespace OPENVDB_VERSION_NAME
1721 } // namespace openvdb
1722 
1723 #endif // OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
Definition: NodeManager.h:858
void reduceTopDown(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:996
RootNodeType & mRoot
Definition: NodeManager.h:1002
DynamicNodeManagerLink< typename RootNodeType::ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:1003
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:932
typename TreeOrLeafManagerT::RootNodeType RootNodeType
Definition: NodeManager.h:863
DynamicNodeManager(const DynamicNodeManager &)=delete
DynamicNodeManager(TreeOrLeafManagerT &tree)
Definition: NodeManager.h:866
const RootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:871
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
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:291
std::unique_ptr< NodeT *[]> mNodePtrs
Definition: NodeManager.h:368
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:283
void clear()
Definition: NodeManager.h:65
NodeT & operator()(size_t n) const
Definition: NodeManager.h:59
bool initRootChildren(RootT &root)
Definition: NodeManager.h:74
To facilitate threading over the nodes of a tree, cache node pointers in linear arrays,...
Definition: NodeManager.h:510
void reduceTopDown(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:684
RootNodeType & mRoot
Definition: NodeManager.h:692
NodeManager(TreeOrLeafManagerT &tree, bool serial=false)
Definition: NodeManager.h:521
typename RootNodeType::ChildNodeType NonConstChildNodeType
Definition: NodeManager.h:517
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:534
Index64 nodeCount() const
Return the total number of cached nodes (excluding the root node)
Definition: NodeManager.h:540
NodeManager(const NodeManager &)=delete
void foreachTopDown(const NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:610
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:603
NodeManagerLink< ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:693
void reduceBottomUp(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:677
typename CopyConstness< TreeOrLeafManagerT, NonConstRootNodeType >::Type RootNodeType
Definition: NodeManager.h:516
typename CopyConstness< TreeOrLeafManagerT, NonConstChildNodeType >::Type ChildNodeType
Definition: NodeManager.h:518
Index64 nodeCount(Index i) const
Return the number of cached nodes at level i, where 0 corresponds to the lowest level.
Definition: NodeManager.h:544
typename TreeOrLeafManagerT::RootNodeType NonConstRootNodeType
Definition: NodeManager.h:515
void clear()
Clear all the cached tree nodes.
Definition: NodeManager.h:530
const RootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:537
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:32
uint64_t Index64
Definition: openvdb/Types.h:31
Definition: openvdb/Exceptions.h:13
Definition: Coord.h:587
Definition: Coord.h:16
typename std::remove_const< ToType >::type Type
Definition: openvdb/Types.h:299
Definition: NodeManager.h:704
void operator()(NodeT &node, size_t idx) const
Definition: NodeManager.h:715
ForeachFilterOp(const OpT &op, openvdb::Index64 size)
Definition: NodeManager.h:705
bool valid(size_t idx) const
Definition: NodeManager.h:720
ForeachFilterOp(const ForeachFilterOp &other)
Definition: NodeManager.h:710
const OpT & op() const
Definition: NodeManager.h:722
Definition: NodeManager.h:45
static bool valid(size_t)
Definition: NodeManager.h:46
Definition: NodeManager.h:735
void operator()(NodeT &node, size_t idx) const
Definition: NodeManager.h:751
bool valid(size_t idx) const
Definition: NodeManager.h:761
ReduceFilterOp(const ReduceFilterOp &other)
Definition: NodeManager.h:741
ReduceFilterOp(const ReduceFilterOp &other, tbb::split)
Definition: NodeManager.h:745
ReduceFilterOp(OpT &op, openvdb::Index64 size)
Definition: NodeManager.h:736
OpT & op()
Definition: NodeManager.h:766
void join(const ReduceFilterOp &other)
Definition: NodeManager.h:756
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:101
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:153