URL https://opencores.org/ocsvn/c0or1k/c0or1k/trunk

Subversion Repositories c0or1k

[/] [c0or1k/] [trunk/] [conts/] [posix/] [libposix/] [include/] [posix/] [sys/] [queue.h] - Blame information for rev 2

Details | Compare with Previous | View Log


/*
 * Copyright (c) 1991, 1993
 *      The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *      @(#)queue.h     8.5 (Berkeley) 8/20/94
 */
 
#ifndef _SYS_QUEUE_H_
#define _SYS_QUEUE_H_
 
/*
 * This file defines five types of data structures: singly-linked lists,
 * lists, simple queues, tail queues, and circular queues.
 *
 * A singly-linked list is headed by a single forward pointer. The
 * elements are singly linked for minimum space and pointer manipulation
 * overhead at the expense of O(n) removal for arbitrary elements. New
 * elements can be added to the list after an existing element or at the
 * head of the list.  Elements being removed from the head of the list
 * should use the explicit macro for this purpose for optimum
 * efficiency. A singly-linked list may only be traversed in the forward
 * direction.  Singly-linked lists are ideal for applications with large
 * datasets and few or no removals or for implementing a LIFO queue.
 *
 * A list is headed by a single forward pointer (or an array of forward
 * pointers for a hash table header). The elements are doubly linked
 * so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before
 * or after an existing element or at the head of the list. A list
 * may only be traversed in the forward direction.
 *
 * A simple queue is headed by a pair of pointers, one the head of the
 * list and the other to the tail of the list. The elements are singly
 * linked to save space, so elements can only be removed from the
 * head of the list. New elements can be added to the list after
 * an existing element, at the head of the list, or at the end of the
 * list. A simple queue may only be traversed in the forward direction.
 *
 * A tail queue is headed by a pair of pointers, one to the head of the
 * list and the other to the tail of the list. The elements are doubly
 * linked so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before or
 * after an existing element, at the head of the list, or at the end of
 * the list. A tail queue may be traversed in either direction.
 *
 * A circle queue is headed by a pair of pointers, one to the head of the
 * list and the other to the tail of the list. The elements are doubly
 * linked so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before or after
 * an existing element, at the head of the list, or at the end of the list.
 * A circle queue may be traversed in either direction, but has a more
 * complex end of list detection.
 *
 * For details on the use of these macros, see the queue(3) manual page.
 */
 
/*
 * List definitions.
 */
#define LIST_HEAD(name, type)                                           \
struct name {                                                           \
        struct type *lh_first;  /* first element */                     \
}
 
#define LIST_HEAD_INITIALIZER(head)                                     \
        { NULL }
 
#define LIST_ENTRY(type)                                                \
struct {                                                                \
        struct type *le_next;   /* next element */                      \
        struct type **le_prev;  /* address of previous next element */  \
}
 
/*
 * List functions.
 */
#define LIST_INIT(head) do {                                            \
        (head)->lh_first = NULL;                                        \
} while (/*CONSTCOND*/0)
 
#define LIST_INSERT_AFTER(listelm, elm, field) do {                     \
        if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)  \
                (listelm)->field.le_next->field.le_prev =               \
                    &(elm)->field.le_next;                              \
        (listelm)->field.le_next = (elm);                               \
        (elm)->field.le_prev = &(listelm)->field.le_next;               \
} while (/*CONSTCOND*/0)
 
#define LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
        (elm)->field.le_prev = (listelm)->field.le_prev;                \
        (elm)->field.le_next = (listelm);                               \
        *(listelm)->field.le_prev = (elm);                              \
        (listelm)->field.le_prev = &(elm)->field.le_next;               \
} while (/*CONSTCOND*/0)
 
#define LIST_INSERT_HEAD(head, elm, field) do {                         \
        if (((elm)->field.le_next = (head)->lh_first) != NULL)          \
                (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
        (head)->lh_first = (elm);                                       \
        (elm)->field.le_prev = &(head)->lh_first;                       \
} while (/*CONSTCOND*/0)
 
#define LIST_REMOVE(elm, field) do {                                    \
        if ((elm)->field.le_next != NULL)                               \
                (elm)->field.le_next->field.le_prev =                   \
                    (elm)->field.le_prev;                               \
        *(elm)->field.le_prev = (elm)->field.le_next;                   \
} while (/*CONSTCOND*/0)
 
#define LIST_FOREACH(var, head, field)                                  \
        for ((var) = ((head)->lh_first);                                \
                (var);                                                  \
                (var) = ((var)->field.le_next))
 
/*
 * List access methods.
 */
#define LIST_EMPTY(head)                ((head)->lh_first == NULL)
#define LIST_FIRST(head)                ((head)->lh_first)
#define LIST_NEXT(elm, field)           ((elm)->field.le_next)
 
 
/*
 * Singly-linked List definitions.
 */
#define SLIST_HEAD(name, type)                                          \
struct name {                                                           \
        struct type *slh_first; /* first element */                     \
}
 
#define SLIST_HEAD_INITIALIZER(head)                                    \
        { NULL }
 
#define SLIST_ENTRY(type)                                               \
struct {                                                                \
        struct type *sle_next;  /* next element */                      \
}
 
/*
 * Singly-linked List functions.
 */
#define SLIST_INIT(head) do {                                           \
        (head)->slh_first = NULL;                                       \
} while (/*CONSTCOND*/0)
 
