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 (elm)->field.le_next = NULL; \
146 (elm)->field.le_prev = NULL; \
147} while (0)
148
149
150
151
152#define QLIST_SAFE_REMOVE(elm, field) do { \
153 if ((elm)->field.le_prev != NULL) { \
154 if ((elm)->field.le_next != NULL) \
155 (elm)->field.le_next->field.le_prev = \
156 (elm)->field.le_prev; \
157 *(elm)->field.le_prev = (elm)->field.le_next; \
158 (elm)->field.le_next = NULL; \
159 (elm)->field.le_prev = NULL; \
160 } \
161} while (0)
162
163
164#define QLIST_IS_INSERTED(elm, field) ((elm)->field.le_prev != NULL)
165
166#define QLIST_FOREACH(var, head, field) \
167 for ((var) = ((head)->lh_first); \
168 (var); \
169 (var) = ((var)->field.le_next))
170
171#define QLIST_FOREACH_SAFE(var, head, field, next_var) \
172 for ((var) = ((head)->lh_first); \
173 (var) && ((next_var) = ((var)->field.le_next), 1); \
174 (var) = (next_var))
175
176
177
178
179#define QLIST_EMPTY(head) ((head)->lh_first == NULL)
180#define QLIST_FIRST(head) ((head)->lh_first)
181#define QLIST_NEXT(elm, field) ((elm)->field.le_next)
182
183
184
185
186
187#define QSLIST_HEAD(name, type) \
188struct name { \
189 struct type *slh_first; \
190}
191
192#define QSLIST_HEAD_INITIALIZER(head) \
193 { NULL }
194
195#define QSLIST_ENTRY(type) \
196struct { \
197 struct type *sle_next; \
198}
199
200
201
202
203#define QSLIST_INIT(head) do { \
204 (head)->slh_first = NULL; \
205} while (0)
206
207#define QSLIST_INSERT_AFTER(slistelm, elm, field) do { \
208 (elm)->field.sle_next = (slistelm)->field.sle_next; \
209 (slistelm)->field.sle_next = (elm); \
210} while (0)
211
212#define QSLIST_INSERT_HEAD(head, elm, field) do { \
213 (elm)->field.sle_next = (head)->slh_first; \
214 (head)->slh_first = (elm); \
215} while (0)
216
217#define QSLIST_INSERT_HEAD_ATOMIC(head, elm, field) do { \
218 typeof(elm) save_sle_next; \
219 do { \
220 save_sle_next = (elm)->field.sle_next = (head)->slh_first; \
221 } while (qatomic_cmpxchg(&(head)->slh_first, save_sle_next, (elm)) !=\
222 save_sle_next); \
223} while (0)
224
225#define QSLIST_MOVE_ATOMIC(dest, src) do { \
226 (dest)->slh_first = qatomic_xchg(&(src)->slh_first, NULL); \
227} while (0)
228
229#define QSLIST_REMOVE_HEAD(head, field) do { \
230 typeof((head)->slh_first) elm = (head)->slh_first; \
231 (head)->slh_first = elm->field.sle_next; \
232 elm->field.sle_next = NULL; \
233} while (0)
234
235#define QSLIST_REMOVE_AFTER(slistelm, field) do { \
236 typeof(slistelm) next = (slistelm)->field.sle_next; \
237 (slistelm)->field.sle_next = next->field.sle_next; \
238 next->field.sle_next = NULL; \
239} while (0)
240
241#define QSLIST_REMOVE(head, elm, type, field) do { \
242 if ((head)->slh_first == (elm)) { \
243 QSLIST_REMOVE_HEAD((head), field); \
244 } else { \
245 struct type *curelm = (head)->slh_first; \
246 while (curelm->field.sle_next != (elm)) \
247 curelm = curelm->field.sle_next; \
248 curelm->field.sle_next = curelm->field.sle_next->field.sle_next; \
249 (elm)->field.sle_next = NULL; \
250 } \
251} while (0)
252
253#define QSLIST_FOREACH(var, head, field) \
254 for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
255
256#define QSLIST_FOREACH_SAFE(var, head, field, tvar) \
257 for ((var) = QSLIST_FIRST((head)); \
258 (var) && ((tvar) = QSLIST_NEXT((var), field), 1); \
259 (var) = (tvar))
260
261
262
263
264#define QSLIST_EMPTY(head) ((head)->slh_first == NULL)
265#define QSLIST_FIRST(head) ((head)->slh_first)
266#define QSLIST_NEXT(elm, field) ((elm)->field.sle_next)
267
268
269
270
271
272#define QSIMPLEQ_HEAD(name, type) \
273struct name { \
274 struct type *sqh_first; \
275 struct type **sqh_last; \
276}
277
278#define QSIMPLEQ_HEAD_INITIALIZER(head) \
279 { NULL, &(head).sqh_first }
280
281#define QSIMPLEQ_ENTRY(type) \
282struct { \
283 struct type *sqe_next; \
284}
285
286
287
288
289#define QSIMPLEQ_INIT(head) do { \
290 (head)->sqh_first = NULL; \
291 (head)->sqh_last = &(head)->sqh_first; \
292} while (0)
293
294#define QSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
295 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
296 (head)->sqh_last = &(elm)->field.sqe_next; \
297 (head)->sqh_first = (elm); \
298} while (0)
299
300#define QSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
301 (elm)->field.sqe_next = NULL; \
302 *(head)->sqh_last = (elm); \
303 (head)->sqh_last = &(elm)->field.sqe_next; \
304} while (0)
305
306#define QSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
307 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \
308 (head)->sqh_last = &(elm)->field.sqe_next; \
309 (listelm)->field.sqe_next = (elm); \
310} while (0)
311
312#define QSIMPLEQ_REMOVE_HEAD(head, field) do { \
313 typeof((head)->sqh_first) elm = (head)->sqh_first; \
314 if (((head)->sqh_first = elm->field.sqe_next) == NULL) \
315 (head)->sqh_last = &(head)->sqh_first; \
316 elm->field.sqe_next = NULL; \
317} while (0)
318
319#define QSIMPLEQ_SPLIT_AFTER(head, elm, field, removed) do { \
320 QSIMPLEQ_INIT(removed); \
321 if (((removed)->sqh_first = (head)->sqh_first) != NULL) { \
322 if (((head)->sqh_first = (elm)->field.sqe_next) == NULL) { \
323 (head)->sqh_last = &(head)->sqh_first; \
324 } \
325 (removed)->sqh_last = &(elm)->field.sqe_next; \
326 (elm)->field.sqe_next = NULL; \
327 } \
328} while (0)
329
330#define QSIMPLEQ_REMOVE(head, elm, type, field) do { \
331 if ((head)->sqh_first == (elm)) { \
332 QSIMPLEQ_REMOVE_HEAD((head), field); \
333 } else { \
334 struct type *curelm = (head)->sqh_first; \
335 while (curelm->field.sqe_next != (elm)) \
336 curelm = curelm->field.sqe_next; \
337 if ((curelm->field.sqe_next = \
338 curelm->field.sqe_next->field.sqe_next) == NULL) \
339 (head)->sqh_last = &(curelm)->field.sqe_next; \
340 (elm)->field.sqe_next = NULL; \
341 } \
342} while (0)
343
344#define QSIMPLEQ_FOREACH(var, head, field) \
345 for ((var) = ((head)->sqh_first); \
346 (var); \
347 (var) = ((var)->field.sqe_next))
348
349#define QSIMPLEQ_FOREACH_SAFE(var, head, field, next) \
350 for ((var) = ((head)->sqh_first); \
351 (var) && ((next = ((var)->field.sqe_next)), 1); \
352 (var) = (next))
353
354#define QSIMPLEQ_CONCAT(head1, head2) do { \
355 if (!QSIMPLEQ_EMPTY((head2))) { \
356 *(head1)->sqh_last = (head2)->sqh_first; \
357 (head1)->sqh_last = (head2)->sqh_last; \
358 QSIMPLEQ_INIT((head2)); \
359 } \
360} while (0)
361
362#define QSIMPLEQ_PREPEND(head1, head2) do { \
363 if (!QSIMPLEQ_EMPTY((head2))) { \
364 *(head2)->sqh_last = (head1)->sqh_first; \
365 (head1)->sqh_first = (head2)->sqh_first; \
366 QSIMPLEQ_INIT((head2)); \
367 } \
368} while (0)
369
370#define QSIMPLEQ_LAST(head, type, field) \
371 (QSIMPLEQ_EMPTY((head)) ? \
372 NULL : \
373 ((struct type *)(void *) \
374 ((char *)((head)->sqh_last) - offsetof(struct type, field))))
375
376
377
378
379#define QSIMPLEQ_EMPTY_ATOMIC(head) \
380 (qatomic_read(&((head)->sqh_first)) == NULL)
381#define QSIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL)
382#define QSIMPLEQ_FIRST(head) ((head)->sqh_first)
383#define QSIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
384
385typedef struct QTailQLink {
386 void *tql_next;
387 struct QTailQLink *tql_prev;
388} QTailQLink;
389
390
391
392
393
394#define QTAILQ_HEAD(name, type) \
395union name { \
396 struct type *tqh_first; \
397 QTailQLink tqh_circ; \
398}
399
400#define QTAILQ_HEAD_INITIALIZER(head) \
401 { .tqh_circ = { NULL, &(head).tqh_circ } }
402
403#define QTAILQ_ENTRY(type) \
404union { \
405 struct type *tqe_next; \
406 QTailQLink tqe_circ; \
407}
408
409
410
411
412#define QTAILQ_INIT(head) do { \
413 (head)->tqh_first = NULL; \
414 (head)->tqh_circ.tql_prev = &(head)->tqh_circ; \
415} while (0)
416
417#define QTAILQ_INSERT_HEAD(head, elm, field) do { \
418 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
419 (head)->tqh_first->field.tqe_circ.tql_prev = \
420 &(elm)->field.tqe_circ; \
421 else \
422 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
423 (head)->tqh_first = (elm); \
424 (elm)->field.tqe_circ.tql_prev = &(head)->tqh_circ; \
425} while (0)
426
427#define QTAILQ_INSERT_TAIL(head, elm, field) do { \
428 (elm)->field.tqe_next = NULL; \
429 (elm)->field.tqe_circ.tql_prev = (head)->tqh_circ.tql_prev; \
430 (head)->tqh_circ.tql_prev->tql_next = (elm); \
431 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
432} while (0)
433
434#define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
435 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
436 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
437 &(elm)->field.tqe_circ; \
438 else \
439 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
440 (listelm)->field.tqe_next = (elm); \
441 (elm)->field.tqe_circ.tql_prev = &(listelm)->field.tqe_circ; \
442} while (0)
443
444#define QTAILQ_INSERT_BEFORE(listelm, elm, field) do { \
445 (elm)->field.tqe_circ.tql_prev = (listelm)->field.tqe_circ.tql_prev; \
446 (elm)->field.tqe_next = (listelm); \
447 (listelm)->field.tqe_circ.tql_prev->tql_next = (elm); \
448 (listelm)->field.tqe_circ.tql_prev = &(elm)->field.tqe_circ; \
449} while (0)
450
451#define QTAILQ_REMOVE(head, elm, field) do { \
452 if (((elm)->field.tqe_next) != NULL) \
453 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
454 (elm)->field.tqe_circ.tql_prev; \
455 else \
456 (head)->tqh_circ.tql_prev = (elm)->field.tqe_circ.tql_prev; \
457 (elm)->field.tqe_circ.tql_prev->tql_next = (elm)->field.tqe_next; \
458 (elm)->field.tqe_circ.tql_prev = NULL; \
459 (elm)->field.tqe_circ.tql_next = NULL; \
460 (elm)->field.tqe_next = NULL; \
461} while (0)
462
463
464#define QTAILQ_REMOVE_SEVERAL(head, left, right, field) do { \
465 if (((right)->field.tqe_next) != NULL) \
466 (right)->field.tqe_next->field.tqe_circ.tql_prev = \
467 (left)->field.tqe_circ.tql_prev; \
468 else \
469 (head)->tqh_circ.tql_prev = (left)->field.tqe_circ.tql_prev; \
470 (left)->field.tqe_circ.tql_prev->tql_next = (right)->field.tqe_next; \
471 } while (0)
472
473#define QTAILQ_FOREACH(var, head, field) \
474 for ((var) = ((head)->tqh_first); \
475 (var); \
476 (var) = ((var)->field.tqe_next))
477
478#define QTAILQ_FOREACH_SAFE(var, head, field, next_var) \
479 for ((var) = ((head)->tqh_first); \
480 (var) && ((next_var) = ((var)->field.tqe_next), 1); \
481 (var) = (next_var))
482
483#define QTAILQ_FOREACH_REVERSE(var, head, field) \
484 for ((var) = QTAILQ_LAST(head); \
485 (var); \
486 (var) = QTAILQ_PREV(var, field))
487
488#define QTAILQ_FOREACH_REVERSE_SAFE(var, head, field, prev_var) \
489 for ((var) = QTAILQ_LAST(head); \
490 (var) && ((prev_var) = QTAILQ_PREV(var, field), 1); \
491 (var) = (prev_var))
492
493
494
495
496#define QTAILQ_EMPTY(head) ((head)->tqh_first == NULL)
497#define QTAILQ_FIRST(head) ((head)->tqh_first)
498#define QTAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
499#define QTAILQ_IN_USE(elm, field) ((elm)->field.tqe_circ.tql_prev != NULL)
500
501#define QTAILQ_LINK_PREV(link) \
502 ((link).tql_prev->tql_prev->tql_next)
503#define QTAILQ_LAST(head) \
504 ((typeof((head)->tqh_first)) QTAILQ_LINK_PREV((head)->tqh_circ))
505#define QTAILQ_PREV(elm, field) \
506 ((typeof((elm)->field.tqe_next)) QTAILQ_LINK_PREV((elm)->field.tqe_circ))
507
508#define field_at_offset(base, offset, type) \
509 ((type *) (((char *) (base)) + (offset)))
510
511
512
513
514
515#define QTAILQ_RAW_FIRST(head) \
516 field_at_offset(head, 0, void *)
517#define QTAILQ_RAW_TQH_CIRC(head) \
518 field_at_offset(head, 0, QTailQLink)
519
520
521
522
523#define QTAILQ_RAW_NEXT(elm, entry) \
524 field_at_offset(elm, entry, void *)
525#define QTAILQ_RAW_TQE_CIRC(elm, entry) \
526 field_at_offset(elm, entry, QTailQLink)
527
528
529
530#define QTAILQ_RAW_FOREACH(elm, head, entry) \
531 for ((elm) = *QTAILQ_RAW_FIRST(head); \
532 (elm); \
533 (elm) = *QTAILQ_RAW_NEXT(elm, entry))
534
535
536
537#define QTAILQ_RAW_INSERT_TAIL(head, elm, entry) do { \
538 *QTAILQ_RAW_NEXT(elm, entry) = NULL; \
539 QTAILQ_RAW_TQE_CIRC(elm, entry)->tql_prev = QTAILQ_RAW_TQH_CIRC(head)->tql_prev; \
540 QTAILQ_RAW_TQH_CIRC(head)->tql_prev->tql_next = (elm); \
541 QTAILQ_RAW_TQH_CIRC(head)->tql_prev = QTAILQ_RAW_TQE_CIRC(elm, entry); \
542} while (0)
543
544#define QLIST_RAW_FIRST(head) \
545 field_at_offset(head, 0, void *)
546
547#define QLIST_RAW_NEXT(elm, entry) \
548 field_at_offset(elm, entry, void *)
549
550#define QLIST_RAW_PREVIOUS(elm, entry) \
551 field_at_offset(elm, entry + sizeof(void *), void *)
552
553#define QLIST_RAW_FOREACH(elm, head, entry) \
554 for ((elm) = *QLIST_RAW_FIRST(head); \
555 (elm); \
556 (elm) = *QLIST_RAW_NEXT(elm, entry))
557
558#define QLIST_RAW_INSERT_AFTER(head, prev, elem, entry) do { \
559 *QLIST_RAW_NEXT(prev, entry) = elem; \
560 *QLIST_RAW_PREVIOUS(elem, entry) = QLIST_RAW_NEXT(prev, entry); \
561 *QLIST_RAW_NEXT(elem, entry) = NULL; \
562} while (0)
563
564#define QLIST_RAW_INSERT_HEAD(head, elm, entry) do { \
565 void *first = *QLIST_RAW_FIRST(head); \
566 *QLIST_RAW_FIRST(head) = elm; \
567 *QLIST_RAW_PREVIOUS(elm, entry) = QLIST_RAW_FIRST(head); \
568 if (first) { \
569 *QLIST_RAW_NEXT(elm, entry) = first; \
570 *QLIST_RAW_PREVIOUS(first, entry) = QLIST_RAW_NEXT(elm, entry); \
571 } else { \
572 *QLIST_RAW_NEXT(elm, entry) = NULL; \
573 } \
574} while (0)
575
576#endif
577