Embedded Template Library 1.0
Loading...
Searching...
No Matches
intrusive_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_LIST_INCLUDED
32#define ETL_INTRUSIVE_LIST_INCLUDED
33
34#include "platform.h"
35#include "nullptr.h"
36#include "type_traits.h"
37#include "exception.h"
38#include "error_handler.h"
39#include "intrusive_links.h"
40#include "static_assert.h"
41#include "algorithm.h"
42#include "iterator.h"
43#include "functional.h"
44
45#include <stddef.h>
46
47#include "private/minmax_push.h"
48
49namespace etl
50{
51 //***************************************************************************
54 //***************************************************************************
64
65 //***************************************************************************
68 //***************************************************************************
70 {
71 public:
72
74 : intrusive_list_exception(ETL_ERROR_TEXT("intrusive_list:empty", ETL_INTRUSIVE_LIST_FILE_ID"A"), file_name_, line_number_)
75 {
76 }
77 };
78
79 //***************************************************************************
82 //***************************************************************************
84 {
85 public:
86
88 : intrusive_list_exception(ETL_ERROR_TEXT("intrusive_list:iterator", ETL_INTRUSIVE_LIST_FILE_ID"B"), file_name_, line_number_)
89 {
90 }
91 };
92
93 //***************************************************************************
96 //***************************************************************************
98 {
99 public:
100
102 : intrusive_list_exception(ETL_ERROR_TEXT("intrusive_list:unsorted", ETL_INTRUSIVE_LIST_FILE_ID"C"), file_name_, line_number_)
103 {
104 }
105 };
106
107 //***************************************************************************
110 //***************************************************************************
112 {
113 public:
114
116 : intrusive_list_exception(ETL_ERROR_TEXT("intrusive_list:value is already linked", ETL_INTRUSIVE_LIST_FILE_ID"E"), file_name_, line_number_)
117 {
118 }
119 };
120
121 //***************************************************************************
124 //***************************************************************************
125 template <typename TLink>
127 {
128 public:
129
130 // Node typedef.
131 typedef TLink link_type;
132
133 //*************************************************************************
137 //*************************************************************************
138 template <typename TIterator>
139 void assign(TIterator first, TIterator last)
140 {
141#if ETL_IS_DEBUG_BUILD
142 intmax_t d = etl::distance(first, last);
144#endif
145
146 initialise();
147
149
150 // Add all of the elements.
151 while (first != last)
152 {
153 link_type& link = *first++;
155 p_last_link = &link;
156 ++current_size;
157 }
158 }
159
160 //*************************************************************************
162 //*************************************************************************
164 {
165 ETL_ASSERT_OR_RETURN(!value.is_linked(), ETL_ERROR(intrusive_list_value_is_already_linked));
166
168 }
169
170 //*************************************************************************
172 //*************************************************************************
174 {
175#if defined(ETL_CHECK_PUSH_POP)
176 ETL_ASSERT(!empty(), ETL_ERROR(intrusive_list_empty));
177#endif
179 }
180
181 //*************************************************************************
183 //*************************************************************************
184 void push_back(link_type& value)
185 {
186 ETL_ASSERT_OR_RETURN(!value.is_linked(), ETL_ERROR(intrusive_list_value_is_already_linked));
187
188 insert_link(terminal_link.link_type::etl_previous, value);
189 }
190
191 //*************************************************************************
193 //*************************************************************************
194 void pop_back()
195 {
196#if defined(ETL_CHECK_PUSH_POP)
197 ETL_ASSERT(!empty(), ETL_ERROR(intrusive_list_empty));
198#endif
200 }
201
202 //*************************************************************************
204 //*************************************************************************
205 void clear()
206 {
207 // Unlink all of the items.
208 link_type* p_unlink = terminal_link.etl_next;
209
210 while (p_unlink != &terminal_link)
211 {
212 link_type* p_next = p_unlink->etl_next;
213 p_unlink->clear();
214 p_unlink = p_next;
215 }
216
217 initialise();
218 }
219
220 //*************************************************************************
222 //*************************************************************************
223 void reverse()
224 {
225 if (is_trivial_list())
226 {
227 return;
228 }
229
230 link_type* pnode = terminal_link.etl_next;
231
232 while (pnode != &terminal_link)
233 {
234 pnode->reverse();
235 pnode = pnode->etl_previous; // Now we've reversed it, we must go to the previous node.
236 }
237
238 // Terminal node.
239 pnode->reverse();
240 }
241
242 //*************************************************************************
244 //*************************************************************************
245 bool empty() const
246 {
247 return (terminal_link.link_type::etl_next == &terminal_link);
248 }
249
250 //*************************************************************************
252 //*************************************************************************
253 size_t size() const
254 {
255 return current_size;
256 }
257
258 protected:
259
262
264
265 //*************************************************************************
267 //*************************************************************************
269 {
270 }
271
272 //*************************************************************************
274 //*************************************************************************
275 bool is_trivial_list() const
276 {
277 return (terminal_link.link_type::etl_next == &terminal_link) || (terminal_link.link_type::etl_next->etl_next == &terminal_link);
278 }
279
280 //*************************************************************************
282 //*************************************************************************
284 {
285 // Connect to the intrusive_list.
287 ++current_size;
288 }
289
290 //*************************************************************************
292 //*************************************************************************
294 {
295 // Connect to the intrusive_list.
297 ++current_size;
298 }
299
300 //*************************************************************************
302 //*************************************************************************
304 {
305 // Connect to the intrusive_list.
307 ++current_size;
308 }
309
310 //*************************************************************************
312 //*************************************************************************
314 {
315 // Connect to the intrusive_list.
317 ++current_size;
318 }
319
320 //*************************************************************************
322 //*************************************************************************
324 {
326 --current_size;
327 }
328
329 //*************************************************************************
331 //*************************************************************************
333 {
335 --current_size;
336 }
337
338 //*************************************************************************
340 //*************************************************************************
342 {
343 return terminal_link.etl_next;
344 }
345
346 //*************************************************************************
348 //*************************************************************************
349 const link_type* get_head() const
350 {
351 return terminal_link.etl_next;
352 }
353
354 //*************************************************************************
356 //*************************************************************************
358 {
359 return terminal_link.etl_previous;
360 }
361
362 //*************************************************************************
364 //*************************************************************************
365 const link_type* get_tail() const
366 {
367 return terminal_link.etl_previous;
368 }
369
370 //*************************************************************************
372 //*************************************************************************
374 {
375 etl::link(terminal_link, terminal_link);
376 current_size = 0;
377 }
378
379 //*************************************************************************
381 //*************************************************************************
383 {
384 link_type* p_link = terminal_link.link_type::etl_next;
385
386 while (p_link != &terminal_link)
387 {
388 if (&search_link == p_link)
389 {
390 return true;
391 }
392
393 p_link = p_link->link_type::etl_next;
394 }
395
396 return false;
397 }
398
399 //*************************************************************************
402 //*************************************************************************
404 {
405 link_type* result = ETL_NULLPTR;
406
407 if (is_link_in_list(link))
408 {
409 link_type* p_next = link.etl_next;
410
411 disconnect_link(link);
412
413 if (p_next != &terminal_link)
414 {
415 result = p_next;
416 }
417 }
418
419 return result;
420 }
421
422 //*************************************************************************
424 //*************************************************************************
426 {
427 // Join the ends.
428 etl::link<link_type>(p_first->etl_previous, p_last);
429
430 while (p_first != p_last)
431 {
432 link_type* p_next = p_first->etl_next;
433 p_first->clear();
434 p_first = p_next;
435 }
436
437 if (p_last == &terminal_link)
438 {
439 return ETL_NULLPTR;
440 }
441 else
442 {
443 return p_last;
444 }
445 }
446 };
447
448 //***************************************************************************
452 //***************************************************************************
453 template <typename TValue, typename TLink>
455 {
456 public:
457
458 // Node typedef.
459 typedef typename etl::intrusive_list_base<TLink>::link_type link_type;
460
462
463 typedef TValue node_type;
464
465 // STL style typedefs.
466 typedef TValue value_type;
467 typedef value_type* pointer;
468 typedef const value_type* const_pointer;
469 typedef value_type& reference;
470 typedef const value_type& const_reference;
471 typedef size_t size_type;
472
473 //*************************************************************************
475 //*************************************************************************
476 class iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, value_type>
477 {
478 public:
479
480 friend class intrusive_list;
481 friend class const_iterator;
482
483 iterator()
484 : p_value(ETL_NULLPTR)
485 {
486 }
487
488 iterator(const iterator& other)
489 : p_value(other.p_value)
490 {
491 }
492
494 {
495 // Read the appropriate 'etl_next'.
496 p_value = p_value->etl_next;
497 return *this;
498 }
499
501 {
502 iterator temp(*this);
503 // Read the appropriate 'etl_next'.
504 p_value = p_value->etl_next;
505 return temp;
506 }
507
509 {
510 // Read the appropriate 'etl_previous'.
511 p_value = p_value->etl_previous;
512 return *this;
513 }
514
516 {
517 iterator temp(*this);
518 // Read the appropriate 'etl_previous'.
519 p_value = p_value->etl_previous;
520 return temp;
521 }
522
524 {
525 p_value = other.p_value;
526 return *this;
527 }
528
529 reference operator *() const
530 {
532 return *static_cast<pointer>(p_value);
534 }
535
536 pointer operator &() const
537 {
538 return static_cast<pointer>(p_value);
539 }
540
541 pointer operator ->() const
542 {
543 return static_cast<pointer>(p_value);
544 }
545
546 friend bool operator == (const iterator& lhs, const iterator& rhs)
547 {
548 return lhs.p_value == rhs.p_value;
549 }
550
551 friend bool operator != (const iterator& lhs, const iterator& rhs)
552 {
553 return !(lhs == rhs);
554 }
555
556 private:
557
558 iterator(link_type* value)
559 : p_value(value)
560 {
561 }
562
563 link_type* p_value;
564 };
565
566 //*************************************************************************
568 //*************************************************************************
569 class const_iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, const value_type>
570 {
571 public:
572
573 friend class intrusive_list;
574
576 : p_value(ETL_NULLPTR)
577 {
578 }
579
581 : p_value(other.p_value)
582 {
583 }
584
586 : p_value(other.p_value)
587 {
588 }
589
591 {
592 // Read the appropriate 'etl_next'.
593 p_value = p_value->etl_next;
594 return *this;
595 }
596
598 {
599 const_iterator temp(*this);
600 // Read the appropriate 'etl_next'.
601 p_value = p_value->etl_next;
602 return temp;
603 }
604
606 {
607 // Read the appropriate 'etl_previous'.
608 p_value = p_value->etl_previous;
609 return *this;
610 }
611
613 {
614 const_iterator temp(*this);
615 // Read the appropriate 'etl_previous'.
616 p_value = p_value->etl_previous;
617 return temp;
618 }
619
621 {
622 p_value = other.p_value;
623 return *this;
624 }
625
627 {
628 return *static_cast<const_pointer>(p_value);
629 }
630
632 {
633 return static_cast<const_pointer>(p_value);
634 }
635
637 {
638 return static_cast<const_pointer>(p_value);
639 }
640
641 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
642 {
643 return lhs.p_value == rhs.p_value;
644 }
645
646 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
647 {
648 return !(lhs == rhs);
649 }
650
651 private:
652
653 const_iterator(const link_type* value)
654 : p_value(value)
655 {
656 }
657
658 const link_type* p_value;
659 };
660
661 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
662
663 //*************************************************************************
665 //*************************************************************************
667 {
668 this->initialise();
669 }
670
671 //*************************************************************************
673 //*************************************************************************
675 {
676 this->clear();
677 }
678
679 //*************************************************************************
681 //*************************************************************************
682 template <typename TIterator>
684 {
685 this->assign(first, last);
686 }
687
688 //*************************************************************************
690 //*************************************************************************
692 {
693 return iterator(this->get_head());
694 }
695
696 //*************************************************************************
698 //*************************************************************************
700 {
701 return const_iterator(this->get_head());
702 }
703
704 //*************************************************************************
706 //*************************************************************************
708 {
709 return const_iterator(this->get_head());
710 }
711
712 //*************************************************************************
714 //*************************************************************************
716 {
717 return iterator(&this->terminal_link);
718 }
719
720 //*************************************************************************
722 //*************************************************************************
724 {
725 return const_iterator(&this->terminal_link);
726 }
727
728 //*************************************************************************
730 //*************************************************************************
732 {
733 return const_iterator(&this->terminal_link);
734 }
735
736 //*************************************************************************
738 //*************************************************************************
739 reference front()
740 {
741 return *static_cast<pointer>(this->get_head());
742 }
743
744 //*************************************************************************
746 //*************************************************************************
747 const_reference front() const
748 {
749 return *static_cast<const_pointer>(this->get_head());
750 }
751
752 //*************************************************************************
754 //*************************************************************************
755 reference back()
756 {
757 return *static_cast<pointer>(this->get_tail());
758 }
759
760 //*************************************************************************
762 //*************************************************************************
763 const_reference back() const
764 {
765 return *static_cast<const_pointer>(this->get_tail());
766 }
767
768 //*************************************************************************
770 //*************************************************************************
772 {
773 this->insert_link(position.p_value->link_type::etl_previous, value);
774 return iterator(&value);
775 }
776
777 //*************************************************************************
779 //*************************************************************************
780 template <typename TIterator>
781 void insert(const_iterator position, TIterator first, TIterator last)
782 {
783 while (first != last)
784 {
785 // Set up the next free link.
786 this->insert_link(*position.p_value->link_type::etl_previous, *first);
787 ++first;
788 }
789 }
790
791 //*************************************************************************
793 //*************************************************************************
795 {
796 iterator next(position);
797 ++next;
798
799 this->disconnect_link(*position.p_value);
800
801 return next;
802 }
803
804 //*************************************************************************
806 //*************************************************************************
808 {
809 iterator next(position);
810 ++next;
811
812 this->disconnect_link(*position.p_value);
813
814 return next;
815 }
816
817 //*************************************************************************
820 //*************************************************************************
822 {
823 const link_type* cp_first = first.p_value;
824 const link_type* cp_last = last.p_value;
825
826 link_type* p_first = const_cast<link_type*>(cp_first);
827 link_type* p_last = const_cast<link_type*>(cp_last);
828
829 this->current_size -= etl::distance(first, last);
830
831 p_last = this->remove_link_range(p_first, p_last);
832
833 if (p_last == ETL_NULLPTR)
834 {
835 return end();
836 }
837 else
838 {
839 return iterator(static_cast<pointer>(p_last));
840 }
841 }
842
843 //*************************************************************************
845 //*************************************************************************
847 {
848 return static_cast<node_type*>(this->remove_link(node));
849 }
850
851 //*************************************************************************
854 //*************************************************************************
855 template <typename TIsEqual>
857 {
858 if (this->empty())
859 {
860 return;
861 }
862
864 ++i_item;
866
867 while (i_item != end())
868 {
869 if (isEqual(*i_previous, *i_item))
870 {
872 }
873 else
874 {
876 ++i_item;
877 }
878 }
879 }
880
881 //*************************************************************************
883 //*************************************************************************
884 void sort()
885 {
887 }
888
889 //*************************************************************************
913 //*************************************************************************
914 template <typename TCompare>
916 {
922 int list_size = 1;
924 int left_size;
925 int right_size;
926
927 if (this->is_trivial_list())
928 {
929 return;
930 }
931
932 while (true)
933 {
934 i_left = begin();
935 i_head = end();
936 i_tail = end();
937
938 number_of_merges = 0; // Count the number of merges we do in this pass.
939
940 while (i_left != end())
941 {
942 ++number_of_merges; // There exists a merge to be done.
943 i_right = i_left;
944 left_size = 0;
945
946 // Step 'list_size' places along from left
947 for (int i = 0; i < list_size; ++i)
948 {
949 ++left_size;
950 ++i_right;
951
952 if (i_right == end())
953 {
954 break;
955 }
956 }
957
958 // If right hasn't fallen off end, we have two lists to merge.
960
961 // Now we have two lists. Merge them.
962 while (left_size > 0 || (right_size > 0 && i_right != end()))
963 {
964 // Decide whether the next node of merge comes from left or right.
965 if (left_size == 0)
966 {
967 // Left is empty. The node must come from right.
968 i_node = i_right++;
969 --right_size;
970 }
971 else if (right_size == 0 || i_right == end())
972 {
973 // Right is empty. The node must come from left.
974 i_node = i_left++;
975 --left_size;
976 }
977 else if (!compare(*i_right, *i_left))
978 {
979 // First node of left is lower or same. The node must come from left.
980 i_node = i_left++;
981 --left_size;
982 }
983 else
984 {
985 // First node of right is lower. The node must come from right.
986 i_node = i_right;
987 ++i_right;
988 --right_size;
989 }
990
991 // Add the next node to the merged head.
992 if (i_head == end())
993 {
994 etl::link<link_type>(i_head.p_value, i_node.p_value);
995 i_head = i_node;
996 i_tail = i_node;
997 }
998 else
999 {
1000 etl::link<link_type>(i_tail.p_value, i_node.p_value);
1001 i_tail = i_node;
1002 }
1003
1004 etl::link<link_type>(i_tail.p_value, this->terminal_link);
1005 }
1006
1007 // Now left has stepped `list_size' places along, and right has too.
1008 i_left = i_right;
1009 }
1010
1011 // If we have done only one merge, we're finished.
1012 if (number_of_merges <= 1) // Allow for number_of_merges == 0, the empty head case
1013 {
1014 return;
1015 }
1016
1017 // Otherwise repeat, merging lists twice the size
1018 list_size *= 2;
1019 }
1020 }
1021
1022 //*************************************************************************
1023 // Removes the values specified.
1024 //*************************************************************************
1025 void remove(const_reference value)
1026 {
1027 iterator i_item = begin();
1028
1029 while (i_item != end())
1030 {
1031 if (*i_item == value)
1032 {
1033 i_item = erase(i_item);
1034 }
1035 else
1036 {
1037 ++i_item;
1038 }
1039 }
1040 }
1041
1042 //*************************************************************************
1044 //*************************************************************************
1045 template <typename TPredicate>
1047 {
1048 iterator i_item = begin();
1049
1050 while (i_item != end())
1051 {
1052 if (predicate(*i_item))
1053 {
1054 i_item = erase(i_item);
1055 }
1056 else
1057 {
1058 ++i_item;
1059 }
1060 }
1061 }
1062
1063 //*************************************************************************
1065 //*************************************************************************
1067 {
1068 // No point splicing to ourself!
1069 if (&other != this)
1070 {
1071 if (!other.empty())
1072 {
1073 link_type& first = *other.get_head();
1074 link_type& last = *other.get_tail();
1075
1076 if (&other != this)
1077 {
1078 this->current_size += other.size();
1079 }
1080
1081 link_type& after = *position.p_value;
1082 link_type& before = *after.etl_previous;
1083
1086
1087 other.initialise();
1088 }
1089 }
1090 }
1091
1092 //*************************************************************************
1094 //*************************************************************************
1096 {
1097 link_type& before = *position.p_value->link_type::etl_previous;
1098
1101
1102 if (&other != this)
1103 {
1104 ++this->current_size;
1105 --other.current_size;
1106 }
1107 }
1108
1109 //*************************************************************************
1111 //*************************************************************************
1113 {
1114 if (!other.empty())
1115 {
1116 if (&other != this)
1117 {
1118 size_t n = etl::distance(begin_, end_);
1119 this->current_size += n;
1120 other.current_size -= n;
1121 }
1122
1123 link_type& first = *begin_.p_value;
1124 link_type& last = *end_.p_value->link_type::etl_previous;
1125
1126 // Unlink from the source list.
1127 etl::unlink(first, last);
1128
1129 // Fix our links.
1130 link_type& before = *position.p_value->link_type::etl_previous;
1131
1132 etl::link_splice<link_type>(before, first, last);
1133 }
1134 }
1135
1136 //*************************************************************************
1138 //*************************************************************************
1140 {
1142 }
1143
1144 //*************************************************************************
1146 //*************************************************************************
1147 template <typename TCompare>
1149 {
1150 if ((this != &other) && !other.empty())
1151 {
1152#if ETL_IS_DEBUG_BUILD
1155#endif
1156
1157 link_type* other_begin = other.get_head();
1158 link_type* other_end = &other.terminal_link;
1159
1160 link_type* this_begin = this->get_head();
1161 link_type* this_end = &this->terminal_link;
1162
1163 while ((this_begin != this_end) && (other_begin != other_end))
1164 {
1165 // Find the place to insert.
1166 while ((this_begin != this_end) && !(compare(*static_cast<pointer>(other_begin), *static_cast<pointer>(this_begin))))
1167 {
1168 this_begin = this_begin->etl_next;
1169 }
1170
1171 // Insert.
1172 if (this_begin != this_end)
1173 {
1174 while ((other_begin != other_end) && (compare(*static_cast<pointer>(other_begin), *static_cast<pointer>(this_begin))))
1175 {
1176 link_type* value = other_begin;
1177 other_begin = other_begin->etl_next;
1178 etl::link_splice<link_type>(*this_begin->etl_previous, *value);
1179 }
1180 }
1181 }
1182
1183 // Any left over?
1184 if ((this_begin == this_end) && (other_begin != other_end))
1185 {
1186 etl::link_splice<link_type>(*this->get_tail(), *other_begin, *other_end->etl_previous);
1187 }
1188
1189 this->current_size += other.size();
1190
1191 other.initialise();
1192 }
1193 }
1194
1195 private:
1196
1197 // Disabled.
1200 };
1201}
1202
1203#include "private/minmax_pop.h"
1204
1205#endif
const_iterator
Definition intrusive_list.h:570
iterator.
Definition intrusive_list.h:477
Definition intrusive_list.h:127
void disconnect_link(link_type *link)
Remove a link.
Definition intrusive_list.h:332
link_type * remove_link(link_type &link)
Definition intrusive_list.h:403
size_t size() const
Returns the number of elements.
Definition intrusive_list.h:253
link_type * get_tail()
Get the tail link.
Definition intrusive_list.h:357
void insert_link(link_type &previous, link_type &new_link)
Insert a link.
Definition intrusive_list.h:283
~intrusive_list_base()
Destructor.
Definition intrusive_list.h:268
void assign(TIterator first, TIterator last)
Definition intrusive_list.h:139
bool is_link_in_list(link_type &search_link) const
Tests if the link is in this list.
Definition intrusive_list.h:382
size_t current_size
Counts the number of elements in the list.
Definition intrusive_list.h:263
void disconnect_link(link_type &link)
Remove a link.
Definition intrusive_list.h:323
void insert_link(link_type &previous, link_type *new_link)
Insert a link.
Definition intrusive_list.h:303
void pop_back()
Removes a value from the back of the intrusive_list.
Definition intrusive_list.h:194
link_type * get_head()
Get the head link.
Definition intrusive_list.h:341
bool empty() const
Returns true if the list has no elements.
Definition intrusive_list.h:245
link_type * remove_link_range(link_type *p_first, link_type *p_last)
Removes a range of links.
Definition intrusive_list.h:425
void initialise()
Initialise the intrusive_list.
Definition intrusive_list.h:373
void reverse()
Reverses the list.
Definition intrusive_list.h:223
void insert_link(link_type *previous, link_type *new_link)
Insert a link.
Definition intrusive_list.h:313
const link_type * get_head() const
Get the head link.
Definition intrusive_list.h:349
link_type terminal_link
The link that acts as the intrusive_list start & end.
Definition intrusive_list.h:261
void insert_link(link_type *previous, link_type &new_link)
Insert a link.
Definition intrusive_list.h:293
void clear()
Clears the intrusive_list.
Definition intrusive_list.h:205
void push_front(link_type &value)
Pushes a value to the front of the intrusive_list.
Definition intrusive_list.h:163
void push_back(link_type &value)
Pushes a value to the back of the intrusive_list.
Definition intrusive_list.h:184
void pop_front()
Removes a value from the front of the intrusive_list.
Definition intrusive_list.h:173
const link_type * get_tail() const
Get the tail link.
Definition intrusive_list.h:365
bool is_trivial_list() const
Is the intrusive_list a trivial length?
Definition intrusive_list.h:275
Definition intrusive_list.h:70
Definition intrusive_list.h:56
Definition intrusive_list.h:84
Definition intrusive_list.h:98
Definition intrusive_list.h:112
Definition intrusive_list.h:455
~intrusive_list()
Destructor.
Definition intrusive_list.h:674
node_type * erase(node_type &node)
Erases the specified node.
Definition intrusive_list.h:846
const_iterator end() const
Gets the end of the intrusive_list.
Definition intrusive_list.h:723
reference back()
Gets a reference to the last element.
Definition intrusive_list.h:755
iterator begin()
Gets the beginning of the intrusive_list.
Definition intrusive_list.h:691
void unique(TIsEqual isEqual)
Definition intrusive_list.h:856
const_iterator begin() const
Gets the beginning of the intrusive_list.
Definition intrusive_list.h:699
void splice(iterator position, list_type &other)
Splice another list into this one.
Definition intrusive_list.h:1066
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition intrusive_list.h:807
void splice(iterator position, list_type &other, iterator begin_, iterator end_)
Splice a range of elements from another list into this one.
Definition intrusive_list.h:1112
reference front()
Gets a reference to the first element.
Definition intrusive_list.h:739
void insert(const_iterator position, TIterator first, TIterator last)
Inserts a range of values to the intrusive_list after the specified position.
Definition intrusive_list.h:781
void merge(list_type &other, TCompare compare)
Merge another list into this one. Both lists should be sorted.
Definition intrusive_list.h:1148
void sort(TCompare compare)
Definition intrusive_list.h:915
void splice(iterator position, list_type &other, iterator isource)
Splice an element from another list into this one.
Definition intrusive_list.h:1095
intrusive_list()
Constructor.
Definition intrusive_list.h:666
iterator erase(const_iterator first, const_iterator last)
Definition intrusive_list.h:821
const_iterator cend() const
Gets the end of the intrusive_list.
Definition intrusive_list.h:731
iterator erase(iterator position)
Erases the value at the specified position.
Definition intrusive_list.h:794
const_iterator cbegin() const
Gets the beginning of the intrusive_list.
Definition intrusive_list.h:707
void remove_if(TPredicate predicate)
Removes according to a predicate.
Definition intrusive_list.h:1046
void sort()
Sort using in-place merge sort algorithm.
Definition intrusive_list.h:884
iterator insert(const_iterator position, value_type &value)
Inserts a value to the intrusive_list before the specified position.
Definition intrusive_list.h:771
const_reference front() const
Gets a const reference to the first element.
Definition intrusive_list.h:747
iterator end()
Gets the end of the intrusive_list.
Definition intrusive_list.h:715
intrusive_list(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Constructor from range.
Definition intrusive_list.h:683
const_reference back() const
Gets a const reference to the last element.
Definition intrusive_list.h:763
void merge(list_type &other)
Merge another list into this one. Both lists should be sorted.
Definition intrusive_list.h:1139
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:966
ETL_NODISCARD ETL_CONSTEXPR14 bool is_sorted(TIterator begin, TIterator end)
Definition algorithm.h:1673
#define ETL_ASSERT(b, e)
Definition error_handler.h:316
Definition exception.h:47
enable_if
Definition type_traits_generator.h:1191
is_integral
Definition type_traits_generator.h:1001
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