Embedded Template Library 1.0
Loading...
Searching...
No Matches
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) 2014 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_LIST_INCLUDED
32#define ETL_LIST_INCLUDED
33
34#include "platform.h"
35#include "algorithm.h"
36#include "iterator.h"
37#include "functional.h"
38#include "pool.h"
39#include "exception.h"
40#include "error_handler.h"
41#include "debug_count.h"
42#include "nullptr.h"
43#include "type_traits.h"
44#include "algorithm.h"
45#include "memory.h"
46#include "static_assert.h"
47#include "parameter_type.h"
48#include "placement_new.h"
49#include "initializer_list.h"
50
51#include <stddef.h>
52
53#include "private/minmax_push.h"
54
55//*****************************************************************************
59//*****************************************************************************
60
61namespace etl
62{
63 //***************************************************************************
66 //***************************************************************************
76
77 //***************************************************************************
80 //***************************************************************************
82 {
83 public:
84
86 : list_exception(ETL_ERROR_TEXT("list:full", ETL_LIST_FILE_ID"A"), file_name_, line_number_)
87 {
88 }
89 };
90
91 //***************************************************************************
94 //***************************************************************************
96 {
97 public:
98
100 : list_exception(ETL_ERROR_TEXT("list:empty", ETL_LIST_FILE_ID"B"), file_name_, line_number_)
101 {
102 }
103 };
104
105 //***************************************************************************
108 //***************************************************************************
110 {
111 public:
112
114 : list_exception(ETL_ERROR_TEXT("list:iterator", ETL_LIST_FILE_ID"C"), file_name_, line_number_)
115 {
116 }
117 };
118
119 //***************************************************************************
122 //***************************************************************************
124 {
125 public:
126
128 : list_exception(ETL_ERROR_TEXT("list:unsorted", ETL_LIST_FILE_ID"D"), file_name_, line_number_)
129 {
130 }
131 };
132
133 //***************************************************************************
136 //***************************************************************************
138 {
139 public:
140
142 : list_exception(ETL_ERROR_TEXT("list:no pool", ETL_LIST_FILE_ID"E"), file_name_, line_number_)
143 {
144 }
145 };
146
147 //***************************************************************************
150 //***************************************************************************
152 {
153 public:
154
155 typedef size_t size_type;
156
157 //*************************************************************************
159 //*************************************************************************
160 struct node_t
161 {
162 //***********************************************************************
164 //***********************************************************************
166 : previous(ETL_NULLPTR),
167 next(ETL_NULLPTR)
168 {
169 }
170
171 //***********************************************************************
173 //***********************************************************************
174 void reverse()
175 {
176 using ETL_OR_STD::swap; // Allow ADL
177
178 swap(previous, next);
179 }
180
181 node_t* previous;
182 node_t* next;
183 };
184
185 //*************************************************************************
187 //*************************************************************************
188 bool has_shared_pool() const
189 {
190 return pool_is_shared;
191 }
192
193 //*************************************************************************
195 //*************************************************************************
196 void reverse()
197 {
198 if (is_trivial_list())
199 {
200 return;
201 }
202
203 node_t* p_node = terminal_node.next;
204
205 while (p_node != &terminal_node)
206 {
207 node_t* p_temp = p_node->previous;
208 p_node->previous = p_node->next;
209 p_node->next = p_temp;
210 p_node = p_node->previous;
211 }
212
213 // Terminal node.
214 node_t* p_temp = p_node->previous;
215 p_node->previous = p_node->next;
216 p_node->next = p_temp;
217 }
218
219 //*************************************************************************
221 //*************************************************************************
223 {
224 return MAX_SIZE;
225 }
226
227 //*************************************************************************
229 //*************************************************************************
231 {
232 return MAX_SIZE;
233 }
234
235 //*************************************************************************
237 //*************************************************************************
239 {
240 if (has_shared_pool())
241 {
242 // We have to count what we actually own.
243 size_type count = 0U;
244
245 node_t* p_node = terminal_node.next;
246
247 while (p_node != &terminal_node)
248 {
249 ++count;
250 p_node = p_node->next;
251 }
252
253 return count;
254 }
255 else
256 {
257 return p_node_pool->size();
258 }
259 }
260
261 //*************************************************************************
263 //*************************************************************************
264 bool empty() const
265 {
266 return (terminal_node.next == &terminal_node);
267 }
268
269 //*************************************************************************
271 //*************************************************************************
272 bool full() const
273 {
274 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
275 return p_node_pool->full();
276 }
277
278 //*************************************************************************
281 //*************************************************************************
283 {
284 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
285 return p_node_pool->available();
286 }
287
288 protected:
289
290 //*************************************************************************
292 //*************************************************************************
293 bool is_trivial_list() const
294 {
295 return (size() < 2);
296 }
297
298 //*************************************************************************
300 //*************************************************************************
302 {
303 return *terminal_node.next;
304 }
305
306 //*************************************************************************
308 //*************************************************************************
309 const node_t& get_head() const
310 {
311 return *terminal_node.next;
312 }
313
314 //*************************************************************************
316 //*************************************************************************
318 {
319 return *terminal_node.previous;
320 }
321
322 //*************************************************************************
324 //*************************************************************************
325 const node_t& get_tail() const
326 {
327 return *terminal_node.previous;
328 }
329
330 //*************************************************************************
332 //*************************************************************************
333 void insert_node(node_t& position, node_t& node)
334 {
335 // Connect to the list.
336 join(*position.previous, node);
337 join(node, position);
338 }
339
340 //*************************************************************************
342 //*************************************************************************
343 void join(node_t& left, node_t& right)
344 {
345 left.next = &right;
346 right.previous = &left;
347 }
348
349 //*************************************************************************
351 //*************************************************************************
353 : p_node_pool(ETL_NULLPTR),
354 MAX_SIZE(0),
356 {
358 }
359
360 //*************************************************************************
362 //*************************************************************************
370
371 //*************************************************************************
373 //*************************************************************************
379
380 //*************************************************************************
382 //*************************************************************************
384 {
385 return p_node_pool;
386 }
387
388 //*************************************************************************
390 //*************************************************************************
392 {
393 }
394
400 };
401
402 //***************************************************************************
405 //***************************************************************************
406 template <typename T>
407 class ilist : public etl::list_base
408 {
409 public:
410
411 typedef T value_type;
412 typedef T* pointer;
413 typedef const T* const_pointer;
414 typedef T& reference;
415 typedef const T& const_reference;
416#if ETL_USING_CPP11
417 typedef T&& rvalue_reference;
418#endif
419 typedef size_t size_type;
420
421 protected:
422
424
425 //*************************************************************************
427 //*************************************************************************
428 struct data_node_t : public node_t
429 {
430 explicit data_node_t(const T& value_)
431 : value(value_)
432 {
433 }
434
435 T value;
436 };
437
438 private:
439
440 //*************************************************************************
442 //*************************************************************************
443 static data_node_t* data_cast(node_t* p_node)
444 {
445 return reinterpret_cast<data_node_t*>(p_node);
446 }
447
448 //*************************************************************************
450 //*************************************************************************
451 static data_node_t& data_cast(node_t& node)
452 {
453 return reinterpret_cast<data_node_t&>(node);
454 }
455
456 //*************************************************************************
458 //*************************************************************************
459 static const data_node_t* data_cast(const node_t* p_node)
460 {
461 return reinterpret_cast<const data_node_t*>(p_node);
462 }
463
464 //*************************************************************************
466 //*************************************************************************
467 static const data_node_t& data_cast(const node_t& node)
468 {
469 return reinterpret_cast<const data_node_t&>(node);
470 }
471
472 public:
473
474 //*************************************************************************
476 //*************************************************************************
477 class iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, T>
478 {
479 public:
480
481 friend class ilist;
482 friend class const_iterator;
483
484 iterator()
485 : p_node(ETL_NULLPTR)
486 {
487 }
488
490 : p_node(&node)
491 {
492 }
493
494 iterator(const iterator& other)
495 : p_node(other.p_node)
496 {
497 }
498
500 {
501 p_node = p_node->next;
502 return *this;
503 }
504
506 {
507 iterator temp(*this);
508 p_node = p_node->next;
509 return temp;
510 }
511
513 {
514 p_node = p_node->previous;
515 return *this;
516 }
517
519 {
520 iterator temp(*this);
521 p_node = p_node->previous;
522 return temp;
523 }
524
526 {
527 p_node = other.p_node;
528 return *this;
529 }
530
531 reference operator *() const
532 {
533 return ilist::data_cast(p_node)->value;
534 }
535
536 pointer operator &() const
537 {
538 return &(ilist::data_cast(p_node)->value);
539 }
540
541 pointer operator ->() const
542 {
543 return &(ilist::data_cast(p_node)->value);
544 }
545
546 friend bool operator == (const iterator& lhs, const iterator& rhs)
547 {
548 return lhs.p_node == rhs.p_node;
549 }
550
551 friend bool operator != (const iterator& lhs, const iterator& rhs)
552 {
553 return !(lhs == rhs);
554 }
555
556 private:
557
558 node_t* p_node;
559 };
560
561 //*************************************************************************
563 //*************************************************************************
564 class const_iterator : public etl::iterator<ETL_OR_STD::bidirectional_iterator_tag, const T>
565 {
566 public:
567
568 friend class ilist;
569
571 : p_node(ETL_NULLPTR)
572 {
573 }
574
576 : p_node(&node)
577 {
578 }
579
581 : p_node(&node)
582 {
583 }
584
585 const_iterator(const typename ilist::iterator& other)
586 : p_node(other.p_node)
587 {
588 }
589
591 : p_node(other.p_node)
592 {
593 }
594
596 {
597 p_node = p_node->next;
598 return *this;
599 }
600
602 {
603 const_iterator temp(*this);
604 p_node = p_node->next;
605 return temp;
606 }
607
609 {
610 p_node = p_node->previous;
611 return *this;
612 }
613
615 {
616 const_iterator temp(*this);
617 p_node = p_node->previous;
618 return temp;
619 }
620
622 {
623 p_node = other.p_node;
624 return *this;
625 }
626
628 {
629 return ilist::data_cast(p_node)->value;
630 }
631
633 {
634 return &(ilist::data_cast(p_node)->value);
635 }
636
638 {
639 return &(ilist::data_cast(p_node)->value);
640 }
641
642 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
643 {
644 return lhs.p_node == rhs.p_node;
645 }
646
647 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
648 {
649 return !(lhs == rhs);
650 }
651
652 private:
653
654 const node_t* p_node;
655 };
656
657 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
658
659 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
660 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
661
662 //*************************************************************************
664 //*************************************************************************
666 {
667 return iterator(get_head());
668 }
669
670 //*************************************************************************
672 //*************************************************************************
674 {
675 return const_iterator(get_head());
676 }
677
678 //*************************************************************************
680 //*************************************************************************
682 {
683 return iterator(terminal_node);
684 }
685
686 //*************************************************************************
688 //*************************************************************************
690 {
692 }
693
694 //*************************************************************************
696 //*************************************************************************
698 {
699 return const_iterator(get_head());
700 }
701
702 //*************************************************************************
704 //*************************************************************************
706 {
708 }
709
710 //*************************************************************************
712 //*************************************************************************
713 reverse_iterator rbegin()
714 {
715 return reverse_iterator(terminal_node);
716 }
717
718 //*************************************************************************
720 //*************************************************************************
721 const_reverse_iterator rbegin() const
722 {
723 return const_reverse_iterator(terminal_node);
724 }
725
726 //*************************************************************************
728 //*************************************************************************
729 reverse_iterator rend()
730 {
731 return reverse_iterator(get_head());
732 }
733
734 //*************************************************************************
736 //*************************************************************************
737 const_reverse_iterator rend() const
738 {
739 return const_reverse_iterator(get_head());
740 }
741
742 //*************************************************************************
744 //*************************************************************************
745 const_reverse_iterator crbegin() const
746 {
747 return const_reverse_iterator(terminal_node);
748 }
749
750 //*************************************************************************
752 //*************************************************************************
753 const_reverse_iterator crend() const
754 {
755 return const_reverse_iterator(get_head());
756 }
757
758 //*************************************************************************
760 //*************************************************************************
762 {
763 return data_cast(get_head()).value;
764 }
765
766 //*************************************************************************
768 //*************************************************************************
770 {
771 return data_cast(get_head()).value;
772 }
773
774 //*************************************************************************
776 //*************************************************************************
778 {
779 return data_cast(get_tail()).value;
780 }
781
782 //*************************************************************************
784 //*************************************************************************
786 {
787 return data_cast(get_tail()).value;
788 }
789
790 //*************************************************************************
794 //*************************************************************************
795 template <typename TIterator>
797 {
798#if ETL_IS_DEBUG_BUILD
799 difference_type d = etl::distance(first, last);
800 ETL_ASSERT(d >= 0, ETL_ERROR(list_iterator));
801 ETL_ASSERT(size_t(d) <= MAX_SIZE, ETL_ERROR(list_full));
802#endif
803 initialise();
804
805 // Add all of the elements.
806 while (first != last)
807 {
808 data_node_t& node = allocate_data_node(*first);
809 join(get_tail(), node);
811 ++first;
812 }
813 }
814
815 //*************************************************************************
817 //*************************************************************************
818 void assign(size_t n, const T& value)
819 {
820#if ETL_IS_DEBUG_BUILD
821 ETL_ASSERT(n <= MAX_SIZE, ETL_ERROR(list_full));
822#endif
823
824 initialise();
825
826 // Add all of the elements.
827 while (n-- > 0)
828 {
829 data_node_t& node = allocate_data_node(value);
830 join(*terminal_node.previous, node);
832 }
833 }
834
835 //*************************************************************************
837 //*************************************************************************
838 void push_front(const T& value)
839 {
840#if defined(ETL_CHECK_PUSH_POP)
841 ETL_ASSERT(!full(), ETL_ERROR(list_full));
842#endif
843 insert_node(get_head(), allocate_data_node(value));
844 }
845
846#if ETL_USING_CPP11
847 //*************************************************************************
849 //*************************************************************************
850 void push_front(rvalue_reference value)
851 {
852#if defined(ETL_CHECK_PUSH_POP)
853 ETL_ASSERT(!full(), ETL_ERROR(list_full));
854#endif
855 insert_node(get_head(), allocate_data_node(etl::move(value)));
856 }
857#endif
858
859#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT && !defined(ETL_LIST_FORCE_CPP03_IMPLEMENTATION)
860 //*************************************************************************
862 //*************************************************************************
863 template <typename ... Args>
864 reference emplace_front(Args && ... args)
865 {
866#if defined(ETL_CHECK_PUSH_POP)
867 ETL_ASSERT(!full(), ETL_ERROR(list_full));
868#endif
869 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
870
871 data_node_t* p_data_node = allocate_data_node();
872 ::new (&(p_data_node->value)) T(etl::forward<Args>(args)...);
873 ETL_INCREMENT_DEBUG_COUNT;
874 insert_node(get_head(), *p_data_node);
875 return front();
876 }
877#else
878 //*************************************************************************
880 //*************************************************************************
882 {
883#if defined(ETL_CHECK_PUSH_POP)
884 ETL_ASSERT(!full(), ETL_ERROR(list_full));
885#endif
886 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
887
888 data_node_t* p_data_node = allocate_data_node();
889 ::new (&(p_data_node->value)) T();
890 ETL_INCREMENT_DEBUG_COUNT;
892 return front();
893 }
894
895 //*************************************************************************
897 //*************************************************************************
898 template <typename T1>
900 {
901#if defined(ETL_CHECK_PUSH_POP)
902 ETL_ASSERT(!full(), ETL_ERROR(list_full));
903#endif
904 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
905
906 data_node_t* p_data_node = allocate_data_node();
907 ::new (&(p_data_node->value)) T(value1);
908 ETL_INCREMENT_DEBUG_COUNT;
910 return front();
911 }
912
913 //*************************************************************************
915 //*************************************************************************
916 template <typename T1, typename T2>
917 reference emplace_front(const T1& value1, const T2& value2)
918 {
919#if defined(ETL_CHECK_PUSH_POP)
920 ETL_ASSERT(!full(), ETL_ERROR(list_full));
921#endif
922 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
923
924 data_node_t* p_data_node = allocate_data_node();
925 ::new (&(p_data_node->value)) T(value1, value2);
926 ETL_INCREMENT_DEBUG_COUNT;
928 return front();
929 }
930
931 //*************************************************************************
933 //*************************************************************************
934 template <typename T1, typename T2, typename T3>
935 reference emplace_front(const T1& value1, const T2& value2, const T3& value3)
936 {
937#if defined(ETL_CHECK_PUSH_POP)
938 ETL_ASSERT(!full(), ETL_ERROR(list_full));
939#endif
940 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
941
942 data_node_t* p_data_node = allocate_data_node();
943 ::new (&(p_data_node->value)) T(value1, value2, value3);
944 ETL_INCREMENT_DEBUG_COUNT;
946 return front();
947 }
948
949 //*************************************************************************
951 //*************************************************************************
952 template <typename T1, typename T2, typename T3, typename T4>
953 reference emplace_front(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
954 {
955#if defined(ETL_CHECK_PUSH_POP)
956 ETL_ASSERT(!full(), ETL_ERROR(list_full));
957#endif
958 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
959
960 data_node_t* p_data_node = allocate_data_node();
961 ::new (&(p_data_node->value)) T(value1, value2, value3, value4);
962 ETL_INCREMENT_DEBUG_COUNT;
964 return front();
965 }
966#endif
967
968 //*************************************************************************
970 //*************************************************************************
972 {
973#if defined(ETL_CHECK_PUSH_POP)
974 ETL_ASSERT(!empty(), ETL_ERROR(list_empty));
975#endif
976 node_t& node = get_head();
977 remove_node(node);
978 }
979
980 //*************************************************************************
982 //*************************************************************************
983 void push_back(const T& value)
984 {
985#if defined(ETL_CHECK_PUSH_POP)
986 ETL_ASSERT(!full(), ETL_ERROR(list_full));
987#endif
988 insert_node(terminal_node, allocate_data_node(value));
989 }
990
991#if ETL_USING_CPP11
992 //*************************************************************************
994 //*************************************************************************
995 void push_back(rvalue_reference value)
996 {
997#if defined(ETL_CHECK_PUSH_POP)
998 ETL_ASSERT(!full(), ETL_ERROR(list_full));
999#endif
1000 insert_node(terminal_node, allocate_data_node(etl::move(value)));
1001 }
1002#endif
1003
1004 //*************************************************************************
1006 //*************************************************************************
1007#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
1008 template <typename ... Args>
1009 reference emplace_back(Args && ... args)
1010 {
1011#if defined(ETL_CHECK_PUSH_POP)
1012 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1013#endif
1014 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1015
1016 data_node_t* p_data_node = allocate_data_node();
1017 ::new (&(p_data_node->value)) T(etl::forward<Args>(args)...);
1018 ETL_INCREMENT_DEBUG_COUNT;
1019 insert_node(terminal_node, *p_data_node);
1020 return back();
1021 }
1022#else
1024 {
1025#if defined(ETL_CHECK_PUSH_POP)
1026 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1027#endif
1028 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1029
1030 data_node_t* p_data_node = allocate_data_node();
1031 ::new (&(p_data_node->value)) T();
1032 ETL_INCREMENT_DEBUG_COUNT;
1034 return back();
1035 }
1036
1037 template <typename T1>
1038 reference emplace_back(const T1& value1)
1039 {
1040#if defined(ETL_CHECK_PUSH_POP)
1041 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1042#endif
1043 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1044
1045 data_node_t* p_data_node = allocate_data_node();
1046 ::new (&(p_data_node->value)) T(value1);
1047 ETL_INCREMENT_DEBUG_COUNT;
1049 return back();
1050 }
1051
1053 reference emplace_back(const T1& value1, const T2& value2)
1054 {
1055#if defined(ETL_CHECK_PUSH_POP)
1056 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1057#endif
1058 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1059
1060 data_node_t* p_data_node = allocate_data_node();
1061 ::new (&(p_data_node->value)) T(value1, value2);
1062 ETL_INCREMENT_DEBUG_COUNT;
1064 return back();
1065 }
1066
1068 reference emplace_back(const T1& value1, const T2& value2, const T3& value3)
1069 {
1070#if defined(ETL_CHECK_PUSH_POP)
1071 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1072#endif
1073 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1074
1075 data_node_t* p_data_node = allocate_data_node();
1076 ::new (&(p_data_node->value)) T(value1, value2, value3);
1077 ETL_INCREMENT_DEBUG_COUNT;
1079 return back();
1080 }
1081
1083 reference emplace_back(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
1084 {
1085#if defined(ETL_CHECK_PUSH_POP)
1086 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1087#endif
1088 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1089
1090 data_node_t* p_data_node = allocate_data_node();
1091 ::new (&(p_data_node->value)) T(value1, value2, value3, value4);
1092 ETL_INCREMENT_DEBUG_COUNT;
1094 return back();
1095 }
1096#endif
1097
1098 //*************************************************************************
1100 //*************************************************************************
1102 {
1103#if defined(ETL_CHECK_PUSH_POP)
1104 ETL_ASSERT(!empty(), ETL_ERROR(list_empty));
1105#endif
1106 node_t& node = get_tail();
1107 remove_node(node);
1108 }
1109
1110 //*************************************************************************
1112 //*************************************************************************
1114 {
1115 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1116
1117 data_node_t& data_node = allocate_data_node(value);
1118 insert_node(*to_iterator(position).p_node, data_node);
1119
1120 return iterator(data_node);
1121 }
1122
1123#if ETL_USING_CPP11
1124 //*************************************************************************
1126 //*************************************************************************
1127 iterator insert(const_iterator position, rvalue_reference value)
1128 {
1129 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1130
1131 data_node_t& data_node = allocate_data_node(etl::move(value));
1132 insert_node(*to_iterator(position).p_node, data_node);
1133
1134 return iterator(data_node);
1135 }
1136#endif
1137
1138 //*************************************************************************
1140 //*************************************************************************
1141#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT && !defined(ETL_LIST_FORCE_CPP03_IMPLEMENTATION)
1142 template <typename ... Args>
1143 iterator emplace(const_iterator position, Args&& ... args)
1144 {
1145 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1146 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1147
1148 data_node_t* p_data_node = allocate_data_node();
1149 ::new (&(p_data_node->value)) T(etl::forward<Args>(args)...);
1150 ETL_INCREMENT_DEBUG_COUNT;
1151 insert_node(*to_iterator(position).p_node, *p_data_node);
1152
1153 return iterator(*p_data_node);
1154 }
1155#else
1157 {
1158 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1159 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1160
1161 data_node_t* p_data_node = allocate_data_node();
1162 ::new (&(p_data_node->value)) T();
1163 ETL_INCREMENT_DEBUG_COUNT;
1164 insert_node(*to_iterator(position).p_node, *p_data_node);
1165
1166 return iterator(*p_data_node);
1167 }
1168
1169 template <typename T1>
1170 iterator emplace(const_iterator position, const T1& value1)
1171 {
1172 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1173 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1174
1175 data_node_t* p_data_node = allocate_data_node();
1176 ::new (&(p_data_node->value)) T(value1);
1177 ETL_INCREMENT_DEBUG_COUNT;
1178 insert_node(*to_iterator(position).p_node, *p_data_node);
1179
1181 }
1182
1184 iterator emplace(const_iterator position, const T1& value1, const T2& value2)
1185 {
1186 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1187 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1188
1189 data_node_t* p_data_node = allocate_data_node();
1190 ::new (&(p_data_node->value)) T(value1, value2);
1191 ETL_INCREMENT_DEBUG_COUNT;
1192 insert_node(*to_iterator(position).p_node, *p_data_node);
1193
1195 }
1196
1198 iterator emplace(const_iterator position, const T1& value1, const T2& value2, const T3& value3)
1199 {
1200 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1201 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1202
1203 data_node_t* p_data_node = allocate_data_node();
1204 ::new (&(p_data_node->value)) T(value1, value2, value3);
1205 ETL_INCREMENT_DEBUG_COUNT;
1206 insert_node(*to_iterator(position).p_node, *p_data_node);
1207
1209 }
1210
1212 iterator emplace(const_iterator position, const T1& value1, const T2& value2, const T3& value3, const T4& value4)
1213 {
1214 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1215 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1216
1217 data_node_t* p_data_node = allocate_data_node();
1218 ::new (&(p_data_node->value)) T(value1, value2, value3, value4);
1219 ETL_INCREMENT_DEBUG_COUNT;
1220 insert_node(*to_iterator(position).p_node, *p_data_node);
1221
1223 }
1224#endif
1225
1226 //*************************************************************************
1228 //*************************************************************************
1229 void insert(const_iterator position, size_t n, const_reference value)
1230 {
1231 for (size_t i = 0UL; i < n; ++i)
1232 {
1233 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1234
1235 // Set up the next free node and insert.
1236 insert_node(*to_iterator(position).p_node, allocate_data_node(value));
1237 }
1238 }
1239
1240 //*************************************************************************
1242 //*************************************************************************
1243 template <typename TIterator>
1244 void insert(const_iterator position, TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral<TIterator>::value, int>::type = 0)
1245 {
1246 while (first != last)
1247 {
1248 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1249
1250 // Set up the next free node and insert.
1251 insert_node(*to_iterator(position).p_node, allocate_data_node(*first));
1252 ++first;
1253 }
1254 }
1255
1256 //*************************************************************************
1258 //*************************************************************************
1260 {
1261 iterator position_ = to_iterator(position);
1262
1263 ++position_;
1264 remove_node(*position_.p_node->previous);
1265 return position_;
1266 }
1267
1268 //*************************************************************************
1270 //*************************************************************************
1272 {
1273 iterator first_ = to_iterator(first);
1274 iterator last_ = to_iterator(last);
1275
1276 node_t* p_first = first_.p_node;
1277 node_t* p_last = last_.p_node;
1278 node_t* p_next;
1279
1280 // Join the ends.
1281 join(*(p_first->previous), *p_last);
1282
1283 // Erase the ones in between.
1284 while (p_first != p_last)
1285 {
1286 p_next = p_first->next; // Remember the next node.
1287 destroy_data_node(static_cast<data_node_t&>(*p_first)); // Destroy the current node.
1288 p_first = p_next; // Move to the next node.
1289 }
1290
1291 return last_;
1292 }
1293
1294 //*************************************************************************
1296 //*************************************************************************
1297 void resize(size_t n)
1298 {
1299 resize(n, T());
1300 }
1301
1302 //*************************************************************************
1304 //*************************************************************************
1305 void resize(size_t n, const_reference value)
1306 {
1307 ETL_ASSERT(n <= MAX_SIZE, ETL_ERROR(list_full));
1308
1309 // Zero?
1310 if (n == 0U)
1311 {
1312 clear();
1313 }
1314 // Smaller?
1315 else if (n < size())
1316 {
1317 iterator i_start = end();
1318 etl::advance(i_start, -difference_type(size() - n));
1319 erase(i_start, end());
1320 }
1321 // Larger?
1322 else if (n > size())
1323 {
1324 insert(end(), n - size(), value);
1325 }
1326 }
1327
1328 //*************************************************************************
1330 //*************************************************************************
1331 void clear()
1332 {
1333 initialise();
1334 }
1335
1336 //*************************************************************************
1337 // Removes the values specified.
1338 //*************************************************************************
1339 void remove(const_reference value)
1340 {
1341 iterator iValue = begin();
1342
1343 while (iValue != end())
1344 {
1345 if (value == *iValue)
1346 {
1347 iValue = erase(iValue);
1348 }
1349 else
1350 {
1351 ++iValue;
1352 }
1353 }
1354 }
1355
1356 //*************************************************************************
1358 //*************************************************************************
1359 template <typename TPredicate>
1361 {
1362 iterator iValue = begin();
1363
1364 while (iValue != end())
1365 {
1366 if (predicate(*iValue))
1367 {
1368 iValue = erase(iValue);
1369 }
1370 else
1371 {
1372 ++iValue;
1373 }
1374 }
1375 }
1376
1377 //*************************************************************************
1380 //*************************************************************************
1381 void unique()
1382 {
1384 }
1385
1386 //*************************************************************************
1389 //*************************************************************************
1390 template <typename TIsEqual>
1392 {
1393 if (empty())
1394 {
1395 return;
1396 }
1397
1398 iterator i_item = begin();
1399 ++i_item;
1401
1402 while (i_item != end())
1403 {
1404 if (isEqual(*i_previous, *i_item))
1405 {
1406 i_item = erase(i_item);
1407 }
1408 else
1409 {
1411 ++i_item;
1412 }
1413 }
1414 }
1415
1416 //*************************************************************************
1418 //*************************************************************************
1420 {
1421 if (&other != this)
1422 {
1423 insert(to, other.begin(), other.end());
1424 other.erase(other.begin(), other.end());
1425 }
1426 }
1427
1428#if ETL_USING_CPP11
1429 //*************************************************************************
1431 //*************************************************************************
1432 void splice(iterator to, ilist&& other)
1433 {
1434 if (&other != this)
1435 {
1436 typename ilist<T>::iterator itr = other.begin();
1437 while (itr != other.end())
1438 {
1439 to = insert(to, etl::move(*itr));
1440 ++itr;
1441 }
1442
1443 other.erase(other.begin(), other.end());
1444 }
1445 }
1446#endif
1447
1448 //*************************************************************************
1450 //*************************************************************************
1452 {
1453 if (&other == this)
1454 {
1455 // Internal move.
1456 move(to, from);
1457 }
1458 else
1459 {
1460 // From another list.
1461 insert(to, *from);
1462 other.erase(from);
1463 }
1464 }
1465
1466#if ETL_USING_CPP11
1467 //*************************************************************************
1469 //*************************************************************************
1471 {
1472 if (&other == this)
1473 {
1474 // Internal move.
1475 move(to, from);
1476 }
1477 else
1478 {
1479 // From another list.
1480 insert(to, etl::move(*from));
1481 other.erase(from);
1482 }
1483 }
1484#endif
1485
1486 //*************************************************************************
1488 //*************************************************************************
1490 {
1491 if (&other == this)
1492 {
1493 // Internal move.
1494 move(to, first, last);
1495 }
1496 else
1497 {
1498 // From another list.
1499 insert(to, first, last);
1500 other.erase(first, last);
1501 }
1502 }
1503
1504#if ETL_USING_CPP11
1505 //*************************************************************************
1507 //*************************************************************************
1508 void splice(iterator to, ilist&& other, iterator first, iterator last)
1509 {
1510 if (&other == this)
1511 {
1512 // Internal move.
1513 move(to, first, last);
1514 }
1515 else
1516 {
1517 // From another list.
1518 ilist::iterator itr = first;
1519 while (itr != last)
1520 {
1521 to = insert(to, etl::move(*itr));
1522 ++itr;
1523 ++to;
1524 }
1525
1526 other.erase(first, last);
1527 }
1528 }
1529#endif
1530
1531 //*************************************************************************
1533 //*************************************************************************
1535 {
1537 }
1538
1539 //*************************************************************************
1541 //*************************************************************************
1542 template <typename TCompare>
1544 {
1545 if ((this != &other) && !other.empty())
1546 {
1547#if ETL_IS_DEBUG_BUILD
1548 ETL_ASSERT(etl::is_sorted(other.begin(), other.end(), compare), ETL_ERROR(list_unsorted));
1550#endif
1551
1554
1557
1558 while ((this_begin != this_end) && (other_begin != other_end))
1559 {
1560 // Find the place to insert.
1561 while ((this_begin != this_end) && !(compare(*other_begin, *this_begin)))
1562 {
1563 ++this_begin;
1564 }
1565
1566 // Insert.
1567 if (this_begin != this_end)
1568 {
1569 while ((other_begin != other_end) && (compare(*other_begin, *this_begin)))
1570 {
1572 ++other_begin;
1573 }
1574 }
1575 }
1576
1577 // Any left over?
1578 if ((this_begin == this_end) && (other_begin != other_end))
1579 {
1581 }
1582
1583 other.clear();
1584 }
1585 }
1586
1587#if ETL_USING_CPP11
1588 //*************************************************************************
1590 //*************************************************************************
1591 void merge(ilist&& other)
1592 {
1593 merge(etl::move(other), etl::less<value_type>());
1594 }
1595
1596 //*************************************************************************
1598 //*************************************************************************
1599 template <typename TCompare>
1600 void merge(ilist&& other, TCompare compare)
1601 {
1602 if (!other.empty())
1603 {
1604#if ETL_IS_DEBUG_BUILD
1605 ETL_ASSERT(etl::is_sorted(other.begin(), other.end(), compare), ETL_ERROR(list_unsorted));
1606 ETL_ASSERT(etl::is_sorted(begin(), end(), compare), ETL_ERROR(list_unsorted));
1607#endif
1608
1609 ilist::iterator other_begin = other.begin();
1610 ilist::iterator other_end = other.end();
1611
1612 ilist::iterator this_begin = begin();
1613 ilist::iterator this_end = end();
1614
1615 while ((this_begin != this_end) && (other_begin != other_end))
1616 {
1617 // Find the place to insert.
1618 while ((this_begin != this_end) && !(compare(*other_begin, *this_begin)))
1619 {
1620 ++this_begin;
1621 }
1622
1623 // Insert.
1624 if (this_begin != this_end)
1625 {
1626 while ((other_begin != other_end) && (compare(*other_begin, *this_begin)))
1627 {
1628 insert(this_begin, etl::move(*other_begin));
1629 ++other_begin;
1630 }
1631 }
1632 }
1633
1634 // Any left over?
1635 if ((this_begin == this_end) && (other_begin != other_end))
1636 {
1637 while (other_begin != other_end)
1638 {
1639 insert(this_end, etl::move(*other_begin));
1640 ++other_begin;
1641 }
1642 }
1643
1644 other.clear();
1645 }
1646 }
1647#endif
1648
1649 //*************************************************************************
1652 //*************************************************************************
1653 void sort()
1654 {
1655 sort(etl::less<T>());
1656 }
1657
1658 //*************************************************************************
1682 //*************************************************************************
1683 template <typename TCompare>
1685 {
1691 int list_size = 1;
1692 int number_of_merges;
1693 int left_size;
1694 int right_size;
1695
1696 if (is_trivial_list())
1697 {
1698 return;
1699 }
1700
1701 while (true)
1702 {
1703 i_left = begin();
1704 i_head = end();
1705 i_tail = end();
1706
1707 number_of_merges = 0; // Count the number of merges we do in this pass.
1708
1709 while (i_left != end())
1710 {
1711 ++number_of_merges; // There exists a merge to be done.
1712 i_right = i_left;
1713 left_size = 0;
1714
1715 // Step 'list_size' places along from left
1716 for (int i = 0; i < list_size; ++i)
1717 {
1718 ++left_size;
1719 ++i_right;
1720
1721 if (i_right == end())
1722 {
1723 break;
1724 }
1725 }
1726
1727 // If right hasn't fallen off end, we have two lists to merge.
1729
1730 // Now we have two lists. Merge them.
1731 while (left_size > 0 || (right_size > 0 && i_right != end()))
1732 {
1733 // Decide whether the next node of merge comes from left or right.
1734 if (left_size == 0)
1735 {
1736 // Left is empty. The node must come from right.
1737 i_node = i_right++;
1738 --right_size;
1739 }
1740 else if (right_size == 0 || i_right == end())
1741 {
1742 // Right is empty. The node must come from left.
1743 i_node = i_left++;
1744 --left_size;
1745 }
1746 else if (!compare(*i_right, *i_left))
1747 {
1748 // First node of left is lower or same. The node must come from left.
1749 i_node = i_left++;
1750 --left_size;
1751 }
1752 else
1753 {
1754 // First node of right is lower. The node must come from right.
1755 i_node = i_right;
1756 ++i_right;
1757 --right_size;
1758 }
1759
1760 // Add the next node to the merged head.
1761 if (i_head == end())
1762 {
1763 join(*i_head.p_node, *i_node.p_node);
1764 i_head = i_node;
1765 i_tail = i_node;
1766 }
1767 else
1768 {
1769 join(*i_tail.p_node, *i_node.p_node);
1770 i_tail = i_node;
1771 }
1772
1773 join(*i_tail.p_node, terminal_node);
1774 }
1775
1776 // Now left has stepped `list_size' places along, and right has too.
1777 i_left = i_right;
1778 }
1779
1780 // If we have done only one merge, we're finished.
1781 if (number_of_merges <= 1) // Allow for number_of_merges == 0, the empty head case
1782 {
1783 return;
1784 }
1785
1786 // Otherwise repeat, merging lists twice the size
1787 list_size *= 2;
1788 }
1789 }
1790
1791 //*************************************************************************
1793 //*************************************************************************
1795 {
1796 if (&rhs != this)
1797 {
1798 assign(rhs.cbegin(), rhs.cend());
1799 }
1800
1801 return *this;
1802 }
1803
1804#if ETL_USING_CPP11
1805 //*************************************************************************
1807 //*************************************************************************
1809 {
1810 if (&rhs != this)
1811 {
1812 this->initialise();
1813
1814 iterator itr = rhs.begin();
1815 while (itr != rhs.end())
1816 {
1817 push_back(etl::move(*itr));
1818 ++itr;
1819 }
1820
1821 rhs.initialise();
1822 }
1823
1824 return *this;
1825 }
1826#endif
1827
1828 protected:
1829
1830 //*************************************************************************
1832 //*************************************************************************
1835 {
1836 }
1837
1838 //*************************************************************************
1840 //*************************************************************************
1841 ilist(etl::ipool& node_pool, size_t max_size_, bool pool_is_shared_)
1842 : list_base(node_pool, max_size_, pool_is_shared_)
1843 {
1844 }
1845
1846 //*************************************************************************
1848 //*************************************************************************
1850 {
1851 if (this->p_node_pool != ETL_NULLPTR)
1852 {
1853 if (!empty())
1854 {
1856 {
1857 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1859 ETL_RESET_DEBUG_COUNT;;
1860 }
1861 else
1862 {
1865
1866 while (p_first != p_last)
1867 {
1868 destroy_data_node(static_cast<data_node_t&>(*p_first)); // Destroy the current node.
1869 p_first = p_first->next; // Move to the next node.
1870 }
1871 }
1872 }
1873 }
1874
1876 }
1877
1878#if ETL_USING_CPP11
1879 //*************************************************************************
1881 //*************************************************************************
1882 void move_container(ilist&& rhs)
1883 {
1884 if (&rhs != this)
1885 {
1886 this->initialise();
1887
1888 if (!rhs.empty())
1889 {
1890 // Are we using the same pool?
1891 if (this->get_node_pool() == rhs.get_node_pool())
1892 {
1893 // Just link the nodes to this list.
1894 join(terminal_node, rhs.get_head());
1895 join(rhs.get_tail(), terminal_node);
1896
1897 ETL_SET_DEBUG_COUNT(ETL_OBJECT_GET_DEBUG_COUNT(rhs));
1898
1899 // Clear the rhs.
1900 ETL_OBJECT_RESET_DEBUG_COUNT(rhs);
1901 rhs.join(rhs.terminal_node, rhs.terminal_node);
1902 }
1903 else
1904 {
1905 // Add all of the elements.
1906 etl::ilist<T>::iterator first = rhs.begin();
1907 etl::ilist<T>::iterator last = rhs.end();
1908
1909 while (first != last)
1910 {
1911 ETL_ASSERT(!full(), ETL_ERROR(list_full));
1912
1913 insert_node(terminal_node, this->allocate_data_node(etl::move(*first)));
1914 ++first;
1915 }
1916
1917 rhs.initialise();
1918 }
1919 }
1920 }
1921 }
1922#endif
1923
1924 private:
1925
1926 //*************************************************************************
1929 //*************************************************************************
1930 void move(iterator to, iterator from)
1931 {
1932 if (from == to)
1933 {
1934 return; // Can't more to before yourself!
1935 }
1936
1937 node_t& from_node = *from.p_node;
1938 node_t& to_node = *to.p_node;
1939
1940 // Disconnect the node from the list.
1941 join(*from_node.previous, *from_node.next);
1942
1943 // Attach it to the new position.
1944 join(*to_node.previous, from_node);
1945 join(from_node, to_node);
1946 }
1947
1948 //*************************************************************************
1951 //*************************************************************************
1952 void move(iterator to, iterator first, iterator last)
1953 {
1954 if ((first == to) || (last == to))
1955 {
1956 return; // Can't more to before yourself!
1957 }
1958
1959#if ETL_IS_DEBUG_BUILD
1960 // Check that we are not doing an illegal move!
1961 for (const_iterator item = first; item != last; ++item)
1962 {
1963 ETL_ASSERT(item != to, ETL_ERROR(list_iterator));
1964 }
1965#endif
1966
1967 node_t& first_node = *first.p_node;
1968 node_t& last_node = *last.p_node;
1969 node_t& to_node = *to.p_node;
1970 node_t& final_node = *last_node.previous;
1971
1972 // Disconnect the range from the list.
1973 join(*first_node.previous, last_node);
1974
1975 // Attach it to the new position.
1976 join(*to_node.previous, first_node);
1977 join(final_node, to_node);
1978 }
1979
1980 //*************************************************************************
1982 //*************************************************************************
1983 void remove_node(node_t& node)
1984 {
1985 // Disconnect the node from the list.
1986 join(*node.previous, *node.next);
1987
1988 // Destroy the pool object.
1989 destroy_data_node(static_cast<data_node_t&>(node));
1990 }
1991
1992 //*************************************************************************
1994 //*************************************************************************
1995 data_node_t& allocate_data_node(const_reference value)
1996 {
1997 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
1998
1999 data_node_t* p_data_node = allocate_data_node();
2000 ::new (&(p_data_node->value)) T(value);
2001 ETL_INCREMENT_DEBUG_COUNT;
2002
2003 return *p_data_node;
2004 }
2005
2006#if ETL_USING_CPP11
2007 //*************************************************************************
2009 //*************************************************************************
2010 data_node_t& allocate_data_node(rvalue_reference value)
2011 {
2012 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
2013
2014 data_node_t* p_data_node = allocate_data_node();
2015 ::new (&(p_data_node->value)) T(etl::move(value));
2016 ETL_INCREMENT_DEBUG_COUNT;
2017
2018 return *p_data_node;
2019 }
2020#endif
2021
2022 //*************************************************************************
2024 //*************************************************************************
2025 data_node_t* allocate_data_node()
2026 {
2027 data_node_t* (etl::ipool::*func)() = &etl::ipool::allocate<data_node_t>;
2028 return (p_node_pool->*func)();
2029 }
2030
2031 //*************************************************************************
2033 //*************************************************************************
2034 void destroy_data_node(data_node_t& node)
2035 {
2036 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(list_no_pool));
2037 node.value.~T();
2038 p_node_pool->release(&node);
2039 ETL_DECREMENT_DEBUG_COUNT;
2040 }
2041
2042 // Disable copy construction.
2043 ilist(const ilist&);
2044
2045#if defined(ETL_POLYMORPHIC_LIST) || defined(ETL_POLYMORPHIC_CONTAINERS)
2046 public:
2047 virtual ~ilist()
2048 {
2049 }
2050#else
2051 protected:
2052 ~ilist()
2053 {
2054 }
2055#endif
2056
2057 private:
2058
2059 //*************************************************************************
2061 //*************************************************************************
2062 iterator to_iterator(const_iterator itr) const
2063 {
2064 return iterator(*(const_cast<node_t*>(itr.p_node)));
2065 }
2066 };
2067
2068 //*************************************************************************
2070 //*************************************************************************
2071 template <typename T, const size_t MAX_SIZE_>
2072 class list : public etl::ilist<T>
2073 {
2074 public:
2075
2076 ETL_STATIC_ASSERT((MAX_SIZE_ > 0U), "Zero capacity etl::list is not valid");
2077
2078 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
2079
2080 public:
2081
2082 typedef T value_type;
2083 typedef T* pointer;
2084 typedef const T* const_pointer;
2085 typedef T& reference;
2086 typedef const T& const_reference;
2087#if ETL_USING_CPP11
2088 typedef T&& rvalue_reference;
2089#endif
2090 typedef size_t size_type;
2091
2092 //*************************************************************************
2094 //*************************************************************************
2096 : etl::ilist<T>(node_pool, MAX_SIZE, false)
2097 {
2098 }
2099
2100 //*************************************************************************
2102 //*************************************************************************
2104 {
2105 this->initialise();
2106 }
2107
2108 //*************************************************************************
2110 //*************************************************************************
2111 explicit list(size_t initial_size)
2112 : etl::ilist<T>(node_pool, MAX_SIZE, false)
2113 {
2114 this->assign(initial_size, T());
2115 }
2116
2117 //*************************************************************************
2119 //*************************************************************************
2120 list(size_t initial_size, const T& value)
2121 : etl::ilist<T>(node_pool, MAX_SIZE, false)
2122 {
2123 this->assign(initial_size, value);
2124 }
2125
2126 //*************************************************************************
2128 //*************************************************************************
2130 : etl::ilist<T>(node_pool, MAX_SIZE, false)
2131 {
2132 if (this != &other)
2133 {
2134 this->assign(other.cbegin(), other.cend());
2135 }
2136 }
2137
2138#if ETL_USING_CPP11
2139 //*************************************************************************
2141 //*************************************************************************
2142 list(list&& other)
2143 : etl::ilist<T>(node_pool, MAX_SIZE, false)
2144 {
2145 if (this != &other)
2146 {
2147 this->initialise();
2148
2149 typename etl::ilist<T>::iterator itr = other.begin();
2150 while (itr != other.end())
2151 {
2152 this->push_back(etl::move(*itr));
2153 ++itr;
2154 }
2155
2156 other.initialise();
2157 }
2158 }
2159#endif
2160
2161 //*************************************************************************
2163 //*************************************************************************
2164 template <typename TIterator>
2166 : ilist<T>(node_pool, MAX_SIZE, false)
2167 {
2168 this->assign(first, last);
2169 }
2170
2171#if ETL_HAS_INITIALIZER_LIST
2172 //*************************************************************************
2174 //*************************************************************************
2175 list(std::initializer_list<T> init)
2176 : ilist<T>(node_pool, MAX_SIZE, false)
2177 {
2178 this->assign(init.begin(), init.end());
2179 }
2180#endif
2181
2182 //*************************************************************************
2184 //*************************************************************************
2186 {
2187 if (&rhs != this)
2188 {
2189 this->assign(rhs.cbegin(), rhs.cend());
2190 }
2191
2192 return *this;
2193 }
2194
2195#if ETL_USING_CPP11
2196 //*************************************************************************
2198 //*************************************************************************
2200 {
2201 this->move_container(etl::move(rhs));
2202
2203 return *this;
2204 }
2205#endif
2206
2207 private:
2208
2211 };
2212
2213 template <typename T, const size_t MAX_SIZE_>
2214 ETL_CONSTANT size_t list<T, MAX_SIZE_>::MAX_SIZE;
2215
2216 //*************************************************************************
2218 //*************************************************************************
2219#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2220 template <typename... T>
2221 list(T...) -> list<typename etl::common_type_t<T...>,
2222 sizeof...(T)>;
2223#endif
2224
2225 //*************************************************************************
2227 //*************************************************************************
2228#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2229 template <typename... T>
2230 constexpr auto make_list(T... t) -> etl::list<typename etl::common_type_t<T...>, sizeof...(T)>
2231 {
2232 return { etl::forward<T>(t)... };
2233 }
2234#endif
2235
2236 //*************************************************************************
2238 //*************************************************************************
2239 template <typename T>
2240 class list_ext : public etl::ilist<T>
2241 {
2242 public:
2243
2244 typedef T value_type;
2245 typedef T* pointer;
2246 typedef const T* const_pointer;
2247 typedef T& reference;
2248 typedef const T& const_reference;
2249 typedef size_t size_type;
2250
2251 typedef typename etl::ilist<T>::data_node_t pool_type;
2252
2253 //*************************************************************************
2255 //*************************************************************************
2257 : etl::ilist<T>(true)
2258 {
2259 }
2260
2261 //*************************************************************************
2263 //*************************************************************************
2264 explicit list_ext(etl::ipool& node_pool)
2265 : etl::ilist<T>(node_pool, node_pool.max_size(), true)
2266 {
2267 }
2268
2269 //*************************************************************************
2271 //*************************************************************************
2273 {
2274 this->initialise();
2275 }
2276
2277 //*************************************************************************
2279 //*************************************************************************
2280 explicit list_ext(size_t initial_size, etl::ipool& node_pool)
2281 : etl::ilist<T>(node_pool, node_pool.max_size(), true)
2282 {
2283 this->assign(initial_size, T());
2284 }
2285
2286 //*************************************************************************
2288 //*************************************************************************
2289 list_ext(size_t initial_size, const T& value, etl::ipool& node_pool)
2290 : etl::ilist<T>(node_pool, node_pool.max_size(), true)
2291 {
2292 this->assign(initial_size, value);
2293 }
2294
2295 //*************************************************************************
2297 //*************************************************************************
2299 : etl::ilist<T>(*other.p_node_pool, other.p_node_pool->max_size(), true)
2300 {
2301 if (this != &other)
2302 {
2303 this->assign(other.cbegin(), other.cend());
2304 }
2305 }
2306
2307 //*************************************************************************
2309 //*************************************************************************
2310 list_ext(const list_ext& other, etl::ipool& node_pool)
2311 : etl::ilist<T>(node_pool, node_pool.max_size(), true)
2312 {
2313 if (this != &other)
2314 {
2315 this->assign(other.cbegin(), other.cend());
2316 }
2317 }
2318
2319#if ETL_USING_CPP11
2320 //*************************************************************************
2322 //*************************************************************************
2324 : etl::ilist<T>(*other.p_node_pool, other.p_node_pool->max_size(), true)
2325 {
2326 this->move_container(etl::move(other));
2327 }
2328
2329 //*************************************************************************
2331 //*************************************************************************
2332 list_ext(list_ext&& other, etl::ipool& node_pool)
2333 : etl::ilist<T>(node_pool, node_pool.max_size(), true)
2334 {
2335 this->move_container(etl::move(other));
2336 }
2337#endif
2338
2339 //*************************************************************************
2341 //*************************************************************************
2342 template <typename TIterator>
2344 : ilist<T>(node_pool, node_pool.max_size(), true)
2345 {
2346 this->assign(first, last);
2347 }
2348
2349#if ETL_HAS_INITIALIZER_LIST
2350 //*************************************************************************
2352 //*************************************************************************
2353 list_ext(std::initializer_list<T> init, etl::ipool& node_pool)
2354 : ilist<T>(node_pool, node_pool.max_size(), true)
2355 {
2356 this->assign(init.begin(), init.end());
2357 }
2358#endif
2359
2360 //*************************************************************************
2362 //*************************************************************************
2364 {
2365 if (&rhs != this)
2366 {
2367 this->assign(rhs.cbegin(), rhs.cend());
2368 }
2369
2370 return *this;
2371 }
2372
2373#if ETL_USING_CPP11
2374 //*************************************************************************
2376 //*************************************************************************
2378 {
2379 this->move_container(etl::move(rhs));
2380
2381 return *this;
2382 }
2383#endif
2384
2385 //*************************************************************************
2387 //*************************************************************************
2389 {
2390 // Clear the list of any current elements.
2391 if (this->get_node_pool() != ETL_NULLPTR)
2392 {
2393 this->clear();
2394 }
2395
2396 this->set_node_pool(pool);
2397 }
2398
2399 //*************************************************************************
2401 //*************************************************************************
2403 {
2404 return *this->p_node_pool;
2405 }
2406 };
2407
2408 //*************************************************************************
2413 //*************************************************************************
2414 template <typename T>
2416 {
2417 return (lhs.size() == rhs.size()) && etl::equal(lhs.begin(), lhs.end(), rhs.begin());
2418 }
2419
2420 //*************************************************************************
2425 //*************************************************************************
2426 template <typename T>
2428 {
2429 return !(lhs == rhs);
2430 }
2431
2432 //*************************************************************************
2438 //*************************************************************************
2439 template <typename T>
2441 {
2442 return etl::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
2443 }
2444
2445 //*************************************************************************
2451 //*************************************************************************
2452 template <typename T>
2454 {
2455 return (rhs < lhs);
2456 }
2457
2458 //*************************************************************************
2464 //*************************************************************************
2465 template <typename T>
2467 {
2468 return !(lhs > rhs);
2469 }
2470
2471 //*************************************************************************
2477 //*************************************************************************
2478 template <typename T>
2480 {
2481 return !(lhs < rhs);
2482 }
2483}
2484
2485#include "private/minmax_pop.h"
2486
2487#endif
const_iterator
Definition list.h:565
iterator.
Definition list.h:478
Template deduction guides.
Definition list.h:2241
list_ext(const list_ext &other, etl::ipool &node_pool)
Copy constructor. Explicit pool.
Definition list.h:2310
list_ext(size_t initial_size, etl::ipool &node_pool)
Construct from size.
Definition list.h:2280
void set_pool(etl::ipool &pool)
Set the pool instance.
Definition list.h:2388
list_ext(size_t initial_size, const T &value, etl::ipool &node_pool)
Construct from size and value.
Definition list.h:2289
list_ext(TIterator first, TIterator last, etl::ipool &node_pool, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Construct from range.
Definition list.h:2343
list_ext()
Default constructor.
Definition list.h:2256
etl::ipool & get_pool() const
Get the pool instance.
Definition list.h:2402
list_ext(etl::ipool &node_pool)
Default constructor.
Definition list.h:2264
~list_ext()
Destructor.
Definition list.h:2272
list_ext(const list_ext &other)
Copy constructor. Implicit pool.
Definition list.h:2298
A templated list implementation that uses a fixed size buffer.
Definition list.h:2073
~list()
Destructor.
Definition list.h:2103
list(const list &other)
Copy constructor.
Definition list.h:2129
list(size_t initial_size, const T &value)
Construct from size and value.
Definition list.h:2120
list(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Construct from range.
Definition list.h:2165
list(size_t initial_size)
Construct from size.
Definition list.h:2111
list()
Default constructor.
Definition list.h:2095
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:968
ETL_NODISCARD ETL_CONSTEXPR14 bool is_sorted(TIterator begin, TIterator end)
Definition algorithm.h:1685
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
ilist(etl::ipool &node_pool, size_t max_size_, bool pool_is_shared_)
Constructor.
Definition list.h:1841
const_reverse_iterator rend() const
Gets the reverse end of the list.
Definition list.h:737
void clear()
Clears the list.
Definition list.h:1331
const_iterator cbegin() const
Gets the beginning of the list.
Definition list.h:697
iterator end()
Gets the end of the list.
Definition list.h:681
void push_back(const T &value)
Pushes a value to the back of the list.
Definition list.h:983
iterator emplace(const_iterator position)
Emplaces a value to the list at the specified position.
Definition list.h:1156
ilist(bool pool_is_shared_)
Constructor.
Definition list.h:1833
reference back()
Gets a reference to the last element.
Definition list.h:777
size_t size_type
The type used for determining the size of list.
Definition list.h:155
void reverse()
Reverses the list.
Definition list.h:196
const_reverse_iterator crend() const
Gets the reverse end of the list.
Definition list.h:753
reference emplace_front(const T1 &value1)
Emplaces a value to the front of the list.
Definition list.h:899
void splice(iterator to, ilist &other, iterator from)
Splices an element from another list to this.
Definition list.h:1451
size_type size() const
Gets the size of the list.
Definition list.h:238
void sort(TCompare compare)
Definition list.h:1684
size_type available() const
Definition list.h:282
void splice(iterator to, ilist &other, iterator first, iterator last)
Splices a range of elements from another list to this.
Definition list.h:1489
void join(node_t &left, node_t &right)
Join two nodes.
Definition list.h:343
void insert(const_iterator position, size_t n, const_reference value)
Inserts 'n' copies of a value to the list at the specified position.
Definition list.h:1229
void unique(TIsEqual isEqual)
Definition list.h:1391
void insert(const_iterator position, TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Inserts a range of values to the list at the specified position.
Definition list.h:1244
const_reverse_iterator rbegin() const
Gets the reverse beginning of the list.
Definition list.h:721
list_base(bool pool_is_shared_)
The constructor that is called from derived classes.
Definition list.h:352
etl::ipool * p_node_pool
The pool of data nodes used in the list.
Definition list.h:395
size_type max_size() const
Gets the maximum possible size of the list.
Definition list.h:222
void resize(size_t n)
Resizes the list.
Definition list.h:1297
list_base(etl::ipool &node_pool_, size_type max_size_, bool pool_is_shared_)
The constructor that is called from derived classes.
Definition list.h:363
bool full() const
Checks to see if the list is full.
Definition list.h:272
reverse_iterator rend()
Gets the reverse end of the list.
Definition list.h:729
reverse_iterator rbegin()
Gets the reverse beginning of the list.
Definition list.h:713
reference emplace_front()
Emplaces a value to the front of the list.
Definition list.h:881
ilist & operator=(const ilist &rhs)
Assignment operator.
Definition list.h:1794
iterator insert(const_iterator position, const_reference value)
Inserts a value to the list at the specified position.
Definition list.h:1113
size_type MAX_SIZE
The maximum size of the list.
Definition list.h:397
node_t terminal_node
The node that acts as the list start and end.
Definition list.h:396
void push_front(const T &value)
Pushes a value to the front of the list.
Definition list.h:838
void initialise()
Initialise the list.
Definition list.h:1849
bool pool_is_shared
If true then the pool is shared between lists.
Definition list.h:398
void splice(iterator to, ilist &other)
Splices from another list to this.
Definition list.h:1419
const_iterator end() const
Gets the end of the list.
Definition list.h:689
ETL_DECLARE_DEBUG_COUNT
Internal debugging.
Definition list.h:399
reference front()
Gets a reference to the first element.
Definition list.h:761
void pop_front()
Removes a value from the front of the list.
Definition list.h:971
const_iterator begin() const
Gets the beginning of the list.
Definition list.h:673
void merge(ilist &other)
Merge another list into this one. Both lists should be sorted.
Definition list.h:1534
bool is_trivial_list() const
Is the list a trivial length?
Definition list.h:293
void assign(size_t n, const T &value)
Assigns 'n' copies of a value to the list.
Definition list.h:818
iterator erase(const_iterator first, const_iterator last)
Erases a range of elements.
Definition list.h:1271
reference emplace_front(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Emplaces a value to the front of the list.
Definition list.h:953
void set_node_pool(etl::ipool &node_pool_)
Set the node pool instance.
Definition list.h:374
reference emplace_front(const T1 &value1, const T2 &value2, const T3 &value3)
Emplaces a value to the front of the list.
Definition list.h:935
void merge(ilist &other, TCompare compare)
Merge another list into this one. Both lists should be sorted.
Definition list.h:1543
void resize(size_t n, const_reference value)
Resizes the list.
Definition list.h:1305
size_type capacity() const
Gets the maximum possible size of the list.
Definition list.h:230
reference emplace_back()
Emplaces a value to the back of the list.
Definition list.h:1023
bool empty() const
Checks to see if the list is empty.
Definition list.h:264
etl::ipool * get_node_pool()
Get the node pool instance.
Definition list.h:383
iterator begin()
Gets the beginning of the list.
Definition list.h:665
void sort()
Definition list.h:1653
const_reference back() const
Gets a reference to the last element.
Definition list.h:785
void unique()
Definition list.h:1381
const_reference front() const
Gets a const reference to the first element.
Definition list.h:769
node_t & get_head()
Get the head node.
Definition list.h:301
const node_t & get_head() const
Get the head node.
Definition list.h:309
void insert_node(node_t &position, node_t &node)
Insert a node before 'position'.
Definition list.h:333
const node_t & get_tail() const
Get the tail node.
Definition list.h:325
const_iterator cend() const
Gets the end of the list.
Definition list.h:705
const_reverse_iterator crbegin() const
Gets the reverse beginning of the list.
Definition list.h:745
~list_base()
Destructor.
Definition list.h:391
void remove_if(TPredicate predicate)
Removes according to a predicate.
Definition list.h:1360
void assign(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Definition list.h:796
node_t & get_tail()
Get the tail node.
Definition list.h:317
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition list.h:1259
bool has_shared_pool() const
true if the list has a shared pool.
Definition list.h:188
void pop_back()
Removes a value from the back of the list.
Definition list.h:1101
reference emplace_front(const T1 &value1, const T2 &value2)
Emplaces a value to the front of the list.
Definition list.h:917
Definition list.h:408
Definition list.h:152
Definition list.h:96
Definition list.h:68
Definition list.h:82
Definition list.h:110
Definition list.h:138
Definition list.h:124
size_t size() const
Returns the number of allocated items in the pool.
Definition ipool.h:301
void release_all()
Release all objects in the pool.
Definition ipool.h:248
bool full() const
Definition ipool.h:319
size_t max_size() const
Returns the maximum number of items in the pool.
Definition ipool.h:269
void release(const void *const p_object)
Definition ipool.h:239
size_t available() const
Returns the number of free items in the pool.
Definition ipool.h:293
Definition ipool.h:102
Definition pool.h:54
enable_if
Definition type_traits_generator.h:1186
is_integral
Definition type_traits_generator.h:996
bitset_ext
Definition absolute.h:38
bool operator>(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:693
size_t max_size() const
Returns the maximum number of items in the variant_pool.
Definition variant_pool_generator.h:395
bool operator>=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:705
bool operator!=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:654
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition array.h:630
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:642
bool operator<(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:666
bool operator<=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:681
Definition compare.h:51
The data node element in the list.
Definition list.h:429
Definition type_traits_generator.h:2096
iterator
Definition iterator.h:399
The node element in the list.
Definition list.h:161
void reverse()
Reverses the previous & next pointers.
Definition list.h:174
node_t()
Constructor.
Definition list.h:165
pair holds two objects of arbitrary type
Definition utility.h:164