queue.h revision fb3e20e0
1/* Copyright (c) 2017 - 2020 LiteSpeed Technologies Inc. See LICENSE. */ 2/*- 3 * SPDX-License-Identifier: BSD-3-Clause 4 * 5 * Copyright (c) 1991, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 * 32 * @(#)queue.h 8.5 (Berkeley) 8/20/94 33 * $FreeBSD$ 34 */ 35 36#ifndef _SYS_QUEUE_H_ 37#define _SYS_QUEUE_H_ 38 39 40/* 41 * This file defines four types of data structures: singly-linked lists, 42 * singly-linked tail queues, lists and tail queues. 43 * 44 * A singly-linked list is headed by a single forward pointer. The elements 45 * are singly linked for minimum space and pointer manipulation overhead at 46 * the expense of O(n) removal for arbitrary elements. New elements can be 47 * added to the list after an existing element or at the head of the list. 48 * Elements being removed from the head of the list should use the explicit 49 * macro for this purpose for optimum efficiency. A singly-linked list may 50 * only be traversed in the forward direction. Singly-linked lists are ideal 51 * for applications with large datasets and few or no removals or for 52 * implementing a LIFO queue. 53 * 54 * A singly-linked tail queue is headed by a pair of pointers, one to the 55 * head of the list and the other to the tail of the list. The elements are 56 * singly linked for minimum space and pointer manipulation overhead at the 57 * expense of O(n) removal for arbitrary elements. New elements can be added 58 * to the list after an existing element, at the head of the list, or at the 59 * end of the list. Elements being removed from the head of the tail queue 60 * should use the explicit macro for this purpose for optimum efficiency. 61 * A singly-linked tail queue may only be traversed in the forward direction. 62 * Singly-linked tail queues are ideal for applications with large datasets 63 * and few or no removals or for implementing a FIFO queue. 64 * 65 * A list is headed by a single forward pointer (or an array of forward 66 * pointers for a hash table header). The elements are doubly linked 67 * so that an arbitrary element can be removed without a need to 68 * traverse the list. New elements can be added to the list before 69 * or after an existing element or at the head of the list. A list 70 * may be traversed in either direction. 71 * 72 * A tail queue is headed by a pair of pointers, one to the head of the 73 * list and the other to the tail of the list. The elements are doubly 74 * linked so that an arbitrary element can be removed without a need to 75 * traverse the list. New elements can be added to the list before or 76 * after an existing element, at the head of the list, or at the end of 77 * the list. A tail queue may be traversed in either direction. 78 * 79 * For details on the use of these macros, see the queue(3) manual page. 80 * 81 * Below is a summary of implemented functions where: 82 * + means the macro is available 83 * - means the macro is not available 84 * s means the macro is available but is slow (runs in O(n) time) 85 * 86 * SLIST LIST STAILQ TAILQ 87 * _HEAD + + + + 88 * _CLASS_HEAD + + + + 89 * _HEAD_INITIALIZER + + + + 90 * _ENTRY + + + + 91 * _CLASS_ENTRY + + + + 92 * _INIT + + + + 93 * _EMPTY + + + + 94 * _FIRST + + + + 95 * _NEXT + + + + 96 * _PREV - + - + 97 * _LAST - - + + 98 * _FOREACH + + + + 99 * _FOREACH_FROM + + + + 100 * _FOREACH_SAFE + + + + 101 * _FOREACH_FROM_SAFE + + + + 102 * _FOREACH_REVERSE - - - + 103 * _FOREACH_REVERSE_FROM - - - + 104 * _FOREACH_REVERSE_SAFE - - - + 105 * _FOREACH_REVERSE_FROM_SAFE - - - + 106 * _INSERT_HEAD + + + + 107 * _INSERT_BEFORE - + - + 108 * _INSERT_AFTER + + + + 109 * _INSERT_TAIL - - + + 110 * _CONCAT s s + + 111 * _REMOVE_AFTER + - + - 112 * _REMOVE_HEAD + - + - 113 * _REMOVE s + s + 114 * _SWAP + + + + 115 * 116 */ 117#ifdef QUEUE_MACRO_DEBUG 118#warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH 119#define QUEUE_MACRO_DEBUG_TRACE 120#define QUEUE_MACRO_DEBUG_TRASH 121#endif 122 123#ifdef QUEUE_MACRO_DEBUG_TRACE 124/* Store the last 2 places the queue element or head was altered */ 125struct qm_trace { 126 unsigned long lastline; 127 unsigned long prevline; 128 const char *lastfile; 129 const char *prevfile; 130}; 131 132#define TRACEBUF struct qm_trace trace; 133#define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL } , 134 135#define QMD_TRACE_HEAD(head) do { \ 136 (head)->trace.prevline = (head)->trace.lastline; \ 137 (head)->trace.prevfile = (head)->trace.lastfile; \ 138 (head)->trace.lastline = __LINE__; \ 139 (head)->trace.lastfile = __FILE__; \ 140} while (0) 141 142#define QMD_TRACE_ELEM(elem) do { \ 143 (elem)->trace.prevline = (elem)->trace.lastline; \ 144 (elem)->trace.prevfile = (elem)->trace.lastfile; \ 145 (elem)->trace.lastline = __LINE__; \ 146 (elem)->trace.lastfile = __FILE__; \ 147} while (0) 148 149#else /* !QUEUE_MACRO_DEBUG_TRACE */ 150#define QMD_TRACE_ELEM(elem) 151#define QMD_TRACE_HEAD(head) 152#define TRACEBUF 153#define TRACEBUF_INITIALIZER 154#endif /* QUEUE_MACRO_DEBUG_TRACE */ 155 156#ifdef QUEUE_MACRO_DEBUG_TRASH 157#define TRASHIT(x) do {(x) = (void *)-1;} while (0) 158#define QMD_IS_TRASHED(x) ((x) == (void *)(intptr_t)-1) 159#else /* !QUEUE_MACRO_DEBUG_TRASH */ 160#define TRASHIT(x) 161#define QMD_IS_TRASHED(x) 0 162#endif /* QUEUE_MACRO_DEBUG_TRASH */ 163 164#if defined(QUEUE_MACRO_DEBUG_TRACE) || defined(QUEUE_MACRO_DEBUG_TRASH) 165#define QMD_SAVELINK(name, link) void **name = (void *)&(link) 166#else /* !QUEUE_MACRO_DEBUG_TRACE && !QUEUE_MACRO_DEBUG_TRASH */ 167#define QMD_SAVELINK(name, link) 168#endif /* QUEUE_MACRO_DEBUG_TRACE || QUEUE_MACRO_DEBUG_TRASH */ 169 170#ifdef __cplusplus 171/* 172 * In C++ there can be structure lists and class lists: 173 */ 174#define QUEUE_TYPEOF(type) type 175#else 176#define QUEUE_TYPEOF(type) struct type 177#endif 178 179/* 180 * Singly-linked List declarations. 181 */ 182#define SLIST_HEAD(name, type) \ 183struct name { \ 184 struct type *slh_first; /* first element */ \ 185} 186 187#define SLIST_CLASS_HEAD(name, type) \ 188struct name { \ 189 class type *slh_first; /* first element */ \ 190} 191 192#define SLIST_HEAD_INITIALIZER(head) \ 193 { NULL } 194 195#define SLIST_ENTRY(type) \ 196struct { \ 197 struct type *sle_next; /* next element */ \ 198} 199 200#define SLIST_CLASS_ENTRY(type) \ 201struct { \ 202 class type *sle_next; /* next element */ \ 203} 204 205/* 206 * Singly-linked List functions. 207 */ 208#if (defined(_KERNEL) && defined(INVARIANTS)) 209#define QMD_SLIST_CHECK_PREVPTR(prevp, elm) do { \ 210 if (*(prevp) != (elm)) \ 211 panic("Bad prevptr *(%p) == %p != %p", \ 212 (prevp), *(prevp), (elm)); \ 213} while (0) 214#else 215#define QMD_SLIST_CHECK_PREVPTR(prevp, elm) 216#endif 217 218#define SLIST_CONCAT(head1, head2, type, field) do { \ 219 QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \ 220 if (curelm == NULL) { \ 221 if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \ 222 SLIST_INIT(head2); \ 223 } else if (SLIST_FIRST(head2) != NULL) { \ 224 while (SLIST_NEXT(curelm, field) != NULL) \ 225 curelm = SLIST_NEXT(curelm, field); \ 226 SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \ 227 SLIST_INIT(head2); \ 228 } \ 229} while (0) 230 231#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 232 233#define SLIST_FIRST(head) ((head)->slh_first) 234 235#define SLIST_FOREACH(var, head, field) \ 236 for ((var) = SLIST_FIRST((head)); \ 237 (var); \ 238 (var) = SLIST_NEXT((var), field)) 239 240#define SLIST_FOREACH_FROM(var, head, field) \ 241 for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 242 (var); \ 243 (var) = SLIST_NEXT((var), field)) 244 245#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 246 for ((var) = SLIST_FIRST((head)); \ 247 (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 248 (var) = (tvar)) 249 250#define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 251 for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 252 (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 253 (var) = (tvar)) 254 255#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 256 for ((varp) = &SLIST_FIRST((head)); \ 257 ((var) = *(varp)) != NULL; \ 258 (varp) = &SLIST_NEXT((var), field)) 259 260#define SLIST_INIT(head) do { \ 261 SLIST_FIRST((head)) = NULL; \ 262} while (0) 263 264#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 265 SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 266 SLIST_NEXT((slistelm), field) = (elm); \ 267} while (0) 268 269#define SLIST_INSERT_HEAD(head, elm, field) do { \ 270 SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 271 SLIST_FIRST((head)) = (elm); \ 272} while (0) 273 274#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 275 276#define SLIST_REMOVE(head, elm, type, field) do { \ 277 QMD_SAVELINK(oldnext, (elm)->field.sle_next); \ 278 if (SLIST_FIRST((head)) == (elm)) { \ 279 SLIST_REMOVE_HEAD((head), field); \ 280 } \ 281 else { \ 282 QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head); \ 283 while (SLIST_NEXT(curelm, field) != (elm)) \ 284 curelm = SLIST_NEXT(curelm, field); \ 285 SLIST_REMOVE_AFTER(curelm, field); \ 286 } \ 287 TRASHIT(*oldnext); \ 288} while (0) 289 290#define SLIST_REMOVE_AFTER(elm, field) do { \ 291 SLIST_NEXT(elm, field) = \ 292 SLIST_NEXT(SLIST_NEXT(elm, field), field); \ 293} while (0) 294 295#define SLIST_REMOVE_HEAD(head, field) do { \ 296 SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 297} while (0) 298 299#define SLIST_REMOVE_PREVPTR(prevp, elm, field) do { \ 300 QMD_SLIST_CHECK_PREVPTR(prevp, elm); \ 301 *(prevp) = SLIST_NEXT(elm, field); \ 302 TRASHIT((elm)->field.sle_next); \ 303} while (0) 304 305#define SLIST_SWAP(head1, head2, type) do { \ 306 QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \ 307 SLIST_FIRST(head1) = SLIST_FIRST(head2); \ 308 SLIST_FIRST(head2) = swap_first; \ 309} while (0) 310 311/* 312 * Singly-linked Tail queue declarations. 313 */ 314#define STAILQ_HEAD(name, type) \ 315struct name { \ 316 struct type *stqh_first;/* first element */ \ 317 struct type **stqh_last;/* addr of last next element */ \ 318} 319 320#define STAILQ_CLASS_HEAD(name, type) \ 321struct name { \ 322 class type *stqh_first; /* first element */ \ 323 class type **stqh_last; /* addr of last next element */ \ 324} 325 326#define STAILQ_HEAD_INITIALIZER(head) \ 327 { NULL, &(head).stqh_first } 328 329#define STAILQ_ENTRY(type) \ 330struct { \ 331 struct type *stqe_next; /* next element */ \ 332} 333 334#define STAILQ_CLASS_ENTRY(type) \ 335struct { \ 336 class type *stqe_next; /* next element */ \ 337} 338 339/* 340 * Singly-linked Tail queue functions. 341 */ 342#define STAILQ_CONCAT(head1, head2) do { \ 343 if (!STAILQ_EMPTY((head2))) { \ 344 *(head1)->stqh_last = (head2)->stqh_first; \ 345 (head1)->stqh_last = (head2)->stqh_last; \ 346 STAILQ_INIT((head2)); \ 347 } \ 348} while (0) 349 350#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 351 352#define STAILQ_FIRST(head) ((head)->stqh_first) 353 354#define STAILQ_FOREACH(var, head, field) \ 355 for((var) = STAILQ_FIRST((head)); \ 356 (var); \ 357 (var) = STAILQ_NEXT((var), field)) 358 359#define STAILQ_FOREACH_FROM(var, head, field) \ 360 for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 361 (var); \ 362 (var) = STAILQ_NEXT((var), field)) 363 364#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 365 for ((var) = STAILQ_FIRST((head)); \ 366 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 367 (var) = (tvar)) 368 369#define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 370 for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 371 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 372 (var) = (tvar)) 373 374#define STAILQ_INIT(head) do { \ 375 STAILQ_FIRST((head)) = NULL; \ 376 (head)->stqh_last = &STAILQ_FIRST((head)); \ 377} while (0) 378 379#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 380 if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 381 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 382 STAILQ_NEXT((tqelm), field) = (elm); \ 383} while (0) 384 385#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 386 if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 387 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 388 STAILQ_FIRST((head)) = (elm); \ 389} while (0) 390 391#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 392 STAILQ_NEXT((elm), field) = NULL; \ 393 *(head)->stqh_last = (elm); \ 394 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 395} while (0) 396 397#define STAILQ_LAST(head, type, field) \ 398 (STAILQ_EMPTY((head)) ? NULL : \ 399 __containerof((head)->stqh_last, \ 400 QUEUE_TYPEOF(type), field.stqe_next)) 401 402#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 403 404#define STAILQ_REMOVE(head, elm, type, field) do { \ 405 QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ 406 if (STAILQ_FIRST((head)) == (elm)) { \ 407 STAILQ_REMOVE_HEAD((head), field); \ 408 } \ 409 else { \ 410 QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \ 411 while (STAILQ_NEXT(curelm, field) != (elm)) \ 412 curelm = STAILQ_NEXT(curelm, field); \ 413 STAILQ_REMOVE_AFTER(head, curelm, field); \ 414 } \ 415 TRASHIT(*oldnext); \ 416} while (0) 417 418#define STAILQ_REMOVE_AFTER(head, elm, field) do { \ 419 if ((STAILQ_NEXT(elm, field) = \ 420 STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ 421 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 422} while (0) 423 424#define STAILQ_REMOVE_HEAD(head, field) do { \ 425 if ((STAILQ_FIRST((head)) = \ 426 STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 427 (head)->stqh_last = &STAILQ_FIRST((head)); \ 428} while (0) 429 430#define STAILQ_SWAP(head1, head2, type) do { \ 431 QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \ 432 QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \ 433 STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ 434 (head1)->stqh_last = (head2)->stqh_last; \ 435 STAILQ_FIRST(head2) = swap_first; \ 436 (head2)->stqh_last = swap_last; \ 437 if (STAILQ_EMPTY(head1)) \ 438 (head1)->stqh_last = &STAILQ_FIRST(head1); \ 439 if (STAILQ_EMPTY(head2)) \ 440 (head2)->stqh_last = &STAILQ_FIRST(head2); \ 441} while (0) 442 443 444/* 445 * List declarations. 446 */ 447#define LIST_HEAD(name, type) \ 448struct name { \ 449 struct type *lh_first; /* first element */ \ 450} 451 452#define LIST_CLASS_HEAD(name, type) \ 453struct name { \ 454 class type *lh_first; /* first element */ \ 455} 456 457#define LIST_HEAD_INITIALIZER(head) \ 458 { NULL } 459 460#define LIST_ENTRY(type) \ 461struct { \ 462 struct type *le_next; /* next element */ \ 463 struct type **le_prev; /* address of previous next element */ \ 464} 465 466#define LIST_CLASS_ENTRY(type) \ 467struct { \ 468 class type *le_next; /* next element */ \ 469 class type **le_prev; /* address of previous next element */ \ 470} 471 472/* 473 * List functions. 474 */ 475 476#if (defined(_KERNEL) && defined(INVARIANTS)) 477/* 478 * QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME) 479 * 480 * If the list is non-empty, validates that the first element of the list 481 * points back at 'head.' 482 */ 483#define QMD_LIST_CHECK_HEAD(head, field) do { \ 484 if (LIST_FIRST((head)) != NULL && \ 485 LIST_FIRST((head))->field.le_prev != \ 486 &LIST_FIRST((head))) \ 487 panic("Bad list head %p first->prev != head", (head)); \ 488} while (0) 489 490/* 491 * QMD_LIST_CHECK_NEXT(TYPE *elm, LIST_ENTRY NAME) 492 * 493 * If an element follows 'elm' in the list, validates that the next element 494 * points back at 'elm.' 495 */ 496#define QMD_LIST_CHECK_NEXT(elm, field) do { \ 497 if (LIST_NEXT((elm), field) != NULL && \ 498 LIST_NEXT((elm), field)->field.le_prev != \ 499 &((elm)->field.le_next)) \ 500 panic("Bad link elm %p next->prev != elm", (elm)); \ 501} while (0) 502 503/* 504 * QMD_LIST_CHECK_PREV(TYPE *elm, LIST_ENTRY NAME) 505 * 506 * Validates that the previous element (or head of the list) points to 'elm.' 507 */ 508#define QMD_LIST_CHECK_PREV(elm, field) do { \ 509 if (*(elm)->field.le_prev != (elm)) \ 510 panic("Bad link elm %p prev->next != elm", (elm)); \ 511} while (0) 512#else 513#define QMD_LIST_CHECK_HEAD(head, field) 514#define QMD_LIST_CHECK_NEXT(elm, field) 515#define QMD_LIST_CHECK_PREV(elm, field) 516#endif /* (_KERNEL && INVARIANTS) */ 517 518#define LIST_CONCAT(head1, head2, type, field) do { \ 519 QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \ 520 if (curelm == NULL) { \ 521 if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \ 522 LIST_FIRST(head2)->field.le_prev = \ 523 &LIST_FIRST((head1)); \ 524 LIST_INIT(head2); \ 525 } \ 526 } else if (LIST_FIRST(head2) != NULL) { \ 527 while (LIST_NEXT(curelm, field) != NULL) \ 528 curelm = LIST_NEXT(curelm, field); \ 529 LIST_NEXT(curelm, field) = LIST_FIRST(head2); \ 530 LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \ 531 LIST_INIT(head2); \ 532 } \ 533} while (0) 534 535#define LIST_EMPTY(head) ((head)->lh_first == NULL) 536 537#define LIST_FIRST(head) ((head)->lh_first) 538 539#define LIST_FOREACH(var, head, field) \ 540 for ((var) = LIST_FIRST((head)); \ 541 (var); \ 542 (var) = LIST_NEXT((var), field)) 543 544#define LIST_FOREACH_FROM(var, head, field) \ 545 for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 546 (var); \ 547 (var) = LIST_NEXT((var), field)) 548 549#define LIST_FOREACH_SAFE(var, head, field, tvar) \ 550 for ((var) = LIST_FIRST((head)); \ 551 (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 552 (var) = (tvar)) 553 554#define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 555 for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 556 (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 557 (var) = (tvar)) 558 559#define LIST_INIT(head) do { \ 560 LIST_FIRST((head)) = NULL; \ 561} while (0) 562 563#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 564 QMD_LIST_CHECK_NEXT(listelm, field); \ 565 if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 566 LIST_NEXT((listelm), field)->field.le_prev = \ 567 &LIST_NEXT((elm), field); \ 568 LIST_NEXT((listelm), field) = (elm); \ 569 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 570} while (0) 571 572#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 573 QMD_LIST_CHECK_PREV(listelm, field); \ 574 (elm)->field.le_prev = (listelm)->field.le_prev; \ 575 LIST_NEXT((elm), field) = (listelm); \ 576 *(listelm)->field.le_prev = (elm); \ 577 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 578} while (0) 579 580#define LIST_INSERT_HEAD(head, elm, field) do { \ 581 QMD_LIST_CHECK_HEAD((head), field); \ 582 if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 583 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 584 LIST_FIRST((head)) = (elm); \ 585 (elm)->field.le_prev = &LIST_FIRST((head)); \ 586} while (0) 587 588#define LIST_NEXT(elm, field) ((elm)->field.le_next) 589 590#define LIST_PREV(elm, head, type, field) \ 591 ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ 592 __containerof((elm)->field.le_prev, \ 593 QUEUE_TYPEOF(type), field.le_next)) 594 595#define LIST_REMOVE(elm, field) do { \ 596 QMD_SAVELINK(oldnext, (elm)->field.le_next); \ 597 QMD_SAVELINK(oldprev, (elm)->field.le_prev); \ 598 QMD_LIST_CHECK_NEXT(elm, field); \ 599 QMD_LIST_CHECK_PREV(elm, field); \ 600 if (LIST_NEXT((elm), field) != NULL) \ 601 LIST_NEXT((elm), field)->field.le_prev = \ 602 (elm)->field.le_prev; \ 603 *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 604 TRASHIT(*oldnext); \ 605 TRASHIT(*oldprev); \ 606} while (0) 607 608#define LIST_SWAP(head1, head2, type, field) do { \ 609 QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \ 610 LIST_FIRST((head1)) = LIST_FIRST((head2)); \ 611 LIST_FIRST((head2)) = swap_tmp; \ 612 if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ 613 swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ 614 if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ 615 swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ 616} while (0) 617 618/* 619 * Tail queue declarations. 620 */ 621#define TAILQ_HEAD(name, type) \ 622struct name { \ 623 struct type *tqh_first; /* first element */ \ 624 struct type **tqh_last; /* addr of last next element */ \ 625 TRACEBUF \ 626} 627 628#define TAILQ_CLASS_HEAD(name, type) \ 629struct name { \ 630 class type *tqh_first; /* first element */ \ 631 class type **tqh_last; /* addr of last next element */ \ 632 TRACEBUF \ 633} 634 635#define TAILQ_HEAD_INITIALIZER(head) \ 636 { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } 637 638#define TAILQ_ENTRY(type) \ 639struct { \ 640 struct type *tqe_next; /* next element */ \ 641 struct type **tqe_prev; /* address of previous next element */ \ 642 TRACEBUF \ 643} 644 645#define TAILQ_CLASS_ENTRY(type) \ 646struct { \ 647 class type *tqe_next; /* next element */ \ 648 class type **tqe_prev; /* address of previous next element */ \ 649 TRACEBUF \ 650} 651 652/* 653 * Tail queue functions. 654 */ 655#if (defined(_KERNEL) && defined(INVARIANTS)) 656/* 657 * QMD_TAILQ_CHECK_HEAD(TAILQ_HEAD *head, TAILQ_ENTRY NAME) 658 * 659 * If the tailq is non-empty, validates that the first element of the tailq 660 * points back at 'head.' 661 */ 662#define QMD_TAILQ_CHECK_HEAD(head, field) do { \ 663 if (!TAILQ_EMPTY(head) && \ 664 TAILQ_FIRST((head))->field.tqe_prev != \ 665 &TAILQ_FIRST((head))) \ 666 panic("Bad tailq head %p first->prev != head", (head)); \ 667} while (0) 668 669/* 670 * QMD_TAILQ_CHECK_TAIL(TAILQ_HEAD *head, TAILQ_ENTRY NAME) 671 * 672 * Validates that the tail of the tailq is a pointer to pointer to NULL. 673 */ 674#define QMD_TAILQ_CHECK_TAIL(head, field) do { \ 675 if (*(head)->tqh_last != NULL) \ 676 panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ 677} while (0) 678 679/* 680 * QMD_TAILQ_CHECK_NEXT(TYPE *elm, TAILQ_ENTRY NAME) 681 * 682 * If an element follows 'elm' in the tailq, validates that the next element 683 * points back at 'elm.' 684 */ 685#define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ 686 if (TAILQ_NEXT((elm), field) != NULL && \ 687 TAILQ_NEXT((elm), field)->field.tqe_prev != \ 688 &((elm)->field.tqe_next)) \ 689 panic("Bad link elm %p next->prev != elm", (elm)); \ 690} while (0) 691 692/* 693 * QMD_TAILQ_CHECK_PREV(TYPE *elm, TAILQ_ENTRY NAME) 694 * 695 * Validates that the previous element (or head of the tailq) points to 'elm.' 696 */ 697#define QMD_TAILQ_CHECK_PREV(elm, field) do { \ 698 if (*(elm)->field.tqe_prev != (elm)) \ 699 panic("Bad link elm %p prev->next != elm", (elm)); \ 700} while (0) 701#else 702#define QMD_TAILQ_CHECK_HEAD(head, field) 703#define QMD_TAILQ_CHECK_TAIL(head, headname) 704#define QMD_TAILQ_CHECK_NEXT(elm, field) 705#define QMD_TAILQ_CHECK_PREV(elm, field) 706#endif /* (_KERNEL && INVARIANTS) */ 707 708#define TAILQ_CONCAT(head1, head2, field) do { \ 709 if (!TAILQ_EMPTY(head2)) { \ 710 *(head1)->tqh_last = (head2)->tqh_first; \ 711 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 712 (head1)->tqh_last = (head2)->tqh_last; \ 713 TAILQ_INIT((head2)); \ 714 QMD_TRACE_HEAD(head1); \ 715 QMD_TRACE_HEAD(head2); \ 716 } \ 717} while (0) 718 719#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 720 721#define TAILQ_FIRST(head) ((head)->tqh_first) 722 723#define TAILQ_FOREACH(var, head, field) \ 724 for ((var) = TAILQ_FIRST((head)); \ 725 (var); \ 726 (var) = TAILQ_NEXT((var), field)) 727 728#define TAILQ_FOREACH_FROM(var, head, field) \ 729 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 730 (var); \ 731 (var) = TAILQ_NEXT((var), field)) 732 733#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 734 for ((var) = TAILQ_FIRST((head)); \ 735 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 736 (var) = (tvar)) 737 738#define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 739 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 740 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 741 (var) = (tvar)) 742 743#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 744 for ((var) = TAILQ_LAST((head), headname); \ 745 (var); \ 746 (var) = TAILQ_PREV((var), headname, field)) 747 748#define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \ 749 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 750 (var); \ 751 (var) = TAILQ_PREV((var), headname, field)) 752 753#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 754 for ((var) = TAILQ_LAST((head), headname); \ 755 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 756 (var) = (tvar)) 757 758#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \ 759 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 760 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 761 (var) = (tvar)) 762 763#define TAILQ_INIT(head) do { \ 764 TAILQ_FIRST((head)) = NULL; \ 765 (head)->tqh_last = &TAILQ_FIRST((head)); \ 766 QMD_TRACE_HEAD(head); \ 767} while (0) 768 769#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 770 QMD_TAILQ_CHECK_NEXT(listelm, field); \ 771 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 772 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 773 &TAILQ_NEXT((elm), field); \ 774 else { \ 775 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 776 QMD_TRACE_HEAD(head); \ 777 } \ 778 TAILQ_NEXT((listelm), field) = (elm); \ 779 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 780 QMD_TRACE_ELEM(&(elm)->field); \ 781 QMD_TRACE_ELEM(&(listelm)->field); \ 782} while (0) 783 784#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 785 QMD_TAILQ_CHECK_PREV(listelm, field); \ 786 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 787 TAILQ_NEXT((elm), field) = (listelm); \ 788 *(listelm)->field.tqe_prev = (elm); \ 789 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 790 QMD_TRACE_ELEM(&(elm)->field); \ 791 QMD_TRACE_ELEM(&(listelm)->field); \ 792} while (0) 793 794#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 795 QMD_TAILQ_CHECK_HEAD(head, field); \ 796 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 797 TAILQ_FIRST((head))->field.tqe_prev = \ 798 &TAILQ_NEXT((elm), field); \ 799 else \ 800 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 801 TAILQ_FIRST((head)) = (elm); \ 802 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 803 QMD_TRACE_HEAD(head); \ 804 QMD_TRACE_ELEM(&(elm)->field); \ 805} while (0) 806 807#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 808 QMD_TAILQ_CHECK_TAIL(head, field); \ 809 TAILQ_NEXT((elm), field) = NULL; \ 810 (elm)->field.tqe_prev = (head)->tqh_last; \ 811 *(head)->tqh_last = (elm); \ 812 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 813 QMD_TRACE_HEAD(head); \ 814 QMD_TRACE_ELEM(&(elm)->field); \ 815} while (0) 816 817#define TAILQ_LAST(head, headname) \ 818 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 819 820#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 821 822#define TAILQ_PREV(elm, headname, field) \ 823 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 824 825#define TAILQ_REMOVE(head, elm, field) do { \ 826 QMD_SAVELINK(oldnext, (elm)->field.tqe_next); \ 827 QMD_SAVELINK(oldprev, (elm)->field.tqe_prev); \ 828 QMD_TAILQ_CHECK_NEXT(elm, field); \ 829 QMD_TAILQ_CHECK_PREV(elm, field); \ 830 if ((TAILQ_NEXT((elm), field)) != NULL) \ 831 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 832 (elm)->field.tqe_prev; \ 833 else { \ 834 (head)->tqh_last = (elm)->field.tqe_prev; \ 835 QMD_TRACE_HEAD(head); \ 836 } \ 837 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 838 TRASHIT(*oldnext); \ 839 TRASHIT(*oldprev); \ 840 QMD_TRACE_ELEM(&(elm)->field); \ 841} while (0) 842 843#define TAILQ_SWAP(head1, head2, type, field) do { \ 844 QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \ 845 QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \ 846 (head1)->tqh_first = (head2)->tqh_first; \ 847 (head1)->tqh_last = (head2)->tqh_last; \ 848 (head2)->tqh_first = swap_first; \ 849 (head2)->tqh_last = swap_last; \ 850 if ((swap_first = (head1)->tqh_first) != NULL) \ 851 swap_first->field.tqe_prev = &(head1)->tqh_first; \ 852 else \ 853 (head1)->tqh_last = &(head1)->tqh_first; \ 854 if ((swap_first = (head2)->tqh_first) != NULL) \ 855 swap_first->field.tqe_prev = &(head2)->tqh_first; \ 856 else \ 857 (head2)->tqh_last = &(head2)->tqh_first; \ 858} while (0) 859 860#endif /* !_SYS_QUEUE_H_ */ 861