1 /* $NetBSD: queue.h,v 1.52 2009/04/20 09:56:08 mschuett Exp $ */ 2 3 /* 4 * QEMU version: Copy from netbsd, removed debug code, removed some of 5 * the implementations. Left in singly-linked lists, lists, simple 6 * queues, and tail queues. 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 40 #ifndef QEMU_SYS_QUEUE_H 41 #define QEMU_SYS_QUEUE_H 42 43 /* 44 * This file defines four types of data structures: singly-linked lists, 45 * lists, simple queues, and tail queues. 46 * 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 * 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 * 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 * 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 * 78 * For details on the use of these macros, see the queue(3) manual page. 79 */ 80 81 /* 82 * List definitions. 83 */ 84 #define QLIST_HEAD(name, type) \ 85 struct name { \ 86 struct type *lh_first; /* first element */ \ 87 } 88 89 #define QLIST_HEAD_INITIALIZER(head) \ 90 { NULL } 91 92 #define QLIST_ENTRY(type) \ 93 struct { \ 94 struct type *le_next; /* next element */ \ 95 struct type **le_prev; /* address of previous next element */ \ 96 } 97 98 /* 99 * List functions. 100 */ 101 #define QLIST_INIT(head) do { \ 102 (head)->lh_first = NULL; \ 103 } while (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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 (/*CONSTCOND*/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 } while (/*CONSTCOND*/0) 146 147 /* 148 * Like QLIST_REMOVE() but safe to call when elm is not in a list 149 */ 150 #define QLIST_SAFE_REMOVE(elm, field) do { \ 151 if ((elm)->field.le_prev != NULL) { \ 152 if ((elm)->field.le_next != NULL) \ 153 (elm)->field.le_next->field.le_prev = \ 154 (elm)->field.le_prev; \ 155 *(elm)->field.le_prev = (elm)->field.le_next; \ 156 (elm)->field.le_next = NULL; \ 157 (elm)->field.le_prev = NULL; \ 158 } \ 159 } while (/*CONSTCOND*/0) 160 161 /* Is elm in a list? */ 162 #define QLIST_IS_INSERTED(elm, field) ((elm)->field.le_prev != NULL) 163 164 #define QLIST_FOREACH(var, head, field) \ 165 for ((var) = ((head)->lh_first); \ 166 (var); \ 167 (var) = ((var)->field.le_next)) 168 169 #define QLIST_FOREACH_SAFE(var, head, field, next_var) \ 170 for ((var) = ((head)->lh_first); \ 171 (var) && ((next_var) = ((var)->field.le_next), 1); \ 172 (var) = (next_var)) 173 174 /* 175 * List access methods. 176 */ 177 #define QLIST_EMPTY(head) ((head)->lh_first == NULL) 178 #define QLIST_FIRST(head) ((head)->lh_first) 179 #define QLIST_NEXT(elm, field) ((elm)->field.le_next) 180 181 182 /* 183 * Singly-linked List definitions. 184 */ 185 #define QSLIST_HEAD(name, type) \ 186 struct name { \ 187 struct type *slh_first; /* first element */ \ 188 } 189 190 #define QSLIST_HEAD_INITIALIZER(head) \ 191 { NULL } 192 193 #define QSLIST_ENTRY(type) \ 194 struct { \ 195 struct type *sle_next; /* next element */ \ 196 } 197 198 /* 199 * Singly-linked List functions. 200 */ 201 #define QSLIST_INIT(head) do { \ 202 (head)->slh_first = NULL; \ 203 } while (/*CONSTCOND*/0) 204 205 #define QSLIST_INSERT_AFTER(slistelm, elm, field) do { \ 206 (elm)->field.sle_next = (slistelm)->field.sle_next; \ 207 (slistelm)->field.sle_next = (elm); \ 208 } while (/*CONSTCOND*/0) 209 210 #define QSLIST_INSERT_HEAD(head, elm, field) do { \ 211 (elm)->field.sle_next = (head)->slh_first; \ 212 (head)->slh_first = (elm); \ 213 } while (/*CONSTCOND*/0) 214 215 #define QSLIST_INSERT_HEAD_ATOMIC(head, elm, field) do { \ 216 typeof(elm) save_sle_next; \ 217 do { \ 218 save_sle_next = (elm)->field.sle_next = (head)->slh_first; \ 219 } while (atomic_cmpxchg(&(head)->slh_first, save_sle_next, (elm)) != \ 220 save_sle_next); \ 221 } while (/*CONSTCOND*/0) 222 223 #define QSLIST_MOVE_ATOMIC(dest, src) do { \ 224 (dest)->slh_first = atomic_xchg(&(src)->slh_first, NULL); \ 225 } while (/*CONSTCOND*/0) 226 227 #define QSLIST_REMOVE_HEAD(head, field) do { \ 228 (head)->slh_first = (head)->slh_first->field.sle_next; \ 229 } while (/*CONSTCOND*/0) 230 231 #define QSLIST_REMOVE_AFTER(slistelm, field) do { \ 232 (slistelm)->field.sle_next = \ 233 QSLIST_NEXT(QSLIST_NEXT((slistelm), field), field); \ 234 } while (/*CONSTCOND*/0) 235 236 #define QSLIST_REMOVE(head, elm, type, field) do { \ 237 if ((head)->slh_first == (elm)) { \ 238 QSLIST_REMOVE_HEAD((head), field); \ 239 } else { \ 240 struct type *curelm = (head)->slh_first; \ 241 while (curelm->field.sle_next != (elm)) \ 242 curelm = curelm->field.sle_next; \ 243 curelm->field.sle_next = curelm->field.sle_next->field.sle_next; \ 244 } \ 245 } while (/*CONSTCOND*/0) 246 247 #define QSLIST_FOREACH(var, head, field) \ 248 for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next) 249 250 #define QSLIST_FOREACH_SAFE(var, head, field, tvar) \ 251 for ((var) = QSLIST_FIRST((head)); \ 252 (var) && ((tvar) = QSLIST_NEXT((var), field), 1); \ 253 (var) = (tvar)) 254 255 /* 256 * Singly-linked List access methods. 257 */ 258 #define QSLIST_EMPTY(head) ((head)->slh_first == NULL) 259 #define QSLIST_FIRST(head) ((head)->slh_first) 260 #define QSLIST_NEXT(elm, field) ((elm)->field.sle_next) 261 262 263 /* 264 * Simple queue definitions. 265 */ 266 #define QSIMPLEQ_HEAD(name, type) \ 267 struct name { \ 268 struct type *sqh_first; /* first element */ \ 269 struct type **sqh_last; /* addr of last next element */ \ 270 } 271 272 #define QSIMPLEQ_HEAD_INITIALIZER(head) \ 273 { NULL, &(head).sqh_first } 274 275 #define QSIMPLEQ_ENTRY(type) \ 276 struct { \ 277 struct type *sqe_next; /* next element */ \ 278 } 279 280 /* 281 * Simple queue functions. 282 */ 283 #define QSIMPLEQ_INIT(head) do { \ 284 (head)->sqh_first = NULL; \ 285 (head)->sqh_last = &(head)->sqh_first; \ 286 } while (/*CONSTCOND*/0) 287 288 #define QSIMPLEQ_INSERT_HEAD(head, elm, field) do { \ 289 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ 290 (head)->sqh_last = &(elm)->field.sqe_next; \ 291 (head)->sqh_first = (elm); \ 292 } while (/*CONSTCOND*/0) 293 294 #define QSIMPLEQ_INSERT_TAIL(head, elm, field) do { \ 295 (elm)->field.sqe_next = NULL; \ 296 *(head)->sqh_last = (elm); \ 297 (head)->sqh_last = &(elm)->field.sqe_next; \ 298 } while (/*CONSTCOND*/0) 299 300 #define QSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 301 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL) \ 302 (head)->sqh_last = &(elm)->field.sqe_next; \ 303 (listelm)->field.sqe_next = (elm); \ 304 } while (/*CONSTCOND*/0) 305 306 #define QSIMPLEQ_REMOVE_HEAD(head, field) do { \ 307 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL)\ 308 (head)->sqh_last = &(head)->sqh_first; \ 309 } while (/*CONSTCOND*/0) 310 311 #define QSIMPLEQ_SPLIT_AFTER(head, elm, field, removed) do { \ 312 QSIMPLEQ_INIT(removed); \ 313 if (((removed)->sqh_first = (head)->sqh_first) != NULL) { \ 314 if (((head)->sqh_first = (elm)->field.sqe_next) == NULL) { \ 315 (head)->sqh_last = &(head)->sqh_first; \ 316 } \ 317 (removed)->sqh_last = &(elm)->field.sqe_next; \ 318 (elm)->field.sqe_next = NULL; \ 319 } \ 320 } while (/*CONSTCOND*/0) 321 322 #define QSIMPLEQ_REMOVE(head, elm, type, field) do { \ 323 if ((head)->sqh_first == (elm)) { \ 324 QSIMPLEQ_REMOVE_HEAD((head), field); \ 325 } else { \ 326 struct type *curelm = (head)->sqh_first; \ 327 while (curelm->field.sqe_next != (elm)) \ 328 curelm = curelm->field.sqe_next; \ 329 if ((curelm->field.sqe_next = \ 330 curelm->field.sqe_next->field.sqe_next) == NULL) \ 331 (head)->sqh_last = &(curelm)->field.sqe_next; \ 332 } \ 333 } while (/*CONSTCOND*/0) 334 335 #define QSIMPLEQ_FOREACH(var, head, field) \ 336 for ((var) = ((head)->sqh_first); \ 337 (var); \ 338 (var) = ((var)->field.sqe_next)) 339 340 #define QSIMPLEQ_FOREACH_SAFE(var, head, field, next) \ 341 for ((var) = ((head)->sqh_first); \ 342 (var) && ((next = ((var)->field.sqe_next)), 1); \ 343 (var) = (next)) 344 345 #define QSIMPLEQ_CONCAT(head1, head2) do { \ 346 if (!QSIMPLEQ_EMPTY((head2))) { \ 347 *(head1)->sqh_last = (head2)->sqh_first; \ 348 (head1)->sqh_last = (head2)->sqh_last; \ 349 QSIMPLEQ_INIT((head2)); \ 350 } \ 351 } while (/*CONSTCOND*/0) 352 353 #define QSIMPLEQ_PREPEND(head1, head2) do { \ 354 if (!QSIMPLEQ_EMPTY((head2))) { \ 355 *(head2)->sqh_last = (head1)->sqh_first; \ 356 (head1)->sqh_first = (head2)->sqh_first; \ 357 QSIMPLEQ_INIT((head2)); \ 358 } \ 359 } while (/*CONSTCOND*/0) 360 361 #define QSIMPLEQ_LAST(head, type, field) \ 362 (QSIMPLEQ_EMPTY((head)) ? \ 363 NULL : \ 364 ((struct type *)(void *) \ 365 ((char *)((head)->sqh_last) - offsetof(struct type, field)))) 366 367 /* 368 * Simple queue access methods. 369 */ 370 #define QSIMPLEQ_EMPTY_ATOMIC(head) (atomic_read(&((head)->sqh_first)) == NULL) 371 #define QSIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL) 372 #define QSIMPLEQ_FIRST(head) ((head)->sqh_first) 373 #define QSIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) 374 375 typedef struct QTailQLink { 376 void *tql_next; 377 struct QTailQLink *tql_prev; 378 } QTailQLink; 379 380 /* 381 * Tail queue definitions. The union acts as a poor man template, as if 382 * it were QTailQLink<type>. 383 */ 384 #define QTAILQ_HEAD(name, type) \ 385 union name { \ 386 struct type *tqh_first; /* first element */ \ 387 QTailQLink tqh_circ; /* link for circular backwards list */ \ 388 } 389 390 #define QTAILQ_HEAD_INITIALIZER(head) \ 391 { .tqh_circ = { NULL, &(head).tqh_circ } } 392 393 #define QTAILQ_ENTRY(type) \ 394 union { \ 395 struct type *tqe_next; /* next element */ \ 396 QTailQLink tqe_circ; /* link for circular backwards list */ \ 397 } 398 399 /* 400 * Tail queue functions. 401 */ 402 #define QTAILQ_INIT(head) do { \ 403 (head)->tqh_first = NULL; \ 404 (head)->tqh_circ.tql_prev = &(head)->tqh_circ; \ 405 } while (/*CONSTCOND*/0) 406 407 #define QTAILQ_INSERT_HEAD(head, elm, field) do { \ 408 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 409 (head)->tqh_first->field.tqe_circ.tql_prev = \ 410 &(elm)->field.tqe_circ; \ 411 else \ 412 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \ 413 (head)->tqh_first = (elm); \ 414 (elm)->field.tqe_circ.tql_prev = &(head)->tqh_circ; \ 415 } while (/*CONSTCOND*/0) 416 417 #define QTAILQ_INSERT_TAIL(head, elm, field) do { \ 418 (elm)->field.tqe_next = NULL; \ 419 (elm)->field.tqe_circ.tql_prev = (head)->tqh_circ.tql_prev; \ 420 (head)->tqh_circ.tql_prev->tql_next = (elm); \ 421 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \ 422 } while (/*CONSTCOND*/0) 423 424 #define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 425 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 426 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \ 427 &(elm)->field.tqe_circ; \ 428 else \ 429 (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \ 430 (listelm)->field.tqe_next = (elm); \ 431 (elm)->field.tqe_circ.tql_prev = &(listelm)->field.tqe_circ; \ 432 } while (/*CONSTCOND*/0) 433 434 #define QTAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 435 (elm)->field.tqe_circ.tql_prev = (listelm)->field.tqe_circ.tql_prev; \ 436 (elm)->field.tqe_next = (listelm); \ 437 (listelm)->field.tqe_circ.tql_prev->tql_next = (elm); \ 438 (listelm)->field.tqe_circ.tql_prev = &(elm)->field.tqe_circ; \ 439 } while (/*CONSTCOND*/0) 440 441 #define QTAILQ_REMOVE(head, elm, field) do { \ 442 if (((elm)->field.tqe_next) != NULL) \ 443 (elm)->field.tqe_next->field.tqe_circ.tql_prev = \ 444 (elm)->field.tqe_circ.tql_prev; \ 445 else \ 446 (head)->tqh_circ.tql_prev = (elm)->field.tqe_circ.tql_prev; \ 447 (elm)->field.tqe_circ.tql_prev->tql_next = (elm)->field.tqe_next; \ 448 (elm)->field.tqe_circ.tql_prev = NULL; \ 449 } while (/*CONSTCOND*/0) 450 451 /* remove @left, @right and all elements in between from @head */ 452 #define QTAILQ_REMOVE_SEVERAL(head, left, right, field) do { \ 453 if (((right)->field.tqe_next) != NULL) \ 454 (right)->field.tqe_next->field.tqe_circ.tql_prev = \ 455 (left)->field.tqe_circ.tql_prev; \ 456 else \ 457 (head)->tqh_circ.tql_prev = (left)->field.tqe_circ.tql_prev; \ 458 (left)->field.tqe_circ.tql_prev->tql_next = (right)->field.tqe_next; \ 459 } while (/*CONSTCOND*/0) 460 461 #define QTAILQ_FOREACH(var, head, field) \ 462 for ((var) = ((head)->tqh_first); \ 463 (var); \ 464 (var) = ((var)->field.tqe_next)) 465 466 #define QTAILQ_FOREACH_SAFE(var, head, field, next_var) \ 467 for ((var) = ((head)->tqh_first); \ 468 (var) && ((next_var) = ((var)->field.tqe_next), 1); \ 469 (var) = (next_var)) 470 471 #define QTAILQ_FOREACH_REVERSE(var, head, field) \ 472 for ((var) = QTAILQ_LAST(head); \ 473 (var); \ 474 (var) = QTAILQ_PREV(var, field)) 475 476 #define QTAILQ_FOREACH_REVERSE_SAFE(var, head, field, prev_var) \ 477 for ((var) = QTAILQ_LAST(head); \ 478 (var) && ((prev_var) = QTAILQ_PREV(var, field), 1); \ 479 (var) = (prev_var)) 480 481 /* 482 * Tail queue access methods. 483 */ 484 #define QTAILQ_EMPTY(head) ((head)->tqh_first == NULL) 485 #define QTAILQ_FIRST(head) ((head)->tqh_first) 486 #define QTAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 487 #define QTAILQ_IN_USE(elm, field) ((elm)->field.tqe_circ.tql_prev != NULL) 488 489 #define QTAILQ_LINK_PREV(link) \ 490 ((link).tql_prev->tql_prev->tql_next) 491 #define QTAILQ_LAST(head) \ 492 ((typeof((head)->tqh_first)) QTAILQ_LINK_PREV((head)->tqh_circ)) 493 #define QTAILQ_PREV(elm, field) \ 494 ((typeof((elm)->field.tqe_next)) QTAILQ_LINK_PREV((elm)->field.tqe_circ)) 495 496 #define field_at_offset(base, offset, type) \ 497 ((type *) (((char *) (base)) + (offset))) 498 499 /* 500 * Raw access of elements of a tail queue head. Offsets are all zero 501 * because it's a union. 502 */ 503 #define QTAILQ_RAW_FIRST(head) \ 504 field_at_offset(head, 0, void *) 505 #define QTAILQ_RAW_TQH_CIRC(head) \ 506 field_at_offset(head, 0, QTailQLink) 507 508 /* 509 * Raw access of elements of a tail entry 510 */ 511 #define QTAILQ_RAW_NEXT(elm, entry) \ 512 field_at_offset(elm, entry, void *) 513 #define QTAILQ_RAW_TQE_CIRC(elm, entry) \ 514 field_at_offset(elm, entry, QTailQLink) 515 /* 516 * Tail queue traversal using pointer arithmetic. 517 */ 518 #define QTAILQ_RAW_FOREACH(elm, head, entry) \ 519 for ((elm) = *QTAILQ_RAW_FIRST(head); \ 520 (elm); \ 521 (elm) = *QTAILQ_RAW_NEXT(elm, entry)) 522 /* 523 * Tail queue insertion using pointer arithmetic. 524 */ 525 #define QTAILQ_RAW_INSERT_TAIL(head, elm, entry) do { \ 526 *QTAILQ_RAW_NEXT(elm, entry) = NULL; \ 527 QTAILQ_RAW_TQE_CIRC(elm, entry)->tql_prev = QTAILQ_RAW_TQH_CIRC(head)->tql_prev; \ 528 QTAILQ_RAW_TQH_CIRC(head)->tql_prev->tql_next = (elm); \ 529 QTAILQ_RAW_TQH_CIRC(head)->tql_prev = QTAILQ_RAW_TQE_CIRC(elm, entry); \ 530 } while (/*CONSTCOND*/0) 531 532 #define QLIST_RAW_FIRST(head) \ 533 field_at_offset(head, 0, void *) 534 535 #define QLIST_RAW_NEXT(elm, entry) \ 536 field_at_offset(elm, entry, void *) 537 538 #define QLIST_RAW_PREVIOUS(elm, entry) \ 539 field_at_offset(elm, entry + sizeof(void *), void *) 540 541 #define QLIST_RAW_FOREACH(elm, head, entry) \ 542 for ((elm) = *QLIST_RAW_FIRST(head); \ 543 (elm); \ 544 (elm) = *QLIST_RAW_NEXT(elm, entry)) 545 546 #define QLIST_RAW_INSERT_AFTER(head, prev, elem, entry) do { \ 547 *QLIST_RAW_NEXT(prev, entry) = elem; \ 548 *QLIST_RAW_PREVIOUS(elem, entry) = QLIST_RAW_NEXT(prev, entry); \ 549 *QLIST_RAW_NEXT(elem, entry) = NULL; \ 550 } while (0) 551 552 #define QLIST_RAW_INSERT_HEAD(head, elm, entry) do { \ 553 void *first = *QLIST_RAW_FIRST(head); \ 554 *QLIST_RAW_FIRST(head) = elm; \ 555 *QLIST_RAW_PREVIOUS(elm, entry) = QLIST_RAW_FIRST(head); \ 556 if (first) { \ 557 *QLIST_RAW_NEXT(elm, entry) = first; \ 558 *QLIST_RAW_PREVIOUS(first, entry) = QLIST_RAW_NEXT(elm, entry); \ 559 } else { \ 560 *QLIST_RAW_NEXT(elm, entry) = NULL; \ 561 } \ 562 } while (0) 563 564 #endif /* QEMU_SYS_QUEUE_H */ 565