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