home *** CD-ROM | disk | FTP | other *** search
/ PC World 2005 June / PCWorld_2005-06_cd.bin / software / vyzkuste / firewally / firewally.exe / framework-2.3.exe / queue.h < prev    next >
C/C++ Source or Header  |  2004-01-30  |  18KB  |  559 lines
  1. /*
  2.  * Copyright (c) 1991, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  *
  33.  *    @(#)queue.h    8.5 (Berkeley) 8/20/94
  34.  * $FreeBSD: /repoman/r/ncvs/src/sys/sys/queue.h,v 1.56 2003/08/14 14:49:26 kan Exp $
  35.  */
  36.  
  37. #ifndef _SYS_QUEUE_H_
  38. #define    _SYS_QUEUE_H_
  39.  
  40. #include <sys/cdefs.h>
  41.  
  42. /*
  43.  * This file defines four types of data structures: singly-linked lists,
  44.  * singly-linked tail queues, lists and tail queues.
  45.  *
  46.  * A singly-linked list is headed by a single forward pointer. The elements
  47.  * are singly linked for minimum space and pointer manipulation overhead at
  48.  * the expense of O(n) removal for arbitrary elements. New elements can be
  49.  * added to the list after an existing element or at the head of the list.
  50.  * Elements being removed from the head of the list should use the explicit
  51.  * macro for this purpose for optimum efficiency. A singly-linked list may
  52.  * only be traversed in the forward direction.  Singly-linked lists are ideal
  53.  * for applications with large datasets and few or no removals or for
  54.  * implementing a LIFO queue.
  55.  *
  56.  * A singly-linked tail queue is headed by a pair of pointers, one to the
  57.  * head of the list and the other to the tail of the list. The elements are
  58.  * singly linked for minimum space and pointer manipulation overhead at the
  59.  * expense of O(n) removal for arbitrary elements. New elements can be added
  60.  * to the list after an existing element, at the head of the list, or at the
  61.  * end of the list. Elements being removed from the head of the tail queue
  62.  * should use the explicit macro for this purpose for optimum efficiency.
  63.  * A singly-linked tail queue may only be traversed in the forward direction.
  64.  * Singly-linked tail queues are ideal for applications with large datasets
  65.  * and few or no removals or for implementing a FIFO queue.
  66.  *
  67.  * A list is headed by a single forward pointer (or an array of forward
  68.  * pointers for a hash table header). The elements are doubly linked
  69.  * 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
  71.  * or after an existing element or at the head of the list. A list
  72.  * may only be traversed in the forward direction.
  73.  *
  74.  * A tail 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
  78.  * after an existing element, at the head of the list, or at the end of
  79.  * the list. A tail queue may be traversed in either direction.
  80.  *
  81.  * For details on the use of these macros, see the queue(3) manual page.
  82.  *
  83.  *
  84.  *                SLIST    LIST    STAILQ    TAILQ
  85.  * _HEAD            +    +    +    +
  86.  * _HEAD_INITIALIZER        +    +    +    +
  87.  * _ENTRY            +    +    +    +
  88.  * _INIT            +    +    +    +
  89.  * _EMPTY            +    +    +    +
  90.  * _FIRST            +    +    +    +
  91.  * _NEXT            +    +    +    +
  92.  * _PREV            -    -    -    +
  93.  * _LAST            -    -    +    +
  94.  * _FOREACH            +    +    +    +
  95.  * _FOREACH_SAFE        +    +    +    +
  96.  * _FOREACH_REVERSE        -    -    -    +
  97.  * _FOREACH_REVERSE_SAFE    -    -    -    +
  98.  * _INSERT_HEAD            +    +    +    +
  99.  * _INSERT_BEFORE        -    +    -    +
  100.  * _INSERT_AFTER        +    +    +    +
  101.  * _INSERT_TAIL            -    -    +    +
  102.  * _CONCAT            -    -    +    +
  103.  * _REMOVE_HEAD            +    -    +    -
  104.  * _REMOVE            +    +    +    +
  105.  *
  106.  */
  107. #define    QUEUE_MACRO_DEBUG 0
  108. #if QUEUE_MACRO_DEBUG
  109. /* Store the last 2 places the queue element or head was altered */
  110. struct qm_trace {
  111.     char * lastfile;
  112.     int lastline;
  113.     char * prevfile;
  114.     int prevline;
  115. };
  116.  
  117. #define    TRACEBUF    struct qm_trace trace;
  118. #define    TRASHIT(x)    do {(x) = (void *)-1;} while (0)
  119.  
  120. #define    QMD_TRACE_HEAD(head) do {                    \
  121.     (head)->trace.prevline = (head)->trace.lastline;        \
  122.     (head)->trace.prevfile = (head)->trace.lastfile;        \
  123.     (head)->trace.lastline = __LINE__;                \
  124.     (head)->trace.lastfile = __FILE__;                \
  125. } while (0)
  126.  
  127. #define    QMD_TRACE_ELEM(elem) do {                    \
  128.     (elem)->trace.prevline = (elem)->trace.lastline;        \
  129.     (elem)->trace.prevfile = (elem)->trace.lastfile;        \
  130.     (elem)->trace.lastline = __LINE__;                \
  131.     (elem)->trace.lastfile = __FILE__;                \
  132. } while (0)
  133.  
  134. #else
  135. #define    QMD_TRACE_ELEM(elem)
  136. #define    QMD_TRACE_HEAD(head)
  137. #define    TRACEBUF
  138. #define    TRASHIT(x)
  139. #endif    /* QUEUE_MACRO_DEBUG */
  140.  
  141. /*
  142.  * Singly-linked List declarations.
  143.  */
  144. #define    SLIST_HEAD(name, type)                        \
  145. struct name {                                \
  146.     struct type *slh_first;    /* first element */            \
  147. }
  148.  
  149. #define    SLIST_HEAD_INITIALIZER(head)                    \
  150.     { NULL }
  151.  
  152. #undef SLIST_ENTRY
  153. #define    SLIST_ENTRY(type)                        \
  154. struct {                                \
  155.     struct type *sle_next;    /* next element */            \
  156. }
  157.  
  158. /*
  159.  * Singly-linked List functions.
  160.  */
  161. #define    SLIST_EMPTY(head)    ((head)->slh_first == NULL)
  162.  
  163. #define    SLIST_FIRST(head)    ((head)->slh_first)
  164.  
  165. #define    SLIST_FOREACH(var, head, field)                    \
  166.     for ((var) = SLIST_FIRST((head));                \
  167.         (var);                            \
  168.         (var) = SLIST_NEXT((var), field))
  169.  
  170. #define    SLIST_FOREACH_SAFE(var, head, field, tvar)            \
  171.     for ((var) = SLIST_FIRST((head));                \
  172.         (var) && ((tvar) = SLIST_NEXT((var), field), 1);        \
  173.         (var) = (tvar))
  174.  
  175. #define    SLIST_FOREACH_PREVPTR(var, varp, head, field)            \
  176.     for ((varp) = &SLIST_FIRST((head));                \
  177.         ((var) = *(varp)) != NULL;                    \
  178.         (varp) = &SLIST_NEXT((var), field))
  179.  
  180. #define    SLIST_INIT(head) do {                        \
  181.     SLIST_FIRST((head)) = NULL;                    \
  182. } while (0)
  183.  
  184. #define    SLIST_INSERT_AFTER(slistelm, elm, field) do {            \
  185.     SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);    \
  186.     SLIST_NEXT((slistelm), field) = (elm);                \
  187. } while (0)
  188.  
  189. #define    SLIST_INSERT_HEAD(head, elm, field) do {            \
  190.     SLIST_NEXT((elm), field) = SLIST_FIRST((head));            \
  191.     SLIST_FIRST((head)) = (elm);                    \
  192. } while (0)
  193.  
  194. #define    SLIST_NEXT(elm, field)    ((elm)->field.sle_next)
  195.  
  196. #define    SLIST_REMOVE(head, elm, type, field) do {            \
  197.     if (SLIST_FIRST((head)) == (elm)) {                \
  198.         SLIST_REMOVE_HEAD((head), field);            \
  199.     }                                \
  200.     else {                                \
  201.         struct type *curelm = SLIST_FIRST((head));        \
  202.         while (SLIST_NEXT(curelm, field) != (elm))        \
  203.             curelm = SLIST_NEXT(curelm, field);        \
  204.         SLIST_NEXT(curelm, field) =                \
  205.             SLIST_NEXT(SLIST_NEXT(curelm, field), field);    \
  206.     }                                \
  207. } while (0)
  208.  
  209. #define    SLIST_REMOVE_HEAD(head, field) do {                \
  210.     SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);    \
  211. } while (0)
  212.  
  213. /*
  214.  * Singly-linked Tail queue declarations.
  215.  */
  216. #define    STAILQ_HEAD(name, type)                        \
  217. struct name {                                \
  218.     struct type *stqh_first;/* first element */            \
  219.     struct type **stqh_last;/* addr of last next element */        \
  220. }
  221.  
  222. #define    STAILQ_HEAD_INITIALIZER(head)                    \
  223.     { NULL, &(head).stqh_first }
  224.  
  225. #define    STAILQ_ENTRY(type)                        \
  226. struct {                                \
  227.     struct type *stqe_next;    /* next element */            \
  228. }
  229.  
  230. /*
  231.  * Singly-linked Tail queue functions.
  232.  */
  233. #define    STAILQ_CONCAT(head1, head2) do {                \
  234.     if (!STAILQ_EMPTY((head2))) {                    \
  235.         *(head1)->stqh_last = (head2)->stqh_first;        \
  236.         (head1)->stqh_last = (head2)->stqh_last;        \
  237.         STAILQ_INIT((head2));                    \
  238.     }                                \
  239. } while (0)
  240.  
  241. #define    STAILQ_EMPTY(head)    ((head)->stqh_first == NULL)
  242.  
  243. #define    STAILQ_FIRST(head)    ((head)->stqh_first)
  244.  
  245. #define    STAILQ_FOREACH(var, head, field)                \
  246.     for((var) = STAILQ_FIRST((head));                \
  247.        (var);                            \
  248.        (var) = STAILQ_NEXT((var), field))
  249.  
  250.  
  251. #define    STAILQ_FOREACH_SAFE(var, head, field, tvar)            \
  252.     for ((var) = STAILQ_FIRST((head));                \
  253.         (var) && ((tvar) = STAILQ_NEXT((var), field), 1);        \
  254.         (var) = (tvar))
  255.  
  256. #define    STAILQ_INIT(head) do {                        \
  257.     STAILQ_FIRST((head)) = NULL;                    \
  258.     (head)->stqh_last = &STAILQ_FIRST((head));            \
  259. } while (0)
  260.  
  261. #define    STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {        \
  262.     if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
  263.         (head)->stqh_last = &STAILQ_NEXT((elm), field);        \
  264.     STAILQ_NEXT((tqelm), field) = (elm);                \
  265. } while (0)
  266.  
  267. #define    STAILQ_INSERT_HEAD(head, elm, field) do {            \
  268.     if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)    \
  269.         (head)->stqh_last = &STAILQ_NEXT((elm), field);        \
  270.     STAILQ_FIRST((head)) = (elm);                    \
  271. } while (0)
  272.  
  273. #define    STAILQ_INSERT_TAIL(head, elm, field) do {            \
  274.     STAILQ_NEXT((elm), field) = NULL;                \
  275.     *(head)->stqh_last = (elm);                    \
  276.     (head)->stqh_last = &STAILQ_NEXT((elm), field);            \
  277. } while (0)
  278.  
  279. #define    STAILQ_LAST(head, type, field)                    \
  280.     (STAILQ_EMPTY((head)) ?                        \
  281.         NULL :                            \
  282.             ((struct type *)                    \
  283.         ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
  284.  
  285. #define    STAILQ_NEXT(elm, field)    ((elm)->field.stqe_next)
  286.  
  287. #define    STAILQ_REMOVE(head, elm, type, field) do {            \
  288.     if (STAILQ_FIRST((head)) == (elm)) {                \
  289.         STAILQ_REMOVE_HEAD((head), field);            \
  290.     }                                \
  291.     else {                                \
  292.         struct type *curelm = STAILQ_FIRST((head));        \
  293.         while (STAILQ_NEXT(curelm, field) != (elm))        \
  294.             curelm = STAILQ_NEXT(curelm, field);        \
  295.         if ((STAILQ_NEXT(curelm, field) =            \
  296.              STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
  297.             (head)->stqh_last = &STAILQ_NEXT((curelm), field);\
  298.     }                                \
  299. } while (0)
  300.  
  301. #define    STAILQ_REMOVE_HEAD(head, field) do {                \
  302.     if ((STAILQ_FIRST((head)) =                    \
  303.          STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)        \
  304.         (head)->stqh_last = &STAILQ_FIRST((head));        \
  305. } while (0)
  306.  
  307. #define    STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {            \
  308.     if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL)    \
  309.         (head)->stqh_last = &STAILQ_FIRST((head));        \
  310. } while (0)
  311.  
  312. /*
  313.  * List declarations.
  314.  */
  315. #define    LIST_HEAD(name, type)                        \
  316. struct name {                                \
  317.     struct type *lh_first;    /* first element */            \
  318. }
  319.  
  320. #define    LIST_HEAD_INITIALIZER(head)                    \
  321.     { NULL }
  322.  
  323. #define    LIST_ENTRY(type)                        \
  324. struct {                                \
  325.     struct type *le_next;    /* next element */            \
  326.     struct type **le_prev;    /* address of previous next element */    \
  327. }
  328.  
  329. /*
  330.  * List functions.
  331.  */
  332.  
  333. #define    LIST_EMPTY(head)    ((head)->lh_first == NULL)
  334.  
  335. #define    LIST_FIRST(head)    ((head)->lh_first)
  336.  
  337. #define    LIST_FOREACH(var, head, field)                    \
  338.     for ((var) = LIST_FIRST((head));                \
  339.         (var);                            \
  340.         (var) = LIST_NEXT((var), field))
  341.  
  342. #define    LIST_FOREACH_SAFE(var, head, field, tvar)            \
  343.     for ((var) = LIST_FIRST((head));                \
  344.         (var) && ((tvar) = LIST_NEXT((var), field), 1);        \
  345.         (var) = (tvar))
  346.  
  347. #define    LIST_INIT(head) do {                        \
  348.     LIST_FIRST((head)) = NULL;                    \
  349. } while (0)
  350.  
  351. #define    LIST_INSERT_AFTER(listelm, elm, field) do {            \
  352.     if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
  353.         LIST_NEXT((listelm), field)->field.le_prev =        \
  354.             &LIST_NEXT((elm), field);                \
  355.     LIST_NEXT((listelm), field) = (elm);                \
  356.     (elm)->field.le_prev = &LIST_NEXT((listelm), field);        \
  357. } while (0)
  358.  
  359. #define    LIST_INSERT_BEFORE(listelm, elm, field) do {            \
  360.     (elm)->field.le_prev = (listelm)->field.le_prev;        \
  361.     LIST_NEXT((elm), field) = (listelm);                \
  362.     *(listelm)->field.le_prev = (elm);                \
  363.     (listelm)->field.le_prev = &LIST_NEXT((elm), field);        \
  364. } while (0)
  365.  
  366. #define    LIST_INSERT_HEAD(head, elm, field) do {                \
  367.     if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)    \
  368.         LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
  369.     LIST_FIRST((head)) = (elm);                    \
  370.     (elm)->field.le_prev = &LIST_FIRST((head));            \
  371. } while (0)
  372.  
  373. #define    LIST_NEXT(elm, field)    ((elm)->field.le_next)
  374.  
  375. #define    LIST_REMOVE(elm, field) do {                    \
  376.     if (LIST_NEXT((elm), field) != NULL)                \
  377.         LIST_NEXT((elm), field)->field.le_prev =         \
  378.             (elm)->field.le_prev;                \
  379.     *(elm)->field.le_prev = LIST_NEXT((elm), field);        \
  380. } while (0)
  381.  
  382. /*
  383.  * Tail queue declarations.
  384.  */
  385. #define    TAILQ_HEAD(name, type)                        \
  386. struct name {                                \
  387.     struct type *tqh_first;    /* first element */            \
  388.     struct type **tqh_last;    /* addr of last next element */        \
  389.     TRACEBUF                            \
  390. }
  391.  
  392. #define    TAILQ_HEAD_INITIALIZER(head)                    \
  393.     { NULL, &(head).tqh_first }
  394.  
  395. #define    TAILQ_ENTRY(type)                        \
  396. struct {                                \
  397.     struct type *tqe_next;    /* next element */            \
  398.     struct type **tqe_prev;    /* address of previous next element */    \
  399.     TRACEBUF                            \
  400. }
  401.  
  402. /*
  403.  * Tail queue functions.
  404.  */
  405. #define    TAILQ_CONCAT(head1, head2, field) do {                \
  406.     if (!TAILQ_EMPTY(head2)) {                    \
  407.         *(head1)->tqh_last = (head2)->tqh_first;        \
  408.         (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;    \
  409.         (head1)->tqh_last = (head2)->tqh_last;            \
  410.         TAILQ_INIT((head2));                    \
  411.         QMD_TRACE_HEAD(head);                    \
  412.         QMD_TRACE_HEAD(head2);                    \
  413.     }                                \
  414. } while (0)
  415.  
  416. #define    TAILQ_EMPTY(head)    ((head)->tqh_first == NULL)
  417.  
  418. #define    TAILQ_FIRST(head)    ((head)->tqh_first)
  419.  
  420. #define    TAILQ_FOREACH(var, head, field)                    \
  421.     for ((var) = TAILQ_FIRST((head));                \
  422.         (var);                            \
  423.         (var) = TAILQ_NEXT((var), field))
  424.  
  425. #define    TAILQ_FOREACH_SAFE(var, head, field, tvar)            \
  426.     for ((var) = TAILQ_FIRST((head));                \
  427.         (var) && ((tvar) = TAILQ_NEXT((var), field), 1);        \
  428.         (var) = (tvar))
  429.  
  430. #define    TAILQ_FOREACH_REVERSE(var, head, headname, field)        \
  431.     for ((var) = TAILQ_LAST((head), headname);            \
  432.         (var);                            \
  433.         (var) = TAILQ_PREV((var), headname, field))
  434.  
  435. #define    TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)    \
  436.     for ((var) = TAILQ_LAST((head), headname);            \
  437.         (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);    \
  438.         (var) = (tvar))
  439.  
  440. #define    TAILQ_INIT(head) do {                        \
  441.     TAILQ_FIRST((head)) = NULL;                    \
  442.     (head)->tqh_last = &TAILQ_FIRST((head));            \
  443.     QMD_TRACE_HEAD(head);                        \
  444. } while (0)
  445.  
  446. #define    TAILQ_INSERT_AFTER(head, listelm, elm, field) do {        \
  447.     if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
  448.         TAILQ_NEXT((elm), field)->field.tqe_prev =         \
  449.             &TAILQ_NEXT((elm), field);                \
  450.     else {                                \
  451.         (head)->tqh_last = &TAILQ_NEXT((elm), field);        \
  452.         QMD_TRACE_HEAD(head);                    \
  453.     }                                \
  454.     TAILQ_NEXT((listelm), field) = (elm);                \
  455.     (elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);        \
  456.     QMD_TRACE_ELEM(&(elm)->field);                    \
  457.     QMD_TRACE_ELEM(&listelm->field);                \
  458. } while (0)
  459.  
  460. #define    TAILQ_INSERT_BEFORE(listelm, elm, field) do {            \
  461.     (elm)->field.tqe_prev = (listelm)->field.tqe_prev;        \
  462.     TAILQ_NEXT((elm), field) = (listelm);                \
  463.     *(listelm)->field.tqe_prev = (elm);                \
  464.     (listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);        \
  465.     QMD_TRACE_ELEM(&(elm)->field);                    \
  466.     QMD_TRACE_ELEM(&listelm->field);                \
  467. } while (0)
  468.  
  469. #define    TAILQ_INSERT_HEAD(head, elm, field) do {            \
  470.     if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)    \
  471.         TAILQ_FIRST((head))->field.tqe_prev =            \
  472.             &TAILQ_NEXT((elm), field);                \
  473.     else                                \
  474.         (head)->tqh_last = &TAILQ_NEXT((elm), field);        \
  475.     TAILQ_FIRST((head)) = (elm);                    \
  476.     (elm)->field.tqe_prev = &TAILQ_FIRST((head));            \
  477.     QMD_TRACE_HEAD(head);                        \
  478.     QMD_TRACE_ELEM(&(elm)->field);                    \
  479. } while (0)
  480.  
  481. #define    TAILQ_INSERT_TAIL(head, elm, field) do {            \
  482.     TAILQ_NEXT((elm), field) = NULL;                \
  483.     (elm)->field.tqe_prev = (head)->tqh_last;            \
  484.     *(head)->tqh_last = (elm);                    \
  485.     (head)->tqh_last = &TAILQ_NEXT((elm), field);            \
  486.     QMD_TRACE_HEAD(head);                        \
  487.     QMD_TRACE_ELEM(&(elm)->field);                    \
  488. } while (0)
  489.  
  490. #define    TAILQ_LAST(head, headname)                    \
  491.     (*(((struct headname *)((head)->tqh_last))->tqh_last))
  492.  
  493. #define    TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
  494.  
  495. #define    TAILQ_PREV(elm, headname, field)                \
  496.     (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
  497.  
  498. #define    TAILQ_REMOVE(head, elm, field) do {                \
  499.     if ((TAILQ_NEXT((elm), field)) != NULL)                \
  500.         TAILQ_NEXT((elm), field)->field.tqe_prev =         \
  501.             (elm)->field.tqe_prev;                \
  502.     else {                                \
  503.         (head)->tqh_last = (elm)->field.tqe_prev;        \
  504.         QMD_TRACE_HEAD(head);                    \
  505.     }                                \
  506.     *(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);        \
  507.     TRASHIT((elm)->field.tqe_next);                    \
  508.     TRASHIT((elm)->field.tqe_prev);                    \
  509.     QMD_TRACE_ELEM(&(elm)->field);                    \
  510. } while (0)
  511.  
  512.  
  513. #ifdef _KERNEL
  514.  
  515. /*
  516.  * XXX insque() and remque() are an old way of handling certain queues.
  517.  * They bogusly assumes that all queue heads look alike.
  518.  */
  519.  
  520. struct quehead {
  521.     struct quehead *qh_link;
  522.     struct quehead *qh_rlink;
  523. };
  524.  
  525. #ifdef    __GNUC__
  526.  
  527. static __inline void
  528. insque(void *a, void *b)
  529. {
  530.     struct quehead *element = (struct quehead *)a,
  531.          *head = (struct quehead *)b;
  532.  
  533.     element->qh_link = head->qh_link;
  534.     element->qh_rlink = head;
  535.     head->qh_link = element;
  536.     element->qh_link->qh_rlink = element;
  537. }
  538.  
  539. static __inline void
  540. remque(void *a)
  541. {
  542.     struct quehead *element = (struct quehead *)a;
  543.  
  544.     element->qh_link->qh_rlink = element->qh_rlink;
  545.     element->qh_rlink->qh_link = element->qh_link;
  546.     element->qh_rlink = 0;
  547. }
  548.  
  549. #else /* !__GNUC__ */
  550.  
  551. void    insque(void *a, void *b);
  552. void    remque(void *a);
  553.  
  554. #endif /* __GNUC__ */
  555.  
  556. #endif /* _KERNEL */
  557.  
  558. #endif /* !_SYS_QUEUE_H_ */
  559.