Thread-safe grow-only dynamic array using the thread-safe allocator. More...
#include <dynamic_array.h>
Classes | |
| class | iterator |
| C++ iterator for iterating over a dynamic_array object. More... | |
| class | node |
| The array is stored as a linked list of nodes where each node points to some number of elements. More... | |
Public Member Functions | |
| dynamic_array ()=delete | |
| Constructor. | |
| dynamic_array (allocator &pool, size_t initial_size=1, double growth_factor=1.5) | |
| Constructor. More... | |
| iterator | begin (void) const |
| Return an iterator pointing to the start of the array. More... | |
| iterator | end (void) const |
| Return an iterator pointing to the end of the array. More... | |
| TYPE & | back (void) const |
| Return an reference to the final (used) element in the dynamic array. More... | |
| void | push_back (const TYPE &element) |
| Add an element to the end of the array. More... | |
| TYPE & | operator[] (size_t element) |
| Return a reference to the given element (counting from 0). More... | |
| size_t | serialise (TYPE *into, size_t size_of_into) const |
| Serialise the dynamic array into a single linear sequence. More... | |
| void | unittest_thread (size_t high) |
| Part of the unit test this method adds elements 0..high to the array. More... | |
Static Public Member Functions | |
| static void | unittest (void) |
| Unit test this class. | |
Public Attributes | |
| allocator & | pool |
| The pool allocator used for all allocation by this object. | |
| node * | head |
| Pointer to the head of the linked list of blocks of data. | |
| std::atomic< node * > | tail |
| Pointer to the tail of the linked list of blocks of data. It std::atomic<> so that it can grow lock-free. | |
| double | growth_factor |
| The next chunk in the linked list is this much larger than the previous. | |
Detailed Description
template<typename TYPE>
class JASS::dynamic_array< TYPE >
Thread-safe grow-only dynamic array using the thread-safe allocator.
The array data is stored in a linked list of chunks where each chunk is larger then the previous as the array is growing. Although random access is supported, it is slow as it is necessary to walk the linked list to find the given element (see operator[]()). The iterator, however, does not need to do this and has O(1) access time to each element.
- Template Parameters
-
TYPE The dynamic array is an array of this type.
Constructor & Destructor Documentation
◆ dynamic_array()
|
inline |
Constructor.
- Parameters
-
pool [in] The pool allocator used for all allocation done by this object. initial_size [in] The size (in elements) of the initial allocation in the linked list. growth_factor [in] The next node in the linked list stored an element this many times larger than the previous (as an integer).
Member Function Documentation
◆ back()
|
inline |
Return an reference to the final (used) element in the dynamic array.
- Returns
- Reference to the last used element in the array.
◆ begin()
|
inline |
Return an iterator pointing to the start of the array.
- Returns
- Iterator pointing to start of array.
◆ end()
|
inline |
Return an iterator pointing to the end of the array.
- Returns
- Iterator pointing to end of array.
◆ operator[]()
|
inline |
Return a reference to the given element (counting from 0).
This method must walk the linked list to find the requested element and then returns a reference to it. Since the growth factor might be 1 and the initial allocation size might be 1, the worst case for requesting the final element is O(n) where n is the number of elements in the array. Walking through the array accessing each element is therefore O(n^2) - so don't do this. The preferred method for iterating over the array is to use a for each iterator (i.e. through begin() and end()). The C++ std::array has "undefined behavior" if the given index is out-of-range. This, too, has undefined behaviour in that case.
- Parameters
-
element [in] The element to find.
◆ push_back()
|
inline |
Add an element to the end of the array.
- Parameters
-
element [in] The element to add.
◆ serialise()
|
inline |
Serialise the dynamic array into a single linear sequence.
- Parameters
-
into [out] pointer to the buffer to serialise (at most size_of_into elements) into. size_of_into [in] the amount of space (in TYPE elements) available in into (so for long[1] it would be 1).
- Returns
- The amount of space it would take to store the entire serialised array in TYPE elements.
◆ unittest_thread()
|
inline |
Part of the unit test this method adds elements 0..high to the array.
- Parameters
-
high [in] How many integer elements to add to the array.
The documentation for this class was generated from the following files:
- source/allocator_pool.h
- source/dynamic_array.h
