List of intrusive nodes. More...

#include <cmsis-plus/utils/lists.h>

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

Public Types
using	difference_type = ptrdiff_t

using	iterator = intrusive_list_iterator< T, N, MP, U >

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

using	pointer = U *

using	reference = U &

using	value_type = U

Public Member Functions
Constructors & Destructor
	intrusive_list ()
	Construct an intrusive list.

	intrusive_list (bool clr)
	Construct an intrusive list with controlled inits.

	~intrusive_list ()
	Destruct the list.

Public Member Functions
void	link (reference node)
	Add a node to the tail of the list.

iterator	begin ()
	Iterator begin.

iterator	end () const
	Iterator begin.

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

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

Public Member Functions
bool	uninitialized (void) const
	Check if the list is uninitialised.

void	clear (void)
	Clear the list.

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

volatile static_double_list_links *	head (void) const
	Get the list head.

volatile static_double_list_links *	tail (void) const
	Get the list tail.

Protected Member Functions
pointer	get_pointer (iterator_pointer node) const

Private Member Functions
void	insert_after (static_double_list_links &node, static_double_list_links *after)
	Insert a new node after existing node.

Protected Attributes
Private Member Variables
static_double_list_links	head_
	A list node used to point to head and tail.

Detailed Description

template<typename T, typename N, N T::* MP, typename U = T>
class os::utils::intrusive_list< T, N, MP, U >

Template Parameters

T	Type of object that includes the intrusive node.
N	Type of intrusive node. Must have the public members prev & next.
MP	Name of the intrusive node member in object T.
U	Type stored in the list, derived from T.

Examples

using threads_list = utils::intrusive_list<

thread, utils::double_list_links, &thread::child_links_>;

os::utils::double_list_links

The core of a double linked list, pointers to next, previous.

Definition lists.h:153

os::utils::intrusive_list

List of intrusive nodes.

Definition lists.h:690

thread

Standard thread.

Definition thread_internal.h:40

Definition at line 689 of file lists.h.

Member Typedef Documentation

◆ difference_type

template<typename T , typename N , N T::* MP, typename U = T>

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

Definition at line 695 of file lists.h.

◆ iterator

template<typename T , typename N , N T::* MP, typename U = T>

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

Definition at line 697 of file lists.h.

◆ iterator_pointer

template<typename T , typename N , N T::* MP, typename U = T>

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

Definition at line 702 of file lists.h.

◆ pointer

template<typename T , typename N , N T::* MP, typename U = T>

using os::utils::intrusive_list< T, N, MP, U >::pointer = U*

Definition at line 693 of file lists.h.

◆ reference

template<typename T , typename N , N T::* MP, typename U = T>

using os::utils::intrusive_list< T, N, MP, U >::reference = U&

Definition at line 694 of file lists.h.

◆ value_type

template<typename T , typename N , N T::* MP, typename U = T>

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

Definition at line 692 of file lists.h.

Constructor & Destructor Documentation

◆ intrusive_list() [1/2]

template<typename T , typename N , N T::* MP, typename U >

os::utils::intrusive_list< T, N, MP, U >::intrusive_list

inline

Definition at line 1135 of file lists.h.

1136 {

1137 }

◆ intrusive_list() [2/2]

template<typename T , typename N , N T::* MP, typename U >

os::utils::intrusive_list< T, N, MP, U >::intrusive_list ( bool clr )

inline

Parameters

clr	If true, the list is cleared.

Definition at line 1140 of file lists.h.

    {
      if (clr)
        {
          clear ();
        }
    }

◆ ~intrusive_list()

template<typename T , typename N , N T::* MP, typename U >

os::utils::intrusive_list< T, N, MP, U >::~intrusive_list

inline

Definition at line 1149 of file lists.h.

1150 {

1151 }

Member Function Documentation

◆ begin()

template<typename T , typename N , N T::* MP, typename U >

intrusive_list< T, N, MP, U >::iterator os::utils::intrusive_list< T, N, MP, U >::begin

inline

Returns: An iterator positioned at the first element.

Note: It is not const because it may initialise on first use.

Definition at line 1185 of file lists.h.

    {
      if (uninitialized ())
        {
          // If this is the first time, initialise the list to empty.
          clear ();
        }
      return iterator{ static_cast<iterator_pointer> (head_.next ()) };
    }

