1 // A doubly-linked list that can be embedded in a struct.
2 //
3 // Usage:
4 // struct llist_node head = LLIST_INIT(head);
5 // typedef struct {
6 // ...
7 // struct llist_node node;
8 // ...
9 // } MyObj;
10 //
11 // llist_insert_tail(&head, &obj->node);
12 // llist_remove(&obj->node);
13 //
14 // struct llist_node *node;
15 // llist_for_each(node, &head) {
16 // MyObj *obj = llist_data(node, MyObj, node);
17 // ...
18 // }
19 //
20
21 #ifndef Py_INTERNAL_LLIST_H
22 #define Py_INTERNAL_LLIST_H
23
24 #include <stddef.h>
25
26 #ifdef __cplusplus
27 extern "C" {
28 #endif
29
30 #ifndef Py_BUILD_CORE
31 # error "Py_BUILD_CORE must be defined to include this header"
32 #endif
33
34 struct llist_node {
35 struct llist_node *next;
36 struct llist_node *prev;
37 };
38
39 // Get the struct containing a node.
40 #define llist_data(node, type, member) (_Py_CONTAINER_OF(node, type, member))
41
42 // Iterate over a list.
43 #define llist_for_each(node, head) \
44 for (node = (head)->next; node != (head); node = node->next)
45
46 // Iterate over a list, but allow removal of the current node.
47 #define llist_for_each_safe(node, head) \
48 for (struct llist_node *_next = (node = (head)->next, node->next); \
49 node != (head); node = _next, _next = node->next)
50
51 #define LLIST_INIT(head) { &head, &head }
52
53 static inline void
llist_init(struct llist_node * head)54 llist_init(struct llist_node *head)
55 {
56 head->next = head;
57 head->prev = head;
58 }
59
60 // Returns 1 if the list is empty, 0 otherwise.
61 static inline int
llist_empty(struct llist_node * head)62 llist_empty(struct llist_node *head)
63 {
64 return head->next == head;
65 }
66
67 // Appends to the tail of the list.
68 static inline void
llist_insert_tail(struct llist_node * head,struct llist_node * node)69 llist_insert_tail(struct llist_node *head, struct llist_node *node)
70 {
71 node->prev = head->prev;
72 node->next = head;
73 head->prev->next = node;
74 head->prev = node;
75 }
76
77 // Remove a node from the list.
78 static inline void
llist_remove(struct llist_node * node)79 llist_remove(struct llist_node *node)
80 {
81 struct llist_node *prev = node->prev;
82 struct llist_node *next = node->next;
83 prev->next = next;
84 next->prev = prev;
85 node->prev = NULL;
86 node->next = NULL;
87 }
88
89 // Append all nodes from head2 onto head1. head2 is left empty.
90 static inline void
llist_concat(struct llist_node * head1,struct llist_node * head2)91 llist_concat(struct llist_node *head1, struct llist_node *head2)
92 {
93 if (!llist_empty(head2)) {
94 head1->prev->next = head2->next;
95 head2->next->prev = head1->prev;
96
97 head1->prev = head2->prev;
98 head2->prev->next = head1;
99 llist_init(head2);
100 }
101 }
102
103 #ifdef __cplusplus
104 }
105 #endif
106 #endif /* !Py_INTERNAL_LLIST_H */
107