iceoryx_doc  1.0.1
objectpool.hpp
1 // Copyright (c) 2019 by Robert Bosch GmbH. All rights reserved.
2 // Copyright (c) 2021 by Apex.AI Inc. All rights reserved.
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 // http://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 //
16 // SPDX-License-Identifier: Apache-2.0
17 #ifndef IOX_UTILS_OBJECTPOOL_OBJECTPOOL_HPP
18 #define IOX_UTILS_OBJECTPOOL_OBJECTPOOL_HPP
19 
20 #include <cstddef> //for size_t
21 #include <cstdint>
22 #include <utility> //for std::forward
23 
24 namespace iox
25 {
26 namespace cxx
27 {
28 // TODO: finalize API and add doxygen comments
29 // the API will be safer and more concise
30 // furthermore the free position computation will be improved to gain performance
31 
32 // note: as in e.g. std::vector, no index bounds checking for efficiency (using illegal indices leads to undefined
33 // behaviour)
34 template <typename T, int CAPACITY = 1> // TODO: use sensible and compatible type for this and NO_INDEX
36 {
37  public:
38  using Index_t = int; // TODO: choose Index_t types correctly wrt. size, conversion compatibility
39  static constexpr int NO_INDEX = -1;
40 
41  private:
42  static constexpr size_t CHUNKSIZE = sizeof(T);
43  using Chunk = char[CHUNKSIZE];
44  using Container = Chunk[CAPACITY]; // we need uninitalized memory without calling any constructors
45  // we cannot use typed C arrays for this reason, since it would call T() (maybe
46  // we could use a one element as CHUNK)
47 
48 
49  Index_t m_freeIndex{0};
50  size_t m_size{0u};
51 
52  // todo: maybe this metainformation can be combined, e.g. the data pointer == nullptr to indicate that
53  // the data is invalid
54  struct CellInfo
55  {
56  bool isValid{false}; // todo: rename into isUsed?
57  bool wasConstructed{false}; // we want to use this to determine whether T destruction should occur in destructor
58  T* data{nullptr};
59  };
60 
61  alignas(T) Container m_values;
62  CellInfo m_cellInfo[CAPACITY];
63  char* m_first;
64  char* m_last;
65 
66  public:
67  class Iterator
68  {
69  private:
70  Index_t index;
72 
73  public:
74  Iterator(Index_t index, ObjectPool<T, CAPACITY>& pool)
75  : index(index)
76  , pool(&pool)
77  {
78  }
79 
80  T& operator*()
81  {
82  return *(pool->m_cellInfo[index].data);
83  }
84 
85  // in contrast to operator* we do checking in operator->
86  // for operator* this is not as straightforward, since we need
87  // to return a reference (what should happen if iterator is end()?)
88  T* operator->()
89  {
90  if (index >= CAPACITY)
91  {
92  return nullptr;
93  }
94  if ((pool->m_cellInfo[index]).isValid)
95  {
96  return pool->m_cellInfo[index].data;
97  }
98  return nullptr;
99  }
100 
101  // pre-increment
102  Iterator& operator++()
103  {
104  for (Index_t i = index + 1; i < CAPACITY; ++i)
105  {
106  if (pool->m_cellInfo[i].isValid == true)
107  {
108  index = i;
109  return *this;
110  }
111  }
112  index = CAPACITY;
113  return *this;
114  }
115 
116  // post increment
117  Iterator operator++(int)
118  {
119  auto ret = Iterator(index, *pool);
120  for (Index_t i = index + 1; i < CAPACITY; ++i)
121  {
122  if (pool->m_cellInfo[i].isValid == true)
123  {
124  index = i;
125  return ret;
126  }
127  }
128  index = CAPACITY;
129  return ret;
130  }
131 
132  bool operator!=(const Iterator& other) const
133  {
134  return (this->index != other.index || this->pool != other.pool);
135  }
136 
137  bool operator==(const Iterator& other) const
138  {
139  return (this->index == other.index && this->pool == other.pool);
140  }
141  };
142 
143  Iterator begin()
144  {
145  for (Index_t i = 0; i < CAPACITY; ++i)
146  {
147  if (m_cellInfo[i].isValid == true)
148  {
149  return Iterator(i, *this);
150  }
151  }
152  return Iterator(CAPACITY, *this);
153  }
154 
155  Iterator end()
156  {
157  return Iterator(CAPACITY, *this);
158  }
159 
160  ObjectPool()
161  : m_first(reinterpret_cast<char*>(&(m_values[0])))
162  , m_last(reinterpret_cast<char*>(&(m_values[CAPACITY - 1])))
163  {
164  }
165 
166 
167  ~ObjectPool()
168  {
169  // destroy objects if they where constructed by the pool
170  for (Index_t i = 0; i < CAPACITY; ++i)
171  {
172  if (m_cellInfo[i].isValid && m_cellInfo[i].wasConstructed)
173  {
174  m_cellInfo[i].data->~T();
175  }
176  }
177  }
178 
179  //***********************************index API ***********************************************************
180 
181  Index_t reserve()
182  {
183  auto index = nextFree();
184 
185  if (index >= 0)
186  {
187  m_freeIndex = index;
188  m_cellInfo[m_freeIndex].isValid = true;
189  m_cellInfo[m_freeIndex].wasConstructed = false;
190  ++m_size;
191  }
192 
193  return index;
194  }
195 
196  Index_t construct()
197  {
198  auto index = nextFree();
199 
200  if (index >= 0)
201  {
202  m_freeIndex = index;
203  m_cellInfo[index].data = new (&m_values[index]) T; // use placement new
204  m_cellInfo[m_freeIndex].isValid = true;
205  m_cellInfo[m_freeIndex].wasConstructed = true;
206  ++m_size;
207  }
208 
209  return index;
210  }
211 
212  template <typename... Args>
213  Index_t construct(Args&&... args)
214  {
215  auto index = nextFree();
216 
217  if (index >= 0)
218  {
219  m_freeIndex = index;
220  m_cellInfo[index].data = new (&m_values[index]) T(std::forward<Args>(args)...); // use placement new
221  m_cellInfo[m_freeIndex].isValid = true;
222  m_cellInfo[m_freeIndex].wasConstructed = true;
223  ++m_size;
224  }
225 
226  return index;
227  }
228 
229  Index_t add(const T& element)
230  {
231  auto index = nextFree();
232 
233  if (index >= 0)
234  {
235  m_freeIndex = index;
236  auto& cellInfo = m_cellInfo[m_freeIndex];
237  cellInfo.data = new (m_values[m_freeIndex]) T(element);
238  cellInfo.isValid = true;
239  cellInfo.wasConstructed = true;
240  ++m_size;
241  }
242 
243  return index;
244  }
245 
246  void remove(Index_t index, bool destruct = false)
247  {
248  if (m_cellInfo[index].isValid)
249  {
250  if (destruct)
251  {
252  m_cellInfo[index].data->~T();
253  }
254  m_cellInfo[index].isValid = false;
255  --m_size;
256  }
257  }
258 
259  // unsafe by design (as std::vector), remove ...?
260  T& operator[](Index_t index)
261  {
262  return *(m_cellInfo[index].data);
263  }
264 
265  Iterator iterator(Index_t index)
266  {
267  if (m_cellInfo[index].isValid)
268  {
269  return Iterator(index, *this);
270  }
271  return end();
272  }
273 
274  size_t size() const
275  {
276  return m_size;
277  }
278 
279  size_t capacity() const
280  {
281  return CAPACITY;
282  }
283 
284  //**************************** pointer API ********************************
285 
286  // get raw memory for object T
287  T* allocate()
288  {
289  auto index = reserve();
290  if (index == NO_INDEX)
291  {
292  return nullptr;
293  }
294  // access to raw memory where nothing was constructed yet
295  // cannot be avoided easily with current logic
296  // since the idea is that the user could also use this memory pointer
297  // to place objects of type T in (should probably not be supported in the future
298  // because it is dangerous if used wrongly)
299 
300  return reinterpret_cast<T*>(m_values[index]);
301  }
302 
303  // default construct object T
304  T* create()
305  {
306  auto index = construct();
307  if (index == NO_INDEX)
308  {
309  return nullptr;
310  }
311  return get(index);
312  }
313 
314  // construct object T with constructors taking arguments
315  template <typename... Args>
316  T* create(Args&&... args)
317  {
318  auto index = construct(std::forward<Args>(args)...);
319  if (index == NO_INDEX)
320  {
321  return nullptr;
322  }
323  return get(index);
324  }
325 
326  // free the cell associated with ptr and call destructor if destruct is true
327  void free(T* ptr, bool destruct)
328  {
329  auto index = pointerToIndex(ptr);
330  if (index >= 0)
331  {
332  remove(index, destruct);
333  }
334  }
335 
336  // free cell associated with ptr
337  // call object destructor if and only if it was constructed by the pool
338  // note: this can be dangerous if the user also destroyed the objects via pointer
339  void free(T* ptr)
340  {
341  auto index = pointerToIndex(ptr);
342  if (index >= 0)
343  {
344  remove(index, m_cellInfo[index].wasConstructed);
345  }
346  }
347 
348  T* insert(const T& element)
349  {
350  auto index = add(element);
351 
352  if (index >= 0)
353  {
354  get(index);
355  }
356  else
357  {
358  return nullptr;
359  }
360 
361  return get(index);
362  }
363 
364  T* get(Index_t index)
365  {
366  return (m_cellInfo[index].isValid) ? m_cellInfo[index].data : nullptr;
367  }
368 
369  T* get(T* ptr)
370  {
371  auto index = pointerToIndex(ptr);
372  if (index != NO_INDEX)
373  {
374  return (m_cellInfo[index].isValid) ? m_cellInfo[index].data : nullptr;
375  }
376  return nullptr;
377  }
378 
379  Iterator iterator(T* ptr)
380  {
381  auto index = pointerToIndex(ptr);
382  if (index >= 0)
383  {
384  return iterator(index);
385  }
386  return end();
387  }
388 
389  Index_t pointerToIndex(T* ptr)
390  {
392  char* p = reinterpret_cast<char*>(ptr);
393  if (p < m_first || p > m_last)
394  {
395  return NO_INDEX;
396  }
397  auto delta = p - m_first;
398  if (static_cast<uint64_t>(delta) % sizeof(T) != 0)
399  {
400  return NO_INDEX;
401  }
402 
403  // if the cell is valid and contains data we expect the pointer to equal data (alignment has to match)
404  auto index = static_cast<Index_t>(static_cast<uint64_t>(delta) / sizeof(T));
405  if (m_cellInfo[index].isValid && m_cellInfo[index].data)
406  {
407  if (m_cellInfo[index].data == ptr)
408  {
409  return index;
410  }
411  else
412  {
413  // pointer is not aligned to object in cell
414  return NO_INDEX;
415  }
416  }
417 
418  return index;
419  }
420 
421  T* indexToPointer(Index_t index)
422  {
423  return m_cellInfo[index].data;
424  }
425 
426  private:
427  // TODO: use fifo/index set for efficient search of free elements
428  Index_t nextFree()
429  {
430  if (m_size >= CAPACITY)
431  return NO_INDEX; // container is full
432 
433  for (; m_cellInfo[m_freeIndex].isValid; m_freeIndex = (m_freeIndex + 1) % CAPACITY)
434  ;
435 
436  return m_freeIndex;
437  }
438 };
439 } // namespace cxx
440 } // namespace iox
441 
442 #endif // IOX_UTILS_OBJECTPOOL_OBJECTPOOL_HPP
Definition: objectpool.hpp:68
Definition: objectpool.hpp:36
Index_t pointerToIndex(T *ptr)
Definition: objectpool.hpp:389
building block to easily create free function for logging in a library context
Definition: lockfree_queue.hpp:28