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