Singly Linked List

The Zephyr singly linked list is implemented in the following file: zephyr/include/zephyr/sys/slist.h.

Zephyr stores singly linked list data in sys_slist_t (i.e., each list element stores a pointer to the next element, rather than the data of the previous element).

/** @cond INTERNAL_HIDDEN */
struct _slist {
    sys_snode_t *head;
    sys_snode_t *tail;
};

/** Single-linked list structure. */
typedef struct _slist sys_slist_t;

This structure allows O(1) access to the first (head) and last (tail) elements of the list:

• Insert at the front of the list or after the end
• Remove the head

To delete/insert a specified node, it is necessary to traverse the list from the head, which has a time complexity of O(n).

Zephyr stores the nodes of the singly linked list in sys_snode_t, which only contains a pointer to the next node:

struct _snode {
    struct _snode *next;
};
/** @endcond */

/** Single-linked list node structure. */
typedef struct _snode sys_snode_t;

Node space should be allocated by the user, typically embedded within the user-defined container structure. For example, if a user wants to organize a set of void *data as a singly linked list, they need to define a user node structure:

struct container_node {
    sys_snode_t node;
    void *data;
};

struct container_node *msg = malloc ( sizeof ( struct container_node )) ;

Access the linked list node through the user node member msg->node. When there is a linked list node node, SYS_SLIST_CONTAINER can be used to retrieve the user node:

sys_snode_t *list_node = sys_slist_get ( &test_list ) ;
struct container_node *msg = SYS_SLIST_CONTAINER ( list_node, msg, node ) ;

The organizational relationship between the singly linked list and its nodes is as follows:

Initialization

sys_slist_t is allocated by the user from accessible memory and initialized using sys_slist_init() or static assignment with SYS_SLIST_STATIC_INIT. The internal fields of sys_slist_t are opaque to the user and should not be accessed by user code.

static sys_slist_t test_list;

sys_slist_init(&test_list);

Or

static sys_slist_t test_list = SYS_SLIST_STATIC_INIT(&test_list);

Operations

Node Addition and Deletion

• sys_slist_prepend() adds a node at the head of the list
• sys_slist_append() adds a node at the tail of the list
• sys_slist_insert() inserts a new node after the specified node in the list
• sys_slist_remove() removes the node following the specified node
• sys_slist_find_and_remove() removes the specified node

static struct container_node test_node_1;
static struct container_node test_node_2;
static struct container_node test_node_3;
static struct container_node test_node_4;

// test_node_1 ( head/tail )
sys_slist_prepend ( &test_list, &test_node_1.node ) ;

// test_node_1 ( head ) -> test_node_2 ( tail )
sys_slist_append ( &test_list, &test_node_2.node ) ;

// test_node_1 ( head ) -> test_node_3 -> test_node_2 ( tail )
sys_slist_insert ( &test_list, &test_node_1.node, &test_node_3.node ) ;

// test_node_1 ( head ) -> test_node_4 -> test_node_3 -> test_node_2 ( tail )
sys_slist_insert ( &test_list, &test_node_1.node, &test_node_4.node ) ;

// test_node_1 ( head ) -> test_node_4 -> test_node_2 ( tail )
sys_slist_remove ( &test_list, &test_node_4.node, &test_node_3.node ) ;

// test_node_1 ( head ) -> test_node_2 ( tail )
sys_slist_find_and_remove ( &test_list, &test_node_3.node ) ;

Node Access

Nodes can be peeked using sys_slist_peek_head() and sys_slist_peek_tail(), and sys_slist_peek_next() can be used to peek the next node of a specified node. If the list is empty, it returns NULL; otherwise, it returns a pointer to sys_snode_t.

// Assume the list is test_node_1 ( head ) -> test_node_4 -> test_node_3 -> test_node_2 ( tail )
// hnode = test_node_1
sys_snode_t *hnode = sys_slist_peek_head ( list ) ;

// tnode = test_node_2
sys_snode_t *tnode = sys_slist_peek_tail ( list ) ;

// nnode = test_node_4
sys_snode_t *nnode = sys_slist_peek_next ( &test_node_1.node ) ;

