OpenVDB  10.0.0
PagedArray.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 ///
4 /// @file PagedArray.h
5 ///
6 /// @author Ken Museth
7 ///
8 /// @brief Concurrent, page-based, dynamically-sized linear data
9 /// structure with O(1) random access and STL-compliant
10 /// iterators. It is primarily intended for applications
11 /// that involve multi-threading push_back of (a possibly
12 /// unkown number of) elements into a dynamically growing
13 /// linear array, and fast random access to said elements.
14 
15 #ifndef OPENVDB_UTIL_PAGED_ARRAY_HAS_BEEN_INCLUDED
16 #define OPENVDB_UTIL_PAGED_ARRAY_HAS_BEEN_INCLUDED
17 
18 #include <openvdb/version.h>
19 #include <openvdb/Types.h>// SharedPtr
20 #include <deque>
21 #include <cassert>
22 #include <iostream>
23 #include <algorithm>// std::swap
24 #include <atomic>
25 #include <tbb/spin_mutex.h>
26 #include <tbb/parallel_for.h>
27 #include <tbb/parallel_sort.h>
28 
29 namespace openvdb {
31 namespace OPENVDB_VERSION_NAME {
32 namespace util {
33 
34 ////////////////////////////////////////
35 
36 
37 /// @brief Concurrent, page-based, dynamically-sized linear data structure
38 /// with O(1) random access and STL-compliant iterators. It is
39 /// primarily intended for applications that concurrently insert
40 /// (a possibly unkown number of) elements into a dynamically
41 /// growing linear array, and fast random access to said elements.
42 ///
43 /// @note Multiple threads can grow the page-table and push_back
44 /// new elements concurrently. A ValueBuffer provides accelerated
45 /// and threadsafe push_back at the cost of potentially re-ordering
46 /// elements (when multiple instances are used).
47 ///
48 /// @details This data structure employes contiguous pages of elements
49 /// (a std::deque) which avoids moving data when the
50 /// capacity is out-grown and new pages are allocated. The
51 /// size of the pages can be controlled with the Log2PageSize
52 /// template parameter (defaults to 1024 elements of type ValueT).
53 ///
54 /// There are three fundamentally different ways to insert elements to
55 /// this container - each with different advanteges and disadvanteges.
56 ///
57 /// The simplest way to insert elements is to use PagedArray::push_back_unsafe
58 /// which is @a not thread-safe:
59 /// @code
60 /// PagedArray<size_t> array;
61 /// for (size_t i=0; i<100000; ++i) array.push_back_unsafe(i);
62 /// @endcode
63 ///
64 /// The fastest way (by far) to insert elements is by means of a PagedArray::ValueBuffer:
65 /// @code
66 /// PagedArray<size_t> array;
67 /// auto buffer = array.getBuffer();
68 /// for (size_t i=0; i<100000; ++i) buffer.push_back(i);
69 /// buffer.flush();
70 /// @endcode
71 /// or
72 /// @code
73 /// PagedArray<size_t> array;
74 /// {
75 /// //local scope of a single thread
76 /// auto buffer = array.getBuffer();
77 /// for (size_t i=0; i<100000; ++i) buffer.push_back(i);
78 /// }
79 /// @endcode
80 /// or with TBB task-based multi-threading:
81 /// @code
82 /// PagedArray<size_t> array;
83 /// tbb::parallel_for(
84 /// tbb::blocked_range<size_t>(0, 10000, array.pageSize()),
85 /// [&array](const tbb::blocked_range<size_t>& range) {
86 /// auto buffer = array.getBuffer();
87 /// for (size_t i=range.begin(); i!=range.end(); ++i) buffer.push_back(i);
88 /// }
89 /// );
90 /// @endcode
91 /// or with TBB thread-local storage for even better performance (due
92 /// to fewer concurrent instantiations of partially full ValueBuffers)
93 /// @code
94 /// PagedArray<size_t> array;
95 /// auto exemplar = array.getBuffer();//dummy used for initialization
96 /// tbb::enumerable_thread_specific<PagedArray<size_t>::ValueBuffer>
97 /// pool(exemplar);//thread local storage pool of ValueBuffers
98 /// tbb::parallel_for(
99 /// tbb::blocked_range<size_t>(0, 10000, array.pageSize()),
100 /// [&pool](const tbb::blocked_range<size_t>& range) {
101 /// auto &buffer = pool.local();
102 /// for (size_t i=range.begin(); i!=range.end(); ++i) buffer.push_back(i);
103 /// }
104 /// );
105 /// for (auto i=pool.begin(); i!=pool.end(); ++i) i->flush();
106 /// @endcode
107 /// This technique generally outperforms PagedArray::push_back_unsafe,
108 /// std::vector::push_back, std::deque::push_back and even
109 /// tbb::concurrent_vector::push_back. Additionally it
110 /// is thread-safe as long as each thread has it's own instance of a
111 /// PagedArray::ValueBuffer. The only disadvantage is the ordering of
112 /// the elements is undefined if multiple instance of a
113 /// PagedArray::ValueBuffer are employed. This is typically the case
114 /// in the context of multi-threading, where the
115 /// ordering of inserts are undefined anyway. Note that a local scope
116 /// can be used to guarentee that the ValueBuffer has inserted all its
117 /// elements by the time the scope ends. Alternatively the ValueBuffer
118 /// can be explicitly flushed by calling ValueBuffer::flush.
119 ///
120 /// The third way to insert elements is to resize the container and use
121 /// random access, e.g.
122 /// @code
123 /// PagedArray<int> array;
124 /// array.resize(100000);
125 /// for (int i=0; i<100000; ++i) array[i] = i;
126 /// @endcode
127 /// or in terms of the random access iterator
128 /// @code
129 /// PagedArray<int> array;
130 /// array.resize(100000);
131 /// for (auto i=array.begin(); i!=array.end(); ++i) *i = i.pos();
132 /// @endcode
133 /// While this approach is both fast and thread-safe it suffers from the
134 /// major disadvantage that the problem size, i.e. number of elements, needs to
135 /// be known in advance. If that's the case you might as well consider
136 /// using std::vector or a raw c-style array! In other words the
137 /// PagedArray is most useful in the context of applications that
138 /// involve multi-threading of dynamically growing linear arrays that
139 /// require fast random access.
140 
141 template<typename ValueT, size_t Log2PageSize = 10UL>
143 {
144 private:
145  static_assert(Log2PageSize > 1UL, "Expected Log2PageSize > 1");
146  class Page;
147 
148  // must allow mutiple threads to call operator[] as long as only one thread calls push_back
149  using PageTableT = std::deque<Page*>;
150 
151 public:
152  using ValueType = ValueT;
154 
155  /// @brief Default constructor
156  PagedArray() : mCapacity{0} { mSize = 0; }
157 
158  /// @brief Destructor removed all allocated pages
159  ~PagedArray() { this->clear(); }
160 
161  // Disallow copy construction and assignment
162  PagedArray(const PagedArray&) = delete;
163  PagedArray& operator=(const PagedArray&) = delete;
164 
165  /// @brief Return a shared pointer to a new instance of this class
166  static Ptr create() { return Ptr(new PagedArray); }
167 
168  /// @brief Caches values into a local memory Page to improve
169  /// performance of push_back into a PagedArray.
170  ///
171  /// @note The ordering of inserted elements is undefined when
172  /// multiple ValueBuffers are used!
173  ///
174  /// @warning By design this ValueBuffer is not threadsafe so
175  /// make sure to create an instance per thread!
176  class ValueBuffer;
177 
178  /// @return a new instance of a ValueBuffer which supports thread-safe push_back!
179  ValueBuffer getBuffer() { return ValueBuffer(*this); }
180 
181  /// Const std-compliant iterator
182  class ConstIterator;
183 
184  /// Non-const std-compliant iterator
185  class Iterator;
186 
187  /// @param value value to be added to this PagedArray
188  ///
189  /// @note For best performance consider using the ValueBuffer!
190  ///
191  /// @warning Not thread-safe and mostly intended for debugging!
193  {
194  const size_t index = mSize.fetch_add(1);
195  if (index >= mCapacity) {
196  mPageTable.push_back( new Page() );
197  mCapacity += Page::Size;
198  }
199  (*mPageTable[index >> Log2PageSize])[index] = value;
200  return index;
201  }
202 
203  /// @brief Reduce the page table to fix the current size.
204  ///
205  /// @warning Not thread-safe!
206  void shrink_to_fit();
207 
208  /// @brief Return a reference to the value at the specified offset
209  ///
210  /// @param i linear offset of the value to be accessed.
211  ///
212  /// @note This random access has constant time complexity.
213  ///
214  /// @warning It is assumed that the i'th element is already allocated!
216  {
217  assert(i<mCapacity);
218  return (*mPageTable[i>>Log2PageSize])[i];
219  }
220 
221  /// @brief Return a const-reference to the value at the specified offset
222  ///
223  /// @param i linear offset of the value to be accessed.
224  ///
225  /// @note This random access has constant time complexity.
226  ///
227  /// @warning It is assumed that the i'th element is already allocated!
228  const ValueType& operator[](size_t i) const
229  {
230  assert(i<mCapacity);
231  return (*mPageTable[i>>Log2PageSize])[i];
232  }
233 
234  /// @brief Set all elements in the page table to the specified value
235  ///
236  /// @param v value to be filled in all the existing pages of this PagedArray.
237  ///
238  /// @note Multi-threaded
239  void fill(const ValueType& v)
240  {
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);
243  };
244  tbb::parallel_for(tbb::blocked_range<size_t>(0, this->pageCount()), op);
245  }
246 
247  /// @brief Copy the first @a count values in this PageArray into
248  /// a raw c-style array, assuming it to be at least @a count
249  /// elements long.
250  ///
251  /// @param p pointer to an array that will used as the destination of the copy.
252  /// @param count number of elements to be copied.
253  ///
254  bool copy(ValueType *p, size_t count) const
255  {
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);
261  }
262  };
263  if (size_t m = count & Page::Mask) {//count is not divisible by page size
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);
266  } else {
267  tbb::parallel_for(tbb::blocked_range<size_t>(0, last_page+1, 32), op);
268  }
269  return true;
270  }
271  void copy(ValueType *p) const { this->copy(p, mSize); }
272 
273  /// @brief Resize this array to the specified size.
274  ///
275  /// @param size number of elements that this PageArray will contain.
276  ///
277  /// @details Will grow or shrink the page table to contain
278  /// the specified number of elements. It will affect the size(),
279  /// iteration will go over all those elements, push_back will
280  /// insert after them and operator[] can be used directly access
281  /// them.
282  ///
283  /// @note No reserve method is implemented due to efficiency concerns
284  /// (especially for the ValueBuffer) from having to deal with empty pages.
285  ///
286  /// @warning Not thread-safe!
287  void resize(size_t size)
288  {
289  mSize = size;
290  if (size > mCapacity) {
291  this->grow(size-1);
292  } else {
293  this->shrink_to_fit();
294  }
295  }
296 
297  /// @brief Resize this array to the specified size and initialize
298  /// all values to @a v.
299  ///
300  /// @param size number of elements that this PageArray will contain.
301  /// @param v value of all the @a size values.
302  ///
303  /// @details Will grow or shrink the page table to contain
304  /// the specified number of elements. It will affect the size(),
305  /// iteration will go over all those elements, push_back will
306  /// insert after them and operator[] can be used directly access them.
307  ///
308  /// @note No reserve method is implemented due to efficiency concerns
309  /// (especially for the ValueBuffer) from having to deal with empty pages.
310  ///
311  /// @warning Not thread-safe!
312  void resize(size_t size, const ValueType& v)
313  {
314  this->resize(size);
315  this->fill(v);
316  }
317 
318  /// @brief Return the number of elements in this array.
319  size_t size() const { return mSize; }
320 
321  /// @brief Return the maximum number of elements that this array
322  /// can contain without allocating more memory pages.
323  size_t capacity() const { return mCapacity; }
324 
325  /// @brief Return the number of additional elements that can be
326  /// added to this array without allocating more memory pages.
327  size_t freeCount() const { return mCapacity - mSize; }
328 
329  /// @brief Return the number of allocated memory pages.
330  size_t pageCount() const { return mPageTable.size(); }
331 
332  /// @brief Return the number of elements per memory page.
333  static size_t pageSize() { return Page::Size; }
334 
335  /// @brief Return log2 of the number of elements per memory page.
336  static size_t log2PageSize() { return Log2PageSize; }
337 
338  /// @brief Return the memory footprint of this array in bytes.
339  size_t memUsage() const
340  {
341  return sizeof(*this) + mPageTable.size() * Page::memUsage();
342  }
343 
344  /// @brief Return true if the container contains no elements.
345  bool isEmpty() const { return mSize == 0; }
346 
347  /// @brief Return true if the page table is partially full, i.e. the
348  /// last non-empty page contains less than pageSize() elements.
349  ///
350  /// @details When the page table is partially full calling merge()
351  /// or using a ValueBuffer will rearrange the ordering of
352  /// existing elements.
353  bool isPartiallyFull() const { return (mSize & Page::Mask) > 0; }
354 
355  /// @brief Removes all elements from the array and delete all pages.
356  ///
357  /// @warning Not thread-safe!
358  void clear()
359  {
360  for (size_t i=0, n=mPageTable.size(); i<n; ++i) delete mPageTable[i];
361  PageTableT().swap(mPageTable);
362  mSize = 0;
363  mCapacity = 0;
364  }
365 
366  /// @brief Return a non-const iterator pointing to the first element
367  Iterator begin() { return Iterator(*this, 0); }
368 
369  /// @brief Return a non-const iterator pointing to the
370  /// past-the-last element.
371  ///
372  /// @warning Iterator does not point to a valid element and should not
373  /// be dereferenced!
374  Iterator end() { return Iterator(*this, mSize); }
375 
376  //@{
377  /// @brief Return a const iterator pointing to the first element
378  ConstIterator cbegin() const { return ConstIterator(*this, 0); }
379  ConstIterator begin() const { return ConstIterator(*this, 0); }
380  //@}
381 
382  //@{
383  /// @brief Return a const iterator pointing to the
384  /// past-the-last element.
385  ///
386  /// @warning Iterator does not point to a valid element and should not
387  /// be dereferenced!
388  ConstIterator cend() const { return ConstIterator(*this, mSize); }
389  ConstIterator end() const { return ConstIterator(*this, mSize); }
390  //@}
391 
392  /// @brief Parallel sort of all the elements in ascending order.
393  void sort() { tbb::parallel_sort(this->begin(), this->end(), std::less<ValueT>() ); }
394 
395  /// @brief Parallel sort of all the elements in descending order.
396  void invSort() { tbb::parallel_sort(this->begin(), this->end(), std::greater<ValueT>()); }
397 
398  //@{
399  /// @brief Parallel sort of all the elements based on a custom
400  /// functor with the api:
401  /// @code bool operator()(const ValueT& a, const ValueT& b) @endcode
402  /// which returns true if a comes before b.
403  template <typename Functor>
404  void sort(Functor func) { tbb::parallel_sort(this->begin(), this->end(), func ); }
405  //@}
406 
407  /// @brief Transfer all the elements (and pages) from the other array to this array.
408  ///
409  /// @param other non-const reference to the PagedArray that will be merged into this PagedArray.
410  ///
411  /// @note The other PagedArray is empty on return.
412  ///
413  /// @warning The ordering of elements is undefined if this page table is partially full!
414  void merge(PagedArray& other);
415 
416  /// @brief Print information for debugging
417  void print(std::ostream& os = std::cout) const
418  {
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";
425  }
426 
427 private:
428 
429  friend class ValueBuffer;
430 
431  void grow(size_t index)
432  {
433  tbb::spin_mutex::scoped_lock lock(mGrowthMutex);
434  while(index >= mCapacity) {
435  mPageTable.push_back( new Page() );
436  mCapacity += Page::Size;
437  }
438  }
439 
440  void add_full(Page*& page, size_t size);
441 
442  void add_partially_full(Page*& page, size_t size);
443 
444  void add(Page*& page, size_t size) {
445  tbb::spin_mutex::scoped_lock lock(mGrowthMutex);
446  if (size == Page::Size) {//page is full
447  this->add_full(page, size);
448  } else if (size>0) {//page is only partially full
449  this->add_partially_full(page, size);
450  }
451  }
452  PageTableT mPageTable;//holds points to allocated pages
453  std::atomic<size_t> mSize;// current number of elements in array
454  size_t mCapacity;//capacity of array given the current page count
455  tbb::spin_mutex mGrowthMutex;//Mutex-lock required to grow pages
456 }; // Public class PagedArray
457 
458 ////////////////////////////////////////////////////////////////////////////////
459 
460 template <typename ValueT, size_t Log2PageSize>
462 {
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;
470  }
471  }
472 }
473 
474 template <typename ValueT, size_t Log2PageSize>
476 {
477  if (&other != this && !other.isEmpty()) {
478  tbb::spin_mutex::scoped_lock lock(mGrowthMutex);
479  // extract last partially full page if it exists
480  Page* page = nullptr;
481  const size_t size = mSize & Page::Mask; //number of elements in the last page
482  if ( size > 0 ) {
483  page = mPageTable.back();
484  mPageTable.pop_back();
485  mSize -= size;
486  }
487  // transfer all pages from the other page table
488  mPageTable.insert(mPageTable.end(), other.mPageTable.begin(), other.mPageTable.end());
489  mSize += other.mSize;
490  mCapacity = Page::Size*mPageTable.size();
491  other.mSize = 0;
492  other.mCapacity = 0;
493  PageTableT().swap(other.mPageTable);
494  // add back last partially full page
495  if (page) this->add_partially_full(page, size);
496  }
497 }
498 
499 template <typename ValueT, size_t Log2PageSize>
500 void PagedArray<ValueT, Log2PageSize>::add_full(Page*& page, size_t size)
501 {
502  assert(size == Page::Size);//page must be full
503  if (mSize & Page::Mask) {//page-table is partially full
504  Page*& tmp = mPageTable.back();
505  std::swap(tmp, page);//swap last table entry with page
506  }
507  mPageTable.push_back(page);
508  mCapacity += Page::Size;
509  mSize += size;
510  page = nullptr;
511 }
512 
513 template <typename ValueT, size_t Log2PageSize>
515 {
516  assert(size > 0 && size < Page::Size);//page must be partially full
517  if (size_t m = mSize & Page::Mask) {//page table is also partially full
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) {//grow page table
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;
525  }
526  } else {//page table is full so simply append page
527  mPageTable.push_back( page );
528  mCapacity += Page::Size;
529  page = nullptr;
530  }
531  mSize += size;
532 }
533 
534 ////////////////////////////////////////////////////////////////////////////////
535 
536 // Public member-class of PagedArray
537 template <typename ValueT, size_t Log2PageSize>
538 class PagedArray<ValueT, Log2PageSize>::
540 {
541 public:
543  /// @brief Constructor from a PageArray
544  ValueBuffer(PagedArray& parent) : mParent(&parent), mPage(new Page()), mSize(0) {}
545  /// @warning This copy-constructor is shallow in the sense that no
546  /// elements are copied, i.e. size = 0.
547  ValueBuffer(const ValueBuffer& other) : mParent(other.mParent), mPage(new Page()), mSize(0) {}
548  /// @brief Destructor that transfers an buffered values to the parent PagedArray.
549  ~ValueBuffer() { mParent->add(mPage, mSize); delete mPage; }
550 
551  ValueBuffer& operator=(const ValueBuffer&) = delete;// disallow copy assignment
552 
553  /// @brief Add a value to the buffer and increment the size.
554  ///
555  /// @details If the internal memory page is full it will
556  /// automaically flush the page to the parent PagedArray.
557  void push_back(const ValueT& v) {
558  (*mPage)[mSize++] = v;
559  if (mSize == Page::Size) this->flush();
560  }
561  /// @brief Manually transfers the values in this buffer to the parent PagedArray.
562  ///
563  /// @note This method is also called by the destructor and
564  /// push_back so it should only be called if one manually wants to
565  /// sync up the buffer with the array, e.g. during debugging.
566  void flush() {
567  mParent->add(mPage, mSize);
568  if (mPage == nullptr) mPage = new Page();
569  mSize = 0;
570  }
571  /// @brief Return a reference to the parent PagedArray
572  PagedArrayType& parent() const { return *mParent; }
573  /// @brief Return the current number of elements cached in this buffer.
574  size_t size() const { return mSize; }
575  static size_t pageSize() { return 1UL << Log2PageSize; }
576 private:
577  PagedArray* mParent;
578  Page* mPage;
579  size_t mSize;
580 };// Public class PagedArray::ValueBuffer
581 
582 ////////////////////////////////////////////////////////////////////////////////
583 
584 // Const std-compliant iterator
585 // Public member-class of PagedArray
586 template <typename ValueT, size_t Log2PageSize>
587 class PagedArray<ValueT, Log2PageSize>::
588 ConstIterator : public std::iterator<std::random_access_iterator_tag, ValueT>
589 {
590 public:
591  using BaseT = std::iterator<std::random_access_iterator_tag, ValueT>;
592  using difference_type = typename BaseT::difference_type;
593  // constructors and assignment
594  ConstIterator() : mPos(0), mParent(nullptr) {}
595  ConstIterator(const PagedArray& parent, size_t pos=0) : mPos(pos), mParent(&parent) {}
596  ConstIterator(const ConstIterator& other) : mPos(other.mPos), mParent(other.mParent) {}
598  mPos=other.mPos;
599  mParent=other.mParent;
600  return *this;
601  }
602  // prefix
603  ConstIterator& operator++() { ++mPos; return *this; }
604  ConstIterator& operator--() { --mPos; return *this; }
605  // postfix
606  ConstIterator operator++(int) { ConstIterator tmp(*this); ++mPos; return tmp; }
607  ConstIterator operator--(int) { ConstIterator tmp(*this); --mPos; return tmp; }
608  // value access
609  const ValueT& operator*() const { return (*mParent)[mPos]; }
610  const ValueT* operator->() const { return &(this->operator*()); }
611  const ValueT& operator[](const difference_type& pos) const { return (*mParent)[mPos+pos]; }
612  // offset
613  ConstIterator& operator+=(const difference_type& pos) { mPos += pos; return *this; }
614  ConstIterator& operator-=(const difference_type& pos) { mPos -= pos; return *this; }
615  ConstIterator operator+(const difference_type &pos) const { return Iterator(*mParent,mPos+pos); }
616  ConstIterator operator-(const difference_type &pos) const { return Iterator(*mParent,mPos-pos); }
617  difference_type operator-(const ConstIterator& other) const { return mPos - other.pos(); }
618  // comparisons
619  bool operator==(const ConstIterator& other) const { return mPos == other.mPos; }
620  bool operator!=(const ConstIterator& other) const { return mPos != other.mPos; }
621  bool operator>=(const ConstIterator& other) const { return mPos >= other.mPos; }
622  bool operator<=(const ConstIterator& other) const { return mPos <= other.mPos; }
623  bool operator< (const ConstIterator& other) const { return mPos < other.mPos; }
624  bool operator> (const ConstIterator& other) const { return mPos > other.mPos; }
625  // non-std methods
626  bool isValid() const { return mParent != nullptr && mPos < mParent->size(); }
627  size_t pos() const { return mPos; }
628 private:
629  size_t mPos;
630  const PagedArray* mParent;
631 };// Public class PagedArray::ConstIterator
632 
633 ////////////////////////////////////////////////////////////////////////////////
634 
635 // Non-const std-compliant iterator
636 // Public member-class of PagedArray
637 template <typename ValueT, size_t Log2PageSize>
638 class PagedArray<ValueT, Log2PageSize>::
639 Iterator : public std::iterator<std::random_access_iterator_tag, ValueT>
640 {
641 public:
642  using BaseT = std::iterator<std::random_access_iterator_tag, ValueT>;
643  using difference_type = typename BaseT::difference_type;
644  // constructors and assignment
645  Iterator() : mPos(0), mParent(nullptr) {}
646  Iterator(PagedArray& parent, size_t pos=0) : mPos(pos), mParent(&parent) {}
647  Iterator(const Iterator& other) : mPos(other.mPos), mParent(other.mParent) {}
648  Iterator& operator=(const Iterator& other) {
649  mPos=other.mPos;
650  mParent=other.mParent;
651  return *this;
652  }
653  // prefix
654  Iterator& operator++() { ++mPos; return *this; }
655  Iterator& operator--() { --mPos; return *this; }
656  // postfix
657  Iterator operator++(int) { Iterator tmp(*this); ++mPos; return tmp; }
658  Iterator operator--(int) { Iterator tmp(*this); --mPos; return tmp; }
659  // value access
660  ValueT& operator*() const { return (*mParent)[mPos]; }
661  ValueT* operator->() const { return &(this->operator*()); }
662  ValueT& operator[](const difference_type& pos) const { return (*mParent)[mPos+pos]; }
663  // offset
664  Iterator& operator+=(const difference_type& pos) { mPos += pos; return *this; }
665  Iterator& operator-=(const difference_type& pos) { mPos -= pos; return *this; }
666  Iterator operator+(const difference_type &pos) const { return Iterator(*mParent, mPos+pos); }
667  Iterator operator-(const difference_type &pos) const { return Iterator(*mParent, mPos-pos); }
668  difference_type operator-(const Iterator& other) const { return mPos - other.pos(); }
669  // comparisons
670  bool operator==(const Iterator& other) const { return mPos == other.mPos; }
671  bool operator!=(const Iterator& other) const { return mPos != other.mPos; }
672  bool operator>=(const Iterator& other) const { return mPos >= other.mPos; }
673  bool operator<=(const Iterator& other) const { return mPos <= other.mPos; }
674  bool operator< (const Iterator& other) const { return mPos < other.mPos; }
675  bool operator> (const Iterator& other) const { return mPos > other.mPos; }
676  // non-std methods
677  bool isValid() const { return mParent != nullptr && mPos < mParent->size(); }
678  size_t pos() const { return mPos; }
679  private:
680  size_t mPos;
681  PagedArray* mParent;
682 };// Public class PagedArray::Iterator
683 
684 ////////////////////////////////////////////////////////////////////////////////
685 
686 // Private member-class of PagedArray implementing a memory page
687 template <typename ValueT, size_t Log2PageSize>
688 class PagedArray<ValueT, Log2PageSize>::
689 Page
690 {
691 public:
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; }
695  // Raw memory allocation without any initialization
696  Page() : mData(reinterpret_cast<ValueT*>(new char[sizeof(ValueT)*Size])) {}
697  ~Page() { delete [] mData; }
698  Page(const Page&) = delete;//copy construction is not implemented
699  Page& operator=(const Page&) = delete;//copy assignment is not implemented
700  ValueT& operator[](const size_t i) { return mData[i & Mask]; }
701  const ValueT& operator[](const size_t i) const { return mData[i & Mask]; }
702  void fill(const ValueT& v) {
703  ValueT* dst = mData;
704  for (size_t i=Size; i; --i) *dst++ = v;
705  }
706  ValueT* data() { return mData; }
707  // Copy the first n elements of this Page to dst (which is assumed to large
708  // enough to hold the n elements).
709  void copy(ValueType *dst, size_t n) const {
710  const ValueT* src = mData;
711  for (size_t i=n; i; --i) *dst++ = *src++;
712  }
713 protected:
714  ValueT* mData;
715 };// Private class PagedArray::Page
716 
717 ////////////////////////////////////////////////////////////////////////////////
718 
719 } // namespace util
720 } // namespace OPENVDB_VERSION_NAME
721 } // namespace openvdb
722 
723 #endif // OPENVDB_UTIL_PAGED_ARRAY_HAS_BEEN_INCLUDED
~ValueBuffer()
Destructor that transfers an buffered values to the parent PagedArray.
Definition: PagedArray.h:549
size_t memUsage() const
Return the memory footprint of this array in bytes.
Definition: PagedArray.h:339
PagedArray()
Default constructor.
Definition: PagedArray.h:156
Iterator(PagedArray &parent, size_t pos=0)
Definition: PagedArray.h:646
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
Iterator end()
Return a non-const iterator pointing to the past-the-last element.
Definition: PagedArray.h:374
ValueT & operator[](const difference_type &pos) const
Definition: PagedArray.h:662
const std::enable_if<!VecTraits< T >::IsVec, T >::type & min(const T &a, const T &b)
Definition: Composite.h:106
Mat3< typename promote< T0, T1 >::type > operator*(const Mat3< T0 > &m0, const Mat3< T1 > &m1)
Multiply m0 by m1 and return the resulting matrix.
Definition: Mat3.h:597
void push_back(const ValueT &v)
Add a value to the buffer and increment the size.
Definition: PagedArray.h:557
Iterator()
Definition: PagedArray.h:645
~PagedArray()
Destructor removed all allocated pages.
Definition: PagedArray.h:159
Iterator(const Iterator &other)
Definition: PagedArray.h:647
static size_t pageSize()
Definition: PagedArray.h:575
void print(std::ostream &os=std::cout) const
Print information for debugging.
Definition: PagedArray.h:417
bool operator<=(const Iterator &other) const
Definition: PagedArray.h:673
Iterator operator-(const difference_type &pos) const
Definition: PagedArray.h:667
ConstIterator operator-(const difference_type &pos) const
Definition: PagedArray.h:616
const ValueT & operator[](const size_t i) const
Definition: PagedArray.h:701
size_t pos() const
Definition: PagedArray.h:627
static size_t log2PageSize()
Return log2 of the number of elements per memory page.
Definition: PagedArray.h:336
Iterator & operator=(const Iterator &other)
Definition: PagedArray.h:648
ValueT ValueType
Definition: PagedArray.h:152
difference_type operator-(const Iterator &other) const
Definition: PagedArray.h:668
void fill(const ValueT &v)
Definition: PagedArray.h:702
bool operator>=(const ConstIterator &other) const
Definition: PagedArray.h:621
bool operator!=(const Iterator &other) const
Definition: PagedArray.h:671
ConstIterator begin() const
Return a const iterator pointing to the first element.
Definition: PagedArray.h:379
void resize(size_t size)
Resize this array to the specified size.
Definition: PagedArray.h:287
ConstIterator operator++(int)
Definition: PagedArray.h:606
Index64 memUsage(const TreeT &tree, bool threaded=true)
Return the total amount of memory in bytes occupied by this tree.
Definition: Count.h:493
void fill(const ValueType &v)
Set all elements in the page table to the specified value.
Definition: PagedArray.h:239
difference_type operator-(const ConstIterator &other) const
Definition: PagedArray.h:617
Iterator operator++(int)
Definition: PagedArray.h:657
size_t pos() const
Definition: PagedArray.h:678
Iterator & operator--()
Definition: PagedArray.h:655
static size_t pageSize()
Return the number of elements per memory page.
Definition: PagedArray.h:333
Concurrent, page-based, dynamically-sized linear data structure with O(1) random access and STL-compl...
Definition: PagedArray.h:142
bool isValid() const
Definition: PagedArray.h:677
ConstIterator(const ConstIterator &other)
Definition: PagedArray.h:596
ConstIterator operator+(const difference_type &pos) const
Definition: PagedArray.h:615
ValueT & operator[](const size_t i)
Definition: PagedArray.h:700
void clear()
Removes all elements from the array and delete all pages.
Definition: PagedArray.h:358
bool operator==(const ConstIterator &other) const
Definition: PagedArray.h:619
ValueBuffer(PagedArray &parent)
Constructor from a PageArray.
Definition: PagedArray.h:544
size_t pageCount() const
Return the number of allocated memory pages.
Definition: PagedArray.h:330
size_t size() const
Return the number of elements in this array.
Definition: PagedArray.h:319
Iterator & operator+=(const difference_type &pos)
Definition: PagedArray.h:664
bool operator>=(const Iterator &other) const
Definition: PagedArray.h:672
ValueT * data()
Definition: PagedArray.h:706
size_t capacity() const
Return the maximum number of elements that this array can contain without allocating more memory page...
Definition: PagedArray.h:323
ConstIterator end() const
Return a const iterator pointing to the past-the-last element.
Definition: PagedArray.h:389
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
ConstIterator & operator+=(const difference_type &pos)
Definition: PagedArray.h:613
ValueBuffer getBuffer()
Definition: PagedArray.h:179
const ValueT & operator[](const difference_type &pos) const
Definition: PagedArray.h:611
Page()
Definition: PagedArray.h:696
typename BaseT::difference_type difference_type
Definition: PagedArray.h:643
ConstIterator & operator-=(const difference_type &pos)
Definition: PagedArray.h:614
void flush()
Manually transfers the values in this buffer to the parent PagedArray.
Definition: PagedArray.h:566
ConstIterator(const PagedArray &parent, size_t pos=0)
Definition: PagedArray.h:595
Definition: PagedArray.h:688
ValueBuffer(const ValueBuffer &other)
Definition: PagedArray.h:547
ConstIterator & operator++()
Definition: PagedArray.h:603
ConstIterator()
Definition: PagedArray.h:594
typename BaseT::difference_type difference_type
Definition: PagedArray.h:592
bool operator!=(const ConstIterator &other) const
Definition: PagedArray.h:620
bool operator<=(const ConstIterator &other) const
Definition: PagedArray.h:622
Definition: Exceptions.h:13
size_t push_back_unsafe(const ValueType &value)
Definition: PagedArray.h:192
void invSort()
Parallel sort of all the elements in descending order.
Definition: PagedArray.h:396
ValueT value
Definition: GridBuilder.h:1290
const ValueT * operator->() const
Definition: PagedArray.h:610
ConstIterator operator--(int)
Definition: PagedArray.h:607
ValueT * operator->() const
Definition: PagedArray.h:661
Iterator operator+(const difference_type &pos) const
Definition: PagedArray.h:666
SharedPtr< PagedArray > Ptr
Definition: PagedArray.h:153
void sort(Functor func)
Parallel sort of all the elements based on a custom functor with the api:
Definition: PagedArray.h:404
void copy(ValueType *p) const
Definition: PagedArray.h:271
static Ptr create()
Return a shared pointer to a new instance of this class.
Definition: PagedArray.h:166
std::iterator< std::random_access_iterator_tag, ValueT > BaseT
Definition: PagedArray.h:591
const ValueType & operator[](size_t i) const
Return a const-reference to the value at the specified offset.
Definition: PagedArray.h:228
bool isEmpty() const
Return true if the container contains no elements.
Definition: PagedArray.h:345
bool operator==(const Iterator &other) const
Definition: PagedArray.h:670
Iterator operator--(int)
Definition: PagedArray.h:658
void sort()
Parallel sort of all the elements in ascending order.
Definition: PagedArray.h:393
Iterator & operator-=(const difference_type &pos)
Definition: PagedArray.h:665
ValueT * mData
Definition: PagedArray.h:714
Iterator begin()
Return a non-const iterator pointing to the first element.
Definition: PagedArray.h:367
ValueType & operator[](size_t i)
Return a reference to the value at the specified offset.
Definition: PagedArray.h:215
ConstIterator & operator=(const ConstIterator &other)
Definition: PagedArray.h:597
ConstIterator cbegin() const
Return a const iterator pointing to the first element.
Definition: PagedArray.h:378
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
std::shared_ptr< T > SharedPtr
Definition: Types.h:114
PagedArrayType & parent() const
Return a reference to the parent PagedArray.
Definition: PagedArray.h:572
bool isValid() const
Definition: PagedArray.h:626
size_t size() const
Return the current number of elements cached in this buffer.
Definition: PagedArray.h:574
bool operator<(const Tuple< SIZE, T0 > &t0, const Tuple< SIZE, T1 > &t1)
Definition: Tuple.h:174
ConstIterator cend() const
Return a const iterator pointing to the past-the-last element.
Definition: PagedArray.h:388
#define OPENVDB_VERSION_NAME
The version namespace name for this library version.
Definition: version.h.in:121
static size_t memUsage()
Definition: PagedArray.h:694
ValueT & operator*() const
Definition: PagedArray.h:660
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
bool operator>(const Tuple< SIZE, T0 > &t0, const Tuple< SIZE, T1 > &t1)
Definition: Tuple.h:186
void copy(ValueType *dst, size_t n) const
Definition: PagedArray.h:709
#define OPENVDB_USE_VERSION_NAMESPACE
Definition: version.h.in:212
std::iterator< std::random_access_iterator_tag, ValueT > BaseT
Definition: PagedArray.h:642
~Page()
Definition: PagedArray.h:697
ConstIterator & operator--()
Definition: PagedArray.h:604
Definition: PagedArray.h:638
Iterator & operator++()
Definition: PagedArray.h:654
const ValueT & operator*() const
Definition: PagedArray.h:609