42 #ifndef OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
43 #define OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
45 #include <boost/shared_ptr.hpp>
46 #include <boost/bind.hpp>
47 #include <boost/function.hpp>
48 #include <boost/mpl/if.hpp>
49 #include <boost/type_traits/is_const.hpp>
50 #include <boost/type_traits/is_pointer.hpp>
51 #include <boost/type_traits/is_same.hpp>
52 #include <boost/type_traits/remove_pointer.hpp>
53 #include <tbb/blocked_range.h>
54 #include <tbb/parallel_for.h>
68 static const bool IsConstTree =
false;
71 template<
typename TreeT>
struct TreeTraits<const TreeT> {
72 static const bool IsConstTree =
true;
82 template<
typename ManagerT>
85 typedef typename ManagerT::RangeType
RangeT;
86 typedef typename ManagerT::LeafType
LeafT;
87 typedef typename ManagerT::BufferType
BufT;
90 LeafT** leafs, BufT* bufs,
size_t bufsPerLeaf)
92 for (
size_t n = r.begin(), m = r.end(), N = bufsPerLeaf; n != m; ++n) {
93 leafs[n]->swap(bufs[n * N + auxBufferIdx]);
113 template<
typename TreeT>
139 assert(this->isValid());
143 mRange = other.mRange; mPos = other.mPos;
return *
this;
148 LeafType&
operator*()
const {
return mRange.mLeafManager.leaf(mPos); }
155 return mRange.mLeafManager.getBuffer(mPos, bufferIdx);
158 size_t pos()
const {
return mPos; }
159 bool isValid()
const {
return mPos>=mRange.mBegin && mPos<=mRange.mEnd; }
161 bool test()
const {
return mPos < mRange.mEnd; }
163 operator bool()
const {
return this->test(); }
165 bool empty()
const {
return !this->test(); }
168 return (mPos != other.mPos) || (&mRange != &other.mRange);
179 mEnd(end), mBegin(begin), mGrainSize(grainSize), mLeafManager(leafManager) {}
185 size_t size()
const {
return mEnd - mBegin; }
191 bool empty()
const {
return !(mBegin < mEnd);}
196 mEnd(r.mEnd), mBegin(doSplit(r)), mGrainSize(r.mGrainSize),
197 mLeafManager(r.mLeafManager) {}
200 size_t mEnd, mBegin, mGrainSize;
206 size_t middle = r.mBegin + (r.mEnd - r.mBegin) / 2u;
214 LeafManager(TreeType& tree,
size_t auxBuffersPerLeaf=0,
bool serial=
false):
218 mAuxBuffersPerLeaf(auxBuffersPerLeaf),
224 this->rebuild(serial);
232 mLeafCount(other.mLeafCount),
233 mAuxBufferCount(other.mAuxBufferCount),
234 mAuxBuffersPerLeaf(other.mAuxBuffersPerLeaf),
235 mLeafs(other.mLeafs),
236 mAuxBuffers(other.mAuxBuffers),
246 delete [] mAuxBuffers;
257 this->initLeafArray();
258 this->initAuxBuffers(serial);
261 void rebuild(
size_t auxBuffersPerLeaf,
bool serial=
false)
264 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
265 this->rebuild(serial);
267 void rebuild(TreeType& tree,
bool serial=
false)
270 this->rebuild(serial);
272 void rebuild(TreeType& tree,
size_t auxBuffersPerLeaf,
bool serial=
false)
275 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
276 this->rebuild(serial);
279 void rebuildAuxBuffers(
size_t auxBuffersPerLeaf,
bool serial=
false)
285 mAuxBuffersPerLeaf = auxBuffersPerLeaf;
286 this->initAuxBuffers(serial);
294 this->removeAuxBuffers();
295 this->initLeafArray();
307 const TreeType&
tree()
const {
return *mTree; }
310 TreeType&
tree() {
return *mTree; }
313 const RootNodeType&
root()
const {
return mTree->root(); }
316 RootNodeType&
root() {
return mTree->root(); }
323 LeafType&
leaf(
size_t leafIdx)
const { assert(leafIdx<mLeafCount);
return *mLeafs[leafIdx]; }
335 BufferType&
getBuffer(
size_t leafIdx,
size_t bufferIdx)
const
337 assert(leafIdx < mLeafCount);
338 assert(bufferIdx == 0 || bufferIdx - 1 < mAuxBuffersPerLeaf);
339 return bufferIdx == 0 ? mLeafs[leafIdx]->buffer()
340 : mAuxBuffers[leafIdx * mAuxBuffersPerLeaf + bufferIdx - 1];
347 RangeType
getRange(
size_t grainsize = 1)
const {
return RangeType(0, mLeafCount, grainsize); }
352 return LeafRange(0, mLeafCount, *
this, grainsize);
366 if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf || this->isConstTree())
return false;
367 mTask = boost::bind(&LeafManager::doSwapLeafBuffer, _1, _2, bufferIdx - 1);
368 this->cook(serial ? 0 : 512);
375 bool swapBuffer(
size_t bufferIdx1,
size_t bufferIdx2,
bool serial =
false)
377 const size_t b1 =
std::min(bufferIdx1, bufferIdx2);
378 const size_t b2 =
std::max(bufferIdx1, bufferIdx2);
379 if (b1 == b2 || b2 > mAuxBuffersPerLeaf)
return false;
381 if (this->isConstTree())
return false;
382 mTask = boost::bind(&LeafManager::doSwapLeafBuffer, _1, _2, b2-1);
384 mTask = boost::bind(&LeafManager::doSwapAuxBuffer, _1, _2, b1-1, b2-1);
386 this->cook(serial ? 0 : 512);
400 if (bufferIdx == 0 || bufferIdx > mAuxBuffersPerLeaf)
return false;
401 mTask = boost::bind(&LeafManager::doSyncAuxBuffer, _1, _2, bufferIdx - 1);
402 this->cook(serial ? 0 : 64);
411 switch (mAuxBuffersPerLeaf) {
412 case 0:
return false;
413 case 1: mTask = boost::bind(&LeafManager::doSyncAllBuffers1, _1, _2);
break;
414 case 2: mTask = boost::bind(&LeafManager::doSyncAllBuffers2, _1, _2);
break;
415 default: mTask = boost::bind(&LeafManager::doSyncAllBuffersN, _1, _2);
break;
417 this->cook(serial ? 0 : 64);
480 template<
typename LeafOp>
481 void foreach(
const LeafOp& op,
bool threaded =
true,
size_t grainSize=1)
483 LeafTransformer<LeafOp> transform(op);
484 transform.run(this->leafRange(grainSize), threaded);
488 template<
typename ArrayT>
491 typedef typename ArrayT::value_type T;
492 BOOST_STATIC_ASSERT(boost::is_pointer<T>::value);
493 typedef typename boost::mpl::if_<boost::is_const<typename boost::remove_pointer<T>::type>,
494 const LeafType, LeafType>::type LeafT;
497 if (boost::is_same<T, LeafT*>::value) {
498 array.resize(mLeafCount);
499 for (
size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]);
501 mTree->getNodes(array);
506 template<
typename ArrayT>
509 typedef typename ArrayT::value_type T;
510 BOOST_STATIC_ASSERT(boost::is_pointer<T>::value);
511 BOOST_STATIC_ASSERT(boost::is_const<
typename boost::remove_pointer<T>::type>::value);
514 if (boost::is_same<T, const LeafType*>::value) {
515 array.resize(mLeafCount);
516 for (
size_t i=0; i<mLeafCount; ++i) array[i] = reinterpret_cast<T>(mLeafs[i]);
518 mTree->getNodes(array);
529 if (mTask) mTask(const_cast<LeafManager*>(
this), r);
541 typedef LeafType* value_type;
543 MyArray(value_type* array) : ptr(array) {}
544 void push_back(value_type leaf) { *ptr++ = leaf; }
549 const size_t leafCount = mTree->leafCount();
550 if (leafCount != mLeafCount) {
552 mLeafs = (leafCount == 0) ? NULL :
new LeafType*[leafCount];
553 mLeafCount = leafCount;
559 void initAuxBuffers(
bool serial)
561 const size_t auxBufferCount = mLeafCount * mAuxBuffersPerLeaf;
562 if (auxBufferCount != mAuxBufferCount) {
563 delete [] mAuxBuffers;
564 mAuxBuffers = (auxBufferCount == 0) ? NULL :
new NonConstBufferType[auxBufferCount];
565 mAuxBufferCount = auxBufferCount;
567 this->syncAllBuffers(serial);
570 void cook(
size_t grainsize)
573 tbb::parallel_for(this->getRange(grainsize), *
this);
575 (*this)(this->getRange());
579 void doSwapLeafBuffer(
const RangeType& r,
size_t auxBufferIdx)
581 LeafManagerImpl<LeafManager>::doSwapLeafBuffer(
582 r, auxBufferIdx, mLeafs, mAuxBuffers, mAuxBuffersPerLeaf);
585 void doSwapAuxBuffer(
const RangeType& r,
size_t auxBufferIdx1,
size_t auxBufferIdx2)
587 for (
size_t N = mAuxBuffersPerLeaf, n = N*r.begin(), m = N*r.end(); n != m; n+=N) {
588 mAuxBuffers[n + auxBufferIdx1].swap(mAuxBuffers[n + auxBufferIdx2]);
592 void doSyncAuxBuffer(
const RangeType& r,
size_t auxBufferIdx)
594 for (
size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
595 mAuxBuffers[n*N + auxBufferIdx] = mLeafs[n]->buffer();
599 void doSyncAllBuffers1(
const RangeType& r)
601 for (
size_t n = r.begin(), m = r.end(); n != m; ++n) {
602 mAuxBuffers[n] = mLeafs[n]->buffer();
606 void doSyncAllBuffers2(
const RangeType& r)
608 for (
size_t n = r.begin(), m = r.end(); n != m; ++n) {
609 const BufferType& leafBuffer = mLeafs[n]->buffer();
610 mAuxBuffers[2*n ] = leafBuffer;
611 mAuxBuffers[2*n+1] = leafBuffer;
615 void doSyncAllBuffersN(
const RangeType& r)
617 for (
size_t n = r.begin(), m = r.end(), N = mAuxBuffersPerLeaf; n != m; ++n) {
618 const BufferType& leafBuffer = mLeafs[n]->buffer();
619 for (
size_t i=n*N, j=i+N; i!=j; ++i) mAuxBuffers[i] = leafBuffer;
625 template<
typename LeafOp>
626 struct LeafTransformer
628 LeafTransformer(
const LeafOp& leafOp) : mLeafOp(leafOp) {}
629 void run(
const LeafRange& range,
bool threaded =
true)
631 threaded ? tbb::parallel_for(range, *
this) : (*this)(range);
633 void operator()(
const LeafRange& range)
const
635 for (
typename LeafRange::Iterator it = range.begin(); it; ++it) mLeafOp(*it, it.pos());
637 const LeafOp mLeafOp;
640 typedef typename boost::function<void (LeafManager*, const RangeType&)> FuncType;
643 size_t mLeafCount, mAuxBufferCount, mAuxBuffersPerLeaf;
645 NonConstBufferType* mAuxBuffers;
647 const bool mIsMaster;
652 template<
typename TreeT>
661 LeafT**, BufT*,
size_t )
671 #endif // OPENVDB_TREE_LEAFMANAGER_HAS_BEEN_INCLUDED
Mat3< typename promote< T0, T1 >::type > operator*(const Mat3< T0 > &m0, const Mat3< T1 > &m1)
Matrix multiplication.
Definition: Mat3.h:608
LeafRange(size_t begin, size_t end, const LeafManager &leafManager, size_t grainSize=1)
Definition: LeafManager.h:178
bool operator!=(const Iterator &other) const
Definition: LeafManager.h:166
Index32 Index
Definition: Types.h:58
size_t auxBuffersPerLeaf() const
Return the number of auxiliary buffers per leaf node.
Definition: LeafManager.h:301
BufferType & getBuffer(size_t leafIdx, size_t bufferIdx) const
Return the leaf or auxiliary buffer for the leaf node at index leafIdx. If bufferIdx is zero...
Definition: LeafManager.h:335
BufferType & buffer(size_t bufferIdx)
Return the nth buffer for the leaf node to which this iterator is pointing, where n = bufferIdx and n...
Definition: LeafManager.h:153
bool test() const
Return true if this iterator is not yet exhausted.
Definition: LeafManager.h:161
Useful traits for Tree types.
Definition: LeafManager.h:67
ManagerT::BufferType BufT
Definition: LeafManager.h:87
Definition: Exceptions.h:88
bool syncAllBuffers(bool serial=false)
Sync up all auxiliary buffers with their corresponding leaf node buffers.
Definition: LeafManager.h:409
bool empty() const
Definition: LeafManager.h:191
LeafType * operator->() const
Return a pointer to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:150
#define OPENVDB_THROW(exception, message)
Definition: Exceptions.h:97
LeafRange leafRange(size_t grainsize=1) const
Return a TBB-compatible LeafRange.
Definition: LeafManager.h:350
TreeT::LeafCIter LeafIterType
Definition: LeafManager.h:73
void rebuildLeafArray()
Remove the auxiliary buffers and rebuild the leaf array.
Definition: LeafManager.h:292
This class manages a linear array of pointers to a given tree's leaf nodes, as well as optional auxil...
Definition: LeafManager.h:114
size_t auxBufferCount() const
Return the total number of allocated auxiliary buffers.
Definition: LeafManager.h:299
LeafType::Buffer NonConstBufferType
Definition: LeafManager.h:124
Iterator & operator++()
Advance to the next leaf node.
Definition: LeafManager.h:146
const LeafManager & leafManager() const
Definition: LeafManager.h:189
boost::remove_const< ToType >::type Type
Definition: TreeIterator.h:66
LeafManager(TreeType &tree, size_t auxBuffersPerLeaf=0, bool serial=false)
Constructor from a tree reference and an auxiliary buffer count (default is no auxiliary buffers) ...
Definition: LeafManager.h:214
ManagerT::RangeType RangeT
Definition: LeafManager.h:656
bool swapLeafBuffer(size_t bufferIdx, bool serial=false)
Swap each leaf node's buffer with the nth corresponding auxiliary buffer, where n = bufferIdx...
Definition: LeafManager.h:364
Iterator & operator=(const Iterator &other)
Definition: LeafManager.h:141
Iterator end() const
Definition: LeafManager.h:183
LeafManager< const TreeT > ManagerT
Definition: LeafManager.h:655
const LeafRange & leafRange() const
Definition: LeafManager.h:171
Iterator begin() const
Definition: LeafManager.h:181
leafmgr::TreeTraits< TreeT >::LeafIterType LeafIterType
Definition: LeafManager.h:123
void getNodes(ArrayT &array) const
Definition: LeafManager.h:507
void rebuild(bool serial=false)
(Re)initialize by resizing (if necessary) and repopulating the leaf array and by deleting existing au...
Definition: LeafManager.h:255
LeafType & leaf(size_t leafIdx) const
Return a pointer to the leaf node at index leafIdx in the array.
Definition: LeafManager.h:323
LeafType & operator*() const
Return a reference to the leaf node to which this iterator is pointing.
Definition: LeafManager.h:148
ManagerT::RangeType RangeT
Definition: LeafManager.h:85
size_t pos() const
Return the index into the leaf array of the current leaf node.
Definition: LeafManager.h:158
#define OPENVDB_VERSION_NAME
Definition: version.h:43
void rebuild(TreeType &tree, size_t auxBuffersPerLeaf, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
Definition: LeafManager.h:272
tbb::blocked_range< size_t > RangeType
Definition: LeafManager.h:126
const TreeType & tree() const
Return a const reference to tree associated with this manager.
Definition: LeafManager.h:307
TreeT TreeType
Definition: LeafManager.h:117
ManagerT::LeafType LeafT
Definition: LeafManager.h:657
RootNodeType & root()
Return a reference to the root node associated with this manager.
Definition: LeafManager.h:316
bool isValid() const
Definition: LeafManager.h:159
bool empty() const
Return true if this iterator is exhausted.
Definition: LeafManager.h:165
Definition: Exceptions.h:39
bool syncAuxBuffer(size_t bufferIdx, bool serial=false)
Sync up the specified auxiliary buffer with the corresponding leaf node buffer.
Definition: LeafManager.h:398
void rebuild(TreeType &tree, bool serial=false)
Repopulate the leaf array and delete and reallocate auxiliary buffers.
Definition: LeafManager.h:267
size_t grainsize() const
Definition: LeafManager.h:187
size_t leafCount() const
Return the number of leaf nodes.
Definition: LeafManager.h:304
CopyConstness< TreeType, NonConstBufferType >::Type BufferType
Definition: LeafManager.h:125
LeafManager(const LeafManager &other)
Definition: LeafManager.h:230
TreeT::LeafIter LeafIterType
Definition: LeafManager.h:69
TreeT::ValueType ValueType
Definition: LeafManager.h:118
bool swapBuffer(size_t bufferIdx1, size_t bufferIdx2, bool serial=false)
Swap any two buffers for each leaf node.
Definition: LeafManager.h:375
virtual ~LeafManager()
Definition: LeafManager.h:242
size_t size() const
Definition: LeafManager.h:185
static void doSwapLeafBuffer(const RangeT &, size_t, LeafT **, BufT *, size_t)
Definition: LeafManager.h:660
ManagerT::BufferType BufT
Definition: LeafManager.h:658
TreeType & tree()
Return a reference to the tree associated with this manager.
Definition: LeafManager.h:310
bool is_divisible() const
Definition: LeafManager.h:193
LeafRange(LeafRange &r, tbb::split)
Definition: LeafManager.h:195
RangeType getRange(size_t grainsize=1) const
Return a tbb::blocked_range of leaf array indices.
Definition: LeafManager.h:347
static void doSwapLeafBuffer(const RangeT &r, size_t auxBufferIdx, LeafT **leafs, BufT *bufs, size_t bufsPerLeaf)
Definition: LeafManager.h:89
void operator()(const RangeType &r) const
Used internally by tbb::parallel_for() - never call it directly!
Definition: LeafManager.h:527
Definition: LeafManager.h:134
void getNodes(ArrayT &array)
Definition: LeafManager.h:489
Definition: LeafManager.h:83
bool operator==(const Iterator &other) const
Definition: LeafManager.h:170
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h:71
ManagerT::LeafType LeafT
Definition: LeafManager.h:86
CopyConstness< TreeType, NonConstLeafType >::Type LeafType
Definition: LeafManager.h:121
LeafType LeafNodeType
Definition: LeafManager.h:122
bool isConstTree() const
Return true if the tree associated with this manager is immutable.
Definition: LeafManager.h:319
TreeType::LeafNodeType NonConstLeafType
Definition: LeafManager.h:120
Iterator(const LeafRange &range, size_t pos)
Definition: LeafManager.h:137
const RootNodeType & root() const
Return a const reference to root node associated with this manager.
Definition: LeafManager.h:313
void removeAuxBuffers()
Remove the auxiliary buffers, but don't rebuild the leaf array.
Definition: LeafManager.h:289
Definition: LeafManager.h:131
TreeT::RootNodeType RootNodeType
Definition: LeafManager.h:119