1248619Sdes/* $OpenBSD: queue.h,v 1.36 2012/04/11 13:29:14 naddy Exp $ */ 2106121Sdes/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ 3106121Sdes 4106121Sdes/* 5106121Sdes * Copyright (c) 1991, 1993 6106121Sdes * The Regents of the University of California. All rights reserved. 7106121Sdes * 8106121Sdes * Redistribution and use in source and binary forms, with or without 9106121Sdes * modification, are permitted provided that the following conditions 10106121Sdes * are met: 11106121Sdes * 1. Redistributions of source code must retain the above copyright 12106121Sdes * notice, this list of conditions and the following disclaimer. 13106121Sdes * 2. Redistributions in binary form must reproduce the above copyright 14106121Sdes * notice, this list of conditions and the following disclaimer in the 15106121Sdes * documentation and/or other materials provided with the distribution. 16124208Sdes * 3. Neither the name of the University nor the names of its contributors 17106121Sdes * may be used to endorse or promote products derived from this software 18106121Sdes * without specific prior written permission. 19106121Sdes * 20106121Sdes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21106121Sdes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22106121Sdes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23106121Sdes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24106121Sdes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25106121Sdes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26106121Sdes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27106121Sdes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28106121Sdes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29106121Sdes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30106121Sdes * SUCH DAMAGE. 31106121Sdes * 32106121Sdes * @(#)queue.h 8.5 (Berkeley) 8/20/94 33106121Sdes */ 34106121Sdes 35157016Sdes/* OPENBSD ORIGINAL: sys/sys/queue.h */ 36157016Sdes 37106121Sdes#ifndef _FAKE_QUEUE_H_ 38106121Sdes#define _FAKE_QUEUE_H_ 39106121Sdes 40106121Sdes/* 41137015Sdes * Require for OS/X and other platforms that have old/broken/incomplete 42137015Sdes * <sys/queue.h>. 43106121Sdes */ 44106121Sdes#undef SLIST_HEAD 45106121Sdes#undef SLIST_HEAD_INITIALIZER 46106121Sdes#undef SLIST_ENTRY 47137015Sdes#undef SLIST_FOREACH_PREVPTR 48106121Sdes#undef SLIST_FIRST 49106121Sdes#undef SLIST_END 50106121Sdes#undef SLIST_EMPTY 51106121Sdes#undef SLIST_NEXT 52106121Sdes#undef SLIST_FOREACH 53106121Sdes#undef SLIST_INIT 54106121Sdes#undef SLIST_INSERT_AFTER 55106121Sdes#undef SLIST_INSERT_HEAD 56106121Sdes#undef SLIST_REMOVE_HEAD 57106121Sdes#undef SLIST_REMOVE 58137015Sdes#undef SLIST_REMOVE_NEXT 59106121Sdes#undef LIST_HEAD 60106121Sdes#undef LIST_HEAD_INITIALIZER 61106121Sdes#undef LIST_ENTRY 62106121Sdes#undef LIST_FIRST 63106121Sdes#undef LIST_END 64106121Sdes#undef LIST_EMPTY 65106121Sdes#undef LIST_NEXT 66106121Sdes#undef LIST_FOREACH 67106121Sdes#undef LIST_INIT 68106121Sdes#undef LIST_INSERT_AFTER 69106121Sdes#undef LIST_INSERT_BEFORE 70106121Sdes#undef LIST_INSERT_HEAD 71106121Sdes#undef LIST_REMOVE 72106121Sdes#undef LIST_REPLACE 73106121Sdes#undef SIMPLEQ_HEAD 74106121Sdes#undef SIMPLEQ_HEAD_INITIALIZER 75106121Sdes#undef SIMPLEQ_ENTRY 76106121Sdes#undef SIMPLEQ_FIRST 77106121Sdes#undef SIMPLEQ_END 78106121Sdes#undef SIMPLEQ_EMPTY 79106121Sdes#undef SIMPLEQ_NEXT 80106121Sdes#undef SIMPLEQ_FOREACH 81106121Sdes#undef SIMPLEQ_INIT 82106121Sdes#undef SIMPLEQ_INSERT_HEAD 83106121Sdes#undef SIMPLEQ_INSERT_TAIL 84106121Sdes#undef SIMPLEQ_INSERT_AFTER 85106121Sdes#undef SIMPLEQ_REMOVE_HEAD 86106121Sdes#undef TAILQ_HEAD 87106121Sdes#undef TAILQ_HEAD_INITIALIZER 88106121Sdes#undef TAILQ_ENTRY 89106121Sdes#undef TAILQ_FIRST 90106121Sdes#undef TAILQ_END 91106121Sdes#undef TAILQ_NEXT 92106121Sdes#undef TAILQ_LAST 93106121Sdes#undef TAILQ_PREV 94106121Sdes#undef TAILQ_EMPTY 95106121Sdes#undef TAILQ_FOREACH 96106121Sdes#undef TAILQ_FOREACH_REVERSE 97106121Sdes#undef TAILQ_INIT 98106121Sdes#undef TAILQ_INSERT_HEAD 99106121Sdes#undef TAILQ_INSERT_TAIL 100106121Sdes#undef TAILQ_INSERT_AFTER 101106121Sdes#undef TAILQ_INSERT_BEFORE 102106121Sdes#undef TAILQ_REMOVE 103106121Sdes#undef TAILQ_REPLACE 104106121Sdes#undef CIRCLEQ_HEAD 105106121Sdes#undef CIRCLEQ_HEAD_INITIALIZER 106106121Sdes#undef CIRCLEQ_ENTRY 107106121Sdes#undef CIRCLEQ_FIRST 108106121Sdes#undef CIRCLEQ_LAST 109106121Sdes#undef CIRCLEQ_END 110106121Sdes#undef CIRCLEQ_NEXT 111106121Sdes#undef CIRCLEQ_PREV 112106121Sdes#undef CIRCLEQ_EMPTY 113106121Sdes#undef CIRCLEQ_FOREACH 114106121Sdes#undef CIRCLEQ_FOREACH_REVERSE 115106121Sdes#undef CIRCLEQ_INIT 116106121Sdes#undef CIRCLEQ_INSERT_AFTER 117106121Sdes#undef CIRCLEQ_INSERT_BEFORE 118106121Sdes#undef CIRCLEQ_INSERT_HEAD 119106121Sdes#undef CIRCLEQ_INSERT_TAIL 120106121Sdes#undef CIRCLEQ_REMOVE 121106121Sdes#undef CIRCLEQ_REPLACE 122106121Sdes 123106121Sdes/* 124106121Sdes * This file defines five types of data structures: singly-linked lists, 125106121Sdes * lists, simple queues, tail queues, and circular queues. 126106121Sdes * 127106121Sdes * 128106121Sdes * A singly-linked list is headed by a single forward pointer. The elements 129106121Sdes * are singly linked for minimum space and pointer manipulation overhead at 130106121Sdes * the expense of O(n) removal for arbitrary elements. New elements can be 131106121Sdes * added to the list after an existing element or at the head of the list. 132106121Sdes * Elements being removed from the head of the list should use the explicit 133106121Sdes * macro for this purpose for optimum efficiency. A singly-linked list may 134106121Sdes * only be traversed in the forward direction. Singly-linked lists are ideal 135106121Sdes * for applications with large datasets and few or no removals or for 136106121Sdes * implementing a LIFO queue. 137106121Sdes * 138106121Sdes * A list is headed by a single forward pointer (or an array of forward 139106121Sdes * pointers for a hash table header). The elements are doubly linked 140106121Sdes * so that an arbitrary element can be removed without a need to 141106121Sdes * traverse the list. New elements can be added to the list before 142106121Sdes * or after an existing element or at the head of the list. A list 143106121Sdes * may only be traversed in the forward direction. 144106121Sdes * 145106121Sdes * A simple queue is headed by a pair of pointers, one the head of the 146106121Sdes * list and the other to the tail of the list. The elements are singly 147106121Sdes * linked to save space, so elements can only be removed from the 148106121Sdes * head of the list. New elements can be added to the list before or after 149106121Sdes * an existing element, at the head of the list, or at the end of the 150106121Sdes * list. A simple queue may only be traversed in the forward direction. 151106121Sdes * 152106121Sdes * A tail queue is headed by a pair of pointers, one to the head of the 153106121Sdes * list and the other to the tail of the list. The elements are doubly 154106121Sdes * linked so that an arbitrary element can be removed without a need to 155106121Sdes * traverse the list. New elements can be added to the list before or 156106121Sdes * after an existing element, at the head of the list, or at the end of 157106121Sdes * the list. A tail queue may be traversed in either direction. 158106121Sdes * 159106121Sdes * A circle queue is headed by a pair of pointers, one to the head of the 160106121Sdes * list and the other to the tail of the list. The elements are doubly 161106121Sdes * linked so that an arbitrary element can be removed without a need to 162106121Sdes * traverse the list. New elements can be added to the list before or after 163106121Sdes * an existing element, at the head of the list, or at the end of the list. 164106121Sdes * A circle queue may be traversed in either direction, but has a more 165106121Sdes * complex end of list detection. 166106121Sdes * 167106121Sdes * For details on the use of these macros, see the queue(3) manual page. 168106121Sdes */ 169106121Sdes 170181111Sdes#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) 171181111Sdes#define _Q_INVALIDATE(a) (a) = ((void *)-1) 172181111Sdes#else 173181111Sdes#define _Q_INVALIDATE(a) 174181111Sdes#endif 175181111Sdes 176106121Sdes/* 177106121Sdes * Singly-linked List definitions. 178106121Sdes */ 179106121Sdes#define SLIST_HEAD(name, type) \ 180106121Sdesstruct name { \ 181106121Sdes struct type *slh_first; /* first element */ \ 182106121Sdes} 183106121Sdes 184106121Sdes#define SLIST_HEAD_INITIALIZER(head) \ 185106121Sdes { NULL } 186106121Sdes 187106121Sdes#define SLIST_ENTRY(type) \ 188106121Sdesstruct { \ 189106121Sdes struct type *sle_next; /* next element */ \ 190106121Sdes} 191106121Sdes 192106121Sdes/* 193106121Sdes * Singly-linked List access methods. 194106121Sdes */ 195106121Sdes#define SLIST_FIRST(head) ((head)->slh_first) 196106121Sdes#define SLIST_END(head) NULL 197106121Sdes#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head)) 198106121Sdes#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 199106121Sdes 200106121Sdes#define SLIST_FOREACH(var, head, field) \ 201106121Sdes for((var) = SLIST_FIRST(head); \ 202106121Sdes (var) != SLIST_END(head); \ 203106121Sdes (var) = SLIST_NEXT(var, field)) 204106121Sdes 205248619Sdes#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 206248619Sdes for ((var) = SLIST_FIRST(head); \ 207248619Sdes (var) && ((tvar) = SLIST_NEXT(var, field), 1); \ 208248619Sdes (var) = (tvar)) 209137015Sdes 210106121Sdes/* 211106121Sdes * Singly-linked List functions. 212106121Sdes */ 213106121Sdes#define SLIST_INIT(head) { \ 214106121Sdes SLIST_FIRST(head) = SLIST_END(head); \ 215106121Sdes} 216106121Sdes 217106121Sdes#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 218106121Sdes (elm)->field.sle_next = (slistelm)->field.sle_next; \ 219106121Sdes (slistelm)->field.sle_next = (elm); \ 220106121Sdes} while (0) 221106121Sdes 222106121Sdes#define SLIST_INSERT_HEAD(head, elm, field) do { \ 223106121Sdes (elm)->field.sle_next = (head)->slh_first; \ 224106121Sdes (head)->slh_first = (elm); \ 225106121Sdes} while (0) 226106121Sdes 227248619Sdes#define SLIST_REMOVE_AFTER(elm, field) do { \ 228137015Sdes (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \ 229137015Sdes} while (0) 230137015Sdes 231106121Sdes#define SLIST_REMOVE_HEAD(head, field) do { \ 232106121Sdes (head)->slh_first = (head)->slh_first->field.sle_next; \ 233106121Sdes} while (0) 234106121Sdes 235106121Sdes#define SLIST_REMOVE(head, elm, type, field) do { \ 236106121Sdes if ((head)->slh_first == (elm)) { \ 237106121Sdes SLIST_REMOVE_HEAD((head), field); \ 238181111Sdes } else { \ 239106121Sdes struct type *curelm = (head)->slh_first; \ 240181111Sdes \ 241181111Sdes while (curelm->field.sle_next != (elm)) \ 242106121Sdes curelm = curelm->field.sle_next; \ 243106121Sdes curelm->field.sle_next = \ 244106121Sdes curelm->field.sle_next->field.sle_next; \ 245181111Sdes _Q_INVALIDATE((elm)->field.sle_next); \ 246106121Sdes } \ 247106121Sdes} while (0) 248106121Sdes 249106121Sdes/* 250106121Sdes * List definitions. 251106121Sdes */ 252106121Sdes#define LIST_HEAD(name, type) \ 253106121Sdesstruct name { \ 254106121Sdes struct type *lh_first; /* first element */ \ 255106121Sdes} 256106121Sdes 257106121Sdes#define LIST_HEAD_INITIALIZER(head) \ 258106121Sdes { NULL } 259106121Sdes 260106121Sdes#define LIST_ENTRY(type) \ 261106121Sdesstruct { \ 262106121Sdes struct type *le_next; /* next element */ \ 263106121Sdes struct type **le_prev; /* address of previous next element */ \ 264106121Sdes} 265106121Sdes 266106121Sdes/* 267106121Sdes * List access methods 268106121Sdes */ 269106121Sdes#define LIST_FIRST(head) ((head)->lh_first) 270106121Sdes#define LIST_END(head) NULL 271106121Sdes#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head)) 272106121Sdes#define LIST_NEXT(elm, field) ((elm)->field.le_next) 273106121Sdes 274106121Sdes#define LIST_FOREACH(var, head, field) \ 275106121Sdes for((var) = LIST_FIRST(head); \ 276106121Sdes (var)!= LIST_END(head); \ 277106121Sdes (var) = LIST_NEXT(var, field)) 278106121Sdes 279248619Sdes#define LIST_FOREACH_SAFE(var, head, field, tvar) \ 280248619Sdes for ((var) = LIST_FIRST(head); \ 281248619Sdes (var) && ((tvar) = LIST_NEXT(var, field), 1); \ 282248619Sdes (var) = (tvar)) 283248619Sdes 284106121Sdes/* 285106121Sdes * List functions. 286106121Sdes */ 287106121Sdes#define LIST_INIT(head) do { \ 288106121Sdes LIST_FIRST(head) = LIST_END(head); \ 289106121Sdes} while (0) 290106121Sdes 291106121Sdes#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 292106121Sdes if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 293106121Sdes (listelm)->field.le_next->field.le_prev = \ 294106121Sdes &(elm)->field.le_next; \ 295106121Sdes (listelm)->field.le_next = (elm); \ 296106121Sdes (elm)->field.le_prev = &(listelm)->field.le_next; \ 297106121Sdes} while (0) 298106121Sdes 299106121Sdes#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 300106121Sdes (elm)->field.le_prev = (listelm)->field.le_prev; \ 301106121Sdes (elm)->field.le_next = (listelm); \ 302106121Sdes *(listelm)->field.le_prev = (elm); \ 303106121Sdes (listelm)->field.le_prev = &(elm)->field.le_next; \ 304106121Sdes} while (0) 305106121Sdes 306106121Sdes#define LIST_INSERT_HEAD(head, elm, field) do { \ 307106121Sdes if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 308106121Sdes (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 309106121Sdes (head)->lh_first = (elm); \ 310106121Sdes (elm)->field.le_prev = &(head)->lh_first; \ 311106121Sdes} while (0) 312106121Sdes 313106121Sdes#define LIST_REMOVE(elm, field) do { \ 314106121Sdes if ((elm)->field.le_next != NULL) \ 315106121Sdes (elm)->field.le_next->field.le_prev = \ 316106121Sdes (elm)->field.le_prev; \ 317106121Sdes *(elm)->field.le_prev = (elm)->field.le_next; \ 318181111Sdes _Q_INVALIDATE((elm)->field.le_prev); \ 319181111Sdes _Q_INVALIDATE((elm)->field.le_next); \ 320106121Sdes} while (0) 321106121Sdes 322106121Sdes#define LIST_REPLACE(elm, elm2, field) do { \ 323106121Sdes if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \ 324106121Sdes (elm2)->field.le_next->field.le_prev = \ 325106121Sdes &(elm2)->field.le_next; \ 326106121Sdes (elm2)->field.le_prev = (elm)->field.le_prev; \ 327106121Sdes *(elm2)->field.le_prev = (elm2); \ 328181111Sdes _Q_INVALIDATE((elm)->field.le_prev); \ 329181111Sdes _Q_INVALIDATE((elm)->field.le_next); \ 330106121Sdes} while (0) 331106121Sdes 332106121Sdes/* 333106121Sdes * Simple queue definitions. 334106121Sdes */ 335106121Sdes#define SIMPLEQ_HEAD(name, type) \ 336106121Sdesstruct name { \ 337106121Sdes struct type *sqh_first; /* first element */ \ 338106121Sdes struct type **sqh_last; /* addr of last next element */ \ 339106121Sdes} 340106121Sdes 341106121Sdes#define SIMPLEQ_HEAD_INITIALIZER(head) \ 342106121Sdes { NULL, &(head).sqh_first } 343106121Sdes 344106121Sdes#define SIMPLEQ_ENTRY(type) \ 345106121Sdesstruct { \ 346106121Sdes struct type *sqe_next; /* next element */ \ 347106121Sdes} 348106121Sdes 349106121Sdes/* 350106121Sdes * Simple queue access methods. 351106121Sdes */ 352106121Sdes#define SIMPLEQ_FIRST(head) ((head)->sqh_first) 353106121Sdes#define SIMPLEQ_END(head) NULL 354106121Sdes#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head)) 355106121Sdes#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) 356106121Sdes 357106121Sdes#define SIMPLEQ_FOREACH(var, head, field) \ 358106121Sdes for((var) = SIMPLEQ_FIRST(head); \ 359106121Sdes (var) != SIMPLEQ_END(head); \ 360106121Sdes (var) = SIMPLEQ_NEXT(var, field)) 361106121Sdes 362248619Sdes#define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ 363248619Sdes for ((var) = SIMPLEQ_FIRST(head); \ 364248619Sdes (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \ 365248619Sdes (var) = (tvar)) 366248619Sdes 367106121Sdes/* 368106121Sdes * Simple queue functions. 369106121Sdes */ 370106121Sdes#define SIMPLEQ_INIT(head) do { \ 371106121Sdes (head)->sqh_first = NULL; \ 372106121Sdes (head)->sqh_last = &(head)->sqh_first; \ 373106121Sdes} while (0) 374106121Sdes 375106121Sdes#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ 376106121Sdes if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ 377106121Sdes (head)->sqh_last = &(elm)->field.sqe_next; \ 378106121Sdes (head)->sqh_first = (elm); \ 379106121Sdes} while (0) 380106121Sdes 381106121Sdes#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ 382106121Sdes (elm)->field.sqe_next = NULL; \ 383106121Sdes *(head)->sqh_last = (elm); \ 384106121Sdes (head)->sqh_last = &(elm)->field.sqe_next; \ 385106121Sdes} while (0) 386106121Sdes 387106121Sdes#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 388106121Sdes if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ 389106121Sdes (head)->sqh_last = &(elm)->field.sqe_next; \ 390106121Sdes (listelm)->field.sqe_next = (elm); \ 391106121Sdes} while (0) 392106121Sdes 393181111Sdes#define SIMPLEQ_REMOVE_HEAD(head, field) do { \ 394181111Sdes if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ 395106121Sdes (head)->sqh_last = &(head)->sqh_first; \ 396106121Sdes} while (0) 397106121Sdes 398248619Sdes#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ 399248619Sdes if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \ 400248619Sdes == NULL) \ 401248619Sdes (head)->sqh_last = &(elm)->field.sqe_next; \ 402248619Sdes} while (0) 403248619Sdes 404106121Sdes/* 405106121Sdes * Tail queue definitions. 406106121Sdes */ 407106121Sdes#define TAILQ_HEAD(name, type) \ 408106121Sdesstruct name { \ 409106121Sdes struct type *tqh_first; /* first element */ \ 410106121Sdes struct type **tqh_last; /* addr of last next element */ \ 411106121Sdes} 412106121Sdes 413106121Sdes#define TAILQ_HEAD_INITIALIZER(head) \ 414106121Sdes { NULL, &(head).tqh_first } 415106121Sdes 416106121Sdes#define TAILQ_ENTRY(type) \ 417106121Sdesstruct { \ 418106121Sdes struct type *tqe_next; /* next element */ \ 419106121Sdes struct type **tqe_prev; /* address of previous next element */ \ 420106121Sdes} 421106121Sdes 422106121Sdes/* 423106121Sdes * tail queue access methods 424106121Sdes */ 425106121Sdes#define TAILQ_FIRST(head) ((head)->tqh_first) 426106121Sdes#define TAILQ_END(head) NULL 427106121Sdes#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 428106121Sdes#define TAILQ_LAST(head, headname) \ 429106121Sdes (*(((struct headname *)((head)->tqh_last))->tqh_last)) 430106121Sdes/* XXX */ 431106121Sdes#define TAILQ_PREV(elm, headname, field) \ 432106121Sdes (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 433106121Sdes#define TAILQ_EMPTY(head) \ 434106121Sdes (TAILQ_FIRST(head) == TAILQ_END(head)) 435106121Sdes 436106121Sdes#define TAILQ_FOREACH(var, head, field) \ 437106121Sdes for((var) = TAILQ_FIRST(head); \ 438106121Sdes (var) != TAILQ_END(head); \ 439106121Sdes (var) = TAILQ_NEXT(var, field)) 440106121Sdes 441248619Sdes#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 442248619Sdes for ((var) = TAILQ_FIRST(head); \ 443248619Sdes (var) != TAILQ_END(head) && \ 444248619Sdes ((tvar) = TAILQ_NEXT(var, field), 1); \ 445248619Sdes (var) = (tvar)) 446248619Sdes 447248619Sdes 448137015Sdes#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 449106121Sdes for((var) = TAILQ_LAST(head, headname); \ 450106121Sdes (var) != TAILQ_END(head); \ 451106121Sdes (var) = TAILQ_PREV(var, headname, field)) 452106121Sdes 453248619Sdes#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 454248619Sdes for ((var) = TAILQ_LAST(head, headname); \ 455248619Sdes (var) != TAILQ_END(head) && \ 456248619Sdes ((tvar) = TAILQ_PREV(var, headname, field), 1); \ 457248619Sdes (var) = (tvar)) 458248619Sdes 459106121Sdes/* 460106121Sdes * Tail queue functions. 461106121Sdes */ 462106121Sdes#define TAILQ_INIT(head) do { \ 463106121Sdes (head)->tqh_first = NULL; \ 464106121Sdes (head)->tqh_last = &(head)->tqh_first; \ 465106121Sdes} while (0) 466106121Sdes 467106121Sdes#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 468106121Sdes if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 469106121Sdes (head)->tqh_first->field.tqe_prev = \ 470106121Sdes &(elm)->field.tqe_next; \ 471106121Sdes else \ 472106121Sdes (head)->tqh_last = &(elm)->field.tqe_next; \ 473106121Sdes (head)->tqh_first = (elm); \ 474106121Sdes (elm)->field.tqe_prev = &(head)->tqh_first; \ 475106121Sdes} while (0) 476106121Sdes 477106121Sdes#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 478106121Sdes (elm)->field.tqe_next = NULL; \ 479106121Sdes (elm)->field.tqe_prev = (head)->tqh_last; \ 480106121Sdes *(head)->tqh_last = (elm); \ 481106121Sdes (head)->tqh_last = &(elm)->field.tqe_next; \ 482106121Sdes} while (0) 483106121Sdes 484106121Sdes#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 485106121Sdes if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 486106121Sdes (elm)->field.tqe_next->field.tqe_prev = \ 487106121Sdes &(elm)->field.tqe_next; \ 488106121Sdes else \ 489106121Sdes (head)->tqh_last = &(elm)->field.tqe_next; \ 490106121Sdes (listelm)->field.tqe_next = (elm); \ 491106121Sdes (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 492106121Sdes} while (0) 493106121Sdes 494106121Sdes#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 495106121Sdes (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 496106121Sdes (elm)->field.tqe_next = (listelm); \ 497106121Sdes *(listelm)->field.tqe_prev = (elm); \ 498106121Sdes (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 499106121Sdes} while (0) 500106121Sdes 501106121Sdes#define TAILQ_REMOVE(head, elm, field) do { \ 502106121Sdes if (((elm)->field.tqe_next) != NULL) \ 503106121Sdes (elm)->field.tqe_next->field.tqe_prev = \ 504106121Sdes (elm)->field.tqe_prev; \ 505106121Sdes else \ 506106121Sdes (head)->tqh_last = (elm)->field.tqe_prev; \ 507106121Sdes *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 508181111Sdes _Q_INVALIDATE((elm)->field.tqe_prev); \ 509181111Sdes _Q_INVALIDATE((elm)->field.tqe_next); \ 510106121Sdes} while (0) 511106121Sdes 512106121Sdes#define TAILQ_REPLACE(head, elm, elm2, field) do { \ 513106121Sdes if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \ 514106121Sdes (elm2)->field.tqe_next->field.tqe_prev = \ 515106121Sdes &(elm2)->field.tqe_next; \ 516106121Sdes else \ 517106121Sdes (head)->tqh_last = &(elm2)->field.tqe_next; \ 518106121Sdes (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ 519106121Sdes *(elm2)->field.tqe_prev = (elm2); \ 520181111Sdes _Q_INVALIDATE((elm)->field.tqe_prev); \ 521181111Sdes _Q_INVALIDATE((elm)->field.tqe_next); \ 522106121Sdes} while (0) 523106121Sdes 524106121Sdes/* 525106121Sdes * Circular queue definitions. 526106121Sdes */ 527106121Sdes#define CIRCLEQ_HEAD(name, type) \ 528106121Sdesstruct name { \ 529106121Sdes struct type *cqh_first; /* first element */ \ 530106121Sdes struct type *cqh_last; /* last element */ \ 531106121Sdes} 532106121Sdes 533106121Sdes#define CIRCLEQ_HEAD_INITIALIZER(head) \ 534106121Sdes { CIRCLEQ_END(&head), CIRCLEQ_END(&head) } 535106121Sdes 536106121Sdes#define CIRCLEQ_ENTRY(type) \ 537106121Sdesstruct { \ 538106121Sdes struct type *cqe_next; /* next element */ \ 539106121Sdes struct type *cqe_prev; /* previous element */ \ 540106121Sdes} 541106121Sdes 542106121Sdes/* 543106121Sdes * Circular queue access methods 544106121Sdes */ 545106121Sdes#define CIRCLEQ_FIRST(head) ((head)->cqh_first) 546106121Sdes#define CIRCLEQ_LAST(head) ((head)->cqh_last) 547106121Sdes#define CIRCLEQ_END(head) ((void *)(head)) 548106121Sdes#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) 549106121Sdes#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) 550106121Sdes#define CIRCLEQ_EMPTY(head) \ 551106121Sdes (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head)) 552106121Sdes 553106121Sdes#define CIRCLEQ_FOREACH(var, head, field) \ 554106121Sdes for((var) = CIRCLEQ_FIRST(head); \ 555106121Sdes (var) != CIRCLEQ_END(head); \ 556106121Sdes (var) = CIRCLEQ_NEXT(var, field)) 557106121Sdes 558248619Sdes#define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \ 559248619Sdes for ((var) = CIRCLEQ_FIRST(head); \ 560248619Sdes (var) != CIRCLEQ_END(head) && \ 561248619Sdes ((tvar) = CIRCLEQ_NEXT(var, field), 1); \ 562248619Sdes (var) = (tvar)) 563248619Sdes 564106121Sdes#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ 565106121Sdes for((var) = CIRCLEQ_LAST(head); \ 566106121Sdes (var) != CIRCLEQ_END(head); \ 567106121Sdes (var) = CIRCLEQ_PREV(var, field)) 568106121Sdes 569248619Sdes#define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 570248619Sdes for ((var) = CIRCLEQ_LAST(head, headname); \ 571248619Sdes (var) != CIRCLEQ_END(head) && \ 572248619Sdes ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \ 573248619Sdes (var) = (tvar)) 574248619Sdes 575106121Sdes/* 576106121Sdes * Circular queue functions. 577106121Sdes */ 578106121Sdes#define CIRCLEQ_INIT(head) do { \ 579106121Sdes (head)->cqh_first = CIRCLEQ_END(head); \ 580106121Sdes (head)->cqh_last = CIRCLEQ_END(head); \ 581106121Sdes} while (0) 582106121Sdes 583106121Sdes#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 584106121Sdes (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 585106121Sdes (elm)->field.cqe_prev = (listelm); \ 586106121Sdes if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \ 587106121Sdes (head)->cqh_last = (elm); \ 588106121Sdes else \ 589106121Sdes (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 590106121Sdes (listelm)->field.cqe_next = (elm); \ 591106121Sdes} while (0) 592106121Sdes 593106121Sdes#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ 594106121Sdes (elm)->field.cqe_next = (listelm); \ 595106121Sdes (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 596106121Sdes if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \ 597106121Sdes (head)->cqh_first = (elm); \ 598106121Sdes else \ 599106121Sdes (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 600106121Sdes (listelm)->field.cqe_prev = (elm); \ 601106121Sdes} while (0) 602106121Sdes 603106121Sdes#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ 604106121Sdes (elm)->field.cqe_next = (head)->cqh_first; \ 605106121Sdes (elm)->field.cqe_prev = CIRCLEQ_END(head); \ 606106121Sdes if ((head)->cqh_last == CIRCLEQ_END(head)) \ 607106121Sdes (head)->cqh_last = (elm); \ 608106121Sdes else \ 609106121Sdes (head)->cqh_first->field.cqe_prev = (elm); \ 610106121Sdes (head)->cqh_first = (elm); \ 611106121Sdes} while (0) 612106121Sdes 613106121Sdes#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ 614106121Sdes (elm)->field.cqe_next = CIRCLEQ_END(head); \ 615106121Sdes (elm)->field.cqe_prev = (head)->cqh_last; \ 616106121Sdes if ((head)->cqh_first == CIRCLEQ_END(head)) \ 617106121Sdes (head)->cqh_first = (elm); \ 618106121Sdes else \ 619106121Sdes (head)->cqh_last->field.cqe_next = (elm); \ 620106121Sdes (head)->cqh_last = (elm); \ 621106121Sdes} while (0) 622106121Sdes 623106121Sdes#define CIRCLEQ_REMOVE(head, elm, field) do { \ 624106121Sdes if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \ 625106121Sdes (head)->cqh_last = (elm)->field.cqe_prev; \ 626106121Sdes else \ 627106121Sdes (elm)->field.cqe_next->field.cqe_prev = \ 628106121Sdes (elm)->field.cqe_prev; \ 629106121Sdes if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \ 630106121Sdes (head)->cqh_first = (elm)->field.cqe_next; \ 631106121Sdes else \ 632106121Sdes (elm)->field.cqe_prev->field.cqe_next = \ 633106121Sdes (elm)->field.cqe_next; \ 634181111Sdes _Q_INVALIDATE((elm)->field.cqe_prev); \ 635181111Sdes _Q_INVALIDATE((elm)->field.cqe_next); \ 636106121Sdes} while (0) 637106121Sdes 638106121Sdes#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \ 639106121Sdes if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \ 640106121Sdes CIRCLEQ_END(head)) \ 641106121Sdes (head).cqh_last = (elm2); \ 642106121Sdes else \ 643106121Sdes (elm2)->field.cqe_next->field.cqe_prev = (elm2); \ 644106121Sdes if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \ 645106121Sdes CIRCLEQ_END(head)) \ 646106121Sdes (head).cqh_first = (elm2); \ 647106121Sdes else \ 648106121Sdes (elm2)->field.cqe_prev->field.cqe_next = (elm2); \ 649181111Sdes _Q_INVALIDATE((elm)->field.cqe_prev); \ 650181111Sdes _Q_INVALIDATE((elm)->field.cqe_next); \ 651106121Sdes} while (0) 652106121Sdes 653106121Sdes#endif /* !_FAKE_QUEUE_H_ */ 654