31#ifndef ETL_LIST_INCLUDED
32#define ETL_LIST_INCLUDED
46#include "static_assert.h"
166 : previous(ETL_NULLPTR),
176 using ETL_OR_STD::swap;
178 swap(previous, next);
208 p_node->previous = p_node->next;
210 p_node = p_node->previous;
215 p_node->previous = p_node->next;
250 p_node = p_node->next;
346 right.previous = &left;
406 template <
typename T>
451 static data_node_t& data_cast(node_t&
node)
453 return reinterpret_cast<data_node_t&
>(
node);
459 static const data_node_t* data_cast(
const node_t* p_node)
461 return reinterpret_cast<const data_node_t*
>(p_node);
467 static const data_node_t& data_cast(
const node_t& node)
469 return reinterpret_cast<const data_node_t&
>(node);
485 : p_node(ETL_NULLPTR)
495 : p_node(
other.p_node)
501 p_node = p_node->next;
508 p_node = p_node->next;
514 p_node = p_node->previous;
521 p_node = p_node->previous;
527 p_node =
other.p_node;
533 return ilist::data_cast(p_node)->value;
538 return &(ilist::data_cast(p_node)->value);
543 return &(ilist::data_cast(p_node)->value);
548 return lhs.p_node ==
rhs.p_node;
571 : p_node(ETL_NULLPTR)
586 : p_node(
other.p_node)
591 : p_node(
other.p_node)
597 p_node = p_node->next;
604 p_node = p_node->next;
610 p_node = p_node->previous;
617 p_node = p_node->previous;
623 p_node =
other.p_node;
629 return ilist::data_cast(p_node)->value;
634 return &(ilist::data_cast(p_node)->value);
639 return &(ilist::data_cast(p_node)->value);
644 return lhs.p_node ==
rhs.p_node;
657 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
659 typedef ETL_OR_STD::reverse_iterator<iterator> reverse_iterator;
660 typedef ETL_OR_STD::reverse_iterator<const_iterator> const_reverse_iterator;
731 return reverse_iterator(
get_head());
737 const_reverse_iterator
rend()
const
739 return const_reverse_iterator(
get_head());
753 const_reverse_iterator
crend()
const
755 return const_reverse_iterator(
get_head());
795 template <
typename TIterator>
798#if ETL_IS_DEBUG_BUILD
799 difference_type
d = etl::distance(first, last);
806 while (first != last)
820#if ETL_IS_DEBUG_BUILD
840#if defined(ETL_CHECK_PUSH_POP)
852#if defined(ETL_CHECK_PUSH_POP)
859#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT && !defined(ETL_LIST_FORCE_CPP03_IMPLEMENTATION)
863 template <
typename ... Args>
866#if defined(ETL_CHECK_PUSH_POP)
871 data_node_t* p_data_node = allocate_data_node();
872 ::new (&(p_data_node->value)) T(
etl::forward<Args>(args)...);
873 ETL_INCREMENT_DEBUG_COUNT;
883#if defined(ETL_CHECK_PUSH_POP)
890 ETL_INCREMENT_DEBUG_COUNT;
898 template <
typename T1>
901#if defined(ETL_CHECK_PUSH_POP)
908 ETL_INCREMENT_DEBUG_COUNT;
916 template <
typename T1,
typename T2>
919#if defined(ETL_CHECK_PUSH_POP)
926 ETL_INCREMENT_DEBUG_COUNT;
934 template <
typename T1,
typename T2,
typename T3>
937#if defined(ETL_CHECK_PUSH_POP)
943 ::new (&(
p_data_node->value))
T(value1, value2, value3);
944 ETL_INCREMENT_DEBUG_COUNT;
952 template <
typename T1,
typename T2,
typename T3,
typename T4>
955#if defined(ETL_CHECK_PUSH_POP)
961 ::new (&(
p_data_node->value))
T(value1, value2, value3, value4);
962 ETL_INCREMENT_DEBUG_COUNT;
973#if defined(ETL_CHECK_PUSH_POP)
985#if defined(ETL_CHECK_PUSH_POP)
997#if defined(ETL_CHECK_PUSH_POP)
1007#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT
1008 template <
typename ... Args>
1011#if defined(ETL_CHECK_PUSH_POP)
1016 data_node_t* p_data_node = allocate_data_node();
1017 ::new (&(p_data_node->value)) T(
etl::forward<Args>(args)...);
1018 ETL_INCREMENT_DEBUG_COUNT;
1025#if defined(ETL_CHECK_PUSH_POP)
1032 ETL_INCREMENT_DEBUG_COUNT;
1037 template <
typename T1>
1040#if defined(ETL_CHECK_PUSH_POP)
1047 ETL_INCREMENT_DEBUG_COUNT;
1055#if defined(ETL_CHECK_PUSH_POP)
1062 ETL_INCREMENT_DEBUG_COUNT;
1070#if defined(ETL_CHECK_PUSH_POP)
1076 ::new (&(
p_data_node->value))
T(value1, value2, value3);
1077 ETL_INCREMENT_DEBUG_COUNT;
1085#if defined(ETL_CHECK_PUSH_POP)
1091 ::new (&(
p_data_node->value))
T(value1, value2, value3, value4);
1092 ETL_INCREMENT_DEBUG_COUNT;
1103#if defined(ETL_CHECK_PUSH_POP)
1131 data_node_t&
data_node = allocate_data_node(etl::move(value));
1141#if ETL_USING_CPP11 && ETL_NOT_USING_STLPORT && !defined(ETL_LIST_FORCE_CPP03_IMPLEMENTATION)
1142 template <
typename ... Args>
1143 iterator
emplace(const_iterator position, Args&& ... args)
1148 data_node_t* p_data_node = allocate_data_node();
1149 ::new (&(p_data_node->value)) T(
etl::forward<Args>(args)...);
1150 ETL_INCREMENT_DEBUG_COUNT;
1151 insert_node(*to_iterator(position).p_node, *p_data_node);
1153 return iterator(*p_data_node);
1163 ETL_INCREMENT_DEBUG_COUNT;
1169 template <
typename T1>
1177 ETL_INCREMENT_DEBUG_COUNT;
1191 ETL_INCREMENT_DEBUG_COUNT;
1204 ::new (&(
p_data_node->value))
T(value1, value2, value3);
1205 ETL_INCREMENT_DEBUG_COUNT;
1218 ::new (&(
p_data_node->value))
T(value1, value2, value3, value4);
1219 ETL_INCREMENT_DEBUG_COUNT;
1231 for (
size_t i = 0
UL;
i <
n; ++
i)
1236 insert_node(*to_iterator(position).p_node, allocate_data_node(value));
1243 template <
typename TIterator>
1246 while (first != last)
1251 insert_node(*to_iterator(position).p_node, allocate_data_node(*first));
1264 remove_node(*
position_.p_node->previous);
1315 else if (
n <
size())
1322 else if (
n >
size())
1339 void remove(const_reference value)
1359 template <
typename TPredicate>
1390 template <
typename TIsEqual>
1437 while (itr !=
other.end())
1443 other.erase(other.begin(), other.end());
1480 insert(to, etl::move(*from));
1494 move(
to, first, last);
1500 other.erase(first, last);
1513 move(
to, first, last);
1518 ilist::iterator itr = first;
1521 to =
insert(to, etl::move(*itr));
1526 other.erase(first, last);
1542 template <
typename TCompare>
1547#if ETL_IS_DEBUG_BUILD
1599 template <
typename TCompare>
1600 void merge(ilist&& other, TCompare compare)
1604#if ETL_IS_DEBUG_BUILD
1609 ilist::iterator other_begin = other.begin();
1610 ilist::iterator other_end = other.end();
1612 ilist::iterator this_begin =
begin();
1613 ilist::iterator this_end =
end();
1615 while ((this_begin != this_end) && (other_begin != other_end))
1618 while ((this_begin != this_end) && !(compare(*other_begin, *this_begin)))
1624 if (this_begin != this_end)
1626 while ((other_begin != other_end) && (compare(*other_begin, *this_begin)))
1628 insert(this_begin, etl::move(*other_begin));
1635 if ((this_begin == this_end) && (other_begin != other_end))
1637 while (other_begin != other_end)
1639 insert(this_end, etl::move(*other_begin));
1683 template <
typename TCompare>
1815 while (itr !=
rhs.end())
1859 ETL_RESET_DEBUG_COUNT;;
1897 ETL_SET_DEBUG_COUNT(ETL_OBJECT_GET_DEBUG_COUNT(
rhs));
1900 ETL_OBJECT_RESET_DEBUG_COUNT(
rhs);
1901 rhs.join(
rhs.terminal_node,
rhs.terminal_node);
1909 while (first != last)
1930 void move(iterator to, iterator from)
1937 node_t& from_node = *from.p_node;
1938 node_t& to_node = *to.p_node;
1941 join(*from_node.previous, *from_node.next);
1944 join(*to_node.previous, from_node);
1945 join(from_node, to_node);
1952 void move(iterator to, iterator first, iterator last)
1954 if ((first == to) || (last == to))
1959#if ETL_IS_DEBUG_BUILD
1961 for (const_iterator item = first; item != last; ++item)
1963 ETL_ASSERT(item != to, ETL_ERROR(list_iterator));
1967 node_t& first_node = *first.p_node;
1968 node_t& last_node = *last.p_node;
1969 node_t& to_node = *to.p_node;
1970 node_t& final_node = *last_node.previous;
1973 join(*first_node.previous, last_node);
1976 join(*to_node.previous, first_node);
1977 join(final_node, to_node);
1983 void remove_node(node_t& node)
1986 join(*node.previous, *node.next);
1989 destroy_data_node(
static_cast<data_node_t&
>(node));
1995 data_node_t& allocate_data_node(const_reference value)
1999 data_node_t* p_data_node = allocate_data_node();
2000 ::new (&(p_data_node->value)) T(value);
2001 ETL_INCREMENT_DEBUG_COUNT;
2003 return *p_data_node;
2010 data_node_t& allocate_data_node(rvalue_reference value)
2014 data_node_t* p_data_node = allocate_data_node();
2015 ::new (&(p_data_node->value)) T(
etl::move(value));
2016 ETL_INCREMENT_DEBUG_COUNT;
2018 return *p_data_node;
2025 data_node_t* allocate_data_node()
2027 data_node_t* (
etl::ipool::*func)() = &etl::ipool::allocate<data_node_t>;
2034 void destroy_data_node(data_node_t& node)
2039 ETL_DECREMENT_DEBUG_COUNT;
2043 ilist(
const ilist&);
2045#if defined(ETL_POLYMORPHIC_LIST) || defined(ETL_POLYMORPHIC_CONTAINERS)
2062 iterator to_iterator(const_iterator itr)
const
2064 return iterator(*(
const_cast<node_t*
>(itr.p_node)));
2071 template <
typename T, const
size_t MAX_SIZE_>
2076 ETL_STATIC_ASSERT((
MAX_SIZE_ > 0
U),
"Zero capacity etl::list is not valid");
2078 static ETL_CONSTANT
size_t MAX_SIZE =
MAX_SIZE_;
2096 :
etl::
ilist<
T>(node_pool, MAX_SIZE, false)
2112 :
etl::
ilist<
T>(node_pool, MAX_SIZE, false)
2121 :
etl::
ilist<
T>(node_pool, MAX_SIZE, false)
2130 :
etl::
ilist<
T>(node_pool, MAX_SIZE, false)
2143 :
etl::
ilist<
T>(node_pool, MAX_SIZE, false)
2150 while (itr !=
other.end())
2152 this->push_back(etl::move(*itr));
2164 template <
typename TIterator>
2166 :
ilist<
T>(node_pool, MAX_SIZE, false)
2168 this->assign(first, last);
2171#if ETL_HAS_INITIALIZER_LIST
2175 list(std::initializer_list<T>
init)
2176 :
ilist<
T>(node_pool, MAX_SIZE, false)
2178 this->assign(
init.begin(),
init.end());
2189 this->assign(
rhs.cbegin(),
rhs.cend());
2213 template <
typename T, const
size_t MAX_SIZE_>
2214 ETL_CONSTANT
size_t list<T, MAX_SIZE_>::MAX_SIZE;
2219#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
2220 template <
typename... T>
2228#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
2229 template <
typename... T>
2239 template <
typename T>
2332 list_ext(list_ext&& other,
etl::ipool& node_pool)
2333 :
etl::ilist<T>(node_pool, node_pool.max_size(), true)
2335 this->move_container(etl::move(other));
2342 template <
typename TIterator>
2346 this->assign(first, last);
2349#if ETL_HAS_INITIALIZER_LIST
2356 this->assign(
init.begin(),
init.end());
2367 this->assign(
rhs.cbegin(),
rhs.cend());
2391 if (this->get_node_pool() != ETL_NULLPTR)
2396 this->set_node_pool(
pool);
2404 return *this->p_node_pool;
2414 template <
typename T>
2417 return (
lhs.size() ==
rhs.size()) && etl::equal(
lhs.begin(),
lhs.end(),
rhs.begin());
2426 template <
typename T>
2439 template <
typename T>
2442 return etl::lexicographical_compare(
lhs.begin(),
lhs.end(),
rhs.begin(),
rhs.end());
2452 template <
typename T>
2465 template <
typename T>
2478 template <
typename T>
const_iterator
Definition list.h:565
iterator.
Definition list.h:478
Template deduction guides.
Definition list.h:2241
list_ext(const list_ext &other, etl::ipool &node_pool)
Copy constructor. Explicit pool.
Definition list.h:2310
list_ext(size_t initial_size, etl::ipool &node_pool)
Construct from size.
Definition list.h:2280
void set_pool(etl::ipool &pool)
Set the pool instance.
Definition list.h:2388
list_ext(size_t initial_size, const T &value, etl::ipool &node_pool)
Construct from size and value.
Definition list.h:2289
list_ext(TIterator first, TIterator last, etl::ipool &node_pool, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Construct from range.
Definition list.h:2343
list_ext()
Default constructor.
Definition list.h:2256
etl::ipool & get_pool() const
Get the pool instance.
Definition list.h:2402
list_ext(etl::ipool &node_pool)
Default constructor.
Definition list.h:2264
~list_ext()
Destructor.
Definition list.h:2272
list_ext(const list_ext &other)
Copy constructor. Implicit pool.
Definition list.h:2298
A templated list implementation that uses a fixed size buffer.
Definition list.h:2073
~list()
Destructor.
Definition list.h:2103
list(const list &other)
Copy constructor.
Definition list.h:2129
list(size_t initial_size, const T &value)
Construct from size and value.
Definition list.h:2120
list(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Construct from range.
Definition list.h:2165
list(size_t initial_size)
Construct from size.
Definition list.h:2111
list()
Default constructor.
Definition list.h:2095
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:968
ETL_NODISCARD ETL_CONSTEXPR14 bool is_sorted(TIterator begin, TIterator end)
Definition algorithm.h:1685
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
ilist(etl::ipool &node_pool, size_t max_size_, bool pool_is_shared_)
Constructor.
Definition list.h:1841
const_reverse_iterator rend() const
Gets the reverse end of the list.
Definition list.h:737
void clear()
Clears the list.
Definition list.h:1331
const_iterator cbegin() const
Gets the beginning of the list.
Definition list.h:697
iterator end()
Gets the end of the list.
Definition list.h:681
void push_back(const T &value)
Pushes a value to the back of the list.
Definition list.h:983
iterator emplace(const_iterator position)
Emplaces a value to the list at the specified position.
Definition list.h:1156
ilist(bool pool_is_shared_)
Constructor.
Definition list.h:1833
reference back()
Gets a reference to the last element.
Definition list.h:777
size_t size_type
The type used for determining the size of list.
Definition list.h:155
void reverse()
Reverses the list.
Definition list.h:196
const_reverse_iterator crend() const
Gets the reverse end of the list.
Definition list.h:753
reference emplace_front(const T1 &value1)
Emplaces a value to the front of the list.
Definition list.h:899
void splice(iterator to, ilist &other, iterator from)
Splices an element from another list to this.
Definition list.h:1451
size_type size() const
Gets the size of the list.
Definition list.h:238
void sort(TCompare compare)
Definition list.h:1684
size_type available() const
Definition list.h:282
void splice(iterator to, ilist &other, iterator first, iterator last)
Splices a range of elements from another list to this.
Definition list.h:1489
void join(node_t &left, node_t &right)
Join two nodes.
Definition list.h:343
void insert(const_iterator position, size_t n, const_reference value)
Inserts 'n' copies of a value to the list at the specified position.
Definition list.h:1229
void unique(TIsEqual isEqual)
Definition list.h:1391
void insert(const_iterator position, TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Inserts a range of values to the list at the specified position.
Definition list.h:1244
const_reverse_iterator rbegin() const
Gets the reverse beginning of the list.
Definition list.h:721
list_base(bool pool_is_shared_)
The constructor that is called from derived classes.
Definition list.h:352
etl::ipool * p_node_pool
The pool of data nodes used in the list.
Definition list.h:395
size_type max_size() const
Gets the maximum possible size of the list.
Definition list.h:222
void resize(size_t n)
Resizes the list.
Definition list.h:1297
list_base(etl::ipool &node_pool_, size_type max_size_, bool pool_is_shared_)
The constructor that is called from derived classes.
Definition list.h:363
bool full() const
Checks to see if the list is full.
Definition list.h:272
reverse_iterator rend()
Gets the reverse end of the list.
Definition list.h:729
reverse_iterator rbegin()
Gets the reverse beginning of the list.
Definition list.h:713
reference emplace_front()
Emplaces a value to the front of the list.
Definition list.h:881
ilist & operator=(const ilist &rhs)
Assignment operator.
Definition list.h:1794
iterator insert(const_iterator position, const_reference value)
Inserts a value to the list at the specified position.
Definition list.h:1113
size_type MAX_SIZE
The maximum size of the list.
Definition list.h:397
node_t terminal_node
The node that acts as the list start and end.
Definition list.h:396
void push_front(const T &value)
Pushes a value to the front of the list.
Definition list.h:838
void initialise()
Initialise the list.
Definition list.h:1849
bool pool_is_shared
If true then the pool is shared between lists.
Definition list.h:398
void splice(iterator to, ilist &other)
Splices from another list to this.
Definition list.h:1419
const_iterator end() const
Gets the end of the list.
Definition list.h:689
ETL_DECLARE_DEBUG_COUNT
Internal debugging.
Definition list.h:399
reference front()
Gets a reference to the first element.
Definition list.h:761
void pop_front()
Removes a value from the front of the list.
Definition list.h:971
const_iterator begin() const
Gets the beginning of the list.
Definition list.h:673
void merge(ilist &other)
Merge another list into this one. Both lists should be sorted.
Definition list.h:1534
bool is_trivial_list() const
Is the list a trivial length?
Definition list.h:293
void assign(size_t n, const T &value)
Assigns 'n' copies of a value to the list.
Definition list.h:818
iterator erase(const_iterator first, const_iterator last)
Erases a range of elements.
Definition list.h:1271
reference emplace_front(const T1 &value1, const T2 &value2, const T3 &value3, const T4 &value4)
Emplaces a value to the front of the list.
Definition list.h:953
void set_node_pool(etl::ipool &node_pool_)
Set the node pool instance.
Definition list.h:374
reference emplace_front(const T1 &value1, const T2 &value2, const T3 &value3)
Emplaces a value to the front of the list.
Definition list.h:935
void merge(ilist &other, TCompare compare)
Merge another list into this one. Both lists should be sorted.
Definition list.h:1543
void resize(size_t n, const_reference value)
Resizes the list.
Definition list.h:1305
size_type capacity() const
Gets the maximum possible size of the list.
Definition list.h:230
reference emplace_back()
Emplaces a value to the back of the list.
Definition list.h:1023
bool empty() const
Checks to see if the list is empty.
Definition list.h:264
etl::ipool * get_node_pool()
Get the node pool instance.
Definition list.h:383
iterator begin()
Gets the beginning of the list.
Definition list.h:665
void sort()
Definition list.h:1653
const_reference back() const
Gets a reference to the last element.
Definition list.h:785
void unique()
Definition list.h:1381
const_reference front() const
Gets a const reference to the first element.
Definition list.h:769
node_t & get_head()
Get the head node.
Definition list.h:301
const node_t & get_head() const
Get the head node.
Definition list.h:309
void insert_node(node_t &position, node_t &node)
Insert a node before 'position'.
Definition list.h:333
const node_t & get_tail() const
Get the tail node.
Definition list.h:325
const_iterator cend() const
Gets the end of the list.
Definition list.h:705
const_reverse_iterator crbegin() const
Gets the reverse beginning of the list.
Definition list.h:745
~list_base()
Destructor.
Definition list.h:391
void remove_if(TPredicate predicate)
Removes according to a predicate.
Definition list.h:1360
void assign(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Definition list.h:796
node_t & get_tail()
Get the tail node.
Definition list.h:317
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition list.h:1259
bool has_shared_pool() const
true if the list has a shared pool.
Definition list.h:188
void pop_back()
Removes a value from the back of the list.
Definition list.h:1101
reference emplace_front(const T1 &value1, const T2 &value2)
Emplaces a value to the front of the list.
Definition list.h:917
size_t size() const
Returns the number of allocated items in the pool.
Definition ipool.h:301
void release_all()
Release all objects in the pool.
Definition ipool.h:248
bool full() const
Definition ipool.h:319
size_t max_size() const
Returns the maximum number of items in the pool.
Definition ipool.h:269
void release(const void *const p_object)
Definition ipool.h:239
size_t available() const
Returns the number of free items in the pool.
Definition ipool.h:293
enable_if
Definition type_traits_generator.h:1186
is_integral
Definition type_traits_generator.h:996
bitset_ext
Definition absolute.h:38
bool operator>(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:693
size_t max_size() const
Returns the maximum number of items in the variant_pool.
Definition variant_pool_generator.h:395
bool operator>=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:705
bool operator!=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:654
void swap(etl::array< T, SIZE > &lhs, etl::array< T, SIZE > &rhs)
Template deduction guides.
Definition array.h:630
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:642
bool operator<(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:666
bool operator<=(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition array.h:681
The data node element in the list.
Definition list.h:429
Definition type_traits_generator.h:2096
iterator
Definition iterator.h:399
The node element in the list.
Definition list.h:161
void reverse()
Reverses the previous & next pointers.
Definition list.h:174
node_t()
Constructor.
Definition list.h:165
pair holds two objects of arbitrary type
Definition utility.h:164