iceoryx_hoofs  2.0.2
forward_list.hpp
1 // Copyright (c) 2020 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 
18 #ifndef IOX_HOOFS_CXX_FORWARD_LIST_HPP
19 #define IOX_HOOFS_CXX_FORWARD_LIST_HPP
20 
21 #include "iceoryx_hoofs/cxx/helplets.hpp"
22 
23 #include <cstdint>
24 #include <iostream>
25 
26 #include "iceoryx_hoofs/platform/platform_correction.hpp"
27 
28 namespace iox
29 {
30 namespace cxx
31 {
56 template <typename T, uint64_t Capacity>
58 {
59  private:
60  // forward declarations, private
61  struct ListLink;
62  template <bool>
63  class IteratorBase;
64 
65  public:
66  using iterator = IteratorBase<false>;
67  using const_iterator = IteratorBase<true>;
68  using value_type = T;
69  using size_type = decltype(Capacity);
70 
72  forward_list() noexcept;
73 
76  ~forward_list() noexcept;
77 
80  forward_list(const forward_list& rhs) noexcept;
81 
84  forward_list(forward_list&& rhs) noexcept;
85 
91  forward_list& operator=(const forward_list& rhs) noexcept;
92 
98  forward_list& operator=(forward_list&& rhs) noexcept;
99 
104  iterator before_begin() noexcept;
105 
109  const_iterator before_begin() const noexcept;
110 
114  const_iterator cbefore_begin() const noexcept;
115 
118  iterator begin() noexcept;
119 
122  const_iterator begin() const noexcept;
123 
126  const_iterator cbegin() const noexcept;
127 
131  iterator end() noexcept;
132 
136  const_iterator end() const noexcept;
137 
141  const_iterator cend() const noexcept;
142 
145  bool empty() const noexcept;
146 
149  bool full() const noexcept;
150 
155  size_type size() const noexcept;
156 
159  size_type capacity() const noexcept;
160 
163  size_type max_size() const noexcept;
164 
168  T& front() noexcept;
169 
173  const T& front() const noexcept;
174 
178  bool push_front(const T& data) noexcept;
179 
183  bool push_front(T&& data) noexcept;
184 
188  bool pop_front() noexcept;
189 
192  void clear() noexcept;
193 
200  iterator erase_after(const_iterator beforeToBeErasedIter) noexcept;
201 
206  size_type remove(const T& data) noexcept;
207 
212  template <typename UnaryPredicate>
213  size_type remove_if(UnaryPredicate pred) noexcept;
214 
218  template <typename... ConstructorArgs>
219  T& emplace_front(ConstructorArgs&&... args) noexcept;
220 
225  template <typename... ConstructorArgs>
226  iterator emplace_after(const_iterator afterToBeEmplacedIter, ConstructorArgs&&... args) noexcept;
227 
232  iterator insert_after(const_iterator citer, const T& data) noexcept;
233 
238  iterator insert_after(const_iterator citer, T&& data) noexcept;
239 
240  private:
243  template <bool IsConstIterator = true>
244  class IteratorBase
245  {
246  public:
247  // provide the following public types for a std::iterator compatible iterator_category interface
248  using iterator_category = std::forward_iterator_tag;
249  using value_type = typename std::conditional<IsConstIterator, const T, T>::type;
250  using difference_type = void;
251  using pointer = typename std::conditional<IsConstIterator, const T*, T*>::type;
252  using reference = typename std::conditional<IsConstIterator, const T&, T&>::type;
253 
254 
257  IteratorBase(const IteratorBase<false>& iter) noexcept;
258 
263  IteratorBase& operator=(const IteratorBase<false>& rhs) noexcept;
264 
268  IteratorBase& operator++() noexcept;
269 
276  template <bool IsConstIteratorOther>
277  bool operator==(const IteratorBase<IsConstIteratorOther>& rhs) const noexcept;
278 
285  template <bool IsConstIteratorOther>
286  bool operator!=(const IteratorBase<IsConstIteratorOther>& rhs) const noexcept;
287 
290  reference operator*() const noexcept;
291 
294  pointer operator->() const noexcept;
295 
296 
297  private:
298  using parentListPointer = typename std::
299  conditional<IsConstIterator, const forward_list<T, Capacity>*, forward_list<T, Capacity>*>::type;
300 
306  explicit IteratorBase(parentListPointer parent, size_type idx) noexcept;
307 
308  // Make IteratorBase<true> a friend class of IteratorBase<false> so the copy constructor can access the
309  // private member variables.
310  friend class IteratorBase<true>;
311  friend class forward_list<T, Capacity>;
312  parentListPointer m_list;
313  size_type m_iterListNodeIdx;
314  };
315 
316  struct NodeLink
317  {
318  size_type nextIdx;
319  bool invalidElement;
320  };
321 
322  void init() noexcept;
323  T* getDataPtrFromIdx(const size_type idx) noexcept;
324  const T* getDataPtrFromIdx(const size_type idx) const noexcept;
325 
326  bool isValidElementIdx(const size_type idx) const noexcept;
327  bool isInvalidIterator(const const_iterator& iter) const noexcept;
328  bool isInvalidIterOrDifferentLists(const const_iterator& iter) const noexcept;
329  bool isInvalidElement(const size_type idx) const noexcept;
330  void setInvalidElement(const size_type idx, const bool value) noexcept;
331  size_type& getNextIdx(const size_type idx) noexcept;
332  const size_type& getNextIdx(const size_type idx) const noexcept;
333  size_type& getNextIdx(const const_iterator& iter) noexcept;
334  const size_type& getNextIdx(const const_iterator& iter) const noexcept;
335  void setNextIdx(const size_type idx, const size_type nextIdx) noexcept;
336  static void errorMessage(const char* source, const char* msg) noexcept;
337 
338  //***************************************
339  // members
340  //***************************************
341 
342  // two extra slots in the list to handle the 'before_begin' and 'end' element
343  // the necessity for 'before_begin' elements stems from the way a forward_list removes elements at an arbitrary
344  // position. Removing the front-most list element (aka begin()) requires an element pointing towards this position,
345  // hence 'before_begin'. The before_begin index is the head of the list.
346  static constexpr size_type BEFORE_BEGIN_INDEX{Capacity};
347  static constexpr size_type END_INDEX{size_type(Capacity) + 1U};
348  static constexpr size_type NODE_LINK_COUNT{size_type(Capacity) + 2U};
349 
350  // available storage-indices are moved between a 'freeList' (m_freeListHeadIdx) and 'usedList' where elements
351  // are inserted by the user (starting from BEFORE_BEGIN_INDEX)
352  size_type m_freeListHeadIdx{0U};
353 
354  NodeLink m_links[NODE_LINK_COUNT];
355  using element_t = uint8_t[sizeof(T)];
356  alignas(T) element_t m_data[Capacity];
357 
358  size_type m_size{0U};
359 }; // forward_list
360 
361 } // namespace cxx
362 } // namespace iox
363 
364 #include "iceoryx_hoofs/internal/cxx/forward_list.inl"
365 
366 #endif // IOX_HOOFS_CXX_FORWARD_LIST_HPP
C++11 compatible uni-directional forward list implementation.
Definition: forward_list.hpp:58
void clear() noexcept
remove all elements from the list, list will be empty element destructors will be invoked
forward_list() noexcept
constructor for an empty list (of T-types elements)
const_iterator cbefore_begin() const noexcept
const_iterator an interator before first element only allowed for usage in erase_after,...
size_type max_size() const noexcept
list meta information, maximum number of elements the list can contain
bool full() const noexcept
list meta information on filling
size_type size() const noexcept
list meta information on filling
iterator end() noexcept
default list operation to retrieve an interator to end of list (behind last valid element) Terminated...
bool push_front(const T &data) noexcept
add element to the beginning of the list
forward_list & operator=(const forward_list &rhs) noexcept
copy assignment, each element is copied (added) to the constructed list any existing elements in 'thi...
iterator erase_after(const_iterator beforeToBeErasedIter) noexcept
remove next element from linked iterator position element destructors will be invoked recursive calls...
iterator insert_after(const_iterator citer, const T &data) noexcept
insert element after iterator position
const_iterator cend() const noexcept
default list operation to retrieve an const_iterator to end of list (behind last valid element) Termi...
iterator emplace_after(const_iterator afterToBeEmplacedIter, ConstructorArgs &&... args) noexcept
construct element inplace after the pointed-to element
iterator begin() noexcept
default list operation to retrieve an interator to first list element
const_iterator cbegin() const noexcept
default list operation to retrieve an const_iterator to first list element
T & emplace_front(ConstructorArgs &&... args) noexcept
construct element inplace at begining of list
size_type capacity() const noexcept
list meta information, maximum number of elements the list can contain
bool empty() const noexcept
list meta information on filling
size_type remove_if(UnaryPredicate pred) noexcept
remove all elements which matches the provided comparison function requires a the template type T to ...
size_type remove(const T &data) noexcept
remove all elements which matches the given comparing element (compare by value) requires a the templ...
T & front() noexcept
Returns a reference to the first element in the container. calling front() on an empty list will term...
bool pop_front() noexcept
remove the first element from the begining of the list element destructor will be invoked
iterator before_begin() noexcept
retrieve an interator before first element only allowed for usage in erase_after, insert_after,...
building block to easily create free function for logging in a library context
Definition: lockfree_queue.hpp:29