[qemu.git] / sys-queue.h

/*      $NetBSD: queue.h,v 1.45.14.1 2007/07/18 20:13:24 liamjfoy Exp $ */\r
\r
/*\r
 * Qemu version: Copy from netbsd, removed debug code, removed some of\r
 * the implementations.  Left in lists, tail queues and circular queues.\r
 */\r
\r
/*\r
 * Copyright (c) 1991, 1993\r
 *      The Regents of the University of California.  All rights reserved.\r
 *\r
 * Redistribution and use in source and binary forms, with or without\r
 * modification, are permitted provided that the following conditions\r
 * are met:\r
 * 1. Redistributions of source code must retain the above copyright\r
 *    notice, this list of conditions and the following disclaimer.\r
 * 2. Redistributions in binary form must reproduce the above copyright\r
 *    notice, this list of conditions and the following disclaimer in the\r
 *    documentation and/or other materials provided with the distribution.\r
 * 3. Neither the name of the University nor the names of its contributors\r
 *    may be used to endorse or promote products derived from this software\r
 *    without specific prior written permission.\r
 *\r
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND\r
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE\r
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\r
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE\r
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL\r
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS\r
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)\r
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT\r
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY\r
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF\r
 * SUCH DAMAGE.\r
 *\r
 *      @(#)queue.h     8.5 (Berkeley) 8/20/94\r
 */\r
\r
#ifndef _SYS_QUEUE_H_\r
#define _SYS_QUEUE_H_\r
\r
/*\r
 * This file defines three types of data structures:\r
 * lists, tail queues, and circular queues.\r
 *\r
 * A list is headed by a single forward pointer (or an array of forward\r
 * pointers for a hash table header). The elements are doubly linked\r
 * so that an arbitrary element can be removed without a need to\r
 * traverse the list. New elements can be added to the list before\r
 * or after an existing element or at the head of the list. A list\r
 * may only be traversed in the forward direction.\r
 *\r
 * A tail queue is headed by a pair of pointers, one to the head of the\r
 * list and the other to the tail of the list. The elements are doubly\r
 * linked so that an arbitrary element can be removed without a need to\r
 * traverse the list. New elements can be added to the list before or\r
 * after an existing element, at the head of the list, or at the end of\r
 * the list. A tail queue may be traversed in either direction.\r
 *\r
 * A circle queue is headed by a pair of pointers, one to the head of the\r
 * list and the other to the tail of the list. The elements are doubly\r
 * linked so that an arbitrary element can be removed without a need to\r
 * traverse the list. New elements can be added to the list before or after\r
 * an existing element, at the head of the list, or at the end of the list.\r
 * A circle queue may be traversed in either direction, but has a more\r
 * complex end of list detection.\r
 *\r
 * For details on the use of these macros, see the queue(3) manual page.\r
 */\r
\r
/*\r
 * List definitions.\r
 */\r
#define LIST_HEAD(name, type)                                           \\r
struct name {                                                           \\r
        struct type *lh_first;  /* first element */                     \\r
}\r
\r
#define LIST_HEAD_INITIALIZER(head)                                     \\r
        { NULL }\r
\r
#define LIST_ENTRY(type)                                                \\r
struct {                                                                \\r
        struct type *le_next;   /* next element */                      \\r
        struct type **le_prev;  /* address of previous next element */  \\r
}\r
\r
/*\r
 * List functions.\r
 */\r
