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