Embedded Template Library 1.0
Loading...
Searching...
No Matches
intrusive_forward_list.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2016 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_INTRUSIVE_FORWARD_LIST_INCLUDED
32#define ETL_INTRUSIVE_FORWARD_LIST_INCLUDED
33
34#include "platform.h"
35#include "algorithm.h"
36#include "iterator.h"
37#include "functional.h"
38#include "nullptr.h"
39#include "type_traits.h"
40#include "exception.h"
41#include "error_handler.h"
42#include "intrusive_links.h"
43
44#include <stddef.h>
45
46#include "private/minmax_push.h"
47
48namespace etl
49{
50 //***************************************************************************
53 //***************************************************************************
63
64 //***************************************************************************
67 //***************************************************************************
69 {
70 public:
71
73 : intrusive_forward_list_exception(ETL_ERROR_TEXT("intrusive_forward_list:empty", ETL_INTRUSIVE_FORWARD_LIST_FILE_ID"A"), file_name_, line_number_)
74 {
75 }
76 };
77
78 //***************************************************************************
81 //***************************************************************************
83 {
84 public:
85
87 : intrusive_forward_list_exception(ETL_ERROR_TEXT("intrusive_forward_list:iterator", ETL_INTRUSIVE_FORWARD_LIST_FILE_ID"B"), file_name_, line_number_)
88 {
89 }
90 };
91
92 //***************************************************************************
95 //***************************************************************************
97 {
98 public:
99
101 : intrusive_forward_list_exception(ETL_ERROR_TEXT("intrusive_forward_list:bounds", ETL_INTRUSIVE_FORWARD_LIST_FILE_ID"C"), file_name_, line_number_)
102 {
103 }
104 };
105
106 //***************************************************************************
109 //***************************************************************************
111 {
112 public:
113
115 : intrusive_forward_list_exception(ETL_ERROR_TEXT("intrusive_forward_list:unsorted", ETL_INTRUSIVE_FORWARD_LIST_FILE_ID"D"), file_name_, line_number_)
116 {
117 }
118 };
119
120 //***************************************************************************
123 //***************************************************************************
125 {
126 public:
127
129 : intrusive_forward_list_exception(ETL_ERROR_TEXT("intrusive_forward_list:value is already linked", ETL_INTRUSIVE_FORWARD_LIST_FILE_ID"E"), file_name_, line_number_)
130 {
131 }
132 };
133
134 //***************************************************************************
137 //***************************************************************************
138 template <typename TLink>
140 {
141 public:
142
143 // Node typedef.
144 typedef TLink link_type;
145
146 //*************************************************************************
148 //*************************************************************************
149 void clear()
150 {
151 // Unlink all of the items.
152 link_type* p_unlink = start.etl_next;
153
154 while (p_unlink != &terminator)
155 {
156 link_type* p_next = p_unlink->etl_next;
157 p_unlink->clear();
158 p_unlink = p_next;
159 }
160
161 initialise();
162 }
163
164 //*************************************************************************
167 //*************************************************************************
168 template <typename TIterator>
169 void assign(TIterator first, TIterator last)
170 {
171#if ETL_IS_DEBUG_BUILD
172 intmax_t d = etl::distance(first, last);
173 ETL_ASSERT_OR_RETURN(d >= 0, ETL_ERROR(intrusive_forward_list_iterator_exception));
174#endif
175
176 clear();
177
178 link_type* p_last = &start;
179
180 // Add all of the elements.
181 while (first != last)
182 {
183 link_type& value = *first++;
184
185 ETL_ASSERT_OR_RETURN(!value.is_linked(), ETL_ERROR(intrusive_forward_list_value_is_already_linked));
186
187 value.etl_next = p_last->etl_next;
188 p_last->etl_next = &value;
189 p_last = &value;
190 ++current_size;
191 }
192 }
193
194 //*************************************************************************
196 //*************************************************************************
197 void push_front(link_type& value)
198 {
199 ETL_ASSERT_OR_RETURN(!value.is_linked(), ETL_ERROR(intrusive_forward_list_value_is_already_linked));
200
201 insert_link_after(start, value);
202 }
203
204 //*************************************************************************
206 //*************************************************************************
208 {
209#if defined(ETL_CHECK_PUSH_POP)
210 ETL_ASSERT_OR_RETURN(!empty(), ETL_ERROR(intrusive_forward_list_empty));
211#endif
213 }
214
215 //*************************************************************************
217 //*************************************************************************
218 void reverse()
219 {
220 if (is_trivial_list())
221 {
222 return;
223 }
224
225 link_type* previous = &terminator; // Point to the terminator of the linked list.
226 link_type* current = start.etl_next; // Point to the first item in the linked list (could be the terminator).
227 link_type* next = start.etl_next; // Point to the first item in the linked list (could be the terminator).
228
229 while (next != &terminator)
230 {
231 next = next->etl_next; // Point to next link.
232 current->etl_next = previous; // Reverse the current link.
233 previous = current; // Previous points to current.
234 current = next; // Current points to next.
235 }
236
237 etl::link<link_type>(start, previous);
238 }
239
240 //*************************************************************************
242 //*************************************************************************
243 bool empty() const
244 {
245 return (current_size == 0);
246 }
247
248 //*************************************************************************
250 //*************************************************************************
251 size_t size() const
252 {
253 return current_size;
254 }
255
256 protected:
257
258 link_type start;
259 static link_type terminator;
260
262
263 //*************************************************************************
265 //*************************************************************************
270
271 //*************************************************************************
273 //*************************************************************************
278
279 //*************************************************************************
281 //*************************************************************************
282 bool is_trivial_list() const
283 {
284 return (size() <= 1U);
285 }
286
287 //*************************************************************************
289 //*************************************************************************
290 void insert_link_after(link_type& position, link_type& link)
291 {
292 // Connect to the intrusive_forward_list.
293 etl::link_splice<link_type>(position, link);
294 ++current_size;
295 }
296
297 //*************************************************************************
299 //*************************************************************************
300 void disconnect_link_after(link_type& link)
301 {
302 link_type* p_next = link.etl_next;
303
304 if (p_next != &this->terminator)
305 {
306 link_type* p_unlinked = etl::unlink_after<link_type>(link);
307 p_unlinked->clear();
308 --current_size;
309 }
310 }
311
312 //*************************************************************************
314 //*************************************************************************
315 link_type* get_head()
316 {
317 return start.etl_next;
318 }
319
320 //*************************************************************************
322 //*************************************************************************
323 const link_type* get_head() const
324 {
325 return start.etl_next;
326 }
327
328 //*************************************************************************
330 //*************************************************************************
332 {
333 start.etl_next = &terminator;
334 current_size = 0;
335 }
336
337 //*************************************************************************
340 //*************************************************************************
341 link_type* is_link_in_list(link_type& search_link)
342 {
343 link_type* p_link = start.etl_next;
344 link_type* p_previous = &start;
345
346 while (p_link != ETL_NULLPTR)
347 {
348 if (&search_link == p_link)
349 {
350 return p_previous;
351 }
352
354
355 if (p_link != ETL_NULLPTR)
356 {
357 p_link = p_link->link_type::etl_next;
358 }
359 }
360
361 return ETL_NULLPTR;
362 }
363
364 //*************************************************************************
368 //*************************************************************************
369 link_type* remove_link(link_type& link)
370 {
371 link_type* result = ETL_NULLPTR;
372
373 link_type* p_previous = is_link_in_list(link);
374
375 if (p_previous != ETL_NULLPTR)
376 {
377 link_type* p_next = link.etl_next;
378
380
381 if (p_next != &this->terminator)
382 {
383 result = p_next;
384 }
385 }
386
387 return result;
388 }
389
390 //*************************************************************************
392 //*************************************************************************
393 link_type* remove_link_range_after(link_type* p_first, link_type* p_last)
394 {
395 link_type* p_after = p_first->etl_next;
396
397 // Join the ends.
399
400 // Unlink the erased range.
401 link_type* p_unlink = p_after;
402
403 while (p_unlink != p_last)
404 {
405 link_type* p_next = p_unlink->etl_next;
406 p_unlink->clear();
407 p_unlink = p_next;
408 }
409
410 if (p_after == &this->terminator)
411 {
412 return ETL_NULLPTR;
413 }
414 else
415 {
416 return p_last;
417 }
418 }
419 };
420
421 template <typename TLink>
423
424 //***************************************************************************
428 //***************************************************************************
429 template <typename TValue, typename TLink>
431 {
432 public:
433
434 // Node typedef.
435 typedef typename etl::intrusive_forward_list_base<TLink>::link_type link_type;
436
437 // STL style typedefs.
438 typedef TValue value_type;
439 typedef value_type* pointer;
440 typedef const value_type* const_pointer;
441 typedef value_type& reference;
442 typedef const value_type& const_reference;
443 typedef size_t size_type;
444
446
447 typedef TValue node_type;
448
449 //*************************************************************************
451 //*************************************************************************
452 class iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, value_type>
453 {
454 public:
455
456 friend class intrusive_forward_list;
457 friend class const_iterator;
458
459 iterator()
460 : p_value(ETL_NULLPTR)
461 {
462 }
463
464 iterator(const iterator& other)
465 : p_value(other.p_value)
466 {
467 }
468
470 {
471 // Read the appropriate 'etl_next'.
472 p_value = p_value->etl_next;
473 return *this;
474 }
475
477 {
478 iterator temp(*this);
479 // Read the appropriate 'etl_next'.
480 p_value = p_value->etl_next;
481 return temp;
482 }
483
485 {
486 p_value = other.p_value;
487 return *this;
488 }
489
490 reference operator *() const
491 {
493 return *static_cast<pointer>(p_value);
495 }
496
497 pointer operator &() const
498 {
499 return static_cast<pointer>(p_value);
500 }
501
502 pointer operator ->() const
503 {
504 return static_cast<pointer>(p_value);
505 }
506
507 friend bool operator == (const iterator& lhs, const iterator& rhs)
508 {
509 return lhs.p_value == rhs.p_value;
510 }
511
512 friend bool operator != (const iterator& lhs, const iterator& rhs)
513 {
514 return !(lhs == rhs);
515 }
516
517 private:
518
519 iterator(link_type* value)
520 : p_value(value)
521 {
522 }
523
524 link_type* p_value;
525 };
526
527 //*************************************************************************
529 //*************************************************************************
530 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const value_type>
531 {
532 public:
533
534 friend class intrusive_forward_list;
535
537 : p_value(ETL_NULLPTR)
538 {
539 }
540
542 : p_value(other.p_value)
543 {
544 }
545
547 : p_value(other.p_value)
548 {
549 }
550
552 {
553 // Read the appropriate 'etl_next'.
554 p_value = p_value->etl_next;
555 return *this;
556 }
557
559 {
560 const_iterator temp(*this);
561 // Read the appropriate 'etl_next'.
562 p_value = p_value->etl_next;
563 return temp;
564 }
565
567 {
568 p_value = other.p_value;
569 return *this;
570 }
571
573 {
574 return *static_cast<const value_type*>(p_value);
575 }
576
578 {
579 return static_cast<const value_type*>(p_value);
580 }
581
583 {
584 return static_cast<const value_type*>(p_value);
585 }
586
587 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
588 {
589 return lhs.p_value == rhs.p_value;
590 }
591
592 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
593 {
594 return !(lhs == rhs);
595 }
596
597 private:
598
599 const_iterator(const link_type* value)
600 : p_value(value)
601 {
602 }
603
604 const link_type* p_value;
605 };
606
607 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
608
609 //*************************************************************************
611 //*************************************************************************
615
616 //*************************************************************************
618 //*************************************************************************
622
623 //*************************************************************************
625 //*************************************************************************
626 template <typename TIterator>
628 {
629 this->assign(first, last);
630 }
631
632 //*************************************************************************
634 //*************************************************************************
636 {
637 return iterator(this->get_head());
638 }
639
640 //*************************************************************************
642 //*************************************************************************
644 {
645 return const_iterator(this->get_head());
646 }
647
648 //*************************************************************************
650 //*************************************************************************
652 {
653 return iterator(&this->start);
654 }
655
656 //*************************************************************************
658 //*************************************************************************
660 {
661 return const_iterator(&this->start);
662 }
663
664 //*************************************************************************
666 //*************************************************************************
668 {
669 return const_iterator(this->get_head());
670 }
671
672 //*************************************************************************
674 //*************************************************************************
676 {
677 return iterator(&this->terminator);
678 }
679
680 //*************************************************************************
682 //*************************************************************************
684 {
685 return const_iterator(&this->terminator);
686 }
687
688 //*************************************************************************
690 //*************************************************************************
692 {
693 return const_iterator(&this->terminator);
694 }
695
696 //*************************************************************************
698 //*************************************************************************
699 reference front()
700 {
701 return *static_cast<pointer>(this->get_head());
702 }
703
704 //*************************************************************************
706 //*************************************************************************
707 const_reference front() const
708 {
709 return *static_cast<const value_type*>(this->get_head());
710 }
711
712 //*************************************************************************
714 //*************************************************************************
716 {
717 ETL_ASSERT_OR_RETURN_VALUE(!value.link_type::is_linked(), ETL_ERROR(intrusive_forward_list_value_is_already_linked), iterator(&value));
718
719 this->insert_link_after(*position.p_value, value);
720 return iterator(&value);
721 }
722
723 //*************************************************************************
725 //*************************************************************************
726 template <typename TIterator>
727 void insert_after(iterator position, TIterator first, TIterator last)
728 {
729 while (first != last)
730 {
731 // Set up the next free link.
732 ETL_ASSERT_OR_RETURN(!(*first).link_type::is_linked(), ETL_ERROR(intrusive_forward_list_value_is_already_linked));
733
734 this->insert_link_after(*position.p_value, *first);
735 ++first;
736 ++position;
737 }
738 }
739
740 //*************************************************************************
742 //*************************************************************************
744 {
745 iterator next(position);
746 if (next != end())
747 {
748 ++next;
749 if (next != end())
750 {
751 ++next;
752 this->disconnect_link_after(*position.p_value);
753 }
754 }
755
756 return next;
757 }
758
759 //*************************************************************************
761 //*************************************************************************
763 {
764 if (first != end() && (first != last))
765 {
766 this->current_size -= etl::distance(first, last) - 1;
767
768 link_type* p_first = first.p_value;
769 link_type* p_last = last.p_value;
771
772 if (p_after == ETL_NULLPTR)
773 {
774 return end();
775 }
776 else
777 {
778 return last;
779 }
780 }
781 else
782 {
783 return last;
784 }
785 }
786
787 //*************************************************************************
789 //*************************************************************************
791 {
792 return static_cast<node_type*>(this->remove_link(node));
793 }
794
795 //*************************************************************************
798 //*************************************************************************
799 template <typename TIsEqual>
801 {
802 if (this->empty())
803 {
804 return;
805 }
806
807 link_type* last = this->get_head();
808 link_type* current = last->etl_next;
809
810 while (current != &this->terminator)
811 {
812 // Is this value the same as the last?
813 if (isEqual(*static_cast<pointer>(current), *static_cast<pointer>(last)))
814 {
815 this->disconnect_link_after(*last);
816 }
817 else
818 {
819 // Move on one.
820 last = current;
821 }
822
823 current = last->etl_next;
824 }
825 }
826
827 //*************************************************************************
829 //*************************************************************************
830 void sort()
831 {
833 }
834
835 //*************************************************************************
859 //*************************************************************************
860 template <typename TCompare>
862 {
868 int list_size = 1;
870 int left_size;
871 int right_size;
872
873 if (this->is_trivial_list())
874 {
875 return;
876 }
877
878 while (true)
879 {
880 i_left = begin();
883
884 number_of_merges = 0; // Count the number of merges we do in this pass.
885
886 while (i_left != end())
887 {
888 ++number_of_merges; // There exists a merge to be done.
889 i_right = i_left;
890 left_size = 0;
891
892 // Step 'list_size' places along from left
893 for (int i = 0; i < list_size; ++i)
894 {
895 ++left_size;
896
897 ++i_right;
898
899 if (i_right == end())
900 {
901 break;
902 }
903 }
904
905 // If right hasn't fallen off end, we have two lists to merge.
907
908 // Now we have two lists. Merge them.
909 while (left_size > 0 || (right_size > 0 && i_right != end()))
910 {
911 // Decide whether the next link of merge comes from left or right.
912 if (left_size == 0)
913 {
914 // Left is empty. The link must come from right.
915 i_link = i_right;
916 ++i_right;
917 --right_size;
918 }
919 else if (right_size == 0 || i_right == end())
920 {
921 // Right is empty. The link must come from left.
922 i_link = i_left;
923 ++i_left;
924 --left_size;
925 }
926 else if (!compare(*i_right, *i_left))
927 {
928 // First link of left is lower or same. The link must come from left.
929 i_link = i_left;
930 ++i_left;
931 --left_size;
932 }
933 else
934 {
935 // First link of right is lower. The link must come from right.
936 i_link = i_right;
937 ++i_right;
938 --right_size;
939 }
940
941 // Add the next link to the merged head.
942 if (i_head == before_begin())
943 {
944 etl::link<link_type>(i_head.p_value, i_link.p_value);
945 i_head = i_link;
946 i_tail = i_link;
947 }
948 else
949 {
950 etl::link<link_type>(i_tail.p_value, i_link.p_value);
951 i_tail = i_link;
952 }
953
954 i_tail.p_value->etl_next = &this->terminator;
955 }
956
957 // Now left has stepped `list_size' places along, and right has too.
958 i_left = i_right;
959 }
960
961 // If we have done only one merge, we're finished.
962 if (number_of_merges <= 1) // Allow for number_of_merges == 0, the empty head case
963 {
964 return;
965 }
966
967 // Otherwise repeat, merging lists twice the size
968 list_size *= 2;
969 }
970 }
971
972 //*************************************************************************
973 // Removes the values specified.
974 //*************************************************************************
975 void remove(const_reference value)
976 {
979
980 while (i_item != end())
981 {
982 if (*i_item == value)
983 {
985 }
986 else
987 {
988 ++i_item;
989 ++i_last_item;
990 }
991 }
992 }
993
994 //*************************************************************************
996 //*************************************************************************
997 template <typename TPredicate>
999 {
1000 iterator i_item = begin();
1002
1003 while (i_item != end())
1004 {
1005 if (predicate(*i_item))
1006 {
1008 }
1009 else
1010 {
1011 ++i_item;
1012 ++i_last_item;
1013 }
1014 }
1015 }
1016
1017 //*************************************************************************
1019 //*************************************************************************
1021 {
1022 // No point splicing to ourself!
1023 if (&other != this)
1024 {
1025 if (!other.empty())
1026 {
1027 link_type& first = *other.get_head();
1028
1029 if (&other != this)
1030 {
1031 this->current_size += other.size();
1032 }
1033
1034 link_type& before = *position.p_value;
1035 link_type& after = *position.p_value->etl_next;
1036
1038
1039 link_type* last = &before;
1040 while (last->etl_next != &other.terminator)
1041 {
1042 last = last->etl_next;
1043 }
1044
1046
1047 other.initialise();
1048 }
1049 }
1050 }
1051
1052 //*************************************************************************
1054 //*************************************************************************
1056 {
1057 link_type& before = *position.p_value;
1058
1061
1062 if (&other != this)
1063 {
1064 ++this->current_size;
1065 --other.current_size;
1066 }
1067 }
1068
1069 //*************************************************************************
1071 //*************************************************************************
1073 {
1074 if (!other.empty())
1075 {
1076 if (&other != this)
1077 {
1078 size_t n = etl::distance(begin_, end_) - 1;
1079 this->current_size += n;
1080 other.current_size -= n;
1081 }
1082
1083 link_type* first = begin_.p_value;
1084 link_type* last = first;
1085
1086 while (last->etl_next != end_.p_value)
1087 {
1088 last = last->etl_next;
1089 }
1090
1091 // Unlink from the source list.
1092 link_type* first_next = first->etl_next;
1093 etl::unlink_after(*first, *last);
1094
1095 // Fix our links.
1096 link_type* before = position.p_value;
1097
1099 }
1100 }
1101
1102 //*************************************************************************
1104 //*************************************************************************
1106 {
1108 }
1109
1110 //*************************************************************************
1112 //*************************************************************************
1113 template <typename TCompare>
1115 {
1116 if ((this != &other) && !other.empty())
1117 {
1118#if ETL_IS_DEBUG_BUILD
1121#endif
1122
1123 link_type* other_begin = other.get_head();
1124 link_type* other_terminal = &other.terminator;
1125
1126 link_type* before = &this->start;
1127 link_type* before_next = get_next(before);
1128 link_type* terminal = &this->terminator;;
1129
1130 while ((before->etl_next != terminal) && (other_begin != other_terminal))
1131 {
1132 // Find the place to insert.
1133 while ((before_next != terminal) && !(compare(*static_cast<pointer>(other_begin), *static_cast<pointer>(before_next))))
1134 {
1136 before_next = get_next(before_next);
1137 }
1138
1139 // Insert.
1140 if (before_next != terminal)
1141 {
1142 while ((other_begin != other_terminal) && (compare(*static_cast<pointer>(other_begin), *static_cast<pointer>(before_next))))
1143 {
1144 link_type* value = other_begin;
1145 other_begin = get_next(other_begin);
1147 before = get_next(before);
1148 }
1149 }
1150 }
1151
1152 // Any left over?
1153 if (before_next == terminal)
1154 {
1155 while (other_begin != other_terminal)
1156 {
1157 link_type* value = other_begin;
1158 other_begin = get_next(other_begin);
1160 before = get_next(before);
1161 }
1162 }
1163
1164 this->current_size += other.size();
1165
1166 other.initialise();
1167 }
1168 }
1169
1170 private:
1171
1172 //*************************************************************************
1174 //*************************************************************************
1175 link_type* get_next(link_type* link) const
1176 {
1177 return link->etl_next;
1178 }
1179
1180 // Disabled.
1182 intrusive_forward_list& operator = (const intrusive_forward_list& rhs);
1183 };
1184}
1185
1186#include "private/minmax_pop.h"
1187
1188#endif
const_iterator
Definition intrusive_forward_list.h:531
iterator.
Definition intrusive_forward_list.h:453
Definition intrusive_forward_list.h:140
bool is_trivial_list() const
Is the intrusive_forward_list a trivial length?
Definition intrusive_forward_list.h:282
link_type * is_link_in_list(link_type &search_link)
Definition intrusive_forward_list.h:341
link_type start
The link pointer that acts as the intrusive_forward_list start.
Definition intrusive_forward_list.h:258
void reverse()
Reverses the intrusive_forward_list.
Definition intrusive_forward_list.h:218
void insert_link_after(link_type &position, link_type &link)
Insert a link.
Definition intrusive_forward_list.h:290
~intrusive_forward_list_base()
Destructor.
Definition intrusive_forward_list.h:274
bool empty() const
Returns true if the list has no elements.
Definition intrusive_forward_list.h:243
static link_type terminator
The link that acts as the intrusive_forward_list terminator.
Definition intrusive_forward_list.h:259
size_t current_size
Counts the number of elements in the list.
Definition intrusive_forward_list.h:261
intrusive_forward_list_base()
Constructor.
Definition intrusive_forward_list.h:266
link_type * remove_link(link_type &link)
Definition intrusive_forward_list.h:369
void initialise()
Initialise the intrusive_forward_list.
Definition intrusive_forward_list.h:331
void pop_front()
Removes a value from the front of the intrusive_forward_list.
Definition intrusive_forward_list.h:207
link_type * get_head()
Get the head link.
Definition intrusive_forward_list.h:315
const link_type * get_head() const
Get the head link.
Definition intrusive_forward_list.h:323
void disconnect_link_after(link_type &link)
Remove a link.
Definition intrusive_forward_list.h:300
void assign(TIterator first, TIterator last)
Definition intrusive_forward_list.h:169
size_t size() const
Returns the number of elements.
Definition intrusive_forward_list.h:251
void push_front(link_type &value)
Pushes a value to the front of the intrusive_forward_list.
Definition intrusive_forward_list.h:197
void clear()
Clears the intrusive_forward_list.
Definition intrusive_forward_list.h:149
link_type * remove_link_range_after(link_type *p_first, link_type *p_last)
Remove a range of elements.
Definition intrusive_forward_list.h:393
Definition intrusive_forward_list.h:69
Definition intrusive_forward_list.h:55
Definition intrusive_forward_list.h:97
Definition intrusive_forward_list.h:83
Definition intrusive_forward_list.h:111
Definition intrusive_forward_list.h:125
Definition intrusive_forward_list.h:431
const_iterator before_begin() const
Gets before the beginning of the intrusive_forward_list.
Definition intrusive_forward_list.h:659
iterator erase_after(iterator first, iterator last)
Erases a range of elements.
Definition intrusive_forward_list.h:762
void sort(TCompare compare)
Definition intrusive_forward_list.h:861
const_iterator cbegin() const
Gets the beginning of the intrusive_forward_list.
Definition intrusive_forward_list.h:667
void splice_after(iterator position, etl::intrusive_forward_list< TValue, TLink > &other)
Splice another list into this one.
Definition intrusive_forward_list.h:1020
~intrusive_forward_list()
Destructor.
Definition intrusive_forward_list.h:619
void unique(TIsEqual isEqual)
Definition intrusive_forward_list.h:800
node_type * erase(node_type &node)
Erases the specified node.
Definition intrusive_forward_list.h:790
void splice_after(iterator position, etl::intrusive_forward_list< TValue, TLink > &other, iterator begin_, iterator end_)
Splice a range of elements from another list into this one.
Definition intrusive_forward_list.h:1072
void splice_after(iterator position, etl::intrusive_forward_list< TValue, TLink > &other, iterator isource)
Splice an element from another list into this one.
Definition intrusive_forward_list.h:1055
void insert_after(iterator position, TIterator first, TIterator last)
Inserts a range of values to the intrusive_forward_list after the specified position.
Definition intrusive_forward_list.h:727
intrusive_forward_list(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Constructor from range.
Definition intrusive_forward_list.h:627
void remove_if(TPredicate predicate)
Removes according to a predicate.
Definition intrusive_forward_list.h:998
iterator erase_after(iterator position)
Erases the value at the specified position.
Definition intrusive_forward_list.h:743
iterator insert_after(iterator position, value_type &value)
Inserts a value to the intrusive_forward_list after the specified position.
Definition intrusive_forward_list.h:715
const_iterator begin() const
Gets the beginning of the intrusive_forward_list.
Definition intrusive_forward_list.h:643
void merge(list_type &other, TCompare compare)
Merge another list into this one. Both lists should be sorted.
Definition intrusive_forward_list.h:1114
iterator end()
Gets the end of the intrusive_forward_list.
Definition intrusive_forward_list.h:675
iterator before_begin()
Gets before the beginning of the intrusive_forward_list.
Definition intrusive_forward_list.h:651
const_iterator end() const
Gets the end of the intrusive_forward_list.
Definition intrusive_forward_list.h:683
const_reference front() const
Gets a const reference to the first element.
Definition intrusive_forward_list.h:707
const_iterator cend() const
Gets the end of the intrusive_forward_list.
Definition intrusive_forward_list.h:691
void merge(list_type &other)
Merge another list into this one. Both lists should be sorted.
Definition intrusive_forward_list.h:1105
void sort()
Sort using in-place merge sort algorithm.
Definition intrusive_forward_list.h:830
intrusive_forward_list()
Constructor.
Definition intrusive_forward_list.h:612
iterator begin()
Gets the beginning of the intrusive_forward_list.
Definition intrusive_forward_list.h:635
reference front()
Gets a reference to the first element.
Definition intrusive_forward_list.h:699
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:968
ETL_NODISCARD ETL_CONSTEXPR14 bool is_sorted(TIterator begin, TIterator end)
Definition algorithm.h:1685
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
enable_if
Definition type_traits_generator.h:1186
is_integral
Definition type_traits_generator.h:996
bitset_ext
Definition absolute.h:38
Definition compare.h:51
iterator
Definition iterator.h:399
pair holds two objects of arbitrary type
Definition utility.h:164