1 /*- 2 * SPDX-License-Identifier: BSD-3-Clause 3 * 4 * Copyright (c) 1991, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. Neither the name of the University nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 * 31 * @(#)queue.h 8.5 (Berkeley) 8/20/94 32 * $FreeBSD$ 33 */ 34 35 #ifndef _SYS_QUEUE_H_ 36 #define _SYS_QUEUE_H_ 37 38 #include <sys/cdefs.h> 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 */ 125 struct 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) \ 183 struct name { \ 184 struct type *slh_first; /* first element */ \ 185 } 186 187 #define SLIST_CLASS_HEAD(name, type) \ 188 struct name { \ 189 class type *slh_first; /* first element */ \ 190 } 191 192 #define SLIST_HEAD_INITIALIZER(head) \ 193 { NULL } 194 195 #define SLIST_ENTRY(type) \ 196 struct { \ 197 struct type *sle_next; /* next element */ \ 198 } 199 200 #define SLIST_CLASS_ENTRY(type) \ 201 struct { \ 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) \ 315 struct 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) \ 321 struct 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) \ 330 struct { \ 331 struct type *stqe_next; /* next element */ \ 332 } 333 334 #define STAILQ_CLASS_ENTRY(type) \ 335 struct { \ 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) \ 448 struct name { \ 449 struct type *lh_first; /* first element */ \ 450 } 451 452 #define LIST_CLASS_HEAD(name, type) \ 453 struct name { \ 454 class type *lh_first; /* first element */ \ 455 } 456 457 #define LIST_HEAD_INITIALIZER(head) \ 458 { NULL } 459 460 #define LIST_ENTRY(type) \ 461 struct { \ 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) \ 467 struct { \ 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) \ 622 struct 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) \ 629 struct 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) \ 639 struct { \ 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) \ 646 struct { \ 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