OpenVDB  7.0.0
NodeManager.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
13 
14 #ifndef OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
15 #define OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
16 
17 #include <openvdb/Types.h>
18 #include <tbb/parallel_for.h>
19 #include <tbb/parallel_reduce.h>
20 #include <deque>
21 
22 
23 namespace openvdb {
25 namespace OPENVDB_VERSION_NAME {
26 namespace tree {
27 
28 // Produce linear arrays of all tree nodes, to facilitate efficient threading
29 // and bottom-up processing.
30 template<typename TreeOrLeafManagerT, Index LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
32 
33 
35 
36 
40 template<typename NodeT>
41 class NodeList
42 {
43 public:
44  using value_type = NodeT*;
45  using ListT = std::deque<value_type>;
46 
47  NodeList() {}
48 
49  void push_back(NodeT* node) { mList.push_back(node); }
50 
51  NodeT& operator()(size_t n) const { assert(n<mList.size()); return *(mList[n]); }
52 
53  NodeT*& operator[](size_t n) { assert(n<mList.size()); return mList[n]; }
54 
55  Index64 nodeCount() const { return mList.size(); }
56 
57  void clear() { mList.clear(); }
58 
59  void resize(size_t n) { mList.resize(n); }
60 
61  class NodeRange
62  {
63  public:
64 
65  NodeRange(size_t begin, size_t end, const NodeList& nodeList, size_t grainSize=1):
66  mEnd(end), mBegin(begin), mGrainSize(grainSize), mNodeList(nodeList) {}
67 
68  NodeRange(NodeRange& r, tbb::split):
69  mEnd(r.mEnd), mBegin(doSplit(r)), mGrainSize(r.mGrainSize),
70  mNodeList(r.mNodeList) {}
71 
72  size_t size() const { return mEnd - mBegin; }
73 
74  size_t grainsize() const { return mGrainSize; }
75 
76  const NodeList& nodeList() const { return mNodeList; }
77 
78  bool empty() const {return !(mBegin < mEnd);}
79 
80  bool is_divisible() const {return mGrainSize < this->size();}
81 
82  class Iterator
83  {
84  public:
85  Iterator(const NodeRange& range, size_t pos): mRange(range), mPos(pos)
86  {
87  assert(this->isValid());
88  }
89  Iterator(const Iterator&) = default;
90  Iterator& operator=(const Iterator&) = default;
92  Iterator& operator++() { ++mPos; return *this; }
94  NodeT& operator*() const { return mRange.mNodeList(mPos); }
96  NodeT* operator->() const { return &(this->operator*()); }
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(); }
106  bool operator!=(const Iterator& other) const
107  {
108  return (mPos != other.mPos) || (&mRange != &other.mRange);
109  }
110  bool operator==(const Iterator& other) const { return !(*this != other); }
111  const NodeRange& nodeRange() const { return mRange; }
112 
113  private:
114  const NodeRange& mRange;
115  size_t mPos;
116  };// NodeList::NodeRange::Iterator
117 
118  Iterator begin() const {return Iterator(*this, mBegin);}
119 
120  Iterator end() const {return Iterator(*this, mEnd);}
121 
122  private:
123  size_t mEnd, mBegin, mGrainSize;
124  const NodeList& mNodeList;
125 
126  static size_t doSplit(NodeRange& r)
127  {
128  assert(r.is_divisible());
129  size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
130  r.mEnd = middle;
131  return middle;
132  }
133  };// NodeList::NodeRange
134 
136  NodeRange nodeRange(size_t grainsize = 1) const
137  {
138  return NodeRange(0, this->nodeCount(), *this, grainsize);
139  }
140 
141  template<typename NodeOp>
142  void foreach(const NodeOp& op, bool threaded = true, size_t grainSize=1)
143  {
144  NodeTransformer<NodeOp> transform(op);
145  transform.run(this->nodeRange(grainSize), threaded);
146  }
147 
148  template<typename NodeOp>
149  void reduce(NodeOp& op, bool threaded = true, size_t grainSize=1)
150  {
151  NodeReducer<NodeOp> transform(op);
152  transform.run(this->nodeRange(grainSize), threaded);
153  }
154 
155 private:
156 
157  // Private struct of NodeList that performs parallel_for
158  template<typename NodeOp>
159  struct NodeTransformer
160  {
161  NodeTransformer(const NodeOp& nodeOp) : mNodeOp(nodeOp)
162  {
163  }
164  void run(const NodeRange& range, bool threaded = true)
165  {
166  threaded ? tbb::parallel_for(range, *this) : (*this)(range);
167  }
168  void operator()(const NodeRange& range) const
169  {
170  for (typename NodeRange::Iterator it = range.begin(); it; ++it) mNodeOp(*it);
171  }
172  const NodeOp mNodeOp;
173  };// NodeList::NodeTransformer
174 
175  // Private struct of NodeList that performs parallel_reduce
176  template<typename NodeOp>
177  struct NodeReducer
178  {
179  NodeReducer(NodeOp& nodeOp) : mNodeOp(&nodeOp), mOwnsOp(false)
180  {
181  }
182  NodeReducer(const NodeReducer& other, tbb::split) :
183  mNodeOp(new NodeOp(*(other.mNodeOp), tbb::split())), mOwnsOp(true)
184  {
185  }
186  ~NodeReducer() { if (mOwnsOp) delete mNodeOp; }
187  void run(const NodeRange& range, bool threaded = true)
188  {
189  threaded ? tbb::parallel_reduce(range, *this) : (*this)(range);
190  }
191  void operator()(const NodeRange& range)
192  {
193  NodeOp &op = *mNodeOp;
194  for (typename NodeRange::Iterator it = range.begin(); it; ++it) op(*it);
195  }
196  void join(const NodeReducer& other)
197  {
198  mNodeOp->join(*(other.mNodeOp));
199  }
200  NodeOp *mNodeOp;
201  const bool mOwnsOp;
202  };// NodeList::NodeReducer
203 
204 
205 protected:
207 };// NodeList
208 
209 
211 
212 
217 template<typename NodeT, Index LEVEL>
219 {
220 public:
222 
223  virtual ~NodeManagerLink() {}
224 
225  void clear() { mList.clear(); mNext.clear(); }
226 
227  template<typename ParentT, typename TreeOrLeafManagerT>
228  void init(ParentT& parent, TreeOrLeafManagerT& tree)
229  {
230  parent.getNodes(mList);
231  for (size_t i=0, n=mList.nodeCount(); i<n; ++i) mNext.init(mList(i), tree);
232  }
233 
234  template<typename ParentT>
235  void rebuild(ParentT& parent)
236  {
237  mList.clear();
238  parent.getNodes(mList);
239  for (size_t i=0, n=mList.nodeCount(); i<n; ++i) mNext.rebuild(mList(i));
240  }
241 
242  Index64 nodeCount() const { return mList.nodeCount() + mNext.nodeCount(); }
243 
245  {
246  return i==NodeT::LEVEL ? mList.nodeCount() : mNext.nodeCount(i);
247  }
248 
249  template<typename NodeOp>
250  void foreachBottomUp(const NodeOp& op, bool threaded, size_t grainSize)
251  {
252  mNext.foreachBottomUp(op, threaded, grainSize);
253  mList.foreach(op, threaded, grainSize);
254  }
255 
256  template<typename NodeOp>
257  void foreachTopDown(const NodeOp& op, bool threaded, size_t grainSize)
258  {
259  mList.foreach(op, threaded, grainSize);
260  mNext.foreachTopDown(op, threaded, grainSize);
261  }
262 
263  template<typename NodeOp>
264  void reduceBottomUp(NodeOp& op, bool threaded, size_t grainSize)
265  {
266  mNext.reduceBottomUp(op, threaded, grainSize);
267  mList.reduce(op, threaded, grainSize);
268  }
269 
270  template<typename NodeOp>
271  void reduceTopDown(NodeOp& op, bool threaded, size_t grainSize)
272  {
273  mList.reduce(op, threaded, grainSize);
274  mNext.reduceTopDown(op, threaded, grainSize);
275  }
276 
277 protected:
279  NodeManagerLink<typename NodeT::ChildNodeType, LEVEL-1> mNext;
280 };// NodeManagerLink class
281 
282 
284 
285 
289 template<typename NodeT>
290 class NodeManagerLink<NodeT, 0>
291 {
292 public:
293  NodeManagerLink() {}
294 
295  virtual ~NodeManagerLink() {}
296 
298  void clear() { mList.clear(); }
299 
300  template<typename ParentT>
301  void rebuild(ParentT& parent) { mList.clear(); parent.getNodes(mList); }
302 
303  Index64 nodeCount() const { return mList.nodeCount(); }
304 
305  Index64 nodeCount(Index) const { return mList.nodeCount(); }
306 
307  template<typename NodeOp>
308  void foreachBottomUp(const NodeOp& op, bool threaded, size_t grainSize)
309  {
310  mList.foreach(op, threaded, grainSize);
311  }
312 
313  template<typename NodeOp>
314  void foreachTopDown(const NodeOp& op, bool threaded, size_t grainSize)
315  {
316  mList.foreach(op, threaded, grainSize);
317  }
318 
319  template<typename NodeOp>
320  void reduceBottomUp(NodeOp& op, bool threaded, size_t grainSize)
321  {
322  mList.reduce(op, threaded, grainSize);
323  }
324 
325  template<typename NodeOp>
326  void reduceTopDown(NodeOp& op, bool threaded, size_t grainSize)
327  {
328  mList.reduce(op, threaded, grainSize);
329  }
330 
331  template<typename ParentT, typename TreeOrLeafManagerT>
332  void init(ParentT& parent, TreeOrLeafManagerT& tree)
333  {
335  if (TreeOrLeafManagerT::DEPTH == 2 && NodeT::LEVEL == 0) {
336  tree.getNodes(mList);
337  } else {
338  parent.getNodes(mList);
339  }
341  }
342 protected:
343  NodeList<NodeT> mList;
344 };// NodeManagerLink class
345 
346 
348 
349 
355 template<typename TreeOrLeafManagerT, Index _LEVELS>
356 class NodeManager
357 {
358 public:
359  static const Index LEVELS = _LEVELS;
360  static_assert(LEVELS > 0,
361  "expected instantiation of template specialization"); // see specialization below
362  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
363  static_assert(RootNodeType::LEVEL >= LEVELS, "number of levels exceeds root node height");
364 
365  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { mChain.init(mRoot, tree); }
366 
367  virtual ~NodeManager() {}
368 
370  void clear() { mChain.clear(); }
371 
374  void rebuild() { mChain.rebuild(mRoot); }
375 
377  const RootNodeType& root() const { return mRoot; }
378 
380  Index64 nodeCount() const { return mChain.nodeCount(); }
381 
384  Index64 nodeCount(Index i) const { return mChain.nodeCount(i); }
385 
387  template<typename NodeOp>
443  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
444  {
445  mChain.foreachBottomUp(op, threaded, grainSize);
446  op(mRoot);
447  }
448 
449  template<typename NodeOp>
450  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
451  {
452  op(mRoot);
453  mChain.foreachTopDown(op, threaded, grainSize);
454  }
455 
457 
459  template<typename NodeOp>
517  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
518  {
519  mChain.reduceBottomUp(op, threaded, grainSize);
520  op(mRoot);
521  }
522 
523  template<typename NodeOp>
524  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
525  {
526  op(mRoot);
527  mChain.reduceTopDown(op, threaded, grainSize);
528  }
530 
531 protected:
533  NodeManagerLink<typename RootNodeType::ChildNodeType, LEVELS-1> mChain;
534 
535 private:
536  NodeManager(const NodeManager&) {}//disallow copy-construction
537 };// NodeManager class
538 
539 
541 
542 
545 template<typename TreeOrLeafManagerT>
546 class NodeManager<TreeOrLeafManagerT, 0>
547 {
548 public:
549  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
550  static const Index LEVELS = 0;
551 
552  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) {}
553 
554  virtual ~NodeManager() {}
555 
557  void clear() {}
558 
561  void rebuild() {}
562 
564  const RootNodeType& root() const { return mRoot; }
565 
567  Index64 nodeCount() const { return 0; }
568 
569  Index64 nodeCount(Index) const { return 0; }
570 
571  template<typename NodeOp>
572  void foreachBottomUp(const NodeOp& op, bool, size_t) { op(mRoot); }
573 
574  template<typename NodeOp>
575  void foreachTopDown(const NodeOp& op, bool, size_t) { op(mRoot); }
576 
577  template<typename NodeOp>
578  void reduceBottomUp(NodeOp& op, bool, size_t) { op(mRoot); }
579 
580  template<typename NodeOp>
581  void reduceTopDown(NodeOp& op, bool, size_t) { op(mRoot); }
582 
583 protected:
584  RootNodeType& mRoot;
585 
586 private:
587  NodeManager(const NodeManager&) {} // disallow copy-construction
588 }; // NodeManager<0>
589 
590 
592 
593 
596 template<typename TreeOrLeafManagerT>
597 class NodeManager<TreeOrLeafManagerT, 1>
598 {
599 public:
600  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
601  static_assert(RootNodeType::LEVEL > 0, "expected instantiation of template specialization");
602  static const Index LEVELS = 1;
603 
604  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
605  {
607  if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
608  tree.getNodes(mList0);
609  } else {
610  mRoot.getNodes(mList0);
611  }
613  }
614 
615  virtual ~NodeManager() {}
616 
618  void clear() { mList0.clear(); }
619 
622  void rebuild() { mList0.clear(); mRoot.getNodes(mList0); }
623 
625  const RootNodeType& root() const { return mRoot; }
626 
628  Index64 nodeCount() const { return mList0.nodeCount(); }
629 
632  Index64 nodeCount(Index i) const { return i==0 ? mList0.nodeCount() : 0; }
633 
634  template<typename NodeOp>
635  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
636  {
637  mList0.foreach(op, threaded, grainSize);
638  op(mRoot);
639  }
640 
641  template<typename NodeOp>
642  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
643  {
644  op(mRoot);
645  mList0.foreach(op, threaded, grainSize);
646  }
647 
648  template<typename NodeOp>
649  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
650  {
651  mList0.reduce(op, threaded, grainSize);
652  op(mRoot);
653  }
654 
655  template<typename NodeOp>
656  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
657  {
658  op(mRoot);
659  mList0.reduce(op, threaded, grainSize);
660  }
661 
662 protected:
663  using NodeT1 = RootNodeType;
664  using NodeT0 = typename NodeT1::ChildNodeType;
665  using ListT0 = NodeList<NodeT0>;
666 
667  NodeT1& mRoot;
668  ListT0 mList0;
669 
670 private:
671  NodeManager(const NodeManager&) {} // disallow copy-construction
672 }; // NodeManager<1>
673 
674 
676 
677 
680 template<typename TreeOrLeafManagerT>
681 class NodeManager<TreeOrLeafManagerT, 2>
682 {
683 public:
684  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
685  static_assert(RootNodeType::LEVEL > 1, "expected instantiation of template specialization");
686  static const Index LEVELS = 2;
687 
688  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
689  {
690  mRoot.getNodes(mList1);
691 
693  if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
694  tree.getNodes(mList0);
695  } else {
696  for (size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
697  }
699  }
700 
701  virtual ~NodeManager() {}
702 
704  void clear() { mList0.clear(); mList1.clear(); }
705 
708  void rebuild()
709  {
710  this->clear();
711  mRoot.getNodes(mList1);
712  for (size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
713  }
714 
716  const RootNodeType& root() const { return mRoot; }
717 
719  Index64 nodeCount() const { return mList0.nodeCount() + mList1.nodeCount(); }
720 
723  Index64 nodeCount(Index i) const
724  {
725  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() : 0;
726  }
727 
728  template<typename NodeOp>
729  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
730  {
731  mList0.foreach(op, threaded, grainSize);
732  mList1.foreach(op, threaded, grainSize);
733  op(mRoot);
734  }
735 
736  template<typename NodeOp>
737  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
738  {
739  op(mRoot);
740  mList1.foreach(op, threaded, grainSize);
741  mList0.foreach(op, threaded, grainSize);
742  }
743 
744  template<typename NodeOp>
745  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
746  {
747  mList0.reduce(op, threaded, grainSize);
748  mList1.reduce(op, threaded, grainSize);
749  op(mRoot);
750  }
751 
752  template<typename NodeOp>
753  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
754  {
755  op(mRoot);
756  mList1.reduce(op, threaded, grainSize);
757  mList0.reduce(op, threaded, grainSize);
758  }
759 
760 protected:
761  using NodeT2 = RootNodeType;
762  using NodeT1 = typename NodeT2::ChildNodeType; // upper level
763  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
764 
765  using ListT1 = NodeList<NodeT1>; // upper level
766  using ListT0 = NodeList<NodeT0>; // lower level
767 
768  NodeT2& mRoot;
769  ListT1 mList1;
770  ListT0 mList0;
771 
772 private:
773  NodeManager(const NodeManager&) {} // disallow copy-construction
774 }; // NodeManager<2>
775 
776 
778 
779 
782 template<typename TreeOrLeafManagerT>
783 class NodeManager<TreeOrLeafManagerT, 3>
784 {
785 public:
786  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
787  static_assert(RootNodeType::LEVEL > 2, "expected instantiation of template specialization");
788  static const Index LEVELS = 3;
789 
790  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
791  {
792  mRoot.getNodes(mList2);
793  for (size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
794 
796  if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
797  tree.getNodes(mList0);
798  } else {
799  for (size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
800  }
802  }
803 
804  virtual ~NodeManager() {}
805 
807  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); }
808 
811  void rebuild()
812  {
813  this->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);
817  }
818 
820  const RootNodeType& root() const { return mRoot; }
821 
823  Index64 nodeCount() const { return mList0.nodeCount()+mList1.nodeCount()+mList2.nodeCount(); }
824 
827  Index64 nodeCount(Index i) const
828  {
829  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount()
830  : i==2 ? mList2.nodeCount() : 0;
831  }
832 
833  template<typename NodeOp>
834  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
835  {
836  mList0.foreach(op, threaded, grainSize);
837  mList1.foreach(op, threaded, grainSize);
838  mList2.foreach(op, threaded, grainSize);
839  op(mRoot);
840  }
841 
842  template<typename NodeOp>
843  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
844  {
845  op(mRoot);
846  mList2.foreach(op, threaded, grainSize);
847  mList1.foreach(op, threaded, grainSize);
848  mList0.foreach(op, threaded, grainSize);
849  }
850 
851  template<typename NodeOp>
852  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
853  {
854  mList0.reduce(op, threaded, grainSize);
855  mList1.reduce(op, threaded, grainSize);
856  mList2.reduce(op, threaded, grainSize);
857  op(mRoot);
858  }
859 
860  template<typename NodeOp>
861  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
862  {
863  op(mRoot);
864  mList2.reduce(op, threaded, grainSize);
865  mList1.reduce(op, threaded, grainSize);
866  mList0.reduce(op, threaded, grainSize);
867  }
868 
869 protected:
870  using NodeT3 = RootNodeType;
871  using NodeT2 = typename NodeT3::ChildNodeType; // upper level
872  using NodeT1 = typename NodeT2::ChildNodeType; // mid level
873  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
874 
875  using ListT2 = NodeList<NodeT2>; // upper level of internal nodes
876  using ListT1 = NodeList<NodeT1>; // lower level of internal nodes
877  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
878 
879  NodeT3& mRoot;
880  ListT2 mList2;
881  ListT1 mList1;
882  ListT0 mList0;
883 
884 private:
885  NodeManager(const NodeManager&) {} // disallow copy-construction
886 }; // NodeManager<3>
887 
888 
890 
891 
894 template<typename TreeOrLeafManagerT>
895 class NodeManager<TreeOrLeafManagerT, 4>
896 {
897 public:
898  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
899  static_assert(RootNodeType::LEVEL > 3, "expected instantiation of template specialization");
900  static const Index LEVELS = 4;
901 
902  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
903  {
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);
907 
909  if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
910  tree.getNodes(mList0);
911  } else {
912  for (size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
913  }
915  }
916 
917  virtual ~NodeManager() {}
918 
920  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); mList3.clear; }
921 
924  void rebuild()
925  {
926  this->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);
931  }
932 
934  const RootNodeType& root() const { return mRoot; }
935 
937  Index64 nodeCount() const
938  {
939  return mList0.nodeCount() + mList1.nodeCount()
940  + mList2.nodeCount() + mList3.nodeCount();
941  }
942 
945  Index64 nodeCount(Index i) const
946  {
947  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() :
948  i==2 ? mList2.nodeCount() : i==3 ? mList3.nodeCount() : 0;
949  }
950 
951  template<typename NodeOp>
952  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
953  {
954  mList0.foreach(op, threaded, grainSize);
955  mList1.foreach(op, threaded, grainSize);
956  mList2.foreach(op, threaded, grainSize);
957  mList3.foreach(op, threaded, grainSize);
958  op(mRoot);
959  }
960 
961  template<typename NodeOp>
962  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
963  {
964  op(mRoot);
965  mList3.foreach(op, threaded, grainSize);
966  mList2.foreach(op, threaded, grainSize);
967  mList1.foreach(op, threaded, grainSize);
968  mList0.foreach(op, threaded, grainSize);
969  }
970 
971  template<typename NodeOp>
972  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
973  {
974  mList0.reduce(op, threaded, grainSize);
975  mList1.reduce(op, threaded, grainSize);
976  mList2.reduce(op, threaded, grainSize);
977  mList3.reduce(op, threaded, grainSize);
978  op(mRoot);
979  }
980 
981  template<typename NodeOp>
982  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
983  {
984  op(mRoot);
985  mList3.reduce(op, threaded, grainSize);
986  mList2.reduce(op, threaded, grainSize);
987  mList1.reduce(op, threaded, grainSize);
988  mList0.reduce(op, threaded, grainSize);
989  }
990 
991 protected:
992  using NodeT4 = RootNodeType;
993  using NodeT3 = typename NodeT4::ChildNodeType; // upper level
994  using NodeT2 = typename NodeT3::ChildNodeType; // upper mid level
995  using NodeT1 = typename NodeT2::ChildNodeType; // lower mid level
996  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
997 
998  using ListT3 = NodeList<NodeT3>; // upper level of internal nodes
999  using ListT2 = NodeList<NodeT2>; // upper mid level of internal nodes
1000  using ListT1 = NodeList<NodeT1>; // lower mid level of internal nodes
1001  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1002 
1003  NodeT4& mRoot;
1004  ListT3 mList3;
1005  ListT2 mList2;
1006  ListT1 mList1;
1007  ListT0 mList0;
1008 
1009 private:
1010  NodeManager(const NodeManager&) {} // disallow copy-construction
1011 }; // NodeManager<4>
1012 
1013 } // namespace tree
1014 } // namespace OPENVDB_VERSION_NAME
1015 } // namespace openvdb
1016 
1017 #endif // OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
Index64 nodeCount(Index i) const
Return the number of cached nodes at level i, where 0 corresponds to the lowest level.
Definition: NodeManager.h:384
const NodeList & nodeList() const
Definition: NodeManager.h:76
bool empty() const
Return true if this iterator is exhausted.
Definition: NodeManager.h:105
NodeRange(NodeRange &r, tbb::split)
Definition: NodeManager.h:68
RootNodeType & mRoot
Definition: NodeManager.h:532
const NodeRange & nodeRange() const
Definition: NodeManager.h:111
NodeT0 * value_type
Definition: NodeManager.h:44
void rebuild()
Clear and recache all the tree nodes from the tree. This is required if tree nodes have been added or...
Definition: NodeManager.h:374
Index64 nodeCount() const
Return the total number of cached nodes (excluding the root node)
Definition: NodeManager.h:380
bool isValid() const
Definition: NodeManager.h:99
const RootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:377
typename TreeOrLeafManagerT::RootNodeType RootNodeType
Definition: NodeManager.h:362
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:443
Definition: NodeManager.h:61
void resize(size_t n)
Definition: NodeManager.h:59
bool is_divisible() const
Definition: NodeManager.h:80
size_t pos() const
Return the index into the list of the current node.
Definition: NodeManager.h:98
Iterator & operator++()
Advance to the next node.
Definition: NodeManager.h:92
bool operator!=(const Iterator &other) const
Definition: NodeManager.h:106
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:102
size_t size() const
Definition: NodeManager.h:72
Iterator end() const
Definition: NodeManager.h:120
To facilitate threading over the nodes of a tree, cache node pointers in linear arrays, one for each level of the tree.
Definition: NodeManager.h:31
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:450
NodeT * operator->() const
Return a pointer to the node to which this iterator is pointing.
Definition: NodeManager.h:96
void reduce(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:149
NodeManagerLink< typename RootNodeType::ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:533
Definition: Exceptions.h:13
Iterator begin() const
Definition: NodeManager.h:118
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
SIMD Intrinsic Headers.
Definition: Platform.h:114
bool operator==(const Iterator &other) const
Definition: NodeManager.h:110
void reduceBottomUp(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:517
bool test() const
Return true if this iterator is not yet exhausted.
Definition: NodeManager.h:101
NodeRange(size_t begin, size_t end, const NodeList &nodeList, size_t grainSize=1)
Definition: NodeManager.h:65
ListT mList
Definition: NodeManager.h:206
void clear()
Clear all the cached tree nodes.
Definition: NodeManager.h:370
bool empty() const
Definition: NodeManager.h:78
NodeT & operator()(size_t n) const
Definition: NodeManager.h:51
NodeList()
Definition: NodeManager.h:47
This class caches tree nodes of a specific type in a linear array.
Definition: NodeManager.h:41
Index32 Index
Definition: Types.h:31
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:115
Iterator(const NodeRange &range, size_t pos)
Definition: NodeManager.h:85
size_t grainsize() const
Definition: NodeManager.h:74
NodeT *& operator[](size_t n)
Definition: NodeManager.h:53
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:618
void push_back(NodeT *node)
Definition: NodeManager.h:49
Index64 nodeCount() const
Definition: NodeManager.h:55
virtual ~NodeManager()
Definition: NodeManager.h:367
uint64_t Index64
Definition: Types.h:30
void reduceTopDown(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:524
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:154
std::deque< value_type > ListT
Definition: NodeManager.h:45
NodeT & operator*() const
Return a reference to the node to which this iterator is pointing.
Definition: NodeManager.h:94
NodeManager(TreeOrLeafManagerT &tree)
Definition: NodeManager.h:365
void clear()
Definition: NodeManager.h:57
NodeRange nodeRange(size_t grainsize=1) const
Return a TBB-compatible NodeRange.
Definition: NodeManager.h:136