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