OpenVDB  6.2.1
NodeManager.h
Go to the documentation of this file.
1 //
3 // Copyright (c) DreamWorks Animation LLC
4 //
5 // All rights reserved. This software is distributed under the
6 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
7 //
8 // Redistributions of source code must retain the above copyright
9 // and license notice and the following restrictions and disclaimer.
10 //
11 // * Neither the name of DreamWorks Animation nor the names of
12 // its contributors may be used to endorse or promote products derived
13 // from this software without specific prior written permission.
14 //
15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
18 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
19 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY INDIRECT, INCIDENTAL,
20 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
21 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 // IN NO EVENT SHALL THE COPYRIGHT HOLDERS' AND CONTRIBUTORS' AGGREGATE
27 // LIABILITY FOR ALL CLAIMS REGARDLESS OF THEIR BASIS EXCEED US$250.00.
28 //
30 
40 
41 #ifndef OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
42 #define OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
43 
44 #include <openvdb/Types.h>
45 #include <tbb/parallel_for.h>
46 #include <tbb/parallel_reduce.h>
47 #include <deque>
48 
49 
50 namespace openvdb {
52 namespace OPENVDB_VERSION_NAME {
53 namespace tree {
54 
55 // Produce linear arrays of all tree nodes, to facilitate efficient threading
56 // and bottom-up processing.
57 template<typename TreeOrLeafManagerT, Index LEVELS = TreeOrLeafManagerT::RootNodeType::LEVEL>
59 
60 
62 
63 
67 template<typename NodeT>
68 class NodeList
69 {
70 public:
71  using value_type = NodeT*;
72  using ListT = std::deque<value_type>;
73 
74  NodeList() {}
75 
76  void push_back(NodeT* node) { mList.push_back(node); }
77 
78  NodeT& operator()(size_t n) const { assert(n<mList.size()); return *(mList[n]); }
79 
80  NodeT*& operator[](size_t n) { assert(n<mList.size()); return mList[n]; }
81 
82  Index64 nodeCount() const { return mList.size(); }
83 
84  void clear() { mList.clear(); }
85 
86  void resize(size_t n) { mList.resize(n); }
87 
88  class NodeRange
89  {
90  public:
91 
92  NodeRange(size_t begin, size_t end, const NodeList& nodeList, size_t grainSize=1):
93  mEnd(end), mBegin(begin), mGrainSize(grainSize), mNodeList(nodeList) {}
94 
95  NodeRange(NodeRange& r, tbb::split):
96  mEnd(r.mEnd), mBegin(doSplit(r)), mGrainSize(r.mGrainSize),
97  mNodeList(r.mNodeList) {}
98 
99  size_t size() const { return mEnd - mBegin; }
100 
101  size_t grainsize() const { return mGrainSize; }
102 
103  const NodeList& nodeList() const { return mNodeList; }
104 
105  bool empty() const {return !(mBegin < mEnd);}
106 
107  bool is_divisible() const {return mGrainSize < this->size();}
108 
109  class Iterator
110  {
111  public:
112  Iterator(const NodeRange& range, size_t pos): mRange(range), mPos(pos)
113  {
114  assert(this->isValid());
115  }
116  Iterator(const Iterator&) = default;
117  Iterator& operator=(const Iterator&) = default;
119  Iterator& operator++() { ++mPos; return *this; }
121  NodeT& operator*() const { return mRange.mNodeList(mPos); }
123  NodeT* operator->() const { return &(this->operator*()); }
125  size_t pos() const { return mPos; }
126  bool isValid() const { return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
128  bool test() const { return mPos < mRange.mEnd; }
130  operator bool() const { return this->test(); }
132  bool empty() const { return !this->test(); }
133  bool operator!=(const Iterator& other) const
134  {
135  return (mPos != other.mPos) || (&mRange != &other.mRange);
136  }
137  bool operator==(const Iterator& other) const { return !(*this != other); }
138  const NodeRange& nodeRange() const { return mRange; }
139 
140  private:
141  const NodeRange& mRange;
142  size_t mPos;
143  };// NodeList::NodeRange::Iterator
144 
145  Iterator begin() const {return Iterator(*this, mBegin);}
146 
147  Iterator end() const {return Iterator(*this, mEnd);}
148 
149  private:
150  size_t mEnd, mBegin, mGrainSize;
151  const NodeList& mNodeList;
152 
153  static size_t doSplit(NodeRange& r)
154  {
155  assert(r.is_divisible());
156  size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
157  r.mEnd = middle;
158  return middle;
159  }
160  };// NodeList::NodeRange
161 
163  NodeRange nodeRange(size_t grainsize = 1) const
164  {
165  return NodeRange(0, this->nodeCount(), *this, grainsize);
166  }
167 
168  template<typename NodeOp>
169  void foreach(const NodeOp& op, bool threaded = true, size_t grainSize=1)
170  {
171  NodeTransformer<NodeOp> transform(op);
172  transform.run(this->nodeRange(grainSize), threaded);
173  }
174 
175  template<typename NodeOp>
176  void reduce(NodeOp& op, bool threaded = true, size_t grainSize=1)
177  {
178  NodeReducer<NodeOp> transform(op);
179  transform.run(this->nodeRange(grainSize), threaded);
180  }
181 
182 private:
183 
184  // Private struct of NodeList that performs parallel_for
185  template<typename NodeOp>
186  struct NodeTransformer
187  {
188  NodeTransformer(const NodeOp& nodeOp) : mNodeOp(nodeOp)
189  {
190  }
191  void run(const NodeRange& range, bool threaded = true)
192  {
193  threaded ? tbb::parallel_for(range, *this) : (*this)(range);
194  }
195  void operator()(const NodeRange& range) const
196  {
197  for (typename NodeRange::Iterator it = range.begin(); it; ++it) mNodeOp(*it);
198  }
199  const NodeOp mNodeOp;
200  };// NodeList::NodeTransformer
201 
202  // Private struct of NodeList that performs parallel_reduce
203  template<typename NodeOp>
204  struct NodeReducer
205  {
206  NodeReducer(NodeOp& nodeOp) : mNodeOp(&nodeOp), mOwnsOp(false)
207  {
208  }
209  NodeReducer(const NodeReducer& other, tbb::split) :
210  mNodeOp(new NodeOp(*(other.mNodeOp), tbb::split())), mOwnsOp(true)
211  {
212  }
213  ~NodeReducer() { if (mOwnsOp) delete mNodeOp; }
214  void run(const NodeRange& range, bool threaded = true)
215  {
216  threaded ? tbb::parallel_reduce(range, *this) : (*this)(range);
217  }
218  void operator()(const NodeRange& range)
219  {
220  NodeOp &op = *mNodeOp;
221  for (typename NodeRange::Iterator it = range.begin(); it; ++it) op(*it);
222  }
223  void join(const NodeReducer& other)
224  {
225  mNodeOp->join(*(other.mNodeOp));
226  }
227  NodeOp *mNodeOp;
228  const bool mOwnsOp;
229  };// NodeList::NodeReducer
230 
231 
232 protected:
234 };// NodeList
235 
236 
238 
239 
244 template<typename NodeT, Index LEVEL>
246 {
247 public:
249 
250  virtual ~NodeManagerLink() {}
251 
252  void clear() { mList.clear(); mNext.clear(); }
253 
254  template<typename ParentT, typename TreeOrLeafManagerT>
255  void init(ParentT& parent, TreeOrLeafManagerT& tree)
256  {
257  parent.getNodes(mList);
258  for (size_t i=0, n=mList.nodeCount(); i<n; ++i) mNext.init(mList(i), tree);
259  }
260 
261  template<typename ParentT>
262  void rebuild(ParentT& parent)
263  {
264  mList.clear();
265  parent.getNodes(mList);
266  for (size_t i=0, n=mList.nodeCount(); i<n; ++i) mNext.rebuild(mList(i));
267  }
268 
269  Index64 nodeCount() const { return mList.nodeCount() + mNext.nodeCount(); }
270 
272  {
273  return i==NodeT::LEVEL ? mList.nodeCount() : mNext.nodeCount(i);
274  }
275 
276  template<typename NodeOp>
277  void foreachBottomUp(const NodeOp& op, bool threaded, size_t grainSize)
278  {
279  mNext.foreachBottomUp(op, threaded, grainSize);
280  mList.foreach(op, threaded, grainSize);
281  }
282 
283  template<typename NodeOp>
284  void foreachTopDown(const NodeOp& op, bool threaded, size_t grainSize)
285  {
286  mList.foreach(op, threaded, grainSize);
287  mNext.foreachTopDown(op, threaded, grainSize);
288  }
289 
290  template<typename NodeOp>
291  void reduceBottomUp(NodeOp& op, bool threaded, size_t grainSize)
292  {
293  mNext.reduceBottomUp(op, threaded, grainSize);
294  mList.reduce(op, threaded, grainSize);
295  }
296 
297  template<typename NodeOp>
298  void reduceTopDown(NodeOp& op, bool threaded, size_t grainSize)
299  {
300  mList.reduce(op, threaded, grainSize);
301  mNext.reduceTopDown(op, threaded, grainSize);
302  }
303 
304 protected:
306  NodeManagerLink<typename NodeT::ChildNodeType, LEVEL-1> mNext;
307 };// NodeManagerLink class
308 
309 
311 
312 
316 template<typename NodeT>
317 class NodeManagerLink<NodeT, 0>
318 {
319 public:
320  NodeManagerLink() {}
321 
322  virtual ~NodeManagerLink() {}
323 
325  void clear() { mList.clear(); }
326 
327  template<typename ParentT>
328  void rebuild(ParentT& parent) { mList.clear(); parent.getNodes(mList); }
329 
330  Index64 nodeCount() const { return mList.nodeCount(); }
331 
332  Index64 nodeCount(Index) const { return mList.nodeCount(); }
333 
334  template<typename NodeOp>
335  void foreachBottomUp(const NodeOp& op, bool threaded, size_t grainSize)
336  {
337  mList.foreach(op, threaded, grainSize);
338  }
339 
340  template<typename NodeOp>
341  void foreachTopDown(const NodeOp& op, bool threaded, size_t grainSize)
342  {
343  mList.foreach(op, threaded, grainSize);
344  }
345 
346  template<typename NodeOp>
347  void reduceBottomUp(NodeOp& op, bool threaded, size_t grainSize)
348  {
349  mList.reduce(op, threaded, grainSize);
350  }
351 
352  template<typename NodeOp>
353  void reduceTopDown(NodeOp& op, bool threaded, size_t grainSize)
354  {
355  mList.reduce(op, threaded, grainSize);
356  }
357 
358  template<typename ParentT, typename TreeOrLeafManagerT>
359  void init(ParentT& parent, TreeOrLeafManagerT& tree)
360  {
362  if (TreeOrLeafManagerT::DEPTH == 2 && NodeT::LEVEL == 0) {
363  tree.getNodes(mList);
364  } else {
365  parent.getNodes(mList);
366  }
368  }
369 protected:
370  NodeList<NodeT> mList;
371 };// NodeManagerLink class
372 
373 
375 
376 
382 template<typename TreeOrLeafManagerT, Index _LEVELS>
383 class NodeManager
384 {
385 public:
386  static const Index LEVELS = _LEVELS;
387  static_assert(LEVELS > 0,
388  "expected instantiation of template specialization"); // see specialization below
389  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
390  static_assert(RootNodeType::LEVEL >= LEVELS, "number of levels exceeds root node height");
391 
392  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) { mChain.init(mRoot, tree); }
393 
394  virtual ~NodeManager() {}
395 
397  void clear() { mChain.clear(); }
398 
401  void rebuild() { mChain.rebuild(mRoot); }
402 
404  const RootNodeType& root() const { return mRoot; }
405 
407  Index64 nodeCount() const { return mChain.nodeCount(); }
408 
411  Index64 nodeCount(Index i) const { return mChain.nodeCount(i); }
412 
414  template<typename NodeOp>
470  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
471  {
472  mChain.foreachBottomUp(op, threaded, grainSize);
473  op(mRoot);
474  }
475 
476  template<typename NodeOp>
477  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
478  {
479  op(mRoot);
480  mChain.foreachTopDown(op, threaded, grainSize);
481  }
482 
484 
486  template<typename NodeOp>
544  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
545  {
546  mChain.reduceBottomUp(op, threaded, grainSize);
547  op(mRoot);
548  }
549 
550  template<typename NodeOp>
551  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
552  {
553  op(mRoot);
554  mChain.reduceTopDown(op, threaded, grainSize);
555  }
557 
558 protected:
560  NodeManagerLink<typename RootNodeType::ChildNodeType, LEVELS-1> mChain;
561 
562 private:
563  NodeManager(const NodeManager&) {}//disallow copy-construction
564 };// NodeManager class
565 
566 
568 
569 
572 template<typename TreeOrLeafManagerT>
573 class NodeManager<TreeOrLeafManagerT, 0>
574 {
575 public:
576  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
577  static const Index LEVELS = 0;
578 
579  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root()) {}
580 
581  virtual ~NodeManager() {}
582 
584  void clear() {}
585 
588  void rebuild() {}
589 
591  const RootNodeType& root() const { return mRoot; }
592 
594  Index64 nodeCount() const { return 0; }
595 
596  Index64 nodeCount(Index) const { return 0; }
597 
598  template<typename NodeOp>
599  void foreachBottomUp(const NodeOp& op, bool, size_t) { op(mRoot); }
600 
601  template<typename NodeOp>
602  void foreachTopDown(const NodeOp& op, bool, size_t) { op(mRoot); }
603 
604  template<typename NodeOp>
605  void reduceBottomUp(NodeOp& op, bool, size_t) { op(mRoot); }
606 
607  template<typename NodeOp>
608  void reduceTopDown(NodeOp& op, bool, size_t) { op(mRoot); }
609 
610 protected:
611  RootNodeType& mRoot;
612 
613 private:
614  NodeManager(const NodeManager&) {} // disallow copy-construction
615 }; // NodeManager<0>
616 
617 
619 
620 
623 template<typename TreeOrLeafManagerT>
624 class NodeManager<TreeOrLeafManagerT, 1>
625 {
626 public:
627  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
628  static_assert(RootNodeType::LEVEL > 0, "expected instantiation of template specialization");
629  static const Index LEVELS = 1;
630 
631  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
632  {
634  if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
635  tree.getNodes(mList0);
636  } else {
637  mRoot.getNodes(mList0);
638  }
640  }
641 
642  virtual ~NodeManager() {}
643 
645  void clear() { mList0.clear(); }
646 
649  void rebuild() { mList0.clear(); mRoot.getNodes(mList0); }
650 
652  const RootNodeType& root() const { return mRoot; }
653 
655  Index64 nodeCount() const { return mList0.nodeCount(); }
656 
659  Index64 nodeCount(Index i) const { return i==0 ? mList0.nodeCount() : 0; }
660 
661  template<typename NodeOp>
662  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
663  {
664  mList0.foreach(op, threaded, grainSize);
665  op(mRoot);
666  }
667 
668  template<typename NodeOp>
669  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
670  {
671  op(mRoot);
672  mList0.foreach(op, threaded, grainSize);
673  }
674 
675  template<typename NodeOp>
676  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
677  {
678  mList0.reduce(op, threaded, grainSize);
679  op(mRoot);
680  }
681 
682  template<typename NodeOp>
683  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
684  {
685  op(mRoot);
686  mList0.reduce(op, threaded, grainSize);
687  }
688 
689 protected:
690  using NodeT1 = RootNodeType;
691  using NodeT0 = typename NodeT1::ChildNodeType;
692  using ListT0 = NodeList<NodeT0>;
693 
694  NodeT1& mRoot;
695  ListT0 mList0;
696 
697 private:
698  NodeManager(const NodeManager&) {} // disallow copy-construction
699 }; // NodeManager<1>
700 
701 
703 
704 
707 template<typename TreeOrLeafManagerT>
708 class NodeManager<TreeOrLeafManagerT, 2>
709 {
710 public:
711  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
712  static_assert(RootNodeType::LEVEL > 1, "expected instantiation of template specialization");
713  static const Index LEVELS = 2;
714 
715  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
716  {
717  mRoot.getNodes(mList1);
718 
720  if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
721  tree.getNodes(mList0);
722  } else {
723  for (size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
724  }
726  }
727 
728  virtual ~NodeManager() {}
729 
731  void clear() { mList0.clear(); mList1.clear(); }
732 
735  void rebuild()
736  {
737  this->clear();
738  mRoot.getNodes(mList1);
739  for (size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
740  }
741 
743  const RootNodeType& root() const { return mRoot; }
744 
746  Index64 nodeCount() const { return mList0.nodeCount() + mList1.nodeCount(); }
747 
750  Index64 nodeCount(Index i) const
751  {
752  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() : 0;
753  }
754 
755  template<typename NodeOp>
756  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
757  {
758  mList0.foreach(op, threaded, grainSize);
759  mList1.foreach(op, threaded, grainSize);
760  op(mRoot);
761  }
762 
763  template<typename NodeOp>
764  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
765  {
766  op(mRoot);
767  mList1.foreach(op, threaded, grainSize);
768  mList0.foreach(op, threaded, grainSize);
769  }
770 
771  template<typename NodeOp>
772  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
773  {
774  mList0.reduce(op, threaded, grainSize);
775  mList1.reduce(op, threaded, grainSize);
776  op(mRoot);
777  }
778 
779  template<typename NodeOp>
780  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
781  {
782  op(mRoot);
783  mList1.reduce(op, threaded, grainSize);
784  mList0.reduce(op, threaded, grainSize);
785  }
786 
787 protected:
788  using NodeT2 = RootNodeType;
789  using NodeT1 = typename NodeT2::ChildNodeType; // upper level
790  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
791 
792  using ListT1 = NodeList<NodeT1>; // upper level
793  using ListT0 = NodeList<NodeT0>; // lower level
794 
795  NodeT2& mRoot;
796  ListT1 mList1;
797  ListT0 mList0;
798 
799 private:
800  NodeManager(const NodeManager&) {} // disallow copy-construction
801 }; // NodeManager<2>
802 
803 
805 
806 
809 template<typename TreeOrLeafManagerT>
810 class NodeManager<TreeOrLeafManagerT, 3>
811 {
812 public:
813  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
814  static_assert(RootNodeType::LEVEL > 2, "expected instantiation of template specialization");
815  static const Index LEVELS = 3;
816 
817  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
818  {
819  mRoot.getNodes(mList2);
820  for (size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
821 
823  if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
824  tree.getNodes(mList0);
825  } else {
826  for (size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
827  }
829  }
830 
831  virtual ~NodeManager() {}
832 
834  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); }
835 
838  void rebuild()
839  {
840  this->clear();
841  mRoot.getNodes(mList2);
842  for (size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
843  for (size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
844  }
845 
847  const RootNodeType& root() const { return mRoot; }
848 
850  Index64 nodeCount() const { return mList0.nodeCount()+mList1.nodeCount()+mList2.nodeCount(); }
851 
854  Index64 nodeCount(Index i) const
855  {
856  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount()
857  : i==2 ? mList2.nodeCount() : 0;
858  }
859 
860  template<typename NodeOp>
861  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
862  {
863  mList0.foreach(op, threaded, grainSize);
864  mList1.foreach(op, threaded, grainSize);
865  mList2.foreach(op, threaded, grainSize);
866  op(mRoot);
867  }
868 
869  template<typename NodeOp>
870  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
871  {
872  op(mRoot);
873  mList2.foreach(op, threaded, grainSize);
874  mList1.foreach(op, threaded, grainSize);
875  mList0.foreach(op, threaded, grainSize);
876  }
877 
878  template<typename NodeOp>
879  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
880  {
881  mList0.reduce(op, threaded, grainSize);
882  mList1.reduce(op, threaded, grainSize);
883  mList2.reduce(op, threaded, grainSize);
884  op(mRoot);
885  }
886 
887  template<typename NodeOp>
888  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
889  {
890  op(mRoot);
891  mList2.reduce(op, threaded, grainSize);
892  mList1.reduce(op, threaded, grainSize);
893  mList0.reduce(op, threaded, grainSize);
894  }
895 
896 protected:
897  using NodeT3 = RootNodeType;
898  using NodeT2 = typename NodeT3::ChildNodeType; // upper level
899  using NodeT1 = typename NodeT2::ChildNodeType; // mid level
900  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
901 
902  using ListT2 = NodeList<NodeT2>; // upper level of internal nodes
903  using ListT1 = NodeList<NodeT1>; // lower level of internal nodes
904  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
905 
906  NodeT3& mRoot;
907  ListT2 mList2;
908  ListT1 mList1;
909  ListT0 mList0;
910 
911 private:
912  NodeManager(const NodeManager&) {} // disallow copy-construction
913 }; // NodeManager<3>
914 
915 
917 
918 
921 template<typename TreeOrLeafManagerT>
922 class NodeManager<TreeOrLeafManagerT, 4>
923 {
924 public:
925  using RootNodeType = typename TreeOrLeafManagerT::RootNodeType;
926  static_assert(RootNodeType::LEVEL > 3, "expected instantiation of template specialization");
927  static const Index LEVELS = 4;
928 
929  NodeManager(TreeOrLeafManagerT& tree) : mRoot(tree.root())
930  {
931  mRoot.getNodes(mList3);
932  for (size_t i=0, n=mList3.nodeCount(); i<n; ++i) mList3(i).getNodes(mList2);
933  for (size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
934 
936  if (TreeOrLeafManagerT::DEPTH == 2 && NodeT0::LEVEL == 0) {
937  tree.getNodes(mList0);
938  } else {
939  for (size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
940  }
942  }
943 
944  virtual ~NodeManager() {}
945 
947  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); mList3.clear; }
948 
951  void rebuild()
952  {
953  this->clear();
954  mRoot.getNodes(mList3);
955  for (size_t i=0, n=mList3.nodeCount(); i<n; ++i) mList3(i).getNodes(mList2);
956  for (size_t i=0, n=mList2.nodeCount(); i<n; ++i) mList2(i).getNodes(mList1);
957  for (size_t i=0, n=mList1.nodeCount(); i<n; ++i) mList1(i).getNodes(mList0);
958  }
959 
961  const RootNodeType& root() const { return mRoot; }
962 
964  Index64 nodeCount() const
965  {
966  return mList0.nodeCount() + mList1.nodeCount()
967  + mList2.nodeCount() + mList3.nodeCount();
968  }
969 
972  Index64 nodeCount(Index i) const
973  {
974  return i==0 ? mList0.nodeCount() : i==1 ? mList1.nodeCount() :
975  i==2 ? mList2.nodeCount() : i==3 ? mList3.nodeCount() : 0;
976  }
977 
978  template<typename NodeOp>
979  void foreachBottomUp(const NodeOp& op, bool threaded = true, size_t grainSize=1)
980  {
981  mList0.foreach(op, threaded, grainSize);
982  mList1.foreach(op, threaded, grainSize);
983  mList2.foreach(op, threaded, grainSize);
984  mList3.foreach(op, threaded, grainSize);
985  op(mRoot);
986  }
987 
988  template<typename NodeOp>
989  void foreachTopDown(const NodeOp& op, bool threaded = true, size_t grainSize=1)
990  {
991  op(mRoot);
992  mList3.foreach(op, threaded, grainSize);
993  mList2.foreach(op, threaded, grainSize);
994  mList1.foreach(op, threaded, grainSize);
995  mList0.foreach(op, threaded, grainSize);
996  }
997 
998  template<typename NodeOp>
999  void reduceBottomUp(NodeOp& op, bool threaded = true, size_t grainSize=1)
1000  {
1001  mList0.reduce(op, threaded, grainSize);
1002  mList1.reduce(op, threaded, grainSize);
1003  mList2.reduce(op, threaded, grainSize);
1004  mList3.reduce(op, threaded, grainSize);
1005  op(mRoot);
1006  }
1007 
1008  template<typename NodeOp>
1009  void reduceTopDown(NodeOp& op, bool threaded = true, size_t grainSize=1)
1010  {
1011  op(mRoot);
1012  mList3.reduce(op, threaded, grainSize);
1013  mList2.reduce(op, threaded, grainSize);
1014  mList1.reduce(op, threaded, grainSize);
1015  mList0.reduce(op, threaded, grainSize);
1016  }
1017 
1018 protected:
1019  using NodeT4 = RootNodeType;
1020  using NodeT3 = typename NodeT4::ChildNodeType; // upper level
1021  using NodeT2 = typename NodeT3::ChildNodeType; // upper mid level
1022  using NodeT1 = typename NodeT2::ChildNodeType; // lower mid level
1023  using NodeT0 = typename NodeT1::ChildNodeType; // lower level
1024 
1025  using ListT3 = NodeList<NodeT3>; // upper level of internal nodes
1026  using ListT2 = NodeList<NodeT2>; // upper mid level of internal nodes
1027  using ListT1 = NodeList<NodeT1>; // lower mid level of internal nodes
1028  using ListT0 = NodeList<NodeT0>; // lower level of internal nodes or leafs
1029 
1030  NodeT4& mRoot;
1031  ListT3 mList3;
1032  ListT2 mList2;
1033  ListT1 mList1;
1034  ListT0 mList0;
1035 
1036 private:
1037  NodeManager(const NodeManager&) {} // disallow copy-construction
1038 }; // NodeManager<4>
1039 
1040 } // namespace tree
1041 } // namespace OPENVDB_VERSION_NAME
1042 } // namespace openvdb
1043 
1044 #endif // OPENVDB_TREE_NODEMANAGER_HAS_BEEN_INCLUDED
1045 
1046 // Copyright (c) DreamWorks Animation LLC
1047 // All rights reserved. This software is distributed under the
1048 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )
bool operator!=(const Iterator &other) const
Definition: NodeManager.h:133
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:477
Index64 nodeCount() const
Definition: NodeManager.h:82
RootNodeType & mRoot
Definition: NodeManager.h:559
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:470
bool operator==(const Iterator &other) const
Definition: NodeManager.h:137
NodeT0 * value_type
Definition: NodeManager.h:71
Iterator begin() const
Definition: NodeManager.h:145
Index64 nodeCount(Index i) const
Return the number of cached nodes at level i, where 0 corresponds to the lowest level.
Definition: NodeManager.h:411
ListT mList
Definition: NodeManager.h:233
bool test() const
Return true if this iterator is not yet exhausted.
Definition: NodeManager.h:128
Iterator & operator++()
Advance to the next node.
Definition: NodeManager.h:119
void clear()
Clear all the cached tree nodes.
Definition: NodeManager.h:397
bool isValid() const
Definition: NodeManager.h:126
void reduceTopDown(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:551
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:401
NodeRange nodeRange(size_t grainsize=1) const
Return a TBB-compatible NodeRange.
Definition: NodeManager.h:163
This class caches tree nodes of a specific type in a linear array.
Definition: NodeManager.h:68
Index32 Index
Definition: Types.h:61
const RootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:404
Iterator end() const
Definition: NodeManager.h:147
const NodeList & nodeList() const
Definition: NodeManager.h:103
size_t size() const
Definition: NodeManager.h:99
NodeRange(size_t begin, size_t end, const NodeList &nodeList, size_t grainSize=1)
Definition: NodeManager.h:92
NodeT & operator*() const
Return a reference to the node to which this iterator is pointing.
Definition: NodeManager.h:121
NodeManager(TreeOrLeafManagerT &tree)
Definition: NodeManager.h:392
size_t pos() const
Return the index into the list of the current node.
Definition: NodeManager.h:125
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:128
void reduceBottomUp(NodeOp &op, bool threaded=true, size_t grainSize=1)
Threaded method that processes nodes with a user supplied functor.
Definition: NodeManager.h:544
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:645
Definition: Exceptions.h:40
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition: Platform.h:149
NodeT & operator()(size_t n) const
Definition: NodeManager.h:78
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:58
std::deque< value_type > ListT
Definition: NodeManager.h:72
Index64 nodeCount() const
Return the total number of cached nodes (excluding the root node)
Definition: NodeManager.h:407
const NodeRange & nodeRange() const
Definition: NodeManager.h:138
void push_back(NodeT *node)
Definition: NodeManager.h:76
uint64_t Index64
Definition: Types.h:60
Iterator(const NodeRange &range, size_t pos)
Definition: NodeManager.h:112
void reduce(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:176
NodeT * operator->() const
Return a pointer to the node to which this iterator is pointing.
Definition: NodeManager.h:123
NodeRange(NodeRange &r, tbb::split)
Definition: NodeManager.h:95
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:150
Definition: NodeManager.h:88
bool empty() const
Definition: NodeManager.h:105
void clear()
Definition: NodeManager.h:84
NodeManagerLink< typename RootNodeType::ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:560
NodeList()
Definition: NodeManager.h:74
typename TreeOrLeafManagerT::RootNodeType RootNodeType
Definition: NodeManager.h:389
virtual ~NodeManager()
Definition: NodeManager.h:394
bool is_divisible() const
Definition: NodeManager.h:107
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:180
void resize(size_t n)
Definition: NodeManager.h:86
bool empty() const
Return true if this iterator is exhausted.
Definition: NodeManager.h:132
size_t grainsize() const
Definition: NodeManager.h:101
NodeT *& operator[](size_t n)
Definition: NodeManager.h:80