1381a2a9aSdr146992 /* 2381a2a9aSdr146992 * Copyright (c) 1991, 1993 3381a2a9aSdr146992 * The Regents of the University of California. All rights reserved. 4381a2a9aSdr146992 * 5381a2a9aSdr146992 * Redistribution and use in source and binary forms, with or without 6381a2a9aSdr146992 * modification, are permitted provided that the following conditions 7381a2a9aSdr146992 * are met: 8381a2a9aSdr146992 * 1. Redistributions of source code must retain the above copyright 9381a2a9aSdr146992 * notice, this list of conditions and the following disclaimer. 10381a2a9aSdr146992 * 2. Redistributions in binary form must reproduce the above copyright 11381a2a9aSdr146992 * notice, this list of conditions and the following disclaimer in the 12381a2a9aSdr146992 * documentation and/or other materials provided with the distribution. 13381a2a9aSdr146992 * 3. Neither the name of the University nor the names of its contributors 14381a2a9aSdr146992 * may be used to endorse or promote products derived from this software 15381a2a9aSdr146992 * without specific prior written permission. 16381a2a9aSdr146992 * 17381a2a9aSdr146992 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18381a2a9aSdr146992 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19381a2a9aSdr146992 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20381a2a9aSdr146992 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21381a2a9aSdr146992 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22381a2a9aSdr146992 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23381a2a9aSdr146992 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24381a2a9aSdr146992 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25381a2a9aSdr146992 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26381a2a9aSdr146992 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27381a2a9aSdr146992 * SUCH DAMAGE. 28381a2a9aSdr146992 * 29381a2a9aSdr146992 * @(#)queue.h 8.5 (Berkeley) 8/20/94 30381a2a9aSdr146992 */ 31381a2a9aSdr146992 /* 32c1374a13SSurya Prakki * Copyright 2009 Sun Microsystems, Inc. All rights reserved. 33381a2a9aSdr146992 * Use is subject to license terms. 34381a2a9aSdr146992 */ 35381a2a9aSdr146992 36381a2a9aSdr146992 #ifndef _SYS_QUEUE_H 37381a2a9aSdr146992 #define _SYS_QUEUE_H 38381a2a9aSdr146992 39381a2a9aSdr146992 #include <sys/note.h> 40*85280f08SToomas Soome #include <sys/containerof.h> 41381a2a9aSdr146992 42381a2a9aSdr146992 #ifdef __cplusplus 43381a2a9aSdr146992 extern "C" { 44381a2a9aSdr146992 #endif 45381a2a9aSdr146992 46381a2a9aSdr146992 /* 47381a2a9aSdr146992 * This file defines five types of data structures: singly-linked lists, 48381a2a9aSdr146992 * lists, simple queues, tail queues, and circular queues. 49381a2a9aSdr146992 * 50381a2a9aSdr146992 * A singly-linked list is headed by a single forward pointer. The 51381a2a9aSdr146992 * elements are singly linked for minimum space and pointer manipulation 52381a2a9aSdr146992 * overhead at the expense of O(n) removal for arbitrary elements. New 53381a2a9aSdr146992 * elements can be added to the list after an existing element or at the 54381a2a9aSdr146992 * head of the list. Elements being removed from the head of the list 55381a2a9aSdr146992 * should use the explicit macro for this purpose for optimum 56381a2a9aSdr146992 * efficiency. A singly-linked list may only be traversed in the forward 57381a2a9aSdr146992 * direction. Singly-linked lists are ideal for applications with large 58381a2a9aSdr146992 * datasets and few or no removals or for implementing a LIFO queue. 59381a2a9aSdr146992 * 60381a2a9aSdr146992 * A list is headed by a single forward pointer (or an array of forward 61381a2a9aSdr146992 * pointers for a hash table header). The elements are doubly linked 62381a2a9aSdr146992 * so that an arbitrary element can be removed without a need to 63381a2a9aSdr146992 * traverse the list. New elements can be added to the list before 64381a2a9aSdr146992 * or after an existing element or at the head of the list. A list 65381a2a9aSdr146992 * may only be traversed in the forward direction. 66381a2a9aSdr146992 * 67381a2a9aSdr146992 * A simple queue is headed by a pair of pointers, one the head of the 68381a2a9aSdr146992 * list and the other to the tail of the list. The elements are singly 69381a2a9aSdr146992 * linked to save space, so elements can only be removed from the 70381a2a9aSdr146992 * head of the list. New elements can be added to the list after 71381a2a9aSdr146992 * an existing element, at the head of the list, or at the end of the 72381a2a9aSdr146992 * list. A simple queue may only be traversed in the forward direction. 73381a2a9aSdr146992 * 74381a2a9aSdr146992 * A tail queue is headed by a pair of pointers, one to the head of the 75381a2a9aSdr146992 * list and the other to the tail of the list. The elements are doubly 76381a2a9aSdr146992 * linked so that an arbitrary element can be removed without a need to 77381a2a9aSdr146992 * traverse the list. New elements can be added to the list before or 78381a2a9aSdr146992 * after an existing element, at the head of the list, or at the end of 79381a2a9aSdr146992 * the list. A tail queue may be traversed in either direction. 80381a2a9aSdr146992 * 81381a2a9aSdr146992 * A circle queue is headed by a pair of pointers, one to the head of the 82381a2a9aSdr146992 * list and the other to the tail of the list. The elements are doubly 83381a2a9aSdr146992 * linked so that an arbitrary element can be removed without a need to 84381a2a9aSdr146992 * traverse the list. New elements can be added to the list before or after 85381a2a9aSdr146992 * an existing element, at the head of the list, or at the end of the list. 86381a2a9aSdr146992 * A circle queue may be traversed in either direction, but has a more 87381a2a9aSdr146992 * complex end of list detection. 88381a2a9aSdr146992 * 89*85280f08SToomas Soome * For details on the use of these macros, see the queue.h(3HEAD) manual page. 90381a2a9aSdr146992 */ 91381a2a9aSdr146992 92*85280f08SToomas Soome #ifdef QUEUE_MACRO_DEBUG 93*85280f08SToomas Soome #warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH 94*85280f08SToomas Soome #define QUEUE_MACRO_DEBUG_TRACE 95*85280f08SToomas Soome #define QUEUE_MACRO_DEBUG_TRASH 96*85280f08SToomas Soome #endif 97*85280f08SToomas Soome 98*85280f08SToomas Soome #ifdef QUEUE_MACRO_DEBUG_TRACE 99*85280f08SToomas Soome /* Store the last 2 places the queue element or head was altered */ 100*85280f08SToomas Soome struct qm_trace { 101*85280f08SToomas Soome unsigned long lastline; 102*85280f08SToomas Soome unsigned long prevline; 103*85280f08SToomas Soome const char *lastfile; 104*85280f08SToomas Soome const char *prevfile; 105*85280f08SToomas Soome }; 106*85280f08SToomas Soome 107*85280f08SToomas Soome #define TRACEBUF struct qm_trace trace; 108*85280f08SToomas Soome #define TRACEBUF_INITIALIZER { __LINE__, 0, __FILE__, NULL }, 109*85280f08SToomas Soome 110*85280f08SToomas Soome #define QMD_TRACE_HEAD(head) do { \ 111*85280f08SToomas Soome (head)->trace.prevline = (head)->trace.lastline; \ 112*85280f08SToomas Soome (head)->trace.prevfile = (head)->trace.lastfile; \ 113*85280f08SToomas Soome (head)->trace.lastline = __LINE__; \ 114*85280f08SToomas Soome (head)->trace.lastfile = __FILE__; \ 115*85280f08SToomas Soome _NOTE(CONSTCOND) \ 116*85280f08SToomas Soome } while (0) 117*85280f08SToomas Soome 118*85280f08SToomas Soome #define QMD_TRACE_ELEM(elem) do { \ 119*85280f08SToomas Soome (elem)->trace.prevline = (elem)->trace.lastline; \ 120*85280f08SToomas Soome (elem)->trace.prevfile = (elem)->trace.lastfile; \ 121*85280f08SToomas Soome (elem)->trace.lastline = __LINE__; \ 122*85280f08SToomas Soome (elem)->trace.lastfile = __FILE__; \ 123*85280f08SToomas Soome _NOTE(CONSTCOND) \ 124*85280f08SToomas Soome } while (0) 125*85280f08SToomas Soome 126*85280f08SToomas Soome #else /* !QUEUE_MACRO_DEBUG_TRACE */ 127*85280f08SToomas Soome #define QMD_TRACE_ELEM(elem) 128*85280f08SToomas Soome #define QMD_TRACE_HEAD(head) 129*85280f08SToomas Soome #define TRACEBUF 130*85280f08SToomas Soome #define TRACEBUF_INITIALIZER 131*85280f08SToomas Soome #endif /* QUEUE_MACRO_DEBUG_TRACE */ 132*85280f08SToomas Soome 133*85280f08SToomas Soome #ifdef QUEUE_MACRO_DEBUG_TRASH 134*85280f08SToomas Soome #define TRASHIT(x) do {(x) = (void *)-1; } while (0) 135*85280f08SToomas Soome #define QMD_IS_TRASHED(x) ((x) == (void *)(intptr_t)-1) 136*85280f08SToomas Soome #else /* !QUEUE_MACRO_DEBUG_TRASH */ 137*85280f08SToomas Soome #define TRASHIT(x) 138*85280f08SToomas Soome #define QMD_IS_TRASHED(x) 0 139*85280f08SToomas Soome #endif /* QUEUE_MACRO_DEBUG_TRASH */ 140*85280f08SToomas Soome 141*85280f08SToomas Soome #if defined(QUEUE_MACRO_DEBUG_TRACE) || defined(QUEUE_MACRO_DEBUG_TRASH) 142*85280f08SToomas Soome #define QMD_SAVELINK(name, link) void **name = (void *)&(link) 143*85280f08SToomas Soome #else /* !QUEUE_MACRO_DEBUG_TRACE && !QUEUE_MACRO_DEBUG_TRASH */ 144*85280f08SToomas Soome #define QMD_SAVELINK(name, link) 145*85280f08SToomas Soome #endif /* QUEUE_MACRO_DEBUG_TRACE || QUEUE_MACRO_DEBUG_TRASH */ 146*85280f08SToomas Soome 147*85280f08SToomas Soome #ifdef __cplusplus 148*85280f08SToomas Soome /* 149*85280f08SToomas Soome * In C++ there can be structure lists and class lists: 150*85280f08SToomas Soome */ 151*85280f08SToomas Soome #define QUEUE_TYPEOF(type) type 152*85280f08SToomas Soome #else 153*85280f08SToomas Soome #define QUEUE_TYPEOF(type) struct type 154*85280f08SToomas Soome #endif 155*85280f08SToomas Soome 156*85280f08SToomas Soome /* 157*85280f08SToomas Soome * Singly-linked List definitions. 158*85280f08SToomas Soome */ 159*85280f08SToomas Soome #define SLIST_HEAD(name, type) \ 160*85280f08SToomas Soome struct name { \ 161*85280f08SToomas Soome struct type *slh_first; /* first element */ \ 162*85280f08SToomas Soome } 163*85280f08SToomas Soome 164*85280f08SToomas Soome #define SLIST_CLASS_HEAD(name, type) \ 165*85280f08SToomas Soome struct name { \ 166*85280f08SToomas Soome class type *slh_first; /* first element */ \ 167*85280f08SToomas Soome } 168*85280f08SToomas Soome 169*85280f08SToomas Soome #define SLIST_HEAD_INITIALIZER(head) \ 170*85280f08SToomas Soome { NULL } 171*85280f08SToomas Soome 172*85280f08SToomas Soome #define SLIST_ENTRY(type) \ 173*85280f08SToomas Soome struct { \ 174*85280f08SToomas Soome struct type *sle_next; /* next element */ \ 175*85280f08SToomas Soome } 176*85280f08SToomas Soome 177*85280f08SToomas Soome #define SLIST_CLASS_ENTRY(type) \ 178*85280f08SToomas Soome struct { \ 179*85280f08SToomas Soome class type *sle_next; /* next element */ \ 180*85280f08SToomas Soome } 181*85280f08SToomas Soome 182*85280f08SToomas Soome /* 183*85280f08SToomas Soome * Singly-linked List access methods. 184*85280f08SToomas Soome */ 185*85280f08SToomas Soome #define SLIST_FIRST(head) ((head)->slh_first) 186*85280f08SToomas Soome #define SLIST_END(head) NULL 187*85280f08SToomas Soome #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 188*85280f08SToomas Soome #define SLIST_EMPTY(head) ((head)->slh_first == SLIST_END(head)) 189*85280f08SToomas Soome 190*85280f08SToomas Soome #define SLIST_FOREACH(var, head, field) \ 191*85280f08SToomas Soome for ((var) = SLIST_FIRST((head)); \ 192*85280f08SToomas Soome (var) != SLIST_END(head); \ 193*85280f08SToomas Soome (var) = SLIST_NEXT((var), field)) 194*85280f08SToomas Soome 195*85280f08SToomas Soome #define SLIST_FOREACH_FROM(var, head, field) \ 196*85280f08SToomas Soome for ((var) = ((var) != SLIST_END(head) ? (var) : SLIST_FIRST((head))); \ 197*85280f08SToomas Soome (var) != SLIST_END(head); \ 198*85280f08SToomas Soome (var) = SLIST_NEXT((var), field)) 199*85280f08SToomas Soome 200*85280f08SToomas Soome #define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 201*85280f08SToomas Soome for ((var) = SLIST_FIRST((head)); \ 202*85280f08SToomas Soome (var) != SLIST_END(head) && \ 203*85280f08SToomas Soome ((tvar) = SLIST_NEXT((var), field), 1); \ 204*85280f08SToomas Soome (var) = (tvar)) 205*85280f08SToomas Soome 206*85280f08SToomas Soome #define SLIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 207*85280f08SToomas Soome for ((var) = ((var) != SLIST_END(head) ? (var) : SLIST_FIRST((head))); \ 208*85280f08SToomas Soome (var) != SLIST_END(head) && \ 209*85280f08SToomas Soome ((tvar) = SLIST_NEXT((var), field), 1); \ 210*85280f08SToomas Soome (var) = (tvar)) 211*85280f08SToomas Soome 212*85280f08SToomas Soome /* 213*85280f08SToomas Soome * Singly-linked List functions. 214*85280f08SToomas Soome */ 215*85280f08SToomas Soome #define SLIST_INIT(head) do { \ 216*85280f08SToomas Soome (head)->slh_first = SLIST_END(head); \ 217*85280f08SToomas Soome _NOTE(CONSTCOND) \ 218*85280f08SToomas Soome } while (0) 219*85280f08SToomas Soome 220*85280f08SToomas Soome #define SLIST_CONCAT(head1, head2, type, field) do { \ 221*85280f08SToomas Soome QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1); \ 222*85280f08SToomas Soome if (curelm == SLIST_END(head1)) { \ 223*85280f08SToomas Soome if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != \ 224*85280f08SToomas Soome SLIST_END(head1)) \ 225*85280f08SToomas Soome SLIST_INIT(head2); \ 226*85280f08SToomas Soome } else if (SLIST_FIRST(head2) != SLIST_END(head2)) { \ 227*85280f08SToomas Soome while (SLIST_NEXT(curelm, field) != SLIST_END(head1)) \ 228*85280f08SToomas Soome curelm = SLIST_NEXT(curelm, field); \ 229*85280f08SToomas Soome SLIST_NEXT(curelm, field) = SLIST_FIRST(head2); \ 230*85280f08SToomas Soome SLIST_INIT(head2); \ 231*85280f08SToomas Soome } \ 232*85280f08SToomas Soome _NOTE(CONSTCOND) \ 233*85280f08SToomas Soome } while (0) 234*85280f08SToomas Soome 235*85280f08SToomas Soome #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 236*85280f08SToomas Soome SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 237*85280f08SToomas Soome SLIST_NEXT((slistelm), field) = (elm); \ 238*85280f08SToomas Soome _NOTE(CONSTCOND) \ 239*85280f08SToomas Soome } while (0) 240*85280f08SToomas Soome 241*85280f08SToomas Soome #define SLIST_INSERT_HEAD(head, elm, field) do { \ 242*85280f08SToomas Soome SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 243*85280f08SToomas Soome SLIST_FIRST((head)) = (elm); \ 244*85280f08SToomas Soome _NOTE(CONSTCOND) \ 245*85280f08SToomas Soome } while (0) 246*85280f08SToomas Soome 247*85280f08SToomas Soome #define SLIST_REMOVE_HEAD(head, field) do { \ 248*85280f08SToomas Soome SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 249*85280f08SToomas Soome _NOTE(CONSTCOND) \ 250*85280f08SToomas Soome } while (0) 251*85280f08SToomas Soome 252*85280f08SToomas Soome #define SLIST_REMOVE_AFTER(slistelm, field) do { \ 253*85280f08SToomas Soome SLIST_NEXT((slistelm), field) = \ 254*85280f08SToomas Soome SLIST_NEXT(SLIST_NEXT((slistelm), field), field); \ 255*85280f08SToomas Soome _NOTE(CONSTCOND) \ 256*85280f08SToomas Soome } while (0) 257*85280f08SToomas Soome 258*85280f08SToomas Soome #define SLIST_REMOVE(head, elm, type, field) do { \ 259*85280f08SToomas Soome QMD_SAVELINK(oldnext, SLIST_NEXT((elm), field)); \ 260*85280f08SToomas Soome if (SLIST_FIRST((head)) == (elm)) { \ 261*85280f08SToomas Soome SLIST_REMOVE_HEAD((head), field); \ 262*85280f08SToomas Soome } \ 263*85280f08SToomas Soome else { \ 264*85280f08SToomas Soome QUEUE_TYPEOF(type) *curelm = SLIST_FIRST((head)); \ 265*85280f08SToomas Soome while (SLIST_NEXT(curelm, field) != (elm)) \ 266*85280f08SToomas Soome curelm = SLIST_NEXT(curelm, field); \ 267*85280f08SToomas Soome SLIST_REMOVE_AFTER(curelm, field); \ 268*85280f08SToomas Soome } \ 269*85280f08SToomas Soome TRASHIT(*oldnext); \ 270*85280f08SToomas Soome _NOTE(CONSTCOND) \ 271*85280f08SToomas Soome } while (0) 272*85280f08SToomas Soome 273*85280f08SToomas Soome #define SLIST_SWAP(head1, head2, type) do { \ 274*85280f08SToomas Soome QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1); \ 275*85280f08SToomas Soome SLIST_FIRST(head1) = SLIST_FIRST(head2); \ 276*85280f08SToomas Soome SLIST_FIRST(head2) = swap_first; \ 277*85280f08SToomas Soome } while (0) 278*85280f08SToomas Soome 279*85280f08SToomas Soome /* 280*85280f08SToomas Soome * Singly-linked Tail queue declarations. 281*85280f08SToomas Soome */ 282*85280f08SToomas Soome #define STAILQ_HEAD(name, type) \ 283*85280f08SToomas Soome struct name { \ 284*85280f08SToomas Soome struct type *stqh_first; /* first element */ \ 285*85280f08SToomas Soome struct type **stqh_last; /* addr of last next element */ \ 286*85280f08SToomas Soome } 287*85280f08SToomas Soome 288*85280f08SToomas Soome #define STAILQ_CLASS_HEAD(name, type) \ 289*85280f08SToomas Soome struct name { \ 290*85280f08SToomas Soome class type *stqh_first; /* first element */ \ 291*85280f08SToomas Soome class type **stqh_last; /* addr of last next element */ \ 292*85280f08SToomas Soome } 293*85280f08SToomas Soome 294*85280f08SToomas Soome #define STAILQ_HEAD_INITIALIZER(head) \ 295*85280f08SToomas Soome { NULL, &(head).stqh_first } 296*85280f08SToomas Soome 297*85280f08SToomas Soome #define STAILQ_ENTRY(type) \ 298*85280f08SToomas Soome struct { \ 299*85280f08SToomas Soome struct type *stqe_next; /* next element */ \ 300*85280f08SToomas Soome } 301*85280f08SToomas Soome 302*85280f08SToomas Soome #define STAILQ_CLASS_ENTRY(type) \ 303*85280f08SToomas Soome struct { \ 304*85280f08SToomas Soome class type *stqe_next; /* next element */ \ 305*85280f08SToomas Soome } 306*85280f08SToomas Soome 307*85280f08SToomas Soome /* 308*85280f08SToomas Soome * Singly-linked Tail queue access methods. 309*85280f08SToomas Soome */ 310*85280f08SToomas Soome #define STAILQ_FIRST(head) ((head)->stqh_first) 311*85280f08SToomas Soome #define STAILQ_END(head) NULL 312*85280f08SToomas Soome #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 313*85280f08SToomas Soome #define STAILQ_EMPTY(head) ((head)->stqh_first == STAILQ_END(head)) 314*85280f08SToomas Soome 315*85280f08SToomas Soome #define STAILQ_FOREACH(var, head, field) \ 316*85280f08SToomas Soome for ((var) = STAILQ_FIRST(head); \ 317*85280f08SToomas Soome (var) != STAILQ_END(head); \ 318*85280f08SToomas Soome (var) = STAILQ_NEXT((var), field)) 319*85280f08SToomas Soome 320*85280f08SToomas Soome #define STAILQ_FOREACH_FROM(var, head, field) \ 321*85280f08SToomas Soome for ((var) = \ 322*85280f08SToomas Soome ((var) != STAILQ_END(head) ? (var) : STAILQ_FIRST((head))); \ 323*85280f08SToomas Soome (var) != STAILQ_END(head); \ 324*85280f08SToomas Soome (var) = STAILQ_NEXT((var), field)) 325*85280f08SToomas Soome 326*85280f08SToomas Soome #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 327*85280f08SToomas Soome for ((var) = STAILQ_FIRST(head); \ 328*85280f08SToomas Soome (var) != STAILQ_END(head) && \ 329*85280f08SToomas Soome ((tvar) = STAILQ_NEXT((var), field), 1); \ 330*85280f08SToomas Soome (var) = (tvar)) 331*85280f08SToomas Soome 332*85280f08SToomas Soome #define STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 333*85280f08SToomas Soome for ((var) = \ 334*85280f08SToomas Soome ((var) != STAILQ_END(head) ? (var) : STAILQ_FIRST((head))); \ 335*85280f08SToomas Soome (var) != STAILQ_END(head) && \ 336*85280f08SToomas Soome ((tvar) = STAILQ_NEXT((var), field), 1); \ 337*85280f08SToomas Soome (var) = (tvar)) 338*85280f08SToomas Soome 339*85280f08SToomas Soome /* 340*85280f08SToomas Soome * Singly-linked Tail queue functions. 341*85280f08SToomas Soome */ 342*85280f08SToomas Soome #define STAILQ_INIT(head) do { \ 343*85280f08SToomas Soome STAILQ_FIRST(head) = STAILQ_END(head); \ 344*85280f08SToomas Soome (head)->stqh_last = &STAILQ_FIRST((head)); \ 345*85280f08SToomas Soome _NOTE(CONSTCOND) \ 346*85280f08SToomas Soome } while (0) 347*85280f08SToomas Soome 348*85280f08SToomas Soome #define STAILQ_CONCAT(head1, head2) do { \ 349*85280f08SToomas Soome if (!STAILQ_EMPTY((head2))) { \ 350*85280f08SToomas Soome *(head1)->stqh_last = STAILQ_FIRST((head2)); \ 351*85280f08SToomas Soome (head1)->stqh_last = (head2)->stqh_last; \ 352*85280f08SToomas Soome STAILQ_INIT((head2)); \ 353*85280f08SToomas Soome } \ 354*85280f08SToomas Soome _NOTE(CONSTCOND) \ 355*85280f08SToomas Soome } while (0) 356*85280f08SToomas Soome 357*85280f08SToomas Soome #define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 358*85280f08SToomas Soome if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 359*85280f08SToomas Soome (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 360*85280f08SToomas Soome STAILQ_NEXT((tqelm), field) = (elm); \ 361*85280f08SToomas Soome _NOTE(CONSTCOND) \ 362*85280f08SToomas Soome } while (0) 363*85280f08SToomas Soome 364*85280f08SToomas Soome #define STAILQ_INSERT_HEAD(head, elm, field) do { \ 365*85280f08SToomas Soome if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 366*85280f08SToomas Soome (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 367*85280f08SToomas Soome STAILQ_FIRST((head)) = (elm); \ 368*85280f08SToomas Soome _NOTE(CONSTCOND) \ 369*85280f08SToomas Soome } while (0) 370*85280f08SToomas Soome 371*85280f08SToomas Soome #define STAILQ_INSERT_TAIL(head, elm, field) do { \ 372*85280f08SToomas Soome STAILQ_NEXT((elm), field) = NULL; \ 373*85280f08SToomas Soome *(head)->stqh_last = (elm); \ 374*85280f08SToomas Soome (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 375*85280f08SToomas Soome _NOTE(CONSTCOND) \ 376*85280f08SToomas Soome } while (0) 377*85280f08SToomas Soome 378*85280f08SToomas Soome #define STAILQ_LAST(head, type, field) \ 379*85280f08SToomas Soome (STAILQ_EMPTY((head)) ? NULL : \ 380*85280f08SToomas Soome __containerof((head)->stqh_last, \ 381*85280f08SToomas Soome QUEUE_TYPEOF(type), field.stqe_next)) 382*85280f08SToomas Soome 383*85280f08SToomas Soome #define STAILQ_REMOVE_HEAD(head, field) do { \ 384*85280f08SToomas Soome if ((STAILQ_FIRST((head)) = \ 385*85280f08SToomas Soome STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 386*85280f08SToomas Soome (head)->stqh_last = &STAILQ_FIRST((head)); \ 387*85280f08SToomas Soome _NOTE(CONSTCOND) \ 388*85280f08SToomas Soome } while (0) 389*85280f08SToomas Soome 390*85280f08SToomas Soome #define STAILQ_REMOVE_AFTER(head, elm, field) do { \ 391*85280f08SToomas Soome if ((STAILQ_NEXT(elm, field) = \ 392*85280f08SToomas Soome STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL) \ 393*85280f08SToomas Soome (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 394*85280f08SToomas Soome _NOTE(CONSTCOND) \ 395*85280f08SToomas Soome } while (0) 396*85280f08SToomas Soome 397*85280f08SToomas Soome #define STAILQ_REMOVE(head, elm, type, field) do { \ 398*85280f08SToomas Soome QMD_SAVELINK(oldnext, (elm)->field.stqe_next); \ 399*85280f08SToomas Soome if (STAILQ_FIRST((head)) == (elm)) { \ 400*85280f08SToomas Soome STAILQ_REMOVE_HEAD((head), field); \ 401*85280f08SToomas Soome } else { \ 402*85280f08SToomas Soome QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head); \ 403*85280f08SToomas Soome while (STAILQ_NEXT(curelm, field) != (elm)) \ 404*85280f08SToomas Soome curelm = STAILQ_NEXT(curelm, field); \ 405*85280f08SToomas Soome STAILQ_REMOVE_AFTER(head, curelm, field); \ 406*85280f08SToomas Soome } \ 407*85280f08SToomas Soome TRASHIT(*oldnext); \ 408*85280f08SToomas Soome _NOTE(CONSTCOND) \ 409*85280f08SToomas Soome } while (0) 410*85280f08SToomas Soome 411*85280f08SToomas Soome #define STAILQ_SWAP(head1, head2, type) do { \ 412*85280f08SToomas Soome QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1); \ 413*85280f08SToomas Soome QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last; \ 414*85280f08SToomas Soome STAILQ_FIRST(head1) = STAILQ_FIRST(head2); \ 415*85280f08SToomas Soome (head1)->stqh_last = (head2)->stqh_last; \ 416*85280f08SToomas Soome STAILQ_FIRST(head2) = swap_first; \ 417*85280f08SToomas Soome (head2)->stqh_last = swap_last; \ 418*85280f08SToomas Soome if (STAILQ_EMPTY(head1)) \ 419*85280f08SToomas Soome (head1)->stqh_last = &STAILQ_FIRST(head1); \ 420*85280f08SToomas Soome if (STAILQ_EMPTY(head2)) \ 421*85280f08SToomas Soome (head2)->stqh_last = &STAILQ_FIRST(head2); \ 422*85280f08SToomas Soome _NOTE(CONSTCOND) \ 423*85280f08SToomas Soome } while (0) 424*85280f08SToomas Soome 425381a2a9aSdr146992 /* 426381a2a9aSdr146992 * List definitions. 427381a2a9aSdr146992 */ 428381a2a9aSdr146992 #define LIST_HEAD(name, type) \ 429381a2a9aSdr146992 struct name { \ 430381a2a9aSdr146992 struct type *lh_first; /* first element */ \ 431381a2a9aSdr146992 } 432381a2a9aSdr146992 433*85280f08SToomas Soome #define LIST_CLASS_HEAD(name, type) \ 434*85280f08SToomas Soome struct name { \ 435*85280f08SToomas Soome class type *lh_first; /* first element */ \ 436*85280f08SToomas Soome } 437*85280f08SToomas Soome 438381a2a9aSdr146992 #define LIST_HEAD_INITIALIZER(head) \ 439381a2a9aSdr146992 { NULL } 440381a2a9aSdr146992 441381a2a9aSdr146992 #define LIST_ENTRY(type) \ 442381a2a9aSdr146992 struct { \ 443381a2a9aSdr146992 struct type *le_next; /* next element */ \ 444381a2a9aSdr146992 struct type **le_prev; /* address of previous next element */ \ 445381a2a9aSdr146992 } 446381a2a9aSdr146992 447*85280f08SToomas Soome #define LIST_CLASS_ENTRY(type) \ 448*85280f08SToomas Soome struct { \ 449*85280f08SToomas Soome class type *le_next; /* next element */ \ 450*85280f08SToomas Soome class type **le_prev; /* address of previous next element */ \ 451*85280f08SToomas Soome } 452*85280f08SToomas Soome 453*85280f08SToomas Soome /* 454*85280f08SToomas Soome * List access methods. 455*85280f08SToomas Soome */ 456*85280f08SToomas Soome #define LIST_FIRST(head) ((head)->lh_first) 457*85280f08SToomas Soome #define LIST_END(head) NULL 458*85280f08SToomas Soome #define LIST_EMPTY(head) ((head)->lh_first == LIST_END(head)) 459*85280f08SToomas Soome #define LIST_NEXT(elm, field) ((elm)->field.le_next) 460*85280f08SToomas Soome #define LIST_PREV(elm, head, type, field) \ 461*85280f08SToomas Soome ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \ 462*85280f08SToomas Soome __containerof((elm)->field.le_prev, type, field.le_next)) 463*85280f08SToomas Soome 464*85280f08SToomas Soome #define LIST_FOREACH(var, head, field) \ 465*85280f08SToomas Soome for ((var) = LIST_FIRST((head)); \ 466*85280f08SToomas Soome (var) != LIST_END(head); \ 467*85280f08SToomas Soome (var) = LIST_NEXT((var), field)) 468*85280f08SToomas Soome 469*85280f08SToomas Soome #define LIST_FOREACH_FROM(var, head, field) \ 470*85280f08SToomas Soome for ((var) = ((var) != LIST_END(head) ? (var) : LIST_FIRST((head));\ 471*85280f08SToomas Soome (var) != LIST_END(head); \ 472*85280f08SToomas Soome (var) = LIST_NEXT((var), field)) 473*85280f08SToomas Soome 474*85280f08SToomas Soome #define LIST_FOREACH_SAFE(var, head, field, tvar) \ 475*85280f08SToomas Soome for ((var) = LIST_FIRST((head)); \ 476*85280f08SToomas Soome (var) != LIST_END(head) && \ 477*85280f08SToomas Soome ((tvar) = LIST_NEXT((var), field), 1); \ 478*85280f08SToomas Soome (var) = (tvar)) 479*85280f08SToomas Soome 480*85280f08SToomas Soome #define LIST_FOREACH_FROM_SAFE(var, head, field, tvar) \ 481*85280f08SToomas Soome for ((var) = ((var) != LIST_END(head) ? (var) : LIST_FIRST((head));\ 482*85280f08SToomas Soome (var) != LIST_END(head) && \ 483*85280f08SToomas Soome ((tvar) = LIST_NEXT((var), field), 1); \ 484*85280f08SToomas Soome (var) = (tvar)) 485*85280f08SToomas Soome 486381a2a9aSdr146992 /* 487381a2a9aSdr146992 * List functions. 488381a2a9aSdr146992 */ 489381a2a9aSdr146992 #if defined(_KERNEL) && defined(QUEUEDEBUG) 490381a2a9aSdr146992 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) \ 491381a2a9aSdr146992 if ((head)->lh_first && \ 492381a2a9aSdr146992 (head)->lh_first->field.le_prev != &(head)->lh_first) \ 493381a2a9aSdr146992 panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__); 494381a2a9aSdr146992 #define QUEUEDEBUG_LIST_OP(elm, field) \ 495381a2a9aSdr146992 if ((elm)->field.le_next && \ 496381a2a9aSdr146992 (elm)->field.le_next->field.le_prev != \ 497381a2a9aSdr146992 &(elm)->field.le_next) \ 498381a2a9aSdr146992 panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\ 499381a2a9aSdr146992 if (*(elm)->field.le_prev != (elm)) \ 500381a2a9aSdr146992 panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__); 501381a2a9aSdr146992 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) \ 502381a2a9aSdr146992 (elm)->field.le_next = (void *)1L; \ 503381a2a9aSdr146992 (elm)->field.le_prev = (void *)1L; 504381a2a9aSdr146992 #else 505381a2a9aSdr146992 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) 506381a2a9aSdr146992 #define QUEUEDEBUG_LIST_OP(elm, field) 507381a2a9aSdr146992 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) 508381a2a9aSdr146992 #endif 509381a2a9aSdr146992 510381a2a9aSdr146992 #define LIST_INIT(head) do { \ 511*85280f08SToomas Soome LIST_FIRST((head)) = LIST_END(head); \ 512381a2a9aSdr146992 _NOTE(CONSTCOND) \ 513381a2a9aSdr146992 } while (0) 514381a2a9aSdr146992 515381a2a9aSdr146992 #define LIST_INSERT_AFTER(listelm, elm, field) do { \ 516381a2a9aSdr146992 QUEUEDEBUG_LIST_OP((listelm), field) \ 517*85280f08SToomas Soome if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 518*85280f08SToomas Soome LIST_NEXT((listelm), field)->field.le_prev = \ 519*85280f08SToomas Soome &LIST_NEXT((elm), field); \ 520*85280f08SToomas Soome LIST_NEXT((listelm), field) = (elm); \ 521*85280f08SToomas Soome (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 522381a2a9aSdr146992 _NOTE(CONSTCOND) \ 523381a2a9aSdr146992 } while (0) 524381a2a9aSdr146992 525381a2a9aSdr146992 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 526381a2a9aSdr146992 QUEUEDEBUG_LIST_OP((listelm), field) \ 527381a2a9aSdr146992 (elm)->field.le_prev = (listelm)->field.le_prev; \ 528*85280f08SToomas Soome LIST_NEXT((elm), field) = (listelm); \ 529381a2a9aSdr146992 *(listelm)->field.le_prev = (elm); \ 530*85280f08SToomas Soome (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 531381a2a9aSdr146992 _NOTE(CONSTCOND) \ 532381a2a9aSdr146992 } while (0) 533381a2a9aSdr146992 534381a2a9aSdr146992 #define LIST_INSERT_HEAD(head, elm, field) do { \ 535381a2a9aSdr146992 QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field) \ 536*85280f08SToomas Soome if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 537*85280f08SToomas Soome LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 538*85280f08SToomas Soome LIST_FIRST((head)) = (elm); \ 539*85280f08SToomas Soome (elm)->field.le_prev = &LIST_FIRST((head)); \ 540381a2a9aSdr146992 _NOTE(CONSTCOND) \ 541381a2a9aSdr146992 } while (0) 542381a2a9aSdr146992 543381a2a9aSdr146992 #define LIST_REMOVE(elm, field) do { \ 544381a2a9aSdr146992 QUEUEDEBUG_LIST_OP((elm), field) \ 545*85280f08SToomas Soome if (LIST_NEXT((elm), field) != NULL) \ 546*85280f08SToomas Soome LIST_NEXT((elm), field)->field.le_prev = \ 547381a2a9aSdr146992 (elm)->field.le_prev; \ 548*85280f08SToomas Soome *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 549381a2a9aSdr146992 QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \ 550381a2a9aSdr146992 _NOTE(CONSTCOND) \ 551381a2a9aSdr146992 } while (0) 552381a2a9aSdr146992 553*85280f08SToomas Soome #define LIST_SWAP(head1, head2, type, field) do { \ 554*85280f08SToomas Soome QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1); \ 555*85280f08SToomas Soome LIST_FIRST((head1)) = LIST_FIRST((head2)); \ 556*85280f08SToomas Soome LIST_FIRST((head2)) = swap_tmp; \ 557*85280f08SToomas Soome if ((swap_tmp = LIST_FIRST((head1))) != NULL) \ 558*85280f08SToomas Soome swap_tmp->field.le_prev = &LIST_FIRST((head1)); \ 559*85280f08SToomas Soome if ((swap_tmp = LIST_FIRST((head2))) != NULL) \ 560*85280f08SToomas Soome swap_tmp->field.le_prev = &LIST_FIRST((head2)); \ 561381a2a9aSdr146992 _NOTE(CONSTCOND) \ 562381a2a9aSdr146992 } while (0) 563381a2a9aSdr146992 564381a2a9aSdr146992 /* 565381a2a9aSdr146992 * Simple queue definitions. 566381a2a9aSdr146992 */ 567381a2a9aSdr146992 #define SIMPLEQ_HEAD(name, type) \ 568381a2a9aSdr146992 struct name { \ 569381a2a9aSdr146992 struct type *sqh_first; /* first element */ \ 570381a2a9aSdr146992 struct type **sqh_last; /* addr of last next element */ \ 571381a2a9aSdr146992 } 572381a2a9aSdr146992 573*85280f08SToomas Soome #define SIMPLEQ_CLASS_HEAD(name, type) \ 574*85280f08SToomas Soome struct name { \ 575*85280f08SToomas Soome class type *sqh_first; /* first element */ \ 576*85280f08SToomas Soome class type **sqh_last; /* addr of last next element */ \ 577*85280f08SToomas Soome } 578*85280f08SToomas Soome 579381a2a9aSdr146992 #define SIMPLEQ_HEAD_INITIALIZER(head) \ 580381a2a9aSdr146992 { NULL, &(head).sqh_first } 581381a2a9aSdr146992 582381a2a9aSdr146992 #define SIMPLEQ_ENTRY(type) \ 583381a2a9aSdr146992 struct { \ 584381a2a9aSdr146992 struct type *sqe_next; /* next element */ \ 585381a2a9aSdr146992 } 586381a2a9aSdr146992 587*85280f08SToomas Soome #define SIMPLEQ_CLASS_ENTRY(type) \ 588*85280f08SToomas Soome struct { \ 589*85280f08SToomas Soome class type *sqe_next; /* next element */ \ 590*85280f08SToomas Soome } 5918c5d29abSToomas Soome 592b346eeddSGordon Ross /* 593b346eeddSGordon Ross * Simple queue access methods. 594b346eeddSGordon Ross */ 595b346eeddSGordon Ross #define SIMPLEQ_FIRST(head) ((head)->sqh_first) 596*85280f08SToomas Soome #define SIMPLEQ_END(head) NULL 597*85280f08SToomas Soome #define SIMPLEQ_EMPTY(head) ((head)->sqh_first == SIMPLEQ_END(head)) 598b346eeddSGordon Ross #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) 599b346eeddSGordon Ross 600*85280f08SToomas Soome #define SIMPLEQ_FOREACH(var, head, field) \ 601*85280f08SToomas Soome for ((var) = SIMPLEQ_FIRST((head)); \ 602*85280f08SToomas Soome (var) != SIMPLEQ_END(head); \ 603*85280f08SToomas Soome (var) = SIMPLEQ_NEXT((var), field)) 604*85280f08SToomas Soome 605*85280f08SToomas Soome #define SIMPLEQ_FOREACH_FROM(var, head, field) \ 606*85280f08SToomas Soome for ((var) = \ 607*85280f08SToomas Soome ((var) != SIMPLEQ_END(head) ? (var) : SIMPLEQ_FIRST((head)));\ 608*85280f08SToomas Soome (var) != SIMPLEQ_END(head); \ 609*85280f08SToomas Soome (var) = SIMPLEQ_NEXT((var), field)) 610*85280f08SToomas Soome 611*85280f08SToomas Soome #define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ 612*85280f08SToomas Soome for ((var) = SIMPLEQ_FIRST((head)); \ 613*85280f08SToomas Soome (var) != SIMPLEQ_END(head) && \ 614*85280f08SToomas Soome ((tvar) = SIMPLEQ_NEXT((var), field), 1); \ 615*85280f08SToomas Soome (var) = (tvar)) 616*85280f08SToomas Soome 617*85280f08SToomas Soome #define SIMPLEQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 618*85280f08SToomas Soome for ((var) = \ 619*85280f08SToomas Soome ((var) != SIMPLEQ_END(head) ? (var) : SIMPLEQ_FIRST((head)));\ 620*85280f08SToomas Soome (var) != SIMPLEQ_END(head) && \ 621*85280f08SToomas Soome ((tvar) = SIMPLEQ_NEXT((var), field), 1); \ 622*85280f08SToomas Soome (var) = (tvar)) 623*85280f08SToomas Soome 624*85280f08SToomas Soome /* 625*85280f08SToomas Soome * Simple queue functions. 626*85280f08SToomas Soome */ 627*85280f08SToomas Soome #define SIMPLEQ_INIT(head) do { \ 628*85280f08SToomas Soome SIMPLEQ_FIRST((head)) = NULL; \ 629*85280f08SToomas Soome (head)->sqh_last = &SIMPLEQ_FIRST((head)); \ 630*85280f08SToomas Soome _NOTE(CONSTCOND) \ 631*85280f08SToomas Soome } while (0) 632*85280f08SToomas Soome 633*85280f08SToomas Soome #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ 634*85280f08SToomas Soome if ((SIMPLEQ_NEXT((elm), field) = SIMPLEQ_FIRST((head))) == NULL)\ 635*85280f08SToomas Soome (head)->sqh_last = &SIMPLEQ_NEXT((elm), field); \ 636*85280f08SToomas Soome SIMPLEQ_FIRST((head)) = (elm); \ 637*85280f08SToomas Soome _NOTE(CONSTCOND) \ 638*85280f08SToomas Soome } while (0) 639*85280f08SToomas Soome 640*85280f08SToomas Soome #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ 641*85280f08SToomas Soome SIMPLEQ_NEXT((elm), field) = NULL; \ 642*85280f08SToomas Soome *(head)->sqh_last = (elm); \ 643*85280f08SToomas Soome (head)->sqh_last = &SIMPLEQ_NEXT((elm), field); \ 644*85280f08SToomas Soome _NOTE(CONSTCOND) \ 645*85280f08SToomas Soome } while (0) 646*85280f08SToomas Soome 647*85280f08SToomas Soome #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 648*85280f08SToomas Soome if ((SIMPLEQ_NEXT((elm), field) = SIMPLEQ_NEXT((listelm), field)) == \ 649*85280f08SToomas Soome NULL) \ 650*85280f08SToomas Soome (head)->sqh_last = &SIMPLEQ_NEXT((elm), field); \ 651*85280f08SToomas Soome SIMPLEQ_NEXT((listelm), field) = (elm); \ 652*85280f08SToomas Soome _NOTE(CONSTCOND) \ 653*85280f08SToomas Soome } while (0) 654*85280f08SToomas Soome 655*85280f08SToomas Soome #define SIMPLEQ_REMOVE_HEAD(head, field) do { \ 656*85280f08SToomas Soome if ((SIMPLEQ_FIRST((head)) = \ 657*85280f08SToomas Soome SIMPLEQ_NEXT(SIMPLEQ_FIRST((head)), field)) == NULL) \ 658*85280f08SToomas Soome (head)->sqh_last = &SIMPLEQ_FIRST((head)); \ 659*85280f08SToomas Soome _NOTE(CONSTCOND) \ 660*85280f08SToomas Soome } while (0) 661*85280f08SToomas Soome 662*85280f08SToomas Soome #define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ 663*85280f08SToomas Soome if ((SIMPLEQ_NEXT((elm)) = \ 664*85280f08SToomas Soome SIMPLEQ_NEXT(SIMPLEQ_NEXT((elm), field), field)) == NULL) \ 665*85280f08SToomas Soome (head)->sqh_last = &SIMPLEQ_NEXT((elm), field); \ 666*85280f08SToomas Soome _NOTE(CONSTCOND) \ 667*85280f08SToomas Soome } while (0) 668*85280f08SToomas Soome 669*85280f08SToomas Soome #define SIMPLEQ_REMOVE(head, elm, type, field) do { \ 670*85280f08SToomas Soome if (SIMPLEQ_FIRST((head)) == (elm)) { \ 671*85280f08SToomas Soome SIMPLEQ_REMOVE_HEAD((head), field); \ 672*85280f08SToomas Soome } else { \ 673*85280f08SToomas Soome QUEUE_TYPEOF(type) *curelm = SIMPLEQ_FIRST((head)); \ 674*85280f08SToomas Soome while (SIMPLEQ_NEXT(curelm, field) != (elm)) \ 675*85280f08SToomas Soome curelm = SIMPLEQ_NEXT(curelm, field); \ 676*85280f08SToomas Soome SIMPLEQ_REMOVE_AFTER((head), curelm, field); \ 677*85280f08SToomas Soome } \ 678*85280f08SToomas Soome _NOTE(CONSTCOND) \ 679*85280f08SToomas Soome } while (0) 680*85280f08SToomas Soome 681*85280f08SToomas Soome #define SIMPLEQ_CONCAT(head1, head2) do { \ 682*85280f08SToomas Soome if (!SIMPLEQ_EMPTY((head2))) { \ 683*85280f08SToomas Soome *(head1)->sqh_last = (head2)->sqh_first; \ 684*85280f08SToomas Soome (head1)->sqh_last = (head2)->sqh_last; \ 685*85280f08SToomas Soome SIMPLEQ_INIT((head2)); \ 686*85280f08SToomas Soome } \ 687*85280f08SToomas Soome _NOTE(CONSTCOND) \ 688*85280f08SToomas Soome } while (0) 689*85280f08SToomas Soome 690*85280f08SToomas Soome #define SIMPLEQ_LAST(head, type, field) \ 691*85280f08SToomas Soome (SIMPLEQ_EMPTY((head)) ? \ 692*85280f08SToomas Soome NULL : \ 693*85280f08SToomas Soome ((QUEUE_TYPEOF(type) *)(void *) \ 694*85280f08SToomas Soome ((char *)((head)->sqh_last) - offsetof(QUEUE_TYPEOF(type), field)))) 695381a2a9aSdr146992 696381a2a9aSdr146992 /* 697381a2a9aSdr146992 * Tail queue definitions. 698381a2a9aSdr146992 */ 699*85280f08SToomas Soome #define TAILQ_HEAD(name, type) \ 700381a2a9aSdr146992 struct name { \ 701*85280f08SToomas Soome struct type *tqh_first; /* first element */ \ 702*85280f08SToomas Soome struct type **tqh_last; /* addr of last next element */ \ 703*85280f08SToomas Soome TRACEBUF \ 704381a2a9aSdr146992 } 705*85280f08SToomas Soome 706*85280f08SToomas Soome #define TAILQ_CLASS_HEAD(name, type) \ 707*85280f08SToomas Soome struct name { \ 708*85280f08SToomas Soome class type *tqh_first; /* first element */ \ 709*85280f08SToomas Soome class type **tqh_last; /* addr of last next element */ \ 710*85280f08SToomas Soome TRACEBUF \ 711*85280f08SToomas Soome } 712381a2a9aSdr146992 713381a2a9aSdr146992 #define TAILQ_HEAD_INITIALIZER(head) \ 714381a2a9aSdr146992 { NULL, &(head).tqh_first } 715381a2a9aSdr146992 716*85280f08SToomas Soome #define TAILQ_ENTRY(type) \ 717381a2a9aSdr146992 struct { \ 718*85280f08SToomas Soome struct type *tqe_next; /* next element */ \ 719*85280f08SToomas Soome struct type **tqe_prev; /* address of previous next element */ \ 720*85280f08SToomas Soome TRACEBUF \ 721381a2a9aSdr146992 } 722*85280f08SToomas Soome 723*85280f08SToomas Soome #define TAILQ_CLASS_ENTRY(type) \ 724*85280f08SToomas Soome struct { \ 725*85280f08SToomas Soome class type *tqe_next; /* next element */ \ 726*85280f08SToomas Soome class type **tqe_prev; /* address of previous next element */ \ 727*85280f08SToomas Soome TRACEBUF \ 728*85280f08SToomas Soome } 729*85280f08SToomas Soome 730*85280f08SToomas Soome /* 731*85280f08SToomas Soome * Tail queue access methods. 732*85280f08SToomas Soome */ 733*85280f08SToomas Soome #define TAILQ_FIRST(head) ((head)->tqh_first) 734*85280f08SToomas Soome #define TAILQ_END(head) NULL 735*85280f08SToomas Soome #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 736*85280f08SToomas Soome #define TAILQ_LAST(head, headname) \ 737*85280f08SToomas Soome (*(((struct headname *)((head)->tqh_last))->tqh_last)) 738*85280f08SToomas Soome #define TAILQ_PREV(elm, headname, field) \ 739*85280f08SToomas Soome (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 740*85280f08SToomas Soome #define TAILQ_EMPTY(head) ((head)->tqh_first == TAILQ_END(head)) 741*85280f08SToomas Soome 742*85280f08SToomas Soome 743*85280f08SToomas Soome #define TAILQ_FOREACH(var, head, field) \ 744*85280f08SToomas Soome for ((var) = TAILQ_FIRST((head)); \ 745*85280f08SToomas Soome (var) != TAILQ_END(head); \ 746*85280f08SToomas Soome (var) = TAILQ_NEXT((var), field)) 747*85280f08SToomas Soome 748*85280f08SToomas Soome #define TAILQ_FOREACH_FROM(var, head, field) \ 749*85280f08SToomas Soome for ((var) = ((var) != TAILQ_END((head)) ? \ 750*85280f08SToomas Soome (var) : TAILQ_FIRST((head))); \ 751*85280f08SToomas Soome (var) != TAILQ_END(head); \ 752*85280f08SToomas Soome (var) = TAILQ_NEXT((var), field)) 753*85280f08SToomas Soome 754*85280f08SToomas Soome #define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 755*85280f08SToomas Soome for ((var) = TAILQ_FIRST((head)); \ 756*85280f08SToomas Soome (var) != TAILQ_END(head) && \ 757*85280f08SToomas Soome ((tvar) = TAILQ_NEXT((var), field), 1); \ 758*85280f08SToomas Soome (var) = (tvar)) 759*85280f08SToomas Soome 760*85280f08SToomas Soome #define TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar) \ 761*85280f08SToomas Soome for ((var) = ((var) != TAILQ_END((head)) ? \ 762*85280f08SToomas Soome (var) : TAILQ_FIRST((head))); \ 763*85280f08SToomas Soome (var) != TAILQ_END(head) && \ 764*85280f08SToomas Soome ((tvar) = TAILQ_NEXT((var), field), 1); \ 765*85280f08SToomas Soome (var) = (tvar)) 766*85280f08SToomas Soome 767*85280f08SToomas Soome #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 768*85280f08SToomas Soome for ((var) = TAILQ_LAST((head), headname); \ 769*85280f08SToomas Soome (var) != TAILQ_END(head); \ 770*85280f08SToomas Soome (var) = TAILQ_PREV((var), headname, field)) 771*85280f08SToomas Soome 772*85280f08SToomas Soome #define TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field) \ 773*85280f08SToomas Soome for ((var) = ((var) != TAILQ_END((head)) ? \ 774*85280f08SToomas Soome (var) : TAILQ_LAST((head), headname)); \ 775*85280f08SToomas Soome (var) != TAILQ_END(head); \ 776*85280f08SToomas Soome (var) = TAILQ_PREV((var), headname, field)) 777*85280f08SToomas Soome 778*85280f08SToomas Soome #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 779*85280f08SToomas Soome for ((var) = TAILQ_LAST((head), headname); \ 780*85280f08SToomas Soome (var) != TAILQ_END(head) && \ 781*85280f08SToomas Soome ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 782*85280f08SToomas Soome (var) = (tvar)) 783*85280f08SToomas Soome 784*85280f08SToomas Soome #define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar)\ 785*85280f08SToomas Soome for ((var) = ((var) != TAILQ_END((head)) ? \ 786*85280f08SToomas Soome (var) : TAILQ_LAST((head), headname)); \ 787*85280f08SToomas Soome (var) != TAILQ_END(head) && \ 788*85280f08SToomas Soome ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 789*85280f08SToomas Soome (var) = (tvar)) 790381a2a9aSdr146992 791381a2a9aSdr146992 /* 792381a2a9aSdr146992 * Tail queue functions. 793381a2a9aSdr146992 */ 794381a2a9aSdr146992 #if defined(_KERNEL) && defined(QUEUEDEBUG) 795381a2a9aSdr146992 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) \ 796381a2a9aSdr146992 if ((head)->tqh_first && \ 797381a2a9aSdr146992 (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \ 798c1374a13SSurya Prakki panic("TAILQ_INSERT_HEAD %p %s:%d", (void *)(head), \ 799c1374a13SSurya Prakki __FILE__, __LINE__); 800381a2a9aSdr146992 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) \ 801381a2a9aSdr146992 if (*(head)->tqh_last != NULL) \ 802c1374a13SSurya Prakki panic("TAILQ_INSERT_TAIL %p %s:%d", (void *)(head), \ 803c1374a13SSurya Prakki __FILE__, __LINE__); 804381a2a9aSdr146992 #define QUEUEDEBUG_TAILQ_OP(elm, field) \ 805381a2a9aSdr146992 if ((elm)->field.tqe_next && \ 806381a2a9aSdr146992 (elm)->field.tqe_next->field.tqe_prev != \ 807381a2a9aSdr146992 &(elm)->field.tqe_next) \ 808c1374a13SSurya Prakki panic("TAILQ_* forw %p %s:%d", (void *)(elm), \ 809c1374a13SSurya Prakki __FILE__, __LINE__);\ 810381a2a9aSdr146992 if (*(elm)->field.tqe_prev != (elm)) \ 811c1374a13SSurya Prakki panic("TAILQ_* back %p %s:%d", (void *)(elm), \ 812c1374a13SSurya Prakki __FILE__, __LINE__); 813381a2a9aSdr146992 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) \ 814381a2a9aSdr146992 if ((elm)->field.tqe_next == NULL && \ 815381a2a9aSdr146992 (head)->tqh_last != &(elm)->field.tqe_next) \ 816381a2a9aSdr146992 panic("TAILQ_PREREMOVE head %p elm %p %s:%d", \ 817c1374a13SSurya Prakki (void *)(head), (void *)(elm), __FILE__, __LINE__); 818381a2a9aSdr146992 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) \ 819381a2a9aSdr146992 (elm)->field.tqe_next = (void *)1L; \ 820381a2a9aSdr146992 (elm)->field.tqe_prev = (void *)1L; 821381a2a9aSdr146992 #else 822381a2a9aSdr146992 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) 823381a2a9aSdr146992 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) 824381a2a9aSdr146992 #define QUEUEDEBUG_TAILQ_OP(elm, field) 825381a2a9aSdr146992 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) 826381a2a9aSdr146992 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) 827381a2a9aSdr146992 #endif 828381a2a9aSdr146992 829381a2a9aSdr146992 #define TAILQ_INIT(head) do { \ 830*85280f08SToomas Soome TAILQ_FIRST((head)) = TAILQ_END((head)); \ 831*85280f08SToomas Soome (head)->tqh_last = &TAILQ_FIRST((head)); \ 832381a2a9aSdr146992 _NOTE(CONSTCOND) \ 833381a2a9aSdr146992 } while (0) 834381a2a9aSdr146992 835381a2a9aSdr146992 #define TAILQ_INSERT_HEAD(head, elm, field) do { \ 836381a2a9aSdr146992 QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field) \ 837*85280f08SToomas Soome if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 838*85280f08SToomas Soome TAILQ_FIRST((head))->field.tqe_prev = \ 839*85280f08SToomas Soome &TAILQ_NEXT((elm), field); \ 840381a2a9aSdr146992 else \ 841*85280f08SToomas Soome (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 842*85280f08SToomas Soome TAILQ_FIRST((head)) = (elm); \ 843*85280f08SToomas Soome (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 844381a2a9aSdr146992 _NOTE(CONSTCOND) \ 845381a2a9aSdr146992 } while (0) 846381a2a9aSdr146992 847381a2a9aSdr146992 #define TAILQ_INSERT_TAIL(head, elm, field) do { \ 848381a2a9aSdr146992 QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field) \ 849*85280f08SToomas Soome TAILQ_NEXT((elm), field) = NULL; \ 850381a2a9aSdr146992 (elm)->field.tqe_prev = (head)->tqh_last; \ 851381a2a9aSdr146992 *(head)->tqh_last = (elm); \ 852*85280f08SToomas Soome (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 853381a2a9aSdr146992 _NOTE(CONSTCOND) \ 854381a2a9aSdr146992 } while (0) 855381a2a9aSdr146992 856381a2a9aSdr146992 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 857381a2a9aSdr146992 QUEUEDEBUG_TAILQ_OP((listelm), field) \ 858*85280f08SToomas Soome if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 859*85280f08SToomas Soome TAILQ_NEXT((elm), field)->field.tqe_prev = \ 860*85280f08SToomas Soome &TAILQ_NEXT((elm), field); \ 861381a2a9aSdr146992 else \ 862*85280f08SToomas Soome (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 863*85280f08SToomas Soome TAILQ_NEXT((listelm), field) = (elm); \ 864*85280f08SToomas Soome (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 865381a2a9aSdr146992 _NOTE(CONSTCOND) \ 866381a2a9aSdr146992 } while (0) 867381a2a9aSdr146992 868381a2a9aSdr146992 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 869381a2a9aSdr146992 QUEUEDEBUG_TAILQ_OP((listelm), field) \ 870381a2a9aSdr146992 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 871*85280f08SToomas Soome TAILQ_NEXT((elm), field) = (listelm); \ 872381a2a9aSdr146992 *(listelm)->field.tqe_prev = (elm); \ 873*85280f08SToomas Soome (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 874381a2a9aSdr146992 _NOTE(CONSTCOND) \ 875381a2a9aSdr146992 } while (0) 876381a2a9aSdr146992 877381a2a9aSdr146992 #define TAILQ_REMOVE(head, elm, field) do { \ 878381a2a9aSdr146992 QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field) \ 879381a2a9aSdr146992 QUEUEDEBUG_TAILQ_OP((elm), field) \ 880*85280f08SToomas Soome if ((TAILQ_NEXT((elm), field)) != NULL) \ 881*85280f08SToomas Soome TAILQ_NEXT((elm), field)->field.tqe_prev = \ 882381a2a9aSdr146992 (elm)->field.tqe_prev; \ 883381a2a9aSdr146992 else \ 884381a2a9aSdr146992 (head)->tqh_last = (elm)->field.tqe_prev; \ 885*85280f08SToomas Soome *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 886381a2a9aSdr146992 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \ 887381a2a9aSdr146992 _NOTE(CONSTCOND) \ 888381a2a9aSdr146992 } while (0) 889381a2a9aSdr146992 890*85280f08SToomas Soome #define TAILQ_SWAP(head1, head2, type, field) do { \ 891*85280f08SToomas Soome QUEUE_TYPEOF(type) *swap_first = TAILQ_FIRST((head1)); \ 892*85280f08SToomas Soome QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last; \ 893*85280f08SToomas Soome TAILQ_FIRST((head1)) = TAILQ_FIRST((head2)); \ 894*85280f08SToomas Soome (head1)->tqh_last = (head2)->tqh_last; \ 895*85280f08SToomas Soome TAILQ_FIRST((head2)) = swap_first; \ 896*85280f08SToomas Soome (head2)->tqh_last = swap_last; \ 897*85280f08SToomas Soome if ((swap_first = TAILQ_FIRST((head1))) != NULL) \ 898*85280f08SToomas Soome swap_first->field.tqe_prev = &TAILQ_FIRST((head1)); \ 899*85280f08SToomas Soome else \ 900*85280f08SToomas Soome (head1)->tqh_last = &TAILQ_FIRST((head1)); \ 901*85280f08SToomas Soome if ((swap_first = TAILQ_FIRST((head2))) != NULL) \ 902*85280f08SToomas Soome swap_first->field.tqe_prev = &TAILQ_FIRST((head2)); \ 903*85280f08SToomas Soome else \ 904*85280f08SToomas Soome (head2)->tqh_last = &TAILQ_FIRST((head2)); \ 905*85280f08SToomas Soome _NOTE(CONSTCOND) \ 906*85280f08SToomas Soome } while (0) 907381a2a9aSdr146992 908381a2a9aSdr146992 /* 909*85280f08SToomas Soome * Circular queue definitions. Do not use. We still keep the macros 910*85280f08SToomas Soome * for compatibility but because of pointer aliasing issues their use 911*85280f08SToomas Soome * is discouraged! 912381a2a9aSdr146992 */ 913381a2a9aSdr146992 #define CIRCLEQ_HEAD(name, type) \ 914381a2a9aSdr146992 struct name { \ 915381a2a9aSdr146992 struct type *cqh_first; /* first element */ \ 916381a2a9aSdr146992 struct type *cqh_last; /* last element */ \ 917381a2a9aSdr146992 } 918381a2a9aSdr146992 919381a2a9aSdr146992 #define CIRCLEQ_HEAD_INITIALIZER(head) \ 920381a2a9aSdr146992 { (void *)&head, (void *)&head } 921381a2a9aSdr146992 922381a2a9aSdr146992 #define CIRCLEQ_ENTRY(type) \ 923381a2a9aSdr146992 struct { \ 924381a2a9aSdr146992 struct type *cqe_next; /* next element */ \ 925381a2a9aSdr146992 struct type *cqe_prev; /* previous element */ \ 926381a2a9aSdr146992 } 927381a2a9aSdr146992 928381a2a9aSdr146992 /* 929*85280f08SToomas Soome * Circular queue access methods. 930*85280f08SToomas Soome */ 931*85280f08SToomas Soome #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head)) 932*85280f08SToomas Soome #define CIRCLEQ_FIRST(head) ((head)->cqh_first) 933*85280f08SToomas Soome #define CIRCLEQ_LAST(head) ((head)->cqh_last) 934*85280f08SToomas Soome #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) 935*85280f08SToomas Soome #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) 936*85280f08SToomas Soome 937*85280f08SToomas Soome #define CIRCLEQ_LOOP_NEXT(head, elm, field) \ 938*85280f08SToomas Soome (((elm)->field.cqe_next == (void *)(head)) \ 939*85280f08SToomas Soome ? ((head)->cqh_first) \ 940*85280f08SToomas Soome : (elm->field.cqe_next)) 941*85280f08SToomas Soome #define CIRCLEQ_LOOP_PREV(head, elm, field) \ 942*85280f08SToomas Soome (((elm)->field.cqe_prev == (void *)(head)) \ 943*85280f08SToomas Soome ? ((head)->cqh_last) \ 944*85280f08SToomas Soome : (elm->field.cqe_prev)) 945*85280f08SToomas Soome 946*85280f08SToomas Soome #define CIRCLEQ_FOREACH(var, head, field) \ 947*85280f08SToomas Soome for ((var) = CIRCLEQ_FIRST((head)); \ 948*85280f08SToomas Soome (var) != (void *)(head); \ 949*85280f08SToomas Soome (var) = CIRCLEQ_NEXT((var), field)) 950*85280f08SToomas Soome 951*85280f08SToomas Soome #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ 952*85280f08SToomas Soome for ((var) = CIRCLEQ_LAST((head)); \ 953*85280f08SToomas Soome (var) != (void *)(head); \ 954*85280f08SToomas Soome (var) = CIRCLEQ_PREV((var), field)) 955*85280f08SToomas Soome 956*85280f08SToomas Soome /* 957381a2a9aSdr146992 * Circular queue functions. 958381a2a9aSdr146992 */ 959381a2a9aSdr146992 #define CIRCLEQ_INIT(head) do { \ 960381a2a9aSdr146992 (head)->cqh_first = (void *)(head); \ 961381a2a9aSdr146992 (head)->cqh_last = (void *)(head); \ 962381a2a9aSdr146992 _NOTE(CONSTCOND) \ 963381a2a9aSdr146992 } while (0) 964381a2a9aSdr146992 965381a2a9aSdr146992 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 966381a2a9aSdr146992 (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 967381a2a9aSdr146992 (elm)->field.cqe_prev = (listelm); \ 968381a2a9aSdr146992 if ((listelm)->field.cqe_next == (void *)(head)) \ 969381a2a9aSdr146992 (head)->cqh_last = (elm); \ 970381a2a9aSdr146992 else \ 971381a2a9aSdr146992 (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 972381a2a9aSdr146992 (listelm)->field.cqe_next = (elm); \ 973381a2a9aSdr146992 _NOTE(CONSTCOND) \ 974381a2a9aSdr146992 } while (0) 975381a2a9aSdr146992 976381a2a9aSdr146992 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ 977381a2a9aSdr146992 (elm)->field.cqe_next = (listelm); \ 978381a2a9aSdr146992 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 979381a2a9aSdr146992 if ((listelm)->field.cqe_prev == (void *)(head)) \ 980381a2a9aSdr146992 (head)->cqh_first = (elm); \ 981381a2a9aSdr146992 else \ 982381a2a9aSdr146992 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 983381a2a9aSdr146992 (listelm)->field.cqe_prev = (elm); \ 984381a2a9aSdr146992 _NOTE(CONSTCOND) \ 985381a2a9aSdr146992 } while (0) 986381a2a9aSdr146992 987381a2a9aSdr146992 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ 988381a2a9aSdr146992 (elm)->field.cqe_next = (head)->cqh_first; \ 989381a2a9aSdr146992 (elm)->field.cqe_prev = (void *)(head); \ 990381a2a9aSdr146992 if ((head)->cqh_last == (void *)(head)) \ 991381a2a9aSdr146992 (head)->cqh_last = (elm); \ 992381a2a9aSdr146992 else \ 993381a2a9aSdr146992 (head)->cqh_first->field.cqe_prev = (elm); \ 994381a2a9aSdr146992 (head)->cqh_first = (elm); \ 995381a2a9aSdr146992 _NOTE(CONSTCOND) \ 996381a2a9aSdr146992 } while (0) 997381a2a9aSdr146992 998381a2a9aSdr146992 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ 999381a2a9aSdr146992 (elm)->field.cqe_next = (void *)(head); \ 1000381a2a9aSdr146992 (elm)->field.cqe_prev = (head)->cqh_last; \ 1001381a2a9aSdr146992 if ((head)->cqh_first == (void *)(head)) \ 1002381a2a9aSdr146992 (head)->cqh_first = (elm); \ 1003381a2a9aSdr146992 else \ 1004381a2a9aSdr146992 (head)->cqh_last->field.cqe_next = (elm); \ 1005381a2a9aSdr146992 (head)->cqh_last = (elm); \ 1006381a2a9aSdr146992 _NOTE(CONSTCOND) \ 1007381a2a9aSdr146992 } while (0) 1008381a2a9aSdr146992 1009381a2a9aSdr146992 #define CIRCLEQ_REMOVE(head, elm, field) do { \ 1010381a2a9aSdr146992 if ((elm)->field.cqe_next == (void *)(head)) \ 1011381a2a9aSdr146992 (head)->cqh_last = (elm)->field.cqe_prev; \ 1012381a2a9aSdr146992 else \ 1013381a2a9aSdr146992 (elm)->field.cqe_next->field.cqe_prev = \ 1014381a2a9aSdr146992 (elm)->field.cqe_prev; \ 1015381a2a9aSdr146992 if ((elm)->field.cqe_prev == (void *)(head)) \ 1016381a2a9aSdr146992 (head)->cqh_first = (elm)->field.cqe_next; \ 1017381a2a9aSdr146992 else \ 1018381a2a9aSdr146992 (elm)->field.cqe_prev->field.cqe_next = \ 1019381a2a9aSdr146992 (elm)->field.cqe_next; \ 1020381a2a9aSdr146992 _NOTE(CONSTCOND) \ 1021381a2a9aSdr146992 } while (0) 1022381a2a9aSdr146992 1023381a2a9aSdr146992 #ifdef __cplusplus 1024381a2a9aSdr146992 } 1025381a2a9aSdr146992 #endif 1026381a2a9aSdr146992 1027381a2a9aSdr146992 #endif /* !_SYS_QUEUE_H */ 1028