1/* $NetBSD: queue.h,v 1.4 2006/09/09 16:22:09 manu 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 * 4. Neither the name of the University nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 * 31 * @(#)queue.h 8.5 (Berkeley) 8/20/94 32 * $FreeBSD: src/sys/sys/queue.h,v 1.58 2004/04/07 04:19:49 imp Exp $ 33 * 34 * 04/24/2004 Backport to v1.45 functionality for ipsec-tools 35 * Heiko Hund <heiko@ist.eigentlich.net> 36 */ 37 38#ifndef _SYS_QUEUE_H_ 39#define _SYS_QUEUE_H_ 40 41//#include <sys/cdefs.h> 42 43/* 44 * This file defines four types of data structures: singly-linked lists, 45 * singly-linked tail queues, lists and tail queues. 46 * 47 * A singly-linked list is headed by a single forward pointer. The elements 48 * are singly linked for minimum space and pointer manipulation overhead at 49 * the expense of O(n) removal for arbitrary elements. New elements can be 50 * added to the list after an existing element or at the head of the list. 51 * Elements being removed from the head of the list should use the explicit 52 * macro for this purpose for optimum efficiency. A singly-linked list may 53 * only be traversed in the forward direction. Singly-linked lists are ideal 54 * for applications with large datasets and few or no removals or for 55 * implementing a LIFO queue. 56 * 57 * A singly-linked tail queue is headed by a pair of pointers, one to the 58 * head of the list and the other to the tail of the list. The elements are 59 * singly linked for minimum space and pointer manipulation overhead at the 60 * expense of O(n) removal for arbitrary elements. New elements can be added 61 * to the list after an existing element, at the head of the list, or at the 62 * end of the list. Elements being removed from the head of the tail queue 63 * should use the explicit macro for this purpose for optimum efficiency. 64 * A singly-linked tail queue may only be traversed in the forward direction. 65 * Singly-linked tail queues are ideal for applications with large datasets 66 * and few or no removals or for implementing a FIFO queue. 67 * 68 * A list is headed by a single forward pointer (or an array of forward 69 * pointers for a hash table header). The elements are doubly linked 70 * so that an arbitrary element can be removed without a need to 71 * traverse the list. New elements can be added to the list before 72 * or after an existing element or at the head of the list. A list 73 * may only be traversed in the forward direction. 74 * 75 * A tail queue is headed by a pair of pointers, one to the head of the 76 * list and the other to the tail of the list. The elements are doubly 77 * linked so that an arbitrary element can be removed without a need to 78 * traverse the list. New elements can be added to the list before or 79 * after an existing element, at the head of the list, or at the end of 80 * the list. A tail queue may be traversed in either direction. 81 * 82 * For details on the use of these macros, see the queue(3) manual page. 83 * 84 * 85 * SLIST LIST STAILQ TAILQ 86 * _HEAD + + + + 87 * _HEAD_INITIALIZER + + + + 88 * _ENTRY + + + + 89 * _INIT + + + + 90 * _EMPTY + + + + 91 * _FIRST + + + + 92 * _NEXT + + + + 93 * _PREV - - - + 94 * _LAST - - + + 95 * _FOREACH + + + + 96 * _FOREACH_REVERSE - - - + 97 * _INSERT_HEAD + + + + 98 * _INSERT_BEFORE - + - + 99 * _INSERT_AFTER + + + + 100 * _INSERT_TAIL - - + + 101 * _REMOVE_HEAD + - + - 102 * _REMOVE + + + + 103 * 104 */ 105 106/* 107 * Singly-linked List declarations. 108 */ 109#define SLIST_HEAD(name, type) \ 110struct name { \ 111 struct type *slh_first; /* first element */ \ 112} 113 114#define SLIST_HEAD_INITIALIZER(head) \ 115 { NULL } 116 117#define SLIST_ENTRY(type) \ 118struct { \ 119 struct type *sle_next; /* next element */ \ 120} 121 122/* 123 * Singly-linked List functions. 124 */ 125#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 126 127#define SLIST_FIRST(head) ((head)->slh_first) 128 129#define SLIST_FOREACH(var, head, field) \ 130 for ((var) = SLIST_FIRST((head)); \ 131 (var); \ 132 (var) = SLIST_NEXT((var), field)) 133 134#define SLIST_INIT(head) do { \ 135 SLIST_FIRST((head)) = NULL; \ 136} while (0) 137 138#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 139 SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 140 SLIST_NEXT((slistelm), field) = (elm); \ 141} while (0) 142 143#define SLIST_INSERT_HEAD(head, elm, field) do { \ 144 SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 145 SLIST_FIRST((head)) = (elm); \ 146} while (0) 147 148#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 149 150#define SLIST_REMOVE(head, elm, type, field) do { \ 151 if (SLIST_FIRST((head)) == (elm)) { \ 152 SLIST_REMOVE_HEAD((head), field); \ 153 } \ 154 else { \ 155 struct type *curelm = SLIST_FIRST((head)); \ 156 while (SLIST_NEXT(curelm, field) != (elm)) \ 157 curelm = SLIST_NEXT(curelm, field); \ 158 SLIST_NEXT(curelm, field) = \ 159 SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ 160 } \ 161} while (0) 162 163#define SLIST_REMOVE_HEAD(head, field) do { \ 164 SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 165} while (0) 166 167/* 168 * Singly-linked Tail queue declarations. 169 */ 170#define STAILQ_HEAD(name, type) \ 171struct name { \ 172 struct type *stqh_first;/* first element */ \ 173 struct type **stqh_last;/* addr of last next element */ \ 174} 175 176#define STAILQ_HEAD_INITIALIZER(head) \ 177 { NULL, &(head).stqh_first } 178 179#define STAILQ_ENTRY(type) \ 180struct { \ 181 struct type *stqe_next; /* next element */ \ 182} 183 184/* 185 * Singly-linked Tail queue functions. 186 */ 187#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 188 189#define STAILQ_FIRST(head) ((head)->stqh_first) 190 191#define STAILQ_FOREACH(var, head, field) \ 192 for((var) = STAILQ_FIRST((head)); \ 193 (var); \ 194 (var) = STAILQ_NEXT((var), field)) 195 196#define STAILQ_INIT(head) do { \ 197 STAILQ_FIRST((head)) = NULL; \ 198 (head)->stqh_last = &STAILQ_FIRST((head)); \ 199} while (0) 200 201#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 202 if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 203 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 204 STAILQ_NEXT((tqelm), field) = (elm); \ 205} while (0) 206 207#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 208 if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 209 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 210 STAILQ_FIRST((head)) = (elm); \ 211} while (0) 212 213#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 214 STAILQ_NEXT((elm), field) = NULL; \ 215 *(head)->stqh_last = (elm); \ 216 (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 217} while (0) 218 219#define STAILQ_LAST(head, type, field) \ 220 (STAILQ_EMPTY(head) ? \ 221 NULL : \ 222 ((struct type *) \ 223 ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) 224 225#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 226 227#define STAILQ_REMOVE(head, elm, type, field) do { \ 228 if (STAILQ_FIRST((head)) == (elm)) { \ 229 STAILQ_REMOVE_HEAD(head, field); \ 230 } \ 231 else { \ 232 struct type *curelm = STAILQ_FIRST((head)); \ 233 while (STAILQ_NEXT(curelm, field) != (elm)) \ 234 curelm = STAILQ_NEXT(curelm, field); \ 235 if ((STAILQ_NEXT(curelm, field) = \ 236 STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ 237 (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ 238 } \ 239} while (0) 240 241#define STAILQ_REMOVE_HEAD(head, field) do { \ 242 if ((STAILQ_FIRST((head)) = \ 243 STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 244 (head)->stqh_last = &STAILQ_FIRST((head)); \ 245} while (0) 246 247#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ 248 if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ 249 (head)->stqh_last = &STAILQ_FIRST((head)); \ 250} while (0) 251 252/* 253 * List declarations. 254 */ 255#define LIST_HEAD(name, type) \ 256struct name { \ 257 struct type *lh_first; /* first element */ \ 258} 259 260#define LIST_HEAD_INITIALIZER(head) \ 261 { NULL } 262 263#define LIST_ENTRY(type) \ 264struct { \ 265 struct type *le_next; /* next element */ \ 266 struct type **le_prev; /* address of previous next element */ \ 267} 268 269/* 270 * List functions. 271 */ 272 273#define LIST_EMPTY(head) ((head)->lh_first == NULL) 274 275#define LIST_FIRST(head) ((head)->lh_first) 276 277#define LIST_FOREACH(var, head, field) \ 278 for ((var) = LIST_FIRST((head)); \ 279 (var); \ 280 (var) = LIST_NEXT((var), field)) 281 282#define LIST_INIT(head) do { \ 283 LIST_FIRST((head)) = NULL; \ 284} while (0) 285 286#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 287 if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 288 LIST_NEXT((listelm), field)->field.le_prev = \ 289 &LIST_NEXT((elm), field); \ 290 LIST_NEXT((listelm), field) = (elm); \ 291 (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 292} while (0) 293 294#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 295 (elm)->field.le_prev = (listelm)->field.le_prev; \ 296 LIST_NEXT((elm), field) = (listelm); \ 297 *(listelm)->field.le_prev = (elm); \ 298 (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 299} while (0) 300 301#define LIST_INSERT_HEAD(head, elm, field) do { \ 302 if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 303 LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 304 LIST_FIRST((head)) = (elm); \ 305 (elm)->field.le_prev = &LIST_FIRST((head)); \ 306} while (0) 307 308#define LIST_NEXT(elm, field) ((elm)->field.le_next) 309 310#define LIST_REMOVE(elm, field) do { \ 311 if (LIST_NEXT((elm), field) != NULL) \ 312 LIST_NEXT((elm), field)->field.le_prev = \ 313 (elm)->field.le_prev; \ 314 *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 315} while (0) 316 317/* 318 * Tail queue declarations. 319 */ 320#define TAILQ_HEAD(name, type) \ 321struct name { \ 322 struct type *tqh_first; /* first element */ \ 323 struct type **tqh_last; /* addr of last next element */ \ 324} 325 326#define TAILQ_HEAD_INITIALIZER(head) \ 327 { NULL, &(head).tqh_first } 328 329#define TAILQ_ENTRY(type) \ 330struct { \ 331 struct type *tqe_next; /* next element */ \ 332 struct type **tqe_prev; /* address of previous next element */ \ 333} 334 335/* 336 * Tail queue functions. 337 */ 338#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 339 340#define TAILQ_FIRST(head) ((head)->tqh_first) 341 342#define TAILQ_FOREACH(var, head, field) \ 343 for ((var) = TAILQ_FIRST((head)); \ 344 (var); \ 345 (var) = TAILQ_NEXT((var), field)) 346 347#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 348 for ((var) = TAILQ_LAST((head), headname); \ 349 (var); \ 350 (var) = TAILQ_PREV((var), headname, field)) 351 352#define TAILQ_INIT(head) do { \ 353 TAILQ_FIRST((head)) = NULL; \ 354 (head)->tqh_last = &TAILQ_FIRST((head)); \ 355} while (0) 356 357#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 358 if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 359 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 360 &TAILQ_NEXT((elm), field); \ 361 else \ 362 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 363 TAILQ_NEXT((listelm), field) = (elm); \ 364 (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 365} while (0) 366 367#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 368 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 369 TAILQ_NEXT((elm), field) = (listelm); \ 370 *(listelm)->field.tqe_prev = (elm); \ 371 (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 372} while (0) 373 374#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 375 if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 376 TAILQ_FIRST((head))->field.tqe_prev = \ 377 &TAILQ_NEXT((elm), field); \ 378 else \ 379 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 380 TAILQ_FIRST((head)) = (elm); \ 381 (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 382} while (0) 383 384#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 385 TAILQ_NEXT((elm), field) = NULL; \ 386 (elm)->field.tqe_prev = (head)->tqh_last; \ 387 *(head)->tqh_last = (elm); \ 388 (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 389} while (0) 390 391#define TAILQ_LAST(head, headname) \ 392 (*(((struct headname *)((head)->tqh_last))->tqh_last)) 393 394#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 395 396#define TAILQ_PREV(elm, headname, field) \ 397 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 398 399#define TAILQ_REMOVE(head, elm, field) do { \ 400 if ((TAILQ_NEXT((elm), field)) != NULL) \ 401 TAILQ_NEXT((elm), field)->field.tqe_prev = \ 402 (elm)->field.tqe_prev; \ 403 else \ 404 (head)->tqh_last = (elm)->field.tqe_prev; \ 405 *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 406} while (0) 407 408 409#ifdef _KERNEL 410 411/* 412 * XXX insque() and remque() are an old way of handling certain queues. 413 * They bogusly assumes that all queue heads look alike. 414 */ 415 416struct quehead { 417 struct quehead *qh_link; 418 struct quehead *qh_rlink; 419}; 420 421#ifdef __GNUC__ 422 423static __inline void 424insque(void *a, void *b) 425{ 426 struct quehead *element = (struct quehead *)a, 427 *head = (struct quehead *)b; 428 429 element->qh_link = head->qh_link; 430 element->qh_rlink = head; 431 head->qh_link = element; 432 element->qh_link->qh_rlink = element; 433} 434 435static __inline void 436remque(void *a) 437{ 438 struct quehead *element = (struct quehead *)a; 439 440 element->qh_link->qh_rlink = element->qh_rlink; 441 element->qh_rlink->qh_link = element->qh_link; 442 element->qh_rlink = 0; 443} 444 445#else /* !__GNUC__ */ 446 447void insque __P((void *a, void *b)); 448void remque __P((void *a)); 449 450#endif /* __GNUC__ */ 451 452#endif /* _KERNEL */ 453 454#endif /* !_SYS_QUEUE_H_ */ 455