Flagged Single-linked list

Flagged single-linked list implementation. More...

Macros
#define	SYS_SFLIST_FOR_EACH_NODE(__sl, __sn)
	Provide the primitive to iterate on a list Note: the loop is unsafe and thus __sn should not be removed.
#define	SYS_SFLIST_ITERATE_FROM_NODE(__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_SFLIST_FOR_EACH_NODE_SAFE(__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_SFLIST_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_SFLIST_PEEK_HEAD_CONTAINER(__sl, __cn, __n)
	Provide the primitive to peek container of the list head.
#define	SYS_SFLIST_PEEK_TAIL_CONTAINER(__sl, __cn, __n)
	Provide the primitive to peek container of the list tail.
#define	SYS_SFLIST_PEEK_NEXT_CONTAINER(__cn, __n)
	Provide the primitive to peek the next container.
#define	SYS_SFLIST_FOR_EACH_CONTAINER(__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_SFLIST_FOR_EACH_CONTAINER_SAFE(__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_SFLIST_STATIC_INIT(ptr_to_list)
	Statically initialize a flagged single-linked list.
#define	SYS_SFLIST_FLAGS_MASK   ((uintptr_t)(__alignof__(sys_sfnode_t) - 1))

Typedefs
typedef struct _sfnode	sys_sfnode_t
	Flagged single-linked list node structure.
typedef struct _sflist	sys_sflist_t
	Flagged single-linked list structure.

Functions
static void	sys_sflist_init (sys_sflist_t *list)
	Initialize a list.
static uint8_t	sys_sfnode_flags_get (sys_sfnode_t *node)
	Fetch flags value for a particular sfnode.
static sys_sfnode_t *	sys_sflist_peek_head (sys_sflist_t *list)
	Peek the first node from the list.
static sys_sfnode_t *	sys_sflist_peek_tail (sys_sflist_t *list)
	Peek the last node from the list.
static void	sys_sfnode_init (sys_sfnode_t *node, uint8_t flags)
	Initialize an sflist node.
static void	sys_sfnode_flags_set (sys_sfnode_t *node, uint8_t flags)
	Set flags value for an sflist node.
static bool	sys_sflist_is_empty (sys_sflist_t *list)
	Test if the given list is empty.
static sys_sfnode_t *	sys_sflist_peek_next_no_check (sys_sfnode_t *node)
	Peek the next node from current node, node is not NULL.
static sys_sfnode_t *	sys_sflist_peek_next (sys_sfnode_t *node)
	Peek the next node from current node.
static void	sys_sflist_prepend (sys_sflist_t *list, sys_sfnode_t *node)
	Prepend a node to the given list.
static void	sys_sflist_append (sys_sflist_t *list, sys_sfnode_t *node)
	Append a node to the given list.
static void	sys_sflist_append_list (sys_sflist_t *list, void *head, void *tail)
	Append a list to the given list.
static void	sys_sflist_merge_sflist (sys_sflist_t *list, sys_sflist_t *list_to_append)
	merge two sflists, appending the second one to the first
static void	sys_sflist_insert (sys_sflist_t *list, sys_sfnode_t *prev, sys_sfnode_t *node)
	Insert a node to the given list.
static sys_sfnode_t *	sys_sflist_get_not_empty (sys_sflist_t *list)
	Fetch and remove the first node of the given list.
static sys_sfnode_t *	sys_sflist_get (sys_sflist_t *list)
	Fetch and remove the first node of the given list.
static void	sys_sflist_remove (sys_sflist_t *list, sys_sfnode_t *prev_node, sys_sfnode_t *node)
	Remove a node.
static bool	sys_sflist_find_and_remove (sys_sflist_t *list, sys_sfnode_t *node)
	Find and remove a node from a list.
static size_t	sys_sflist_len (sys_sflist_t *list)
	Compute the size of the given list in O(n) time.

Detailed Description

Flagged single-linked list implementation.

Similar to Single-linked list with the added ability to define user "flags" bits for each node. They can be accessed and modified using the sys_sfnode_flags_get() and sys_sfnode_flags_set() APIs.

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

#define SYS_SFLIST_CONTAINER	(		__ln,
			__cn,
			__n )

#include <zephyr/sys/sflist.h>

Value:

        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.

Parameters

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

SYS_SFLIST_FLAGS_MASK

#define SYS_SFLIST_FLAGS_MASK   ((uintptr_t)(__alignof__(sys_sfnode_t) - 1))

