sad

simple audio daemon
git clone git://git.2f30.org/sad
Log | Files | Refs | LICENSE

queue.h (35044B)


      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 $	*/
      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); (var) != SLIST_END(head);                    \
    117        (var) = SLIST_NEXT(var, field))
    118 
    119 #define SLIST_FOREACH_SAFE(var, head, field, tvar)                             \
    120   for ((var) = SLIST_FIRST(head);                                              \
    121        (var) && ((tvar) = SLIST_NEXT(var, field), 1); (var) = (tvar))
    122 
    123 /*
    124  * Singly-linked List functions.
    125  */
    126 #define SLIST_INIT(head)                                                       \
    127   { SLIST_FIRST(head) = SLIST_END(head); }
    128 
    129 #define SLIST_INSERT_AFTER(slistelm, elm, field)                               \
    130   do {                                                                         \
    131     (elm)->field.sle_next = (slistelm)->field.sle_next;                        \
    132     (slistelm)->field.sle_next = (elm);                                        \
    133   } while (0)
    134 
    135 #define SLIST_INSERT_HEAD(head, elm, field)                                    \
    136   do {                                                                         \
    137     (elm)->field.sle_next = (head)->slh_first;                                 \
    138     (head)->slh_first = (elm);                                                 \
    139   } while (0)
    140 
    141 #define SLIST_REMOVE_AFTER(elm, field)                                         \
    142   do {                                                                         \
    143     (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next;             \
    144   } while (0)
    145 
    146 #define SLIST_REMOVE_HEAD(head, field)                                         \
    147   do {                                                                         \
    148     (head)->slh_first = (head)->slh_first->field.sle_next;                     \
    149   } while (0)
    150 
    151 #define SLIST_REMOVE(head, elm, type, field)                                   \
    152   do {                                                                         \
    153     if ((head)->slh_first == (elm)) {                                          \
    154       SLIST_REMOVE_HEAD((head), field);                                        \
    155     } else {                                                                   \
    156       struct type *curelm = (head)->slh_first;                                 \
    157                                                                                \
    158       while (curelm->field.sle_next != (elm))                                  \
    159         curelm = curelm->field.sle_next;                                       \
    160       curelm->field.sle_next = curelm->field.sle_next->field.sle_next;         \
    161       _Q_INVALIDATE((elm)->field.sle_next);                                    \
    162     }                                                                          \
    163   } while (0)
    164 
    165 /*
    166  * List definitions.
    167  */
    168 #define LIST_HEAD(name, type)                                                  \
    169   struct name {                                                                \
    170     struct type *lh_first; /* first element */                                 \
    171   }
    172 
    173 #define LIST_HEAD_INITIALIZER(head)                                            \
    174   { NULL }
    175 
    176 #define LIST_ENTRY(type)                                                       \
    177   struct {                                                                     \
    178     struct type *le_next;  /* next element */                                  \
    179     struct type **le_prev; /* address of previous next element */              \
    180   }
    181 
    182 /*
    183  * List access methods
    184  */
    185 #define LIST_FIRST(head) ((head)->lh_first)
    186 #define LIST_END(head) NULL
    187 #define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
    188 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
    189 
    190 #define LIST_FOREACH(var, head, field)                                         \
    191   for ((var) = LIST_FIRST(head); (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); (var) && ((tvar) = LIST_NEXT(var, field), 1); \
    196        (var) = (tvar))
    197 
    198 /*
    199  * List functions.
    200  */
    201 #define LIST_INIT(head)                                                        \
    202   do {                                                                         \
    203     LIST_FIRST(head) = LIST_END(head);                                         \
    204   } while (0)
    205 
    206 #define LIST_INSERT_AFTER(listelm, elm, field)                                 \
    207   do {                                                                         \
    208     if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)             \
    209       (listelm)->field.le_next->field.le_prev = &(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)                                \
    215   do {                                                                         \
    216     (elm)->field.le_prev = (listelm)->field.le_prev;                           \
    217     (elm)->field.le_next = (listelm);                                          \
    218     *(listelm)->field.le_prev = (elm);                                         \
    219     (listelm)->field.le_prev = &(elm)->field.le_next;                          \
    220   } while (0)
    221 
    222 #define LIST_INSERT_HEAD(head, elm, field)                                     \
    223   do {                                                                         \
    224     if (((elm)->field.le_next = (head)->lh_first) != NULL)                     \
    225       (head)->lh_first->field.le_prev = &(elm)->field.le_next;                 \
    226     (head)->lh_first = (elm);                                                  \
    227     (elm)->field.le_prev = &(head)->lh_first;                                  \
    228   } while (0)
    229 
    230 #define LIST_REMOVE(elm, field)                                                \
    231   do {                                                                         \
    232     if ((elm)->field.le_next != NULL)                                          \
    233       (elm)->field.le_next->field.le_prev = (elm)->field.le_prev;              \
    234     *(elm)->field.le_prev = (elm)->field.le_next;                              \
    235     _Q_INVALIDATE((elm)->field.le_prev);                                       \
    236     _Q_INVALIDATE((elm)->field.le_next);                                       \
    237   } while (0)
    238 
    239 #define LIST_REPLACE(elm, elm2, field)                                         \
    240   do {                                                                         \
    241     if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)                \
    242       (elm2)->field.le_next->field.le_prev = &(elm2)->field.le_next;           \
    243     (elm2)->field.le_prev = (elm)->field.le_prev;                              \
    244     *(elm2)->field.le_prev = (elm2);                                           \
    245     _Q_INVALIDATE((elm)->field.le_prev);                                       \
    246     _Q_INVALIDATE((elm)->field.le_next);                                       \
    247   } while (0)
    248 
    249 /*
    250  * Simple queue definitions.
    251  */
    252 #define SIMPLEQ_HEAD(name, type)                                               \
    253   struct name {                                                                \
    254     struct type *sqh_first; /* first element */                                \
    255     struct type **sqh_last; /* addr of last next element */                    \
    256   }
    257 
    258 #define SIMPLEQ_HEAD_INITIALIZER(head)                                         \
    259   { NULL, &(head).sqh_first }
    260 
    261 #define SIMPLEQ_ENTRY(type)                                                    \
    262   struct {                                                                     \
    263     struct type *sqe_next; /* next element */                                  \
    264   }
    265 
    266 /*
    267  * Simple queue access methods.
    268  */
    269 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
    270 #define SIMPLEQ_END(head) NULL
    271 #define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
    272 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
    273 
    274 #define SIMPLEQ_FOREACH(var, head, field)                                      \
    275   for ((var) = SIMPLEQ_FIRST(head); (var) != SIMPLEQ_END(head);                \
    276        (var) = SIMPLEQ_NEXT(var, field))
    277 
    278 #define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar)                           \
    279   for ((var) = SIMPLEQ_FIRST(head);                                            \
    280        (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); (var) = (tvar))
    281 
    282 /*
    283  * Simple queue functions.
    284  */
    285 #define SIMPLEQ_INIT(head)                                                     \
    286   do {                                                                         \
    287     (head)->sqh_first = NULL;                                                  \
    288     (head)->sqh_last = &(head)->sqh_first;                                     \
    289   } while (0)
    290 
    291 #define SIMPLEQ_INSERT_HEAD(head, elm, field)                                  \
    292   do {                                                                         \
    293     if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)                   \
    294       (head)->sqh_last = &(elm)->field.sqe_next;                               \
    295     (head)->sqh_first = (elm);                                                 \
    296   } while (0)
    297 
    298 #define SIMPLEQ_INSERT_TAIL(head, elm, field)                                  \
    299   do {                                                                         \
    300     (elm)->field.sqe_next = NULL;                                              \
    301     *(head)->sqh_last = (elm);                                                 \
    302     (head)->sqh_last = &(elm)->field.sqe_next;                                 \
    303   } while (0)
    304 
    305 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field)                        \
    306   do {                                                                         \
    307     if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)           \
    308       (head)->sqh_last = &(elm)->field.sqe_next;                               \
    309     (listelm)->field.sqe_next = (elm);                                         \
    310   } while (0)
    311 
    312 #define SIMPLEQ_REMOVE_HEAD(head, field)                                       \
    313   do {                                                                         \
    314     if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL)       \
    315       (head)->sqh_last = &(head)->sqh_first;                                   \
    316   } while (0)
    317 
    318 #define SIMPLEQ_REMOVE_AFTER(head, elm, field)                                 \
    319   do {                                                                         \
    320     if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) ==     \
    321         NULL)                                                                  \
    322       (head)->sqh_last = &(elm)->field.sqe_next;                               \
    323   } while (0)
    324 
    325 /*
    326  * XOR Simple queue definitions.
    327  */
    328 #define XSIMPLEQ_HEAD(name, type)                                              \
    329   struct name {                                                                \
    330     struct type *sqx_first; /* first element */                                \
    331     struct type **sqx_last; /* addr of last next element */                    \
    332     unsigned long sqx_cookie;                                                  \
    333   }
    334 
    335 #define XSIMPLEQ_ENTRY(type)                                                   \
    336   struct {                                                                     \
    337     struct type *sqx_next; /* next element */                                  \
    338   }
    339 
    340 /*
    341  * XOR Simple queue access methods.
    342  */
    343 #define XSIMPLEQ_XOR(head, ptr)                                                \
    344   ((__typeof(ptr))((head)->sqx_cookie ^ (unsigned long)(ptr)))
    345 #define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first))
    346 #define XSIMPLEQ_END(head) NULL
    347 #define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
    348 #define XSIMPLEQ_NEXT(head, elm, field)                                        \
    349   XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
    350 
    351 #define XSIMPLEQ_FOREACH(var, head, field)                                     \
    352   for ((var) = XSIMPLEQ_FIRST(head); (var) != XSIMPLEQ_END(head);              \
    353        (var) = XSIMPLEQ_NEXT(head, var, field))
    354 
    355 #define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar)                          \
    356   for ((var) = XSIMPLEQ_FIRST(head);                                           \
    357        (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); (var) = (tvar))
    358 
    359 /*
    360  * XOR Simple queue functions.
    361  */
    362 #define XSIMPLEQ_INIT(head)                                                    \
    363   do {                                                                         \
    364     arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie));           \
    365     (head)->sqx_first = XSIMPLEQ_XOR(head, NULL);                              \
    366     (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first);                 \
    367   } while (0)
    368 
    369 #define XSIMPLEQ_INSERT_HEAD(head, elm, field)                                 \
    370   do {                                                                         \
    371     if (((elm)->field.sqx_next = (head)->sqx_first) ==                         \
    372         XSIMPLEQ_XOR(head, NULL))                                              \
    373       (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);           \
    374     (head)->sqx_first = XSIMPLEQ_XOR(head, (elm));                             \
    375   } while (0)
    376 
    377 #define XSIMPLEQ_INSERT_TAIL(head, elm, field)                                 \
    378   do {                                                                         \
    379     (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL);                          \
    380     *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm));       \
    381     (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);             \
    382   } while (0)
    383 
    384 #define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field)                       \
    385   do {                                                                         \
    386     if (((elm)->field.sqx_next = (listelm)->field.sqx_next) ==                 \
    387         XSIMPLEQ_XOR(head, NULL))                                              \
    388       (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);           \
    389     (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm));                     \
    390   } while (0)
    391 
    392 #define XSIMPLEQ_REMOVE_HEAD(head, field)                                      \
    393   do {                                                                         \
    394     if (((head)->sqx_first =                                                   \
    395              XSIMPLEQ_XOR(head, (head)->sqx_first)->field.sqx_next) ==         \
    396         XSIMPLEQ_XOR(head, NULL))                                              \
    397       (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first);               \
    398   } while (0)
    399 
    400 #define XSIMPLEQ_REMOVE_AFTER(head, elm, field)                                \
    401   do {                                                                         \
    402     if (((elm)->field.sqx_next =                                               \
    403              XSIMPLEQ_XOR(head, (elm)->field.sqx_next)->field.sqx_next) ==     \
    404         XSIMPLEQ_XOR(head, NULL))                                              \
    405       (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);           \
    406   } while (0)
    407 
    408 /*
    409  * Tail queue definitions.
    410  */
    411 #define TAILQ_HEAD(name, type)                                                 \
    412   struct name {                                                                \
    413     struct type *tqh_first; /* first element */                                \
    414     struct type **tqh_last; /* addr of last next element */                    \
    415   }
    416 
    417 #define TAILQ_HEAD_INITIALIZER(head)                                           \
    418   { NULL, &(head).tqh_first }
    419 
    420 #define TAILQ_ENTRY(type)                                                      \
    421   struct {                                                                     \
    422     struct type *tqe_next;  /* next element */                                 \
    423     struct type **tqe_prev; /* address of previous next element */             \
    424   }
    425 
    426 /*
    427  * tail queue access methods
    428  */
    429 #define TAILQ_FIRST(head) ((head)->tqh_first)
    430 #define TAILQ_END(head) NULL
    431 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
    432 #define TAILQ_LAST(head, headname)                                             \
    433   (*(((struct headname *)((head)->tqh_last))->tqh_last))
    434 /* XXX */
    435 #define TAILQ_PREV(elm, headname, field)                                       \
    436   (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
    437 #define TAILQ_EMPTY(head) (TAILQ_FIRST(head) == TAILQ_END(head))
    438 
    439 #define TAILQ_FOREACH(var, head, field)                                        \
    440   for ((var) = TAILQ_FIRST(head); (var) != TAILQ_END(head);                    \
    441        (var) = TAILQ_NEXT(var, field))
    442 
    443 #define TAILQ_FOREACH_SAFE(var, head, field, tvar)                             \
    444   for ((var) = TAILQ_FIRST(head);                                              \
    445        (var) != TAILQ_END(head) && ((tvar) = TAILQ_NEXT(var, field), 1);       \
    446        (var) = (tvar))
    447 
    448 #define TAILQ_FOREACH_REVERSE(var, head, headname, field)                      \
    449   for ((var) = TAILQ_LAST(head, headname); (var) != TAILQ_END(head);           \
    450        (var) = TAILQ_PREV(var, headname, field))
    451 
    452 #define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)           \
    453   for ((var) = TAILQ_LAST(head, headname);                                     \
    454        (var) != TAILQ_END(head) &&                                             \
    455        ((tvar) = TAILQ_PREV(var, headname, field), 1);                         \
    456        (var) = (tvar))
    457 
    458 /*
    459  * Tail queue functions.
    460  */
    461 #define TAILQ_INIT(head)                                                       \
    462   do {                                                                         \
    463     (head)->tqh_first = NULL;                                                  \
    464     (head)->tqh_last = &(head)->tqh_first;                                     \
    465   } while (0)
    466 
    467 #define TAILQ_INSERT_HEAD(head, elm, field)                                    \
    468   do {                                                                         \
    469     if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)                   \
    470       (head)->tqh_first->field.tqe_prev = &(elm)->field.tqe_next;              \
    471     else                                                                       \
    472       (head)->tqh_last = &(elm)->field.tqe_next;                               \
    473     (head)->tqh_first = (elm);                                                 \
    474     (elm)->field.tqe_prev = &(head)->tqh_first;                                \
    475   } while (0)
    476 
    477 #define TAILQ_INSERT_TAIL(head, elm, field)                                    \
    478   do {                                                                         \
    479     (elm)->field.tqe_next = NULL;                                              \
    480     (elm)->field.tqe_prev = (head)->tqh_last;                                  \
    481     *(head)->tqh_last = (elm);                                                 \
    482     (head)->tqh_last = &(elm)->field.tqe_next;                                 \
    483   } while (0)
    484 
    485 #define TAILQ_INSERT_AFTER(head, listelm, elm, field)                          \
    486   do {                                                                         \
    487     if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)           \
    488       (elm)->field.tqe_next->field.tqe_prev = &(elm)->field.tqe_next;          \
    489     else                                                                       \
    490       (head)->tqh_last = &(elm)->field.tqe_next;                               \
    491     (listelm)->field.tqe_next = (elm);                                         \
    492     (elm)->field.tqe_prev = &(listelm)->field.tqe_next;                        \
    493   } while (0)
    494 
    495 #define TAILQ_INSERT_BEFORE(listelm, elm, field)                               \
    496   do {                                                                         \
    497     (elm)->field.tqe_prev = (listelm)->field.tqe_prev;                         \
    498     (elm)->field.tqe_next = (listelm);                                         \
    499     *(listelm)->field.tqe_prev = (elm);                                        \
    500     (listelm)->field.tqe_prev = &(elm)->field.tqe_next;                        \
    501   } while (0)
    502 
    503 #define TAILQ_REMOVE(head, elm, field)                                         \
    504   do {                                                                         \
    505     if (((elm)->field.tqe_next) != NULL)                                       \
    506       (elm)->field.tqe_next->field.tqe_prev = (elm)->field.tqe_prev;           \
    507     else                                                                       \
    508       (head)->tqh_last = (elm)->field.tqe_prev;                                \
    509     *(elm)->field.tqe_prev = (elm)->field.tqe_next;                            \
    510     _Q_INVALIDATE((elm)->field.tqe_prev);                                      \
    511     _Q_INVALIDATE((elm)->field.tqe_next);                                      \
    512   } while (0)
    513 
    514 #define TAILQ_REPLACE(head, elm, elm2, field)                                  \
    515   do {                                                                         \
    516     if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)              \
    517       (elm2)->field.tqe_next->field.tqe_prev = &(elm2)->field.tqe_next;        \
    518     else                                                                       \
    519       (head)->tqh_last = &(elm2)->field.tqe_next;                              \
    520     (elm2)->field.tqe_prev = (elm)->field.tqe_prev;                            \
    521     *(elm2)->field.tqe_prev = (elm2);                                          \
    522     _Q_INVALIDATE((elm)->field.tqe_prev);                                      \
    523     _Q_INVALIDATE((elm)->field.tqe_next);                                      \
    524   } while (0)
    525 
    526 /*
    527  * Circular queue definitions.
    528  */
    529 #define CIRCLEQ_HEAD(name, type)                                               \
    530   struct name {                                                                \
    531     struct type *cqh_first; /* first element */                                \
    532     struct type *cqh_last;  /* last element */                                 \
    533   }
    534 
    535 #define CIRCLEQ_HEAD_INITIALIZER(head)                                         \
    536   { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
    537 
    538 #define CIRCLEQ_ENTRY(type)                                                    \
    539   struct {                                                                     \
    540     struct type *cqe_next; /* next element */                                  \
    541     struct type *cqe_prev; /* previous element */                              \
    542   }
    543 
    544 /*
    545  * Circular queue access methods
    546  */
    547 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
    548 #define CIRCLEQ_LAST(head) ((head)->cqh_last)
    549 #define CIRCLEQ_END(head) ((void *)(head))
    550 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
    551 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
    552 #define CIRCLEQ_EMPTY(head) (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
    553 
    554 #define CIRCLEQ_FOREACH(var, head, field)                                      \
    555   for ((var) = CIRCLEQ_FIRST(head); (var) != CIRCLEQ_END(head);                \
    556        (var) = CIRCLEQ_NEXT(var, field))
    557 
    558 #define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar)                           \
    559   for ((var) = CIRCLEQ_FIRST(head);                                            \
    560        (var) != CIRCLEQ_END(head) && ((tvar) = CIRCLEQ_NEXT(var, field), 1);   \
    561        (var) = (tvar))
    562 
    563 #define CIRCLEQ_FOREACH_REVERSE(var, head, field)                              \
    564   for ((var) = CIRCLEQ_LAST(head); (var) != CIRCLEQ_END(head);                 \
    565        (var) = CIRCLEQ_PREV(var, field))
    566 
    567 #define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)         \
    568   for ((var) = CIRCLEQ_LAST(head, headname);                                   \
    569        (var) != CIRCLEQ_END(head) &&                                           \
    570        ((tvar) = CIRCLEQ_PREV(var, headname, field), 1);                       \
    571        (var) = (tvar))
    572 
    573 /*
    574  * Circular queue functions.
    575  */
    576 #define CIRCLEQ_INIT(head)                                                     \
    577   do {                                                                         \
    578     (head)->cqh_first = CIRCLEQ_END(head);                                     \
    579     (head)->cqh_last = CIRCLEQ_END(head);                                      \
    580   } while (0)
    581 
    582 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field)                        \
    583   do {                                                                         \
    584     (elm)->field.cqe_next = (listelm)->field.cqe_next;                         \
    585     (elm)->field.cqe_prev = (listelm);                                         \
    586     if ((listelm)->field.cqe_next == CIRCLEQ_END(head))                        \
    587       (head)->cqh_last = (elm);                                                \
    588     else                                                                       \
    589       (listelm)->field.cqe_next->field.cqe_prev = (elm);                       \
    590     (listelm)->field.cqe_next = (elm);                                         \
    591   } while (0)
    592 
    593 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field)                       \
    594   do {                                                                         \
    595     (elm)->field.cqe_next = (listelm);                                         \
    596     (elm)->field.cqe_prev = (listelm)->field.cqe_prev;                         \
    597     if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))                        \
    598       (head)->cqh_first = (elm);                                               \
    599     else                                                                       \
    600       (listelm)->field.cqe_prev->field.cqe_next = (elm);                       \
    601     (listelm)->field.cqe_prev = (elm);                                         \
    602   } while (0)
    603 
    604 #define CIRCLEQ_INSERT_HEAD(head, elm, field)                                  \
    605   do {                                                                         \
    606     (elm)->field.cqe_next = (head)->cqh_first;                                 \
    607     (elm)->field.cqe_prev = CIRCLEQ_END(head);                                 \
    608     if ((head)->cqh_last == CIRCLEQ_END(head))                                 \
    609       (head)->cqh_last = (elm);                                                \
    610     else                                                                       \
    611       (head)->cqh_first->field.cqe_prev = (elm);                               \
    612     (head)->cqh_first = (elm);                                                 \
    613   } while (0)
    614 
    615 #define CIRCLEQ_INSERT_TAIL(head, elm, field)                                  \
    616   do {                                                                         \
    617     (elm)->field.cqe_next = CIRCLEQ_END(head);                                 \
    618     (elm)->field.cqe_prev = (head)->cqh_last;                                  \
    619     if ((head)->cqh_first == CIRCLEQ_END(head))                                \
    620       (head)->cqh_first = (elm);                                               \
    621     else                                                                       \
    622       (head)->cqh_last->field.cqe_next = (elm);                                \
    623     (head)->cqh_last = (elm);                                                  \
    624   } while (0)
    625 
    626 #define CIRCLEQ_REMOVE(head, elm, field)                                       \
    627   do {                                                                         \
    628     if ((elm)->field.cqe_next == CIRCLEQ_END(head))                            \
    629       (head)->cqh_last = (elm)->field.cqe_prev;                                \
    630     else                                                                       \
    631       (elm)->field.cqe_next->field.cqe_prev = (elm)->field.cqe_prev;           \
    632     if ((elm)->field.cqe_prev == CIRCLEQ_END(head))                            \
    633       (head)->cqh_first = (elm)->field.cqe_next;                               \
    634     else                                                                       \
    635       (elm)->field.cqe_prev->field.cqe_next = (elm)->field.cqe_next;           \
    636     _Q_INVALIDATE((elm)->field.cqe_prev);                                      \
    637     _Q_INVALIDATE((elm)->field.cqe_next);                                      \
    638   } while (0)
    639 
    640 #define CIRCLEQ_REPLACE(head, elm, elm2, field)                                \
    641   do {                                                                         \
    642     if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == CIRCLEQ_END(head)) \
    643       (head)->cqh_last = (elm2);                                               \
    644     else                                                                       \
    645       (elm2)->field.cqe_next->field.cqe_prev = (elm2);                         \
    646     if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == CIRCLEQ_END(head)) \
    647       (head)->cqh_first = (elm2);                                              \
    648     else                                                                       \
    649       (elm2)->field.cqe_prev->field.cqe_next = (elm2);                         \
    650     _Q_INVALIDATE((elm)->field.cqe_prev);                                      \
    651     _Q_INVALIDATE((elm)->field.cqe_next);                                      \
    652   } while (0)
    653 
    654 #endif /* !_SYS_QUEUE_H_ */