The intrusive_list Class Template Reference

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

Fully Qualified Name

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

Included Headers

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

Base class

class	micro_os_plus::utils::double_list< T, L >
	A class template for a doubly linked list of nodes. More...

Member Typedefs

using	difference_type = ptrdiff_t
	Type of pointer difference. More...
using	is_statically_allocated = typename links_type::is_statically_allocated
	Type of reference to the iterator internal pointer. More...
using	iterator = intrusive_list_iterator< T, N, MP, U >
	Type of iterator over the values. More...
using	iterator_pointer = N *
	Type of reference to the iterator internal pointer. More...
using	links_type = L
	Type of the list links node object where the pointers to the list head and tail are stored. More...
using	pointer = value_type *
	Type of pointer to object pointed to by the iterator. More...
using	reference = value_type &
	Type of reference to object pointed to by the iterator. More...
using	value_type = U
	Type of value pointed to by the iterator. More...

Member Functions

constexpr	intrusive_list ()
	Construct an intrusive doubly linked list. More...
constexpr	~intrusive_list ()
	Destruct the list. More...
iterator	begin () const
	Iterator begin. More...
void	clear (void)
	Clear the list. More...
bool	empty (void) const
	Check if the list is empty. More...
iterator	end () const
	Iterator begin. More...
pointer	head (void) const
	Get the list head. More...
void	initialize_once (void)
	Initialize the list only at first run. More...
void	link_head (reference node)
	Add a node to the head of the list. More...
void	link_tail (reference node)
	Add a node to the tail of the list. More...
const links_type *	links_pointer () const
	Get the address of the node storing the list links. More...
pointer	tail (void) const
	Get the list tail. More...
bool	uninitialized (void) const
	Check if the list is uninitialised (only statically allocated lists can be uninitialised). More...
pointer	unlink_head (void)
	Unlink the first element from the list. More...
pointer	unlink_tail (void)
	Unlink the last element from the list. More...

Protected Member Functions

pointer	get_pointer (iterator_pointer node) const
	Get the address of the node. More...

Protected Member Attributes

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

Description

The class template declaration is:

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 >;

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

Member Typedefs

difference_type

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

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

Type of pointer difference.

Definition at line 886 of file lists.h.

is_statically_allocated

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

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

Type of reference to the iterator internal pointer.

Definition at line 875 of file lists.h.

iterator

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

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

iterator_pointer

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

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

links_type

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

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

pointer

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

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

reference

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

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

value_type

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

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

Constructors

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

Destructor

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

Member Functions

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

clear()

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

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

Clear the list.

Parameters

None.

Returns

Nothing.

Initialise the mandatory node with links to itself.

Definition at line 614 of file lists.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 935 of file lists.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 983 of file lists.h.

head()

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

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

constexpr

Get the list head.

Parameters

None.

Returns

Pointer to the head node.

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

info

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

Definition at line 925 of file lists.h.

link_head()

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

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

link_tail()

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

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

links_pointer()

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

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

inlineconstexpr

Get the address of the node storing the list links.

Returns

A pointer to the list head object.

Definition at line 669 of file lists.h.

tail()

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

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

constexpr

Get the list tail.

Parameters

None.

Returns

Pointer to the tail node.

Definition at line 632 of file lists.h.

uninitialized()

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

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

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

Definition at line 584 of file lists.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 967 of file lists.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 960 of file lists.h.

Protected Member Functions

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

Protected Member Attributes

links_

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

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

protected

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

---

Generated via docusaurus-plugin-doxygen by Doxygen 1.13.2