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 __SLIST_H__
18 #define __SLIST_H__
19
20 #include <stddef.h>
21 #include <stdbool.h>
22
23 #ifdef __cplusplus
24 extern "C" {
25 #endif
26
27 struct _snode {
28 struct _snode *next;
29 };
30
31 typedef struct _snode sys_snode_t;
32
33 struct _slist {
34 sys_snode_t *head;
35 sys_snode_t *tail;
36 };
37
38 typedef struct _slist sys_slist_t;
39
40 /**
41 * @brief Provide the primitive to iterate on a list
42 * Note: the loop is unsafe and thus __sn should not be removed
43 *
44 * User _MUST_ add the loop statement curly braces enclosing its own code:
45 *
46 * SYS_SLIST_FOR_EACH_NODE(l, n) {
47 * <user code>
48 * }
49 *
50 * This and other SYS_SLIST_*() macros are not thread safe.
51 *
52 * @param __sl A pointer on a sys_slist_t to iterate on
53 * @param __sn A sys_snode_t pointer to peek each node of the list
54 */
55 #define SYS_SLIST_FOR_EACH_NODE(__sl, __sn) \
56 for ((__sn) = sys_slist_peek_head(__sl); (__sn); \
57 (__sn) = sys_slist_peek_next(__sn))
58
59 /**
60 * @brief Provide the primitive to iterate on a list, from a node in the list
61 * Note: the loop is unsafe and thus __sn should not be removed
62 *
63 * User _MUST_ add the loop statement curly braces enclosing its own code:
64 *
65 * SYS_SLIST_ITERATE_FROM_NODE(l, n) {
66 * <user code>
67 * }
68 *
69 * Like SYS_SLIST_FOR_EACH_NODE(), but __dn already contains a node in the list
70 * where to start searching for the next entry from. If NULL, it starts from
71 * the head.
72 *
73 * This and other SYS_SLIST_*() macros are not thread safe.
74 *
75 * @param __sl A pointer on a sys_slist_t to iterate on
76 * @param __sn A sys_snode_t pointer to peek each node of the list
77 * it contains the starting node, or NULL to start from the head
78 */
79 #define SYS_SLIST_ITERATE_FROM_NODE(__sl, __sn) \
80 for ((__sn) = (__sn) ? sys_slist_peek_next_no_check(__sn) \
81 : sys_slist_peek_head(__sl); \
82 (__sn); \
83 (__sn) = sys_slist_peek_next(__sn))
84
85 /**
86 * @brief Provide the primitive to safely iterate on a list
87 * Note: __sn can be removed, it will not break the loop.
88 *
89 * User _MUST_ add the loop statement curly braces enclosing its own code:
90 *
91 * SYS_SLIST_FOR_EACH_NODE_SAFE(l, n, s) {
92 * <user code>
93 * }
94 *
95 * This and other SYS_SLIST_*() macros are not thread safe.
96 *
97 * @param __sl A pointer on a sys_slist_t to iterate on
98 * @param __sn A sys_snode_t pointer to peek each node of the list
99 * @param __sns A sys_snode_t pointer for the loop to run safely
100 */
101 #define SYS_SLIST_FOR_EACH_NODE_SAFE(__sl, __sn, __sns) \
102 for ((__sn) = sys_slist_peek_head(__sl), \
103 (__sns) = sys_slist_peek_next(__sn); \
104 (__sn); (__sn) = (__sns), \
105 (__sns) = sys_slist_peek_next(__sn))
106
107 /*
108 * @brief Provide the primitive to resolve the container of a list node
109 * Note: it is safe to use with NULL pointer nodes
110 *
111 * @param __ln A pointer on a sys_node_t to get its container
112 * @param __cn Container struct type pointer
113 * @param __n The field name of sys_node_t within the container struct
114 */
115 #define SYS_SLIST_CONTAINER(__ln, __cn, __n) \
116 ((__ln) ? CONTAINER_OF((__ln), __typeof__(*(__cn)), __n) : NULL)
117 /*
118 * @brief Provide the primitive to peek container of the list head
119 *
120 * @param __sl A pointer on a sys_slist_t to peek
121 * @param __cn Container struct type pointer
122 * @param __n The field name of sys_node_t within the container struct
123 */
124 #define SYS_SLIST_PEEK_HEAD_CONTAINER(__sl, __cn, __n) \
125 SYS_SLIST_CONTAINER(sys_slist_peek_head(__sl), __cn, __n)
126
127 /*
128 * @brief Provide the primitive to peek container of the list tail
129 *
130 * @param __sl A pointer on a sys_slist_t to peek
131 * @param __cn Container struct type pointer
132 * @param __n The field name of sys_node_t within the container struct
133 */
134 #define SYS_SLIST_PEEK_TAIL_CONTAINER(__sl, __cn, __n) \
135 SYS_SLIST_CONTAINER(sys_slist_peek_tail(__sl), __cn, __n)
136
137 /*
138 * @brief Provide the primitive to peek the next container
139 *
140 * @param __cn Container struct type pointer
141 * @param __n The field name of sys_node_t within the container struct
142 */
143
144 #define SYS_SLIST_PEEK_NEXT_CONTAINER(__cn, __n) \
145 ((__cn) ? SYS_SLIST_CONTAINER(sys_slist_peek_next(&((__cn)->__n)), \
146 __cn, __n) : NULL)
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 for ((__cn) = SYS_SLIST_PEEK_HEAD_CONTAINER(__sl, __cn, __n); (__cn); \
164 (__cn) = SYS_SLIST_PEEK_NEXT_CONTAINER(__cn, __n))
165
166 /**
167 * @brief Provide the primitive to safely iterate on a list under a container
168 * Note: __cn can be detached, it will not break the loop.
169 *
170 * User _MUST_ add the loop statement curly braces enclosing its own code:
171 *
172 * SYS_SLIST_FOR_EACH_NODE_SAFE(l, c, cn, n) {
173 * <user code>
174 * }
175 *
176 * @param __sl A pointer on a sys_slist_t to iterate on
177 * @param __cn A pointer to peek each entry of the list
178 * @param __cns A pointer for the loop to run safely
179 * @param __n The field name of sys_node_t within the container struct
180 */
181 #define SYS_SLIST_FOR_EACH_CONTAINER_SAFE(__sl, __cn, __cns, __n) \
182 for ((__cn)= SYS_SLIST_PEEK_HEAD_CONTAINER(__sl, __cn, __n), \
183 (__cns) = SYS_SLIST_PEEK_NEXT_CONTAINER(__cn, __n); (__cn); \
184 (__cn)= (__cns), (__cns) = SYS_SLIST_PEEK_NEXT_CONTAINER(__cn, __n))
185
186 /**
187 * @brief Initialize a list
188 *
189 * @param list A pointer on the list to initialize
190 */
sys_slist_init(sys_slist_t * list)191 static inline void sys_slist_init(sys_slist_t *list)
192 {
193 list->head = NULL;
194 list->tail = NULL;
195 }
196
197 #define SYS_SLIST_STATIC_INIT(ptr_to_list) {NULL, NULL}
198
199 /**
200 * @brief Test if the given list is empty
201 *
202 * @param list A pointer on the list to test
203 *
204 * @return a boolean, true if it's empty, false otherwise
205 */
sys_slist_is_empty(sys_slist_t * list)206 static inline bool sys_slist_is_empty(sys_slist_t *list)
207 {
208 return (!list->head);
209 }
210
211 /**
212 * @brief Peek the first node from the list
213 *
214 * @param list A point on the list to peek the first node from
215 *
216 * @return A pointer on the first node of the list (or NULL if none)
217 */
sys_slist_peek_head(sys_slist_t * list)218 static inline sys_snode_t *sys_slist_peek_head(sys_slist_t *list)
219 {
220 return list->head;
221 }
222
223 /**
224 * @brief Peek the last node from the list
225 *
226 * @param list A point on the list to peek the last node from
227 *
228 * @return A pointer on the last node of the list (or NULL if none)
229 */
sys_slist_peek_tail(sys_slist_t * list)230 static inline sys_snode_t *sys_slist_peek_tail(sys_slist_t *list)
231 {
232 return list->tail;
233 }
234
235 /**
236 * @brief Peek the next node from current node, node is not NULL
237 *
238 * Faster then sys_slist_peek_next() if node is known not to be NULL.
239 *
240 * @param node A pointer on the node where to peek the next node
241 *
242 * @return a pointer on the next node (or NULL if none)
243 */
sys_slist_peek_next_no_check(sys_snode_t * node)244 static inline sys_snode_t *sys_slist_peek_next_no_check(sys_snode_t *node)
245 {
246 return node->next;
247 }
248
249 /**
250 * @brief Peek the next node from current node
251 *
252 * @param node A pointer on the node where to peek the next node
253 *
254 * @return a pointer on the next node (or NULL if none)
255 */
sys_slist_peek_next(sys_snode_t * node)256 static inline sys_snode_t *sys_slist_peek_next(sys_snode_t *node)
257 {
258 return node ? sys_slist_peek_next_no_check(node) : NULL;
259 }
260
261 /**
262 * @brief Prepend a node to the given list
263 *
264 * This and other sys_slist_*() functions are not thread safe.
265 *
266 * @param list A pointer on the list to affect
267 * @param node A pointer on the node to prepend
268 */
sys_slist_prepend(sys_slist_t * list,sys_snode_t * node)269 static inline void sys_slist_prepend(sys_slist_t *list,
270 sys_snode_t *node)
271 {
272 node->next = list->head;
273 list->head = node;
274
275 if (!list->tail) {
276 list->tail = list->head;
277 }
278 }
279
280 /**
281 * @brief Append a node to the given list
282 *
283 * This and other sys_slist_*() functions are not thread safe.
284 *
285 * @param list A pointer on the list to affect
286 * @param node A pointer on the node to append
287 */
sys_slist_append(sys_slist_t * list,sys_snode_t * node)288 static inline void sys_slist_append(sys_slist_t *list,
289 sys_snode_t *node)
290 {
291 node->next = NULL;
292
293 if (!list->tail) {
294 list->tail = node;
295 list->head = node;
296 } else {
297 list->tail->next = node;
298 list->tail = node;
299 }
300 }
301
302 /**
303 * @brief Append a list to the given list
304 *
305 * Append a singly-linked, NULL-terminated list consisting of nodes containing
306 * the pointer to the next node as the first element of a node, to @a list.
307 * This and other sys_slist_*() functions are not thread safe.
308 *
309 * @param list A pointer on the list to affect
310 * @param head A pointer to the first element of the list to append
311 * @param tail A pointer to the last element of the list to append
312 */
sys_slist_append_list(sys_slist_t * list,void * head,void * tail)313 static inline void sys_slist_append_list(sys_slist_t *list,
314 void *head, void *tail)
315 {
316 if (!list->tail) {
317 list->head = (sys_snode_t *)head;
318 list->tail = (sys_snode_t *)tail;
319 } else {
320 list->tail->next = (sys_snode_t *)head;
321 list->tail = (sys_snode_t *)tail;
322 }
323 }
324
325 /**
326 * @brief merge two slists, appending the second one to the first
327 *
328 * When the operation is completed, the appending list is empty.
329 * This and other sys_slist_*() functions are not thread safe.
330 *
331 * @param list A pointer on the list to affect
332 * @param list_to_append A pointer to the list to append.
333 */
sys_slist_merge_slist(sys_slist_t * list,sys_slist_t * list_to_append)334 static inline void sys_slist_merge_slist(sys_slist_t *list,
335 sys_slist_t *list_to_append)
336 {
337 sys_slist_append_list(list, list_to_append->head,
338 list_to_append->tail);
339 sys_slist_init(list_to_append);
340 }
341
342 /**
343 * @brief Insert a node to the given list
344 *
345 * This and other sys_slist_*() functions are not thread safe.
346 *
347 * @param list A pointer on the list to affect
348 * @param prev A pointer on the previous node
349 * @param node A pointer on the node to insert
350 */
sys_slist_insert(sys_slist_t * list,sys_snode_t * prev,sys_snode_t * node)351 static inline void sys_slist_insert(sys_slist_t *list,
352 sys_snode_t *prev,
353 sys_snode_t *node)
354 {
355 if (!prev) {
356 sys_slist_prepend(list, node);
357 } else if (!prev->next) {
358 sys_slist_append(list, node);
359 } else {
360 node->next = prev->next;
361 prev->next = node;
362 }
363 }
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 */
sys_slist_get_not_empty(sys_slist_t * list)375 static inline sys_snode_t *sys_slist_get_not_empty(sys_slist_t *list)
376 {
377 sys_snode_t *node = list->head;
378 list->head = node->next;
379
380 if (list->tail == node) {
381 list->tail = list->head;
382 }
383
384 return node;
385 }
386
387 /**
388 * @brief Fetch and remove the first node of the given list
389 *
390 * This and other sys_slist_*() functions are not thread safe.
391 *
392 * @param list A pointer on the list to affect
393 *
394 * @return A pointer to the first node of the list (or NULL if empty)
395 */
sys_slist_get(sys_slist_t * list)396 static inline sys_snode_t *sys_slist_get(sys_slist_t *list)
397 {
398 return sys_slist_is_empty(list) ? NULL : sys_slist_get_not_empty(list);
399 }
400
401 /**
402 * @brief Remove a node
403 *
404 * This and other sys_slist_*() functions are not thread safe.
405 *
406 * @param list A pointer on the list to affect
407 * @param prev_node A pointer on the previous node
408 * (can be NULL, which means the node is the list's head)
409 * @param node A pointer on the node to remove
410 */
sys_slist_remove(sys_slist_t * list,sys_snode_t * prev_node,sys_snode_t * node)411 static inline void sys_slist_remove(sys_slist_t *list,
412 sys_snode_t *prev_node,
413 sys_snode_t *node)
414 {
415 if (!prev_node) {
416 list->head = node->next;
417
418 /* Was node also the tail? */
419 if (list->tail == node) {
420 list->tail = list->head;
421 }
422 } else {
423 prev_node->next = node->next;
424
425 /* Was node the tail? */
426 if (list->tail == node) {
427 list->tail = prev_node;
428 }
429 }
430
431 node->next = NULL;
432 }
433
434 /**
435 * @brief Find and remove a node from a list
436 *
437 * This and other sys_slist_*() functions are not thread safe.
438 *
439 * @param list A pointer on the list to affect
440 * @param node A pointer on the node to remove from the list
441 *
442 * @return true if node was removed
443 */
sys_slist_find_and_remove(sys_slist_t * list,sys_snode_t * node)444 static inline bool sys_slist_find_and_remove(sys_slist_t *list,
445 sys_snode_t *node)
446 {
447 sys_snode_t *prev = NULL;
448 sys_snode_t *test;
449 SYS_SLIST_FOR_EACH_NODE(list, test) {
450 if (test == node) {
451 sys_slist_remove(list, prev, node);
452 return true;
453 }
454
455 prev = test;
456 }
457 return false;
458 }
459
460 #ifdef __cplusplus
461 }
462 #endif
463
464 #endif /* __SLIST_H__ */
465