HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
NodeManager.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2012-2018 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 //
29 ///////////////////////////////////////////////////////////////////////////
30 
31 /// @file tree/NodeManager.h
32 ///
33 /// @author Ken Museth
34 ///
35 /// @brief NodeManager produces linear arrays of all tree nodes
36 /// allowing for efficient threading and bottom-up processing.
37 ///
38 /// @note A NodeManager can be constructed from a Tree or LeafManager.
39 /// The latter is slightly more efficient since the cached leaf nodes will be reused.
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 
61 ////////////////////////////////////////
62 
63 
64 /// @brief This class caches tree nodes of a specific type in a linear array.
65 ///
66 /// @note It is for internal use and should rarely be used directly.
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;
118  /// Advance to the next node.
119  Iterator& operator++() { ++mPos; return *this; }
120  /// Return a reference to the node to which this iterator is pointing.
121  NodeT& operator*() const { return mRange.mNodeList(mPos); }
122  /// Return a pointer to the node to which this iterator is pointing.
123  NodeT* operator->() const { return &(this->operator*()); }
124  /// Return the index into the list of the current node.
125  size_t pos() const { return mPos; }
126  bool isValid() const { return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
127  /// Return @c true if this iterator is not yet exhausted.
128  bool test() const { return mPos < mRange.mEnd; }
129  /// Return @c true if this iterator is not yet exhausted.
130  operator bool() const { return this->test(); }
131  /// Return @c true if this iterator is exhausted.
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 
162  /// Return a TBB-compatible NodeRange.
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 
237 /////////////////////////////////////////////
238 
239 
240 /// @brief This class is a link in a chain that each caches tree nodes
241 /// of a specific type in a linear array.
242 ///
243 /// @note It is for internal use and should rarely be used directly.
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 
310 ////////////////////////////////////////
311 
312 
313 /// @private
314 /// @brief Specialization that terminates the chain of cached tree nodes
315 /// @note It is for internal use and should rarely be used directly.
316 template<typename NodeT>
317 class NodeManagerLink<NodeT, 0>
318 {
319 public:
320  NodeManagerLink() {}
321 
322  virtual ~NodeManagerLink() {}
323 
324  /// @brief Clear all the cached tree nodes
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 
374 ////////////////////////////////////////
375 
376 
377 /// @brief To facilitate threading over the nodes of a tree, cache
378 /// node pointers in linear arrays, one for each level of the tree.
379 ///
380 /// @details This implementation works with trees of any depth, but
381 /// optimized specializations are provided for the most typical tree depths.
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 
396  /// @brief Clear all the cached tree nodes
397  void clear() { mChain.clear(); }
398 
399  /// @brief Clear and recache all the tree nodes from the
400  /// tree. This is required if tree nodes have been added or removed.
402 
403  /// @brief Return a reference to the root node.
404  const RootNodeType& root() const { return mRoot; }
405 
406  /// @brief Return the total number of cached nodes (excluding the root node)
407  Index64 nodeCount() const { return mChain.nodeCount(); }
408 
409  /// @brief Return the number of cached nodes at level @a i, where
410  /// 0 corresponds to the lowest level.
411  Index64 nodeCount(Index i) const { return mChain.nodeCount(i); }
412 
413  //@{
414  /// @brief Threaded method that applies a user-supplied functor
415  /// to all the nodes in the tree.
416  ///
417  /// @param op user-supplied functor, see examples for interface details.
418  /// @param threaded optional toggle to disable threading, on by default.
419  /// @param grainSize optional parameter to specify the grainsize
420  /// for threading, one by default.
421  ///
422  /// @warning The functor object is deep-copied to create TBB tasks.
423  ///
424  /// @par Example:
425  /// @code
426  /// // Functor to offset all the inactive values of a tree. Note
427  /// // this implementation also illustrates how different
428  /// // computation can be applied to the different node types.
429  /// template<typename TreeType>
430  /// struct OffsetOp
431  /// {
432  /// using ValueT = typename TreeT::ValueType;
433  /// using RootT = typename TreeT::RootNodeType;
434  /// using LeafT = typename TreeT::LeafNodeType;
435  /// OffsetOp(const ValueT& v) : mOffset(v) {}
436  ///
437  /// // Processes the root node. Required by the NodeManager
438  /// void operator()(RootT& root) const
439  /// {
440  /// for (typename RootT::ValueOffIter i = root.beginValueOff(); i; ++i) *i += mOffset;
441  /// }
442  /// // Processes the leaf nodes. Required by the NodeManager
443  /// void operator()(LeafT& leaf) const
444  /// {
445  /// for (typename LeafT::ValueOffIter i = leaf.beginValueOff(); i; ++i) *i += mOffset;
446  /// }
447  /// // Processes the internal nodes. Required by the NodeManager
448  /// template<typename NodeT>
449  /// void operator()(NodeT& node) const
450  /// {
451  /// for (typename NodeT::ValueOffIter i = node.beginValueOff(); i; ++i) *i += mOffset;
452  /// }
453  /// private:
454  /// const ValueT mOffset;
455  /// };
456  ///
457  /// // usage:
458  /// OffsetOp<FloatTree> op(3.0f);
459  /// tree::NodeManager<FloatTree> nodes(tree);
460  /// nodes.foreachBottomUp(op);
461  ///
462  /// // or if a LeafManager already exists
463  /// using T = tree::LeafManager<FloatTree>;
464  /// OffsetOp<T> op(3.0f);
465  /// tree::NodeManager<T> nodes(leafManager);
466  /// nodes.foreachBottomUp(op);
467  ///
468  /// @endcode
469  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 
483  //@}
484 
485  //@{
486  /// @brief Threaded method that processes nodes with a user supplied functor
487  ///
488  /// @param op user-supplied functor, see examples for interface details.
489  /// @param threaded optional toggle to disable threading, on by default.
490  /// @param grainSize optional parameter to specify the grainsize
491  /// for threading, one by default.
492  ///
493  /// @warning The functor object is deep-copied to create TBB tasks.
494  ///
495  /// @par Example:
496  /// @code
497  /// // Functor to count nodes in a tree
498  /// template<typename TreeType>
499  /// struct NodeCountOp
500  /// {
501  /// NodeCountOp() : nodeCount(TreeType::DEPTH, 0), totalCount(0)
502  /// {
503  /// }
504  /// NodeCountOp(const NodeCountOp& other, tbb::split) :
505  /// nodeCount(TreeType::DEPTH, 0), totalCount(0)
506  /// {
507  /// }
508  /// void join(const NodeCountOp& other)
509  /// {
510  /// for (size_t i = 0; i < nodeCount.size(); ++i) {
511  /// nodeCount[i] += other.nodeCount[i];
512  /// }
513  /// totalCount += other.totalCount;
514  /// }
515  /// // do nothing for the root node
516  /// void operator()(const typename TreeT::RootNodeType& node)
517  /// {
518  /// }
519  /// // count the internal and leaf nodes
520  /// template<typename NodeT>
521  /// void operator()(const NodeT& node)
522  /// {
523  /// ++(nodeCount[NodeT::LEVEL]);
524  /// ++totalCount;
525  /// }
526  /// std::vector<openvdb::Index64> nodeCount;
527  /// openvdb::Index64 totalCount;
528  /// };
529  ///
530  /// // usage:
531  /// NodeCountOp<FloatTree> op;
532  /// tree::NodeManager<FloatTree> nodes(tree);
533  /// nodes.reduceBottomUp(op);
534  ///
535  /// // or if a LeafManager already exists
536  /// NodeCountOp<FloatTree> op;
537  /// using T = tree::LeafManager<FloatTree>;
538  /// T leafManager(tree);
539  /// tree::NodeManager<T> nodes(leafManager);
540  /// nodes.reduceBottomUp(op);
541  ///
542  /// @endcode
543  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  }
556  //@}
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 
567 ////////////////////////////////////////////
568 
569 
570 /// @private
571 /// Template specialization of the NodeManager with no caching of nodes
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 
583  /// @brief Clear all the cached tree nodes
584  void clear() {}
585 
586  /// @brief Clear and recache all the tree nodes from the
587  /// tree. This is required if tree nodes have been added or removed.
588  void rebuild() {}
589 
590  /// @brief Return a reference to the root node.
591  const RootNodeType& root() const { return mRoot; }
592 
593  /// @brief Return the total number of cached nodes (excluding the root node)
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:
612 
613 private:
614  NodeManager(const NodeManager&) {} // disallow copy-construction
615 }; // NodeManager<0>
616 
617 
618 ////////////////////////////////////////////
619 
620 
621 /// @private
622 /// Template specialization of the NodeManager with one level of nodes
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 
644  /// @brief Clear all the cached tree nodes
645  void clear() { mList0.clear(); }
646 
647  /// @brief Clear and recache all the tree nodes from the
648  /// tree. This is required if tree nodes have been added or removed.
649  void rebuild() { mList0.clear(); mRoot.getNodes(mList0); }
650 
651  /// @brief Return a reference to the root node.
652  const RootNodeType& root() const { return mRoot; }
653 
654  /// @brief Return the total number of cached nodes (excluding the root node)
655  Index64 nodeCount() const { return mList0.nodeCount(); }
656 
657  /// @brief Return the number of cached nodes at level @a i, where
658  /// 0 corresponds to the lowest level.
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 
702 ////////////////////////////////////////////
703 
704 
705 /// @private
706 /// Template specialization of the NodeManager with two levels of nodes
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 
730  /// @brief Clear all the cached tree nodes
731  void clear() { mList0.clear(); mList1.clear(); }
732 
733  /// @brief Clear and recache all the tree nodes from the
734  /// tree. This is required if tree nodes have been added or removed.
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 
742  /// @brief Return a reference to the root node.
743  const RootNodeType& root() const { return mRoot; }
744 
745  /// @brief Return the total number of cached nodes (excluding the root node)
746  Index64 nodeCount() const { return mList0.nodeCount() + mList1.nodeCount(); }
747 
748  /// @brief Return the number of cached nodes at level @a i, where
749  /// 0 corresponds to the lowest level.
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 
804 ////////////////////////////////////////////
805 
806 
807 /// @private
808 /// Template specialization of the NodeManager with three levels of nodes
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 
833  /// @brief Clear all the cached tree nodes
834  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); }
835 
836  /// @brief Clear and recache all the tree nodes from the
837  /// tree. This is required if tree nodes have been added or removed.
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 
846  /// @brief Return a reference to the root node.
847  const RootNodeType& root() const { return mRoot; }
848 
849  /// @brief Return the total number of cached nodes (excluding the root node)
850  Index64 nodeCount() const { return mList0.nodeCount()+mList1.nodeCount()+mList2.nodeCount(); }
851 
852  /// @brief Return the number of cached nodes at level @a i, where
853  /// 0 corresponds to the lowest level.
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 
916 ////////////////////////////////////////////
917 
918 
919 /// @private
920 /// Template specialization of the NodeManager with four levels of nodes
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 
946  /// @brief Clear all the cached tree nodes
947  void clear() { mList0.clear(); mList1.clear(); mList2.clear(); mList3.clear; }
948 
949  /// @brief Clear and recache all the tree nodes from the
950  /// tree. This is required if tree nodes have been added or removed.
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 
960  /// @brief Return a reference to the root node.
961  const RootNodeType& root() const { return mRoot; }
962 
963  /// @brief Return the total number of cached nodes (excluding the root node)
964  Index64 nodeCount() const
965  {
966  return mList0.nodeCount() + mList1.nodeCount()
967  + mList2.nodeCount() + mList3.nodeCount();
968  }
969 
970  /// @brief Return the number of cached nodes at level @a i, where
971  /// 0 corresponds to the lowest level.
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) 2012-2018 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/ )
NodeRange(size_t begin, size_t end, const NodeList &nodeList, size_t grainSize=1)
Definition: NodeManager.h:92
NodeT * operator->() const
Return a pointer to the node to which this iterator is pointing.
Definition: NodeManager.h:123
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
GLenum GLint * range
Definition: glcorearb.h:1924
Index64 nodeCount() const
Return the total number of cached nodes (excluding the root node)
Definition: NodeManager.h:407
NodeManagerLink< typename RootNodeType::ChildNodeType, LEVELS-1 > mChain
Definition: NodeManager.h:560
NodeT & operator*() const
Return a reference to the node to which this iterator is pointing.
Definition: NodeManager.h:121
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:189
void clear()
Clear all the cached tree nodes.
Definition: NodeManager.h:397
This class caches tree nodes of a specific type in a linear array.
Definition: NodeManager.h:68
png_uint_32 i
Definition: png.h:2877
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
GLdouble n
Definition: glcorearb.h:2007
void reduce(NodeOp &op, bool threaded=true, size_t grainSize=1)
Definition: NodeManager.h:176
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
size_t pos() const
Return the index into the list of the current node.
Definition: NodeManager.h:125
GLuint GLuint end
Definition: glcorearb.h:474
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
GA_API const UT_StringHolder transform
const RootNodeType & root() const
Return a reference to the root node.
Definition: NodeManager.h:404
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_BEGIN
Definition: Platform.h:129
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
bool empty() const
Return true if this iterator is exhausted.
Definition: NodeManager.h:132
#define OPENVDB_NO_UNREACHABLE_CODE_WARNING_END
Definition: Platform.h:130
GLboolean r
Definition: glcorearb.h:1221
typename TreeOrLeafManagerT::RootNodeType RootNodeType
Definition: NodeManager.h:389
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
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h:135
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
NodeRange nodeRange(size_t grainsize=1) const
Return a TBB-compatible NodeRange.
Definition: NodeManager.h:163
bool test() const
Return true if this iterator is not yet exhausted.
Definition: NodeManager.h:128