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