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
82
83
84#define QLIST_HEAD(name, type) \
85struct name { \
86 struct type *lh_first; \
87}
88
89#define QLIST_HEAD_INITIALIZER(head) \
90 { NULL }
91
92#define QLIST_ENTRY(type) \
93struct { \
94 struct type *le_next; \
95 struct type **le_prev; \
96}
97
98
99
100
101#define QLIST_INIT(head) do { \
102 (head)->lh_first = NULL; \
103} while (0)
104
105#define QLIST_SWAP(dstlist, srclist, field) do { \
106 void *tmplist; \
107 tmplist = (srclist)->lh_first; \
108 (srclist)->lh_first = (dstlist)->lh_first; \
109 if ((srclist)->lh_first != NULL) { \
110 (srclist)->lh_first->field.le_prev = &(srclist)->lh_first; \
111 } \
112 (dstlist)->lh_first = tmplist; \
113 if ((dstlist)->lh_first != NULL) { \
114 (dstlist)->lh_first->field.le_prev = &(dstlist)->lh_first; \
115 } \
116} while (0)
117
118#define QLIST_INSERT_AFTER(listelm, elm, field) do { \
119 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
120 (listelm)->field.le_next->field.le_prev = \
121 &(elm)->field.le_next; \
122 (listelm)->field.le_next = (elm); \
123 (elm)->field.le_prev = &(listelm)->field.le_next; \
124} while (0)
125
126#define QLIST_INSERT_BEFORE(listelm, elm, field) do { \
127 (elm)->field.le_prev = (listelm)->field.le_prev; \
128 (elm)->field.le_next = (listelm); \
129 *(listelm)->field.le_prev = (elm); \
130 (listelm)->field.le_prev = &(elm)->field.le_next; \
131} while (0)
132
133#define QLIST_INSERT_HEAD(head, elm, field) do { \
134 if (((elm)->field.le_next = (head)->lh_first) != NULL) \
135 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
136 (head)->lh_first = (elm); \
137 (elm)->field.le_prev = &(head)->lh_first; \
138} while (0)
139
140#define QLIST_REMOVE(elm, field) do { \
141 if ((elm)->field.le_next != NULL) \
142 (elm)->field.le_next->field.le_prev = \
143 (elm)->field.le_prev; \
144 *(elm)->field.le_prev = (elm)->field.le_next; \
145} while (0)
146
147#define QLIST_FOREACH(var, head, field) \
148 for ((var) = ((head)->lh_first); \
149 (var); \
150 (var) = ((var)->field.le_next))
151
152#define QLIST_FOREACH_SAFE(var, head, field, next_var) \
153 for ((var) = ((head)->lh_first); \
154 (var) && ((next_var) = ((var)->field.le_next), 1); \
155 (var) = (next_var))
156
157
158
159
160#define QLIST_EMPTY(head) ((head)->lh_first == NULL)
161#define QLIST_FIRST(head) ((head)->lh_first)
162#define QLIST_NEXT(elm, field) ((elm)->field.le_next)
163
164
165
166
167
168#define QSLIST_HEAD(name, type) \
169struct name { \
170 struct type *slh_first; \
171}
172
173#define QSLIST_HEAD_INITIALIZER(head) \
174 { NULL }
175
176#define QSLIST_ENTRY(type) \
177struct { \
178 struct type *sle_next; \
179}
180
181
182
183
184#define QSLIST_INIT(head) do { \
185 (head)->slh_first = NULL; \
186} while (0)
187
188#define QSLIST_INSERT_AFTER(slistelm, elm, field) do { \
189 (elm)->field.sle_next = (slistelm)->field.sle_next; \
190 (slistelm)->field.sle_next = (elm); \
191} while (0)
192
193#define QSLIST_INSERT_HEAD(head, elm, field) do { \
194 (elm)->field.sle_next = (head)->slh_first; \
195 (head)->slh_first = (elm); \
196} while (0)
197
198#define QSLIST_INSERT_HEAD_ATOMIC(head, elm, field) do { \
199 typeof(elm) save_sle_next; \
200 do { \
201 save_sle_next = (elm)->field.sle_next = (head)->slh_first; \
202 } while (atomic_cmpxchg(&(head)->slh_first, save_sle_next, (elm)) != \
203 save_sle_next); \
204} while (0)
205
206#define QSLIST_MOVE_ATOMIC(dest, src) do { \
207 (dest)->slh_first = atomic_xchg(&(src)->slh_first, NULL); \
208} while (0)
209
210#define QSLIST_REMOVE_HEAD(head, field) do { \
211 (head)->slh_first = (head)->slh_first->field.sle_next; \
212} while (0)
213
214#define QSLIST_REMOVE_AFTER(slistelm, field) do { \
215 (slistelm)->field.sle_next = \
216 QSLIST_NEXT(QSLIST_NEXT((slistelm), field), field); \
217} while (0)
218
219#define QSLIST_FOREACH(var, head, field) \
220 for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
221
222#define QSLIST_FOREACH_SAFE(var, head, field, tvar) \
223 for ((var) = QSLIST_FIRST((head)); \
224 (var) && ((tvar) = QSLIST_NEXT((var), field), 1); \
225 (var) = (tvar))
226
227
228
229
230#define QSLIST_EMPTY(head) ((head)->slh_first == NULL)
231#define QSLIST_FIRST(head) ((head)->slh_first)
232#define QSLIST_NEXT(elm, field) ((elm)->field.sle_next)
233
234
235
236
237
238#define QSIMPLEQ_HEAD(name, type) \
239struct name { \
240 struct type *sqh_first; \
241 struct type **sqh_last; \
242}
243
244#define QSIMPLEQ_HEAD_INITIALIZER(head) \
245 { NULL, &(head).sqh_first }
246
247#define QSIMPLEQ_ENTRY(type) \
248struct { \
249 struct type *sqe_next; \
250}
251
252
253
254
255#define QSIMPLEQ_INIT(head) do { \
256 (head)->sqh_first = NULL; \
257 (head)->sqh_last = &(head)->sqh_first; \
258} while (0)
259
260#define QSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
261 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
262 (head)->sqh_last = &(elm)->field.sqe_next; \
263 (head)->sqh_first = (elm); \
264} while (0)
265
266#define QSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
267 (elm)->field.sqe_next = NULL; \
268 *(head)->sqh_last = (elm); \
269 (head)->sqh_last = &(elm)->field.sqe_next; \
270} while (0)
271
272#define QSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
273 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \
274 (head)->sqh_last = &(elm)->field.sqe_next; \
275 (listelm)->field.sqe_next = (elm); \
276} while (0)
277
278#define QSIMPLEQ_REMOVE_HEAD(head, field) do { \
279 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL)\
280 (head)->sqh_last = &(head)->sqh_first; \
281} while (0)
282
283#define QSIMPLEQ_SPLIT_AFTER(head, elm, field, removed) do { \
284 QSIMPLEQ_INIT(removed); \
285 if (((removed)->sqh_first = (head)->sqh_first) != NULL) { \
286 if (((head)->sqh_first = (elm)->field.sqe_next) == NULL) { \
287 (head)->sqh_last = &(head)->sqh_first; \
288 } \
289 (removed)->sqh_last = &(elm)->field.sqe_next; \
290 (elm)->field.sqe_next = NULL; \
291 } \
292} while (0)
293
294#define QSIMPLEQ_REMOVE(head, elm, type, field) do { \
295 if ((head)->sqh_first == (elm)) { \
296 QSIMPLEQ_REMOVE_HEAD((head), field); \
297 } else { \
298 struct type *curelm = (head)->sqh_first; \
299 while (curelm->field.sqe_next != (elm)) \
300 curelm = curelm->field.sqe_next; \
301 if ((curelm->field.sqe_next = \
302 curelm->field.sqe_next->field.sqe_next) == NULL) \
303 (head)->sqh_last = &(curelm)->field.sqe_next; \
304 } \
305} while (0)
306
307#define QSIMPLEQ_FOREACH(var, head, field) \
308 for ((var) = ((head)->sqh_first); \
309 (var); \
310 (var) = ((var)->field.sqe_next))
311
312#define QSIMPLEQ_FOREACH_SAFE(var, head, field, next) \
313 for ((var) = ((head)->sqh_first); \
314 (var) && ((next = ((var)->field.sqe_next)), 1); \
315 (var) = (next))
316
317#define QSIMPLEQ_CONCAT(head1, head2) do { \
318 if (!QSIMPLEQ_EMPTY((head2))) { \
319 *(head1)->sqh_last = (head2)->sqh_first; \
320 (head1)->sqh_last = (head2)->sqh_last; \
321 QSIMPLEQ_INIT((head2)); \
322 } \
323} while (0)
324
325#define QSIMPLEQ_PREPEND(head1, head2) do { \
326 if (!QSIMPLEQ_EMPTY((head2))) { \
327 *(head2)->sqh_last = (head1)->sqh_first; \
328 (head1)->sqh_first = (head2)->sqh_first; \
329 QSIMPLEQ_INIT((head2)); \
330 } \
331} while (0)
332
333#define QSIMPLEQ_LAST(head, type, field) \
334 (QSIMPLEQ_EMPTY((head)) ? \
335 NULL : \
336 ((struct type *)(void *) \
337 ((char *)((head)->sqh_last) - offsetof(struct type, field))))
338
339
340
341
342#define QSIMPLEQ_EMPTY_ATOMIC(head) (atomic_read(&((head)->sqh_first)) == NULL)
343#define QSIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL)
344#define QSIMPLEQ_FIRST(head) ((head)->sqh_first)
345#define QSIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
346
347typedef struct QTailQLink {
348 void *tql_next;
349 struct QTailQLink *tql_prev;
350} QTailQLink;
351
352
353
354
355
356#define QTAILQ_HEAD(name, type) \
357union name { \
358 struct type *tqh_first; \
359 QTailQLink tqh_circ; \
360}
361
362#define QTAILQ_HEAD_INITIALIZER(head) \
363 { .tqh_circ = { NULL, &(head).tqh_circ } }
364
365#define QTAILQ_ENTRY(type) \
366union { \
367 struct type *tqe_next; \
368 QTailQLink tqe_circ; \
369}
370
371
372
373
374#define QTAILQ_INIT(head) do { \
375 (head)->tqh_first = NULL; \
376 (head)->tqh_circ.tql_prev = &(head)->tqh_circ; \
377} while (0)
378
379#define QTAILQ_INSERT_HEAD(head, elm, field) do { \
380 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
381 (head)->tqh_first->field.tqe_circ.tql_prev = \
382 &(elm)->field.tqe_circ; \
383 else \
384 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
385 (head)->tqh_first = (elm); \
386 (elm)->field.tqe_circ.tql_prev = &(head)->tqh_circ; \
387} while (0)
388
389#define QTAILQ_INSERT_TAIL(head, elm, field) do { \
390 (elm)->field.tqe_next = NULL; \
391 (elm)->field.tqe_circ.tql_prev = (head)->tqh_circ.tql_prev; \
392 (head)->tqh_circ.tql_prev->tql_next = (elm); \
393 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
394} while (0)
395
396#define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
397 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
398 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
399 &(elm)->field.tqe_circ; \
400 else \
401 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
402 (listelm)->field.tqe_next = (elm); \
403 (elm)->field.tqe_circ.tql_prev = &(listelm)->field.tqe_circ; \
404} while (0)
405
406#define QTAILQ_INSERT_BEFORE(listelm, elm, field) do { \
407 (elm)->field.tqe_circ.tql_prev = (listelm)->field.tqe_circ.tql_prev; \
408 (elm)->field.tqe_next = (listelm); \
409 (listelm)->field.tqe_circ.tql_prev->tql_next = (elm); \
410 (listelm)->field.tqe_circ.tql_prev = &(elm)->field.tqe_circ; \
411} while (0)
412
413#define QTAILQ_REMOVE(head, elm, field) do { \
414 if (((elm)->field.tqe_next) != NULL) \
415 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
416 (elm)->field.tqe_circ.tql_prev; \
417 else \
418 (head)->tqh_circ.tql_prev = (elm)->field.tqe_circ.tql_prev; \
419 (elm)->field.tqe_circ.tql_prev->tql_next = (elm)->field.tqe_next; \
420 (elm)->field.tqe_circ.tql_prev = NULL; \
421} while (0)
422
423
424#define QTAILQ_REMOVE_SEVERAL(head, left, right, field) do { \
425 if (((right)->field.tqe_next) != NULL) \
426 (right)->field.tqe_next->field.tqe_circ.tql_prev = \
427 (left)->field.tqe_circ.tql_prev; \
428 else \
429 (head)->tqh_circ.tql_prev = (left)->field.tqe_circ.tql_prev; \
430 (left)->field.tqe_circ.tql_prev->tql_next = (right)->field.tqe_next; \
431 } while (0)
432
433#define QTAILQ_FOREACH(var, head, field) \
434 for ((var) = ((head)->tqh_first); \
435 (var); \
436 (var) = ((var)->field.tqe_next))
437
438#define QTAILQ_FOREACH_SAFE(var, head, field, next_var) \
439 for ((var) = ((head)->tqh_first); \
440 (var) && ((next_var) = ((var)->field.tqe_next), 1); \
441 (var) = (next_var))
442
443#define QTAILQ_FOREACH_REVERSE(var, head, field) \
444 for ((var) = QTAILQ_LAST(head); \
445 (var); \
446 (var) = QTAILQ_PREV(var, field))
447
448#define QTAILQ_FOREACH_REVERSE_SAFE(var, head, field, prev_var) \
449 for ((var) = QTAILQ_LAST(head); \
450 (var) && ((prev_var) = QTAILQ_PREV(var, field), 1); \
451 (var) = (prev_var))
452
453
454
455
456#define QTAILQ_EMPTY(head) ((head)->tqh_first == NULL)
457#define QTAILQ_FIRST(head) ((head)->tqh_first)
458#define QTAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
459#define QTAILQ_IN_USE(elm, field) ((elm)->field.tqe_circ.tql_prev != NULL)
460
461#define QTAILQ_LINK_PREV(link) \
462 ((link).tql_prev->tql_prev->tql_next)
463#define QTAILQ_LAST(head) \
464 ((typeof((head)->tqh_first)) QTAILQ_LINK_PREV((head)->tqh_circ))
465#define QTAILQ_PREV(elm, field) \
466 ((typeof((elm)->field.tqe_next)) QTAILQ_LINK_PREV((elm)->field.tqe_circ))
467
468#define field_at_offset(base, offset, type) \
469 ((type *) (((char *) (base)) + (offset)))
470
471
472
473
474
475#define QTAILQ_RAW_FIRST(head) \
476 field_at_offset(head, 0, void *)
477#define QTAILQ_RAW_TQH_CIRC(head) \
478 field_at_offset(head, 0, QTailQLink)
479
480
481
482
483#define QTAILQ_RAW_NEXT(elm, entry) \
484 field_at_offset(elm, entry, void *)
485#define QTAILQ_RAW_TQE_CIRC(elm, entry) \
486 field_at_offset(elm, entry, QTailQLink)
487
488
489
490#define QTAILQ_RAW_FOREACH(elm, head, entry) \
491 for ((elm) = *QTAILQ_RAW_FIRST(head); \
492 (elm); \
493 (elm) = *QTAILQ_RAW_NEXT(elm, entry))
494
495
496
497#define QTAILQ_RAW_INSERT_TAIL(head, elm, entry) do { \
498 *QTAILQ_RAW_NEXT(elm, entry) = NULL; \
499 QTAILQ_RAW_TQE_CIRC(elm, entry)->tql_prev = QTAILQ_RAW_TQH_CIRC(head)->tql_prev; \
500 QTAILQ_RAW_TQH_CIRC(head)->tql_prev->tql_next = (elm); \
501 QTAILQ_RAW_TQH_CIRC(head)->tql_prev = QTAILQ_RAW_TQE_CIRC(elm, entry); \
502} while (0)
503
504#endif
505