Back to index

glibc  2.9
queue.h
Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 1991, 1993
00003  *     The Regents of the University of California.  All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  * 1. Redistributions of source code must retain the above copyright
00009  *    notice, this list of conditions and the following disclaimer.
00010  * 2. Redistributions in binary form must reproduce the above copyright
00011  *    notice, this list of conditions and the following disclaimer in the
00012  *    documentation and/or other materials provided with the distribution.
00013  * 3. Neither the name of the University nor the names of its contributors
00014  *    may be used to endorse or promote products derived from this software
00015  *    without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00018  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00019  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00020  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00021  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00022  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00023  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00024  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00025  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00026  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00027  * SUCH DAMAGE.
00028  *
00029  *     @(#)queue.h   8.5 (Berkeley) 8/20/94
00030  */
00031 
00032 #ifndef       _SYS_QUEUE_H_
00033 #define       _SYS_QUEUE_H_
00034 
00035 /*
00036  * This file defines five types of data structures: singly-linked lists,
00037  * lists, simple queues, tail queues, and circular queues.
00038  *
00039  * A singly-linked list is headed by a single forward pointer. The
00040  * elements are singly linked for minimum space and pointer manipulation
00041  * overhead at the expense of O(n) removal for arbitrary elements. New
00042  * elements can be added to the list after an existing element or at the
00043  * head of the list.  Elements being removed from the head of the list
00044  * should use the explicit macro for this purpose for optimum
00045  * efficiency. A singly-linked list may only be traversed in the forward
00046  * direction.  Singly-linked lists are ideal for applications with large
00047  * datasets and few or no removals or for implementing a LIFO queue.
00048  *
00049  * A list is headed by a single forward pointer (or an array of forward
00050  * pointers for a hash table header). The elements are doubly linked
00051  * so that an arbitrary element can be removed without a need to
00052  * traverse the list. New elements can be added to the list before
00053  * or after an existing element or at the head of the list. A list
00054  * may only be traversed in the forward direction.
00055  *
00056  * A simple queue is headed by a pair of pointers, one the head of the
00057  * list and the other to the tail of the list. The elements are singly
00058  * linked to save space, so elements can only be removed from the
00059  * head of the list. New elements can be added to the list after
00060  * an existing element, at the head of the list, or at the end of the
00061  * list. A simple queue may only be traversed in the forward direction.
00062  *
00063  * A tail queue is headed by a pair of pointers, one to the head of the
00064  * list and the other to the tail of the list. The elements are doubly
00065  * linked so that an arbitrary element can be removed without a need to
00066  * traverse the list. New elements can be added to the list before or
00067  * after an existing element, at the head of the list, or at the end of
00068  * the list. A tail queue may be traversed in either direction.
00069  *
00070  * A circle queue is headed by a pair of pointers, one to the head of the
00071  * list and the other to the tail of the list. The elements are doubly
00072  * linked so that an arbitrary element can be removed without a need to
00073  * traverse the list. New elements can be added to the list before or after
00074  * an existing element, at the head of the list, or at the end of the list.
00075  * A circle queue may be traversed in either direction, but has a more
00076  * complex end of list detection.
00077  *
00078  * For details on the use of these macros, see the queue(3) manual page.
00079  */
00080 
00081 /*
00082  * List definitions.
00083  */
00084 #define       LIST_HEAD(name, type)                                          \
00085 struct name {                                                  \
00086        struct type *lh_first;      /* first element */                \
00087 }
00088 
00089 #define       LIST_HEAD_INITIALIZER(head)                             \
00090        { NULL }
00091 
00092 #define       LIST_ENTRY(type)                                        \
00093 struct {                                                       \
00094        struct type *le_next;       /* next element */                 \
00095        struct type **le_prev;      /* address of previous next element */    \
00096 }
00097 
00098 /*
00099  * List functions.
00100  */
00101 #define       LIST_INIT(head) do {                                    \
00102        (head)->lh_first = NULL;                                \
00103 } while (/*CONSTCOND*/0)
00104 
00105 #define       LIST_INSERT_AFTER(listelm, elm, field) do {                    \
00106        if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
00107               (listelm)->field.le_next->field.le_prev =        \
00108                   &(elm)->field.le_next;                       \
00109        (listelm)->field.le_next = (elm);                       \
00110        (elm)->field.le_prev = &(listelm)->field.le_next;              \
00111 } while (/*CONSTCOND*/0)
00112 
00113 #define       LIST_INSERT_BEFORE(listelm, elm, field) do {                   \
00114        (elm)->field.le_prev = (listelm)->field.le_prev;        \
00115        (elm)->field.le_next = (listelm);                       \
00116        *(listelm)->field.le_prev = (elm);                      \
00117        (listelm)->field.le_prev = &(elm)->field.le_next;              \
00118 } while (/*CONSTCOND*/0)
00119 
00120 #define       LIST_INSERT_HEAD(head, elm, field) do {                        \
00121        if (((elm)->field.le_next = (head)->lh_first) != NULL)         \
00122               (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
00123        (head)->lh_first = (elm);                               \
00124        (elm)->field.le_prev = &(head)->lh_first;               \
00125 } while (/*CONSTCOND*/0)
00126 
00127 #define       LIST_REMOVE(elm, field) do {                                   \
00128        if ((elm)->field.le_next != NULL)                       \
00129               (elm)->field.le_next->field.le_prev =                   \
00130                   (elm)->field.le_prev;                        \
00131        *(elm)->field.le_prev = (elm)->field.le_next;                  \
00132 } while (/*CONSTCOND*/0)
00133 
00134 #define       LIST_FOREACH(var, head, field)                                 \
00135        for ((var) = ((head)->lh_first);                        \
00136               (var);                                           \
00137               (var) = ((var)->field.le_next))
00138 
00139 /*
00140  * List access methods.
00141  */
00142 #define       LIST_EMPTY(head)            ((head)->lh_first == NULL)
00143 #define       LIST_FIRST(head)            ((head)->lh_first)
00144 #define       LIST_NEXT(elm, field)              ((elm)->field.le_next)
00145 
00146 
00147 /*
00148  * Singly-linked List definitions.
00149  */
00150 #define       SLIST_HEAD(name, type)                                         \
00151 struct name {                                                  \
00152        struct type *slh_first;     /* first element */                \
00153 }
00154 
00155 #define       SLIST_HEAD_INITIALIZER(head)                                   \
00156        { NULL }
00157 
00158 #define       SLIST_ENTRY(type)                                       \
00159 struct {                                                       \
00160        struct type *sle_next;      /* next element */                 \
00161 }
00162 
00163 /*
00164  * Singly-linked List functions.
00165  */
00166 #define       SLIST_INIT(head) do {                                          \
00167        (head)->slh_first = NULL;                               \
00168 } while (/*CONSTCOND*/0)
00169 
00170 #define       SLIST_INSERT_AFTER(slistelm, elm, field) do {                  \
00171        (elm)->field.sle_next = (slistelm)->field.sle_next;            \
00172        (slistelm)->field.sle_next = (elm);                            \
00173 } while (/*CONSTCOND*/0)
00174 
00175 #define       SLIST_INSERT_HEAD(head, elm, field) do {                \
00176        (elm)->field.sle_next = (head)->slh_first;                     \
00177        (head)->slh_first = (elm);                              \
00178 } while (/*CONSTCOND*/0)
00179 
00180 #define       SLIST_REMOVE_HEAD(head, field) do {                            \
00181        (head)->slh_first = (head)->slh_first->field.sle_next;         \
00182 } while (/*CONSTCOND*/0)
00183 
00184 #define       SLIST_REMOVE(head, elm, type, field) do {               \
00185        if ((head)->slh_first == (elm)) {                       \
00186               SLIST_REMOVE_HEAD((head), field);                \
00187        }                                                       \
00188        else {                                                  \
00189               struct type *curelm = (head)->slh_first;         \
00190               while(curelm->field.sle_next != (elm))                  \
00191                      curelm = curelm->field.sle_next;          \
00192               curelm->field.sle_next =                         \
00193                   curelm->field.sle_next->field.sle_next;             \
00194        }                                                       \
00195 } while (/*CONSTCOND*/0)
00196 
00197 #define       SLIST_FOREACH(var, head, field)                                \
00198        for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
00199 
00200 /*
00201  * Singly-linked List access methods.
00202  */
00203 #define       SLIST_EMPTY(head)    ((head)->slh_first == NULL)
00204 #define       SLIST_FIRST(head)    ((head)->slh_first)
00205 #define       SLIST_NEXT(elm, field)      ((elm)->field.sle_next)
00206 
00207 
00208 /*
00209  * Singly-linked Tail queue declarations.
00210  */
00211 #define       STAILQ_HEAD(name, type)                                 \
00212 struct name {                                                  \
00213        struct type *stqh_first;    /* first element */                \
00214        struct type **stqh_last;    /* addr of last next element */           \
00215 }
00216 
00217 #define       STAILQ_HEAD_INITIALIZER(head)                                  \
00218        { NULL, &(head).stqh_first }
00219 
00220 #define       STAILQ_ENTRY(type)                                      \
00221 struct {                                                       \
00222        struct type *stqe_next;     /* next element */                 \
00223 }
00224 
00225 /*
00226  * Singly-linked Tail queue functions.
00227  */
00228 #define       STAILQ_INIT(head) do {                                         \
00229        (head)->stqh_first = NULL;                              \
00230        (head)->stqh_last = &(head)->stqh_first;                       \
00231 } while (/*CONSTCOND*/0)
00232 
00233 #define       STAILQ_INSERT_HEAD(head, elm, field) do {               \
00234        if (((elm)->field.stqe_next = (head)->stqh_first) == NULL)     \
00235               (head)->stqh_last = &(elm)->field.stqe_next;            \
00236        (head)->stqh_first = (elm);                             \
00237 } while (/*CONSTCOND*/0)
00238 
00239 #define       STAILQ_INSERT_TAIL(head, elm, field) do {               \
00240        (elm)->field.stqe_next = NULL;                                 \
00241        *(head)->stqh_last = (elm);                             \
00242        (head)->stqh_last = &(elm)->field.stqe_next;                   \
00243 } while (/*CONSTCOND*/0)
00244 
00245 #define       STAILQ_INSERT_AFTER(head, listelm, elm, field) do {            \
00246        if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
00247               (head)->stqh_last = &(elm)->field.stqe_next;            \
00248        (listelm)->field.stqe_next = (elm);                            \
00249 } while (/*CONSTCOND*/0)
00250 
00251 #define       STAILQ_REMOVE_HEAD(head, field) do {                           \
00252        if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
00253               (head)->stqh_last = &(head)->stqh_first;                \
00254 } while (/*CONSTCOND*/0)
00255 
00256 #define       STAILQ_REMOVE(head, elm, type, field) do {                     \
00257        if ((head)->stqh_first == (elm)) {                      \
00258               STAILQ_REMOVE_HEAD((head), field);               \
00259        } else {                                                \
00260               struct type *curelm = (head)->stqh_first;        \
00261               while (curelm->field.stqe_next != (elm))                \
00262                      curelm = curelm->field.stqe_next;         \
00263               if ((curelm->field.stqe_next =                          \
00264                      curelm->field.stqe_next->field.stqe_next) == NULL) \
00265                          (head)->stqh_last = &(curelm)->field.stqe_next; \
00266        }                                                       \
00267 } while (/*CONSTCOND*/0)
00268 
00269 #define       STAILQ_FOREACH(var, head, field)                        \
00270        for ((var) = ((head)->stqh_first);                      \
00271               (var);                                           \
00272               (var) = ((var)->field.stqe_next))
00273 
00274 #define       STAILQ_CONCAT(head1, head2) do {                        \
00275        if (!STAILQ_EMPTY((head2))) {                                  \
00276               *(head1)->stqh_last = (head2)->stqh_first;              \
00277               (head1)->stqh_last = (head2)->stqh_last;         \
00278               STAILQ_INIT((head2));                                   \
00279        }                                                       \
00280 } while (/*CONSTCOND*/0)
00281 
00282 /*
00283  * Singly-linked Tail queue access methods.
00284  */
00285 #define       STAILQ_EMPTY(head)   ((head)->stqh_first == NULL)
00286 #define       STAILQ_FIRST(head)   ((head)->stqh_first)
00287 #define       STAILQ_NEXT(elm, field)     ((elm)->field.stqe_next)
00288 
00289 
00290 /*
00291  * Simple queue definitions.
00292  */
00293 #define       SIMPLEQ_HEAD(name, type)                                \
00294 struct name {                                                  \
00295        struct type *sqh_first;     /* first element */                \
00296        struct type **sqh_last;     /* addr of last next element */           \
00297 }
00298 
00299 #define       SIMPLEQ_HEAD_INITIALIZER(head)                                 \
00300        { NULL, &(head).sqh_first }
00301 
00302 #define       SIMPLEQ_ENTRY(type)                                     \
00303 struct {                                                       \
00304        struct type *sqe_next;      /* next element */                 \
00305 }
00306 
00307 /*
00308  * Simple queue functions.
00309  */
00310 #define       SIMPLEQ_INIT(head) do {                                        \
00311        (head)->sqh_first = NULL;                               \
00312        (head)->sqh_last = &(head)->sqh_first;                         \
00313 } while (/*CONSTCOND*/0)
00314 
00315 #define       SIMPLEQ_INSERT_HEAD(head, elm, field) do {                     \
00316        if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)       \
00317               (head)->sqh_last = &(elm)->field.sqe_next;              \
00318        (head)->sqh_first = (elm);                              \
00319 } while (/*CONSTCOND*/0)
00320 
00321 #define       SIMPLEQ_INSERT_TAIL(head, elm, field) do {                     \
00322        (elm)->field.sqe_next = NULL;                                  \
00323        *(head)->sqh_last = (elm);                              \
00324        (head)->sqh_last = &(elm)->field.sqe_next;                     \
00325 } while (/*CONSTCOND*/0)
00326 
00327 #define       SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {           \
00328        if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
00329               (head)->sqh_last = &(elm)->field.sqe_next;              \
00330        (listelm)->field.sqe_next = (elm);                      \
00331 } while (/*CONSTCOND*/0)
00332 
00333 #define       SIMPLEQ_REMOVE_HEAD(head, field) do {                          \
00334        if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
00335               (head)->sqh_last = &(head)->sqh_first;                  \
00336 } while (/*CONSTCOND*/0)
00337 
00338 #define       SIMPLEQ_REMOVE(head, elm, type, field) do {                    \
00339        if ((head)->sqh_first == (elm)) {                       \
00340               SIMPLEQ_REMOVE_HEAD((head), field);                     \
00341        } else {                                                \
00342               struct type *curelm = (head)->sqh_first;         \
00343               while (curelm->field.sqe_next != (elm))                 \
00344                      curelm = curelm->field.sqe_next;          \
00345               if ((curelm->field.sqe_next =                           \
00346                      curelm->field.sqe_next->field.sqe_next) == NULL) \
00347                          (head)->sqh_last = &(curelm)->field.sqe_next; \
00348        }                                                       \
00349 } while (/*CONSTCOND*/0)
00350 
00351 #define       SIMPLEQ_FOREACH(var, head, field)                       \
00352        for ((var) = ((head)->sqh_first);                       \
00353               (var);                                           \
00354               (var) = ((var)->field.sqe_next))
00355 
00356 /*
00357  * Simple queue access methods.
00358  */
00359 #define       SIMPLEQ_EMPTY(head)         ((head)->sqh_first == NULL)
00360 #define       SIMPLEQ_FIRST(head)         ((head)->sqh_first)
00361 #define       SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)
00362 
00363 
00364 /*
00365  * Tail queue definitions.
00366  */
00367 #define       _TAILQ_HEAD(name, type, qual)                                  \
00368 struct name {                                                  \
00369        qual type *tqh_first;              /* first element */         \
00370        qual type *qual *tqh_last;  /* addr of last next element */    \
00371 }
00372 #define TAILQ_HEAD(name, type)     _TAILQ_HEAD(name, struct type,)
00373 
00374 #define       TAILQ_HEAD_INITIALIZER(head)                                   \
00375        { NULL, &(head).tqh_first }
00376 
00377 #define       _TAILQ_ENTRY(type, qual)                                \
00378 struct {                                                       \
00379        qual type *tqe_next;        /* next element */          \
00380        qual type *qual *tqe_prev;  /* address of previous next element */\
00381 }
00382 #define TAILQ_ENTRY(type)   _TAILQ_ENTRY(struct type,)
00383 
00384 /*
00385  * Tail queue functions.
00386  */
00387 #define       TAILQ_INIT(head) do {                                          \
00388        (head)->tqh_first = NULL;                               \
00389        (head)->tqh_last = &(head)->tqh_first;                         \
00390 } while (/*CONSTCOND*/0)
00391 
00392 #define       TAILQ_INSERT_HEAD(head, elm, field) do {                \
00393        if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)       \
00394               (head)->tqh_first->field.tqe_prev =                     \
00395                   &(elm)->field.tqe_next;                      \
00396        else                                                    \
00397               (head)->tqh_last = &(elm)->field.tqe_next;              \
00398        (head)->tqh_first = (elm);                              \
00399        (elm)->field.tqe_prev = &(head)->tqh_first;                    \
00400 } while (/*CONSTCOND*/0)
00401 
00402 #define       TAILQ_INSERT_TAIL(head, elm, field) do {                \
00403        (elm)->field.tqe_next = NULL;                                  \
00404        (elm)->field.tqe_prev = (head)->tqh_last;               \
00405        *(head)->tqh_last = (elm);                              \
00406        (head)->tqh_last = &(elm)->field.tqe_next;                     \
00407 } while (/*CONSTCOND*/0)
00408 
00409 #define       TAILQ_INSERT_AFTER(head, listelm, elm, field) do {             \
00410        if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
00411               (elm)->field.tqe_next->field.tqe_prev =          \
00412                   &(elm)->field.tqe_next;                      \
00413        else                                                    \
00414               (head)->tqh_last = &(elm)->field.tqe_next;              \
00415        (listelm)->field.tqe_next = (elm);                      \
00416        (elm)->field.tqe_prev = &(listelm)->field.tqe_next;            \
00417 } while (/*CONSTCOND*/0)
00418 
00419 #define       TAILQ_INSERT_BEFORE(listelm, elm, field) do {                  \
00420        (elm)->field.tqe_prev = (listelm)->field.tqe_prev;             \
00421        (elm)->field.tqe_next = (listelm);                      \
00422        *(listelm)->field.tqe_prev = (elm);                            \
00423        (listelm)->field.tqe_prev = &(elm)->field.tqe_next;            \
00424 } while (/*CONSTCOND*/0)
00425 
00426 #define       TAILQ_REMOVE(head, elm, field) do {                            \
00427        if (((elm)->field.tqe_next) != NULL)                           \
00428               (elm)->field.tqe_next->field.tqe_prev =          \
00429                   (elm)->field.tqe_prev;                       \
00430        else                                                    \
00431               (head)->tqh_last = (elm)->field.tqe_prev;        \
00432        *(elm)->field.tqe_prev = (elm)->field.tqe_next;                \
00433 } while (/*CONSTCOND*/0)
00434 
00435 #define       TAILQ_FOREACH(var, head, field)                                \
00436        for ((var) = ((head)->tqh_first);                       \
00437               (var);                                           \
00438               (var) = ((var)->field.tqe_next))
00439 
00440 #define       TAILQ_FOREACH_REVERSE(var, head, headname, field)              \
00441        for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));  \
00442               (var);                                           \
00443               (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
00444 
00445 #define       TAILQ_CONCAT(head1, head2, field) do {                         \
00446        if (!TAILQ_EMPTY(head2)) {                              \
00447               *(head1)->tqh_last = (head2)->tqh_first;         \
00448               (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
00449               (head1)->tqh_last = (head2)->tqh_last;                  \
00450               TAILQ_INIT((head2));                             \
00451        }                                                       \
00452 } while (/*CONSTCOND*/0)
00453 
00454 /*
00455  * Tail queue access methods.
00456  */
00457 #define       TAILQ_EMPTY(head)           ((head)->tqh_first == NULL)
00458 #define       TAILQ_FIRST(head)           ((head)->tqh_first)
00459 #define       TAILQ_NEXT(elm, field)             ((elm)->field.tqe_next)
00460 
00461 #define       TAILQ_LAST(head, headname) \
00462        (*(((struct headname *)((head)->tqh_last))->tqh_last))
00463 #define       TAILQ_PREV(elm, headname, field) \
00464        (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
00465 
00466 
00467 /*
00468  * Circular queue definitions.
00469  */
00470 #define       CIRCLEQ_HEAD(name, type)                                \
00471 struct name {                                                  \
00472        struct type *cqh_first;            /* first element */         \
00473        struct type *cqh_last;             /* last element */          \
00474 }
00475 
00476 #define       CIRCLEQ_HEAD_INITIALIZER(head)                                 \
00477        { (void *)&head, (void *)&head }
00478 
00479 #define       CIRCLEQ_ENTRY(type)                                     \
00480 struct {                                                       \
00481        struct type *cqe_next;             /* next element */          \
00482        struct type *cqe_prev;             /* previous element */             \
00483 }
00484 
00485 /*
00486  * Circular queue functions.
00487  */
00488 #define       CIRCLEQ_INIT(head) do {                                        \
00489        (head)->cqh_first = (void *)(head);                            \
00490        (head)->cqh_last = (void *)(head);                      \
00491 } while (/*CONSTCOND*/0)
00492 
00493 #define       CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {           \
00494        (elm)->field.cqe_next = (listelm)->field.cqe_next;             \
00495        (elm)->field.cqe_prev = (listelm);                      \
00496        if ((listelm)->field.cqe_next == (void *)(head))        \
00497               (head)->cqh_last = (elm);                        \
00498        else                                                    \
00499               (listelm)->field.cqe_next->field.cqe_prev = (elm);      \
00500        (listelm)->field.cqe_next = (elm);                      \
00501 } while (/*CONSTCOND*/0)
00502 
00503 #define       CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {          \
00504        (elm)->field.cqe_next = (listelm);                      \
00505        (elm)->field.cqe_prev = (listelm)->field.cqe_prev;             \
00506        if ((listelm)->field.cqe_prev == (void *)(head))        \
00507               (head)->cqh_first = (elm);                       \
00508        else                                                    \
00509               (listelm)->field.cqe_prev->field.cqe_next = (elm);      \
00510        (listelm)->field.cqe_prev = (elm);                      \
00511 } while (/*CONSTCOND*/0)
00512 
00513 #define       CIRCLEQ_INSERT_HEAD(head, elm, field) do {                     \
00514        (elm)->field.cqe_next = (head)->cqh_first;                     \
00515        (elm)->field.cqe_prev = (void *)(head);                        \
00516        if ((head)->cqh_last == (void *)(head))                        \
00517               (head)->cqh_last = (elm);                        \
00518        else                                                    \
00519               (head)->cqh_first->field.cqe_prev = (elm);              \
00520        (head)->cqh_first = (elm);                              \
00521 } while (/*CONSTCOND*/0)
00522 
00523 #define       CIRCLEQ_INSERT_TAIL(head, elm, field) do {                     \
00524        (elm)->field.cqe_next = (void *)(head);                        \
00525        (elm)->field.cqe_prev = (head)->cqh_last;               \
00526        if ((head)->cqh_first == (void *)(head))                \
00527               (head)->cqh_first = (elm);                       \
00528        else                                                    \
00529               (head)->cqh_last->field.cqe_next = (elm);        \
00530        (head)->cqh_last = (elm);                               \
00531 } while (/*CONSTCOND*/0)
00532 
00533 #define       CIRCLEQ_REMOVE(head, elm, field) do {                          \
00534        if ((elm)->field.cqe_next == (void *)(head))                   \
00535               (head)->cqh_last = (elm)->field.cqe_prev;        \
00536        else                                                    \
00537               (elm)->field.cqe_next->field.cqe_prev =                 \
00538                   (elm)->field.cqe_prev;                       \
00539        if ((elm)->field.cqe_prev == (void *)(head))                   \
00540               (head)->cqh_first = (elm)->field.cqe_next;              \
00541        else                                                    \
00542               (elm)->field.cqe_prev->field.cqe_next =                 \
00543                   (elm)->field.cqe_next;                       \
00544 } while (/*CONSTCOND*/0)
00545 
00546 #define       CIRCLEQ_FOREACH(var, head, field)                       \
00547        for ((var) = ((head)->cqh_first);                       \
00548               (var) != (const void *)(head);                          \
00549               (var) = ((var)->field.cqe_next))
00550 
00551 #define       CIRCLEQ_FOREACH_REVERSE(var, head, field)               \
00552        for ((var) = ((head)->cqh_last);                        \
00553               (var) != (const void *)(head);                          \
00554               (var) = ((var)->field.cqe_prev))
00555 
00556 /*
00557  * Circular queue access methods.
00558  */
00559 #define       CIRCLEQ_EMPTY(head)         ((head)->cqh_first == (void *)(head))
00560 #define       CIRCLEQ_FIRST(head)         ((head)->cqh_first)
00561 #define       CIRCLEQ_LAST(head)          ((head)->cqh_last)
00562 #define       CIRCLEQ_NEXT(elm, field)    ((elm)->field.cqe_next)
00563 #define       CIRCLEQ_PREV(elm, field)    ((elm)->field.cqe_prev)
00564 
00565 #define CIRCLEQ_LOOP_NEXT(head, elm, field)                           \
00566        (((elm)->field.cqe_next == (void *)(head))                     \
00567            ? ((head)->cqh_first)                               \
00568            : (elm->field.cqe_next))
00569 #define CIRCLEQ_LOOP_PREV(head, elm, field)                           \
00570        (((elm)->field.cqe_prev == (void *)(head))                     \
00571            ? ((head)->cqh_last)                                \
00572            : (elm->field.cqe_prev))
00573 
00574 #endif /* sys/queue.h */