#include <zephyr/sys/sflist.h>

SYS_SFLIST_FOR_EACH_CONTAINER

#define SYS_SFLIST_FOR_EACH_CONTAINER	(		__sl,
			__cn,
			__n )

#include <zephyr/sys/sflist.h>

Value:

        Z_GENLIST_FOR_EACH_CONTAINER(sflist, __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.

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

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

Parameters

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

SYS_SFLIST_FOR_EACH_CONTAINER_SAFE

#define SYS_SFLIST_FOR_EACH_CONTAINER_SAFE	(		__sl,
			__cn,
			__cns,
			__n )

#include <zephyr/sys/sflist.h>

Value:

        Z_GENLIST_FOR_EACH_CONTAINER_SAFE(sflist, __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.

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

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

Parameters

__sl	A pointer on a sys_sflist_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_sfnode_t within the container struct

SYS_SFLIST_FOR_EACH_NODE

#define SYS_SFLIST_FOR_EACH_NODE	(		__sl,
			__sn )

#include <zephyr/sys/sflist.h>

Value:

        Z_GENLIST_FOR_EACH_NODE(sflist, __sl, __sn)

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

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

Parameters

__sl	A pointer on a sys_sflist_t to iterate on
__sn	A sys_sfnode_t pointer to peek each node of the list

SYS_SFLIST_FOR_EACH_NODE_SAFE

#define SYS_SFLIST_FOR_EACH_NODE_SAFE	(		__sl,
			__sn,
			__sns )

#include <zephyr/sys/sflist.h>

Value:

        Z_GENLIST_FOR_EACH_NODE_SAFE(sflist, __sl, __sn, __sns)

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

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

Parameters

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

SYS_SFLIST_ITERATE_FROM_NODE

#define SYS_SFLIST_ITERATE_FROM_NODE	(		__sl,
			__sn )

#include <zephyr/sys/sflist.h>

Value:

        Z_GENLIST_ITERATE_FROM_NODE(sflist, __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.

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

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

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

Parameters

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

SYS_SFLIST_PEEK_HEAD_CONTAINER

#define SYS_SFLIST_PEEK_HEAD_CONTAINER	(		__sl,
			__cn,
			__n )

#include <zephyr/sys/sflist.h>

Value:

        Z_GENLIST_PEEK_HEAD_CONTAINER(sflist, __sl, __cn, __n)

Provide the primitive to peek container of the list head.

Parameters

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

SYS_SFLIST_PEEK_NEXT_CONTAINER

#define SYS_SFLIST_PEEK_NEXT_CONTAINER	(		__cn,
			__n )

#include <zephyr/sys/sflist.h>

Value:

        Z_GENLIST_PEEK_NEXT_CONTAINER(sflist, __cn, __n)

Provide the primitive to peek the next container.

Parameters

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

SYS_SFLIST_PEEK_TAIL_CONTAINER

#define SYS_SFLIST_PEEK_TAIL_CONTAINER	(		__sl,
			__cn,
			__n )

#include <zephyr/sys/sflist.h>

Value:

        Z_GENLIST_PEEK_TAIL_CONTAINER(sflist, __sl, __cn, __n)

Provide the primitive to peek container of the list tail.

Parameters

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

SYS_SFLIST_STATIC_INIT

#define SYS_SFLIST_STATIC_INIT

(

ptr_to_list

)

#include <zephyr/sys/sflist.h>

Value:

{NULL, NULL}

Statically initialize a flagged single-linked list.

Parameters

ptr_to_list

A pointer on the list to initialize

Typedef Documentation

sys_sflist_t

typedef struct _sflist sys_sflist_t

#include <zephyr/sys/sflist.h>

Flagged single-linked list structure.

sys_sfnode_t

typedef struct _sfnode sys_sfnode_t

#include <zephyr/sys/sflist.h>

Flagged single-linked list node structure.

Function Documentation

sys_sflist_append()

static void sys_sflist_append ( sys_sflist_t * list, sys_sfnode_t * node )

inlinestatic

#include <zephyr/sys/sflist.h>

Append a node to the given list.

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

Parameters

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

sys_sflist_append_list()

static void sys_sflist_append_list ( sys_sflist_t * list, void * head, void * tail )

inlinestatic

#include <zephyr/sys/sflist.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_sflist_*() 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_sflist_find_and_remove()