The singly linked list also provides a set of “for each” macros that allow direct traversal of the singly linked list without manually traversing the next pointers. SYS_SLIST_FOR_EACH_NODE enumerates each node in the list, providing a local variable to store the node pointer. SYS_SLIST_FOR_EACH_NODE_SAFE behaves similarly but requires an additional temporary variable for node storage, allowing users to delete traversed nodes during iteration. Both macros have corresponding “CONTAINEROF” variants (SYS_SLIST_FOR_EACH_CONTAINER and SYS_SLIST_FOR_EACH_CONTAINER_SAFE), which allocate a local variable corresponding to the user-defined container structure and perform the necessary offsets internally. SYS_SLIST_FOR_EACH_NODE starts traversing all nodes from the head of the list, while SYS_SLIST_ITERATE_FROM_NODE can start traversing from a specified node. Typically, we use user container nodes.

struct container_node *cnode;
struct container_node *s_cnode;

// Parameters: list ( test_list ), container node variable ( cnode ), name of the list in the node container structure ( node, refer to struct container_node )
SYS_SLIST_FOR_EACH_CONTAINER ( test_list, cnode, node ) {
        // Modify node content
    }

// Parameters: list ( test_list ), container node variable ( cnode ), safe container node pointer ( s_cnode ), name of the list in the node container structure ( node, refer to struct container_node )
SYS_SLIST_FOR_EACH_CONTAINER_SAFE ( test_list, cnode, s_cnode, node ) {
    // Delete node
    sys_slist_find_and_remove ( &test_list, &cnode->node ) ;
    }

When using the SYS_SLIST_FOR_EACH_CONTAINER_SAFE macro, the next node reference can be saved through the additional s_cnode. This allows safe access and traversal of the next node after deleting the current node without affecting the correctness of the traversal. However, when using the SYS_SLIST_FOR_EACH_CONTAINER macro, deleting the current node will cause the traversal process to malfunction, as the next node reference is not saved.

List Operations

Check if the linked list list is empty:

static inline bool sys_slist_is_empty ( sys_slist_t *list ) ;

Add a linked list (with head and tail) to the end of list:

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

Merge sys_slist_merge_slist into list:

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

Get the number of nodes in list:

static inline size_t sys_slist_len ( sys_slist_t *list ) ;

Flagged Singly Linked List

The flagged linked list sys_sflist_t is implemented in zephyr/include/zephyr/sys/sflist.h. Its principle is the same as that of the ordinary singly linked list sys_slist_t, but the flagged linked list can set 2 bits for flags. Zephyr targets 32-bit and above SoCs, so the memory allocated for nodes is at least 4 bytes aligned. Therefore, for a node pointer, the low 2 bits are not used, and the flagged linked list utilizes these unused 2 bits as flag bits.

# ifdef __LP64__
typedef uint64_t unative_t;
# else
typedef uint32_t unative_t;
# endif

/** @cond INTERNAL_HIDDEN */
struct _sfnode {
    unative_t next_and_flags;
};
/** @endcond */

/** Flagged single-linked list node structure. */
typedef struct _sfnode sys_sfnode_t;

# define SYS_SFLIST_FLAGS_MASK    0x3UL

Use sys_sfnode_flags_get and sys_sfnode_flags_set to manipulate the flag bits, and use z_sfnode_next_peek to obtain the address of the next node.

static inline void sys_sfnode_flags_set ( sys_sfnode_t *node, uint8_t flags )
{
    __ASSERT (( flags & ~SYS_SFLIST_FLAGS_MASK ) == 0UL, "flags too large" ) ;
    node->next_and_flags = ( unative_t ) ( z_sfnode_next_peek ( node )) | flags;
}

static inline uint8_t sys_sfnode_flags_get ( sys_sfnode_t *node )
{
    return node->next_and_flags & SYS_SFLIST_FLAGS_MASK;
}

static inline sys_sfnode_t *z_sfnode_next_peek ( sys_sfnode_t *node )
{
    return ( sys_sfnode_t * ) ( node->next_and_flags & ~SYS_SFLIST_FLAGS_MASK ) ;
}

References

https://docs.zephyrproject.org/3.5.0/kernel/data_structures/slist.html