distortos  v0.5.0
object-oriented C++ RTOS for microcontrollers
IntrusiveForwardList.hpp
Go to the documentation of this file.
1 
12 #ifndef ESTD_INTRUSIVEFORWARDLIST_HPP_
13 #define ESTD_INTRUSIVEFORWARDLIST_HPP_
14 
15 #include <iterator>
16 
17 #include <cstddef>
18 
19 namespace estd
20 {
21 
22 namespace internal
23 {
24 
25 class IntrusiveForwardListBase;
26 
27 }
28 
39 {
40 public:
41 
44  class AccessKey
45  {
47 
52  constexpr AccessKey()
53  {
54 
55  }
56 
57  AccessKey(const AccessKey&) = delete;
58  AccessKey(AccessKey&&) = delete;
59  const AccessKey& operator=(const AccessKey&) = delete;
60  AccessKey& operator=(AccessKey&&) = delete;
61  };
62 
68  nextNode_{}
69  {
70 
71  }
72 
80  nextNode_{other.nextNode_}
81  {
82  other.reset();
83  }
84 
90  {
91  return nextNode_;
92  }
93 
98  bool isLinked() const
99  {
100  return nextNode_ != nullptr;
101  }
102 
113  {
114  nextNode_ = position->getNextNode();
115  position->nextNode_ = this;
116  }
117 
125  {
126  using std::swap;
127  swap(nextNode_, other.nextNode_);
128  }
129 
139  {
140  auto& nextNode = *nextNode_;
141  nextNode_ = nextNode.nextNode_;
142 
143  nextNode.reset();
144  }
145 
147  const IntrusiveForwardListNode& operator=(const IntrusiveForwardListNode&) = delete;
148  IntrusiveForwardListNode& operator=(IntrusiveForwardListNode&&) = delete;
149 
150 private:
151 
156  void reset()
157  {
158  nextNode_ = {};
159  }
160 
163 };
164 
173 {
174  left.swap(right);
175 }
176 
177 namespace internal
178 {
179 
188 {
189 public:
190 
196  rootNode_{}
197  {
198 
199  }
200 
208  {
209  clear();
210  }
211 
217  {
218  return &rootNode_;
219  }
220 
226  {
227  return &rootNode_;
228  }
229 
235  {
236  return rootNode_.getNextNode();
237  }
238 
244  {
245  return rootNode_.getNextNode();
246  }
247 
253  {
254  return before_begin();
255  }
256 
262  {
263  return begin();
264  }
265 
271  {
272  return end();
273  }
274 
279  void clear()
280  {
281  while (empty() == false)
282  pop_front();
283  }
284 
289  bool empty() const
290  {
291  return begin() == end();
292  }
293 
299  {
300  return nullptr;
301  }
302 
308  {
309  return nullptr;
310  }
311 
316  void pop_front()
317  {
318  erase_after(before_begin());
319  }
320 
328  {
329  insert_after(before_begin(), newNode);
330  }
331 
339  {
340  rootNode_.swap(other.rootNode_);
341  }
342 
354  {
355  position->unlinkNext({});
356  return position->getNextNode();
357  }
358 
368  static void insert_after(IntrusiveForwardListNode* const position, IntrusiveForwardListNode& newNode)
369  {
370  newNode.linkAfter(position, {});
371  }
372 
383  static void splice_after(IntrusiveForwardListNode* const position,
384  IntrusiveForwardListNode* const beforeSplicedNode)
385  {
386  const auto splicedNode = beforeSplicedNode->getNextNode();
387  erase_after(beforeSplicedNode);
388  insert_after(position, *splicedNode);
389  }
390 
393  const IntrusiveForwardListBase& operator=(const IntrusiveForwardListBase&) = delete;
394  IntrusiveForwardListBase& operator=(IntrusiveForwardListBase&&) = delete;
395 
396 private:
397 
400 };
401 
410 {
411  left.swap(right);
412 }
413 
414 } // namespace internal
415 
427 template<typename T, IntrusiveForwardListNode T::* NodePointer, typename U = T>
429 {
430 public:
431 
433  using difference_type = ptrdiff_t;
434 
436  using iterator_category = std::forward_iterator_tag;
437 
439  using pointer = U*;
440 
442  using reference = U&;
443 
445  using value_type = U;
446 
452  node_{}
453  {
454 
455  }
456 
463  constexpr explicit IntrusiveForwardListIterator(IntrusiveForwardListNode* const node) :
464  node_{node}
465  {
466 
467  }
468 
475  constexpr explicit IntrusiveForwardListIterator(reference element) :
476  node_{&(element.*NodePointer)}
477  {
478  static_assert(std::is_same<U, T>::value == true || std::is_convertible<U, T>::value == true,
479  "U must be implicitly convertible to T!");
480  }
481 
489  {
490  return getPointer();
491  }
492 
500  {
501  return *getPointer();
502  }
503 
511  {
512  node_ = node_->getNextNode();
513  return *this;
514  }
515 
523  {
524  const auto temporary = *this;
525  node_ = node_->getNextNode();
526  return temporary;
527  }
528 
537  bool operator==(const IntrusiveForwardListIterator& other) const
538  {
539  return node_ == other.node_;
540  }
541 
542 private:
543 
551  {
552  static_assert(std::is_same<U, T>::value == true || std::is_convertible<U, T>::value == true,
553  "U must be implicitly convertible to T!");
554 
555  const auto offset = reinterpret_cast<size_t>(&(static_cast<pointer>(nullptr)->*NodePointer));
556  return reinterpret_cast<pointer>(reinterpret_cast<size_t>(node_) - offset);
557  }
558 
561 };
562 
577 template<typename T, IntrusiveForwardListNode T::* NodePointer, typename U = T>
580 {
581  return (left == right) == false;
582 }
583 
595 template<typename T, const IntrusiveForwardListNode T::* NodePointer, typename U = T>
597 {
598 public:
599 
601  using difference_type = ptrdiff_t;
602 
604  using iterator_category = std::forward_iterator_tag;
605 
607  using pointer = const U*;
608 
610  using reference = const U&;
611 
613  using value_type = U;
614 
620  node_{}
621  {
622 
623  }
624 
632  constexpr explicit IntrusiveForwardListConstIterator(const IntrusiveForwardListNode* const node) :
633  node_{node}
634  {
635 
636  }
637 
644  constexpr explicit IntrusiveForwardListConstIterator(reference element) :
645  node_{&(element.*NodePointer)}
646  {
647  static_assert(std::is_same<U, T>::value == true || std::is_convertible<U, T>::value == true,
648  "U must be implicitly convertible to T!");
649  }
650 
661  template<IntrusiveForwardListNode T::* NonConstNodePointer>
662  constexpr
665  {
666 
667  }
668 
676  {
677  return getPointer();
678  }
679 
687  {
688  return *getPointer();
689  }
690 
698  {
699  node_ = node_->getNextNode();
700  return *this;
701  }
702 
710  {
711  const auto temporary = *this;
712  node_ = node_->getNextNode();
713  return temporary;
714  }
715 
726  {
727  return node_ == other.node_;
728  }
729 
730 private:
731 
739  {
740  static_assert(std::is_same<U, T>::value == true || std::is_convertible<U, T>::value == true,
741  "U must be implicitly convertible to T!");
742 
743  const auto offset = reinterpret_cast<size_t>(&(static_cast<pointer>(nullptr)->*NodePointer));
744  return reinterpret_cast<pointer>(reinterpret_cast<size_t>(node_) - offset);
745  }
746 
749 };
750 
765 template<typename T, const IntrusiveForwardListNode T::* NodePointer, typename U = T>
768 {
769  return (left == right) == false;
770 }
771 
787 template<typename T, IntrusiveForwardListNode T::* NodePointer, const IntrusiveForwardListNode T::* ConstNodePointer,
788  typename U = T>
791 {
792  return decltype(right){left} == right;
793 }
794 
810 template<typename T, IntrusiveForwardListNode T::* NodePointer, const IntrusiveForwardListNode T::* ConstNodePointer,
811  typename U = T>
814 {
815  return (left == right) == false;
816 }
817 
833 template<typename T, IntrusiveForwardListNode T::* NodePointer, const IntrusiveForwardListNode T::* ConstNodePointer,
834  typename U = T>
837 {
838  return right != left;
839 }
840 
854 template<typename T, IntrusiveForwardListNode T::* NodePointer, typename U = T>
856 {
857 public:
858 
861 
863  using const_pointer = const U*;
864 
866  using const_reference = const U&;
867 
870 
872  using pointer = U*;
873 
875  using reference = U&;
876 
878  using value_type = U;
879 
884  constexpr IntrusiveForwardList() :
885  intrusiveForwardListBase_{}
886  {
887 
888  }
889 
895  {
896  return iterator{intrusiveForwardListBase_.before_begin()};
897  }
898 
904  {
905  return const_iterator{intrusiveForwardListBase_.before_begin()};
906  }
907 
913  {
914  return iterator{intrusiveForwardListBase_.begin()};
915  }
916 
922  {
923  return const_iterator{intrusiveForwardListBase_.begin()};
924  }
925 
931  {
932  return before_begin();
933  }
934 
940  {
941  return begin();
942  }
943 
949  {
950  return end();
951  }
952 
957  void clear()
958  {
959  intrusiveForwardListBase_.clear();
960  }
961 
966  bool empty() const
967  {
968  return intrusiveForwardListBase_.empty();
969  }
970 
976  {
977  return iterator{intrusiveForwardListBase_.end()};
978  }
979 
985  {
986  return const_iterator{intrusiveForwardListBase_.end()};
987  }
988 
994  {
995  return *begin();
996  }
997 
1003  {
1004  return *begin();
1005  }
1006 
1011  void pop_front()
1012  {
1013  erase_after(before_begin());
1014  }
1015 
1022  void push_front(reference newElement)
1023  {
1024  insert_after(before_begin(), newElement);
1025  }
1026 
1034  {
1035  intrusiveForwardListBase_.swap(other.intrusiveForwardListBase_);
1036  }
1037 
1048  static iterator erase_after(const iterator position)
1049  {
1050  auto& positionNode = (*position).*NodePointer;
1051  const auto afterNextNode = internal::IntrusiveForwardListBase::erase_after(&positionNode);
1052  return iterator{afterNextNode};
1053  }
1054 
1066  static iterator insert_after(const iterator position, reference newElement)
1067  {
1068  static_assert(std::is_same<U, T>::value == true || std::is_convertible<U, T>::value == true,
1069  "U must be implicitly convertible to T!");
1070 
1071  auto& positionNode = (*position).*NodePointer;
1072  auto& newElementNode = newElement.*NodePointer;
1073  internal::IntrusiveForwardListBase::insert_after(&positionNode, newElementNode);
1074  return iterator{&newElementNode};
1075  }
1076 
1087  static void splice_after(const iterator position, const iterator beforeSplicedElement)
1088  {
1089  auto& positionNode = (*position).*NodePointer;
1090  auto& beforeSplicedElementNode = (*beforeSplicedElement).*NodePointer;
1091  internal::IntrusiveForwardListBase::splice_after(&positionNode, &beforeSplicedElementNode);
1092  }
1093 
1094  IntrusiveForwardList(const IntrusiveForwardList&) = delete;
1096  const IntrusiveForwardList& operator=(const IntrusiveForwardList&) = delete;
1097  IntrusiveForwardList& operator=(IntrusiveForwardList&&) = delete;
1098 
1099 private:
1100 
1103 };
1104 
1117 template<typename T, IntrusiveForwardListNode T::* NodePointer, typename U = T>
1119 {
1120  left.swap(right);
1121 }
1122 
1123 } // namespace estd
1124 
1125 #endif // ESTD_INTRUSIVEFORWARDLIST_HPP_
Collection of useful templates.
constexpr IntrusiveForwardListConstIterator(const IntrusiveForwardListNode *const node)
IntrusiveForwardListConstIterator&#39;s constructor.
Definition: IntrusiveForwardList.hpp:632
static void splice_after(IntrusiveForwardListNode *const position, IntrusiveForwardListNode *const beforeSplicedNode)
Transfers the node from one list to another list after position.
Definition: IntrusiveForwardList.hpp:383
std::forward_iterator_tag iterator_category
category of the iterator
Definition: IntrusiveForwardList.hpp:604
QueueNode & reference
reference to value linked in the list
Definition: IntrusiveForwardList.hpp:875
const_reference front() const
Definition: IntrusiveForwardList.hpp:1002
Definition: IntrusiveForwardList.hpp:44
ptrdiff_t difference_type
difference type
Definition: IntrusiveForwardList.hpp:433
bool operator==(const IntrusiveForwardListIterator &other) const
IntrusiveForwardListIterator&#39;s "equal to" comparison operator.
Definition: IntrusiveForwardList.hpp:537
IntrusiveForwardListNode * before_begin()
Definition: IntrusiveForwardList.hpp:216
constexpr IntrusiveForwardListConstIterator()
IntrusiveForwardListConstIterator&#39;s constructor.
Definition: IntrusiveForwardList.hpp:619
const_iterator before_begin() const
Definition: IntrusiveForwardList.hpp:903
bool empty() const
Definition: IntrusiveForwardList.hpp:289
const IntrusiveForwardListNode * cend() const
Definition: IntrusiveForwardList.hpp:270
U & reference
reference to object "pointed to" by the iterator
Definition: IntrusiveForwardList.hpp:442
reference operator*() const
IntrusiveForwardListIterator&#39;s unary prefix dereference operator.
Definition: IntrusiveForwardList.hpp:499
void push_front(reference newElement)
Links the element at the beginning of the list.
Definition: IntrusiveForwardList.hpp:1022
constexpr IntrusiveForwardListConstIterator(const IntrusiveForwardListIterator< T, NonConstNodePointer, U > &iterator)
IntrusiveForwardListConstIterator&#39;s constructor.
Definition: IntrusiveForwardList.hpp:663
IntrusiveForwardListIterator class is an iterator of elements on IntrusiveForwardList.
Definition: IntrusiveForwardList.hpp:428
const U * pointer
pointer to object "pointed to" by the iterator
Definition: IntrusiveForwardList.hpp:607
void swap(IntrusiveForwardList< T, NodePointer, U > &left, IntrusiveForwardList< T, NodePointer, U > &right)
Swaps contents of two lists.
Definition: IntrusiveForwardList.hpp:1118
IntrusiveForwardList class is an intrusive linear singly linked list.
Definition: IntrusiveForwardList.hpp:855
IntrusiveForwardListNode rootNode_
root node of the intrusive forward list
Definition: IntrusiveForwardList.hpp:399
IntrusiveForwardListBase class provides base functionalities for IntrusiveForwardList class...
Definition: IntrusiveForwardList.hpp:187
const IntrusiveForwardListNode * before_begin() const
Definition: IntrusiveForwardList.hpp:225
static iterator insert_after(const iterator position, reference newElement)
Links the element in the list after position.
Definition: IntrusiveForwardList.hpp:1066
IntrusiveForwardListConstIterator operator++(int)
IntrusiveForwardListConstIterator&#39;s unary postfix increment operator.
Definition: IntrusiveForwardList.hpp:709
const QueueNode & const_reference
const reference to value linked in the list
Definition: IntrusiveForwardList.hpp:866
pointer getPointer() const
Converts contained pointer to IntrusiveForwardListNode to pointer to object that contains this node...
Definition: IntrusiveForwardList.hpp:738
IntrusiveForwardListConstIterator class is a const iterator of elements on IntrusiveForwardList.
Definition: IntrusiveForwardList.hpp:596
U * pointer
pointer to object "pointed to" by the iterator
Definition: IntrusiveForwardList.hpp:439
iterator before_begin()
Definition: IntrusiveForwardList.hpp:894
bool operator!=(const IntrusiveForwardListIterator< T, NodePointer, U > &left, const IntrusiveForwardListIterator< T, NodePointer, U > &right)
IntrusiveForwardListIterator&#39;s "not equal to" comparison operator.
Definition: IntrusiveForwardList.hpp:578
IntrusiveForwardListNode class is the node that is needed for the object to be linked in IntrusiveFor...
Definition: IntrusiveForwardList.hpp:38
pointer operator->() const
IntrusiveForwardListConstIterator&#39;s binary infix pointer member access operator.
Definition: IntrusiveForwardList.hpp:675
const_iterator begin() const
Definition: IntrusiveForwardList.hpp:921
const IntrusiveForwardListNode * begin() const
Definition: IntrusiveForwardList.hpp:243
pointer getPointer() const
Converts contained pointer to IntrusiveForwardListNode to pointer to object that contains this node...
Definition: IntrusiveForwardList.hpp:550
const_iterator cbefore_begin() const
Definition: IntrusiveForwardList.hpp:930
constexpr IntrusiveForwardListNode()
IntrusiveForwardListNode&#39;s constructor.
Definition: IntrusiveForwardList.hpp:67
const IntrusiveForwardListNode * end() const
Definition: IntrusiveForwardList.hpp:307
reference front()
Definition: IntrusiveForwardList.hpp:993
IntrusiveForwardListConstIterator & operator++()
IntrusiveForwardListConstIterator&#39;s unary prefix increment operator.
Definition: IntrusiveForwardList.hpp:697
constexpr IntrusiveForwardListBase()
IntrusiveForwardListBase&#39;s constructor.
Definition: IntrusiveForwardList.hpp:195
reference operator*() const
IntrusiveForwardListConstIterator&#39;s unary prefix dereference operator.
Definition: IntrusiveForwardList.hpp:686
void pop_front()
Unlinks the first node from the list.
Definition: IntrusiveForwardList.hpp:316
constexpr IntrusiveForwardList()
IntrusiveForwardList&#39;s constructor.
Definition: IntrusiveForwardList.hpp:884
~IntrusiveForwardListBase()
IntrusiveForwardListBase&#39;s destructor.
Definition: IntrusiveForwardList.hpp:207
IntrusiveForwardListNode * begin()
Definition: IntrusiveForwardList.hpp:234
void reset()
Resets the node to the same state as right after construction.
Definition: IntrusiveForwardList.hpp:156
const QueueNode * const_pointer
const pointer to value linked in the list
Definition: IntrusiveForwardList.hpp:863
constexpr AccessKey()
AccessKey&#39;s constructor.
Definition: IntrusiveForwardList.hpp:52
void clear()
Unlinks all elements from the list.
Definition: IntrusiveForwardList.hpp:957
void push_front(IntrusiveForwardListNode &newNode)
Links the node at the beginning of the list.
Definition: IntrusiveForwardList.hpp:327
constexpr IntrusiveForwardListIterator()
IntrusiveForwardListIterator&#39;s constructor.
Definition: IntrusiveForwardList.hpp:451
constexpr IntrusiveForwardListIterator(reference element)
IntrusiveForwardListIterator&#39;s constructor.
Definition: IntrusiveForwardList.hpp:475
constexpr IntrusiveForwardListIterator(IntrusiveForwardListNode *const node)
IntrusiveForwardListIterator&#39;s constructor.
Definition: IntrusiveForwardList.hpp:463
static IntrusiveForwardListNode * erase_after(IntrusiveForwardListNode *const position)
Unlinks the node following position from the list.
Definition: IntrusiveForwardList.hpp:353
static void insert_after(IntrusiveForwardListNode *const position, IntrusiveForwardListNode &newNode)
Links the node in the list after position.
Definition: IntrusiveForwardList.hpp:368
bool operator==(const IntrusiveForwardListConstIterator &other) const
IntrusiveForwardListConstIterator&#39;s "equal to" comparison operator.
Definition: IntrusiveForwardList.hpp:725
void unlinkNext(AccessKey)
Unlinks the node following this one from the list.
Definition: IntrusiveForwardList.hpp:138
const_iterator cend() const
Definition: IntrusiveForwardList.hpp:948
std::forward_iterator_tag iterator_category
category of the iterator
Definition: IntrusiveForwardList.hpp:436
iterator end()
Definition: IntrusiveForwardList.hpp:975
internal::IntrusiveForwardListBase intrusiveForwardListBase_
internal IntrusiveForwardListBase object
Definition: IntrusiveForwardList.hpp:1102
U value_type
value "pointed to" by the iterator
Definition: IntrusiveForwardList.hpp:613
const_iterator cbegin() const
Definition: IntrusiveForwardList.hpp:939
ptrdiff_t difference_type
difference type
Definition: IntrusiveForwardList.hpp:601
void swap(IntrusiveForwardList &other)
Swaps contents with another list.
Definition: IntrusiveForwardList.hpp:1033
void linkAfter(IntrusiveForwardListNode *const position, AccessKey)
Links the node in the list after position.
Definition: IntrusiveForwardList.hpp:112
const IntrusiveForwardListNode * cbefore_begin() const
Definition: IntrusiveForwardList.hpp:252
void swap(IntrusiveForwardListBase &other)
Swaps contents with another list.
Definition: IntrusiveForwardList.hpp:338
const IntrusiveForwardListNode * node_
pointer to const IntrusiveForwardListNode of the object "pointed to" by the iterator ...
Definition: IntrusiveForwardList.hpp:748
IntrusiveForwardListIterator & operator++()
IntrusiveForwardListIterator&#39;s unary prefix increment operator.
Definition: IntrusiveForwardList.hpp:510
IntrusiveForwardListNode * end()
Definition: IntrusiveForwardList.hpp:298
bool isLinked() const
Definition: IntrusiveForwardList.hpp:98
IntrusiveForwardListNode(IntrusiveForwardListNode &&other)
IntrusiveForwardListNode&#39;s move constructor.
Definition: IntrusiveForwardList.hpp:79
IntrusiveForwardListNode * node_
pointer to IntrusiveForwardListNode of the object "pointed to" by the iterator
Definition: IntrusiveForwardList.hpp:560
void swap(IntrusiveForwardListNode &other)
Swaps contents with another node.
Definition: IntrusiveForwardList.hpp:124
const IntrusiveForwardListNode * cbegin() const
Definition: IntrusiveForwardList.hpp:261
bool operator==(const IntrusiveForwardListIterator< T, NodePointer, U > &left, const IntrusiveForwardListConstIterator< T, ConstNodePointer, U > &right)
"Equal to" comparison operator for IntrusiveForwardListIterator and IntrusiveForwardListConstIterator...
Definition: IntrusiveForwardList.hpp:789
void clear()
Unlinks all nodes from the list.
Definition: IntrusiveForwardList.hpp:279
iterator begin()
Definition: IntrusiveForwardList.hpp:912
IntrusiveForwardListNode * nextNode_
pointer to next node on the list
Definition: IntrusiveForwardList.hpp:162
bool empty() const
Definition: IntrusiveForwardList.hpp:966
const_iterator end() const
Definition: IntrusiveForwardList.hpp:984
void swap(IntrusiveForwardListBase &left, IntrusiveForwardListBase &right)
Swaps contents of two lists.
Definition: IntrusiveForwardList.hpp:409
pointer operator->() const
IntrusiveForwardListIterator&#39;s binary infix pointer member access operator.
Definition: IntrusiveForwardList.hpp:488
QueueNode value_type
value linked in the list
Definition: IntrusiveForwardList.hpp:878
QueueNode * pointer
pointer to value linked in the list
Definition: IntrusiveForwardList.hpp:872
U value_type
value "pointed to" by the iterator
Definition: IntrusiveForwardList.hpp:445
void pop_front()
Unlinks the first element from the list.
Definition: IntrusiveForwardList.hpp:1011
IntrusiveForwardListIterator operator++(int)
IntrusiveForwardListIterator&#39;s unary postfix increment operator.
Definition: IntrusiveForwardList.hpp:522
const U & reference
reference to object "pointed to" by the iterator
Definition: IntrusiveForwardList.hpp:610
static iterator erase_after(const iterator position)
Unlinks the element following position from the list.
Definition: IntrusiveForwardList.hpp:1048
constexpr IntrusiveForwardListConstIterator(reference element)
IntrusiveForwardListConstIterator&#39;s constructor.
Definition: IntrusiveForwardList.hpp:644
IntrusiveForwardListNode * getNextNode() const
Definition: IntrusiveForwardList.hpp:89
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