iceoryx_doc  1.0.1
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_LIST_HPP
18 #define IOX_UTILS_CXX_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 {
54 template <typename T, uint64_t Capacity>
55 class list
56 {
57  private:
58  // forward declarations, private
59  struct ListLink;
60  template <bool>
61  class IteratorBase;
62 
63  public:
64  using iterator = IteratorBase<false>;
65  using const_iterator = IteratorBase<true>;
66  using value_type = T;
67  using size_type = decltype(Capacity);
68 
70  list() noexcept;
71 
74  ~list();
75 
78  list(const list& rhs) noexcept;
79 
82  list(list&& rhs) noexcept;
83 
89  list& operator=(const list& rhs) noexcept;
90 
96  list& operator=(list&& rhs) noexcept;
97 
98 
101  iterator begin() noexcept;
102 
105  const_iterator begin() const noexcept;
106 
109  const_iterator cbegin() const noexcept;
110 
114  iterator end() noexcept;
115 
119  const_iterator end() const noexcept;
120 
124  const_iterator cend() const noexcept;
125 
128  bool empty() const noexcept;
129 
132  bool full() const noexcept;
133 
138  size_type size() const noexcept;
139 
142  size_type capacity() const noexcept;
143 
146  size_type max_size() const noexcept;
147 
151  T& front() noexcept;
152 
156  const T& front() const noexcept;
157 
161  T& back() noexcept;
162 
166  const T& back() const noexcept;
167 
171  bool push_front(const T& data) noexcept;
172 
176  bool push_front(T&& data) noexcept;
177 
181  bool push_back(const T& data) noexcept;
182 
186  bool push_back(T&& data) noexcept;
187 
191  bool pop_front() noexcept;
192 
196  bool pop_back() noexcept;
197 
200  void clear() noexcept;
201 
208  iterator erase(const_iterator iter) noexcept;
209 
214  size_type remove(const T& data) noexcept;
215 
220  template <typename UnaryPredicate>
221  size_type remove_if(UnaryPredicate pred) noexcept;
222 
226  template <typename... ConstructorArgs>
227  T& emplace_front(ConstructorArgs&&... args) noexcept;
228 
232  template <typename... ConstructorArgs>
233  T& emplace_back(ConstructorArgs&&... args) noexcept;
234 
239  template <typename... ConstructorArgs>
240  iterator emplace(const_iterator iter, ConstructorArgs&&... args) noexcept;
241 
246  iterator insert(const_iterator citer, const T& data) noexcept;
247 
252  iterator insert(const_iterator citer, T&& data) noexcept;
253 
254  private:
257  template <bool IsConstIterator = true>
258  class IteratorBase
259  {
260  public:
261  // provide the following public types for a std::iterator compatible iterator_category interface
262  using iterator_category = std::bidirectional_iterator_tag;
263  using value_type = typename std::conditional<IsConstIterator, const T, T>::type;
264  using difference_type = void;
265  using pointer = typename std::conditional<IsConstIterator, const T*, T*>::type;
266  using reference = typename std::conditional<IsConstIterator, const T&, T&>::type;
267 
268 
271  IteratorBase(const IteratorBase<false>& iter) noexcept;
272 
277  IteratorBase& operator=(const IteratorBase<false>& rhs) noexcept;
278 
282  IteratorBase& operator++() noexcept;
283 
287  IteratorBase& operator--() noexcept;
288 
289 
296  template <bool IsConstIteratorOther>
297  bool operator==(const IteratorBase<IsConstIteratorOther>& rhs) const noexcept;
298 
305  template <bool IsConstIteratorOther>
306  bool operator!=(const IteratorBase<IsConstIteratorOther>& rhs) const noexcept;
307 
310  reference operator*() const noexcept;
311 
314  pointer operator->() const noexcept;
315 
316 
317  private:
318  using parentListPointer =
319  typename std::conditional<IsConstIterator, const list<T, Capacity>*, list<T, Capacity>*>::type;
320 
326  explicit IteratorBase(parentListPointer parent, size_type idx) noexcept;
327 
328  // Make IteratorBase<true> a friend class of IteratorBase<false> so the copy constructor can access the
329  // private member variables.
330  friend class IteratorBase<true>;
331  friend class list<T, Capacity>;
332  parentListPointer m_list;
333  size_type m_iterListNodeIdx;
334  };
335 
336  struct NodeLink
337  {
338  size_type nextIdx;
339  size_type prevIdx;
340  };
341 
342  void init() noexcept;
343  T* getDataPtrFromIdx(const size_type idx) noexcept;
344  const T* getDataPtrFromIdx(const size_type idx) const noexcept;
345 
346  bool isValidElementIdx(const size_type idx) const noexcept;
347  bool handleInvalidElement(const size_type idx) const noexcept;
348  bool handleInvalidIterator(const const_iterator& iter) const noexcept;
349  bool isInvalidIterOrDifferentLists(const const_iterator& iter) const noexcept;
350  size_type& getPrevIdx(const size_type idx) noexcept;
351  size_type& getNextIdx(const size_type idx) noexcept;
352  size_type& getPrevIdx(const const_iterator& iter) noexcept;
353  size_type& getNextIdx(const const_iterator& iter) noexcept;
354  const size_type& getPrevIdx(const size_type idx) const noexcept;
355  const size_type& getNextIdx(const size_type idx) const noexcept;
356  const size_type& getPrevIdx(const const_iterator& iter) const noexcept;
357  const size_type& getNextIdx(const const_iterator& iter) const noexcept;
358  void setPrevIdx(const size_type idx, const size_type prevIdx) noexcept;
359  void setNextIdx(const size_type idx, const size_type nextIdx) noexcept;
360 
361  static void errorMessage(const char* source, const char* msg) noexcept;
362 
363  //***************************************
364  // members
365  //***************************************
366 
367  static constexpr size_type BEGIN_END_LINK_INDEX{size_type(Capacity)};
368  static constexpr size_type NODE_LINK_COUNT{size_type(Capacity) + 1U};
369  static constexpr size_type INVALID_INDEX{NODE_LINK_COUNT};
370 
371  // unused/free elements are stored in an internal list (freeList), this freeList is accessed via the
372  // member variable m_freeListHeadIdx; user insert- and erase- operations move elements between the freeList and
373  // active list
374  size_type m_freeListHeadIdx{0U};
375 
376  // m_links array is one element bigger than request element count. In this additional element links are stored
377  // to the beginning and end of the list. This additional element (index position 'capacity' aka
378  // BEGIN_END_LINK_INDEX) 'previous' will point to the last valid element (end()) and 'next' will point to the
379  // first used list element (begin())
380  NodeLink m_links[NODE_LINK_COUNT];
381  using element_t = uint8_t[sizeof(T)];
382  alignas(T) element_t m_data[Capacity];
383 
384  size_type m_size{0U};
385 }; // list
386 
387 } // namespace cxx
388 } // namespace iox
389 
390 #include "iceoryx_utils/internal/cxx/list.inl"
391 
392 #endif // IOX_UTILS_CXX_LIST_HPP
C++11 compatible bi-directional list implementation.
Definition: list.hpp:56
size_type max_size() const noexcept
list meta information, maximum number of elements the list can contain
Definition: list.inl:196
size_type capacity() const noexcept
list meta information, maximum number of elements the list can contain
Definition: list.inl:190
bool pop_front() noexcept
remove the first element from the begining of the list element destructor will be invoked
Definition: list.inl:400
iterator erase(const_iterator iter) noexcept
remove next element from linked iterator position element destructors will be invoked recursive calls...
Definition: list.inl:255
list() noexcept
constructor for an empty list (of T-types elements)
Definition: list.inl:29
T & emplace_front(ConstructorArgs &&... args) noexcept
construct element inplace at begining of list
Definition: list.inl:204
size_type size() const noexcept
list meta information on filling
Definition: list.inl:184
void clear() noexcept
remove all elements from the list, list will be empty element destructors will be invoked
Definition: list.inl:429
const_iterator cend() const noexcept
default list operation to retrieve an const_iterator to end of list (behind last valid element) Termi...
Definition: list.inl:165
bool push_back(const T &data) noexcept
add element to the end of the list
Definition: list.inl:378
iterator emplace(const_iterator iter, ConstructorArgs &&... args) noexcept
construct element inplace at iterator position
Definition: list.inl:218
iterator end() noexcept
default list operation to retrieve an interator to end of list (behind last valid element) Terminated...
Definition: list.inl:155
iterator insert(const_iterator citer, const T &data) noexcept
insert element before iterator position
Definition: list.inl:416
bool pop_back() noexcept
remove the last element from the end of the list element destructor will be invoked
Definition: list.inl:408
const_iterator cbegin() const noexcept
default list operation to retrieve an const_iterator to first list element
Definition: list.inl:148
T & front() noexcept
Returns a reference to the first element in the container. calling front() on an empty list will term...
Definition: list.inl:323
bool full() const noexcept
list meta information on filling
Definition: list.inl:178
list & operator=(list &&rhs) noexcept
move assignment, list is cleared and initialized, elements are moved from source list any existing el...
T & back() noexcept
Returns a reference to the last element in the container. calling back() on an empty list will termin...
Definition: list.inl:339
list & operator=(const list &rhs) noexcept
copy assignment, each element is copied (added) to the constructed list any existing elements in 'thi...
iterator begin() noexcept
default list operation to retrieve an interator to first list element
Definition: list.inl:138
size_type remove(const T &data) noexcept
remove all elements which matches the given comparing element (compare by value) requires a the templ...
Definition: list.inl:292
T & emplace_back(ConstructorArgs &&... args) noexcept
construct element inplace at end of list
Definition: list.inl:211
bool empty() const noexcept
list meta information on filling
Definition: list.inl:172
bool push_front(const T &data) noexcept
add element to the beginning of the list
Definition: list.inl:355
size_type remove_if(UnaryPredicate pred) noexcept
remove all elements which matches the provided comparison function requires a the template type T to ...
Definition: list.inl:300
~list()
destructs the list and also calls the destructor of all contained elements
Definition: list.inl:131
building block to easily create free function for logging in a library context
Definition: lockfree_queue.hpp:28