Single-linked list

Single-linked list implementation. More...

Macros
#define	SYS_SLIST_FOR_EACH_NODE(__sl, __sn)    Z_GENLIST_FOR_EACH_NODE(slist, __sl, __sn)
	Provide the primitive to iterate on a list Note: the loop is unsafe and thus __sn should not be removed.
#define	SYS_SLIST_ITERATE_FROM_NODE(__sl, __sn)    Z_GENLIST_ITERATE_FROM_NODE(slist, __sl, __sn)
	Provide the primitive to iterate on a list, from a node in the list Note: the loop is unsafe and thus __sn should not be removed.
#define	SYS_SLIST_FOR_EACH_NODE_SAFE(__sl, __sn, __sns)    Z_GENLIST_FOR_EACH_NODE_SAFE(slist, __sl, __sn, __sns)
	Provide the primitive to safely iterate on a list Note: __sn can be removed, it will not break the loop.
#define	SYS_SLIST_CONTAINER(__ln, __cn, __n)    Z_GENLIST_CONTAINER(__ln, __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_SLIST_PEEK_HEAD_CONTAINER(__sl, __cn, __n)    Z_GENLIST_PEEK_HEAD_CONTAINER(slist, __sl, __cn, __n)
	Provide the primitive to peek container of the list head.
#define	SYS_SLIST_PEEK_TAIL_CONTAINER(__sl, __cn, __n)    Z_GENLIST_PEEK_TAIL_CONTAINER(slist, __sl, __cn, __n)
	Provide the primitive to peek container of the list tail.
#define	SYS_SLIST_PEEK_NEXT_CONTAINER(__cn, __n)    Z_GENLIST_PEEK_NEXT_CONTAINER(slist, __cn, __n)
	Provide the primitive to peek the next container.
#define	SYS_SLIST_FOR_EACH_CONTAINER(__sl, __cn, __n)    Z_GENLIST_FOR_EACH_CONTAINER(slist, __sl, __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_SLIST_FOR_EACH_CONTAINER_SAFE(__sl, __cn, __cns, __n)    Z_GENLIST_FOR_EACH_CONTAINER_SAFE(slist, __sl, __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_SLIST_STATIC_INIT(ptr_to_list)   {NULL, NULL}
	Statically initialize a single-linked list.

Typedefs
typedef struct _snode	sys_snode_t
	Single-linked list node structure.
typedef struct _slist	sys_slist_t
	Single-linked list structure.

Functions
static void	sys_slist_init (sys_slist_t *list)
	Initialize a list.
static sys_snode_t *	sys_slist_peek_head (sys_slist_t *list)
	Peek the first node from the list.
static sys_snode_t *	sys_slist_peek_tail (sys_slist_t *list)
	Peek the last node from the list.
static bool	sys_slist_is_empty (sys_slist_t *list)
	Test if the given list is empty.
static sys_snode_t *	sys_slist_peek_next_no_check (sys_snode_t *node)
	Peek the next node from current node, node is not NULL.
static sys_snode_t *	sys_slist_peek_next (sys_snode_t *node)
	Peek the next node from current node.
static void	sys_slist_prepend (sys_slist_t *list, sys_snode_t *node)
	Prepend a node to the given list.
static void	sys_slist_append (sys_slist_t *list, sys_snode_t *node)
	Append a node to the given list.
static void	sys_slist_append_list (sys_slist_t *list, void *head, void *tail)
	Append a list to the given list.
static void	sys_slist_merge_slist (sys_slist_t *list, sys_slist_t *list_to_append)
	merge two slists, appending the second one to the first
static void	sys_slist_insert (sys_slist_t *list, sys_snode_t *prev, sys_snode_t *node)
	Insert a node to the given list.
static sys_snode_t *	sys_slist_get_not_empty (sys_slist_t *list)
	Fetch and remove the first node of the given list.
static sys_snode_t *	sys_slist_get (sys_slist_t *list)
	Fetch and remove the first node of the given list.
static void	sys_slist_remove (sys_slist_t *list, sys_snode_t *prev_node, sys_snode_t *node)
	Remove a node.
static bool	sys_slist_find_and_remove (sys_slist_t *list, sys_snode_t *node)
	Find and remove a node from a list.
static bool	sys_slist_find (sys_slist_t *list, sys_snode_t *node, sys_snode_t **prev)
	Find if a node is already linked in a singly linked list.
static size_t	sys_slist_len (sys_slist_t *list)
	Compute the size of the given list in O(n) time.

Detailed Description

Single-linked list implementation.

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

Macro Definition Documentation

SYS_SLIST_CONTAINER

#define SYS_SLIST_CONTAINER	(		__ln,
			__cn,
			__n
	)		Z_GENLIST_CONTAINER(__ln, __cn, __n)

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

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

Parameters

__ln	A pointer on a sys_node_t to get its container
__cn	Container struct type pointer
__n	The field name of sys_node_t within the container struct