#define SLIST_INSERT_AFTER(slistelm, elm, field) do {                   \
        (elm)->field.sle_next = (slistelm)->field.sle_next;             \
        (slistelm)->field.sle_next = (elm);                             \
} while (/*CONSTCOND*/0)
 
#define SLIST_INSERT_HEAD(head, elm, field) do {                        \
        (elm)->field.sle_next = (head)->slh_first;                      \
        (head)->slh_first = (elm);                                      \
} while (/*CONSTCOND*/0)
 
#define SLIST_REMOVE_HEAD(head, field) do {                             \
        (head)->slh_first = (head)->slh_first->field.sle_next;          \
} while (/*CONSTCOND*/0)
 
#define SLIST_REMOVE(head, elm, type, field) do {                       \
        if ((head)->slh_first == (elm)) {                               \
                SLIST_REMOVE_HEAD((head), field);                       \
        }                                                               \
        else {                                                          \
                struct type *curelm = (head)->slh_first;                \
                while(curelm->field.sle_next != (elm))                  \
                        curelm = curelm->field.sle_next;                \
                curelm->field.sle_next =                                \
                    curelm->field.sle_next->field.sle_next;             \
        }                                                               \
} while (/*CONSTCOND*/0)
 
#define SLIST_FOREACH(var, head, field)                                 \
        for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
 
/*
 * Singly-linked List access methods.
 */
#define SLIST_EMPTY(head)       ((head)->slh_first == NULL)
#define SLIST_FIRST(head)       ((head)->slh_first)
#define SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
 
 
/*
 * Singly-linked Tail queue declarations.
 */
#define STAILQ_HEAD(name, type)                                 \
struct name {                                                           \
        struct type *stqh_first;        /* first element */                     \
        struct type **stqh_last;        /* addr of last next element */         \
}
 
#define STAILQ_HEAD_INITIALIZER(head)                                   \
        { NULL, &(head).stqh_first }
 
#define STAILQ_ENTRY(type)                                              \
struct {                                                                \
        struct type *stqe_next; /* next element */                      \
}
 
/*
 * Singly-linked Tail queue functions.
 */
#define STAILQ_INIT(head) do {                                          \
        (head)->stqh_first = NULL;                                      \
        (head)->stqh_last = &(head)->stqh_first;                                \
} while (/*CONSTCOND*/0)
 
#define STAILQ_INSERT_HEAD(head, elm, field) do {                       \
        if (((elm)->field.stqe_next = (head)->stqh_first) == NULL)      \
                (head)->stqh_last = &(elm)->field.stqe_next;            \
        (head)->stqh_first = (elm);                                     \
} while (/*CONSTCOND*/0)
 
#define STAILQ_INSERT_TAIL(head, elm, field) do {                       \
        (elm)->field.stqe_next = NULL;                                  \
        *(head)->stqh_last = (elm);                                     \
        (head)->stqh_last = &(elm)->field.stqe_next;                    \
} while (/*CONSTCOND*/0)
 
#define STAILQ_INSERT_AFTER(head, listelm, elm, field) do {             \
        if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
                (head)->stqh_last = &(elm)->field.stqe_next;            \
        (listelm)->field.stqe_next = (elm);                             \
} while (/*CONSTCOND*/0)
 
#define STAILQ_REMOVE_HEAD(head, field) do {                            \
        if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
                (head)->stqh_last = &(head)->stqh_first;                        \
} while (/*CONSTCOND*/0)
 
#define STAILQ_REMOVE(head, elm, type, field) do {                      \
        if ((head)->stqh_first == (elm)) {                              \
                STAILQ_REMOVE_HEAD((head), field);                      \
        } else {                                                        \
                struct type *curelm = (head)->stqh_first;               \
                while (curelm->field.stqe_next != (elm))                        \
                        curelm = curelm->field.stqe_next;               \
                if ((curelm->field.stqe_next =                          \
                        curelm->field.stqe_next->field.stqe_next) == NULL) \
                            (head)->stqh_last = &(curelm)->field.stqe_next; \
        }                                                               \
} while (/*CONSTCOND*/0)
 
#define STAILQ_FOREACH(var, head, field)                                \
        for ((var) = ((head)->stqh_first);                              \
                (var);                                                  \
                (var) = ((var)->field.stqe_next))
 
/*
 * Singly-linked Tail queue access methods.
 */
#define STAILQ_EMPTY(head)      ((head)->stqh_first == NULL)
#define STAILQ_FIRST(head)      ((head)->stqh_first)
#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
 
 
/*
 * Simple queue definitions.
 */
#define SIMPLEQ_HEAD(name, type)                                        \
struct name {                                                           \
        struct type *sqh_first; /* first element */                     \
        struct type **sqh_last; /* addr of last next element */         \
}
 
#define SIMPLEQ_HEAD_INITIALIZER(head)                                  \
        { NULL, &(head).sqh_first }
 
#define SIMPLEQ_ENTRY(type)                                             \
struct {                                                                \
        struct type *sqe_next;  /* next element */                      \
}
 
/*
 * Simple queue functions.
 */
#define SIMPLEQ_INIT(head) do {                                         \
        (head)->sqh_first = NULL;                                       \
        (head)->sqh_last = &(head)->sqh_first;                          \
} while (/*CONSTCOND*/0)
 
#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {                      \
        if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)        \
                (head)->sqh_last = &(elm)->field.sqe_next;              \
        (head)->sqh_first = (elm);                                      \
} while (/*CONSTCOND*/0)
 
#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {                      \
        (elm)->field.sqe_next = NULL;                                   \
        *(head)->sqh_last = (elm);                                      \
        (head)->sqh_last = &(elm)->field.sqe_next;                      \
} while (/*CONSTCOND*/0)
 