◆ clear()

void os::utils::static_double_list::clear ( void )

inherited

Parameters: None.

Returns: Nothing.

Initialise the mandatory node with links to itself.

Definition at line 108 of file lists.cpp.

    {
#pragma GCC diagnostic push
#if defined(__clang__)
#elif defined(__GNUC__)
#pragma GCC diagnostic ignored "-Wuseless-cast"
#endif
      head_.next (const_cast<static_double_list_links*> (&head_));
      head_.prev (const_cast<static_double_list_links*> (&head_));
#pragma GCC diagnostic pop
    }

References os::utils::static_double_list::head_, os::utils::static_double_list_links::next(), and os::utils::static_double_list_links::prev().

Referenced by os::utils::double_list::double_list(), os::rtos::internal::ready_threads_list::link(), and os::rtos::internal::terminated_threads_list::link().

◆ empty()

bool os::utils::static_double_list::empty ( void ) const

inlineinherited

Parameters: None.

Return values

true	The list has no nodes.
false	The list has at least one node.

Definition at line 1001 of file lists.h.

    {
      // If it points to itself, it is empty.
      return (head_.next () == &head_) || (head_.next () == nullptr);
    }

References os::utils::static_double_list::head_, and os::utils::static_double_list_links::next().

Referenced by os::utils::double_list::~double_list(), os::rtos::internal::clock_timestamps_list::check_timestamp(), os::rtos::internal::clock_timestamps_list::link(), os::rtos::internal::ready_threads_list::link(), os::rtos::internal::waiting_threads_list::link(), os::rtos::internal::waiting_threads_list::resume_one(), and os::rtos::internal::ready_threads_list::unlink_head().

◆ end()

template<typename T , typename N , N T::* MP, typename U >

intrusive_list< T, N, MP, U >::iterator os::utils::intrusive_list< T, N, MP, U >::end

inline

Returns: An iterator positioned after the last element.

Definition at line 1197 of file lists.h.

    {
      return iterator{ static_cast<iterator_pointer> (
          const_cast<static_double_list_links*> (&head_)) };
    }

◆ get_pointer()

template<typename T , typename N , N T::* MP, typename U >

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

inlineprotected

Definition at line 1207 of file lists.h.

    {
      // static_assert(std::is_convertible<U, T>::value == true, "U must be
      // implicitly convertible to T!");
 
      // Compute the distance between the member intrusive link
      // node and the class begin.
      const auto offset = reinterpret_cast<difference_type> (
          &(static_cast<T*> (nullptr)->*MP));
 
      // Compute the address of the object which includes the
      // intrusive node, by adjusting down the node address.
      return reinterpret_cast<pointer> (
          reinterpret_cast<difference_type> (node) - offset);
    }

◆ head()

volatile static_double_list_links * os::utils::static_double_list::head ( void ) const

inlineinherited

Parameters: None.

Returns: Pointer to head node.

Definition at line 1008 of file lists.h.

    {
      return static_cast<volatile static_double_list_links*> (head_.next ());
    }

References os::utils::static_double_list::head_, and os::utils::static_double_list_links::next().

◆ insert_after()

void os::utils::static_double_list::insert_after	(	static_double_list_links &	node,
		static_double_list_links *	after
	)

protectedinherited

Parameters

node	Reference to node to insert.
after	Reference to existing node.

Returns: Nothing.

Definition at line 121 of file lists.cpp.

    {
#if defined(OS_TRACE_UTILS_LISTS)
      trace::printf ("%s() n=%p after %p\n", __func__, &node, after);
#endif
 
      // Unlinked nodes must have both pointers null.
      // If not, most probably the node was already linked.
      // Or the memory is corrupted.
      assert (node.prev () == nullptr);
      assert (node.next () == nullptr);
 
      // The `after` node must be linked. Only the `next` pointer is
      // tested, since only it is used.
      assert (after->next () != nullptr);
 
      // Make the new node point to its neighbours.
      node.prev (after);
      node.next (after->next ());
 
      // Make the neighbours point to the node. The order is important.
      after->next ()->prev (&node);
      after->next (&node);
    }

References os::utils::static_double_list_links::next(), os::utils::static_double_list_links::prev(), and os::trace::printf().