SYS_SLIST_FOR_EACH_CONTAINER

#define SYS_SLIST_FOR_EACH_CONTAINER	(		__sl,
			__cn,
			__n
	)		Z_GENLIST_FOR_EACH_CONTAINER(slist, __sl, __cn, __n)

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

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_SLIST_FOR_EACH_CONTAINER(l, c, n) {
    <user code>
}

Parameters

__sl	A pointer on a sys_slist_t to iterate on
__cn	A pointer to peek each entry of the list
__n	The field name of sys_node_t within the container struct

SYS_SLIST_FOR_EACH_CONTAINER_SAFE

#define SYS_SLIST_FOR_EACH_CONTAINER_SAFE	(		__sl,
			__cn,
			__cns,
			__n
	)		Z_GENLIST_FOR_EACH_CONTAINER_SAFE(slist, __sl, __cn, __cns, __n)

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

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_SLIST_FOR_EACH_NODE_SAFE(l, c, cn, n) {
    <user code>
}

Parameters

__sl	A pointer on a sys_slist_t to iterate on
__cn	A pointer to peek each entry of the list
__cns	A pointer for the loop to run safely
__n	The field name of sys_node_t within the container struct

SYS_SLIST_FOR_EACH_NODE

#define SYS_SLIST_FOR_EACH_NODE	(		__sl,
			__sn
	)		Z_GENLIST_FOR_EACH_NODE(slist, __sl, __sn)

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

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

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

SYS_SLIST_FOR_EACH_NODE(l, n) {
    <user code>
}

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

Parameters

__sl	A pointer on a sys_slist_t to iterate on
__sn	A sys_snode_t pointer to peek each node of the list

SYS_SLIST_FOR_EACH_NODE_SAFE

#define SYS_SLIST_FOR_EACH_NODE_SAFE	(		__sl,
			__sn,
			__sns
	)		Z_GENLIST_FOR_EACH_NODE_SAFE(slist, __sl, __sn, __sns)

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

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

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

SYS_SLIST_FOR_EACH_NODE_SAFE(l, n, s) {
    <user code>
}

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

Parameters

__sl	A pointer on a sys_slist_t to iterate on
__sn	A sys_snode_t pointer to peek each node of the list
__sns	A sys_snode_t pointer for the loop to run safely

SYS_SLIST_ITERATE_FROM_NODE

#define SYS_SLIST_ITERATE_FROM_NODE	(		__sl,
			__sn
	)		Z_GENLIST_ITERATE_FROM_NODE(slist, __sl, __sn)

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

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

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

SYS_SLIST_ITERATE_FROM_NODE(l, n) {
    <user code>
}

Like SYS_SLIST_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_SLIST_*() macros are not thread safe.

Parameters

__sl	A pointer on a sys_slist_t to iterate on
__sn	A sys_snode_t pointer to peek each node of the list it contains the starting node, or NULL to start from the head

SYS_SLIST_PEEK_HEAD_CONTAINER

#define SYS_SLIST_PEEK_HEAD_CONTAINER	(		__sl,
			__cn,
			__n
	)		Z_GENLIST_PEEK_HEAD_CONTAINER(slist, __sl, __cn, __n)

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

Provide the primitive to peek container of the list head.

Parameters

__sl	A pointer on a sys_slist_t to peek
__cn	Container struct type pointer
__n	The field name of sys_node_t within the container struct

SYS_SLIST_PEEK_NEXT_CONTAINER

#define SYS_SLIST_PEEK_NEXT_CONTAINER	(		__cn,
			__n
	)		Z_GENLIST_PEEK_NEXT_CONTAINER(slist, __cn, __n)

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

Provide the primitive to peek the next container.

Parameters

__cn	Container struct type pointer
__n	The field name of sys_node_t within the container struct

SYS_SLIST_PEEK_TAIL_CONTAINER

#define SYS_SLIST_PEEK_TAIL_CONTAINER	(		__sl,
			__cn,
			__n
	)		Z_GENLIST_PEEK_TAIL_CONTAINER(slist, __sl, __cn, __n)

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

Provide the primitive to peek container of the list tail.

Parameters

__sl	A pointer on a sys_slist_t to peek
__cn	Container struct type pointer
__n	The field name of sys_node_t within the container struct

SYS_SLIST_STATIC_INIT

#define SYS_SLIST_STATIC_INIT

(

ptr_to_list

)

{NULL, NULL}

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

Statically initialize a single-linked list.

Parameters

ptr_to_list

A pointer on the list to initialize

Typedef Documentation

sys_slist_t

typedef struct _slist sys_slist_t

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

Single-linked list structure.

sys_snode_t

typedef struct _snode sys_snode_t

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

Single-linked list node structure.

Function Documentation

sys_slist_append()

static void sys_slist_append ( sys_slist_t *  list, sys_snode_t *  node  )

inlinestatic

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

Append a node to the given list.

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

Parameters

list	A pointer on the list to affect
node	A pointer on the node to append