#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
        if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
                (head)->sqh_last = &(elm)->field.sqe_next;              \
        (listelm)->field.sqe_next = (elm);                              \
} while (/*CONSTCOND*/0)
 
#define SIMPLEQ_REMOVE_HEAD(head, field) do {                           \
        if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
                (head)->sqh_last = &(head)->sqh_first;                  \
} while (/*CONSTCOND*/0)
 
#define SIMPLEQ_REMOVE(head, elm, type, field) do {                     \
        if ((head)->sqh_first == (elm)) {                               \
                SIMPLEQ_REMOVE_HEAD((head), field);                     \
        } else {                                                        \
                struct type *curelm = (head)->sqh_first;                \
                while (curelm->field.sqe_next != (elm))                 \
                        curelm = curelm->field.sqe_next;                \
                if ((curelm->field.sqe_next =                           \
                        curelm->field.sqe_next->field.sqe_next) == NULL) \
                            (head)->sqh_last = &(curelm)->field.sqe_next; \
        }                                                               \
} while (/*CONSTCOND*/0)
 
#define SIMPLEQ_FOREACH(var, head, field)                               \
        for ((var) = ((head)->sqh_first);                               \
                (var);                                                  \
                (var) = ((var)->field.sqe_next))
 
/*
 * Simple queue access methods.
 */
#define SIMPLEQ_EMPTY(head)             ((head)->sqh_first == NULL)
#define SIMPLEQ_FIRST(head)             ((head)->sqh_first)
#define SIMPLEQ_NEXT(elm, field)        ((elm)->field.sqe_next)
 
 
/*
 * Tail queue definitions.
 */
#define _TAILQ_HEAD(name, type, qual)                                   \
struct name {                                                           \
        qual type *tqh_first;           /* first element */             \
        qual type *qual *tqh_last;      /* addr of last next element */ \
}
#define TAILQ_HEAD(name, type)  _TAILQ_HEAD(name, struct type,)
 
#define TAILQ_HEAD_INITIALIZER(head)                                    \
        { NULL, &(head).tqh_first }
 
#define _TAILQ_ENTRY(type, qual)                                        \
struct {                                                                \
        qual type *tqe_next;            /* next element */              \
        qual type *qual *tqe_prev;      /* address of previous next element */\
}
#define TAILQ_ENTRY(type)       _TAILQ_ENTRY(struct type,)
 
/*
 * Tail queue functions.
 */
#define TAILQ_INIT(head) do {                                           \
        (head)->tqh_first = NULL;                                       \
        (head)->tqh_last = &(head)->tqh_first;                          \
} while (/*CONSTCOND*/0)
 
#define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
        if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
                (head)->tqh_first->field.tqe_prev =                     \
                    &(elm)->field.tqe_next;                             \
        else                                                            \
                (head)->tqh_last = &(elm)->field.tqe_next;              \
        (head)->tqh_first = (elm);                                      \
        (elm)->field.tqe_prev = &(head)->tqh_first;                     \
} while (/*CONSTCOND*/0)
 
#define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
        (elm)->field.tqe_next = NULL;                                   \
        (elm)->field.tqe_prev = (head)->tqh_last;                       \
        *(head)->tqh_last = (elm);                                      \
        (head)->tqh_last = &(elm)->field.tqe_next;                      \
} while (/*CONSTCOND*/0)
 
#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
        if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
                (elm)->field.tqe_next->field.tqe_prev =                 \
                    &(elm)->field.tqe_next;                             \
        else                                                            \
                (head)->tqh_last = &(elm)->field.tqe_next;              \
        (listelm)->field.tqe_next = (elm);                              \
        (elm)->field.tqe_prev = &(listelm)->field.tqe_next;             \
} while (/*CONSTCOND*/0)
 
#define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
        (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
        (elm)->field.tqe_next = (listelm);                              \
        *(listelm)->field.tqe_prev = (elm);                             \
        (listelm)->field.tqe_prev = &(elm)->field.tqe_next;             \
} while (/*CONSTCOND*/0)
 
#define TAILQ_REMOVE(head, elm, field) do {                             \
        if (((elm)->field.tqe_next) != NULL)                            \
                (elm)->field.tqe_next->field.tqe_prev =                 \
                    (elm)->field.tqe_prev;                              \
        else                                                            \
                (head)->tqh_last = (elm)->field.tqe_prev;               \
        *(elm)->field.tqe_prev = (elm)->field.tqe_next;                 \
} while (/*CONSTCOND*/0)
 
#define TAILQ_FOREACH(var, head, field)                                 \
        for ((var) = ((head)->tqh_first);                               \
                (var);                                                  \
                (var) = ((var)->field.tqe_next))
 