#define LIST_INIT(head) do {                                            \\r
        (head)->lh_first = NULL;                                        \\r
} while (/*CONSTCOND*/0)\r
\r
#define LIST_INSERT_AFTER(listelm, elm, field) do {                     \\r
        if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)  \\r
                (listelm)->field.le_next->field.le_prev =               \\r
                    &(elm)->field.le_next;                              \\r
        (listelm)->field.le_next = (elm);                               \\r
        (elm)->field.le_prev = &(listelm)->field.le_next;               \\r
} while (/*CONSTCOND*/0)\r
\r
#define LIST_INSERT_BEFORE(listelm, elm, field) do {                    \\r
        (elm)->field.le_prev = (listelm)->field.le_prev;                \\r
        (elm)->field.le_next = (listelm);                               \\r
        *(listelm)->field.le_prev = (elm);                              \\r
        (listelm)->field.le_prev = &(elm)->field.le_next;               \\r
} while (/*CONSTCOND*/0)\r
\r
#define LIST_INSERT_HEAD(head, elm, field) do {                         \\r
        if (((elm)->field.le_next = (head)->lh_first) != NULL)          \\r
                (head)->lh_first->field.le_prev = &(elm)->field.le_next;\\r
        (head)->lh_first = (elm);                                       \\r
        (elm)->field.le_prev = &(head)->lh_first;                       \\r
} while (/*CONSTCOND*/0)\r
\r
#define LIST_REMOVE(elm, field) do {                                    \\r
        if ((elm)->field.le_next != NULL)                               \\r
                (elm)->field.le_next->field.le_prev =                   \\r
                    (elm)->field.le_prev;                               \\r
        *(elm)->field.le_prev = (elm)->field.le_next;                   \\r
} while (/*CONSTCOND*/0)\r
\r
#define LIST_FOREACH(var, head, field)                                  \\r
        for ((var) = ((head)->lh_first);                                \\r
                (var);                                                  \\r
                (var) = ((var)->field.le_next))\r
\r
/*\r
 * List access methods.\r
 */\r
#define LIST_EMPTY(head)                ((head)->lh_first == NULL)\r
#define LIST_FIRST(head)                ((head)->lh_first)\r
#define LIST_NEXT(elm, field)           ((elm)->field.le_next)\r
\r
\r
/*\r
 * Tail queue definitions.\r
 */\r
#define _TAILQ_HEAD(name, type, qual)                                   \\r
struct name {                                                           \\r
        qual type *tqh_first;           /* first element */             \\r
        qual type *qual *tqh_last;      /* addr of last next element */ \\r
}\r
#define TAILQ_HEAD(name, type)  _TAILQ_HEAD(name, struct type,)\r
\r
#define TAILQ_HEAD_INITIALIZER(head)                                    \\r
        { NULL, &(head).tqh_first }\r
\r
#define _TAILQ_ENTRY(type, qual)                                        \\r
struct {                                                                \\r
        qual type *tqe_next;            /* next element */              \\r
        qual type *qual *tqe_prev;      /* address of previous next element */\\r
}\r
#define TAILQ_ENTRY(type)       _TAILQ_ENTRY(struct type,)\r
\r
/*\r
 * Tail queue functions.\r
 */\r
