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 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 1 : 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 1 : 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 1 : #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 1 : #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 1 : #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 1 : #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 1 : #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 1 : #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 1 : #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 1 : #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 1 : #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 : */
199 1 : 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 1 : #define SYS_SLIST_STATIC_INIT(ptr_to_list) {NULL, NULL}
210 :
211 : static inline sys_snode_t *z_snode_next_peek(const sys_snode_t *node)
212 : {
213 : return node->next;
214 : }
215 :
216 : static inline void z_snode_next_set(sys_snode_t *parent, sys_snode_t *child)
217 : {
218 : parent->next = child;
219 : }
220 :
221 : static inline void z_slist_head_set(sys_slist_t *list, sys_snode_t *node)
222 : {
223 : list->head = node;
224 : }
225 :
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 : */
238 1 : static inline sys_snode_t *sys_slist_peek_head(const 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 : */
250 1 : static inline sys_snode_t *sys_slist_peek_tail(const 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(const sys_slist_t *list);
267 :
268 1 : 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(const sys_snode_t *node);
280 :
281 1 : 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(const sys_snode_t *node);
291 :
292 1 : 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 1 : 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 1 : 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 : * @param list A pointer on the list to affect
328 : * @param head A pointer to the first element of the list to append
329 : * @param tail A pointer to the last element of the list to append
330 : */
331 : static inline void sys_slist_append_list(sys_slist_t *list,
332 : void *head, void *tail);
333 :
334 1 : Z_GENLIST_APPEND_LIST(slist, snode)
335 :
336 : /**
337 : * @brief merge two slists, appending the second one to the first
338 : *
339 : * When the operation is completed, the appending list is empty.
340 : * This and other sys_slist_*() functions are not thread safe.
341 : *
342 : * @param list A pointer on the list to affect
343 : * @param list_to_append A pointer to the list to append.
344 : */
345 : static inline void sys_slist_merge_slist(sys_slist_t *list,
346 : sys_slist_t *list_to_append);
347 :
348 1 : Z_GENLIST_MERGE_LIST(slist, snode)
349 :
350 : /**
351 : * @brief Insert a node to the given list
352 : *
353 : * This and other sys_slist_*() functions are not thread safe.
354 : *
355 : * @param list A pointer on the list to affect
356 : * @param prev A pointer on the previous node
357 : * @param node A pointer on the node to insert
358 : */
359 : static inline void sys_slist_insert(sys_slist_t *list,
360 : sys_snode_t *prev,
361 : sys_snode_t *node);
362 :
363 1 : Z_GENLIST_INSERT(slist, snode)
364 :
365 : /**
366 : * @brief Fetch and remove the first node of the given list
367 : *
368 : * List must be known to be non-empty.
369 : * This and other sys_slist_*() functions are not thread safe.
370 : *
371 : * @param list A pointer on the list to affect
372 : *
373 : * @return A pointer to the first node of the list
374 : */
375 : static inline sys_snode_t *sys_slist_get_not_empty(sys_slist_t *list);
376 :
377 1 : Z_GENLIST_GET_NOT_EMPTY(slist, snode)
378 :
379 : /**
380 : * @brief Fetch and remove the first node of the given list
381 : *
382 : * This and other sys_slist_*() functions are not thread safe.
383 : *
384 : * @param list A pointer on the list to affect
385 : *
386 : * @return A pointer to the first node of the list (or NULL if empty)
387 : */
388 : static inline sys_snode_t *sys_slist_get(sys_slist_t *list);
389 :
390 1 : Z_GENLIST_GET(slist, snode)
391 :
392 : /**
393 : * @brief Remove a node
394 : *
395 : * This and other sys_slist_*() functions are not thread safe.
396 : *
397 : * @param list A pointer on the list to affect
398 : * @param prev_node A pointer on the previous node
399 : * (can be NULL, which means the node is the list's head)
400 : * @param node A pointer on the node to remove
401 : */
402 : static inline void sys_slist_remove(sys_slist_t *list,
403 : sys_snode_t *prev_node,
404 : sys_snode_t *node);
405 :
406 1 : Z_GENLIST_REMOVE(slist, snode)
407 :
408 : /**
409 : * @brief Find and remove a node from a list
410 : *
411 : * This and other sys_slist_*() functions are not thread safe.
412 : *
413 : * @param list A pointer on the list to affect
414 : * @param node A pointer on the node to remove from the list
415 : *
416 : * @return true if node was removed
417 : */
418 : static inline bool sys_slist_find_and_remove(sys_slist_t *list,
419 : sys_snode_t *node);
420 :
421 : /**
422 : * @brief Find if a node is already linked in a singly linked list
423 : *
424 : * This and other sys_slist_*() functions are not thread safe.
425 : *
426 : * @param list A pointer to the list to check
427 : * @param node A pointer to the node to search in the list
428 : * @param[out] prev A pointer to the previous node
429 : *
430 : * @return true if node was found in the list, false otherwise
431 : */
432 : static inline bool sys_slist_find(const sys_slist_t *list, const sys_snode_t *node,
433 : sys_snode_t **prev);
434 1 : Z_GENLIST_FIND(slist, snode)
435 :
436 : /**
437 : * @brief Compute the size of the given list in O(n) time
438 : *
439 : * @param list A pointer on the list
440 : *
441 : * @return an integer equal to the size of the list, or 0 if empty
442 : */
443 : static inline size_t sys_slist_len(const sys_slist_t *list);
444 :
445 1 : Z_GENLIST_LEN(slist, snode)
446 :
447 : /** @} */
448 1 : Z_GENLIST_FIND_AND_REMOVE(slist, snode)
449 :
450 : #ifdef __cplusplus
451 : }
452 : #endif
453 :
454 : #endif /* ZEPHYR_INCLUDE_SYS_SLIST_H_ */
|
