Zephyr API Documentation 3.7.99
A Scalable Open Source RTOS
Loading...
Searching...
No Matches
Doubly-linked list

Doubly-linked list implementation More...

Macros

#define 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.
 
#define 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.
 
#define 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.
 
#define 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.
 
#define SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n)
 Provide the primitive to peek container of the list head.
 
#define SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n)
 Provide the primitive to peek the next container.
 
#define 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.
 
#define 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.
 
#define 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 void sys_dlist_init (sys_dlist_t *list)
 initialize list to its empty state
 
static void sys_dnode_init (sys_dnode_t *node)
 initialize node to its state when not in a list
 
static bool sys_dnode_is_linked (const sys_dnode_t *node)
 check if a node is a member of any list
 
static bool sys_dlist_is_head (sys_dlist_t *list, sys_dnode_t *node)
 check if a node is the list's head
 
static bool sys_dlist_is_tail (sys_dlist_t *list, sys_dnode_t *node)
 check if a node is the list's tail
 
static bool sys_dlist_is_empty (sys_dlist_t *list)
 check if the list is empty
 
static bool sys_dlist_has_multiple_nodes (sys_dlist_t *list)
 check if more than one node present
 
static sys_dnode_tsys_dlist_peek_head (sys_dlist_t *list)
 get a reference to the head item in the list
 
static sys_dnode_tsys_dlist_peek_head_not_empty (sys_dlist_t *list)
 get a reference to the head item in the list
 
static sys_dnode_tsys_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
 
static sys_dnode_tsys_dlist_peek_next (sys_dlist_t *list, sys_dnode_t *node)
 get a reference to the next item in the list
 
static sys_dnode_tsys_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
 
static sys_dnode_tsys_dlist_peek_prev (sys_dlist_t *list, sys_dnode_t *node)
 get a reference to the previous item in the list
 
static sys_dnode_tsys_dlist_peek_tail (sys_dlist_t *list)
 get a reference to the tail item in the list
 
static void sys_dlist_append (sys_dlist_t *list, sys_dnode_t *node)
 add node to tail of list
 
static void sys_dlist_prepend (sys_dlist_t *list, sys_dnode_t *node)
 add node to head of list
 
static void sys_dlist_insert (sys_dnode_t *successor, sys_dnode_t *node)
 Insert a node into a list.
 
static 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
 
static void sys_dlist_remove (sys_dnode_t *node)
 remove a specific node from a list
 
static sys_dnode_tsys_dlist_get (sys_dlist_t *list)
 get the first node in a list
 
static size_t sys_dlist_len (sys_dlist_t *list)
 Compute the size of the given list in O(n) time.
 

Detailed Description

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.

Macro Definition Documentation

◆ SYS_DLIST_CONTAINER

#define SYS_DLIST_CONTAINER ( __dn,
__cn,
__n )

#include <zephyr/sys/dlist.h>

Value:
(((__dn) != NULL) ? CONTAINER_OF(__dn, __typeof__(*(__cn)), __n) : NULL)
#define CONTAINER_OF(ptr, type, field)
Get a pointer to a structure containing the element.
Definition util.h:275

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

Parameters
__dnA pointer on a sys_dnode_t to get its container
__cnContainer struct type pointer
__nThe field name of sys_dnode_t within the container struct

◆ SYS_DLIST_FOR_EACH_CONTAINER

#define SYS_DLIST_FOR_EACH_CONTAINER ( __dl,
__cn,
__n )

#include <zephyr/sys/dlist.h>

Value:
for ((__cn) = SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n); \
(__cn) != NULL; \
(__cn) = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n))
#define SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n)
Provide the primitive to peek container of the list head.
Definition dlist.h:141
#define SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n)
Provide the primitive to peek the next container.
Definition dlist.h:151

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
__dlA pointer on a sys_dlist_t to iterate on
__cnA container struct type pointer to peek each entry of the list
__nThe field name of sys_dnode_t within the container struct

◆ SYS_DLIST_FOR_EACH_CONTAINER_SAFE

#define SYS_DLIST_FOR_EACH_CONTAINER_SAFE ( __dl,
__cn,
__cns,
__n )

#include <zephyr/sys/dlist.h>

