Embedded Template Library 1.0
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 //***************************************************************************
56 {
57 public:
58
59 intrusive_list_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
60 : exception(reason_, file_name_, line_number_)
61 {
62 }
63 };
64
65 //***************************************************************************
68 //***************************************************************************
70 {
71 public:
72
73 intrusive_list_empty(string_type file_name_, numeric_type line_number_)
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
87 intrusive_list_iterator_exception(string_type file_name_, numeric_type line_number_)
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
101 intrusive_list_unsorted(string_type file_name_, numeric_type line_number_)
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
115 intrusive_list_value_is_already_linked(string_type file_name_, numeric_type line_number_)
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
148 link_type* p_last_link = &terminal_link;
149
150 // Add all of the elements.
151 while (first != last)
152 {
153 link_type& link = *first++;
154 etl::link_splice<link_type>(p_last_link, link);
155 p_last_link = &link;
156 ++current_size;
157 }
158 }
159
160 //*************************************************************************
162 //*************************************************************************
163 void push_front(link_type& value)
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
261 link_type terminal_link;
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 //*************************************************************************
283 void insert_link(link_type& previous, link_type& new_link)
284 {
285 // Connect to the intrusive_list.
286 etl::link_splice<link_type>(previous, new_link);
287 ++current_size;
288 }
289
290 //*************************************************************************
292 //*************************************************************************
293 void insert_link(link_type* previous, link_type& new_link)
294 {
295 // Connect to the intrusive_list.
296 etl::link_splice<link_type>(previous, new_link);
297 ++current_size;
298 }
299
300 //*************************************************************************
302 //*************************************************************************
303 void insert_link(link_type& previous, link_type* new_link)
304 {
305 // Connect to the intrusive_list.
306 etl::link_splice<link_type>(previous, new_link);
307 ++current_size;
308 }
309
310 //*************************************************************************
312 //*************************************************************************
313 void insert_link(link_type* previous, link_type* new_link)
314 {
315 // Connect to the intrusive_list.
316 etl::link_splice<link_type>(previous, new_link);
317 ++current_size;
318 }
319
320 //*************************************************************************
322 //*************************************************************************
323 void remove_link(link_type& link)
324 {
325 etl::unlink<link_type>(link);
326 --current_size;
327 }
328
329 //*************************************************************************
331 //*************************************************************************
332 void remove_link(link_type* link)
333 {
334 etl::unlink<link_type>(*link);
335 --current_size;
336 }
337
338 //*************************************************************************
340 //*************************************************************************
341 link_type* get_head()
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 //*************************************************************************
357 link_type* get_tail()
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
380 //***************************************************************************
384 //***************************************************************************
385 template <typename TValue, typename TLink>
387 {
388 public:
389
390 // Node typedef.
391 typedef typename etl::intrusive_list_base<TLink>::link_type link_type;
392
394
395 // STL style typedefs.
396 typedef TValue value_type;
397 typedef value_type* pointer;
398 typedef const value_type* const_pointer;
399 typedef value_type& reference;
400 typedef const value_type& const_reference;
401 typedef size_t size_type;
402
403 //*************************************************************************
405 //*************************************************************************
406 class iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, value_type>
407 {
408 public:
409
410 friend class intrusive_list;
411 friend class const_iterator;
412
413 iterator()
414 : p_value(ETL_NULLPTR)
415 {
416 }
417
418 iterator(const iterator& other)
419 : p_value(other.p_value)
420 {
421 }
422
423 iterator& operator ++()
424 {
425 // Read the appropriate 'etl_next'.
426 p_value = p_value->etl_next;
427 return *this;
428 }
429
430 iterator operator ++(int)
431 {
432 iterator temp(*this);
433 // Read the appropriate 'etl_next'.
434 p_value = p_value->etl_next;
435 return temp;
436 }
437
438 iterator& operator --()
439 {
440 // Read the appropriate 'etl_previous'.
441 p_value = p_value->etl_previous;
442 return *this;
443 }
444
445 iterator operator --(int)
446 {
447 iterator temp(*this);
448 // Read the appropriate 'etl_previous'.
449 p_value = p_value->etl_previous;
450 return temp;
451 }
452
453 iterator& operator =(const iterator& other)
454 {
455 p_value = other.p_value;
456 return *this;
457 }
458
459 reference operator *() const
460 {
461 return *static_cast<pointer>(p_value);
462 }
463
464 pointer operator &() const
465 {
466 return static_cast<pointer>(p_value);
467 }
468
469 pointer operator ->() const
470 {
471 return static_cast<pointer>(p_value);
472 }
473
474 friend bool operator == (const iterator& lhs, const iterator& rhs)
475 {
476 return lhs.p_value == rhs.p_value;
477 }
478
479 friend bool operator != (const iterator& lhs, const iterator& rhs)
480 {
481 return !(lhs == rhs);
482 }
483
484 private:
485
486 iterator(link_type* value)
487 : p_value(value)
488 {
489 }
490
491 link_type* p_value;
492 };
493
494 //*************************************************************************
496 //*************************************************************************
497 class const_iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, const value_type>
498 {
499 public:
500
501 friend class intrusive_list;
502
504 : p_value(ETL_NULLPTR)
505 {
506 }
507
508 const_iterator(const typename intrusive_list::iterator& other)
509 : p_value(other.p_value)
510 {
511 }
512
513 const_iterator(const const_iterator& other)
514 : p_value(other.p_value)
515 {
516 }
517
518 const_iterator& operator ++()
519 {
520 // Read the appropriate 'etl_next'.
521 p_value = p_value->etl_next;
522 return *this;
523 }
524
525 const_iterator operator ++(int)
526 {
527 const_iterator temp(*this);
528 // Read the appropriate 'etl_next'.
529 p_value = p_value->etl_next;
530 return temp;
531 }
532
533 const_iterator& operator --()
534 {
535 // Read the appropriate 'etl_previous'.
536 p_value = p_value->etl_previous;
537 return *this;
538 }
539
540 const_iterator operator --(int)
541 {
542 const_iterator temp(*this);
543 // Read the appropriate 'etl_previous'.
544 p_value = p_value->etl_previous;
545 return temp;
546 }
547
548 const_iterator& operator =(const const_iterator& other)
549 {
550 p_value = other.p_value;
551 return *this;
552 }
553
554 const_reference operator *() const
555 {
556 return *static_cast<const_pointer>(p_value);
557 }
558
559 const_pointer operator &() const
560 {
561 return static_cast<const_pointer>(p_value);
562 }
563
564 const_pointer operator ->() const
565 {
566 return static_cast<const_pointer>(p_value);
567 }
568
569 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
570 {
571 return lhs.p_value == rhs.p_value;
572 }
573
574 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
575 {
576 return !(lhs == rhs);
577 }
578
579 private:
580
581 const_iterator(const link_type* value)
582 : p_value(value)
583 {
584 }
585
586 const link_type* p_value;
587 };
588
589 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
590
591 //*************************************************************************
593 //*************************************************************************
595 {
596 this->initialise();
597 }
598
599 //*************************************************************************
601 //*************************************************************************
603 {
604 this->clear();
605 }
606
607 //*************************************************************************
609 //*************************************************************************
610 template <typename TIterator>
611 intrusive_list(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral<TIterator>::value, int>::type = 0)
612 {
613 this->assign(first, last);
614 }
615
616 //*************************************************************************
618 //*************************************************************************
620 {
621 return iterator(this->get_head());
622 }
623
624 //*************************************************************************
626 //*************************************************************************
628 {
629 return const_iterator(this->get_head());
630 }
631
632 //*************************************************************************
634 //*************************************************************************
636 {
637 return const_iterator(this->get_head());
638 }
639
640 //*************************************************************************
642 //*************************************************************************
644 {
645 return iterator(&this->terminal_link);
646 }
647
648 //*************************************************************************
650 //*************************************************************************
652 {
653 return const_iterator(&this->terminal_link);
654 }
655
656 //*************************************************************************
658 //*************************************************************************
660 {
661 return const_iterator(&this->terminal_link);
662 }
663
664 //*************************************************************************
666 //*************************************************************************
667 reference front()
668 {
669 return *static_cast<pointer>(this->get_head());
670 }
671
672 //*************************************************************************
674 //*************************************************************************
675 const_reference front() const
676 {
677 return *static_cast<const_pointer>(this->get_head());
678 }
679
680 //*************************************************************************
682 //*************************************************************************
683 reference back()
684 {
685 return *static_cast<pointer>(this->get_tail());
686 }
687
688 //*************************************************************************
690 //*************************************************************************
691 const_reference back() const
692 {
693 return *static_cast<const_pointer>(this->get_tail());
694 }
695
696 //*************************************************************************
698 //*************************************************************************
699 iterator insert(const_iterator position, value_type& value)
700 {
701 this->insert_link(position.p_value->link_type::etl_previous, value);
702 return iterator(&value);
703 }
704
705 //*************************************************************************
707 //*************************************************************************
708 template <typename TIterator>
709 void insert(const_iterator position, TIterator first, TIterator last)
710 {
711 while (first != last)
712 {
713 // Set up the next free link.
714 this->insert_link(*position.p_value->link_type::etl_previous, *first);
715 ++first;
716 }
717 }
718
719 //*************************************************************************
721 //*************************************************************************
723 {
724 iterator next(position);
725 ++next;
726
727 this->remove_link(*position.p_value);
728
729 return next;
730 }
731
732 //*************************************************************************
734 //*************************************************************************
736 {
737 iterator next(position);
738 ++next;
739
740 this->remove_link(*position.p_value);
741
742 return next;
743 }
744
745 //*************************************************************************
748 //*************************************************************************
750 {
751 const link_type* cp_first = first.p_value;
752 const link_type* cp_last = last.p_value;
753
754 link_type* p_first = const_cast<link_type*>(cp_first);
755 link_type* p_last = const_cast<link_type*>(cp_last);
756
757 this->current_size -= etl::distance(first, last);
758
759 // Join the ends.
760 etl::link<link_type>(p_first->etl_previous, p_last);
761
762 while (p_first != p_last)
763 {
764 link_type* p_next = p_first->etl_next;
765 p_first->clear();
766 p_first = p_next;
767 }
768
769 if (p_last == &this->terminal_link)
770 {
771 return end();
772 }
773 else
774 {
775 return iterator(static_cast<pointer>(p_last));
776 }
777 }
778
779 //*************************************************************************
782 //*************************************************************************
783 template <typename TIsEqual>
784 void unique(TIsEqual isEqual)
785 {
786 if (this->empty())
787 {
788 return;
789 }
790
791 iterator i_item = begin();
792 ++i_item;
793 iterator i_previous = begin();
794
795 while (i_item != end())
796 {
797 if (isEqual(*i_previous, *i_item))
798 {
799 i_item = erase(i_item);
800 }
801 else
802 {
803 i_previous = i_item;
804 ++i_item;
805 }
806 }
807 }
808
809 //*************************************************************************
811 //*************************************************************************
812 void sort()
813 {
815 }
816
817 //*************************************************************************
841 //*************************************************************************
842 template <typename TCompare>
843 void sort(TCompare compare)
844 {
845 iterator i_left;
846 iterator i_right;
847 iterator i_node;
848 iterator i_head;
849 iterator i_tail;
850 int list_size = 1;
851 int number_of_merges;
852 int left_size;
853 int right_size;
854
855 if (this->is_trivial_list())
856 {
857 return;
858 }
859
860 while (true)
861 {
862 i_left = begin();
863 i_head = end();
864 i_tail = end();
865
866 number_of_merges = 0; // Count the number of merges we do in this pass.
867
868 while (i_left != end())
869 {
870 ++number_of_merges; // There exists a merge to be done.
871 i_right = i_left;
872 left_size = 0;
873
874 // Step 'list_size' places along from left
875 for (int i = 0; i < list_size; ++i)
876 {
877 ++left_size;
878 ++i_right;
879
880 if (i_right == end())
881 {
882 break;
883 }
884 }
885
886 // If right hasn't fallen off end, we have two lists to merge.
887 right_size = list_size;
888
889 // Now we have two lists. Merge them.
890 while (left_size > 0 || (right_size > 0 && i_right != end()))
891 {
892 // Decide whether the next node of merge comes from left or right.
893 if (left_size == 0)
894 {
895 // Left is empty. The node must come from right.
896 i_node = i_right++;
897 --right_size;
898 }
899 else if (right_size == 0 || i_right == end())
900 {
901 // Right is empty. The node must come from left.
902 i_node = i_left++;
903 --left_size;
904 }
905 else if (!compare(*i_right, *i_left))
906 {
907 // First node of left is lower or same. The node must come from left.
908 i_node = i_left++;
909 --left_size;
910 }
911 else
912 {
913 // First node of right is lower. The node must come from right.
914 i_node = i_right;
915 ++i_right;
916 --right_size;
917 }
918
919 // Add the next node to the merged head.
920 if (i_head == end())
921 {
922 etl::link<link_type>(i_head.p_value, i_node.p_value);
923 i_head = i_node;
924 i_tail = i_node;
925 }
926 else
927 {
928 etl::link<link_type>(i_tail.p_value, i_node.p_value);
929 i_tail = i_node;
930 }
931
932 etl::link<link_type>(i_tail.p_value, this->terminal_link);
933 }
934
935 // Now left has stepped `list_size' places along, and right has too.
936 i_left = i_right;
937 }
938
939 // If we have done only one merge, we're finished.
940 if (number_of_merges <= 1) // Allow for number_of_merges == 0, the empty head case
941 {
942 return;
943 }
944
945 // Otherwise repeat, merging lists twice the size
946 list_size *= 2;
947 }
948 }
949
950 //*************************************************************************
951 // Removes the values specified.
952 //*************************************************************************
953 void remove(const_reference value)
954 {
955 iterator i_item = begin();
956
957 while (i_item != end())
958 {
959 if (*i_item == value)
960 {
961 i_item = erase(i_item);
962 }
963 else
964 {
965 ++i_item;
966 }
967 }
968 }
969
970 //*************************************************************************
972 //*************************************************************************
973 template <typename TPredicate>
974 void remove_if(TPredicate predicate)
975 {
976 iterator i_item = begin();
977
978 while (i_item != end())
979 {
980 if (predicate(*i_item))
981 {
982 i_item = erase(i_item);
983 }
984 else
985 {
986 ++i_item;
987 }
988 }
989 }
990
991 //*************************************************************************
993 //*************************************************************************
994 void splice(iterator position, list_type& other)
995 {
996 // No point splicing to ourself!
997 if (&other != this)
998 {
999 if (!other.empty())
1000 {
1001 link_type& first = *other.get_head();
1002 link_type& last = *other.get_tail();
1003
1004 if (&other != this)
1005 {
1006 this->current_size += other.size();
1007 }
1008
1009 link_type& after = *position.p_value;
1010 link_type& before = *after.etl_previous;
1011
1012 etl::link<link_type>(before, first);
1013 etl::link<link_type>(last, after);
1014
1015 other.initialise();
1016 }
1017 }
1018 }
1019
1020 //*************************************************************************
1022 //*************************************************************************
1023 void splice(iterator position, list_type& other, iterator isource)
1024 {
1025 link_type& before = *position.p_value->link_type::etl_previous;
1026
1027 etl::unlink<link_type>(*isource.p_value);
1028 etl::link_splice<link_type>(before, *isource.p_value);
1029
1030 if (&other != this)
1031 {
1032 ++this->current_size;
1033 --other.current_size;
1034 }
1035 }
1036
1037 //*************************************************************************
1039 //*************************************************************************
1040 void splice(iterator position, list_type& other, iterator begin_, iterator end_)
1041 {
1042 if (!other.empty())
1043 {
1044 if (&other != this)
1045 {
1046 size_t n = etl::distance(begin_, end_);
1047 this->current_size += n;
1048 other.current_size -= n;
1049 }
1050
1051 link_type& first = *begin_.p_value;
1052 link_type& last = *end_.p_value->link_type::etl_previous;
1053
1054 // Unlink from the source list.
1055 etl::unlink(first, last);
1056
1057 // Fix our links.
1058 link_type& before = *position.p_value->link_type::etl_previous;
1059
1060 etl::link_splice<link_type>(before, first, last);
1061 }
1062 }
1063
1064 //*************************************************************************
1066 //*************************************************************************
1067 void merge(list_type& other)
1068 {
1069 merge(other, etl::less<value_type>());
1070 }
1071
1072 //*************************************************************************
1074 //*************************************************************************
1075 template <typename TCompare>
1076 void merge(list_type& other, TCompare compare)
1077 {
1078 if ((this != &other) && !other.empty())
1079 {
1080#if ETL_IS_DEBUG_BUILD
1081 ETL_ASSERT(etl::is_sorted(other.begin(), other.end(), compare), ETL_ERROR(intrusive_list_unsorted));
1083#endif
1084
1085 link_type* other_begin = other.get_head();
1086 link_type* other_end = &other.terminal_link;
1087
1088 link_type* this_begin = this->get_head();
1089 link_type* this_end = &this->terminal_link;
1090
1091 while ((this_begin != this_end) && (other_begin != other_end))
1092 {
1093 // Find the place to insert.
1094 while ((this_begin != this_end) && !(compare(*static_cast<pointer>(other_begin), *static_cast<pointer>(this_begin))))
1095 {
1096 this_begin = this_begin->etl_next;
1097 }
1098
1099 // Insert.
1100 if (this_begin != this_end)
1101 {
1102 while ((other_begin != other_end) && (compare(*static_cast<pointer>(other_begin), *static_cast<pointer>(this_begin))))
1103 {
1104 link_type* value = other_begin;
1105 other_begin = other_begin->etl_next;
1106 etl::link_splice<link_type>(*this_begin->etl_previous, *value);
1107 }
1108 }
1109 }
1110
1111 // Any left over?
1112 if ((this_begin == this_end) && (other_begin != other_end))
1113 {
1114 etl::link_splice<link_type>(*this->get_tail(), *other_begin, *other_end->etl_previous);
1115 }
1116
1117 this->current_size += other.size();
1118
1119 other.initialise();
1120 }
1121 }
1122
1123 private:
1124
1125 // Disabled.
1126 intrusive_list(const intrusive_list& other);
1127 intrusive_list& operator = (const intrusive_list& rhs);
1128 };
1129}
1130
1131#include "private/minmax_pop.h"
1132
1133#endif
const_iterator
Definition: intrusive_list.h:498
iterator.
Definition: intrusive_list.h:407
Definition: intrusive_list.h:127
void remove_link(link_type &link)
Remove a link.
Definition: intrusive_list.h:323
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
size_t current_size
Counts the number of elements in the list.
Definition: intrusive_list.h:263
void remove_link(link_type *link)
Remove a link.
Definition: intrusive_list.h:332
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
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:387
~intrusive_list()
Destructor.
Definition: intrusive_list.h:602
const_iterator end() const
Gets the end of the intrusive_list.
Definition: intrusive_list.h:651
reference back()
Gets a reference to the last element.
Definition: intrusive_list.h:683
iterator begin()
Gets the beginning of the intrusive_list.
Definition: intrusive_list.h:619
void unique(TIsEqual isEqual)
Definition: intrusive_list.h:784
const_iterator begin() const
Gets the beginning of the intrusive_list.
Definition: intrusive_list.h:627
void splice(iterator position, list_type &other)
Splice another list into this one.
Definition: intrusive_list.h:994
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition: intrusive_list.h:735
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:1040
reference front()
Gets a reference to the first element.
Definition: intrusive_list.h:667
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:709
void merge(list_type &other, TCompare compare)
Merge another list into this one. Both lists should be sorted.
Definition: intrusive_list.h:1076
void sort(TCompare compare)
Definition: intrusive_list.h:843
void splice(iterator position, list_type &other, iterator isource)
Splice an element from another list into this one.
Definition: intrusive_list.h:1023
intrusive_list()
Constructor.
Definition: intrusive_list.h:594
iterator erase(const_iterator first, const_iterator last)
Definition: intrusive_list.h:749
const_iterator cend() const
Gets the end of the intrusive_list.
Definition: intrusive_list.h:659
iterator erase(iterator position)
Erases the value at the specified position.
Definition: intrusive_list.h:722
const_iterator cbegin() const
Gets the beginning of the intrusive_list.
Definition: intrusive_list.h:635
void remove_if(TPredicate predicate)
Removes according to a predicate.
Definition: intrusive_list.h:974
void sort()
Sort using in-place merge sort algorithm.
Definition: intrusive_list.h:812
iterator insert(const_iterator position, value_type &value)
Inserts a value to the intrusive_list before the specified position.
Definition: intrusive_list.h:699
const_reference front() const
Gets a const reference to the first element.
Definition: intrusive_list.h:675
iterator end()
Gets the end of the intrusive_list.
Definition: intrusive_list.h:643
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:611
const_reference back() const
Gets a const reference to the last element.
Definition: intrusive_list.h:691
void merge(list_type &other)
Merge another list into this one. Both lists should be sorted.
Definition: intrusive_list.h:1067
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