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