Referenced by os::rtos::internal::thread_children_list::link(), os::rtos::internal::clock_timestamps_list::link(), os::rtos::internal::ready_threads_list::link(), os::rtos::internal::waiting_threads_list::link(), and os::rtos::internal::terminated_threads_list::link().

◆ link()

template<typename T , typename N , N T::* MP, typename U >

void os::utils::intrusive_list< T, N, MP, U >::link ( reference node )

Parameters

[in] node Reference to a list node.

Returns: Nothing.

Definition at line 1155 of file lists.h.

    {
      if (uninitialized ())
        {
          // If this is the first time, initialise the list to empty.
          clear ();
        }
 
      // Compute the distance between the member intrusive link
      // node and the class begin.
      const auto offset = reinterpret_cast<difference_type> (
          &(static_cast<T*> (nullptr)->*MP));
 
      // Add thread intrusive node at the end of the list.
      insert_after (*reinterpret_cast<static_double_list_links*> (
                        reinterpret_cast<difference_type> (&node) + offset),
                    const_cast<static_double_list_links*> (tail ()));
    }

◆ tail()

volatile static_double_list_links * os::utils::static_double_list::tail ( void ) const

inlineinherited

Parameters: None.

Returns: Pointer to tail node.

Definition at line 1014 of file lists.h.

    {
      return (head_.prev ());
    }

References os::utils::static_double_list::head_, and os::utils::static_double_list_links::prev().

Referenced by os::rtos::internal::thread_children_list::link(), os::rtos::internal::clock_timestamps_list::link(), os::rtos::internal::ready_threads_list::link(), os::rtos::internal::waiting_threads_list::link(), and os::rtos::internal::terminated_threads_list::link().

◆ uninitialized()

bool os::utils::static_double_list::uninitialized ( void ) const

inlineinherited

Parameters: None.

Return values

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

Definition at line 994 of file lists.h.

    {
      // If it points to nowhere, it is not yet initialised.
      return (head_.prev () == nullptr);
    }

References os::utils::static_double_list::head_, and os::utils::static_double_list_links::prev().

◆ unlink_head()

template<typename T , typename N , N T::* MP, typename U >

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

Returns: Pointer to the first element in the list.

Definition at line 1225 of file lists.h.

    {
      assert (!empty ());
 
      // The first element in the list.
      iterator_pointer link = static_cast<iterator_pointer> (head_.next ());
      link->unlink ();
 
      return get_pointer (link);
    }

References link().

◆ unlink_tail()

template<typename T , typename N , N T::* MP, typename U >

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

Returns: Pointer to the last element in the list.

Definition at line 1238 of file lists.h.

    {
      assert (!empty ());
 
      // The last element in the list.
      iterator_pointer link = static_cast<iterator_pointer> (head_.prev ());
      link->unlink ();
 
      return get_pointer (link);
    }

References link().

Member Data Documentation

◆ head_

static_double_list_links os::utils::static_double_list::head_

protectedinherited

To simplify processing, the list always has a node.

Definition at line 473 of file lists.h.

Referenced by os::rtos::internal::waiting_threads_list::begin(), os::rtos::internal::clock_timestamps_list::check_timestamp(), os::utils::static_double_list::clear(), os::utils::static_double_list::empty(), os::rtos::internal::waiting_threads_list::end(), os::utils::static_double_list::head(), os::rtos::internal::clock_timestamps_list::link(), os::rtos::internal::ready_threads_list::link(), os::rtos::internal::waiting_threads_list::link(), os::rtos::internal::terminated_threads_list::link(), os::utils::static_double_list::tail(), and os::utils::static_double_list::uninitialized().

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

lists.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ difference_type

◆ iterator

◆ iterator_pointer

◆ pointer

◆ reference

◆ value_type

Constructor & Destructor Documentation

◆ intrusive_list() [1/2]

◆ intrusive_list() [2/2]

◆ ~intrusive_list()

Member Function Documentation

◆ begin()

◆ clear()

◆ empty()

◆ end()

◆ get_pointer()

◆ head()

◆ insert_after()

◆ link()

◆ tail()

◆ uninitialized()

◆ unlink_head()

◆ unlink_tail()

Member Data Documentation

◆ head_