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(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(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(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(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(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(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(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(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 : * FIXME: Why are the element parameters void *?
396 : *
397 : * @param list A pointer on the list to affect
398 : * @param head A pointer to the first element of the list to append
399 : * @param tail A pointer to the last element of the list to append
400 : */
401 : static inline void sys_sflist_append_list(sys_sflist_t *list,
402 : void *head, void *tail);
403 :
404 1 : Z_GENLIST_APPEND_LIST(sflist, sfnode)
405 :
406 : /**
407 : * @brief merge two sflists, appending the second one to the first
408 : *
409 : * When the operation is completed, the appending list is empty.
410 : * This and other sys_sflist_*() functions are not thread safe.
411 : *
412 : * @param list A pointer on the list to affect
413 : * @param list_to_append A pointer to the list to append.
414 : */
415 : static inline void sys_sflist_merge_sflist(sys_sflist_t *list,
416 : sys_sflist_t *list_to_append);
417 :
418 1 : Z_GENLIST_MERGE_LIST(sflist, sfnode)
419 :
420 : /**
421 : * @brief Insert a node to the given list
422 : *
423 : * This and other sys_sflist_*() functions are not thread safe.
424 : *
425 : * @param list A pointer on the list to affect
426 : * @param prev A pointer on the previous node
427 : * @param node A pointer on the node to insert
428 : */
429 : static inline void sys_sflist_insert(sys_sflist_t *list,
430 : sys_sfnode_t *prev,
431 : sys_sfnode_t *node);
432 :
433 1 : Z_GENLIST_INSERT(sflist, sfnode)
434 :
435 : /**
436 : * @brief Fetch and remove the first node of the given list
437 : *
438 : * List must be known to be non-empty.
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
444 : */
445 : static inline sys_sfnode_t *sys_sflist_get_not_empty(sys_sflist_t *list);
446 :
447 1 : Z_GENLIST_GET_NOT_EMPTY(sflist, sfnode)
448 :
449 : /**
450 : * @brief Fetch and remove the first node of the given list
451 : *
452 : * This and other sys_sflist_*() functions are not thread safe.
453 : *
454 : * @param list A pointer on the list to affect
455 : *
456 : * @return A pointer to the first node of the list (or NULL if empty)
457 : */
458 : static inline sys_sfnode_t *sys_sflist_get(sys_sflist_t *list);
459 :
460 1 : Z_GENLIST_GET(sflist, sfnode)
461 :
462 : /**
463 : * @brief Remove a node
464 : *
465 : * This and other sys_sflist_*() functions are not thread safe.
466 : *
467 : * @param list A pointer on the list to affect
468 : * @param prev_node A pointer on the previous node
469 : * (can be NULL, which means the node is the list's head)
470 : * @param node A pointer on the node to remove
471 : */
472 : static inline void sys_sflist_remove(sys_sflist_t *list,
473 : sys_sfnode_t *prev_node,
474 : sys_sfnode_t *node);
475 :
476 1 : Z_GENLIST_REMOVE(sflist, sfnode)
477 :
478 : /**
479 : * @brief Find and remove a node from a list
480 : *
481 : * This and other sys_sflist_*() functions are not thread safe.
482 : *
483 : * @param list A pointer on the list to affect
484 : * @param node A pointer on the node to remove from the list
485 : *
486 : * @return true if node was removed
487 : */
488 : static inline bool sys_sflist_find_and_remove(sys_sflist_t *list,
489 : sys_sfnode_t *node);
490 :
491 1 : Z_GENLIST_FIND_AND_REMOVE(sflist, sfnode)
492 :
493 : /**
494 : * @brief Compute the size of the given list in O(n) time
495 : *
496 : * @param list A pointer on the list
497 : *
498 : * @return an integer equal to the size of the list, or 0 if empty
499 : */
500 : static inline size_t sys_sflist_len(sys_sflist_t *list);
501 :
502 1 : Z_GENLIST_LEN(sflist, sfnode)
503 :
504 : /** @} */
505 :
506 : #ifdef __cplusplus
507 : }
508 : #endif
509 :
510 : #endif /* ZEPHYR_INCLUDE_SYS_SFLIST_H_ */
|
