Embedded Multicore Building Blocks V1.0.0
lock_free_tree_value_pool.h
1 /*
2  * Copyright (c) 2014-2017, Siemens AG. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  * 1. Redistributions of source code must retain the above copyright notice,
8  * this list of conditions and the following disclaimer.
9  *
10  * 2. Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
15  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
18  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24  * POSSIBILITY OF SUCH DAMAGE.
25  */
26 
27 #ifndef EMBB_CONTAINERS_LOCK_FREE_TREE_VALUE_POOL_H_
28 #define EMBB_CONTAINERS_LOCK_FREE_TREE_VALUE_POOL_H_
29 
30 #include <embb/base/atomic.h>
31 #include <embb/base/memory_allocation.h>
32 #include <iterator>
33 #include <utility>
34 
35 namespace embb {
36 namespace containers {
52 template<typename Type,
53  Type Undefined,
56 >
58  /*
59  * Description of the algorithm:
60  *
61  * The binary tree is split into two parts, the leaves and the binary tree
62  * above the leaves. Example:
63  *
64  * b
65  * b b
66  * b b b b
67  * l l l l l l l l
68  *
69  * The elements b are the elements "above", the leaves l are the pool
70  * elements. The elements b are represented by the array tree, the elements l
71  * be the array pool.
72  *
73  * A binary tree for storing n elements has k = 2^j leaves, where j is the
74  * smallest number such that n <= 2^j holds. The variable with name size
75  * stores k. The variable tree_size holds the number of elements b, the tree
76  * above. It is size - 1. The array pool is not constructed with size k, but
77  * with the real size n, as only the first n elements from the pool array are
78  * accessed. The tree is used as if elements l and b form a binary tree
79  * together and would be stored in one array. That makes the algorithm
80  * easier.
81  *
82  * The elements b store the number of not allocated cells below. The pool
83  * elements l are either not allocated, and store the respective element, or
84  * are allocated and contain the element Undefined.
85  *
86  * A tree storing the elements a,b,c,d,e would therefore look like this:
87  *
88  * 8
89  * 4 1
90  * 2 2 1 0
91  * pool[]: a b c d e
92  *
93  * tree = {8,4,1,2,2,1,0}
94  * pool = {'a','b','c','d','e'}
95  * size = 8
96  * tree_size = 7
97  *
98  * The algorithm for allocating an element starts at the root node and
99  * recursively traverses the tree. It tries to decrement a node (a decrement
100  * is actually a conditional decrement, i.e., a node is decremented if the
101  * result is not less than 0. This is the place, where the algorithm is not
102  * wait-free anymore, as this cannot be implemented atomically.) and if
103  * successful, calls itself on the left child, if not successful, on the right
104  * child. If the algorithm encounters a leaf, it tries to reserve it by doing
105  * a CAS to Undefined. If that is successful, the element together with its
106  * pool index are returned. Otherwise, no element is returned.
107  *
108  * The algorithm for freeing an element is much more simple. The element is
109  * stored at the pool position it was allocated from and then, the algorithm
110  * walks the tree towards the root, thereby increasing the value of each
111  * visited node.
112  *
113  * For future work, the memory consumption could be further reduced by
114  * "stripping" away unused cells in the binary tree. In the example above,
115  * that would be cell 0 in the row "2 2 1 0".
116  */
117  private:
118  // Private constructor
120 
121  // Prevent copy-construction
123 
124  // Prevent assignment
125  LockFreeTreeValuePool& operator=(const LockFreeTreeValuePool&);
126 
127  // See algorithm description above
128  int size_;
129 
130  // See algorithm description above
131  int tree_size_;
132 
133  // See algorithm description above
134  int real_size_;
135 
136  // The tree above the pool
138 
139  // The actual pool
141 
142  // respective allocator
143  PoolAllocator pool_allocator_;
144 
145  // respective allocator
146  TreeAllocator tree_allocator_;
147 
153  static int GetSmallestPowerByTwoValue(int value);
154 
160  bool IsLeaf(
161  int node
163  );
164 
170  bool IsValid(
171  int node
173  );
174 
181  int GetLeftChildIndex(
182  int node
184  );
185 
192  int GetRightChildIndex(
193  int node
195  );
196 
201  int NodeIndexToPoolIndex(
202  int node
204  );
205 
210  int PoolIndexToNodeIndex(int index);
211 
217  bool IsRoot(
218  int node
220  );
221 
227  int GetParentNode(
228  int node
230  );
231 
240  int allocate_rec(
241  int node,
243  Type& element
245  );
246 
253  void Fill(
254  int node,
256  int elementsToStore,
258  int power2Value
260  );
261 
262  public:
268  class Iterator : public std::iterator<
269  std::forward_iterator_tag, std::pair<int, Type> > {
270  private:
271  explicit Iterator(LockFreeTreeValuePool * pool);
272  Iterator(LockFreeTreeValuePool * pool, int index);
273  void Advance();
274 
275  LockFreeTreeValuePool * pool_;
276  int index_;
277 
278  friend class LockFreeTreeValuePool;
279 
280  public:
285  Iterator();
286 
291  Iterator(
292  Iterator const & other
293  );
294 
302  Iterator const & other
303  );
304 
311  Iterator & operator ++();
312 
319  Iterator operator ++(int);
320 
328  bool operator ==(
329  Iterator const & rhs
330  );
331 
339  bool operator !=(
340  Iterator const & rhs
341  );
342 
349  std::pair<int, Type> operator *();
350  };
351 
358  Iterator Begin();
359 
367  Iterator End();
368 
381  template<typename ForwardIterator>
383  ForwardIterator first,
386  ForwardIterator last
389  );
390 
400  size_t capacity);
402 
409 
419  int Allocate(
420  Type & element
423  );
424 
434  void Free(
435  Type element,
437  int index
439  );
440 };
441 } // namespace containers
442 } // namespace embb
443 
444 #include <embb/containers/internal/lock_free_tree_value_pool-inl.h>
445 
446 #endif // EMBB_CONTAINERS_LOCK_FREE_TREE_VALUE_POOL_H_
Definition: lock_free_mpmc_queue.h:40
~LockFreeTreeValuePool()
Destructs the pool.
bool operator!=(Iterator const &rhs)
Compares two iterators for inequality.
Iterator & operator=(Iterator const &other)
Copies an iterator.
Forward iterator to iterate over the allocated elements of the pool.
Definition: lock_free_tree_value_pool.h:268
int Allocate(Type &element)
Allocates an element from the pool.
Lock-free value pool using binary tree construction.
Definition: lock_free_tree_value_pool.h:57
Allocator according to the C++ standard.
Definition: memory_allocation.h:525
void Free(Type element, int index)
Returns an element to the pool.
Iterator Begin()
Gets a forward iterator to the first allocated element in the pool.
static size_t GetMinimumElementCountForGuaranteedCapacity(size_t capacity)
Due to concurrency effects, a pool might provide less elements than managed by it.
Iterator & operator++()
Pre-increments an iterator.
bool operator==(Iterator const &rhs)
Compares two iterators for equality.
Iterator()
Constructs an invalid iterator.
Iterator End()
Gets a forward iterator pointing after the last allocated element in the pool.
std::pair< int, Type > operator*()
Dereferences the iterator.