queue.h revision 42382
1283424Sdchagin/* 2283424Sdchagin * Copyright (c) 1991, 1993 3283424Sdchagin * The Regents of the University of California. All rights reserved. 4283424Sdchagin * 5283424Sdchagin * Redistribution and use in source and binary forms, with or without 6283424Sdchagin * modification, are permitted provided that the following conditions 7283424Sdchagin * are met: 8283424Sdchagin * 1. Redistributions of source code must retain the above copyright 9283424Sdchagin * notice, this list of conditions and the following disclaimer. 10283424Sdchagin * 2. Redistributions in binary form must reproduce the above copyright 11283424Sdchagin * notice, this list of conditions and the following disclaimer in the 12283424Sdchagin * documentation and/or other materials provided with the distribution. 13283424Sdchagin * 3. All advertising materials mentioning features or use of this software 14283424Sdchagin * must display the following acknowledgement: 15283424Sdchagin * This product includes software developed by the University of 16283424Sdchagin * California, Berkeley and its contributors. 17283424Sdchagin * 4. Neither the name of the University nor the names of its contributors 18283424Sdchagin * may be used to endorse or promote products derived from this software 19283424Sdchagin * without specific prior written permission. 20283424Sdchagin * 21283424Sdchagin * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22283424Sdchagin * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23283424Sdchagin * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24283424Sdchagin * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25283424Sdchagin * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26283424Sdchagin * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27283424Sdchagin * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28283424Sdchagin * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29283424Sdchagin * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30283424Sdchagin * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31283424Sdchagin * SUCH DAMAGE. 32283424Sdchagin * 33283424Sdchagin * @(#)queue.h 8.5 (Berkeley) 8/20/94 34283424Sdchagin * $Id: queue.h,v 1.23 1999/01/06 20:03:11 n_hibma Exp $ 35283424Sdchagin */ 36283424Sdchagin 37283424Sdchagin#ifndef _SYS_QUEUE_H_ 38283424Sdchagin#define _SYS_QUEUE_H_ 39283424Sdchagin 40283424Sdchagin/* 41283424Sdchagin * This file defines five types of data structures: singly-linked lists, 42283424Sdchagin * slingly-linked tail queues, lists, tail queues, and circular queues. 43283424Sdchagin * 44283424Sdchagin * A singly-linked list is headed by a single forward pointer. The elements 45283424Sdchagin * are singly linked for minimum space and pointer manipulation overhead at 46283424Sdchagin * the expense of O(n) removal for arbitrary elements. New elements can be 47283424Sdchagin * added to the list after an existing element or at the head of the list. 48283424Sdchagin * Elements being removed from the head of the list should use the explicit 49283424Sdchagin * macro for this purpose for optimum efficiency. A singly-linked list may 50283424Sdchagin * only be traversed in the forward direction. Singly-linked lists are ideal 51283424Sdchagin * for applications with large datasets and few or no removals or for 52283424Sdchagin * implementing a LIFO queue. 53283424Sdchagin * 54283424Sdchagin * A singly-linked tail queue is headed by a pair of pointers, one to the 55283424Sdchagin * head of the list and the other to the tail of the list. The elements are 56283424Sdchagin * singly linked for minimum space and pointer manipulation overhead at the 57283424Sdchagin * expense of O(n) removal for arbitrary elements. New elements can be added 58283424Sdchagin * to the list after an existing element, at the head of the list, or at the 59283424Sdchagin * end of the list. Elements being removed from the head of the tail queue 60283424Sdchagin * should use the explicit macro for this purpose for optimum efficiency. 61283424Sdchagin * A singly-linked tail queue may only be traversed in the forward direction. 62283424Sdchagin * Singly-linked tail queues are ideal for applications with large datasets 63283424Sdchagin * and few or no removals or for implementing a FIFO queue. 64283424Sdchagin * 65283424Sdchagin * A list is headed by a single forward pointer (or an array of forward 66283424Sdchagin * pointers for a hash table header). The elements are doubly linked 67283424Sdchagin * so that an arbitrary element can be removed without a need to 68283424Sdchagin * traverse the list. New elements can be added to the list before 69283424Sdchagin * or after an existing element or at the head of the list. A list 70283424Sdchagin * may only be traversed in the forward direction. 71283424Sdchagin * 72283424Sdchagin * A tail queue is headed by a pair of pointers, one to the head of the 73283424Sdchagin * list and the other to the tail of the list. The elements are doubly 74283424Sdchagin * linked so that an arbitrary element can be removed without a need to 75283424Sdchagin * traverse the list. New elements can be added to the list before or 76283424Sdchagin * after an existing element, at the head of the list, or at the end of 77283424Sdchagin * the list. A tail queue may only be traversed in the forward direction. 78283424Sdchagin * 79283424Sdchagin * A circle queue is headed by a pair of pointers, one to the head of the 80283424Sdchagin * list and the other to the tail of the list. The elements are doubly 81283424Sdchagin * linked so that an arbitrary element can be removed without a need to 82283424Sdchagin * traverse the list. New elements can be added to the list before or after 83283424Sdchagin * an existing element, at the head of the list, or at the end of the list. 84283424Sdchagin * A circle queue may be traversed in either direction, but has a more 85283424Sdchagin * complex end of list detection. 86283424Sdchagin * 87283424Sdchagin * For details on the use of these macros, see the queue(3) manual page. 88283424Sdchagin * 89283424Sdchagin * 90283424Sdchagin * SLIST LIST STAILQ TAILQ CIRCLEQ 91283424Sdchagin * _HEAD + + + + + 92283424Sdchagin * _ENTRY + + + + + 93283424Sdchagin * _INIT + + + + + 94283424Sdchagin * _EMPTY + + + + + 95283424Sdchagin * _FIRST + + + + + 96283424Sdchagin * _NEXT + + + + + 97283424Sdchagin * _PREV - - - + + 98283424Sdchagin * _LAST - - + + + 99283424Sdchagin * _FOREACH + + - + + 100283424Sdchagin * _INSERT_HEAD + + + + + 101283424Sdchagin * _INSERT_BEFORE - + - + + 102283424Sdchagin * _INSERT_AFTER + + + + + 103283424Sdchagin * _INSERT_TAIL - - + + + 104283424Sdchagin * _REMOVE_HEAD + - + - - 105283424Sdchagin * _REMOVE + + + + + 106283424Sdchagin * 107283424Sdchagin */ 108283424Sdchagin 109283424Sdchagin/* 110283424Sdchagin * Singly-linked List definitions. 111283424Sdchagin */ 112283424Sdchagin#define SLIST_HEAD(name, type) \ 113283424Sdchaginstruct name { \ 114283424Sdchagin struct type *slh_first; /* first element */ \ 115283424Sdchagin} 116283424Sdchagin 117283424Sdchagin#define SLIST_ENTRY(type) \ 118283424Sdchaginstruct { \ 119283424Sdchagin struct type *sle_next; /* next element */ \ 120283424Sdchagin} 121283424Sdchagin 122283424Sdchagin/* 123283424Sdchagin * Singly-linked List functions. 124283424Sdchagin */ 125283424Sdchagin#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 126283424Sdchagin 127283424Sdchagin#define SLIST_FIRST(head) ((head)->slh_first) 128283424Sdchagin 129283424Sdchagin#define SLIST_FOREACH(var, head, field) \ 130283424Sdchagin for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next) 131283424Sdchagin 132283424Sdchagin#define SLIST_INIT(head) { \ 133283424Sdchagin (head)->slh_first = NULL; \ 134283424Sdchagin} 135283424Sdchagin 136283424Sdchagin#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 137283424Sdchagin (elm)->field.sle_next = (slistelm)->field.sle_next; \ 138283424Sdchagin (slistelm)->field.sle_next = (elm); \ 139283424Sdchagin} while (0) 140283424Sdchagin 141283424Sdchagin#define SLIST_INSERT_HEAD(head, elm, field) do { \ 142283424Sdchagin (elm)->field.sle_next = (head)->slh_first; \ 143283424Sdchagin (head)->slh_first = (elm); \ 144283424Sdchagin} while (0) 145283424Sdchagin 146283424Sdchagin#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 147283424Sdchagin 148283424Sdchagin#define SLIST_REMOVE_HEAD(head, field) do { \ 149283424Sdchagin (head)->slh_first = (head)->slh_first->field.sle_next; \ 150283424Sdchagin} while (0) 151283424Sdchagin 152283424Sdchagin#define SLIST_REMOVE(head, elm, type, field) do { \ 153283424Sdchagin if ((head)->slh_first == (elm)) { \ 154283424Sdchagin SLIST_REMOVE_HEAD((head), field); \ 155283424Sdchagin } \ 156283424Sdchagin else { \ 157283424Sdchagin struct type *curelm = (head)->slh_first; \ 158283424Sdchagin while( curelm->field.sle_next != (elm) ) \ 159283424Sdchagin curelm = curelm->field.sle_next; \ 160283424Sdchagin curelm->field.sle_next = \ 161283424Sdchagin curelm->field.sle_next->field.sle_next; \ 162283424Sdchagin } \ 163283424Sdchagin} while (0) 164283424Sdchagin 165283424Sdchagin/* 166283424Sdchagin * Singly-linked Tail queue definitions. 167283424Sdchagin */ 168283424Sdchagin#define STAILQ_HEAD(name, type) \ 169283424Sdchaginstruct name { \ 170283424Sdchagin struct type *stqh_first;/* first element */ \ 171283424Sdchagin struct type **stqh_last;/* addr of last next element */ \ 172283424Sdchagin} 173283424Sdchagin 174283424Sdchagin#define STAILQ_HEAD_INITIALIZER(head) \ 175283424Sdchagin { NULL, &(head).stqh_first } 176283424Sdchagin 177283424Sdchagin#define STAILQ_ENTRY(type) \ 178283424Sdchaginstruct { \ 179283424Sdchagin struct type *stqe_next; /* next element */ \ 180283424Sdchagin} 181283424Sdchagin 182283424Sdchagin/* 183283424Sdchagin * Singly-linked Tail queue functions. 184283424Sdchagin */ 185283424Sdchagin#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 186283424Sdchagin 187283424Sdchagin#define STAILQ_INIT(head) do { \ 188283424Sdchagin (head)->stqh_first = NULL; \ 189283424Sdchagin (head)->stqh_last = &(head)->stqh_first; \ 190283424Sdchagin} while (0) 191283424Sdchagin 192283424Sdchagin#define STAILQ_FIRST(head) ((head)->stqh_first) 193283424Sdchagin#define STAILQ_LAST(head) (*(head)->stqh_last) 194283424Sdchagin 195283424Sdchagin#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 196283424Sdchagin if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \ 197283424Sdchagin (head)->stqh_last = &(elm)->field.stqe_next; \ 198283424Sdchagin (head)->stqh_first = (elm); \ 199283424Sdchagin} while (0) 200283424Sdchagin 201283424Sdchagin#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 202283424Sdchagin (elm)->field.stqe_next = NULL; \ 203283424Sdchagin *(head)->stqh_last = (elm); \ 204283424Sdchagin (head)->stqh_last = &(elm)->field.stqe_next; \ 205283424Sdchagin} while (0) 206283424Sdchagin 207283424Sdchagin#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 208283424Sdchagin if (((elm)->field.stqe_next = (tqelm)->field.stqe_next) == NULL)\ 209283424Sdchagin (head)->stqh_last = &(elm)->field.stqe_next; \ 210283424Sdchagin (tqelm)->field.stqe_next = (elm); \ 211283424Sdchagin} while (0) 212283424Sdchagin 213283424Sdchagin#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 214283424Sdchagin 215283424Sdchagin#define STAILQ_REMOVE_HEAD(head, field) do { \ 216283424Sdchagin if (((head)->stqh_first = \ 217283424Sdchagin (head)->stqh_first->field.stqe_next) == NULL) \ 218283424Sdchagin (head)->stqh_last = &(head)->stqh_first; \ 219283424Sdchagin} while (0) 220283424Sdchagin 221283424Sdchagin#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \ 222283424Sdchagin if (((head)->stqh_first = (elm)->field.stqe_next) == NULL) \ 223283424Sdchagin (head)->stqh_last = &(head)->stqh_first; \ 224283424Sdchagin} while (0) 225283424Sdchagin 226283424Sdchagin 227283424Sdchagin#define STAILQ_REMOVE(head, elm, type, field) do { \ 228283424Sdchagin if ((head)->stqh_first == (elm)) { \ 229283424Sdchagin STAILQ_REMOVE_HEAD(head, field); \ 230283424Sdchagin } \ 231283424Sdchagin else { \ 232283424Sdchagin struct type *curelm = (head)->stqh_first; \ 233283424Sdchagin while( curelm->field.stqe_next != (elm) ) \ 234283424Sdchagin curelm = curelm->field.stqe_next; \ 235283424Sdchagin if((curelm->field.stqe_next = \ 236283424Sdchagin curelm->field.stqe_next->field.stqe_next) == NULL) \ 237283424Sdchagin (head)->stqh_last = &(curelm)->field.stqe_next; \ 238283424Sdchagin } \ 239283424Sdchagin} while (0) 240283424Sdchagin 241283424Sdchagin/* 242283424Sdchagin * List definitions. 243283424Sdchagin */ 244283424Sdchagin#define LIST_HEAD(name, type) \ 245283424Sdchaginstruct name { \ 246283424Sdchagin struct type *lh_first; /* first element */ \ 247283424Sdchagin} 248283424Sdchagin 249283424Sdchagin#define LIST_HEAD_INITIALIZER(head) \ 250283424Sdchagin { NULL } 251283424Sdchagin 252283424Sdchagin#define LIST_ENTRY(type) \ 253283424Sdchaginstruct { \ 254283424Sdchagin struct type *le_next; /* next element */ \ 255283424Sdchagin struct type **le_prev; /* address of previous next element */ \ 256283424Sdchagin} 257283424Sdchagin 258283424Sdchagin/* 259283424Sdchagin * List functions. 260283424Sdchagin */ 261283424Sdchagin 262283424Sdchagin#define LIST_EMPTY(head) ((head)->lh_first == NULL) 263283424Sdchagin 264283424Sdchagin#define LIST_FIRST(head) ((head)->lh_first) 265283424Sdchagin 266283424Sdchagin#define LIST_FOREACH(var, head, field) \ 267283424Sdchagin for((var) = (head)->lh_first; (var); (var) = (var)->field.le_next) 268283424Sdchagin 269283424Sdchagin#define LIST_INIT(head) do { \ 270283424Sdchagin (head)->lh_first = NULL; \ 271283424Sdchagin} while (0) 272283424Sdchagin 273283424Sdchagin#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 274283424Sdchagin if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 275283424Sdchagin (listelm)->field.le_next->field.le_prev = \ 276283424Sdchagin &(elm)->field.le_next; \ 277283424Sdchagin (listelm)->field.le_next = (elm); \ 278283424Sdchagin (elm)->field.le_prev = &(listelm)->field.le_next; \ 279283424Sdchagin} while (0) 280283424Sdchagin 281283424Sdchagin#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 282283424Sdchagin (elm)->field.le_prev = (listelm)->field.le_prev; \ 283283424Sdchagin (elm)->field.le_next = (listelm); \ 284283424Sdchagin *(listelm)->field.le_prev = (elm); \ 285283424Sdchagin (listelm)->field.le_prev = &(elm)->field.le_next; \ 286283424Sdchagin} while (0) 287283424Sdchagin 288283424Sdchagin#define LIST_INSERT_HEAD(head, elm, field) do { \ 289283424Sdchagin if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 290283424Sdchagin (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 291283424Sdchagin (head)->lh_first = (elm); \ 292283424Sdchagin (elm)->field.le_prev = &(head)->lh_first; \ 293283424Sdchagin} while (0) 294283424Sdchagin 295283424Sdchagin#define LIST_NEXT(elm, field) ((elm)->field.le_next) 296283424Sdchagin 297283424Sdchagin#define LIST_REMOVE(elm, field) do { \ 298283424Sdchagin if ((elm)->field.le_next != NULL) \ 299283424Sdchagin (elm)->field.le_next->field.le_prev = \ 300283424Sdchagin (elm)->field.le_prev; \ 301283424Sdchagin *(elm)->field.le_prev = (elm)->field.le_next; \ 302283424Sdchagin} while (0) 303283424Sdchagin 304283424Sdchagin/* 305283424Sdchagin * Tail queue definitions. 306283424Sdchagin */ 307283424Sdchagin#define TAILQ_HEAD(name, type) \ 308283424Sdchaginstruct name { \ 309283424Sdchagin struct type *tqh_first; /* first element */ \ 310283424Sdchagin struct type **tqh_last; /* addr of last next element */ \ 311283424Sdchagin} 312283424Sdchagin 313283424Sdchagin#define TAILQ_HEAD_INITIALIZER(head) \ 314283424Sdchagin { NULL, &(head).tqh_first } 315283424Sdchagin 316283424Sdchagin#define TAILQ_ENTRY(type) \ 317283424Sdchaginstruct { \ 318283424Sdchagin struct type *tqe_next; /* next element */ \ 319283424Sdchagin struct type **tqe_prev; /* address of previous next element */ \ 320283424Sdchagin} 321283424Sdchagin 322283424Sdchagin/* 323283424Sdchagin * Tail queue functions. 324283424Sdchagin */ 325283424Sdchagin#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 326283424Sdchagin 327283424Sdchagin#define TAILQ_FOREACH(var, head, field) \ 328283424Sdchagin for (var = TAILQ_FIRST(head); var; var = TAILQ_NEXT(var, field)) 329283424Sdchagin 330283424Sdchagin#define TAILQ_FIRST(head) ((head)->tqh_first) 331283424Sdchagin 332283424Sdchagin#define TAILQ_LAST(head, headname) \ 333283424Sdchagin (*(((struct headname *)((head)->tqh_last))->tqh_last)) 334283424Sdchagin 335283424Sdchagin#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 336283424Sdchagin 337283424Sdchagin#define TAILQ_PREV(elm, headname, field) \ 338283424Sdchagin (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 339283424Sdchagin 340283424Sdchagin#define TAILQ_INIT(head) do { \ 341283424Sdchagin (head)->tqh_first = NULL; \ 342283424Sdchagin (head)->tqh_last = &(head)->tqh_first; \ 343283424Sdchagin} while (0) 344283424Sdchagin 345283424Sdchagin#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 346283424Sdchagin if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 347283424Sdchagin (head)->tqh_first->field.tqe_prev = \ 348283424Sdchagin &(elm)->field.tqe_next; \ 349283424Sdchagin else \ 350283424Sdchagin (head)->tqh_last = &(elm)->field.tqe_next; \ 351283424Sdchagin (head)->tqh_first = (elm); \ 352283424Sdchagin (elm)->field.tqe_prev = &(head)->tqh_first; \ 353283424Sdchagin} while (0) 354283424Sdchagin 355283424Sdchagin#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 356283424Sdchagin (elm)->field.tqe_next = NULL; \ 357283424Sdchagin (elm)->field.tqe_prev = (head)->tqh_last; \ 358283424Sdchagin *(head)->tqh_last = (elm); \ 359283424Sdchagin (head)->tqh_last = &(elm)->field.tqe_next; \ 360283424Sdchagin} while (0) 361283424Sdchagin 362283424Sdchagin#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 363283424Sdchagin if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 364283424Sdchagin (elm)->field.tqe_next->field.tqe_prev = \ 365283424Sdchagin &(elm)->field.tqe_next; \ 366283424Sdchagin else \ 367283424Sdchagin (head)->tqh_last = &(elm)->field.tqe_next; \ 368283424Sdchagin (listelm)->field.tqe_next = (elm); \ 369283424Sdchagin (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 370283424Sdchagin} while (0) 371283424Sdchagin 372283424Sdchagin#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 373283424Sdchagin (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 374283424Sdchagin (elm)->field.tqe_next = (listelm); \ 375283424Sdchagin *(listelm)->field.tqe_prev = (elm); \ 376283424Sdchagin (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 377283424Sdchagin} while (0) 378283424Sdchagin 379283424Sdchagin#define TAILQ_REMOVE(head, elm, field) do { \ 380283424Sdchagin if (((elm)->field.tqe_next) != NULL) \ 381283424Sdchagin (elm)->field.tqe_next->field.tqe_prev = \ 382283424Sdchagin (elm)->field.tqe_prev; \ 383283424Sdchagin else \ 384283424Sdchagin (head)->tqh_last = (elm)->field.tqe_prev; \ 385283424Sdchagin *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 386283424Sdchagin} while (0) 387283424Sdchagin 388283424Sdchagin/* 389283424Sdchagin * Circular queue definitions. 390283424Sdchagin */ 391283424Sdchagin#define CIRCLEQ_HEAD(name, type) \ 392283424Sdchaginstruct name { \ 393283424Sdchagin struct type *cqh_first; /* first element */ \ 394283424Sdchagin struct type *cqh_last; /* last element */ \ 395283424Sdchagin} 396283424Sdchagin 397283424Sdchagin#define CIRCLEQ_ENTRY(type) \ 398283424Sdchaginstruct { \ 399283424Sdchagin struct type *cqe_next; /* next element */ \ 400283424Sdchagin struct type *cqe_prev; /* previous element */ \ 401283424Sdchagin} 402283424Sdchagin 403283424Sdchagin/* 404283424Sdchagin * Circular queue functions. 405283424Sdchagin */ 406283424Sdchagin#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head)) 407283424Sdchagin 408283424Sdchagin#define CIRCLEQ_FIRST(head) ((head)->cqh_first) 409283424Sdchagin 410283424Sdchagin#define CIRCLEQ_FOREACH(var, head, field) \ 411283424Sdchagin for((var) = (head)->cqh_first; \ 412283424Sdchagin (var) != (void *)(head); \ 413283424Sdchagin (var) = (var)->field.cqe_next) 414283424Sdchagin 415283424Sdchagin#define CIRCLEQ_INIT(head) do { \ 416283424Sdchagin (head)->cqh_first = (void *)(head); \ 417283424Sdchagin (head)->cqh_last = (void *)(head); \ 418283424Sdchagin} while (0) 419283424Sdchagin 420283424Sdchagin#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 421283424Sdchagin (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 422283424Sdchagin (elm)->field.cqe_prev = (listelm); \ 423283424Sdchagin if ((listelm)->field.cqe_next == (void *)(head)) \ 424283424Sdchagin (head)->cqh_last = (elm); \ 425283424Sdchagin else \ 426283424Sdchagin (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 427283424Sdchagin (listelm)->field.cqe_next = (elm); \ 428283424Sdchagin} while (0) 429283424Sdchagin 430283424Sdchagin#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ 431283424Sdchagin (elm)->field.cqe_next = (listelm); \ 432283424Sdchagin (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 433 if ((listelm)->field.cqe_prev == (void *)(head)) \ 434 (head)->cqh_first = (elm); \ 435 else \ 436 (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 437 (listelm)->field.cqe_prev = (elm); \ 438} while (0) 439 440#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ 441 (elm)->field.cqe_next = (head)->cqh_first; \ 442 (elm)->field.cqe_prev = (void *)(head); \ 443 if ((head)->cqh_last == (void *)(head)) \ 444 (head)->cqh_last = (elm); \ 445 else \ 446 (head)->cqh_first->field.cqe_prev = (elm); \ 447 (head)->cqh_first = (elm); \ 448} while (0) 449 450#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ 451 (elm)->field.cqe_next = (void *)(head); \ 452 (elm)->field.cqe_prev = (head)->cqh_last; \ 453 if ((head)->cqh_first == (void *)(head)) \ 454 (head)->cqh_first = (elm); \ 455 else \ 456 (head)->cqh_last->field.cqe_next = (elm); \ 457 (head)->cqh_last = (elm); \ 458} while (0) 459 460#define CIRCLEQ_LAST(head) ((head)->cqh_last) 461 462#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next) 463 464#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev) 465 466#define CIRCLEQ_REMOVE(head, elm, field) do { \ 467 if ((elm)->field.cqe_next == (void *)(head)) \ 468 (head)->cqh_last = (elm)->field.cqe_prev; \ 469 else \ 470 (elm)->field.cqe_next->field.cqe_prev = \ 471 (elm)->field.cqe_prev; \ 472 if ((elm)->field.cqe_prev == (void *)(head)) \ 473 (head)->cqh_first = (elm)->field.cqe_next; \ 474 else \ 475 (elm)->field.cqe_prev->field.cqe_next = \ 476 (elm)->field.cqe_next; \ 477} while (0) 478 479#ifdef KERNEL 480 481/* 482 * XXX insque() and remque() are an old way of handling certain queues. 483 * They bogusly assumes that all queue heads look alike. 484 */ 485 486struct quehead { 487 struct quehead *qh_link; 488 struct quehead *qh_rlink; 489}; 490 491#ifdef __GNUC__ 492 493static __inline void 494insque(void *a, void *b) 495{ 496 struct quehead *element = a, *head = b; 497 498 element->qh_link = head->qh_link; 499 element->qh_rlink = head; 500 head->qh_link = element; 501 element->qh_link->qh_rlink = element; 502} 503 504static __inline void 505remque(void *a) 506{ 507 struct quehead *element = a; 508 509 element->qh_link->qh_rlink = element->qh_rlink; 510 element->qh_rlink->qh_link = element->qh_link; 511 element->qh_rlink = 0; 512} 513 514#else /* !__GNUC__ */ 515 516void insque __P((void *a, void *b)); 517void remque __P((void *a)); 518 519#endif /* __GNUC__ */ 520 521#endif /* KERNEL */ 522 523#endif /* !_SYS_QUEUE_H_ */ 524