queue.h revision 48641
1177633Sdfr/* 2177633Sdfr * Copyright (c) 1991, 1993 3177633Sdfr * The Regents of the University of California. All rights reserved. 4177633Sdfr * 5177633Sdfr * Redistribution and use in source and binary forms, with or without 6177633Sdfr * modification, are permitted provided that the following conditions 7177633Sdfr * are met: 8177633Sdfr * 1. Redistributions of source code must retain the above copyright 9177633Sdfr * notice, this list of conditions and the following disclaimer. 10177633Sdfr * 2. Redistributions in binary form must reproduce the above copyright 11177633Sdfr * notice, this list of conditions and the following disclaimer in the 12177633Sdfr * documentation and/or other materials provided with the distribution. 13177633Sdfr * 3. All advertising materials mentioning features or use of this software 14177633Sdfr * must display the following acknowledgement: 15177633Sdfr * This product includes software developed by the University of 16177633Sdfr * California, Berkeley and its contributors. 17177633Sdfr * 4. Neither the name of the University nor the names of its contributors 18177633Sdfr * may be used to endorse or promote products derived from this software 19177633Sdfr * without specific prior written permission. 20177633Sdfr * 21177633Sdfr * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22177633Sdfr * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23177633Sdfr * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24177633Sdfr * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25177633Sdfr * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26177633Sdfr * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27177633Sdfr * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28177633Sdfr * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29177633Sdfr * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30177633Sdfr * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31177633Sdfr * SUCH DAMAGE. 32177633Sdfr * 33177633Sdfr * @(#)queue.h 8.5 (Berkeley) 8/20/94 34177633Sdfr * $Id: queue.h,v 1.25 1999/04/20 22:37:17 n_hibma Exp $ 35177633Sdfr */ 36177633Sdfr 37177633Sdfr#ifndef _SYS_QUEUE_H_ 38177633Sdfr#define _SYS_QUEUE_H_ 39177633Sdfr 40177685Sdfr/* 41177685Sdfr * This file defines five types of data structures: singly-linked lists, 42177633Sdfr * slingly-linked tail queues, lists, tail queues, and circular queues. 43177633Sdfr * 44177633Sdfr * A singly-linked list is headed by a single forward pointer. The elements 45177633Sdfr * are singly linked for minimum space and pointer manipulation overhead at 46177633Sdfr * the expense of O(n) removal for arbitrary elements. New elements can be 47177633Sdfr * added to the list after an existing element or at the head of the list. 48177633Sdfr * Elements being removed from the head of the list should use the explicit 49177633Sdfr * macro for this purpose for optimum efficiency. A singly-linked list may 50177633Sdfr * only be traversed in the forward direction. Singly-linked lists are ideal 51177633Sdfr * for applications with large datasets and few or no removals or for 52177633Sdfr * implementing a LIFO queue. 53177633Sdfr * 54177633Sdfr * A singly-linked tail queue is headed by a pair of pointers, one to the 55177633Sdfr * head of the list and the other to the tail of the list. The elements are 56177633Sdfr * singly linked for minimum space and pointer manipulation overhead at the 57177633Sdfr * expense of O(n) removal for arbitrary elements. New elements can be added 58177633Sdfr * to the list after an existing element, at the head of the list, or at the 59177633Sdfr * end of the list. Elements being removed from the head of the tail queue 60177633Sdfr * should use the explicit macro for this purpose for optimum efficiency. 61177633Sdfr * A singly-linked tail queue may only be traversed in the forward direction. 62177633Sdfr * Singly-linked tail queues are ideal for applications with large datasets 63177633Sdfr * and few or no removals or for implementing a FIFO queue. 64177633Sdfr * 65177633Sdfr * A list is headed by a single forward pointer (or an array of forward 66177633Sdfr * pointers for a hash table header). The elements are doubly linked 67177633Sdfr * so that an arbitrary element can be removed without a need to 68177633Sdfr * traverse the list. New elements can be added to the list before 69177633Sdfr * or after an existing element or at the head of the list. A list 70177633Sdfr * may only be traversed in the forward direction. 71177633Sdfr * 72177633Sdfr * A tail queue is headed by a pair of pointers, one to the head of the 73177633Sdfr * list and the other to the tail of the list. The elements are doubly 74177633Sdfr * linked so that an arbitrary element can be removed without a need to 75177633Sdfr * traverse the list. New elements can be added to the list before or 76177633Sdfr * after an existing element, at the head of the list, or at the end of 77177633Sdfr * the list. A tail queue may only be traversed in the forward direction. 78177633Sdfr * 79177633Sdfr * A circle queue is headed by a pair of pointers, one to the head of the 80177633Sdfr * list and the other to the tail of the list. The elements are doubly 81177633Sdfr * linked so that an arbitrary element can be removed without a need to 82177633Sdfr * traverse the list. New elements can be added to the list before or after 83177633Sdfr * an existing element, at the head of the list, or at the end of the list. 84177633Sdfr * A circle queue may be traversed in either direction, but has a more 85177633Sdfr * complex end of list detection. 86177633Sdfr * 87177633Sdfr * For details on the use of these macros, see the queue(3) manual page. 88177633Sdfr * 89177633Sdfr * 90177633Sdfr * SLIST LIST STAILQ TAILQ CIRCLEQ 91177633Sdfr * _HEAD + + + + + 92177633Sdfr * _ENTRY + + + + + 93177633Sdfr * _INIT + + + + + 94177633Sdfr * _EMPTY + + + + + 95177633Sdfr * _FIRST + + + + + 96177633Sdfr * _NEXT + + + + + 97177633Sdfr * _PREV - - - + + 98177633Sdfr * _LAST - - + + + 99177633Sdfr * _FOREACH + + - + + 100177633Sdfr * _INSERT_HEAD + + + + + 101177633Sdfr * _INSERT_BEFORE - + - + + 102177633Sdfr * _INSERT_AFTER + + + + + 103177633Sdfr * _INSERT_TAIL - - + + + 104177633Sdfr * _REMOVE_HEAD + - + - - 105177633Sdfr * _REMOVE + + + + + 106177633Sdfr * 107177633Sdfr */ 108177633Sdfr 109177633Sdfr/* 110177633Sdfr * Singly-linked List definitions. 111177633Sdfr */ 112177633Sdfr#define SLIST_HEAD(name, type) \ 113177633Sdfrstruct name { \ 114177633Sdfr struct type *slh_first; /* first element */ \ 115177633Sdfr} 116177633Sdfr 117177633Sdfr#define SLIST_ENTRY(type) \ 118177633Sdfrstruct { \ 119177633Sdfr struct type *sle_next; /* next element */ \ 120177633Sdfr} 121177633Sdfr 122177633Sdfr/* 123177633Sdfr * Singly-linked List functions. 124177633Sdfr */ 125177633Sdfr#define SLIST_EMPTY(head) ((head)->slh_first == NULL) 126177633Sdfr 127177633Sdfr#define SLIST_FIRST(head) ((head)->slh_first) 128177633Sdfr 129177633Sdfr#define SLIST_FOREACH(var, head, field) \ 130177633Sdfr for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next) 131177633Sdfr 132177633Sdfr#define SLIST_INIT(head) { \ 133177633Sdfr (head)->slh_first = NULL; \ 134177633Sdfr} 135177633Sdfr 136177633Sdfr#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 137177633Sdfr (elm)->field.sle_next = (slistelm)->field.sle_next; \ 138177633Sdfr (slistelm)->field.sle_next = (elm); \ 139177633Sdfr} while (0) 140177633Sdfr 141177633Sdfr#define SLIST_INSERT_HEAD(head, elm, field) do { \ 142177633Sdfr (elm)->field.sle_next = (head)->slh_first; \ 143177633Sdfr (head)->slh_first = (elm); \ 144177633Sdfr} while (0) 145177633Sdfr 146177633Sdfr#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 147177633Sdfr 148177633Sdfr#define SLIST_REMOVE_HEAD(head, field) do { \ 149177633Sdfr (head)->slh_first = (head)->slh_first->field.sle_next; \ 150177633Sdfr} while (0) 151177633Sdfr 152177633Sdfr#define SLIST_REMOVE(head, elm, type, field) do { \ 153177633Sdfr if ((head)->slh_first == (elm)) { \ 154177633Sdfr SLIST_REMOVE_HEAD((head), field); \ 155177633Sdfr } \ 156177633Sdfr else { \ 157177633Sdfr struct type *curelm = (head)->slh_first; \ 158177633Sdfr while( curelm->field.sle_next != (elm) ) \ 159177633Sdfr curelm = curelm->field.sle_next; \ 160177633Sdfr curelm->field.sle_next = \ 161177633Sdfr curelm->field.sle_next->field.sle_next; \ 162177633Sdfr } \ 163177633Sdfr} while (0) 164177633Sdfr 165177633Sdfr/* 166177633Sdfr * Singly-linked Tail queue definitions. 167177633Sdfr */ 168177633Sdfr#define STAILQ_HEAD(name, type) \ 169177633Sdfrstruct name { \ 170177633Sdfr struct type *stqh_first;/* first element */ \ 171177633Sdfr struct type **stqh_last;/* addr of last next element */ \ 172177633Sdfr} 173177633Sdfr 174177633Sdfr#define STAILQ_HEAD_INITIALIZER(head) \ 175177633Sdfr { NULL, &(head).stqh_first } 176177633Sdfr 177177633Sdfr#define STAILQ_ENTRY(type) \ 178177633Sdfrstruct { \ 179177633Sdfr struct type *stqe_next; /* next element */ \ 180177633Sdfr} 181177633Sdfr 182177633Sdfr/* 183177633Sdfr * Singly-linked Tail queue functions. 184177633Sdfr */ 185177633Sdfr#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) 186177633Sdfr 187177633Sdfr#define STAILQ_INIT(head) do { \ 188177633Sdfr (head)->stqh_first = NULL; \ 189177633Sdfr (head)->stqh_last = &(head)->stqh_first; \ 190177633Sdfr} while (0) 191177633Sdfr 192177633Sdfr#define STAILQ_FIRST(head) ((head)->stqh_first) 193177633Sdfr#define STAILQ_LAST(head) (*(head)->stqh_last) 194177633Sdfr 195177633Sdfr#define STAILQ_INSERT_HEAD(head, elm, field) do { \ 196177633Sdfr if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \ 197177633Sdfr (head)->stqh_last = &(elm)->field.stqe_next; \ 198177633Sdfr (head)->stqh_first = (elm); \ 199177633Sdfr} while (0) 200177633Sdfr 201177633Sdfr#define STAILQ_INSERT_TAIL(head, elm, field) do { \ 202177633Sdfr (elm)->field.stqe_next = NULL; \ 203177633Sdfr *(head)->stqh_last = (elm); \ 204177633Sdfr (head)->stqh_last = &(elm)->field.stqe_next; \ 205177633Sdfr} while (0) 206177633Sdfr 207177633Sdfr#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \ 208177633Sdfr if (((elm)->field.stqe_next = (tqelm)->field.stqe_next) == NULL)\ 209177633Sdfr (head)->stqh_last = &(elm)->field.stqe_next; \ 210177633Sdfr (tqelm)->field.stqe_next = (elm); \ 211177633Sdfr} while (0) 212177633Sdfr 213177633Sdfr#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) 214177633Sdfr 215177633Sdfr#define STAILQ_REMOVE_HEAD(head, field) do { \ 216177633Sdfr if (((head)->stqh_first = \ 217177633Sdfr (head)->stqh_first->field.stqe_next) == NULL) \ 218177633Sdfr (head)->stqh_last = &(head)->stqh_first; \ 219177633Sdfr} while (0) 220177633Sdfr 221177633Sdfr 222177633Sdfr#define STAILQ_REMOVE(head, elm, type, field) do { \ 223177633Sdfr if ((head)->stqh_first == (elm)) { \ 224177633Sdfr STAILQ_REMOVE_HEAD(head, field); \ 225177633Sdfr } \ 226177633Sdfr else { \ 227177633Sdfr struct type *curelm = (head)->stqh_first; \ 228177633Sdfr while( curelm->field.stqe_next != (elm) ) \ 229177633Sdfr curelm = curelm->field.stqe_next; \ 230177633Sdfr if((curelm->field.stqe_next = \ 231177633Sdfr curelm->field.stqe_next->field.stqe_next) == NULL) \ 232177633Sdfr (head)->stqh_last = &(curelm)->field.stqe_next; \ 233177633Sdfr } \ 234177633Sdfr} while (0) 235177633Sdfr 236177633Sdfr/* 237177633Sdfr * List definitions. 238177633Sdfr */ 239177633Sdfr#define LIST_HEAD(name, type) \ 240177633Sdfrstruct name { \ 241177633Sdfr struct type *lh_first; /* first element */ \ 242180025Sdfr} 243180025Sdfr 244177633Sdfr#define LIST_HEAD_INITIALIZER(head) \ 245177633Sdfr { NULL } 246177633Sdfr 247177633Sdfr#define LIST_ENTRY(type) \ 248177633Sdfrstruct { \ 249177633Sdfr struct type *le_next; /* next element */ \ 250177633Sdfr struct type **le_prev; /* address of previous next element */ \ 251177633Sdfr} 252180025Sdfr 253180025Sdfr/* 254180025Sdfr * List functions. 255180025Sdfr */ 256177633Sdfr 257177633Sdfr#define LIST_EMPTY(head) ((head)->lh_first == NULL) 258177633Sdfr 259177633Sdfr#define LIST_FIRST(head) ((head)->lh_first) 260177633Sdfr 261177633Sdfr#define LIST_FOREACH(var, head, field) \ 262177633Sdfr for((var) = (head)->lh_first; (var); (var) = (var)->field.le_next) 263177633Sdfr 264177633Sdfr#define LIST_INIT(head) do { \ 265177633Sdfr (head)->lh_first = NULL; \ 266177633Sdfr} while (0) 267177633Sdfr 268177633Sdfr#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 269177633Sdfr if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 270177633Sdfr (listelm)->field.le_next->field.le_prev = \ 271177633Sdfr &(elm)->field.le_next; \ 272177633Sdfr (listelm)->field.le_next = (elm); \ 273177633Sdfr (elm)->field.le_prev = &(listelm)->field.le_next; \ 274177633Sdfr} while (0) 275177633Sdfr 276177633Sdfr#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 277180025Sdfr (elm)->field.le_prev = (listelm)->field.le_prev; \ 278180025Sdfr (elm)->field.le_next = (listelm); \ 279177633Sdfr *(listelm)->field.le_prev = (elm); \ 280177633Sdfr (listelm)->field.le_prev = &(elm)->field.le_next; \ 281177633Sdfr} while (0) 282180025Sdfr 283180025Sdfr#define LIST_INSERT_HEAD(head, elm, field) do { \ 284180025Sdfr if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 285180025Sdfr (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 286177633Sdfr (head)->lh_first = (elm); \ 287177633Sdfr (elm)->field.le_prev = &(head)->lh_first; \ 288177633Sdfr} while (0) 289177633Sdfr 290177633Sdfr#define LIST_NEXT(elm, field) ((elm)->field.le_next) 291177633Sdfr 292177633Sdfr#define LIST_REMOVE(elm, field) do { \ 293177633Sdfr if ((elm)->field.le_next != NULL) \ 294177633Sdfr (elm)->field.le_next->field.le_prev = \ 295177633Sdfr (elm)->field.le_prev; \ 296177633Sdfr *(elm)->field.le_prev = (elm)->field.le_next; \ 297177633Sdfr} while (0) 298177633Sdfr 299177633Sdfr/* 300177633Sdfr * Tail queue definitions. 301177633Sdfr */ 302177633Sdfr#define TAILQ_HEAD(name, type) \ 303177633Sdfrstruct name { \ 304177633Sdfr struct type *tqh_first; /* first element */ \ 305180025Sdfr struct type **tqh_last; /* addr of last next element */ \ 306180025Sdfr} 307177633Sdfr 308177633Sdfr#define TAILQ_HEAD_INITIALIZER(head) \ 309177633Sdfr { NULL, &(head).tqh_first } 310180025Sdfr 311180025Sdfr#define TAILQ_ENTRY(type) \ 312180025Sdfrstruct { \ 313180025Sdfr struct type *tqe_next; /* next element */ \ 314177633Sdfr struct type **tqe_prev; /* address of previous next element */ \ 315177633Sdfr} 316177633Sdfr 317177633Sdfr/* 318177633Sdfr * Tail queue functions. 319177633Sdfr */ 320177633Sdfr#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) 321177633Sdfr 322177633Sdfr#define TAILQ_FOREACH(var, head, field) \ 323177633Sdfr for (var = TAILQ_FIRST(head); var; var = TAILQ_NEXT(var, field)) 324177633Sdfr 325177633Sdfr#define TAILQ_FIRST(head) ((head)->tqh_first) 326177633Sdfr 327177633Sdfr#define TAILQ_LAST(head, headname) \ 328177633Sdfr (*(((struct headname *)((head)->tqh_last))->tqh_last)) 329177633Sdfr 330177633Sdfr#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 331180025Sdfr 332180025Sdfr#define TAILQ_PREV(elm, headname, field) \ 333177633Sdfr (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 334177633Sdfr 335177633Sdfr#define TAILQ_INIT(head) do { \ 336180025Sdfr (head)->tqh_first = NULL; \ 337180025Sdfr (head)->tqh_last = &(head)->tqh_first; \ 338180025Sdfr} while (0) 339180025Sdfr 340177633Sdfr#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 341177633Sdfr if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 342177633Sdfr (head)->tqh_first->field.tqe_prev = \ 343177633Sdfr &(elm)->field.tqe_next; \ 344177633Sdfr else \ 345177633Sdfr (head)->tqh_last = &(elm)->field.tqe_next; \ 346177633Sdfr (head)->tqh_first = (elm); \ 347177633Sdfr (elm)->field.tqe_prev = &(head)->tqh_first; \ 348177633Sdfr} while (0) 349177633Sdfr 350177633Sdfr#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 351177633Sdfr (elm)->field.tqe_next = NULL; \ 352177633Sdfr (elm)->field.tqe_prev = (head)->tqh_last; \ 353177633Sdfr *(head)->tqh_last = (elm); \ 354177633Sdfr (head)->tqh_last = &(elm)->field.tqe_next; \ 355177633Sdfr} while (0) 356177633Sdfr 357177633Sdfr#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 358180025Sdfr if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 359180025Sdfr (elm)->field.tqe_next->field.tqe_prev = \ 360177633Sdfr &(elm)->field.tqe_next; \ 361177633Sdfr else \ 362177633Sdfr (head)->tqh_last = &(elm)->field.tqe_next; \ 363180025Sdfr (listelm)->field.tqe_next = (elm); \ 364180025Sdfr (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 365180025Sdfr} while (0) 366180025Sdfr 367177633Sdfr#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 368177633Sdfr (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 369177633Sdfr (elm)->field.tqe_next = (listelm); \ 370177633Sdfr *(listelm)->field.tqe_prev = (elm); \ 371177633Sdfr (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 372177633Sdfr} while (0) 373177633Sdfr 374177633Sdfr#define TAILQ_REMOVE(head, elm, field) do { \ 375177633Sdfr if (((elm)->field.tqe_next) != NULL) \ 376177633Sdfr (elm)->field.tqe_next->field.tqe_prev = \ 377177633Sdfr (elm)->field.tqe_prev; \ 378177633Sdfr else \ 379177633Sdfr (head)->tqh_last = (elm)->field.tqe_prev; \ 380177633Sdfr *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 381177633Sdfr} while (0) 382177633Sdfr 383177633Sdfr/* 384177633Sdfr * Circular queue definitions. 385177633Sdfr */ 386177633Sdfr#define CIRCLEQ_HEAD(name, type) \ 387177633Sdfrstruct name { \ 388177633Sdfr struct type *cqh_first; /* first element */ \ 389177633Sdfr struct type *cqh_last; /* last element */ \ 390177633Sdfr} 391177633Sdfr 392177633Sdfr#define CIRCLEQ_ENTRY(type) \ 393177633Sdfrstruct { \ 394177633Sdfr struct type *cqe_next; /* next element */ \ 395177633Sdfr struct type *cqe_prev; /* previous element */ \ 396177633Sdfr} 397177633Sdfr 398177633Sdfr/* 399177633Sdfr * Circular queue functions. 400177633Sdfr */ 401177633Sdfr#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head)) 402177633Sdfr 403177633Sdfr#define CIRCLEQ_FIRST(head) ((head)->cqh_first) 404177633Sdfr 405177633Sdfr#define CIRCLEQ_FOREACH(var, head, field) \ 406177633Sdfr for((var) = (head)->cqh_first; \ 407177633Sdfr (var) != (void *)(head); \ 408177633Sdfr (var) = (var)->field.cqe_next) 409177633Sdfr 410177633Sdfr#define CIRCLEQ_INIT(head) do { \ 411177633Sdfr (head)->cqh_first = (void *)(head); \ 412177633Sdfr (head)->cqh_last = (void *)(head); \ 413177633Sdfr} while (0) 414177633Sdfr 415177633Sdfr#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 416177633Sdfr (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 417177633Sdfr (elm)->field.cqe_prev = (listelm); \ 418177633Sdfr if ((listelm)->field.cqe_next == (void *)(head)) \ 419177633Sdfr (head)->cqh_last = (elm); \ 420177633Sdfr else \ 421177633Sdfr (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 422177633Sdfr (listelm)->field.cqe_next = (elm); \ 423177633Sdfr} while (0) 424177633Sdfr 425177633Sdfr#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ 426177633Sdfr (elm)->field.cqe_next = (listelm); \ 427177633Sdfr (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 428177633Sdfr if ((listelm)->field.cqe_prev == (void *)(head)) \ 429177633Sdfr (head)->cqh_first = (elm); \ 430177633Sdfr else \ 431177633Sdfr (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 432177633Sdfr (listelm)->field.cqe_prev = (elm); \ 433177633Sdfr} while (0) 434177633Sdfr 435177633Sdfr#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ 436177633Sdfr (elm)->field.cqe_next = (head)->cqh_first; \ 437177633Sdfr (elm)->field.cqe_prev = (void *)(head); \ 438177633Sdfr if ((head)->cqh_last == (void *)(head)) \ 439177633Sdfr (head)->cqh_last = (elm); \ 440177633Sdfr else \ 441177633Sdfr (head)->cqh_first->field.cqe_prev = (elm); \ 442177633Sdfr (head)->cqh_first = (elm); \ 443177633Sdfr} while (0) 444177633Sdfr 445177633Sdfr#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ 446177633Sdfr (elm)->field.cqe_next = (void *)(head); \ 447177633Sdfr (elm)->field.cqe_prev = (head)->cqh_last; \ 448177633Sdfr if ((head)->cqh_first == (void *)(head)) \ 449177633Sdfr (head)->cqh_first = (elm); \ 450177633Sdfr else \ 451177633Sdfr (head)->cqh_last->field.cqe_next = (elm); \ 452177633Sdfr (head)->cqh_last = (elm); \ 453177633Sdfr} while (0) 454177633Sdfr 455177633Sdfr#define CIRCLEQ_LAST(head) ((head)->cqh_last) 456177633Sdfr 457177633Sdfr#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next) 458177633Sdfr 459177633Sdfr#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev) 460177633Sdfr 461177633Sdfr#define CIRCLEQ_REMOVE(head, elm, field) do { \ 462177633Sdfr if ((elm)->field.cqe_next == (void *)(head)) \ 463177633Sdfr (head)->cqh_last = (elm)->field.cqe_prev; \ 464177633Sdfr else \ 465177633Sdfr (elm)->field.cqe_next->field.cqe_prev = \ 466177633Sdfr (elm)->field.cqe_prev; \ 467177633Sdfr if ((elm)->field.cqe_prev == (void *)(head)) \ 468177633Sdfr (head)->cqh_first = (elm)->field.cqe_next; \ 469177633Sdfr else \ 470177633Sdfr (elm)->field.cqe_prev->field.cqe_next = \ 471177633Sdfr (elm)->field.cqe_next; \ 472177633Sdfr} while (0) 473177633Sdfr 474177633Sdfr#ifdef KERNEL 475177633Sdfr 476177633Sdfr/* 477177633Sdfr * XXX insque() and remque() are an old way of handling certain queues. 478177633Sdfr * They bogusly assumes that all queue heads look alike. 479177633Sdfr */ 480177633Sdfr 481177633Sdfrstruct quehead { 482177633Sdfr struct quehead *qh_link; 483177633Sdfr struct quehead *qh_rlink; 484177633Sdfr}; 485177633Sdfr 486177633Sdfr#ifdef __GNUC__ 487177633Sdfr 488177633Sdfrstatic __inline void 489177633Sdfrinsque(void *a, void *b) 490177633Sdfr{ 491177633Sdfr struct quehead *element = a, *head = b; 492177633Sdfr 493177633Sdfr element->qh_link = head->qh_link; 494177633Sdfr element->qh_rlink = head; 495177633Sdfr head->qh_link = element; 496177633Sdfr element->qh_link->qh_rlink = element; 497177633Sdfr} 498177633Sdfr 499177633Sdfrstatic __inline void 500177633Sdfrremque(void *a) 501177633Sdfr{ 502177633Sdfr struct quehead *element = a; 503177633Sdfr 504177633Sdfr element->qh_link->qh_rlink = element->qh_rlink; 505177633Sdfr element->qh_rlink->qh_link = element->qh_link; 506177633Sdfr element->qh_rlink = 0; 507177633Sdfr} 508177633Sdfr 509177633Sdfr#else /* !__GNUC__ */ 510177633Sdfr 511177633Sdfrvoid insque __P((void *a, void *b)); 512177633Sdfrvoid remque __P((void *a)); 513177633Sdfr 514177633Sdfr#endif /* __GNUC__ */ 515177633Sdfr 516180025Sdfr#endif /* KERNEL */ 517177633Sdfr 518177633Sdfr#endif /* !_SYS_QUEUE_H_ */ 519177633Sdfr