Zephyr API Documentation  3.7.0-rc3
A Scalable Open Source RTOS
Loading...
Searching...
No Matches
dlist.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2013-2015 Wind River Systems, Inc.
3 *
4 * SPDX-License-Identifier: Apache-2.0
5 */
6
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
32extern "C" {
33#endif
34
35
36struct _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
50typedef struct _dnode sys_dlist_t;
54typedef struct _dnode sys_dnode_t;
55
56
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
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
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
132#define SYS_DLIST_CONTAINER(__dn, __cn, __n) \
133 (((__dn) != NULL) ? CONTAINER_OF(__dn, __typeof__(*(__cn)), __n) : NULL)
141#define SYS_DLIST_PEEK_HEAD_CONTAINER(__dl, __cn, __n) \
142 SYS_DLIST_CONTAINER(sys_dlist_peek_head(__dl), __cn, __n)
143
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
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
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
202static 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
211#define SYS_DLIST_STATIC_INIT(ptr_to_list) { {(ptr_to_list)}, {(ptr_to_list)} }
212
219static inline void sys_dnode_init(sys_dnode_t *node)
220{
221 node->next = NULL;
222 node->prev = NULL;
223}
224
233static inline bool sys_dnode_is_linked(const sys_dnode_t *node)
234{
235 return node->next != NULL;
236}
237
247static inline bool sys_dlist_is_head(sys_dlist_t *list, sys_dnode_t *node)
248{
249 return list->head == node;
250}
251
261static inline bool sys_dlist_is_tail(sys_dlist_t *list, sys_dnode_t *node)
262{
263 return list->tail == node;
264}
265
274static inline bool sys_dlist_is_empty(sys_dlist_t *list)
275{
276 return list->head == list;
277}
278
290{
291 return list->head != list->tail;
292}
293
303{
304 return sys_dlist_is_empty(list) ? NULL : list->head;
305}
306
318{
319 return list->head;
320}
321
334 sys_dnode_t *node)
335{
336 return (node == list->tail) ? NULL : node->next;
337}
338
350 sys_dnode_t *node)
351{
352 return (node != NULL) ? sys_dlist_peek_next_no_check(list, node) : NULL;
353}
354
368 sys_dnode_t *node)
369{
370 return (node == list->head) ? NULL : node->prev;
371}
372
385 sys_dnode_t *node)
386{
387 return (node != NULL) ? sys_dlist_peek_prev_no_check(list, node) : NULL;
388}
389
399{
400 return sys_dlist_is_empty(list) ? NULL : list->tail;
401}
402
412static 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
432static 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
451static 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
476static 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
504static 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
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
543static 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
556#ifdef __cplusplus
557}
558#endif
559
560#endif /* ZEPHYR_INCLUDE_SYS_DLIST_H_ */
static bool sys_dlist_has_multiple_nodes(sys_dlist_t *list)
check if more than one node present
Definition: dlist.h:289
static void sys_dlist_remove(sys_dnode_t *node)
remove a specific node from a list
Definition: dlist.h:504
static void sys_dlist_append(sys_dlist_t *list, sys_dnode_t *node)
add node to tail of list
Definition: dlist.h:412
static sys_dnode_t * sys_dlist_peek_prev(sys_dlist_t *list, sys_dnode_t *node)
get a reference to the previous item in the list
Definition: dlist.h:384
static sys_dnode_t * sys_dlist_get(sys_dlist_t *list)
get the first node in a list
Definition: dlist.h:524
#define SYS_DLIST_FOR_EACH_NODE(__dl, __dn)
Provide the primitive to iterate on a list Note: the loop is unsafe and thus __dn should not be remov...
Definition: dlist.h:72
static bool sys_dlist_is_tail(sys_dlist_t *list, sys_dnode_t *node)
check if a node is the list's tail
Definition: dlist.h:261
struct _dnode sys_dnode_t
Doubly-linked list node structure.
Definition: dlist.h:54
static void sys_dlist_insert_at(sys_dlist_t *list, sys_dnode_t *node, int(*cond)(sys_dnode_t *node, void *data), void *data)
insert node at position
Definition: dlist.h:476
static void sys_dlist_prepend(sys_dlist_t *list, sys_dnode_t *node)
add node to head of list
Definition: dlist.h:432
static sys_dnode_t * sys_dlist_peek_head(sys_dlist_t *list)
get a reference to the head item in the list
Definition: dlist.h:302
static sys_dnode_t * sys_dlist_peek_head_not_empty(sys_dlist_t *list)
get a reference to the head item in the list
Definition: dlist.h:317
static sys_dnode_t * sys_dlist_peek_next(sys_dlist_t *list, sys_dnode_t *node)
get a reference to the next item in the list
Definition: dlist.h:349
static bool sys_dlist_is_head(sys_dlist_t *list, sys_dnode_t *node)
check if a node is the list's head
Definition: dlist.h:247
static sys_dnode_t * sys_dlist_peek_prev_no_check(sys_dlist_t *list, sys_dnode_t *node)
get a reference to the previous item in the list, node is not NULL
Definition: dlist.h:367
static sys_dnode_t * sys_dlist_peek_next_no_check(sys_dlist_t *list, sys_dnode_t *node)
get a reference to the next item in the list, node is not NULL
Definition: dlist.h:333
static size_t sys_dlist_len(sys_dlist_t *list)
Compute the size of the given list in O(n) time.
Definition: dlist.h:543
static void sys_dlist_insert(sys_dnode_t *successor, sys_dnode_t *node)
Insert a node into a list.
Definition: dlist.h:451
struct _dnode sys_dlist_t
Doubly-linked list structure.
Definition: dlist.h:50
static bool sys_dlist_is_empty(sys_dlist_t *list)
check if the list is empty
Definition: dlist.h:274
static bool sys_dnode_is_linked(const sys_dnode_t *node)
check if a node is a member of any list
Definition: dlist.h:233
static sys_dnode_t * sys_dlist_peek_tail(sys_dlist_t *list)
get a reference to the tail item in the list
Definition: dlist.h:398
static void sys_dnode_init(sys_dnode_t *node)
initialize node to its state when not in a list
Definition: dlist.h:219
static void sys_dlist_init(sys_dlist_t *list)
initialize list to its empty state
Definition: dlist.h:202