OpenVDB  1.2.0
LeafManager.h
Go to the documentation of this file.
1 //
3 // Copyright (c) 2012-2013 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 //
41 
42 #ifndef OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
43 #define OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
44 
45 #include <boost/shared_ptr.hpp>
46 #include <boost/bind.hpp>
47 #include <boost/function.hpp>
48 #include <tbb/blocked_range.h>
49 #include <tbb/parallel_for.h>
50 #include <openvdb/Types.h>
51 #include "TreeIterator.h" // for CopyConstness
52 
53 namespace openvdb {
55 namespace OPENVDB_VERSION_NAME {
56 namespace tree {
57 
58 namespace leafmgr {
59 
61 template<typename TreeT> struct TreeTraits {
63  static const bool IsConstTree = false;
64  typedef typename TreeT::LeafIter LeafIterType;
65 };
66 template<typename TreeT> struct TreeTraits<const TreeT> {
67  static const bool IsConstTree = true;
68  typedef typename TreeT::LeafCIter LeafIterType;
69 };
71 
72 } // namespace leafmgr
73 
74 
77 template<typename ManagerT>
79 {
80  typedef typename ManagerT::RangeType RangeT;
81  typedef typename ManagerT::LeafType LeafT;
82  typedef typename ManagerT::BufferType BufT;
83 
84  static inline void doSwapLeafBuffer(const RangeT& r, size_t auxBufferIdx,
85  LeafT** leafs, BufT* bufs, size_t bufsPerLeaf)
86  {
87  for (size_t n = r.begin(), m = r.end(), N = bufsPerLeaf; n != m; ++n) {
88  leafs[n]->swap(bufs[n * N + auxBufferIdx]);
89  }
90  }
91 };
92 
93 
95 
96 
108 template<typename TreeT>
110 {
111 public:
112  typedef TreeT TreeType;
113  typedef typename TreeType::LeafNodeType NonConstLeafType;
116  typedef typename LeafType::Buffer NonConstBufferType;
118  typedef tbb::blocked_range<size_t> RangeType;//leaf index range
119 
120  static const bool IsConstTree = leafmgr::TreeTraits<TreeT>::IsConstTree;
121 
122  class LeafRange
123  {
124  public:
125  class Iterator
126  {
127  public:
128  Iterator(const LeafRange& range, size_t pos): mRange(range), mPos(pos)
129  {
130  assert(this->isValid());
131  }
133  Iterator& operator++() { ++mPos; return *this; }
135  LeafType& operator*() const { return mRange.mLeafManager.leaf(mPos); }
137  LeafType* operator->() const { return &(this->operator*()); }
140  BufferType& buffer(size_t bufferIdx)
141  {
142  return mRange.mLeafManager.getBuffer(mPos, bufferIdx);
143  }
145  size_t pos() const { return mPos; }
146  bool isValid() const { return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
148  bool test() const { return mPos < mRange.mEnd; }
150  operator bool() const { return this->test(); }
152  bool empty() const { return !this->test(); }
153  //bool operator<( const Iterator& other ) const { return mPos < other.mPos; }
154  void operator=( const Iterator& other) { mRange = other.mRange; mPos = other.mPos; }
155  bool operator!=(const Iterator& other) const
156  {
157  return (mPos != other.mPos) || (&mRange != &other.mRange);
158  }
159  bool operator==(const Iterator& other) const { return !(*this != other); }
160  const LeafRange& leafRange() const { return mRange; }
161 
162  private:
163  const LeafRange& mRange;
164  size_t mPos;
165  };// end Iterator
166 
167  LeafRange(size_t begin, size_t end, const LeafManager& leafManager, size_t grainSize=1):
168  mEnd(end), mBegin(begin), mGrainSize(grainSize), mLeafManager(leafManager) {}
169 
170  Iterator begin() const {return Iterator(*this, mBegin);}
171 
172  Iterator end() const {return Iterator(*this, mEnd);}
173 
174  size_t size() const { return mEnd - mBegin; }
175 
176  size_t grainsize() const { return mGrainSize; }
177 
178  const LeafManager& leafManager() const { return mLeafManager; }
179 
180  bool empty() const {return !(mBegin < mEnd);}
181 
182  bool is_divisible() const {return mGrainSize < this->size();}
183 
184  LeafRange(LeafRange& r, tbb::split):
185  mEnd(r.mEnd), mBegin(doSplit(r)), mGrainSize(r.mGrainSize),
186  mLeafManager(r.mLeafManager) {}
187 
188  private:
189  size_t mEnd, mBegin, mGrainSize;
190  const LeafManager& mLeafManager;
191 
192  static size_t doSplit(LeafRange& r)
193  {
194  assert(r.is_divisible());
195  size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
196  r.mEnd = middle;
197  return middle;
198  }
199  };// end of LeafRange
200 
203  LeafManager(TreeType& tree, size_t auxBuffersPerLeaf=0, bool serial=false):
204  mTree(&tree),
205  mLeafCount(0),
206  mAuxBufferCount(0),
207  mAuxBuffersPerLeaf(auxBuffersPerLeaf),
208  mLeafs(NULL),
209  mAuxBuffers(NULL),
210  mTask(0),
211  mIsMaster(true)
212  {
213  this->rebuild(serial);
214  }
215 
219  LeafManager(const LeafManager& other):
220  mTree(other.mTree),
221  mLeafCount(other.mLeafCount),
222  mAuxBufferCount(other.mAuxBufferCount),
223  mAuxBuffersPerLeaf(other.mAuxBuffersPerLeaf),
224  mLeafs(other.mLeafs),
225  mAuxBuffers(other.mAuxBuffers),
226  mTask(other.mTask),
227  mIsMaster(false)
228  {
229  }
230 
231  virtual ~LeafManager()
232  {
233  if (mIsMaster) {
234  delete [] mLeafs;
235  delete [] mAuxBuffers;
236  }
237  }
238 
244  void rebuild(bool serial=false)
245  {
246  this->initLeafArray();
247  this->initAuxBuffers(serial);
248  }
250  void rebuild(size_t auxBuffersPerLeaf, bool serial=false)
252  {
253  mAuxBuffersPerLeaf = auxBuffersPerLeaf;
254  this->rebuild(serial);
255  }
256  void rebuild(TreeType& tree, bool serial=false)
257  {
258  mTree = &tree;
259  this->rebuild(serial);
260  }
261  void rebuild(TreeType& tree, size_t auxBuffersPerLeaf, bool serial=false)
262  {
263  mTree = &tree;
264  mAuxBuffersPerLeaf = auxBuffersPerLeaf;
265  this->rebuild(serial);
266  }
268  void rebuildAuxBuffers(size_t auxBuffersPerLeaf, bool serial=false)
273  {
274  mAuxBuffersPerLeaf = auxBuffersPerLeaf;
275  this->initAuxBuffers(serial);
276  }
278  void removeAuxBuffers() { this->rebuildAuxBuffers(0); }
279 
282  {
283  this->removeAuxBuffers();
284  this->initLeafArray();
285  }
287  OPENVDB_DEPRECATED void rebuildLeafs() { this->rebuildLeafArray(); }
288 
290  size_t auxBufferCount() const { return mAuxBufferCount; }
292  size_t auxBuffersPerLeaf() const { return mAuxBuffersPerLeaf; }
293 
295  size_t leafCount() const { return mLeafCount; }
296 
298  TreeType& tree() { return *mTree; }
299 
301  bool isConstTree() const { return this->IsConstTree; }
302 
305  LeafType& leaf(size_t leafIdx) const { assert(leafIdx<mLeafCount); return *mLeafs[leafIdx]; }
306 
317  BufferType& getBuffer(size_t leafIdx, size_t bufferIdx) const
318  {
319  assert(leafIdx < mLeafCount);
320  assert(bufferIdx == 0 || bufferIdx - 1 < mAuxBuffersPerLeaf);
321  return bufferIdx == 0 ? mLeafs[leafIdx]->buffer()
322  : mAuxBuffers[leafIdx * mAuxBuffersPerLeaf + bufferIdx - 1];
323  }
324 
329  RangeType getRange(size_t grainsize = 1) const { return RangeType(0, mLeafCount, grainsize); }
330 
332  LeafRange leafRange(size_t grainsize = 1) const
333  {
334  return LeafRange(0, mLeafCount, *this, grainsize);
335  }
336 
346  bool swapLeafBuffer(size_t bufferIdx, bool serial = false)
347  {
348  if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf || this->isConstTree()) return false;
349  mTask = boost::bind(&LeafManager::doSwapLeafBuffer, _1, _2, bufferIdx - 1);
350  this->cook(serial ? 0 : 512);
351  return true;//success
352  }
357  bool swapBuffer(size_t bufferIdx1, size_t bufferIdx2, bool serial = false)
358  {
359  const size_t b1 = std::min(bufferIdx1, bufferIdx2);
360  const size_t b2 = std::max(bufferIdx1, bufferIdx2);
361  if (b1 == b2 || b2 > mAuxBuffersPerLeaf) return false;
362  if (b1 == 0) {
363  if (this->isConstTree()) return false;
364  mTask = boost::bind(&LeafManager::doSwapLeafBuffer, _1, _2, b2-1);
365  } else {
366  mTask = boost::bind(&LeafManager::doSwapAuxBuffer, _1, _2, b1-1, b2-1);
367  }
368  this->cook(serial ? 0 : 512);
369  return true;//success
370  }
371 
380  bool syncAuxBuffer(size_t bufferIdx, bool serial = false)
381  {
382  if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf) return false;
383  mTask = boost::bind(&LeafManager::doSyncAuxBuffer, _1, _2, bufferIdx - 1);
384  this->cook(serial ? 0 : 64);
385  return true;//success
386  }
387 
391  bool syncAllBuffers(bool serial = false)
392  {
393  switch (mAuxBuffersPerLeaf) {
394  case 0: return false;//nothing to do
395  case 1: mTask = boost::bind(&LeafManager::doSyncAllBuffers1, _1, _2); break;
396  case 2: mTask = boost::bind(&LeafManager::doSyncAllBuffers2, _1, _2); break;
397  default: mTask = boost::bind(&LeafManager::doSyncAllBuffersN, _1, _2); break;
398  }
399  this->cook(serial ? 0 : 64);
400  return true;//success
401  }
402 
460  template<typename LeafOp>
461  void foreach(const LeafOp& op, bool threaded = true)
462  {
463  LeafTransformer<LeafOp> transform(*this, op);
464  transform.run(threaded);
465  }
466 
468  // All methods below are for internal use only and should never be called directly
469 
471  void operator()(const RangeType& r) const
472  {
473  if (mTask) mTask(const_cast<LeafManager*>(this), r);
474  else OPENVDB_THROW(ValueError, "task is undefined");
475  }
476 
477 
478 
479 private:
480  void initLeafArray()
481  {
482  const size_t leafCount = mTree->leafCount();
483  if (leafCount != mLeafCount) {
484  delete [] mLeafs;
485  mLeafs = (leafCount == 0) ? NULL : new LeafType*[leafCount];
486  mLeafCount = leafCount;
487  }
488  LeafIterType iter = mTree->beginLeaf();
489  for (size_t n = 0; n != leafCount; ++n, ++iter) mLeafs[n] = iter.getLeaf();
490  }
491 
492  void initAuxBuffers(bool serial)
493  {
494  const size_t auxBufferCount = mLeafCount * mAuxBuffersPerLeaf;
495  if (auxBufferCount != mAuxBufferCount) {
496  delete [] mAuxBuffers;
497  mAuxBuffers = (auxBufferCount == 0) ? NULL : new NonConstBufferType[auxBufferCount];
498  mAuxBufferCount = auxBufferCount;
499  }
500  this->syncAllBuffers(serial);
501  }
502 
503  void cook(size_t grainsize)
504  {
505  if (grainsize>0) {
506  tbb::parallel_for(this->getRange(grainsize), *this);
507  } else {
508  (*this)(this->getRange());
509  }
510  }
511 
512  void doSwapLeafBuffer(const RangeType& r, size_t auxBufferIdx)
513  {
514  LeafManagerImpl<LeafManager>::doSwapLeafBuffer(
515  r, auxBufferIdx, mLeafs, mAuxBuffers, mAuxBuffersPerLeaf);
516  }
517 
518  void doSwapAuxBuffer(const RangeType& r, size_t auxBufferIdx1, size_t auxBufferIdx2)
519  {
520  for (size_t N = mAuxBuffersPerLeaf, n = N*r.begin(), m = N*r.end(); n != m; n+=N) {
521  mAuxBuffers[n + auxBufferIdx1].swap(mAuxBuffers[n + auxBufferIdx2]);
522  }
523  }
524 
525  void doSyncAuxBuffer(const RangeType& r, size_t auxBufferIdx)
526  {
527  for (size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
528  mAuxBuffers[n*N + auxBufferIdx] = mLeafs[n]->buffer();
529  }
530  }
531 
532  void doSyncAllBuffers1(const RangeType& r)
533  {
534  for (size_t n = r.begin(), m = r.end(); n != m; ++n) {
535  mAuxBuffers[n] = mLeafs[n]->buffer();
536  }
537  }
538 
539  void doSyncAllBuffers2(const RangeType& r)
540  {
541  for (size_t n = r.begin(), m = r.end(); n != m; ++n) {
542  const BufferType& leafBuffer = mLeafs[n]->buffer();
543  mAuxBuffers[2*n ] = leafBuffer;
544  mAuxBuffers[2*n+1] = leafBuffer;
545  }
546  }
547 
548  void doSyncAllBuffersN(const RangeType& r)
549  {
550  for (size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
551  const BufferType& leafBuffer = mLeafs[n]->buffer();
552  for (size_t i=n*N, j=i+N; i!=j; ++i) mAuxBuffers[i] = leafBuffer;
553  }
554  }
555 
558  template<typename LeafOp>
559  struct LeafTransformer
560  {
561  LeafTransformer(LeafManager& leafs, const LeafOp& leafOp)
562  : mLeafManager(&leafs), mLeafOp(leafOp) {}
563  void run(bool threaded = true)
564  {
565  if (threaded) {
566  tbb::parallel_for(mLeafManager->getRange(), *this);
567  } else {
568  (*this)(mLeafManager->getRange());
569  }
570  }
571  void operator()(const tbb::blocked_range<size_t>& range) const
572  {
573  for (size_t n = range.begin(); n < range.end(); ++n) {
574  mLeafOp(mLeafManager->leaf(n), n);
575  }
576  }
577  LeafManager* mLeafManager;
578  const LeafOp mLeafOp;
579  };
580 
581  typedef typename boost::function<void (LeafManager*, const RangeType&)> FuncType;
582 
583  TreeType* mTree;
584  size_t mLeafCount, mAuxBufferCount, mAuxBuffersPerLeaf;
585  LeafType** mLeafs;//array of LeafNode pointers
586  NonConstBufferType* mAuxBuffers;//array of auxiliary buffers
587  FuncType mTask;
588  const bool mIsMaster;
589 };//end of LeafManager class
590 
591 
592 // Partial specializations of LeafManager methods for const trees
593 template<typename TreeT>
594 struct LeafManagerImpl<LeafManager<const TreeT> >
595 {
597  typedef typename ManagerT::RangeType RangeT;
598  typedef typename ManagerT::LeafType LeafT;
599  typedef typename ManagerT::BufferType BufT;
600 
601  static inline void doSwapLeafBuffer(const RangeT&, size_t /*auxBufferIdx*/,
602  LeafT**, BufT*, size_t /*bufsPerLeaf*/)
603  {
604  // Buffers can't be swapped into const trees.
605  }
606 };
607 
608 } // namespace tree
609 } // namespace OPENVDB_VERSION_NAME
610 } // namespace openvdb
611 
612 #endif // OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
613 
614 // Copyright (c) 2012-2013 DreamWorks Animation LLC
615 // All rights reserved. This software is distributed under the
616 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )