]> git.proxmox.com Git - mirror_qemu.git/blame - include/qemu/queue.h
projects / mirror_qemu.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
util/reserved-region: Add new ReservedRegion helpers
[mirror_qemu.git] / include / qemu / queue.h
CommitLineData
c616bbe1 1/* $NetBSD: queue.h,v 1.52 2009/04/20 09:56:08 mschuett Exp $ */
fc56ef08
BS		 2
3/*
5cbdb3a3 4 * QEMU version: Copy from netbsd, removed debug code, removed some of
6095aa88 5 * the implementations. Left in singly-linked lists, lists, simple
cf904cfa 6 * queues, and tail queues.
fc56ef08
BS		 7 */
8
9/*
10 * Copyright (c) 1991, 1993
11 * The Regents of the University of California. All rights reserved.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
21 * 3. Neither the name of the University nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 *
37 * @(#)queue.h 8.5 (Berkeley) 8/20/94
38 */
39
2a6a4076
MA		 40#ifndef QEMU_SYS_QUEUE_H
41#define QEMU_SYS_QUEUE_H
fc56ef08
BS		 42
43/*
cf904cfa
PB		 44 * This file defines four types of data structures: singly-linked lists,
45 * lists, simple queues, and tail queues.
fc56ef08 46 *
6095aa88
PB		 47 * A singly-linked list is headed by a single forward pointer. The
48 * elements are singly linked for minimum space and pointer manipulation
49 * overhead at the expense of O(n) removal for arbitrary elements. New
50 * elements can be added to the list after an existing element or at the
51 * head of the list. Elements being removed from the head of the list
52 * should use the explicit macro for this purpose for optimum
53 * efficiency. A singly-linked list may only be traversed in the forward
54 * direction. Singly-linked lists are ideal for applications with large
55 * datasets and few or no removals or for implementing a LIFO queue.
56 *
fc56ef08
BS		 57 * A list is headed by a single forward pointer (or an array of forward
58 * pointers for a hash table header). The elements are doubly linked
59 * so that an arbitrary element can be removed without a need to
60 * traverse the list. New elements can be added to the list before
61 * or after an existing element or at the head of the list. A list
62 * may only be traversed in the forward direction.
63 *
c616bbe1
PR		 64 * A simple queue is headed by a pair of pointers, one the head of the
65 * list and the other to the tail of the list. The elements are singly
66 * linked to save space, so elements can only be removed from the
67 * head of the list. New elements can be added to the list after
68 * an existing element, at the head of the list, or at the end of the
69 * list. A simple queue may only be traversed in the forward direction.
70 *
fc56ef08
BS		 71 * A tail queue is headed by a pair of pointers, one to the head of the
72 * list and the other to the tail of the list. The elements are doubly
73 * linked so that an arbitrary element can be removed without a need to
74 * traverse the list. New elements can be added to the list before or
75 * after an existing element, at the head of the list, or at the end of
76 * the list. A tail queue may be traversed in either direction.
77 *
fc56ef08
BS		 78 * For details on the use of these macros, see the queue(3) manual page.
79 */
80
81/*
82 * List definitions.
83 */
72cf2d4f 84#define QLIST_HEAD(name, type) \
fc56ef08
BS		 85struct name { \
86 struct type *lh_first; /* first element */ \
87}
88
72cf2d4f 89#define QLIST_HEAD_INITIALIZER(head) \
fc56ef08
BS		 90 { NULL }
91
72cf2d4f 92#define QLIST_ENTRY(type) \
fc56ef08
BS		 93struct { \
94 struct type *le_next; /* next element */ \
95 struct type **le_prev; /* address of previous next element */ \
96}
97
98/*
99 * List functions.
100 */
72cf2d4f 101#define QLIST_INIT(head) do { \
fc56ef08
BS		 102 (head)->lh_first = NULL; \
103} while (/*CONSTCOND*/0)
7911747b
PB		 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 (/*CONSTCOND*/0)
fc56ef08 117
72cf2d4f 118#define QLIST_INSERT_AFTER(listelm, elm, field) do { \
fc56ef08
BS		 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 (/*CONSTCOND*/0)
125
72cf2d4f 126#define QLIST_INSERT_BEFORE(listelm, elm, field) do { \
fc56ef08
BS		 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 (/*CONSTCOND*/0)
132
72cf2d4f 133#define QLIST_INSERT_HEAD(head, elm, field) do { \
fc56ef08
BS		 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 (/*CONSTCOND*/0)
139
72cf2d4f 140#define QLIST_REMOVE(elm, field) do { \
fc56ef08
BS		 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; \
a31ca680
SH		 145 (elm)->field.le_next = NULL; \
146 (elm)->field.le_prev = NULL; \
fc56ef08
BS		 147} while (/*CONSTCOND*/0)
148
195ed8cb
SH		 149/*
150 * Like QLIST_REMOVE() but safe to call when elm is not in a list
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 (/*CONSTCOND*/0)
162
4749079c
SH		 163/* Is elm in a list? */
164#define QLIST_IS_INSERTED(elm, field) ((elm)->field.le_prev != NULL)
165
72cf2d4f 166#define QLIST_FOREACH(var, head, field) \
fc56ef08
BS		 167 for ((var) = ((head)->lh_first); \
168 (var); \
169 (var) = ((var)->field.le_next))
170
72cf2d4f 171#define QLIST_FOREACH_SAFE(var, head, field, next_var) \
bb150dc8
JQ		 172 for ((var) = ((head)->lh_first); \
173 (var) && ((next_var) = ((var)->field.le_next), 1); \
174 (var) = (next_var))
175
fc56ef08
BS		 176/*
177 * List access methods.
178 */
72cf2d4f
BS		 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)
fc56ef08
BS		 182
183
6095aa88
PB		 184/*
185 * Singly-linked List definitions.
186 */
187#define QSLIST_HEAD(name, type) \
188struct name { \
189 struct type *slh_first; /* first element */ \
190}
191
192#define QSLIST_HEAD_INITIALIZER(head) \
193 { NULL }
194
195#define QSLIST_ENTRY(type) \
196struct { \
197 struct type *sle_next; /* next element */ \
198}
199
200/*
201 * Singly-linked List functions.
202 */
203#define QSLIST_INIT(head) do { \
204 (head)->slh_first = NULL; \
205} while (/*CONSTCOND*/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 (/*CONSTCOND*/0)
211
212#define QSLIST_INSERT_HEAD(head, elm, field) do { \
c740ad92
PB		 213 (elm)->field.sle_next = (head)->slh_first; \
214 (head)->slh_first = (elm); \
215} while (/*CONSTCOND*/0)
216
2120465f
PB		 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; \
d73415a3 221 } while (qatomic_cmpxchg(&(head)->slh_first, save_sle_next, (elm)) !=\
2120465f 222 save_sle_next); \
c740ad92
PB		 223} while (/*CONSTCOND*/0)
224
225#define QSLIST_MOVE_ATOMIC(dest, src) do { \
d73415a3 226 (dest)->slh_first = qatomic_xchg(&(src)->slh_first, NULL); \
6095aa88
PB		 227} while (/*CONSTCOND*/0)
228
229#define QSLIST_REMOVE_HEAD(head, field) do { \
a31ca680
SH		 230 typeof((head)->slh_first) elm = (head)->slh_first; \
231 (head)->slh_first = elm->field.sle_next; \
232 elm->field.sle_next = NULL; \
6095aa88
PB		 233} while (/*CONSTCOND*/0)
234
8c3570e3 235#define QSLIST_REMOVE_AFTER(slistelm, field) do { \
a31ca680
SH		 236 typeof(slistelm) next = (slistelm)->field.sle_next; \
237 (slistelm)->field.sle_next = next->field.sle_next; \
238 next->field.sle_next = NULL; \
8c3570e3
PB		 239} while (/*CONSTCOND*/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; \
a31ca680 249 (elm)->field.sle_next = NULL; \
8c3570e3 250 } \
6095aa88
PB		 251} while (/*CONSTCOND*/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 * Singly-linked List access methods.
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
c616bbe1
PR		 269/*
270 * Simple queue definitions.
271 */
272#define QSIMPLEQ_HEAD(name, type) \
273struct name { \
274 struct type *sqh_first; /* first element */ \
275 struct type **sqh_last; /* addr of last next element */ \
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; /* next element */ \
284}
285
286/*
287 * Simple queue functions.
288 */
289#define QSIMPLEQ_INIT(head) do { \
290 (head)->sqh_first = NULL; \
291 (head)->sqh_last = &(head)->sqh_first; \
292} while (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/0)
311
312#define QSIMPLEQ_REMOVE_HEAD(head, field) do { \
a31ca680
SH		 313 typeof((head)->sqh_first) elm = (head)->sqh_first; \
314 if (((head)->sqh_first = elm->field.sqe_next) == NULL) \
c616bbe1 315 (head)->sqh_last = &(head)->sqh_first; \
a31ca680 316 elm->field.sqe_next = NULL; \
c616bbe1
PR		 317} while (/*CONSTCOND*/0)
318
82595da8
PB		 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 (/*CONSTCOND*/0)
329
c616bbe1
PR		 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; \
a31ca680 340 (elm)->field.sqe_next = NULL; \
c616bbe1
PR		 341 } \
342} while (/*CONSTCOND*/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 (/*CONSTCOND*/0)
361
67a74148
SH		 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 (/*CONSTCOND*/0)
369
c616bbe1
PR		 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 * Simple queue access methods.
378 */
d73415a3
SH		 379#define QSIMPLEQ_EMPTY_ATOMIC(head) \
380 (qatomic_read(&((head)->sqh_first)) == NULL)
c616bbe1
PR		 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
7274f01b
PB		 385typedef struct QTailQLink {
386 void *tql_next;
387 struct QTailQLink *tql_prev;
388} QTailQLink;
c616bbe1 389
fc56ef08 390/*
7274f01b
PB		 391 * Tail queue definitions. The union acts as a poor man template, as if
392 * it were QTailQLink<type>.
fc56ef08 393 */
f95bb39c 394#define QTAILQ_HEAD(name, type) \
7274f01b
PB		 395union name { \
396 struct type *tqh_first; /* first element */ \
397 QTailQLink tqh_circ; /* link for circular backwards list */ \
fc56ef08 398}
fc56ef08 399
72cf2d4f 400#define QTAILQ_HEAD_INITIALIZER(head) \
7274f01b 401 { .tqh_circ = { NULL, &(head).tqh_circ } }
fc56ef08 402
f95bb39c 403#define QTAILQ_ENTRY(type) \
7274f01b
PB		 404union { \
405 struct type *tqe_next; /* next element */ \
406 QTailQLink tqe_circ; /* link for circular backwards list */ \
fc56ef08 407}
fc56ef08
BS		 408
409/*
410 * Tail queue functions.
411 */
72cf2d4f 412#define QTAILQ_INIT(head) do { \
fc56ef08 413 (head)->tqh_first = NULL; \
7274f01b 414 (head)->tqh_circ.tql_prev = &(head)->tqh_circ; \
fc56ef08
BS		 415} while (/*CONSTCOND*/0)
416
72cf2d4f 417#define QTAILQ_INSERT_HEAD(head, elm, field) do { \
fc56ef08 418 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
7274f01b
PB		 419 (head)->tqh_first->field.tqe_circ.tql_prev = \
420 &(elm)->field.tqe_circ; \
fc56ef08 421 else \
7274f01b 422 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
fc56ef08 423 (head)->tqh_first = (elm); \
7274f01b 424 (elm)->field.tqe_circ.tql_prev = &(head)->tqh_circ; \
fc56ef08
BS		 425} while (/*CONSTCOND*/0)
426
72cf2d4f 427#define QTAILQ_INSERT_TAIL(head, elm, field) do { \
fc56ef08 428 (elm)->field.tqe_next = NULL; \
7274f01b
PB		 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; \
fc56ef08
BS		 432} while (/*CONSTCOND*/0)
433
72cf2d4f 434#define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
fc56ef08 435 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
7274f01b
PB		 436 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
437 &(elm)->field.tqe_circ; \
fc56ef08 438 else \
7274f01b 439 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
fc56ef08 440 (listelm)->field.tqe_next = (elm); \
7274f01b 441 (elm)->field.tqe_circ.tql_prev = &(listelm)->field.tqe_circ; \
fc56ef08
BS		 442} while (/*CONSTCOND*/0)
443
7274f01b
PB		 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; \
fc56ef08
BS		 449} while (/*CONSTCOND*/0)
450
72cf2d4f 451#define QTAILQ_REMOVE(head, elm, field) do { \
fc56ef08 452 if (((elm)->field.tqe_next) != NULL) \
7274f01b
PB		 453 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \
454 (elm)->field.tqe_circ.tql_prev; \
fc56ef08 455 else \
7274f01b
PB		 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; \
a31ca680
SH		 459 (elm)->field.tqe_circ.tql_next = NULL; \
460 (elm)->field.tqe_next = NULL; \
fc56ef08
BS		 461} while (/*CONSTCOND*/0)
462
050ec8cc
EC		 463/* remove @left, @right and all elements in between from @head */
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 (/*CONSTCOND*/0)
472
72cf2d4f 473#define QTAILQ_FOREACH(var, head, field) \
fc56ef08
BS		 474 for ((var) = ((head)->tqh_first); \
475 (var); \
476 (var) = ((var)->field.tqe_next))
477
72cf2d4f 478#define QTAILQ_FOREACH_SAFE(var, head, field, next_var) \
fc56ef08
BS		 479 for ((var) = ((head)->tqh_first); \
480 (var) && ((next_var) = ((var)->field.tqe_next), 1); \
481 (var) = (next_var))
482
eae3eb3e
PB		 483#define QTAILQ_FOREACH_REVERSE(var, head, field) \
484 for ((var) = QTAILQ_LAST(head); \
fc56ef08 485 (var); \
eae3eb3e 486 (var) = QTAILQ_PREV(var, field))
fc56ef08 487
eae3eb3e
PB		 488#define QTAILQ_FOREACH_REVERSE_SAFE(var, head, field, prev_var) \
489 for ((var) = QTAILQ_LAST(head); \
5ed76a4c 490 (var) && ((prev_var) = QTAILQ_PREV(var, field), 1); \
15fa08f8
RH		 491 (var) = (prev_var))
492
fc56ef08
BS		 493/*
494 * Tail queue access methods.
495 */
72cf2d4f
BS		 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)
7274f01b 499#define QTAILQ_IN_USE(elm, field) ((elm)->field.tqe_circ.tql_prev != NULL)
fc56ef08 500
7274f01b
PB		 501#define QTAILQ_LINK_PREV(link) \
502 ((link).tql_prev->tql_prev->tql_next)
eae3eb3e 503#define QTAILQ_LAST(head) \
7274f01b 504 ((typeof((head)->tqh_first)) QTAILQ_LINK_PREV((head)->tqh_circ))
eae3eb3e 505#define QTAILQ_PREV(elm, field) \
7274f01b 506 ((typeof((elm)->field.tqe_next)) QTAILQ_LINK_PREV((elm)->field.tqe_circ))
fc56ef08 507
94869d5c 508#define field_at_offset(base, offset, type) \
7274f01b 509 ((type *) (((char *) (base)) + (offset)))
94869d5c
JD		 510
511/*
7274f01b
PB		 512 * Raw access of elements of a tail queue head. Offsets are all zero
513 * because it's a union.
94869d5c
JD		 514 */
515#define QTAILQ_RAW_FIRST(head) \
7274f01b
PB		 516 field_at_offset(head, 0, void *)
517#define QTAILQ_RAW_TQH_CIRC(head) \
518 field_at_offset(head, 0, QTailQLink)
94869d5c
JD		 519
520/*
521 * Raw access of elements of a tail entry
522 */
523#define QTAILQ_RAW_NEXT(elm, entry) \
7274f01b
PB		 524 field_at_offset(elm, entry, void *)
525#define QTAILQ_RAW_TQE_CIRC(elm, entry) \
526 field_at_offset(elm, entry, QTailQLink)
94869d5c 527/*
7274f01b 528 * Tail queue traversal using pointer arithmetic.
94869d5c
JD		 529 */
530#define QTAILQ_RAW_FOREACH(elm, head, entry) \
7274f01b 531 for ((elm) = *QTAILQ_RAW_FIRST(head); \
94869d5c 532 (elm); \
7274f01b 533 (elm) = *QTAILQ_RAW_NEXT(elm, entry))
94869d5c
JD		 534/*
535 * Tail queue insertion using pointer arithmetic.
536 */
7274f01b
PB		 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); \
94869d5c
JD		 542} while (/*CONSTCOND*/0)
543
4746dbf8
EA		 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
a085664f
EA		 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
4746dbf8
EA		 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
2a6a4076 576#endif /* QEMU_SYS_QUEUE_H */
QEMU mirror