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

Subversion Repositories or1k

[/] [or1k/] [trunk/] [ecos-2.0/] [packages/] [net/] [tcpip/] [v2_0/] [include/] [sys/] [queue.h] - Blame information for rev 1254

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 or other sources,
// and are covered by the appropriate copyright disclaimers included herein.
//
// -------------------------------------------
//
//####BSDCOPYRIGHTEND####
//==========================================================================
//#####DESCRIPTIONBEGIN####
//
// Author(s):    gthomas
// Contributors: gthomas
// Date:         2000-01-10
// Purpose:      
// Description:  
//              
//
//####DESCRIPTIONEND####
//
//==========================================================================
 
 
/*      $OpenBSD: queue.h,v 1.14 1999/09/08 08:20:04 espie Exp $        */
/*      $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $       */
 
/*
 * 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
 */
 
#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 before or 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.
 */
 
/*
 * 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 access methods.
 */
#define SLIST_FIRST(head)       ((head)->slh_first)
#define SLIST_END(head)         NULL
#define SLIST_EMPTY(head)       (SLIST_FIRST(head) == SLIST_END(head))
#define SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
 
#define SLIST_FOREACH(var, head, field)                                 \
        for((var) = SLIST_FIRST(head);                                  \
            (var) != SLIST_END(head);                                   \
            (var) = SLIST_NEXT(var, field))
 
/*
 * Singly-linked List functions.
 */
#define SLIST_INIT(head) {                                              \
        SLIST_FIRST(head) = SLIST_END(head);                            \
}
 
#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_REMOVE_HEAD(head, field) do {                             \
        (head)->slh_first = (head)->slh_first->field.sle_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 access methods
 */
#define LIST_FIRST(head)                ((head)->lh_first)
#define LIST_END(head)                  NULL
#define LIST_EMPTY(head)                (LIST_FIRST(head) == LIST_END(head))
#define LIST_NEXT(elm, field)           ((elm)->field.le_next)
 
#define LIST_FOREACH(var, head, field)                                  \
        for((var) = LIST_FIRST(head);                                   \
            (var)!= LIST_END(head);                                     \
            (var) = LIST_NEXT(var, field))
 
/*
 * List functions.
 */
#define LIST_INIT(head) do {                                            \
        LIST_FIRST(head) = LIST_END(head);                              \
} 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_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)
 
#define LIST_REPLACE(elm, elm2, field) do {                             \
        if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)     \
                (elm2)->field.le_next->field.le_prev =                  \
                    &(elm2)->field.le_next;                             \
        (elm2)->field.le_prev = (elm)->field.le_prev;                   \
        *(elm2)->field.le_prev = (elm2);                                \
} while (0)
 
/*
 * 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 access methods.
 */
#define SIMPLEQ_FIRST(head)         ((head)->sqh_first)
#define SIMPLEQ_END(head)           NULL
#define SIMPLEQ_EMPTY(head)         (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
#define SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)
 
#define SIMPLEQ_FOREACH(var, head, field)                               \
        for((var) = SIMPLEQ_FIRST(head);                                \
            (var) != SIMPLEQ_END(head);                                 \
            (var) = SIMPLEQ_NEXT(var, field))
 
/*
 * Simple queue functions.
 */
