GCC Code Coverage Report

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