1*0Sstevel@tonic-gate /* BSDI $Id: queue.h,v 2.4 1996/07/02 13:22:11 bostic Exp $ */ 2*0Sstevel@tonic-gate 3*0Sstevel@tonic-gate /* 4*0Sstevel@tonic-gate * Copyright (c) 1991, 1993 5*0Sstevel@tonic-gate * The Regents of the University of California. All rights reserved. 6*0Sstevel@tonic-gate * 7*0Sstevel@tonic-gate * Redistribution and use in source and binary forms, with or without 8*0Sstevel@tonic-gate * modification, are permitted provided that the following conditions 9*0Sstevel@tonic-gate * are met: 10*0Sstevel@tonic-gate * 1. Redistributions of source code must retain the above copyright 11*0Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer. 12*0Sstevel@tonic-gate * 2. Redistributions in binary form must reproduce the above copyright 13*0Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer in the 14*0Sstevel@tonic-gate * documentation and/or other materials provided with the distribution. 15*0Sstevel@tonic-gate * 3. All advertising materials mentioning features or use of this software 16*0Sstevel@tonic-gate * must display the following acknowledgement: 17*0Sstevel@tonic-gate * This product includes software developed by the University of 18*0Sstevel@tonic-gate * California, Berkeley and its contributors. 19*0Sstevel@tonic-gate * 4. Neither the name of the University nor the names of its contributors 20*0Sstevel@tonic-gate * may be used to endorse or promote products derived from this software 21*0Sstevel@tonic-gate * without specific prior written permission. 22*0Sstevel@tonic-gate * 23*0Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24*0Sstevel@tonic-gate * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25*0Sstevel@tonic-gate * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26*0Sstevel@tonic-gate * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27*0Sstevel@tonic-gate * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28*0Sstevel@tonic-gate * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29*0Sstevel@tonic-gate * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30*0Sstevel@tonic-gate * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31*0Sstevel@tonic-gate * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32*0Sstevel@tonic-gate * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33*0Sstevel@tonic-gate * SUCH DAMAGE. 34*0Sstevel@tonic-gate * 35*0Sstevel@tonic-gate * @(#)queue.h 8.5 (Berkeley) 8/20/94 36*0Sstevel@tonic-gate * %W% (Sun) %G% 37*0Sstevel@tonic-gate */ 38*0Sstevel@tonic-gate /* 39*0Sstevel@tonic-gate * Copyright (c) 1998 by Sun Microsystems, Inc. 40*0Sstevel@tonic-gate * All rights reserved. 41*0Sstevel@tonic-gate */ 42*0Sstevel@tonic-gate 43*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 44*0Sstevel@tonic-gate 45*0Sstevel@tonic-gate #ifndef _SYS_QUEUE_H_ 46*0Sstevel@tonic-gate #define _SYS_QUEUE_H_ 47*0Sstevel@tonic-gate 48*0Sstevel@tonic-gate /* 49*0Sstevel@tonic-gate * This file defines three types of data structures: lists, tail queues, 50*0Sstevel@tonic-gate * and circular queues. 51*0Sstevel@tonic-gate * 52*0Sstevel@tonic-gate * A list is headed by a single forward pointer (or an array of forward 53*0Sstevel@tonic-gate * pointers for a hash table header). The elements are doubly linked 54*0Sstevel@tonic-gate * so that an arbitrary element can be removed without a need to 55*0Sstevel@tonic-gate * traverse the list. New elements can be added to the list before 56*0Sstevel@tonic-gate * or after an existing element or at the head of the list. A list 57*0Sstevel@tonic-gate * may only be traversed in the forward direction. 58*0Sstevel@tonic-gate * 59*0Sstevel@tonic-gate * A tail queue is headed by a pair of pointers, one to the head of the 60*0Sstevel@tonic-gate * list and the other to the tail of the list. The elements are doubly 61*0Sstevel@tonic-gate * linked so that an arbitrary element can be removed without a need to 62*0Sstevel@tonic-gate * traverse the list. New elements can be added to the list before or 63*0Sstevel@tonic-gate * after an existing element, at the head of the list, or at the end of 64*0Sstevel@tonic-gate * the list. A tail queue may only be traversed in the forward direction. 65*0Sstevel@tonic-gate * 66*0Sstevel@tonic-gate * A circle queue is headed by a pair of pointers, one to the head of the 67*0Sstevel@tonic-gate * list and the other to the tail of the list. The elements are doubly 68*0Sstevel@tonic-gate * linked so that an arbitrary element can be removed without a need to 69*0Sstevel@tonic-gate * traverse the list. New elements can be added to the list before or after 70*0Sstevel@tonic-gate * an existing element, at the head of the list, or at the end of the list. 71*0Sstevel@tonic-gate * A circle queue may be traversed in either direction, but has a more 72*0Sstevel@tonic-gate * complex end of list detection. 73*0Sstevel@tonic-gate * 74*0Sstevel@tonic-gate * For details on the use of these macros, see the queue(3) manual page. 75*0Sstevel@tonic-gate */ 76*0Sstevel@tonic-gate 77*0Sstevel@tonic-gate /* 78*0Sstevel@tonic-gate * List definitions. 79*0Sstevel@tonic-gate */ 80*0Sstevel@tonic-gate #define LIST_HEAD(name, type) \ 81*0Sstevel@tonic-gate struct name { \ 82*0Sstevel@tonic-gate struct type *lh_first; /* first element */ \ 83*0Sstevel@tonic-gate } 84*0Sstevel@tonic-gate 85*0Sstevel@tonic-gate #define LIST_ENTRY(type) \ 86*0Sstevel@tonic-gate struct { \ 87*0Sstevel@tonic-gate struct type *le_next; /* next element */ \ 88*0Sstevel@tonic-gate struct type **le_prev; /* address of previous next element */ \ 89*0Sstevel@tonic-gate } 90*0Sstevel@tonic-gate 91*0Sstevel@tonic-gate #define LIST_FIRST(head) ((head)->lh_first) 92*0Sstevel@tonic-gate #define LIST_NEXT(elm, field) ((elm)->field.le_next) 93*0Sstevel@tonic-gate #define LIST_END(head) NULL 94*0Sstevel@tonic-gate 95*0Sstevel@tonic-gate /* 96*0Sstevel@tonic-gate * List functions. 97*0Sstevel@tonic-gate */ 98*0Sstevel@tonic-gate #define LIST_INIT(head) { \ 99*0Sstevel@tonic-gate (head)->lh_first = NULL; \ 100*0Sstevel@tonic-gate } 101*0Sstevel@tonic-gate 102*0Sstevel@tonic-gate #define LIST_INSERT_AFTER(listelm, elm, field) do { \ 103*0Sstevel@tonic-gate if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 104*0Sstevel@tonic-gate (listelm)->field.le_next->field.le_prev = \ 105*0Sstevel@tonic-gate &(elm)->field.le_next; \ 106*0Sstevel@tonic-gate (listelm)->field.le_next = (elm); \ 107*0Sstevel@tonic-gate (elm)->field.le_prev = &(listelm)->field.le_next; \ 108*0Sstevel@tonic-gate } while (0) 109*0Sstevel@tonic-gate 110*0Sstevel@tonic-gate #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 111*0Sstevel@tonic-gate (elm)->field.le_prev = (listelm)->field.le_prev; \ 112*0Sstevel@tonic-gate (elm)->field.le_next = (listelm); \ 113*0Sstevel@tonic-gate *(listelm)->field.le_prev = (elm); \ 114*0Sstevel@tonic-gate (listelm)->field.le_prev = &(elm)->field.le_next; \ 115*0Sstevel@tonic-gate } while (0) 116*0Sstevel@tonic-gate 117*0Sstevel@tonic-gate #define LIST_INSERT_HEAD(head, elm, field) do { \ 118*0Sstevel@tonic-gate if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 119*0Sstevel@tonic-gate (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 120*0Sstevel@tonic-gate (head)->lh_first = (elm); \ 121*0Sstevel@tonic-gate (elm)->field.le_prev = &(head)->lh_first; \ 122*0Sstevel@tonic-gate } while (0) 123*0Sstevel@tonic-gate 124*0Sstevel@tonic-gate #define LIST_REMOVE(elm, field) do { \ 125*0Sstevel@tonic-gate if ((elm)->field.le_next != NULL) \ 126*0Sstevel@tonic-gate (elm)->field.le_next->field.le_prev = \ 127*0Sstevel@tonic-gate (elm)->field.le_prev; \ 128*0Sstevel@tonic-gate *(elm)->field.le_prev = (elm)->field.le_next; \ 129*0Sstevel@tonic-gate } while (0) 130*0Sstevel@tonic-gate 131*0Sstevel@tonic-gate /* 132*0Sstevel@tonic-gate * Tail queue definitions. 133*0Sstevel@tonic-gate */ 134*0Sstevel@tonic-gate #define TAILQ_HEAD(name, type) \ 135*0Sstevel@tonic-gate struct name { \ 136*0Sstevel@tonic-gate struct type *tqh_first; /* first element */ \ 137*0Sstevel@tonic-gate struct type **tqh_last; /* addr of last next element */ \ 138*0Sstevel@tonic-gate } 139*0Sstevel@tonic-gate 140*0Sstevel@tonic-gate #define TAILQ_ENTRY(type) \ 141*0Sstevel@tonic-gate struct { \ 142*0Sstevel@tonic-gate struct type *tqe_next; /* next element */ \ 143*0Sstevel@tonic-gate struct type **tqe_prev; /* address of previous next element */ \ 144*0Sstevel@tonic-gate } 145*0Sstevel@tonic-gate 146*0Sstevel@tonic-gate #define TAILQ_FIRST(head) ((head)->tqh_first) 147*0Sstevel@tonic-gate #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 148*0Sstevel@tonic-gate #define TAILQ_END(head) NULL 149*0Sstevel@tonic-gate 150*0Sstevel@tonic-gate /* 151*0Sstevel@tonic-gate * Tail queue functions. 152*0Sstevel@tonic-gate */ 153*0Sstevel@tonic-gate #define TAILQ_INIT(head) do { \ 154*0Sstevel@tonic-gate (head)->tqh_first = NULL; \ 155*0Sstevel@tonic-gate (head)->tqh_last = &(head)->tqh_first; \ 156*0Sstevel@tonic-gate } while (0) 157*0Sstevel@tonic-gate 158*0Sstevel@tonic-gate #define TAILQ_INSERT_HEAD(head, elm, field) do { \ 159*0Sstevel@tonic-gate if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 160*0Sstevel@tonic-gate (head)->tqh_first->field.tqe_prev = \ 161*0Sstevel@tonic-gate &(elm)->field.tqe_next; \ 162*0Sstevel@tonic-gate else \ 163*0Sstevel@tonic-gate (head)->tqh_last = &(elm)->field.tqe_next; \ 164*0Sstevel@tonic-gate (head)->tqh_first = (elm); \ 165*0Sstevel@tonic-gate (elm)->field.tqe_prev = &(head)->tqh_first; \ 166*0Sstevel@tonic-gate } while (0) 167*0Sstevel@tonic-gate 168*0Sstevel@tonic-gate #define TAILQ_INSERT_TAIL(head, elm, field) do { \ 169*0Sstevel@tonic-gate (elm)->field.tqe_next = NULL; \ 170*0Sstevel@tonic-gate (elm)->field.tqe_prev = (head)->tqh_last; \ 171*0Sstevel@tonic-gate *(head)->tqh_last = (elm); \ 172*0Sstevel@tonic-gate (head)->tqh_last = &(elm)->field.tqe_next; \ 173*0Sstevel@tonic-gate } while (0) 174*0Sstevel@tonic-gate 175*0Sstevel@tonic-gate #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 176*0Sstevel@tonic-gate if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 177*0Sstevel@tonic-gate (elm)->field.tqe_next->field.tqe_prev = \ 178*0Sstevel@tonic-gate &(elm)->field.tqe_next; \ 179*0Sstevel@tonic-gate else \ 180*0Sstevel@tonic-gate (head)->tqh_last = &(elm)->field.tqe_next; \ 181*0Sstevel@tonic-gate (listelm)->field.tqe_next = (elm); \ 182*0Sstevel@tonic-gate (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 183*0Sstevel@tonic-gate } while (0) 184*0Sstevel@tonic-gate 185*0Sstevel@tonic-gate #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 186*0Sstevel@tonic-gate (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 187*0Sstevel@tonic-gate (elm)->field.tqe_next = (listelm); \ 188*0Sstevel@tonic-gate *(listelm)->field.tqe_prev = (elm); \ 189*0Sstevel@tonic-gate (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 190*0Sstevel@tonic-gate } while (0) 191*0Sstevel@tonic-gate 192*0Sstevel@tonic-gate #define TAILQ_REMOVE(head, elm, field) do { \ 193*0Sstevel@tonic-gate if (((elm)->field.tqe_next) != NULL) \ 194*0Sstevel@tonic-gate (elm)->field.tqe_next->field.tqe_prev = \ 195*0Sstevel@tonic-gate (elm)->field.tqe_prev; \ 196*0Sstevel@tonic-gate else \ 197*0Sstevel@tonic-gate (head)->tqh_last = (elm)->field.tqe_prev; \ 198*0Sstevel@tonic-gate *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 199*0Sstevel@tonic-gate } while (0) 200*0Sstevel@tonic-gate 201*0Sstevel@tonic-gate /* 202*0Sstevel@tonic-gate * Circular queue definitions. 203*0Sstevel@tonic-gate */ 204*0Sstevel@tonic-gate #define CIRCLEQ_HEAD(name, type) \ 205*0Sstevel@tonic-gate struct name { \ 206*0Sstevel@tonic-gate struct type *cqh_first; /* first element */ \ 207*0Sstevel@tonic-gate struct type *cqh_last; /* last element */ \ 208*0Sstevel@tonic-gate } 209*0Sstevel@tonic-gate 210*0Sstevel@tonic-gate #define CIRCLEQ_ENTRY(type) \ 211*0Sstevel@tonic-gate struct { \ 212*0Sstevel@tonic-gate struct type *cqe_next; /* next element */ \ 213*0Sstevel@tonic-gate struct type *cqe_prev; /* previous element */ \ 214*0Sstevel@tonic-gate } 215*0Sstevel@tonic-gate 216*0Sstevel@tonic-gate #define CIRCLEQ_FIRST(head) ((head)->cqh_first) 217*0Sstevel@tonic-gate #define CIRCLEQ_LAST(head) ((head)->cqh_last) 218*0Sstevel@tonic-gate #define CIRCLEQ_END(head) ((void *)(head)) 219*0Sstevel@tonic-gate #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) 220*0Sstevel@tonic-gate #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) 221*0Sstevel@tonic-gate 222*0Sstevel@tonic-gate /* 223*0Sstevel@tonic-gate * Circular queue functions. 224*0Sstevel@tonic-gate */ 225*0Sstevel@tonic-gate #define CIRCLEQ_INIT(head) do { \ 226*0Sstevel@tonic-gate (head)->cqh_first = (void *)(head); \ 227*0Sstevel@tonic-gate (head)->cqh_last = (void *)(head); \ 228*0Sstevel@tonic-gate } while (0) 229*0Sstevel@tonic-gate 230*0Sstevel@tonic-gate #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 231*0Sstevel@tonic-gate (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 232*0Sstevel@tonic-gate (elm)->field.cqe_prev = (listelm); \ 233*0Sstevel@tonic-gate if ((listelm)->field.cqe_next == (void *)(head)) \ 234*0Sstevel@tonic-gate (head)->cqh_last = (elm); \ 235*0Sstevel@tonic-gate else \ 236*0Sstevel@tonic-gate (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 237*0Sstevel@tonic-gate (listelm)->field.cqe_next = (elm); \ 238*0Sstevel@tonic-gate } while (0) 239*0Sstevel@tonic-gate 240*0Sstevel@tonic-gate #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ 241*0Sstevel@tonic-gate (elm)->field.cqe_next = (listelm); \ 242*0Sstevel@tonic-gate (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 243*0Sstevel@tonic-gate if ((listelm)->field.cqe_prev == (void *)(head)) \ 244*0Sstevel@tonic-gate (head)->cqh_first = (elm); \ 245*0Sstevel@tonic-gate else \ 246*0Sstevel@tonic-gate (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 247*0Sstevel@tonic-gate (listelm)->field.cqe_prev = (elm); \ 248*0Sstevel@tonic-gate } while (0) 249*0Sstevel@tonic-gate 250*0Sstevel@tonic-gate #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ 251*0Sstevel@tonic-gate (elm)->field.cqe_next = (head)->cqh_first; \ 252*0Sstevel@tonic-gate (elm)->field.cqe_prev = (void *)(head); \ 253*0Sstevel@tonic-gate if ((head)->cqh_last == (void *)(head)) \ 254*0Sstevel@tonic-gate (head)->cqh_last = (elm); \ 255*0Sstevel@tonic-gate else \ 256*0Sstevel@tonic-gate (head)->cqh_first->field.cqe_prev = (elm); \ 257*0Sstevel@tonic-gate (head)->cqh_first = (elm); \ 258*0Sstevel@tonic-gate } while (0) 259*0Sstevel@tonic-gate 260*0Sstevel@tonic-gate #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ 261*0Sstevel@tonic-gate (elm)->field.cqe_next = (void *)(head); \ 262*0Sstevel@tonic-gate (elm)->field.cqe_prev = (head)->cqh_last; \ 263*0Sstevel@tonic-gate if ((head)->cqh_first == (void *)(head)) \ 264*0Sstevel@tonic-gate (head)->cqh_first = (elm); \ 265*0Sstevel@tonic-gate else \ 266*0Sstevel@tonic-gate (head)->cqh_last->field.cqe_next = (elm); \ 267*0Sstevel@tonic-gate (head)->cqh_last = (elm); \ 268*0Sstevel@tonic-gate } while (0) 269*0Sstevel@tonic-gate 270*0Sstevel@tonic-gate #define CIRCLEQ_REMOVE(head, elm, field) do { \ 271*0Sstevel@tonic-gate if ((elm)->field.cqe_next == (void *)(head)) \ 272*0Sstevel@tonic-gate (head)->cqh_last = (elm)->field.cqe_prev; \ 273*0Sstevel@tonic-gate else \ 274*0Sstevel@tonic-gate (elm)->field.cqe_next->field.cqe_prev = \ 275*0Sstevel@tonic-gate (elm)->field.cqe_prev; \ 276*0Sstevel@tonic-gate if ((elm)->field.cqe_prev == (void *)(head)) \ 277*0Sstevel@tonic-gate (head)->cqh_first = (elm)->field.cqe_next; \ 278*0Sstevel@tonic-gate else \ 279*0Sstevel@tonic-gate (elm)->field.cqe_prev->field.cqe_next = \ 280*0Sstevel@tonic-gate (elm)->field.cqe_next; \ 281*0Sstevel@tonic-gate } while (0) 282*0Sstevel@tonic-gate #endif /* !_SYS_QUEUE_H_ */ 283