1273806Snp/* 2273806Snp * Copyright (c) 2014 Chelsio, Inc. All rights reserved. 3273806Snp * 4273806Snp * This software is available to you under a choice of one of two 5273806Snp * licenses. You may choose to be licensed under the terms of the GNU 6273806Snp * General Public License (GPL) Version 2, available from the file 7273806Snp * COPYING in the main directory of this source tree, or the 8273806Snp * OpenIB.org BSD license below: 9273806Snp * 10273806Snp * Redistribution and use in source and binary forms, with or 11273806Snp * without modification, are permitted provided that the following 12273806Snp * conditions are met: 13273806Snp * 14273806Snp * - Redistributions of source code must retain the above 15273806Snp * copyright notice, this list of conditions and the following 16273806Snp * disclaimer. 17273806Snp * 18273806Snp * - Redistributions in binary form must reproduce the above 19273806Snp * copyright notice, this list of conditions and the following 20273806Snp * disclaimer in the documentation and/or other materials 21273806Snp * provided with the distribution. 22273806Snp * 23273806Snp * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 24273806Snp * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 25273806Snp * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 26273806Snp * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 27273806Snp * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 28273806Snp * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 29273806Snp * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 30273806Snp * SOFTWARE. 31273806Snp */ 32273806Snp 33273806Snp/*- 34273806Snp * Copyright (c) 1991, 1993 35273806Snp * The Regents of the University of California. All rights reserved. 36273806Snp * 37273806Snp * Redistribution and use in source and binary forms, with or without 38273806Snp * modification, are permitted provided that the following conditions 39273806Snp * are met: 40273806Snp * 1. Redistributions of source code must retain the above copyright 41273806Snp * notice, this list of conditions and the following disclaimer. 42273806Snp * 2. Redistributions in binary form must reproduce the above copyright 43273806Snp * notice, this list of conditions and the following disclaimer in the 44273806Snp * documentation and/or other materials provided with the distribution. 45273806Snp * 4. Neither the name of the University nor the names of its contributors 46273806Snp * may be used to endorse or promote products derived from this software 47273806Snp * without specific prior written permission. 48273806Snp * 49273806Snp * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 50273806Snp * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 51273806Snp * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 52273806Snp * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 53273806Snp * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 54273806Snp * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 55273806Snp * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 56273806Snp * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 57273806Snp * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 58273806Snp * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 59273806Snp * SUCH DAMAGE. 60273806Snp * 61273806Snp * @(#)queue.h 8.5 (Berkeley) 8/20/94 62273806Snp * $FreeBSD$ 63273806Snp */ 64273806Snp 65273806Snp#ifndef _SYS_QUEUE_H_ 66273806Snp#define _SYS_QUEUE_H_ 67273806Snp 68273806Snp#include <sys/cdefs.h> 69273806Snp 70273806Snp/* 71273806Snp * This file defines four types of data structures: singly-linked lists, 72273806Snp * singly-linked tail queues, lists and tail queues. 73273806Snp * 74273806Snp * A singly-linked list is headed by a single forward pointer. The elements 75273806Snp * are singly linked for minimum space and pointer manipulation overhead at 76273806Snp * the expense of O(n) removal for arbitrary elements. New elements can be 77273806Snp * added to the list after an existing element or at the head of the list. 78273806Snp * Elements being removed from the head of the list should use the explicit 79273806Snp * macro for this purpose for optimum efficiency. A singly-linked list may 80273806Snp * only be traversed in the forward direction. Singly-linked lists are ideal 81273806Snp * for applications with large datasets and few or no removals or for 82273806Snp * implementing a LIFO queue. 83273806Snp * 84273806Snp * A singly-linked tail queue is headed by a pair of pointers, one to the 85273806Snp * head of the list and the other to the tail of the list. The elements are 86273806Snp * singly linked for minimum space and pointer manipulation overhead at the 87273806Snp * expense of O(n) removal for arbitrary elements. New elements can be added 88273806Snp * to the list after an existing element, at the head of the list, or at the 89273806Snp * end of the list. Elements being removed from the head of the tail queue 90273806Snp * should use the explicit macro for this purpose for optimum efficiency. 91273806Snp * A singly-linked tail queue may only be traversed in the forward direction. 92273806Snp * Singly-linked tail queues are ideal for applications with large datasets 93273806Snp * and few or no removals or for implementing a FIFO queue. 94273806Snp * 95273806Snp * A list is headed by a single forward pointer (or an array of forward 96273806Snp * pointers for a hash table header). The elements are doubly linked 97273806Snp * so that an arbitrary element can be removed without a need to 98273806Snp * traverse the list. New elements can be added to the list before 99273806Snp * or after an existing element or at the head of the list. A list 100273806Snp * may only be traversed in the forward direction. 101273806Snp * 102273806Snp * A tail queue is headed by a pair of pointers, one to the head of the 103273806Snp * list and the other to the tail of the list. The elements are doubly 104273806Snp * linked so that an arbitrary element can be removed without a need to 105273806Snp * traverse the list. New elements can be added to the list before or 106273806Snp * after an existing element, at the head of the list, or at the end of 107273806Snp * the list. A tail queue may be traversed in either direction. 108273806Snp * 109273806Snp * For details on the use of these macros, see the queue(3) manual page. 110273806Snp * 111273806Snp * 112273806Snp * SLIST LIST STAILQ TAILQ 113273806Snp * _HEAD + + + + 114273806Snp * _HEAD_INITIALIZER + + + + 115273806Snp * _ENTRY + + + + 116273806Snp * _INIT + + + + 117273806Snp * _EMPTY + + + + 118273806Snp * _FIRST + + + + 119273806Snp * _NEXT + + + + 120273806Snp * _PREV - - - + 121273806Snp * _LAST - - + + 122273806Snp * _FOREACH + + + + 123273806Snp * _FOREACH_SAFE + + + + 124273806Snp * _FOREACH_REVERSE - - - + 125273806Snp * _FOREACH_REVERSE_SAFE - - - + 126273806Snp * _INSERT_HEAD + + + + 127273806Snp * _INSERT_BEFORE - + - + 128273806Snp * _INSERT_AFTER + + + + 129273806Snp * _INSERT_TAIL - - + + 130273806Snp * _CONCAT - - + + 131273806Snp * _REMOVE_HEAD + - + - 132273806Snp * _REMOVE + + + + 133273806Snp * 134273806Snp */ 135273806Snp#ifdef QUEUE_MACRO_DEBUG 136273806Snp/* Store the last 2 places the queue element or head was altered */ 137273806Snpstruct qm_trace { 138273806Snp char * lastfile; 139273806Snp int lastline; 140273806Snp char * prevfile; 141273806Snp int prevline; 142273806Snp}; 143273806Snp 144273806Snp#define TRACEBUF struct qm_trace trace; 145273806Snp#define TRASHIT(x) do {(x) = (void *)-1;} while (0) 146273806Snp 147273806Snp#define QMD_TRACE_HEAD(head) do { \ 148273806Snp (head)->trace.prevline = (head)->trace.lastline; \ 149273806Snp (head)->trace.prevfile = (head)->trace.lastfile; \ 150273806Snp (head)->trace.lastline = __LINE__; \ 151273806Snp (head)->trace.lastfile = __FILE__; \ 152273806Snp} while (0) 153273806Snp 154273806Snp#define QMD_TRACE_ELEM(elem) do { \ 155273806Snp (elem)->trace.prevline = (elem)->trace.lastline; \ 156273806Snp (elem)->trace.prevfile = (elem)->trace.lastfile; \ 157273806Snp (elem)->trace.lastline = __LINE__; \ 158273806Snp (elem)->trace.lastfile = __FILE__; \ 159273806Snp} while (0) 160273806Snp 161273806Snp#else 162273806Snp#define QMD_TRACE_ELEM(elem) 163273806Snp#define QMD_TRACE_HEAD(head) 164273806Snp#define TRACEBUF 165273806Snp#define TRASHIT(x) 166273806Snp#endif /* QUEUE_MACRO_DEBUG */ 167273806Snp 168273806Snp/* 169273806Snp * Singly-linked List declarations. 170273806Snp */ 171273806Snp#define SLIST_HEAD(name, type) \ 172273806Snpstruct name { \ 173273806Snp struct type *slh_first; /* first element */ \ 174273806Snp} 175273806Snp 176273806Snp#define SLIST_HEAD_INITIALIZER(head) \ 177273806Snp { NULL } 178273806Snp 179273806Snp#define SLIST_ENTRY(type) \ 180273806Snpstruct { \ 181273806Snp struct type *sle_next; /* next element */ \ 182273806Snp} 183273806Snp 184273806Snp/* 185273806Snp * Singly-linked List functions. 186273806Snp */ 187273806Snp#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 188273806Snp 189273806Snp#define SLIST_FIRST(head) ((head)->slh_first) 190273806Snp 191273806Snp#define SLIST_FOREACH(var, head, field) \ 192273806Snp for ((var) = SLIST_FIRST((head)); \ 193273806Snp (var); \ 194273806Snp (var) = SLIST_NEXT((var), field)) 195273806Snp 196273806Snp#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 197273806Snp for ((var) = SLIST_FIRST((head)); \ 198273806Snp (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 199273806Snp (var) = (tvar)) 200273806Snp 201273806Snp#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 202273806Snp for ((varp) = &SLIST_FIRST((head)); \ 203273806Snp ((var) = *(varp)) != NULL; \ 204273806Snp (varp) = &SLIST_NEXT((var), field)) 205273806Snp 206273806Snp#define SLIST_INIT(head) do { \ 207273806Snp SLIST_FIRST((head)) = NULL; \ 208273806Snp} while (0) 209273806Snp 210273806Snp#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 211273806Snp SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 212273806Snp SLIST_NEXT((slistelm), field) = (elm); \ 213273806Snp} while (0) 214273806Snp 215273806Snp#define SLIST_INSERT_HEAD(head, elm, field) do { \ 216273806Snp SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 217273806Snp SLIST_FIRST((head)) = (elm); \ 218273806Snp} while (0) 219273806Snp 220273806Snp#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 221273806Snp 222273806Snp#define SLIST_REMOVE(head, elm, type, field) do { \ 223273806Snp if (SLIST_FIRST((head)) == (elm)) { \ 224273806Snp SLIST_REMOVE_HEAD((head), field); \ 225273806Snp } \ 226273806Snp else { \ 227273806Snp struct type *curelm = SLIST_FIRST((head)); \ 228273806Snp while (SLIST_NEXT(curelm, field) != (elm)) \ 229273806Snp curelm = SLIST_NEXT(curelm, field); \ 230273806Snp SLIST_NEXT(curelm, field) = \ 231273806Snp SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ 232273806Snp } \ 233273806Snp TRASHIT((elm)->field.sle_next); \ 234273806Snp} while (0) 235273806Snp 236273806Snp#define SLIST_REMOVE_HEAD(head, field) do { \ 237273806Snp SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 238273806Snp} while (0) 239273806Snp 240273806Snp/* 241273806Snp * Singly-linked Tail queue declarations. 242273806Snp */ 243273806Snp#define STAILQ_HEAD(name, type) \ 244273806Snpstruct name { \ 245273806Snp struct type *stqh_first;/* first element */ \ 246273806Snp struct type **stqh_last;/* addr of last next element */ \ 247273806Snp} 248273806Snp 249273806Snp#define STAILQ_HEAD_INITIALIZER(head) \ 250273806Snp { NULL, &(head).stqh_first } 251273806Snp 252273806Snp#define STAILQ_ENTRY(type) \ 253273806Snpstruct { \ 254273806Snp struct type *stqe_next; /* next element */ \ 255273806Snp} 256273806Snp 257273806Snp/* 258273806Snp * Singly-linked Tail queue functions. 259273806Snp */ 260273806Snp#define STAILQ_CONCAT(head1, head2) do { \ 261273806Snp if (!STAILQ_EMPTY((head2))) { \ 262273806Snp *(head1)->stqh_last = (head2)->stqh_first; \ 263273806Snp (head1)->stqh_last = (head2)->stqh_last; \ 264273806Snp STAILQ_INIT((head2)); \ 265273806Snp } \ 266273806Snp} while (0) 267273806Snp 268273806Snp#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 269273806Snp 270273806Snp#define STAILQ_FIRST(head) ((head)->stqh_first) 271273806Snp 272273806Snp#define STAILQ_FOREACH(var, head, field) \ 273273806Snp for((var) = STAILQ_FIRST((head)); \ 274273806Snp (var); \ 275273806Snp (var) = STAILQ_NEXT((var), field)) 276273806Snp 277273806Snp 278273806Snp#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 279273806Snp for ((var) = STAILQ_FIRST((head)); \ 280273806Snp (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 281273806Snp (var) = (tvar)) 282273806Snp 283273806Snp#define STAILQ_INIT(head) do { \ 284273806Snp STAILQ_FIRST((head)) = NULL; \ 285273806Snp (head)->stqh_last = &STAILQ_FIRST((head)); \ 286273806Snp} while (0) 287273806Snp 288273806Snp#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 289273806Snp if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 290273806Snp (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 291273806Snp STAILQ_NEXT((tqelm), field) = (elm); \ 292273806Snp} while (0) 293273806Snp 294273806Snp#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 295273806Snp if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 296273806Snp (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 297273806Snp STAILQ_FIRST((head)) = (elm); \ 298273806Snp} while (0) 299273806Snp 300273806Snp#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 301273806Snp STAILQ_NEXT((elm), field) = NULL; \ 302273806Snp *(head)->stqh_last = (elm); \ 303273806Snp (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 304273806Snp} while (0) 305273806Snp 306273806Snp#define STAILQ_LAST(head, type, field) \ 307273806Snp (STAILQ_EMPTY((head)) ? \ 308273806Snp NULL : \ 309273806Snp ((struct type *)(void *) \ 310273806Snp ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) 311273806Snp 312273806Snp#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 313273806Snp 314273806Snp#define STAILQ_REMOVE(head, elm, type, field) do { \ 315273806Snp if (STAILQ_FIRST((head)) == (elm)) { \ 316273806Snp STAILQ_REMOVE_HEAD((head), field); \ 317273806Snp } \ 318273806Snp else { \ 319273806Snp struct type *curelm = STAILQ_FIRST((head)); \ 320273806Snp while (STAILQ_NEXT(curelm, field) != (elm)) \ 321273806Snp curelm = STAILQ_NEXT(curelm, field); \ 322273806Snp if ((STAILQ_NEXT(curelm, field) = \ 323273806Snp STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ 324273806Snp (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ 325273806Snp } \ 326273806Snp TRASHIT((elm)->field.stqe_next); \ 327273806Snp} while (0) 328273806Snp 329273806Snp#define STAILQ_REMOVE_HEAD(head, field) do { \ 330273806Snp if ((STAILQ_FIRST((head)) = \ 331273806Snp STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 332273806Snp (head)->stqh_last = &STAILQ_FIRST((head)); \ 333273806Snp} while (0) 334273806Snp 335273806Snp/* 336273806Snp * List declarations. 337273806Snp */ 338273806Snp#define LIST_HEAD(name, type) \ 339273806Snpstruct name { \ 340273806Snp struct type *lh_first; /* first element */ \ 341273806Snp} 342273806Snp 343273806Snp#define LIST_HEAD_INITIALIZER(head) \ 344273806Snp { NULL } 345273806Snp 346273806Snp#define LIST_ENTRY(type) \ 347273806Snpstruct { \ 348273806Snp struct type *le_next; /* next element */ \ 349273806Snp struct type **le_prev; /* address of previous next element */ \ 350273806Snp} 351273806Snp 352273806Snp/* 353273806Snp * List functions. 354273806Snp */ 355273806Snp 356273806Snp#if (defined(_KERNEL) && defined(INVARIANTS)) 357273806Snp#define QMD_LIST_CHECK_HEAD(head, field) do { \ 358273806Snp if (LIST_FIRST((head)) != NULL && \ 359273806Snp LIST_FIRST((head))->field.le_prev != \ 360273806Snp &LIST_FIRST((head))) \ 361273806Snp panic("Bad list head %p first->prev != head", (head)); \ 362273806Snp} while (0) 363273806Snp 364273806Snp#define QMD_LIST_CHECK_NEXT(elm, field) do { \ 365273806Snp if (LIST_NEXT((elm), field) != NULL && \ 366273806Snp LIST_NEXT((elm), field)->field.le_prev != \ 367273806Snp &((elm)->field.le_next)) \ 368273806Snp panic("Bad link elm %p next->prev != elm", (elm)); \ 369273806Snp} while (0) 370273806Snp 371273806Snp#define QMD_LIST_CHECK_PREV(elm, field) do { \ 372273806Snp if (*(elm)->field.le_prev != (elm)) \ 373273806Snp panic("Bad link elm %p prev->next != elm", (elm)); \ 374273806Snp} while (0) 375273806Snp#else 376273806Snp#define QMD_LIST_CHECK_HEAD(head, field) 377273806Snp#define QMD_LIST_CHECK_NEXT(elm, field) 378273806Snp#define QMD_LIST_CHECK_PREV(elm, field) 379273806Snp#endif /* (_KERNEL && INVARIANTS) */ 380273806Snp 381273806Snp#define LIST_EMPTY(head) ((head)->lh_first == NULL) 382273806Snp 383273806Snp#define LIST_FIRST(head) ((head)->lh_first) 384273806Snp 385273806Snp#define LIST_FOREACH(var, head, field) \ 386273806Snp for ((var) = LIST_FIRST((head)); \ 387273806Snp (var); \ 388273806Snp (var) = LIST_NEXT((var), field)) 389273806Snp 390273806Snp#define LIST_FOREACH_SAFE(var, head, field, tvar) \ 391273806Snp for ((var) = LIST_FIRST((head)); \ 392273806Snp (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 393273806Snp (var) = (tvar)) 394273806Snp 395273806Snp#define LIST_INIT(head) do { \ 396273806Snp LIST_FIRST((head)) = NULL; \ 397273806Snp} while (0) 398273806Snp 399273806Snp#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 400273806Snp QMD_LIST_CHECK_NEXT(listelm, field); \ 401273806Snp if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 402273806Snp LIST_NEXT((listelm), field)->field.le_prev = \ 403273806Snp &LIST_NEXT((elm), field); \ 404273806Snp LIST_NEXT((listelm), field) = (elm); \ 405273806Snp (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 406273806Snp} while (0) 407273806Snp 408273806Snp#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 409273806Snp QMD_LIST_CHECK_PREV(listelm, field); \ 410273806Snp (elm)->field.le_prev = (listelm)->field.le_prev; \ 411273806Snp LIST_NEXT((elm), field) = (listelm); \ 412273806Snp *(listelm)->field.le_prev = (elm); \ 413273806Snp (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 414273806Snp} while (0) 415273806Snp 416273806Snp#define LIST_INSERT_HEAD(head, elm, field) do { \ 417273806Snp QMD_LIST_CHECK_HEAD((head), field); \ 418273806Snp if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 419273806Snp LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 420273806Snp LIST_FIRST((head)) = (elm); \ 421273806Snp (elm)->field.le_prev = &LIST_FIRST((head)); \ 422273806Snp} while (0) 423273806Snp 424273806Snp#define LIST_NEXT(elm, field) ((elm)->field.le_next) 425273806Snp 426273806Snp#define LIST_REMOVE(elm, field) do { \ 427273806Snp QMD_LIST_CHECK_NEXT(elm, field); \ 428273806Snp QMD_LIST_CHECK_PREV(elm, field); \ 429273806Snp if (LIST_NEXT((elm), field) != NULL) \ 430273806Snp LIST_NEXT((elm), field)->field.le_prev = \ 431273806Snp (elm)->field.le_prev; \ 432273806Snp *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 433273806Snp TRASHIT((elm)->field.le_next); \ 434273806Snp TRASHIT((elm)->field.le_prev); \ 435273806Snp} while (0) 436273806Snp 437273806Snp/* 438273806Snp * Tail queue declarations. 439273806Snp */ 440273806Snp#define TAILQ_HEAD(name, type) \ 441273806Snpstruct name { \ 442273806Snp struct type *tqh_first; /* first element */ \ 443273806Snp struct type **tqh_last; /* addr of last next element */ \ 444273806Snp TRACEBUF \ 445273806Snp} 446273806Snp 447273806Snp#define TAILQ_HEAD_INITIALIZER(head) \ 448273806Snp { NULL, &(head).tqh_first } 449273806Snp 450273806Snp#define TAILQ_ENTRY(type) \ 451273806Snpstruct { \ 452273806Snp struct type *tqe_next; /* next element */ \ 453273806Snp struct type **tqe_prev; /* address of previous next element */ \ 454273806Snp TRACEBUF \ 455273806Snp} 456273806Snp 457273806Snp/* 458273806Snp * Tail queue functions. 459273806Snp */ 460273806Snp#if (defined(_KERNEL) && defined(INVARIANTS)) 461273806Snp#define QMD_TAILQ_CHECK_HEAD(head, field) do { \ 462273806Snp if (!TAILQ_EMPTY(head) && \ 463273806Snp TAILQ_FIRST((head))->field.tqe_prev != \ 464273806Snp &TAILQ_FIRST((head))) \ 465273806Snp panic("Bad tailq head %p first->prev != head", (head)); \ 466273806Snp} while (0) 467273806Snp 468273806Snp#define QMD_TAILQ_CHECK_TAIL(head, field) do { \ 469273806Snp if (*(head)->tqh_last != NULL) \ 470273806Snp panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \ 471273806Snp} while (0) 472273806Snp 473273806Snp#define QMD_TAILQ_CHECK_NEXT(elm, field) do { \ 474273806Snp if (TAILQ_NEXT((elm), field) != NULL && \ 475273806Snp TAILQ_NEXT((elm), field)->field.tqe_prev != \ 476273806Snp &((elm)->field.tqe_next)) \ 477273806Snp panic("Bad link elm %p next->prev != elm", (elm)); \ 478273806Snp} while (0) 479273806Snp 480273806Snp#define QMD_TAILQ_CHECK_PREV(elm, field) do { \ 481273806Snp if (*(elm)->field.tqe_prev != (elm)) \ 482273806Snp panic("Bad link elm %p prev->next != elm", (elm)); \ 483273806Snp} while (0) 484273806Snp#else 485273806Snp#define QMD_TAILQ_CHECK_HEAD(head, field) 486273806Snp#define QMD_TAILQ_CHECK_TAIL(head, headname) 487273806Snp#define QMD_TAILQ_CHECK_NEXT(elm, field) 488273806Snp#define QMD_TAILQ_CHECK_PREV(elm, field) 489273806Snp#endif /* (_KERNEL && INVARIANTS) */ 490273806Snp 491273806Snp#define TAILQ_CONCAT(head1, head2, field) do { \ 492273806Snp if (!TAILQ_EMPTY(head2)) { \ 493273806Snp *(head1)->tqh_last = (head2)->tqh_first; \ 494273806Snp (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 495273806Snp (head1)->tqh_last = (head2)->tqh_last; \ 496273806Snp TAILQ_INIT((head2)); \ 497273806Snp QMD_TRACE_HEAD(head1); \ 498273806Snp QMD_TRACE_HEAD(head2); \ 499273806Snp } \ 500273806Snp} while (0) 501273806Snp 502273806Snp#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 503273806Snp 504273806Snp#define TAILQ_FIRST(head) ((head)->tqh_first) 505273806Snp 506273806Snp#define TAILQ_FOREACH(var, head, field) \ 507273806Snp for ((var) = TAILQ_FIRST((head)); \ 508273806Snp (var); \ 509273806Snp (var) = TAILQ_NEXT((var), field)) 510273806Snp 511273806Snp#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 512273806Snp for ((var) = TAILQ_FIRST((head)); \ 513273806Snp (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 514273806Snp (var) = (tvar)) 515273806Snp 516273806Snp#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 517273806Snp for ((var) = TAILQ_LAST((head), headname); \ 518273806Snp (var); \ 519273806Snp (var) = TAILQ_PREV((var), headname, field)) 520273806Snp 521273806Snp#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 522273806Snp for ((var) = TAILQ_LAST((head), headname); \ 523273806Snp (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 524273806Snp (var) = (tvar)) 525273806Snp 526273806Snp#define TAILQ_INIT(head) do { \ 527273806Snp TAILQ_FIRST((head)) = NULL; \ 528273806Snp (head)->tqh_last = &TAILQ_FIRST((head)); \ 529273806Snp QMD_TRACE_HEAD(head); \ 530273806Snp} while (0) 531273806Snp 532273806Snp#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 533273806Snp QMD_TAILQ_CHECK_NEXT(listelm, field); \ 534273806Snp if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 535273806Snp TAILQ_NEXT((elm), field)->field.tqe_prev = \ 536273806Snp &TAILQ_NEXT((elm), field); \ 537273806Snp else { \ 538273806Snp (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 539273806Snp QMD_TRACE_HEAD(head); \ 540273806Snp } \ 541273806Snp TAILQ_NEXT((listelm), field) = (elm); \ 542273806Snp (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 543273806Snp QMD_TRACE_ELEM(&(elm)->field); \ 544273806Snp QMD_TRACE_ELEM(&listelm->field); \ 545273806Snp} while (0) 546273806Snp 547273806Snp#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 548273806Snp QMD_TAILQ_CHECK_PREV(listelm, field); \ 549273806Snp (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 550273806Snp TAILQ_NEXT((elm), field) = (listelm); \ 551273806Snp *(listelm)->field.tqe_prev = (elm); \ 552273806Snp (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 553273806Snp QMD_TRACE_ELEM(&(elm)->field); \ 554273806Snp QMD_TRACE_ELEM(&listelm->field); \ 555273806Snp} while (0) 556273806Snp 557273806Snp#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 558273806Snp QMD_TAILQ_CHECK_HEAD(head, field); \ 559273806Snp if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 560273806Snp TAILQ_FIRST((head))->field.tqe_prev = \ 561273806Snp &TAILQ_NEXT((elm), field); \ 562273806Snp else \ 563273806Snp (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 564273806Snp TAILQ_FIRST((head)) = (elm); \ 565273806Snp (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 566273806Snp QMD_TRACE_HEAD(head); \ 567273806Snp QMD_TRACE_ELEM(&(elm)->field); \ 568273806Snp} while (0) 569273806Snp 570273806Snp#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 571273806Snp QMD_TAILQ_CHECK_TAIL(head, field); \ 572273806Snp TAILQ_NEXT((elm), field) = NULL; \ 573273806Snp (elm)->field.tqe_prev = (head)->tqh_last; \ 574273806Snp *(head)->tqh_last = (elm); \ 575273806Snp (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 576273806Snp QMD_TRACE_HEAD(head); \ 577273806Snp QMD_TRACE_ELEM(&(elm)->field); \ 578273806Snp} while (0) 579273806Snp 580273806Snp#define TAILQ_LAST(head, headname) \ 581273806Snp (*(((struct headname *)((head)->tqh_last))->tqh_last)) 582273806Snp 583273806Snp#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 584273806Snp 585273806Snp#define TAILQ_PREV(elm, headname, field) \ 586273806Snp (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 587273806Snp 588273806Snp#define TAILQ_REMOVE(head, elm, field) do { \ 589273806Snp QMD_TAILQ_CHECK_NEXT(elm, field); \ 590273806Snp QMD_TAILQ_CHECK_PREV(elm, field); \ 591273806Snp if ((TAILQ_NEXT((elm), field)) != NULL) \ 592273806Snp TAILQ_NEXT((elm), field)->field.tqe_prev = \ 593273806Snp (elm)->field.tqe_prev; \ 594273806Snp else { \ 595273806Snp (head)->tqh_last = (elm)->field.tqe_prev; \ 596273806Snp QMD_TRACE_HEAD(head); \ 597273806Snp } \ 598273806Snp *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 599273806Snp TRASHIT((elm)->field.tqe_next); \ 600273806Snp TRASHIT((elm)->field.tqe_prev); \ 601273806Snp QMD_TRACE_ELEM(&(elm)->field); \ 602273806Snp} while (0) 603273806Snp 604273806Snp 605273806Snp#ifdef _KERNEL 606273806Snp 607273806Snp/* 608273806Snp * XXX insque() and remque() are an old way of handling certain queues. 609273806Snp * They bogusly assumes that all queue heads look alike. 610273806Snp */ 611273806Snp 612273806Snpstruct quehead { 613273806Snp struct quehead *qh_link; 614273806Snp struct quehead *qh_rlink; 615273806Snp}; 616273806Snp 617273806Snp#ifdef __CC_SUPPORTS___INLINE 618273806Snp 619273806Snpstatic __inline void 620273806Snpinsque(void *a, void *b) 621273806Snp{ 622273806Snp struct quehead *element = (struct quehead *)a, 623273806Snp *head = (struct quehead *)b; 624273806Snp 625273806Snp element->qh_link = head->qh_link; 626273806Snp element->qh_rlink = head; 627273806Snp head->qh_link = element; 628273806Snp element->qh_link->qh_rlink = element; 629273806Snp} 630273806Snp 631273806Snpstatic __inline void 632273806Snpremque(void *a) 633273806Snp{ 634273806Snp struct quehead *element = (struct quehead *)a; 635273806Snp 636273806Snp element->qh_link->qh_rlink = element->qh_rlink; 637273806Snp element->qh_rlink->qh_link = element->qh_link; 638273806Snp element->qh_rlink = 0; 639273806Snp} 640273806Snp 641273806Snp#else /* !__CC_SUPPORTS___INLINE */ 642273806Snp 643273806Snpvoid insque(void *a, void *b); 644273806Snpvoid remque(void *a); 645273806Snp 646273806Snp#endif /* __CC_SUPPORTS___INLINE */ 647273806Snp 648273806Snp#endif /* _KERNEL */ 649273806Snp 650273806Snp#endif /* !_SYS_QUEUE_H_ */ 651