Double-linked List

Similar to the single-linked list in many respects, Zephyr includes a double-linked implementation. This provides the same algorithmic behavior for all the existing slist operations, but also allows for constant-time removal and insertion (at all points: before or after the head, tail or any internal node). To do this, the list stores two pointers per node, and thus has somewhat higher runtime code and memory space needs.

A sys_dlist_t struct may be instantiated by the user in any accessible memory. It must be initialized with sys_dlist_init() or SYS_DLIST_STATIC_INIT before use. The sys_dnode_t struct is expected to be provided by the user for any nodes added to the list (typically embedded within the struct to be tracked, as described above). It must be initialized in zeroed/bss memory or with sys_dnode_init() before use.

Primitive operations may retrieve the head/tail of a list and the next/prev pointers of a node with sys_dlist_peek_head(), sys_dlist_peek_tail(), sys_dlist_peek_next() and sys_dlist_peek_prev(). These can all return NULL where appropriate (i.e. for empty lists, or nodes at the endpoints of the list).

A dlist can be modified in constant time by removing a node with sys_dlist_remove(), by adding a node to the head or tail of a list with sys_dlist_prepend() and sys_dlist_append(), or by inserting a node before an existing node with sys_dlist_insert().

As for slist, each node in a dlist can be processed in a natural code block style using SYS_DLIST_FOR_EACH_NODE. This macro also exists in a “FROM_NODE” form which allows for iterating from a known starting point, a “SAFE” variant that allows for removing the node being inspected within the code block, a “CONTAINER” style that provides the pointer to a containing struct instead of the raw node, and a “CONTAINER_SAFE” variant that provides both properties.

Convenience utilities provided by dlist include sys_dlist_insert_at(), which inserts a node that linearly searches through a list to find the right insertion point, which is provided by the user as a C callback function pointer, and sys_dnode_is_linked(), which will affirmatively return whether or not a node is currently linked into a dlist or not (via an implementation that has zero overhead vs. the normal list processing).

Double-linked List Internals

Internally, the dlist implementation is minimal: the sys_dlist_t struct contains “head” and “tail” pointer fields, the sys_dnode_t contains “prev” and “next” pointers, and no other data is stored. But in practice the two structs are internally identical, and the list struct is inserted as a node into the list itself. This allows for a very clean symmetry of operations:

  • An empty list has backpointers to itself in the list struct, which can be trivially detected.

  • The head and tail of the list can be detected by comparing the prev/next pointers of a node vs. the list struct address.

  • An insertion or deletion never needs to check for the special case of inserting at the head or tail. There are never any NULL pointers within the list to be avoided. Exactly the same operations are run, without tests or branches, for all list modification primitives.

Effectively, a dlist of N nodes can be thought of as a “ring” of “N+1” nodes, where one node represents the list tracking struct.

dlist example

A dlist containing three elements. Note that the list struct appears as a fourth “element” in the list.

single-element dlist example

An dlist containing just one element.

dlist example

An empty dlist.

Doubly-linked List API Reference

group doubly-linked-list_apis

Doubly-linked list implementation.

Doubly-linked list implementation using inline macros/functions. This API is not thread safe, and thus if a list is used across threads, calls to functions must be protected with synchronization primitives.

The lists are expected to be initialized such that both the head and tail pointers point to the list itself. Initializing the lists in such a fashion simplifies the adding and removing of nodes to/from the list.

Defines

SYS_DLIST_FOR_EACH_NODE(__dl, __dn)

Provide the primitive to iterate on a list Note: the loop is unsafe and thus __dn should not be removed.

User MUST add the loop statement curly braces enclosing its own code: 

SYS_DLIST_FOR_EACH_NODE(l, n) {
    <user code>
}
This and other SYS_DLIST_*() macros are not thread safe.

Parameters:

  • __dl – A pointer on a sys_dlist_t to iterate on

  • __dn – A sys_dnode_t pointer to peek each node of the list

SYS_DLIST_ITERATE_FROM_NODE(__dl, __dn)

Provide the primitive to iterate on a list, from a node in the list Note: the loop is unsafe and thus __dn should not be removed.

User MUST add the loop statement curly braces enclosing its own code: 

SYS_DLIST_ITERATE_FROM_NODE(l, n) {
    <user code>
}
Like SYS_DLIST_FOR_EACH_NODE(), but __dn already contains a node in the list where to start searching for the next entry from. If NULL, it starts from the head.