Value:
for ((__cn) = SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n), \
(__cns) = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n); \
(__cn) != NULL; (__cn) = (__cns), \
(__cns) = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __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
__dlA pointer on a sys_dlist_t to iterate on
__cnA container struct type pointer to peek each entry of the list
__cnsA container struct type pointer for the loop to run safely
__nThe field name of sys_dnode_t within the container struct

◆ SYS_DLIST_FOR_EACH_NODE

#define SYS_DLIST_FOR_EACH_NODE ( __dl,
__dn )

#include <zephyr/sys/dlist.h>

Value:
for (__dn = sys_dlist_peek_head(__dl); __dn != NULL; \
__dn = sys_dlist_peek_next(__dl, __dn))
static sys_dnode_t * sys_dlist_peek_head(sys_dlist_t *list)
get a reference to the head item in the list
Definition dlist.h:302
static 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
Definition dlist.h:349

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
__dlA pointer on a sys_dlist_t to iterate on
__dnA sys_dnode_t pointer to peek each node of the list

◆ SYS_DLIST_FOR_EACH_NODE_SAFE

#define SYS_DLIST_FOR_EACH_NODE_SAFE ( __dl,
__dn,
__dns )

#include <zephyr/sys/dlist.h>

Value:
for ((__dn) = sys_dlist_peek_head(__dl), \
(__dns) = sys_dlist_peek_next((__dl), (__dn)); \
(__dn) != NULL; (__dn) = (__dns), \
(__dns) = sys_dlist_peek_next(__dl, __dn))

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
__dlA pointer on a sys_dlist_t to iterate on
__dnA sys_dnode_t pointer to peek each node of the list
__dnsA sys_dnode_t pointer for the loop to run safely

◆ SYS_DLIST_ITERATE_FROM_NODE

#define SYS_DLIST_ITERATE_FROM_NODE ( __dl,
__dn )

#include <zephyr/sys/dlist.h>

Value:
for (__dn = __dn ? sys_dlist_peek_next_no_check(__dl, __dn) \
__dn != NULL; \
__dn = sys_dlist_peek_next(__dl, __dn))
static 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
Definition dlist.h:333

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
__dlA pointer on a sys_dlist_t to iterate on
__dnA 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_PEEK_HEAD_CONTAINER

#define SYS_DLIST_PEEK_HEAD_CONTAINER ( __dl,
__cn,
__n )

#include <zephyr/sys/dlist.h>

Value:
#define 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 point...
Definition dlist.h:132

Provide the primitive to peek container of the list head.

Parameters
__dlA pointer on a sys_dlist_t to peek
__cnContainer struct type pointer
__nThe field name of sys_dnode_t within the container struct

◆ SYS_DLIST_PEEK_NEXT_CONTAINER

#define SYS_DLIST_PEEK_NEXT_CONTAINER ( __dl,
__cn,
__n )

#include <zephyr/sys/dlist.h>

Value:
(((__cn) != NULL) ? \
SYS_DLIST_CONTAINER(sys_dlist_peek_next((__dl), &((__cn)->__n)), \
__cn, __n) : NULL)

Provide the primitive to peek the next container.

Parameters
__dlA pointer on a sys_dlist_t to peek
__cnContainer struct type pointer
__nThe field name of sys_dnode_t within the container struct

◆ SYS_DLIST_STATIC_INIT

#define SYS_DLIST_STATIC_INIT ( ptr_to_list)

#include <zephyr/sys/dlist.h>

Value:
{ {(ptr_to_list)}, {(ptr_to_list)} }

Static initializer for a doubly-linked list.

Typedef Documentation

◆ sys_dlist_t

typedef struct _dnode sys_dlist_t

#include <zephyr/sys/dlist.h>

Doubly-linked list structure.

◆ sys_dnode_t

typedef struct _dnode sys_dnode_t

#include <zephyr/sys/dlist.h>

Doubly-linked list node structure.

Function Documentation

◆ sys_dlist_append()

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

#include <zephyr/sys/dlist.h>

add node to tail of list

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

Parameters
listthe doubly-linked list to operate on
nodethe element to append

◆ sys_dlist_get()

static sys_dnode_t * sys_dlist_get ( sys_dlist_t * list)
inlinestatic

#include <zephyr/sys/dlist.h>

get the first node in a list

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

Parameters
listthe doubly-linked list to operate on
Returns
the first node in the list, NULL if list is empty

◆ sys_dlist_has_multiple_nodes()

static bool sys_dlist_has_multiple_nodes ( sys_dlist_t * list)
inlinestatic

