1 /*
2 * Copyright (c) 2013-2015 Wind River Systems, Inc.
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
7 /**
8 * @file
9 * @brief Doubly-linked list implementation
10 *
11 * Doubly-linked list implementation using inline macros/functions.
12 * This API is not thread safe, and thus if a list is used across threads,
13 * calls to functions must be protected with synchronization primitives.
14 *
15 * The lists are expected to be initialized such that both the head and tail
16 * pointers point to the list itself. Initializing the lists in such a fashion
17 * simplifies the adding and removing of nodes to/from the list.
18 */
19
20 #ifndef ZEPHYR_INCLUDE_SYS_DLIST_H_
21 #define ZEPHYR_INCLUDE_SYS_DLIST_H_
22
23 #include <stddef.h>
24 #include <stdbool.h>
25 #include <toolchain.h>
26
27 #ifdef __cplusplus
28 extern "C" {
29 #endif
30
31 /**
32 * @defgroup doubly-linked-list_apis Doubly-linked list
33 * @ingroup datastructure_apis
34 * @{
35 */
36
37 struct _dnode {
38 union {
39 struct _dnode *head; /* ptr to head of list (sys_dlist_t) */
40 struct _dnode *next; /* ptr to next node (sys_dnode_t) */
41 };
42 union {
43 struct _dnode *tail; /* ptr to tail of list (sys_dlist_t) */
44 struct _dnode *prev; /* ptr to previous node (sys_dnode_t) */
45 };
46 };
47
48 typedef struct _dnode sys_dlist_t;
49 typedef struct _dnode sys_dnode_t;
50
51
52 /**
53 * @brief Provide the primitive to iterate on a list
54 * Note: the loop is unsafe and thus __dn should not be removed
55 *
56 * User _MUST_ add the loop statement curly braces enclosing its own code:
57 *
58 * SYS_DLIST_FOR_EACH_NODE(l, n) {
59 * <user code>
60 * }
61 *
62 * This and other SYS_DLIST_*() macros are not thread safe.
63 *
64 * @param __dl A pointer on a sys_dlist_t to iterate on
65 * @param __dn A sys_dnode_t pointer to peek each node of the list
66 */
67 #define SYS_DLIST_FOR_EACH_NODE(__dl, __dn) \
68 for (__dn = sys_dlist_peek_head(__dl); __dn != NULL; \
69 __dn = sys_dlist_peek_next(__dl, __dn))
70
71 /**
72 * @brief Provide the primitive to iterate on a list, from a node in the list
73 * Note: the loop is unsafe and thus __dn should not be removed
74 *
75 * User _MUST_ add the loop statement curly braces enclosing its own code:
76 *
77 * SYS_DLIST_ITERATE_FROM_NODE(l, n) {
78 * <user code>
79 * }
80 *
81 * Like SYS_DLIST_FOR_EACH_NODE(), but __dn already contains a node in the list
82 * where to start searching for the next entry from. If NULL, it starts from
83 * the head.
84 *
85 * This and other SYS_DLIST_*() macros are not thread safe.
86 *
87 * @param __dl A pointer on a sys_dlist_t to iterate on
88 * @param __dn A sys_dnode_t pointer to peek each node of the list;
89 * it contains the starting node, or NULL to start from the head
90 */
91 #define SYS_DLIST_ITERATE_FROM_NODE(__dl, __dn) \
92 for (__dn = __dn ? sys_dlist_peek_next_no_check(__dl, __dn) \
93 : sys_dlist_peek_head(__dl); \
94 __dn != NULL; \
95 __dn = sys_dlist_peek_next(__dl, __dn))
96
97 /**
98 * @brief Provide the primitive to safely iterate on a list
99 * Note: __dn 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_DLIST_FOR_EACH_NODE_SAFE(l, n, s) {
104 * <user code>
105 * }
106 *
107 * This and other SYS_DLIST_*() macros are not thread safe.
108 *
109 * @param __dl A pointer on a sys_dlist_t to iterate on
110 * @param __dn A sys_dnode_t pointer to peek each node of the list
111 * @param __dns A sys_dnode_t pointer for the loop to run safely
112 */
113 #define SYS_DLIST_FOR_EACH_NODE_SAFE(__dl, __dn, __dns) \
114 for (__dn = sys_dlist_peek_head(__dl), \
115 __dns = sys_dlist_peek_next(__dl, __dn); \
116 __dn != NULL; __dn = __dns, \
117 __dns = sys_dlist_peek_next(__dl, __dn))
118
119 /*
120 * @brief Provide the primitive to resolve the container of a list node
121 * Note: it is safe to use with NULL pointer nodes
122 *
123 * @param __dn A pointer on a sys_dnode_t to get its container
124 * @param __cn Container struct type pointer
125 * @param __n The field name of sys_dnode_t within the container struct
126 */
127 #define SYS_DLIST_CONTAINER(__dn, __cn, __n) \
128 ((__dn != NULL) ? CONTAINER_OF(__dn, __typeof__(*__cn), __n) : NULL)
129 /*
130 * @brief Provide the primitive to peek container of the list head
131 *
132 * @param __dl A pointer on a sys_dlist_t to peek
133 * @param __cn Container struct type pointer
134 * @param __n The field name of sys_dnode_t within the container struct
135 */
136 #define SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n) \
137 SYS_DLIST_CONTAINER(sys_dlist_peek_head(__dl), __cn, __n)
138
139 /*
140 * @brief Provide the primitive to peek the next container
141 *
142 * @param __dl A pointer on a sys_dlist_t to peek
143 * @param __cn Container struct type pointer
144 * @param __n The field name of sys_dnode_t within the container struct
145 */
146 #define SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n) \
147 ((__cn != NULL) ? \
148 SYS_DLIST_CONTAINER(sys_dlist_peek_next(__dl, &(__cn->__n)), \
149 __cn, __n) : NULL)
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_DLIST_FOR_EACH_CONTAINER(l, c, n) {
158 * <user code>
159 * }
160 *
161 * @param __dl A pointer on a sys_dlist_t to iterate on
162 * @param __cn A pointer to peek each entry of the list
163 * @param __n The field name of sys_dnode_t within the container struct
164 */
165 #define SYS_DLIST_FOR_EACH_CONTAINER(__dl, __cn, __n) \
166 for (__cn = SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n); \
167 __cn != NULL; \
168 __cn = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n))
169
170 /**
171 * @brief Provide the primitive to safely iterate on a list under a container
172 * Note: __cn can be detached, it will not break the loop.
173 *
174 * User _MUST_ add the loop statement curly braces enclosing its own code:
175 *
176 * SYS_DLIST_FOR_EACH_CONTAINER_SAFE(l, c, cn, n) {
177 * <user code>
178 * }
179 *
180 * @param __dl A pointer on a sys_dlist_t to iterate on
181 * @param __cn A pointer to peek each entry of the list
182 * @param __cns A pointer for the loop to run safely
183 * @param __n The field name of sys_dnode_t within the container struct
184 */
185 #define SYS_DLIST_FOR_EACH_CONTAINER_SAFE(__dl, __cn, __cns, __n) \
186 for (__cn = SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n), \
187 __cns = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n); \
188 __cn != NULL; __cn = __cns, \
189 __cns = SYS_DLIST_PEEK_NEXT_CONTAINER(__dl, __cn, __n))
190
191 /**
192 * @brief initialize list to its empty state
193 *
194 * @param list the doubly-linked list
195 *
196 * @return N/A
197 */
198
sys_dlist_init(sys_dlist_t * list)199 static inline void sys_dlist_init(sys_dlist_t *list)
200 {
201 list->head = (sys_dnode_t *)list;
202 list->tail = (sys_dnode_t *)list;
203 }
204
205 #define SYS_DLIST_STATIC_INIT(ptr_to_list) { {(ptr_to_list)}, {(ptr_to_list)} }
206
207 /**
208 * @brief initialize node to its state when not in a list
209 *
210 * @param node the node
211 *
212 * @return N/A
213 */
214
sys_dnode_init(sys_dnode_t * node)215 static inline void sys_dnode_init(sys_dnode_t *node)
216 {
217 node->next = NULL;
218 node->prev = NULL;
219 }
220
221 /**
222 * @brief check if a node is a member of any list
223 *
224 * @param node the node
225 *
226 * @return true if node is linked into a list, false if it is not
227 */
228
sys_dnode_is_linked(const sys_dnode_t * node)229 static inline bool sys_dnode_is_linked(const sys_dnode_t *node)
230 {
231 return node->next != NULL;
232 }
233
234 /**
235 * @brief check if a node is the list's head
236 *
237 * @param list the doubly-linked list to operate on
238 * @param node the node to check
239 *
240 * @return true if node is the head, false otherwise
241 */
242
sys_dlist_is_head(sys_dlist_t * list,sys_dnode_t * node)243 static inline bool sys_dlist_is_head(sys_dlist_t *list, sys_dnode_t *node)
244 {
245 return list->head == node;
246 }
247
248 /**
249 * @brief check if a node is the list's tail
250 *
251 * @param list the doubly-linked list to operate on
252 * @param node the node to check
253 *
254 * @return true if node is the tail, false otherwise
255 */
256
sys_dlist_is_tail(sys_dlist_t * list,sys_dnode_t * node)257 static inline bool sys_dlist_is_tail(sys_dlist_t *list, sys_dnode_t *node)
258 {
259 return list->tail == node;
260 }
261
262 /**
263 * @brief check if the list is empty
264 *
265 * @param list the doubly-linked list to operate on
266 *
267 * @return true if empty, false otherwise
268 */
269
sys_dlist_is_empty(sys_dlist_t * list)270 static inline bool sys_dlist_is_empty(sys_dlist_t *list)
271 {
272 return list->head == list;
273 }
274
275 /**
276 * @brief check if more than one node present
277 *
278 * This and other sys_dlist_*() functions are not thread safe.
279 *
280 * @param list the doubly-linked list to operate on
281 *
282 * @return true if multiple nodes, false otherwise
283 */
284
sys_dlist_has_multiple_nodes(sys_dlist_t * list)285 static inline bool sys_dlist_has_multiple_nodes(sys_dlist_t *list)
286 {
287 return list->head != list->tail;
288 }
289
290 /**
291 * @brief get a reference to the head item in the list
292 *
293 * @param list the doubly-linked list to operate on
294 *
295 * @return a pointer to the head element, NULL if list is empty
296 */
297
sys_dlist_peek_head(sys_dlist_t * list)298 static inline sys_dnode_t *sys_dlist_peek_head(sys_dlist_t *list)
299 {
300 return sys_dlist_is_empty(list) ? NULL : list->head;
301 }
302
303 /**
304 * @brief get a reference to the head item in the list
305 *
306 * The list must be known to be non-empty.
307 *
308 * @param list the doubly-linked list to operate on
309 *
310 * @return a pointer to the head element
311 */
312
sys_dlist_peek_head_not_empty(sys_dlist_t * list)313 static inline sys_dnode_t *sys_dlist_peek_head_not_empty(sys_dlist_t *list)
314 {
315 return list->head;
316 }
317
318 /**
319 * @brief get a reference to the next item in the list, node is not NULL
320 *
321 * Faster than sys_dlist_peek_next() if node is known not to be NULL.
322 *
323 * @param list the doubly-linked list to operate on
324 * @param node the node from which to get the next element in the list
325 *
326 * @return a pointer to the next element from a node, NULL if node is the tail
327 */
328
sys_dlist_peek_next_no_check(sys_dlist_t * list,sys_dnode_t * node)329 static inline sys_dnode_t *sys_dlist_peek_next_no_check(sys_dlist_t *list,
330 sys_dnode_t *node)
331 {
332 return (node == list->tail) ? NULL : node->next;
333 }
334
335 /**
336 * @brief get a reference to the next item in the list
337 *
338 * @param list the doubly-linked list to operate on
339 * @param node the node from which to get the next element in the list
340 *
341 * @return a pointer to the next element from a node, NULL if node is the tail
342 * or NULL (when node comes from reading the head of an empty list).
343 */
344
sys_dlist_peek_next(sys_dlist_t * list,sys_dnode_t * node)345 static inline sys_dnode_t *sys_dlist_peek_next(sys_dlist_t *list,
346 sys_dnode_t *node)
347 {
348 return (node != NULL) ? sys_dlist_peek_next_no_check(list, node) : NULL;
349 }
350
351 /**
352 * @brief get a reference to the previous item in the list, node is not NULL
353 *
354 * Faster than sys_dlist_peek_prev() if node is known not to be NULL.
355 *
356 * @param list the doubly-linked list to operate on
357 * @param node the node from which to get the previous element in the list
358 *
359 * @return a pointer to the previous element from a node, NULL if node is the
360 * tail
361 */
362
sys_dlist_peek_prev_no_check(sys_dlist_t * list,sys_dnode_t * node)363 static inline sys_dnode_t *sys_dlist_peek_prev_no_check(sys_dlist_t *list,
364 sys_dnode_t *node)
365 {
366 return (node == list->head) ? NULL : node->prev;
367 }
368
369 /**
370 * @brief get a reference to the previous item in the list
371 *
372 * @param list the doubly-linked list to operate on
373 * @param node the node from which to get the previous element in the list
374 *
375 * @return a pointer to the previous element from a node, NULL if node is the
376 * tail or NULL (when node comes from reading the head of an empty
377 * list).
378 */
379
sys_dlist_peek_prev(sys_dlist_t * list,sys_dnode_t * node)380 static inline sys_dnode_t *sys_dlist_peek_prev(sys_dlist_t *list,
381 sys_dnode_t *node)
382 {
383 return (node != NULL) ? sys_dlist_peek_prev_no_check(list, node) : NULL;
384 }
385
386 /**
387 * @brief get a reference to the tail item in the list
388 *
389 * @param list the doubly-linked list to operate on
390 *
391 * @return a pointer to the tail element, NULL if list is empty
392 */
393
sys_dlist_peek_tail(sys_dlist_t * list)394 static inline sys_dnode_t *sys_dlist_peek_tail(sys_dlist_t *list)
395 {
396 return sys_dlist_is_empty(list) ? NULL : list->tail;
397 }
398
399 /**
400 * @brief add node to tail of list
401 *
402 * This and other sys_dlist_*() functions are not thread safe.
403 *
404 * @param list the doubly-linked list to operate on
405 * @param node the element to append
406 *
407 * @return N/A
408 */
409
sys_dlist_append(sys_dlist_t * list,sys_dnode_t * node)410 static inline void sys_dlist_append(sys_dlist_t *list, sys_dnode_t *node)
411 {
412 sys_dnode_t *const tail = list->tail;
413
414 node->next = list;
415 node->prev = tail;
416
417 tail->next = node;
418 list->tail = node;
419 }
420
421 /**
422 * @brief add node to head of list
423 *
424 * This and other sys_dlist_*() functions are not thread safe.
425 *
426 * @param list the doubly-linked list to operate on
427 * @param node the element to append
428 *
429 * @return N/A
430 */
431
sys_dlist_prepend(sys_dlist_t * list,sys_dnode_t * node)432 static inline void sys_dlist_prepend(sys_dlist_t *list, sys_dnode_t *node)
433 {
434 sys_dnode_t *const head = list->head;
435
436 node->next = head;
437 node->prev = list;
438
439 head->prev = node;
440 list->head = node;
441 }
442
443 /**
444 * @brief Insert a node into a list
445 *
446 * Insert a node before a specified node in a dlist.
447 *
448 * @param successor the position before which "node" will be inserted
449 * @param node the element to insert
450 */
sys_dlist_insert(sys_dnode_t * successor,sys_dnode_t * node)451 static inline void sys_dlist_insert(sys_dnode_t *successor, sys_dnode_t *node)
452 {
453 sys_dnode_t *const prev = successor->prev;
454
455 node->prev = prev;
456 node->next = successor;
457 prev->next = node;
458 successor->prev = node;
459 }
460
461 /**
462 * @brief insert node at position
463 *
464 * Insert a node in a location depending on a external condition. The cond()
465 * function checks if the node is to be inserted _before_ the current node
466 * against which it is checked.
467 * This and other sys_dlist_*() functions are not thread safe.
468 *
469 * @param list the doubly-linked list to operate on
470 * @param node the element to insert
471 * @param cond a function that determines if the current node is the correct
472 * insert point
473 * @param data parameter to cond()
474 *
475 * @return N/A
476 */
477
sys_dlist_insert_at(sys_dlist_t * list,sys_dnode_t * node,int (* cond)(sys_dnode_t * node,void * data),void * data)478 static inline void sys_dlist_insert_at(sys_dlist_t *list, sys_dnode_t *node,
479 int (*cond)(sys_dnode_t *node, void *data), void *data)
480 {
481 if (sys_dlist_is_empty(list)) {
482 sys_dlist_append(list, node);
483 } else {
484 sys_dnode_t *pos = sys_dlist_peek_head(list);
485
486 while ((pos != NULL) && (cond(pos, data) == 0)) {
487 pos = sys_dlist_peek_next(list, pos);
488 }
489 if (pos != NULL) {
490 sys_dlist_insert(pos, node);
491 } else {
492 sys_dlist_append(list, node);
493 }
494 }
495 }
496
497 /**
498 * @brief remove a specific node from a list
499 *
500 * The list is implicit from the node. The node must be part of a list.
501 * This and other sys_dlist_*() functions are not thread safe.
502 *
503 * @param node the node to remove
504 *
505 * @return N/A
506 */
507
sys_dlist_remove(sys_dnode_t * node)508 static inline void sys_dlist_remove(sys_dnode_t *node)
509 {
510 sys_dnode_t *const prev = node->prev;
511 sys_dnode_t *const next = node->next;
512
513 prev->next = next;
514 next->prev = prev;
515 sys_dnode_init(node);
516 }
517
518 /**
519 * @brief get the first node in a list
520 *
521 * This and other sys_dlist_*() functions are not thread safe.
522 *
523 * @param list the doubly-linked list to operate on
524 *
525 * @return the first node in the list, NULL if list is empty
526 */
527
sys_dlist_get(sys_dlist_t * list)528 static inline sys_dnode_t *sys_dlist_get(sys_dlist_t *list)
529 {
530 sys_dnode_t *node = NULL;
531
532 if (!sys_dlist_is_empty(list)) {
533 node = list->head;
534 sys_dlist_remove(node);
535 }
536
537 return node;
538 }
539
540 /** @} */
541
542 #ifdef __cplusplus
543 }
544 #endif
545
546 #endif /* ZEPHYR_INCLUDE_SYS_DLIST_H_ */
547
