Embedded Template Library 1.0
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 //***************************************************************************
55 {
56 public:
57
58 intrusive_forward_list_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
59 : exception(reason_, file_name_, line_number_)
60 {
61 }
62 };
63
64 //***************************************************************************
67 //***************************************************************************
69 {
70 public:
71
72 intrusive_forward_list_empty(string_type file_name_, numeric_type line_number_)
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
86 intrusive_forward_list_iterator_exception(string_type file_name_, numeric_type line_number_)
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
100 intrusive_forward_list_index_exception(string_type file_name_, numeric_type line_number_)
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
114 intrusive_forward_list_unsorted(string_type file_name_, numeric_type line_number_)
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
128 intrusive_forward_list_value_is_already_linked(string_type file_name_, numeric_type line_number_)
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 int count = 0;
181
182 // Add all of the elements.
183 while (first != last)
184 {
185 ++count;
186
187 link_type& value = *first++;
188
189 ETL_ASSERT_OR_RETURN(!value.is_linked(), ETL_ERROR(intrusive_forward_list_value_is_already_linked));
190
191 value.etl_next = p_last->etl_next;
192 p_last->etl_next = &value;
193 p_last = &value;
194 ++current_size;
195 }
196 }
197
198 //*************************************************************************
200 //*************************************************************************
201 void push_front(link_type& value)
202 {
203 ETL_ASSERT_OR_RETURN(!value.is_linked(), ETL_ERROR(intrusive_forward_list_value_is_already_linked));
204
205 insert_link_after(start, value);
206 }
207
208 //*************************************************************************
210 //*************************************************************************
212 {
213#if defined(ETL_CHECK_PUSH_POP)
214 ETL_ASSERT_OR_RETURN(!empty(), ETL_ERROR(intrusive_forward_list_empty));
215#endif
217 }
218
219 //*************************************************************************
221 //*************************************************************************
222 void reverse()
223 {
224 if (is_trivial_list())
225 {
226 return;
227 }
228
229 link_type* previous = &terminator; // Point to the terminator of the linked list.
230 link_type* current = start.etl_next; // Point to the first item in the linked list (could be the terminator).
231 link_type* next = start.etl_next; // Point to the first item in the linked list (could be the terminator).
232
233 while (next != &terminator)
234 {
235 next = next->etl_next; // Point to next link.
236 current->etl_next = previous; // Reverse the current link.
237 previous = current; // Previous points to current.
238 current = next; // Current points to next.
239 }
240
241 etl::link<link_type>(start, previous);
242 }
243
244 //*************************************************************************
246 //*************************************************************************
247 bool empty() const
248 {
249 return (current_size == 0);
250 }
251
252 //*************************************************************************
254 //*************************************************************************
255 size_t size() const
256 {
257 return current_size;
258 }
259
260 protected:
261
262 link_type start;
263 static link_type terminator;
264
266
267 //*************************************************************************
269 //*************************************************************************
271 {
272 initialise();
273 }
274
275 //*************************************************************************
277 //*************************************************************************
279 {
280 clear();
281 }
282
283 //*************************************************************************
285 //*************************************************************************
286 bool is_trivial_list() const
287 {
288 return (size() <= 1U);
289 }
290
291 //*************************************************************************
293 //*************************************************************************
294 void insert_link_after(link_type& position, link_type& link)
295 {
296 // Connect to the intrusive_forward_list.
297 etl::link_splice<link_type>(position, link);
298 ++current_size;
299 }
300
301 //*************************************************************************
303 //*************************************************************************
304 void remove_link_after(link_type& link)
305 {
306 link_type* p_next = link.etl_next;
307
308 if (p_next != &this->terminator)
309 {
310 link_type* p_unlinked = etl::unlink_after<link_type>(link);
311 p_unlinked->clear();
312 --current_size;
313 }
314 }
315
316 //*************************************************************************
318 //*************************************************************************
319 link_type* get_head()
320 {
321 return start.etl_next;
322 }
323
324 //*************************************************************************
326 //*************************************************************************
327 const link_type* get_head() const
328 {
329 return start.etl_next;
330 }
331
332 //*************************************************************************
334 //*************************************************************************
336 {
337 start.etl_next = &terminator;
338 current_size = 0;
339 }
340 };
341
342 template <typename TLink>
344
345 //***************************************************************************
349 //***************************************************************************
350 template <typename TValue, typename TLink>
352 {
353 public:
354
355 // Node typedef.
356 typedef typename etl::intrusive_forward_list_base<TLink>::link_type link_type;
357
358 // STL style typedefs.
359 typedef TValue value_type;
360 typedef value_type* pointer;
361 typedef const value_type* const_pointer;
362 typedef value_type& reference;
363 typedef const value_type& const_reference;
364 typedef size_t size_type;
365
367
368 //*************************************************************************
370 //*************************************************************************
371 class iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, value_type>
372 {
373 public:
374
375 friend class intrusive_forward_list;
376 friend class const_iterator;
377
378 iterator()
379 : p_value(ETL_NULLPTR)
380 {
381 }
382
383 iterator(const iterator& other)
384 : p_value(other.p_value)
385 {
386 }
387
388 iterator& operator ++()
389 {
390 // Read the appropriate 'etl_next'.
391 p_value = p_value->etl_next;
392 return *this;
393 }
394
395 iterator operator ++(int)
396 {
397 iterator temp(*this);
398 // Read the appropriate 'etl_next'.
399 p_value = p_value->etl_next;
400 return temp;
401 }
402
403 iterator& operator =(const iterator& other)
404 {
405 p_value = other.p_value;
406 return *this;
407 }
408
409 reference operator *() const
410 {
411 return *static_cast<pointer>(p_value);
412 }
413
414 pointer operator &() const
415 {
416 return static_cast<pointer>(p_value);
417 }
418
419 pointer operator ->() const
420 {
421 return static_cast<pointer>(p_value);
422 }
423
424 friend bool operator == (const iterator& lhs, const iterator& rhs)
425 {
426 return lhs.p_value == rhs.p_value;
427 }
428
429 friend bool operator != (const iterator& lhs, const iterator& rhs)
430 {
431 return !(lhs == rhs);
432 }
433
434 private:
435
436 iterator(link_type* value)
437 : p_value(value)
438 {
439 }
440
441 link_type* p_value;
442 };
443
444 //*************************************************************************
446 //*************************************************************************
447 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const value_type>
448 {
449 public:
450
451 friend class intrusive_forward_list;
452
454 : p_value(ETL_NULLPTR)
455 {
456 }
457
459 : p_value(other.p_value)
460 {
461 }
462
463 const_iterator(const const_iterator& other)
464 : p_value(other.p_value)
465 {
466 }
467
468 const_iterator& operator ++()
469 {
470 // Read the appropriate 'etl_next'.
471 p_value = p_value->etl_next;
472 return *this;
473 }
474
475 const_iterator operator ++(int)
476 {
477 const_iterator temp(*this);
478 // Read the appropriate 'etl_next'.
479 p_value = p_value->etl_next;
480 return temp;
481 }
482
483 const_iterator& operator =(const const_iterator& other)
484 {
485 p_value = other.p_value;
486 return *this;
487 }
488
489 const_reference operator *() const
490 {
491 return *static_cast<const value_type*>(p_value);
492 }
493
494 const_pointer operator &() const
495 {
496 return static_cast<const value_type*>(p_value);
497 }
498
499 const_pointer operator ->() const
500 {
501 return static_cast<const value_type*>(p_value);
502 }
503
504 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
505 {
506 return lhs.p_value == rhs.p_value;
507 }
508
509 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
510 {
511 return !(lhs == rhs);
512 }
513
514 private:
515
516 const_iterator(const link_type* value)
517 : p_value(value)
518 {
519 }
520
521 const link_type* p_value;
522 };
523
524 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
525
526 //*************************************************************************
528 //*************************************************************************
530 {
531 }
532
533 //*************************************************************************
535 //*************************************************************************
537 {
538 }
539
540 //*************************************************************************
542 //*************************************************************************
543 template <typename TIterator>
544 intrusive_forward_list(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral<TIterator>::value, int>::type = 0)
545 {
546 this->assign(first, last);
547 }
548
549 //*************************************************************************
551 //*************************************************************************
553 {
554 return iterator(this->get_head());
555 }
556
557 //*************************************************************************
559 //*************************************************************************
561 {
562 return const_iterator(this->get_head());
563 }
564
565 //*************************************************************************
567 //*************************************************************************
569 {
570 return iterator(&this->start);
571 }
572
573 //*************************************************************************
575 //*************************************************************************
577 {
578 return const_iterator(&this->start);
579 }
580
581 //*************************************************************************
583 //*************************************************************************
585 {
586 return const_iterator(this->get_head());
587 }
588
589 //*************************************************************************
591 //*************************************************************************
593 {
594 return iterator(&this->terminator);
595 }
596
597 //*************************************************************************
599 //*************************************************************************
601 {
602 return const_iterator(&this->terminator);
603 }
604
605 //*************************************************************************
607 //*************************************************************************
609 {
610 return const_iterator(&this->terminator);
611 }
612
613 //*************************************************************************
615 //*************************************************************************
616 reference front()
617 {
618 return *static_cast<pointer>(this->get_head());
619 }
620
621 //*************************************************************************
623 //*************************************************************************
624 const_reference front() const
625 {
626 return *static_cast<const value_type*>(this->get_head());
627 }
628
629 //*************************************************************************
631 //*************************************************************************
632 iterator insert_after(iterator position, value_type& value)
633 {
634 ETL_ASSERT_OR_RETURN_VALUE(!value.link_type::is_linked(), ETL_ERROR(intrusive_forward_list_value_is_already_linked), iterator(&value));
635
636 this->insert_link_after(*position.p_value, value);
637 return iterator(&value);
638 }
639
640 //*************************************************************************
642 //*************************************************************************
643 template <typename TIterator>
644 void insert_after(iterator position, TIterator first, TIterator last)
645 {
646 while (first != last)
647 {
648 // Set up the next free link.
649 ETL_ASSERT_OR_RETURN(!(*first).link_type::is_linked(), ETL_ERROR(intrusive_forward_list_value_is_already_linked));
650
651 this->insert_link_after(*position.p_value, *first);
652 ++first;
653 ++position;
654 }
655 }
656
657 //*************************************************************************
659 //*************************************************************************
661 {
662 iterator next(position);
663 if (next != end())
664 {
665 ++next;
666 if (next != end())
667 {
668 ++next;
669 this->remove_link_after(*position.p_value);
670 }
671 }
672
673 return next;
674 }
675
676 //*************************************************************************
678 //*************************************************************************
680 {
681 if (first != end() && (first != last))
682 {
683 this->current_size -= etl::distance(first, last) - 1;
684
685 link_type* p_first = first.p_value;
686 link_type* p_last = last.p_value;
687 link_type* p_after = p_first->etl_next;
688
689 // Join the ends.
690 etl::link<link_type>(p_first, p_last);
691
692 // Unlink the erased range.
693 link_type* p_unlink = p_after;
694
695 while (p_unlink != p_last)
696 {
697 link_type* p_next = p_unlink->etl_next;
698 p_unlink->clear();
699 p_unlink = p_next;
700 }
701
702 if (p_after == &this->terminator)
703 {
704 return end();
705 }
706 else
707 {
708 return last;
709 }
710 }
711 else
712 {
713 return last;
714 }
715 }
716
717 //*************************************************************************
720 //*************************************************************************
721 template <typename TIsEqual>
722 void unique(TIsEqual isEqual)
723 {
724 if (this->empty())
725 {
726 return;
727 }
728
729 link_type* last = this->get_head();
730 link_type* current = last->etl_next;
731
732 while (current != &this->terminator)
733 {
734 // Is this value the same as the last?
735 if (isEqual(*static_cast<pointer>(current), *static_cast<pointer>(last)))
736 {
737 this->remove_link_after(*last);
738 }
739 else
740 {
741 // Move on one.
742 last = current;
743 }
744
745 current = last->etl_next;
746 }
747 }
748
749 //*************************************************************************
751 //*************************************************************************
752 void sort()
753 {
755 }
756
757 //*************************************************************************
781 //*************************************************************************
782 template <typename TCompare>
783 void sort(TCompare compare)
784 {
785 iterator i_left;
786 iterator i_right;
787 iterator i_link;
788 iterator i_head;
789 iterator i_tail;
790 int list_size = 1;
791 int number_of_merges;
792 int left_size;
793 int right_size;
794
795 if (this->is_trivial_list())
796 {
797 return;
798 }
799
800 while (true)
801 {
802 i_left = begin();
803 i_head = before_begin();
804 i_tail = before_begin();
805
806 number_of_merges = 0; // Count the number of merges we do in this pass.
807
808 while (i_left != end())
809 {
810 ++number_of_merges; // There exists a merge to be done.
811 i_right = i_left;
812 left_size = 0;
813
814 // Step 'list_size' places along from left
815 for (int i = 0; i < list_size; ++i)
816 {
817 ++left_size;
818
819 ++i_right;
820
821 if (i_right == end())
822 {
823 break;
824 }
825 }
826
827 // If right hasn't fallen off end, we have two lists to merge.
828 right_size = list_size;
829
830 // Now we have two lists. Merge them.
831 while (left_size > 0 || (right_size > 0 && i_right != end()))
832 {
833 // Decide whether the next link of merge comes from left or right.
834 if (left_size == 0)
835 {
836 // Left is empty. The link must come from right.
837 i_link = i_right;
838 ++i_right;
839 --right_size;
840 }
841 else if (right_size == 0 || i_right == end())
842 {
843 // Right is empty. The link must come from left.
844 i_link = i_left;
845 ++i_left;
846 --left_size;
847 }
848 else if (!compare(*i_right, *i_left))
849 {
850 // First link of left is lower or same. The link must come from left.
851 i_link = i_left;
852 ++i_left;
853 --left_size;
854 }
855 else
856 {
857 // First link of right is lower. The link must come from right.
858 i_link = i_right;
859 ++i_right;
860 --right_size;
861 }
862
863 // Add the next link to the merged head.
864 if (i_head == before_begin())
865 {
866 etl::link<link_type>(i_head.p_value, i_link.p_value);
867 i_head = i_link;
868 i_tail = i_link;
869 }
870 else
871 {
872 etl::link<link_type>(i_tail.p_value, i_link.p_value);
873 i_tail = i_link;
874 }
875
876 i_tail.p_value->etl_next = &this->terminator;
877 }
878
879 // Now left has stepped `list_size' places along, and right has too.
880 i_left = i_right;
881 }
882
883 // If we have done only one merge, we're finished.
884 if (number_of_merges <= 1) // Allow for number_of_merges == 0, the empty head case
885 {
886 return;
887 }
888
889 // Otherwise repeat, merging lists twice the size
890 list_size *= 2;
891 }
892 }
893
894 //*************************************************************************
895 // Removes the values specified.
896 //*************************************************************************
897 void remove(const_reference value)
898 {
899 iterator i_item = begin();
900 iterator i_last_item = before_begin();
901
902 while (i_item != end())
903 {
904 if (*i_item == value)
905 {
906 i_item = erase_after(i_last_item);
907 }
908 else
909 {
910 ++i_item;
911 ++i_last_item;
912 }
913 }
914 }
915
916 //*************************************************************************
918 //*************************************************************************
919 template <typename TPredicate>
920 void remove_if(TPredicate predicate)
921 {
922 iterator i_item = begin();
923 iterator i_last_item = before_begin();
924
925 while (i_item != end())
926 {
927 if (predicate(*i_item))
928 {
929 i_item = erase_after(i_last_item);
930 }
931 else
932 {
933 ++i_item;
934 ++i_last_item;
935 }
936 }
937 }
938
939 //*************************************************************************
941 //*************************************************************************
943 {
944 // No point splicing to ourself!
945 if (&other != this)
946 {
947 if (!other.empty())
948 {
949 link_type& first = *other.get_head();
950
951 if (&other != this)
952 {
953 this->current_size += other.size();
954 }
955
956 link_type& before = *position.p_value;
957 link_type& after = *position.p_value->etl_next;
958
959 etl::link<link_type>(before, first);
960
961 link_type* last = &before;
962 while (last->etl_next != &other.terminator)
963 {
964 last = last->etl_next;
965 }
966
967 etl::link<link_type>(last, after);
968
969 other.initialise();
970 }
971 }
972 }
973
974 //*************************************************************************
976 //*************************************************************************
978 {
979 link_type& before = *position.p_value;
980
981 etl::unlink<link_type>(*isource.p_value);
982 etl::link_splice<link_type>(before, *isource.p_value);
983
984 if (&other != this)
985 {
986 ++this->current_size;
987 --other.current_size;
988 }
989 }
990
991 //*************************************************************************
993 //*************************************************************************
995 {
996 if (!other.empty())
997 {
998 if (&other != this)
999 {
1000 size_t n = etl::distance(begin_, end_) - 1;
1001 this->current_size += n;
1002 other.current_size -= n;
1003 }
1004
1005 link_type* first = begin_.p_value;
1006 link_type* last = first;
1007
1008 while (last->etl_next != end_.p_value)
1009 {
1010 last = last->etl_next;
1011 }
1012
1013 // Unlink from the source list.
1014 link_type* first_next = first->etl_next;
1015 etl::unlink_after(*first, *last);
1016
1017 // Fix our links.
1018 link_type* before = position.p_value;
1019
1020 etl::link_splice<link_type>(*before, *first_next, *last);
1021 }
1022 }
1023
1024 //*************************************************************************
1026 //*************************************************************************
1027 void merge(list_type& other)
1028 {
1029 merge(other, etl::less<value_type>());
1030 }
1031
1032 //*************************************************************************
1034 //*************************************************************************
1035 template <typename TCompare>
1036 void merge(list_type& other, TCompare compare)
1037 {
1038 if ((this != &other) && !other.empty())
1039 {
1040#if ETL_IS_DEBUG_BUILD
1043#endif
1044
1045 link_type* other_begin = other.get_head();
1046 link_type* other_terminal = &other.terminator;
1047
1048 link_type* before = &this->start;
1049 link_type* before_next = get_next(before);
1050 link_type* terminal = &this->terminator;;
1051
1052 while ((before->etl_next != terminal) && (other_begin != other_terminal))
1053 {
1054 // Find the place to insert.
1055 while ((before_next != terminal) && !(compare(*static_cast<pointer>(other_begin), *static_cast<pointer>(before_next))))
1056 {
1057 before = before_next;
1058 before_next = get_next(before_next);
1059 }
1060
1061 // Insert.
1062 if (before_next != terminal)
1063 {
1064 while ((other_begin != other_terminal) && (compare(*static_cast<pointer>(other_begin), *static_cast<pointer>(before_next))))
1065 {
1066 link_type* value = other_begin;
1067 other_begin = get_next(other_begin);
1068 etl::link_splice<link_type>(*before, *value);
1069 before = get_next(before);
1070 }
1071 }
1072 }
1073
1074 // Any left over?
1075 if (before_next == terminal)
1076 {
1077 while (other_begin != other_terminal)
1078 {
1079 link_type* value = other_begin;
1080 other_begin = get_next(other_begin);
1081 etl::link_splice<link_type>(*before, *value);
1082 before = get_next(before);
1083 }
1084 }
1085
1086 this->current_size += other.size();
1087
1088 other.initialise();
1089 }
1090 }
1091
1092 private:
1093
1094 //*************************************************************************
1096 //*************************************************************************
1097 link_type* get_next(link_type* link) const
1098 {
1099 return link->etl_next;
1100 }
1101
1102 // Disabled.
1104 intrusive_forward_list& operator = (const intrusive_forward_list& rhs);
1105 };
1106}
1107
1108#include "private/minmax_pop.h"
1109
1110#endif
const_iterator
Definition: intrusive_forward_list.h:448
iterator.
Definition: intrusive_forward_list.h:372
Definition: intrusive_forward_list.h:140
bool is_trivial_list() const
Is the intrusive_forward_list a trivial length?
Definition: intrusive_forward_list.h:286
link_type start
The link pointer that acts as the intrusive_forward_list start.
Definition: intrusive_forward_list.h:262
void reverse()
Reverses the intrusive_forward_list.
Definition: intrusive_forward_list.h:222
void insert_link_after(link_type &position, link_type &link)
Insert a link.
Definition: intrusive_forward_list.h:294
~intrusive_forward_list_base()
Destructor.
Definition: intrusive_forward_list.h:278
bool empty() const
Returns true if the list has no elements.
Definition: intrusive_forward_list.h:247
static link_type terminator
The link that acts as the intrusive_forward_list terminator.
Definition: intrusive_forward_list.h:263
size_t current_size
Counts the number of elements in the list.
Definition: intrusive_forward_list.h:265
intrusive_forward_list_base()
Constructor.
Definition: intrusive_forward_list.h:270
void remove_link_after(link_type &link)
Remove a link.
Definition: intrusive_forward_list.h:304
void initialise()
Initialise the intrusive_forward_list.
Definition: intrusive_forward_list.h:335
void pop_front()
Removes a value from the front of the intrusive_forward_list.
Definition: intrusive_forward_list.h:211
link_type * get_head()
Get the head link.
Definition: intrusive_forward_list.h:319
const link_type * get_head() const
Get the head link.
Definition: intrusive_forward_list.h:327
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:255
void push_front(link_type &value)
Pushes a value to the front of the intrusive_forward_list.
Definition: intrusive_forward_list.h:201
void clear()
Clears the intrusive_forward_list.
Definition: intrusive_forward_list.h:149
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:352
const_iterator before_begin() const
Gets before the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:576
iterator erase_after(iterator first, iterator last)
Erases a range of elements.
Definition: intrusive_forward_list.h:679
void sort(TCompare compare)
Definition: intrusive_forward_list.h:783
const_iterator cbegin() const
Gets the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:584
void splice_after(iterator position, etl::intrusive_forward_list< TValue, TLink > &other)
Splice another list into this one.
Definition: intrusive_forward_list.h:942
~intrusive_forward_list()
Destructor.
Definition: intrusive_forward_list.h:536
void unique(TIsEqual isEqual)
Definition: intrusive_forward_list.h:722
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:994
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:977
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:644
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:544
void remove_if(TPredicate predicate)
Removes according to a predicate.
Definition: intrusive_forward_list.h:920
iterator erase_after(iterator position)
Erases the value at the specified position.
Definition: intrusive_forward_list.h:660
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:632
const_iterator begin() const
Gets the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:560
void merge(list_type &other, TCompare compare)
Merge another list into this one. Both lists should be sorted.
Definition: intrusive_forward_list.h:1036
iterator end()
Gets the end of the intrusive_forward_list.
Definition: intrusive_forward_list.h:592
iterator before_begin()
Gets before the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:568
const_iterator end() const
Gets the end of the intrusive_forward_list.
Definition: intrusive_forward_list.h:600
const_reference front() const
Gets a const reference to the first element.
Definition: intrusive_forward_list.h:624
const_iterator cend() const
Gets the end of the intrusive_forward_list.
Definition: intrusive_forward_list.h:608
void merge(list_type &other)
Merge another list into this one. Both lists should be sorted.
Definition: intrusive_forward_list.h:1027
void sort()
Sort using in-place merge sort algorithm.
Definition: intrusive_forward_list.h:752
intrusive_forward_list()
Constructor.
Definition: intrusive_forward_list.h:529
iterator begin()
Gets the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:552
reference front()
Gets a reference to the first element.
Definition: intrusive_forward_list.h:616
ETL_NODISCARD ETL_CONSTEXPR14 bool is_sorted(TIterator begin, TIterator end)
Definition: algorithm.h:1441
ETL_CONSTEXPR14 TIterator remove(TIterator first, TIterator last, const T &value)
Definition: algorithm.h:1934
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
ETL_CONSTEXPR exception(string_type reason_, string_type, numeric_type line_)
Constructor.
Definition: exception.h:69
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
etl::byte operator&(etl::byte lhs, etl::byte rhs)
And.
Definition: byte.h:273
bool operator!=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:645
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:633
Definition: compare.h:52
iterator
Definition: iterator.h:399
Definition: functional.h:134