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