LCOV - code coverage report
Current view: top level - zephyr/sys - sflist.h Coverage Total Hit
Test: new.info Lines: 93.9 % 33 31
Test Date: 2025-09-05 20:47:19

            Line data    Source code
       1            0 : /*
       2              :  * Copyright (c) 2016 Intel Corporation
       3              :  *
       4              :  * SPDX-License-Identifier: Apache-2.0
       5              :  */
       6              : 
       7              :  /**
       8              :   * @file
       9              :   * @defgroup flagged-single-linked-list_apis Flagged Single-linked list
      10              :   * @ingroup datastructure_apis
      11              :   *
      12              :   * @brief Flagged single-linked list implementation.
      13              :   *
      14              :   * Similar to @ref single-linked-list_apis with the added ability to define
      15              :   * user "flags" bits for each node. They can be accessed and modified
      16              :   * using the sys_sfnode_flags_get() and sys_sfnode_flags_set() APIs.
      17              :   *
      18              :   * Flagged single-linked list implementation using inline macros/functions.
      19              :   * This API is not thread safe, and thus if a list is used across threads,
      20              :   * calls to functions must be protected with synchronization primitives.
      21              :   *
      22              :   * @{
      23              :   */
      24              : 
      25              : #ifndef ZEPHYR_INCLUDE_SYS_SFLIST_H_
      26              : #define ZEPHYR_INCLUDE_SYS_SFLIST_H_
      27              : 
      28              : #include <stdint.h>
      29              : #include <stdbool.h>
      30              : #include <zephyr/sys/__assert.h>
      31              : #include "list_gen.h"
      32              : 
      33              : #ifdef __cplusplus
      34              : extern "C" {
      35              : #endif
      36              : 
      37              : /** @cond INTERNAL_HIDDEN */
      38              : struct _sfnode {
      39              :         uintptr_t next_and_flags;
      40              : };
      41              : /** @endcond */
      42              : 
      43              : /** Flagged single-linked list node structure. */
      44            1 : typedef struct _sfnode sys_sfnode_t;
      45              : 
      46              : /** @cond INTERNAL_HIDDEN */
      47              : struct _sflist {
      48              :         sys_sfnode_t *head;
      49              :         sys_sfnode_t *tail;
      50              : };
      51              : /** @endcond */
      52              : 
      53              : /** Flagged single-linked list structure. */
      54            1 : typedef struct _sflist sys_sflist_t;
      55              : 
      56              : /**
      57              :  * @brief Provide the primitive to iterate on a list
      58              :  * Note: the loop is unsafe and thus __sn should not be removed
      59              :  *
      60              :  * User _MUST_ add the loop statement curly braces enclosing its own code:
      61              :  *
      62              :  *     SYS_SFLIST_FOR_EACH_NODE(l, n) {
      63              :  *         <user code>
      64              :  *     }
      65              :  *
      66              :  * This and other SYS_SFLIST_*() macros are not thread safe.
      67              :  *
      68              :  * @param __sl A pointer on a sys_sflist_t to iterate on
      69              :  * @param __sn A sys_sfnode_t pointer to peek each node of the list
      70              :  */
      71            1 : #define SYS_SFLIST_FOR_EACH_NODE(__sl, __sn)                            \
      72              :         Z_GENLIST_FOR_EACH_NODE(sflist, __sl, __sn)
      73              : 
      74              : /**
      75              :  * @brief Provide the primitive to iterate on a list, from a node in the list
      76              :  * Note: the loop is unsafe and thus __sn should not be removed
      77              :  *
      78              :  * User _MUST_ add the loop statement curly braces enclosing its own code:
      79              :  *
      80              :  *     SYS_SFLIST_ITERATE_FROM_NODE(l, n) {
      81              :  *         <user code>
      82              :  *     }
      83              :  *
      84              :  * Like SYS_SFLIST_FOR_EACH_NODE(), but __dn already contains a node in the list
      85              :  * where to start searching for the next entry from. If NULL, it starts from
      86              :  * the head.
      87              :  *
      88              :  * This and other SYS_SFLIST_*() macros are not thread safe.
      89              :  *
      90              :  * @param __sl A pointer on a sys_sflist_t to iterate on
      91              :  * @param __sn A sys_sfnode_t pointer to peek each node of the list
      92              :  *             it contains the starting node, or NULL to start from the head
      93              :  */
      94            1 : #define SYS_SFLIST_ITERATE_FROM_NODE(__sl, __sn)                                \
      95              :         Z_GENLIST_ITERATE_FROM_NODE(sflist, __sl, __sn)
      96              : 
      97              : /**
      98              :  * @brief Provide the primitive to safely iterate on a list
      99              :  * Note: __sn can be removed, it will not break the loop.
     100              :  *
     101              :  * User _MUST_ add the loop statement curly braces enclosing its own code:
     102              :  *
     103              :  *     SYS_SFLIST_FOR_EACH_NODE_SAFE(l, n, s) {
     104              :  *         <user code>
     105              :  *     }
     106              :  *
     107              :  * This and other SYS_SFLIST_*() macros are not thread safe.
     108              :  *
     109              :  * @param __sl A pointer on a sys_sflist_t to iterate on
     110              :  * @param __sn A sys_sfnode_t pointer to peek each node of the list
     111              :  * @param __sns A sys_sfnode_t pointer for the loop to run safely
     112              :  */
     113            1 : #define SYS_SFLIST_FOR_EACH_NODE_SAFE(__sl, __sn, __sns)                        \
     114              :         Z_GENLIST_FOR_EACH_NODE_SAFE(sflist, __sl, __sn, __sns)
     115              : 
     116              : /**
     117              :  * @brief Provide the primitive to resolve the container of a list node
     118              :  * Note: it is safe to use with NULL pointer nodes
     119              :  *
     120              :  * @param __ln A pointer on a sys_sfnode_t to get its container
     121              :  * @param __cn Container struct type pointer
     122              :  * @param __n The field name of sys_sfnode_t within the container struct
     123              :  */
     124            1 : #define SYS_SFLIST_CONTAINER(__ln, __cn, __n) \
     125              :         Z_GENLIST_CONTAINER(__ln, __cn, __n)
     126              : 
     127              : /**
     128              :  * @brief Provide the primitive to peek container of the list head
     129              :  *
     130              :  * @param __sl A pointer on a sys_sflist_t to peek
     131              :  * @param __cn Container struct type pointer
     132              :  * @param __n The field name of sys_sfnode_t within the container struct
     133              :  */
     134            1 : #define SYS_SFLIST_PEEK_HEAD_CONTAINER(__sl, __cn, __n) \
     135              :         Z_GENLIST_PEEK_HEAD_CONTAINER(sflist, __sl, __cn, __n)
     136              : 
     137              : /**
     138              :  * @brief Provide the primitive to peek container of the list tail
     139              :  *
     140              :  * @param __sl A pointer on a sys_sflist_t to peek
     141              :  * @param __cn Container struct type pointer
     142              :  * @param __n The field name of sys_sfnode_t within the container struct
     143              :  */
     144            1 : #define SYS_SFLIST_PEEK_TAIL_CONTAINER(__sl, __cn, __n) \
     145              :         Z_GENLIST_PEEK_TAIL_CONTAINER(sflist, __sl, __cn, __n)
     146              : 
     147              : /**
     148              :  * @brief Provide the primitive to peek the next container
     149              :  *
     150              :  * @param __cn Container struct type pointer
     151              :  * @param __n The field name of sys_sfnode_t within the container struct
     152              :  */
     153            1 : #define SYS_SFLIST_PEEK_NEXT_CONTAINER(__cn, __n) \
     154              :         Z_GENLIST_PEEK_NEXT_CONTAINER(sflist, __cn, __n)
     155              : 
     156              : /**
     157              :  * @brief Provide the primitive to iterate on a list under a container
     158              :  * Note: the loop is unsafe and thus __cn should not be detached
     159              :  *
     160              :  * User _MUST_ add the loop statement curly braces enclosing its own code:
     161              :  *
     162              :  *     SYS_SFLIST_FOR_EACH_CONTAINER(l, c, n) {
     163              :  *         <user code>
     164              :  *     }
     165              :  *
     166              :  * @param __sl A pointer on a sys_sflist_t to iterate on
     167              :  * @param __cn A pointer to peek each entry of the list
     168              :  * @param __n The field name of sys_sfnode_t within the container struct
     169              :  */
     170            1 : #define SYS_SFLIST_FOR_EACH_CONTAINER(__sl, __cn, __n)                  \
     171              :         Z_GENLIST_FOR_EACH_CONTAINER(sflist, __sl, __cn, __n)
     172              : 
     173              : /**
     174              :  * @brief Provide the primitive to safely iterate on a list under a container
     175              :  * Note: __cn can be detached, it will not break the loop.
     176              :  *
     177              :  * User _MUST_ add the loop statement curly braces enclosing its own code:
     178              :  *
     179              :  *     SYS_SFLIST_FOR_EACH_NODE_SAFE(l, c, cn, n) {
     180              :  *         <user code>
     181              :  *     }
     182              :  *
     183              :  * @param __sl A pointer on a sys_sflist_t to iterate on
     184              :  * @param __cn A pointer to peek each entry of the list
     185              :  * @param __cns A pointer for the loop to run safely
     186              :  * @param __n The field name of sys_sfnode_t within the container struct
     187              :  */
     188            1 : #define SYS_SFLIST_FOR_EACH_CONTAINER_SAFE(__sl, __cn, __cns, __n)      \
     189              :         Z_GENLIST_FOR_EACH_CONTAINER_SAFE(sflist, __sl, __cn, __cns, __n)
     190              : 
     191              : 
     192              : /*
     193              :  * Required function definitions for the list_gen.h interface
     194              :  *
     195              :  * These are the only functions that do not treat the list/node pointers
     196              :  * as completely opaque types.
     197              :  */
     198              : 
     199              : /**
     200              :  * @brief Initialize a list
     201              :  *
     202              :  * @param list A pointer on the list to initialize
     203              :  */
     204            1 : static inline void sys_sflist_init(sys_sflist_t *list)
     205              : {
     206              :         list->head = NULL;
     207              :         list->tail = NULL;
     208              : }
     209              : 
     210              : /**
     211              :  * @brief Statically initialize a flagged single-linked list
     212              :  * @param ptr_to_list A pointer on the list to initialize
     213              :  */
     214            1 : #define SYS_SFLIST_STATIC_INIT(ptr_to_list) {NULL, NULL}
     215              : 
     216              : /* Flag bits are stored in unused LSB of the sys_sfnode_t pointer */
     217            0 : #define SYS_SFLIST_FLAGS_MASK   ((uintptr_t)(__alignof__(sys_sfnode_t) - 1))
     218              : /* At least 2 available flag bits are expected */
     219              : BUILD_ASSERT(SYS_SFLIST_FLAGS_MASK >= 0x3);
     220              : 
     221              : static inline sys_sfnode_t *z_sfnode_next_peek(const sys_sfnode_t *node)
     222              : {
     223              :         return (sys_sfnode_t *)(node->next_and_flags & ~SYS_SFLIST_FLAGS_MASK);
     224              : }
     225              : 
     226              : static inline uint8_t sys_sfnode_flags_get(const sys_sfnode_t *node);
     227              : 
     228              : static inline void z_sfnode_next_set(sys_sfnode_t *parent,
     229              :                                        sys_sfnode_t *child)
     230              : {
     231              :         uint8_t cur_flags = sys_sfnode_flags_get(parent);
     232              : 
     233              :         parent->next_and_flags = cur_flags | (uintptr_t)child;
     234              : }
     235              : 
     236              : static inline void z_sflist_head_set(sys_sflist_t *list, sys_sfnode_t *node)
     237              : {
     238              :         list->head = node;
     239              : }
     240              : 
     241              : static inline void z_sflist_tail_set(sys_sflist_t *list, sys_sfnode_t *node)
     242              : {
     243              :         list->tail = node;
     244              : }
     245              : 
     246              : /**
     247              :  * @brief Peek the first node from the list
     248              :  *
     249              :  * @param list A point on the list to peek the first node from
     250              :  *
     251              :  * @return A pointer on the first node of the list (or NULL if none)
     252              :  */
     253            1 : static inline sys_sfnode_t *sys_sflist_peek_head(const sys_sflist_t *list)
     254              : {
     255              :         return list->head;
     256              : }
     257              : 
     258              : /**
     259              :  * @brief Peek the last node from the list
     260              :  *
     261              :  * @param list A point on the list to peek the last node from
     262              :  *
     263              :  * @return A pointer on the last node of the list (or NULL if none)
     264              :  */
     265            1 : static inline sys_sfnode_t *sys_sflist_peek_tail(const sys_sflist_t *list)
     266              : {
     267              :         return list->tail;
     268              : }
     269              : 
     270              : /*
     271              :  * APIs specific to sflist type
     272              :  */
     273              : 
     274              : /**
     275              :  * @brief Fetch flags value for a particular sfnode
     276              :  *
     277              :  * @param node A pointer to the node to fetch flags from
     278              :  * @return The value of flags, which will be between 0 and 3 on 32-bit
     279              :  *         architectures, or between 0 and 7 on 64-bit architectures
     280              :  */
     281            1 : static inline uint8_t sys_sfnode_flags_get(const sys_sfnode_t *node)
     282              : {
     283              :         return node->next_and_flags & SYS_SFLIST_FLAGS_MASK;
     284              : }
     285              : 
     286              : /**
     287              :  * @brief Initialize an sflist node
     288              :  *
     289              :  * Set an initial flags value for this slist node, which can be a value between
     290              :  * 0 and 3 on 32-bit architectures, or between 0 and 7 on 64-bit architectures.
     291              :  * These flags will persist even if the node is moved around within a list,
     292              :  * removed, or transplanted to a different slist.
     293              :  *
     294              :  * This is ever so slightly faster than sys_sfnode_flags_set() and should
     295              :  * only be used on a node that hasn't been added to any list.
     296              :  *
     297              :  * @param node A pointer to the node to set the flags on
     298              :  * @param flags The flags value to set
     299              :  */
     300            1 : static inline void sys_sfnode_init(sys_sfnode_t *node, uint8_t flags)
     301              : {
     302              :         __ASSERT((flags & ~SYS_SFLIST_FLAGS_MASK) == 0UL, "flags too large");
     303              :         node->next_and_flags = flags;
     304              : }
     305              : 
     306              : /**
     307              :  * @brief Set flags value for an sflist node
     308              :  *
     309              :  * Set a flags value for this slist node, which can be a value between
     310              :  * 0 and 3 on 32-bit architectures, or between 0 and 7 on 64-bit architectures.
     311              :  * These flags will persist even if the node is moved around within a list,
     312              :  * removed, or transplanted to a different slist.
     313              :  *
     314              :  * @param node A pointer to the node to set the flags on
     315              :  * @param flags The flags value to set
     316              :  */
     317            1 : static inline void sys_sfnode_flags_set(sys_sfnode_t *node, uint8_t flags)
     318              : {
     319              :         __ASSERT((flags & ~SYS_SFLIST_FLAGS_MASK) == 0UL, "flags too large");
     320              :         node->next_and_flags = (uintptr_t)(z_sfnode_next_peek(node)) | flags;
     321              : }
     322              : 
     323              : /*
     324              :  * Derived, generated APIs
     325              :  */
     326              : 
     327              : /**
     328              :  * @brief Test if the given list is empty
     329              :  *
     330              :  * @param list A pointer on the list to test
     331              :  *
     332              :  * @return a boolean, true if it's empty, false otherwise
     333              :  */
     334              : static inline bool sys_sflist_is_empty(const sys_sflist_t *list);
     335              : 
     336            1 : Z_GENLIST_IS_EMPTY(sflist)
     337              : 
     338              : /**
     339              :  * @brief Peek the next node from current node, node is not NULL
     340              :  *
     341              :  * Faster then sys_sflist_peek_next() if node is known not to be NULL.
     342              :  *
     343              :  * @param node A pointer on the node where to peek the next node
     344              :  *
     345              :  * @return a pointer on the next node (or NULL if none)
     346              :  */
     347              : static inline sys_sfnode_t *sys_sflist_peek_next_no_check(const sys_sfnode_t *node);
     348              : 
     349            1 : Z_GENLIST_PEEK_NEXT_NO_CHECK(sflist, sfnode)
     350              : 
     351              : /**
     352              :  * @brief Peek the next node from current node
     353              :  *
     354              :  * @param node A pointer on the node where to peek the next node
     355              :  *
     356              :  * @return a pointer on the next node (or NULL if none)
     357              :  */
     358              : static inline sys_sfnode_t *sys_sflist_peek_next(const sys_sfnode_t *node);
     359              : 
     360            1 : Z_GENLIST_PEEK_NEXT(sflist, sfnode)
     361              : 
     362              : /**
     363              :  * @brief Prepend a node to the given list
     364              :  *
     365              :  * This and other sys_sflist_*() functions are not thread safe.
     366              :  *
     367              :  * @param list A pointer on the list to affect
     368              :  * @param node A pointer on the node to prepend
     369              :  */
     370              : static inline void sys_sflist_prepend(sys_sflist_t *list,
     371              :                                       sys_sfnode_t *node);
     372              : 
     373            1 : Z_GENLIST_PREPEND(sflist, sfnode)
     374              : 
     375              : /**
     376              :  * @brief Append a node to the given list
     377              :  *
     378              :  * This and other sys_sflist_*() functions are not thread safe.
     379              :  *
     380              :  * @param list A pointer on the list to affect
     381              :  * @param node A pointer on the node to append
     382              :  */
     383              : static inline void sys_sflist_append(sys_sflist_t *list,
     384              :                                      sys_sfnode_t *node);
     385              : 
     386            1 : Z_GENLIST_APPEND(sflist, sfnode)
     387              : 
     388              : /**
     389              :  * @brief Append a list to the given list
     390              :  *
     391              :  * Append a singly-linked, NULL-terminated list consisting of nodes containing
     392              :  * the pointer to the next node as the first element of a node, to @a list.
     393              :  * This and other sys_sflist_*() functions are not thread safe.
     394              :  *
     395              :  * @param list A pointer on the list to affect
     396              :  * @param head A pointer to the first element of the list to append
     397              :  * @param tail A pointer to the last element of the list to append
     398              :  */
     399              : static inline void sys_sflist_append_list(sys_sflist_t *list,
     400              :                                           void *head, void *tail);
     401              : 
     402            1 : Z_GENLIST_APPEND_LIST(sflist, sfnode)
     403              : 
     404              : /**
     405              :  * @brief merge two sflists, appending the second one to the first
     406              :  *
     407              :  * When the operation is completed, the appending list is empty.
     408              :  * This and other sys_sflist_*() functions are not thread safe.
     409              :  *
     410              :  * @param list A pointer on the list to affect
     411              :  * @param list_to_append A pointer to the list to append.
     412              :  */
     413              : static inline void sys_sflist_merge_sflist(sys_sflist_t *list,
     414              :                                            sys_sflist_t *list_to_append);
     415              : 
     416            1 : Z_GENLIST_MERGE_LIST(sflist, sfnode)
     417              : 
     418              : /**
     419              :  * @brief Insert a node to the given list
     420              :  *
     421              :  * This and other sys_sflist_*() functions are not thread safe.
     422              :  *
     423              :  * @param list A pointer on the list to affect
     424              :  * @param prev A pointer on the previous node
     425              :  * @param node A pointer on the node to insert
     426              :  */
     427              : static inline void sys_sflist_insert(sys_sflist_t *list,
     428              :                                      sys_sfnode_t *prev,
     429              :                                      sys_sfnode_t *node);
     430              : 
     431            1 : Z_GENLIST_INSERT(sflist, sfnode)
     432              : 
     433              : /**
     434              :  * @brief Fetch and remove the first node of the given list
     435              :  *
     436              :  * List must be known to be non-empty.
     437              :  * This and other sys_sflist_*() functions are not thread safe.
     438              :  *
     439              :  * @param list A pointer on the list to affect
     440              :  *
     441              :  * @return A pointer to the first node of the list
     442              :  */
     443              : static inline sys_sfnode_t *sys_sflist_get_not_empty(sys_sflist_t *list);
     444              : 
     445            1 : Z_GENLIST_GET_NOT_EMPTY(sflist, sfnode)
     446              : 
     447              : /**
     448              :  * @brief Fetch and remove the first node of the given list
     449              :  *
     450              :  * This and other sys_sflist_*() functions are not thread safe.
     451              :  *
     452              :  * @param list A pointer on the list to affect
     453              :  *
     454              :  * @return A pointer to the first node of the list (or NULL if empty)
     455              :  */
     456              : static inline sys_sfnode_t *sys_sflist_get(sys_sflist_t *list);
     457              : 
     458            1 : Z_GENLIST_GET(sflist, sfnode)
     459              : 
     460              : /**
     461              :  * @brief Remove a node
     462              :  *
     463              :  * This and other sys_sflist_*() functions are not thread safe.
     464              :  *
     465              :  * @param list A pointer on the list to affect
     466              :  * @param prev_node A pointer on the previous node
     467              :  *        (can be NULL, which means the node is the list's head)
     468              :  * @param node A pointer on the node to remove
     469              :  */
     470              : static inline void sys_sflist_remove(sys_sflist_t *list,
     471              :                                      sys_sfnode_t *prev_node,
     472              :                                      sys_sfnode_t *node);
     473              : 
     474            1 : Z_GENLIST_REMOVE(sflist, sfnode)
     475              : 
     476              : /**
     477              :  * @brief Find and remove a node from a list
     478              :  *
     479              :  * This and other sys_sflist_*() functions are not thread safe.
     480              :  *
     481              :  * @param list A pointer on the list to affect
     482              :  * @param node A pointer on the node to remove from the list
     483              :  *
     484              :  * @return true if node was removed
     485              :  */
     486              : static inline bool sys_sflist_find_and_remove(sys_sflist_t *list,
     487              :                                               sys_sfnode_t *node);
     488              : 
     489            1 : Z_GENLIST_FIND_AND_REMOVE(sflist, sfnode)
     490              : 
     491              : /**
     492              :  * @brief Compute the size of the given list in O(n) time
     493              :  *
     494              :  * @param list A pointer on the list
     495              :  *
     496              :  * @return an integer equal to the size of the list, or 0 if empty
     497              :  */
     498              : static inline size_t sys_sflist_len(const sys_sflist_t *list);
     499              : 
     500            1 : Z_GENLIST_LEN(sflist, sfnode)
     501              : 
     502              : /** @} */
     503              : 
     504              : #ifdef __cplusplus
     505              : }
     506              : #endif
     507              : 
     508              : #endif /* ZEPHYR_INCLUDE_SYS_SFLIST_H_ */
        

Generated by: LCOV version 2.0-1