#include <zephyr/sys/dlist.h>

check if more than one node present

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

Parameters
listthe doubly-linked list to operate on
Returns
true if multiple nodes, false otherwise

◆ sys_dlist_init()

static void sys_dlist_init ( sys_dlist_t * list)
inlinestatic

#include <zephyr/sys/dlist.h>

initialize list to its empty state

Parameters
listthe doubly-linked list

◆ sys_dlist_insert()

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

#include <zephyr/sys/dlist.h>

Insert a node into a list.

Insert a node before a specified node in a dlist.

Parameters
successorthe position before which "node" will be inserted
nodethe element to insert

◆ sys_dlist_insert_at()

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

#include <zephyr/sys/dlist.h>

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
listthe doubly-linked list to operate on
nodethe element to insert
conda function that determines if the current node is the correct insert point
dataparameter to cond()

◆ sys_dlist_is_empty()

static bool sys_dlist_is_empty ( sys_dlist_t * list)
inlinestatic

#include <zephyr/sys/dlist.h>

check if the list is empty

Parameters
listthe doubly-linked list to operate on
Returns
true if empty, false otherwise

◆ sys_dlist_is_head()

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

#include <zephyr/sys/dlist.h>

check if a node is the list's head

Parameters
listthe doubly-linked list to operate on
nodethe node to check
Returns
true if node is the head, false otherwise

◆ sys_dlist_is_tail()

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

#include <zephyr/sys/dlist.h>

check if a node is the list's tail

Parameters
listthe doubly-linked list to operate on
nodethe node to check
Returns
true if node is the tail, false otherwise

◆ sys_dlist_len()

static size_t sys_dlist_len ( sys_dlist_t * list)
inlinestatic

#include <zephyr/sys/dlist.h>

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

Parameters
listA pointer on the list
Returns
an integer equal to the size of the list, or 0 if empty

◆ sys_dlist_peek_head()

static sys_dnode_t * sys_dlist_peek_head ( sys_dlist_t * list)
inlinestatic

#include <zephyr/sys/dlist.h>

get a reference to the head item in the list

Parameters
listthe doubly-linked list to operate on
Returns
a pointer to the head element, NULL if list is empty

◆ sys_dlist_peek_head_not_empty()

static sys_dnode_t * sys_dlist_peek_head_not_empty ( sys_dlist_t * list)
inlinestatic

#include <zephyr/sys/dlist.h>

get a reference to the head item in the list

The list must be known to be non-empty.

Parameters
listthe doubly-linked list to operate on
Returns
a pointer to the head element

◆ sys_dlist_peek_next()

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

#include <zephyr/sys/dlist.h>

get a reference to the next item in the list

Parameters
listthe doubly-linked list to operate on
nodethe 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).

◆ sys_dlist_peek_next_no_check()

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

#include <zephyr/sys/dlist.h>

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
listthe doubly-linked list to operate on
nodethe 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

◆ sys_dlist_peek_prev()

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

#include <zephyr/sys/dlist.h>

get a reference to the previous item in the list

Parameters
listthe doubly-linked list to operate on
nodethe 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).

◆ sys_dlist_peek_prev_no_check()

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

#include <zephyr/sys/dlist.h>

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
listthe doubly-linked list to operate on
nodethe 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

◆ sys_dlist_peek_tail()

static sys_dnode_t * sys_dlist_peek_tail ( sys_dlist_t * list)
inlinestatic

#include <zephyr/sys/dlist.h>

get a reference to the tail item in the list

Parameters
listthe doubly-linked list to operate on
Returns
a pointer to the tail element, NULL if list is empty

◆ sys_dlist_prepend()

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

#include <zephyr/sys/dlist.h>

add node to head of list

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

Parameters
listthe doubly-linked list to operate on
nodethe element to append

◆ sys_dlist_remove()

static void sys_dlist_remove ( sys_dnode_t * node)
inlinestatic

#include <zephyr/sys/dlist.h>

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
nodethe node to remove

◆ sys_dnode_init()

static void sys_dnode_init ( sys_dnode_t * node)
inlinestatic

#include <zephyr/sys/dlist.h>

initialize node to its state when not in a list

Parameters
nodethe node

◆ sys_dnode_is_linked()

static bool sys_dnode_is_linked ( const sys_dnode_t * node)
inlinestatic

#include <zephyr/sys/dlist.h>

check if a node is a member of any list

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