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