#define TAILQ_INIT(head) do {                                           \\r
        (head)->tqh_first = NULL;                                       \\r
        (head)->tqh_last = &(head)->tqh_first;                          \\r
} while (/*CONSTCOND*/0)\r
\r
#define TAILQ_INSERT_HEAD(head, elm, field) do {                        \\r
        if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \\r
                (head)->tqh_first->field.tqe_prev =                     \\r
                    &(elm)->field.tqe_next;                             \\r
        else                                                            \\r
                (head)->tqh_last = &(elm)->field.tqe_next;              \\r
        (head)->tqh_first = (elm);                                      \\r
        (elm)->field.tqe_prev = &(head)->tqh_first;                     \\r
} while (/*CONSTCOND*/0)\r
\r
#define TAILQ_INSERT_TAIL(head, elm, field) do {                        \\r
        (elm)->field.tqe_next = NULL;                                   \\r
        (elm)->field.tqe_prev = (head)->tqh_last;                       \\r
        *(head)->tqh_last = (elm);                                      \\r
        (head)->tqh_last = &(elm)->field.tqe_next;                      \\r
} while (/*CONSTCOND*/0)\r
\r
#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \\r
        if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\\r
                (elm)->field.tqe_next->field.tqe_prev =                 \\r
                    &(elm)->field.tqe_next;                             \\r
        else                                                            \\r
                (head)->tqh_last = &(elm)->field.tqe_next;              \\r
        (listelm)->field.tqe_next = (elm);                              \\r
        (elm)->field.tqe_prev = &(listelm)->field.tqe_next;             \\r
} while (/*CONSTCOND*/0)\r
\r
#define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \\r
        (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \\r
        (elm)->field.tqe_next = (listelm);                              \\r
        *(listelm)->field.tqe_prev = (elm);                             \\r
        (listelm)->field.tqe_prev = &(elm)->field.tqe_next;             \\r
} while (/*CONSTCOND*/0)\r
\r
#define TAILQ_REMOVE(head, elm, field) do {                             \\r
        if (((elm)->field.tqe_next) != NULL)                            \\r
                (elm)->field.tqe_next->field.tqe_prev =                 \\r
                    (elm)->field.tqe_prev;                              \\r
        else                                                            \\r
                (head)->tqh_last = (elm)->field.tqe_prev;               \\r
        *(elm)->field.tqe_prev = (elm)->field.tqe_next;                 \\r
} while (/*CONSTCOND*/0)\r
\r
#define TAILQ_FOREACH(var, head, field)                                 \\r
        for ((var) = ((head)->tqh_first);                               \\r
                (var);                                                  \\r
                (var) = ((var)->field.tqe_next))\r
\r
#define TAILQ_FOREACH_SAFE(var, head, field, next_var)                  \\r
        for ((var) = ((head)->tqh_first);                               \\r
                (var) && ((next_var) = ((var)->field.tqe_next), 1);     \\r
                (var) = (next_var))\r
\r
#define TAILQ_FOREACH_REVERSE(var, head, headname, field)               \\r
        for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));    \\r
                (var);                                                  \\r
                (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))\r
\r
/*\r
 * Tail queue access methods.\r
 */\r
#define TAILQ_EMPTY(head)               ((head)->tqh_first == NULL)\r
#define TAILQ_FIRST(head)               ((head)->tqh_first)\r
#define TAILQ_NEXT(elm, field)          ((elm)->field.tqe_next)\r
\r
#define TAILQ_LAST(head, headname) \\r
        (*(((struct headname *)((head)->tqh_last))->tqh_last))\r
#define TAILQ_PREV(elm, headname, field) \\r
        (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))\r
\r
\r
/*\r
 * Circular queue definitions.\r
 */\r
#define CIRCLEQ_HEAD(name, type)                                        \\r
struct name {                                                           \\r
        struct type *cqh_first;         /* first element */             \\r
        struct type *cqh_last;          /* last element */              \\r
}\r
\r
#define CIRCLEQ_HEAD_INITIALIZER(head)                                  \\r
        { (void *)&head, (void *)&head }\r
\r
#define CIRCLEQ_ENTRY(type)                                             \\r
struct {                                                                \\r
        struct type *cqe_next;          /* next element */              \\r
        struct type *cqe_prev;          /* previous element */          \\r
}\r
\r
/*\r
 * Circular queue functions.\r
 */\r
