OpenVDB  1.1.0
LeafManager.h
Go to the documentation of this file.
1 
2 //
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 
62 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 
105 template<typename TreeT>
107 {
108 public:
109  typedef TreeT TreeType;
110  typedef typename TreeType::LeafNodeType NonConstLeafType;
113  typedef typename LeafType::Buffer NonConstBufferType;
115  typedef tbb::blocked_range<size_t> RangeType;//leaf index range
116 
117  static const bool IsConstTree = leafmgr::TreeTraits<TreeT>::IsConstTree;
118 
119  class LeafRange
120  {
121  public:
122  class Iterator
123  {
124  public:
125  Iterator(const LeafRange& range, size_t pos): mRange(range), mPos(pos)
126  {
127  assert(this->isValid());
128  }
130  Iterator& operator++() { ++mPos; return *this; }
132  LeafType& operator*() const { return mRange.mLeafManager.leaf(mPos); }
134  LeafType* operator->() const { return &(this->operator*()); }
137  BufferType& buffer(size_t bufferIdx)
138  {
139  return mRange.mLeafManager.getBuffer(mPos, bufferIdx);
140  }
142  size_t pos() const { return mPos; }
143  bool isValid() const { return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
145  operator bool() const { return mPos < mRange.mEnd; }
146  //bool operator<( const Iterator& other ) const { return mPos < other.mPos; }
147  void operator=( const Iterator& other) { mRange = other.mRange; mPos = other.mPos; }
148  bool operator!=(const Iterator& other) const
149  {
150  return (mPos != other.mPos) || (&mRange != &other.mRange);
151  }
152  bool operator==(const Iterator& other) const { return !(*this != other); }
153  const LeafRange& leafRange() const { return mRange; }
154 
155  private:
156  const LeafRange& mRange;
157  size_t mPos;
158  };// end Iterator
159 
160  LeafRange(size_t begin, size_t end, const LeafManager& leafManager, size_t grainSize=1):
161  mEnd(end), mBegin(begin), mGrainSize(grainSize), mLeafManager(leafManager) {}
162 
163  Iterator begin() const {return Iterator(*this, mBegin);}
164 
165  Iterator end() const {return Iterator(*this, mEnd);}
166 
167  size_t size() const { return mEnd - mBegin; }
168 
169  size_t grainsize() const { return mGrainSize; }
170 
171  const LeafManager& leafManager() const { return mLeafManager; }
172 
173  bool empty() const {return !(mBegin < mEnd);}
174 
175  bool is_divisible() const {return mGrainSize < this->size();}
176 
177  LeafRange(LeafRange& r, tbb::split):
178  mEnd(r.mEnd), mBegin(doSplit(r)), mGrainSize(r.mGrainSize),
179  mLeafManager(r.mLeafManager) {}
180 
181  private:
182  size_t mEnd, mBegin, mGrainSize;
183  const LeafManager& mLeafManager;
184 
185  static size_t doSplit(LeafRange& r)
186  {
187  assert(r.is_divisible());
188  size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
189  r.mEnd = middle;
190  return middle;
191  }
192  };// end of LeafRange
193 
196  LeafManager(TreeType& tree, size_t auxBuffersPerLeaf=0, bool serial=false):
197  mTree(&tree),
198  mLeafCount(0),
199  mAuxBufferCount(0),
200  mAuxBuffersPerLeaf(auxBuffersPerLeaf),
201  mLeafs(NULL),
202  mAuxBuffers(NULL),
203  mTask(0),
204  mIsMaster(true)
205  {
206  this->rebuild(serial);
207  }
208 
212  LeafManager(const LeafManager& other):
213  mTree(other.mTree),
214  mLeafCount(other.mLeafCount),
215  mAuxBufferCount(other.mAuxBufferCount),
216  mAuxBuffersPerLeaf(other.mAuxBuffersPerLeaf),
217  mLeafs(other.mLeafs),
218  mAuxBuffers(other.mAuxBuffers),
219  mTask(other.mTask),
220  mIsMaster(false)
221  {
222  }
223 
224  virtual ~LeafManager()
225  {
226  if (mIsMaster) {
227  delete [] mLeafs;
228  delete [] mAuxBuffers;
229  }
230  }
231 
237  void rebuild(bool serial=false)
238  {
239  this->initLeafArray();
240  this->initAuxBuffers(serial);
241  }
243 
244  void rebuild(size_t auxBuffersPerLeaf, bool serial=false)
245  {
246  mAuxBuffersPerLeaf = auxBuffersPerLeaf;
247  this->rebuild(serial);
248  }
249  void rebuild(TreeType& tree, bool serial=false)
250  {
251  mTree = &tree;
252  this->rebuild(serial);
253  }
254  void rebuild(TreeType& tree, size_t auxBuffersPerLeaf, bool serial=false)
255  {
256  mTree = &tree;
257  mAuxBuffersPerLeaf = auxBuffersPerLeaf;
258  this->rebuild(serial);
259  }
261 
262 
263 
264 
265  void rebuildAuxBuffers(size_t auxBuffersPerLeaf, bool serial=false)
266  {
267  mAuxBuffersPerLeaf = auxBuffersPerLeaf;
268  this->initAuxBuffers(serial);
269  }
271  void removeAuxBuffers() { this->rebuildAuxBuffers(0); }
272 
274  void rebuildLeafArray()
275  {
276  this->removeAuxBuffers();
277  this->initLeafArray();
278  }
280  OPENVDB_DEPRECATED void rebuildLeafs() { this->rebuildLeafArray(); }
281 
283  size_t auxBufferCount() const { return mAuxBufferCount; }
285  size_t auxBuffersPerLeaf() const { return mAuxBuffersPerLeaf; }
286 
288  size_t leafCount() const { return mLeafCount; }
289 
291  TreeType& tree() { return *mTree; }
292 
294  bool isConstTree() const { return this->IsConstTree; }
295 
298  LeafType& leaf(size_t leafIdx) const { assert(leafIdx<mLeafCount); return *mLeafs[leafIdx]; }
299 
310  BufferType& getBuffer(size_t leafIdx, size_t bufferIdx) const
311  {
312  assert(leafIdx < mLeafCount);
313  assert(bufferIdx == 0 || bufferIdx - 1 < mAuxBuffersPerLeaf);
314  return bufferIdx == 0 ? mLeafs[leafIdx]->buffer()
315  : mAuxBuffers[leafIdx * mAuxBuffersPerLeaf + bufferIdx - 1];
316  }
317 
322  RangeType getRange(size_t grainsize = 1) const { return RangeType(0, mLeafCount, grainsize); }
323 
325  LeafRange leafRange(size_t grainsize = 1) const
326  {
327  return LeafRange(0, mLeafCount, *this, grainsize);
328  }
329 
339  bool swapLeafBuffer(size_t bufferIdx, bool serial = false)
340  {
341  if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf || this->isConstTree()) return false;
342  mTask = boost::bind(&LeafManager::doSwapLeafBuffer, _1, _2, bufferIdx - 1);
343  this->cook(serial ? 0 : 512);
344  return true;//success
345  }
350  bool swapBuffer(size_t bufferIdx1, size_t bufferIdx2, bool serial = false)
351  {
352  const size_t b1 = std::min(bufferIdx1, bufferIdx2);
353  const size_t b2 = std::max(bufferIdx1, bufferIdx2);
354  if (b1 == b2 || b2 > mAuxBuffersPerLeaf) return false;
355  if (b1 == 0) {
356  if (this->isConstTree()) return false;
357  mTask = boost::bind(&LeafManager::doSwapLeafBuffer, _1, _2, b2-1);
358  } else {
359  mTask = boost::bind(&LeafManager::doSwapAuxBuffer, _1, _2, b1-1, b2-1);
360  }
361  this->cook(serial ? 0 : 512);
362  return true;//success
363  }
364 
373  bool syncAuxBuffer(size_t bufferIdx, bool serial = false)
374  {
375  if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf) return false;
376  mTask = boost::bind(&LeafManager::doSyncAuxBuffer, _1, _2, bufferIdx - 1);
377  this->cook(serial ? 0 : 64);
378  return true;//success
379  }
380 
384  bool syncAllBuffers(bool serial = false)
385  {
386  switch (mAuxBuffersPerLeaf) {
387  case 0: return false;//nothing to do
388  case 1: mTask = boost::bind(&LeafManager::doSyncAllBuffers1, _1, _2); break;
389  case 2: mTask = boost::bind(&LeafManager::doSyncAllBuffers2, _1, _2); break;
390  default: mTask = boost::bind(&LeafManager::doSyncAllBuffersN, _1, _2); break;
391  }
392  this->cook(serial ? 0 : 64);
393  return true;//success
394  }
395 
397  // All methods below are for internal use only and should never be called directly
398 
400  void operator()(const RangeType& r) const
401  {
402  if (mTask) mTask(const_cast<LeafManager*>(this), r);
403  else OPENVDB_THROW(ValueError, "task is undefined");
404  }
405 
406 private:
407  void initLeafArray()
408  {
409  const size_t leafCount = mTree->leafCount();
410  if (leafCount != mLeafCount) {
411  delete [] mLeafs;
412  mLeafs = (leafCount == 0) ? NULL : new LeafType*[leafCount];
413  mLeafCount = leafCount;
414  }
415  LeafIterType iter = mTree->beginLeaf();
416  for (size_t n = 0; n != leafCount; ++n, ++iter) mLeafs[n] = iter.getLeaf();
417  }
418 
419  void initAuxBuffers(bool serial)
420  {
421  const size_t auxBufferCount = mLeafCount * mAuxBuffersPerLeaf;
422  if (auxBufferCount != mAuxBufferCount) {
423  delete [] mAuxBuffers;
424  mAuxBuffers = (auxBufferCount == 0) ? NULL : new NonConstBufferType[auxBufferCount];
425  mAuxBufferCount = auxBufferCount;
426  }
427  this->syncAllBuffers(serial);
428  }
429 
430  void cook(size_t grainsize)
431  {
432  if (grainsize>0) {
433  tbb::parallel_for(this->getRange(grainsize), *this);
434  } else {
435  (*this)(this->getRange());
436  }
437  }
438 
439  void doSwapLeafBuffer(const RangeType& r, size_t auxBufferIdx)
440  {
441  LeafManagerImpl<LeafManager>::doSwapLeafBuffer(
442  r, auxBufferIdx, mLeafs, mAuxBuffers, mAuxBuffersPerLeaf);
443  }
444 
445  void doSwapAuxBuffer(const RangeType& r, size_t auxBufferIdx1, size_t auxBufferIdx2)
446  {
447  for (size_t N = mAuxBuffersPerLeaf, n = N*r.begin(), m = N*r.end(); n != m; n+=N) {
448  mAuxBuffers[n + auxBufferIdx1].swap(mAuxBuffers[n + auxBufferIdx2]);
449  }
450  }
451 
452  void doSyncAuxBuffer(const RangeType& r, size_t auxBufferIdx)
453  {
454  for (size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
455  mAuxBuffers[n*N + auxBufferIdx] = mLeafs[n]->buffer();
456  }
457  }
458 
459  void doSyncAllBuffers1(const RangeType& r)
460  {
461  for (size_t n = r.begin(), m = r.end(); n != m; ++n) {
462  mAuxBuffers[n] = mLeafs[n]->buffer();
463  }
464  }
465 
466  void doSyncAllBuffers2(const RangeType& r)
467  {
468  for (size_t n = r.begin(), m = r.end(); n != m; ++n) {
469  const BufferType& leafBuffer = mLeafs[n]->buffer();
470  mAuxBuffers[2*n ] = leafBuffer;
471  mAuxBuffers[2*n+1] = leafBuffer;
472  }
473  }
474 
475  void doSyncAllBuffersN(const RangeType& r)
476  {
477  for (size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
478  const BufferType& leafBuffer = mLeafs[n]->buffer();
479  for (size_t i=n*N, j=i+N; i!=j; ++i) mAuxBuffers[i] = leafBuffer;
480  }
481  }
482 
483  typedef typename boost::function<void (LeafManager*, const RangeType&)> FuncType;
484 
485  TreeType* mTree;
486  size_t mLeafCount, mAuxBufferCount, mAuxBuffersPerLeaf;
487  LeafType** mLeafs;//array of LeafNode pointers
488  NonConstBufferType* mAuxBuffers;//array of auxiliary buffers
489  FuncType mTask;
490  const bool mIsMaster;
491 };//end of LeafManager class
492 
493 
494 // Partial specializations of LeafManager methods for const trees
495 template<typename TreeT>
496 struct LeafManagerImpl<LeafManager<const TreeT> >
497 {
499  typedef typename ManagerT::RangeType RangeT;
500  typedef typename ManagerT::LeafType LeafT;
501  typedef typename ManagerT::BufferType BufT;
502 
503  static inline void doSwapLeafBuffer(const RangeT&, size_t /*auxBufferIdx*/,
504  LeafT**, BufT*, size_t /*bufsPerLeaf*/)
505  {
506  // Buffers can't be swapped into const trees.
507  }
508 };
509 
510 } // namespace tree
511 } // namespace OPENVDB_VERSION_NAME
512 } // namespace openvdb
513 
514 #endif // OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
515 
516 // Copyright (c) 2012-2013 DreamWorks Animation LLC
517 // All rights reserved. This software is distributed under the
518 // Mozilla Public License 2.0 ( http://www.mozilla.org/MPL/2.0/ )