sys_slist_append_list()

static void sys_slist_append_list ( sys_slist_t *  list, void *  head, void *  tail  )

inlinestatic

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

Append a list to the given list.

Append a singly-linked, NULL-terminated list consisting of nodes containing the pointer to the next node as the first element of a node, to list. This and other sys_slist_*() functions are not thread safe.

FIXME: Why are the element parameters void *?

Parameters

list	A pointer on the list to affect
head	A pointer to the first element of the list to append
tail	A pointer to the last element of the list to append

sys_slist_find()

static bool sys_slist_find ( sys_slist_t *  list, sys_snode_t *  node, sys_snode_t **  prev  )

inlinestatic

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

Find if a node is already linked in a singly linked list.

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

Parameters

	list	A pointer to the list to check
	node	A pointer to the node to search in the list
[out]	prev	A pointer to the previous node

Returns

true if node was found in the list, false otherwise

sys_slist_find_and_remove()

static bool sys_slist_find_and_remove ( sys_slist_t *  list, sys_snode_t *  node  )

inlinestatic

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

Find and remove a node from a list.

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

Parameters

list	A pointer on the list to affect
node	A pointer on the node to remove from the list

Returns

true if node was removed

sys_slist_get()

static sys_snode_t * sys_slist_get ( sys_slist_t *  list )

inlinestatic

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

Fetch and remove the first node of the given list.

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

Parameters

list	A pointer on the list to affect

Returns

A pointer to the first node of the list (or NULL if empty)

sys_slist_get_not_empty()

static sys_snode_t * sys_slist_get_not_empty ( sys_slist_t *  list )

inlinestatic

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

Fetch and remove the first node of the given list.

List must be known to be non-empty. This and other sys_slist_*() functions are not thread safe.

Parameters

list	A pointer on the list to affect

Returns

A pointer to the first node of the list

sys_slist_init()

static void sys_slist_init ( sys_slist_t *  list )

inlinestatic

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

Initialize a list.

Parameters

list	A pointer on the list to initialize

sys_slist_insert()

static void sys_slist_insert ( sys_slist_t *  list, sys_snode_t *  prev, sys_snode_t *  node  )

inlinestatic

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

Insert a node to the given list.

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

Parameters

list	A pointer on the list to affect
prev	A pointer on the previous node
node	A pointer on the node to insert

sys_slist_is_empty()

static bool sys_slist_is_empty ( sys_slist_t *  list )

inlinestatic

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

Test if the given list is empty.

Parameters

list	A pointer on the list to test

Returns

a boolean, true if it's empty, false otherwise

sys_slist_len()

static size_t sys_slist_len ( sys_slist_t *  list )

inlinestatic

#include <include/zephyr/sys/slist.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_slist_merge_slist()

static void sys_slist_merge_slist ( sys_slist_t *  list, sys_slist_t *  list_to_append  )

inlinestatic

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

merge two slists, appending the second one to the first

When the operation is completed, the appending list is empty. This and other sys_slist_*() functions are not thread safe.

Parameters

list	A pointer on the list to affect
list_to_append	A pointer to the list to append.

sys_slist_peek_head()

static sys_snode_t * sys_slist_peek_head ( sys_slist_t *  list )

inlinestatic

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

Peek the first node from the list.

Parameters

list	A point on the list to peek the first node from

Returns

A pointer on the first node of the list (or NULL if none)

sys_slist_peek_next()

static sys_snode_t * sys_slist_peek_next ( sys_snode_t *  node )

inlinestatic

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

Peek the next node from current node.

Parameters

node	A pointer on the node where to peek the next node

Returns

a pointer on the next node (or NULL if none)

sys_slist_peek_next_no_check()

static sys_snode_t * sys_slist_peek_next_no_check ( sys_snode_t *  node )

inlinestatic

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

Peek the next node from current node, node is not NULL.

Faster then sys_slist_peek_next() if node is known not to be NULL.

Parameters

node	A pointer on the node where to peek the next node

Returns

a pointer on the next node (or NULL if none)

sys_slist_peek_tail()

static sys_snode_t * sys_slist_peek_tail ( sys_slist_t *  list )

inlinestatic

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

Peek the last node from the list.

Parameters

list	A point on the list to peek the last node from

Returns

A pointer on the last node of the list (or NULL if none)

sys_slist_prepend()

static void sys_slist_prepend ( sys_slist_t *  list, sys_snode_t *  node  )

inlinestatic

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

Prepend a node to the given list.

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

Parameters

list	A pointer on the list to affect
node	A pointer on the node to prepend

sys_slist_remove()

static void sys_slist_remove ( sys_slist_t *  list, sys_snode_t *  prev_node, sys_snode_t *  node  )

inlinestatic

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

Remove a node.

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

Parameters

list	A pointer on the list to affect
prev_node	A pointer on the previous node (can be NULL, which means the node is the list's head)
node	A pointer on the node to remove