Debian Codegraph @

src/basic/list.h

raw
1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
2 #pragma once
3
4 #include "basic-forward.h"
5
6 /* The head of the linked list. Use this in the structure that shall
7 * contain the head of the linked list */
8 #define LIST_HEAD(t,name) \
9 t *name
10
11 /* The pointers in the linked list's items. Use this in the item structure */
12 #define LIST_FIELDS(t,name) \
13 t *name##_next, *name##_prev
14
15 /* Initialize the list's head */
16 #define LIST_HEAD_INIT(head) \
17 do { \
18 (head) = NULL; \
19 } while (false)
20
21 /* Initialize a list item */
22 #define LIST_INIT(name,item) \
23 do { \
24 typeof(*(item)) *_item = (item); \
25 assert(_item); \
26 _item->name##_prev = _item->name##_next = NULL; \
27 } while (false)
28
29 /* Prepend an item to the list */
30 #define LIST_PREPEND(name,head,item) \
31 ({ \
32 typeof(*(head)) **_head = &(head), *_item = (item); \
33 assert(_item); \
34 if ((_item->name##_next = *_head)) \
35 _item->name##_next->name##_prev = _item; \
36 _item->name##_prev = NULL; \
37 *_head = _item; \
38 _item; \
39 })
40
41 /* Append an item to the list */
42 #define LIST_APPEND(name,head,item) \
43 ({ \
44 typeof(*(head)) **_hhead = &(head), *_tail; \
45 _tail = LIST_FIND_TAIL(name, *_hhead); \
46 LIST_INSERT_AFTER(name, *_hhead, _tail, item); \
47 })
48
49 /* Remove an item from the list */
50 #define LIST_REMOVE(name,head,item) \
51 ({ \
52 typeof(*(head)) **_head = &(head), *_item = (item); \
53 assert(_item); \
54 if (_item->name##_next) \
55 _item->name##_next->name##_prev = _item->name##_prev; \
56 if (_item->name##_prev) \
57 _item->name##_prev->name##_next = _item->name##_next; \
58 else { \
59 assert(*_head == _item); \
60 *_head = _item->name##_next; \
61 } \
62 _item->name##_next = _item->name##_prev = NULL; \
63 _item; \
64 })
65
66 /* Find the head of the list */
67 #define LIST_FIND_HEAD(name,item) \
68 ({ \
69 typeof(*(item)) *_item = (item); \
70 while (_item && _item->name##_prev) \
71 _item = _item->name##_prev; \
72 _item; \
73 })
74
75 /* Find the tail of the list */
76 #define LIST_FIND_TAIL(name,item) \
77 ({ \
78 typeof(*(item)) *_item = (item); \
79 while (_item && _item->name##_next) \
80 _item = _item->name##_next; \
81 _item; \
82 })
83
84 /* Insert an item after another one (a = where, b = what) */
85 #define LIST_INSERT_AFTER(name,head,a,b) \
86 ({ \
87 typeof(*(head)) **_head = &(head), *_a = (a), *_b = (b); \
88 assert(_b); \
89 if (!_a) { \
90 if ((_b->name##_next = *_head)) \
91 _b->name##_next->name##_prev = _b; \
92 _b->name##_prev = NULL; \
93 *_head = _b; \
94 } else { \
95 if ((_b->name##_next = _a->name##_next)) \
96 _b->name##_next->name##_prev = _b; \
97 _b->name##_prev = _a; \
98 _a->name##_next = _b; \
99 } \
100 _b; \
101 })
102
103 /* Insert an item before another one (a = where, b = what) */
104 #define LIST_INSERT_BEFORE(name,head,a,b) \
105 ({ \
106 typeof(*(head)) **_head = &(head), *_a = (a), *_b = (b); \
107 assert(_b); \
108 if (!_a) { \
109 if (!*_head) { \
110 _b->name##_next = NULL; \
111 _b->name##_prev = NULL; \
112 *_head = _b; \
113 } else { \
114 typeof(*(head)) *_tail = (head); \
115 while (_tail->name##_next) \
116 _tail = _tail->name##_next; \
117 _b->name##_next = NULL; \
118 _b->name##_prev = _tail; \
119 _tail->name##_next = _b; \
120 } \
121 } else { \
122 if ((_b->name##_prev = _a->name##_prev)) \
123 _b->name##_prev->name##_next = _b; \
124 else \
125 *_head = _b; \
126 _b->name##_next = _a; \
127 _a->name##_prev = _b; \
128 } \
129 _b; \
130 })
131
132 #define LIST_JUST_US(name, item) \
133 ({ \
134 typeof(*(item)) *_item = (item); \
135 !(_item)->name##_prev && !(_item)->name##_next; \
136 })
137
138 /* The type of the iterator 'i' is automatically determined by the type of 'head', and declared in the
139 * loop. Hence, do not declare the same variable in the outer scope. Sometimes, we set 'head' through
140 * hashmap_get(). In that case, you need to explicitly cast the result. */
141 #define LIST_FOREACH_WITH_NEXT(name,i,n,head) \
142 for (typeof(*(head)) *n, *i = (head); i && (n = i->name##_next, true); i = n)
143
144 #define LIST_FOREACH(name,i,head) \
145 LIST_FOREACH_WITH_NEXT(name, i, UNIQ_T(n, UNIQ), head)
146
147 #define _LIST_FOREACH_WITH_PREV(name,i,p,start) \
148 for (typeof(*(start)) *p, *i = (start); i && (p = i->name##_prev, true); i = p)
149
150 #define LIST_FOREACH_BACKWARDS(name,i,start) \
151 _LIST_FOREACH_WITH_PREV(name, i, UNIQ_T(p, UNIQ), start)
152
153 /* Iterate through all the members of the list p is included in, but skip over p */
154 #define LIST_FOREACH_OTHERS(name,i,p) \
155 for (typeof(*(p)) *_p = (p), *i = ({ \
156 typeof(*_p) *_j = _p; \
157 while (_j && _j->name##_prev) \
158 _j = _j->name##_prev; \
159 if (_j == _p) \
160 _j = _p->name##_next; \
161 _j; \
162 }); \
163 i; \
164 i = i->name##_next == _p ? _p->name##_next : i->name##_next)
165
166 /* Loop starting from p->next until p->prev. p can be adjusted meanwhile. */
167 #define LIST_LOOP_BUT_ONE(name,i,head,p) \
168 for (typeof(*(p)) *i = (p)->name##_next ? (p)->name##_next : (head); \
169 i != (p); \
170 i = i->name##_next ? i->name##_next : (head))
171
172 /* Join two lists tail to head: a->b, c->d to a->b->c->d and de-initialise second list */
173 #define LIST_JOIN(name,a,b) \
174 ({ \
175 assert(b); \
176 if (!(a)) \
177 (a) = (b); \
178 else { \
179 typeof(*(a)) *_head = (b), *_tail; \
180 _tail = LIST_FIND_TAIL(name, (a)); \
181 _tail->name##_next = _head; \
182 _head->name##_prev = _tail; \
183 } \
184 (b) = NULL; \
185 a; \
186 })
187
188 #define LIST_POP(name, a) \
189 ({ \
190 typeof(a)* _a = &(a); \
191 typeof(a) _p = *_a; \
192 if (_p) \
193 LIST_REMOVE(name, *_a, _p); \
194 _p; \
195 })
196
197 #define LIST_CLEAR(name, head, free_func) \
198 _LIST_CLEAR(name, head, free_func, UNIQ_T(elem, UNIQ))
199
200 /* Clear the list, destroying each element with free_func */
201 #define _LIST_CLEAR(name, head, free_func, elem) \
202 ({ \
203 typeof(head) elem; \
204 while ((elem = LIST_POP(name, head))) \
205 free_func(elem); \
206 head; \
207 })