How to use the µOS++ Intrusive Lists

Rationale

The C++ standard libraries provide extensive support for various lists; however, the majority necessitate dynamic memory allocations for list nodes (the objects used to store pairs of links), which can pose challenges on embedded systems. Consequently, it is advisable to avoid such allocations where possible, particularly at the system level.

Regular lists

A standard doubly linked list comprises a pair of pointers (represented by the red object) and a set of additional pointers that connect to each other as well as to the payload (depicted by the yellow objects).

Whenever a payload is added to the list, the corresponding object must be acquired from an allocator. Similarly, whenever an object is removed from the list, it must be returned to the free storage.

Intrusive lists

One potential method to circumvent dynamically allocated list nodes is to embed the list links within the payload objects. This approach is utilised by intrusive lists, which are doubly linked lists that maintain two pointers within each linked object. Objects that belong to multiple lists possess multiple pairs of pointers, one for each list.

At the implementation level, this can be accomplished by employing composition, whereby the objects containing the pairs of links are members of the payload objects.

info

The iterators must maintain a record of the offset from the object's beginning to the location of the pairs of links.

For objects that are known to be linked into a single list, a simpler variant exists, wherein the payload object is derived from the object storing the pairs of links.

info

This reduces computations in the iterators, as the offset to the pair of links is zero.

Statically initialised lists

To support objects that auto-register themselves with static registrar objects — lists created through the static constructors mechanism in the global scope — it is essential to ensure that the registrar is initialised before the clients need to register. Given that, according to the C++ standard, the order in which static constructors are invoked is indeterminate, the only solution is to initialise the registrar before the static constructors.

info

This initialisation is carried out by the startup code when the BSS section is set to zero.

These statically allocated lists must not alter the content of any of their members within the constructors, as this may occur after clients have already registered.

Before inserting anything into these lists, the user must call initialize_once(), which will check the list and, if it is still in the initial zero state, will initialise it to the empty state (with both pointers pointing to itself).

C++ API

Namespaces

The definitions are organised within a namespace under micro_os_plus:

• micro_os_plus::utils

Intrusive doubly linked lists class

The intrusive lists can be defined by instantiating a class template:

 /*
  * @tparam T Type of object that includes the intrusive node.
  * @tparam N Type of intrusive node with the next & previous links.
  * @tparam MP Name of the intrusive node member in object T.
  * @tparam L Type of the links node.
  * @tparam U Type stored in the list, derived from T.
  */
template <class T, class N, N T::*MP, class L = double_list_links,
          class U = T>
class intrusive_list;

See the reference Intrusive doubly linked lists page.

Doubly linked lists class

For simpler use cases, such as traditional lists or low intrusive lists, there is a simpler template:

 /*
  * @tparam T Type of the elements linked into the list,
  * derived from class `double_list_links_base`.
  * @tparam L Type of the links node (one of
  * `double_list_links` or `static_double_list_links`).
  */
template <class T, class L = double_list_links>
class double_list;

See the reference Doubly linked lists page.

Methods

The available C++ methods for the list are as follows:

pointer head (void);
pointer tail (void);

void link_tail (reference node);
void link_head (reference node);

pointer unlink_tail (void);
pointer unlink_head (void);

bool empty (void);

void initialize_once (void);

Forward iterators are defined as usual:

iterator begin ();
iterator end ();

Individual nodes (derived from double_list_links_base) offer the following methods:

void link_next (double_list_links_base* node);
void link_previous (double_list_links_base* node);

void unlink (void);
void clear (void);

bool linked (void);

// Accessors.
double_list_links_base* next (void);
double_list_links_base* previous (void);

C API

There are no C equivalents for the C++ definitions.

Examples

An example demonstrating the usage of intrusive lists can be found in tests/src/sample-test.cpp.

Presented below is a brief excerpt.

Points to consider:

• The method by which links are incorporated as a member of the object.
• The necessity for this member to be declared public.
• The elegant approach to specifying the type of the list through a C++ template.

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

namespace os = micro_os_plus;

class child
{
public:
  child (const char* name);
  // ...
protected:
  const char* name_;

public:
  // Intrusive node used to link this child to the registry list.
  // Must be public.
  os::utils::double_list_links registry_links_;
};

using static_children_list = os::utils::intrusive_list<
        child, // type of nodes in the list
        decltype (child::registry_links_), // type of the `registry_links_` member
        &child::registry_links_, // name of member
        static_double_list_links>; // type of the head links node

// The list head is statically allocated.
static_children_list kids_registry;

Known problems

• For statically allocated lists, the destructor cannot revert the object to the initial zero state. In case the objects are reused, it is essential to clear the memory (e.g., via memset()) before invoking the constructor via placement new.