utils-lists 4.0.2
The µOS++ Intrusive Lists
Loading...
Searching...
No Matches
lists-inlines.h
Go to the documentation of this file.
1/*
2 * This file is part of the µOS++ project (https://micro-os-plus.github.com/).
3 * Copyright (c) 2016 Liviu Ionescu. All rights reserved.
4 *
5 * Permission to use, copy, modify, and/or distribute this software
6 * for any purpose is hereby granted, under the terms of the MIT license.
7 *
8 * If a copy of the license was not distributed with this file, it can
9 * be obtained from https://opensource.org/licenses/mit.
10 */
11
23
24#ifndef MICRO_OS_PLUS_UTILS_LISTS_INLINES_H_
25#define MICRO_OS_PLUS_UTILS_LISTS_INLINES_H_
26
27// ----------------------------------------------------------------------------
28
29#ifdef __cplusplus
30
31// ----------------------------------------------------------------------------
32
33#if defined(__GNUC__)
34#pragma GCC diagnostic push
35
36#pragma GCC diagnostic ignored "-Waggregate-return"
37#if defined(__clang__)
38#pragma clang diagnostic ignored "-Wc++98-compat"
39#endif
40#endif
41
42// ----------------------------------------------------------------------------
43
45{
46 // ==========================================================================
47
76 {
77 // Must be empty! No members must be changed by this constructor!
78 }
79
94 {
95 // Must be empty! No members must be changed by this constructor!
96 }
97
112 constexpr void
114 {
115 previous_ = this;
116 next_ = this;
117 }
118
119#pragma GCC diagnostic push
120
121#if defined(__GNUC__) && !defined(__clang__)
122#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
123#endif
124
136 constexpr double_list_links_base*
138 {
139 return next_;
140 }
141
153 constexpr double_list_links_base*
155 {
156 return previous_;
157 }
158
159#pragma GCC diagnostic pop
160
161 // ==========================================================================
162
190 {
191 // Must be empty! No members must be changed by this constructor!
192 }
193
194#pragma GCC diagnostic push
195
196#if defined(__clang__)
197#pragma GCC diagnostic ignored "-Wdocumentation-unknown-command"
198#endif
219#pragma GCC diagnostic pop
221 {
222 // The goal is to revert the content to a state similar to the
223 // statically initialised state (BSS zero).
224 // Unfortunately GCC does not honour this.
225 // next_ = nullptr;
226 // previous_ = nullptr;
227 }
228
229 // ==========================================================================
230
255 {
256 // For regular (non static) classes the members
257 // must be explicitly initialised.
258 initialize ();
259 }
260
269
270 // ==========================================================================
271
284 template <class T, class N, class U>
288
297 template <class T, class N, class U>
299 iterator_pointer const node)
300 : node_{ node }
301 {
302 }
303
304#if 0
305 template <class T, class N, class U>
307 reference element)
308 : node_{ &(element.*MP) }
309 {
310 static_assert (std::is_convertible<U, T>::value == true,
311 "U must be implicitly convertible to T!");
312 }
313#endif
314
323 template <class T, class N, class U>
326 {
327 return get_pointer ();
328 }
329
341 template <class T, class N, class U>
344 {
345 return *get_pointer ();
346 }
347
356 template <class T, class N, class U>
359 {
360 node_ = static_cast<N*> (node_->next ());
361 return *this;
362 }
363
372 template <class T, class N, class U>
375 {
376 const auto tmp = *this;
377 node_ = static_cast<iterator_pointer> (node_->next);
378 return tmp;
379 }
380
389 template <class T, class N, class U>
392 {
393 node_ = static_cast<iterator_pointer> (node_->previous);
394 return *this;
395 }
396
405 template <class T, class N, class U>
408 {
409 const auto tmp = *this;
410 node_ = static_cast<iterator_pointer> (node_->previous);
411 return tmp;
412 }
413
422 template <class T, class N, class U>
423 constexpr bool
425 const double_list_iterator& other) const
426 {
427 return node_ == other.node_;
428 }
429
438 template <class T, class N, class U>
439 constexpr bool
441 const double_list_iterator& other) const
442 {
443 return node_ != other.node_;
444 }
445
453 template <class T, class N, class U>
459
460 // ==========================================================================
461
485 template <class T, class L>
487 {
488#if defined(MICRO_OS_PLUS_TRACE_UTILS_LISTS_CONSTRUCT)
489 trace::printf ("%s() @%p \n", __func__, this);
490#endif
491
492 if constexpr (is_statically_allocated::value)
493 {
494 // By all means, do not add any code to clear the pointers, since
495 // the links node was statically initialised.
496 }
497 else
498 {
499 clear ();
500 }
501 }
502
515 template <class T, class L>
517 {
518#if defined(MICRO_OS_PLUS_TRACE_UTILS_LISTS_CONSTRUCT)
519 trace::printf ("%s() @%p \n", __func__, this);
520#endif
521
522 // Perhaps enable it for non statically allocated lists.
523 // assert (empty ());
524#if defined(MICRO_OS_PLUS_TRACE_UTILS_LISTS)
525 if (!empty ())
526 {
527 trace::printf ("%s() @%p list not empty\n", __func__, this);
529#endif
530 }
531
535 * Only statically allocated nodes in the initial state are considered
536 * _uninitialized_. For dynamically allocated lists, this method always
537 * returns `false` since their nodes are explicitly initialized during
538 * construction.
539 */
540 template <class T, class L>
541 bool
543 {
544 if constexpr (is_statically_allocated::value)
545 {
546 return links_.uninitialized ();
547 }
548 else
549 {
550 return false;
551 }
552 }
553
554 /**
555 * @details
556 * If the statically allocated list is still in the initial
557 * _uninitialised_ state (with both pointers null), this method
558 * initialises the list to the empty state, with both pointers
559 * pointing to itself. For non-statically initialised lists,
560 * this method has no effect.
561 *
562 * @note
563 * Must be manually called for statically allocated lists before
564 * inserting elements or performing any other operations.
565 */
566 template <class T, class L>
567 void
569 {
570 if constexpr (is_statically_allocated::value)
571 {
572 links_.initialize_once ();
573 }
574 }
575
578 * Checks whether the list contains any nodes.
579 * The list is considered empty if the internal links node is not linked to
580 * any other nodes. This method provides a fast way to determine if the list
581 * has elements or is currently empty.
582 */
583 template <class T, class L>
584 bool
587 // If the links node is not linked, the list is empty.
588 return !links_.linked ();
589 }
590
594 * both its `previous_` and `next_` pointers refer to itself. This marks the
595 * list as empty and ensures it is in a safe, known state, ready for new
596 * insertions. This operation is typically used to reset the list, removing
597 * all elements and breaking any existing links.
598 */
599 template <class T, class L>
600 void
602 {
603#if defined(MICRO_OS_PLUS_TRACE_UTILS_LISTS)
604 trace::printf ("%s() @%p\n", __func__, this);
605#endif
606 links_.initialize ();
607 }
608
614 * The returned pointer should be checked against `end()` or the sentinel
615 * node to determine if the list contains any elements.
616 */
617 template <class T, class L>
618 constexpr typename double_list<T, L>::pointer
620 {
621 return reinterpret_cast<pointer> (links_.next ());
622 }
623
632 template <class T, class L>
633 constexpr typename double_list<T, L>::pointer
635 {
636 return reinterpret_cast<pointer> (links_.previous ());
637 }
638
647 template <class T, class L>
648 void
650 {
651 if constexpr (is_statically_allocated::value)
652 {
653 assert (!links_.uninitialized ());
654 }
655
656 // Add new node at the end of the list.
657 tail ()->link_next (&node);
658 }
659
668 template <class T, class L>
669 void
671 {
672 if constexpr (is_statically_allocated::value)
673 {
674 assert (!links_.uninitialized ());
675 }
676
677 // Add the new node at the head of the list.
678 head ()->link_previous (&node);
679 }
680
689 template <class T, class L>
692 {
693 if constexpr (is_statically_allocated::value)
694 {
695 assert (!links_.uninitialized ());
696 }
697
698 return iterator{ static_cast<iterator_pointer> (links_.next ()) };
699 }
700
709 template <class T, class L>
712 {
713 // The assert would probably be redundant, since it was
714 // already tested in `begin()`.
715
716 return iterator{ reinterpret_cast<iterator_pointer> (
717 const_cast<links_type*> (&links_)) };
718 }
719
720 // ==========================================================================
721
722 /**
723 * @details
724 * The default constructor for `intrusive_list_iterator` initialises the
725 * iterator to a null state, meaning it does not point to any node in the
726 * list. This is typically used to create an "end" iterator or to initialise
727 * an iterator variable before assigning it to a valid node.
728 *
729 * @note
730 * The internal node pointer is value-initialised (set to `nullptr`),
731 * ensuring that the iterator is safe to use in comparisons and will not
732 * dereference an invalid address.
733 */
734 template <class T, class N, N T::* MP, class U>
739
748 template <class T, class N, N T::* MP, class U>
750 N* const node)
751 : node_{ node }
752 {
753 }
754
763 template <class T, class N, N T::* MP, class U>
765 reference element)
766 : node_{ &(element.*MP) }
767 {
768 static_assert (std::is_convertible<U, T>::value == true,
769 "U must be implicitly convertible to T!");
771
780 template <class T, class N, N T::* MP, class U>
784 return get_pointer ();
785 }
786
794 * This allows the iterator to be used in a manner similar to standard C++
795 * iterators, enabling direct access to the list element for reading or
796 * modification.
797 */
798 template <class T, class N, N T::* MP, class U>
804
805 /**
806 * @details
807 * The pre-increment operator (`operator++`) advances the intrusive list
808 * iterator to the next node in the list. It updates the internal node
809 * pointer to point to the node returned by the current node's `next()`
810 * method. This enables forward traversal of the list, following the linked
811 * structure.
812 */
813 template <class T, class N, N T::* MP, class U>
817 node_ = static_cast<iterator_pointer> (node_->next ());
818 return *this;
819 }
820
826 * requires access to the current element before moving to the next one,
827 * following the standard C++ iterator semantics for post-increment.
828 */
829 template <class T, class N, N T::* MP, class U>
832 {
833 const auto tmp = *this;
834 node_ = static_cast<iterator_pointer> (node_->next ());
835 return tmp;
837
846 template <class T, class N, N T::* MP, class U>
849 {
850 node_ = static_cast<iterator_pointer> (node_->previous ());
851 return *this;
852 }
853
856 * The post-decrement operator (`operator--(int)`) moves the intrusive list
857 * iterator to the previous node in the list, but returns a copy of the
858 * iterator as it was before the decrement. This enables iteration logic that
859 * requires access to the current element before moving backward, following
860 * the standard C++ iterator semantics for post-decrement.
861 */
862 template <class T, class N, N T::* MP, class U>
865 {
866 const auto tmp = *this;
867 node_ = static_cast<iterator_pointer> (node_->previous ());
868 return tmp;
869 }
870
874 * intrusive list iterators point to the same node in the list by comparing
875 * their internal node pointers. This enables standard iterator comparisons,
876 * such as detecting the end of a range or verifying if two iterators refer
877 * to the same position within the list.
878 */
879 template <class T, class N, N T::* MP, class U>
880 inline bool
882 const intrusive_list_iterator& other) const
883 {
884 return node_ == other.node_;
885 }
886
895 template <class T, class N, N T::* MP, class U>
896 inline bool
898 const intrusive_list_iterator& other) const
899 {
900 return node_ != other.node_;
901 }
902
912 template <class T, class N, N T::* MP, class U>
915 {
916 // static_assert(std::is_convertible<U, T>::value == true, "U must be
917 // implicitly convertible to T!");
918
919 // Compute the distance between the member intrusive link
920 // node and the class begin.
921 const auto offset = reinterpret_cast<difference_type> (
922 &(static_cast<T*> (nullptr)->*MP));
923
924 // Compute the address of the object which includes the
925 // intrusive node, by adjusting down the node address.
926 return reinterpret_cast<pointer> (reinterpret_cast<difference_type> (node_)
927 - offset);
928 }
929
936 template <class T, class N, N T::* MP, class U>
942
943 // ==========================================================================
944
960 template <class T, class N, N T::* MP, class L, class U>
964
967 * The destructor for `intrusive_list` does not perform any cleanup or
968 * pointer manipulation. List management and node unlinking are handled
969 * elsewhere, so the destructor is intentionally left empty to avoid
970 * unnecessary writes or side effects during object destruction.
971 */
972 template <class T, class N, N T::* MP, class L, class U>
975 }
976
982 * initialised lists, this method has no effect.
983 *
984 * @note
985 * Must be manually called for statically allocated lists before inserting
986 * elements or performing any other operations.
987 */
988 template <class T, class N, N T::* MP, class L, class U>
989 void
994
1002 template <class T, class N, N T::* MP, class L, class U>
1003 constexpr bool
1005 {
1006 return double_list<N, L>::empty ();
1007 }
1008
1009 /**
1010 * @details
1011 * Adds a new node to the end (tail) of the intrusive list.
1012 * The offset of the intrusive node member within the containing object is
1013 * computed, and the node is linked after the current tail node. This
1014 * operation does not check for duplicate nodes or whether the node is
1015 * already linked elsewhere. For statically allocated lists, the
1016 * initialisation check is handled by the links class.
1018 template <class T, class N, N T::* MP, class L, class U>
1019 void
1021 {
1022 // The assert(links_.initialised()) is checked by the L class.
1023
1024 // Compute the distance between the member intrusive link
1025 // node and the class begin.
1026 const auto offset = reinterpret_cast<difference_type> (
1027 &(static_cast<T*> (nullptr)->*MP));
1028
1029 // Add thread intrusive node at the end of the list.
1030 (const_cast<N*> (double_list<N, L>::tail ()))
1031 ->link_next (reinterpret_cast<N*> (
1032 reinterpret_cast<difference_type> (&node) + offset));
1034
1044 template <class T, class N, N T::* MP, class L, class U>
1045 void
1047 {
1048 // The assert(links_.initialised()) is checked by the L class.
1049
1050 // Compute the distance between the member intrusive link
1051 // node and the class begin.
1052 const auto offset = reinterpret_cast<difference_type> (
1053 &(static_cast<T*> (nullptr)->*MP));
1054
1055 // Add thread intrusive node at the end of the list.
1056 (const_cast<N*> (double_list<N, L>::head ()))
1057 ->link_previous (reinterpret_cast<N*> (
1058 reinterpret_cast<difference_type> (&node) + offset));
1059 }
1060
1061#if defined(__GNUC__)
1062#pragma GCC diagnostic push
1063#pragma GCC diagnostic ignored "-Waggregate-return"
1064#endif
1065
1072 * `end()`.
1073 */
1074 template <class T, class N, N T::* MP, class L, class U>
1077 {
1078 // The assert(links_.initialised()) is checked by the L class.
1079
1080 return iterator{ static_cast<iterator_pointer> (
1081 double_list<N, L>::links_.next ()) };
1082 }
1083
1092 template <class T, class N, N T::* MP, class L, class U>
1095 {
1096 // The assert would probably be redundant, since it was
1097 // already tested in `begin()`.
1098
1099 using head_type_ = typename double_list<N, L>::links_type;
1100 return iterator{ reinterpret_cast<iterator_pointer> (
1101 const_cast<head_type_*> (double_list<N, L>::links_pointer ())) };
1102 }
1103
1104#if defined(__GNUC__)
1105#pragma GCC diagnostic pop
1106#endif
1107
1117 template <class T, class N, N T::* MP, class L, class U>
1120 {
1121 // static_assert(std::is_convertible<U, T>::value == true, "U must be
1122 // implicitly convertible to T!");
1123
1124 // Compute the distance between the member intrusive link
1125 // node and the class begin.
1126 const auto offset = reinterpret_cast<difference_type> (
1127 &(static_cast<T*> (nullptr)->*MP));
1128
1129 // Compute the address of the object which includes the
1130 // intrusive node, by adjusting down the node address.
1131 return reinterpret_cast<pointer> (reinterpret_cast<difference_type> (node)
1132 - offset);
1133 }
1134
1143 template <class T, class N, N T::* MP, class L, class U>
1146 {
1147 // No assert here, treat empty link unlinks as nop.
1148
1149 // The first element in the list.
1151 = static_cast<iterator_pointer> (double_list<N, L>::links_.next ());
1152 it->unlink ();
1153
1154 return get_pointer (it);
1155 }
1156
1165 template <class T, class N, N T::* MP, class L, class U>
1168 {
1169 // No assert here, treat empty link unlinks as nop.
1170
1171 // The last element in the list.
1172 iterator_pointer it = static_cast<iterator_pointer> (
1173 double_list<N, L>::links_.previous ());
1174 it->unlink ();
1175
1176 return get_pointer (it);
1177 }
1178
1179 // ==========================================================================
1180} // namespace micro_os_plus::utils
1181
1182#if defined(__GNUC__)
1183#pragma GCC diagnostic pop
1184#endif
1185
1186// ----------------------------------------------------------------------------
1187
1188#endif // __cplusplus
1189
1190// ----------------------------------------------------------------------------
1191
1192#endif // MICRO_OS_PLUS_UTILS_LISTS_INLINES_H_
1193
1194// ----------------------------------------------------------------------------
A class template for a doubly linked list forward iterator.
Definition lists.h:490
constexpr bool operator==(const double_list_iterator &other) const
Equality comparison operator.
constexpr iterator_pointer get_iterator_pointer(void) const
Get the internal iterator pointer (node pointer).
constexpr pointer operator->() const
Pointer access operator.
value_type * pointer
Type of pointer to object pointed to by the iterator.
Definition lists.h:500
constexpr pointer get_pointer(void) const
Get a pointer to the value pointed to by the iterator.
constexpr double_list_iterator & operator--()
Pre-decrement operator.
constexpr bool operator!=(const double_list_iterator &other) const
Inequality comparison operator.
constexpr double_list_iterator & operator++()
Pre-increment operator.
constexpr reference operator*() const
Dereference operator.
value_type & reference
Type of reference to object pointed to by the iterator.
Definition lists.h:505
iterator_pointer node_
Pointer to the node.
Definition lists.h:640
constexpr double_list_iterator()
Default constructor. Constructs an iterator pointing to nullptr.
N * iterator_pointer
Type of reference to the iterator internal pointer.
Definition lists.h:510
constexpr const links_type * links_pointer(void) const
Get the address of the node storing the list links.
Definition lists.h:886
void link_head(reference node)
Add a node to the head of the list.
links_type links_
The list top node used to point to head and tail nodes.
Definition lists.h:904
L links_type
Type of the links node object where the pointers to the list head and tail are stored.
Definition lists.h:686
value_type * iterator_pointer
Type of reference to the iterator internal pointer.
Definition lists.h:711
constexpr pointer tail(void) const
Get the list tail.
void initialize_once(void)
Initialize the list only at first run.
value_type * pointer
Type of pointer to object pointed to by the iterator.
Definition lists.h:696
constexpr ~double_list()
Destruct the list.
value_type & reference
Type of reference to object pointed to by the iterator.
Definition lists.h:701
double_list()
Construct a doubly linked list.
void clear(void)
Clear the list.
constexpr pointer head(void) const
Get the list head.
iterator end() const
Iterator end.
iterator begin() const
Iterator begin.
double_list_iterator< value_type > iterator
Type of iterator over the values.
Definition lists.h:706
bool empty(void) const
Check if the list is empty.
void link_tail(reference node)
Add a node to the tail of the list.
bool uninitialized(void) const
Check if the list is uninitialised (only statically allocated lists can be uninitialised).
A class template for the intrusive list iterator.
Definition lists.h:929
value_type * pointer
Type of pointer to object pointed to by the iterator.
Definition lists.h:939
pointer get_pointer(void) const
Get the object node from the intrusive node.
intrusive_list_iterator & operator++()
Pre-increment operator.
iterator_pointer get_iterator_pointer(void) const
Retrieve the iterator pointer for the current node.
N * iterator_pointer
Type of reference to the iterator internal pointer.
Definition lists.h:949
reference operator*() const
Dereference operator.
bool operator==(const intrusive_list_iterator &other) const
Equality comparison operator.
value_type & reference
Type of reference to object pointed to by the iterator.
Definition lists.h:944
constexpr intrusive_list_iterator()
Default constructor. Constructs an iterator pointing to nullptr.
bool operator!=(const intrusive_list_iterator &other) const
Inequality comparison operator.
pointer operator->() const
Pointer access operator.
intrusive_list_iterator & operator--()
Pre-decrement operator.
ptrdiff_t difference_type
Type of pointer difference.
Definition lists.h:954
iterator_pointer node_
Pointer to intrusive node.
Definition lists.h:1081
constexpr intrusive_list()
Construct an intrusive doubly linked list.
constexpr bool empty(void) const
Check if the list is empty.
void link_tail(reference node)
Add a node to the tail of the list.
N * iterator_pointer
Type of reference to the iterator internal pointer.
Definition lists.h:1178
iterator begin() const
Iterator begin.
pointer unlink_head(void)
Unlink the first element from the list.
void link_head(reference node)
Add a node to the head of the list.
constexpr ~intrusive_list()
Destruct the list.
intrusive_list_iterator< T, N, MP, U > iterator
Type of iterator over the values.
Definition lists.h:1167
void initialize_once(void)
Initialize the list only at first run.
iterator end() const
Iterator begin.
ptrdiff_t difference_type
Type of pointer difference.
Definition lists.h:1183
value_type * pointer
Type of pointer to object pointed to by the iterator.
Definition lists.h:1157
pointer unlink_tail(void)
Unlink the last element from the list.
pointer get_pointer(iterator_pointer node) const
Get the address of the object from the intrusive node pointer.
The µOS++ utilities definitions.