HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT > Class Template Reference

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

typedef ValueT ValueType
 

Public Member Functions

 PagedArray ()=default
 Default constructor. More...
 
 ~PagedArray ()
 Destructor removed all allocated pages. More...
 
 PagedArray (const PagedArray &)=delete
 
PagedArrayoperator= (const PagedArray &)=delete
 
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 returns the linear offset for the inserted element. More...
 
size_t push_back_unsafe (const ValueType &value)
 Slightly faster than the thread-safe push_back above. More...
 
OPENVDB_DEPRECATED ValueType pop_back ()
 Returns the last element, decrements the size by one. More...
 
void shrink_to_fit ()
 Reduce the page table to fix the current size. More...
 
ValueTypeoperator[] (size_t i)
 Return a reference to the value at the specified offset. More...
 
const ValueTypeoperator[] (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 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
 

Detailed Description

template<typename ValueT, size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
class openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >

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.

Note
Multiple threads can grow the page-table and push_back new elements concurrently. A ValueBuffer provides accelerated and threadsafe push_back at the cost of potentially re-ordering elements (when multiple instances are used).

This data structure employes contiguous pages of elements (like 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). The TableT template parameter is used to define the data structure for the page table. The default, std::vector, offers fast random access in exchange for slower push_back, whereas std:deque offers faster push_back but slower random access.

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 e.g.

PagedArray<size_t> array;
for (size_t i=0; i<100000; ++i) array.push_back(i);

or with TBB task-based multi-threading

PagedArray<size_t> array;
tbb::parallel_for(
tbb::blocked_range<size_t>(0, 10000, array.pageSize()),
[&array](const tbb::blocked_range<size_t>& range) {
for (size_t i=range.begin(); i!=range.end(); ++i) array.push_back(i);
}
);

PagedArray::push_back has the advantage that it's thread-safe and preserves the ordering of the inserted elements. In fact it returns the linear offset to the added element which can then be used for fast O(1) random access. The disadvantage is it's the slowest of the three different ways of inserting elements.

The fastest way (by far) to insert elements by means of a PagedArray::ValueBuffer, e.g.

PagedArray<size_t> array;
PagedArray<size_t>::ValueBuffer buffer(array);
for (size_t i=0; i<100000; ++i) buffer.push_back(i);
buffer.flush();

or

PagedArray<size_t> array;
{
//local scope of a single thread
PagedArray<size_t>::ValueBuffer buffer(array);
for (size_t i=0; i<100000; ++i) buffer.push_back(i);
}

or with TBB task-based multi-threading

PagedArray<size_t> array;
tbb::parallel_for(
tbb::blocked_range<size_t>(0, 10000, array.pageSize()),
[&array](const tbb::blocked_range<size_t>& range) {
PagedArray<size_t>::ValueBuffer buffer(array);
for (size_t i=range.begin(); i!=range.end(); ++i) buffer.push_back(i);
}
);

or with TBB thread-local storage for even better performance (due to fewer concurrent instantiations of partially full ValueBuffers)

PagedArray<size_t> array;
PagedArray<size_t>::ValueBuffer exemplar(array);//dummy used for initialization
tbb::enumerable_thread_specific<PagedArray<size_t>::ValueBuffer>
pool(exemplar);//thread local storage pool of ValueBuffers
tbb::parallel_for(
tbb::blocked_range<size_t>(0, 10000, array.pageSize()),
[&pool](const tbb::blocked_range<size_t>& range) {
PagedArray<size_t>::ValueBuffer &buffer = pool.local();
for (size_t i=range.begin(); i!=range.end(); ++i) buffer.push_back(i);
}
);
for (auto i=pool.begin(); i!=pool.end(); ++i) i->flush();

This technique generally outperforms PagedArray::push_back, 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.

PagedArray<int> array;
array.resize(100000);
for (int i=0; i<100000; ++i) array[i] = i;

or in terms of the random access iterator

PagedArray<int> array;
array.resize(100000);
for (auto i=array.begin(); i!=array.end(); ++i) *i = i.pos();

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 188 of file PagedArray.h.

Member Typedef Documentation

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
typedef ValueT openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::ValueType

Definition at line 201 of file PagedArray.h.

Constructor & Destructor Documentation

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::PagedArray ( )
default

Default constructor.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::~PagedArray ( )
inline

Destructor removed all allocated pages.

Definition at line 207 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::PagedArray ( const PagedArray< ValueT, Log2PageSize, TableT > &  )
delete

Member Function Documentation

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
Iterator openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::begin ( void  )
inline

Return a non-const iterator pointing to the first element.

Definition at line 454 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
ConstIterator openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::begin ( void  ) const
inline

Return a const iterator pointing to the first element.

Definition at line 466 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
size_t openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::capacity ( ) const
inline

Return the maximum number of elements that this array can contain without allocating more memory pages.

Definition at line 410 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
ConstIterator openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::cbegin ( ) const
inline

Return a const iterator pointing to the first element.

Definition at line 465 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
ConstIterator openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::cend ( ) const
inline

Return a const iterator pointing to the past-the-last element.

Warning
Iterator does not point to a valid element and should not be dereferenced!

Definition at line 475 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::clear ( void  )
inline

Removes all elements from the array and delete all pages.

Warning
Not thread-safe!

Definition at line 445 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
bool openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::copy ( ValueType p,
size_t  count 
) const
inline

Copy the first count values in this PageArray into a raw c-style array, assuming it to be at least count elements long.

Parameters
ppointer to an array that will used as the destination of the copy.
countnumber of elements to be copied.

Definition at line 341 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::copy ( ValueType p) const
inline

Definition at line 358 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
Iterator openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::end ( void  )
inline

Return a non-const iterator pointing to the past-the-last element.

Warning
Iterator does not point to a valid element and should not be dereferenced!

Definition at line 461 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
ConstIterator openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::end ( void  ) const
inline

Return a const iterator pointing to the past-the-last element.

Warning
Iterator does not point to a valid element and should not be dereferenced!

Definition at line 476 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::fill ( const ValueType v)
inline

Set all elements in the page table to the specified value.

Parameters
vvalue to be filled in all the existing pages of this PagedArray.
Note
Multi-threaded

Definition at line 326 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
size_t openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::freeCount ( ) const
inline

Return the number of additional elements that can be added to this array without allocating more memory pages.

Definition at line 414 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::invSort ( )
inline

Parallel sort of all the elements in descending order.

Definition at line 483 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
bool openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::isEmpty ( ) const
inline

Return true if the container contains no elements.

Definition at line 432 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
bool openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::isPartiallyFull ( ) const
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 440 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
static size_t openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::log2PageSize ( )
inlinestatic

Return log2 of the number of elements per memory page.

Definition at line 423 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
size_t openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::memUsage ( ) const
inline

Return the memory footprint of this array in bytes.

Definition at line 426 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize, template< typename...> class TableT>
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::merge ( PagedArray< ValueT, Log2PageSize, TableT > &  other)

Transfer all the elements (and pages) from the other array to this array.

Parameters
othernon-const reference to the PagedArray that will be merged into this PagedArray.
Note
The other PagedArray is empty on return.
Warning
The ordering of elements is undefined if this page table is partially full!

Definition at line 562 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
PagedArray& openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::operator= ( const PagedArray< ValueT, Log2PageSize, TableT > &  )
delete
template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
ValueType& openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::operator[] ( size_t  i)
inline

Return a reference to the value at the specified offset.

Parameters
ilinear offset of the value to be accessed.
Note
This random access has constant time complexity.
Warning
It is assumed that the i'th element is already allocated!

Definition at line 302 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
const ValueType& openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::operator[] ( size_t  i) const
inline

Return a const-reference to the value at the specified offset.

Parameters
ilinear offset of the value to be accessed.
Note
This random access has constant time complexity.
Warning
It is assumed that the i'th element is already allocated!

Definition at line 315 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
size_t openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::pageCount ( ) const
inline

Return the number of allocated memory pages.

Definition at line 417 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
static size_t openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::pageSize ( )
inlinestatic

Return the number of elements per memory page.

Definition at line 420 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
OPENVDB_DEPRECATED ValueType openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::pop_back ( )
inline

Returns the last element, decrements the size by one.

Deprecated:
This method will be removed in the near future
Bug:
This method can produce unexpected results if used in combination with a ValueBuffer (due to empty pages). However,it can safely be used the push_back methods defined above.

Consider subsequnetly calling shrink_to_fit to reduce the page table to match the new size.

Note
Calling this method on an empty containter is undefined (as is also the case for std containers).
Warning
If values were added to the container by means of multiple ValueBuffers the last value might not be what you expect since the ordering is generally not perserved. Only PagedArray::push_back preserves the ordering (or a single instance of a ValueBuffer).

Definition at line 282 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::print ( std::ostream &  os = std::cout) const
inline

Print information for debugging.

Definition at line 504 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
size_t openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::push_back ( const ValueType value)
inline

Thread safe insertion, adds a new element at the end and increases the container size by one and returns the linear offset for the inserted element.

Parameters
valuevalue to be added to this PagedArray

Constant time complexity. May allocate a new page.

Definition at line 236 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
size_t openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::push_back_unsafe ( const ValueType value)
inline

Slightly faster than the thread-safe push_back above.

Parameters
valuevalue to be added to this PagedArray
Note
For best performance consider using the ValueBuffer!
Warning
Not thread-safe!

Definition at line 251 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::resize ( size_t  size)
inline

Resize this array to the specified size.

Parameters
sizenumber 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.

Note
No reserve method is implemented due to efficiency concerns (especially for the ValueBuffer) from having to deal with empty pages.
Warning
Not thread-safe!

Definition at line 374 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::resize ( size_t  size,
const ValueType v 
)
inline

Resize this array to the specified size and initialize all values to v.

Parameters
sizenumber of elements that this PageArray will contain.
vvalue 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.

Note
No reserve method is implemented due to efficiency concerns (especially for the ValueBuffer) from having to deal with empty pages.
Warning
Not thread-safe!

Definition at line 399 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize, template< typename...> class TableT>
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::shrink_to_fit ( )

Reduce the page table to fix the current size.

Warning
Not thread-safe!

Definition at line 548 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
size_t openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::size ( void  ) const
inline

Return the number of elements in this array.

Definition at line 406 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::sort ( void  )
inline

Parallel sort of all the elements in ascending order.

Definition at line 480 of file PagedArray.h.

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
template<typename Functor >
void openvdb::OPENVDB_VERSION_NAME::util::PagedArray< ValueT, Log2PageSize, TableT >::sort ( Functor  func)
inline

Parallel sort of all the elements based on a custom functor with the api:

bool operator()(const ValueT& a, const ValueT& b)

which returns true if a comes before b.

Definition at line 491 of file PagedArray.h.

Friends And Related Function Documentation

template<typename ValueT , size_t Log2PageSize = 10UL, template< typename...> class TableT = std::vector>
friend class ValueBuffer
friend

Definition at line 516 of file PagedArray.h.


The documentation for this class was generated from the following file: