1/* 2 * Copyright (c) 2014 Chelsio, Inc. All rights reserved. 3 * 4 * This software is available to you under a choice of one of two 5 * licenses. You may choose to be licensed under the terms of the GNU 6 * General Public License (GPL) Version 2, available from the file 7 * COPYING in the main directory of this source tree, or the 8 * OpenIB.org BSD license below: 9 * 10 * Redistribution and use in source and binary forms, with or 11 * without modification, are permitted provided that the following 12 * conditions are met: 13 * 14 * - Redistributions of source code must retain the above 15 * copyright notice, this list of conditions and the following 16 * disclaimer. 17 * 18 * - Redistributions in binary form must reproduce the above 19 * copyright notice, this list of conditions and the following 20 * disclaimer in the documentation and/or other materials 21 * provided with the distribution. 22 * 23 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 24 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 25 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 26 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 27 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 28 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 29 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 30 * SOFTWARE. 31 */ 32 33/*- 34 * Copyright (c) 1991, 1993 35 * The Regents of the University of California. All rights reserved. 36 * 37 * Redistribution and use in source and binary forms, with or without 38 * modification, are permitted provided that the following conditions 39 * are met: 40 * 1. Redistributions of source code must retain the above copyright 41 * notice, this list of conditions and the following disclaimer. 42 * 2. Redistributions in binary form must reproduce the above copyright 43 * notice, this list of conditions and the following disclaimer in the 44 * documentation and/or other materials provided with the distribution. 45 * 4. Neither the name of the University nor the names of its contributors 46 * may be used to endorse or promote products derived from this software 47 * without specific prior written permission. 48 * 49 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 50 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 51 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 52 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 53 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 54 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 55 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 56 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 57 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 58 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 59 * SUCH DAMAGE. 60 * 61 * @(#)queue.h 8.5 (Berkeley) 8/20/94 62 * $FreeBSD$ 63 */ 64 65#ifndef _SYS_QUEUE_H_ 66#define _SYS_QUEUE_H_ 67 68#include <sys/cdefs.h> 69 70/* 71 * This file defines four types of data structures: singly-linked lists, 72 * singly-linked tail queues, lists and tail queues. 73 * 74 * A singly-linked list is headed by a single forward pointer. The elements 75 * are singly linked for minimum space and pointer manipulation overhead at 76 * the expense of O(n) removal for arbitrary elements. New elements can be 77 * added to the list after an existing element or at the head of the list. 78 * Elements being removed from the head of the list should use the explicit 79 * macro for this purpose for optimum efficiency. A singly-linked list may 80 * only be traversed in the forward direction. Singly-linked lists are ideal 81 * for applications with large datasets and few or no removals or for 82 * implementing a LIFO queue. 83 * 84 * A singly-linked tail queue is headed by a pair of pointers, one to the 85 * head of the list and the other to the tail of the list. The elements are 86 * singly linked for minimum space and pointer manipulation overhead at the 87 * expense of O(n) removal for arbitrary elements. New elements can be added 88 * to the list after an existing element, at the head of the list, or at the 89 * end of the list. Elements being removed from the head of the tail queue 90 * should use the explicit macro for this purpose for optimum efficiency. 91 * A singly-linked tail queue may only be traversed in the forward direction. 92 * Singly-linked tail queues are ideal for applications with large datasets 93 * and few or no removals or for implementing a FIFO queue. 94 * 95 * A list is headed by a single forward pointer (or an array of forward 96 * pointers for a hash table header). The elements are doubly linked 97 * so that an arbitrary element can be removed without a need to 98 * traverse the list. New elements can be added to the list before 99 * or after an existing element or at the head of the list. A list 100 * may only be traversed in the forward direction. 101 * 102 * A tail queue is headed by a pair of pointers, one to the head of the 103 * list and the other to the tail of the list. The elements are doubly 104 * linked so that an arbitrary element can be removed without a need to 105 * traverse the list. New elements can be added to the list before or 106 * after an existing element, at the head of the list, or at the end of 107 * the list. A tail queue may be traversed in either direction. 108 * 109 * For details on the use of these macros, see the queue(3) manual page. 110 * 111 * 112 * SLIST LIST STAILQ TAILQ 113 * _HEAD + + + + 114 * _HEAD_INITIALIZER + + + + 115 * _ENTRY + + + + 116 * _INIT + + + + 117 * _EMPTY + + + + 118 * _FIRST + + + + 119 * _NEXT + + + + 120 * _PREV - - - + 121 * _LAST - - + + 122 * _FOREACH + + + + 123 * _FOREACH_SAFE + + + + 124 * _FOREACH_REVERSE - - - + 125 * _FOREACH_REVERSE_SAFE - - - + 126 * _INSERT_HEAD + + + + 127 * _INSERT_BEFORE - + - + 128 * _INSERT_AFTER + + + + 129 * _INSERT_TAIL - - + + 130 * _CONCAT - - + + 131 * _REMOVE_HEAD + - + - 132 * _REMOVE + + + + 133 * 134 */ 135#ifdef QUEUE_MACRO_DEBUG 136/* Store the last 2 places the queue element or head was altered */ 137struct qm_trace { 138 char * lastfile; 139 int lastline; 140 char * prevfile; 141 int prevline; 142}; 143 144#define TRACEBUF struct qm_trace trace; 145#define TRASHIT(x) do {(x) = (void *)-1;} while (0) 146 147#define QMD_TRACE_HEAD(head) do { \ 148 (head)->trace.prevline = (head)->trace.lastline; \ 149 (head)->trace.prevfile = (head)->trace.lastfile; \ 150 (head)->trace.lastline = __LINE__; \ 151 (head)->trace.lastfile = __FILE__; \ 152} while (0) 153 154#define QMD_TRACE_ELEM(elem) do { \ 155 (elem)->trace.prevline = (elem)->trace.lastline; \ 156 (elem)->trace.prevfile = (elem)->trace.lastfile; \ 157 (elem)->trace.lastline = __LINE__; \ 158 (elem)->trace.lastfile = __FILE__; \ 159} while (0) 160 161#else 162#define QMD_TRACE_ELEM(elem) 163#define QMD_TRACE_HEAD(head) 164#define TRACEBUF 165#define TRASHIT(x) 166#endif /* QUEUE_MACRO_DEBUG */ 167 168/* 169 * Singly-linked List declarations. 170 */ 171#define SLIST_HEAD(name, type) \ 172struct name { \ 173 struct type *slh_first; /* first element */ \ 174} 175 176#define SLIST_HEAD_INITIALIZER(head) \ 177 { NULL } 178 179#define SLIST_ENTRY(type) \ 180struct { \ 181 struct type *sle_next; /* next element */ \ 182} 183 184/* 185 * Singly-linked List functions. 186 */ 187#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 188 189#define SLIST_FIRST(head) ((head)->slh_first) 190 191#define SLIST_FOREACH(var, head, field) \ 192 for ((var) = SLIST_FIRST((head)); \ 193 (var); \ 194 (var) = SLIST_NEXT((var), field)) 195 196#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 197 for ((var) = SLIST_FIRST((head)); \ 198 (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 199 (var) = (tvar)) 200 201#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 202 for ((varp) = &SLIST_FIRST((head)); \ 203 ((var) = *(varp)) != NULL; \ 204 (varp) = &SLIST_NEXT((var), field)) 205 206#define SLIST_INIT(head) do { \ 207 SLIST_FIRST((head)) = NULL; \ 208} while (0) 209 210#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 211 SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 212 SLIST_NEXT((slistelm), field) = (elm); \ 213} while (0) 214 215#define SLIST_INSERT_HEAD(head, elm, field) do { \ 216 SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 217 SLIST_FIRST((head)) = (elm); \ 218} while (0) 219 220#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 221 222#define SLIST_REMOVE(head, elm, type, field) do { \ 223 if (SLIST_FIRST((head)) == (elm)) { \ 224 SLIST_REMOVE_HEAD((head), field); \ 225 } \ 226 else { \ 227 struct type *curelm = SLIST_FIRST((head)); \ 228 while (SLIST_NEXT(curelm, field) != (elm)) \ 229 curelm = SLIST_NEXT(curelm, field); \ 230 SLIST_NEXT(curelm, field) = \ 231 SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ 232 } \ 233 TRASHIT((elm)->field.sle_next); \ 234} while (0) 235 236#define SLIST_REMOVE_HEAD(head, field) do { \ 237 SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 238} while (0) 239 240/* 241 * Singly-linked Tail queue declarations. 242 */ 243#define STAILQ_HEAD(name, type) \ 244struct name { \ 245 struct type *stqh_first;/* first element */ \ 246 struct type **stqh_last;/* addr of last next element */ \ 247} 248 249#define STAILQ_HEAD_INITIALIZER(head) \ 250 { NULL, &(head).stqh_first } 251 252#define STAILQ_ENTRY(type) \ 253struct { \ 254 struct type *stqe_next; /* next element */ \ 255} 256 257/* 258 * Singly-linked Tail queue functions. 259 */ 260#define STAILQ_CONCAT(head1, head2) do { \ 261 if (!STAILQ_EMPTY((head2))) { \ 262 *(head1)->stqh_last = (head2)->stqh_first; \ 263 (head1)->stqh_last = (head2)->stqh_last; \ 264 STAILQ_INIT((head2)); \ 265 } \ 266} while (0) 267 268#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 269 270#define STAILQ_FIRST(head) ((head)->stqh_first) 271 272#define STAILQ_FOREACH(var, head, field) \ 273 for((var) = STAILQ_FIRST((head)); \ 274 (var); \ 275 (var) = STAILQ_NEXT((var), field)) 276 277 278#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 279 for ((var) = STAILQ_FIRST((head)); \ 280 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 281 (var) = (tvar)) 282 283#define STAILQ_INIT(head) do { \ 284 STAILQ_FIRST((head)) = NULL; \ 285 (head)->stqh_last = &STAILQ_FIRST((head)); \ 286} while (0) 287 288#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 289 if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 290 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 291 STAILQ_NEXT((tqelm), field) = (elm); \ 292} while (0) 293 294#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 295 if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 296 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 297 STAILQ_FIRST((head)) = (elm); \ 298} while (0) 299 300#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 301 STAILQ_NEXT((elm), field) = NULL; \ 302 *(head)->stqh_last = (elm); \ 303 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 304} while (0) 305 306#define STAILQ_LAST(head, type, field) \ 307 (STAILQ_EMPTY((head)) ? \ 308 NULL : \ 309 ((struct type *)(void *) \ 310 ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) 311 312#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 313 314#define STAILQ_REMOVE(head, elm, type, field) do { \ 315 if (STAILQ_FIRST((head)) == (elm)) { \ 316 STAILQ_REMOVE_HEAD((head), field); \ 317 } \ 318 else { \ 319 struct type *curelm = STAILQ_FIRST((head)); \ 320 while (STAILQ_NEXT(curelm, field) != (elm)) \ 321 curelm = STAILQ_NEXT(curelm, field); \ 322 if ((STAILQ_NEXT(curelm, field) = \ 323 STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ 324 (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ 325 } \ 326 TRASHIT((elm)->field.stqe_next); \ 327} while (0) 328 329#define STAILQ_REMOVE_HEAD(head, field) do { \ 330 if ((STAILQ_FIRST((head)) = \ 331 STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 332 (head)->stqh_last = &STAILQ_FIRST((head)); \ 333} while (0) 334 335/* 336 * List declarations. 337 */ 338#define LIST_HEAD(name, type) \ 339struct name { \ 340 struct type *lh_first; /* first element */ \ 341} 342 343#define LIST_HEAD_INITIALIZER(head) \ 344 { NULL } 345 346#define LIST_ENTRY(type) \ 347struct { \ 348 struct type *le_next; /* next element */ \ 349 struct type **le_prev; /* address of previous next element */ \ 350} 351 352/* 353 * List functions. 354 */ 355 356#if (defined(_KERNEL) && defined(INVARIANTS)) 357#define QMD_LIST_CHECK_HEAD(head, field) do { \ 358 if (LIST_FIRST((head)) != NULL && \ 359 LIST_FIRST((head))->field.le_prev != \ 360 &LIST_FIRST((head))) \ 361 panic("Bad list head %p first->prev != head", (head)); \ 362} while (0) 363 364#define QMD_LIST_CHECK_NEXT(elm, field) do { \ 365 if (LIST_NEXT((elm), field) != NULL && \ 366 LIST_NEXT((elm), field)->field.le_prev != \ 367 &((elm)->field.le_next)) \ 368 panic("Bad link elm %p next->prev != elm", (elm)); \ 369} while (0) 370 371#define QMD_LIST_CHECK_PREV(elm, field) do { \ 372 if (*(elm)->field.le_prev != (elm)) \ 373 panic("Bad link elm %p prev->next != elm", (elm)); \ 374} while (0) 375#else 376#define QMD_LIST_CHECK_HEAD(head, field) 377#define QMD_LIST_CHECK_NEXT(elm, field) 378#define QMD_LIST_CHECK_PREV(elm, field) 379#endif /* (_KERNEL && INVARIANTS) */ 380 381#define LIST_EMPTY(head) ((head)->lh_first == NULL) 382 383#define LIST_FIRST(head) ((head)->lh_first) 384 385#define LIST_FOREACH(var, head, field) \ 386 for ((var) = LIST_FIRST((head)); \ 387 (var); \ 388 (var) = LIST_NEXT((var), field)) 389 390#define LIST_FOREACH_SAFE(var, head, field, tvar) \ 391 for ((var) = LIST_FIRST((head)); \ 392 (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 393 (var) = (tvar)) 394 395#define LIST_INIT(head) do { \ 396 LIST_FIRST((head)) = NULL; \ 397} while (0) 398 399#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 400 QMD_LIST_CHECK_NEXT(listelm, field); \ 401 if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 402 LIST_NEXT((listelm), field)->field.le_prev = \ 403 &LIST_NEXT((elm), field); \ 404 LIST_NEXT((listelm), field) = (elm); \ 405 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 406} while (0) 407 408#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 409 QMD_LIST_CHECK_PREV(listelm, field); \ 410 (elm)->field.le_prev = (listelm)->field.le_prev; \ 411 LIST_NEXT((elm), field) = (listelm); \ 412 *(listelm)->field.le_prev = (elm); \ 413 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 414} while (0) 415 416#define LIST_INSERT_HEAD(head, elm, field) do { \ 417 QMD_LIST_CHECK_HEAD((head), field); \ 418 if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 419 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 420 LIST_FIRST((head)) = (elm); \ 421 (elm)->field.le_prev = &LIST_FIRST((head)); \ 422} while (0) 423 424#define LIST_NEXT(elm, field) ((elm)->field.le_next) 425 426#define LIST_REMOVE(elm, field) do { \ 427 QMD_LIST_CHECK_NEXT(elm, field); \ 428 QMD_LIST_CHECK_PREV(elm, field); \ 429 if (LIST_NEXT((elm), field) != NULL) \ 430 LIST_NEXT((elm), field)->field.le_prev = \ 431 (elm)->field.le_prev; \ 432 *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 433 TRASHIT((elm)->field.le_next); \ 434 TRASHIT((elm)->field.le_prev); \ 435} while (0) 436 437/* 438 * Tail queue declarations. 439 */ 440#define TAILQ_HEAD(name, type) \ 441struct name { \ 442 struct type *tqh_first; /* first element */ \ 443 struct type **tqh_last; /* addr of last next element */ \ 444 TRACEBUF \ 445} 446 447#define TAILQ_HEAD_INITIALIZER(head) \ 448 { NULL, &(head).tqh_first } 449 450#define TAILQ_ENTRY(type) \ 451struct { \ 452 struct type *tqe_next; /* next element */ \ 453 struct type **tqe_prev; /* address of previous next element */ \ 454 TRACEBUF \ 455} 456 457/* 458 * Tail queue functions. 459 */ 460#if (defined(_KERNEL) && defined(INVARIANTS)) 461#define QMD_TAILQ_CHECK_HEAD(head, field) do { \ 462 if (!TAILQ_EMPTY(head) && \ 463 TAILQ_FIRST((head))->field.tqe_prev != \ 464 &TAILQ_FIRST((head))) \ 465 panic("Bad tailq head %p first->prev != head", (head)); \ 466} while (0) 467 468#define QMD_TAILQ_CHECK_TAIL(head, field) do { \ 469 if (*(head)->tqh_last != NULL) \ 470 panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ 471} while (0) 472 473#define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ 474 if (TAILQ_NEXT((elm), field) != NULL && \ 475 TAILQ_NEXT((elm), field)->field.tqe_prev != \ 476 &((elm)->field.tqe_next)) \ 477 panic("Bad link elm %p next->prev != elm", (elm)); \ 478} while (0) 479 480#define QMD_TAILQ_CHECK_PREV(elm, field) do { \ 481 if (*(elm)->field.tqe_prev != (elm)) \ 482 panic("Bad link elm %p prev->next != elm", (elm)); \ 483} while (0) 484#else 485#define QMD_TAILQ_CHECK_HEAD(head, field) 486#define QMD_TAILQ_CHECK_TAIL(head, headname) 487#define QMD_TAILQ_CHECK_NEXT(elm, field) 488#define QMD_TAILQ_CHECK_PREV(elm, field) 489#endif /* (_KERNEL && INVARIANTS) */ 490 491#define TAILQ_CONCAT(head1, head2, field) do { \ 492 if (!TAILQ_EMPTY(head2)) { \ 493 *(head1)->tqh_last = (head2)->tqh_first; \ 494 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 495 (head1)->tqh_last = (head2)->tqh_last; \ 496 TAILQ_INIT((head2)); \ 497 QMD_TRACE_HEAD(head1); \ 498 QMD_TRACE_HEAD(head2); \ 499 } \ 500} while (0) 501 502#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 503 504#define TAILQ_FIRST(head) ((head)->tqh_first) 505 506#define TAILQ_FOREACH(var, head, field) \ 507 for ((var) = TAILQ_FIRST((head)); \ 508 (var); \ 509 (var) = TAILQ_NEXT((var), field)) 510 511#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 512 for ((var) = TAILQ_FIRST((head)); \ 513 (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 514 (var) = (tvar)) 515 516#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 517 for ((var) = TAILQ_LAST((head), headname); \ 518 (var); \ 519 (var) = TAILQ_PREV((var), headname, field)) 520 521#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 522 for ((var) = TAILQ_LAST((head), headname); \ 523 (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 524 (var) = (tvar)) 525 526#define TAILQ_INIT(head) do { \ 527 TAILQ_FIRST((head)) = NULL; \ 528 (head)->tqh_last = &TAILQ_FIRST((head)); \ 529 QMD_TRACE_HEAD(head); \ 530} while (0) 531 532#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 533 QMD_TAILQ_CHECK_NEXT(listelm, field); \ 534 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 535 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 536 &TAILQ_NEXT((elm), field); \ 537 else { \ 538 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 539 QMD_TRACE_HEAD(head); \ 540 } \ 541 TAILQ_NEXT((listelm), field) = (elm); \ 542 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 543 QMD_TRACE_ELEM(&(elm)->field); \ 544 QMD_TRACE_ELEM(&listelm->field); \ 545} while (0) 546 547#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 548 QMD_TAILQ_CHECK_PREV(listelm, field); \ 549 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 550 TAILQ_NEXT((elm), field) = (listelm); \ 551 *(listelm)->field.tqe_prev = (elm); \ 552 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 553 QMD_TRACE_ELEM(&(elm)->field); \ 554 QMD_TRACE_ELEM(&listelm->field); \ 555} while (0) 556 557#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 558 QMD_TAILQ_CHECK_HEAD(head, field); \ 559 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 560 TAILQ_FIRST((head))->field.tqe_prev = \ 561 &TAILQ_NEXT((elm), field); \ 562 else \ 563 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 564 TAILQ_FIRST((head)) = (elm); \ 565 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 566 QMD_TRACE_HEAD(head); \ 567 QMD_TRACE_ELEM(&(elm)->field); \ 568} while (0) 569 570#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 571 QMD_TAILQ_CHECK_TAIL(head, field); \ 572 TAILQ_NEXT((elm), field) = NULL; \ 573 (elm)->field.tqe_prev = (head)->tqh_last; \ 574 *(head)->tqh_last = (elm); \ 575 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 576 QMD_TRACE_HEAD(head); \ 577 QMD_TRACE_ELEM(&(elm)->field); \ 578} while (0) 579 580#define TAILQ_LAST(head, headname) \ 581 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 582 583#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 584 585#define TAILQ_PREV(elm, headname, field) \ 586 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 587 588#define TAILQ_REMOVE(head, elm, field) do { \ 589 QMD_TAILQ_CHECK_NEXT(elm, field); \ 590 QMD_TAILQ_CHECK_PREV(elm, field); \ 591 if ((TAILQ_NEXT((elm), field)) != NULL) \ 592 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 593 (elm)->field.tqe_prev; \ 594 else { \ 595 (head)->tqh_last = (elm)->field.tqe_prev; \ 596 QMD_TRACE_HEAD(head); \ 597 } \ 598 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 599 TRASHIT((elm)->field.tqe_next); \ 600 TRASHIT((elm)->field.tqe_prev); \ 601 QMD_TRACE_ELEM(&(elm)->field); \ 602} while (0) 603 604 605#ifdef _KERNEL 606 607/* 608 * XXX insque() and remque() are an old way of handling certain queues. 609 * They bogusly assumes that all queue heads look alike. 610 */ 611 612struct quehead { 613 struct quehead *qh_link; 614 struct quehead *qh_rlink; 615}; 616 617#ifdef __CC_SUPPORTS___INLINE 618 619static __inline void 620insque(void *a, void *b) 621{ 622 struct quehead *element = (struct quehead *)a, 623 *head = (struct quehead *)b; 624 625 element->qh_link = head->qh_link; 626 element->qh_rlink = head; 627 head->qh_link = element; 628 element->qh_link->qh_rlink = element; 629} 630 631static __inline void 632remque(void *a) 633{ 634 struct quehead *element = (struct quehead *)a; 635 636 element->qh_link->qh_rlink = element->qh_rlink; 637 element->qh_rlink->qh_link = element->qh_link; 638 element->qh_rlink = 0; 639} 640 641#else /* !__CC_SUPPORTS___INLINE */ 642 643void insque(void *a, void *b); 644void remque(void *a); 645 646#endif /* __CC_SUPPORTS___INLINE */ 647 648#endif /* _KERNEL */ 649 650#endif /* !_SYS_QUEUE_H_ */ 651