31#ifndef ETL_INTRUSIVE_FORWARD_LIST_INCLUDED
32#define ETL_INTRUSIVE_FORWARD_LIST_INCLUDED
59 :
exception(reason_, file_name_, line_number_)
129 :
intrusive_forward_list_exception(ETL_ERROR_TEXT(
"intrusive_forward_list:value is already linked", ETL_INTRUSIVE_FORWARD_LIST_FILE_ID
"E"), file_name_, line_number_)
138 template <
typename TLink>
144 typedef TLink link_type;
152 link_type* p_unlink =
start.etl_next;
156 link_type* p_next = p_unlink->etl_next;
168 template <
typename TIterator>
169 void assign(TIterator first, TIterator last)
171#if ETL_IS_DEBUG_BUILD
172 intmax_t d = etl::distance(first, last);
178 link_type* p_last = &
start;
183 while (first != last)
187 link_type& value = *first++;
191 value.etl_next = p_last->etl_next;
192 p_last->etl_next = &value;
213#if defined(ETL_CHECK_PUSH_POP)
230 link_type* current =
start.etl_next;
231 link_type* next =
start.etl_next;
235 next = next->etl_next;
236 current->etl_next = previous;
241 etl::link<link_type>(
start, previous);
288 return (
size() <= 1U);
297 etl::link_splice<link_type>(position, link);
306 link_type* p_next = link.etl_next;
308 if (p_next != &this->terminator)
310 link_type* p_unlinked = etl::unlink_after<link_type>(link);
321 return start.etl_next;
329 return start.etl_next;
342 template <
typename TLink>
350 template <
typename TValue,
typename TLink>
356 typedef typename etl::intrusive_forward_list_base<TLink>::link_type link_type;
359 typedef TValue value_type;
360 typedef value_type* pointer;
361 typedef const value_type* const_pointer;
362 typedef value_type& reference;
363 typedef const value_type& const_reference;
364 typedef size_t size_type;
379 : p_value(ETL_NULLPTR)
384 : p_value(other.p_value)
391 p_value = p_value->etl_next;
399 p_value = p_value->etl_next;
405 p_value = other.p_value;
409 reference operator *()
const
411 return *
static_cast<pointer
>(p_value);
416 return static_cast<pointer
>(p_value);
419 pointer operator ->()
const
421 return static_cast<pointer
>(p_value);
426 return lhs.p_value == rhs.p_value;
431 return !(lhs == rhs);
454 : p_value(ETL_NULLPTR)
459 : p_value(other.p_value)
464 : p_value(other.p_value)
471 p_value = p_value->etl_next;
479 p_value = p_value->etl_next;
485 p_value = other.p_value;
489 const_reference operator *()
const
491 return *
static_cast<const value_type*
>(p_value);
496 return static_cast<const value_type*
>(p_value);
499 const_pointer operator ->()
const
501 return static_cast<const value_type*
>(p_value);
506 return lhs.p_value == rhs.p_value;
511 return !(lhs == rhs);
521 const link_type* p_value;
524 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
543 template <
typename TIterator>
546 this->
assign(first, last);
618 return *
static_cast<pointer
>(this->
get_head());
626 return *
static_cast<const value_type*
>(this->
get_head());
643 template <
typename TIterator>
646 while (first != last)
681 if (first !=
end() && (first != last))
685 link_type* p_first = first.p_value;
686 link_type* p_last = last.p_value;
687 link_type* p_after = p_first->etl_next;
690 etl::link<link_type>(p_first, p_last);
693 link_type* p_unlink = p_after;
695 while (p_unlink != p_last)
697 link_type* p_next = p_unlink->etl_next;
721 template <
typename TIsEqual>
730 link_type* current = last->etl_next;
735 if (isEqual(*
static_cast<pointer
>(current), *
static_cast<pointer
>(last)))
745 current = last->etl_next;
782 template <
typename TCompare>
791 int number_of_merges;
806 number_of_merges = 0;
808 while (i_left !=
end())
815 for (
int i = 0; i < list_size; ++i)
821 if (i_right ==
end())
828 right_size = list_size;
831 while (left_size > 0 || (right_size > 0 && i_right !=
end()))
841 else if (right_size == 0 || i_right ==
end())
848 else if (!
compare(*i_right, *i_left))
866 etl::link<link_type>(i_head.p_value, i_link.p_value);
872 etl::link<link_type>(i_tail.p_value, i_link.p_value);
884 if (number_of_merges <= 1)
897 void remove(const_reference value)
902 while (i_item !=
end())
904 if (*i_item == value)
919 template <
typename TPredicate>
925 while (i_item !=
end())
927 if (predicate(*i_item))
949 link_type& first = *other.
get_head();
956 link_type& before = *position.p_value;
957 link_type& after = *position.p_value->etl_next;
959 etl::link<link_type>(before, first);
961 link_type* last = &before;
964 last = last->etl_next;
967 etl::link<link_type>(last, after);
979 link_type& before = *position.p_value;
981 etl::unlink<link_type>(*isource.p_value);
982 etl::link_splice<link_type>(before, *isource.p_value);
1000 size_t n = etl::distance(begin_, end_) - 1;
1005 link_type* first = begin_.p_value;
1006 link_type* last = first;
1008 while (last->etl_next != end_.p_value)
1010 last = last->etl_next;
1014 link_type* first_next = first->etl_next;
1015 etl::unlink_after(*first, *last);
1018 link_type* before = position.p_value;
1020 etl::link_splice<link_type>(*before, *first_next, *last);
1035 template <
typename TCompare>
1038 if ((
this != &other) && !other.
empty())
1040#if ETL_IS_DEBUG_BUILD
1045 link_type* other_begin = other.
get_head();
1046 link_type* other_terminal = &other.
terminator;
1048 link_type* before = &this->
start;
1049 link_type* before_next = get_next(before);
1052 while ((before->etl_next != terminal) && (other_begin != other_terminal))
1055 while ((before_next != terminal) && !(
compare(*
static_cast<pointer
>(other_begin), *
static_cast<pointer
>(before_next))))
1057 before = before_next;
1058 before_next = get_next(before_next);
1062 if (before_next != terminal)
1064 while ((other_begin != other_terminal) && (
compare(*
static_cast<pointer
>(other_begin), *
static_cast<pointer
>(before_next))))
1066 link_type* value = other_begin;
1067 other_begin = get_next(other_begin);
1068 etl::link_splice<link_type>(*before, *value);
1069 before = get_next(before);
1075 if (before_next == terminal)
1077 while (other_begin != other_terminal)
1079 link_type* value = other_begin;
1080 other_begin = get_next(other_begin);
1081 etl::link_splice<link_type>(*before, *value);
1082 before = get_next(before);
1097 link_type* get_next(link_type* link)
const
1099 return link->etl_next;
const_iterator
Definition: intrusive_forward_list.h:448
iterator.
Definition: intrusive_forward_list.h:372
Definition: intrusive_forward_list.h:140
bool is_trivial_list() const
Is the intrusive_forward_list a trivial length?
Definition: intrusive_forward_list.h:286
link_type start
The link pointer that acts as the intrusive_forward_list start.
Definition: intrusive_forward_list.h:262
void reverse()
Reverses the intrusive_forward_list.
Definition: intrusive_forward_list.h:222
void insert_link_after(link_type &position, link_type &link)
Insert a link.
Definition: intrusive_forward_list.h:294
~intrusive_forward_list_base()
Destructor.
Definition: intrusive_forward_list.h:278
bool empty() const
Returns true if the list has no elements.
Definition: intrusive_forward_list.h:247
static link_type terminator
The link that acts as the intrusive_forward_list terminator.
Definition: intrusive_forward_list.h:263
size_t current_size
Counts the number of elements in the list.
Definition: intrusive_forward_list.h:265
intrusive_forward_list_base()
Constructor.
Definition: intrusive_forward_list.h:270
void remove_link_after(link_type &link)
Remove a link.
Definition: intrusive_forward_list.h:304
void initialise()
Initialise the intrusive_forward_list.
Definition: intrusive_forward_list.h:335
void pop_front()
Removes a value from the front of the intrusive_forward_list.
Definition: intrusive_forward_list.h:211
link_type * get_head()
Get the head link.
Definition: intrusive_forward_list.h:319
const link_type * get_head() const
Get the head link.
Definition: intrusive_forward_list.h:327
void assign(TIterator first, TIterator last)
Definition: intrusive_forward_list.h:169
size_t size() const
Returns the number of elements.
Definition: intrusive_forward_list.h:255
void push_front(link_type &value)
Pushes a value to the front of the intrusive_forward_list.
Definition: intrusive_forward_list.h:201
void clear()
Clears the intrusive_forward_list.
Definition: intrusive_forward_list.h:149
Definition: intrusive_forward_list.h:69
Definition: intrusive_forward_list.h:55
Definition: intrusive_forward_list.h:97
Definition: intrusive_forward_list.h:83
Definition: intrusive_forward_list.h:111
Definition: intrusive_forward_list.h:125
Definition: intrusive_forward_list.h:352
const_iterator before_begin() const
Gets before the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:576
iterator erase_after(iterator first, iterator last)
Erases a range of elements.
Definition: intrusive_forward_list.h:679
void sort(TCompare compare)
Definition: intrusive_forward_list.h:783
const_iterator cbegin() const
Gets the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:584
void splice_after(iterator position, etl::intrusive_forward_list< TValue, TLink > &other)
Splice another list into this one.
Definition: intrusive_forward_list.h:942
~intrusive_forward_list()
Destructor.
Definition: intrusive_forward_list.h:536
void unique(TIsEqual isEqual)
Definition: intrusive_forward_list.h:722
void splice_after(iterator position, etl::intrusive_forward_list< TValue, TLink > &other, iterator begin_, iterator end_)
Splice a range of elements from another list into this one.
Definition: intrusive_forward_list.h:994
void splice_after(iterator position, etl::intrusive_forward_list< TValue, TLink > &other, iterator isource)
Splice an element from another list into this one.
Definition: intrusive_forward_list.h:977
void insert_after(iterator position, TIterator first, TIterator last)
Inserts a range of values to the intrusive_forward_list after the specified position.
Definition: intrusive_forward_list.h:644
intrusive_forward_list(TIterator first, TIterator last, typename etl::enable_if<!etl::is_integral< TIterator >::value, int >::type=0)
Constructor from range.
Definition: intrusive_forward_list.h:544
void remove_if(TPredicate predicate)
Removes according to a predicate.
Definition: intrusive_forward_list.h:920
iterator erase_after(iterator position)
Erases the value at the specified position.
Definition: intrusive_forward_list.h:660
iterator insert_after(iterator position, value_type &value)
Inserts a value to the intrusive_forward_list after the specified position.
Definition: intrusive_forward_list.h:632
const_iterator begin() const
Gets the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:560
void merge(list_type &other, TCompare compare)
Merge another list into this one. Both lists should be sorted.
Definition: intrusive_forward_list.h:1036
iterator end()
Gets the end of the intrusive_forward_list.
Definition: intrusive_forward_list.h:592
iterator before_begin()
Gets before the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:568
const_iterator end() const
Gets the end of the intrusive_forward_list.
Definition: intrusive_forward_list.h:600
const_reference front() const
Gets a const reference to the first element.
Definition: intrusive_forward_list.h:624
const_iterator cend() const
Gets the end of the intrusive_forward_list.
Definition: intrusive_forward_list.h:608
void merge(list_type &other)
Merge another list into this one. Both lists should be sorted.
Definition: intrusive_forward_list.h:1027
void sort()
Sort using in-place merge sort algorithm.
Definition: intrusive_forward_list.h:752
intrusive_forward_list()
Constructor.
Definition: intrusive_forward_list.h:529
iterator begin()
Gets the beginning of the intrusive_forward_list.
Definition: intrusive_forward_list.h:552
reference front()
Gets a reference to the first element.
Definition: intrusive_forward_list.h:616
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