HDK
|
Concurrent, page-based, dynamically-sized linear data structure with O(1) random access and STL-compliant iterators. It is primarily intended for applications that concurrently insert (a possibly unkown number of) elements into a dynamically growing linear array, and fast random access to said elements. More...
#include <PagedArray.h>
Classes | |
class | ConstIterator |
class | Iterator |
class | Page |
class | ValueBuffer |
Public Types | |
using | ValueType = ValueT |
using | Ptr = SharedPtr< PagedArray > |
Public Member Functions | |
PagedArray () | |
Default constructor. More... | |
~PagedArray () | |
Destructor removed all allocated pages. More... | |
PagedArray (const PagedArray &)=delete | |
PagedArray & | operator= (const PagedArray &)=delete |
ValueBuffer | getBuffer () |
size_t | push_back_unsafe (const ValueType &value) |
void | shrink_to_fit () |
Reduce the page table to fix the current size. More... | |
ValueType & | operator[] (size_t i) |
Return a reference to the value at the specified offset. More... | |
const ValueType & | operator[] (size_t i) const |
Return a const-reference to the value at the specified offset. More... | |
void | fill (const ValueType &v) |
Set all elements in the page table to the specified value. More... | |
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 count elements long. More... | |
void | copy (ValueType *p) const |
void | resize (size_t size) |
Resize this array to the specified size. More... | |
void | resize (size_t size, const ValueType &v) |
Resize this array to the specified size and initialize all values to v. More... | |
size_t | size () const |
Return the number of elements in this array. More... | |
size_t | capacity () const |
Return the maximum number of elements that this array can contain without allocating more memory pages. More... | |
size_t | freeCount () const |
Return the number of additional elements that can be added to this array without allocating more memory pages. More... | |
size_t | pageCount () const |
Return the number of allocated memory pages. More... | |
size_t | memUsage () const |
Return the memory footprint of this array in bytes. More... | |
bool | isEmpty () const |
Return true if the container contains no elements. More... | |
bool | isPartiallyFull () const |
Return true if the page table is partially full, i.e. the last non-empty page contains less than pageSize() elements. More... | |
void | clear () |
Removes all elements from the array and delete all pages. More... | |
Iterator | begin () |
Return a non-const iterator pointing to the first element. More... | |
Iterator | end () |
Return a non-const iterator pointing to the past-the-last element. More... | |
void | sort () |
Parallel sort of all the elements in ascending order. More... | |
void | invSort () |
Parallel sort of all the elements in descending order. More... | |
void | merge (PagedArray &other) |
Transfer all the elements (and pages) from the other array to this array. More... | |
void | print (std::ostream &os=std::cout) const |
Print information for debugging. More... | |
ConstIterator | cbegin () const |
Return a const iterator pointing to the first element. More... | |
ConstIterator | begin () const |
Return a const iterator pointing to the first element. More... | |
ConstIterator | cend () const |
Return a const iterator pointing to the past-the-last element. More... | |
ConstIterator | end () const |
Return a const iterator pointing to the past-the-last element. More... | |
template<typename Functor > | |
void | sort (Functor func) |
Parallel sort of all the elements based on a custom functor with the api: More... | |
Static Public Member Functions | |
static Ptr | create () |
Return a shared pointer to a new instance of this class. More... | |
static size_t | pageSize () |
Return the number of elements per memory page. More... | |
static size_t | log2PageSize () |
Return log2 of the number of elements per memory page. More... | |
Friends | |
class | ValueBuffer |
Concurrent, page-based, dynamically-sized linear data structure with O(1) random access and STL-compliant iterators. It is primarily intended for applications that concurrently insert (a possibly unkown number of) elements into a dynamically growing linear array, and fast random access to said elements.
This data structure employes contiguous pages of elements (a std::deque) which avoids moving data when the capacity is out-grown and new pages are allocated. The size of the pages can be controlled with the Log2PageSize template parameter (defaults to 1024 elements of type ValueT).
There are three fundamentally different ways to insert elements to this container - each with different advanteges and disadvanteges.
The simplest way to insert elements is to use PagedArray::push_back_unsafe which is not thread-safe:
The fastest way (by far) to insert elements is by means of a PagedArray::ValueBuffer:
or
or with TBB task-based multi-threading:
or with TBB thread-local storage for even better performance (due to fewer concurrent instantiations of partially full ValueBuffers)
This technique generally outperforms PagedArray::push_back_unsafe, std::vector::push_back, std::deque::push_back and even tbb::concurrent_vector::push_back. Additionally it is thread-safe as long as each thread has it's own instance of a PagedArray::ValueBuffer. The only disadvantage is the ordering of the elements is undefined if multiple instance of a PagedArray::ValueBuffer are employed. This is typically the case in the context of multi-threading, where the ordering of inserts are undefined anyway. Note that a local scope can be used to guarentee that the ValueBuffer has inserted all its elements by the time the scope ends. Alternatively the ValueBuffer can be explicitly flushed by calling ValueBuffer::flush.
The third way to insert elements is to resize the container and use random access, e.g.
or in terms of the random access iterator
While this approach is both fast and thread-safe it suffers from the major disadvantage that the problem size, i.e. number of elements, needs to be known in advance. If that's the case you might as well consider using std::vector or a raw c-style array! In other words the PagedArray is most useful in the context of applications that involve multi-threading of dynamically growing linear arrays that require fast random access.
Definition at line 143 of file PagedArray.h.
using openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize >::Ptr = SharedPtr<PagedArray> |
Definition at line 154 of file PagedArray.h.
using openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize >::ValueType = ValueT |
Definition at line 153 of file PagedArray.h.
|
inline |
Default constructor.
Definition at line 157 of file PagedArray.h.
|
inline |
Destructor removed all allocated pages.
Definition at line 160 of file PagedArray.h.
|
delete |
|
inline |
Return a non-const iterator pointing to the first element.
Definition at line 368 of file PagedArray.h.
|
inline |
Return a const iterator pointing to the first element.
Definition at line 380 of file PagedArray.h.
|
inline |
Return the maximum number of elements that this array can contain without allocating more memory pages.
Definition at line 324 of file PagedArray.h.
|
inline |
Return a const iterator pointing to the first element.
Definition at line 379 of file PagedArray.h.
|
inline |
Return a const iterator pointing to the past-the-last element.
Definition at line 389 of file PagedArray.h.
|
inline |
Removes all elements from the array and delete all pages.
Definition at line 359 of file PagedArray.h.
|
inline |
Copy the first count values in this PageArray into a raw c-style array, assuming it to be at least count elements long.
p | pointer to an array that will used as the destination of the copy. |
count | number of elements to be copied. |
Definition at line 255 of file PagedArray.h.
|
inline |
Definition at line 272 of file PagedArray.h.
|
inlinestatic |
Return a shared pointer to a new instance of this class.
Definition at line 167 of file PagedArray.h.
|
inline |
Return a non-const iterator pointing to the past-the-last element.
Definition at line 375 of file PagedArray.h.
|
inline |
Return a const iterator pointing to the past-the-last element.
Definition at line 390 of file PagedArray.h.
|
inline |
Set all elements in the page table to the specified value.
v | value to be filled in all the existing pages of this PagedArray. |
Definition at line 240 of file PagedArray.h.
|
inline |
Return the number of additional elements that can be added to this array without allocating more memory pages.
Definition at line 328 of file PagedArray.h.
|
inline |
Definition at line 180 of file PagedArray.h.
|
inline |
Parallel sort of all the elements in descending order.
Definition at line 397 of file PagedArray.h.
|
inline |
Return true if the container contains no elements.
Definition at line 346 of file PagedArray.h.
|
inline |
Return true if the page table is partially full, i.e. the last non-empty page contains less than pageSize() elements.
When the page table is partially full calling merge() or using a ValueBuffer will rearrange the ordering of existing elements.
Definition at line 354 of file PagedArray.h.
|
inlinestatic |
Return log2 of the number of elements per memory page.
Definition at line 337 of file PagedArray.h.
|
inline |
Return the memory footprint of this array in bytes.
Definition at line 340 of file PagedArray.h.
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize >::merge | ( | PagedArray< ValueT, Log2PageSize > & | other | ) |
Transfer all the elements (and pages) from the other array to this array.
other | non-const reference to the PagedArray that will be merged into this PagedArray. |
Definition at line 476 of file PagedArray.h.
|
delete |
|
inline |
Return a reference to the value at the specified offset.
i | linear offset of the value to be accessed. |
Definition at line 216 of file PagedArray.h.
|
inline |
Return a const-reference to the value at the specified offset.
i | linear offset of the value to be accessed. |
Definition at line 229 of file PagedArray.h.
|
inline |
Return the number of allocated memory pages.
Definition at line 331 of file PagedArray.h.
|
inlinestatic |
Return the number of elements per memory page.
Definition at line 334 of file PagedArray.h.
|
inline |
Print information for debugging.
Definition at line 418 of file PagedArray.h.
|
inline |
value | value to be added to this PagedArray |
Definition at line 193 of file PagedArray.h.
|
inline |
Resize this array to the specified size.
size | number of elements that this PageArray will contain. |
Will grow or shrink the page table to contain the specified number of elements. It will affect the size(), iteration will go over all those elements, push_back will insert after them and operator[] can be used directly access them.
Definition at line 288 of file PagedArray.h.
|
inline |
Resize this array to the specified size and initialize all values to v.
size | number of elements that this PageArray will contain. |
v | value of all the size values. |
Will grow or shrink the page table to contain the specified number of elements. It will affect the size(), iteration will go over all those elements, push_back will insert after them and operator[] can be used directly access them.
Definition at line 313 of file PagedArray.h.
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize >::shrink_to_fit | ( | ) |
Reduce the page table to fix the current size.
Definition at line 462 of file PagedArray.h.
|
inline |
Return the number of elements in this array.
Definition at line 320 of file PagedArray.h.
|
inline |
Parallel sort of all the elements in ascending order.
Definition at line 394 of file PagedArray.h.
|
inline |
Parallel sort of all the elements based on a custom functor with the api:
which returns true if a comes before b.
Definition at line 405 of file PagedArray.h.
|
friend |
Definition at line 430 of file PagedArray.h.