15#ifndef OPENVDB_UTIL_PAGED_ARRAY_HAS_BEEN_INCLUDED
16#define OPENVDB_UTIL_PAGED_ARRAY_HAS_BEEN_INCLUDED
18#include <openvdb/version.h>
25#include <tbb/spin_mutex.h>
26#include <tbb/parallel_for.h>
27#include <tbb/parallel_sort.h>
141template<
typename ValueT,
size_t Log2PageSize = 10UL>
145 static_assert(Log2PageSize > 1UL,
"Expected Log2PageSize > 1");
149 using PageTableT = std::deque<Page*>;
194 const size_t index = mSize.fetch_add(1);
195 if (index >= mCapacity) {
196 mPageTable.push_back(
new Page() );
197 mCapacity += Page::Size;
199 (*mPageTable[index >> Log2PageSize])[index] =
value;
206 void shrink_to_fit();
218 return (*mPageTable[i>>Log2PageSize])[i];
231 return (*mPageTable[i>>Log2PageSize])[i];
241 auto op = [&](
const tbb::blocked_range<size_t>& r){
242 for(
size_t i=r.begin(); i!=r.end(); ++i) mPageTable[i]->fill(v);
244 tbb::parallel_for(tbb::blocked_range<size_t>(0, this->pageCount()), op);
256 size_t last_page = count >> Log2PageSize;
257 if (last_page >= this->pageCount())
return false;
258 auto op = [&](
const tbb::blocked_range<size_t>& r){
259 for (
size_t i=r.begin(); i!=r.end(); ++i) {
260 mPageTable[i]->copy(p+i*Page::Size, Page::Size);
263 if (
size_t m = count & Page::Mask) {
264 tbb::parallel_for(tbb::blocked_range<size_t>(0, last_page, 32), op);
265 mPageTable[last_page]->copy(p+last_page*Page::Size, m);
267 tbb::parallel_for(tbb::blocked_range<size_t>(0, last_page+1, 32), op);
290 if (size > mCapacity) {
293 this->shrink_to_fit();
319 size_t size()
const {
return mSize; }
341 return sizeof(*this) + mPageTable.size() * Page::memUsage();
360 for (
size_t i=0, n=mPageTable.size(); i<n; ++i)
delete mPageTable[i];
361 PageTableT().swap(mPageTable);
393 void sort() { tbb::parallel_sort(this->begin(), this->end(), std::less<ValueT>() ); }
396 void invSort() { tbb::parallel_sort(this->begin(), this->end(), std::greater<ValueT>()); }
403 template <
typename Functor>
404 void sort(Functor func) { tbb::parallel_sort(this->begin(), this->end(), func ); }
417 void print(std::ostream& os = std::cout)
const
419 os <<
"PagedArray:\n"
420 <<
"\tSize: " << this->size() <<
" elements\n"
421 <<
"\tPage table: " << this->pageCount() <<
" pages\n"
422 <<
"\tPage size: " << this->pageSize() <<
" elements\n"
423 <<
"\tCapacity: " << this->capacity() <<
" elements\n"
424 <<
"\tFootprint: " << this->memUsage() <<
" bytes\n";
431 void grow(
size_t index)
433 tbb::spin_mutex::scoped_lock lock(mGrowthMutex);
434 while(index >= mCapacity) {
435 mPageTable.push_back(
new Page() );
436 mCapacity += Page::Size;
440 void add_full(Page*& page,
size_t size);
442 void add_partially_full(Page*& page,
size_t size);
444 void add(Page*& page,
size_t size) {
445 tbb::spin_mutex::scoped_lock lock(mGrowthMutex);
446 if (size == Page::Size) {
447 this->add_full(page, size);
449 this->add_partially_full(page, size);
452 PageTableT mPageTable;
453 std::atomic<size_t> mSize;
455 tbb::spin_mutex mGrowthMutex;
460template <
typename ValueT,
size_t Log2PageSize>
463 if (mPageTable.size() > (mSize >> Log2PageSize) + 1) {
464 tbb::spin_mutex::scoped_lock lock(mGrowthMutex);
465 const size_t pageCount = (mSize >> Log2PageSize) + 1;
466 if (mPageTable.size() > pageCount) {
467 delete mPageTable.back();
468 mPageTable.pop_back();
469 mCapacity -= Page::Size;
474template <
typename ValueT,
size_t Log2PageSize>
477 if (&other !=
this && !other.
isEmpty()) {
478 tbb::spin_mutex::scoped_lock lock(mGrowthMutex);
480 Page* page =
nullptr;
481 const size_t size = mSize & Page::Mask;
483 page = mPageTable.back();
484 mPageTable.pop_back();
488 mPageTable.insert(mPageTable.end(), other.mPageTable.begin(), other.mPageTable.end());
489 mSize += other.mSize;
490 mCapacity = Page::Size*mPageTable.size();
493 PageTableT().swap(other.mPageTable);
495 if (page) this->add_partially_full(page, size);
499template <
typename ValueT,
size_t Log2PageSize>
502 assert(size == Page::Size);
503 if (mSize & Page::Mask) {
504 Page*& tmp = mPageTable.back();
505 std::swap(tmp, page);
507 mPageTable.push_back(page);
508 mCapacity += Page::Size;
513template <
typename ValueT,
size_t Log2PageSize>
514void PagedArray<ValueT, Log2PageSize>::add_partially_full(Page*& page,
size_t size)
516 assert(size > 0 && size < Page::Size);
517 if (
size_t m = mSize & Page::Mask) {
518 ValueT *s = page->data(), *t = mPageTable.back()->data() + m;
519 for (
size_t i=std::min(mSize+size, mCapacity)-mSize; i; --i) *t++ = *s++;
520 if (mSize+size > mCapacity) {
521 mPageTable.push_back(
new Page() );
522 t = mPageTable.back()->data();
523 for (
size_t i=mSize+size-mCapacity; i; --i) *t++ = *s++;
524 mCapacity += Page::Size;
527 mPageTable.push_back( page );
528 mCapacity += Page::Size;
537template <
typename ValueT,
size_t Log2PageSize>
558 (*mPage)[mSize++] = v;
559 if (mSize == Page::Size) this->flush();
567 mParent->add(mPage, mSize);
568 if (mPage ==
nullptr) mPage =
new Page();
574 size_t size()
const {
return mSize; }
575 static size_t pageSize() {
return 1UL << Log2PageSize; }
586template <
typename ValueT,
size_t Log2PageSize>
588ConstIterator :
public std::iterator<std::random_access_iterator_tag, ValueT>
591 using BaseT = std::iterator<std::random_access_iterator_tag, ValueT>;
599 mParent=other.mParent;
609 const ValueT&
operator*()
const {
return (*mParent)[mPos]; }
610 const ValueT*
operator->()
const {
return &(this->operator*()); }
623 bool operator< (
const ConstIterator& other)
const {
return mPos < other.mPos; }
624 bool operator> (
const ConstIterator& other)
const {
return mPos > other.mPos; }
626 bool isValid()
const {
return mParent !=
nullptr && mPos < mParent->size(); }
627 size_t pos()
const {
return mPos; }
637template <
typename ValueT,
size_t Log2PageSize>
639Iterator :
public std::iterator<std::random_access_iterator_tag, ValueT>
642 using BaseT = std::iterator<std::random_access_iterator_tag, ValueT>;
650 mParent=other.mParent;
674 bool operator< (
const Iterator& other)
const {
return mPos < other.mPos; }
675 bool operator> (
const Iterator& other)
const {
return mPos > other.mPos; }
677 bool isValid()
const {
return mParent !=
nullptr && mPos < mParent->size(); }
678 size_t pos()
const {
return mPos; }
687template <
typename ValueT,
size_t Log2PageSize>
692 static const size_t Size = 1UL << Log2PageSize;
693 static const size_t Mask = Size - 1UL;
694 static size_t memUsage() {
return sizeof(ValueT)*Size; }
696 Page() : mData(reinterpret_cast<ValueT*>(new char[sizeof(ValueT)*Size])) {}
700 ValueT&
operator[](
const size_t i) {
return mData[i & Mask]; }
701 const ValueT&
operator[](
const size_t i)
const {
return mData[i & Mask]; }
704 for (
size_t i=Size; i; --i) *dst++ = v;
706 ValueT*
data() {
return mData; }
710 const ValueT* src = mData;
711 for (
size_t i=n; i; --i) *dst++ = *src++;
ValueT value
Definition: GridBuilder.h:1290
Definition: PagedArray.h:589
typename BaseT::difference_type difference_type
Definition: PagedArray.h:592
bool operator==(const ConstIterator &other) const
Definition: PagedArray.h:619
const ValueT & operator[](const difference_type &pos) const
Definition: PagedArray.h:611
bool operator>=(const ConstIterator &other) const
Definition: PagedArray.h:621
ConstIterator operator+(const difference_type &pos) const
Definition: PagedArray.h:615
ConstIterator & operator+=(const difference_type &pos)
Definition: PagedArray.h:613
difference_type operator-(const ConstIterator &other) const
Definition: PagedArray.h:617
ConstIterator & operator--()
Definition: PagedArray.h:604
bool isValid() const
Definition: PagedArray.h:626
std::iterator< std::random_access_iterator_tag, ValueT > BaseT
Definition: PagedArray.h:591
ConstIterator & operator-=(const difference_type &pos)
Definition: PagedArray.h:614
ConstIterator operator-(const difference_type &pos) const
Definition: PagedArray.h:616
bool operator!=(const ConstIterator &other) const
Definition: PagedArray.h:620
size_t pos() const
Definition: PagedArray.h:627
ConstIterator operator++(int)
Definition: PagedArray.h:606
const ValueT & operator*() const
Definition: PagedArray.h:609
const ValueT * operator->() const
Definition: PagedArray.h:610
bool operator<=(const ConstIterator &other) const
Definition: PagedArray.h:622
ConstIterator & operator++()
Definition: PagedArray.h:603
ConstIterator(const PagedArray &parent, size_t pos=0)
Definition: PagedArray.h:595
ConstIterator & operator=(const ConstIterator &other)
Definition: PagedArray.h:597
ConstIterator()
Definition: PagedArray.h:594
ConstIterator operator--(int)
Definition: PagedArray.h:607
ConstIterator(const ConstIterator &other)
Definition: PagedArray.h:596
Definition: PagedArray.h:640
typename BaseT::difference_type difference_type
Definition: PagedArray.h:643
bool operator>=(const Iterator &other) const
Definition: PagedArray.h:672
Iterator()
Definition: PagedArray.h:645
Iterator(const Iterator &other)
Definition: PagedArray.h:647
ValueT & operator[](const difference_type &pos) const
Definition: PagedArray.h:662
Iterator(PagedArray &parent, size_t pos=0)
Definition: PagedArray.h:646
ValueT * operator->() const
Definition: PagedArray.h:661
Iterator & operator+=(const difference_type &pos)
Definition: PagedArray.h:664
bool isValid() const
Definition: PagedArray.h:677
Iterator operator+(const difference_type &pos) const
Definition: PagedArray.h:666
ValueT & operator*() const
Definition: PagedArray.h:660
bool operator!=(const Iterator &other) const
Definition: PagedArray.h:671
std::iterator< std::random_access_iterator_tag, ValueT > BaseT
Definition: PagedArray.h:642
Iterator operator--(int)
Definition: PagedArray.h:658
Iterator & operator-=(const difference_type &pos)
Definition: PagedArray.h:665
bool operator<=(const Iterator &other) const
Definition: PagedArray.h:673
size_t pos() const
Definition: PagedArray.h:678
difference_type operator-(const Iterator &other) const
Definition: PagedArray.h:668
Iterator operator++(int)
Definition: PagedArray.h:657
Iterator & operator=(const Iterator &other)
Definition: PagedArray.h:648
Iterator & operator++()
Definition: PagedArray.h:654
Iterator & operator--()
Definition: PagedArray.h:655
bool operator==(const Iterator &other) const
Definition: PagedArray.h:670
Iterator operator-(const difference_type &pos) const
Definition: PagedArray.h:667
Definition: PagedArray.h:690
void copy(ValueType *dst, size_t n) const
Definition: PagedArray.h:709
const ValueT & operator[](const size_t i) const
Definition: PagedArray.h:701
ValueT & operator[](const size_t i)
Definition: PagedArray.h:700
static size_t memUsage()
Definition: PagedArray.h:694
~Page()
Definition: PagedArray.h:697
ValueT * mData
Definition: PagedArray.h:714
Page(const Page &)=delete
ValueT * data()
Definition: PagedArray.h:706
Page()
Definition: PagedArray.h:696
void fill(const ValueT &v)
Definition: PagedArray.h:702
Page & operator=(const Page &)=delete
Definition: PagedArray.h:540
size_t size() const
Return the current number of elements cached in this buffer.
Definition: PagedArray.h:574
~ValueBuffer()
Destructor that transfers an buffered values to the parent PagedArray.
Definition: PagedArray.h:549
ValueBuffer & operator=(const ValueBuffer &)=delete
void push_back(const ValueT &v)
Add a value to the buffer and increment the size.
Definition: PagedArray.h:557
ValueBuffer(const ValueBuffer &other)
Definition: PagedArray.h:547
PagedArrayType & parent() const
Return a reference to the parent PagedArray.
Definition: PagedArray.h:572
void flush()
Manually transfers the values in this buffer to the parent PagedArray.
Definition: PagedArray.h:566
ValueBuffer(PagedArray &parent)
Constructor from a PageArray.
Definition: PagedArray.h:544
static size_t pageSize()
Definition: PagedArray.h:575
Concurrent, page-based, dynamically-sized linear data structure with O(1) random access and STL-compl...
Definition: PagedArray.h:143
ConstIterator cend() const
Return a const iterator pointing to the past-the-last element.
Definition: PagedArray.h:388
size_t memUsage() const
Return the memory footprint of this array in bytes.
Definition: PagedArray.h:339
static size_t log2PageSize()
Return log2 of the number of elements per memory page.
Definition: PagedArray.h:336
Iterator begin()
Return a non-const iterator pointing to the first element.
Definition: PagedArray.h:367
size_t size() const
Return the number of elements in this array.
Definition: PagedArray.h:319
PagedArray(const PagedArray &)=delete
size_t push_back_unsafe(const ValueType &value)
Definition: PagedArray.h:192
void copy(ValueType *p) const
Definition: PagedArray.h:271
void sort()
Parallel sort of all the elements in ascending order.
Definition: PagedArray.h:393
size_t pageCount() const
Return the number of allocated memory pages.
Definition: PagedArray.h:330
void resize(size_t size)
Resize this array to the specified size.
Definition: PagedArray.h:287
void sort(Functor func)
Parallel sort of all the elements based on a custom functor with the api:
Definition: PagedArray.h:404
PagedArray()
Default constructor.
Definition: PagedArray.h:156
void invSort()
Parallel sort of all the elements in descending order.
Definition: PagedArray.h:396
ConstIterator end() const
Definition: PagedArray.h:389
void fill(const ValueType &v)
Set all elements in the page table to the specified value.
Definition: PagedArray.h:239
size_t freeCount() const
Return the number of additional elements that can be added to this array without allocating more memo...
Definition: PagedArray.h:327
size_t capacity() const
Return the maximum number of elements that this array can contain without allocating more memory page...
Definition: PagedArray.h:323
bool isPartiallyFull() const
Return true if the page table is partially full, i.e. the last non-empty page contains less than page...
Definition: PagedArray.h:353
ValueT ValueType
Definition: PagedArray.h:152
PagedArray & operator=(const PagedArray &)=delete
void resize(size_t size, const ValueType &v)
Resize this array to the specified size and initialize all values to v.
Definition: PagedArray.h:312
ValueType & operator[](size_t i)
Return a reference to the value at the specified offset.
Definition: PagedArray.h:215
ConstIterator cbegin() const
Return a const iterator pointing to the first element.
Definition: PagedArray.h:378
~PagedArray()
Destructor removed all allocated pages.
Definition: PagedArray.h:159
Iterator end()
Return a non-const iterator pointing to the past-the-last element.
Definition: PagedArray.h:374
bool copy(ValueType *p, size_t count) const
Copy the first count values in this PageArray into a raw c-style array, assuming it to be at least co...
Definition: PagedArray.h:254
ValueBuffer getBuffer()
Definition: PagedArray.h:179
SharedPtr< PagedArray > Ptr
Definition: PagedArray.h:153
void clear()
Removes all elements from the array and delete all pages.
Definition: PagedArray.h:358
bool isEmpty() const
Return true if the container contains no elements.
Definition: PagedArray.h:345
const ValueType & operator[](size_t i) const
Return a const-reference to the value at the specified offset.
Definition: PagedArray.h:228
ConstIterator begin() const
Definition: PagedArray.h:379
static Ptr create()
Return a shared pointer to a new instance of this class.
Definition: PagedArray.h:166
void print(std::ostream &os=std::cout) const
Print information for debugging.
Definition: PagedArray.h:417
static size_t pageSize()
Return the number of elements per memory page.
Definition: PagedArray.h:333
std::shared_ptr< T > SharedPtr
Definition: Types.h:114
Definition: Exceptions.h:13
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212