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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [rtos/] [ecos-3.0/] [packages/] [net/] [tcpip/] [current/] [include/] [sys/] [queue.h] - Blame information for rev 786

Details | Compare with Previous | View Log


//==========================================================================
//
//      include/sys/queue.h
//
//      
//
//==========================================================================
// ####BSDALTCOPYRIGHTBEGIN####                                             
// -------------------------------------------                              
// Portions of this software may have been derived from OpenBSD             
// or other sources, and if so are covered by the appropriate copyright     
// and license included herein.                                             
// -------------------------------------------                              
// ####BSDALTCOPYRIGHTEND####                                               
//==========================================================================
//#####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 openrisc

[/] [openrisc/] [trunk/] [rtos/] [ecos-3.0/] [packages/] [net/] [tcpip/] [current/] [include/] [sys/] [queue.h] - Blame information for rev 786

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