iceoryx_hoofs  2.0.2
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 
28 namespace iox
29 {
30 namespace cxx
31 {
57 template <typename T, uint64_t Capacity>
58 class 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)
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...
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 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...
T & emplace_front(ConstructorArgs &&... args) noexcept
construct element inplace at begining of list
bool full() const noexcept
list meta information on filling
list & operator=(const list &rhs) noexcept
copy assignment, each element is copied (added) to the constructed list any existing elements in 'thi...
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