gonzui

    1: /*      $OpenBSD: queue.h,v 1.35 2012/01/11 00:06:48 bluhm Exp $     */
    2: /*      $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $    */
    3: 
    4: /*
    5:  * Copyright (c) 1991, 1993
    6:  *      The Regents of the University of California.  All rights reserved.
    7:  *
    8:  * Redistribution and use in source and binary forms, with or without
    9:  * modification, are permitted provided that the following conditions
   10:  * are met:
   11:  * 1. Redistributions of source code must retain the above copyright
   12:  *    notice, this list of conditions and the following disclaimer.
   13:  * 2. Redistributions in binary form must reproduce the above copyright
   14:  *    notice, this list of conditions and the following disclaimer in the
   15:  *    documentation and/or other materials provided with the distribution.
   16:  * 3. Neither the name of the University nor the names of its contributors
   17:  *    may be used to endorse or promote products derived from this software
   18:  *    without specific prior written permission.
   19:  *
   20:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   21:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   22:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   23:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   24:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   25:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   26:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   27:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   28:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   29:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   30:  * SUCH DAMAGE.
   31:  *
   32:  *      @(#)queue.h  8.5 (Berkeley) 8/20/94
   33:  */
   34: 
   35: #ifndef _SYS_QUEUE_H_
   36: #define _SYS_QUEUE_H_
   37: 
   38: /*
   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 elements
   44:  * are singly linked for minimum space and pointer manipulation overhead at
   45:  * the expense of O(n) removal for arbitrary elements. New elements can be
   46:  * 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 explicit
   48:  * macro for this purpose for optimum efficiency. A singly-linked list may
   49:  * only be traversed in the forward direction.  Singly-linked lists are ideal
   50:  * for applications with large datasets and few or no removals or for
   51:  * implementing a LIFO queue.
   52:  *
   53:  * A list is headed by a single forward pointer (or an array of forward
   54:  * pointers for a hash table header). The elements are doubly linked
   55:  * so that an arbitrary element can be removed without a need to
   56:  * traverse the list. New elements can be added to the list before
   57:  * or after an existing element or at the head of the list. A list
   58:  * may only be traversed in the forward direction.
   59:  *
   60:  * A simple queue is headed by a pair of pointers, one the head of the
   61:  * list and the other to the tail of the list. The elements are singly
   62:  * linked to save space, so elements can only be removed from the
   63:  * head of the list. New elements can be added to the list before or after
   64:  * an existing element, at the head of the list, or at the end of the
   65:  * 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 the
   68:  * list and the other to the tail of the list. The elements are doubly
   69:  * linked so that an arbitrary element can be removed without a need to
   70:  * traverse the list. New elements can be added to the list before or
   71:  * after an existing element, at the head of the list, or at the end of
   72:  * 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 the
   75:  * list and the other to the tail of the list. The elements are doubly
   76:  * linked so that an arbitrary element can be removed without a need to
   77:  * traverse the list. New elements can be added to the list before or after
   78:  * 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 more
   80:  * complex end of list detection.
   81:  *
   82:  * For details on the use of these macros, see the queue(3) manual page.
   83:  */
   84: 
   85: #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
   86: #define _Q_INVALIDATE(a) (a) = ((void *)-1)
   87: #else
   88: #define _Q_INVALIDATE(a)
   89: #endif
   90: 
   91: /*
   92:  * Singly-linked List definitions.
   93:  */
   94: #define SLIST_HEAD(name, type)                                          \
   95: struct name {                                                           \
   96:         struct type *slh_first;        /* first element */                    \
   97: }
   98:  
   99: #define SLIST_HEAD_INITIALIZER(head)                                    \
  100:         { NULL }
  101:  
  102: #define SLIST_ENTRY(type)                                               \
  103: struct {                                                                \
  104:         struct type *sle_next; /* next element */                      \
  105: }
  106:  
  107: /*
  108:  * Singly-linked List access methods.
  109:  */
  110: #define SLIST_FIRST(head)       ((head)->slh_first)
  111: #define SLIST_END(head)         NULL
  112: #define SLIST_EMPTY(head)       (SLIST_FIRST(head) == SLIST_END(head))
  113: #define SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
  114: 
  115: #define SLIST_FOREACH(var, head, field)                                 \
  116:         for((var) = SLIST_FIRST(head);                                 \
  117:             (var) != SLIST_END(head);                                  \
  118:             (var) = SLIST_NEXT(var, field))
  119: 
  120: #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))
  124: 
  125: /*
  126:  * Singly-linked List functions.
  127:  */
  128: #define SLIST_INIT(head) {                                              \
  129:         SLIST_FIRST(head) = SLIST_END(head);                           \
  130: }
  131: 
  132: #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)
  136: 
  137: #define SLIST_INSERT_HEAD(head, elm, field) do {                        \
  138:         (elm)->field.sle_next = (head)->slh_first;                     \
  139:         (head)->slh_first = (elm);                                     \
  140: } while (0)
  141: 
  142: #define SLIST_REMOVE_NEXT(head, elm, field) do {                        \
  143:         (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
  144: } while (0)
  145: 
  146: #define SLIST_REMOVE_HEAD(head, field) do {                             \
  147:         (head)->slh_first = (head)->slh_first->field.sle_next;         \
  148: } while (0)
  149: 
  150: #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)
  163: 
  164: /*
  165:  * List definitions.
  166:  */
  167: #define LIST_HEAD(name, type)                                           \
  168: struct name {                                                           \
  169:         struct type *lh_first; /* first element */                     \
  170: }
  171: 
  172: #define LIST_HEAD_INITIALIZER(head)                                     \
  173:         { NULL }
  174: 
  175: #define LIST_ENTRY(type)                                                \
  176: struct {                                                                \
  177:         struct type *le_next;  /* next element */                       \
  178:         struct type **le_prev; /* address of previous next element */  \
  179: }
  180: 
  181: /*
  182:  * List access methods
  183:  */
  184: #define LIST_FIRST(head)                ((head)->lh_first)
  185: #define LIST_END(head)                  NULL
  186: #define LIST_EMPTY(head)                (LIST_FIRST(head) == LIST_END(head))
  187: #define LIST_NEXT(elm, field)           ((elm)->field.le_next)
  188: 
  189: #define LIST_FOREACH(var, head, field)                                  \
  190:         for((var) = LIST_FIRST(head);                                  \
  191:             (var)!= LIST_END(head);                                    \
  192:             (var) = LIST_NEXT(var, field))
  193: 
  194: #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))
  198: 
  199: /*
  200:  * List functions.
  201:  */
  202: #define LIST_INIT(head) do {                                            \
  203:         LIST_FIRST(head) = LIST_END(head);                             \
  204: } while (0)
  205: 
  206: #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)
  213: 
  214: #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)
  220: 
  221: #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)
  227: 
  228: #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)
  236: 
  237: #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)
  246: 
  247: /*
  248:  * Simple queue definitions.
  249:  */
  250: #define SIMPLEQ_HEAD(name, type)                                        \
  251: struct name {                                                           \
  252:         struct type *sqh_first;        /* first element */                    \
  253:         struct type **sqh_last;        /* addr of last next element */                \
  254: }
  255: 
  256: #define SIMPLEQ_HEAD_INITIALIZER(head)                                  \
  257:         { NULL, &(head).sqh_first }
  258: 
  259: #define SIMPLEQ_ENTRY(type)                                             \
  260: struct {                                                                \
  261:         struct type *sqe_next; /* next element */                      \
  262: }
  263: 
  264: /*
  265:  * Simple queue access methods.
  266:  */
  267: #define SIMPLEQ_FIRST(head)         ((head)->sqh_first)
  268: #define SIMPLEQ_END(head)           NULL
  269: #define SIMPLEQ_EMPTY(head)         (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
  270: #define SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)
  271: 
  272: #define SIMPLEQ_FOREACH(var, head, field)                               \
  273:         for((var) = SIMPLEQ_FIRST(head);                               \
  274:             (var) != SIMPLEQ_END(head);                                        \
  275:             (var) = SIMPLEQ_NEXT(var, field))
  276: 
  277: #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))
  281: 
  282: /*
  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)
  289: 
  290: #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)
  295: 
  296: #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)
  301: 
  302: #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)
  307: 
  308: #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)
  312: 
  313: #define SIMPLEQ_REMOVE_NEXT(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)
  318: 
  319: /*
  320:  * Tail queue definitions.
  321:  */
  322: #define TAILQ_HEAD(name, type)                                          \
  323: struct name {                                                           \
  324:         struct type *tqh_first;        /* first element */                    \
  325:         struct type **tqh_last;        /* addr of last next element */                \
  326: }
  327: 
  328: #define TAILQ_HEAD_INITIALIZER(head)                                    \
  329:         { NULL, &(head).tqh_first }
  330: 
  331: #define TAILQ_ENTRY(type)                                               \
  332: struct {                                                                \
  333:         struct type *tqe_next; /* next element */                      \
  334:         struct type **tqe_prev;        /* address of previous next element */ \
  335: }
  336: 
  337: /* 
  338:  * tail queue access methods 
  339:  */
  340: #define TAILQ_FIRST(head)               ((head)->tqh_first)
  341: #define TAILQ_END(head)                 NULL
  342: #define TAILQ_NEXT(elm, field)          ((elm)->field.tqe_next)
  343: #define TAILQ_LAST(head, headname)                                      \
  344:         (*(((struct headname *)((head)->tqh_last))->tqh_last))
  345: /* XXX */
  346: #define TAILQ_PREV(elm, headname, field)                                \
  347:         (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
  348: #define TAILQ_EMPTY(head)                                               \
  349:         (TAILQ_FIRST(head) == TAILQ_END(head))
  350: 
  351: #define TAILQ_FOREACH(var, head, field)                                 \
  352:         for((var) = TAILQ_FIRST(head);                                 \
  353:             (var) != TAILQ_END(head);                                  \
  354:             (var) = TAILQ_NEXT(var, field))
  355: 
  356: #define TAILQ_FOREACH_SAFE(var, head, field, tvar)                      \
  357:         for ((var) = TAILQ_FIRST(head);                                        \
  358:             (var) != TAILQ_END(head) &&                                        \
  359:             ((tvar) = TAILQ_NEXT(var, field), 1);                      \
  360:             (var) = (tvar))
  361: 
  362: 
  363: #define TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
  364:         for((var) = TAILQ_LAST(head, headname);                                \
  365:             (var) != TAILQ_END(head);                                  \
  366:             (var) = TAILQ_PREV(var, headname, field))
  367: 
  368: #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)    \
  369:         for ((var) = TAILQ_LAST(head, headname);                       \
  370:             (var) != TAILQ_END(head) &&                                        \
  371:             ((tvar) = TAILQ_PREV(var, headname, field), 1);            \
  372:             (var) = (tvar))
  373: 
  374: /*
  375:  * Tail queue functions.
  376:  */
  377: #define TAILQ_INIT(head) do {                                           \
  378:         (head)->tqh_first = NULL;                                      \
  379:         (head)->tqh_last = &(head)->tqh_first;                         \
  380: } while (0)
  381: 
  382: #define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
  383:         if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)       \
  384:                 (head)->tqh_first->field.tqe_prev =                   \
  385:                     &(elm)->field.tqe_next;                           \
  386:         else                                                           \
  387:                 (head)->tqh_last = &(elm)->field.tqe_next;            \
  388:         (head)->tqh_first = (elm);                                     \
  389:         (elm)->field.tqe_prev = &(head)->tqh_first;                    \
  390: } while (0)
  391: 
  392: #define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
  393:         (elm)->field.tqe_next = NULL;                                  \
  394:         (elm)->field.tqe_prev = (head)->tqh_last;                      \
  395:         *(head)->tqh_last = (elm);                                     \
  396:         (head)->tqh_last = &(elm)->field.tqe_next;                     \
  397: } while (0)
  398: 
  399: #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
  400:         if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
  401:                 (elm)->field.tqe_next->field.tqe_prev =                       \
  402:                     &(elm)->field.tqe_next;                           \
  403:         else                                                           \
  404:                 (head)->tqh_last = &(elm)->field.tqe_next;            \
  405:         (listelm)->field.tqe_next = (elm);                             \
  406:         (elm)->field.tqe_prev = &(listelm)->field.tqe_next;            \
  407: } while (0)
  408: 
  409: #define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
  410:         (elm)->field.tqe_prev = (listelm)->field.tqe_prev;             \
  411:         (elm)->field.tqe_next = (listelm);                             \
  412:         *(listelm)->field.tqe_prev = (elm);                            \
  413:         (listelm)->field.tqe_prev = &(elm)->field.tqe_next;            \
  414: } while (0)
  415: 
  416: #define TAILQ_REMOVE(head, elm, field) do {                             \
  417:         if (((elm)->field.tqe_next) != NULL)                           \
  418:                 (elm)->field.tqe_next->field.tqe_prev =                       \
  419:                     (elm)->field.tqe_prev;                            \
  420:         else                                                           \
  421:                 (head)->tqh_last = (elm)->field.tqe_prev;             \
  422:         *(elm)->field.tqe_prev = (elm)->field.tqe_next;                        \
  423:         _Q_INVALIDATE((elm)->field.tqe_prev);                          \
  424:         _Q_INVALIDATE((elm)->field.tqe_next);                          \
  425: } while (0)
  426: 
  427: #define TAILQ_REPLACE(head, elm, elm2, field) do {                      \
  428:         if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)  \
  429:                 (elm2)->field.tqe_next->field.tqe_prev =              \
  430:                     &(elm2)->field.tqe_next;                          \
  431:         else                                                           \
  432:                 (head)->tqh_last = &(elm2)->field.tqe_next;           \
  433:         (elm2)->field.tqe_prev = (elm)->field.tqe_prev;                        \
  434:         *(elm2)->field.tqe_prev = (elm2);                              \
  435:         _Q_INVALIDATE((elm)->field.tqe_prev);                          \
  436:         _Q_INVALIDATE((elm)->field.tqe_next);                          \
  437: } while (0)
  438: 
  439: /*
  440:  * Circular queue definitions.
  441:  */
  442: #define CIRCLEQ_HEAD(name, type)                                        \
  443: struct name {                                                           \
  444:         struct type *cqh_first;                /* first element */           \
  445:         struct type *cqh_last;         /* last element */             \
  446: }
  447: 
  448: #define CIRCLEQ_HEAD_INITIALIZER(head)                                  \
  449:         { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
  450: 
  451: #define CIRCLEQ_ENTRY(type)                                             \
  452: struct {                                                                \
  453:         struct type *cqe_next;         /* next element */             \
  454:         struct type *cqe_prev;         /* previous element */         \
  455: }
  456: 
  457: /*
  458:  * Circular queue access methods 
  459:  */
  460: #define CIRCLEQ_FIRST(head)             ((head)->cqh_first)
  461: #define CIRCLEQ_LAST(head)              ((head)->cqh_last)
  462: #define CIRCLEQ_END(head)               ((void *)(head))
  463: #define CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)
  464: #define CIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)
  465: #define CIRCLEQ_EMPTY(head)                                             \
  466:         (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
  467: 
  468: #define CIRCLEQ_FOREACH(var, head, field)                               \
  469:         for((var) = CIRCLEQ_FIRST(head);                               \
  470:             (var) != CIRCLEQ_END(head);                                        \
  471:             (var) = CIRCLEQ_NEXT(var, field))
  472: 
  473: #define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar)                    \
  474:         for ((var) = CIRCLEQ_FIRST(head);                              \
  475:             (var) != CIRCLEQ_END(head) &&                              \
  476:             ((tvar) = CIRCLEQ_NEXT(var, field), 1);                    \
  477:             (var) = (tvar))
  478: 
  479: #define CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \
  480:         for((var) = CIRCLEQ_LAST(head);                                        \
  481:             (var) != CIRCLEQ_END(head);                                        \
  482:             (var) = CIRCLEQ_PREV(var, field))
  483: 
  484: #define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)  \
  485:         for ((var) = CIRCLEQ_LAST(head, headname);                     \
  486:             (var) != CIRCLEQ_END(head) &&                              \
  487:             ((tvar) = CIRCLEQ_PREV(var, headname, field), 1);          \
  488:             (var) = (tvar))
  489: 
  490: /*
  491:  * Circular queue functions.
  492:  */
  493: #define CIRCLEQ_INIT(head) do {                                         \
  494:         (head)->cqh_first = CIRCLEQ_END(head);                         \
  495:         (head)->cqh_last = CIRCLEQ_END(head);                          \
  496: } while (0)
  497: 
  498: #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
  499:         (elm)->field.cqe_next = (listelm)->field.cqe_next;             \
  500:         (elm)->field.cqe_prev = (listelm);                             \
  501:         if ((listelm)->field.cqe_next == CIRCLEQ_END(head))            \
  502:                 (head)->cqh_last = (elm);                             \
  503:         else                                                           \
  504:                 (listelm)->field.cqe_next->field.cqe_prev = (elm);    \
  505:         (listelm)->field.cqe_next = (elm);                             \
  506: } while (0)
  507: 
  508: #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {           \
  509:         (elm)->field.cqe_next = (listelm);                             \
  510:         (elm)->field.cqe_prev = (listelm)->field.cqe_prev;             \
  511:         if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))            \
  512:                 (head)->cqh_first = (elm);                            \
  513:         else                                                           \
  514:                 (listelm)->field.cqe_prev->field.cqe_next = (elm);    \
  515:         (listelm)->field.cqe_prev = (elm);                             \
  516: } while (0)
  517: 
  518: #define CIRCLEQ_INSERT_HEAD(head, elm, field) do {                      \
  519:         (elm)->field.cqe_next = (head)->cqh_first;                     \
  520:         (elm)->field.cqe_prev = CIRCLEQ_END(head);                     \
  521:         if ((head)->cqh_last == CIRCLEQ_END(head))                     \
  522:                 (head)->cqh_last = (elm);                             \
  523:         else                                                           \
  524:                 (head)->cqh_first->field.cqe_prev = (elm);            \
  525:         (head)->cqh_first = (elm);                                     \
  526: } while (0)
  527: 
  528: #define CIRCLEQ_INSERT_TAIL(head, elm, field) do {                      \
  529:         (elm)->field.cqe_next = CIRCLEQ_END(head);                     \
  530:         (elm)->field.cqe_prev = (head)->cqh_last;                      \
  531:         if ((head)->cqh_first == CIRCLEQ_END(head))                    \
  532:                 (head)->cqh_first = (elm);                            \
  533:         else                                                           \
  534:                 (head)->cqh_last->field.cqe_next = (elm);             \
  535:         (head)->cqh_last = (elm);                                      \
  536: } while (0)
  537: 
  538: #define CIRCLEQ_REMOVE(head, elm, field) do {                           \
  539:         if ((elm)->field.cqe_next == CIRCLEQ_END(head))                        \
  540:                 (head)->cqh_last = (elm)->field.cqe_prev;             \
  541:         else                                                           \
  542:                 (elm)->field.cqe_next->field.cqe_prev =                       \
  543:                     (elm)->field.cqe_prev;                            \
  544:         if ((elm)->field.cqe_prev == CIRCLEQ_END(head))                        \
  545:                 (head)->cqh_first = (elm)->field.cqe_next;            \
  546:         else                                                           \
  547:                 (elm)->field.cqe_prev->field.cqe_next =                       \
  548:                     (elm)->field.cqe_next;                            \
  549:         _Q_INVALIDATE((elm)->field.cqe_prev);                          \
  550:         _Q_INVALIDATE((elm)->field.cqe_next);                          \
  551: } while (0)
  552: 
  553: #define CIRCLEQ_REPLACE(head, elm, elm2, field) do {                    \
  554:         if (((elm2)->field.cqe_next = (elm)->field.cqe_next) ==                \
  555:             CIRCLEQ_END(head))                                         \
  556:                 (head).cqh_last = (elm2);                             \
  557:         else                                                           \
  558:                 (elm2)->field.cqe_next->field.cqe_prev = (elm2);      \
  559:         if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) ==                \
  560:             CIRCLEQ_END(head))                                         \
  561:                 (head).cqh_first = (elm2);                            \
  562:         else                                                           \
  563:                 (elm2)->field.cqe_prev->field.cqe_next = (elm2);      \
  564:         _Q_INVALIDATE((elm)->field.cqe_prev);                          \
  565:         _Q_INVALIDATE((elm)->field.cqe_next);                          \
  566: } while (0)
  567: 
  568: #endif  /* !_SYS_QUEUE_H_ */