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)    (((__dn) != NULL) ? CONTAINER_OF(__dn, __typeof__(*(__cn)), __n) : NULL)
	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)    SYS_DLIST_CONTAINER(sys_dlist_peek_head(__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)   { {(ptr_to_list)}, {(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_t *	sys_dlist_peek_head (sys_dlist_t *list)
	get a reference to the head item in the list
static sys_dnode_t *	sys_dlist_peek_head_not_empty (sys_dlist_t *list)
	get a reference to the head item in the list
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
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
static 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
static 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
static sys_dnode_t *	sys_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_t *	sys_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
	)		(((__dn) != NULL) ? CONTAINER_OF(__dn, __typeof__(*(__cn)), __n) : NULL)

#include <include/zephyr/sys/dlist.h>

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_FOR_EACH_CONTAINER

#define SYS_DLIST_FOR_EACH_CONTAINER	(		__dl,
			__cn,
			__n
	)

#include <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))

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

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

#include <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

__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_FOR_EACH_NODE

#define SYS_DLIST_FOR_EACH_NODE	(		__dl,
			__dn
	)

#include <include/zephyr/sys/dlist.h>

Value:

        for (__dn = sys_dlist_peek_head(__dl); __dn != NULL;            \
             __dn = sys_dlist_peek_next(__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_FOR_EACH_NODE_SAFE

#define SYS_DLIST_FOR_EACH_NODE_SAFE	(		__dl,
			__dn,
			__dns
	)

#include <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

__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_ITERATE_FROM_NODE

#define SYS_DLIST_ITERATE_FROM_NODE	(		__dl,
			__dn
	)

#include <include/zephyr/sys/dlist.h>

Value:

        for (__dn = __dn ? sys_dlist_peek_next_no_check(__dl, __dn) \
                         : sys_dlist_peek_head(__dl); \
             __dn != NULL; \
             __dn = sys_dlist_peek_next(__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_PEEK_HEAD_CONTAINER

#define SYS_DLIST_PEEK_HEAD_CONTAINER	(		__dl,
			__cn,
			__n
	)		SYS_DLIST_CONTAINER(sys_dlist_peek_head(__dl), __cn, __n)

#include <include/zephyr/sys/dlist.h>

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

#define SYS_DLIST_PEEK_NEXT_CONTAINER	(		__dl,
			__cn,
			__n
	)

#include <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

__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_STATIC_INIT

#define SYS_DLIST_STATIC_INIT

(

ptr_to_list

)

{ {(ptr_to_list)}, {(ptr_to_list)} }

#include <include/zephyr/sys/dlist.h>

Static initializer for a doubly-linked list.

Typedef Documentation

sys_dlist_t

typedef struct _dnode sys_dlist_t

#include <include/zephyr/sys/dlist.h>

Doubly-linked list structure.

sys_dnode_t

typedef struct _dnode sys_dnode_t

#include <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 <include/zephyr/sys/dlist.h>

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

sys_dlist_get()

static sys_dnode_t * sys_dlist_get ( sys_dlist_t *  list )

inlinestatic

#include <include/zephyr/sys/dlist.h>

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

sys_dlist_has_multiple_nodes()

static bool sys_dlist_has_multiple_nodes ( sys_dlist_t *  list )

inlinestatic

#include <include/zephyr/sys/dlist.h>

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

sys_dlist_init()

static void sys_dlist_init ( sys_dlist_t *  list )

inlinestatic

#include <include/zephyr/sys/dlist.h>

initialize list to its empty state

Parameters

list	the doubly-linked list

sys_dlist_insert()

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

inlinestatic

#include <include/zephyr/sys/dlist.h>

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

sys_dlist_insert_at()

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

inlinestatic

#include <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

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()

sys_dlist_is_empty()

static bool sys_dlist_is_empty ( sys_dlist_t *  list )

inlinestatic

#include <include/zephyr/sys/dlist.h>

check if the list is empty

Parameters

list	the 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 <include/zephyr/sys/dlist.h>

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

sys_dlist_is_tail()

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

inlinestatic

#include <include/zephyr/sys/dlist.h>

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

sys_dlist_len()

static size_t sys_dlist_len ( sys_dlist_t *  list )

inlinestatic

#include <include/zephyr/sys/dlist.h>

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

sys_dlist_peek_head()

static sys_dnode_t * sys_dlist_peek_head ( sys_dlist_t *  list )

inlinestatic

#include <include/zephyr/sys/dlist.h>

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

sys_dlist_peek_head_not_empty()

static sys_dnode_t * sys_dlist_peek_head_not_empty ( sys_dlist_t *  list )

inlinestatic

#include <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

list	the 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 <include/zephyr/sys/dlist.h>

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

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

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

sys_dlist_peek_prev()

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

inlinestatic

#include <include/zephyr/sys/dlist.h>

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

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

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

sys_dlist_peek_tail()

static sys_dnode_t * sys_dlist_peek_tail ( sys_dlist_t *  list )

inlinestatic

#include <include/zephyr/sys/dlist.h>

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

sys_dlist_prepend()

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

inlinestatic

#include <include/zephyr/sys/dlist.h>

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

sys_dlist_remove()

static void sys_dlist_remove ( sys_dnode_t *  node )

inlinestatic

#include <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

node	the node to remove

sys_dnode_init()

static void sys_dnode_init ( sys_dnode_t *  node )

inlinestatic

#include <include/zephyr/sys/dlist.h>

initialize node to its state when not in a list

Parameters

node

the node

sys_dnode_is_linked()

static bool sys_dnode_is_linked ( const sys_dnode_t *  node )

inlinestatic

#include <include/zephyr/sys/dlist.h>

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