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 of reference to the iterator internal pointer.

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.

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 () const
	Get the address of the node storing the list links.

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

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

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 node.

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.

Examples

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

A pair of head/tail pointers, maintaining a list of intrusive nodes.

Intrusive nodes do not need separate allocations for the links, but store them in the linked objects, in the MP member. The main thing this class does is to compute the address of the object by subtracting the offset from the address of the member storing the pointers.

For statically allocated lists, set L=static_double_list_links.

Definition at line 817 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 865 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 of reference to the iterator internal pointer.

Definition at line 854 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 849 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 860 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 829 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 839 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 844 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 834 of file lists.h.

Constructor & Destructor Documentation

◆ 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

Construct an intrusive doubly linked list.

Definition at line 557 of file inlines.h.

◆ ~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.

Definition at line 562 of file 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.

Definition at line 634 of file inlines.h.

◆ clear()

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

inherited

Clear the list.

Parameters: None.

Returns: Nothing.

Initialise the mandatory node with links to itself.

Definition at line 593 of file 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.

Definition at line 588 of file 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.

Definition at line 644 of file 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 node.

Returns: A pointer with the address of the node.

Definition at line 660 of file 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.

Definition at line 602 of file 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), initialise the list to the empty state, with both pointers pointing to itself.

For non-statically initialised lists, this method is ineffective.

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

Definition at line 581 of file 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.

Definition at line 612 of file 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.

Definition at line 595 of file inlines.h.

◆ links_pointer()

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

inlineconstexprinherited

Get the address of the node storing the list links.

Returns: A pointer to the list head object.

Definition at line 648 of file lists.h.

◆ 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.

Definition at line 611 of file 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 can be).

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 uninitialized.

Definition at line 563 of file 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.

Returns: Pointer to the first element in the list.

Definition at line 678 of file 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.

Returns: Pointer to the last element in the list.

Definition at line 692 of file 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.

The node next pointer points to the list head, and the previous pointer points to the list tail.

To simplify processing, the list always has these pointers set, with an empty list node pointing to itself.

Definition at line 667 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()

◆ ~intrusive_list()

Member Function Documentation

◆ begin()

◆ clear()

◆ empty()

◆ end()

◆ get_pointer()

◆ head()

◆ initialize_once()

◆ link_head()

◆ link_tail()

◆ links_pointer()

◆ tail()

◆ uninitialized()

◆ unlink_head()

◆ unlink_tail()

Member Data Documentation

◆ links_