31#ifndef ETL_FORWARD_LIST_INCLUDED
32#define ETL_FORWARD_LIST_INCLUDED
47#include "static_assert.h"
72 :
exception(reason_, file_name_, line_number_)
128 :
forward_list_exception(ETL_ERROR_TEXT(
"list:no pool", ETL_FORWARD_LIST_FILE_ID
"D"), file_name_, line_number_)
194 while (p_node != ETL_NULLPTR)
197 p_node = p_node->next;
246 node_t* p_current = p_last->next;
247 node_t* p_next = p_current->next;
249 p_current->next = ETL_NULLPTR;
251 while (p_next != ETL_NULLPTR)
255 p_next = p_current->next;
257 p_current->next = p_last;
314 join(&node, position.next);
315 join(&position, &node);
355 ETL_DECLARE_DEBUG_COUNT
362 template <
typename T>
367 typedef T value_type;
369 typedef const T* const_pointer;
370 typedef T& reference;
371 typedef const T& const_reference;
375 typedef T&& rvalue_reference;
405 : p_node(ETL_NULLPTR)
415 : p_node(other.p_node)
421 p_node = p_node->next;
428 p_node = p_node->next;
434 p_node = other.p_node;
438 reference operator *()
const
440 return iforward_list::data_cast(p_node)->value;
445 return &(iforward_list::data_cast(p_node)->value);
448 pointer operator ->()
const
450 return &(iforward_list::data_cast(p_node)->value);
455 return lhs.p_node == rhs.p_node;
460 return !(lhs == rhs);
478 : p_node(ETL_NULLPTR)
493 : p_node(other.p_node)
498 : p_node(other.p_node)
504 p_node = p_node->next;
511 p_node = p_node->next;
517 p_node = other.p_node;
521 const_reference operator *()
const
523 return iforward_list::data_cast(p_node)->value;
528 return &(iforward_list::data_cast(p_node)->value);
531 const_pointer operator ->()
const
533 return &(iforward_list::data_cast(p_node)->value);
538 return lhs.p_node == rhs.p_node;
543 return !(lhs == rhs);
551 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
630 return data_cast(*
get_head()).value;
638 return data_cast(*
get_head()).value;
646 template <
typename TIterator>
649#if ETL_IS_DEBUG_BUILD
650 difference_type d = etl::distance(first, last);
659 while (first != last)
665 join(p_last_node, &data_node);
666 data_node.next = ETL_NULLPTR;
667 p_last_node = &data_node;
686 join(p_last_node, &data_node);
687 data_node.next = ETL_NULLPTR;
688 p_last_node = &data_node;
697#if defined(ETL_CHECK_PUSH_POP)
711#if defined(ETL_CHECK_PUSH_POP)
715 data_node_t& data_node = allocate_data_node(etl::move(value));
720#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
724 template <
typename ... Args>
727#if defined(ETL_CHECK_PUSH_POP)
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
740 template <
typename T1>
743#if defined(ETL_CHECK_PUSH_POP)
747 ::new (&(p_data_node->value)) T(value1);
748 ETL_INCREMENT_DEBUG_COUNT
756 template <
typename T1,
typename T2>
759#if defined(ETL_CHECK_PUSH_POP)
763 ::new (&(p_data_node->value)) T(value1, value2);
764 ETL_INCREMENT_DEBUG_COUNT
772 template <
typename T1,
typename T2,
typename T3>
773 reference
emplace_front(
const T1& value1,
const T2& value2,
const T3& value3)
775#if defined(ETL_CHECK_PUSH_POP)
779 ::new (&(p_data_node->value)) T(value1, value2, value3);
780 ETL_INCREMENT_DEBUG_COUNT
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)
791#if defined(ETL_CHECK_PUSH_POP)
795 ::new (&(p_data_node->value)) T(value1, value2, value3, value4);
796 ETL_INCREMENT_DEBUG_COUNT
807#if defined(ETL_CHECK_PUSH_POP)
845 while ((i < n) && (i_node !=
end()))
848 i_last_node = i_node;
857 else if (i_node ==
end())
882#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
886 template <
typename ... Args>
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
902 template <
typename T1>
908 ::new (&(p_data_node->value)) T(value1);
909 ETL_INCREMENT_DEBUG_COUNT
918 template <
typename T1,
typename T2>
924 ::new (&(p_data_node->value)) T(value1, value2);
925 ETL_INCREMENT_DEBUG_COUNT
934 template <
typename T1,
typename T2,
typename T3>
940 ::new (&(p_data_node->value)) T(value1, value2, value3);
941 ETL_INCREMENT_DEBUG_COUNT
950 template <
typename T1,
typename T2,
typename T3,
typename T4>
956 ::new (&(p_data_node->value)) T(value1, value2, value3, value4);
957 ETL_INCREMENT_DEBUG_COUNT
971 for (
size_t i = 0UL; !
full() && (i < n); ++i)
983 return to_iterator(position);
989 template <
typename TIterator>
992#if ETL_IS_DEBUG_BUILD
993 difference_type d = etl::distance(first, last);
997 while (first != last)
1006 return to_iterator(position);
1021 remove_node_after(*position.p_node);
1040 remove_node_after(*position.p_node);
1052 if (first !=
end() && (first != last))
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;
1059 join(p_first, p_last);
1064 while (p_first != p_last)
1066 p_next = p_first->next;
1067 destroy_data_node(
static_cast<data_node_t&
>(*p_first));
1071 if (p_next == ETL_NULLPTR)
1092 if (from_before == to_before)
1097 node_t* p_from_before =
const_cast<node_t*
>(from_before.p_node);
1098 node_t* p_to_before =
const_cast<node_t*
>(to_before.p_node);
1100 node_t* p_from = p_from_before->next;
1103 join(p_from_before, p_from->next);
1106 join(p_from, p_to_before->next);
1107 join(p_to_before, p_from);
1116 if ((first_before == to_before) || (last == to_before))
1129 node_t* p_first_before =
const_cast<node_t*
>(first_before.p_node);
1131 node_t* p_to_before =
const_cast<node_t*
>(to_before.p_node);
1132 node_t* p_first = p_first_before->next;
1133 node_t* p_final = p_first_before;
1136 while (p_final->next != p_last)
1138 p_final = p_final->next;
1142 join(p_first_before, p_final->next);
1145 join(p_final, p_to_before->next);
1146 join(p_to_before, p_first);
1162 template <
typename TIsEqual>
1171 node_t* current = last->next;
1173 while (current != ETL_NULLPTR)
1176 if (isEqual(data_cast(current)->value, data_cast(last)->value))
1178 remove_node_after(*last);
1186 current = last->next;
1224 template <
typename TCompare>
1233 int number_of_merges;
1248 number_of_merges = 0;
1250 while (p_left !=
end())
1257 for (
int i = 0; i < list_size; ++i)
1263 if (p_right ==
end())
1270 right_size = list_size;
1273 while (left_size > 0 || (right_size > 0 && p_right !=
end()))
1283 else if (right_size == 0 || p_right ==
end())
1290 else if (!
compare(*p_right, *p_left))
1308 join(p_head.p_node, p_node.p_node);
1314 join(p_tail.p_node, p_node.p_node);
1318 p_tail.p_node->next = ETL_NULLPTR;
1326 if (number_of_merges <= 1)
1339 void remove(
const T& value)
1344 while (i_item !=
end())
1346 if (*i_item == value)
1361 template <
typename TPredicate>
1367 while (i_item !=
end())
1369 if (predicate(*i_item))
1400 move_container(etl::move(rhs));
1435 ETL_RESET_DEBUG_COUNT
1443 while (p_first != ETL_NULLPTR)
1445 p_next = p_first->next;
1446 destroy_data_node(
static_cast<data_node_t&
>(*p_first));
1461 ::new (&(p_node->value)) T(value);
1462 ETL_INCREMENT_DEBUG_COUNT
1471 data_node_t& allocate_data_node(rvalue_reference value)
1473 data_node_t* p_node = allocate_data_node();
1474 ::new (&(p_node->value)) T(
etl::move(value));
1475 ETL_INCREMENT_DEBUG_COUNT
1497 this->start_node.next = rhs.start_node.next;
1499 ETL_SET_DEBUG_COUNT(ETL_OBJECT_GET_DEBUG_COUNT(rhs));
1501 ETL_OBJECT_RESET_DEBUG_COUNT(rhs);
1502 rhs.start_node.next = ETL_NULLPTR;
1512 while (first != last)
1516 data_node_t& data_node = this->allocate_data_node(etl::move(*first));
1518 join(p_last_node, &data_node);
1519 data_node.next = ETL_NULLPTR;
1520 p_last_node = &data_node;
1535 static data_node_t* data_cast(node_t* p_node)
1537 return static_cast<data_node_t*
>(p_node);
1543 static data_node_t& data_cast(node_t& node)
1545 return static_cast<data_node_t&
>(node);
1551 static const data_node_t* data_cast(
const node_t* p_node)
1553 return static_cast<const data_node_t*
>(p_node);
1559 static const data_node_t& data_cast(
const node_t& node)
1561 return static_cast<const data_node_t&
>(node);
1567 void remove_node_after(node_t& node)
1570 node_t* p_node = node.next;
1572 if (p_node != ETL_NULLPTR)
1575 join(&node, p_node->next);
1578 destroy_data_node(
static_cast<data_node_t&
>(*p_node));
1587 data_node_t* (
etl::ipool::*func)() = &etl::ipool::allocate<data_node_t>;
1594 void destroy_data_node(data_node_t& node)
1598 ETL_DECREMENT_DEBUG_COUNT
1607#if defined(ETL_POLYMORPHIC_FORWARD_LIST) || defined(ETL_POLYMORPHIC_CONTAINERS)
1624 iterator to_iterator(const_iterator itr)
const
1626 return iterator(
const_cast<node_t*
>(itr.p_node));
1634 template <
typename T, const
size_t MAX_SIZE_>
1639 ETL_STATIC_ASSERT((MAX_SIZE_ > 0U),
"Zero capacity etl::forward_list is not valid");
1641 static ETL_CONSTANT
size_t MAX_SIZE = MAX_SIZE_;
1645 typedef T value_type;
1647 typedef const T* const_pointer;
1648 typedef T& reference;
1649 typedef const T& const_reference;
1667 this->
assign(initial_size, value);
1686 this->move_container(etl::move(other));
1693 template <
typename TIterator>
1697 this->
assign(first, last);
1700#if ETL_HAS_INITIALIZER_LIST
1707 this->
assign(init.begin(), init.end());
1739 this->move_container(etl::move(rhs));
1751 template <
typename T, const
size_t MAX_SIZE_>
1752 ETL_CONSTANT
size_t forward_list<T, MAX_SIZE_>::MAX_SIZE;
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)>;
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)>
1769 return { { etl::forward<T>(t)... } };
1777 template <
typename T>
1782 typedef T value_type;
1784 typedef const T* const_pointer;
1785 typedef T& reference;
1786 typedef const T& const_reference;
1814 this->
assign(initial_size, T());
1823 this->
assign(initial_size, value);
1851 this->move_container(etl::move(other));
1857 forward_list_ext(forward_list_ext&& other,
etl::ipool& node_pool)
1860 this->move_container(etl::move(other));
1867 template <
typename TIterator>
1871 this->
assign(first, last);
1874#if ETL_HAS_INITIALIZER_LIST
1881 this->
assign(init.begin(), init.end());
1912 this->move_container(etl::move(rhs));
1947 template <
typename T>
1950 return (lhs.
size() == rhs.
size()) &&
1960 template <
typename T>
1963 return !(lhs == rhs);
1973 template <
typename T>
1976 return etl::lexicographical_compare(lhs.
begin(), lhs.
end(), rhs.
begin(), rhs.
end());
1986 template <
typename T>
1999 template <
typename T>
2002 return !(lhs > rhs);
2012 template <
typename T>
2015 return !(lhs < rhs);
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
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: 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