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