1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#ifndef QEMU_SYS_QUEUE_H_
41#define QEMU_SYS_QUEUE_H_
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81#include "qemu/atomic.h"
82
83
84
85
86#define QLIST_HEAD(name, type) \
87struct name { \
88 struct type *lh_first; \
89}
90
91#define QLIST_HEAD_INITIALIZER(head) \
92 { NULL }
93
94#define QLIST_ENTRY(type) \
95struct { \
96 struct type *le_next; \
97 struct type **le_prev; \
98}
99
100
101
102
103#define QLIST_INIT(head) do { \
104 (head)->lh_first = NULL; \
105} while (0)
106
107#define QLIST_SWAP(dstlist, srclist, field) do { \
108 void *tmplist; \
109 tmplist = (srclist)->lh_first; \
110 (srclist)->lh_first = (dstlist)->lh_first; \
111 if ((srclist)->lh_first != NULL) { \
112 (srclist)->lh_first->field.le_prev = &(srclist)->lh_first; \
113 } \
114 (dstlist)->lh_first = tmplist; \
115 if ((dstlist)->lh_first != NULL) { \
116 (dstlist)->lh_first->field.le_prev = &(dstlist)->lh_first; \
117 } \
118} while (0)
119
120#define QLIST_INSERT_AFTER(listelm, elm, field) do { \
121 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
122 (listelm)->field.le_next->field.le_prev = \
123 &(elm)->field.le_next; \
124 (listelm)->field.le_next = (elm); \
125 (elm)->field.le_prev = &(listelm)->field.le_next; \
126} while (0)
127
128#define QLIST_INSERT_BEFORE(listelm, elm, field) do { \
129 (elm)->field.le_prev = (listelm)->field.le_prev; \
130 (elm)->field.le_next = (listelm); \
131 *(listelm)->field.le_prev = (elm); \
132 (listelm)->field.le_prev = &(elm)->field.le_next; \
133} while (0)
134
135#define QLIST_INSERT_HEAD(head, elm, field) do { \
136 if (((elm)->field.le_next = (head)->lh_first) != NULL) \
137 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
138 (head)->lh_first = (elm); \
139 (elm)->field.le_prev = &(head)->lh_first; \
140} while (0)
141
142#define QLIST_REMOVE(elm, field) do { \
143 if ((elm)->field.le_next != NULL) \
144 (elm)->field.le_next->field.le_prev = \
145 (elm)->field.le_prev; \
146 *(elm)->field.le_prev = (elm)->field.le_next; \
147} while (0)
148
149#define QLIST_FOREACH(var, head, field) \
150 for ((var) = ((head)->lh_first); \
151 (var); \
152 (var) = ((var)->field.le_next))
153
154#define QLIST_FOREACH_SAFE(var, head, field, next_var) \
155 for ((var) = ((head)->lh_first); \
156 (var) && ((next_var) = ((var)->field.le_next), 1); \
157 (var) = (next_var))
158
159
160
161
162#define QLIST_EMPTY(head) ((head)->lh_first == NULL)
163#define QLIST_FIRST(head) ((head)->lh_first)
164#define QLIST_NEXT(elm, field) ((elm)->field.le_next)
165
166
167
168
169
170#define QSLIST_HEAD(name, type) \
171struct name { \
172 struct type *slh_first; \
173}
174
175#define QSLIST_HEAD_INITIALIZER(head) \
176 { NULL }
177
178#define QSLIST_ENTRY(type) \
179struct { \
180 struct type *sle_next; \
181}
182
183
184
185
186#define QSLIST_INIT(head) do { \
187 (head)->slh_first = NULL; \
188} while (0)
189
190#define QSLIST_INSERT_AFTER(slistelm, elm, field) do { \
191 (elm)->field.sle_next = (slistelm)->field.sle_next; \
192 (slistelm)->field.sle_next = (elm); \
193} while (0)
194
195#define QSLIST_INSERT_HEAD(head, elm, field) do { \
196 (elm)->field.sle_next = (head)->slh_first; \
197 (head)->slh_first = (elm); \
198} while (0)
199
200#define QSLIST_INSERT_HEAD_ATOMIC(head, elm, field) do { \
201 typeof(elm) save_sle_next; \
202 do { \
203 save_sle_next = (elm)->field.sle_next = (head)->slh_first; \
204 } while (atomic_cmpxchg(&(head)->slh_first, save_sle_next, (elm)) != \
205 save_sle_next); \
206} while (0)
207
208#define QSLIST_MOVE_ATOMIC(dest, src) do { \
209 (dest)->slh_first = atomic_xchg(&(src)->slh_first, NULL); \
210} while (0)
211
212#define QSLIST_REMOVE_HEAD(head, field) do { \
213 (head)->slh_first = (head)->slh_first->field.sle_next; \
214} while (0)
215
216#define QSLIST_REMOVE_AFTER(slistelm, field) do { \
217 (slistelm)->field.sle_next = \
218 QSLIST_NEXT(QSLIST_NEXT((slistelm), field), field); \
219} while (0)
220
221#define QSLIST_FOREACH(var, head, field) \
222 for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
223
224#define QSLIST_FOREACH_SAFE(var, head, field, tvar) \
225 for ((var) = QSLIST_FIRST((head)); \
226 (var) && ((tvar) = QSLIST_NEXT((var), field), 1); \
227 (var) = (tvar))
228
229
230
231
232#define QSLIST_EMPTY(head) ((head)->slh_first == NULL)
233#define QSLIST_FIRST(head) ((head)->slh_first)
234#define QSLIST_NEXT(elm, field) ((elm)->field.sle_next)
235
236
237
238
239
240#define QSIMPLEQ_HEAD(name, type) \
241struct name { \
242 struct type *sqh_first; \
243 struct type **sqh_last; \
244}
245
246#define QSIMPLEQ_HEAD_INITIALIZER(head) \
247 { NULL, &(head).sqh_first }
248
249#define QSIMPLEQ_ENTRY(type) \
250struct { \
251 struct type *sqe_next; \
252}
253
254
255
256
257#define QSIMPLEQ_INIT(head) do { \
258 (head)->sqh_first = NULL; \
259 (head)->sqh_last = &(head)->sqh_first; \
260} while (0)
261
262#define QSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
263 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
264 (head)->sqh_last = &(elm)->field.sqe_next; \
265 (head)->sqh_first = (elm); \
266} while (0)
267
268#define QSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
269 (elm)->field.sqe_next = NULL; \
270 *(head)->sqh_last = (elm); \
271 (head)->sqh_last = &(elm)->field.sqe_next; \
272} while (0)
273
274#define QSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
275 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \
276 (head)->sqh_last = &(elm)->field.sqe_next; \
277 (listelm)->field.sqe_next = (elm); \
278} while (0)
279
280#define QSIMPLEQ_REMOVE_HEAD(head, field) do { \
281 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL)\
282 (head)->sqh_last = &(head)->sqh_first; \
283} while (0)
284
285#define QSIMPLEQ_SPLIT_AFTER(head, elm, field, removed) do { \
286 QSIMPLEQ_INIT(removed); \
287 if (((removed)->sqh_first = (head)->sqh_first) != NULL) { \
288 if (((head)->sqh_first = (elm)->field.sqe_next) == NULL) { \
289 (head)->sqh_last = &(head)->sqh_first; \
290 } \
291 (removed)->sqh_last = &(elm)->field.sqe_next; \
292 (elm)->field.sqe_next = NULL; \
293 } \
294} while (0)
295
296#define QSIMPLEQ_REMOVE(head, elm, type, field) do { \
297 if ((head)->sqh_first == (elm)) { \
298 QSIMPLEQ_REMOVE_HEAD((head), field); \
299 } else { \
300 struct type *curelm = (head)->sqh_first; \
301 while (curelm->field.sqe_next != (elm)) \
302 curelm = curelm->field.sqe_next; \
303 if ((curelm->field.sqe_next = \
304 curelm->field.sqe_next->field.sqe_next) == NULL) \
305 (head)->sqh_last = &(curelm)->field.sqe_next; \
306 } \
307} while (0)
308
309#define QSIMPLEQ_FOREACH(var, head, field) \
310 for ((var) = ((head)->sqh_first); \
311 (var); \
312 (var) = ((var)->field.sqe_next))
313
314#define QSIMPLEQ_FOREACH_SAFE(var, head, field, next) \
315 for ((var) = ((head)->sqh_first); \
316 (var) && ((next = ((var)->field.sqe_next)), 1); \
317 (var) = (next))
318
319#define QSIMPLEQ_CONCAT(head1, head2) do { \
320 if (!QSIMPLEQ_EMPTY((head2))) { \
321 *(head1)->sqh_last = (head2)->sqh_first; \
322 (head1)->sqh_last = (head2)->sqh_last; \
323 QSIMPLEQ_INIT((head2)); \
324 } \
325} while (0)
326
327#define QSIMPLEQ_LAST(head, type, field) \
328 (QSIMPLEQ_EMPTY((head)) ? \
329 NULL : \
330 ((struct type *)(void *) \
331 ((char *)((head)->sqh_last) - offsetof(struct type, field))))
332
333
334
335
336#define QSIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL)
337#define QSIMPLEQ_FIRST(head) ((head)->sqh_first)
338#define QSIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
339
340
341
342
343
344#define Q_TAILQ_HEAD(name, type, qual) \
345struct name { \
346 qual type *tqh_first; \
347 qual type *qual *tqh_last; \
348}
349#define QTAILQ_HEAD(name, type) Q_TAILQ_HEAD(name, struct type,)
350
351#define QTAILQ_HEAD_INITIALIZER(head) \
352 { NULL, &(head).tqh_first }
353
354#define Q_TAILQ_ENTRY(type, qual) \
355struct { \
356 qual type *tqe_next; \
357 qual type *qual *tqe_prev; \
358}
359#define QTAILQ_ENTRY(type) Q_TAILQ_ENTRY(struct type,)
360
361
362
363
364#define QTAILQ_INIT(head) do { \
365 (head)->tqh_first = NULL; \
366 (head)->tqh_last = &(head)->tqh_first; \
367} while (0)
368
369#define QTAILQ_INSERT_HEAD(head, elm, field) do { \
370 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
371 (head)->tqh_first->field.tqe_prev = \
372 &(elm)->field.tqe_next; \
373 else \
374 (head)->tqh_last = &(elm)->field.tqe_next; \
375 (head)->tqh_first = (elm); \
376 (elm)->field.tqe_prev = &(head)->tqh_first; \
377} while (0)
378
379#define QTAILQ_INSERT_TAIL(head, elm, field) do { \
380 (elm)->field.tqe_next = NULL; \
381 (elm)->field.tqe_prev = (head)->tqh_last; \
382 *(head)->tqh_last = (elm); \
383 (head)->tqh_last = &(elm)->field.tqe_next; \
384} while (0)
385
386#define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
387 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
388 (elm)->field.tqe_next->field.tqe_prev = \
389 &(elm)->field.tqe_next; \
390 else \
391 (head)->tqh_last = &(elm)->field.tqe_next; \
392 (listelm)->field.tqe_next = (elm); \
393 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
394} while (0)
395
396#define QTAILQ_INSERT_BEFORE(listelm, elm, field) do { \
397 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
398 (elm)->field.tqe_next = (listelm); \
399 *(listelm)->field.tqe_prev = (elm); \
400 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
401} while (0)
402
403#define QTAILQ_REMOVE(head, elm, field) do { \
404 if (((elm)->field.tqe_next) != NULL) \
405 (elm)->field.tqe_next->field.tqe_prev = \
406 (elm)->field.tqe_prev; \
407 else \
408 (head)->tqh_last = (elm)->field.tqe_prev; \
409 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
410} while (0)
411
412#define QTAILQ_FOREACH(var, head, field) \
413 for ((var) = ((head)->tqh_first); \
414 (var); \
415 (var) = ((var)->field.tqe_next))
416
417#define QTAILQ_FOREACH_SAFE(var, head, field, next_var) \
418 for ((var) = ((head)->tqh_first); \
419 (var) && ((next_var) = ((var)->field.tqe_next), 1); \
420 (var) = (next_var))
421
422#define QTAILQ_FOREACH_REVERSE(var, head, headname, field) \
423 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \
424 (var); \
425 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
426
427
428
429
430#define QTAILQ_EMPTY(head) ((head)->tqh_first == NULL)
431#define QTAILQ_FIRST(head) ((head)->tqh_first)
432#define QTAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
433
434#define QTAILQ_LAST(head, headname) \
435 (*(((struct headname *)((head)->tqh_last))->tqh_last))
436#define QTAILQ_PREV(elm, headname, field) \
437 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
438
439#endif
440