distortos  v0.7.0
object-oriented C++ RTOS for microcontrollers
SortedIntrusiveForwardList.hpp
Go to the documentation of this file.
1 
12 #ifndef ESTD_SORTEDINTRUSIVEFORWARDLIST_HPP_
13 #define ESTD_SORTEDINTRUSIVEFORWARDLIST_HPP_
14 
16 
17 #include <algorithm>
18 
19 namespace estd
20 {
21 
39 template<typename Compare, typename T, IntrusiveForwardListNode T::* NodePointer, typename U = T>
41 {
42 public:
43 
46 
49 
52 
55 
58 
61 
64 
67 
74  constexpr explicit SortedIntrusiveForwardList(const Compare& compare = Compare{}) :
75  implementation_{compare}
76  {
77 
78  }
79 
85  {
87  }
88 
94  {
96  }
97 
103  {
105  }
106 
112  {
114  }
115 
121  {
123  }
124 
130  {
132  }
133 
139  {
141  }
142 
147  void clear()
148  {
150  }
151 
156  bool empty() const
157  {
159  }
160 
166  {
168  }
169 
175  {
177  }
178 
184  {
186  }
187 
193  {
195  }
196 
206  {
208  newElement);
209  }
210 
215  void pop_front()
216  {
218  }
219 
227  void splice_after(const iterator beforeSplicedElement)
228  {
229  const auto splicedElement = std::next(beforeSplicedElement);
231  beforeSplicedElement);
232  }
233 
241  {
243  }
244 
255  static iterator erase_after(const iterator position)
256  {
258  }
259 
262  const SortedIntrusiveForwardList& operator=(const SortedIntrusiveForwardList&) = delete;
264 
265 private:
266 
268  struct Implementation : public Compare
269  {
276  constexpr explicit Implementation(const Compare& comparee) :
277  Compare{comparee},
279  {
280 
281  }
282 
292  {
294  auto next = intrusiveForwardList.begin();
295  const auto end = intrusiveForwardList.end();
296 
297  while (next != end && this->Compare::operator()(*next, newElement) == false)
298  {
299  it = next;
300  ++next;
301  }
302 
303  return it;
304  }
305 
312  void swap(Implementation& other)
313  {
315  using std::swap;
316  swap(static_cast<Compare&>(*this), static_cast<Compare&>(other));
317  }
318 
319  Implementation(const Implementation&) = delete;
320  Implementation(Implementation&&) = default;
321  const Implementation& operator=(const Implementation&) = delete;
322  Implementation& operator=(Implementation&&) = delete;
323 
326  };
327 
329  Implementation implementation_;
330 };
331 
346 template<typename Compare, typename T, IntrusiveForwardListNode T::* NodePointer, typename U = T>
349 {
350  left.swap(right);
351 }
352 
353 } // namespace estd
354 
355 #endif // ESTD_SORTEDINTRUSIVEFORWARDLIST_HPP_
Collection of useful templates.
Definition: DmaChannel.hpp:121
U & reference
reference to value linked in the list
Definition: IntrusiveForwardList.hpp:875
SortedIntrusiveForwardList class is an IntrusiveForwardList with sorted elements.
Definition: SortedIntrusiveForwardList.hpp:40
const_iterator begin() const
Definition: SortedIntrusiveForwardList.hpp:111
void clear()
Unlinks all elements from the list.
Definition: SortedIntrusiveForwardList.hpp:147
const_iterator before_begin() const
Definition: SortedIntrusiveForwardList.hpp:93
IntrusiveForwardList class is an intrusive linear singly linked list.
Definition: IntrusiveForwardList.hpp:855
typename UnsortedIntrusiveForwardList::reference reference
reference to value linked in the list
Definition: SortedIntrusiveForwardList.hpp:63
typename UnsortedIntrusiveForwardList::iterator iterator
iterator of elements on the list
Definition: SortedIntrusiveForwardList.hpp:57
static iterator insert_after(const iterator position, reference newElement)
Links the element in the list after position.
Definition: IntrusiveForwardList.hpp:1066
const U & const_reference
const reference to value linked in the list
Definition: IntrusiveForwardList.hpp:866
iterator end()
Definition: SortedIntrusiveForwardList.hpp:165
iterator before_begin()
Definition: IntrusiveForwardList.hpp:894
void pop_front()
Unlinks the first element from the list.
Definition: SortedIntrusiveForwardList.hpp:215
const_iterator cend() const
Definition: SortedIntrusiveForwardList.hpp:138
typename UnsortedIntrusiveForwardList::value_type value_type
value linked in the list
Definition: SortedIntrusiveForwardList.hpp:66
static iterator erase_after(const iterator position)
Unlinks the element following position from the list.
Definition: SortedIntrusiveForwardList.hpp:255
const_iterator cbefore_begin() const
Definition: IntrusiveForwardList.hpp:930
typename UnsortedIntrusiveForwardList::const_pointer const_pointer
const pointer to value linked in the list
Definition: SortedIntrusiveForwardList.hpp:51
reference front()
Definition: IntrusiveForwardList.hpp:993
iterator before_begin()
Definition: SortedIntrusiveForwardList.hpp:84
const U * const_pointer
const pointer to value linked in the list
Definition: IntrusiveForwardList.hpp:863
Implementation struct is used primarily for "Empty Base Optimization" with Compare type.
Definition: SortedIntrusiveForwardList.hpp:268
bool empty() const
Definition: SortedIntrusiveForwardList.hpp:156
void clear()
Unlinks all elements from the list.
Definition: IntrusiveForwardList.hpp:957
IntrusiveForwardList template class header.
iterator insert(reference newElement)
Links the element in the list, keeping it sorted.
Definition: SortedIntrusiveForwardList.hpp:205
IntrusiveForwardListConstIterator< T, NodePointer, U > const_iterator
const iterator of elements on the list
Definition: IntrusiveForwardList.hpp:860
const_iterator cbegin() const
Definition: SortedIntrusiveForwardList.hpp:129
const_iterator cend() const
Definition: IntrusiveForwardList.hpp:948
const_iterator end() const
Definition: SortedIntrusiveForwardList.hpp:174
iterator end()
Definition: IntrusiveForwardList.hpp:975
void swap(SortedIntrusiveForwardList &other)
Swaps contents with another list.
Definition: SortedIntrusiveForwardList.hpp:240
const_iterator cbegin() const
Definition: IntrusiveForwardList.hpp:939
typename UnsortedIntrusiveForwardList::const_iterator const_iterator
const iterator of elements on the list
Definition: SortedIntrusiveForwardList.hpp:48
const_iterator cbefore_begin() const
Definition: SortedIntrusiveForwardList.hpp:120
UnsortedIntrusiveForwardList intrusiveForwardList
internal unsorted IntrusiveForwardList
Definition: SortedIntrusiveForwardList.hpp:325
reference front()
Definition: SortedIntrusiveForwardList.hpp:183
IntrusiveForwardListIterator< T, NodePointer, U > iterator
iterator of elements on the list
Definition: IntrusiveForwardList.hpp:869
void swap(IntrusiveForwardListNode &left, IntrusiveForwardListNode &right)
Swaps contents of two nodes.
Definition: IntrusiveForwardList.hpp:172
typename UnsortedIntrusiveForwardList::const_reference const_reference
const reference to value linked in the list
Definition: SortedIntrusiveForwardList.hpp:54
void splice_after(const iterator beforeSplicedElement)
Transfers the element from another list to this one, keeping it sorted.
Definition: SortedIntrusiveForwardList.hpp:227
iterator findInsertPositionBefore(const_reference newElement)
Finds insert position "before" the position that satisfies sorting criteria.
Definition: SortedIntrusiveForwardList.hpp:291
void swap(IntrusiveForwardList &other)
Swaps contents with another list.
Definition: IntrusiveForwardList.hpp:1033
void swap(Implementation &other)
Swaps contents with another instance.
Definition: SortedIntrusiveForwardList.hpp:312
constexpr Implementation(const Compare &comparee)
Implementation's constructor.
Definition: SortedIntrusiveForwardList.hpp:276
const_reference front() const
Definition: SortedIntrusiveForwardList.hpp:192
typename UnsortedIntrusiveForwardList::pointer pointer
pointer to value linked in the list
Definition: SortedIntrusiveForwardList.hpp:60
constexpr SortedIntrusiveForwardList(const Compare &compare=Compare{})
SortedIntrusiveForwardList's constructor.
Definition: SortedIntrusiveForwardList.hpp:74
iterator begin()
Definition: IntrusiveForwardList.hpp:912
void swap(SortedIntrusiveForwardList< Compare, T, NodePointer, U > &left, SortedIntrusiveForwardList< Compare, T, NodePointer, U > &right)
Swaps contents of two lists.
Definition: SortedIntrusiveForwardList.hpp:347
bool empty() const
Definition: IntrusiveForwardList.hpp:966
iterator begin()
Definition: SortedIntrusiveForwardList.hpp:102
U value_type
value linked in the list
Definition: IntrusiveForwardList.hpp:878
U * pointer
pointer to value linked in the list
Definition: IntrusiveForwardList.hpp:872
void pop_front()
Unlinks the first element from the list.
Definition: IntrusiveForwardList.hpp:1011
Implementation implementation_
internal Implementation object - unsorted IntrusiveForwardList and Compare instance
Definition: SortedIntrusiveForwardList.hpp:329
static iterator erase_after(const iterator position)
Unlinks the element following position from the list.
Definition: IntrusiveForwardList.hpp:1048
static void splice_after(const iterator position, const iterator beforeSplicedElement)
Transfers the element from one list to another list after position.
Definition: IntrusiveForwardList.hpp:1087