Embedded Multicore Building Blocks V1.0.0
Classes | Public Member Functions | Static Public Member Functions | List of all members
embb::containers::LockFreeTreeValuePool< Type, Undefined, PoolAllocator, TreeAllocator > Class Template Reference

Lock-free value pool using binary tree construction. More...

#include <lock_free_tree_value_pool.h>

Classes

class  Iterator
 Forward iterator to iterate over the allocated elements of the pool. More...
 

Public Member Functions

Iterator Begin ()
 Gets a forward iterator to the first allocated element in the pool. More...
 
Iterator End ()
 Gets a forward iterator pointing after the last allocated element in the pool. More...
 
template<typename ForwardIterator >
 LockFreeTreeValuePool (ForwardIterator first, ForwardIterator last)
 Constructs a pool and fills it with the elements in the specified range. More...
 
 ~LockFreeTreeValuePool ()
 Destructs the pool. More...
 
int Allocate (Type &element)
 Allocates an element from the pool. More...
 
void Free (Type element, int index)
 Returns an element to the pool. More...
 

Static Public Member Functions

static size_t GetMinimumElementCountForGuaranteedCapacity (size_t capacity)
 Due to concurrency effects, a pool might provide less elements than managed by it. More...
 

Detailed Description

template<typename Type, Type Undefined, class PoolAllocator = embb::base::Allocator< embb::base::Atomic<Type> >, class TreeAllocator = embb::base::Allocator < embb::base::Atomic<int> >>
class embb::containers::LockFreeTreeValuePool< Type, Undefined, PoolAllocator, TreeAllocator >

Lock-free value pool using binary tree construction.

Implemented concepts:
Value Pool Concept
See also
WaitFreeArrayValuePool
Template Parameters
TypeElement type (must support atomic operations such as int).
UndefinedBottom element (cannot be stored in the pool)
PoolAllocatorAllocator used to allocate the pool array
TreeAllocatorAllocator used to allocate the array representing the binary tree.

Constructor & Destructor Documentation

template<typename Type , Type Undefined, class PoolAllocator = embb::base::Allocator< embb::base::Atomic<Type> >, class TreeAllocator = embb::base::Allocator < embb::base::Atomic<int> >>
template<typename ForwardIterator >
embb::containers::LockFreeTreeValuePool< Type, Undefined, PoolAllocator, TreeAllocator >::LockFreeTreeValuePool ( ForwardIterator  first,
ForwardIterator  last 
)

Constructs a pool and fills it with the elements in the specified range.

Dynamic memory allocation
Let n = std::distance(first, last)) and k be the minimum number such that n <= 2^k holds. Then, ((2^k)-1) * sizeof(embb::Atomic<int>) + n*sizeof(embb::Atomic<Type>) bytes of memory are allocated.
Concurrency
Not thread-safe
See also
Value Pool Concept
Parameters
[in]firstIterator pointing to the first element of the range the pool is filled with
[in]lastIterator pointing to the last plus one element of the range the pool is filled with
template<typename Type , Type Undefined, class PoolAllocator = embb::base::Allocator< embb::base::Atomic<Type> >, class TreeAllocator = embb::base::Allocator < embb::base::Atomic<int> >>
embb::containers::LockFreeTreeValuePool< Type, Undefined, PoolAllocator, TreeAllocator >::~LockFreeTreeValuePool ( )

Destructs the pool.

Concurrency
Not thread-safe

Member Function Documentation

template<typename Type , Type Undefined, class PoolAllocator = embb::base::Allocator< embb::base::Atomic<Type> >, class TreeAllocator = embb::base::Allocator < embb::base::Atomic<int> >>
Iterator embb::containers::LockFreeTreeValuePool< Type, Undefined, PoolAllocator, TreeAllocator >::Begin ( )

Gets a forward iterator to the first allocated element in the pool.

Returns
a forward iterator pointing to the first allocated element.
Concurrency
Thread-safe and wait-free
template<typename Type , Type Undefined, class PoolAllocator = embb::base::Allocator< embb::base::Atomic<Type> >, class TreeAllocator = embb::base::Allocator < embb::base::Atomic<int> >>
Iterator embb::containers::LockFreeTreeValuePool< Type, Undefined, PoolAllocator, TreeAllocator >::End ( )

Gets a forward iterator pointing after the last allocated element in the pool.

Returns
a forward iterator pointing after the last allocated element.
Concurrency
Thread-safe and wait-free
template<typename Type , Type Undefined, class PoolAllocator = embb::base::Allocator< embb::base::Atomic<Type> >, class TreeAllocator = embb::base::Allocator < embb::base::Atomic<int> >>
static size_t embb::containers::LockFreeTreeValuePool< Type, Undefined, PoolAllocator, TreeAllocator >::GetMinimumElementCountForGuaranteedCapacity ( size_t  capacity)
static

Due to concurrency effects, a pool might provide less elements than managed by it.

However, usually one wants to guarantee a minimal capacity. The count of elements that must be given to the pool when to guarantee capacity elements is computed using this function.

Returns
count of indices the pool has to be initialized with
Parameters
[in]capacitycount of indices that shall be guaranteed
template<typename Type , Type Undefined, class PoolAllocator = embb::base::Allocator< embb::base::Atomic<Type> >, class TreeAllocator = embb::base::Allocator < embb::base::Atomic<int> >>
int embb::containers::LockFreeTreeValuePool< Type, Undefined, PoolAllocator, TreeAllocator >::Allocate ( Type &  element)

Allocates an element from the pool.

Returns
Index of the element if the pool is not empty, otherwise -1.
Concurrency
Thread-safe and lock-free
See also
Value Pool Concept
Parameters
[in,out]elementReference to the allocated element. Unchanged, if the operation was not successful.
template<typename Type , Type Undefined, class PoolAllocator = embb::base::Allocator< embb::base::Atomic<Type> >, class TreeAllocator = embb::base::Allocator < embb::base::Atomic<int> >>
void embb::containers::LockFreeTreeValuePool< Type, Undefined, PoolAllocator, TreeAllocator >::Free ( Type  element,
int  index 
)

Returns an element to the pool.

Note
The element must have been allocated with Allocate().
Concurrency
Thread-safe and lock-free
See also
Value Pool Concept
Parameters
[in]elementElement to be returned to the pool
[in]indexIndex of the element as obtained by Allocate()