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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [rtos/] [ecos-2.0/] [packages/] [net/] [bsd_tcpip/] [v2_0/] [include/] [sys/] [queue.h] - Blame information for rev 27

Go to most recent revision | Details | Compare with Previous | View Log


//==========================================================================
//
//      include/sys/queue.h
//
//==========================================================================
//####BSDCOPYRIGHTBEGIN####
//
// -------------------------------------------
//
// Portions of this software may have been derived from OpenBSD, 
// FreeBSD or other sources, and are covered by the appropriate
// copyright disclaimers included herein.
//
// Portions created by Red Hat are
// Copyright (C) 2002 Red Hat, Inc. All Rights Reserved.
//
// -------------------------------------------
//
//####BSDCOPYRIGHTEND####
//==========================================================================
 
/*
 * 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. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by the University of
 *      California, Berkeley and its contributors.
 * 4. 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
 * $FreeBSD: src/sys/sys/queue.h,v 1.32.2.4 2001/03/31 03:33:39 hsu Exp $
 */
 
#ifndef _SYS_QUEUE_H_
#define _SYS_QUEUE_H_
 
/*
 * This file defines five types of data structures: singly-linked lists,
 * singly-linked tail queues, lists, 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 singly-linked 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
 * 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, at the head of the list, or at the
 * end of the list. Elements being removed from the head of the tail queue
 * should use the explicit macro for this purpose for optimum efficiency.
 * A singly-linked tail queue may only be traversed in the forward direction.
 * Singly-linked tail queues are ideal for applications with large datasets
 * and few or no removals or for implementing a FIFO 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 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.
 *
 *
 *                      SLIST   LIST    STAILQ  TAILQ   CIRCLEQ
 * _HEAD                +       +       +       +       +
 * _ENTRY               +       +       +       +       +
 * _INIT                +       +       +       +       +
 * _EMPTY               +       +       +       +       +
 * _FIRST               +       +       +       +       +
 * _NEXT                +       +       +       +       +
 * _PREV                -       -       -       +       +
 * _LAST                -       -       +       +       +
 * _FOREACH             +       +       +       +       +
 * _FOREACH_REVERSE     -       -       -       +       +
 * _INSERT_HEAD         +       +       +       +       +
 * _INSERT_BEFORE       -       +       -       +       +
 * _INSERT_AFTER        +       +       +       +       +
 * _INSERT_TAIL         -       -       +       +       +
 * _REMOVE_HEAD         +       -       +       -       -
 * _REMOVE              +       +       +       +       +
 *
 */
 
/*
 * 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_EMPTY(head)       ((head)->slh_first == NULL)
 
#define SLIST_FIRST(head)       ((head)->slh_first)
 
#define SLIST_FOREACH(var, head, field)                                 \
        for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
 
#define SLIST_INIT(head) {                                              \
        (head)->slh_first = NULL;                                       \
}
 
#define SLIST_INSERT_AFTER(slistelm, elm, field) do {                   \
        (elm)->field.sle_next = (slistelm)->field.sle_next;             \
        (slistelm)->field.sle_next = (elm);                             \
} while (0)
 
#define SLIST_INSERT_HEAD(head, elm, field) do {                        \
        (elm)->field.sle_next = (head)->slh_first;                      \
        (head)->slh_first = (elm);                                      \
} while (0)
 
#define SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
 
#define SLIST_REMOVE_HEAD(head, field) do {                             \
        (head)->slh_first = (head)->slh_first->field.sle_next;          \
} while (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 (0)
 
/*
 * Singly-linked Tail queue definitions.
 */
#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_EMPTY(head) ((head)->stqh_first == NULL)
 
#define STAILQ_INIT(head) do {                                          \
        (head)->stqh_first = NULL;                                      \
        (head)->stqh_last = &(head)->stqh_first;                        \
} while (0)
 
#define STAILQ_FIRST(head)      ((head)->stqh_first)
 
