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