xref: /illumos-gate/usr/src/uts/common/sys/queue.h (revision 85280f08)
1381a2a9aSdr146992 /*
2381a2a9aSdr146992  * Copyright (c) 1991, 1993
3381a2a9aSdr146992  *	The Regents of the University of California.  All rights reserved.
4381a2a9aSdr146992  *
5381a2a9aSdr146992  * Redistribution and use in source and binary forms, with or without
6381a2a9aSdr146992  * modification, are permitted provided that the following conditions
7381a2a9aSdr146992  * are met:
8381a2a9aSdr146992  * 1. Redistributions of source code must retain the above copyright
9381a2a9aSdr146992  *    notice, this list of conditions and the following disclaimer.
10381a2a9aSdr146992  * 2. Redistributions in binary form must reproduce the above copyright
11381a2a9aSdr146992  *    notice, this list of conditions and the following disclaimer in the
12381a2a9aSdr146992  *    documentation and/or other materials provided with the distribution.
13381a2a9aSdr146992  * 3. Neither the name of the University nor the names of its contributors
14381a2a9aSdr146992  *    may be used to endorse or promote products derived from this software
15381a2a9aSdr146992  *    without specific prior written permission.
16381a2a9aSdr146992  *
17381a2a9aSdr146992  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18381a2a9aSdr146992  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19381a2a9aSdr146992  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20381a2a9aSdr146992  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21381a2a9aSdr146992  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22381a2a9aSdr146992  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23381a2a9aSdr146992  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24381a2a9aSdr146992  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25381a2a9aSdr146992  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26381a2a9aSdr146992  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27381a2a9aSdr146992  * SUCH DAMAGE.
28381a2a9aSdr146992  *
29381a2a9aSdr146992  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
30381a2a9aSdr146992  */
31381a2a9aSdr146992 /*
32c1374a13SSurya Prakki  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
33381a2a9aSdr146992  * Use is subject to license terms.
34381a2a9aSdr146992  */
35381a2a9aSdr146992 
36381a2a9aSdr146992 #ifndef	_SYS_QUEUE_H
37381a2a9aSdr146992 #define	_SYS_QUEUE_H
38381a2a9aSdr146992 
39381a2a9aSdr146992 #include <sys/note.h>
40*85280f08SToomas Soome #include <sys/containerof.h>
41381a2a9aSdr146992 
42381a2a9aSdr146992 #ifdef __cplusplus
43381a2a9aSdr146992 extern "C" {
44381a2a9aSdr146992 #endif
45381a2a9aSdr146992 
46381a2a9aSdr146992 /*
47381a2a9aSdr146992  * This file defines five types of data structures: singly-linked lists,
48381a2a9aSdr146992  * lists, simple queues, tail queues, and circular queues.
49381a2a9aSdr146992  *
50381a2a9aSdr146992  * A singly-linked list is headed by a single forward pointer. The
51381a2a9aSdr146992  * elements are singly linked for minimum space and pointer manipulation
52381a2a9aSdr146992  * overhead at the expense of O(n) removal for arbitrary elements. New
53381a2a9aSdr146992  * elements can be added to the list after an existing element or at the
54381a2a9aSdr146992  * head of the list.  Elements being removed from the head of the list
55381a2a9aSdr146992  * should use the explicit macro for this purpose for optimum
56381a2a9aSdr146992  * efficiency. A singly-linked list may only be traversed in the forward
57381a2a9aSdr146992  * direction.  Singly-linked lists are ideal for applications with large
58381a2a9aSdr146992  * datasets and few or no removals or for implementing a LIFO queue.
59381a2a9aSdr146992  *
60381a2a9aSdr146992  * A list is headed by a single forward pointer (or an array of forward
61381a2a9aSdr146992  * pointers for a hash table header). The elements are doubly linked
62381a2a9aSdr146992  * so that an arbitrary element can be removed without a need to
63381a2a9aSdr146992  * traverse the list. New elements can be added to the list before
64381a2a9aSdr146992  * or after an existing element or at the head of the list. A list
65381a2a9aSdr146992  * may only be traversed in the forward direction.
66381a2a9aSdr146992  *
67381a2a9aSdr146992  * A simple queue is headed by a pair of pointers, one the head of the
68381a2a9aSdr146992  * list and the other to the tail of the list. The elements are singly
69381a2a9aSdr146992  * linked to save space, so elements can only be removed from the
70381a2a9aSdr146992  * head of the list. New elements can be added to the list after
71381a2a9aSdr146992  * an existing element, at the head of the list, or at the end of the
72381a2a9aSdr146992  * list. A simple queue may only be traversed in the forward direction.
73381a2a9aSdr146992  *
74381a2a9aSdr146992  * A tail queue is headed by a pair of pointers, one to the head of the
75381a2a9aSdr146992  * list and the other to the tail of the list. The elements are doubly
76381a2a9aSdr146992  * linked so that an arbitrary element can be removed without a need to
77381a2a9aSdr146992  * traverse the list. New elements can be added to the list before or
78381a2a9aSdr146992  * after an existing element, at the head of the list, or at the end of
79381a2a9aSdr146992  * the list. A tail queue may be traversed in either direction.
80381a2a9aSdr146992  *
81381a2a9aSdr146992  * A circle queue is headed by a pair of pointers, one to the head of the
82381a2a9aSdr146992  * list and the other to the tail of the list. The elements are doubly
83381a2a9aSdr146992  * linked so that an arbitrary element can be removed without a need to
84381a2a9aSdr146992  * traverse the list. New elements can be added to the list before or after
85381a2a9aSdr146992  * an existing element, at the head of the list, or at the end of the list.
86381a2a9aSdr146992  * A circle queue may be traversed in either direction, but has a more
87381a2a9aSdr146992  * complex end of list detection.
88381a2a9aSdr146992  *
89*85280f08SToomas Soome  * For details on the use of these macros, see the queue.h(3HEAD) manual page.
90381a2a9aSdr146992  */
91381a2a9aSdr146992 
92*85280f08SToomas Soome #ifdef QUEUE_MACRO_DEBUG
93*85280f08SToomas Soome #warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH
94*85280f08SToomas Soome #define	QUEUE_MACRO_DEBUG_TRACE
95*85280f08SToomas Soome #define	QUEUE_MACRO_DEBUG_TRASH
96*85280f08SToomas Soome #endif
97*85280f08SToomas Soome 
98*85280f08SToomas Soome #ifdef QUEUE_MACRO_DEBUG_TRACE
99*85280f08SToomas Soome /* Store the last 2 places the queue element or head was altered */
100*85280f08SToomas Soome struct qm_trace {
101*85280f08SToomas Soome 	unsigned long	lastline;
102*85280f08SToomas Soome 	unsigned long	prevline;
103*85280f08SToomas Soome 	const char	*lastfile;
104*85280f08SToomas Soome 	const char	*prevfile;
105*85280f08SToomas Soome };
106*85280f08SToomas Soome 
107*85280f08SToomas Soome #define	TRACEBUF	struct qm_trace trace;
108*85280f08SToomas Soome #define	TRACEBUF_INITIALIZER	{ __LINE__, 0, __FILE__, NULL },
109*85280f08SToomas Soome 
110*85280f08SToomas Soome #define	QMD_TRACE_HEAD(head) do {					\
111*85280f08SToomas Soome 	(head)->trace.prevline = (head)->trace.lastline;		\
112*85280f08SToomas Soome 	(head)->trace.prevfile = (head)->trace.lastfile;		\
113*85280f08SToomas Soome 	(head)->trace.lastline = __LINE__;				\
114*85280f08SToomas Soome 	(head)->trace.lastfile = __FILE__;				\
115*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
116*85280f08SToomas Soome } while (0)
117*85280f08SToomas Soome 
118*85280f08SToomas Soome #define	QMD_TRACE_ELEM(elem) do {					\
119*85280f08SToomas Soome 	(elem)->trace.prevline = (elem)->trace.lastline;		\
120*85280f08SToomas Soome 	(elem)->trace.prevfile = (elem)->trace.lastfile;		\
121*85280f08SToomas Soome 	(elem)->trace.lastline = __LINE__;				\
122*85280f08SToomas Soome 	(elem)->trace.lastfile = __FILE__;				\
123*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
124*85280f08SToomas Soome } while (0)
125*85280f08SToomas Soome 
126*85280f08SToomas Soome #else	/* !QUEUE_MACRO_DEBUG_TRACE */
127*85280f08SToomas Soome #define	QMD_TRACE_ELEM(elem)
128*85280f08SToomas Soome #define	QMD_TRACE_HEAD(head)
129*85280f08SToomas Soome #define	TRACEBUF
130*85280f08SToomas Soome #define	TRACEBUF_INITIALIZER
131*85280f08SToomas Soome #endif	/* QUEUE_MACRO_DEBUG_TRACE */
132*85280f08SToomas Soome 
133*85280f08SToomas Soome #ifdef QUEUE_MACRO_DEBUG_TRASH
134*85280f08SToomas Soome #define	TRASHIT(x)		do {(x) = (void *)-1; } while (0)
135*85280f08SToomas Soome #define	QMD_IS_TRASHED(x)	((x) == (void *)(intptr_t)-1)
136*85280f08SToomas Soome #else	/* !QUEUE_MACRO_DEBUG_TRASH */
137*85280f08SToomas Soome #define	TRASHIT(x)
138*85280f08SToomas Soome #define	QMD_IS_TRASHED(x)	0
139*85280f08SToomas Soome #endif	/* QUEUE_MACRO_DEBUG_TRASH */
140*85280f08SToomas Soome 
141*85280f08SToomas Soome #if defined(QUEUE_MACRO_DEBUG_TRACE) || defined(QUEUE_MACRO_DEBUG_TRASH)
142*85280f08SToomas Soome #define	QMD_SAVELINK(name, link)	void **name = (void *)&(link)
143*85280f08SToomas Soome #else	/* !QUEUE_MACRO_DEBUG_TRACE && !QUEUE_MACRO_DEBUG_TRASH */
144*85280f08SToomas Soome #define	QMD_SAVELINK(name, link)
145*85280f08SToomas Soome #endif	/* QUEUE_MACRO_DEBUG_TRACE || QUEUE_MACRO_DEBUG_TRASH */
146*85280f08SToomas Soome 
147*85280f08SToomas Soome #ifdef __cplusplus
148*85280f08SToomas Soome /*
149*85280f08SToomas Soome  * In C++ there can be structure lists and class lists:
150*85280f08SToomas Soome  */
151*85280f08SToomas Soome #define	QUEUE_TYPEOF(type) type
152*85280f08SToomas Soome #else
153*85280f08SToomas Soome #define	QUEUE_TYPEOF(type) struct type
154*85280f08SToomas Soome #endif
155*85280f08SToomas Soome 
156*85280f08SToomas Soome /*
157*85280f08SToomas Soome  * Singly-linked List definitions.
158*85280f08SToomas Soome  */
159*85280f08SToomas Soome #define	SLIST_HEAD(name, type)						\
160*85280f08SToomas Soome struct name {								\
161*85280f08SToomas Soome 	struct type *slh_first;	/* first element */			\
162*85280f08SToomas Soome }
163*85280f08SToomas Soome 
164*85280f08SToomas Soome #define	SLIST_CLASS_HEAD(name, type)					\
165*85280f08SToomas Soome struct name {								\
166*85280f08SToomas Soome 	class type *slh_first;	/* first element */			\
167*85280f08SToomas Soome }
168*85280f08SToomas Soome 
169*85280f08SToomas Soome #define	SLIST_HEAD_INITIALIZER(head)					\
170*85280f08SToomas Soome 	{ NULL }
171*85280f08SToomas Soome 
172*85280f08SToomas Soome #define	SLIST_ENTRY(type)						\
173*85280f08SToomas Soome struct {								\
174*85280f08SToomas Soome 	struct type *sle_next;	/* next element */			\
175*85280f08SToomas Soome }
176*85280f08SToomas Soome 
177*85280f08SToomas Soome #define	SLIST_CLASS_ENTRY(type)						\
178*85280f08SToomas Soome struct {								\
179*85280f08SToomas Soome 	class type *sle_next;		/* next element */		\
180*85280f08SToomas Soome }
181*85280f08SToomas Soome 
182*85280f08SToomas Soome /*
183*85280f08SToomas Soome  * Singly-linked List access methods.
184*85280f08SToomas Soome  */
185*85280f08SToomas Soome #define	SLIST_FIRST(head)	((head)->slh_first)
186*85280f08SToomas Soome #define	SLIST_END(head)		NULL
187*85280f08SToomas Soome #define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
188*85280f08SToomas Soome #define	SLIST_EMPTY(head)	((head)->slh_first == SLIST_END(head))
189*85280f08SToomas Soome 
190*85280f08SToomas Soome #define	SLIST_FOREACH(var, head, field)					\
191*85280f08SToomas Soome 	for ((var) = SLIST_FIRST((head));				\
192*85280f08SToomas Soome 		(var) != SLIST_END(head);				\
193*85280f08SToomas Soome 		(var) = SLIST_NEXT((var), field))
194*85280f08SToomas Soome 
195*85280f08SToomas Soome #define	SLIST_FOREACH_FROM(var, head, field)				\
196*85280f08SToomas Soome 	for ((var) = ((var) != SLIST_END(head) ? (var) : SLIST_FIRST((head))); \
197*85280f08SToomas Soome 		(var) != SLIST_END(head);				\
198*85280f08SToomas Soome 		(var) = SLIST_NEXT((var), field))
199*85280f08SToomas Soome 
200*85280f08SToomas Soome #define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
201*85280f08SToomas Soome 	for ((var) = SLIST_FIRST((head));				\
202*85280f08SToomas Soome 		(var) != SLIST_END(head) &&				\
203*85280f08SToomas Soome 		((tvar) = SLIST_NEXT((var), field), 1);			\
204*85280f08SToomas Soome 		(var) = (tvar))
205*85280f08SToomas Soome 
206*85280f08SToomas Soome #define	SLIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
207*85280f08SToomas Soome 	for ((var) = ((var) != SLIST_END(head) ? (var) : SLIST_FIRST((head))); \
208*85280f08SToomas Soome 		(var) != SLIST_END(head) &&				\
209*85280f08SToomas Soome 		((tvar) = SLIST_NEXT((var), field), 1);			\
210*85280f08SToomas Soome 		(var) = (tvar))
211*85280f08SToomas Soome 
212*85280f08SToomas Soome /*
213*85280f08SToomas Soome  * Singly-linked List functions.
214*85280f08SToomas Soome  */
215*85280f08SToomas Soome #define	SLIST_INIT(head) do {						\
216*85280f08SToomas Soome 	(head)->slh_first = SLIST_END(head);				\
217*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
218*85280f08SToomas Soome } while (0)
219*85280f08SToomas Soome 
220*85280f08SToomas Soome #define	SLIST_CONCAT(head1, head2, type, field) do {			\
221*85280f08SToomas Soome 	QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1);		\
222*85280f08SToomas Soome 	if (curelm == SLIST_END(head1)) {				\
223*85280f08SToomas Soome 		if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) !=	\
224*85280f08SToomas Soome 		    SLIST_END(head1))					\
225*85280f08SToomas Soome 			SLIST_INIT(head2);				\
226*85280f08SToomas Soome 	} else if (SLIST_FIRST(head2) != SLIST_END(head2)) {		\
227*85280f08SToomas Soome 		while (SLIST_NEXT(curelm, field) != SLIST_END(head1))	\
228*85280f08SToomas Soome 			curelm = SLIST_NEXT(curelm, field);		\
229*85280f08SToomas Soome 		SLIST_NEXT(curelm, field) = SLIST_FIRST(head2);		\
230*85280f08SToomas Soome 		SLIST_INIT(head2);					\
231*85280f08SToomas Soome 	}								\
232*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
233*85280f08SToomas Soome } while (0)
234*85280f08SToomas Soome 
235*85280f08SToomas Soome #define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
236*85280f08SToomas Soome 	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);	\
237*85280f08SToomas Soome 	SLIST_NEXT((slistelm), field) = (elm);				\
238*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
239*85280f08SToomas Soome } while (0)
240*85280f08SToomas Soome 
241*85280f08SToomas Soome #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
242*85280f08SToomas Soome 	SLIST_NEXT((elm), field) = SLIST_FIRST((head));			\
243*85280f08SToomas Soome 	SLIST_FIRST((head)) = (elm);					\
244*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
245*85280f08SToomas Soome } while (0)
246*85280f08SToomas Soome 
247*85280f08SToomas Soome #define	SLIST_REMOVE_HEAD(head, field) do {				\
248*85280f08SToomas Soome 	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
249*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
250*85280f08SToomas Soome } while (0)
251*85280f08SToomas Soome 
252*85280f08SToomas Soome #define	SLIST_REMOVE_AFTER(slistelm, field) do {			\
253*85280f08SToomas Soome 	SLIST_NEXT((slistelm), field) =					\
254*85280f08SToomas Soome 	    SLIST_NEXT(SLIST_NEXT((slistelm), field), field);		\
255*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
256*85280f08SToomas Soome } while (0)
257*85280f08SToomas Soome 
258*85280f08SToomas Soome #define	SLIST_REMOVE(head, elm, type, field) do {			\
259*85280f08SToomas Soome 	QMD_SAVELINK(oldnext, SLIST_NEXT((elm), field));		\
260*85280f08SToomas Soome 	if (SLIST_FIRST((head)) == (elm)) {				\
261*85280f08SToomas Soome 		SLIST_REMOVE_HEAD((head), field);			\
262*85280f08SToomas Soome 	}								\
263*85280f08SToomas Soome 	else {								\
264*85280f08SToomas Soome 		QUEUE_TYPEOF(type) *curelm = SLIST_FIRST((head));	\
265*85280f08SToomas Soome 		while (SLIST_NEXT(curelm, field) != (elm))		\
266*85280f08SToomas Soome 			curelm = SLIST_NEXT(curelm, field);		\
267*85280f08SToomas Soome 		SLIST_REMOVE_AFTER(curelm, field);			\
268*85280f08SToomas Soome 	}								\
269*85280f08SToomas Soome 	TRASHIT(*oldnext);						\
270*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
271*85280f08SToomas Soome } while (0)
272*85280f08SToomas Soome 
273*85280f08SToomas Soome #define	SLIST_SWAP(head1, head2, type) do {				\
274*85280f08SToomas Soome 	QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1);		\
275*85280f08SToomas Soome 	SLIST_FIRST(head1) = SLIST_FIRST(head2);			\
276*85280f08SToomas Soome 	SLIST_FIRST(head2) = swap_first;				\
277*85280f08SToomas Soome } while (0)
278*85280f08SToomas Soome 
279*85280f08SToomas Soome /*
280*85280f08SToomas Soome  * Singly-linked Tail queue declarations.
281*85280f08SToomas Soome  */
282*85280f08SToomas Soome #define	STAILQ_HEAD(name, type)						\
283*85280f08SToomas Soome struct name {								\
284*85280f08SToomas Soome 	struct type *stqh_first;	/* first element */		\
285*85280f08SToomas Soome 	struct type **stqh_last;	/* addr of last next element */	\
286*85280f08SToomas Soome }
287*85280f08SToomas Soome 
288*85280f08SToomas Soome #define	STAILQ_CLASS_HEAD(name, type)					\
289*85280f08SToomas Soome struct name {								\
290*85280f08SToomas Soome 	class type *stqh_first;	/* first element */			\
291*85280f08SToomas Soome 	class type **stqh_last;	/* addr of last next element */		\
292*85280f08SToomas Soome }
293*85280f08SToomas Soome 
294*85280f08SToomas Soome #define	STAILQ_HEAD_INITIALIZER(head)					\
295*85280f08SToomas Soome 	{ NULL, &(head).stqh_first }
296*85280f08SToomas Soome 
297*85280f08SToomas Soome #define	STAILQ_ENTRY(type)						\
298*85280f08SToomas Soome struct {								\
299*85280f08SToomas Soome 	struct type *stqe_next;	/* next element */			\
300*85280f08SToomas Soome }
301*85280f08SToomas Soome 
302*85280f08SToomas Soome #define	STAILQ_CLASS_ENTRY(type)					\
303*85280f08SToomas Soome struct {								\
304*85280f08SToomas Soome 	class type *stqe_next;	/* next element */			\
305*85280f08SToomas Soome }
306*85280f08SToomas Soome 
307*85280f08SToomas Soome /*
308*85280f08SToomas Soome  * Singly-linked Tail queue access methods.
309*85280f08SToomas Soome  */
310*85280f08SToomas Soome #define	STAILQ_FIRST(head)	((head)->stqh_first)
311*85280f08SToomas Soome #define	STAILQ_END(head)	NULL
312*85280f08SToomas Soome #define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
313*85280f08SToomas Soome #define	STAILQ_EMPTY(head)	((head)->stqh_first == STAILQ_END(head))
314*85280f08SToomas Soome 
315*85280f08SToomas Soome #define	STAILQ_FOREACH(var, head, field)				\
316*85280f08SToomas Soome 	for ((var) = STAILQ_FIRST(head);				\
317*85280f08SToomas Soome 	    (var) != STAILQ_END(head);					\
318*85280f08SToomas Soome 	    (var) = STAILQ_NEXT((var), field))
319*85280f08SToomas Soome 
320*85280f08SToomas Soome #define	STAILQ_FOREACH_FROM(var, head, field)				\
321*85280f08SToomas Soome 	for ((var) =							\
322*85280f08SToomas Soome 	    ((var) != STAILQ_END(head) ? (var) : STAILQ_FIRST((head))); \
323*85280f08SToomas Soome 	    (var) != STAILQ_END(head);					\
324*85280f08SToomas Soome 	    (var) = STAILQ_NEXT((var), field))
325*85280f08SToomas Soome 
326*85280f08SToomas Soome #define	STAILQ_FOREACH_SAFE(var, head, field, tvar)			\
327*85280f08SToomas Soome 	for ((var) = STAILQ_FIRST(head);				\
328*85280f08SToomas Soome 	    (var) != STAILQ_END(head) &&				\
329*85280f08SToomas Soome 	    ((tvar) = STAILQ_NEXT((var), field), 1);			\
330*85280f08SToomas Soome 	    (var) = (tvar))
331*85280f08SToomas Soome 
332*85280f08SToomas Soome #define	STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)		\
333*85280f08SToomas Soome 	for ((var) =							\
334*85280f08SToomas Soome 	    ((var) != STAILQ_END(head) ? (var) : STAILQ_FIRST((head))); \
335*85280f08SToomas Soome 	    (var) != STAILQ_END(head) &&				\
336*85280f08SToomas Soome 	    ((tvar) = STAILQ_NEXT((var), field), 1);			\
337*85280f08SToomas Soome 	    (var) = (tvar))
338*85280f08SToomas Soome 
339*85280f08SToomas Soome /*
340*85280f08SToomas Soome  * Singly-linked Tail queue functions.
341*85280f08SToomas Soome  */
342*85280f08SToomas Soome #define	STAILQ_INIT(head) do {						\
343*85280f08SToomas Soome 	STAILQ_FIRST(head) = STAILQ_END(head);				\
344*85280f08SToomas Soome 	(head)->stqh_last = &STAILQ_FIRST((head));			\
345*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
346*85280f08SToomas Soome } while (0)
347*85280f08SToomas Soome 
348*85280f08SToomas Soome #define	STAILQ_CONCAT(head1, head2) do {				\
349*85280f08SToomas Soome 	if (!STAILQ_EMPTY((head2))) {					\
350*85280f08SToomas Soome 		*(head1)->stqh_last = STAILQ_FIRST((head2));		\
351*85280f08SToomas Soome 		(head1)->stqh_last = (head2)->stqh_last;		\
352*85280f08SToomas Soome 		STAILQ_INIT((head2));					\
353*85280f08SToomas Soome 	}								\
354*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
355*85280f08SToomas Soome } while (0)
356*85280f08SToomas Soome 
357*85280f08SToomas Soome #define	STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\
358*85280f08SToomas Soome 	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
359*85280f08SToomas Soome 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
360*85280f08SToomas Soome 	STAILQ_NEXT((tqelm), field) = (elm);				\
361*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
362*85280f08SToomas Soome } while (0)
363*85280f08SToomas Soome 
364*85280f08SToomas Soome #define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
365*85280f08SToomas Soome 	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)	\
366*85280f08SToomas Soome 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
367*85280f08SToomas Soome 	STAILQ_FIRST((head)) = (elm);					\
368*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
369*85280f08SToomas Soome } while (0)
370*85280f08SToomas Soome 
371*85280f08SToomas Soome #define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
372*85280f08SToomas Soome 	STAILQ_NEXT((elm), field) = NULL;				\
373*85280f08SToomas Soome 	*(head)->stqh_last = (elm);					\
374*85280f08SToomas Soome 	(head)->stqh_last = &STAILQ_NEXT((elm), field);			\
375*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
376*85280f08SToomas Soome } while (0)
377*85280f08SToomas Soome 
378*85280f08SToomas Soome #define	STAILQ_LAST(head, type, field)					\
379*85280f08SToomas Soome 	(STAILQ_EMPTY((head)) ? NULL :					\
380*85280f08SToomas Soome 	    __containerof((head)->stqh_last,				\
381*85280f08SToomas Soome 	    QUEUE_TYPEOF(type), field.stqe_next))
382*85280f08SToomas Soome 
383*85280f08SToomas Soome #define	STAILQ_REMOVE_HEAD(head, field) do {				\
384*85280f08SToomas Soome 	if ((STAILQ_FIRST((head)) =					\
385*85280f08SToomas Soome 	    STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)		\
386*85280f08SToomas Soome 		(head)->stqh_last = &STAILQ_FIRST((head));		\
387*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
388*85280f08SToomas Soome } while (0)
389*85280f08SToomas Soome 
390*85280f08SToomas Soome #define	STAILQ_REMOVE_AFTER(head, elm, field) do {			\
391*85280f08SToomas Soome 	if ((STAILQ_NEXT(elm, field) =					\
392*85280f08SToomas Soome 	    STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)	\
393*85280f08SToomas Soome 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
394*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
395*85280f08SToomas Soome } while (0)
396*85280f08SToomas Soome 
397*85280f08SToomas Soome #define	STAILQ_REMOVE(head, elm, type, field) do {			\
398*85280f08SToomas Soome 	QMD_SAVELINK(oldnext, (elm)->field.stqe_next);			\
399*85280f08SToomas Soome 	if (STAILQ_FIRST((head)) == (elm)) {				\
400*85280f08SToomas Soome 		STAILQ_REMOVE_HEAD((head), field);			\
401*85280f08SToomas Soome 	} else {							\
402*85280f08SToomas Soome 		QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head);	\
403*85280f08SToomas Soome 		while (STAILQ_NEXT(curelm, field) != (elm))		\
404*85280f08SToomas Soome 			curelm = STAILQ_NEXT(curelm, field);		\
405*85280f08SToomas Soome 		STAILQ_REMOVE_AFTER(head, curelm, field);		\
406*85280f08SToomas Soome 	}								\
407*85280f08SToomas Soome 	TRASHIT(*oldnext);						\
408*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
409*85280f08SToomas Soome } while (0)
410*85280f08SToomas Soome 
411*85280f08SToomas Soome #define	STAILQ_SWAP(head1, head2, type) do {				\
412*85280f08SToomas Soome 	QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1);		\
413*85280f08SToomas Soome 	QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last;		\
414*85280f08SToomas Soome 	STAILQ_FIRST(head1) = STAILQ_FIRST(head2);			\
415*85280f08SToomas Soome 	(head1)->stqh_last = (head2)->stqh_last;			\
416*85280f08SToomas Soome 	STAILQ_FIRST(head2) = swap_first;				\
417*85280f08SToomas Soome 	(head2)->stqh_last = swap_last;					\
418*85280f08SToomas Soome 	if (STAILQ_EMPTY(head1))					\
419*85280f08SToomas Soome 		(head1)->stqh_last = &STAILQ_FIRST(head1);		\
420*85280f08SToomas Soome 	if (STAILQ_EMPTY(head2))					\
421*85280f08SToomas Soome 		(head2)->stqh_last = &STAILQ_FIRST(head2);		\
422*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
423*85280f08SToomas Soome } while (0)
424*85280f08SToomas Soome 
425381a2a9aSdr146992 /*
426381a2a9aSdr146992  * List definitions.
427381a2a9aSdr146992  */
428381a2a9aSdr146992 #define	LIST_HEAD(name, type)						\
429381a2a9aSdr146992 struct name {								\
430381a2a9aSdr146992 	struct type *lh_first;	/* first element */			\
431381a2a9aSdr146992 }
432381a2a9aSdr146992 
433*85280f08SToomas Soome #define	LIST_CLASS_HEAD(name, type)					\
434*85280f08SToomas Soome struct name {								\
435*85280f08SToomas Soome 	class type *lh_first;	/* first element */			\
436*85280f08SToomas Soome }
437*85280f08SToomas Soome 
438381a2a9aSdr146992 #define	LIST_HEAD_INITIALIZER(head)					\
439381a2a9aSdr146992 	{ NULL }
440381a2a9aSdr146992 
441381a2a9aSdr146992 #define	LIST_ENTRY(type)						\
442381a2a9aSdr146992 struct {								\
443381a2a9aSdr146992 	struct type *le_next;	/* next element */			\
444381a2a9aSdr146992 	struct type **le_prev;	/* address of previous next element */	\
445381a2a9aSdr146992 }
446381a2a9aSdr146992 
447*85280f08SToomas Soome #define	LIST_CLASS_ENTRY(type)						\
448*85280f08SToomas Soome struct {								\
449*85280f08SToomas Soome 	class type *le_next;	/* next element */			\
450*85280f08SToomas Soome 	class type **le_prev;	/* address of previous next element */	\
451*85280f08SToomas Soome }
452*85280f08SToomas Soome 
453*85280f08SToomas Soome /*
454*85280f08SToomas Soome  * List access methods.
455*85280f08SToomas Soome  */
456*85280f08SToomas Soome #define	LIST_FIRST(head)		((head)->lh_first)
457*85280f08SToomas Soome #define	LIST_END(head)			NULL
458*85280f08SToomas Soome #define	LIST_EMPTY(head)		((head)->lh_first == LIST_END(head))
459*85280f08SToomas Soome #define	LIST_NEXT(elm, field)		((elm)->field.le_next)
460*85280f08SToomas Soome #define	LIST_PREV(elm, head, type, field)				\
461*85280f08SToomas Soome 	((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL :		\
462*85280f08SToomas Soome 	__containerof((elm)->field.le_prev, type, field.le_next))
463*85280f08SToomas Soome 
464*85280f08SToomas Soome #define	LIST_FOREACH(var, head, field)					\
465*85280f08SToomas Soome 	for ((var) = LIST_FIRST((head));				\
466*85280f08SToomas Soome 	    (var) != LIST_END(head);					\
467*85280f08SToomas Soome 	    (var) = LIST_NEXT((var), field))
468*85280f08SToomas Soome 
469*85280f08SToomas Soome #define	LIST_FOREACH_FROM(var, head, field)				\
470*85280f08SToomas Soome 	for ((var) = ((var) != LIST_END(head) ? (var) : LIST_FIRST((head));\
471*85280f08SToomas Soome 	    (var) != LIST_END(head);					\
472*85280f08SToomas Soome 	    (var) = LIST_NEXT((var), field))
473*85280f08SToomas Soome 
474*85280f08SToomas Soome #define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
475*85280f08SToomas Soome 	for ((var) = LIST_FIRST((head));				\
476*85280f08SToomas Soome 	    (var) != LIST_END(head) &&				\
477*85280f08SToomas Soome 	    ((tvar) = LIST_NEXT((var), field), 1);			\
478*85280f08SToomas Soome 	    (var) = (tvar))
479*85280f08SToomas Soome 
480*85280f08SToomas Soome #define	LIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
481*85280f08SToomas Soome 	for ((var) = ((var) != LIST_END(head) ? (var) : LIST_FIRST((head));\
482*85280f08SToomas Soome 	    (var) != LIST_END(head) &&				\
483*85280f08SToomas Soome 	    ((tvar) = LIST_NEXT((var), field), 1);			\
484*85280f08SToomas Soome 	    (var) = (tvar))
485*85280f08SToomas Soome 
486381a2a9aSdr146992 /*
487381a2a9aSdr146992  * List functions.
488381a2a9aSdr146992  */
489381a2a9aSdr146992 #if defined(_KERNEL) && defined(QUEUEDEBUG)
490381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)			\
491381a2a9aSdr146992 	if ((head)->lh_first &&						\
492381a2a9aSdr146992 	    (head)->lh_first->field.le_prev != &(head)->lh_first)	\
493381a2a9aSdr146992 		panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
494381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_OP(elm, field)					\
495381a2a9aSdr146992 	if ((elm)->field.le_next &&					\
496381a2a9aSdr146992 	    (elm)->field.le_next->field.le_prev !=			\
497381a2a9aSdr146992 	    &(elm)->field.le_next)					\
498381a2a9aSdr146992 		panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
499381a2a9aSdr146992 	if (*(elm)->field.le_prev != (elm))				\
500381a2a9aSdr146992 		panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__);
501381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_POSTREMOVE(elm, field)				\
502381a2a9aSdr146992 	(elm)->field.le_next = (void *)1L;				\
503381a2a9aSdr146992 	(elm)->field.le_prev = (void *)1L;
504381a2a9aSdr146992 #else
505381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
506381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_OP(elm, field)
507381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
508381a2a9aSdr146992 #endif
509381a2a9aSdr146992 
510381a2a9aSdr146992 #define	LIST_INIT(head) do {						\
511*85280f08SToomas Soome 	LIST_FIRST((head)) = LIST_END(head);				\
512381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
513381a2a9aSdr146992 } while (0)
514381a2a9aSdr146992 
515381a2a9aSdr146992 #define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
516381a2a9aSdr146992 	QUEUEDEBUG_LIST_OP((listelm), field)				\
517*85280f08SToomas Soome 	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
518*85280f08SToomas Soome 		LIST_NEXT((listelm), field)->field.le_prev =		\
519*85280f08SToomas Soome 		    &LIST_NEXT((elm), field);				\
520*85280f08SToomas Soome 	LIST_NEXT((listelm), field) = (elm);				\
521*85280f08SToomas Soome 	(elm)->field.le_prev = &LIST_NEXT((listelm), field);		\
522381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
523381a2a9aSdr146992 } while (0)
524381a2a9aSdr146992 
525381a2a9aSdr146992 #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
526381a2a9aSdr146992 	QUEUEDEBUG_LIST_OP((listelm), field)				\
527381a2a9aSdr146992 	(elm)->field.le_prev = (listelm)->field.le_prev;		\
528*85280f08SToomas Soome 	LIST_NEXT((elm), field) = (listelm);				\
529381a2a9aSdr146992 	*(listelm)->field.le_prev = (elm);				\
530*85280f08SToomas Soome 	(listelm)->field.le_prev = &LIST_NEXT((elm), field);		\
531381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
532381a2a9aSdr146992 } while (0)
533381a2a9aSdr146992 
534381a2a9aSdr146992 #define	LIST_INSERT_HEAD(head, elm, field) do {				\
535381a2a9aSdr146992 	QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field)		\
536*85280f08SToomas Soome 	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\
537*85280f08SToomas Soome 		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
538*85280f08SToomas Soome 	LIST_FIRST((head)) = (elm);					\
539*85280f08SToomas Soome 	(elm)->field.le_prev = &LIST_FIRST((head));			\
540381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
541381a2a9aSdr146992 } while (0)
542381a2a9aSdr146992 
543381a2a9aSdr146992 #define	LIST_REMOVE(elm, field) do {					\
544381a2a9aSdr146992 	QUEUEDEBUG_LIST_OP((elm), field)				\
545*85280f08SToomas Soome 	if (LIST_NEXT((elm), field) != NULL)				\
546*85280f08SToomas Soome 		LIST_NEXT((elm), field)->field.le_prev =		\
547381a2a9aSdr146992 		    (elm)->field.le_prev;				\
548*85280f08SToomas Soome 	*(elm)->field.le_prev = LIST_NEXT((elm), field);		\
549381a2a9aSdr146992 	QUEUEDEBUG_LIST_POSTREMOVE((elm), field)			\
550381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
551381a2a9aSdr146992 } while (0)
552381a2a9aSdr146992 
553*85280f08SToomas Soome #define	LIST_SWAP(head1, head2, type, field) do {                       \
554*85280f08SToomas Soome 	QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1);               \
555*85280f08SToomas Soome 	LIST_FIRST((head1)) = LIST_FIRST((head2));                      \
556*85280f08SToomas Soome 	LIST_FIRST((head2)) = swap_tmp;                                 \
557*85280f08SToomas Soome 	if ((swap_tmp = LIST_FIRST((head1))) != NULL)                   \
558*85280f08SToomas Soome 		swap_tmp->field.le_prev = &LIST_FIRST((head1));         \
559*85280f08SToomas Soome 	if ((swap_tmp = LIST_FIRST((head2))) != NULL)                   \
560*85280f08SToomas Soome 		swap_tmp->field.le_prev = &LIST_FIRST((head2));         \
561381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
562381a2a9aSdr146992 } while (0)
563381a2a9aSdr146992 
564381a2a9aSdr146992 /*
565381a2a9aSdr146992  * Simple queue definitions.
566381a2a9aSdr146992  */
567381a2a9aSdr146992 #define	SIMPLEQ_HEAD(name, type)					\
568381a2a9aSdr146992 struct name {								\
569381a2a9aSdr146992 	struct type *sqh_first;	/* first element */		\
570381a2a9aSdr146992 	struct type **sqh_last;	/* addr of last next element */	\
571381a2a9aSdr146992 }
572381a2a9aSdr146992 
573*85280f08SToomas Soome #define	SIMPLEQ_CLASS_HEAD(name, type)					\
574*85280f08SToomas Soome struct name {								\
575*85280f08SToomas Soome 	class type *sqh_first;	/* first element */		\
576*85280f08SToomas Soome 	class type **sqh_last;	/* addr of last next element */	\
577*85280f08SToomas Soome }
578*85280f08SToomas Soome 
579381a2a9aSdr146992 #define	SIMPLEQ_HEAD_INITIALIZER(head)					\
580381a2a9aSdr146992 	{ NULL, &(head).sqh_first }
581381a2a9aSdr146992 
582381a2a9aSdr146992 #define	SIMPLEQ_ENTRY(type)						\
583381a2a9aSdr146992 struct {								\
584381a2a9aSdr146992 	struct type *sqe_next;	/* next element */			\
585381a2a9aSdr146992 }
586381a2a9aSdr146992 
587*85280f08SToomas Soome #define	SIMPLEQ_CLASS_ENTRY(type)					\
588*85280f08SToomas Soome struct {								\
589*85280f08SToomas Soome 	class type *sqe_next;	/* next element */			\
590*85280f08SToomas Soome }
5918c5d29abSToomas Soome 
592b346eeddSGordon Ross /*
593b346eeddSGordon Ross  * Simple queue access methods.
594b346eeddSGordon Ross  */
595b346eeddSGordon Ross #define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
596*85280f08SToomas Soome #define	SIMPLEQ_END(head)		NULL
597*85280f08SToomas Soome #define	SIMPLEQ_EMPTY(head)		((head)->sqh_first == SIMPLEQ_END(head))
598b346eeddSGordon Ross #define	SIMPLEQ_NEXT(elm, field)	((elm)->field.sqe_next)
599b346eeddSGordon Ross 
600*85280f08SToomas Soome #define	SIMPLEQ_FOREACH(var, head, field)				\
601*85280f08SToomas Soome 	for ((var) = SIMPLEQ_FIRST((head));				\
602*85280f08SToomas Soome 	    (var) != SIMPLEQ_END(head);					\
603*85280f08SToomas Soome 	    (var) = SIMPLEQ_NEXT((var), field))
604*85280f08SToomas Soome 
605*85280f08SToomas Soome #define	SIMPLEQ_FOREACH_FROM(var, head, field)				\
606*85280f08SToomas Soome 	for ((var) =							\
607*85280f08SToomas Soome 	    ((var) != SIMPLEQ_END(head) ? (var) : SIMPLEQ_FIRST((head)));\
608*85280f08SToomas Soome 	    (var) != SIMPLEQ_END(head);					\
609*85280f08SToomas Soome 	    (var) = SIMPLEQ_NEXT((var), field))
610*85280f08SToomas Soome 
611*85280f08SToomas Soome #define	SIMPLEQ_FOREACH_SAFE(var, head, field, tvar)			\
612*85280f08SToomas Soome 	for ((var) = SIMPLEQ_FIRST((head));				\
613*85280f08SToomas Soome 	    (var) != SIMPLEQ_END(head) &&				\
614*85280f08SToomas Soome 	    ((tvar) = SIMPLEQ_NEXT((var), field), 1);			\
615*85280f08SToomas Soome 	    (var) = (tvar))
616*85280f08SToomas Soome 
617*85280f08SToomas Soome #define	SIMPLEQ_FOREACH_FROM_SAFE(var, head, field, tvar)		\
618*85280f08SToomas Soome 	for ((var) =							\
619*85280f08SToomas Soome 	    ((var) != SIMPLEQ_END(head) ? (var) : SIMPLEQ_FIRST((head)));\
620*85280f08SToomas Soome 	    (var) != SIMPLEQ_END(head) &&				\
621*85280f08SToomas Soome 	    ((tvar) = SIMPLEQ_NEXT((var), field), 1);			\
622*85280f08SToomas Soome 	    (var) = (tvar))
623*85280f08SToomas Soome 
624*85280f08SToomas Soome /*
625*85280f08SToomas Soome  * Simple queue functions.
626*85280f08SToomas Soome  */
627*85280f08SToomas Soome #define	SIMPLEQ_INIT(head) do {						\
628*85280f08SToomas Soome 	SIMPLEQ_FIRST((head)) = NULL;					\
629*85280f08SToomas Soome 	(head)->sqh_last = &SIMPLEQ_FIRST((head));			\
630*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
631*85280f08SToomas Soome } while (0)
632*85280f08SToomas Soome 
633*85280f08SToomas Soome #define	SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
634*85280f08SToomas Soome 	if ((SIMPLEQ_NEXT((elm), field) = SIMPLEQ_FIRST((head))) == NULL)\
635*85280f08SToomas Soome 		(head)->sqh_last = &SIMPLEQ_NEXT((elm), field);		\
636*85280f08SToomas Soome 	SIMPLEQ_FIRST((head)) = (elm);					\
637*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
638*85280f08SToomas Soome } while (0)
639*85280f08SToomas Soome 
640*85280f08SToomas Soome #define	SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
641*85280f08SToomas Soome 	SIMPLEQ_NEXT((elm), field) = NULL;				\
642*85280f08SToomas Soome 	*(head)->sqh_last = (elm);					\
643*85280f08SToomas Soome 	(head)->sqh_last = &SIMPLEQ_NEXT((elm), field);			\
644*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
645*85280f08SToomas Soome } while (0)
646*85280f08SToomas Soome 
647*85280f08SToomas Soome #define	SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
648*85280f08SToomas Soome 	if ((SIMPLEQ_NEXT((elm), field) = SIMPLEQ_NEXT((listelm), field)) == \
649*85280f08SToomas Soome 	    NULL)							\
650*85280f08SToomas Soome 		(head)->sqh_last = &SIMPLEQ_NEXT((elm), field);		\
651*85280f08SToomas Soome 	SIMPLEQ_NEXT((listelm), field) = (elm);				\
652*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
653*85280f08SToomas Soome } while (0)
654*85280f08SToomas Soome 
655*85280f08SToomas Soome #define	SIMPLEQ_REMOVE_HEAD(head, field) do {				\
656*85280f08SToomas Soome 	if ((SIMPLEQ_FIRST((head)) =					\
657*85280f08SToomas Soome 	    SIMPLEQ_NEXT(SIMPLEQ_FIRST((head)), field)) == NULL)	\
658*85280f08SToomas Soome 		(head)->sqh_last = &SIMPLEQ_FIRST((head));		\
659*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
660*85280f08SToomas Soome } while (0)
661*85280f08SToomas Soome 
662*85280f08SToomas Soome #define	SIMPLEQ_REMOVE_AFTER(head, elm, field) do {			\
663*85280f08SToomas Soome 	if ((SIMPLEQ_NEXT((elm)) =					\
664*85280f08SToomas Soome 	    SIMPLEQ_NEXT(SIMPLEQ_NEXT((elm), field), field)) == NULL)	\
665*85280f08SToomas Soome 		(head)->sqh_last = &SIMPLEQ_NEXT((elm), field);		\
666*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
667*85280f08SToomas Soome } while (0)
668*85280f08SToomas Soome 
669*85280f08SToomas Soome #define	SIMPLEQ_REMOVE(head, elm, type, field) do {			\
670*85280f08SToomas Soome 	if (SIMPLEQ_FIRST((head)) == (elm)) {				\
671*85280f08SToomas Soome 		SIMPLEQ_REMOVE_HEAD((head), field);			\
672*85280f08SToomas Soome 	} else {							\
673*85280f08SToomas Soome 		QUEUE_TYPEOF(type) *curelm = SIMPLEQ_FIRST((head));	\
674*85280f08SToomas Soome 		while (SIMPLEQ_NEXT(curelm, field) != (elm))		\
675*85280f08SToomas Soome 			curelm = SIMPLEQ_NEXT(curelm, field);		\
676*85280f08SToomas Soome 		SIMPLEQ_REMOVE_AFTER((head), curelm, field);		\
677*85280f08SToomas Soome 	}								\
678*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
679*85280f08SToomas Soome } while (0)
680*85280f08SToomas Soome 
681*85280f08SToomas Soome #define	SIMPLEQ_CONCAT(head1, head2) do {				\
682*85280f08SToomas Soome 	if (!SIMPLEQ_EMPTY((head2))) {					\
683*85280f08SToomas Soome 		*(head1)->sqh_last = (head2)->sqh_first;		\
684*85280f08SToomas Soome 		(head1)->sqh_last = (head2)->sqh_last;			\
685*85280f08SToomas Soome 		SIMPLEQ_INIT((head2));					\
686*85280f08SToomas Soome 	}								\
687*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
688*85280f08SToomas Soome } while (0)
689*85280f08SToomas Soome 
690*85280f08SToomas Soome #define	SIMPLEQ_LAST(head, type, field)					\
691*85280f08SToomas Soome 	(SIMPLEQ_EMPTY((head)) ?					\
692*85280f08SToomas Soome 	    NULL :							\
693*85280f08SToomas Soome 	    ((QUEUE_TYPEOF(type) *)(void *)				\
694*85280f08SToomas Soome 	    ((char *)((head)->sqh_last) - offsetof(QUEUE_TYPEOF(type), field))))
695381a2a9aSdr146992 
696381a2a9aSdr146992 /*
697381a2a9aSdr146992  * Tail queue definitions.
698381a2a9aSdr146992  */
699*85280f08SToomas Soome #define	TAILQ_HEAD(name, type)						\
700381a2a9aSdr146992 struct name {								\
701*85280f08SToomas Soome 	struct type *tqh_first;		/* first element */		\
702*85280f08SToomas Soome 	struct type **tqh_last;	/* addr of last next element */		\
703*85280f08SToomas Soome 	TRACEBUF							\
704381a2a9aSdr146992 }
705*85280f08SToomas Soome 
706*85280f08SToomas Soome #define	TAILQ_CLASS_HEAD(name, type)					\
707*85280f08SToomas Soome struct name {								\
708*85280f08SToomas Soome 	class type *tqh_first;		/* first element */		\
709*85280f08SToomas Soome 	class type **tqh_last;	/* addr of last next element */		\
710*85280f08SToomas Soome 	TRACEBUF							\
711*85280f08SToomas Soome }
712381a2a9aSdr146992 
713381a2a9aSdr146992 #define	TAILQ_HEAD_INITIALIZER(head)					\
714381a2a9aSdr146992 	{ NULL, &(head).tqh_first }
715381a2a9aSdr146992 
716*85280f08SToomas Soome #define	TAILQ_ENTRY(type)						\
717381a2a9aSdr146992 struct {								\
718*85280f08SToomas Soome 	struct type *tqe_next;	/* next element */			\
719*85280f08SToomas Soome 	struct type **tqe_prev;	/* address of previous next element */	\
720*85280f08SToomas Soome 	TRACEBUF							\
721381a2a9aSdr146992 }
722*85280f08SToomas Soome 
723*85280f08SToomas Soome #define	TAILQ_CLASS_ENTRY(type)						\
724*85280f08SToomas Soome struct {								\
725*85280f08SToomas Soome 	class type *tqe_next;	/* next element */			\
726*85280f08SToomas Soome 	class type **tqe_prev;	/* address of previous next element */	\
727*85280f08SToomas Soome 	TRACEBUF							\
728*85280f08SToomas Soome }
729*85280f08SToomas Soome 
730*85280f08SToomas Soome /*
731*85280f08SToomas Soome  * Tail queue access methods.
732*85280f08SToomas Soome  */
733*85280f08SToomas Soome #define	TAILQ_FIRST(head)		((head)->tqh_first)
734*85280f08SToomas Soome #define	TAILQ_END(head)			NULL
735*85280f08SToomas Soome #define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
736*85280f08SToomas Soome #define	TAILQ_LAST(head, headname) \
737*85280f08SToomas Soome 	(*(((struct headname *)((head)->tqh_last))->tqh_last))
738*85280f08SToomas Soome #define	TAILQ_PREV(elm, headname, field) \
739*85280f08SToomas Soome 	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
740*85280f08SToomas Soome #define	TAILQ_EMPTY(head)		((head)->tqh_first == TAILQ_END(head))
741*85280f08SToomas Soome 
742*85280f08SToomas Soome 
743*85280f08SToomas Soome #define	TAILQ_FOREACH(var, head, field)					\
744*85280f08SToomas Soome 	for ((var) = TAILQ_FIRST((head));				\
745*85280f08SToomas Soome 	    (var) != TAILQ_END(head);					\
746*85280f08SToomas Soome 	    (var) = TAILQ_NEXT((var), field))
747*85280f08SToomas Soome 
748*85280f08SToomas Soome #define	TAILQ_FOREACH_FROM(var, head, field)				\
749*85280f08SToomas Soome 	for ((var) = ((var) != TAILQ_END((head)) ?			\
750*85280f08SToomas Soome 	    (var) : TAILQ_FIRST((head)));				\
751*85280f08SToomas Soome 	    (var) != TAILQ_END(head);					\
752*85280f08SToomas Soome 	    (var) = TAILQ_NEXT((var), field))
753*85280f08SToomas Soome 
754*85280f08SToomas Soome #define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
755*85280f08SToomas Soome 	for ((var) = TAILQ_FIRST((head));				\
756*85280f08SToomas Soome 	    (var) != TAILQ_END(head) &&					\
757*85280f08SToomas Soome 	    ((tvar) = TAILQ_NEXT((var), field), 1);			\
758*85280f08SToomas Soome 	    (var) = (tvar))
759*85280f08SToomas Soome 
760*85280f08SToomas Soome #define	TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)			\
761*85280f08SToomas Soome 	for ((var) = ((var) != TAILQ_END((head)) ?			\
762*85280f08SToomas Soome 	    (var) : TAILQ_FIRST((head)));				\
763*85280f08SToomas Soome 	    (var) != TAILQ_END(head) &&					\
764*85280f08SToomas Soome 	    ((tvar) = TAILQ_NEXT((var), field), 1);			\
765*85280f08SToomas Soome 	    (var) = (tvar))
766*85280f08SToomas Soome 
767*85280f08SToomas Soome #define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
768*85280f08SToomas Soome 	for ((var) = TAILQ_LAST((head), headname);			\
769*85280f08SToomas Soome 	    (var) != TAILQ_END(head);					\
770*85280f08SToomas Soome 	    (var) = TAILQ_PREV((var), headname, field))
771*85280f08SToomas Soome 
772*85280f08SToomas Soome #define	TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field)		\
773*85280f08SToomas Soome 	for ((var) = ((var) != TAILQ_END((head)) ?			\
774*85280f08SToomas Soome 	    (var) : TAILQ_LAST((head), headname));			\
775*85280f08SToomas Soome 	    (var) != TAILQ_END(head);					\
776*85280f08SToomas Soome 	    (var) = TAILQ_PREV((var), headname, field))
777*85280f08SToomas Soome 
778*85280f08SToomas Soome #define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
779*85280f08SToomas Soome 	for ((var) = TAILQ_LAST((head), headname);			\
780*85280f08SToomas Soome 	    (var) != TAILQ_END(head) &&					\
781*85280f08SToomas Soome 	    ((tvar) = TAILQ_PREV((var), headname, field), 1);		\
782*85280f08SToomas Soome 	    (var) = (tvar))
783*85280f08SToomas Soome 
784*85280f08SToomas Soome #define	TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar)\
785*85280f08SToomas Soome 	for ((var) = ((var) != TAILQ_END((head)) ?			\
786*85280f08SToomas Soome 	    (var) : TAILQ_LAST((head), headname));			\
787*85280f08SToomas Soome 	    (var) != TAILQ_END(head) &&					\
788*85280f08SToomas Soome 	    ((tvar) = TAILQ_PREV((var), headname, field), 1);		\
789*85280f08SToomas Soome 	    (var) = (tvar))
790381a2a9aSdr146992 
791381a2a9aSdr146992 /*
792381a2a9aSdr146992  * Tail queue functions.
793381a2a9aSdr146992  */
794381a2a9aSdr146992 #if defined(_KERNEL) && defined(QUEUEDEBUG)
795381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)			\
796381a2a9aSdr146992 	if ((head)->tqh_first &&					\
797381a2a9aSdr146992 	    (head)->tqh_first->field.tqe_prev != &(head)->tqh_first)	\
798c1374a13SSurya Prakki 		panic("TAILQ_INSERT_HEAD %p %s:%d", (void *)(head),	\
799c1374a13SSurya Prakki 		    __FILE__, __LINE__);
800381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)			\
801381a2a9aSdr146992 	if (*(head)->tqh_last != NULL)					\
802c1374a13SSurya Prakki 		panic("TAILQ_INSERT_TAIL %p %s:%d", (void *)(head),	\
803c1374a13SSurya Prakki 		    __FILE__, __LINE__);
804381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_OP(elm, field)					\
805381a2a9aSdr146992 	if ((elm)->field.tqe_next &&					\
806381a2a9aSdr146992 	    (elm)->field.tqe_next->field.tqe_prev !=			\
807381a2a9aSdr146992 	    &(elm)->field.tqe_next)					\
808c1374a13SSurya Prakki 		panic("TAILQ_* forw %p %s:%d", (void *)(elm),		\
809c1374a13SSurya Prakki 		    __FILE__, __LINE__);\
810381a2a9aSdr146992 	if (*(elm)->field.tqe_prev != (elm))				\
811c1374a13SSurya Prakki 		panic("TAILQ_* back %p %s:%d", (void *)(elm),		\
812c1374a13SSurya Prakki 		    __FILE__, __LINE__);
813381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)			\
814381a2a9aSdr146992 	if ((elm)->field.tqe_next == NULL &&				\
815381a2a9aSdr146992 	    (head)->tqh_last != &(elm)->field.tqe_next)			\
816381a2a9aSdr146992 		panic("TAILQ_PREREMOVE head %p elm %p %s:%d",		\
817c1374a13SSurya Prakki 		    (void *)(head), (void *)(elm), __FILE__, __LINE__);
818381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)				\
819381a2a9aSdr146992 	(elm)->field.tqe_next = (void *)1L;				\
820381a2a9aSdr146992 	(elm)->field.tqe_prev = (void *)1L;
821381a2a9aSdr146992 #else
822381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
823381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
824381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_OP(elm, field)
825381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)
826381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
827381a2a9aSdr146992 #endif
828381a2a9aSdr146992 
829381a2a9aSdr146992 #define	TAILQ_INIT(head) do {						\
830*85280f08SToomas Soome 	TAILQ_FIRST((head)) = TAILQ_END((head));			\
831*85280f08SToomas Soome 	(head)->tqh_last = &TAILQ_FIRST((head));			\
832381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
833381a2a9aSdr146992 } while (0)
834381a2a9aSdr146992 
835381a2a9aSdr146992 #define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
836381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field)		\
837*85280f08SToomas Soome 	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)	\
838*85280f08SToomas Soome 		TAILQ_FIRST((head))->field.tqe_prev =			\
839*85280f08SToomas Soome 		    &TAILQ_NEXT((elm), field);				\
840381a2a9aSdr146992 	else								\
841*85280f08SToomas Soome 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
842*85280f08SToomas Soome 	TAILQ_FIRST((head)) = (elm);					\
843*85280f08SToomas Soome 	(elm)->field.tqe_prev = &TAILQ_FIRST((head));			\
844381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
845381a2a9aSdr146992 } while (0)
846381a2a9aSdr146992 
847381a2a9aSdr146992 #define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
848381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field)		\
849*85280f08SToomas Soome 	TAILQ_NEXT((elm), field) = NULL;				\
850381a2a9aSdr146992 	(elm)->field.tqe_prev = (head)->tqh_last;			\
851381a2a9aSdr146992 	*(head)->tqh_last = (elm);					\
852*85280f08SToomas Soome 	(head)->tqh_last = &TAILQ_NEXT((elm), field);			\
853381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
854381a2a9aSdr146992 } while (0)
855381a2a9aSdr146992 
856381a2a9aSdr146992 #define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
857381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
858*85280f08SToomas Soome 	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
859*85280f08SToomas Soome 		TAILQ_NEXT((elm), field)->field.tqe_prev =		\
860*85280f08SToomas Soome 		    &TAILQ_NEXT((elm), field);				\
861381a2a9aSdr146992 	else								\
862*85280f08SToomas Soome 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
863*85280f08SToomas Soome 	TAILQ_NEXT((listelm), field) = (elm);				\
864*85280f08SToomas Soome 	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);		\
865381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
866381a2a9aSdr146992 } while (0)
867381a2a9aSdr146992 
868381a2a9aSdr146992 #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
869381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
870381a2a9aSdr146992 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
871*85280f08SToomas Soome 	TAILQ_NEXT((elm), field) = (listelm);				\
872381a2a9aSdr146992 	*(listelm)->field.tqe_prev = (elm);				\
873*85280f08SToomas Soome 	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);		\
874381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
875381a2a9aSdr146992 } while (0)
876381a2a9aSdr146992 
877381a2a9aSdr146992 #define	TAILQ_REMOVE(head, elm, field) do {				\
878381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field)		\
879381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_OP((elm), field)				\
880*85280f08SToomas Soome 	if ((TAILQ_NEXT((elm), field)) != NULL)				\
881*85280f08SToomas Soome 		TAILQ_NEXT((elm), field)->field.tqe_prev =		\
882381a2a9aSdr146992 		    (elm)->field.tqe_prev;				\
883381a2a9aSdr146992 	else								\
884381a2a9aSdr146992 		(head)->tqh_last = (elm)->field.tqe_prev;		\
885*85280f08SToomas Soome 	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);		\
886381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field);			\
887381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
888381a2a9aSdr146992 } while (0)
889381a2a9aSdr146992 
890*85280f08SToomas Soome #define	TAILQ_SWAP(head1, head2, type, field) do {			\
891*85280f08SToomas Soome 	QUEUE_TYPEOF(type) *swap_first = TAILQ_FIRST((head1));		\
892*85280f08SToomas Soome 	QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last;		\
893*85280f08SToomas Soome 	TAILQ_FIRST((head1)) = TAILQ_FIRST((head2));			\
894*85280f08SToomas Soome 	(head1)->tqh_last = (head2)->tqh_last;				\
895*85280f08SToomas Soome 	TAILQ_FIRST((head2)) = swap_first;				\
896*85280f08SToomas Soome 	(head2)->tqh_last = swap_last;					\
897*85280f08SToomas Soome 	if ((swap_first = TAILQ_FIRST((head1))) != NULL)		\
898*85280f08SToomas Soome 		swap_first->field.tqe_prev = &TAILQ_FIRST((head1));	\
899*85280f08SToomas Soome 	else								\
900*85280f08SToomas Soome 		(head1)->tqh_last = &TAILQ_FIRST((head1));		\
901*85280f08SToomas Soome 	if ((swap_first = TAILQ_FIRST((head2))) != NULL)		\
902*85280f08SToomas Soome 		swap_first->field.tqe_prev = &TAILQ_FIRST((head2));	\
903*85280f08SToomas Soome 	else								\
904*85280f08SToomas Soome 		(head2)->tqh_last = &TAILQ_FIRST((head2));		\
905*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
906*85280f08SToomas Soome } while (0)
907381a2a9aSdr146992 
908381a2a9aSdr146992 /*
909*85280f08SToomas Soome  * Circular queue definitions. Do not use. We still keep the macros
910*85280f08SToomas Soome  * for compatibility but because of pointer aliasing issues their use
911*85280f08SToomas Soome  * is discouraged!
912381a2a9aSdr146992  */
913381a2a9aSdr146992 #define	CIRCLEQ_HEAD(name, type)					\
914381a2a9aSdr146992 struct name {								\
915381a2a9aSdr146992 	struct type *cqh_first;		/* first element */	\
916381a2a9aSdr146992 	struct type *cqh_last;		/* last element */		\
917381a2a9aSdr146992 }
918381a2a9aSdr146992 
919381a2a9aSdr146992 #define	CIRCLEQ_HEAD_INITIALIZER(head)					\
920381a2a9aSdr146992 	{ (void *)&head, (void *)&head }
921381a2a9aSdr146992 
922381a2a9aSdr146992 #define	CIRCLEQ_ENTRY(type)						\
923381a2a9aSdr146992 struct {								\
924381a2a9aSdr146992 	struct type *cqe_next;		/* next element */		\
925381a2a9aSdr146992 	struct type *cqe_prev;		/* previous element */		\
926381a2a9aSdr146992 }
927381a2a9aSdr146992 
928381a2a9aSdr146992 /*
929*85280f08SToomas Soome  * Circular queue access methods.
930*85280f08SToomas Soome  */
931*85280f08SToomas Soome #define	CIRCLEQ_EMPTY(head)		((head)->cqh_first == (void *)(head))
932*85280f08SToomas Soome #define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
933*85280f08SToomas Soome #define	CIRCLEQ_LAST(head)		((head)->cqh_last)
934*85280f08SToomas Soome #define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
935*85280f08SToomas Soome #define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
936*85280f08SToomas Soome 
937*85280f08SToomas Soome #define	CIRCLEQ_LOOP_NEXT(head, elm, field)				\
938*85280f08SToomas Soome 	(((elm)->field.cqe_next == (void *)(head))			\
939*85280f08SToomas Soome 	    ? ((head)->cqh_first)					\
940*85280f08SToomas Soome 	    : (elm->field.cqe_next))
941*85280f08SToomas Soome #define	CIRCLEQ_LOOP_PREV(head, elm, field)				\
942*85280f08SToomas Soome 	(((elm)->field.cqe_prev == (void *)(head))			\
943*85280f08SToomas Soome 	    ? ((head)->cqh_last)					\
944*85280f08SToomas Soome 	    : (elm->field.cqe_prev))
945*85280f08SToomas Soome 
946*85280f08SToomas Soome #define	CIRCLEQ_FOREACH(var, head, field)				\
947*85280f08SToomas Soome 	for ((var) = CIRCLEQ_FIRST((head));				\
948*85280f08SToomas Soome 		(var) != (void *)(head);				\
949*85280f08SToomas Soome 		(var) = CIRCLEQ_NEXT((var), field))
950*85280f08SToomas Soome 
951*85280f08SToomas Soome #define	CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
952*85280f08SToomas Soome 	for ((var) = CIRCLEQ_LAST((head));				\
953*85280f08SToomas Soome 		(var) != (void *)(head);				\
954*85280f08SToomas Soome 		(var) = CIRCLEQ_PREV((var), field))
955*85280f08SToomas Soome 
956*85280f08SToomas Soome /*
957381a2a9aSdr146992  * Circular queue functions.
958381a2a9aSdr146992  */
959381a2a9aSdr146992 #define	CIRCLEQ_INIT(head) do {						\
960381a2a9aSdr146992 	(head)->cqh_first = (void *)(head);				\
961381a2a9aSdr146992 	(head)->cqh_last = (void *)(head);				\
962381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
963381a2a9aSdr146992 } while (0)
964381a2a9aSdr146992 
965381a2a9aSdr146992 #define	CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
966381a2a9aSdr146992 	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
967381a2a9aSdr146992 	(elm)->field.cqe_prev = (listelm);				\
968381a2a9aSdr146992 	if ((listelm)->field.cqe_next == (void *)(head))		\
969381a2a9aSdr146992 		(head)->cqh_last = (elm);				\
970381a2a9aSdr146992 	else								\
971381a2a9aSdr146992 		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
972381a2a9aSdr146992 	(listelm)->field.cqe_next = (elm);				\
973381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
974381a2a9aSdr146992 } while (0)
975381a2a9aSdr146992 
976381a2a9aSdr146992 #define	CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
977381a2a9aSdr146992 	(elm)->field.cqe_next = (listelm);				\
978381a2a9aSdr146992 	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
979381a2a9aSdr146992 	if ((listelm)->field.cqe_prev == (void *)(head))		\
980381a2a9aSdr146992 		(head)->cqh_first = (elm);				\
981381a2a9aSdr146992 	else								\
982381a2a9aSdr146992 		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
983381a2a9aSdr146992 	(listelm)->field.cqe_prev = (elm);				\
984381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
985381a2a9aSdr146992 } while (0)
986381a2a9aSdr146992 
987381a2a9aSdr146992 #define	CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
988381a2a9aSdr146992 	(elm)->field.cqe_next = (head)->cqh_first;			\
989381a2a9aSdr146992 	(elm)->field.cqe_prev = (void *)(head);				\
990381a2a9aSdr146992 	if ((head)->cqh_last == (void *)(head))			\
991381a2a9aSdr146992 		(head)->cqh_last = (elm);				\
992381a2a9aSdr146992 	else								\
993381a2a9aSdr146992 		(head)->cqh_first->field.cqe_prev = (elm);		\
994381a2a9aSdr146992 	(head)->cqh_first = (elm);					\
995381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
996381a2a9aSdr146992 } while (0)
997381a2a9aSdr146992 
998381a2a9aSdr146992 #define	CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
999381a2a9aSdr146992 	(elm)->field.cqe_next = (void *)(head);				\
1000381a2a9aSdr146992 	(elm)->field.cqe_prev = (head)->cqh_last;			\
1001381a2a9aSdr146992 	if ((head)->cqh_first == (void *)(head))			\
1002381a2a9aSdr146992 		(head)->cqh_first = (elm);				\
1003381a2a9aSdr146992 	else								\
1004381a2a9aSdr146992 		(head)->cqh_last->field.cqe_next = (elm);		\
1005381a2a9aSdr146992 	(head)->cqh_last = (elm);					\
1006381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
1007381a2a9aSdr146992 } while (0)
1008381a2a9aSdr146992 
1009381a2a9aSdr146992 #define	CIRCLEQ_REMOVE(head, elm, field) do {				\
1010381a2a9aSdr146992 	if ((elm)->field.cqe_next == (void *)(head))			\
1011381a2a9aSdr146992 		(head)->cqh_last = (elm)->field.cqe_prev;		\
1012381a2a9aSdr146992 	else								\
1013381a2a9aSdr146992 		(elm)->field.cqe_next->field.cqe_prev =			\
1014381a2a9aSdr146992 		    (elm)->field.cqe_prev;				\
1015381a2a9aSdr146992 	if ((elm)->field.cqe_prev == (void *)(head))			\
1016381a2a9aSdr146992 		(head)->cqh_first = (elm)->field.cqe_next;		\
1017381a2a9aSdr146992 	else								\
1018381a2a9aSdr146992 		(elm)->field.cqe_prev->field.cqe_next =			\
1019381a2a9aSdr146992 		    (elm)->field.cqe_next;				\
1020381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
1021381a2a9aSdr146992 } while (0)
1022381a2a9aSdr146992 
1023381a2a9aSdr146992 #ifdef __cplusplus
1024381a2a9aSdr146992 }
1025381a2a9aSdr146992 #endif
1026381a2a9aSdr146992 
1027381a2a9aSdr146992 #endif	/* !_SYS_QUEUE_H */
1028