intrusive_list Class Template
A class template for a list of nodes which store the links inside themselves as intrusive nodes. More...
Declaration
class micro_os_plus::utils::intrusive_list<T, N, MP, L, U> { ... }
Included Headers
Base class
| class | doubly_list<T, L> |
|
A class template for a doubly linked list of nodes. More... | |
Public Member Typedefs Index
template < ... > | |
| using | difference_type = ptrdiff_t |
|
Type of pointer difference. More... | |
template < ... > | |
| using | is_statically_allocated = typename links_type::is_statically_allocated |
|
Type indicating if the links node is statically allocated. More... | |
template < ... > | |
| using | iterator = intrusive_list_iterator< T, N, MP, U > |
|
Type of iterator over the values. More... | |
template < ... > | |
| using | iterator_pointer = N * |
|
Type of reference to the iterator internal pointer. More... | |
template < ... > | |
| using | links_type = L |
|
Type of the list links node object where the pointers to the list head and tail are stored. More... | |
template < ... > | |
| using | pointer = value_type * |
|
Type of pointer to object pointed to by the iterator. More... | |
template < ... > | |
| using | reference = value_type & |
|
Type of reference to object pointed to by the iterator. More... | |
template < ... > | |
| using | reverse_iterator = std::reverse_iterator< iterator > |
|
Type of reverse iterator over the values. More... | |
template < ... > | |
| using | value_type = U |
|
Type of value pointed to by the iterator. More... | |
Public Constructors Index
template < ... > | |
| constexpr | intrusive_list () noexcept |
|
Construct an intrusive doubly linked list. More... | |
template < ... > | |
| intrusive_list (const intrusive_list &)=delete | |
|
Deleted copy constructor. More... | |
template < ... > | |
| intrusive_list (intrusive_list &&)=delete | |
|
Deleted move constructor. More... | |
Public Destructor Index
template < ... > | |
| constexpr | ~intrusive_list () |
|
Destruct the list. More... | |
Public Operators Index
template < ... > | |
| intrusive_list & | operator= (const intrusive_list &)=delete |
|
Deleted copy assignment operator. More... | |
template < ... > | |
| intrusive_list & | operator= (intrusive_list &&)=delete |
|
Deleted move assignment operator. More... | |
Public Member Functions Index
template < ... > | |
| iterator | begin () const noexcept |
|
Iterator begin. More... | |
template < ... > | |
| void | clear (void) noexcept |
|
Clear the list. More... | |
template < ... > | |
| constexpr bool | empty (void) const noexcept |
|
Check if the list is empty. More... | |
template < ... > | |
| iterator | end () const noexcept |
|
Iterator end. More... | |
template < ... > | |
| constexpr pointer | head (void) const noexcept |
|
Get the list head. More... | |
template < ... > | |
| bool | initialise_once (void) noexcept |
|
Initialise the list only at first run. More... | |
template < ... > | |
| bool | initialised (void) const noexcept |
|
Check if the list is initialised (only statically allocated lists can be uninitialised). More... | |
template < ... > | |
| void | link_head (reference node) noexcept |
|
Add a node to the head of the list. More... | |
template < ... > | |
| void | link_tail (reference node) noexcept |
|
Add a node to the tail of the list. More... | |
template < ... > | |
| constexpr const links_type * | links_pointer (void) const noexcept |
|
Get the address of the node storing the list links. More... | |
template < ... > | |
| reverse_iterator | rbegin () const noexcept |
|
Reverse iterator begin. More... | |
template < ... > | |
| reverse_iterator | rend () const noexcept |
|
Reverse iterator end. More... | |
template < ... > | |
| constexpr pointer | tail (void) const noexcept |
|
Get the list tail. More... | |
template < ... > | |
| pointer | unlink_head (void) noexcept |
|
Unlink the first element from the list. More... | |
template < ... > | |
| pointer | unlink_tail (void) noexcept |
|
Unlink the last element from the list. More... | |
Protected Member Functions Index
template < ... > | |
| pointer | get_pointer (iterator_pointer node) const noexcept |
|
Get the address of the object from the intrusive node pointer. More... | |
Protected Member Attributes Index
template < ... > | |
| links_type | links_ |
|
The list top node used to point to head and tail nodes. More... | |
Description
A class template for a list of nodes which store the links inside themselves as intrusive nodes.
- Template Parameters
-
T Type of object that includes the intrusive node.
N Type of intrusive node with the next & previous links.
MP Name of the intrusive node member in object T.
L Type of the links node (one of doubly_list_links or static_doubly_list_links).
U Type stored in the list, derived from T.
This class implements an intrusive doubly linked list, where each object stores its own link node as a member. The list maintains a pair of head and tail pointers, allowing efficient insertion, removal, and iteration. The intrusive approach eliminates the need for separate node allocations, as the links are embedded within the objects themselves.
The template parameter MP specifies the member pointer to the intrusive node within the object, enabling the list to compute the address of the parent object from the node pointer. This design supports both regular and statically allocated lists, depending on the type used for L.
Iterators provide access to the objects in the list, supporting bidirectional traversal.
Example
For statically allocated lists, set L=static_doubly_list_links.
Definition at line 278 of file intrusive-list.h.
Public Member Typedefs
difference_type
|
Type of pointer difference.
Definition at line 326 of file intrusive-list.h.
is_statically_allocated
|
Type indicating if the links node is statically allocated.
Definition at line 315 of file intrusive-list.h.
iterator
|
Type of iterator over the values.
Definition at line 305 of file intrusive-list.h.
iterator_pointer
|
Type of reference to the iterator internal pointer.
Definition at line 321 of file intrusive-list.h.
links_type
|
Type of the list links node object where the pointers to the list head and tail are stored.
Definition at line 285 of file intrusive-list.h.
pointer
|
Type of pointer to object pointed to by the iterator.
Definition at line 295 of file intrusive-list.h.
reference
|
Type of reference to object pointed to by the iterator.
Definition at line 300 of file intrusive-list.h.
reverse_iterator
|
Type of reverse iterator over the values.
Definition at line 310 of file intrusive-list.h.
value_type
|
Type of value pointed to by the iterator.
Definition at line 290 of file intrusive-list.h.
Public Constructors
intrusive_list()
| constexpr noexcept |
Construct an intrusive doubly linked list.
The default constructor for intrusive_list creates an empty intrusive list. No initialisation of internal pointers is performed here; for statically allocated lists, the pointers are expected to be zero-initialised by the runtime, while for dynamically allocated lists, initialisation is handled by the base class or explicit methods.
- The rule of five
The copy constructor, move constructor, copy assignment operator, and move assignment operator are explicitly deleted to prevent accidental copying or moving of intrusive_list objects. This ensures the integrity of the list structure, as duplicating or moving lists could result in invalid or inconsistent links within the list.
Declaration at line 331 of file intrusive-list.h, definition at line 282 of file intrusive-list-inlines.h.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::intrusive_list, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::intrusive_list, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator= and micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator=.
intrusive_list()
| delete |
Deleted copy constructor.
Copying of intrusive_list instances is explicitly disallowed to prevent accidental duplication, which could compromise the integrity of the list structure.
Definition at line 343 of file intrusive-list.h.
Reference micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::intrusive_list.
intrusive_list()
| delete |
Deleted move constructor.
Moving of intrusive_list instances is explicitly disallowed to avoid invalid or inconsistent links within the list that could result from moving lists.
Definition at line 353 of file intrusive-list.h.
Reference micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::intrusive_list.
Public Destructor
~intrusive_list()
| constexpr |
Destruct the list.
The destructor for intrusive_list does not perform any cleanup or pointer manipulation. List management and node unlinking are handled elsewhere, so the destructor is intentionally left empty to avoid unnecessary writes or side effects during object destruction.
Declaration at line 381 of file intrusive-list.h, definition at line 298 of file intrusive-list-inlines.h.
Public Operators
operator=()
| delete |
Deleted copy assignment operator.
Copy assignment is explicitly disallowed to prevent accidental overwriting of list objects, which could lead to corruption of the list structure.
Definition at line 364 of file intrusive-list.h.
Reference micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::intrusive_list.
operator=()
| delete |
Deleted move assignment operator.
Move assignment is explicitly disallowed to avoid invalid or inconsistent links within the list that could result from moving lists.
Definition at line 375 of file intrusive-list.h.
References micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::intrusive_list, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::begin, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::empty, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::end, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::get_pointer, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::initialise_once, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::link_head, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::link_tail, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::rbegin, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::rend, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::unlink_head and micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::unlink_tail.
Public Member Functions
begin()
| inline nodiscard noexcept |
Iterator begin.
- Returns
An iterator positioned at the first element.
Returns an iterator to the first element in the intrusive list. The iterator points to the node after the internal links node (the head). For statically allocated lists, the initialisation check is handled by the links class. If the list is empty, the iterator will compare equal to end().
Declaration at line 456 of file intrusive-list.h, definition at line 422 of file intrusive-list-inlines.h.
Reference micro_os_plus::utils::doubly_list< T, L >::links_.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator= and micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::rend.
clear()
| noexcept |
Clear the list.
- Parameters
None.
- Returns
Nothing.
The clear() method initialises the mandatory internal links node so that both its previous_ and next_ pointers refer to itself. This marks the list as empty and ensures it is in a safe, known state, ready for new insertions. This operation is typically used to reset the list, removing all elements and breaking any existing links.
Declaration at line 392 of file doubly-list.h, definition at line 394 of file doubly-list-inlines.h.
empty()
| nodiscard constexpr noexcept |
Check if the list is empty.
- Parameters
None.
- Return Values
-
true The list has no nodes.
false The list has at least one node.
Checks whether the intrusive list contains any nodes. This method delegates to the underlying double list implementation to determine if the list is empty. The list is considered empty if there are no elements linked.
Declaration at line 404 of file intrusive-list.h, definition at line 334 of file intrusive-list-inlines.h.
Reference micro_os_plus::utils::doubly_list< T, L >::empty.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator=, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::unlink_head and micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::unlink_tail.
end()
| inline nodiscard noexcept |
Iterator end.
- Returns
An iterator positioned after the last element.
Returns an iterator to the position after the last element in the intrusive list (the end iterator). This iterator points to the internal links node, which acts as a sentinel. It is used as the past-the-end marker in iteration and comparison operations. The end iterator does not reference any valid list element.
Declaration at line 464 of file intrusive-list.h, definition at line 445 of file intrusive-list-inlines.h.
Reference micro_os_plus::utils::doubly_list< T, L >::links_pointer.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator= and micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::rbegin.
head()
| nodiscard constexpr noexcept |
Get the list head.
- Parameters
None.
- Returns
Pointer to the head node.
Returns a pointer to the first node in the list. If the list is empty, this will point to the internal links node itself, which can be used to detect the end of the list during iteration. The returned pointer should be checked against end() or the sentinel node to determine if the list contains any elements.
Declaration at line 402 of file doubly-list.h, definition at line 413 of file doubly-list-inlines.h.
initialise_once()
| noexcept |
Initialise the list only at first run.
- Parameters
None.
- Returns
true if the list was initialised, false otherwise.
If the statically allocated list is still in the initial uninitialised state (with both pointers null), this method initialises the list to the empty state, with both pointers pointing to itself. For non-statically initialised lists, this method has no effect.
Must be manually called for statically allocated lists before inserting elements or performing any other operations.
Declaration at line 393 of file intrusive-list.h, definition at line 319 of file intrusive-list-inlines.h.
Reference micro_os_plus::utils::doubly_list< T, L >::initialise_once.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator=.
initialised()
| nodiscard noexcept |
Check if the list is initialised (only statically allocated lists can be uninitialised).
- Parameters
None.
- Return Values
-
true The list was initialised.
false The list was not initialised.
An uninitialised node is a node with any of the pointers set to nullptr. Only statically allocated nodes in the initial state are considered uninitialised. For dynamically allocated lists, this method always returns true since their nodes are explicitly initialised during construction.
Declaration at line 359 of file doubly-list.h, definition at line 327 of file doubly-list-inlines.h.
Reference micro_os_plus::utils::doubly_list< N, doubly_list_links >::links_.
link_head()
| noexcept |
Add a node to the head of the list.
- Parameters
-
[in] node Reference to a list node.
- Returns
Nothing.
Adds a new node to the beginning (head) of the intrusive list. The offset of the intrusive node member within the containing object is computed, and the node is linked before the current head node. This operation does not check for duplicate nodes or whether the node is already linked elsewhere. For statically allocated lists, the initialisation check is handled by the links class.
Declaration at line 424 of file intrusive-list.h, definition at line 384 of file intrusive-list-inlines.h.
Reference micro_os_plus::utils::doubly_list< T, L >::head.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator=.
link_tail()
| noexcept |
Add a node to the tail of the list.
- Parameters
-
[in] node Reference to a list node.
- Returns
Nothing.
Adds a new node to the end (tail) of the intrusive list. The offset of the intrusive node member within the containing object is computed, and the node is linked after the current tail node. This operation does not check for duplicate nodes or whether the node is already linked elsewhere. For statically allocated lists, the initialisation check is handled by the links class.
Declaration at line 414 of file intrusive-list.h, definition at line 351 of file intrusive-list-inlines.h.
Reference micro_os_plus::utils::doubly_list< T, L >::tail.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator=.
links_pointer()
| nodiscard constexpr noexcept |
Get the address of the node storing the list links.
- Parameters
None.
- Returns
A pointer to the internal links node.
Returns the address of the links_ member. This method is required by derived classes (such as intrusive_list) when constructing their end() iterator, where a direct reference to the protected member is not accessible.
Returns the address of the links_ member directly. This method is required by derived classes (such as intrusive_list) when constructing their end() iterator, where a direct reference to the protected member is not accessible from the derived scope.
Declaration at line 484 of file doubly-list.h, definition at line 567 of file doubly-list-inlines.h.
rbegin()
| inline nodiscard noexcept |
Reverse iterator begin.
- Returns
A reverse iterator positioned at the last element.
Returns a reverse iterator to the last element in the intrusive list. Equivalent to reverse_iterator{ end() }. Traversal proceeds from the tail towards the head.
Declaration at line 472 of file intrusive-list.h, definition at line 468 of file intrusive-list-inlines.h.
Reference micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::end.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator=.
rend()
| inline nodiscard noexcept |
Reverse iterator end.
- Returns
A reverse iterator positioned before the first element.
Returns a reverse iterator to the position before the first element in the intrusive list. Equivalent to reverse_iterator{ begin() }. Used as the past-the-end marker for reverse-direction iteration.
Declaration at line 480 of file intrusive-list.h, definition at line 482 of file intrusive-list-inlines.h.
Reference micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::begin.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator=.
tail()
| nodiscard constexpr noexcept |
Get the list tail.
- Parameters
None.
- Returns
Pointer to the tail node.
Returns a pointer to the last node in the list. If the list is empty, this will point to the internal links node itself, which can be used to detect the end of the list during reverse iteration. The returned pointer should be checked against the sentinel node to determine if the list contains any elements.
Declaration at line 412 of file doubly-list.h, definition at line 428 of file doubly-list-inlines.h.
unlink_head()
| nodiscard noexcept |
Unlink the first element from the list.
- Parameters
None.
- Returns
Pointer to the first element in the list, or nullptr if the list is empty.
Removes and unlinks the first element from the intrusive list. If the list is empty, returns nullptr immediately without modifying the list. The method unlinks the node at the head of the list and returns a pointer to the parent object containing the unlinked node.
Declaration at line 446 of file intrusive-list.h, definition at line 531 of file intrusive-list-inlines.h.
References micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::empty, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::get_pointer and micro_os_plus::utils::doubly_list< T, L >::links_.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator=.
unlink_tail()
| nodiscard noexcept |
Unlink the last element from the list.
- Parameters
None.
- Returns
Pointer to the last element in the list, or nullptr if the list is empty.
Removes and unlinks the last element from the intrusive list. If the list is empty, returns nullptr immediately without modifying the list. The method unlinks the node at the tail of the list and returns a pointer to the parent object containing the unlinked node.
Declaration at line 435 of file intrusive-list.h, definition at line 560 of file intrusive-list-inlines.h.
References micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::empty, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::get_pointer and micro_os_plus::utils::doubly_list< T, L >::links_.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator=.
Protected Member Functions
get_pointer()
| inline nodiscard noexcept protected |
Get the address of the object from the intrusive node pointer.
- Parameters
-
node Pointer to the intrusive node.
- Returns
A pointer to the parent object containing the node.
Computes and returns a pointer to the parent object that contains the intrusive node referenced by the given node pointer. This is achieved by calculating the offset of the intrusive node member within the parent object type and subtracting it from the node's address. This allows retrieval of the full object from just the node pointer, enabling intrusive list traversal and manipulation.
Declaration at line 491 of file intrusive-list.h, definition at line 503 of file intrusive-list-inlines.h.
Referenced by micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator=, micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::unlink_head and micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::unlink_tail.
Protected Member Attributes
links_
| protected |
The list top node used to point to head and tail nodes.
This member stores the internal links node for the list. The next pointer of this node points to the head of the list, and the previous pointer points to the tail. For an empty list, both pointers refer to the node itself, simplifying list management and boundary checks.
Definition at line 499 of file doubly-list.h.
Referenced by micro_os_plus::utils::doubly_list< N, doubly_list_links >::empty, micro_os_plus::utils::doubly_list< N, doubly_list_links >::end and micro_os_plus::utils::doubly_list< N, doubly_list_links >::initialised.
The documentation for this class was generated from the following files:
Generated via doxygen2docusaurus 2.2.2 by Doxygen 1.17.0.