Zephyr API Documentation 3.7.99
A Scalable Open Source RTOS
|
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_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. | |
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.
#define SYS_DLIST_CONTAINER | ( | __dn, | |
__cn, | |||
__n ) |
#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.
__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 |
#define SYS_DLIST_FOR_EACH_CONTAINER | ( | __dl, | |
__cn, | |||
__n ) |
#include <zephyr/sys/dlist.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_DLIST_FOR_EACH_CONTAINER(l, c, n) { <user code> }
__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 |
#define SYS_DLIST_FOR_EACH_CONTAINER_SAFE | ( | __dl, | |
__cn, | |||
__cns, | |||
__n ) |
#include <zephyr/sys/dlist.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_DLIST_FOR_EACH_CONTAINER_SAFE(l, c, cn, n) { <user code> }
__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 |
#define SYS_DLIST_FOR_EACH_NODE | ( | __dl, | |
__dn ) |
#include <zephyr/sys/dlist.h>
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.
__dl | A pointer on a sys_dlist_t to iterate on |
__dn | A sys_dnode_t pointer to peek each node of the list |
#define SYS_DLIST_FOR_EACH_NODE_SAFE | ( | __dl, | |
__dn, | |||
__dns ) |
#include <zephyr/sys/dlist.h>
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.
__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 |
#define SYS_DLIST_ITERATE_FROM_NODE | ( | __dl, | |
__dn ) |
#include <zephyr/sys/dlist.h>
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.
__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 |
#define SYS_DLIST_PEEK_HEAD_CONTAINER | ( | __dl, | |
__cn, | |||
__n ) |
#include <zephyr/sys/dlist.h>
Provide the primitive to peek container of the list head.
__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 |
#define SYS_DLIST_PEEK_NEXT_CONTAINER | ( | __dl, | |
__cn, | |||
__n ) |
#include <zephyr/sys/dlist.h>
Provide the primitive to peek the next container.
__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 |
#define SYS_DLIST_STATIC_INIT | ( | ptr_to_list | ) |
#include <zephyr/sys/dlist.h>
Static initializer for a doubly-linked list.
typedef struct _dnode sys_dlist_t |
#include <zephyr/sys/dlist.h>
Doubly-linked list structure.
typedef struct _dnode sys_dnode_t |
#include <zephyr/sys/dlist.h>
Doubly-linked list node structure.
|
inlinestatic |
#include <zephyr/sys/dlist.h>
add node to tail of list
This and other sys_dlist_*() functions are not thread safe.
list | the doubly-linked list to operate on |
node | the element to append |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
get the first node in a list
This and other sys_dlist_*() functions are not thread safe.
list | the doubly-linked list to operate on |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
check if more than one node present
This and other sys_dlist_*() functions are not thread safe.
list | the doubly-linked list to operate on |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
initialize list to its empty state
list | the doubly-linked list |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
Insert a node into a list.
Insert a node before a specified node in a dlist.
successor | the position before which "node" will be inserted |
node | the element to insert |
|
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.
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() |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
check if the list is empty
list | the doubly-linked list to operate on |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
check if a node is the list's head
list | the doubly-linked list to operate on |
node | the node to check |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
check if a node is the list's tail
list | the doubly-linked list to operate on |
node | the node to check |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
Compute the size of the given list in O(n) time.
list | A pointer on the list |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
get a reference to the head item in the list
list | the doubly-linked list to operate on |
|
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.
list | the doubly-linked list to operate on |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
get a reference to the next item in the list
list | the doubly-linked list to operate on |
node | the node from which to get the next element in the list |
|
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.
list | the doubly-linked list to operate on |
node | the node from which to get the next element in the list |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
get a reference to the previous item in the list
list | the doubly-linked list to operate on |
node | the node from which to get the previous element in the list |
|
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.
list | the doubly-linked list to operate on |
node | the node from which to get the previous element in the list |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
get a reference to the tail item in the list
list | the doubly-linked list to operate on |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
add node to head of list
This and other sys_dlist_*() functions are not thread safe.
list | the doubly-linked list to operate on |
node | the element to append |
|
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.
node | the node to remove |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
initialize node to its state when not in a list
node | the node |
|
inlinestatic |
#include <zephyr/sys/dlist.h>
check if a node is a member of any list
node | the node |