iceoryx_hoofs 2.0.5
Loading...
Searching...
No Matches
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_LIST_HPP
19#define IOX_HOOFS_CXX_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{
57template <typename T, uint64_t Capacity>
58class list
59{
60 private:
61 // forward declarations, private
62 struct ListLink;
63 template <bool>
64 class IteratorBase;
65
66 public:
67 using iterator = IteratorBase<false>;
68 using const_iterator = IteratorBase<true>;
69 using value_type = T;
70 using size_type = decltype(Capacity);
71
73 list() noexcept;
74
77 ~list() noexcept;
78
81 list(const list& rhs) noexcept;
82
85 list(list&& rhs) noexcept;
86
92 list& operator=(const list& rhs) noexcept;
93
99 list& operator=(list&& rhs) noexcept;
100
101
104 iterator begin() noexcept;
105
108 const_iterator begin() const noexcept;
109
112 const_iterator cbegin() const noexcept;
113
117 iterator end() noexcept;
118
122 const_iterator end() const noexcept;
123
127 const_iterator cend() const noexcept;
128
131 bool empty() const noexcept;
132
135 bool full() const noexcept;
136
141 size_type size() const noexcept;
142
145 size_type capacity() const noexcept;
146
149 size_type max_size() const noexcept;
150
154 T& front() noexcept;
155
159 const T& front() const noexcept;
160
164 T& back() noexcept;
165
169 const T& back() const noexcept;
170
174 bool push_front(const T& data) noexcept;
175
179 bool push_front(T&& data) noexcept;
180
184 bool push_back(const T& data) noexcept;
185
189 bool push_back(T&& data) noexcept;
190
194 bool pop_front() noexcept;
195
199 bool pop_back() noexcept;
200
203 void clear() noexcept;
204
211 iterator erase(const_iterator iter) noexcept;
212
217 size_type remove(const T& data) noexcept;
218
223 template <typename UnaryPredicate>
224 size_type remove_if(UnaryPredicate pred) noexcept;
225
229 template <typename... ConstructorArgs>
230 T& emplace_front(ConstructorArgs&&... args) noexcept;
231
235 template <typename... ConstructorArgs>
236 T& emplace_back(ConstructorArgs&&... args) noexcept;
237
242 template <typename... ConstructorArgs>
243 iterator emplace(const_iterator iter, ConstructorArgs&&... args) noexcept;
244
249 iterator insert(const_iterator citer, const T& data) noexcept;
250
255 iterator insert(const_iterator citer, T&& data) noexcept;
256
257 private:
260 template <bool IsConstIterator = true>
261 class IteratorBase
262 {
263 public:
264 // provide the following public types for a std::iterator compatible iterator_category interface
265 using iterator_category = std::bidirectional_iterator_tag;
266 using value_type = typename std::conditional<IsConstIterator, const T, T>::type;
267 using difference_type = void;
268 using pointer = typename std::conditional<IsConstIterator, const T*, T*>::type;
269 using reference = typename std::conditional<IsConstIterator, const T&, T&>::type;
270
271
274 IteratorBase(const IteratorBase<false>& iter) noexcept;
275
280 IteratorBase& operator=(const IteratorBase<false>& rhs) noexcept;
281
285 IteratorBase& operator++() noexcept;
286
290 IteratorBase& operator--() noexcept;
291
292
299 template <bool IsConstIteratorOther>
300 bool operator==(const IteratorBase<IsConstIteratorOther>& rhs) const noexcept;
301
308 template <bool IsConstIteratorOther>
309 bool operator!=(const IteratorBase<IsConstIteratorOther>& rhs) const noexcept;
310
313 reference operator*() const noexcept;
314
317 pointer operator->() const noexcept;
318
319
320 private:
321 using parentListPointer =
322 typename std::conditional<IsConstIterator, const list<T, Capacity>*, list<T, Capacity>*>::type;
323
329 explicit IteratorBase(parentListPointer parent, size_type idx) noexcept;
330
331 // Make IteratorBase<true> a friend class of IteratorBase<false> so the copy constructor can access the
332 // private member variables.
333 friend class IteratorBase<true>;
334 friend class list<T, Capacity>;
335 parentListPointer m_list;
336 size_type m_iterListNodeIdx;
337 };
338
339 struct NodeLink
340 {
341 size_type nextIdx;
342 size_type prevIdx;
343 };
344
345 void init() noexcept;
346 T* getDataPtrFromIdx(const size_type idx) noexcept;
347 const T* getDataPtrFromIdx(const size_type idx) const noexcept;
348
349 bool isValidElementIdx(const size_type idx) const noexcept;
350 bool isInvalidIterator(const const_iterator& iter) const noexcept;
351 bool isInvalidIterOrDifferentLists(const const_iterator& iter) const noexcept;
352 size_type& getPrevIdx(const size_type idx) noexcept;
353 size_type& getNextIdx(const size_type idx) noexcept;
354 size_type& getPrevIdx(const const_iterator& iter) noexcept;
355 size_type& getNextIdx(const const_iterator& iter) noexcept;
356 const size_type& getPrevIdx(const size_type idx) const noexcept;
357 const size_type& getNextIdx(const size_type idx) const noexcept;
358 const size_type& getPrevIdx(const const_iterator& iter) const noexcept;
359 const size_type& getNextIdx(const const_iterator& iter) const noexcept;
360 void setPrevIdx(const size_type idx, const size_type prevIdx) noexcept;
361 void setNextIdx(const size_type idx, const size_type nextIdx) noexcept;
362
363 static void errorMessage(const char* source, const char* msg) noexcept;
364
365 //***************************************
366 // members
367 //***************************************
368
369 static constexpr size_type BEGIN_END_LINK_INDEX{size_type(Capacity)};
370 static constexpr size_type NODE_LINK_COUNT{size_type(Capacity) + 1U};
371 static constexpr size_type INVALID_INDEX{NODE_LINK_COUNT};
372
373 // unused/free elements are stored in an internal list (freeList), this freeList is accessed via the
374 // member variable m_freeListHeadIdx; user insert- and erase- operations move elements between the freeList and
375 // active list
376 size_type m_freeListHeadIdx{0U};
377
378 // m_links array is one element bigger than request element count. In this additional element links are stored
379 // to the beginning and end of the list. This additional element (index position 'capacity' aka
380 // BEGIN_END_LINK_INDEX) 'previous' will point to the last valid element (end()) and 'next' will point to the
381 // first used list element (begin())
382 NodeLink m_links[NODE_LINK_COUNT];
383 using element_t = uint8_t[sizeof(T)];
384 alignas(T) element_t m_data[Capacity];
385
386 size_type m_size{0U};
387}; // list
388
389} // namespace cxx
390} // namespace iox
391
392#include "iceoryx_hoofs/internal/cxx/list.inl"
393
394#endif // IOX_HOOFS_CXX_LIST_HPP
C++11 compatible bi-directional list implementation.
Definition list.hpp:59
size_type remove(const T &data) noexcept
remove all elements which matches the given comparing element (compare by value) requires a the templ...
iterator erase(const_iterator iter) noexcept
remove next element from linked iterator position element destructors will be invoked recursive calls...
bool pop_front() noexcept
remove the first element from the begining of the list element destructor will be invoked
size_type capacity() const noexcept
list meta information, maximum number of elements the list can contain
list() noexcept
constructor for an empty list (of T-types elements)
T & emplace_front(ConstructorArgs &&... args) noexcept
construct element inplace at begining of list
list & operator=(const list &rhs) noexcept
copy assignment, each element is copied (added) to the constructed list any existing elements in 'thi...
void clear() noexcept
remove all elements from the list, list will be empty element destructors will be invoked
size_type remove_if(UnaryPredicate pred) noexcept
remove all elements which matches the provided comparison function requires a the template type T to ...
bool push_back(const T &data) noexcept
add element to the end of the list
iterator begin() noexcept
default list operation to retrieve an interator to first list element
const_iterator cend() const noexcept
default list operation to retrieve an const_iterator to end of list (behind last valid element) Termi...
iterator emplace(const_iterator iter, ConstructorArgs &&... args) noexcept
construct element inplace at iterator position
iterator end() noexcept
default list operation to retrieve an interator to end of list (behind last valid element) Terminated...
size_type max_size() const noexcept
list meta information, maximum number of elements the list can contain
bool pop_back() noexcept
remove the last element from the end of the list element destructor will be invoked
size_type size() const noexcept
list meta information on filling
T & front() noexcept
Returns a reference to the first element in the container. calling front() on an empty list will term...
bool full() const noexcept
list meta information on filling
T & back() noexcept
Returns a reference to the last element in the container. calling back() on an empty list will termin...
T & emplace_back(ConstructorArgs &&... args) noexcept
construct element inplace at end of list
iterator insert(const_iterator citer, const T &data) noexcept
insert element before iterator position
bool empty() const noexcept
list meta information on filling
bool push_front(const T &data) noexcept
add element to the beginning of the list
const_iterator cbegin() const noexcept
default list operation to retrieve an const_iterator to first list element
building block to easily create free function for logging in a library context
Definition lockfree_queue.hpp:29