#define CIRCLEQ_INIT(head) do {                                         \\r
        (head)->cqh_first = (void *)(head);                             \\r
        (head)->cqh_last = (void *)(head);                              \\r
} while (/*CONSTCOND*/0)\r
\r
#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \\r
        (elm)->field.cqe_next = (listelm)->field.cqe_next;              \\r
        (elm)->field.cqe_prev = (listelm);                              \\r
        if ((listelm)->field.cqe_next == (void *)(head))                \\r
                (head)->cqh_last = (elm);                               \\r
        else                                                            \\r
                (listelm)->field.cqe_next->field.cqe_prev = (elm);      \\r
        (listelm)->field.cqe_next = (elm);                              \\r
} while (/*CONSTCOND*/0)\r
\r
#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {           \\r
        (elm)->field.cqe_next = (listelm);                              \\r
        (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \\r
        if ((listelm)->field.cqe_prev == (void *)(head))                \\r
                (head)->cqh_first = (elm);                              \\r
        else                                                            \\r
                (listelm)->field.cqe_prev->field.cqe_next = (elm);      \\r
        (listelm)->field.cqe_prev = (elm);                              \\r
} while (/*CONSTCOND*/0)\r
\r
#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {                      \\r
        (elm)->field.cqe_next = (head)->cqh_first;                      \\r
        (elm)->field.cqe_prev = (void *)(head);                         \\r
        if ((head)->cqh_last == (void *)(head))                         \\r
                (head)->cqh_last = (elm);                               \\r
        else                                                            \\r
                (head)->cqh_first->field.cqe_prev = (elm);              \\r
        (head)->cqh_first = (elm);                                      \\r
} while (/*CONSTCOND*/0)\r
\r
#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {                      \\r
        (elm)->field.cqe_next = (void *)(head);                         \\r
        (elm)->field.cqe_prev = (head)->cqh_last;                       \\r
        if ((head)->cqh_first == (void *)(head))                        \\r
                (head)->cqh_first = (elm);                              \\r
        else                                                            \\r
                (head)->cqh_last->field.cqe_next = (elm);               \\r
        (head)->cqh_last = (elm);                                       \\r
} while (/*CONSTCOND*/0)\r
\r
#define CIRCLEQ_REMOVE(head, elm, field) do {                           \\r
        if ((elm)->field.cqe_next == (void *)(head))                    \\r
                (head)->cqh_last = (elm)->field.cqe_prev;               \\r
        else                                                            \\r
                (elm)->field.cqe_next->field.cqe_prev =                 \\r
                    (elm)->field.cqe_prev;                              \\r
        if ((elm)->field.cqe_prev == (void *)(head))                    \\r
                (head)->cqh_first = (elm)->field.cqe_next;              \\r
        else                                                            \\r
                (elm)->field.cqe_prev->field.cqe_next =                 \\r
                    (elm)->field.cqe_next;                              \\r
} while (/*CONSTCOND*/0)\r
\r
#define CIRCLEQ_FOREACH(var, head, field)                               \\r
        for ((var) = ((head)->cqh_first);                               \\r
                (var) != (const void *)(head);                          \\r
                (var) = ((var)->field.cqe_next))\r
\r
#define CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \\r
        for ((var) = ((head)->cqh_last);                                \\r
                (var) != (const void *)(head);                          \\r
                (var) = ((var)->field.cqe_prev))\r
\r
/*\r
 * Circular queue access methods.\r
 */\r
#define CIRCLEQ_EMPTY(head)             ((head)->cqh_first == (void *)(head))\r
#define CIRCLEQ_FIRST(head)             ((head)->cqh_first)\r
#define CIRCLEQ_LAST(head)              ((head)->cqh_last)\r
#define CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)\r
#define CIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)\r
\r
#define CIRCLEQ_LOOP_NEXT(head, elm, field)                             \\r
        (((elm)->field.cqe_next == (void *)(head))                      \\r
            ? ((head)->cqh_first)                                       \\r
            : (elm->field.cqe_next))\r
#define CIRCLEQ_LOOP_PREV(head, elm, field)                             \\r
        (((elm)->field.cqe_prev == (void *)(head))                      \\r
            ? ((head)->cqh_last)                                        \\r
            : (elm->field.cqe_prev))\r
