iceoryx_hoofs 2.0.5
Loading...
Searching...
No Matches
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
28namespace iox
29{
30namespace cxx
31{
56template <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
T & front() noexcept
Returns a reference to the first element in the container. calling front() on an empty list will term...
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
T & emplace_front(ConstructorArgs &&... args) noexcept
construct element inplace at begining of list
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
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...
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