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