\r
#endif  /* !_SYS_QUEUE_H_ */\r
Commit	Line	Data
23cde8bb AL	1	/* $NetBSD: queue.h,v 1.45.14.1 2007/07/18 20:13:24 liamjfoy Exp $ */\r
	2	\r
	3	/*\r
	4	* Qemu version: Copy from netbsd, removed debug code, removed some of\r
	5	* the implementations. Left in lists, tail queues and circular queues.\r
	6	*/\r
	7	\r
	8	/*\r
	9	* Copyright (c) 1991, 1993\r
	10	* The Regents of the University of California. All rights reserved.\r
	11	*\r
	12	* Redistribution and use in source and binary forms, with or without\r
	13	* modification, are permitted provided that the following conditions\r
	14	* are met:\r
	15	* 1. Redistributions of source code must retain the above copyright\r
	16	* notice, this list of conditions and the following disclaimer.\r
	17	* 2. Redistributions in binary form must reproduce the above copyright\r
	18	* notice, this list of conditions and the following disclaimer in the\r
	19	* documentation and/or other materials provided with the distribution.\r
	20	* 3. Neither the name of the University nor the names of its contributors\r
	21	* may be used to endorse or promote products derived from this software\r
	22	* without specific prior written permission.\r
	23	*\r
	24	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND\r
	25	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE\r
	26	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\r
	27	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE\r
	28	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL\r
	29	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS\r
	30	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)\r
	31	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT\r
	32	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY\r
	33	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF\r
	34	* SUCH DAMAGE.\r
	35	*\r
	36	* @(#)queue.h 8.5 (Berkeley) 8/20/94\r
	37	*/\r
	38	\r
	39	#ifndef _SYS_QUEUE_H_\r
	40	#define _SYS_QUEUE_H_\r
	41	\r
	42	/*\r
	43	* This file defines three types of data structures:\r
	44	* lists, tail queues, and circular queues.\r
	45	*\r
	46	* A list is headed by a single forward pointer (or an array of forward\r
	47	* pointers for a hash table header). The elements are doubly linked\r
	48	* so that an arbitrary element can be removed without a need to\r
	49	* traverse the list. New elements can be added to the list before\r
	50	* or after an existing element or at the head of the list. A list\r
	51	* may only be traversed in the forward direction.\r
	52	*\r
	53	* A tail queue is headed by a pair of pointers, one to the head of the\r
	54	* list and the other to the tail of the list. The elements are doubly\r
	55	* linked so that an arbitrary element can be removed without a need to\r
	56	* traverse the list. New elements can be added to the list before or\r
	57	* after an existing element, at the head of the list, or at the end of\r
	58	* the list. A tail queue may be traversed in either direction.\r
	59	*\r
	60	* A circle queue is headed by a pair of pointers, one to the head of the\r
	61	* list and the other to the tail of the list. The elements are doubly\r
	62	* linked so that an arbitrary element can be removed without a need to\r
	63	* traverse the list. New elements can be added to the list before or after\r
	64	* an existing element, at the head of the list, or at the end of the list.\r
65	* A circle queue may be traversed in either direction, but has a more\r
66	* complex end of list detection.\r
67	*\r
68	* For details on the use of these macros, see the queue(3) manual page.\r
69	*/\r
70	\r
71	/*\r
72	* List definitions.\r
73	*/\r
74	#define LIST_HEAD(name, type) \\r
75	struct name { \\r
76	struct type lh_first; / first element */ \\r
77	}\r
78	\r
79	#define LIST_HEAD_INITIALIZER(head) \\r
80	{ NULL }\r
81	\r
82	#define LIST_ENTRY(type) \\r
83	struct { \\r
84	struct type le_next; / next element */ \\r
85	struct type *le_prev; / address of previous next element */ \\r
86	}\r
87	\r
88	/*\r
89	* List functions.\r
90	*/\r
91	#define LIST_INIT(head) do { \\r
92	(head)->lh_first = NULL; \\r
93	} while (/CONSTCOND/0)\r
94	\r
95	#define LIST_INSERT_AFTER(listelm, elm, field) do { \\r
96	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \\r
97	(listelm)->field.le_next->field.le_prev = \\r
98	&(elm)->field.le_next; \\r
99	(listelm)->field.le_next = (elm); \\r
100	(elm)->field.le_prev = &(listelm)->field.le_next; \\r
101	} while (/CONSTCOND/0)\r
102	\r
103	#define LIST_INSERT_BEFORE(listelm, elm, field) do { \\r
104	(elm)->field.le_prev = (listelm)->field.le_prev; \\r
105	(elm)->field.le_next = (listelm); \\r
106	*(listelm)->field.le_prev = (elm); \\r
107	(listelm)->field.le_prev = &(elm)->field.le_next; \\r
108	} while (/CONSTCOND/0)\r
109	\r
110	#define LIST_INSERT_HEAD(head, elm, field) do { \\r
111	if (((elm)->field.le_next = (head)->lh_first) != NULL) \\r
112	(head)->lh_first->field.le_prev = &(elm)->field.le_next;\\r
113	(head)->lh_first = (elm); \\r
114	(elm)->field.le_prev = &(head)->lh_first; \\r
115	} while (/CONSTCOND/0)\r
116	\r
117	#define LIST_REMOVE(elm, field) do { \\r
118	if ((elm)->field.le_next != NULL) \\r
119	(elm)->field.le_next->field.le_prev = \\r
120	(elm)->field.le_prev; \\r
121	*(elm)->field.le_prev = (elm)->field.le_next; \\r
122	} while (/CONSTCOND/0)\r
123	\r
124	#define LIST_FOREACH(var, head, field) \\r
125	for ((var) = ((head)->lh_first); \\r
126	(var); \\r
127	(var) = ((var)->field.le_next))\r
128	\r
129	/*\r
130	* List access methods.\r
131	*/\r
132	#define LIST_EMPTY(head) ((head)->lh_first == NULL)\r
133	#define LIST_FIRST(head) ((head)->lh_first)\r
134	#define LIST_NEXT(elm, field) ((elm)->field.le_next)\r
135	\r
136	\r
137	/*\r
138	* Tail queue definitions.\r
139	*/\r
140	#define _TAILQ_HEAD(name, type, qual) \\r
141	struct name { \\r
142	qual type tqh_first; / first element */ \\r
143	qual type qual tqh_last; /* addr of last next element */ \\r
144	}\r
145	#define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,)\r
146	\r
147	#define TAILQ_HEAD_INITIALIZER(head) \\r
148	{ NULL, &(head).tqh_first }\r
149	\r
150	#define _TAILQ_ENTRY(type, qual) \\r
151	struct { \\r
152	qual type tqe_next; / next element */ \\r
153	qual type qual tqe_prev; /* address of previous next element */\\r
154	}\r
155	#define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,)\r
156	\r
157	/*\r
158	* Tail queue functions.\r
159	*/\r
160	#define TAILQ_INIT(head) do { \\r
161	(head)->tqh_first = NULL; \\r
162	(head)->tqh_last = &(head)->tqh_first; \\r
163	} while (/CONSTCOND/0)\r
164	\r
165	#define TAILQ_INSERT_HEAD(head, elm, field) do { \\r
166	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \\r
167	(head)->tqh_first->field.tqe_prev = \\r
168	&(elm)->field.tqe_next; \\r
169	else \\r
170	(head)->tqh_last = &(elm)->field.tqe_next; \\r
171	(head)->tqh_first = (elm); \\r
172	(elm)->field.tqe_prev = &(head)->tqh_first; \\r
173	} while (/CONSTCOND/0)\r
174	\r
175	#define TAILQ_INSERT_TAIL(head, elm, field) do { \\r
176	(elm)->field.tqe_next = NULL; \\r
177	(elm)->field.tqe_prev = (head)->tqh_last; \\r
178	*(head)->tqh_last = (elm); \\r
179	(head)->tqh_last = &(elm)->field.tqe_next; \\r
180	} while (/CONSTCOND/0)\r
181	\r
182	#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \\r
183	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\\r
184	(elm)->field.tqe_next->field.tqe_prev = \\r
185	&(elm)->field.tqe_next; \\r
186	else \\r
187	(head)->tqh_last = &(elm)->field.tqe_next; \\r
188	(listelm)->field.tqe_next = (elm); \\r
189	(elm)->field.tqe_prev = &(listelm)->field.tqe_next; \\r
190	} while (/CONSTCOND/0)\r
191	\r
192	#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \\r
193	(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \\r
194	(elm)->field.tqe_next = (listelm); \\r
195	*(listelm)->field.tqe_prev = (elm); \\r
196	(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \\r
197	} while (/CONSTCOND/0)\r
198	\r
199	#define TAILQ_REMOVE(head, elm, field) do { \\r
200	if (((elm)->field.tqe_next) != NULL) \\r
201	(elm)->field.tqe_next->field.tqe_prev = \\r
202	(elm)->field.tqe_prev; \\r
203	else \\r
204	(head)->tqh_last = (elm)->field.tqe_prev; \\r
205	*(elm)->field.tqe_prev = (elm)->field.tqe_next; \\r
206	} while (/CONSTCOND/0)\r
207	\r
208	#define TAILQ_FOREACH(var, head, field) \\r
209	for ((var) = ((head)->tqh_first); \\r
210	(var); \\r
211	(var) = ((var)->field.tqe_next))\r
212	\r
31280d92 AL	213	#define TAILQ_FOREACH_SAFE(var, head, field, next_var) \\r
	214	for ((var) = ((head)->tqh_first); \\r
	215	(var) && ((next_var) = ((var)->field.tqe_next), 1); \\r
	216	(var) = (next_var))\r
	217	\r
