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(head) ((head)->sqh_first == NULL)
345#define QSIMPLEQ_FIRST(head) ((head)->sqh_first)
346#define QSIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
347
348
349
350
351
352#define Q_TAILQ_HEAD(name, type, qual) \
353struct name { \
354 qual type *tqh_first; \
355 qual type *qual *tqh_last; \
356}
357#define QTAILQ_HEAD(name, type) Q_TAILQ_HEAD(name, struct type,)
358
359#define QTAILQ_HEAD_INITIALIZER(head) \
360 { NULL, &(head).tqh_first }
361
362#define Q_TAILQ_ENTRY(type, qual) \
363struct { \
364 qual type *tqe_next; \
365 qual type *qual *tqe_prev; \
366}
367#define QTAILQ_ENTRY(type) Q_TAILQ_ENTRY(struct type,)
368
369
370
371
372#define QTAILQ_INIT(head) do { \
373 (head)->tqh_first = NULL; \
374 (head)->tqh_last = &(head)->tqh_first; \
375} while (0)
376
377#define QTAILQ_INSERT_HEAD(head, elm, field) do { \
378 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
379 (head)->tqh_first->field.tqe_prev = \
380 &(elm)->field.tqe_next; \
381 else \
382 (head)->tqh_last = &(elm)->field.tqe_next; \
383 (head)->tqh_first = (elm); \
384 (elm)->field.tqe_prev = &(head)->tqh_first; \
385} while (0)
386
387#define QTAILQ_INSERT_TAIL(head, elm, field) do { \
388 (elm)->field.tqe_next = NULL; \
389 (elm)->field.tqe_prev = (head)->tqh_last; \
390 *(head)->tqh_last = (elm); \
391 (head)->tqh_last = &(elm)->field.tqe_next; \
392} while (0)
393
394#define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
395 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
396 (elm)->field.tqe_next->field.tqe_prev = \
397 &(elm)->field.tqe_next; \
398 else \
399 (head)->tqh_last = &(elm)->field.tqe_next; \
400 (listelm)->field.tqe_next = (elm); \
401 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
402} while (0)
403
404#define QTAILQ_INSERT_BEFORE(listelm, elm, field) do { \
405 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
406 (elm)->field.tqe_next = (listelm); \
407 *(listelm)->field.tqe_prev = (elm); \
408 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
409} while (0)
410
411#define QTAILQ_REMOVE(head, elm, field) do { \
412 if (((elm)->field.tqe_next) != NULL) \
413 (elm)->field.tqe_next->field.tqe_prev = \
414 (elm)->field.tqe_prev; \
415 else \
416 (head)->tqh_last = (elm)->field.tqe_prev; \
417 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
418 (elm)->field.tqe_prev = NULL; \
419} while (0)
420
421#define QTAILQ_FOREACH(var, head, field) \
422 for ((var) = ((head)->tqh_first); \
423 (var); \
424 (var) = ((var)->field.tqe_next))
425
426#define QTAILQ_FOREACH_SAFE(var, head, field, next_var) \
427 for ((var) = ((head)->tqh_first); \
428 (var) && ((next_var) = ((var)->field.tqe_next), 1); \
429 (var) = (next_var))
430
431#define QTAILQ_FOREACH_REVERSE(var, head, headname, field) \
432 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \
433 (var); \
434 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
435
436#define QTAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev_var) \
437 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \
438 (var) && ((prev_var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)), 1); \
439 (var) = (prev_var))
440
441
442
443
444#define QTAILQ_EMPTY(head) ((head)->tqh_first == NULL)
445#define QTAILQ_FIRST(head) ((head)->tqh_first)
446#define QTAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
447#define QTAILQ_IN_USE(elm, field) ((elm)->field.tqe_prev != NULL)
448
449#define QTAILQ_LAST(head, headname) \
450 (*(((struct headname *)((head)->tqh_last))->tqh_last))
451#define QTAILQ_PREV(elm, headname, field) \
452 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
453
454#define field_at_offset(base, offset, type) \
455 ((type) (((char *) (base)) + (offset)))
456
457typedef struct DUMMY_Q_ENTRY DUMMY_Q_ENTRY;
458typedef struct DUMMY_Q DUMMY_Q;
459
460struct DUMMY_Q_ENTRY {
461 QTAILQ_ENTRY(DUMMY_Q_ENTRY) next;
462};
463
464struct DUMMY_Q {
465 QTAILQ_HEAD(DUMMY_Q_HEAD, DUMMY_Q_ENTRY) head;
466};
467
468#define dummy_q ((DUMMY_Q *) 0)
469#define dummy_qe ((DUMMY_Q_ENTRY *) 0)
470
471
472
473
474#define QTAILQ_FIRST_OFFSET (offsetof(typeof(dummy_q->head), tqh_first))
475#define QTAILQ_LAST_OFFSET (offsetof(typeof(dummy_q->head), tqh_last))
476
477
478
479#define QTAILQ_RAW_FIRST(head) \
480 (*field_at_offset(head, QTAILQ_FIRST_OFFSET, void **))
481#define QTAILQ_RAW_TQH_LAST(head) \
482 (*field_at_offset(head, QTAILQ_LAST_OFFSET, void ***))
483
484
485
486
487#define QTAILQ_NEXT_OFFSET (offsetof(typeof(dummy_qe->next), tqe_next))
488#define QTAILQ_PREV_OFFSET (offsetof(typeof(dummy_qe->next), tqe_prev))
489
490
491
492
493#define QTAILQ_RAW_NEXT(elm, entry) \
494 (*field_at_offset(elm, entry + QTAILQ_NEXT_OFFSET, void **))
495#define QTAILQ_RAW_TQE_PREV(elm, entry) \
496 (*field_at_offset(elm, entry + QTAILQ_PREV_OFFSET, void ***))
497
498
499
500#define QTAILQ_RAW_FOREACH(elm, head, entry) \
501 for ((elm) = QTAILQ_RAW_FIRST(head); \
502 (elm); \
503 (elm) = QTAILQ_RAW_NEXT(elm, entry))
504
505
506
507#define QTAILQ_RAW_INSERT_TAIL(head, elm, entry) do { \
508 QTAILQ_RAW_NEXT(elm, entry) = NULL; \
509 QTAILQ_RAW_TQE_PREV(elm, entry) = QTAILQ_RAW_TQH_LAST(head); \
510 *QTAILQ_RAW_TQH_LAST(head) = (elm); \
511 QTAILQ_RAW_TQH_LAST(head) = &QTAILQ_RAW_NEXT(elm, entry); \
512} while (0)
513
514#endif
515