#define STAILQ_LAST(head, type, field)                                  \
        (STAILQ_EMPTY(head) ?                                           \
                NULL :                                                  \
                ((struct type *)                                        \
                ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
 
#define STAILQ_FOREACH(var, head, field)                                \
        for((var) = (head)->stqh_first; (var); (var) = (var)->field.stqe_next)
 
#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 (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 (0)
 
#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {               \
        if (((elm)->field.stqe_next = (tqelm)->field.stqe_next) == NULL)\
                (head)->stqh_last = &(elm)->field.stqe_next;            \
        (tqelm)->field.stqe_next = (elm);                               \
} while (0)
 
#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
 
#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 (0)
 
#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {                 \
        if (((head)->stqh_first = (elm)->field.stqe_next) == NULL)      \
                (head)->stqh_last = &(head)->stqh_first;                \
} while (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 (0)
 
/*
 * 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_EMPTY(head) ((head)->lh_first == NULL)
 
#define LIST_FIRST(head)        ((head)->lh_first)
 
#define LIST_FOREACH(var, head, field)                                  \
        for((var) = (head)->lh_first; (var); (var) = (var)->field.le_next)
 
#define LIST_INIT(head) do {                                            \
        (head)->lh_first = NULL;                                        \
} while (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 (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 (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 (0)
 
#define LIST_NEXT(elm, field)   ((elm)->field.le_next)
 
#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 (0)
 
/*
 * Tail queue definitions.
 */
#define TAILQ_HEAD(name, type)                                          \
struct name {                                                           \
        struct type *tqh_first; /* first element */                     \
        struct type **tqh_last; /* addr of last next element */         \
}
 
#define TAILQ_HEAD_INITIALIZER(head)                                    \
        { NULL, &(head).tqh_first }
 
#define TAILQ_ENTRY(type)                                               \
struct {                                                                \
        struct type *tqe_next;  /* next element */                      \
        struct type **tqe_prev; /* address of previous next element */  \
}
 
/*
 * Tail queue functions.
 */
#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
 
#define TAILQ_FOREACH(var, head, field)                                 \
        for (var = TAILQ_FIRST(head); var; var = TAILQ_NEXT(var, field))
 
#define TAILQ_FOREACH_REVERSE(var, head, headname, field)               \
        for ((var) = TAILQ_LAST((head), headname);                      \
             (var);                                                     \
             (var) = TAILQ_PREV((var), headname, field))
 
#define TAILQ_FIRST(head) ((head)->tqh_first)
 
#define TAILQ_LAST(head, headname) \
        (*(((struct headname *)((head)->tqh_last))->tqh_last))
 
#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
 
#define TAILQ_PREV(elm, headname, field) \
        (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
 
#define TAILQ_INIT(head) do {                                           \
        (head)->tqh_first = NULL;                                       \
        (head)->tqh_last = &(head)->tqh_first;                          \
} while (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 (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 (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 (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 (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 (0)
 
/*
 * Circular queue definitions.
 */
#define CIRCLEQ_HEAD(name, type)                                        \
struct name {                                                           \
        struct type *cqh_first;         /* first element */             \
        struct type *cqh_last;          /* last element */              \
}
 
#define CIRCLEQ_ENTRY(type)                                             \
struct {                                                                \
        struct type *cqe_next;          /* next element */              \
        struct type *cqe_prev;          /* previous element */          \
}
 
/*
 * Circular queue functions.
 */
#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
 
#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
 
#define CIRCLEQ_FOREACH(var, head, field)                               \
        for((var) = (head)->cqh_first;                                  \
            (var) != (void *)(head);                                    \
            (var) = (var)->field.cqe_next)
 
#define CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \
        for((var) = (head)->cqh_last;                                   \
            (var) != (void *)(head);                                    \
            (var) = (var)->field.cqe_prev)
 
#define CIRCLEQ_INIT(head) do {                                         \
        (head)->cqh_first = (void *)(head);                             \
        (head)->cqh_last = (void *)(head);                              \
} while (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 (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 (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 (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 (0)
 
#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_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 (0)
 
#ifdef _KERNEL
 
/*
 * XXX insque() and remque() are an old way of handling certain queues.
 * They bogusly assumes that all queue heads look alike.
 */
 
struct quehead {
        struct quehead *qh_link;
        struct quehead *qh_rlink;
};
 
#ifdef  __GNUC__
 
static __inline void
insque(void *a, void *b)
{
        struct quehead *element = a, *head = b;
 
        element->qh_link = head->qh_link;
        element->qh_rlink = head;
        head->qh_link = element;
        element->qh_link->qh_rlink = element;
}
 
static __inline void
remque(void *a)
{
        struct quehead *element = a;
 
        element->qh_link->qh_rlink = element->qh_rlink;
        element->qh_rlink->qh_link = element->qh_link;
        element->qh_rlink = 0;
}
 
#else /* !__GNUC__ */
 
void    insque __P((void *a, void *b));
void    remque __P((void *a));
 
#endif /* __GNUC__ */
 
#endif /* _KERNEL */
 
#endif /* !_SYS_QUEUE_H_ */

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [rtos/] [ecos-2.0/] [packages/] [net/] [bsd_tcpip/] [v2_0/] [include/] [sys/] [queue.h] - Blame information for rev 27

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