31#ifndef ETL_INTRUSIVE_LIST_INCLUDED
32#define ETL_INTRUSIVE_LIST_INCLUDED
40#include "static_assert.h"
60 :
exception(reason_, file_name_, line_number_)
74 :
intrusive_list_exception(ETL_ERROR_TEXT(
"intrusive_list:empty", ETL_INTRUSIVE_LIST_FILE_ID
"A"), file_name_, line_number_)
88 :
intrusive_list_exception(ETL_ERROR_TEXT(
"intrusive_list:iterator", ETL_INTRUSIVE_LIST_FILE_ID
"B"), file_name_, line_number_)
102 :
intrusive_list_exception(ETL_ERROR_TEXT(
"intrusive_list:unsorted", ETL_INTRUSIVE_LIST_FILE_ID
"C"), file_name_, line_number_)
116 :
intrusive_list_exception(ETL_ERROR_TEXT(
"intrusive_list:value is already linked", ETL_INTRUSIVE_LIST_FILE_ID
"E"), file_name_, line_number_)
125 template <
typename TLink>
131 typedef TLink link_type;
138 template <
typename TIterator>
139 void assign(TIterator first, TIterator last)
141#if ETL_IS_DEBUG_BUILD
142 intmax_t d = etl::distance(first, last);
151 while (first != last)
153 link_type& link = *first++;
154 etl::link_splice<link_type>(p_last_link, link);
175#if defined(ETL_CHECK_PUSH_POP)
196#if defined(ETL_CHECK_PUSH_POP)
212 link_type* p_next = p_unlink->etl_next;
235 pnode = pnode->etl_previous;
286 etl::link_splice<link_type>(previous, new_link);
296 etl::link_splice<link_type>(previous, new_link);
306 etl::link_splice<link_type>(previous, new_link);
316 etl::link_splice<link_type>(previous, new_link);
325 etl::unlink<link_type>(link);
334 etl::unlink<link_type>(*link);
385 template <
typename TValue,
typename TLink>
391 typedef typename etl::intrusive_list_base<TLink>::link_type link_type;
396 typedef TValue value_type;
397 typedef value_type* pointer;
398 typedef const value_type* const_pointer;
399 typedef value_type& reference;
400 typedef const value_type& const_reference;
401 typedef size_t size_type;
414 : p_value(ETL_NULLPTR)
419 : p_value(other.p_value)
426 p_value = p_value->etl_next;
434 p_value = p_value->etl_next;
441 p_value = p_value->etl_previous;
449 p_value = p_value->etl_previous;
455 p_value = other.p_value;
459 reference operator *()
const
461 return *
static_cast<pointer
>(p_value);
466 return static_cast<pointer
>(p_value);
469 pointer operator ->()
const
471 return static_cast<pointer
>(p_value);
476 return lhs.p_value == rhs.p_value;
481 return !(lhs == rhs);
504 : p_value(ETL_NULLPTR)
509 : p_value(other.p_value)
514 : p_value(other.p_value)
521 p_value = p_value->etl_next;
529 p_value = p_value->etl_next;
536 p_value = p_value->etl_previous;
544 p_value = p_value->etl_previous;
550 p_value = other.p_value;
554 const_reference operator *()
const
556 return *
static_cast<const_pointer
>(p_value);
561 return static_cast<const_pointer
>(p_value);
564 const_pointer operator ->()
const
566 return static_cast<const_pointer
>(p_value);
571 return lhs.p_value == rhs.p_value;
576 return !(lhs == rhs);
586 const link_type* p_value;
589 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
610 template <
typename TIterator>
613 this->
assign(first, last);
669 return *
static_cast<pointer
>(this->
get_head());
677 return *
static_cast<const_pointer
>(this->
get_head());
685 return *
static_cast<pointer
>(this->
get_tail());
693 return *
static_cast<const_pointer
>(this->
get_tail());
701 this->
insert_link(position.p_value->link_type::etl_previous, value);
708 template <
typename TIterator>
711 while (first != last)
714 this->
insert_link(*position.p_value->link_type::etl_previous, *first);
751 const link_type* cp_first = first.p_value;
752 const link_type* cp_last = last.p_value;
754 link_type* p_first =
const_cast<link_type*
>(cp_first);
755 link_type* p_last =
const_cast<link_type*
>(cp_last);
760 etl::link<link_type>(p_first->etl_previous, p_last);
762 while (p_first != p_last)
764 link_type* p_next = p_first->etl_next;
775 return iterator(
static_cast<pointer
>(p_last));
783 template <
typename TIsEqual>
795 while (i_item !=
end())
797 if (isEqual(*i_previous, *i_item))
799 i_item =
erase(i_item);
842 template <
typename TCompare>
851 int number_of_merges;
866 number_of_merges = 0;
868 while (i_left !=
end())
875 for (
int i = 0; i < list_size; ++i)
880 if (i_right ==
end())
887 right_size = list_size;
890 while (left_size > 0 || (right_size > 0 && i_right !=
end()))
899 else if (right_size == 0 || i_right ==
end())
905 else if (!
compare(*i_right, *i_left))
922 etl::link<link_type>(i_head.p_value, i_node.p_value);
928 etl::link<link_type>(i_tail.p_value, i_node.p_value);
932 etl::link<link_type>(i_tail.p_value, this->terminal_link);
940 if (number_of_merges <= 1)
953 void remove(const_reference value)
957 while (i_item !=
end())
959 if (*i_item == value)
961 i_item =
erase(i_item);
973 template <
typename TPredicate>
978 while (i_item !=
end())
980 if (predicate(*i_item))
982 i_item =
erase(i_item);
1001 link_type& first = *other.
get_head();
1002 link_type& last = *other.
get_tail();
1009 link_type& after = *position.p_value;
1010 link_type& before = *after.etl_previous;
1012 etl::link<link_type>(before, first);
1013 etl::link<link_type>(last, after);
1025 link_type& before = *position.p_value->link_type::etl_previous;
1027 etl::unlink<link_type>(*isource.p_value);
1028 etl::link_splice<link_type>(before, *isource.p_value);
1046 size_t n = etl::distance(begin_, end_);
1051 link_type& first = *begin_.p_value;
1052 link_type& last = *end_.p_value->link_type::etl_previous;
1055 etl::unlink(first, last);
1058 link_type& before = *position.p_value->link_type::etl_previous;
1060 etl::link_splice<link_type>(before, first, last);
1075 template <
typename TCompare>
1078 if ((
this != &other) && !other.
empty())
1080#if ETL_IS_DEBUG_BUILD
1085 link_type* other_begin = other.
get_head();
1088 link_type* this_begin = this->
get_head();
1091 while ((this_begin != this_end) && (other_begin != other_end))
1094 while ((this_begin != this_end) && !(
compare(*
static_cast<pointer
>(other_begin), *
static_cast<pointer
>(this_begin))))
1096 this_begin = this_begin->etl_next;
1100 if (this_begin != this_end)
1102 while ((other_begin != other_end) && (
compare(*
static_cast<pointer
>(other_begin), *
static_cast<pointer
>(this_begin))))
1104 link_type* value = other_begin;
1105 other_begin = other_begin->etl_next;
1106 etl::link_splice<link_type>(*this_begin->etl_previous, *value);
1112 if ((this_begin == this_end) && (other_begin != other_end))
1114 etl::link_splice<link_type>(*this->
get_tail(), *other_begin, *other_end->etl_previous);
const_iterator
Definition: intrusive_list.h:498
iterator.
Definition: intrusive_list.h:407
Definition: intrusive_list.h:127
void remove_link(link_type &link)
Remove a link.
Definition: intrusive_list.h:323
size_t size() const
Returns the number of elements.
Definition: intrusive_list.h:253
link_type * get_tail()
Get the tail link.
Definition: intrusive_list.h:357
void insert_link(link_type &previous, link_type &new_link)
Insert a link.
Definition: intrusive_list.h:283
~intrusive_list_base()
Destructor.
Definition: intrusive_list.h:268
void assign(TIterator first, TIterator last)
Definition: intrusive_list.h:139
size_t current_size
Counts the number of elements in the list.
Definition: intrusive_list.h:263
void remove_link(link_type *link)
Remove a link.
Definition: intrusive_list.h:332
void insert_link(link_type &previous, link_type *new_link)
Insert a link.
Definition: intrusive_list.h:303
void pop_back()
Removes a value from the back of the intrusive_list.
Definition: intrusive_list.h:194
link_type * get_head()
Get the head link.
Definition: intrusive_list.h:341
bool empty() const
Returns true if the list has no elements.
Definition: intrusive_list.h:245
void initialise()
Initialise the intrusive_list.
Definition: intrusive_list.h:373
void reverse()
Reverses the list.
Definition: intrusive_list.h:223
void insert_link(link_type *previous, link_type *new_link)
Insert a link.
Definition: intrusive_list.h:313
const link_type * get_head() const
Get the head link.
Definition: intrusive_list.h:349
link_type terminal_link
The link that acts as the intrusive_list start & end.
Definition: intrusive_list.h:261
void insert_link(link_type *previous, link_type &new_link)
Insert a link.
Definition: intrusive_list.h:293
void clear()
Clears the intrusive_list.
Definition: intrusive_list.h:205
void push_front(link_type &value)
Pushes a value to the front of the intrusive_list.
Definition: intrusive_list.h:163
void push_back(link_type &value)
Pushes a value to the back of the intrusive_list.
Definition: intrusive_list.h:184
void pop_front()
Removes a value from the front of the intrusive_list.
Definition: intrusive_list.h:173
const link_type * get_tail() const
Get the tail link.
Definition: intrusive_list.h:365
bool is_trivial_list() const
Is the intrusive_list a trivial length?
Definition: intrusive_list.h:275
Definition: intrusive_list.h:70
Definition: intrusive_list.h:56
Definition: intrusive_list.h:84
Definition: intrusive_list.h:98
Definition: intrusive_list.h:112
Definition: intrusive_list.h:387
~intrusive_list()
Destructor.
Definition: intrusive_list.h:602
const_iterator end() const
Gets the end of the intrusive_list.
Definition: intrusive_list.h:651
reference back()
Gets a reference to the last element.
Definition: intrusive_list.h:683
iterator begin()
Gets the beginning of the intrusive_list.
Definition: intrusive_list.h:619
void unique(TIsEqual isEqual)
Definition: intrusive_list.h:784
const_iterator begin() const
Gets the beginning of the intrusive_list.
Definition: intrusive_list.h:627
void splice(iterator position, list_type &other)
Splice another list into this one.
Definition: intrusive_list.h:994
iterator erase(const_iterator position)
Erases the value at the specified position.
Definition: intrusive_list.h:735
void splice(iterator position, list_type &other, iterator begin_, iterator end_)
Splice a range of elements from another list into this one.
Definition: intrusive_list.h:1040
reference front()
Gets a reference to the first element.
Definition: intrusive_list.h:667
void insert(const_iterator position, TIterator first, TIterator last)
Inserts a range of values to the intrusive_list after the specified position.
Definition: intrusive_list.h:709
void merge(list_type &other, TCompare compare)
Merge another list into this one. Both lists should be sorted.
Definition: intrusive_list.h:1076
void sort(TCompare compare)
Definition: intrusive_list.h:843
void splice(iterator position, list_type &other, iterator isource)
Splice an element from another list into this one.
Definition: intrusive_list.h:1023
intrusive_list()
Constructor.
Definition: intrusive_list.h:594
iterator erase(const_iterator first, const_iterator last)
Definition: intrusive_list.h:749
const_iterator cend() const
Gets the end of the intrusive_list.
Definition: intrusive_list.h:659
iterator erase(iterator position)
Erases the value at the specified position.
Definition: intrusive_list.h:722
const_iterator cbegin() const
Gets the beginning of the intrusive_list.
Definition: intrusive_list.h:635
void remove_if(TPredicate predicate)
Removes according to a predicate.
Definition: intrusive_list.h:974
void sort()
Sort using in-place merge sort algorithm.
Definition: intrusive_list.h:812
iterator insert(const_iterator position, value_type &value)
Inserts a value to the intrusive_list before the specified position.
Definition: intrusive_list.h:699
const_reference front() const
Gets a const reference to the first element.
Definition: intrusive_list.h:675
iterator end()
Gets the end of the intrusive_list.
Definition: intrusive_list.h:643
intrusive_list(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Constructor from range.
Definition: intrusive_list.h:611
const_reference back() const
Gets a const reference to the last element.
Definition: intrusive_list.h:691
void merge(list_type &other)
Merge another list into this one. Both lists should be sorted.
Definition: intrusive_list.h:1067
ETL_NODISCARD ETL_CONSTEXPR14 bool is_sorted(TIterator begin, TIterator end)
Definition: algorithm.h:1441
ETL_CONSTEXPR14 TIterator remove(TIterator first, TIterator last, const T &value)
Definition: algorithm.h:1934
#define ETL_ASSERT(b, e)
Definition: error_handler.h:316
ETL_CONSTEXPR exception(string_type reason_, string_type, numeric_type line_)
Constructor.
Definition: exception.h:69
Definition: exception.h:47
enable_if
Definition: type_traits_generator.h:1191
is_integral
Definition: type_traits_generator.h:1001
bitset_ext
Definition: absolute.h:38
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:645
bool operator==(const etl::array< T, SIZE > &lhs, const etl::array< T, SIZE > &rhs)
Definition: array.h:633
iterator
Definition: iterator.h:399
Definition: functional.h:134