1275970Scy/* $OpenBSD: queue.h,v 1.16 2000/09/07 19:47:59 art Exp $ */ 2275970Scy/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ 3275970Scy 4275970Scy/* 5275970Scy * Copyright (c) 1991, 1993 6275970Scy * The Regents of the University of California. All rights reserved. 7275970Scy * 8275970Scy * Redistribution and use in source and binary forms, with or without 9275970Scy * modification, are permitted provided that the following conditions 10275970Scy * are met: 11275970Scy * 1. Redistributions of source code must retain the above copyright 12275970Scy * notice, this list of conditions and the following disclaimer. 13275970Scy * 2. Redistributions in binary form must reproduce the above copyright 14275970Scy * notice, this list of conditions and the following disclaimer in the 15275970Scy * documentation and/or other materials provided with the distribution. 16275970Scy * 3. Neither the name of the University nor the names of its contributors 17275970Scy * may be used to endorse or promote products derived from this software 18275970Scy * without specific prior written permission. 19275970Scy * 20275970Scy * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21275970Scy * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22275970Scy * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23275970Scy * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24275970Scy * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25275970Scy * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26275970Scy * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27275970Scy * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28275970Scy * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29275970Scy * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30275970Scy * SUCH DAMAGE. 31275970Scy * 32275970Scy * @(#)queue.h 8.5 (Berkeley) 8/20/94 33275970Scy */ 34275970Scy 35275970Scy#ifndef SYS_QUEUE_H__ 36275970Scy#define SYS_QUEUE_H__ 37275970Scy 38275970Scy/* 39275970Scy * This file defines five types of data structures: singly-linked lists, 40275970Scy * lists, simple queues, tail queues, and circular queues. 41275970Scy * 42275970Scy * 43275970Scy * A singly-linked list is headed by a single forward pointer. The elements 44275970Scy * are singly linked for minimum space and pointer manipulation overhead at 45275970Scy * the expense of O(n) removal for arbitrary elements. New elements can be 46275970Scy * added to the list after an existing element or at the head of the list. 47275970Scy * Elements being removed from the head of the list should use the explicit 48275970Scy * macro for this purpose for optimum efficiency. A singly-linked list may 49275970Scy * only be traversed in the forward direction. Singly-linked lists are ideal 50275970Scy * for applications with large datasets and few or no removals or for 51275970Scy * implementing a LIFO queue. 52275970Scy * 53275970Scy * A list is headed by a single forward pointer (or an array of forward 54275970Scy * pointers for a hash table header). The elements are doubly linked 55275970Scy * so that an arbitrary element can be removed without a need to 56275970Scy * traverse the list. New elements can be added to the list before 57275970Scy * or after an existing element or at the head of the list. A list 58275970Scy * may only be traversed in the forward direction. 59275970Scy * 60275970Scy * A simple queue is headed by a pair of pointers, one the head of the 61275970Scy * list and the other to the tail of the list. The elements are singly 62275970Scy * linked to save space, so elements can only be removed from the 63275970Scy * head of the list. New elements can be added to the list before or after 64275970Scy * an existing element, at the head of the list, or at the end of the 65275970Scy * list. A simple queue may only be traversed in the forward direction. 66275970Scy * 67275970Scy * A tail queue is headed by a pair of pointers, one to the head of the 68275970Scy * list and the other to the tail of the list. The elements are doubly 69275970Scy * linked so that an arbitrary element can be removed without a need to 70275970Scy * traverse the list. New elements can be added to the list before or 71275970Scy * after an existing element, at the head of the list, or at the end of 72275970Scy * the list. A tail queue may be traversed in either direction. 73275970Scy * 74275970Scy * A circle queue is headed by a pair of pointers, one to the head of the 75275970Scy * list and the other to the tail of the list. The elements are doubly 76275970Scy * linked so that an arbitrary element can be removed without a need to 77275970Scy * traverse the list. New elements can be added to the list before or after 78275970Scy * an existing element, at the head of the list, or at the end of the list. 79275970Scy * A circle queue may be traversed in either direction, but has a more 80275970Scy * complex end of list detection. 81275970Scy * 82275970Scy * For details on the use of these macros, see the queue(3) manual page. 83275970Scy */ 84275970Scy 85275970Scy/* 86275970Scy * Singly-linked List definitions. 87275970Scy */ 88275970Scy#define SLIST_HEAD(name, type) \ 89275970Scystruct name { \ 90275970Scy struct type *slh_first; /* first element */ \ 91275970Scy} 92275970Scy 93275970Scy#define SLIST_HEAD_INITIALIZER(head) \ 94275970Scy { NULL } 95275970Scy 96275970Scy#ifndef _WIN32 97275970Scy#define SLIST_ENTRY(type) \ 98275970Scystruct { \ 99275970Scy struct type *sle_next; /* next element */ \ 100275970Scy} 101275970Scy#endif 102275970Scy 103275970Scy/* 104275970Scy * Singly-linked List access methods. 105275970Scy */ 106275970Scy#define SLIST_FIRST(head) ((head)->slh_first) 107275970Scy#define SLIST_END(head) NULL 108275970Scy#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head)) 109275970Scy#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) 110275970Scy 111275970Scy#define SLIST_FOREACH(var, head, field) \ 112275970Scy for((var) = SLIST_FIRST(head); \ 113275970Scy (var) != SLIST_END(head); \ 114275970Scy (var) = SLIST_NEXT(var, field)) 115275970Scy 116275970Scy/* 117275970Scy * Singly-linked List functions. 118275970Scy */ 119275970Scy#define SLIST_INIT(head) { \ 120275970Scy SLIST_FIRST(head) = SLIST_END(head); \ 121275970Scy} 122275970Scy 123275970Scy#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ 124275970Scy (elm)->field.sle_next = (slistelm)->field.sle_next; \ 125275970Scy (slistelm)->field.sle_next = (elm); \ 126275970Scy} while (0) 127275970Scy 128275970Scy#define SLIST_INSERT_HEAD(head, elm, field) do { \ 129275970Scy (elm)->field.sle_next = (head)->slh_first; \ 130275970Scy (head)->slh_first = (elm); \ 131275970Scy} while (0) 132275970Scy 133275970Scy#define SLIST_REMOVE_HEAD(head, field) do { \ 134275970Scy (head)->slh_first = (head)->slh_first->field.sle_next; \ 135275970Scy} while (0) 136275970Scy 137275970Scy/* 138275970Scy * List definitions. 139275970Scy */ 140275970Scy#define LIST_HEAD(name, type) \ 141275970Scystruct name { \ 142275970Scy struct type *lh_first; /* first element */ \ 143275970Scy} 144275970Scy 145275970Scy#define LIST_HEAD_INITIALIZER(head) \ 146275970Scy { NULL } 147275970Scy 148275970Scy#define LIST_ENTRY(type) \ 149275970Scystruct { \ 150275970Scy struct type *le_next; /* next element */ \ 151275970Scy struct type **le_prev; /* address of previous next element */ \ 152275970Scy} 153275970Scy 154275970Scy/* 155275970Scy * List access methods 156275970Scy */ 157275970Scy#define LIST_FIRST(head) ((head)->lh_first) 158275970Scy#define LIST_END(head) NULL 159275970Scy#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head)) 160275970Scy#define LIST_NEXT(elm, field) ((elm)->field.le_next) 161275970Scy 162275970Scy#define LIST_FOREACH(var, head, field) \ 163275970Scy for((var) = LIST_FIRST(head); \ 164275970Scy (var)!= LIST_END(head); \ 165275970Scy (var) = LIST_NEXT(var, field)) 166275970Scy 167275970Scy/* 168275970Scy * List functions. 169275970Scy */ 170275970Scy#define LIST_INIT(head) do { \ 171275970Scy LIST_FIRST(head) = LIST_END(head); \ 172275970Scy} while (0) 173275970Scy 174275970Scy#define LIST_INSERT_AFTER(listelm, elm, field) do { \ 175275970Scy if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ 176275970Scy (listelm)->field.le_next->field.le_prev = \ 177275970Scy &(elm)->field.le_next; \ 178275970Scy (listelm)->field.le_next = (elm); \ 179275970Scy (elm)->field.le_prev = &(listelm)->field.le_next; \ 180275970Scy} while (0) 181275970Scy 182275970Scy#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ 183275970Scy (elm)->field.le_prev = (listelm)->field.le_prev; \ 184275970Scy (elm)->field.le_next = (listelm); \ 185275970Scy *(listelm)->field.le_prev = (elm); \ 186275970Scy (listelm)->field.le_prev = &(elm)->field.le_next; \ 187275970Scy} while (0) 188275970Scy 189275970Scy#define LIST_INSERT_HEAD(head, elm, field) do { \ 190275970Scy if (((elm)->field.le_next = (head)->lh_first) != NULL) \ 191275970Scy (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ 192275970Scy (head)->lh_first = (elm); \ 193275970Scy (elm)->field.le_prev = &(head)->lh_first; \ 194275970Scy} while (0) 195275970Scy 196275970Scy#define LIST_REMOVE(elm, field) do { \ 197275970Scy if ((elm)->field.le_next != NULL) \ 198275970Scy (elm)->field.le_next->field.le_prev = \ 199275970Scy (elm)->field.le_prev; \ 200275970Scy *(elm)->field.le_prev = (elm)->field.le_next; \ 201275970Scy} while (0) 202275970Scy 203275970Scy#define LIST_REPLACE(elm, elm2, field) do { \ 204275970Scy if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \ 205275970Scy (elm2)->field.le_next->field.le_prev = \ 206275970Scy &(elm2)->field.le_next; \ 207275970Scy (elm2)->field.le_prev = (elm)->field.le_prev; \ 208275970Scy *(elm2)->field.le_prev = (elm2); \ 209275970Scy} while (0) 210275970Scy 211275970Scy/* 212275970Scy * Simple queue definitions. 213275970Scy */ 214275970Scy#define SIMPLEQ_HEAD(name, type) \ 215275970Scystruct name { \ 216275970Scy struct type *sqh_first; /* first element */ \ 217275970Scy struct type **sqh_last; /* addr of last next element */ \ 218275970Scy} 219275970Scy 220275970Scy#define SIMPLEQ_HEAD_INITIALIZER(head) \ 221275970Scy { NULL, &(head).sqh_first } 222275970Scy 223275970Scy#define SIMPLEQ_ENTRY(type) \ 224275970Scystruct { \ 225275970Scy struct type *sqe_next; /* next element */ \ 226275970Scy} 227275970Scy 228275970Scy/* 229275970Scy * Simple queue access methods. 230275970Scy */ 231275970Scy#define SIMPLEQ_FIRST(head) ((head)->sqh_first) 232275970Scy#define SIMPLEQ_END(head) NULL 233275970Scy#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head)) 234275970Scy#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) 235275970Scy 236275970Scy#define SIMPLEQ_FOREACH(var, head, field) \ 237275970Scy for((var) = SIMPLEQ_FIRST(head); \ 238275970Scy (var) != SIMPLEQ_END(head); \ 239275970Scy (var) = SIMPLEQ_NEXT(var, field)) 240275970Scy 241275970Scy/* 242275970Scy * Simple queue functions. 243275970Scy */ 244275970Scy#define SIMPLEQ_INIT(head) do { \ 245275970Scy (head)->sqh_first = NULL; \ 246275970Scy (head)->sqh_last = &(head)->sqh_first; \ 247275970Scy} while (0) 248275970Scy 249275970Scy#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ 250275970Scy if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ 251275970Scy (head)->sqh_last = &(elm)->field.sqe_next; \ 252275970Scy (head)->sqh_first = (elm); \ 253275970Scy} while (0) 254275970Scy 255275970Scy#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ 256275970Scy (elm)->field.sqe_next = NULL; \ 257275970Scy *(head)->sqh_last = (elm); \ 258275970Scy (head)->sqh_last = &(elm)->field.sqe_next; \ 259275970Scy} while (0) 260275970Scy 261275970Scy#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 262275970Scy if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ 263275970Scy (head)->sqh_last = &(elm)->field.sqe_next; \ 264275970Scy (listelm)->field.sqe_next = (elm); \ 265275970Scy} while (0) 266275970Scy 267275970Scy#define SIMPLEQ_REMOVE_HEAD(head, elm, field) do { \ 268275970Scy if (((head)->sqh_first = (elm)->field.sqe_next) == NULL) \ 269275970Scy (head)->sqh_last = &(head)->sqh_first; \ 270275970Scy} while (0) 271275970Scy 272275970Scy/* 273275970Scy * Tail queue definitions. 274275970Scy */ 275275970Scy#define TAILQ_HEAD(name, type) \ 276275970Scystruct name { \ 277275970Scy struct type *tqh_first; /* first element */ \ 278275970Scy struct type **tqh_last; /* addr of last next element */ \ 279275970Scy} 280275970Scy 281275970Scy#define TAILQ_HEAD_INITIALIZER(head) \ 282275970Scy { NULL, &(head).tqh_first } 283275970Scy 284275970Scy#define TAILQ_ENTRY(type) \ 285275970Scystruct { \ 286275970Scy struct type *tqe_next; /* next element */ \ 287275970Scy struct type **tqe_prev; /* address of previous next element */ \ 288275970Scy} 289275970Scy 290275970Scy/* 291275970Scy * tail queue access methods 292275970Scy */ 293275970Scy#define TAILQ_FIRST(head) ((head)->tqh_first) 294275970Scy#define TAILQ_END(head) NULL 295275970Scy#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) 296275970Scy#define TAILQ_LAST(head, headname) \ 297275970Scy (*(((struct headname *)((head)->tqh_last))->tqh_last)) 298275970Scy/* XXX */ 299275970Scy#define TAILQ_PREV(elm, headname, field) \ 300275970Scy (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) 301275970Scy#define TAILQ_EMPTY(head) \ 302275970Scy (TAILQ_FIRST(head) == TAILQ_END(head)) 303275970Scy 304275970Scy#define TAILQ_FOREACH(var, head, field) \ 305275970Scy for((var) = TAILQ_FIRST(head); \ 306275970Scy (var) != TAILQ_END(head); \ 307275970Scy (var) = TAILQ_NEXT(var, field)) 308275970Scy 309275970Scy#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ 310275970Scy for((var) = TAILQ_LAST(head, headname); \ 311275970Scy (var) != TAILQ_END(head); \ 312275970Scy (var) = TAILQ_PREV(var, headname, field)) 313275970Scy 314275970Scy/* 315275970Scy * Tail queue functions. 316275970Scy */ 317275970Scy#define TAILQ_INIT(head) do { \ 318275970Scy (head)->tqh_first = NULL; \ 319275970Scy (head)->tqh_last = &(head)->tqh_first; \ 320275970Scy} while (0) 321275970Scy 322275970Scy#define TAILQ_INSERT_HEAD(head, elm, field) do { \ 323275970Scy if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ 324275970Scy (head)->tqh_first->field.tqe_prev = \ 325275970Scy &(elm)->field.tqe_next; \ 326275970Scy else \ 327275970Scy (head)->tqh_last = &(elm)->field.tqe_next; \ 328275970Scy (head)->tqh_first = (elm); \ 329275970Scy (elm)->field.tqe_prev = &(head)->tqh_first; \ 330275970Scy} while (0) 331275970Scy 332275970Scy#define TAILQ_INSERT_TAIL(head, elm, field) do { \ 333275970Scy (elm)->field.tqe_next = NULL; \ 334275970Scy (elm)->field.tqe_prev = (head)->tqh_last; \ 335275970Scy *(head)->tqh_last = (elm); \ 336275970Scy (head)->tqh_last = &(elm)->field.tqe_next; \ 337275970Scy} while (0) 338275970Scy 339275970Scy#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ 340275970Scy if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ 341275970Scy (elm)->field.tqe_next->field.tqe_prev = \ 342275970Scy &(elm)->field.tqe_next; \ 343275970Scy else \ 344275970Scy (head)->tqh_last = &(elm)->field.tqe_next; \ 345275970Scy (listelm)->field.tqe_next = (elm); \ 346275970Scy (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ 347275970Scy} while (0) 348275970Scy 349275970Scy#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ 350275970Scy (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ 351275970Scy (elm)->field.tqe_next = (listelm); \ 352275970Scy *(listelm)->field.tqe_prev = (elm); \ 353275970Scy (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ 354275970Scy} while (0) 355275970Scy 356275970Scy#define TAILQ_REMOVE(head, elm, field) do { \ 357275970Scy if (((elm)->field.tqe_next) != NULL) \ 358275970Scy (elm)->field.tqe_next->field.tqe_prev = \ 359275970Scy (elm)->field.tqe_prev; \ 360275970Scy else \ 361275970Scy (head)->tqh_last = (elm)->field.tqe_prev; \ 362275970Scy *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ 363275970Scy} while (0) 364275970Scy 365275970Scy#define TAILQ_REPLACE(head, elm, elm2, field) do { \ 366275970Scy if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \ 367275970Scy (elm2)->field.tqe_next->field.tqe_prev = \ 368275970Scy &(elm2)->field.tqe_next; \ 369275970Scy else \ 370275970Scy (head)->tqh_last = &(elm2)->field.tqe_next; \ 371275970Scy (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ 372275970Scy *(elm2)->field.tqe_prev = (elm2); \ 373275970Scy} while (0) 374275970Scy 375275970Scy/* 376275970Scy * Circular queue definitions. 377275970Scy */ 378275970Scy#define CIRCLEQ_HEAD(name, type) \ 379275970Scystruct name { \ 380275970Scy struct type *cqh_first; /* first element */ \ 381275970Scy struct type *cqh_last; /* last element */ \ 382275970Scy} 383275970Scy 384275970Scy#define CIRCLEQ_HEAD_INITIALIZER(head) \ 385275970Scy { CIRCLEQ_END(&head), CIRCLEQ_END(&head) } 386275970Scy 387275970Scy#define CIRCLEQ_ENTRY(type) \ 388275970Scystruct { \ 389275970Scy struct type *cqe_next; /* next element */ \ 390275970Scy struct type *cqe_prev; /* previous element */ \ 391275970Scy} 392275970Scy 393275970Scy/* 394275970Scy * Circular queue access methods 395275970Scy */ 396275970Scy#define CIRCLEQ_FIRST(head) ((head)->cqh_first) 397275970Scy#define CIRCLEQ_LAST(head) ((head)->cqh_last) 398275970Scy#define CIRCLEQ_END(head) ((void *)(head)) 399275970Scy#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) 400275970Scy#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) 401275970Scy#define CIRCLEQ_EMPTY(head) \ 402275970Scy (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head)) 403275970Scy 404275970Scy#define CIRCLEQ_FOREACH(var, head, field) \ 405275970Scy for((var) = CIRCLEQ_FIRST(head); \ 406275970Scy (var) != CIRCLEQ_END(head); \ 407275970Scy (var) = CIRCLEQ_NEXT(var, field)) 408275970Scy 409275970Scy#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ 410275970Scy for((var) = CIRCLEQ_LAST(head); \ 411275970Scy (var) != CIRCLEQ_END(head); \ 412275970Scy (var) = CIRCLEQ_PREV(var, field)) 413275970Scy 414275970Scy/* 415275970Scy * Circular queue functions. 416275970Scy */ 417275970Scy#define CIRCLEQ_INIT(head) do { \ 418275970Scy (head)->cqh_first = CIRCLEQ_END(head); \ 419275970Scy (head)->cqh_last = CIRCLEQ_END(head); \ 420275970Scy} while (0) 421275970Scy 422275970Scy#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ 423275970Scy (elm)->field.cqe_next = (listelm)->field.cqe_next; \ 424275970Scy (elm)->field.cqe_prev = (listelm); \ 425275970Scy if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \ 426275970Scy (head)->cqh_last = (elm); \ 427275970Scy else \ 428275970Scy (listelm)->field.cqe_next->field.cqe_prev = (elm); \ 429275970Scy (listelm)->field.cqe_next = (elm); \ 430275970Scy} while (0) 431275970Scy 432275970Scy#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ 433275970Scy (elm)->field.cqe_next = (listelm); \ 434275970Scy (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ 435275970Scy if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \ 436275970Scy (head)->cqh_first = (elm); \ 437275970Scy else \ 438275970Scy (listelm)->field.cqe_prev->field.cqe_next = (elm); \ 439275970Scy (listelm)->field.cqe_prev = (elm); \ 440275970Scy} while (0) 441275970Scy 442275970Scy#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ 443275970Scy (elm)->field.cqe_next = (head)->cqh_first; \ 444275970Scy (elm)->field.cqe_prev = CIRCLEQ_END(head); \ 445275970Scy if ((head)->cqh_last == CIRCLEQ_END(head)) \ 446275970Scy (head)->cqh_last = (elm); \ 447275970Scy else \ 448275970Scy (head)->cqh_first->field.cqe_prev = (elm); \ 449275970Scy (head)->cqh_first = (elm); \ 450275970Scy} while (0) 451275970Scy 452275970Scy#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ 453275970Scy (elm)->field.cqe_next = CIRCLEQ_END(head); \ 454275970Scy (elm)->field.cqe_prev = (head)->cqh_last; \ 455275970Scy if ((head)->cqh_first == CIRCLEQ_END(head)) \ 456275970Scy (head)->cqh_first = (elm); \ 457275970Scy else \ 458275970Scy (head)->cqh_last->field.cqe_next = (elm); \ 459275970Scy (head)->cqh_last = (elm); \ 460275970Scy} while (0) 461275970Scy 462275970Scy#define CIRCLEQ_REMOVE(head, elm, field) do { \ 463275970Scy if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \ 464275970Scy (head)->cqh_last = (elm)->field.cqe_prev; \ 465275970Scy else \ 466275970Scy (elm)->field.cqe_next->field.cqe_prev = \ 467275970Scy (elm)->field.cqe_prev; \ 468275970Scy if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \ 469275970Scy (head)->cqh_first = (elm)->field.cqe_next; \ 470275970Scy else \ 471275970Scy (elm)->field.cqe_prev->field.cqe_next = \ 472275970Scy (elm)->field.cqe_next; \ 473275970Scy} while (0) 474275970Scy 475275970Scy#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \ 476275970Scy if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \ 477275970Scy CIRCLEQ_END(head)) \ 478275970Scy (head).cqh_last = (elm2); \ 479275970Scy else \ 480275970Scy (elm2)->field.cqe_next->field.cqe_prev = (elm2); \ 481275970Scy if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \ 482275970Scy CIRCLEQ_END(head)) \ 483275970Scy (head).cqh_first = (elm2); \ 484275970Scy else \ 485275970Scy (elm2)->field.cqe_prev->field.cqe_next = (elm2); \ 486275970Scy} while (0) 487275970Scy 488275970Scy#endif /* !SYS_QUEUE_H__ */ 489