This and other SYS_DLIST_*() macros are not thread safe.

Parameters:

  • __dl – A pointer on a sys_dlist_t to iterate on

  • __dn – A sys_dnode_t pointer to peek each node of the list; it contains the starting node, or NULL to start from the head

SYS_DLIST_FOR_EACH_NODE_SAFE(__dl, __dn, __dns)

Provide the primitive to safely iterate on a list Note: __dn can be removed, it will not break the loop.

User MUST add the loop statement curly braces enclosing its own code: 

SYS_DLIST_FOR_EACH_NODE_SAFE(l, n, s) {
    <user code>
}
This and other SYS_DLIST_*() macros are not thread safe.

Parameters:

  • __dl – A pointer on a sys_dlist_t to iterate on

  • __dn – A sys_dnode_t pointer to peek each node of the list

  • __dns – A sys_dnode_t pointer for the loop to run safely

SYS_DLIST_CONTAINER(__dn, __cn, __n)

Provide the primitive to resolve the container of a list node Note: it is safe to use with NULL pointer nodes.

Parameters:

  • __dn – A pointer on a sys_dnode_t to get its container

  • __cn – Container struct type pointer

  • __n – The field name of sys_dnode_t within the container struct

SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n)

Provide the primitive to peek container of the list head.

Parameters:

  • __dl – A pointer on a sys_dlist_t to peek

  • __cn – Container struct type pointer

  • __n – The field name of sys_dnode_t within the container struct

SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n)

Provide the primitive to peek the next container.

Parameters:

  • __dl – A pointer on a sys_dlist_t to peek

  • __cn – Container struct type pointer

  • __n – The field name of sys_dnode_t within the container struct

SYS_DLIST_FOR_EACH_CONTAINER(__dl, __cn, __n)

Provide the primitive to iterate on a list under a container Note: the loop is unsafe and thus __cn should not be detached.

User MUST add the loop statement curly braces enclosing its own code: 

SYS_DLIST_FOR_EACH_CONTAINER(l, c, n) {
    <user code>
}

Parameters:

  • __dl – A pointer on a sys_dlist_t to iterate on

  • __cn – A container struct type pointer to peek each entry of the list

  • __n – The field name of sys_dnode_t within the container struct

SYS_DLIST_FOR_EACH_CONTAINER_SAFE(__dl, __cn, __cns, __n)

Provide the primitive to safely iterate on a list under a container Note: __cn can be detached, it will not break the loop.

User MUST add the loop statement curly braces enclosing its own code: 

SYS_DLIST_FOR_EACH_CONTAINER_SAFE(l, c, cn, n) {
    <user code>
}

Parameters:

  • __dl – A pointer on a sys_dlist_t to iterate on

  • __cn – A container struct type pointer to peek each entry of the list

  • __cns – A container struct type pointer for the loop to run safely

  • __n – The field name of sys_dnode_t within the container struct

SYS_DLIST_STATIC_INIT(ptr_to_list)

Static initializer for a doubly-linked list.

Typedefs

typedef struct _dnode sys_dlist_t

Doubly-linked list structure.

typedef struct _dnode sys_dnode_t

Doubly-linked list node structure.

Functions

static inline void sys_dlist_init(sys_dlist_t *list)

initialize list to its empty state

Parameters:

  • list – the doubly-linked list

static inline void sys_dnode_init(sys_dnode_t *node)

initialize node to its state when not in a list

Parameters:

  • node – the node

static inline bool sys_dnode_is_linked(const sys_dnode_t *node)

check if a node is a member of any list

Parameters:

  • node – the node

Returns:

true if node is linked into a list, false if it is not

static inline bool sys_dlist_is_head(sys_dlist_t *list, sys_dnode_t *node)

check if a node is the list’s head

Parameters:

  • list – the doubly-linked list to operate on

  • node – the node to check

Returns:

true if node is the head, false otherwise

static inline bool sys_dlist_is_tail(sys_dlist_t *list, sys_dnode_t *node)

check if a node is the list’s tail

Parameters:

  • list – the doubly-linked list to operate on

  • node – the node to check

Returns:

true if node is the tail, false otherwise

static inline bool sys_dlist_is_empty(sys_dlist_t *list)

check if the list is empty

Parameters:

  • list – the doubly-linked list to operate on

Returns:

true if empty, false otherwise

static inline bool sys_dlist_has_multiple_nodes(sys_dlist_t *list)

check if more than one node present

This and other sys_dlist_*() functions are not thread safe.

