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 (atomic_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 = atomic_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) (atomic_read(&((head)->sqh_first)) == NULL)
380#define QSIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL)
381#define QSIMPLEQ_FIRST(head) ((head)->sqh_first)
382#define QSIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
383
384typedef struct QTailQLink {
385 void *tql_next;
386 struct QTailQLink *tql_prev;
387} QTailQLink;
388
389
390
391
392
393#define QTAILQ_HEAD(name, type) \
394union name { \
395 struct type *tqh_first; \
396 QTailQLink tqh_circ; \
397}
398
399#define QTAILQ_HEAD_INITIALIZER(head) \
400 { .tqh_circ = { NULL, &(head).tqh_circ } }
401
402#define QTAILQ_ENTRY(type) \
403union { \
404 struct type *tqe_next; \
405 QTailQLink tqe_circ; \
406}
407
408
409
410
411#define QTAILQ_INIT(head) do { \
412 (head)->tqh_first = NULL; \
413 (head)->tqh_circ.tql_prev = &(head)->tqh_circ; \
414} while (0)
415
416#define QTAILQ_INSERT_HEAD(head, elm, field) do { \
417 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
418 (head)->tqh_first->field.tqe_circ.tql_prev = \
419 &(elm)->field.tqe_circ; \
420 else \
421 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
422 (head)->tqh_first = (elm); \
423 (elm)->field.tqe_circ.tql_prev = &(head)->tqh_circ; \
424} while (0)
425
426#define QTAILQ_INSERT_TAIL(head, elm, field) do { \
427 (elm)->field.tqe_next = NULL; \
428 (elm)->field.tqe_circ.tql_prev = (head)->tqh_circ.tql_prev; \
429 (head)->tqh_circ.tql_prev->tql_next = (elm); \
430 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
431} while (0)
432
433#define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
434 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
435 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
436 &(elm)->field.tqe_circ; \
437 else \
438 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
439 (listelm)->field.tqe_next = (elm); \
440 (elm)->field.tqe_circ.tql_prev = &(listelm)->field.tqe_circ; \
441} while (0)
442
443#define QTAILQ_INSERT_BEFORE(listelm, elm, field) do { \
444 (elm)->field.tqe_circ.tql_prev = (listelm)->field.tqe_circ.tql_prev; \
445 (elm)->field.tqe_next = (listelm); \
446 (listelm)->field.tqe_circ.tql_prev->tql_next = (elm); \
447 (listelm)->field.tqe_circ.tql_prev = &(elm)->field.tqe_circ; \
448} while (0)
449
450#define QTAILQ_REMOVE(head, elm, field) do { \
451 if (((elm)->field.tqe_next) != NULL) \
452 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
453 (elm)->field.tqe_circ.tql_prev; \
454 else \
455 (head)->tqh_circ.tql_prev = (elm)->field.tqe_circ.tql_prev; \
456 (elm)->field.tqe_circ.tql_prev->tql_next = (elm)->field.tqe_next; \
457 (elm)->field.tqe_circ.tql_prev = NULL; \
458 (elm)->field.tqe_circ.tql_next = NULL; \
459 (elm)->field.tqe_next = NULL; \
460} while (0)
461
462
463#define QTAILQ_REMOVE_SEVERAL(head, left, right, field) do { \
464 if (((right)->field.tqe_next) != NULL) \
465 (right)->field.tqe_next->field.tqe_circ.tql_prev = \
466 (left)->field.tqe_circ.tql_prev; \
467 else \
468 (head)->tqh_circ.tql_prev = (left)->field.tqe_circ.tql_prev; \
469 (left)->field.tqe_circ.tql_prev->tql_next = (right)->field.tqe_next; \
470 } while (0)
471
472#define QTAILQ_FOREACH(var, head, field) \
473 for ((var) = ((head)->tqh_first); \
474 (var); \
475 (var) = ((var)->field.tqe_next))
476
477#define QTAILQ_FOREACH_SAFE(var, head, field, next_var) \
478 for ((var) = ((head)->tqh_first); \
479 (var) && ((next_var) = ((var)->field.tqe_next), 1); \
480 (var) = (next_var))
481
482#define QTAILQ_FOREACH_REVERSE(var, head, field) \
483 for ((var) = QTAILQ_LAST(head); \
484 (var); \
485 (var) = QTAILQ_PREV(var, field))
486
487#define QTAILQ_FOREACH_REVERSE_SAFE(var, head, field, prev_var) \
488 for ((var) = QTAILQ_LAST(head); \
489 (var) && ((prev_var) = QTAILQ_PREV(var, field), 1); \
490 (var) = (prev_var))
491
492
493
494
495#define QTAILQ_EMPTY(head) ((head)->tqh_first == NULL)
496#define QTAILQ_FIRST(head) ((head)->tqh_first)
497#define QTAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
498#define QTAILQ_IN_USE(elm, field) ((elm)->field.tqe_circ.tql_prev != NULL)
499
500#define QTAILQ_LINK_PREV(link) \
501 ((link).tql_prev->tql_prev->tql_next)
502#define QTAILQ_LAST(head) \
503 ((typeof((head)->tqh_first)) QTAILQ_LINK_PREV((head)->tqh_circ))
504#define QTAILQ_PREV(elm, field) \
505 ((typeof((elm)->field.tqe_next)) QTAILQ_LINK_PREV((elm)->field.tqe_circ))
506
507#define field_at_offset(base, offset, type) \
508 ((type *) (((char *) (base)) + (offset)))
509
510
511
512
513
514#define QTAILQ_RAW_FIRST(head) \
515 field_at_offset(head, 0, void *)
516#define QTAILQ_RAW_TQH_CIRC(head) \
517 field_at_offset(head, 0, QTailQLink)
518
519
520
521
522#define QTAILQ_RAW_NEXT(elm, entry) \
523 field_at_offset(elm, entry, void *)
524#define QTAILQ_RAW_TQE_CIRC(elm, entry) \
525 field_at_offset(elm, entry, QTailQLink)
526
527
528
529#define QTAILQ_RAW_FOREACH(elm, head, entry) \
530 for ((elm) = *QTAILQ_RAW_FIRST(head); \
531 (elm); \
532 (elm) = *QTAILQ_RAW_NEXT(elm, entry))
533
534
535
536#define QTAILQ_RAW_INSERT_TAIL(head, elm, entry) do { \
537 *QTAILQ_RAW_NEXT(elm, entry) = NULL; \
538 QTAILQ_RAW_TQE_CIRC(elm, entry)->tql_prev = QTAILQ_RAW_TQH_CIRC(head)->tql_prev; \
539 QTAILQ_RAW_TQH_CIRC(head)->tql_prev->tql_next = (elm); \
540 QTAILQ_RAW_TQH_CIRC(head)->tql_prev = QTAILQ_RAW_TQE_CIRC(elm, entry); \
541} while (0)
542
543#define QLIST_RAW_FIRST(head) \
544 field_at_offset(head, 0, void *)
545
546#define QLIST_RAW_NEXT(elm, entry) \
547 field_at_offset(elm, entry, void *)
548
549#define QLIST_RAW_PREVIOUS(elm, entry) \
550 field_at_offset(elm, entry + sizeof(void *), void *)
551
552#define QLIST_RAW_FOREACH(elm, head, entry) \
553 for ((elm) = *QLIST_RAW_FIRST(head); \
554 (elm); \
555 (elm) = *QLIST_RAW_NEXT(elm, entry))
556
557#define QLIST_RAW_INSERT_AFTER(head, prev, elem, entry) do { \
558 *QLIST_RAW_NEXT(prev, entry) = elem; \
559 *QLIST_RAW_PREVIOUS(elem, entry) = QLIST_RAW_NEXT(prev, entry); \
560 *QLIST_RAW_NEXT(elem, entry) = NULL; \
561} while (0)
562
563#define QLIST_RAW_INSERT_HEAD(head, elm, entry) do { \
564 void *first = *QLIST_RAW_FIRST(head); \
565 *QLIST_RAW_FIRST(head) = elm; \
566 *QLIST_RAW_PREVIOUS(elm, entry) = QLIST_RAW_FIRST(head); \
567 if (first) { \
568 *QLIST_RAW_NEXT(elm, entry) = first; \
569 *QLIST_RAW_PREVIOUS(first, entry) = QLIST_RAW_NEXT(elm, entry); \
570 } else { \
571 *QLIST_RAW_NEXT(elm, entry) = NULL; \
572 } \
573} while (0)
574
575#endif
576