distortos  v0.4.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_convertible<U, T>::value == true, "U must be implicitly convertible to T!");
479  }
480 
488  {
489  return getPointer();
490  }
491 
499  {
500  return *getPointer();
501  }
502 
510  {
511  node_ = node_->getNextNode();
512  return *this;
513  }
514 
522  {
523  const auto temporary = *this;
524  node_ = node_->getNextNode();
525  return temporary;
526  }
527 
536  bool operator==(const IntrusiveForwardListIterator& other) const
537  {
538  return node_ == other.node_;
539  }
540 
541 private:
542 
550  {
551  static_assert(std::is_convertible<U, T>::value == true, "U must be implicitly convertible to T!");
552 
553  const auto offset = reinterpret_cast<size_t>(&(static_cast<pointer>(nullptr)->*NodePointer));
554  return reinterpret_cast<pointer>(reinterpret_cast<size_t>(node_) - offset);
555  }
556 
559 };
560 
575 template<typename T, IntrusiveForwardListNode T::* NodePointer, typename U = T>
578 {
579  return (left == right) == false;
580 }
581 
593 template<typename T, const IntrusiveForwardListNode T::* NodePointer, typename U = T>
595 {
596 public:
597 
599  using difference_type = ptrdiff_t;
600 
602  using iterator_category = std::forward_iterator_tag;
603 
605  using pointer = const U*;
606 
608  using reference = const U&;
609 
611  using value_type = U;
612 
618  node_{}
619  {
620 
621  }
622 
630  constexpr explicit IntrusiveForwardListConstIterator(const IntrusiveForwardListNode* const node) :
631  node_{node}
632  {
633 
634  }
635 
642  constexpr explicit IntrusiveForwardListConstIterator(reference element) :
643  node_{&(element.*NodePointer)}
644  {
645  static_assert(std::is_convertible<U, T>::value == true, "U must be implicitly convertible to T!");
646  }
647 
658  template<IntrusiveForwardListNode T::* NonConstNodePointer>
659  constexpr
662  {
663 
664  }
665 
673  {
674  return getPointer();
675  }
676 
684  {
685  return *getPointer();
686  }
687 
695  {
696  node_ = node_->getNextNode();
697  return *this;
698  }
699 
707  {
708  const auto temporary = *this;
709  node_ = node_->getNextNode();
710  return temporary;
711  }
712 
723  {
724  return node_ == other.node_;
725  }
726 
727 private:
728 
736  {
737  static_assert(std::is_convertible<U, T>::value == true, "U must be implicitly convertible to T!");
738 
739  const auto offset = reinterpret_cast<size_t>(&(static_cast<pointer>(nullptr)->*NodePointer));
740  return reinterpret_cast<pointer>(reinterpret_cast<size_t>(node_) - offset);
741  }
742 
745 };
746 
761 template<typename T, const IntrusiveForwardListNode T::* NodePointer, typename U = T>
764 {
765  return (left == right) == false;
766 }
767 
783 template<typename T, IntrusiveForwardListNode T::* NodePointer, const IntrusiveForwardListNode T::* ConstNodePointer,
784  typename U = T>
787 {
788  return decltype(right){left} == right;
789 }
790 
806 template<typename T, IntrusiveForwardListNode T::* NodePointer, const IntrusiveForwardListNode T::* ConstNodePointer,
807  typename U = T>
810 {
811  return (left == right) == false;
812 }
813 
829 template<typename T, IntrusiveForwardListNode T::* NodePointer, const IntrusiveForwardListNode T::* ConstNodePointer,
830  typename U = T>
833 {
834  return right != left;
835 }
836 
850 template<typename T, IntrusiveForwardListNode T::* NodePointer, typename U = T>
852 {
853 public:
854 
857 
859  using const_pointer = const U*;
860 
862  using const_reference = const U&;
863 
866 
868  using pointer = U*;
869 
871  using reference = U&;
872 
874  using value_type = U;
875 
880  constexpr IntrusiveForwardList() :
881  intrusiveForwardListBase_{}
882  {
883 
884  }
885 
891  {
892  return iterator{intrusiveForwardListBase_.before_begin()};
893  }
894 
900  {
901  return const_iterator{intrusiveForwardListBase_.before_begin()};
902  }
903 
909  {
910  return iterator{intrusiveForwardListBase_.begin()};
911  }
912 
918  {
919  return const_iterator{intrusiveForwardListBase_.begin()};
920  }
921 
927  {
928  return before_begin();
929  }
930 
936  {
937  return begin();
938  }
939 
945  {
946  return end();
947  }
948 
953  void clear()
954  {
955  intrusiveForwardListBase_.clear();
956  }
957 
962  bool empty() const
963  {
964  return intrusiveForwardListBase_.empty();
965  }
966 
972  {
973  return iterator{intrusiveForwardListBase_.end()};
974  }
975 
981  {
982  return const_iterator{intrusiveForwardListBase_.end()};
983  }
984 
990  {
991  return *begin();
992  }
993 
999  {
1000  return *begin();
1001  }
1002 
1007  void pop_front()
1008  {
1009  erase_after(before_begin());
1010  }
1011 
1018  void push_front(reference newElement)
1019  {
1020  insert_after(before_begin(), newElement);
1021  }
1022 
1030  {
1031  intrusiveForwardListBase_.swap(other.intrusiveForwardListBase_);
1032  }
1033 
1044  static iterator erase_after(const iterator position)
1045  {
1046  auto& positionNode = (*position).*NodePointer;
1047  const auto afterNextNode = internal::IntrusiveForwardListBase::erase_after(&positionNode);
1048  return iterator{afterNextNode};
1049  }
1050 
1062  static iterator insert_after(const iterator position, reference newElement)
1063  {
1064  static_assert(std::is_convertible<U, T>::value == true, "U must be implicitly convertible to T!");
1065 
1066  auto& positionNode = (*position).*NodePointer;
1067  auto& newElementNode = newElement.*NodePointer;
1068  internal::IntrusiveForwardListBase::insert_after(&positionNode, newElementNode);
1069  return iterator{&newElementNode};
1070  }
1071 
1082  static void splice_after(const iterator position, const iterator beforeSplicedElement)
1083  {
1084  auto& positionNode = (*position).*NodePointer;
1085  auto& beforeSplicedElementNode = (*beforeSplicedElement).*NodePointer;
1086  internal::IntrusiveForwardListBase::splice_after(&positionNode, &beforeSplicedElementNode);
1087  }
1088 
1089  IntrusiveForwardList(const IntrusiveForwardList&) = delete;
1091  const IntrusiveForwardList& operator=(const IntrusiveForwardList&) = delete;
1092  IntrusiveForwardList& operator=(IntrusiveForwardList&&) = delete;
1093 
1094 private:
1095 
1098 };
1099 
1112 template<typename T, IntrusiveForwardListNode T::* NodePointer, typename U = T>
1114 {
1115  left.swap(right);
1116 }
1117 
1118 } // namespace estd
1119 
1120 #endif // ESTD_INTRUSIVEFORWARDLIST_HPP_
Collection of useful templates.
constexpr IntrusiveForwardListConstIterator(const IntrusiveForwardListNode *const node)
IntrusiveForwardListConstIterator&#39;s constructor.
Definition: IntrusiveForwardList.hpp:630
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:602
QueueNode & reference
reference to value linked in the list
Definition: IntrusiveForwardList.hpp:871
const_reference front() const
Definition: IntrusiveForwardList.hpp:998
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:536
IntrusiveForwardListNode * before_begin()
Definition: IntrusiveForwardList.hpp:216
constexpr IntrusiveForwardListConstIterator()
IntrusiveForwardListConstIterator&#39;s constructor.
Definition: IntrusiveForwardList.hpp:617
const_iterator before_begin() const
Definition: IntrusiveForwardList.hpp:899
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:498
void push_front(reference newElement)
Links the element at the beginning of the list.
Definition: IntrusiveForwardList.hpp:1018
constexpr IntrusiveForwardListConstIterator(const IntrusiveForwardListIterator< T, NonConstNodePointer, U > &iterator)
IntrusiveForwardListConstIterator&#39;s constructor.
Definition: IntrusiveForwardList.hpp:660
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:605
void swap(IntrusiveForwardList< T, NodePointer, U > &left, IntrusiveForwardList< T, NodePointer, U > &right)
Swaps contents of two lists.
Definition: IntrusiveForwardList.hpp:1113
IntrusiveForwardList class is an intrusive linear singly linked list.
Definition: IntrusiveForwardList.hpp:851
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:1062
IntrusiveForwardListConstIterator operator++(int)
IntrusiveForwardListConstIterator&#39;s unary postfix increment operator.
Definition: IntrusiveForwardList.hpp:706
const QueueNode & const_reference
const reference to value linked in the list
Definition: IntrusiveForwardList.hpp:862
pointer getPointer() const
Converts contained pointer to IntrusiveForwardListNode to pointer to object that contains this node...
Definition: IntrusiveForwardList.hpp:735
IntrusiveForwardListConstIterator class is a const iterator of elements on IntrusiveForwardList.
Definition: IntrusiveForwardList.hpp:594
U * pointer
pointer to object "pointed to" by the iterator
Definition: IntrusiveForwardList.hpp:439
iterator before_begin()
Definition: IntrusiveForwardList.hpp:890
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:576
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:672
const_iterator begin() const
Definition: IntrusiveForwardList.hpp:917
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:549
const_iterator cbefore_begin() const
Definition: IntrusiveForwardList.hpp:926
constexpr IntrusiveForwardListNode()
IntrusiveForwardListNode&#39;s constructor.
Definition: IntrusiveForwardList.hpp:67
const IntrusiveForwardListNode * end() const
Definition: IntrusiveForwardList.hpp:307
reference front()
Definition: IntrusiveForwardList.hpp:989
IntrusiveForwardListConstIterator & operator++()
IntrusiveForwardListConstIterator&#39;s unary prefix increment operator.
Definition: IntrusiveForwardList.hpp:694
constexpr IntrusiveForwardListBase()
IntrusiveForwardListBase&#39;s constructor.
Definition: IntrusiveForwardList.hpp:195
reference operator*() const
IntrusiveForwardListConstIterator&#39;s unary prefix dereference operator.
Definition: IntrusiveForwardList.hpp:683
void pop_front()
Unlinks the first node from the list.
Definition: IntrusiveForwardList.hpp:316
constexpr IntrusiveForwardList()
IntrusiveForwardList&#39;s constructor.
Definition: IntrusiveForwardList.hpp:880
~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:859
constexpr AccessKey()
AccessKey&#39;s constructor.
Definition: IntrusiveForwardList.hpp:52
void clear()
Unlinks all elements from the list.
Definition: IntrusiveForwardList.hpp:953
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:722
void unlinkNext(AccessKey)
Unlinks the node following this one from the list.
Definition: IntrusiveForwardList.hpp:138
const_iterator cend() const
Definition: IntrusiveForwardList.hpp:944
std::forward_iterator_tag iterator_category
category of the iterator
Definition: IntrusiveForwardList.hpp:436
iterator end()
Definition: IntrusiveForwardList.hpp:971
internal::IntrusiveForwardListBase intrusiveForwardListBase_
internal IntrusiveForwardListBase object
Definition: IntrusiveForwardList.hpp:1097
U value_type
value "pointed to" by the iterator
Definition: IntrusiveForwardList.hpp:611
const_iterator cbegin() const
Definition: IntrusiveForwardList.hpp:935
ptrdiff_t difference_type
difference type
Definition: IntrusiveForwardList.hpp:599
void swap(IntrusiveForwardList &other)
Swaps contents with another list.
Definition: IntrusiveForwardList.hpp:1029
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:744
IntrusiveForwardListIterator & operator++()
IntrusiveForwardListIterator&#39;s unary prefix increment operator.
Definition: IntrusiveForwardList.hpp:509
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:558
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:785
void clear()
Unlinks all nodes from the list.
Definition: IntrusiveForwardList.hpp:279
iterator begin()
Definition: IntrusiveForwardList.hpp:908
IntrusiveForwardListNode * nextNode_
pointer to next node on the list
Definition: IntrusiveForwardList.hpp:162
bool empty() const
Definition: IntrusiveForwardList.hpp:962
const_iterator end() const
Definition: IntrusiveForwardList.hpp:980
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:487
QueueNode value_type
value linked in the list
Definition: IntrusiveForwardList.hpp:874
QueueNode * pointer
pointer to value linked in the list
Definition: IntrusiveForwardList.hpp:868
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:1007
IntrusiveForwardListIterator operator++(int)
IntrusiveForwardListIterator&#39;s unary postfix increment operator.
Definition: IntrusiveForwardList.hpp:521
const U & reference
reference to object "pointed to" by the iterator
Definition: IntrusiveForwardList.hpp:608
static iterator erase_after(const iterator position)
Unlinks the element following position from the list.
Definition: IntrusiveForwardList.hpp:1044
constexpr IntrusiveForwardListConstIterator(reference element)
IntrusiveForwardListConstIterator&#39;s constructor.
Definition: IntrusiveForwardList.hpp:642
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:1082