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_PREPEND(head1, head2) do { \
328 if (!QSIMPLEQ_EMPTY((head2))) { \
329 *(head2)->sqh_last = (head1)->sqh_first; \
330 (head1)->sqh_first = (head2)->sqh_first; \
331 QSIMPLEQ_INIT((head2)); \
332 } \
333} while (0)
334
335#define QSIMPLEQ_LAST(head, type, field) \
336 (QSIMPLEQ_EMPTY((head)) ? \
337 NULL : \
338 ((struct type *)(void *) \
339 ((char *)((head)->sqh_last) - offsetof(struct type, field))))
340
341
342
343
344#define QSIMPLEQ_EMPTY_ATOMIC(head) (atomic_read(&((head)->sqh_first)) == NULL)
345#define QSIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL)
346#define QSIMPLEQ_FIRST(head) ((head)->sqh_first)
347#define QSIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
348
349typedef struct QTailQLink {
350 void *tql_next;
351 struct QTailQLink *tql_prev;
352} QTailQLink;
353
354
355
356
357
358#define QTAILQ_HEAD(name, type) \
359union name { \
360 struct type *tqh_first; \
361 QTailQLink tqh_circ; \
362}
363
364#define QTAILQ_HEAD_INITIALIZER(head) \
365 { .tqh_circ = { NULL, &(head).tqh_circ } }
366
367#define QTAILQ_ENTRY(type) \
368union { \
369 struct type *tqe_next; \
370 QTailQLink tqe_circ; \
371}
372
373
374
375
376#define QTAILQ_INIT(head) do { \
377 (head)->tqh_first = NULL; \
378 (head)->tqh_circ.tql_prev = &(head)->tqh_circ; \
379} while (0)
380
381#define QTAILQ_INSERT_HEAD(head, elm, field) do { \
382 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
383 (head)->tqh_first->field.tqe_circ.tql_prev = \
384 &(elm)->field.tqe_circ; \
385 else \
386 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
387 (head)->tqh_first = (elm); \
388 (elm)->field.tqe_circ.tql_prev = &(head)->tqh_circ; \
389} while (0)
390
391#define QTAILQ_INSERT_TAIL(head, elm, field) do { \
392 (elm)->field.tqe_next = NULL; \
393 (elm)->field.tqe_circ.tql_prev = (head)->tqh_circ.tql_prev; \
394 (head)->tqh_circ.tql_prev->tql_next = (elm); \
395 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
396} while (0)
397
398#define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
399 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
400 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
401 &(elm)->field.tqe_circ; \
402 else \
403 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
404 (listelm)->field.tqe_next = (elm); \
405 (elm)->field.tqe_circ.tql_prev = &(listelm)->field.tqe_circ; \
406} while (0)
407
408#define QTAILQ_INSERT_BEFORE(listelm, elm, field) do { \
409 (elm)->field.tqe_circ.tql_prev = (listelm)->field.tqe_circ.tql_prev; \
410 (elm)->field.tqe_next = (listelm); \
411 (listelm)->field.tqe_circ.tql_prev->tql_next = (elm); \
412 (listelm)->field.tqe_circ.tql_prev = &(elm)->field.tqe_circ; \
413} while (0)
414
415#define QTAILQ_REMOVE(head, elm, field) do { \
416 if (((elm)->field.tqe_next) != NULL) \
417 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
418 (elm)->field.tqe_circ.tql_prev; \
419 else \
420 (head)->tqh_circ.tql_prev = (elm)->field.tqe_circ.tql_prev; \
421 (elm)->field.tqe_circ.tql_prev->tql_next = (elm)->field.tqe_next; \
422 (elm)->field.tqe_circ.tql_prev = NULL; \
423} while (0)
424
425#define QTAILQ_FOREACH(var, head, field) \
426 for ((var) = ((head)->tqh_first); \
427 (var); \
428 (var) = ((var)->field.tqe_next))
429
430#define QTAILQ_FOREACH_SAFE(var, head, field, next_var) \
431 for ((var) = ((head)->tqh_first); \
432 (var) && ((next_var) = ((var)->field.tqe_next), 1); \
433 (var) = (next_var))
434
435#define QTAILQ_FOREACH_REVERSE(var, head, field) \
436 for ((var) = QTAILQ_LAST(head); \
437 (var); \
438 (var) = QTAILQ_PREV(var, field))
439
440#define QTAILQ_FOREACH_REVERSE_SAFE(var, head, field, prev_var) \
441 for ((var) = QTAILQ_LAST(head); \
442 (var) && ((prev_var) = QTAILQ_PREV(var, field), 1); \
443 (var) = (prev_var))
444
445
446
447
448#define QTAILQ_EMPTY(head) ((head)->tqh_first == NULL)
449#define QTAILQ_FIRST(head) ((head)->tqh_first)
450#define QTAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
451#define QTAILQ_IN_USE(elm, field) ((elm)->field.tqe_circ.tql_prev != NULL)
452
453#define QTAILQ_LINK_PREV(link) \
454 ((link).tql_prev->tql_prev->tql_next)
455#define QTAILQ_LAST(head) \
456 ((typeof((head)->tqh_first)) QTAILQ_LINK_PREV((head)->tqh_circ))
457#define QTAILQ_PREV(elm, field) \
458 ((typeof((elm)->field.tqe_next)) QTAILQ_LINK_PREV((elm)->field.tqe_circ))
459
460#define field_at_offset(base, offset, type) \
461 ((type *) (((char *) (base)) + (offset)))
462
463
464
465
466
467#define QTAILQ_RAW_FIRST(head) \
468 field_at_offset(head, 0, void *)
469#define QTAILQ_RAW_TQH_CIRC(head) \
470 field_at_offset(head, 0, QTailQLink)
471
472
473
474
475#define QTAILQ_RAW_NEXT(elm, entry) \
476 field_at_offset(elm, entry, void *)
477#define QTAILQ_RAW_TQE_CIRC(elm, entry) \
478 field_at_offset(elm, entry, QTailQLink)
479
480
481
482#define QTAILQ_RAW_FOREACH(elm, head, entry) \
483 for ((elm) = *QTAILQ_RAW_FIRST(head); \
484 (elm); \
485 (elm) = *QTAILQ_RAW_NEXT(elm, entry))
486
487
488
489#define QTAILQ_RAW_INSERT_TAIL(head, elm, entry) do { \
490 *QTAILQ_RAW_NEXT(elm, entry) = NULL; \
491 QTAILQ_RAW_TQE_CIRC(elm, entry)->tql_prev = QTAILQ_RAW_TQH_CIRC(head)->tql_prev; \
492 QTAILQ_RAW_TQH_CIRC(head)->tql_prev->tql_next = (elm); \
493 QTAILQ_RAW_TQH_CIRC(head)->tql_prev = QTAILQ_RAW_TQE_CIRC(elm, entry); \
494} while (0)
495
496#endif
497