Branch data Line data Source code
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 : :
197 : 6 : static inline void sys_dlist_init(sys_dlist_t *list)
198 : : {
199 : 6 : list->head = (sys_dnode_t *)list;
200 : 6 : list->tail = (sys_dnode_t *)list;
201 : 6 : }
202 : :
203 : : #define SYS_DLIST_STATIC_INIT(ptr_to_list) { {(ptr_to_list)}, {(ptr_to_list)} }
204 : :
205 : : /**
206 : : * @brief initialize node to its state when not in a list
207 : : *
208 : : * @param node the node
209 : : */
210 : :
211 : 4 : static inline void sys_dnode_init(sys_dnode_t *node)
212 : : {
213 : 4 : node->next = NULL;
214 : 4 : node->prev = NULL;
215 : 4 : }
216 : :
217 : : /**
218 : : * @brief check if a node is a member of any list
219 : : *
220 : : * @param node the node
221 : : *
222 : : * @return true if node is linked into a list, false if it is not
223 : : */
224 : :
225 : 5 : static inline bool sys_dnode_is_linked(const sys_dnode_t *node)
226 : : {
227 : 5 : return node->next != NULL;
228 : : }
229 : :
230 : : /**
231 : : * @brief check if a node is the list's head
232 : : *
233 : : * @param list the doubly-linked list to operate on
234 : : * @param node the node to check
235 : : *
236 : : * @return true if node is the head, false otherwise
237 : : */
238 : :
239 : : static inline bool sys_dlist_is_head(sys_dlist_t *list, sys_dnode_t *node)
240 : : {
241 : : return list->head == node;
242 : : }
243 : :
244 : : /**
245 : : * @brief check if a node is the list's tail
246 : : *
247 : : * @param list the doubly-linked list to operate on
248 : : * @param node the node to check
249 : : *
250 : : * @return true if node is the tail, false otherwise
251 : : */
252 : :
253 : : static inline bool sys_dlist_is_tail(sys_dlist_t *list, sys_dnode_t *node)
254 : : {
255 : : return list->tail == node;
256 : : }
257 : :
258 : : /**
259 : : * @brief check if the list is empty
260 : : *
261 : : * @param list the doubly-linked list to operate on
262 : : *
263 : : * @return true if empty, false otherwise
264 : : */
265 : :
266 : 11 : static inline bool sys_dlist_is_empty(sys_dlist_t *list)
267 : : {
268 : 11 : return list->head == list;
269 : : }
270 : :
271 : : /**
272 : : * @brief check if more than one node present
273 : : *
274 : : * This and other sys_dlist_*() functions are not thread safe.
275 : : *
276 : : * @param list the doubly-linked list to operate on
277 : : *
278 : : * @return true if multiple nodes, false otherwise
279 : : */
280 : :
281 : : static inline bool sys_dlist_has_multiple_nodes(sys_dlist_t *list)
282 : : {
283 : : return list->head != list->tail;
284 : : }
285 : :
286 : : /**
287 : : * @brief get a reference to the head item in the list
288 : : *
289 : : * @param list the doubly-linked list to operate on
290 : : *
291 : : * @return a pointer to the head element, NULL if list is empty
292 : : */
293 : :
294 : 11 : static inline sys_dnode_t *sys_dlist_peek_head(sys_dlist_t *list)
295 : : {
296 [ + + ]: 11 : return sys_dlist_is_empty(list) ? NULL : list->head;
297 : : }
298 : :
299 : : /**
300 : : * @brief get a reference to the head item in the list
301 : : *
302 : : * The list must be known to be non-empty.
303 : : *
304 : : * @param list the doubly-linked list to operate on
305 : : *
306 : : * @return a pointer to the head element
307 : : */
308 : :
309 : : static inline sys_dnode_t *sys_dlist_peek_head_not_empty(sys_dlist_t *list)
310 : : {
311 : : return list->head;
312 : : }
313 : :
314 : : /**
315 : : * @brief get a reference to the next item in the list, node is not NULL
316 : : *
317 : : * Faster than sys_dlist_peek_next() if node is known not to be NULL.
318 : : *
319 : : * @param list the doubly-linked list to operate on
320 : : * @param node the node from which to get the next element in the list
321 : : *
322 : : * @return a pointer to the next element from a node, NULL if node is the tail
323 : : */
324 : :
325 : 0 : static inline sys_dnode_t *sys_dlist_peek_next_no_check(sys_dlist_t *list,
326 : : sys_dnode_t *node)
327 : : {
328 [ # # ]: 0 : return (node == list->tail) ? NULL : node->next;
329 : : }
330 : :
331 : : /**
332 : : * @brief get a reference to the next item in the list
333 : : *
334 : : * @param list the doubly-linked list to operate on
335 : : * @param node the node from which to get the next element in the list
336 : : *
337 : : * @return a pointer to the next element from a node, NULL if node is the tail
338 : : * or NULL (when node comes from reading the head of an empty list).
339 : : */
340 : :
341 : 0 : static inline sys_dnode_t *sys_dlist_peek_next(sys_dlist_t *list,
342 : : sys_dnode_t *node)
343 : : {
344 [ # # ]: 0 : return (node != NULL) ? sys_dlist_peek_next_no_check(list, node) : NULL;
345 : : }
346 : :
347 : : /**
348 : : * @brief get a reference to the previous item in the list, node is not NULL
349 : : *
350 : : * Faster than sys_dlist_peek_prev() if node is known not to be NULL.
351 : : *
352 : : * @param list the doubly-linked list to operate on
353 : : * @param node the node from which to get the previous element in the list
354 : : *
355 : : * @return a pointer to the previous element from a node, NULL if node is the
356 : : * tail
357 : : */
358 : :
359 : : static inline sys_dnode_t *sys_dlist_peek_prev_no_check(sys_dlist_t *list,
360 : : sys_dnode_t *node)
361 : : {
362 : : return (node == list->head) ? NULL : node->prev;
363 : : }
364 : :
365 : : /**
366 : : * @brief get a reference to the previous item in the list
367 : : *
368 : : * @param list the doubly-linked list to operate on
369 : : * @param node the node from which to get the previous element in the list
370 : : *
371 : : * @return a pointer to the previous element from a node, NULL if node is the
372 : : * tail or NULL (when node comes from reading the head of an empty
373 : : * list).
374 : : */
375 : :
376 : : static inline sys_dnode_t *sys_dlist_peek_prev(sys_dlist_t *list,
377 : : sys_dnode_t *node)
378 : : {
379 : : return (node != NULL) ? sys_dlist_peek_prev_no_check(list, node) : NULL;
380 : : }
381 : :
382 : : /**
383 : : * @brief get a reference to the tail item in the list
384 : : *
385 : : * @param list the doubly-linked list to operate on
386 : : *
387 : : * @return a pointer to the tail element, NULL if list is empty
388 : : */
389 : :
390 : : static inline sys_dnode_t *sys_dlist_peek_tail(sys_dlist_t *list)
391 : : {
392 : : return sys_dlist_is_empty(list) ? NULL : list->tail;
393 : : }
394 : :
395 : : /**
396 : : * @brief add node to tail of list
397 : : *
398 : : * This and other sys_dlist_*() functions are not thread safe.
399 : : *
400 : : * @param list the doubly-linked list to operate on
401 : : * @param node the element to append
402 : : */
403 : :
404 : 1 : static inline void sys_dlist_append(sys_dlist_t *list, sys_dnode_t *node)
405 : : {
406 : 1 : sys_dnode_t *const tail = list->tail;
407 : :
408 : 1 : node->next = list;
409 : 1 : node->prev = tail;
410 : :
411 : 1 : tail->next = node;
412 : 1 : list->tail = node;
413 : 1 : }
414 : :
415 : : /**
416 : : * @brief add node to head of list
417 : : *
418 : : * This and other sys_dlist_*() functions are not thread safe.
419 : : *
420 : : * @param list the doubly-linked list to operate on
421 : : * @param node the element to append
422 : : */
423 : :
424 : : static inline void sys_dlist_prepend(sys_dlist_t *list, sys_dnode_t *node)
425 : : {
426 : : sys_dnode_t *const head = list->head;
427 : :
428 : : node->next = head;
429 : : node->prev = list;
430 : :
431 : : head->prev = node;
432 : : list->head = node;
433 : : }
434 : :
435 : : /**
436 : : * @brief Insert a node into a list
437 : : *
438 : : * Insert a node before a specified node in a dlist.
439 : : *
440 : : * @param successor the position before which "node" will be inserted
441 : : * @param node the element to insert
442 : : */
443 : 1 : static inline void sys_dlist_insert(sys_dnode_t *successor, sys_dnode_t *node)
444 : : {
445 : 1 : sys_dnode_t *const prev = successor->prev;
446 : :
447 : 1 : node->prev = prev;
448 : 1 : node->next = successor;
449 : 1 : prev->next = node;
450 : 1 : successor->prev = node;
451 : 1 : }
452 : :
453 : : /**
454 : : * @brief insert node at position
455 : : *
456 : : * Insert a node in a location depending on a external condition. The cond()
457 : : * function checks if the node is to be inserted _before_ the current node
458 : : * against which it is checked.
459 : : * This and other sys_dlist_*() functions are not thread safe.
460 : : *
461 : : * @param list the doubly-linked list to operate on
462 : : * @param node the element to insert
463 : : * @param cond a function that determines if the current node is the correct
464 : : * insert point
465 : : * @param data parameter to cond()
466 : : */
467 : :
468 : : static inline void sys_dlist_insert_at(sys_dlist_t *list, sys_dnode_t *node,
469 : : int (*cond)(sys_dnode_t *node, void *data), void *data)
470 : : {
471 : : if (sys_dlist_is_empty(list)) {
472 : : sys_dlist_append(list, node);
473 : : } else {
474 : : sys_dnode_t *pos = sys_dlist_peek_head(list);
475 : :
476 : : while ((pos != NULL) && (cond(pos, data) == 0)) {
477 : : pos = sys_dlist_peek_next(list, pos);
478 : : }
479 : : if (pos != NULL) {
480 : : sys_dlist_insert(pos, node);
481 : : } else {
482 : : sys_dlist_append(list, node);
483 : : }
484 : : }
485 : : }
486 : :
487 : : /**
488 : : * @brief remove a specific node from a list
489 : : *
490 : : * The list is implicit from the node. The node must be part of a list.
491 : : * This and other sys_dlist_*() functions are not thread safe.
492 : : *
493 : : * @param node the node to remove
494 : : */
495 : :
496 : 1 : static inline void sys_dlist_remove(sys_dnode_t *node)
497 : : {
498 : 1 : sys_dnode_t *const prev = node->prev;
499 : 1 : sys_dnode_t *const next = node->next;
500 : :
501 : 1 : prev->next = next;
502 : 1 : next->prev = prev;
503 : 1 : sys_dnode_init(node);
504 : 1 : }
505 : :
506 : : /**
507 : : * @brief get the first node in a list
508 : : *
509 : : * This and other sys_dlist_*() functions are not thread safe.
510 : : *
511 : : * @param list the doubly-linked list to operate on
512 : : *
513 : : * @return the first node in the list, NULL if list is empty
514 : : */
515 : :
516 : : static inline sys_dnode_t *sys_dlist_get(sys_dlist_t *list)
517 : : {
518 : : sys_dnode_t *node = NULL;
519 : :
520 : : if (!sys_dlist_is_empty(list)) {
521 : : node = list->head;
522 : : sys_dlist_remove(node);
523 : : }
524 : :
525 : : return node;
526 : : }
527 : :
528 : : /** @} */
529 : :
530 : : #ifdef __cplusplus
531 : : }
532 : : #endif
533 : :
534 : : #endif /* ZEPHYR_INCLUDE_SYS_DLIST_H_ */
|