A class template for a list of nodes which store the links inside themselves as intrusive nodes. More...

#include <micro-os-plus/utils/lists.h>

Inheritance diagram for micro_os_plus::utils::intrusive_list< T, N, MP, L, U >:

Public Types
using	difference_type = ptrdiff_t
	Type of pointer difference.

using	is_statically_allocated
	Type indicating if the links node is statically allocated.

using	iterator = intrusive_list_iterator<T, N, MP, U>
	Type of iterator over the values.

using	iterator_pointer = N*
	Type of reference to the iterator internal pointer.

using	links_type = L
	Type of the list links node object where the pointers to the list head and tail are stored.

using	pointer = value_type*
	Type of pointer to object pointed to by the iterator.

using	reference = value_type&
	Type of reference to object pointed to by the iterator.

using	value_type = U
	Type of value pointed to by the iterator.

Public Member Functions
constexpr	intrusive_list ()
	Construct an intrusive doubly linked list.

	intrusive_list (const intrusive_list &)=delete
	Deleted copy constructor.

	intrusive_list (intrusive_list &&)=delete
	Deleted move constructor.

constexpr	~intrusive_list ()
	Destruct the list.

iterator	begin () const
	Iterator begin.

void	clear (void)
	Clear the list.

constexpr bool	empty (void) const
	Check if the list is empty.

iterator	end () const
	Iterator begin.

constexpr pointer	head (void) const
	Get the list head.

void	initialize_once (void)
	Initialize the list only at first run.

void	link_head (reference node)
	Add a node to the head of the list.

void	link_tail (reference node)
	Add a node to the tail of the list.

constexpr const links_type *	links_pointer (void) const
	Get the address of the node storing the list links.

intrusive_list &	operator= (const intrusive_list &)=delete
	Deleted copy assignment operator.

intrusive_list &	operator= (intrusive_list &&)=delete
	Deleted move assignment operator.

constexpr pointer	tail (void) const
	Get the list tail.

bool	uninitialized (void) const
	Check if the list is uninitialised (only statically allocated lists can be uninitialised).

pointer	unlink_head (void)
	Unlink the first element from the list.

pointer	unlink_tail (void)
	Unlink the last element from the list.

Protected Member Functions
pointer	get_pointer (iterator_pointer node) const
	Get the address of the object from the intrusive node pointer.

Protected Attributes
links_type	links_
	The list top node used to point to head and tail nodes.

