1/* $OpenBSD: queue.h,v 1.38 2013/07/03 15:05:21 fgsch Exp $ */2/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */34/*5 * Copyright (c) 1991, 19936 * The Regents of the University of California. All rights reserved.7 *8 * Redistribution and use in source and binary forms, with or without9 * modification, are permitted provided that the following conditions10 * are met:11 * 1. Redistributions of source code must retain the above copyright12 * notice, this list of conditions and the following disclaimer.13 * 2. Redistributions in binary form must reproduce the above copyright14 * notice, this list of conditions and the following disclaimer in the15 * documentation and/or other materials provided with the distribution.16 * 3. Neither the name of the University nor the names of its contributors17 * may be used to endorse or promote products derived from this software18 * without specific prior written permission.19 *20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF30 * SUCH DAMAGE.31 *32 * @(#)queue.h 8.5 (Berkeley) 8/20/9433 */3435#ifndef _SYS_QUEUE_H_36#define _SYS_QUEUE_H_3738/*39 * This file defines five types of data structures: singly-linked lists,40 * lists, simple queues, tail queues, and circular queues.41 *42 *43 * A singly-linked list is headed by a single forward pointer. The elements44 * are singly linked for minimum space and pointer manipulation overhead at45 * the expense of O(n) removal for arbitrary elements. New elements can be46 * added to the list after an existing element or at the head of the list.47 * Elements being removed from the head of the list should use the explicit48 * macro for this purpose for optimum efficiency. A singly-linked list may49 * only be traversed in the forward direction. Singly-linked lists are ideal50 * for applications with large datasets and few or no removals or for51 * implementing a LIFO queue.52 *53 * A list is headed by a single forward pointer (or an array of forward54 * pointers for a hash table header). The elements are doubly linked55 * so that an arbitrary element can be removed without a need to56 * traverse the list. New elements can be added to the list before57 * or after an existing element or at the head of the list. A list58 * may only be traversed in the forward direction.59 *60 * A simple queue is headed by a pair of pointers, one the head of the61 * list and the other to the tail of the list. The elements are singly62 * linked to save space, so elements can only be removed from the63 * head of the list. New elements can be added to the list before or after64 * an existing element, at the head of the list, or at the end of the65 * list. A simple queue may only be traversed in the forward direction.66 *67 * A tail queue is headed by a pair of pointers, one to the head of the68 * list and the other to the tail of the list. The elements are doubly69 * linked so that an arbitrary element can be removed without a need to70 * traverse the list. New elements can be added to the list before or71 * after an existing element, at the head of the list, or at the end of72 * the list. A tail queue may be traversed in either direction.73 *74 * A circle queue is headed by a pair of pointers, one to the head of the75 * list and the other to the tail of the list. The elements are doubly76 * linked so that an arbitrary element can be removed without a need to77 * traverse the list. New elements can be added to the list before or after78 * an existing element, at the head of the list, or at the end of the list.79 * A circle queue may be traversed in either direction, but has a more80 * complex end of list detection.81 *82 * For details on the use of these macros, see the queue(3) manual page.83 */8485#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))86#define _Q_INVALIDATE(a) (a) = ((void *)-1)87#else88#define _Q_INVALIDATE(a)89#endif9091/*92 * Singly-linked List definitions.93 */94#define SLIST_HEAD(name, type) \95struct name { \96 struct type *slh_first; /* first element */ \97}9899#define SLIST_HEAD_INITIALIZER(head) \100 { NULL }101102#define SLIST_ENTRY(type) \103struct { \104 struct type *sle_next; /* next element */ \105}106107/*108 * Singly-linked List access methods.109 */110#define SLIST_FIRST(head) ((head)->slh_first)111#define SLIST_END(head) NULL112#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))113#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)114115#define SLIST_FOREACH(var, head, field) \116 for((var) = SLIST_FIRST(head); \117 (var) != SLIST_END(head); \118 (var) = SLIST_NEXT(var, field))119120#define SLIST_FOREACH_SAFE(var, head, field, tvar) \121 for ((var) = SLIST_FIRST(head); \122 (var) && ((tvar) = SLIST_NEXT(var, field), 1); \123 (var) = (tvar))124125/*126 * Singly-linked List functions.127 */128#define SLIST_INIT(head) { \129 SLIST_FIRST(head) = SLIST_END(head); \130}131132#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \133 (elm)->field.sle_next = (slistelm)->field.sle_next; \134 (slistelm)->field.sle_next = (elm); \135} while (0)136137#define SLIST_INSERT_HEAD(head, elm, field) do { \138 (elm)->field.sle_next = (head)->slh_first; \139 (head)->slh_first = (elm); \140} while (0)141142#define SLIST_REMOVE_AFTER(elm, field) do { \143 (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \144} while (0)145146#define SLIST_REMOVE_HEAD(head, field) do { \147 (head)->slh_first = (head)->slh_first->field.sle_next; \148} while (0)149150#define SLIST_REMOVE(head, elm, type, field) do { \151 if ((head)->slh_first == (elm)) { \152 SLIST_REMOVE_HEAD((head), field); \153 } else { \154 struct type *curelm = (head)->slh_first; \155 \156 while (curelm->field.sle_next != (elm)) \157 curelm = curelm->field.sle_next; \158 curelm->field.sle_next = \159 curelm->field.sle_next->field.sle_next; \160 _Q_INVALIDATE((elm)->field.sle_next); \161 } \162} while (0)163164/*165 * List definitions.166 */167#define LIST_HEAD(name, type) \168struct name { \169 struct type *lh_first; /* first element */ \170}171172#define LIST_HEAD_INITIALIZER(head) \173 { NULL }174175#define LIST_ENTRY(type) \176struct { \177 struct type *le_next; /* next element */ \178 struct type **le_prev; /* address of previous next element */ \179}180181/*182 * List access methods183 */184#define LIST_FIRST(head) ((head)->lh_first)185#define LIST_END(head) NULL186#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))187#define LIST_NEXT(elm, field) ((elm)->field.le_next)188189#define LIST_FOREACH(var, head, field) \190 for((var) = LIST_FIRST(head); \191 (var)!= LIST_END(head); \192 (var) = LIST_NEXT(var, field))193194#define LIST_FOREACH_SAFE(var, head, field, tvar) \195 for ((var) = LIST_FIRST(head); \196 (var) && ((tvar) = LIST_NEXT(var, field), 1); \197 (var) = (tvar))198199/*200 * List functions.201 */202#define LIST_INIT(head) do { \203 LIST_FIRST(head) = LIST_END(head); \204} while (0)205206#define LIST_INSERT_AFTER(listelm, elm, field) do { \207 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \208 (listelm)->field.le_next->field.le_prev = \209 &(elm)->field.le_next; \210 (listelm)->field.le_next = (elm); \211 (elm)->field.le_prev = &(listelm)->field.le_next; \212} while (0)213214#define LIST_INSERT_BEFORE(listelm, elm, field) do { \215 (elm)->field.le_prev = (listelm)->field.le_prev; \216 (elm)->field.le_next = (listelm); \217 *(listelm)->field.le_prev = (elm); \218 (listelm)->field.le_prev = &(elm)->field.le_next; \219} while (0)220221#define LIST_INSERT_HEAD(head, elm, field) do { \222 if (((elm)->field.le_next = (head)->lh_first) != NULL) \223 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\224 (head)->lh_first = (elm); \225 (elm)->field.le_prev = &(head)->lh_first; \226} while (0)227228#define LIST_REMOVE(elm, field) do { \229 if ((elm)->field.le_next != NULL) \230 (elm)->field.le_next->field.le_prev = \231 (elm)->field.le_prev; \232 *(elm)->field.le_prev = (elm)->field.le_next; \233 _Q_INVALIDATE((elm)->field.le_prev); \234 _Q_INVALIDATE((elm)->field.le_next); \235} while (0)236237#define LIST_REPLACE(elm, elm2, field) do { \238 if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \239 (elm2)->field.le_next->field.le_prev = \240 &(elm2)->field.le_next; \241 (elm2)->field.le_prev = (elm)->field.le_prev; \242 *(elm2)->field.le_prev = (elm2); \243 _Q_INVALIDATE((elm)->field.le_prev); \244 _Q_INVALIDATE((elm)->field.le_next); \245} while (0)246247/*248 * Simple queue definitions.249 */250#define SIMPLEQ_HEAD(name, type) \251struct name { \252 struct type *sqh_first; /* first element */ \253 struct type **sqh_last; /* addr of last next element */ \254}255256#define SIMPLEQ_HEAD_INITIALIZER(head) \257 { NULL, &(head).sqh_first }258259#define SIMPLEQ_ENTRY(type) \260struct { \261 struct type *sqe_next; /* next element */ \262}263264/*265 * Simple queue access methods.266 */267#define SIMPLEQ_FIRST(head) ((head)->sqh_first)268#define SIMPLEQ_END(head) NULL269#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))270#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)271272#define SIMPLEQ_FOREACH(var, head, field) \273 for((var) = SIMPLEQ_FIRST(head); \274 (var) != SIMPLEQ_END(head); \275 (var) = SIMPLEQ_NEXT(var, field))276277#define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \278 for ((var) = SIMPLEQ_FIRST(head); \279 (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \280 (var) = (tvar))281282/*283 * Simple queue functions.284 */285#define SIMPLEQ_INIT(head) do { \286 (head)->sqh_first = NULL; \287 (head)->sqh_last = &(head)->sqh_first; \288} while (0)289290#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \291 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \292 (head)->sqh_last = &(elm)->field.sqe_next; \293 (head)->sqh_first = (elm); \294} while (0)295296#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \297 (elm)->field.sqe_next = NULL; \298 *(head)->sqh_last = (elm); \299 (head)->sqh_last = &(elm)->field.sqe_next; \300} while (0)301302#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \303 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\304 (head)->sqh_last = &(elm)->field.sqe_next; \305 (listelm)->field.sqe_next = (elm); \306} while (0)307308#define SIMPLEQ_REMOVE_HEAD(head, field) do { \309 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \310 (head)->sqh_last = &(head)->sqh_first; \311} while (0)312313#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \314 if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \315 == NULL) \316 (head)->sqh_last = &(elm)->field.sqe_next; \317} while (0)318319/*320 * XOR Simple queue definitions.321 */322#define XSIMPLEQ_HEAD(name, type) \323struct name { \324 struct type *sqx_first; /* first element */ \325 struct type **sqx_last; /* addr of last next element */ \326 unsigned long sqx_cookie; \327}328329#define XSIMPLEQ_ENTRY(type) \330struct { \331 struct type *sqx_next; /* next element */ \332}333334/*335 * XOR Simple queue access methods.336 */337#define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \338 (unsigned long)(ptr)))339#define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first))340#define XSIMPLEQ_END(head) NULL341#define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))342#define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))343344345#define XSIMPLEQ_FOREACH(var, head, field) \346 for ((var) = XSIMPLEQ_FIRST(head); \347 (var) != XSIMPLEQ_END(head); \348 (var) = XSIMPLEQ_NEXT(head, var, field))349350#define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \351 for ((var) = XSIMPLEQ_FIRST(head); \352 (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \353 (var) = (tvar))354355/*356 * XOR Simple queue functions.357 */358#define XSIMPLEQ_INIT(head) do { \359 arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \360 (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \361 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \362} while (0)363364#define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \365 if (((elm)->field.sqx_next = (head)->sqx_first) == \366 XSIMPLEQ_XOR(head, NULL)) \367 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \368 (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \369} while (0)370371#define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \372 (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \373 *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \374 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \375} while (0)376377#define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \378 if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \379 XSIMPLEQ_XOR(head, NULL)) \380 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \381 (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \382} while (0)383384#define XSIMPLEQ_REMOVE_HEAD(head, field) do { \385 if (((head)->sqx_first = XSIMPLEQ_XOR(head, \386 (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \387 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \388} while (0)389390#define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \391 if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \392 (elm)->field.sqx_next)->field.sqx_next) \393 == XSIMPLEQ_XOR(head, NULL)) \394 (head)->sqx_last = \395 XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \396} while (0)397398399/*400 * Tail queue definitions.401 */402#define TAILQ_HEAD(name, type) \403struct name { \404 struct type *tqh_first; /* first element */ \405 struct type **tqh_last; /* addr of last next element */ \406}407408#define TAILQ_HEAD_INITIALIZER(head) \409 { NULL, &(head).tqh_first }410411#define TAILQ_ENTRY(type) \412struct { \413 struct type *tqe_next; /* next element */ \414 struct type **tqe_prev; /* address of previous next element */ \415}416417/*418 * tail queue access methods419 */420#define TAILQ_FIRST(head) ((head)->tqh_first)421#define TAILQ_END(head) NULL422#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)423#define TAILQ_LAST(head, headname) \424 (*(((struct headname *)((head)->tqh_last))->tqh_last))425/* XXX */426#define TAILQ_PREV(elm, headname, field) \427 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))428#define TAILQ_EMPTY(head) \429 (TAILQ_FIRST(head) == TAILQ_END(head))430431#define TAILQ_FOREACH(var, head, field) \432 for((var) = TAILQ_FIRST(head); \433 (var) != TAILQ_END(head); \434 (var) = TAILQ_NEXT(var, field))435436#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \437 for ((var) = TAILQ_FIRST(head); \438 (var) != TAILQ_END(head) && \439 ((tvar) = TAILQ_NEXT(var, field), 1); \440 (var) = (tvar))441442443#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \444 for((var) = TAILQ_LAST(head, headname); \445 (var) != TAILQ_END(head); \446 (var) = TAILQ_PREV(var, headname, field))447448#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \449 for ((var) = TAILQ_LAST(head, headname); \450 (var) != TAILQ_END(head) && \451 ((tvar) = TAILQ_PREV(var, headname, field), 1); \452 (var) = (tvar))453454/*455 * Tail queue functions.456 */457#define TAILQ_INIT(head) do { \458 (head)->tqh_first = NULL; \459 (head)->tqh_last = &(head)->tqh_first; \460} while (0)461462#define TAILQ_INSERT_HEAD(head, elm, field) do { \463 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \464 (head)->tqh_first->field.tqe_prev = \465 &(elm)->field.tqe_next; \466 else \467 (head)->tqh_last = &(elm)->field.tqe_next; \468 (head)->tqh_first = (elm); \469 (elm)->field.tqe_prev = &(head)->tqh_first; \470} while (0)471472#define TAILQ_INSERT_TAIL(head, elm, field) do { \473 (elm)->field.tqe_next = NULL; \474 (elm)->field.tqe_prev = (head)->tqh_last; \475 *(head)->tqh_last = (elm); \476 (head)->tqh_last = &(elm)->field.tqe_next; \477} while (0)478479#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \480 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\481 (elm)->field.tqe_next->field.tqe_prev = \482 &(elm)->field.tqe_next; \483 else \484 (head)->tqh_last = &(elm)->field.tqe_next; \485 (listelm)->field.tqe_next = (elm); \486 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \487} while (0)488489#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \490 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \491 (elm)->field.tqe_next = (listelm); \492 *(listelm)->field.tqe_prev = (elm); \493 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \494} while (0)495496#define TAILQ_REMOVE(head, elm, field) do { \497 if (((elm)->field.tqe_next) != NULL) \498 (elm)->field.tqe_next->field.tqe_prev = \499 (elm)->field.tqe_prev; \500 else \501 (head)->tqh_last = (elm)->field.tqe_prev; \502 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \503 _Q_INVALIDATE((elm)->field.tqe_prev); \504 _Q_INVALIDATE((elm)->field.tqe_next); \505} while (0)506507#define TAILQ_REPLACE(head, elm, elm2, field) do { \508 if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \509 (elm2)->field.tqe_next->field.tqe_prev = \510 &(elm2)->field.tqe_next; \511 else \512 (head)->tqh_last = &(elm2)->field.tqe_next; \513 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \514 *(elm2)->field.tqe_prev = (elm2); \515 _Q_INVALIDATE((elm)->field.tqe_prev); \516 _Q_INVALIDATE((elm)->field.tqe_next); \517} while (0)518519/*520 * Circular queue definitions.521 */522#define CIRCLEQ_HEAD(name, type) \523struct name { \524 struct type *cqh_first; /* first element */ \525 struct type *cqh_last; /* last element */ \526}527528#define CIRCLEQ_HEAD_INITIALIZER(head) \529 { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }530531#define CIRCLEQ_ENTRY(type) \532struct { \533 struct type *cqe_next; /* next element */ \534 struct type *cqe_prev; /* previous element */ \535}536537/*538 * Circular queue access methods539 */540#define CIRCLEQ_FIRST(head) ((head)->cqh_first)541#define CIRCLEQ_LAST(head) ((head)->cqh_last)542#define CIRCLEQ_END(head) ((void *)(head))543#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)544#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)545#define CIRCLEQ_EMPTY(head) \546 (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))547548#define CIRCLEQ_FOREACH(var, head, field) \549 for((var) = CIRCLEQ_FIRST(head); \550 (var) != CIRCLEQ_END(head); \551 (var) = CIRCLEQ_NEXT(var, field))552553#define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \554 for ((var) = CIRCLEQ_FIRST(head); \555 (var) != CIRCLEQ_END(head) && \556 ((tvar) = CIRCLEQ_NEXT(var, field), 1); \557 (var) = (tvar))558559#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \560 for((var) = CIRCLEQ_LAST(head); \561 (var) != CIRCLEQ_END(head); \562 (var) = CIRCLEQ_PREV(var, field))563564#define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \565 for ((var) = CIRCLEQ_LAST(head, headname); \566 (var) != CIRCLEQ_END(head) && \567 ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \568 (var) = (tvar))569570/*571 * Circular queue functions.572 */573#define CIRCLEQ_INIT(head) do { \574 (head)->cqh_first = CIRCLEQ_END(head); \575 (head)->cqh_last = CIRCLEQ_END(head); \576} while (0)577578#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \579 (elm)->field.cqe_next = (listelm)->field.cqe_next; \580 (elm)->field.cqe_prev = (listelm); \581 if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \582 (head)->cqh_last = (elm); \583 else \584 (listelm)->field.cqe_next->field.cqe_prev = (elm); \585 (listelm)->field.cqe_next = (elm); \586} while (0)587588#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \589 (elm)->field.cqe_next = (listelm); \590 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \591 if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \592 (head)->cqh_first = (elm); \593 else \594 (listelm)->field.cqe_prev->field.cqe_next = (elm); \595 (listelm)->field.cqe_prev = (elm); \596} while (0)597598#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \599 (elm)->field.cqe_next = (head)->cqh_first; \600 (elm)->field.cqe_prev = CIRCLEQ_END(head); \601 if ((head)->cqh_last == CIRCLEQ_END(head)) \602 (head)->cqh_last = (elm); \603 else \604 (head)->cqh_first->field.cqe_prev = (elm); \605 (head)->cqh_first = (elm); \606} while (0)607608#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \609 (elm)->field.cqe_next = CIRCLEQ_END(head); \610 (elm)->field.cqe_prev = (head)->cqh_last; \611 if ((head)->cqh_first == CIRCLEQ_END(head)) \612 (head)->cqh_first = (elm); \613 else \614 (head)->cqh_last->field.cqe_next = (elm); \615 (head)->cqh_last = (elm); \616} while (0)617618#define CIRCLEQ_REMOVE(head, elm, field) do { \619 if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \620 (head)->cqh_last = (elm)->field.cqe_prev; \621 else \622 (elm)->field.cqe_next->field.cqe_prev = \623 (elm)->field.cqe_prev; \624 if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \625 (head)->cqh_first = (elm)->field.cqe_next; \626 else \627 (elm)->field.cqe_prev->field.cqe_next = \628 (elm)->field.cqe_next; \629 _Q_INVALIDATE((elm)->field.cqe_prev); \630 _Q_INVALIDATE((elm)->field.cqe_next); \631} while (0)632633#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \634 if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \635 CIRCLEQ_END(head)) \636 (head)->cqh_last = (elm2); \637 else \638 (elm2)->field.cqe_next->field.cqe_prev = (elm2); \639 if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \640 CIRCLEQ_END(head)) \641 (head)->cqh_first = (elm2); \642 else \643 (elm2)->field.cqe_prev->field.cqe_next = (elm2); \644 _Q_INVALIDATE((elm)->field.cqe_prev); \645 _Q_INVALIDATE((elm)->field.cqe_next); \646} while (0)647648#endif /* !_SYS_QUEUE_H_ */