23cde8bb AL	218	#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \\r
	219	for ((var) = ((((struct headname )((head)->tqh_last))->tqh_last)); \\r
	220	(var); \\r
	221	(var) = ((((struct headname )((var)->field.tqe_prev))->tqh_last)))\r
	222	\r
	223	/*\r
	224	* Tail queue access methods.\r
	225	*/\r
	226	#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)\r
	227	#define TAILQ_FIRST(head) ((head)->tqh_first)\r
	228	#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)\r
	229	\r
	230	#define TAILQ_LAST(head, headname) \\r
	231	((((struct headname )((head)->tqh_last))->tqh_last))\r
	232	#define TAILQ_PREV(elm, headname, field) \\r
	233	((((struct headname )((elm)->field.tqe_prev))->tqh_last))\r
	234	\r
	235	\r
	236	/*\r
	237	* Circular queue definitions.\r
	238	*/\r
	239	#define CIRCLEQ_HEAD(name, type) \\r
	240	struct name { \\r
	241	struct type cqh_first; / first element */ \\r
	242	struct type cqh_last; / last element */ \\r
	243	}\r
	244	\r
	245	#define CIRCLEQ_HEAD_INITIALIZER(head) \\r
	246	{ (void )&head, (void )&head }\r
	247	\r
	248	#define CIRCLEQ_ENTRY(type) \\r
	249	struct { \\r
	250	struct type cqe_next; / next element */ \\r
	251	struct type cqe_prev; / previous element */ \\r
	252	}\r
	253	\r
	254	/*\r
	255	* Circular queue functions.\r
	256	*/\r
	257	#define CIRCLEQ_INIT(head) do { \\r
	258	(head)->cqh_first = (void *)(head); \\r
	259	(head)->cqh_last = (void *)(head); \\r
	260	} while (/CONSTCOND/0)\r
	261	\r
	262	#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \\r
	263	(elm)->field.cqe_next = (listelm)->field.cqe_next; \\r
	264	(elm)->field.cqe_prev = (listelm); \\r
	265	if ((listelm)->field.cqe_next == (void *)(head)) \\r
	266	(head)->cqh_last = (elm); \\r
	267	else \\r
	268	(listelm)->field.cqe_next->field.cqe_prev = (elm); \\r
	269	(listelm)->field.cqe_next = (elm); \\r
	270	} while (/CONSTCOND/0)\r
	271	\r
	272	#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \\r
	273	(elm)->field.cqe_next = (listelm); \\r
	274	(elm)->field.cqe_prev = (listelm)->field.cqe_prev; \\r
	275	if ((listelm)->field.cqe_prev == (void *)(head)) \\r
	276	(head)->cqh_first = (elm); \\r
	277	else \\r
	278	(listelm)->field.cqe_prev->field.cqe_next = (elm); \\r
	279	(listelm)->field.cqe_prev = (elm); \\r
	280	} while (/CONSTCOND/0)\r
	281	\r
