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