Detailed Description

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>
class micro_os_plus::utils::intrusive_list< T, N, MP, L, U >

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 `double_list_links` or `static_double_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

namespace os = micro_os_plus;
using threads_list = os::utils::intrusive_list<
  thread, os::utils::double_list_links, &thread::child_links_>;

For statically allocated lists, set L=static_double_list_links.

Definition at line 1135 of file lists.h.

Member Typedef Documentation

◆ difference_type

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

using micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::difference_type = ptrdiff_t

Type of pointer difference.

Definition at line 1183 of file lists.h.

◆ is_statically_allocated

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

using micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::is_statically_allocated

Initial value:

typename links_type::is_statically_allocated

Type indicating if the links node is statically allocated.

Definition at line 1172 of file lists.h.

◆ iterator

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

using micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::iterator = intrusive_list_iterator<T, N, MP, U>

Type of iterator over the values.

Definition at line 1167 of file lists.h.

◆ iterator_pointer

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

using micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::iterator_pointer = N*

Type of reference to the iterator internal pointer.

Definition at line 1178 of file lists.h.

◆ links_type

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

using micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::links_type = L

Type of the list links node object where the pointers to the list head and tail are stored.

Definition at line 1147 of file lists.h.

◆ pointer

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

using micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::pointer = value_type*

Type of pointer to object pointed to by the iterator.

Definition at line 1157 of file lists.h.

◆ reference

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

using micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::reference = value_type&

Type of reference to object pointed to by the iterator.

Definition at line 1162 of file lists.h.

◆ value_type

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

using micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::value_type = U

Type of value pointed to by the iterator.

Definition at line 1152 of file lists.h.

Constructor & Destructor Documentation

◆ intrusive_list() [1/3]

template<class T, class N, N T::* MP, class L, class U>

micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::intrusive_list ( )

constexpr

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.

Definition at line 961 of file lists-inlines.h.

◆ intrusive_list() [2/3]

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::intrusive_list ( const intrusive_list< T, N, MP, L, U > & )

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.

◆ intrusive_list() [3/3]

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::intrusive_list ( intrusive_list< T, N, MP, L, U > && )

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.

◆ ~intrusive_list()

template<class T, class N, N T::* MP, class L, class U>

micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::~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.

Definition at line 973 of file lists-inlines.h.

Member Function Documentation

◆ begin()

template<class T, class N, N T::* MP, class L, class U>

intrusive_list< T, N, MP, L, U >::iterator micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::begin ( ) const

inline

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().

Definition at line 1076 of file lists-inlines.h.

◆ clear()

void micro_os_plus::utils::double_list< N, double_list_links >::clear ( void )

inherited

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.

Definition at line 816 of file lists-inlines.h.

◆ empty()

template<class T, class N, N T::* MP, class L, class U>

bool micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::empty ( void ) const

constexpr

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.

Definition at line 1004 of file lists-inlines.h.

◆ end()

template<class T, class N, N T::* MP, class L, class U>

intrusive_list< T, N, MP, L, U >::iterator micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::end ( ) const

inline

Iterator begin.

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.

Definition at line 1094 of file lists-inlines.h.

◆ get_pointer()

template<class T, class N, N T::* MP, class L, class U>

intrusive_list< T, N, MP, L, U >::pointer micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::get_pointer ( iterator_pointer node ) const

inlineprotected

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.

Definition at line 1119 of file lists-inlines.h.

◆ head()

double_list< N, double_list_links >::pointer micro_os_plus::utils::double_list< N, double_list_links >::head ( void ) const

constexprinherited

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.

Definition at line 826 of file lists-inlines.h.

◆ initialize_once()

template<class T, class N, N T::* MP, class L, class U>

void micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::initialize_once ( void )

Initialize the list only at first run.

Parameters: None.

Returns: Nothing.

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.

Note: Must be manually called for statically allocated lists before inserting elements or performing any other operations.

Definition at line 990 of file lists-inlines.h.

◆ link_head()

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

void micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::link_head ( reference node )

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.

Definition at line 1046 of file lists-inlines.h.

◆ link_tail()

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

void micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::link_tail ( reference node )

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.

Definition at line 1020 of file lists-inlines.h.

◆ links_pointer()

const links_type * micro_os_plus::utils::double_list< N, double_list_links >::links_pointer ( void ) const

inlineconstexprinherited

Get the address of the node storing the list links.

Parameters: None.

Returns: A pointer to the list head object.

Definition at line 886 of file lists.h.

◆ operator=() [1/2]

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

intrusive_list & micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator= ( const intrusive_list< T, N, MP, L, U > & )

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.

◆ operator=() [2/2]

template<class T, class N, N T::* MP, class L = double_list_links, class U = T>

intrusive_list & micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::operator= ( intrusive_list< T, N, MP, L, U > && )

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.

◆ tail()

double_list< N, double_list_links >::pointer micro_os_plus::utils::double_list< N, double_list_links >::tail ( void ) const

constexprinherited

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.

Definition at line 836 of file lists-inlines.h.

◆ uninitialized()

bool micro_os_plus::utils::double_list< N, double_list_links >::uninitialized ( void ) const

inherited

Check if the list is uninitialised (only statically allocated lists can be uninitialised).

Parameters: None.

Return values

true	The list was not initialised.
false	The list was initialised.

An uninitialized node is a node with any of the pointers set to nullptr. Only statically allocated nodes in the initial state are considered uninitialized. For dynamically allocated lists, this method always returns false since their nodes are explicitly initialized during construction.

Definition at line 783 of file lists-inlines.h.

◆ unlink_head()

template<class T, class N, N T::* MP, class L, class U>

intrusive_list< T, N, MP, L, U >::pointer micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::unlink_head ( void )

Unlink the first element from the list.

Parameters: None.

Returns: Pointer to the first element in the list.

Removes and unlinks the first element from the intrusive list. If the list is empty, this operation is a no-op and returns a pointer to the internal links node. The method unlinks the node at the head of the list and returns a pointer to the parent object containing the unlinked node.

Definition at line 1145 of file lists-inlines.h.

◆ unlink_tail()

template<class T, class N, N T::* MP, class L, class U>

intrusive_list< T, N, MP, L, U >::pointer micro_os_plus::utils::intrusive_list< T, N, MP, L, U >::unlink_tail ( void )

Unlink the last element from the list.

Parameters: None.

Returns: Pointer to the last element in the list.

Removes and unlinks the last element from the intrusive list. If the list is empty, this operation is a no-op and returns a pointer to the internal links node. The method unlinks the node at the tail of the list and returns a pointer to the parent object containing the unlinked node.

Definition at line 1167 of file lists-inlines.h.

Member Data Documentation

◆ links_

links_type micro_os_plus::utils::double_list< N, double_list_links >::links_

protectedinherited

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 904 of file lists.h.

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ difference_type

◆ is_statically_allocated

◆ iterator

◆ iterator_pointer

◆ links_type

◆ pointer

◆ reference

◆ value_type

Constructor & Destructor Documentation

◆ intrusive_list() [1/3]

◆ intrusive_list() [2/3]

◆ intrusive_list() [3/3]

◆ ~intrusive_list()

Member Function Documentation

◆ begin()

◆ clear()

◆ empty()

◆ end()

◆ get_pointer()

◆ head()

◆ initialize_once()

◆ link_head()

◆ link_tail()

◆ links_pointer()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ tail()

◆ uninitialized()

◆ unlink_head()

◆ unlink_tail()

Member Data Documentation

◆ links_