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