282	#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \\r
283	(elm)->field.cqe_next = (head)->cqh_first; \\r
284	(elm)->field.cqe_prev = (void *)(head); \\r
285	if ((head)->cqh_last == (void *)(head)) \\r
286	(head)->cqh_last = (elm); \\r
287	else \\r
288	(head)->cqh_first->field.cqe_prev = (elm); \\r
289	(head)->cqh_first = (elm); \\r
290	} while (/CONSTCOND/0)\r
291	\r
292	#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \\r
293	(elm)->field.cqe_next = (void *)(head); \\r
294	(elm)->field.cqe_prev = (head)->cqh_last; \\r
295	if ((head)->cqh_first == (void *)(head)) \\r
296	(head)->cqh_first = (elm); \\r
297	else \\r
298	(head)->cqh_last->field.cqe_next = (elm); \\r
299	(head)->cqh_last = (elm); \\r
300	} while (/CONSTCOND/0)\r
301	\r
302	#define CIRCLEQ_REMOVE(head, elm, field) do { \\r
303	if ((elm)->field.cqe_next == (void *)(head)) \\r
304	(head)->cqh_last = (elm)->field.cqe_prev; \\r
305	else \\r
306	(elm)->field.cqe_next->field.cqe_prev = \\r
307	(elm)->field.cqe_prev; \\r
308	if ((elm)->field.cqe_prev == (void *)(head)) \\r
309	(head)->cqh_first = (elm)->field.cqe_next; \\r
310	else \\r
311	(elm)->field.cqe_prev->field.cqe_next = \\r
312	(elm)->field.cqe_next; \\r
313	} while (/CONSTCOND/0)\r
314	\r
315	#define CIRCLEQ_FOREACH(var, head, field) \\r
316	for ((var) = ((head)->cqh_first); \\r
317	(var) != (const void *)(head); \\r
318	(var) = ((var)->field.cqe_next))\r
319	\r
320	#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \\r
321	for ((var) = ((head)->cqh_last); \\r
322	(var) != (const void *)(head); \\r
323	(var) = ((var)->field.cqe_prev))\r
324	\r
325	/*\r
326	* Circular queue access methods.\r
327	*/\r
328	#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))\r
329	#define CIRCLEQ_FIRST(head) ((head)->cqh_first)\r
330	#define CIRCLEQ_LAST(head) ((head)->cqh_last)\r
331	#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)\r
332	#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)\r
333	\r
334	#define CIRCLEQ_LOOP_NEXT(head, elm, field) \\r
335	(((elm)->field.cqe_next == (void *)(head)) \\r
336	? ((head)->cqh_first) \\r
337	: (elm->field.cqe_next))\r
338	#define CIRCLEQ_LOOP_PREV(head, elm, field) \\r
339	(((elm)->field.cqe_prev == (void *)(head)) \\r
340	? ((head)->cqh_last) \\r
341	: (elm->field.cqe_prev))\r
342	\r
343	#endif /* !_SYS_QUEUE_H_ */\r