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