static bool sys_sflist_find_and_remove ( sys_sflist_t * list, sys_sfnode_t * node )

inlinestatic

#include <zephyr/sys/sflist.h>

Find and remove a node from a list.

This and other sys_sflist_*() 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_sflist_get()

static sys_sfnode_t * sys_sflist_get ( sys_sflist_t * list )

inlinestatic

#include <zephyr/sys/sflist.h>

Fetch and remove the first node of the given list.

This and other sys_sflist_*() 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_sflist_get_not_empty()

static sys_sfnode_t * sys_sflist_get_not_empty ( sys_sflist_t * list )

inlinestatic

#include <zephyr/sys/sflist.h>

Fetch and remove the first node of the given list.

List must be known to be non-empty. This and other sys_sflist_*() 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_sflist_init()

static void sys_sflist_init ( sys_sflist_t * list )

inlinestatic

#include <zephyr/sys/sflist.h>

Initialize a list.

Parameters

list	A pointer on the list to initialize

sys_sflist_insert()

static void sys_sflist_insert ( sys_sflist_t * list, sys_sfnode_t * prev, sys_sfnode_t * node )

inlinestatic

#include <zephyr/sys/sflist.h>

Insert a node to the given list.

This and other sys_sflist_*() 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_sflist_is_empty()

static bool sys_sflist_is_empty ( sys_sflist_t * list )

inlinestatic

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

static size_t sys_sflist_len ( sys_sflist_t * list )

inlinestatic

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

static void sys_sflist_merge_sflist ( sys_sflist_t * list, sys_sflist_t * list_to_append )

inlinestatic

#include <zephyr/sys/sflist.h>

merge two sflists, appending the second one to the first

When the operation is completed, the appending list is empty. This and other sys_sflist_*() 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_sflist_peek_head()

static sys_sfnode_t * sys_sflist_peek_head ( sys_sflist_t * list )

inlinestatic

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

static sys_sfnode_t * sys_sflist_peek_next ( sys_sfnode_t * node )

inlinestatic

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

static sys_sfnode_t * sys_sflist_peek_next_no_check ( sys_sfnode_t * node )

inlinestatic

#include <zephyr/sys/sflist.h>

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

Faster then sys_sflist_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_sflist_peek_tail()

static sys_sfnode_t * sys_sflist_peek_tail ( sys_sflist_t * list )

inlinestatic

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

static void sys_sflist_prepend ( sys_sflist_t * list, sys_sfnode_t * node )

inlinestatic

#include <zephyr/sys/sflist.h>

Prepend a node to the given list.

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

Parameters

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

sys_sflist_remove()

static void sys_sflist_remove ( sys_sflist_t * list, sys_sfnode_t * prev_node, sys_sfnode_t * node )

inlinestatic

#include <zephyr/sys/sflist.h>

Remove a node.

This and other sys_sflist_*() 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

sys_sfnode_flags_get()

static uint8_t sys_sfnode_flags_get ( sys_sfnode_t * node )

inlinestatic

#include <zephyr/sys/sflist.h>

Fetch flags value for a particular sfnode.

Parameters

node	A pointer to the node to fetch flags from

Returns

The value of flags, which will be between 0 and 3 on 32-bit architectures, or between 0 and 7 on 64-bit architectures

sys_sfnode_flags_set()

static void sys_sfnode_flags_set ( sys_sfnode_t * node, uint8_t flags )

inlinestatic

#include <zephyr/sys/sflist.h>

Set flags value for an sflist node.

Set a flags value for this slist node, which can be a value between 0 and 3 on 32-bit architectures, or between 0 and 7 on 64-bit architectures. These flags will persist even if the node is moved around within a list, removed, or transplanted to a different slist.

Parameters

node	A pointer to the node to set the flags on
flags	The flags value to set

sys_sfnode_init()

static void sys_sfnode_init ( sys_sfnode_t * node, uint8_t flags )

inlinestatic

#include <zephyr/sys/sflist.h>

Initialize an sflist node.

Set an initial flags value for this slist node, which can be a value between 0 and 3 on 32-bit architectures, or between 0 and 7 on 64-bit architectures. These flags will persist even if the node is moved around within a list, removed, or transplanted to a different slist.

This is ever so slightly faster than sys_sfnode_flags_set() and should only be used on a node that hasn't been added to any list.

Parameters

node	A pointer to the node to set the flags on
flags	The flags value to set