#define TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
        for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));    \
                (var);                                                  \
                (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
 
/*
 * Tail queue access methods.
 */
#define TAILQ_EMPTY(head)               ((head)->tqh_first == NULL)
#define TAILQ_FIRST(head)               ((head)->tqh_first)
#define TAILQ_NEXT(elm, field)          ((elm)->field.tqe_next)
 
#define TAILQ_LAST(head, headname) \
        (*(((struct headname *)((head)->tqh_last))->tqh_last))
#define TAILQ_PREV(elm, headname, field) \
        (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 
 
/*
 * Circular queue definitions.
 */
#define CIRCLEQ_HEAD(name, type)                                        \
struct name {                                                           \
        struct type *cqh_first;         /* first element */             \
        struct type *cqh_last;          /* last element */              \
}
 
#define CIRCLEQ_HEAD_INITIALIZER(head)                                  \
        { (void *)&head, (void *)&head }
 
#define CIRCLEQ_ENTRY(type)                                             \
struct {                                                                \
        struct type *cqe_next;          /* next element */              \
        struct type *cqe_prev;          /* previous element */          \
}
 
/*
 * Circular queue functions.
 */
#define CIRCLEQ_INIT(head) do {                                         \
        (head)->cqh_first = (void *)(head);                             \
        (head)->cqh_last = (void *)(head);                              \
} while (/*CONSTCOND*/0)
 
#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
        (elm)->field.cqe_next = (listelm)->field.cqe_next;              \
        (elm)->field.cqe_prev = (listelm);                              \
        if ((listelm)->field.cqe_next == (void *)(head))                \
                (head)->cqh_last = (elm);                               \
        else                                                            \
                (listelm)->field.cqe_next->field.cqe_prev = (elm);      \
        (listelm)->field.cqe_next = (elm);                              \
} while (/*CONSTCOND*/0)
 
#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {           \
        (elm)->field.cqe_next = (listelm);                              \
        (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \
        if ((listelm)->field.cqe_prev == (void *)(head))                \
                (head)->cqh_first = (elm);                              \
        else                                                            \
                (listelm)->field.cqe_prev->field.cqe_next = (elm);      \
        (listelm)->field.cqe_prev = (elm);                              \
} while (/*CONSTCOND*/0)
 
#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {                      \
        (elm)->field.cqe_next = (head)->cqh_first;                      \
        (elm)->field.cqe_prev = (void *)(head);                         \
        if ((head)->cqh_last == (void *)(head))                         \
                (head)->cqh_last = (elm);                               \
        else                                                            \
                (head)->cqh_first->field.cqe_prev = (elm);              \
        (head)->cqh_first = (elm);                                      \
} while (/*CONSTCOND*/0)
 
#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {                      \
        (elm)->field.cqe_next = (void *)(head);                         \
        (elm)->field.cqe_prev = (head)->cqh_last;                       \
        if ((head)->cqh_first == (void *)(head))                        \
                (head)->cqh_first = (elm);                              \
        else                                                            \
                (head)->cqh_last->field.cqe_next = (elm);               \
        (head)->cqh_last = (elm);                                       \
} while (/*CONSTCOND*/0)
 
#define CIRCLEQ_REMOVE(head, elm, field) do {                           \
        if ((elm)->field.cqe_next == (void *)(head))                    \
                (head)->cqh_last = (elm)->field.cqe_prev;               \
        else                                                            \
                (elm)->field.cqe_next->field.cqe_prev =                 \
                    (elm)->field.cqe_prev;                              \
        if ((elm)->field.cqe_prev == (void *)(head))                    \
                (head)->cqh_first = (elm)->field.cqe_next;              \
        else                                                            \
                (elm)->field.cqe_prev->field.cqe_next =                 \
                    (elm)->field.cqe_next;                              \
} while (/*CONSTCOND*/0)
 
#define CIRCLEQ_FOREACH(var, head, field)                               \
        for ((var) = ((head)->cqh_first);                               \
                (var) != (const void *)(head);                          \
                (var) = ((var)->field.cqe_next))
 
#define CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \
        for ((var) = ((head)->cqh_last);                                \
                (var) != (const void *)(head);                          \
                (var) = ((var)->field.cqe_prev))
 
/*
 * Circular queue access methods.
 */
#define CIRCLEQ_EMPTY(head)             ((head)->cqh_first == (void *)(head))
#define CIRCLEQ_FIRST(head)             ((head)->cqh_first)
#define CIRCLEQ_LAST(head)              ((head)->cqh_last)
#define CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)
#define CIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)
 
#define CIRCLEQ_LOOP_NEXT(head, elm, field)                             \
        (((elm)->field.cqe_next == (void *)(head))                      \
            ? ((head)->cqh_first)                                       \
            : (elm->field.cqe_next))
#define CIRCLEQ_LOOP_PREV(head, elm, field)                             \
        (((elm)->field.cqe_prev == (void *)(head))                      \
            ? ((head)->cqh_last)                                        \
            : (elm->field.cqe_prev))
 
#endif  /* sys/queue.h */

Browse

Tools

Subversion Repositories c0or1k

[/] [c0or1k/] [trunk/] [conts/] [posix/] [libposix/] [include/] [posix/] [sys/] [queue.h] - Blame information for rev 2

