iceoryx_doc  1.0.1
forward_list.hpp
1 // Copyright (c) 2020 by Robert Bosch GmbH. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // SPDX-License-Identifier: Apache-2.0
16 
17 #ifndef IOX_UTILS_CXX_FORWARD_LIST_HPP
18 #define IOX_UTILS_CXX_FORWARD_LIST_HPP
19 
20 #include <cstdint>
21 #include <iostream>
22 
23 #include "iceoryx_utils/platform/platform_correction.hpp"
24 
25 namespace iox
26 {
27 namespace cxx
28 {
53 template <typename T, uint64_t Capacity>
55 {
56  private:
57  // forward declarations, private
58  struct ListLink;
59  template <bool>
60  class IteratorBase;
61 
62  public:
63  using iterator = IteratorBase<false>;
64  using const_iterator = IteratorBase<true>;
65  using value_type = T;
66  using size_type = decltype(Capacity);
67 
69  forward_list() noexcept;
70 
73  ~forward_list();
74 
77  forward_list(const forward_list& rhs) noexcept;
78 
81  forward_list(forward_list&& rhs) noexcept;
82 
88  forward_list& operator=(const forward_list& rhs) noexcept;
89 
96 
101  iterator before_begin() noexcept;
102 
106  const_iterator before_begin() const noexcept;
107 
111  const_iterator cbefore_begin() const noexcept;
112 
115  iterator begin() noexcept;
116 
119  const_iterator begin() const noexcept;
120 
123  const_iterator cbegin() const noexcept;
124 
128  iterator end() noexcept;
129 
133  const_iterator end() const noexcept;
134 
138  const_iterator cend() const noexcept;
139 
142  bool empty() const noexcept;
143 
146  bool full() const noexcept;
147 
152  size_type size() const noexcept;
153 
156  size_type capacity() const noexcept;
157 
160  size_type max_size() const noexcept;
161 
165  T& front() noexcept;
166 
170  const T& front() const noexcept;
171 
175  bool push_front(const T& data) noexcept;
176 
180  bool push_front(T&& data) noexcept;
181 
185  bool pop_front() noexcept;
186 
189  void clear() noexcept;
190 
197  iterator erase_after(const_iterator beforeToBeErasedIter) noexcept;
198 
203  size_type remove(const T& data) noexcept;
204 
209  template <typename UnaryPredicate>
210  size_type remove_if(UnaryPredicate pred) noexcept;
211 
215  template <typename... ConstructorArgs>
216  T& emplace_front(ConstructorArgs&&... args) noexcept;
217 
222  template <typename... ConstructorArgs>
223  iterator emplace_after(const_iterator afterToBeEmplacedIter, ConstructorArgs&&... args) noexcept;
224 
229  iterator insert_after(const_iterator citer, const T& data) noexcept;
230 
235  iterator insert_after(const_iterator citer, T&& data) noexcept;
236 
237  private:
240  template <bool IsConstIterator = true>
241  class IteratorBase
242  {
243  public:
244  // provide the following public types for a std::iterator compatible iterator_category interface
245  using iterator_category = std::forward_iterator_tag;
246  using value_type = typename std::conditional<IsConstIterator, const T, T>::type;
247  using difference_type = void;
248  using pointer = typename std::conditional<IsConstIterator, const T*, T*>::type;
249  using reference = typename std::conditional<IsConstIterator, const T&, T&>::type;
250 
251 
254  IteratorBase(const IteratorBase<false>& iter) noexcept;
255 
260  IteratorBase& operator=(const IteratorBase<false>& rhs) noexcept;
261 
265  IteratorBase& operator++() noexcept;
266 
273  template <bool IsConstIteratorOther>
274  bool operator==(const IteratorBase<IsConstIteratorOther>& rhs) const noexcept;
275 
282  template <bool IsConstIteratorOther>
283  bool operator!=(const IteratorBase<IsConstIteratorOther>& rhs) const noexcept;
284 
287  reference operator*() const noexcept;
288 
291  pointer operator->() const noexcept;
292 
293 
294  private:
295  using parentListPointer = typename std::
296  conditional<IsConstIterator, const forward_list<T, Capacity>*, forward_list<T, Capacity>*>::type;
297 
303  explicit IteratorBase(parentListPointer parent, size_type idx) noexcept;
304 
305  // Make IteratorBase<true> a friend class of IteratorBase<false> so the copy constructor can access the
306  // private member variables.
307  friend class IteratorBase<true>;
308  friend class forward_list<T, Capacity>;
309  parentListPointer m_list;
310  size_type m_iterListNodeIdx;
311  };
312 
313  struct NodeLink
314  {
315  size_type nextIdx;
316  bool invalidElement;
317  };
318 
319  void init() noexcept;
320  T* getDataPtrFromIdx(const size_type idx) noexcept;
321  const T* getDataPtrFromIdx(const size_type idx) const noexcept;
322 
323  bool isValidElementIdx(const size_type idx) const noexcept;
324  bool handleInvalidElement(const size_type idx) const noexcept;
325  bool handleInvalidIterator(const const_iterator& iter) const noexcept;
326  bool isInvalidIterOrDifferentLists(const const_iterator& iter) const noexcept;
327  bool isInvalidElement(const size_type idx) const noexcept;
328  void setInvalidElement(const size_type idx, const bool value) noexcept;
329  size_type& getNextIdx(const size_type idx) noexcept;
330  const size_type& getNextIdx(const size_type idx) const noexcept;
331  size_type& getNextIdx(const const_iterator& iter) noexcept;
332  const size_type& getNextIdx(const const_iterator& iter) const noexcept;
333  void setNextIdx(const size_type idx, const size_type nextIdx) noexcept;
334  static void errorMessage(const char* source, const char* msg) noexcept;
335 
336  //***************************************
337  // members
338  //***************************************
339 
340  // two extra slots in the list to handle the 'before_begin' and 'end' element
341  // the necessity for 'before_begin' elements stems from the way a forward_list removes elements at an arbitrary
342  // position. Removing the front-most list element (aka begin()) requires an element pointing towards this position,
343  // hence 'before_begin'. The before_begin index is the head of the list.
344  static constexpr size_type BEFORE_BEGIN_INDEX{Capacity};
345  static constexpr size_type END_INDEX{size_type(Capacity) + 1U};
346  static constexpr size_type NODE_LINK_COUNT{size_type(Capacity) + 2U};
347 
348  // available storage-indices are moved between a 'freeList' (m_freeListHeadIdx) and 'usedList' where elements
349  // are inserted by the user (starting from BEFORE_BEGIN_INDEX)
350  size_type m_freeListHeadIdx{0U};
351 
352  NodeLink m_links[NODE_LINK_COUNT];
353  using element_t = uint8_t[sizeof(T)];
354  alignas(T) element_t m_data[Capacity];
355 
356  size_type m_size{0U};
357 }; // forward_list
358 
359 } // namespace cxx
360 } // namespace iox
361 
362 #include "iceoryx_utils/internal/cxx/forward_list.inl"
363 
364 #endif // IOX_UTILS_CXX_FORWARD_LIST_HPP
C++11 compatible uni-directional forward list implementation.
Definition: forward_list.hpp:55
const_iterator cend() const noexcept
default list operation to retrieve an const_iterator to end of list (behind last valid element) Termi...
Definition: forward_list.inl:173
T & front() noexcept
Returns a reference to the first element in the container. calling front() on an empty list will term...
Definition: forward_list.inl:324
void clear() noexcept
remove all elements from the list, list will be empty element destructors will be invoked
Definition: forward_list.inl:385
forward_list() noexcept
constructor for an empty list (of T-types elements)
Definition: forward_list.inl:29
bool full() const noexcept
list meta information on filling
Definition: forward_list.inl:186
T & emplace_front(ConstructorArgs &&... args) noexcept
construct element inplace at begining of list
Definition: forward_list.inl:212
size_type max_size() const noexcept
list meta information, maximum number of elements the list can contain
Definition: forward_list.inl:204
size_type remove_if(UnaryPredicate pred) noexcept
remove all elements which matches the provided comparison function requires a the template type T to ...
Definition: forward_list.inl:299
iterator before_begin() noexcept
retrieve an interator before first element only allowed for usage in erase_after, insert_after,...
Definition: forward_list.inl:130
size_type remove(const T &data) noexcept
remove all elements which matches the given comparing element (compare by value) requires a the templ...
Definition: forward_list.inl:291
bool push_front(const T &data) noexcept
add element to the beginning of the list
Definition: forward_list.inl:340
iterator erase_after(const_iterator beforeToBeErasedIter) noexcept
remove next element from linked iterator position element destructors will be invoked recursive calls...
Definition: forward_list.inl:256
size_type capacity() const noexcept
list meta information, maximum number of elements the list can contain
Definition: forward_list.inl:198
forward_list & operator=(const forward_list &rhs) noexcept
copy assignment, each element is copied (added) to the constructed list any existing elements in 'thi...
size_type size() const noexcept
list meta information on filling
Definition: forward_list.inl:192
const_iterator cbegin() const noexcept
default list operation to retrieve an const_iterator to first list element
Definition: forward_list.inl:156
iterator emplace_after(const_iterator afterToBeEmplacedIter, ConstructorArgs &&... args) noexcept
construct element inplace after the pointed-to element
Definition: forward_list.inl:220
bool empty() const noexcept
list meta information on filling
Definition: forward_list.inl:180
~forward_list()
destructs the list and also calls the destructor of all contained elements
Definition: forward_list.inl:123
iterator insert_after(const_iterator citer, const T &data) noexcept
insert element after iterator position
Definition: forward_list.inl:370
forward_list & operator=(forward_list &&rhs) noexcept
move assignment, list is cleared and initialized, elements are moved from source list any existing el...
bool pop_front() noexcept
remove the first element from the begining of the list element destructor will be invoked
Definition: forward_list.inl:362
iterator begin() noexcept
default list operation to retrieve an interator to first list element
Definition: forward_list.inl:146
const_iterator cbefore_begin() const noexcept
const_iterator an interator before first element only allowed for usage in erase_after,...
Definition: forward_list.inl:140
iterator end() noexcept
default list operation to retrieve an interator to end of list (behind last valid element) Terminated...
Definition: forward_list.inl:163
building block to easily create free function for logging in a library context
Definition: lockfree_queue.hpp:28