Embedded Template Library 1.0
forward_list.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 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_FORWARD_LIST_INCLUDED
32#define ETL_FORWARD_LIST_INCLUDED
33
34#include "platform.h"
35#include "algorithm.h"
36#include "iterator.h"
37#include "functional.h"
38#include "utility.h"
39#include "pool.h"
40#include "exception.h"
41#include "error_handler.h"
42#include "debug_count.h"
43#include "nullptr.h"
44#include "type_traits.h"
45#include "memory.h"
46#include "iterator.h"
47#include "static_assert.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 //***************************************************************************
68 {
69 public:
70
71 forward_list_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
72 : exception(reason_, file_name_, line_number_)
73 {
74 }
75 };
76
77 //***************************************************************************
80 //***************************************************************************
82 {
83 public:
84
85 forward_list_full(string_type file_name_, numeric_type line_number_)
86 : etl::forward_list_exception(ETL_ERROR_TEXT("forward_list:full", ETL_FORWARD_LIST_FILE_ID"A"), file_name_, line_number_)
87 {
88 }
89 };
90
91 //***************************************************************************
94 //***************************************************************************
96 {
97 public:
98
99 forward_list_empty(string_type file_name_, numeric_type line_number_)
100 : etl::forward_list_exception(ETL_ERROR_TEXT("forward_list:empty", ETL_FORWARD_LIST_FILE_ID"B"), file_name_, line_number_)
101 {
102 }
103 };
104
105 //***************************************************************************
108 //***************************************************************************
110 {
111 public:
112
113 forward_list_iterator(string_type file_name_, numeric_type line_number_)
114 : etl::forward_list_exception(ETL_ERROR_TEXT("forward_list:iterator", ETL_FORWARD_LIST_FILE_ID"C"), file_name_, line_number_)
115 {
116 }
117 };
118
119 //***************************************************************************
122 //***************************************************************************
124 {
125 public:
126
127 forward_list_no_pool(string_type file_name_, numeric_type line_number_)
128 : forward_list_exception(ETL_ERROR_TEXT("list:no pool", ETL_FORWARD_LIST_FILE_ID"D"), file_name_, line_number_)
129 {
130 }
131 };
132
133 //***************************************************************************
136 //***************************************************************************
138 {
139 protected:
140
141 //*************************************************************************
143 //*************************************************************************
144 struct node_t
145 {
146 node_t()
147 : next(ETL_NULLPTR)
148 {
149 }
150
151 node_t* next;
152 };
153
154 public:
155
156 typedef size_t size_type;
157
158 //*************************************************************************
160 //*************************************************************************
161 bool has_shared_pool() const
162 {
163 return pool_is_shared;
164 }
165
166 //*************************************************************************
168 //*************************************************************************
170 {
171 return MAX_SIZE;
172 }
173
174 //*************************************************************************
176 //*************************************************************************
178 {
179 return MAX_SIZE;
180 }
181
182 //*************************************************************************
184 //*************************************************************************
186 {
187 if (has_shared_pool())
188 {
189 // We have to count what we actually own.
190 size_type count = 0;
191
192 node_t* p_node = start_node.next;
193
194 while (p_node != ETL_NULLPTR)
195 {
196 ++count;
197 p_node = p_node->next;
198 }
199
200 return count;
201 }
202 else
203 {
204 return p_node_pool->size();
205 }
206 }
207
208 //*************************************************************************
210 //*************************************************************************
211 bool empty() const
212 {
213 return (start_node.next == ETL_NULLPTR);
214 }
215
216 //*************************************************************************
218 //*************************************************************************
219 bool full() const
220 {
221 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(forward_list_no_pool));
222 return p_node_pool->full();
223 }
224
225 //*************************************************************************
228 //*************************************************************************
229 size_t available() const
230 {
231 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(forward_list_no_pool));
232 return p_node_pool->available();
233 }
234
235 //*************************************************************************
237 //*************************************************************************
238 void reverse()
239 {
240 if (is_trivial_list())
241 {
242 return;
243 }
244
245 node_t* p_last = &start_node;
246 node_t* p_current = p_last->next;
247 node_t* p_next = p_current->next;
248
249 p_current->next = ETL_NULLPTR;
250
251 while (p_next != ETL_NULLPTR)
252 {
253 p_last = p_current;
254 p_current = p_next;
255 p_next = p_current->next;
256
257 p_current->next = p_last;
258 }
259
260 join(&start_node, p_current);
261 }
262
263 protected:
264
265 //*************************************************************************
267 //*************************************************************************
268 forward_list_base(bool pool_is_shared_)
269 : p_node_pool(ETL_NULLPTR),
270 MAX_SIZE(0),
271 pool_is_shared(pool_is_shared_)
272 {
273 }
274
275 //*************************************************************************
277 //*************************************************************************
278 forward_list_base(etl::ipool& node_pool_, size_type max_size_, bool pool_is_shared_)
279 : p_node_pool(&node_pool_),
280 MAX_SIZE(max_size_),
281 pool_is_shared(pool_is_shared_)
282 {
283 }
284
285 //*************************************************************************
287 //*************************************************************************
289 {
290 }
291
292 //*************************************************************************
294 //*************************************************************************
296 {
297 return start_node.next;
298 }
299
300 //*************************************************************************
302 //*************************************************************************
303 const node_t* get_head() const
304 {
305 return start_node.next;
306 }
307
308 //*************************************************************************
310 //*************************************************************************
311 inline void insert_node_after(node_t& position, node_t& node)
312 {
313 // Connect to the forward_list.
314 join(&node, position.next);
315 join(&position, &node);
316 }
317
318 //*************************************************************************
320 //*************************************************************************
321 bool is_trivial_list() const
322 {
323 return (size() < 2);
324 }
325
326 //*************************************************************************
328 //*************************************************************************
329 void join(node_t* left, node_t* right)
330 {
331 left->next = right;
332 }
333
334 //*************************************************************************
336 //*************************************************************************
337 void set_node_pool(etl::ipool& node_pool_)
338 {
339 p_node_pool = &node_pool_;
341 }
342
343 //*************************************************************************
345 //*************************************************************************
347 {
348 return p_node_pool;
349 }
350
355 ETL_DECLARE_DEBUG_COUNT
356 };
357
358 //***************************************************************************
361 //***************************************************************************
362 template <typename T>
364 {
365 public:
366
367 typedef T value_type;
368 typedef T* pointer;
369 typedef const T* const_pointer;
370 typedef T& reference;
371 typedef const T& const_reference;
372 typedef size_t size_type;
373
374#if ETL_USING_CPP11
375 typedef T&& rvalue_reference;
376#endif
377
378 protected:
379
380 //*************************************************************************
382 //*************************************************************************
383 struct data_node_t : public node_t
384 {
385 explicit data_node_t(const T& value_)
386 : value(value_)
387 {}
388
389 T value;
390 };
391
392 public:
393
394 //*************************************************************************
396 //*************************************************************************
397 class iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, T>
398 {
399 public:
400
401 friend class iforward_list;
402 friend class const_iterator;
403
404 iterator()
405 : p_node(ETL_NULLPTR)
406 {
407 }
408
409 iterator(node_t* node)
410 : p_node(node)
411 {
412 }
413
414 iterator(const iterator& other)
415 : p_node(other.p_node)
416 {
417 }
418
419 iterator& operator ++()
420 {
421 p_node = p_node->next;
422 return *this;
423 }
424
425 iterator operator ++(int)
426 {
427 iterator temp(*this);
428 p_node = p_node->next;
429 return temp;
430 }
431
432 iterator operator =(const iterator& other)
433 {
434 p_node = other.p_node;
435 return *this;
436 }
437
438 reference operator *() const
439 {
440 return iforward_list::data_cast(p_node)->value;
441 }
442
443 pointer operator &() const
444 {
445 return &(iforward_list::data_cast(p_node)->value);
446 }
447
448 pointer operator ->() const
449 {
450 return &(iforward_list::data_cast(p_node)->value);
451 }
452
453 friend bool operator == (const iterator& lhs, const iterator& rhs)
454 {
455 return lhs.p_node == rhs.p_node;
456 }
457
458 friend bool operator != (const iterator& lhs, const iterator& rhs)
459 {
460 return !(lhs == rhs);
461 }
462
463 private:
464
465 node_t* p_node;
466 };
467
468 //*************************************************************************
470 //*************************************************************************
471 class const_iterator : public etl::iterator<ETL_OR_STD::forward_iterator_tag, const T>
472 {
473 public:
474
475 friend class iforward_list;
476
478 : p_node(ETL_NULLPTR)
479 {
480 }
481
483 : p_node(node)
484 {
485 }
486
487 const_iterator(const node_t* node)
488 : p_node(node)
489 {
490 }
491
492 const_iterator(const typename iforward_list::iterator& other)
493 : p_node(other.p_node)
494 {
495 }
496
497 const_iterator(const const_iterator& other)
498 : p_node(other.p_node)
499 {
500 }
501
502 const_iterator& operator ++()
503 {
504 p_node = p_node->next;
505 return *this;
506 }
507
508 const_iterator operator ++(int)
509 {
510 const_iterator temp(*this);
511 p_node = p_node->next;
512 return temp;
513 }
514
515 const_iterator& operator =(const const_iterator& other)
516 {
517 p_node = other.p_node;
518 return *this;
519 }
520
521 const_reference operator *() const
522 {
523 return iforward_list::data_cast(p_node)->value;
524 }
525
526 const_pointer operator &() const
527 {
528 return &(iforward_list::data_cast(p_node)->value);
529 }
530
531 const_pointer operator ->() const
532 {
533 return &(iforward_list::data_cast(p_node)->value);
534 }
535
536 friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
537 {
538 return lhs.p_node == rhs.p_node;
539 }
540
541 friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
542 {
543 return !(lhs == rhs);
544 }
545
546 private:
547
548 const node_t* p_node;
549 };
550
551 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
552
553 //*************************************************************************
555 //*************************************************************************
557 {
558 return iterator(get_head());
559 }
560
561 //*************************************************************************
563 //*************************************************************************
565 {
566 return const_iterator(get_head());
567 }
568
569 //*************************************************************************
571 //*************************************************************************
573 {
574 return iterator(&start_node);
575 }
576
577 //*************************************************************************
579 //*************************************************************************
581 {
582 return const_iterator(&start_node);
583 }
584
585 //*************************************************************************
587 //*************************************************************************
589 {
590 return const_iterator(get_head());
591 }
592
593 //*************************************************************************
595 //*************************************************************************
597 {
598 return iterator();
599 }
600
601 //*************************************************************************
603 //*************************************************************************
605 {
606 return const_iterator();
607 }
608
609 //*************************************************************************
611 //*************************************************************************
613 {
614 return const_iterator();
615 }
616
617 //*************************************************************************
619 //*************************************************************************
620 void clear()
621 {
622 initialise();
623 }
624
625 //*************************************************************************
627 //*************************************************************************
628 reference front()
629 {
630 return data_cast(*get_head()).value;
631 }
632
633 //*************************************************************************
635 //*************************************************************************
636 const_reference front() const
637 {
638 return data_cast(*get_head()).value;
639 }
640
641 //*************************************************************************
645 //*************************************************************************
646 template <typename TIterator>
647 void assign(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral<TIterator>::value, int>::type = 0)
648 {
649#if ETL_IS_DEBUG_BUILD
650 difference_type d = etl::distance(first, last);
651 ETL_ASSERT(d >= 0, ETL_ERROR(forward_list_iterator));
652#endif
653
654 initialise();
655
656 node_t* p_last_node = &start_node;
657
658 // Add all of the elements.
659 while (first != last)
660 {
661 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
662
663 data_node_t& data_node = allocate_data_node(*first);
664 ++first;
665 join(p_last_node, &data_node);
666 data_node.next = ETL_NULLPTR;
667 p_last_node = &data_node;
668 }
669 }
670
671 //*************************************************************************
673 //*************************************************************************
674 void assign(size_t n, const T& value)
675 {
676 ETL_ASSERT(n <= MAX_SIZE, ETL_ERROR(forward_list_full));
677
678 initialise();
679
680 node_t* p_last_node = &start_node;
681
682 // Add all of the elements.
683 while (size() < n)
684 {
685 data_node_t& data_node = allocate_data_node(value);
686 join(p_last_node, &data_node);
687 data_node.next = ETL_NULLPTR;
688 p_last_node = &data_node;
689 }
690 }
691
692 //*************************************************************************
694 //*************************************************************************
695 void push_front(const T& value)
696 {
697#if defined(ETL_CHECK_PUSH_POP)
698 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
699#endif
700
701 data_node_t& data_node = allocate_data_node(value);
702 insert_node_after(start_node, data_node);
703 }
704
705#if ETL_USING_CPP11
706 //*************************************************************************
708 //*************************************************************************
709 void push_front(rvalue_reference value)
710 {
711#if defined(ETL_CHECK_PUSH_POP)
712 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
713#endif
714
715 data_node_t& data_node = allocate_data_node(etl::move(value));
716 insert_node_after(start_node, data_node);
717 }
718#endif
719
720#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
721 //*************************************************************************
723 //*************************************************************************
724 template <typename ... Args>
725 reference emplace_front(Args && ... args)
726 {
727#if defined(ETL_CHECK_PUSH_POP)
728 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
729#endif
730 data_node_t* p_data_node = allocate_data_node();
731 ::new (&(p_data_node->value)) T(etl::forward<Args>(args)...);
732 ETL_INCREMENT_DEBUG_COUNT
733 insert_node_after(start_node, *p_data_node);
734 return front();
735 }
736#else
737 //*************************************************************************
739 //*************************************************************************
740 template <typename T1>
741 reference emplace_front(const T1& value1)
742 {
743#if defined(ETL_CHECK_PUSH_POP)
744 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
745#endif
746 data_node_t* p_data_node = allocate_data_node();
747 ::new (&(p_data_node->value)) T(value1);
748 ETL_INCREMENT_DEBUG_COUNT
749 insert_node_after(start_node, *p_data_node);
750 return front();
751 }
752
753 //*************************************************************************
755 //*************************************************************************
756 template <typename T1, typename T2>
757 reference emplace_front(const T1& value1, const T2& value2)
758 {
759#if defined(ETL_CHECK_PUSH_POP)
760 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
761#endif
762 data_node_t* p_data_node = allocate_data_node();
763 ::new (&(p_data_node->value)) T(value1, value2);
764 ETL_INCREMENT_DEBUG_COUNT
765 insert_node_after(start_node, *p_data_node);
766 return front();
767 }
768
769 //*************************************************************************
771 //*************************************************************************
772 template <typename T1, typename T2, typename T3>
773 reference emplace_front(const T1& value1, const T2& value2, const T3& value3)
774 {
775#if defined(ETL_CHECK_PUSH_POP)
776 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
777#endif
778 data_node_t* p_data_node = allocate_data_node();
779 ::new (&(p_data_node->value)) T(value1, value2, value3);
780 ETL_INCREMENT_DEBUG_COUNT
781 insert_node_after(start_node, *p_data_node);
782 return front();
783 }
784
785 //*************************************************************************
787 //*************************************************************************
788 template <typename T1, typename T2, typename T3, typename T4>
789 reference emplace_front(const T1& value1, const T2& value2, const T3& value3, const T4& value4)
790 {
791#if defined(ETL_CHECK_PUSH_POP)
792 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
793#endif
794 data_node_t* p_data_node = allocate_data_node();
795 ::new (&(p_data_node->value)) T(value1, value2, value3, value4);
796 ETL_INCREMENT_DEBUG_COUNT
797 insert_node_after(start_node, *p_data_node);
798 return front();
799 }
800#endif // ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
801
802 //*************************************************************************
804 //*************************************************************************
806 {
807#if defined(ETL_CHECK_PUSH_POP)
808 ETL_ASSERT(!empty(), ETL_ERROR(forward_list_empty));
809#endif
810 remove_node_after(start_node);
811 }
812
813 //*************************************************************************
815 //*************************************************************************
816 void resize(size_t n)
817 {
818 resize(n, T());
819 }
820
821 //*************************************************************************
825 //*************************************************************************
826 void resize(size_t n, T value)
827 {
828 ETL_ASSERT(n <= MAX_SIZE, ETL_ERROR(forward_list_full));
829
830 if (n == 0U)
831 {
832 clear();
833 }
834 else if (empty())
835 {
836 assign(n, value);
837 }
838 else
839 {
840 size_t i = 0UL;
841 iterator i_node = begin();
842 iterator i_last_node;
843
844 // Find where we're currently at.
845 while ((i < n) && (i_node != end()))
846 {
847 ++i;
848 i_last_node = i_node;
849 ++i_node;
850 }
851
852 if (i_node != end())
853 {
854 // Reduce.
855 erase_after(i_last_node, end());
856 }
857 else if (i_node == end())
858 {
859 // Increase.
860 while (i < n)
861 {
862 i_last_node = insert_after(i_last_node, value);
863 ++i;
864 }
865 }
866 }
867 }
868
869 //*************************************************************************
871 //*************************************************************************
872 iterator insert_after(const_iterator position, const T& value)
873 {
874 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
875
876 data_node_t& data_node = allocate_data_node(value);
877 insert_node_after(*to_iterator(position).p_node, data_node);
878
879 return iterator(&data_node);
880 }
881
882#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
883 //*************************************************************************
885 //*************************************************************************
886 template <typename ... Args>
887 iterator emplace_after(const_iterator position, Args && ... args)
888 {
889 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
890
891 data_node_t* p_data_node = allocate_data_node();
892 ::new (&(p_data_node->value)) T(etl::forward<Args>(args)...);
893 ETL_INCREMENT_DEBUG_COUNT
894 insert_node_after(*to_iterator(position).p_node, *p_data_node);
895
896 return iterator(p_data_node);
897 }
898#else
899 //*************************************************************************
901 //*************************************************************************
902 template <typename T1>
903 iterator emplace_after(const_iterator position, const T1& value1)
904 {
905 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
906
907 data_node_t* p_data_node = allocate_data_node();
908 ::new (&(p_data_node->value)) T(value1);
909 ETL_INCREMENT_DEBUG_COUNT
910 insert_node_after(*position.p_node, *p_data_node);
911
912 return iterator(p_data_node);
913 }
914
915 //*************************************************************************
917 //*************************************************************************
918 template <typename T1, typename T2>
919 iterator emplace_after(const_iterator position, const T1& value1, const T2& value2)
920 {
921 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
922
923 data_node_t* p_data_node = allocate_data_node();
924 ::new (&(p_data_node->value)) T(value1, value2);
925 ETL_INCREMENT_DEBUG_COUNT
926 insert_node_after(*position.p_node, *p_data_node);
927
928 return iterator(p_data_node);
929 }
930
931 //*************************************************************************
933 //*************************************************************************
934 template <typename T1, typename T2, typename T3>
935 iterator emplace_after(const_iterator position, const T1& value1, const T2& value2, const T3& value3)
936 {
937 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
938
939 data_node_t* p_data_node = allocate_data_node();
940 ::new (&(p_data_node->value)) T(value1, value2, value3);
941 ETL_INCREMENT_DEBUG_COUNT
942 insert_node_after(*position.p_node, *p_data_node);
943
944 return iterator(p_data_node);
945 }
946
947 //*************************************************************************
949 //*************************************************************************
950 template <typename T1, typename T2, typename T3, typename T4>
951 iterator emplace_after(const_iterator position, const T1& value1, const T2& value2, const T3& value3, const T4& value4)
952 {
953 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
954
955 data_node_t* p_data_node = allocate_data_node();
956 ::new (&(p_data_node->value)) T(value1, value2, value3, value4);
957 ETL_INCREMENT_DEBUG_COUNT
958 insert_node_after(*position.p_node, *p_data_node);
959
960 return iterator(p_data_node);
961 }
962#endif // ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
963
964 //*************************************************************************
966 //*************************************************************************
967 iterator insert_after(const_iterator position, size_t n, const T& value)
968 {
969 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
970
971 for (size_t i = 0UL; !full() && (i < n); ++i)
972 {
973 // Set up the next free node.
974 data_node_t& data_node = allocate_data_node(value);
975 insert_node_after(*to_iterator(position).p_node, data_node);
976 }
977
978 if (n > 0U)
979 {
980 ++position;
981 }
982
983 return to_iterator(position);
984 }
985
986 //*************************************************************************
988 //*************************************************************************
989 template <typename TIterator>
990 iterator insert_after(const_iterator position, TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral<TIterator>::value, int>::type = 0)
991 {
992#if ETL_IS_DEBUG_BUILD
993 difference_type d = etl::distance(first, last);
994 ETL_ASSERT((d + size()) <= MAX_SIZE, ETL_ERROR(forward_list_full));
995#endif
996
997 while (first != last)
998 {
999 // Set up the next free node.
1000 data_node_t& data_node = allocate_data_node(*first);
1001 ++first;
1002 insert_node_after(*to_iterator(position).p_node, data_node);
1003 ++position;
1004 }
1005
1006 return to_iterator(position);
1007 }
1008
1009 //*************************************************************************
1011 //*************************************************************************
1013 {
1014 iterator next(position);
1015 if (next != end())
1016 {
1017 ++next;
1018 if (next != end())
1019 {
1020 ++next;
1021 remove_node_after(*position.p_node);
1022 }
1023 }
1024
1025 return next;
1026 }
1027
1028 //*************************************************************************
1030 //*************************************************************************
1032 {
1033 iterator next(position);
1034 if (next != end())
1035 {
1036 ++next;
1037 if (next != end())
1038 {
1039 ++next;
1040 remove_node_after(*position.p_node);
1041 }
1042 }
1043
1044 return next;
1045 }
1046
1047 //*************************************************************************
1049 //*************************************************************************
1051 {
1052 if (first != end() && (first != last))
1053 {
1054 node_t* p_first = to_iterator(first).p_node;
1055 node_t* p_last = to_iterator(last).p_node;
1056 node_t* p_next = p_first->next;
1057
1058 // Join the ends.
1059 join(p_first, p_last);
1060
1061 p_first = p_next;
1062
1063 // Erase the ones in between.
1064 while (p_first != p_last)
1065 {
1066 p_next = p_first->next; // Remember the next node.
1067 destroy_data_node(static_cast<data_node_t&>(*p_first)); // Destroy the pool object.
1068 p_first = p_next; // Move to the next node.
1069 }
1070
1071 if (p_next == ETL_NULLPTR)
1072 {
1073 return end();
1074 }
1075 else
1076 {
1077 return iterator(p_last);
1078 }
1079 }
1080 else
1081 {
1082 return end();
1083 }
1084 }
1085
1086 //*************************************************************************
1089 //*************************************************************************
1090 void move_after(const_iterator from_before, const_iterator to_before)
1091 {
1092 if (from_before == to_before) // Can't move to after yourself!
1093 {
1094 return;
1095 }
1096
1097 node_t* p_from_before = const_cast<node_t*>(from_before.p_node); // We're not changing the value, just it's position.
1098 node_t* p_to_before = const_cast<node_t*>(to_before.p_node); // We're not changing the value, just it's position.
1099
1100 node_t* p_from = p_from_before->next;
1101
1102 // Disconnect from the list.
1103 join(p_from_before, p_from->next);
1104
1105 // Attach it to the new position.
1106 join(p_from, p_to_before->next);
1107 join(p_to_before, p_from);
1108 }
1109
1110 //*************************************************************************
1113 //*************************************************************************
1114 void move_after(const_iterator first_before, const_iterator last, const_iterator to_before)
1115 {
1116 if ((first_before == to_before) || (last == to_before))
1117 {
1118 return; // Can't more to before yourself!
1119 }
1120
1121//#if ETL_IS_DEBUG_BUILD
1122 // Check that we are not doing an illegal move!
1123 for (const_iterator item = first_before; item != last; ++item)
1124 {
1125 ETL_ASSERT(item != to_before, ETL_ERROR(forward_list_iterator));
1126 }
1127//#endif
1128
1129 node_t* p_first_before = const_cast<node_t*>(first_before.p_node); // We're not changing the value, just it's position.
1130 node_t* p_last = const_cast<node_t*>(last.p_node); // We're not changing the value, just it's position.
1131 node_t* p_to_before = const_cast<node_t*>(to_before.p_node); // We're not changing the value, just it's position.
1132 node_t* p_first = p_first_before->next;
1133 node_t* p_final = p_first_before;
1134
1135 // Find the last node that will be moved.
1136 while (p_final->next != p_last)
1137 {
1138 p_final = p_final->next;
1139 }
1140
1141 // Disconnect from the list.
1142 join(p_first_before, p_final->next);
1143
1144 // Attach it to the new position.
1145 join(p_final, p_to_before->next);
1146 join(p_to_before, p_first);
1147 }
1148
1149 //*************************************************************************
1152 //*************************************************************************
1153 void unique()
1154 {
1156 }
1157
1158 //*************************************************************************
1161 //*************************************************************************
1162 template <typename TIsEqual>
1163 void unique(TIsEqual isEqual)
1164 {
1165 if (empty())
1166 {
1167 return;
1168 }
1169
1170 node_t* last = get_head();
1171 node_t* current = last->next;
1172
1173 while (current != ETL_NULLPTR)
1174 {
1175 // Is this value the same as the last?
1176 if (isEqual(data_cast(current)->value, data_cast(last)->value))
1177 {
1178 remove_node_after(*last);
1179 }
1180 else
1181 {
1182 // Move on one.
1183 last = current;
1184 }
1185
1186 current = last->next;
1187 }
1188 }
1189
1190 //*************************************************************************
1193 //*************************************************************************
1194 void sort()
1195 {
1196 sort(etl::less<T>());
1197 }
1198
1199 //*************************************************************************
1223 //*************************************************************************
1224 template <typename TCompare>
1225 void sort(TCompare compare)
1226 {
1227 iterator p_left;
1228 iterator p_right;
1229 iterator p_node;
1230 iterator p_head;
1231 iterator p_tail;
1232 int list_size = 1;
1233 int number_of_merges;
1234 int left_size;
1235 int right_size;
1236
1237 if (is_trivial_list())
1238 {
1239 return;
1240 }
1241
1242 while (true)
1243 {
1244 p_left = begin();
1245 p_head = before_begin();
1246 p_tail = before_begin();
1247
1248 number_of_merges = 0; // Count the number of merges we do in this pass.
1249
1250 while (p_left != end())
1251 {
1252 ++number_of_merges; // There exists a merge to be done.
1253 p_right = p_left;
1254 left_size = 0;
1255
1256 // Step 'list_size' places along from left
1257 for (int i = 0; i < list_size; ++i)
1258 {
1259 ++left_size;
1260
1261 ++p_right;
1262
1263 if (p_right == end())
1264 {
1265 break;
1266 }
1267 }
1268
1269 // If right hasn't fallen off end, we have two lists to merge.
1270 right_size = list_size;
1271
1272 // Now we have two lists. Merge them.
1273 while (left_size > 0 || (right_size > 0 && p_right != end()))
1274 {
1275 // Decide whether the next node of merge comes from left or right.
1276 if (left_size == 0)
1277 {
1278 // Left is empty. The node must come from right.
1279 p_node = p_right;
1280 ++p_right;
1281 --right_size;
1282 }
1283 else if (right_size == 0 || p_right == end())
1284 {
1285 // Right is empty. The node must come from left.
1286 p_node = p_left;
1287 ++p_left;
1288 --left_size;
1289 }
1290 else if (!compare(*p_right, *p_left))
1291 {
1292 // First node of left is lower or same. The node must come from left.
1293 p_node = p_left;
1294 ++p_left;
1295 --left_size;
1296 }
1297 else
1298 {
1299 // First node of right is lower. The node must come from right.
1300 p_node = p_right;
1301 ++p_right;
1302 --right_size;
1303 }
1304
1305 // Add the next node to the merged head.
1306 if (p_head == before_begin())
1307 {
1308 join(p_head.p_node, p_node.p_node);
1309 p_head = p_node;
1310 p_tail = p_node;
1311 }
1312 else
1313 {
1314 join(p_tail.p_node, p_node.p_node);
1315 p_tail = p_node;
1316 }
1317
1318 p_tail.p_node->next = ETL_NULLPTR;
1319 }
1320
1321 // Now left has stepped `list_size' places along, and right has too.
1322 p_left = p_right;
1323 }
1324
1325 // If we have done only one merge, we're finished.
1326 if (number_of_merges <= 1) // Allow for number_of_merges == 0, the empty head case
1327 {
1328 return;
1329 }
1330
1331 // Otherwise repeat, merging lists twice the size
1332 list_size *= 2;
1333 }
1334 }
1335
1336 //*************************************************************************
1337 // Removes the values specified.
1338 //*************************************************************************
1339 void remove(const T& value)
1340 {
1341 iterator i_item = begin();
1342 iterator i_last_item = before_begin();
1343
1344 while (i_item != end())
1345 {
1346 if (*i_item == value)
1347 {
1348 i_item = erase_after(i_last_item);
1349 }
1350 else
1351 {
1352 ++i_item;
1353 ++i_last_item;
1354 }
1355 }
1356 }
1357
1358 //*************************************************************************
1360 //*************************************************************************
1361 template <typename TPredicate>
1362 void remove_if(TPredicate predicate)
1363 {
1364 iterator i_item = begin();
1365 iterator i_last_item = before_begin();
1366
1367 while (i_item != end())
1368 {
1369 if (predicate(*i_item))
1370 {
1371 i_item = erase_after(i_last_item);
1372 }
1373 else
1374 {
1375 ++i_item;
1376 ++i_last_item;
1377 }
1378 }
1379 }
1380
1381 //*************************************************************************
1383 //*************************************************************************
1385 {
1386 if (&rhs != this)
1387 {
1388 assign(rhs.cbegin(), rhs.cend());
1389 }
1390
1391 return *this;
1392 }
1393
1394#if ETL_USING_CPP11
1395 //*************************************************************************
1397 //*************************************************************************
1399 {
1400 move_container(etl::move(rhs));
1401
1402 return *this;
1403 }
1404#endif
1405
1406 protected:
1407
1408 //*************************************************************************
1410 //*************************************************************************
1411 iforward_list(bool pool_is_shared_)
1412 : forward_list_base(pool_is_shared_)
1413 {
1414 }
1415
1416 //*************************************************************************
1418 //*************************************************************************
1419 iforward_list(etl::ipool& node_pool, size_t max_size_, bool pool_is_shared_)
1420 : forward_list_base(node_pool, max_size_, pool_is_shared_)
1421 {
1422 }
1423
1424 //*************************************************************************
1426 //*************************************************************************
1428 {
1429 if (!empty())
1430 {
1432 {
1433 ETL_ASSERT(p_node_pool != ETL_NULLPTR, ETL_ERROR(forward_list_no_pool));
1435 ETL_RESET_DEBUG_COUNT
1436 }
1437 else
1438 {
1439 node_t* p_first = start_node.next;
1440 node_t* p_next;
1441
1442 // Erase the ones in between.
1443 while (p_first != ETL_NULLPTR)
1444 {
1445 p_next = p_first->next; // Remember the next node.
1446 destroy_data_node(static_cast<data_node_t&>(*p_first)); // Destroy the pool object.
1447 p_first = p_next; // Move to the next node.
1448 }
1449 }
1450 }
1451
1452 start_node.next = ETL_NULLPTR;
1453 }
1454
1455 //*************************************************************************
1457 //*************************************************************************
1458 data_node_t& allocate_data_node(const_reference value)
1459 {
1460 data_node_t* p_node = allocate_data_node();
1461 ::new (&(p_node->value)) T(value);
1462 ETL_INCREMENT_DEBUG_COUNT
1463
1464 return *p_node;
1465 }
1466
1467#if ETL_USING_CPP11
1468 //*************************************************************************
1470 //*************************************************************************
1471 data_node_t& allocate_data_node(rvalue_reference value)
1472 {
1473 data_node_t* p_node = allocate_data_node();
1474 ::new (&(p_node->value)) T(etl::move(value));
1475 ETL_INCREMENT_DEBUG_COUNT
1476
1477 return *p_node;
1478 }
1479#endif
1480
1481#if ETL_USING_CPP11
1482 //*************************************************************************
1484 //*************************************************************************
1485 void move_container(iforward_list&& rhs)
1486 {
1487 if (&rhs != this)
1488 {
1489 this->initialise();
1490
1491 if (!rhs.empty())
1492 {
1493 // Are we using the same pool?
1494 if (this->get_node_pool() == rhs.get_node_pool())
1495 {
1496 // Just link the nodes to this list.
1497 this->start_node.next = rhs.start_node.next;
1498
1499 ETL_SET_DEBUG_COUNT(ETL_OBJECT_GET_DEBUG_COUNT(rhs));
1500
1501 ETL_OBJECT_RESET_DEBUG_COUNT(rhs);
1502 rhs.start_node.next = ETL_NULLPTR;
1503 }
1504 else
1505 {
1506 node_t* p_last_node = &this->start_node;
1507
1508 // Add all of the elements.
1509 etl::iforward_list<T>::iterator first = rhs.begin();
1510 etl::iforward_list<T>::iterator last = rhs.end();
1511
1512 while (first != last)
1513 {
1514 ETL_ASSERT(!full(), ETL_ERROR(forward_list_full));
1515
1516 data_node_t& data_node = this->allocate_data_node(etl::move(*first));
1517 ++first;
1518 join(p_last_node, &data_node);
1519 data_node.next = ETL_NULLPTR;
1520 p_last_node = &data_node;
1521 }
1522
1523 rhs.initialise();
1524 }
1525 }
1526 }
1527 }
1528#endif
1529
1530 private:
1531
1532 //*************************************************************************
1534 //*************************************************************************
1535 static data_node_t* data_cast(node_t* p_node)
1536 {
1537 return static_cast<data_node_t*>(p_node);
1538 }
1539
1540 //*************************************************************************
1542 //*************************************************************************
1543 static data_node_t& data_cast(node_t& node)
1544 {
1545 return static_cast<data_node_t&>(node);
1546 }
1547
1548 //*************************************************************************
1550 //*************************************************************************
1551 static const data_node_t* data_cast(const node_t* p_node)
1552 {
1553 return static_cast<const data_node_t*>(p_node);
1554 }
1555
1556 //*************************************************************************
1558 //*************************************************************************
1559 static const data_node_t& data_cast(const node_t& node)
1560 {
1561 return static_cast<const data_node_t&>(node);
1562 }
1563
1564 //*************************************************************************
1566 //*************************************************************************
1567 void remove_node_after(node_t& node)
1568 {
1569 // The node to erase.
1570 node_t* p_node = node.next;
1571
1572 if (p_node != ETL_NULLPTR)
1573 {
1574 // Disconnect the node from the forward_list.
1575 join(&node, p_node->next);
1576
1577 // Destroy the pool object.
1578 destroy_data_node(static_cast<data_node_t&>(*p_node));
1579 }
1580 }
1581
1582 //*************************************************************************
1584 //*************************************************************************
1585 data_node_t* allocate_data_node()
1586 {
1587 data_node_t* (etl::ipool::*func)() = &etl::ipool::allocate<data_node_t>;
1588 return (p_node_pool->*func)();
1589 }
1590
1591 //*************************************************************************
1593 //*************************************************************************
1594 void destroy_data_node(data_node_t& node)
1595 {
1596 node.value.~T();
1597 p_node_pool->release(&node);
1598 ETL_DECREMENT_DEBUG_COUNT
1599 }
1600
1601 // Disable copy construction.
1603
1604 //*************************************************************************
1606 //*************************************************************************
1607#if defined(ETL_POLYMORPHIC_FORWARD_LIST) || defined(ETL_POLYMORPHIC_CONTAINERS)
1608 public:
1609 virtual ~iforward_list()
1610 {
1611 }
1612#else
1613 protected:
1615 {
1616 }
1617#endif
1618
1619 private:
1620
1621 //*************************************************************************
1623 //*************************************************************************
1624 iterator to_iterator(const_iterator itr) const
1625 {
1626 return iterator(const_cast<node_t*>(itr.p_node));
1627 }
1628 };
1629
1630 //*************************************************************************
1633 //*************************************************************************
1634 template <typename T, const size_t MAX_SIZE_>
1636 {
1637 public:
1638
1639 ETL_STATIC_ASSERT((MAX_SIZE_ > 0U), "Zero capacity etl::forward_list is not valid");
1640
1641 static ETL_CONSTANT size_t MAX_SIZE = MAX_SIZE_;
1642
1643 public:
1644
1645 typedef T value_type;
1646 typedef T* pointer;
1647 typedef const T* const_pointer;
1648 typedef T& reference;
1649 typedef const T& const_reference;
1650 typedef size_t size_type;
1651
1652 //*************************************************************************
1654 //*************************************************************************
1656 : etl::iforward_list<T>(node_pool, MAX_SIZE, false)
1657 {
1658 this->initialise();
1659 }
1660
1661 //*************************************************************************
1663 //*************************************************************************
1664 explicit forward_list(size_t initial_size, const T& value = T())
1665 : etl::iforward_list<T>(node_pool, MAX_SIZE, false)
1666 {
1667 this->assign(initial_size, value);
1668 }
1669
1670 //*************************************************************************
1672 //*************************************************************************
1674 : etl::iforward_list<T>(node_pool, MAX_SIZE, false)
1675 {
1676 this->assign(other.cbegin(), other.cend());
1677 }
1678
1679#if ETL_USING_CPP11
1680 //*************************************************************************
1682 //*************************************************************************
1683 forward_list(forward_list&& other)
1684 : etl::iforward_list<T>(node_pool, MAX_SIZE, false)
1685 {
1686 this->move_container(etl::move(other));
1687 }
1688#endif
1689
1690 //*************************************************************************
1692 //*************************************************************************
1693 template <typename TIterator>
1694 forward_list(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral<TIterator>::value, int>::type = 0)
1695 : etl::iforward_list<T>(node_pool, MAX_SIZE, false)
1696 {
1697 this->assign(first, last);
1698 }
1699
1700#if ETL_HAS_INITIALIZER_LIST
1701 //*************************************************************************
1703 //*************************************************************************
1704 forward_list(std::initializer_list<T> init)
1705 : etl::iforward_list<T>(node_pool, MAX_SIZE, false)
1706 {
1707 this->assign(init.begin(), init.end());
1708 }
1709#endif
1710
1711 //*************************************************************************
1713 //*************************************************************************
1715 {
1716 this->initialise();
1717 }
1718
1719 //*************************************************************************
1721 //*************************************************************************
1723 {
1724 if (&rhs != this)
1725 {
1726 this->assign(rhs.cbegin(), rhs.cend());
1727 }
1728
1729 return *this;
1730 }
1731
1732#if ETL_USING_CPP11
1733 //*************************************************************************
1735 //*************************************************************************
1737 {
1738
1739 this->move_container(etl::move(rhs));
1740
1741 return *this;
1742 }
1743#endif
1744
1745 private:
1746
1749 };
1750
1751 template <typename T, const size_t MAX_SIZE_>
1752 ETL_CONSTANT size_t forward_list<T, MAX_SIZE_>::MAX_SIZE;
1753
1754 //*************************************************************************
1756 //*************************************************************************
1757#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1758 template <typename... T>
1759 forward_list(T...) ->forward_list<typename etl::common_type_t<T...>, sizeof...(T)>;
1760#endif
1761
1762 //*************************************************************************
1764 //*************************************************************************
1765#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1766 template <typename... T>
1767 constexpr auto make_forward_list(T&&... t) -> etl::forward_list<typename etl::common_type_t<T...>, sizeof...(T)>
1768 {
1769 return { { etl::forward<T>(t)... } };
1770 }
1771#endif
1772
1773 //*************************************************************************
1776 //*************************************************************************
1777 template <typename T>
1779 {
1780 public:
1781
1782 typedef T value_type;
1783 typedef T* pointer;
1784 typedef const T* const_pointer;
1785 typedef T& reference;
1786 typedef const T& const_reference;
1787 typedef size_t size_type;
1788
1790
1791 //*************************************************************************
1793 //*************************************************************************
1795 : etl::iforward_list<T>(true)
1796 {
1797 }
1798
1799 //*************************************************************************
1801 //*************************************************************************
1802 explicit forward_list_ext(etl::ipool& node_pool)
1803 : etl::iforward_list<T>(node_pool, node_pool.max_size(), true)
1804 {
1805 this->initialise();
1806 }
1807
1808 //*************************************************************************
1810 //*************************************************************************
1811 explicit forward_list_ext(size_t initial_size, etl::ipool& node_pool)
1812 : etl::iforward_list<T>(node_pool, node_pool.max_size(), true)
1813 {
1814 this->assign(initial_size, T());
1815 }
1816
1817 //*************************************************************************
1819 //*************************************************************************
1820 explicit forward_list_ext(size_t initial_size, const T& value, etl::ipool& node_pool)
1821 : etl::iforward_list<T>(node_pool, node_pool.max_size(), true)
1822 {
1823 this->assign(initial_size, value);
1824 }
1825
1826 //*************************************************************************
1828 //*************************************************************************
1830 : etl::iforward_list<T>(*other.p_node_pool, other.p_node_pool->max_size(), true)
1831 {
1832 this->assign(other.cbegin(), other.cend());
1833 }
1834
1835 //*************************************************************************
1837 //*************************************************************************
1839 : etl::iforward_list<T>(node_pool, node_pool.max_size(), true)
1840 {
1841 this->assign(other.cbegin(), other.cend());
1842 }
1843
1844#if ETL_USING_CPP11
1845 //*************************************************************************
1847 //*************************************************************************
1849 : etl::iforward_list<T>(*other.p_node_pool, other.p_node_pool->max_size(), true)
1850 {
1851 this->move_container(etl::move(other));
1852 }
1853
1854 //*************************************************************************
1856 //*************************************************************************
1857 forward_list_ext(forward_list_ext&& other, etl::ipool& node_pool)
1858 : etl::iforward_list<T>(node_pool, node_pool.max_size(), true)
1859 {
1860 this->move_container(etl::move(other));
1861 }
1862#endif
1863
1864 //*************************************************************************
1866 //*************************************************************************
1867 template <typename TIterator>
1868 forward_list_ext(TIterator first, TIterator last, etl::ipool& node_pool, typename etl::enable_if<!etl::is_integral<TIterator>::value, int>::type = 0)
1869 : etl::iforward_list<T>(node_pool, node_pool.max_size(), true)
1870 {
1871 this->assign(first, last);
1872 }
1873
1874#if ETL_HAS_INITIALIZER_LIST
1875 //*************************************************************************
1877 //*************************************************************************
1878 forward_list_ext(std::initializer_list<T> init, etl::ipool& node_pool)
1879 : etl::iforward_list<T>(node_pool, node_pool.max_size(), true)
1880 {
1881 this->assign(init.begin(), init.end());
1882 }
1883#endif
1884
1885 //*************************************************************************
1887 //*************************************************************************
1889 {
1890 this->initialise();
1891 }
1892
1893 //*************************************************************************
1895 //*************************************************************************
1897 {
1898 if (&rhs != this)
1899 {
1900 this->assign(rhs.cbegin(), rhs.cend());
1901 }
1902
1903 return *this;
1904 }
1905
1906#if ETL_USING_CPP11
1907 //*************************************************************************
1909 //*************************************************************************
1911 {
1912 this->move_container(etl::move(rhs));
1913
1914 return *this;
1915 }
1916#endif
1917
1918 //*************************************************************************
1920 //*************************************************************************
1922 {
1923 // Clear the list of any current elements.
1924 if (this->get_node_pool() != ETL_NULLPTR)
1925 {
1926 this->clear();
1927 }
1928
1929 this->set_node_pool(pool);
1930 }
1931
1932 //*************************************************************************
1934 //*************************************************************************
1936 {
1937 return *this->p_node_pool;
1938 }
1939 };
1940
1941 //*************************************************************************
1946 //*************************************************************************
1947 template <typename T>
1949 {
1950 return (lhs.size() == rhs.size()) &&
1951 etl::equal(lhs.begin(), lhs.end(), rhs.begin());
1952 }
1953
1954 //*************************************************************************
1959 //*************************************************************************
1960 template <typename T>
1962 {
1963 return !(lhs == rhs);
1964 }
1965
1966 //*************************************************************************
1972 //*************************************************************************
1973 template <typename T>
1975 {
1976 return etl::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
1977 }
1978
1979 //*************************************************************************
1985 //*************************************************************************
1986 template <typename T>
1988 {
1989 return (rhs < lhs);
1990 }
1991
1992 //*************************************************************************
1998 //*************************************************************************
1999 template <typename T>
2001 {
2002 return !(lhs > rhs);
2003 }
2004
2005 //*************************************************************************
2011 //*************************************************************************
2012 template <typename T>
2014 {
2015 return !(lhs < rhs);
2016 }
2017}
2018
2019#include "private/minmax_pop.h"
2020
2021#endif
Template deduction guides.
Definition: forward_list.h:1779
void set_pool(etl::ipool &pool)
Set the pool instance.
Definition: forward_list.h:1921
etl::ipool & get_pool() const
Get the pool instance.
Definition: forward_list.h:1935
forward_list_ext()
Default constructor.
Definition: forward_list.h:1794
forward_list_ext(etl::ipool &node_pool)
Default constructor.
Definition: forward_list.h:1802
forward_list_ext(size_t initial_size, const T &value, etl::ipool &node_pool)
Construct from size and value.
Definition: forward_list.h:1820
forward_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: forward_list.h:1868
forward_list_ext(const forward_list_ext &other)
Copy constructor. Implicit pool.
Definition: forward_list.h:1829
forward_list_ext(size_t initial_size, etl::ipool &node_pool)
Construct from size.
Definition: forward_list.h:1811
forward_list_ext(const forward_list_ext &other, etl::ipool &node_pool)
Copy constructor. Explicit pool.
Definition: forward_list.h:1838
~forward_list_ext()
Destructor.
Definition: forward_list.h:1888
Definition: forward_list.h:1636
~forward_list()
Destructor.
Definition: forward_list.h:1714
forward_list(size_t initial_size, const T &value=T())
Construct from size and value.
Definition: forward_list.h:1664
forward_list(const forward_list &other)
Copy constructor.
Definition: forward_list.h:1673
forward_list()
Default constructor.
Definition: forward_list.h:1655
forward_list(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Construct from range.
Definition: forward_list.h:1694
const_iterator
Definition: forward_list.h:472
iterator.
Definition: forward_list.h:398
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
iterator end()
Gets the end of the forward_list.
Definition: forward_list.h:596
void resize(size_t n)
Resizes the forward_list.
Definition: forward_list.h:816
reference emplace_front(const T1 &value1)
Emplaces a value to the front of the list..
Definition: forward_list.h:741
size_type MAX_SIZE
The maximum size of the forward_list.
Definition: forward_list.h:353
void unique(TIsEqual isEqual)
Definition: forward_list.h:1163
void assign(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Definition: forward_list.h:647
iforward_list & operator=(const iforward_list &rhs)
Assignment operator.
Definition: forward_list.h:1384
iterator emplace_after(const_iterator position, const T1 &value1)
Emplaces a value to the forward_list after the specified position.
Definition: forward_list.h:903
forward_list_base(bool pool_is_shared_)
The constructor that is called from derived classes.
Definition: forward_list.h:268
reference emplace_front(const T1 &value1, const T2 &value2, const T3 &value3)
Emplaces a value to the front of the list..
Definition: forward_list.h:773
const_iterator cbegin() const
Gets the beginning of the forward_list.
Definition: forward_list.h:588
iterator before_begin()
Gets before the beginning of the forward_list.
Definition: forward_list.h:572
iterator erase_after(iterator position)
Erases the value at the specified position.
Definition: forward_list.h:1012
void insert_node_after(node_t &position, node_t &node)
Insert a node.
Definition: forward_list.h:311
iterator erase_after(const_iterator position)
Erases the value at the specified position.
Definition: forward_list.h:1031
iterator emplace_after(const_iterator position, const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Emplaces a value to the forward_list after the specified position.
Definition: forward_list.h:951
void unique()
Definition: forward_list.h:1153
node_t start_node
The node that acts as the forward_list start.
Definition: forward_list.h:351
iterator insert_after(const_iterator position, size_t n, const T &value)
Inserts 'n' copies of a value to the forward_list after the specified position.
Definition: forward_list.h:967
size_type max_size() const
Gets the maximum possible size of the forward_list.
Definition: forward_list.h:169
forward_list_base(etl::ipool &node_pool_, size_type max_size_, bool pool_is_shared_)
The constructor that is called from derived classes.
Definition: forward_list.h:278
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: forward_list.h:789
void resize(size_t n, T value)
Definition: forward_list.h:826
iforward_list(etl::ipool &node_pool, size_t max_size_, bool pool_is_shared_)
Constructor.
Definition: forward_list.h:1419
size_t available() const
Definition: forward_list.h:229
size_type capacity() const
Gets the maximum possible size of the forward_list.
Definition: forward_list.h:177
void clear()
Clears the forward_list.
Definition: forward_list.h:620
iterator emplace_after(const_iterator position, const T1 &value1, const T2 &value2)
Emplaces a value to the forward_list after the specified position.
Definition: forward_list.h:919
node_t * get_head()
Get the head node.
Definition: forward_list.h:295
const_iterator before_begin() const
Gets before the beginning of the forward_list.
Definition: forward_list.h:580
etl::ipool * get_node_pool()
Get the node pool instance.
Definition: forward_list.h:346
void reverse()
Reverses the forward_list.
Definition: forward_list.h:238
const_iterator cend() const
Gets the end of the forward_list.
Definition: forward_list.h:612
const_iterator begin() const
Gets the beginning of the forward_list.
Definition: forward_list.h:564
void join(node_t *left, node_t *right)
Join two nodes.
Definition: forward_list.h:329
size_t size_type
The type used for determining the size of forward_list.
Definition: forward_list.h:156
reference front()
Gets a reference to the first element.
Definition: forward_list.h:628
void move_after(const_iterator first_before, const_iterator last, const_iterator to_before)
Definition: forward_list.h:1114
bool pool_is_shared
If true then the pool is shared between lists.
Definition: forward_list.h:354
void push_front(const T &value)
Pushes a value to the front of the forward_list.
Definition: forward_list.h:695
iterator insert_after(const_iterator position, const T &value)
Inserts a value to the forward_list after the specified position.
Definition: forward_list.h:872
reference emplace_front(const T1 &value1, const T2 &value2)
Emplaces a value to the front of the list..
Definition: forward_list.h:757
iterator emplace_after(const_iterator position, const T1 &value1, const T2 &value2, const T3 &value3)
Emplaces a value to the forward_list after the specified position.
Definition: forward_list.h:935
void sort()
Definition: forward_list.h:1194
void sort(TCompare compare)
Definition: forward_list.h:1225
void initialise()
Initialise the forward_list.
Definition: forward_list.h:1427
etl::ipool * p_node_pool
The pool of data nodes used in the list.
Definition: forward_list.h:352
const_reference front() const
Gets a const reference to the first element.
Definition: forward_list.h:636
void remove_if(TPredicate predicate)
Removes according to a predicate.
Definition: forward_list.h:1362
bool has_shared_pool() const
true if the list has a shared pool.
Definition: forward_list.h:161
bool full() const
Checks to see if the forward_list is full.
Definition: forward_list.h:219
void pop_front()
Removes a value from the front of the forward_list.
Definition: forward_list.h:805
iterator insert_after(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 forward_list after the specified position.
Definition: forward_list.h:990
~forward_list_base()
Destructor.
Definition: forward_list.h:288
iterator erase_after(const_iterator first, const_iterator last)
Erases a range of elements.
Definition: forward_list.h:1050
bool empty() const
Checks to see if the forward_list is empty.
Definition: forward_list.h:211
void assign(size_t n, const T &value)
Assigns 'n' copies of a value to the forward_list.
Definition: forward_list.h:674
void set_node_pool(etl::ipool &node_pool_)
Set the node pool instance.
Definition: forward_list.h:337
void move_after(const_iterator from_before, const_iterator to_before)
Definition: forward_list.h:1090
~iforward_list()
Destructor.
Definition: forward_list.h:1614
size_type size() const
Gets the size of the forward_list.
Definition: forward_list.h:185
data_node_t & allocate_data_node(const_reference value)
Allocate a data_node_t.
Definition: forward_list.h:1458
const_iterator end() const
Gets the end of the forward_list.
Definition: forward_list.h:604
iterator begin()
Gets the beginning of the forward_list.
Definition: forward_list.h:556
iforward_list(bool pool_is_shared_)
Constructor.
Definition: forward_list.h:1411
const node_t * get_head() const
Get the head node.
Definition: forward_list.h:303
bool is_trivial_list() const
Is the forward_list a trivial length?
Definition: forward_list.h:321
Definition: forward_list.h:138
Definition: forward_list.h:96
Definition: forward_list.h:68
Definition: forward_list.h:82
Definition: forward_list.h:110
Definition: forward_list.h:364
Definition: forward_list.h:124
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::iforward_list< T > &lhs, const etl::iforward_list< T > &rhs)
Definition: forward_list.h:1961
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:633
bool operator==(const etl::iforward_list< T > &lhs, const etl::iforward_list< T > &rhs)
Definition: forward_list.h:1948
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 node element in the forward_list.
Definition: forward_list.h:145
The data node element in the forward_list.
Definition: forward_list.h:384
Definition: type_traits_generator.h:2055
iterator
Definition: iterator.h:399