1 /*
2  * Copyright (c) 2016 Intel Corporation
3  *
4  * SPDX-License-Identifier: Apache-2.0
5  */
6 
7  /**
8   * @file
9   * @defgroup single-linked-list_apis Single-linked list
10   * @ingroup datastructure_apis
11   *
12   * @brief Single-linked list implementation.
13   *
14   * Single-linked list implementation using inline macros/functions.
15   * This API is not thread safe, and thus if a list is used across threads,
16   * calls to functions must be protected with synchronization primitives.
17   * @{
18   */
19 
20 #ifndef ZEPHYR_INCLUDE_SYS_SLIST_H_
21 #define ZEPHYR_INCLUDE_SYS_SLIST_H_
22 
23 #include <stddef.h>
24 #include <stdbool.h>
25 #include "list_gen.h"
26 
27 #ifdef __cplusplus
28 extern "C" {
29 #endif
30 
31 
32 /** @cond INTERNAL_HIDDEN */
33 struct _snode {
34 	struct _snode *next;
35 };
36 /** @endcond */
37 
38 /** Single-linked list node structure. */
39 typedef struct _snode sys_snode_t;
40 
41 /** @cond INTERNAL_HIDDEN */
42 struct _slist {
43 	sys_snode_t *head;
44 	sys_snode_t *tail;
45 };
46 /** @endcond */
47 
48 /** Single-linked list structure. */
49 typedef struct _slist sys_slist_t;
50 
51 /**
52  * @brief Provide the primitive to iterate on a list
53  * Note: the loop is unsafe and thus __sn should not be removed
54  *
55  * User _MUST_ add the loop statement curly braces enclosing its own code:
56  *
57  *     SYS_SLIST_FOR_EACH_NODE(l, n) {
58  *         <user code>
59  *     }
60  *
61  * This and other SYS_SLIST_*() macros are not thread safe.
62  *
63  * @param __sl A pointer on a sys_slist_t to iterate on
64  * @param __sn A sys_snode_t pointer to peek each node of the list
65  */
66 #define SYS_SLIST_FOR_EACH_NODE(__sl, __sn)				\
67 	Z_GENLIST_FOR_EACH_NODE(slist, __sl, __sn)
68 
69 /**
70  * @brief Provide the primitive to iterate on a list, from a node in the list
71  * Note: the loop is unsafe and thus __sn should not be removed
72  *
73  * User _MUST_ add the loop statement curly braces enclosing its own code:
74  *
75  *     SYS_SLIST_ITERATE_FROM_NODE(l, n) {
76  *         <user code>
77  *     }
78  *
79  * Like SYS_SLIST_FOR_EACH_NODE(), but __dn already contains a node in the list
80  * where to start searching for the next entry from. If NULL, it starts from
81  * the head.
82  *
83  * This and other SYS_SLIST_*() macros are not thread safe.
84  *
85  * @param __sl A pointer on a sys_slist_t to iterate on
86  * @param __sn A sys_snode_t pointer to peek each node of the list
87  *             it contains the starting node, or NULL to start from the head
88  */
89 #define SYS_SLIST_ITERATE_FROM_NODE(__sl, __sn)				\
90 	Z_GENLIST_ITERATE_FROM_NODE(slist, __sl, __sn)
91 
92 /**
93  * @brief Provide the primitive to safely iterate on a list
94  * Note: __sn can be removed, it will not break the loop.
95  *
96  * User _MUST_ add the loop statement curly braces enclosing its own code:
97  *
98  *     SYS_SLIST_FOR_EACH_NODE_SAFE(l, n, s) {
99  *         <user code>
100  *     }
101  *
102  * This and other SYS_SLIST_*() macros are not thread safe.
103  *
104  * @param __sl A pointer on a sys_slist_t to iterate on
105  * @param __sn A sys_snode_t pointer to peek each node of the list
106  * @param __sns A sys_snode_t pointer for the loop to run safely
107  */
108 #define SYS_SLIST_FOR_EACH_NODE_SAFE(__sl, __sn, __sns)			\
109 	Z_GENLIST_FOR_EACH_NODE_SAFE(slist, __sl, __sn, __sns)
110 
111 /**
112  * @brief Provide the primitive to resolve the container of a list node
113  * Note: it is safe to use with NULL pointer nodes
114  *
115  * @param __ln A pointer on a sys_node_t to get its container
116  * @param __cn Container struct type pointer
117  * @param __n The field name of sys_node_t within the container struct
118  */
119 #define SYS_SLIST_CONTAINER(__ln, __cn, __n) \
120 	Z_GENLIST_CONTAINER(__ln, __cn, __n)
121 
122 /**
123  * @brief Provide the primitive to peek container of the list head
124  *
125  * @param __sl A pointer on a sys_slist_t to peek
126  * @param __cn Container struct type pointer
127  * @param __n The field name of sys_node_t within the container struct
128  */
129 #define SYS_SLIST_PEEK_HEAD_CONTAINER(__sl, __cn, __n) \
130 	Z_GENLIST_PEEK_HEAD_CONTAINER(slist, __sl, __cn, __n)
131 
132 /**
133  * @brief Provide the primitive to peek container of the list tail
134  *
135  * @param __sl A pointer on a sys_slist_t to peek
136  * @param __cn Container struct type pointer
137  * @param __n The field name of sys_node_t within the container struct
138  */
139 #define SYS_SLIST_PEEK_TAIL_CONTAINER(__sl, __cn, __n) \
140 	Z_GENLIST_PEEK_TAIL_CONTAINER(slist, __sl, __cn, __n)
141 
142 /**
143  * @brief Provide the primitive to peek the next container
144  *
145  * @param __cn Container struct type pointer
146  * @param __n The field name of sys_node_t within the container struct
147  */
148 #define SYS_SLIST_PEEK_NEXT_CONTAINER(__cn, __n) \
149 	Z_GENLIST_PEEK_NEXT_CONTAINER(slist, __cn, __n)
150 
151 /**
152  * @brief Provide the primitive to iterate on a list under a container
153  * Note: the loop is unsafe and thus __cn should not be detached
154  *
155  * User _MUST_ add the loop statement curly braces enclosing its own code:
156  *
157  *     SYS_SLIST_FOR_EACH_CONTAINER(l, c, n) {
158  *         <user code>
159  *     }
160  *
161  * @param __sl A pointer on a sys_slist_t to iterate on
162  * @param __cn A pointer to peek each entry of the list
163  * @param __n The field name of sys_node_t within the container struct
164  */
165 #define SYS_SLIST_FOR_EACH_CONTAINER(__sl, __cn, __n)			\
166 	Z_GENLIST_FOR_EACH_CONTAINER(slist, __sl, __cn, __n)
167 
168 /**
169  * @brief Provide the primitive to safely iterate on a list under a container
170  * Note: __cn can be detached, it will not break the loop.
171  *
172  * User _MUST_ add the loop statement curly braces enclosing its own code:
173  *
174  *     SYS_SLIST_FOR_EACH_NODE_SAFE(l, c, cn, n) {
175  *         <user code>
176  *     }
177  *
178  * @param __sl A pointer on a sys_slist_t to iterate on
179  * @param __cn A pointer to peek each entry of the list
180  * @param __cns A pointer for the loop to run safely
181  * @param __n The field name of sys_node_t within the container struct
182  */
183 #define SYS_SLIST_FOR_EACH_CONTAINER_SAFE(__sl, __cn, __cns, __n)	\
184 	Z_GENLIST_FOR_EACH_CONTAINER_SAFE(slist, __sl, __cn, __cns, __n)
185 
186 
187 /*
188  * Required function definitions for the list_gen.h interface
189  *
190  * These are the only functions that do not treat the list/node pointers
191  * as completely opaque types.
192  */
193 
194 /**
195  * @brief Initialize a list
196  *
197  * @param list A pointer on the list to initialize
198  */
sys_slist_init(sys_slist_t * list)199 static inline void sys_slist_init(sys_slist_t *list)
200 {
201 	list->head = NULL;
202 	list->tail = NULL;
203 }
204 
205 /**
206  * @brief Statically initialize a single-linked list
207  * @param ptr_to_list A pointer on the list to initialize
208  */
209 #define SYS_SLIST_STATIC_INIT(ptr_to_list) {NULL, NULL}
210 
z_snode_next_peek(sys_snode_t * node)211 static inline sys_snode_t *z_snode_next_peek(sys_snode_t *node)
212 {
213 	return node->next;
214 }
215 
z_snode_next_set(sys_snode_t * parent,sys_snode_t * child)216 static inline void z_snode_next_set(sys_snode_t *parent, sys_snode_t *child)
217 {
218 	parent->next = child;
219 }
220 
z_slist_head_set(sys_slist_t * list,sys_snode_t * node)221 static inline void z_slist_head_set(sys_slist_t *list, sys_snode_t *node)
222 {
223 	list->head = node;
224 }
225 
z_slist_tail_set(sys_slist_t * list,sys_snode_t * node)226 static inline void z_slist_tail_set(sys_slist_t *list, sys_snode_t *node)
227 {
228 	list->tail = node;
229 }
230 
231 /**
232  * @brief Peek the first node from the list
233  *
234  * @param list A point on the list to peek the first node from
235  *
236  * @return A pointer on the first node of the list (or NULL if none)
237  */
sys_slist_peek_head(sys_slist_t * list)238 static inline sys_snode_t *sys_slist_peek_head(sys_slist_t *list)
239 {
240 	return list->head;
241 }
242 
243 /**
244  * @brief Peek the last node from the list
245  *
246  * @param list A point on the list to peek the last node from
247  *
248  * @return A pointer on the last node of the list (or NULL if none)
249  */
sys_slist_peek_tail(sys_slist_t * list)250 static inline sys_snode_t *sys_slist_peek_tail(sys_slist_t *list)
251 {
252 	return list->tail;
253 }
254 
255 /*
256  * Derived, generated APIs
257  */
258 
259 /**
260  * @brief Test if the given list is empty
261  *
262  * @param list A pointer on the list to test
263  *
264  * @return a boolean, true if it's empty, false otherwise
265  */
266 static inline bool sys_slist_is_empty(sys_slist_t *list);
267 
268 Z_GENLIST_IS_EMPTY(slist)
269 
270 /**
271  * @brief Peek the next node from current node, node is not NULL
272  *
273  * Faster then sys_slist_peek_next() if node is known not to be NULL.
274  *
275  * @param node A pointer on the node where to peek the next node
276  *
277  * @return a pointer on the next node (or NULL if none)
278  */
279 static inline sys_snode_t *sys_slist_peek_next_no_check(sys_snode_t *node);
280 
281 Z_GENLIST_PEEK_NEXT_NO_CHECK(slist, snode)
282 
283 /**
284  * @brief Peek the next node from current node
285  *
286  * @param node A pointer on the node where to peek the next node
287  *
288  * @return a pointer on the next node (or NULL if none)
289  */
290 static inline sys_snode_t *sys_slist_peek_next(sys_snode_t *node);
291 
292 Z_GENLIST_PEEK_NEXT(slist, snode)
293 
294 /**
295  * @brief Prepend a node to the given list
296  *
297  * This and other sys_slist_*() functions are not thread safe.
298  *
299  * @param list A pointer on the list to affect
300  * @param node A pointer on the node to prepend
301  */
302 static inline void sys_slist_prepend(sys_slist_t *list,
303 				     sys_snode_t *node);
304 
305 Z_GENLIST_PREPEND(slist, snode)
306 
307 /**
308  * @brief Append a node to the given list
309  *
310  * This and other sys_slist_*() functions are not thread safe.
311  *
312  * @param list A pointer on the list to affect
313  * @param node A pointer on the node to append
314  */
315 static inline void sys_slist_append(sys_slist_t *list,
316 				    sys_snode_t *node);
317 
318 Z_GENLIST_APPEND(slist, snode)
319 
320 /**
321  * @brief Append a list to the given list
322  *
323  * Append a singly-linked, NULL-terminated list consisting of nodes containing
324  * the pointer to the next node as the first element of a node, to @a list.
325  * This and other sys_slist_*() functions are not thread safe.
326  *
327  * FIXME: Why are the element parameters void *?
328  *
329  * @param list A pointer on the list to affect
330  * @param head A pointer to the first element of the list to append
331  * @param tail A pointer to the last element of the list to append
332  */
333 static inline void sys_slist_append_list(sys_slist_t *list,
334 					 void *head, void *tail);
335 
336 Z_GENLIST_APPEND_LIST(slist, snode)
337 
338 /**
339  * @brief merge two slists, appending the second one to the first
340  *
341  * When the operation is completed, the appending list is empty.
342  * This and other sys_slist_*() functions are not thread safe.
343  *
344  * @param list A pointer on the list to affect
345  * @param list_to_append A pointer to the list to append.
346  */
347 static inline void sys_slist_merge_slist(sys_slist_t *list,
348 					 sys_slist_t *list_to_append);
349 
350 Z_GENLIST_MERGE_LIST(slist, snode)
351 
352 /**
353  * @brief Insert a node to the given list
354  *
355  * This and other sys_slist_*() functions are not thread safe.
356  *
357  * @param list A pointer on the list to affect
358  * @param prev A pointer on the previous node
359  * @param node A pointer on the node to insert
360  */
361 static inline void sys_slist_insert(sys_slist_t *list,
362 				    sys_snode_t *prev,
363 				    sys_snode_t *node);
364 
365 Z_GENLIST_INSERT(slist, snode)
366 
367 /**
368  * @brief Fetch and remove the first node of the given list
369  *
370  * List must be known to be non-empty.
371  * This and other sys_slist_*() functions are not thread safe.
372  *
373  * @param list A pointer on the list to affect
374  *
375  * @return A pointer to the first node of the list
376  */
377 static inline sys_snode_t *sys_slist_get_not_empty(sys_slist_t *list);
378 
379 Z_GENLIST_GET_NOT_EMPTY(slist, snode)
380 
381 /**
382  * @brief Fetch and remove the first node of the given list
383  *
384  * This and other sys_slist_*() functions are not thread safe.
385  *
386  * @param list A pointer on the list to affect
387  *
388  * @return A pointer to the first node of the list (or NULL if empty)
389  */
390 static inline sys_snode_t *sys_slist_get(sys_slist_t *list);
391 
392 Z_GENLIST_GET(slist, snode)
393 
394 /**
395  * @brief Remove a node
396  *
397  * This and other sys_slist_*() functions are not thread safe.
398  *
399  * @param list A pointer on the list to affect
400  * @param prev_node A pointer on the previous node
401  *        (can be NULL, which means the node is the list's head)
402  * @param node A pointer on the node to remove
403  */
404 static inline void sys_slist_remove(sys_slist_t *list,
405 				    sys_snode_t *prev_node,
406 				    sys_snode_t *node);
407 
408 Z_GENLIST_REMOVE(slist, snode)
409 
410 /**
411  * @brief Find and remove a node from a list
412  *
413  * This and other sys_slist_*() functions are not thread safe.
414  *
415  * @param list A pointer on the list to affect
416  * @param node A pointer on the node to remove from the list
417  *
418  * @return true if node was removed
419  */
420 static inline bool sys_slist_find_and_remove(sys_slist_t *list,
421 					     sys_snode_t *node);
422 
423 /**
424  * @brief Compute the size of the given list in O(n) time
425  *
426  * @param list A pointer on the list
427  *
428  * @return an integer equal to the size of the list, or 0 if empty
429  */
430 static inline size_t sys_slist_len(sys_slist_t *list);
431 
432 Z_GENLIST_LEN(slist, snode)
433 
434 /** @} */
435 Z_GENLIST_FIND_AND_REMOVE(slist, snode)
436 
437 #ifdef __cplusplus
438 }
439 #endif
440 
441 #endif /* ZEPHYR_INCLUDE_SYS_SLIST_H_ */
442