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