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