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 32 #ifndef _SYS_QUEUE_H_ 33 #define _SYS_QUEUE_H_ 34 35 #include <sys/cdefs.h> 36 37 /* 38 * This file defines four types of data structures: singly-linked lists, 39 * singly-linked tail queues, lists and tail queues. 40 * 41 * A singly-linked list is headed by a single forward pointer. The elements 42 * are singly linked for minimum space and pointer manipulation overhead at 43 * the expense of O(n) removal for arbitrary elements. New elements can be 44 * added to the list after an existing element or at the head of the list. 45 * Elements being removed from the head of the list should use the explicit 46 * macro for this purpose for optimum efficiency. A singly-linked list may 47 * only be traversed in the forward direction. Singly-linked lists are ideal 48 * for applications with large datasets and few or no removals or for 49 * implementing a LIFO queue. 50 * 51 * A singly-linked tail queue is headed by a pair of pointers, one to the 52 * head of the list and the other to the tail of the list. The elements are 53 * singly linked for minimum space and pointer manipulation overhead at the 54 * expense of O(n) removal for arbitrary elements. New elements can be added 55 * to the list after an existing element, at the head of the list, or at the 56 * end of the list. Elements being removed from the head of the tail queue 57 * should use the explicit macro for this purpose for optimum efficiency. 58 * A singly-linked tail queue may only be traversed in the forward direction. 59 * Singly-linked tail queues are ideal for applications with large datasets 60 * and few or no removals or for implementing a FIFO queue. 61 * 62 * A list is headed by a single forward pointer (or an array of forward 63 * pointers for a hash table header). The elements are doubly linked 64 * so that an arbitrary element can be removed without a need to 65 * traverse the list. New elements can be added to the list before 66 * or after an existing element or at the head of the list. A list 67 * may be traversed in either direction. 68 * 69 * A tail queue is headed by a pair of pointers, one to the head of the 70 * list and the other to the tail of the list. The elements are doubly 71 * linked so that an arbitrary element can be removed without a need to 72 * traverse the list. New elements can be added to the list before or 73 * after an existing element, at the head of the list, or at the end of 74 * the list. A tail queue may be traversed in either direction. 75 * 76 * For details on the use of these macros, see the queue(3) manual page. 77 * 78 * Below is a summary of implemented functions where: 79 * + means the macro is available 80 * - means the macro is not available 81 * s means the macro is available but is slow (runs in O(n) time) 82 * 83 * SLIST LIST STAILQ TAILQ 84 * _HEAD + + + + 85 * _CLASS_HEAD + + + + 86 * _HEAD_INITIALIZER + + + + 87 * _ENTRY + + + + 88 * _CLASS_ENTRY + + + + 89 * _INIT + + + + 90 * _EMPTY + + + + 91 * _END + + + + 92 * _FIRST + + + + 93 * _NEXT + + + + 94 * _PREV - + - + 95 * _LAST - - + + 96 * _LAST_FAST - - - + 97 * _FOREACH + + + + 98 * _FOREACH_FROM + + + + 99 * _FOREACH_SAFE + + + + 100 * _FOREACH_FROM_SAFE + + + + 101 * _FOREACH_REVERSE - - - + 102 * _FOREACH_REVERSE_FROM - - - + 103 * _FOREACH_REVERSE_SAFE - - - + 104 * _FOREACH_REVERSE_FROM_SAFE - - - + 105 * _INSERT_HEAD + + + + 106 * _INSERT_BEFORE - + - + 107 * _INSERT_AFTER + + + + 108 * _INSERT_TAIL - - + + 109 * _CONCAT s s + + 110 * _REMOVE_AFTER + - + - 111 * _REMOVE_HEAD + + + + 112 * _REMOVE s + s + 113 * _REPLACE - + - + 114 * _SPLIT_AFTER + + + + 115 * _SWAP + + + + 116 * 117 */ 118 #ifdef QUEUE_MACRO_DEBUG 119 #warn Use QUEUE_MACRO_DEBUG_xxx instead (TRACE, TRASH and/or ASSERTIONS) 120 #define QUEUE_MACRO_DEBUG_TRACE 121 #define QUEUE_MACRO_DEBUG_TRASH 122 #endif 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 QMD_SAVELINK(name, link) void **name = (void *)&(link) 158 #define TRASHIT(x) do {(x) = (void *)-1;} while (0) 159 #define QMD_IS_TRASHED(x) ((x) == (void *)(intptr_t)-1) 160 #else /* !QUEUE_MACRO_DEBUG_TRASH */ 161 #define QMD_SAVELINK(name, link) 162 #define TRASHIT(x) 163 #define QMD_IS_TRASHED(x) 0 164 #endif /* QUEUE_MACRO_DEBUG_TRASH */ 165 166 #if defined(QUEUE_MACRO_DEBUG_ASSERTIONS) && \ 167 defined(QUEUE_MACRO_NO_DEBUG_ASSERTIONS) 168 #error Both QUEUE_MACRO_DEBUG_ASSERTIONS and QUEUE_MACRO_NO_DEBUG_ASSERTIONS defined 169 #endif 170 171 /* 172 * Automatically define QUEUE_MACRO_DEBUG_ASSERTIONS when compiling the kernel 173 * with INVARIANTS, if not already defined and not prevented by presence of 174 * QUEUE_MACRO_NO_DEBUG_ASSERTIONS. 175 */ 176 #if !defined(QUEUE_MACRO_DEBUG_ASSERTIONS) && \ 177 !defined(QUEUE_MACRO_NO_DEBUG_ASSERTIONS) && \ 178 (defined(_KERNEL) && defined(INVARIANTS)) 179 #define QUEUE_MACRO_DEBUG_ASSERTIONS 180 #endif 181 182 /* 183 * If queue assertions are enabled, provide default definitions for QMD_PANIC() 184 * and QMD_ASSERT() if undefined. 185 */ 186 #ifdef QUEUE_MACRO_DEBUG_ASSERTIONS 187 #ifndef QMD_PANIC 188 #if defined(_KERNEL) || defined(_STANDALONE) 189 /* 190 * On _STANDALONE, either <stand.h> or the headers using <sys/queue.h> provide 191 * a declaration or macro for panic(). 192 */ 193 #ifdef _KERNEL 194 #include <sys/kassert.h> 195 #endif 196 #define QMD_PANIC(fmt, ...) do { \ 197 panic(fmt, ##__VA_ARGS__); \ 198 } while (0) 199 #else /* !(_KERNEL || _STANDALONE) */ 200 #include <stdio.h> 201 #include <stdlib.h> 202 #define QMD_PANIC(fmt, ...) do { \ 203 fprintf(stderr, fmt "\n", ##__VA_ARGS__); \ 204 abort(); \ 205 } while (0) 206 #endif /* _KERNEL || _STANDALONE */ 207 #endif /* !QMD_PANIC */ 208 209 #ifndef QMD_ASSERT 210 #define QMD_ASSERT(expression, fmt, ...) do { \ 211 if (__predict_false(!(expression))) \ 212 QMD_PANIC("%s:%u: %s: " fmt, \ 213 __FILE__, __LINE__, __func__, ##__VA_ARGS__); \ 214 } while (0) 215 #endif /* !QMD_ASSERT */ 216 #else /* !QUEUE_MACRO_DEBUG_ASSERTIONS */ 217 #undef QMD_ASSERT 218 #define QMD_ASSERT(test, fmt, ...) do {} while (0) 219 #endif /* QUEUE_MACRO_DEBUG_ASSERTIONS */ 220 221 222 #ifdef __cplusplus 223 /* 224 * In C++ there can be structure lists and class lists: 225 */ 226 #define QUEUE_TYPEOF(type) type 227 #else 228 #define QUEUE_TYPEOF(type) struct type 229 #endif 230 231 /* 232 * Singly-linked List declarations. 233 */ 234 235 #define SLIST_HEAD(name, type) \ 236 struct name { \ 237 struct type *slh_first; /* first element */ \ 238 } 239 240 #define SLIST_CLASS_HEAD(name, type) \ 241 struct name { \ 242 class type *slh_first; /* first element */ \ 243 } 244 245 #define SLIST_HEAD_INITIALIZER(head) \ 246 { NULL } 247 248 #define SLIST_ENTRY(type) \ 249 struct { \ 250 struct type *sle_next; /* next element */ \ 251 } 252 253 #define SLIST_CLASS_ENTRY(type) \ 254 struct { \ 255 class type *sle_next; /* next element */ \ 256 } 257 258 /* 259 * Singly-linked List functions. 260 */ 261 262 #define QMD_SLIST_CHECK_PREVPTR(prevp, elm) \ 263 QMD_ASSERT(*(prevp) == (elm), \ 264 "Bad prevptr *(%p) == %p != %p", \ 265 (prevp), *(prevp), (elm)) 266 267 #define SLIST_ASSERT_EMPTY(head) \ 268 QMD_ASSERT(SLIST_EMPTY((head)), \ 269 "slist %p is not empty", (head)) 270 271 #define SLIST_ASSERT_NONEMPTY(head) \ 272 QMD_ASSERT(!SLIST_EMPTY((head)), \ 273 "slist %p is empty", (head)) 274 275 #define SLIST_CONCAT(head1, head2, type, field) do { \ 276 QUEUE_TYPEOF(type) *_Curelm = SLIST_FIRST(head1); \ 277 if (_Curelm == NULL) { \ 278 if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL) \ 279 SLIST_INIT(head2); \ 280 } else if (SLIST_FIRST(head2) != NULL) { \ 281 while (SLIST_NEXT(_Curelm, field) != NULL) \ 282 _Curelm = SLIST_NEXT(_Curelm, field); \ 283 SLIST_NEXT(_Curelm, field) = SLIST_FIRST(head2); \ 284 SLIST_INIT(head2); \ 285 } \ 286 } while (0) 287 288 #define SLIST_EMPTY(head) ((head)->slh_first == NULL) 289 290 #define SLIST_EMPTY_ATOMIC(head) \ 291 (atomic_load_ptr(&(head)->slh_first) == NULL) 292 293 #define SLIST_FIRST(head) ((head)->slh_first) 294 295 #define SLIST_FOREACH(var, head, field) \ 296 for ((var) = SLIST_FIRST((head)); \ 297 (var); \ 298 (var) = SLIST_NEXT((var), field)) 299 300 #define SLIST_FOREACH_FROM(var, head, field) \ 301 for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 302 (var); \ 303 (var) = SLIST_NEXT((var), field)) 304 305 #define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 306 for ((var) = SLIST_FIRST((head)); \ 307 (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 308 (var) = (tvar)) 309 310 #define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 311 for ((var) = ((var) ? (var) : SLIST_FIRST((head))); \ 312 (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 313 (var) = (tvar)) 314 315 #define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 316 for ((varp) = &SLIST_FIRST((head)); \ 317 ((var) = *(varp)) != NULL; \ 318 (varp) = &SLIST_NEXT((var), field)) 319 320 #define SLIST_INIT(head) do { \ 321 SLIST_FIRST((head)) = NULL; \ 322 } while (0) 323 324 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 325 SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 326 SLIST_NEXT((slistelm), field) = (elm); \ 327 } while (0) 328 329 #define SLIST_INSERT_HEAD(head, elm, field) do { \ 330 SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 331 SLIST_FIRST((head)) = (elm); \ 332 } while (0) 333 334 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 335 336 #define SLIST_REMOVE(head, elm, type, field) do { \ 337 if (SLIST_FIRST((head)) == (elm)) { \ 338 SLIST_REMOVE_HEAD((head), field); \ 339 } \ 340 else { \ 341 QUEUE_TYPEOF(type) *_Curelm = SLIST_FIRST(head); \ 342 while (SLIST_NEXT(_Curelm, field) != (elm)) \ 343 _Curelm = SLIST_NEXT(_Curelm, field); \ 344 SLIST_REMOVE_AFTER(_Curelm, field); \ 345 } \ 346 } while (0) 347 348 #define SLIST_REMOVE_AFTER(elm, field) do { \ 349 QMD_SAVELINK(_Oldnext, SLIST_NEXT(elm, field)->field.sle_next); \ 350 SLIST_NEXT(elm, field) = \ 351 SLIST_NEXT(SLIST_NEXT(elm, field), field); \ 352 TRASHIT(*_Oldnext); \ 353 } while (0) 354 355 #define SLIST_REMOVE_HEAD(head, field) do { \ 356 QMD_SAVELINK(_Oldnext, SLIST_FIRST(head)->field.sle_next); \ 357 SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 358 TRASHIT(*_Oldnext); \ 359 } while (0) 360 361 #define SLIST_REMOVE_PREVPTR(prevp, elm, field) do { \ 362 QMD_SLIST_CHECK_PREVPTR(prevp, elm); \ 363 *(prevp) = SLIST_NEXT(elm, field); \ 364 TRASHIT((elm)->field.sle_next); \ 365 } while (0) 366 367 #define SLIST_SPLIT_AFTER(head, elm, rest, field) do { \ 368 SLIST_ASSERT_NONEMPTY((head)); \ 369 SLIST_FIRST((rest)) = SLIST_NEXT((elm), field); \ 370 SLIST_NEXT((elm), field) = NULL; \ 371 } while (0) 372 373 #define SLIST_SWAP(head1, head2, type) do { \ 374 QUEUE_TYPEOF(type) *_Swap_first = SLIST_FIRST(head1); \ 375 SLIST_FIRST(head1) = SLIST_FIRST(head2); \ 376 SLIST_FIRST(head2) = _Swap_first; \ 377 } while (0) 378 379 #define SLIST_END(head) NULL 380 381 /* 382 * Singly-linked Tail queue declarations. 383 */ 384 385 #define STAILQ_HEAD(name, type) \ 386 struct name { \ 387 struct type *stqh_first;/* first element */ \ 388 struct type **stqh_last;/* addr of last next element */ \ 389 } 390 391 #define STAILQ_CLASS_HEAD(name, type) \ 392 struct name { \ 393 class type *stqh_first; /* first element */ \ 394 class type **stqh_last; /* addr of last next element */ \ 395 } 396 397 #define STAILQ_HEAD_INITIALIZER(head) \ 398 { NULL, &(head).stqh_first } 399 400 #define STAILQ_ENTRY(type) \ 401 struct { \ 402 struct type *stqe_next; /* next element */ \ 403 } 404 405 #define STAILQ_CLASS_ENTRY(type) \ 406 struct { \ 407 class type *stqe_next; /* next element */ \ 408 } 409 410 /* 411 * Singly-linked Tail queue functions. 412 */ 413 414 /* 415 * QMD_STAILQ_CHECK_EMPTY(STAILQ_HEAD *head) 416 * 417 * Validates that the stailq head's pointer to the last element's next pointer 418 * actually points to the head's first element pointer field. 419 */ 420 #define QMD_STAILQ_CHECK_EMPTY(head) \ 421 QMD_ASSERT((head)->stqh_last == &(head)->stqh_first, \ 422 "Empty stailq %p->stqh_last is %p, " \ 423 "not head's first field address", \ 424 (head), (head)->stqh_last) 425 426 /* 427 * QMD_STAILQ_CHECK_TAIL(STAILQ_HEAD *head) 428 * 429 * Validates that the stailq's last element's next pointer is NULL. 430 */ 431 #define QMD_STAILQ_CHECK_TAIL(head) \ 432 QMD_ASSERT(*(head)->stqh_last == NULL, \ 433 "Stailq %p last element's next pointer is " \ 434 "%p, not NULL", (head), *(head)->stqh_last) 435 436 #define STAILQ_ASSERT_EMPTY(head) \ 437 QMD_ASSERT(STAILQ_EMPTY((head)), \ 438 "stailq %p is not empty", (head)) 439 440 #define STAILQ_ASSERT_NONEMPTY(head) \ 441 QMD_ASSERT(!STAILQ_EMPTY((head)), \ 442 "stailq %p is empty", (head)) 443 444 #define STAILQ_CONCAT(head1, head2) do { \ 445 if (!STAILQ_EMPTY((head2))) { \ 446 *(head1)->stqh_last = (head2)->stqh_first; \ 447 (head1)->stqh_last = (head2)->stqh_last; \ 448 STAILQ_INIT((head2)); \ 449 } \ 450 } while (0) 451 452 #define STAILQ_EMPTY(head) ({ \ 453 if (STAILQ_FIRST(head) == NULL) \ 454 QMD_STAILQ_CHECK_EMPTY(head); \ 455 STAILQ_FIRST(head) == NULL; \ 456 }) 457 458 #define STAILQ_EMPTY_ATOMIC(head) \ 459 (atomic_load_ptr(&(head)->stqh_first) == NULL) 460 461 #define STAILQ_FIRST(head) ((head)->stqh_first) 462 463 #define STAILQ_FOREACH(var, head, field) \ 464 for((var) = STAILQ_FIRST((head)); \ 465 (var); \ 466 (var) = STAILQ_NEXT((var), field)) 467 468 #define STAILQ_FOREACH_FROM(var, head, field) \ 469 for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 470 (var); \ 471 (var) = STAILQ_NEXT((var), field)) 472 473 #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 474 for ((var) = STAILQ_FIRST((head)); \ 475 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 476 (var) = (tvar)) 477 478 #define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 479 for ((var) = ((var) ? (var) : STAILQ_FIRST((head))); \ 480 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 481 (var) = (tvar)) 482 483 #define STAILQ_INIT(head) do { \ 484 STAILQ_FIRST((head)) = NULL; \ 485 (head)->stqh_last = &STAILQ_FIRST((head)); \ 486 } while (0) 487 488 #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 489 if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 490 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 491 STAILQ_NEXT((tqelm), field) = (elm); \ 492 } while (0) 493 494 #define STAILQ_INSERT_HEAD(head, elm, field) do { \ 495 if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 496 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 497 STAILQ_FIRST((head)) = (elm); \ 498 } while (0) 499 500 #define STAILQ_INSERT_TAIL(head, elm, field) do { \ 501 QMD_STAILQ_CHECK_TAIL(head); \ 502 STAILQ_NEXT((elm), field) = NULL; \ 503 *(head)->stqh_last = (elm); \ 504 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 505 } while (0) 506 507 #define STAILQ_LAST(head, type, field) \ 508 (STAILQ_EMPTY((head)) ? NULL : \ 509 __containerof((head)->stqh_last, \ 510 QUEUE_TYPEOF(type), field.stqe_next)) 511 512 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 513 514 #define STAILQ_REMOVE(head, elm, type, field) do { \ 515 QMD_SAVELINK(_Oldnext, (elm)->field.stqe_next); \ 516 if (STAILQ_FIRST((head)) == (elm)) { \ 517 STAILQ_REMOVE_HEAD((head), field); \ 518 } \ 519 else { \ 520 QUEUE_TYPEOF(type) *_Curelm = STAILQ_FIRST(head); \ 521 while (STAILQ_NEXT(_Curelm, field) != (elm)) \ 522 _Curelm = STAILQ_NEXT(_Curelm, field); \ 523 STAILQ_REMOVE_AFTER(head, _Curelm, field); \ 524 } \ 525 TRASHIT(*_Oldnext); \ 526 } while (0) 527 528 #define STAILQ_REMOVE_AFTER(head, elm, field) do { \ 529 if ((STAILQ_NEXT(elm, field) = \ 530 STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ 531 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 532 } while (0) 533 534 #define STAILQ_REMOVE_HEAD(head, field) do { \ 535 if ((STAILQ_FIRST((head)) = \ 536 STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 537 (head)->stqh_last = &STAILQ_FIRST((head)); \ 538 } while (0) 539 540 #define STAILQ_SPLIT_AFTER(head, elm, rest, field) do { \ 541 STAILQ_ASSERT_NONEMPTY((head)); \ 542 QMD_STAILQ_CHECK_TAIL((head)); \ 543 if (STAILQ_NEXT((elm), field) == NULL) \ 544 /* 'elm' is the last element in 'head'. */ \ 545 STAILQ_INIT((rest)); \ 546 else { \ 547 STAILQ_FIRST((rest)) = STAILQ_NEXT((elm), field); \ 548 (rest)->stqh_last = (head)->stqh_last; \ 549 STAILQ_NEXT((elm), field) = NULL; \ 550 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 551 } \ 552 } while (0) 553 554 #define STAILQ_SWAP(head1, head2, type) do { \ 555 QUEUE_TYPEOF(type) *_Swap_first = STAILQ_FIRST(head1); \ 556 QUEUE_TYPEOF(type) **_Swap_last = (head1)->stqh_last; \ 557 STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ 558 (head1)->stqh_last = (head2)->stqh_last; \ 559 STAILQ_FIRST(head2) = _Swap_first; \ 560 (head2)->stqh_last = _Swap_last; \ 561 if (STAILQ_FIRST(head1) == NULL) \ 562 (head1)->stqh_last = &STAILQ_FIRST(head1); \ 563 if (STAILQ_FIRST(head2) == NULL) \ 564 (head2)->stqh_last = &STAILQ_FIRST(head2); \ 565 } while (0) 566 567 #define STAILQ_REVERSE(head, type, field) do { \ 568 if (STAILQ_EMPTY(head)) \ 569 break; \ 570 QUEUE_TYPEOF(type) *_Var, *_Varp, *_Varn; \ 571 for (_Var = STAILQ_FIRST(head), _Varp = NULL; \ 572 _Var != NULL;) { \ 573 _Varn = STAILQ_NEXT(_Var, field); \ 574 STAILQ_NEXT(_Var, field) = _Varp; \ 575 _Varp = _Var; \ 576 _Var = _Varn; \ 577 } \ 578 (head)->stqh_last = &STAILQ_NEXT(STAILQ_FIRST(head), field); \ 579 (head)->stqh_first = _Varp; \ 580 } while (0) 581 582 #define STAILQ_END(head) NULL 583 584 585 /* 586 * List declarations. 587 */ 588 589 #define LIST_HEAD(name, type) \ 590 struct name { \ 591 struct type *lh_first; /* first element */ \ 592 } 593 594 #define LIST_CLASS_HEAD(name, type) \ 595 struct name { \ 596 class type *lh_first; /* first element */ \ 597 } 598 599 #define LIST_HEAD_INITIALIZER(head) \ 600 { NULL } 601 602 #define LIST_ENTRY(type) \ 603 struct { \ 604 struct type *le_next; /* next element */ \ 605 struct type **le_prev; /* address of previous next element */ \ 606 } 607 608 #define LIST_CLASS_ENTRY(type) \ 609 struct { \ 610 class type *le_next; /* next element */ \ 611 class type **le_prev; /* address of previous next element */ \ 612 } 613 614 /* 615 * List functions. 616 */ 617 618 /* 619 * QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME) 620 * 621 * If the list is non-empty, validates that the first element of the list 622 * points back at 'head.' 623 */ 624 #define QMD_LIST_CHECK_HEAD(head, field) \ 625 QMD_ASSERT(LIST_FIRST((head)) == NULL || \ 626 LIST_FIRST((head))->field.le_prev == \ 627 &LIST_FIRST((head)), \ 628 "Bad list head %p first->prev != head", \ 629 (head)) 630 631 /* 632 * QMD_LIST_CHECK_NEXT(TYPE *elm, LIST_ENTRY NAME) 633 * 634 * If an element follows 'elm' in the list, validates that the next element 635 * points back at 'elm.' 636 */ 637 #define QMD_LIST_CHECK_NEXT(elm, field) \ 638 QMD_ASSERT(LIST_NEXT((elm), field) == NULL || \ 639 LIST_NEXT((elm), field)->field.le_prev == \ 640 &((elm)->field.le_next), \ 641 "Bad link elm %p next->prev != elm", (elm)) 642 643 /* 644 * QMD_LIST_CHECK_PREV(TYPE *elm, LIST_ENTRY NAME) 645 * 646 * Validates that the previous element (or head of the list) points to 'elm.' 647 */ 648 #define QMD_LIST_CHECK_PREV(elm, field) \ 649 QMD_ASSERT(*(elm)->field.le_prev == (elm), \ 650 "Bad link elm %p prev->next != elm", (elm)) 651 652 #define LIST_ASSERT_EMPTY(head) \ 653 QMD_ASSERT(LIST_EMPTY((head)), \ 654 "list %p is not empty", (head)) 655 656 #define LIST_ASSERT_NONEMPTY(head) \ 657 QMD_ASSERT(!LIST_EMPTY((head)), \ 658 "list %p is empty", (head)) 659 660 #define LIST_CONCAT(head1, head2, type, field) do { \ 661 QUEUE_TYPEOF(type) *_Curelm = LIST_FIRST(head1); \ 662 if (_Curelm == NULL) { \ 663 if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \ 664 LIST_FIRST(head2)->field.le_prev = \ 665 &LIST_FIRST((head1)); \ 666 LIST_INIT(head2); \ 667 } \ 668 } else if (LIST_FIRST(head2) != NULL) { \ 669 while (LIST_NEXT(_Curelm, field) != NULL) \ 670 _Curelm = LIST_NEXT(_Curelm, field); \ 671 LIST_NEXT(_Curelm, field) = LIST_FIRST(head2); \ 672 LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(_Curelm, field);\ 673 LIST_INIT(head2); \ 674 } \ 675 } while (0) 676 677 #define LIST_EMPTY(head) ((head)->lh_first == NULL) 678 679 #define LIST_EMPTY_ATOMIC(head) \ 680 (atomic_load_ptr(&(head)->lh_first) == NULL) 681 682 #define LIST_FIRST(head) ((head)->lh_first) 683 684 #define LIST_FOREACH(var, head, field) \ 685 for ((var) = LIST_FIRST((head)); \ 686 (var); \ 687 (var) = LIST_NEXT((var), field)) 688 689 #define LIST_FOREACH_FROM(var, head, field) \ 690 for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 691 (var); \ 692 (var) = LIST_NEXT((var), field)) 693 694 #define LIST_FOREACH_SAFE(var, head, field, tvar) \ 695 for ((var) = LIST_FIRST((head)); \ 696 (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 697 (var) = (tvar)) 698 699 #define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 700 for ((var) = ((var) ? (var) : LIST_FIRST((head))); \ 701 (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 702 (var) = (tvar)) 703 704 #define LIST_INIT(head) do { \ 705 LIST_FIRST((head)) = NULL; \ 706 } while (0) 707 708 #define LIST_INSERT_AFTER(listelm, elm, field) do { \ 709 QMD_LIST_CHECK_NEXT(listelm, field); \ 710 if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 711 LIST_NEXT((listelm), field)->field.le_prev = \ 712 &LIST_NEXT((elm), field); \ 713 LIST_NEXT((listelm), field) = (elm); \ 714 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 715 } while (0) 716 717 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 718 QMD_LIST_CHECK_PREV(listelm, field); \ 719 (elm)->field.le_prev = (listelm)->field.le_prev; \ 720 LIST_NEXT((elm), field) = (listelm); \ 721 *(listelm)->field.le_prev = (elm); \ 722 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 723 } while (0) 724 725 #define LIST_INSERT_HEAD(head, elm, field) do { \ 726 QMD_LIST_CHECK_HEAD((head), field); \ 727 if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 728 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 729 LIST_FIRST((head)) = (elm); \ 730 (elm)->field.le_prev = &LIST_FIRST((head)); \ 731 } while (0) 732 733 #define LIST_NEXT(elm, field) ((elm)->field.le_next) 734 735 #define LIST_PREV(elm, head, type, field) \ 736 ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ 737 __containerof((elm)->field.le_prev, \ 738 QUEUE_TYPEOF(type), field.le_next)) 739 740 #define LIST_REMOVE_HEAD(head, field) \ 741 LIST_REMOVE(LIST_FIRST(head), field) 742 743 #define LIST_REMOVE(elm, field) do { \ 744 QMD_SAVELINK(_Oldnext, (elm)->field.le_next); \ 745 QMD_SAVELINK(_Oldprev, (elm)->field.le_prev); \ 746 QMD_LIST_CHECK_NEXT(elm, field); \ 747 QMD_LIST_CHECK_PREV(elm, field); \ 748 if (LIST_NEXT((elm), field) != NULL) \ 749 LIST_NEXT((elm), field)->field.le_prev = \ 750 (elm)->field.le_prev; \ 751 *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 752 TRASHIT(*_Oldnext); \ 753 TRASHIT(*_Oldprev); \ 754 } while (0) 755 756 #define LIST_REPLACE(elm, elm2, field) do { \ 757 QMD_SAVELINK(_Oldnext, (elm)->field.le_next); \ 758 QMD_SAVELINK(_Oldprev, (elm)->field.le_prev); \ 759 QMD_LIST_CHECK_NEXT(elm, field); \ 760 QMD_LIST_CHECK_PREV(elm, field); \ 761 LIST_NEXT((elm2), field) = LIST_NEXT((elm), field); \ 762 if (LIST_NEXT((elm2), field) != NULL) \ 763 LIST_NEXT((elm2), field)->field.le_prev = \ 764 &(elm2)->field.le_next; \ 765 (elm2)->field.le_prev = (elm)->field.le_prev; \ 766 *(elm2)->field.le_prev = (elm2); \ 767 TRASHIT(*_Oldnext); \ 768 TRASHIT(*_Oldprev); \ 769 } while (0) 770 771 #define LIST_SPLIT_AFTER(head, elm, rest, field) do { \ 772 LIST_ASSERT_NONEMPTY((head)); \ 773 if (LIST_NEXT((elm), field) == NULL) \ 774 /* 'elm' is the last element in 'head'. */ \ 775 LIST_INIT((rest)); \ 776 else { \ 777 LIST_FIRST((rest)) = LIST_NEXT((elm), field); \ 778 LIST_NEXT((elm), field)->field.le_prev = \ 779 &LIST_FIRST((rest)); \ 780 LIST_NEXT((elm), field) = NULL; \ 781 } \ 782 } while (0) 783 784 #define LIST_SWAP(head1, head2, type, field) do { \ 785 QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \ 786 LIST_FIRST((head1)) = LIST_FIRST((head2)); \ 787 LIST_FIRST((head2)) = swap_tmp; \ 788 if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ 789 swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ 790 if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ 791 swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ 792 } while (0) 793 794 #define LIST_END(head) NULL 795 796 /* 797 * Tail queue declarations. 798 */ 799 800 #define TAILQ_HEAD(name, type) \ 801 struct name { \ 802 struct type *tqh_first; /* first element */ \ 803 struct type **tqh_last; /* addr of last next element */ \ 804 TRACEBUF \ 805 } 806 807 #define TAILQ_CLASS_HEAD(name, type) \ 808 struct name { \ 809 class type *tqh_first; /* first element */ \ 810 class type **tqh_last; /* addr of last next element */ \ 811 TRACEBUF \ 812 } 813 814 #define TAILQ_HEAD_INITIALIZER(head) \ 815 { NULL, &(head).tqh_first, TRACEBUF_INITIALIZER } 816 817 #define TAILQ_ENTRY(type) \ 818 struct { \ 819 struct type *tqe_next; /* next element */ \ 820 struct type **tqe_prev; /* address of previous next element */ \ 821 TRACEBUF \ 822 } 823 824 #define TAILQ_CLASS_ENTRY(type) \ 825 struct { \ 826 class type *tqe_next; /* next element */ \ 827 class type **tqe_prev; /* address of previous next element */ \ 828 TRACEBUF \ 829 } 830 831 /* 832 * Tail queue functions. 833 */ 834 835 /* 836 * QMD_TAILQ_CHECK_HEAD(TAILQ_HEAD *head, TAILQ_ENTRY NAME) 837 * 838 * If the tailq is non-empty, validates that the first element of the tailq 839 * points back at 'head.' 840 */ 841 #define QMD_TAILQ_CHECK_HEAD(head, field) \ 842 QMD_ASSERT(TAILQ_EMPTY(head) || \ 843 TAILQ_FIRST((head))->field.tqe_prev == \ 844 &TAILQ_FIRST((head)), \ 845 "Bad tailq head %p first->prev != head", \ 846 (head)) 847 848 /* 849 * QMD_TAILQ_CHECK_TAIL(TAILQ_HEAD *head, TAILQ_ENTRY NAME) 850 * 851 * Validates that the tail of the tailq is a pointer to pointer to NULL. 852 */ 853 #define QMD_TAILQ_CHECK_TAIL(head, field) \ 854 QMD_ASSERT(*(head)->tqh_last == NULL, \ 855 "Bad tailq NEXT(%p->tqh_last) != NULL", \ 856 (head)) 857 858 /* 859 * QMD_TAILQ_CHECK_NEXT(TYPE *elm, TAILQ_ENTRY NAME) 860 * 861 * If an element follows 'elm' in the tailq, validates that the next element 862 * points back at 'elm.' 863 */ 864 #define QMD_TAILQ_CHECK_NEXT(elm, field) \ 865 QMD_ASSERT(TAILQ_NEXT((elm), field) == NULL || \ 866 TAILQ_NEXT((elm), field)->field.tqe_prev == \ 867 &((elm)->field.tqe_next), \ 868 "Bad link elm %p next->prev != elm", (elm)) 869 870 /* 871 * QMD_TAILQ_CHECK_PREV(TYPE *elm, TAILQ_ENTRY NAME) 872 * 873 * Validates that the previous element (or head of the tailq) points to 'elm.' 874 */ 875 #define QMD_TAILQ_CHECK_PREV(elm, field) \ 876 QMD_ASSERT(*(elm)->field.tqe_prev == (elm), \ 877 "Bad link elm %p prev->next != elm", (elm)) 878 879 #define TAILQ_ASSERT_EMPTY(head) \ 880 QMD_ASSERT(TAILQ_EMPTY((head)), \ 881 "tailq %p is not empty", (head)) 882 883 #define TAILQ_ASSERT_NONEMPTY(head) \ 884 QMD_ASSERT(!TAILQ_EMPTY((head)), \ 885 "tailq %p is empty", (head)) 886 887 #define TAILQ_CONCAT(head1, head2, field) do { \ 888 if (!TAILQ_EMPTY(head2)) { \ 889 *(head1)->tqh_last = (head2)->tqh_first; \ 890 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 891 (head1)->tqh_last = (head2)->tqh_last; \ 892 TAILQ_INIT((head2)); \ 893 QMD_TRACE_HEAD(head1); \ 894 QMD_TRACE_HEAD(head2); \ 895 } \ 896 } while (0) 897 898 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 899 900 #define TAILQ_EMPTY_ATOMIC(head) \ 901 (atomic_load_ptr(&(head)->tqh_first) == NULL) 902 903 #define TAILQ_FIRST(head) ((head)->tqh_first) 904 905 #define TAILQ_FOREACH(var, head, field) \ 906 for ((var) = TAILQ_FIRST((head)); \ 907 (var); \ 908 (var) = TAILQ_NEXT((var), field)) 909 910 #define TAILQ_FOREACH_FROM(var, head, field) \ 911 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 912 (var); \ 913 (var) = TAILQ_NEXT((var), field)) 914 915 #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 916 for ((var) = TAILQ_FIRST((head)); \ 917 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 918 (var) = (tvar)) 919 920 #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 921 for ((var) = ((var) ? (var) : TAILQ_FIRST((head))); \ 922 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 923 (var) = (tvar)) 924 925 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 926 for ((var) = TAILQ_LAST((head), headname); \ 927 (var); \ 928 (var) = TAILQ_PREV((var), headname, field)) 929 930 #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \ 931 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 932 (var); \ 933 (var) = TAILQ_PREV((var), headname, field)) 934 935 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 936 for ((var) = TAILQ_LAST((head), headname); \ 937 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 938 (var) = (tvar)) 939 940 #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar)\ 941 for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \ 942 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 943 (var) = (tvar)) 944 945 #define TAILQ_INIT(head) do { \ 946 TAILQ_FIRST((head)) = NULL; \ 947 (head)->tqh_last = &TAILQ_FIRST((head)); \ 948 QMD_TRACE_HEAD(head); \ 949 } while (0) 950 951 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 952 QMD_TAILQ_CHECK_NEXT(listelm, field); \ 953 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 954 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 955 &TAILQ_NEXT((elm), field); \ 956 else { \ 957 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 958 QMD_TRACE_HEAD(head); \ 959 } \ 960 TAILQ_NEXT((listelm), field) = (elm); \ 961 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 962 QMD_TRACE_ELEM(&(elm)->field); \ 963 QMD_TRACE_ELEM(&(listelm)->field); \ 964 } while (0) 965 966 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 967 QMD_TAILQ_CHECK_PREV(listelm, field); \ 968 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 969 TAILQ_NEXT((elm), field) = (listelm); \ 970 *(listelm)->field.tqe_prev = (elm); \ 971 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 972 QMD_TRACE_ELEM(&(elm)->field); \ 973 QMD_TRACE_ELEM(&(listelm)->field); \ 974 } while (0) 975 976 #define TAILQ_INSERT_HEAD(head, elm, field) do { \ 977 QMD_TAILQ_CHECK_HEAD(head, field); \ 978 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 979 TAILQ_FIRST((head))->field.tqe_prev = \ 980 &TAILQ_NEXT((elm), field); \ 981 else \ 982 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 983 TAILQ_FIRST((head)) = (elm); \ 984 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 985 QMD_TRACE_HEAD(head); \ 986 QMD_TRACE_ELEM(&(elm)->field); \ 987 } while (0) 988 989 #define TAILQ_INSERT_TAIL(head, elm, field) do { \ 990 QMD_TAILQ_CHECK_TAIL(head, field); \ 991 TAILQ_NEXT((elm), field) = NULL; \ 992 (elm)->field.tqe_prev = (head)->tqh_last; \ 993 *(head)->tqh_last = (elm); \ 994 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 995 QMD_TRACE_HEAD(head); \ 996 QMD_TRACE_ELEM(&(elm)->field); \ 997 } while (0) 998 999 #define TAILQ_LAST(head, headname) \ 1000 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 1001 1002 /* 1003 * The FAST function is fast in that it causes no data access other 1004 * then the access to the head. The standard LAST function above 1005 * will cause a data access of both the element you want and 1006 * the previous element. FAST is very useful for instances when 1007 * you may want to prefetch the last data element. 1008 */ 1009 #define TAILQ_LAST_FAST(head, type, field) \ 1010 (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, QUEUE_TYPEOF(type), field.tqe_next)) 1011 1012 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 1013 1014 #define TAILQ_PREV(elm, headname, field) \ 1015 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 1016 1017 #define TAILQ_PREV_FAST(elm, head, type, field) \ 1018 ((elm)->field.tqe_prev == &(head)->tqh_first ? NULL : \ 1019 __containerof((elm)->field.tqe_prev, QUEUE_TYPEOF(type), field.tqe_next)) 1020 1021 #define TAILQ_REMOVE_HEAD(head, field) \ 1022 TAILQ_REMOVE(head, TAILQ_FIRST(head), field) 1023 1024 #define TAILQ_REMOVE(head, elm, field) do { \ 1025 QMD_SAVELINK(_Oldnext, (elm)->field.tqe_next); \ 1026 QMD_SAVELINK(_Oldprev, (elm)->field.tqe_prev); \ 1027 QMD_TAILQ_CHECK_NEXT(elm, field); \ 1028 QMD_TAILQ_CHECK_PREV(elm, field); \ 1029 if ((TAILQ_NEXT((elm), field)) != NULL) \ 1030 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 1031 (elm)->field.tqe_prev; \ 1032 else { \ 1033 (head)->tqh_last = (elm)->field.tqe_prev; \ 1034 QMD_TRACE_HEAD(head); \ 1035 } \ 1036 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 1037 TRASHIT(*_Oldnext); \ 1038 TRASHIT(*_Oldprev); \ 1039 QMD_TRACE_ELEM(&(elm)->field); \ 1040 } while (0) 1041 1042 #define TAILQ_REPLACE(head, elm, elm2, field) do { \ 1043 QMD_SAVELINK(_Oldnext, (elm)->field.tqe_next); \ 1044 QMD_SAVELINK(_Oldprev, (elm)->field.tqe_prev); \ 1045 QMD_TAILQ_CHECK_NEXT(elm, field); \ 1046 QMD_TAILQ_CHECK_PREV(elm, field); \ 1047 TAILQ_NEXT((elm2), field) = TAILQ_NEXT((elm), field); \ 1048 if (TAILQ_NEXT((elm2), field) != TAILQ_END(head)) \ 1049 TAILQ_NEXT((elm2), field)->field.tqe_prev = \ 1050 &(elm2)->field.tqe_next; \ 1051 else \ 1052 (head)->tqh_last = &(elm2)->field.tqe_next; \ 1053 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ 1054 *(elm2)->field.tqe_prev = (elm2); \ 1055 TRASHIT(*_Oldnext); \ 1056 TRASHIT(*_Oldprev); \ 1057 QMD_TRACE_ELEM(&(elm)->field); \ 1058 } while (0) 1059 1060 #define TAILQ_SPLIT_AFTER(head, elm, rest, field) do { \ 1061 TAILQ_ASSERT_NONEMPTY((head)); \ 1062 QMD_TAILQ_CHECK_TAIL((head), field); \ 1063 if (TAILQ_NEXT((elm), field) == NULL) \ 1064 /* 'elm' is the last element in 'head'. */ \ 1065 TAILQ_INIT((rest)); \ 1066 else { \ 1067 TAILQ_FIRST((rest)) = TAILQ_NEXT((elm), field); \ 1068 (rest)->tqh_last = (head)->tqh_last; \ 1069 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 1070 &TAILQ_FIRST((rest)); \ 1071 \ 1072 TAILQ_NEXT((elm), field) = NULL; \ 1073 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 1074 } \ 1075 } while (0) 1076 1077 #define TAILQ_SWAP(head1, head2, type, field) do { \ 1078 QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first; \ 1079 QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \ 1080 (head1)->tqh_first = (head2)->tqh_first; \ 1081 (head1)->tqh_last = (head2)->tqh_last; \ 1082 (head2)->tqh_first = swap_first; \ 1083 (head2)->tqh_last = swap_last; \ 1084 if ((swap_first = (head1)->tqh_first) != NULL) \ 1085 swap_first->field.tqe_prev = &(head1)->tqh_first; \ 1086 else \ 1087 (head1)->tqh_last = &(head1)->tqh_first; \ 1088 if ((swap_first = (head2)->tqh_first) != NULL) \ 1089 swap_first->field.tqe_prev = &(head2)->tqh_first; \ 1090 else \ 1091 (head2)->tqh_last = &(head2)->tqh_first; \ 1092 } while (0) 1093 1094 #define TAILQ_END(head) NULL 1095 1096 #endif /* !_SYS_QUEUE_H_ */ 1097