#define SIMPLEQ_INIT(head) do {                                         \
        (head)->sqh_first = NULL;                                       \
        (head)->sqh_last = &(head)->sqh_first;                          \
} while (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 (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 (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 (0)
 
#define SIMPLEQ_REMOVE_HEAD(head, elm, field) do {                      \
        if (((head)->sqh_first = (elm)->field.sqe_next) == NULL)        \
                (head)->sqh_last = &(head)->sqh_first;                  \
} 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 access methods
 */
#define TAILQ_FIRST(head)               ((head)->tqh_first)
#define TAILQ_END(head)                 NULL
#define TAILQ_NEXT(elm, field)          ((elm)->field.tqe_next)
#define TAILQ_LAST(head, headname)                                      \
        (*(((struct headname *)((head)->tqh_last))->tqh_last))
/* XXX */
#define TAILQ_PREV(elm, headname, field)                                \
        (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
#define TAILQ_EMPTY(head)                                               \
        (TAILQ_FIRST(head) == TAILQ_END(head))
 
#define TAILQ_FOREACH(var, head, field)                                 \
        for((var) = TAILQ_FIRST(head);                                  \
            (var) != TAILQ_END(head);                                   \
            (var) = TAILQ_NEXT(var, field))
 
/*
 * Tail queue functions.
 */
#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)
 
#define TAILQ_REPLACE(head, elm, elm2, field) do {                      \
        if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)   \
                (elm2)->field.tqe_next->field.tqe_prev =                \
                    &(elm2)->field.le_next;                             \
        else                                                            \
                (head).tqh_last = &(elm2)->field.tqe_next;              \
        (elm2)->field.tqe_prev = (elm)->field.tqe_prev;                 \
        *(elm2)->field.tqe_prev = (elm2);                               \
} 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_HEAD_INITIALIZER(head)                                  \
        { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
 
#define CIRCLEQ_ENTRY(type)                                             \
struct {                                                                \
        struct type *cqe_next;          /* next element */              \
        struct type *cqe_prev;          /* previous element */          \
}
 
/*
 * Circular queue access methods
 */
#define CIRCLEQ_FIRST(head)             ((head)->cqh_first)
#define CIRCLEQ_LAST(head)              ((head)->cqh_last)
#define CIRCLEQ_END(head)               ((void *)(head))
#define CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)
#define CIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)
#define CIRCLEQ_EMPTY(head)                                             \
        (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
 
#define CIRCLEQ_FOREACH(var, head, field)                               \
        for((var) = CIRCLEQ_FIRST(head);                                \
            (var) != CIRCLEQ_END(head);                                 \
            (var) = CIRCLEQ_NEXT(var, field))
 
#define CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \
        for((var) = CIRCLEQ_LAST(head);                                 \
            (var) != CIRCLEQ_END(head);                                 \
            (var) = CIRCLEQ_PREV(var, field))
 
/*
 * Circular queue functions.
 */
#define CIRCLEQ_INIT(head) do {                                         \
        (head)->cqh_first = CIRCLEQ_END(head);                          \
        (head)->cqh_last = CIRCLEQ_END(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 == CIRCLEQ_END(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 == CIRCLEQ_END(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 = CIRCLEQ_END(head);                      \
        if ((head)->cqh_last == CIRCLEQ_END(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 = CIRCLEQ_END(head);                      \
        (elm)->field.cqe_prev = (head)->cqh_last;                       \
        if ((head)->cqh_first == CIRCLEQ_END(head))                     \
                (head)->cqh_first = (elm);                              \
        else                                                            \
                (head)->cqh_last->field.cqe_next = (elm);               \
        (head)->cqh_last = (elm);                                       \
} while (0)
 
#define CIRCLEQ_REMOVE(head, elm, field) do {                           \
        if ((elm)->field.cqe_next == CIRCLEQ_END(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 == CIRCLEQ_END(head))                 \
                (head)->cqh_first = (elm)->field.cqe_next;              \
        else                                                            \
                (elm)->field.cqe_prev->field.cqe_next =                 \
                    (elm)->field.cqe_next;                              \
} while (0)
 
#define CIRCLEQ_REPLACE(head, elm, elm2, field) do {                    \
        if (((elm2)->field.cqe_next = (elm)->field.cqe_next) ==         \
            CIRCLEQ_END(head))                                          \
                (head).cqh_last = (elm2);                               \
        else                                                            \
                (elm2)->field.cqe_next->field.cqe_prev = (elm2);        \
        if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) ==         \
            CIRCLEQ_END(head))                                          \
                (head).cqh_first = (elm2);                              \
        else                                                            \
                (elm2)->field.cqe_prev->field.cqe_next = (elm2);        \
} while (0)
 
#endif  /* !_SYS_QUEUE_H_ */

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [trunk/] [ecos-2.0/] [packages/] [net/] [tcpip/] [v2_0/] [include/] [sys/] [queue.h] - Blame information for rev 1254

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