1156283Srwatson/*- 2156283Srwatson * Copyright (c) 1991, 1993 3156283Srwatson * The Regents of the University of California. All rights reserved. 4156283Srwatson * 5156283Srwatson * Redistribution and use in source and binary forms, with or without 6156283Srwatson * modification, are permitted provided that the following conditions 7156283Srwatson * are met: 8156283Srwatson * 1. Redistributions of source code must retain the above copyright 9156283Srwatson * notice, this list of conditions and the following disclaimer. 10156283Srwatson * 2. Redistributions in binary form must reproduce the above copyright 11156283Srwatson * notice, this list of conditions and the following disclaimer in the 12156283Srwatson * documentation and/or other materials provided with the distribution. 13156283Srwatson * 4. Neither the name of the University nor the names of its contributors 14156283Srwatson * may be used to endorse or promote products derived from this software 15156283Srwatson * without specific prior written permission. 16156283Srwatson * 17156283Srwatson * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18156283Srwatson * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19156283Srwatson * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20156283Srwatson * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21156283Srwatson * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22156283Srwatson * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23156283Srwatson * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24156283Srwatson * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25156283Srwatson * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26156283Srwatson * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27156283Srwatson * SUCH DAMAGE. 28156283Srwatson * 29156283Srwatson * @(#)queue.h 8.5 (Berkeley) 8/20/94 30156283Srwatson * 31156283Srwatson * Derived from FreeBSD src/sys/sys/queue.h:1.63. 32156283Srwatson * $P4: //depot/projects/trustedbsd/openbsm/compat/queue.h#3 $ 33156283Srwatson */ 34156283Srwatson 35156283Srwatson#ifndef _COMPAT_QUEUE_H_ 36156283Srwatson#define _COMPAT_QUEUE_H_ 37156283Srwatson 38156283Srwatson#include <sys/cdefs.h> 39156283Srwatson 40156283Srwatson/* 41156283Srwatson * This file defines four types of data structures: singly-linked lists, 42156283Srwatson * singly-linked tail queues, lists and tail queues. 43156283Srwatson * 44156283Srwatson * A singly-linked list is headed by a single forward pointer. The elements 45156283Srwatson * are singly linked for minimum space and pointer manipulation overhead at 46156283Srwatson * the expense of O(n) removal for arbitrary elements. New elements can be 47156283Srwatson * added to the list after an existing element or at the head of the list. 48156283Srwatson * Elements being removed from the head of the list should use the explicit 49156283Srwatson * macro for this purpose for optimum efficiency. A singly-linked list may 50156283Srwatson * only be traversed in the forward direction. Singly-linked lists are ideal 51156283Srwatson * for applications with large datasets and few or no removals or for 52156283Srwatson * implementing a LIFO queue. 53156283Srwatson * 54156283Srwatson * A singly-linked tail queue is headed by a pair of pointers, one to the 55156283Srwatson * head of the list and the other to the tail of the list. The elements are 56156283Srwatson * singly linked for minimum space and pointer manipulation overhead at the 57156283Srwatson * expense of O(n) removal for arbitrary elements. New elements can be added 58156283Srwatson * to the list after an existing element, at the head of the list, or at the 59156283Srwatson * end of the list. Elements being removed from the head of the tail queue 60156283Srwatson * should use the explicit macro for this purpose for optimum efficiency. 61156283Srwatson * A singly-linked tail queue may only be traversed in the forward direction. 62156283Srwatson * Singly-linked tail queues are ideal for applications with large datasets 63156283Srwatson * and few or no removals or for implementing a FIFO queue. 64156283Srwatson * 65156283Srwatson * A list is headed by a single forward pointer (or an array of forward 66156283Srwatson * pointers for a hash table header). The elements are doubly linked 67156283Srwatson * so that an arbitrary element can be removed without a need to 68156283Srwatson * traverse the list. New elements can be added to the list before 69156283Srwatson * or after an existing element or at the head of the list. A list 70156283Srwatson * may only be traversed in the forward direction. 71156283Srwatson * 72156283Srwatson * A tail queue is headed by a pair of pointers, one to the head of the 73156283Srwatson * list and the other to the tail of the list. The elements are doubly 74156283Srwatson * linked so that an arbitrary element can be removed without a need to 75156283Srwatson * traverse the list. New elements can be added to the list before or 76156283Srwatson * after an existing element, at the head of the list, or at the end of 77156283Srwatson * the list. A tail queue may be traversed in either direction. 78156283Srwatson * 79156283Srwatson * For details on the use of these macros, see the queue(3) manual page. 80156283Srwatson * 81156283Srwatson * 82156283Srwatson * SLIST LIST STAILQ TAILQ 83156283Srwatson * _HEAD + + + + 84156283Srwatson * _HEAD_INITIALIZER + + + + 85156283Srwatson * _ENTRY + + + + 86156283Srwatson * _INIT + + + + 87156283Srwatson * _EMPTY + + + + 88156283Srwatson * _FIRST + + + + 89156283Srwatson * _NEXT + + + + 90156283Srwatson * _PREV - - - + 91156283Srwatson * _LAST - - + + 92156283Srwatson * _FOREACH + + + + 93156283Srwatson * _FOREACH_SAFE + + + + 94156283Srwatson * _FOREACH_REVERSE - - - + 95156283Srwatson * _FOREACH_REVERSE_SAFE - - - + 96156283Srwatson * _INSERT_HEAD + + + + 97156283Srwatson * _INSERT_BEFORE - + - + 98156283Srwatson * _INSERT_AFTER + + + + 99156283Srwatson * _INSERT_TAIL - - + + 100156283Srwatson * _CONCAT - - + + 101156283Srwatson * _REMOVE_HEAD + - + - 102156283Srwatson * _REMOVE + + + + 103156283Srwatson * 104156283Srwatson */ 105156283Srwatson#ifdef QUEUE_MACRO_DEBUG 106156283Srwatson/* Store the last 2 places the queue element or head was altered */ 107156283Srwatsonstruct qm_trace { 108156283Srwatson char * lastfile; 109156283Srwatson int lastline; 110156283Srwatson char * prevfile; 111156283Srwatson int prevline; 112156283Srwatson}; 113156283Srwatson 114156283Srwatson#define TRACEBUF struct qm_trace trace; 115156283Srwatson#define TRASHIT(x) do {(x) = (void *)-1;} while (0) 116156283Srwatson 117156283Srwatson#define QMD_TRACE_HEAD(head) do { \ 118156283Srwatson (head)->trace.prevline = (head)->trace.lastline; \ 119156283Srwatson (head)->trace.prevfile = (head)->trace.lastfile; \ 120156283Srwatson (head)->trace.lastline = __LINE__; \ 121156283Srwatson (head)->trace.lastfile = __FILE__; \ 122156283Srwatson} while (0) 123156283Srwatson 124156283Srwatson#define QMD_TRACE_ELEM(elem) do { \ 125156283Srwatson (elem)->trace.prevline = (elem)->trace.lastline; \ 126156283Srwatson (elem)->trace.prevfile = (elem)->trace.lastfile; \ 127156283Srwatson (elem)->trace.lastline = __LINE__; \ 128156283Srwatson (elem)->trace.lastfile = __FILE__; \ 129156283Srwatson} while (0) 130156283Srwatson 131156283Srwatson#else 132156283Srwatson#define QMD_TRACE_ELEM(elem) 133156283Srwatson#define QMD_TRACE_HEAD(head) 134156283Srwatson#define TRACEBUF 135156283Srwatson#define TRASHIT(x) 136156283Srwatson#endif /* QUEUE_MACRO_DEBUG */ 137156283Srwatson 138156283Srwatson/* 139156283Srwatson * Singly-linked List declarations. 140156283Srwatson */ 141156283Srwatson#define SLIST_HEAD(name, type) \ 142156283Srwatsonstruct name { \ 143156283Srwatson struct type *slh_first; /* first element */ \ 144156283Srwatson} 145156283Srwatson 146156283Srwatson#define SLIST_HEAD_INITIALIZER(head) \ 147156283Srwatson { NULL } 148156283Srwatson 149156283Srwatson#define SLIST_ENTRY(type) \ 150156283Srwatsonstruct { \ 151156283Srwatson struct type *sle_next; /* next element */ \ 152156283Srwatson} 153156283Srwatson 154156283Srwatson/* 155156283Srwatson * Singly-linked List functions. 156156283Srwatson */ 157156283Srwatson#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 158156283Srwatson 159156283Srwatson#define SLIST_FIRST(head) ((head)->slh_first) 160156283Srwatson 161156283Srwatson#define SLIST_FOREACH(var, head, field) \ 162156283Srwatson for ((var) = SLIST_FIRST((head)); \ 163156283Srwatson (var); \ 164156283Srwatson (var) = SLIST_NEXT((var), field)) 165156283Srwatson 166156283Srwatson#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ 167156283Srwatson for ((var) = SLIST_FIRST((head)); \ 168156283Srwatson (var) && ((tvar) = SLIST_NEXT((var), field), 1); \ 169156283Srwatson (var) = (tvar)) 170156283Srwatson 171156283Srwatson#define SLIST_FOREACH_PREVPTR(var, varp, head, field) \ 172156283Srwatson for ((varp) = &SLIST_FIRST((head)); \ 173156283Srwatson ((var) = *(varp)) != NULL; \ 174156283Srwatson (varp) = &SLIST_NEXT((var), field)) 175156283Srwatson 176156283Srwatson#define SLIST_INIT(head) do { \ 177156283Srwatson SLIST_FIRST((head)) = NULL; \ 178156283Srwatson} while (0) 179156283Srwatson 180156283Srwatson#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 181156283Srwatson SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field); \ 182156283Srwatson SLIST_NEXT((slistelm), field) = (elm); \ 183156283Srwatson} while (0) 184156283Srwatson 185156283Srwatson#define SLIST_INSERT_HEAD(head, elm, field) do { \ 186156283Srwatson SLIST_NEXT((elm), field) = SLIST_FIRST((head)); \ 187156283Srwatson SLIST_FIRST((head)) = (elm); \ 188156283Srwatson} while (0) 189156283Srwatson 190156283Srwatson#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 191156283Srwatson 192156283Srwatson#define SLIST_REMOVE(head, elm, type, field) do { \ 193156283Srwatson if (SLIST_FIRST((head)) == (elm)) { \ 194156283Srwatson SLIST_REMOVE_HEAD((head), field); \ 195156283Srwatson } \ 196156283Srwatson else { \ 197156283Srwatson struct type *curelm = SLIST_FIRST((head)); \ 198156283Srwatson while (SLIST_NEXT(curelm, field) != (elm)) \ 199156283Srwatson curelm = SLIST_NEXT(curelm, field); \ 200156283Srwatson SLIST_NEXT(curelm, field) = \ 201156283Srwatson SLIST_NEXT(SLIST_NEXT(curelm, field), field); \ 202156283Srwatson } \ 203156283Srwatson TRASHIT((elm)->field.sle_next); \ 204156283Srwatson} while (0) 205156283Srwatson 206156283Srwatson#define SLIST_REMOVE_HEAD(head, field) do { \ 207156283Srwatson SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field); \ 208156283Srwatson} while (0) 209156283Srwatson 210156283Srwatson/* 211156283Srwatson * Singly-linked Tail queue declarations. 212156283Srwatson */ 213156283Srwatson#define STAILQ_HEAD(name, type) \ 214156283Srwatsonstruct name { \ 215156283Srwatson struct type *stqh_first;/* first element */ \ 216156283Srwatson struct type **stqh_last;/* addr of last next element */ \ 217156283Srwatson} 218156283Srwatson 219156283Srwatson#define STAILQ_HEAD_INITIALIZER(head) \ 220156283Srwatson { NULL, &(head).stqh_first } 221156283Srwatson 222156283Srwatson#define STAILQ_ENTRY(type) \ 223156283Srwatsonstruct { \ 224156283Srwatson struct type *stqe_next; /* next element */ \ 225156283Srwatson} 226156283Srwatson 227156283Srwatson/* 228156283Srwatson * Singly-linked Tail queue functions. 229156283Srwatson */ 230156283Srwatson#define STAILQ_CONCAT(head1, head2) do { \ 231156283Srwatson if (!STAILQ_EMPTY((head2))) { \ 232156283Srwatson *(head1)->stqh_last = (head2)->stqh_first; \ 233156283Srwatson (head1)->stqh_last = (head2)->stqh_last; \ 234156283Srwatson STAILQ_INIT((head2)); \ 235156283Srwatson } \ 236156283Srwatson} while (0) 237156283Srwatson 238156283Srwatson#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 239156283Srwatson 240156283Srwatson#define STAILQ_FIRST(head) ((head)->stqh_first) 241156283Srwatson 242156283Srwatson#define STAILQ_FOREACH(var, head, field) \ 243156283Srwatson for((var) = STAILQ_FIRST((head)); \ 244156283Srwatson (var); \ 245156283Srwatson (var) = STAILQ_NEXT((var), field)) 246156283Srwatson 247156283Srwatson 248156283Srwatson#define STAILQ_FOREACH_SAFE(var, head, field, tvar) \ 249156283Srwatson for ((var) = STAILQ_FIRST((head)); \ 250156283Srwatson (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \ 251156283Srwatson (var) = (tvar)) 252156283Srwatson 253156283Srwatson#define STAILQ_INIT(head) do { \ 254156283Srwatson STAILQ_FIRST((head)) = NULL; \ 255156283Srwatson (head)->stqh_last = &STAILQ_FIRST((head)); \ 256156283Srwatson} while (0) 257156283Srwatson 258156283Srwatson#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 259156283Srwatson if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\ 260156283Srwatson (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 261156283Srwatson STAILQ_NEXT((tqelm), field) = (elm); \ 262156283Srwatson} while (0) 263156283Srwatson 264156283Srwatson#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 265156283Srwatson if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL) \ 266156283Srwatson (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 267156283Srwatson STAILQ_FIRST((head)) = (elm); \ 268156283Srwatson} while (0) 269156283Srwatson 270156283Srwatson#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 271156283Srwatson STAILQ_NEXT((elm), field) = NULL; \ 272156283Srwatson *(head)->stqh_last = (elm); \ 273156283Srwatson (head)->stqh_last = &STAILQ_NEXT((elm), field); \ 274156283Srwatson} while (0) 275156283Srwatson 276156283Srwatson#define STAILQ_LAST(head, type, field) \ 277156283Srwatson (STAILQ_EMPTY((head)) ? \ 278156283Srwatson NULL : \ 279156283Srwatson ((struct type *) \ 280156283Srwatson ((char *)((head)->stqh_last) - __offsetof(struct type, field)))) 281156283Srwatson 282156283Srwatson#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 283156283Srwatson 284156283Srwatson#define STAILQ_REMOVE(head, elm, type, field) do { \ 285156283Srwatson if (STAILQ_FIRST((head)) == (elm)) { \ 286156283Srwatson STAILQ_REMOVE_HEAD((head), field); \ 287156283Srwatson } \ 288156283Srwatson else { \ 289156283Srwatson struct type *curelm = STAILQ_FIRST((head)); \ 290156283Srwatson while (STAILQ_NEXT(curelm, field) != (elm)) \ 291156283Srwatson curelm = STAILQ_NEXT(curelm, field); \ 292156283Srwatson if ((STAILQ_NEXT(curelm, field) = \ 293156283Srwatson STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\ 294156283Srwatson (head)->stqh_last = &STAILQ_NEXT((curelm), field);\ 295156283Srwatson } \ 296156283Srwatson TRASHIT((elm)->field.stqe_next); \ 297156283Srwatson} while (0) 298156283Srwatson 299156283Srwatson#define STAILQ_REMOVE_HEAD(head, field) do { \ 300156283Srwatson if ((STAILQ_FIRST((head)) = \ 301156283Srwatson STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL) \ 302156283Srwatson (head)->stqh_last = &STAILQ_FIRST((head)); \ 303156283Srwatson} while (0) 304156283Srwatson 305156283Srwatson#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ 306156283Srwatson if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL) \ 307156283Srwatson (head)->stqh_last = &STAILQ_FIRST((head)); \ 308156283Srwatson} while (0) 309156283Srwatson 310156283Srwatson/* 311156283Srwatson * List declarations. 312156283Srwatson */ 313156283Srwatson#define LIST_HEAD(name, type) \ 314156283Srwatsonstruct name { \ 315156283Srwatson struct type *lh_first; /* first element */ \ 316156283Srwatson} 317156283Srwatson 318156283Srwatson#define LIST_HEAD_INITIALIZER(head) \ 319156283Srwatson { NULL } 320156283Srwatson 321156283Srwatson#define LIST_ENTRY(type) \ 322156283Srwatsonstruct { \ 323156283Srwatson struct type *le_next; /* next element */ \ 324156283Srwatson struct type **le_prev; /* address of previous next element */ \ 325156283Srwatson} 326156283Srwatson 327156283Srwatson/* 328156283Srwatson * List functions. 329156283Srwatson */ 330156283Srwatson 331156283Srwatson#if (defined(_KERNEL) && defined(INVARIANTS)) || defined(QUEUE_MACRO_DEBUG) 332156283Srwatson#define QMD_LIST_CHECK_HEAD(head, field) do { \ 333156283Srwatson if (LIST_FIRST((head)) != NULL && \ 334156283Srwatson LIST_FIRST((head))->field.le_prev != \ 335156283Srwatson &LIST_FIRST((head))) \ 336156283Srwatson panic("Bad list head %p first->prev != head", (head)); \ 337156283Srwatson} while (0) 338156283Srwatson 339156283Srwatson#define QMD_LIST_CHECK_NEXT(elm, field) do { \ 340156283Srwatson if (LIST_NEXT((elm), field) != NULL && \ 341156283Srwatson LIST_NEXT((elm), field)->field.le_prev != \ 342156283Srwatson &((elm)->field.le_next)) \ 343156283Srwatson panic("Bad link elm %p next->prev != elm", (elm)); \ 344156283Srwatson} while (0) 345156283Srwatson 346156283Srwatson#define QMD_LIST_CHECK_PREV(elm, field) do { \ 347156283Srwatson if (*(elm)->field.le_prev != (elm)) \ 348156283Srwatson panic("Bad link elm %p prev->next != elm", (elm)); \ 349156283Srwatson} while (0) 350156283Srwatson#else 351156283Srwatson#define QMD_LIST_CHECK_HEAD(head, field) 352156283Srwatson#define QMD_LIST_CHECK_NEXT(elm, field) 353156283Srwatson#define QMD_LIST_CHECK_PREV(elm, field) 354156283Srwatson#endif /* (_KERNEL && INVARIANTS) || QUEUE_MACRO_DEBUG */ 355156283Srwatson 356156283Srwatson#define LIST_EMPTY(head) ((head)->lh_first == NULL) 357156283Srwatson 358156283Srwatson#define LIST_FIRST(head) ((head)->lh_first) 359156283Srwatson 360156283Srwatson#define LIST_FOREACH(var, head, field) \ 361156283Srwatson for ((var) = LIST_FIRST((head)); \ 362156283Srwatson (var); \ 363156283Srwatson (var) = LIST_NEXT((var), field)) 364156283Srwatson 365156283Srwatson#define LIST_FOREACH_SAFE(var, head, field, tvar) \ 366156283Srwatson for ((var) = LIST_FIRST((head)); \ 367156283Srwatson (var) && ((tvar) = LIST_NEXT((var), field), 1); \ 368156283Srwatson (var) = (tvar)) 369156283Srwatson 370156283Srwatson#define LIST_INIT(head) do { \ 371156283Srwatson LIST_FIRST((head)) = NULL; \ 372156283Srwatson} while (0) 373156283Srwatson 374156283Srwatson#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 375156283Srwatson QMD_LIST_CHECK_NEXT(listelm, field); \ 376156283Srwatson if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\ 377156283Srwatson LIST_NEXT((listelm), field)->field.le_prev = \ 378156283Srwatson &LIST_NEXT((elm), field); \ 379156283Srwatson LIST_NEXT((listelm), field) = (elm); \ 380156283Srwatson (elm)->field.le_prev = &LIST_NEXT((listelm), field); \ 381156283Srwatson} while (0) 382156283Srwatson 383156283Srwatson#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 384156283Srwatson QMD_LIST_CHECK_PREV(listelm, field); \ 385156283Srwatson (elm)->field.le_prev = (listelm)->field.le_prev; \ 386156283Srwatson LIST_NEXT((elm), field) = (listelm); \ 387156283Srwatson *(listelm)->field.le_prev = (elm); \ 388156283Srwatson (listelm)->field.le_prev = &LIST_NEXT((elm), field); \ 389156283Srwatson} while (0) 390156283Srwatson 391156283Srwatson#define LIST_INSERT_HEAD(head, elm, field) do { \ 392156283Srwatson QMD_LIST_CHECK_HEAD((head), field); \ 393156283Srwatson if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \ 394156283Srwatson LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\ 395156283Srwatson LIST_FIRST((head)) = (elm); \ 396156283Srwatson (elm)->field.le_prev = &LIST_FIRST((head)); \ 397156283Srwatson} while (0) 398156283Srwatson 399156283Srwatson#define LIST_NEXT(elm, field) ((elm)->field.le_next) 400156283Srwatson 401156283Srwatson#define LIST_REMOVE(elm, field) do { \ 402156283Srwatson QMD_LIST_CHECK_NEXT(elm, field); \ 403156283Srwatson QMD_LIST_CHECK_PREV(elm, field); \ 404156283Srwatson if (LIST_NEXT((elm), field) != NULL) \ 405156283Srwatson LIST_NEXT((elm), field)->field.le_prev = \ 406156283Srwatson (elm)->field.le_prev; \ 407156283Srwatson *(elm)->field.le_prev = LIST_NEXT((elm), field); \ 408156283Srwatson TRASHIT((elm)->field.le_next); \ 409156283Srwatson TRASHIT((elm)->field.le_prev); \ 410156283Srwatson} while (0) 411156283Srwatson 412156283Srwatson/* 413156283Srwatson * Tail queue declarations. 414156283Srwatson */ 415156283Srwatson#define TAILQ_HEAD(name, type) \ 416156283Srwatsonstruct name { \ 417156283Srwatson struct type *tqh_first; /* first element */ \ 418156283Srwatson struct type **tqh_last; /* addr of last next element */ \ 419156283Srwatson TRACEBUF \ 420156283Srwatson} 421156283Srwatson 422156283Srwatson#define TAILQ_HEAD_INITIALIZER(head) \ 423156283Srwatson { NULL, &(head).tqh_first } 424156283Srwatson 425156283Srwatson#define TAILQ_ENTRY(type) \ 426156283Srwatsonstruct { \ 427156283Srwatson struct type *tqe_next; /* next element */ \ 428156283Srwatson struct type **tqe_prev; /* address of previous next element */ \ 429156283Srwatson TRACEBUF \ 430156283Srwatson} 431156283Srwatson 432156283Srwatson/* 433156283Srwatson * Tail queue functions. 434156283Srwatson */ 435156283Srwatson#define TAILQ_CONCAT(head1, head2, field) do { \ 436156283Srwatson if (!TAILQ_EMPTY(head2)) { \ 437156283Srwatson *(head1)->tqh_last = (head2)->tqh_first; \ 438156283Srwatson (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ 439156283Srwatson (head1)->tqh_last = (head2)->tqh_last; \ 440156283Srwatson TAILQ_INIT((head2)); \ 441156283Srwatson QMD_TRACE_HEAD(head1); \ 442156283Srwatson QMD_TRACE_HEAD(head2); \ 443156283Srwatson } \ 444156283Srwatson} while (0) 445156283Srwatson 446156283Srwatson#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 447156283Srwatson 448156283Srwatson#define TAILQ_FIRST(head) ((head)->tqh_first) 449156283Srwatson 450156283Srwatson#define TAILQ_FOREACH(var, head, field) \ 451156283Srwatson for ((var) = TAILQ_FIRST((head)); \ 452156283Srwatson (var); \ 453156283Srwatson (var) = TAILQ_NEXT((var), field)) 454156283Srwatson 455156283Srwatson#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ 456156283Srwatson for ((var) = TAILQ_FIRST((head)); \ 457156283Srwatson (var) && ((tvar) = TAILQ_NEXT((var), field), 1); \ 458156283Srwatson (var) = (tvar)) 459156283Srwatson 460156283Srwatson#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 461156283Srwatson for ((var) = TAILQ_LAST((head), headname); \ 462156283Srwatson (var); \ 463156283Srwatson (var) = TAILQ_PREV((var), headname, field)) 464156283Srwatson 465156283Srwatson#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ 466156283Srwatson for ((var) = TAILQ_LAST((head), headname); \ 467156283Srwatson (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \ 468156283Srwatson (var) = (tvar)) 469156283Srwatson 470156283Srwatson#define TAILQ_INIT(head) do { \ 471156283Srwatson TAILQ_FIRST((head)) = NULL; \ 472156283Srwatson (head)->tqh_last = &TAILQ_FIRST((head)); \ 473156283Srwatson QMD_TRACE_HEAD(head); \ 474156283Srwatson} while (0) 475156283Srwatson 476156283Srwatson#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 477156283Srwatson if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\ 478156283Srwatson TAILQ_NEXT((elm), field)->field.tqe_prev = \ 479156283Srwatson &TAILQ_NEXT((elm), field); \ 480156283Srwatson else { \ 481156283Srwatson (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 482156283Srwatson QMD_TRACE_HEAD(head); \ 483156283Srwatson } \ 484156283Srwatson TAILQ_NEXT((listelm), field) = (elm); \ 485156283Srwatson (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field); \ 486156283Srwatson QMD_TRACE_ELEM(&(elm)->field); \ 487156283Srwatson QMD_TRACE_ELEM(&listelm->field); \ 488156283Srwatson} while (0) 489156283Srwatson 490156283Srwatson#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 491156283Srwatson (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 492156283Srwatson TAILQ_NEXT((elm), field) = (listelm); \ 493156283Srwatson *(listelm)->field.tqe_prev = (elm); \ 494156283Srwatson (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field); \ 495156283Srwatson QMD_TRACE_ELEM(&(elm)->field); \ 496156283Srwatson QMD_TRACE_ELEM(&listelm->field); \ 497156283Srwatson} while (0) 498156283Srwatson 499156283Srwatson#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 500156283Srwatson if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL) \ 501156283Srwatson TAILQ_FIRST((head))->field.tqe_prev = \ 502156283Srwatson &TAILQ_NEXT((elm), field); \ 503156283Srwatson else \ 504156283Srwatson (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 505156283Srwatson TAILQ_FIRST((head)) = (elm); \ 506156283Srwatson (elm)->field.tqe_prev = &TAILQ_FIRST((head)); \ 507156283Srwatson QMD_TRACE_HEAD(head); \ 508156283Srwatson QMD_TRACE_ELEM(&(elm)->field); \ 509156283Srwatson} while (0) 510156283Srwatson 511156283Srwatson#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 512156283Srwatson TAILQ_NEXT((elm), field) = NULL; \ 513156283Srwatson (elm)->field.tqe_prev = (head)->tqh_last; \ 514156283Srwatson *(head)->tqh_last = (elm); \ 515156283Srwatson (head)->tqh_last = &TAILQ_NEXT((elm), field); \ 516156283Srwatson QMD_TRACE_HEAD(head); \ 517156283Srwatson QMD_TRACE_ELEM(&(elm)->field); \ 518156283Srwatson} while (0) 519156283Srwatson 520156283Srwatson#define TAILQ_LAST(head, headname) \ 521156283Srwatson (*(((struct headname *)((head)->tqh_last))->tqh_last)) 522156283Srwatson 523156283Srwatson#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 524156283Srwatson 525156283Srwatson#define TAILQ_PREV(elm, headname, field) \ 526156283Srwatson (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 527156283Srwatson 528156283Srwatson#define TAILQ_REMOVE(head, elm, field) do { \ 529156283Srwatson if ((TAILQ_NEXT((elm), field)) != NULL) \ 530156283Srwatson TAILQ_NEXT((elm), field)->field.tqe_prev = \ 531156283Srwatson (elm)->field.tqe_prev; \ 532156283Srwatson else { \ 533156283Srwatson (head)->tqh_last = (elm)->field.tqe_prev; \ 534156283Srwatson QMD_TRACE_HEAD(head); \ 535156283Srwatson } \ 536156283Srwatson *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \ 537156283Srwatson TRASHIT((elm)->field.tqe_next); \ 538156283Srwatson TRASHIT((elm)->field.tqe_prev); \ 539156283Srwatson QMD_TRACE_ELEM(&(elm)->field); \ 540156283Srwatson} while (0) 541156283Srwatson 542156283Srwatson#endif /* !_COMPAT_QUEUE_H_ */ 543