Parameters:

  • list – the doubly-linked list to operate on

Returns:

true if multiple nodes, false otherwise

static inline sys_dnode_t *sys_dlist_peek_head(sys_dlist_t *list)

get a reference to the head item in the list

Parameters:

  • list – the doubly-linked list to operate on

Returns:

a pointer to the head element, NULL if list is empty

static inline sys_dnode_t *sys_dlist_peek_head_not_empty(sys_dlist_t *list)

get a reference to the head item in the list

The list must be known to be non-empty.

Parameters:

  • list – the doubly-linked list to operate on

Returns:

a pointer to the head element

static inline sys_dnode_t *sys_dlist_peek_next_no_check(sys_dlist_t *list, sys_dnode_t *node)

get a reference to the next item in the list, node is not NULL

Faster than sys_dlist_peek_next() if node is known not to be NULL.

Parameters:

  • list – the doubly-linked list to operate on

  • node – the node from which to get the next element in the list

Returns:

a pointer to the next element from a node, NULL if node is the tail

static inline sys_dnode_t *sys_dlist_peek_next(sys_dlist_t *list, sys_dnode_t *node)

get a reference to the next item in the list

Parameters:

  • list – the doubly-linked list to operate on

  • node – the node from which to get the next element in the list

Returns:

a pointer to the next element from a node, NULL if node is the tail or NULL (when node comes from reading the head of an empty list).

static inline sys_dnode_t *sys_dlist_peek_prev_no_check(sys_dlist_t *list, sys_dnode_t *node)

get a reference to the previous item in the list, node is not NULL

Faster than sys_dlist_peek_prev() if node is known not to be NULL.

Parameters:

  • list – the doubly-linked list to operate on

  • node – the node from which to get the previous element in the list

Returns:

a pointer to the previous element from a node, NULL if node is the tail

static inline sys_dnode_t *sys_dlist_peek_prev(sys_dlist_t *list, sys_dnode_t *node)

get a reference to the previous item in the list

Parameters:

  • list – the doubly-linked list to operate on

  • node – the node from which to get the previous element in the list

Returns:

a pointer to the previous element from a node, NULL if node is the tail or NULL (when node comes from reading the head of an empty list).

static inline sys_dnode_t *sys_dlist_peek_tail(sys_dlist_t *list)

get a reference to the tail item in the list

Parameters:

  • list – the doubly-linked list to operate on

Returns:

a pointer to the tail element, NULL if list is empty

static inline void sys_dlist_append(sys_dlist_t *list, sys_dnode_t *node)

add node to tail of list

This and other sys_dlist_*() functions are not thread safe.

Parameters:

  • list – the doubly-linked list to operate on

  • node – the element to append

static inline void sys_dlist_prepend(sys_dlist_t *list, sys_dnode_t *node)

add node to head of list

This and other sys_dlist_*() functions are not thread safe.

Parameters:

  • list – the doubly-linked list to operate on

  • node – the element to append

static inline void sys_dlist_insert(sys_dnode_t *successor, sys_dnode_t *node)

Insert a node into a list.

Insert a node before a specified node in a dlist.

Parameters:

  • successor – the position before which “node” will be inserted

  • node – the element to insert

static inline void sys_dlist_insert_at(sys_dlist_t *list, sys_dnode_t *node, int (*cond)(sys_dnode_t *node, void *data), void *data)

insert node at position

Insert a node in a location depending on a external condition. The cond() function checks if the node is to be inserted before the current node against which it is checked. This and other sys_dlist_*() functions are not thread safe.

Parameters:

  • list – the doubly-linked list to operate on

  • node – the element to insert

  • cond – a function that determines if the current node is the correct insert point

  • data – parameter to cond()

static inline void sys_dlist_remove(sys_dnode_t *node)

remove a specific node from a list

The list is implicit from the node. The node must be part of a list. This and other sys_dlist_*() functions are not thread safe.

Parameters:

  • node – the node to remove

static inline sys_dnode_t *sys_dlist_get(sys_dlist_t *list)

get the first node in a list

This and other sys_dlist_*() functions are not thread safe.

Parameters:

  • list – the doubly-linked list to operate on

Returns:

the first node in the list, NULL if list is empty

static inline size_t sys_dlist_len(sys_dlist_t *list)

Compute the size of the given list in O(n) time.

Parameters:

  • list – A pointer on the list

Returns:

an integer equal to the size of the list, or 0 if empty