Line No.	Rev	Author	Line
1	2	drasko	`/*`
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. Neither the name of the University nor the names of its contributors`
14			`* may be used to endorse or promote products derived from this software`
15			`* without specific prior written permission.`
16			`*`
17			* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18			`* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE`
19			`* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE`
20			`* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE`
21			`* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL`
22			`* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS`
23			`* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)`
24			`* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT`
25			`* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY`
26			`* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF`
27			`* SUCH DAMAGE.`
28			`*`
29			`* @(#)queue.h 8.5 (Berkeley) 8/20/94`
30			`*/`
31
32			`#ifndef _SYS_QUEUE_H_`
33			`#define _SYS_QUEUE_H_`
34
35			`/*`
36			`* This file defines five types of data structures: singly-linked lists,`
37			`* lists, simple queues, tail queues, and circular queues.`
38			`*`
39			`* A singly-linked list is headed by a single forward pointer. The`
40			`* elements are singly linked for minimum space and pointer manipulation`
41			`* overhead at the expense of O(n) removal for arbitrary elements. New`
42			`* elements can be added to the list after an existing element or at the`
43			`* head of the list. Elements being removed from the head of the list`
44			`* should use the explicit macro for this purpose for optimum`
45			`* efficiency. A singly-linked list may only be traversed in the forward`
46			`* direction. Singly-linked lists are ideal for applications with large`
47			`* datasets and few or no removals or for implementing a LIFO queue.`
48			`*`
49			`* A list is headed by a single forward pointer (or an array of forward`
50			`* pointers for a hash table header). The elements are doubly linked`
51			`* so that an arbitrary element can be removed without a need to`
52			`* traverse the list. New elements can be added to the list before`
53			`* or after an existing element or at the head of the list. A list`
54			`* may only be traversed in the forward direction.`
55			`*`
56			`* A simple queue is headed by a pair of pointers, one the head of the`
57			`* list and the other to the tail of the list. The elements are singly`
58			`* linked to save space, so elements can only be removed from the`
59			`* head of the list. New elements can be added to the list after`
60			`* an existing element, at the head of the list, or at the end of the`
61			`* list. A simple queue may only be traversed in the forward direction.`
62			`*`
63			`* A tail queue is headed by a pair of pointers, one to the head of the`
64			`* list and the other to the tail of the list. The elements are doubly`
65			`* linked so that an arbitrary element can be removed without a need to`
66			`* traverse the list. New elements can be added to the list before or`
67			`* after an existing element, at the head of the list, or at the end of`
68			`* the list. A tail queue may be traversed in either direction.`
69			`*`
70			`* A circle queue is headed by a pair of pointers, one to the head of the`
71			`* list and the other to the tail of the list. The elements are doubly`
72			`* linked so that an arbitrary element can be removed without a need to`
73			`* traverse the list. New elements can be added to the list before or after`
74			`* an existing element, at the head of the list, or at the end of the list.`
75			`* A circle queue may be traversed in either direction, but has a more`
76			`* complex end of list detection.`
77			`*`
78			`* For details on the use of these macros, see the queue(3) manual page.`
79			`*/`
80
81			`/*`
82			`* List definitions.`
83			`*/`
84			`#define LIST_HEAD(name, type) \`
85			`struct name { \`
86			`struct type lh_first; / first element */ \`
87			`}`
88
89			`#define LIST_HEAD_INITIALIZER(head) \`
90			`{ NULL }`
91
92			`#define LIST_ENTRY(type) \`
93			`struct { \`
94			`struct type le_next; / next element */ \`
95			`struct type *le_prev; / address of previous next element */ \`
96			`}`
97
98			`/*`
99			`* List functions.`
100			`*/`
101			`#define LIST_INIT(head) do { \`
102			`(head)->lh_first = NULL; \`
103			`} while (/CONSTCOND/0)`
104
105			`#define LIST_INSERT_AFTER(listelm, elm, field) do { \`
106			`if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \`
107			`(listelm)->field.le_next->field.le_prev = \`
108			`&(elm)->field.le_next; \`
109			`(listelm)->field.le_next = (elm); \`
110			`(elm)->field.le_prev = &(listelm)->field.le_next; \`
111			`} while (/CONSTCOND/0)`
112
113			`#define LIST_INSERT_BEFORE(listelm, elm, field) do { \`
114			`(elm)->field.le_prev = (listelm)->field.le_prev; \`
115			`(elm)->field.le_next = (listelm); \`
116			`*(listelm)->field.le_prev = (elm); \`
117			`(listelm)->field.le_prev = &(elm)->field.le_next; \`
118			`} while (/CONSTCOND/0)`
119
120			`#define LIST_INSERT_HEAD(head, elm, field) do { \`
121			`if (((elm)->field.le_next = (head)->lh_first) != NULL) \`
122			`(head)->lh_first->field.le_prev = &(elm)->field.le_next;\`
123			`(head)->lh_first = (elm); \`
124			`(elm)->field.le_prev = &(head)->lh_first; \`
125			`} while (/CONSTCOND/0)`
126
127			`#define LIST_REMOVE(elm, field) do { \`
128			`if ((elm)->field.le_next != NULL) \`
129			`(elm)->field.le_next->field.le_prev = \`
130			`(elm)->field.le_prev; \`
131			`*(elm)->field.le_prev = (elm)->field.le_next; \`
132			`} while (/CONSTCOND/0)`
133
134			`#define LIST_FOREACH(var, head, field) \`
135			`for ((var) = ((head)->lh_first); \`
136			`(var); \`
137			`(var) = ((var)->field.le_next))`
138
139			`/*`
140			`* List access methods.`
141			`*/`
142			`#define LIST_EMPTY(head) ((head)->lh_first == NULL)`
143			`#define LIST_FIRST(head) ((head)->lh_first)`
144			`#define LIST_NEXT(elm, field) ((elm)->field.le_next)`
145
146
147			`/*`
148			`* Singly-linked List definitions.`
149			`*/`
150			`#define SLIST_HEAD(name, type) \`
151			`struct name { \`
152			`struct type slh_first; / first element */ \`
153			`}`
154
155			`#define SLIST_HEAD_INITIALIZER(head) \`
156			`{ NULL }`
157
158			`#define SLIST_ENTRY(type) \`
159			`struct { \`
160			`struct type sle_next; / next element */ \`
161			`}`
162
163			`/*`
164			`* Singly-linked List functions.`
165			`*/`
166			`#define SLIST_INIT(head) do { \`
167			`(head)->slh_first = NULL; \`
168			`} while (/CONSTCOND/0)`
169
170			`#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \`
171			`(elm)->field.sle_next = (slistelm)->field.sle_next; \`
172			`(slistelm)->field.sle_next = (elm); \`
173			`} while (/CONSTCOND/0)`
174
175			`#define SLIST_INSERT_HEAD(head, elm, field) do { \`
176			`(elm)->field.sle_next = (head)->slh_first; \`
177			`(head)->slh_first = (elm); \`
178			`} while (/CONSTCOND/0)`
179
180			`#define SLIST_REMOVE_HEAD(head, field) do { \`
181			`(head)->slh_first = (head)->slh_first->field.sle_next; \`
182			`} while (/CONSTCOND/0)`
183
184			`#define SLIST_REMOVE(head, elm, type, field) do { \`
185			`if ((head)->slh_first == (elm)) { \`
186			`SLIST_REMOVE_HEAD((head), field); \`
187			`} \`
188			`else { \`
189			`struct type *curelm = (head)->slh_first; \`
190			`while(curelm->field.sle_next != (elm)) \`
191			`curelm = curelm->field.sle_next; \`
192			`curelm->field.sle_next = \`
193			`curelm->field.sle_next->field.sle_next; \`
194			`} \`
195			`} while (/CONSTCOND/0)`
196
197			`#define SLIST_FOREACH(var, head, field) \`
198			`for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)`
199
200			`/*`
201			`* Singly-linked List access methods.`
202			`*/`
203			`#define SLIST_EMPTY(head) ((head)->slh_first == NULL)`
204			`#define SLIST_FIRST(head) ((head)->slh_first)`
205			`#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)`
206
207
208			`/*`
209			`* Singly-linked Tail queue declarations.`
210			`*/`
211			`#define STAILQ_HEAD(name, type) \`
212			`struct name { \`
213			`struct type stqh_first; / first element */ \`
214			`struct type *stqh_last; / addr of last next element */ \`
215			`}`
216
217			`#define STAILQ_HEAD_INITIALIZER(head) \`
218			`{ NULL, &(head).stqh_first }`
219
220			`#define STAILQ_ENTRY(type) \`
221			`struct { \`
222			`struct type stqe_next; / next element */ \`
223			`}`
224
225			`/*`
226			`* Singly-linked Tail queue functions.`
227			`*/`
228			`#define STAILQ_INIT(head) do { \`
229			`(head)->stqh_first = NULL; \`
230			`(head)->stqh_last = &(head)->stqh_first; \`
231			`} while (/CONSTCOND/0)`
232
233			`#define STAILQ_INSERT_HEAD(head, elm, field) do { \`
234			`if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \`
235			`(head)->stqh_last = &(elm)->field.stqe_next; \`
236			`(head)->stqh_first = (elm); \`
237			`} while (/CONSTCOND/0)`
238
239			`#define STAILQ_INSERT_TAIL(head, elm, field) do { \`
240			`(elm)->field.stqe_next = NULL; \`
241			`*(head)->stqh_last = (elm); \`
242			`(head)->stqh_last = &(elm)->field.stqe_next; \`
243			`} while (/CONSTCOND/0)`
244
245			`#define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \`
246			`if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\`
247			`(head)->stqh_last = &(elm)->field.stqe_next; \`
248			`(listelm)->field.stqe_next = (elm); \`
249			`} while (/CONSTCOND/0)`
250
251			`#define STAILQ_REMOVE_HEAD(head, field) do { \`
252			`if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \`
253			`(head)->stqh_last = &(head)->stqh_first; \`
254			`} while (/CONSTCOND/0)`
255
256			`#define STAILQ_REMOVE(head, elm, type, field) do { \`
257			`if ((head)->stqh_first == (elm)) { \`
258			`STAILQ_REMOVE_HEAD((head), field); \`
259			`} else { \`
260			`struct type *curelm = (head)->stqh_first; \`
261			`while (curelm->field.stqe_next != (elm)) \`
262			`curelm = curelm->field.stqe_next; \`
263			`if ((curelm->field.stqe_next = \`
264			`curelm->field.stqe_next->field.stqe_next) == NULL) \`
265			`(head)->stqh_last = &(curelm)->field.stqe_next; \`
266			`} \`
267			`} while (/CONSTCOND/0)`
268
269			`#define STAILQ_FOREACH(var, head, field) \`
270			`for ((var) = ((head)->stqh_first); \`
271			`(var); \`
272			`(var) = ((var)->field.stqe_next))`
273
274			`/*`
275			`* Singly-linked Tail queue access methods.`
276			`*/`
277			`#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)`
278			`#define STAILQ_FIRST(head) ((head)->stqh_first)`
279			`#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)`
280
281
282			`/*`
283			`* Simple queue definitions.`
284			`*/`
285			`#define SIMPLEQ_HEAD(name, type) \`
286			`struct name { \`
287			`struct type sqh_first; / first element */ \`
288			`struct type *sqh_last; / addr of last next element */ \`
289			`}`
290
291			`#define SIMPLEQ_HEAD_INITIALIZER(head) \`
292			`{ NULL, &(head).sqh_first }`
293
294			`#define SIMPLEQ_ENTRY(type) \`
295			`struct { \`
296			`struct type sqe_next; / next element */ \`
297			`}`
298
299			`/*`
300			`* Simple queue functions.`
301			`*/`
302			`#define SIMPLEQ_INIT(head) do { \`
303			`(head)->sqh_first = NULL; \`
304			`(head)->sqh_last = &(head)->sqh_first; \`
305			`} while (/CONSTCOND/0)`
306
307			`#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \`
308			`if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \`
309			`(head)->sqh_last = &(elm)->field.sqe_next; \`
310			`(head)->sqh_first = (elm); \`
311			`} while (/CONSTCOND/0)`
312
313			`#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \`
314			`(elm)->field.sqe_next = NULL; \`
315			`*(head)->sqh_last = (elm); \`
316			`(head)->sqh_last = &(elm)->field.sqe_next; \`
317			`} while (/CONSTCOND/0)`
318
319			`#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \`
320			`if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\`
321			`(head)->sqh_last = &(elm)->field.sqe_next; \`
322			`(listelm)->field.sqe_next = (elm); \`
323			`} while (/CONSTCOND/0)`
324
325			`#define SIMPLEQ_REMOVE_HEAD(head, field) do { \`
326			`if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \`
327			`(head)->sqh_last = &(head)->sqh_first; \`
328			`} while (/CONSTCOND/0)`
329
330			`#define SIMPLEQ_REMOVE(head, elm, type, field) do { \`
331			`if ((head)->sqh_first == (elm)) { \`
332			`SIMPLEQ_REMOVE_HEAD((head), field); \`
333			`} else { \`
334			`struct type *curelm = (head)->sqh_first; \`
335			`while (curelm->field.sqe_next != (elm)) \`
336			`curelm = curelm->field.sqe_next; \`
337			`if ((curelm->field.sqe_next = \`
338			`curelm->field.sqe_next->field.sqe_next) == NULL) \`
339			`(head)->sqh_last = &(curelm)->field.sqe_next; \`
340			`} \`
341			`} while (/CONSTCOND/0)`
342
343			`#define SIMPLEQ_FOREACH(var, head, field) \`
344			`for ((var) = ((head)->sqh_first); \`
345			`(var); \`
346			`(var) = ((var)->field.sqe_next))`
347
348			`/*`
349			`* Simple queue access methods.`
350			`*/`
351			`#define SIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL)`
352			`#define SIMPLEQ_FIRST(head) ((head)->sqh_first)`
353			`#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)`
354
355
356			`/*`
357			`* Tail queue definitions.`
358			`*/`
359			`#define _TAILQ_HEAD(name, type, qual) \`
360			`struct name { \`
361			`qual type tqh_first; / first element */ \`
362			`qual type qual tqh_last; /* addr of last next element */ \`
363			`}`
364			`#define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,)`
365
366			`#define TAILQ_HEAD_INITIALIZER(head) \`
367			`{ NULL, &(head).tqh_first }`
368
369			`#define _TAILQ_ENTRY(type, qual) \`
370			`struct { \`
371			`qual type tqe_next; / next element */ \`
372			`qual type qual tqe_prev; /* address of previous next element */\`
373			`}`
374			`#define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,)`
375
376			`/*`
377			`* Tail queue functions.`
378			`*/`
379			`#define TAILQ_INIT(head) do { \`
380			`(head)->tqh_first = NULL; \`
381			`(head)->tqh_last = &(head)->tqh_first; \`
382			`} while (/CONSTCOND/0)`
383
384			`#define TAILQ_INSERT_HEAD(head, elm, field) do { \`
385			`if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \`
386			`(head)->tqh_first->field.tqe_prev = \`
387			`&(elm)->field.tqe_next; \`
388			`else \`
389			`(head)->tqh_last = &(elm)->field.tqe_next; \`
390			`(head)->tqh_first = (elm); \`
391			`(elm)->field.tqe_prev = &(head)->tqh_first; \`
392			`} while (/CONSTCOND/0)`
393
394			`#define TAILQ_INSERT_TAIL(head, elm, field) do { \`
395			`(elm)->field.tqe_next = NULL; \`
396			`(elm)->field.tqe_prev = (head)->tqh_last; \`
397			`*(head)->tqh_last = (elm); \`
398			`(head)->tqh_last = &(elm)->field.tqe_next; \`
399			`} while (/CONSTCOND/0)`
400
401			`#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \`
402			`if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\`
403			`(elm)->field.tqe_next->field.tqe_prev = \`
404			`&(elm)->field.tqe_next; \`
405			`else \`
406			`(head)->tqh_last = &(elm)->field.tqe_next; \`
407			`(listelm)->field.tqe_next = (elm); \`
408			`(elm)->field.tqe_prev = &(listelm)->field.tqe_next; \`
409			`} while (/CONSTCOND/0)`
410
411			`#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \`
412			`(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \`
413			`(elm)->field.tqe_next = (listelm); \`
414			`*(listelm)->field.tqe_prev = (elm); \`
415			`(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \`
416			`} while (/CONSTCOND/0)`
417
418			`#define TAILQ_REMOVE(head, elm, field) do { \`
419			`if (((elm)->field.tqe_next) != NULL) \`
420			`(elm)->field.tqe_next->field.tqe_prev = \`
421			`(elm)->field.tqe_prev; \`
422			`else \`
423			`(head)->tqh_last = (elm)->field.tqe_prev; \`
424			`*(elm)->field.tqe_prev = (elm)->field.tqe_next; \`
425			`} while (/CONSTCOND/0)`
426
427			`#define TAILQ_FOREACH(var, head, field) \`
428			`for ((var) = ((head)->tqh_first); \`
429			`(var); \`
430			`(var) = ((var)->field.tqe_next))`
431
432			`#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \`
433			`for ((var) = ((((struct headname )((head)->tqh_last))->tqh_last)); \`
434			`(var); \`
435			`(var) = ((((struct headname )((var)->field.tqe_prev))->tqh_last)))`
436
437			`/*`
438			`* Tail queue access methods.`
439			`*/`
440			`#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)`
441			`#define TAILQ_FIRST(head) ((head)->tqh_first)`
442			`#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)`
443
444			`#define TAILQ_LAST(head, headname) \`
445			`((((struct headname )((head)->tqh_last))->tqh_last))`
446			`#define TAILQ_PREV(elm, headname, field) \`
447			`((((struct headname )((elm)->field.tqe_prev))->tqh_last))`
448
449
450			`/*`
451			`* Circular queue definitions.`
452			`*/`
453			`#define CIRCLEQ_HEAD(name, type) \`
454			`struct name { \`
455			`struct type cqh_first; / first element */ \`
456			`struct type cqh_last; / last element */ \`
457			`}`
458
459			`#define CIRCLEQ_HEAD_INITIALIZER(head) \`
460			`{ (void )&head, (void )&head }`
461
462			`#define CIRCLEQ_ENTRY(type) \`
463			`struct { \`
464			`struct type cqe_next; / next element */ \`
465			`struct type cqe_prev; / previous element */ \`
466			`}`
467
468			`/*`
469			`* Circular queue functions.`
470			`*/`
471			`#define CIRCLEQ_INIT(head) do { \`
472			`(head)->cqh_first = (void *)(head); \`
473			`(head)->cqh_last = (void *)(head); \`
474			`} while (/CONSTCOND/0)`
475
476			`#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \`
477			`(elm)->field.cqe_next = (listelm)->field.cqe_next; \`
478			`(elm)->field.cqe_prev = (listelm); \`
479			`if ((listelm)->field.cqe_next == (void *)(head)) \`
480			`(head)->cqh_last = (elm); \`
481			`else \`
482			`(listelm)->field.cqe_next->field.cqe_prev = (elm); \`
483			`(listelm)->field.cqe_next = (elm); \`
484			`} while (/CONSTCOND/0)`
485
486			`#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \`
487			`(elm)->field.cqe_next = (listelm); \`
488			`(elm)->field.cqe_prev = (listelm)->field.cqe_prev; \`
489			`if ((listelm)->field.cqe_prev == (void *)(head)) \`
490			`(head)->cqh_first = (elm); \`
491			`else \`
492			`(listelm)->field.cqe_prev->field.cqe_next = (elm); \`
493			`(listelm)->field.cqe_prev = (elm); \`
494			`} while (/CONSTCOND/0)`
495
496			`#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \`
497			`(elm)->field.cqe_next = (head)->cqh_first; \`
498			`(elm)->field.cqe_prev = (void *)(head); \`
499			`if ((head)->cqh_last == (void *)(head)) \`
500			`(head)->cqh_last = (elm); \`
501			`else \`
502			`(head)->cqh_first->field.cqe_prev = (elm); \`
503			`(head)->cqh_first = (elm); \`
504			`} while (/CONSTCOND/0)`
505
506			`#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \`
507			`(elm)->field.cqe_next = (void *)(head); \`
508			`(elm)->field.cqe_prev = (head)->cqh_last; \`
509			`if ((head)->cqh_first == (void *)(head)) \`
510			`(head)->cqh_first = (elm); \`
511			`else \`
512			`(head)->cqh_last->field.cqe_next = (elm); \`
513			`(head)->cqh_last = (elm); \`
514			`} while (/CONSTCOND/0)`
515
516			`#define CIRCLEQ_REMOVE(head, elm, field) do { \`
517			`if ((elm)->field.cqe_next == (void *)(head)) \`
518			`(head)->cqh_last = (elm)->field.cqe_prev; \`
519			`else \`
520			`(elm)->field.cqe_next->field.cqe_prev = \`
521			`(elm)->field.cqe_prev; \`
522			`if ((elm)->field.cqe_prev == (void *)(head)) \`
523			`(head)->cqh_first = (elm)->field.cqe_next; \`
524			`else \`
525			`(elm)->field.cqe_prev->field.cqe_next = \`
526			`(elm)->field.cqe_next; \`
527			`} while (/CONSTCOND/0)`
528
529			`#define CIRCLEQ_FOREACH(var, head, field) \`
530			`for ((var) = ((head)->cqh_first); \`
531			`(var) != (const void *)(head); \`
532			`(var) = ((var)->field.cqe_next))`
533
534			`#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \`
535			`for ((var) = ((head)->cqh_last); \`
536			`(var) != (const void *)(head); \`
537			`(var) = ((var)->field.cqe_prev))`
538
539			`/*`
540			`* Circular queue access methods.`
541			`*/`
542			`#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))`
543			`#define CIRCLEQ_FIRST(head) ((head)->cqh_first)`
544			`#define CIRCLEQ_LAST(head) ((head)->cqh_last)`
545			`#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)`
546			`#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)`
547
548			`#define CIRCLEQ_LOOP_NEXT(head, elm, field) \`
549			`(((elm)->field.cqe_next == (void *)(head)) \`
550			`? ((head)->cqh_first) \`
551			`: (elm->field.cqe_next))`
552			`#define CIRCLEQ_LOOP_PREV(head, elm, field) \`
553			`(((elm)->field.cqe_prev == (void *)(head)) \`
554			`? ((head)->cqh_last) \`
555			`: (elm->field.cqe_prev))`
556
557			`#endif /* sys/queue.h */`