Embedded Multicore Building Blocks V1.0.0
Classes
Value Pool Concept

Concept for thread-safe value pools. More...

Classes

class  embb::containers::LockFreeTreeValuePool< Type, Undefined, PoolAllocator, TreeAllocator >
 Lock-free value pool using binary tree construction. More...
 
class  embb::containers::WaitFreeArrayValuePool< Type, Undefined, Allocator >
 Wait-free value pool using array construction. More...
 

Detailed Description

Concept for thread-safe value pools.

Description
A value pool is a multi-set of elements, where each element has a unique, continuous (starting with 0) index. The elements cannot be modified and are given at construction time by providing first/last iterators.
A value pool provides two primary operations: Allocate and Free. Allocate allocates an element/index "pair" (index via return, element via reference parameter) from the pool, and Free returns an element/index pair to the pool. To guarantee linearizability, element is not allowed to be modified between Allocate and Free. It is only allowed to free elements that have previously been allocated. The Allocate function does not guarantee an order on which indices are allocated. The count of elements that can be allocated with Allocate might be smaller than the count of elements, the pool is initialized with. This might be because of implementation details and respective concurrency effects: for example, if indices are managed within a queue, one has to protect queue elements from concurrency effects (reuse and access). As long as a thread potentially accesses a node (and with that an index), the respective index cannot not be given out to the user, even if being logically not part of the pool anymore. However, the user might want to guarantee a certain amount of indices to the user. Therefore, the static GetMinimumElementCountForGuaranteedCapacity method is used. The user passes the count of indices to this method that shall be guaranteed by the pool. The method returns the count on indices, the pool has to be initialized with in order to guarantee this count on indices.
Requirements
  • Let Pool be the pool class
  • Let Type be the element type of the pool. Atomic operations must be possible on Type.
  • Let b, d be objects of type Type
  • Let i, j be forward iterators supporting std::distance.
  • Let c be an object of type Type&
  • Let e be a value of type int
  • Let f be a value of type int
Valid Expressions
Expression Return type Description
Pool<Type, b>(i, j)
Nothing Constructs a value pool holding elements of type Type, where b is the bottom element. The bottom element cannot be stored in the pool, it is exclusively used to mark empty cells. The pool initially contains std::distance(i, j) elements which are copied during construction from the range [i, j]. A concrete class satisfying the value pool concept might provide additional template parameters for specifying allocators.
Allocate(c)
int Allocates an element/index "pair" from the pool. Returns -1, if no element is available, i.e., the pool is empty. Otherwise, returns the index of the element in the pool. The value of the pool element is written into parameter reference c.
Free(d, e)
void Returns an element d to the pool, where e is its index. The values of d and e have to match the values of the previous call to Allocate. For each allocated element, Free must be called exactly once.
GetMinimumElementCountForGuaranteedCapacity(f)
void Static method, returns the count of indices, the user has to initialize the pool with in order to guarantee a count of f elements (irrespective of concurrency effects).