Line data Source code
1 0 : /*
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 1 : typedef struct _dnode sys_dlist_t;
51 : /**
52 : * @brief Doubly-linked list node structure.
53 : */
54 1 : 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 1 : #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 1 : #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 1 : #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 1 : #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 1 : #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 1 : #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 1 : #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 1 : #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 :
202 1 : 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 1 : #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 :
219 1 : 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 :
233 1 : 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 :
247 1 : static inline bool sys_dlist_is_head(const sys_dlist_t *list, const 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 :
261 1 : static inline bool sys_dlist_is_tail(const sys_dlist_t *list, const 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 :
274 1 : static inline bool sys_dlist_is_empty(const 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 :
289 1 : static inline bool sys_dlist_has_multiple_nodes(const 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 :
302 1 : static inline sys_dnode_t *sys_dlist_peek_head(const 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 :
317 1 : static inline sys_dnode_t *sys_dlist_peek_head_not_empty(const 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 :
333 1 : static inline sys_dnode_t *sys_dlist_peek_next_no_check(const sys_dlist_t *list,
334 : const 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 :
349 1 : static inline sys_dnode_t *sys_dlist_peek_next(const sys_dlist_t *list,
350 : const 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 :
367 1 : static inline sys_dnode_t *sys_dlist_peek_prev_no_check(const sys_dlist_t *list,
368 : const 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 :
384 1 : static inline sys_dnode_t *sys_dlist_peek_prev(const sys_dlist_t *list,
385 : const 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 :
398 1 : static inline sys_dnode_t *sys_dlist_peek_tail(const 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 :
412 1 : 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 :
432 1 : 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 : */
451 1 : 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 :
476 1 : 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 : * Like :c:func:`sys_dlist_remove()`, this routine removes a specific node
499 : * from a list. However, unlike :c:func:`sys_dlist_remove()`, this routine
500 : * does not re-initialize the removed node. One significant implication of
501 : * this difference is that the function :c:func`sys_dnode_is_linked()` will
502 : * not work on a dequeued node.
503 : *
504 : * The list is implicit from the node. The node must be part of a list.
505 : * This and other sys_dlist_*() functions are not thread safe.
506 : *
507 : * @param node the node to dequeue
508 : */
509 1 : static inline void sys_dlist_dequeue(sys_dnode_t *node)
510 : {
511 : sys_dnode_t *const prev = node->prev;
512 : sys_dnode_t *const next = node->next;
513 :
514 : prev->next = next;
515 : next->prev = prev;
516 : }
517 :
518 : /**
519 : * @brief remove a specific node from a list
520 : *
521 : * The list is implicit from the node. The node must be part of a list.
522 : * This and other sys_dlist_*() functions are not thread safe.
523 : *
524 : * @param node the node to remove
525 : */
526 :
527 1 : static inline void sys_dlist_remove(sys_dnode_t *node)
528 : {
529 : sys_dnode_t *const prev = node->prev;
530 : sys_dnode_t *const next = node->next;
531 :
532 : prev->next = next;
533 : next->prev = prev;
534 : sys_dnode_init(node);
535 : }
536 :
537 : /**
538 : * @brief get the first node in a list
539 : *
540 : * This and other sys_dlist_*() functions are not thread safe.
541 : *
542 : * @param list the doubly-linked list to operate on
543 : *
544 : * @return the first node in the list, NULL if list is empty
545 : */
546 :
547 1 : static inline sys_dnode_t *sys_dlist_get(sys_dlist_t *list)
548 : {
549 : sys_dnode_t *node = NULL;
550 :
551 : if (!sys_dlist_is_empty(list)) {
552 : node = list->head;
553 : sys_dlist_remove(node);
554 : }
555 :
556 : return node;
557 : }
558 :
559 : /**
560 : * @brief Compute the size of the given list in O(n) time
561 : *
562 : * @param list A pointer on the list
563 : *
564 : * @return an integer equal to the size of the list, or 0 if empty
565 : */
566 1 : static inline size_t sys_dlist_len(const sys_dlist_t *list)
567 : {
568 : size_t len = 0;
569 : sys_dnode_t *node = NULL;
570 :
571 : SYS_DLIST_FOR_EACH_NODE(list, node) {
572 : len++;
573 : }
574 : return len;
575 : }
576 :
577 : /** @} */
578 :
579 : #ifdef __cplusplus
580 : }
581 : #endif
582 :
583 : #endif /* ZEPHYR_INCLUDE_SYS_DLIST_H_ */
|
