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