xref: /illumos-gate/usr/src/boot/sys/sys/queue.h (revision 199767f8)
1*199767f8SToomas Soome /*-
2*199767f8SToomas Soome  * Copyright (c) 1991, 1993
3*199767f8SToomas Soome  *	The Regents of the University of California.  All rights reserved.
4*199767f8SToomas Soome  *
5*199767f8SToomas Soome  * Redistribution and use in source and binary forms, with or without
6*199767f8SToomas Soome  * modification, are permitted provided that the following conditions
7*199767f8SToomas Soome  * are met:
8*199767f8SToomas Soome  * 1. Redistributions of source code must retain the above copyright
9*199767f8SToomas Soome  *    notice, this list of conditions and the following disclaimer.
10*199767f8SToomas Soome  * 2. Redistributions in binary form must reproduce the above copyright
11*199767f8SToomas Soome  *    notice, this list of conditions and the following disclaimer in the
12*199767f8SToomas Soome  *    documentation and/or other materials provided with the distribution.
13*199767f8SToomas Soome  * 4. Neither the name of the University nor the names of its contributors
14*199767f8SToomas Soome  *    may be used to endorse or promote products derived from this software
15*199767f8SToomas Soome  *    without specific prior written permission.
16*199767f8SToomas Soome  *
17*199767f8SToomas Soome  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18*199767f8SToomas Soome  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19*199767f8SToomas Soome  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20*199767f8SToomas Soome  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21*199767f8SToomas Soome  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22*199767f8SToomas Soome  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23*199767f8SToomas Soome  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24*199767f8SToomas Soome  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25*199767f8SToomas Soome  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26*199767f8SToomas Soome  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27*199767f8SToomas Soome  * SUCH DAMAGE.
28*199767f8SToomas Soome  *
29*199767f8SToomas Soome  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
30*199767f8SToomas Soome  * $FreeBSD$
31*199767f8SToomas Soome  */
32*199767f8SToomas Soome 
33*199767f8SToomas Soome #ifndef _SYS_QUEUE_H_
34*199767f8SToomas Soome #define	_SYS_QUEUE_H_
35*199767f8SToomas Soome 
36*199767f8SToomas Soome #include <sys/cdefs.h>
37*199767f8SToomas Soome 
38*199767f8SToomas Soome /*
39*199767f8SToomas Soome  * This file defines four types of data structures: singly-linked lists,
40*199767f8SToomas Soome  * singly-linked tail queues, lists and tail queues.
41*199767f8SToomas Soome  *
42*199767f8SToomas Soome  * A singly-linked list is headed by a single forward pointer. The elements
43*199767f8SToomas Soome  * are singly linked for minimum space and pointer manipulation overhead at
44*199767f8SToomas Soome  * the expense of O(n) removal for arbitrary elements. New elements can be
45*199767f8SToomas Soome  * added to the list after an existing element or at the head of the list.
46*199767f8SToomas Soome  * Elements being removed from the head of the list should use the explicit
47*199767f8SToomas Soome  * macro for this purpose for optimum efficiency. A singly-linked list may
48*199767f8SToomas Soome  * only be traversed in the forward direction.  Singly-linked lists are ideal
49*199767f8SToomas Soome  * for applications with large datasets and few or no removals or for
50*199767f8SToomas Soome  * implementing a LIFO queue.
51*199767f8SToomas Soome  *
52*199767f8SToomas Soome  * A singly-linked tail queue is headed by a pair of pointers, one to the
53*199767f8SToomas Soome  * head of the list and the other to the tail of the list. The elements are
54*199767f8SToomas Soome  * singly linked for minimum space and pointer manipulation overhead at the
55*199767f8SToomas Soome  * expense of O(n) removal for arbitrary elements. New elements can be added
56*199767f8SToomas Soome  * to the list after an existing element, at the head of the list, or at the
57*199767f8SToomas Soome  * end of the list. Elements being removed from the head of the tail queue
58*199767f8SToomas Soome  * should use the explicit macro for this purpose for optimum efficiency.
59*199767f8SToomas Soome  * A singly-linked tail queue may only be traversed in the forward direction.
60*199767f8SToomas Soome  * Singly-linked tail queues are ideal for applications with large datasets
61*199767f8SToomas Soome  * and few or no removals or for implementing a FIFO queue.
62*199767f8SToomas Soome  *
63*199767f8SToomas Soome  * A list is headed by a single forward pointer (or an array of forward
64*199767f8SToomas Soome  * pointers for a hash table header). The elements are doubly linked
65*199767f8SToomas Soome  * so that an arbitrary element can be removed without a need to
66*199767f8SToomas Soome  * traverse the list. New elements can be added to the list before
67*199767f8SToomas Soome  * or after an existing element or at the head of the list. A list
68*199767f8SToomas Soome  * may be traversed in either direction.
69*199767f8SToomas Soome  *
70*199767f8SToomas Soome  * A tail queue is headed by a pair of pointers, one to the head of the
71*199767f8SToomas Soome  * list and the other to the tail of the list. The elements are doubly
72*199767f8SToomas Soome  * linked so that an arbitrary element can be removed without a need to
73*199767f8SToomas Soome  * traverse the list. New elements can be added to the list before or
74*199767f8SToomas Soome  * after an existing element, at the head of the list, or at the end of
75*199767f8SToomas Soome  * the list. A tail queue may be traversed in either direction.
76*199767f8SToomas Soome  *
77*199767f8SToomas Soome  * For details on the use of these macros, see the queue(3) manual page.
78*199767f8SToomas Soome  *
79*199767f8SToomas Soome  *
80*199767f8SToomas Soome  *				SLIST	LIST	STAILQ	TAILQ
81*199767f8SToomas Soome  * _HEAD			+	+	+	+
82*199767f8SToomas Soome  * _CLASS_HEAD			+	+	+	+
83*199767f8SToomas Soome  * _HEAD_INITIALIZER		+	+	+	+
84*199767f8SToomas Soome  * _ENTRY			+	+	+	+
85*199767f8SToomas Soome  * _CLASS_ENTRY			+	+	+	+
86*199767f8SToomas Soome  * _INIT			+	+	+	+
87*199767f8SToomas Soome  * _EMPTY			+	+	+	+
88*199767f8SToomas Soome  * _FIRST			+	+	+	+
89*199767f8SToomas Soome  * _NEXT			+	+	+	+
90*199767f8SToomas Soome  * _PREV			-	+	-	+
91*199767f8SToomas Soome  * _LAST			-	-	+	+
92*199767f8SToomas Soome  * _FOREACH			+	+	+	+
93*199767f8SToomas Soome  * _FOREACH_FROM		+	+	+	+
94*199767f8SToomas Soome  * _FOREACH_SAFE		+	+	+	+
95*199767f8SToomas Soome  * _FOREACH_FROM_SAFE		+	+	+	+
96*199767f8SToomas Soome  * _FOREACH_REVERSE		-	-	-	+
97*199767f8SToomas Soome  * _FOREACH_REVERSE_FROM	-	-	-	+
98*199767f8SToomas Soome  * _FOREACH_REVERSE_SAFE	-	-	-	+
99*199767f8SToomas Soome  * _FOREACH_REVERSE_FROM_SAFE	-	-	-	+
100*199767f8SToomas Soome  * _INSERT_HEAD			+	+	+	+
101*199767f8SToomas Soome  * _INSERT_BEFORE		-	+	-	+
102*199767f8SToomas Soome  * _INSERT_AFTER		+	+	+	+
103*199767f8SToomas Soome  * _INSERT_TAIL			-	-	+	+
104*199767f8SToomas Soome  * _CONCAT			-	-	+	+
105*199767f8SToomas Soome  * _REMOVE_AFTER		+	-	+	-
106*199767f8SToomas Soome  * _REMOVE_HEAD			+	-	+	-
107*199767f8SToomas Soome  * _REMOVE			+	+	+	+
108*199767f8SToomas Soome  * _SWAP			+	+	+	+
109*199767f8SToomas Soome  *
110*199767f8SToomas Soome  */
111*199767f8SToomas Soome #ifdef QUEUE_MACRO_DEBUG
112*199767f8SToomas Soome /* Store the last 2 places the queue element or head was altered */
113*199767f8SToomas Soome struct qm_trace {
114*199767f8SToomas Soome 	unsigned long	 lastline;
115*199767f8SToomas Soome 	unsigned long	 prevline;
116*199767f8SToomas Soome 	const char	*lastfile;
117*199767f8SToomas Soome 	const char	*prevfile;
118*199767f8SToomas Soome };
119*199767f8SToomas Soome 
120*199767f8SToomas Soome #define	TRACEBUF	struct qm_trace trace;
121*199767f8SToomas Soome #define	TRACEBUF_INITIALIZER	{ __LINE__, 0, __FILE__, NULL } ,
122*199767f8SToomas Soome #define	TRASHIT(x)	do {(x) = (void *)-1;} while (0)
123*199767f8SToomas Soome #define	QMD_SAVELINK(name, link)	void **name = (void *)&(link)
124*199767f8SToomas Soome 
125*199767f8SToomas Soome #define	QMD_TRACE_HEAD(head) do {					\
126*199767f8SToomas Soome 	(head)->trace.prevline = (head)->trace.lastline;		\
127*199767f8SToomas Soome 	(head)->trace.prevfile = (head)->trace.lastfile;		\
128*199767f8SToomas Soome 	(head)->trace.lastline = __LINE__;				\
129*199767f8SToomas Soome 	(head)->trace.lastfile = __FILE__;				\
130*199767f8SToomas Soome } while (0)
131*199767f8SToomas Soome 
132*199767f8SToomas Soome #define	QMD_TRACE_ELEM(elem) do {					\
133*199767f8SToomas Soome 	(elem)->trace.prevline = (elem)->trace.lastline;		\
134*199767f8SToomas Soome 	(elem)->trace.prevfile = (elem)->trace.lastfile;		\
135*199767f8SToomas Soome 	(elem)->trace.lastline = __LINE__;				\
136*199767f8SToomas Soome 	(elem)->trace.lastfile = __FILE__;				\
137*199767f8SToomas Soome } while (0)
138*199767f8SToomas Soome 
139*199767f8SToomas Soome #else
140*199767f8SToomas Soome #define	QMD_TRACE_ELEM(elem)
141*199767f8SToomas Soome #define	QMD_TRACE_HEAD(head)
142*199767f8SToomas Soome #define	QMD_SAVELINK(name, link)
143*199767f8SToomas Soome #define	TRACEBUF
144*199767f8SToomas Soome #define	TRACEBUF_INITIALIZER
145*199767f8SToomas Soome #define	TRASHIT(x)
146*199767f8SToomas Soome #endif	/* QUEUE_MACRO_DEBUG */
147*199767f8SToomas Soome 
148*199767f8SToomas Soome #ifdef __cplusplus
149*199767f8SToomas Soome /*
150*199767f8SToomas Soome  * In C++ there can be structure lists and class lists:
151*199767f8SToomas Soome  */
152*199767f8SToomas Soome #define	QUEUE_TYPEOF(type) type
153*199767f8SToomas Soome #else
154*199767f8SToomas Soome #define	QUEUE_TYPEOF(type) struct type
155*199767f8SToomas Soome #endif
156*199767f8SToomas Soome 
157*199767f8SToomas Soome /*
158*199767f8SToomas Soome  * Singly-linked List declarations.
159*199767f8SToomas Soome  */
160*199767f8SToomas Soome #define	SLIST_HEAD(name, type)						\
161*199767f8SToomas Soome struct name {								\
162*199767f8SToomas Soome 	struct type *slh_first;	/* first element */			\
163*199767f8SToomas Soome }
164*199767f8SToomas Soome 
165*199767f8SToomas Soome #define	SLIST_CLASS_HEAD(name, type)					\
166*199767f8SToomas Soome struct name {								\
167*199767f8SToomas Soome 	class type *slh_first;	/* first element */			\
168*199767f8SToomas Soome }
169*199767f8SToomas Soome 
170*199767f8SToomas Soome #define	SLIST_HEAD_INITIALIZER(head)					\
171*199767f8SToomas Soome 	{ NULL }
172*199767f8SToomas Soome 
173*199767f8SToomas Soome #define	SLIST_ENTRY(type)						\
174*199767f8SToomas Soome struct {								\
175*199767f8SToomas Soome 	struct type *sle_next;	/* next element */			\
176*199767f8SToomas Soome }
177*199767f8SToomas Soome 
178*199767f8SToomas Soome #define	SLIST_CLASS_ENTRY(type)						\
179*199767f8SToomas Soome struct {								\
180*199767f8SToomas Soome 	class type *sle_next;		/* next element */		\
181*199767f8SToomas Soome }
182*199767f8SToomas Soome 
183*199767f8SToomas Soome /*
184*199767f8SToomas Soome  * Singly-linked List functions.
185*199767f8SToomas Soome  */
186*199767f8SToomas Soome #define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
187*199767f8SToomas Soome 
188*199767f8SToomas Soome #define	SLIST_FIRST(head)	((head)->slh_first)
189*199767f8SToomas Soome 
190*199767f8SToomas Soome #define	SLIST_FOREACH(var, head, field)					\
191*199767f8SToomas Soome 	for ((var) = SLIST_FIRST((head));				\
192*199767f8SToomas Soome 	    (var);							\
193*199767f8SToomas Soome 	    (var) = SLIST_NEXT((var), field))
194*199767f8SToomas Soome 
195*199767f8SToomas Soome #define	SLIST_FOREACH_FROM(var, head, field)				\
196*199767f8SToomas Soome 	for ((var) = ((var) ? (var) : SLIST_FIRST((head)));		\
197*199767f8SToomas Soome 	    (var);							\
198*199767f8SToomas Soome 	    (var) = SLIST_NEXT((var), field))
199*199767f8SToomas Soome 
200*199767f8SToomas Soome #define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
201*199767f8SToomas Soome 	for ((var) = SLIST_FIRST((head));				\
202*199767f8SToomas Soome 	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);		\
203*199767f8SToomas Soome 	    (var) = (tvar))
204*199767f8SToomas Soome 
205*199767f8SToomas Soome #define	SLIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
206*199767f8SToomas Soome 	for ((var) = ((var) ? (var) : SLIST_FIRST((head)));		\
207*199767f8SToomas Soome 	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);		\
208*199767f8SToomas Soome 	    (var) = (tvar))
209*199767f8SToomas Soome 
210*199767f8SToomas Soome #define	SLIST_FOREACH_PREVPTR(var, varp, head, field)			\
211*199767f8SToomas Soome 	for ((varp) = &SLIST_FIRST((head));				\
212*199767f8SToomas Soome 	    ((var) = *(varp)) != NULL;					\
213*199767f8SToomas Soome 	    (varp) = &SLIST_NEXT((var), field))
214*199767f8SToomas Soome 
215*199767f8SToomas Soome #define	SLIST_INIT(head) do {						\
216*199767f8SToomas Soome 	SLIST_FIRST((head)) = NULL;					\
217*199767f8SToomas Soome } while (0)
218*199767f8SToomas Soome 
219*199767f8SToomas Soome #define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
220*199767f8SToomas Soome 	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);	\
221*199767f8SToomas Soome 	SLIST_NEXT((slistelm), field) = (elm);				\
222*199767f8SToomas Soome } while (0)
223*199767f8SToomas Soome 
224*199767f8SToomas Soome #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
225*199767f8SToomas Soome 	SLIST_NEXT((elm), field) = SLIST_FIRST((head));			\
226*199767f8SToomas Soome 	SLIST_FIRST((head)) = (elm);					\
227*199767f8SToomas Soome } while (0)
228*199767f8SToomas Soome 
229*199767f8SToomas Soome #define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
230*199767f8SToomas Soome 
231*199767f8SToomas Soome #define	SLIST_REMOVE(head, elm, type, field) do {			\
232*199767f8SToomas Soome 	QMD_SAVELINK(oldnext, (elm)->field.sle_next);			\
233*199767f8SToomas Soome 	if (SLIST_FIRST((head)) == (elm)) {				\
234*199767f8SToomas Soome 		SLIST_REMOVE_HEAD((head), field);			\
235*199767f8SToomas Soome 	}								\
236*199767f8SToomas Soome 	else {								\
237*199767f8SToomas Soome 		QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head);		\
238*199767f8SToomas Soome 		while (SLIST_NEXT(curelm, field) != (elm))		\
239*199767f8SToomas Soome 			curelm = SLIST_NEXT(curelm, field);		\
240*199767f8SToomas Soome 		SLIST_REMOVE_AFTER(curelm, field);			\
241*199767f8SToomas Soome 	}								\
242*199767f8SToomas Soome 	TRASHIT(*oldnext);						\
243*199767f8SToomas Soome } while (0)
244*199767f8SToomas Soome 
245*199767f8SToomas Soome #define SLIST_REMOVE_AFTER(elm, field) do {				\
246*199767f8SToomas Soome 	SLIST_NEXT(elm, field) =					\
247*199767f8SToomas Soome 	    SLIST_NEXT(SLIST_NEXT(elm, field), field);			\
248*199767f8SToomas Soome } while (0)
249*199767f8SToomas Soome 
250*199767f8SToomas Soome #define	SLIST_REMOVE_HEAD(head, field) do {				\
251*199767f8SToomas Soome 	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
252*199767f8SToomas Soome } while (0)
253*199767f8SToomas Soome 
254*199767f8SToomas Soome #define SLIST_SWAP(head1, head2, type) do {				\
255*199767f8SToomas Soome 	QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1);		\
256*199767f8SToomas Soome 	SLIST_FIRST(head1) = SLIST_FIRST(head2);			\
257*199767f8SToomas Soome 	SLIST_FIRST(head2) = swap_first;				\
258*199767f8SToomas Soome } while (0)
259*199767f8SToomas Soome 
260*199767f8SToomas Soome /*
261*199767f8SToomas Soome  * Singly-linked Tail queue declarations.
262*199767f8SToomas Soome  */
263*199767f8SToomas Soome #define	STAILQ_HEAD(name, type)						\
264*199767f8SToomas Soome struct name {								\
265*199767f8SToomas Soome 	struct type *stqh_first;/* first element */			\
266*199767f8SToomas Soome 	struct type **stqh_last;/* addr of last next element */		\
267*199767f8SToomas Soome }
268*199767f8SToomas Soome 
269*199767f8SToomas Soome #define	STAILQ_CLASS_HEAD(name, type)					\
270*199767f8SToomas Soome struct name {								\
271*199767f8SToomas Soome 	class type *stqh_first;	/* first element */			\
272*199767f8SToomas Soome 	class type **stqh_last;	/* addr of last next element */		\
273*199767f8SToomas Soome }
274*199767f8SToomas Soome 
275*199767f8SToomas Soome #define	STAILQ_HEAD_INITIALIZER(head)					\
276*199767f8SToomas Soome 	{ NULL, &(head).stqh_first }
277*199767f8SToomas Soome 
278*199767f8SToomas Soome #define	STAILQ_ENTRY(type)						\
279*199767f8SToomas Soome struct {								\
280*199767f8SToomas Soome 	struct type *stqe_next;	/* next element */			\
281*199767f8SToomas Soome }
282*199767f8SToomas Soome 
283*199767f8SToomas Soome #define	STAILQ_CLASS_ENTRY(type)					\
284*199767f8SToomas Soome struct {								\
285*199767f8SToomas Soome 	class type *stqe_next;	/* next element */			\
286*199767f8SToomas Soome }
287*199767f8SToomas Soome 
288*199767f8SToomas Soome /*
289*199767f8SToomas Soome  * Singly-linked Tail queue functions.
290*199767f8SToomas Soome  */
291*199767f8SToomas Soome #define	STAILQ_CONCAT(head1, head2) do {				\
292*199767f8SToomas Soome 	if (!STAILQ_EMPTY((head2))) {					\
293*199767f8SToomas Soome 		*(head1)->stqh_last = (head2)->stqh_first;		\
294*199767f8SToomas Soome 		(head1)->stqh_last = (head2)->stqh_last;		\
295*199767f8SToomas Soome 		STAILQ_INIT((head2));					\
296*199767f8SToomas Soome 	}								\
297*199767f8SToomas Soome } while (0)
298*199767f8SToomas Soome 
299*199767f8SToomas Soome #define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)
300*199767f8SToomas Soome 
301*199767f8SToomas Soome #define	STAILQ_FIRST(head)	((head)->stqh_first)
302*199767f8SToomas Soome 
303*199767f8SToomas Soome #define	STAILQ_FOREACH(var, head, field)				\
304*199767f8SToomas Soome 	for((var) = STAILQ_FIRST((head));				\
305*199767f8SToomas Soome 	   (var);							\
306*199767f8SToomas Soome 	   (var) = STAILQ_NEXT((var), field))
307*199767f8SToomas Soome 
308*199767f8SToomas Soome #define	STAILQ_FOREACH_FROM(var, head, field)				\
309*199767f8SToomas Soome 	for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));		\
310*199767f8SToomas Soome 	   (var);							\
311*199767f8SToomas Soome 	   (var) = STAILQ_NEXT((var), field))
312*199767f8SToomas Soome 
313*199767f8SToomas Soome #define	STAILQ_FOREACH_SAFE(var, head, field, tvar)			\
314*199767f8SToomas Soome 	for ((var) = STAILQ_FIRST((head));				\
315*199767f8SToomas Soome 	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\
316*199767f8SToomas Soome 	    (var) = (tvar))
317*199767f8SToomas Soome 
318*199767f8SToomas Soome #define	STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)		\
319*199767f8SToomas Soome 	for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));		\
320*199767f8SToomas Soome 	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\
321*199767f8SToomas Soome 	    (var) = (tvar))
322*199767f8SToomas Soome 
323*199767f8SToomas Soome #define	STAILQ_INIT(head) do {						\
324*199767f8SToomas Soome 	STAILQ_FIRST((head)) = NULL;					\
325*199767f8SToomas Soome 	(head)->stqh_last = &STAILQ_FIRST((head));			\
326*199767f8SToomas Soome } while (0)
327*199767f8SToomas Soome 
328*199767f8SToomas Soome #define	STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\
329*199767f8SToomas Soome 	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
330*199767f8SToomas Soome 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
331*199767f8SToomas Soome 	STAILQ_NEXT((tqelm), field) = (elm);				\
332*199767f8SToomas Soome } while (0)
333*199767f8SToomas Soome 
334*199767f8SToomas Soome #define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
335*199767f8SToomas Soome 	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)	\
336*199767f8SToomas Soome 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
337*199767f8SToomas Soome 	STAILQ_FIRST((head)) = (elm);					\
338*199767f8SToomas Soome } while (0)
339*199767f8SToomas Soome 
340*199767f8SToomas Soome #define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
341*199767f8SToomas Soome 	STAILQ_NEXT((elm), field) = NULL;				\
342*199767f8SToomas Soome 	*(head)->stqh_last = (elm);					\
343*199767f8SToomas Soome 	(head)->stqh_last = &STAILQ_NEXT((elm), field);			\
344*199767f8SToomas Soome } while (0)
345*199767f8SToomas Soome 
346*199767f8SToomas Soome #define	STAILQ_LAST(head, type, field)				\
347*199767f8SToomas Soome 	(STAILQ_EMPTY((head)) ? NULL :				\
348*199767f8SToomas Soome 	    __containerof((head)->stqh_last,			\
349*199767f8SToomas Soome 	    QUEUE_TYPEOF(type), field.stqe_next))
350*199767f8SToomas Soome 
351*199767f8SToomas Soome #define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
352*199767f8SToomas Soome 
353*199767f8SToomas Soome #define	STAILQ_REMOVE(head, elm, type, field) do {			\
354*199767f8SToomas Soome 	QMD_SAVELINK(oldnext, (elm)->field.stqe_next);			\
355*199767f8SToomas Soome 	if (STAILQ_FIRST((head)) == (elm)) {				\
356*199767f8SToomas Soome 		STAILQ_REMOVE_HEAD((head), field);			\
357*199767f8SToomas Soome 	}								\
358*199767f8SToomas Soome 	else {								\
359*199767f8SToomas Soome 		QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head);	\
360*199767f8SToomas Soome 		while (STAILQ_NEXT(curelm, field) != (elm))		\
361*199767f8SToomas Soome 			curelm = STAILQ_NEXT(curelm, field);		\
362*199767f8SToomas Soome 		STAILQ_REMOVE_AFTER(head, curelm, field);		\
363*199767f8SToomas Soome 	}								\
364*199767f8SToomas Soome 	TRASHIT(*oldnext);						\
365*199767f8SToomas Soome } while (0)
366*199767f8SToomas Soome 
367*199767f8SToomas Soome #define STAILQ_REMOVE_AFTER(head, elm, field) do {			\
368*199767f8SToomas Soome 	if ((STAILQ_NEXT(elm, field) =					\
369*199767f8SToomas Soome 	     STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)	\
370*199767f8SToomas Soome 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
371*199767f8SToomas Soome } while (0)
372*199767f8SToomas Soome 
373*199767f8SToomas Soome #define	STAILQ_REMOVE_HEAD(head, field) do {				\
374*199767f8SToomas Soome 	if ((STAILQ_FIRST((head)) =					\
375*199767f8SToomas Soome 	     STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)		\
376*199767f8SToomas Soome 		(head)->stqh_last = &STAILQ_FIRST((head));		\
377*199767f8SToomas Soome } while (0)
378*199767f8SToomas Soome 
379*199767f8SToomas Soome #define STAILQ_SWAP(head1, head2, type) do {				\
380*199767f8SToomas Soome 	QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1);		\
381*199767f8SToomas Soome 	QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last;		\
382*199767f8SToomas Soome 	STAILQ_FIRST(head1) = STAILQ_FIRST(head2);			\
383*199767f8SToomas Soome 	(head1)->stqh_last = (head2)->stqh_last;			\
384*199767f8SToomas Soome 	STAILQ_FIRST(head2) = swap_first;				\
385*199767f8SToomas Soome 	(head2)->stqh_last = swap_last;					\
386*199767f8SToomas Soome 	if (STAILQ_EMPTY(head1))					\
387*199767f8SToomas Soome 		(head1)->stqh_last = &STAILQ_FIRST(head1);		\
388*199767f8SToomas Soome 	if (STAILQ_EMPTY(head2))					\
389*199767f8SToomas Soome 		(head2)->stqh_last = &STAILQ_FIRST(head2);		\
390*199767f8SToomas Soome } while (0)
391*199767f8SToomas Soome 
392*199767f8SToomas Soome 
393*199767f8SToomas Soome /*
394*199767f8SToomas Soome  * List declarations.
395*199767f8SToomas Soome  */
396*199767f8SToomas Soome #define	LIST_HEAD(name, type)						\
397*199767f8SToomas Soome struct name {								\
398*199767f8SToomas Soome 	struct type *lh_first;	/* first element */			\
399*199767f8SToomas Soome }
400*199767f8SToomas Soome 
401*199767f8SToomas Soome #define	LIST_CLASS_HEAD(name, type)					\
402*199767f8SToomas Soome struct name {								\
403*199767f8SToomas Soome 	class type *lh_first;	/* first element */			\
404*199767f8SToomas Soome }
405*199767f8SToomas Soome 
406*199767f8SToomas Soome #define	LIST_HEAD_INITIALIZER(head)					\
407*199767f8SToomas Soome 	{ NULL }
408*199767f8SToomas Soome 
409*199767f8SToomas Soome #define	LIST_ENTRY(type)						\
410*199767f8SToomas Soome struct {								\
411*199767f8SToomas Soome 	struct type *le_next;	/* next element */			\
412*199767f8SToomas Soome 	struct type **le_prev;	/* address of previous next element */	\
413*199767f8SToomas Soome }
414*199767f8SToomas Soome 
415*199767f8SToomas Soome #define	LIST_CLASS_ENTRY(type)						\
416*199767f8SToomas Soome struct {								\
417*199767f8SToomas Soome 	class type *le_next;	/* next element */			\
418*199767f8SToomas Soome 	class type **le_prev;	/* address of previous next element */	\
419*199767f8SToomas Soome }
420*199767f8SToomas Soome 
421*199767f8SToomas Soome /*
422*199767f8SToomas Soome  * List functions.
423*199767f8SToomas Soome  */
424*199767f8SToomas Soome 
425*199767f8SToomas Soome #if (defined(_KERNEL) && defined(INVARIANTS))
426*199767f8SToomas Soome #define	QMD_LIST_CHECK_HEAD(head, field) do {				\
427*199767f8SToomas Soome 	if (LIST_FIRST((head)) != NULL &&				\
428*199767f8SToomas Soome 	    LIST_FIRST((head))->field.le_prev !=			\
429*199767f8SToomas Soome 	     &LIST_FIRST((head)))					\
430*199767f8SToomas Soome 		panic("Bad list head %p first->prev != head", (head));	\
431*199767f8SToomas Soome } while (0)
432*199767f8SToomas Soome 
433*199767f8SToomas Soome #define	QMD_LIST_CHECK_NEXT(elm, field) do {				\
434*199767f8SToomas Soome 	if (LIST_NEXT((elm), field) != NULL &&				\
435*199767f8SToomas Soome 	    LIST_NEXT((elm), field)->field.le_prev !=			\
436*199767f8SToomas Soome 	     &((elm)->field.le_next))					\
437*199767f8SToomas Soome 	     	panic("Bad link elm %p next->prev != elm", (elm));	\
438*199767f8SToomas Soome } while (0)
439*199767f8SToomas Soome 
440*199767f8SToomas Soome #define	QMD_LIST_CHECK_PREV(elm, field) do {				\
441*199767f8SToomas Soome 	if (*(elm)->field.le_prev != (elm))				\
442*199767f8SToomas Soome 		panic("Bad link elm %p prev->next != elm", (elm));	\
443*199767f8SToomas Soome } while (0)
444*199767f8SToomas Soome #else
445*199767f8SToomas Soome #define	QMD_LIST_CHECK_HEAD(head, field)
446*199767f8SToomas Soome #define	QMD_LIST_CHECK_NEXT(elm, field)
447*199767f8SToomas Soome #define	QMD_LIST_CHECK_PREV(elm, field)
448*199767f8SToomas Soome #endif /* (_KERNEL && INVARIANTS) */
449*199767f8SToomas Soome 
450*199767f8SToomas Soome #define	LIST_EMPTY(head)	((head)->lh_first == NULL)
451*199767f8SToomas Soome 
452*199767f8SToomas Soome #define	LIST_FIRST(head)	((head)->lh_first)
453*199767f8SToomas Soome 
454*199767f8SToomas Soome #define	LIST_FOREACH(var, head, field)					\
455*199767f8SToomas Soome 	for ((var) = LIST_FIRST((head));				\
456*199767f8SToomas Soome 	    (var);							\
457*199767f8SToomas Soome 	    (var) = LIST_NEXT((var), field))
458*199767f8SToomas Soome 
459*199767f8SToomas Soome #define	LIST_FOREACH_FROM(var, head, field)				\
460*199767f8SToomas Soome 	for ((var) = ((var) ? (var) : LIST_FIRST((head)));		\
461*199767f8SToomas Soome 	    (var);							\
462*199767f8SToomas Soome 	    (var) = LIST_NEXT((var), field))
463*199767f8SToomas Soome 
464*199767f8SToomas Soome #define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
465*199767f8SToomas Soome 	for ((var) = LIST_FIRST((head));				\
466*199767f8SToomas Soome 	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\
467*199767f8SToomas Soome 	    (var) = (tvar))
468*199767f8SToomas Soome 
469*199767f8SToomas Soome #define	LIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
470*199767f8SToomas Soome 	for ((var) = ((var) ? (var) : LIST_FIRST((head)));		\
471*199767f8SToomas Soome 	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\
472*199767f8SToomas Soome 	    (var) = (tvar))
473*199767f8SToomas Soome 
474*199767f8SToomas Soome #define	LIST_INIT(head) do {						\
475*199767f8SToomas Soome 	LIST_FIRST((head)) = NULL;					\
476*199767f8SToomas Soome } while (0)
477*199767f8SToomas Soome 
478*199767f8SToomas Soome #define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
479*199767f8SToomas Soome 	QMD_LIST_CHECK_NEXT(listelm, field);				\
480*199767f8SToomas Soome 	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
481*199767f8SToomas Soome 		LIST_NEXT((listelm), field)->field.le_prev =		\
482*199767f8SToomas Soome 		    &LIST_NEXT((elm), field);				\
483*199767f8SToomas Soome 	LIST_NEXT((listelm), field) = (elm);				\
484*199767f8SToomas Soome 	(elm)->field.le_prev = &LIST_NEXT((listelm), field);		\
485*199767f8SToomas Soome } while (0)
486*199767f8SToomas Soome 
487*199767f8SToomas Soome #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
488*199767f8SToomas Soome 	QMD_LIST_CHECK_PREV(listelm, field);				\
489*199767f8SToomas Soome 	(elm)->field.le_prev = (listelm)->field.le_prev;		\
490*199767f8SToomas Soome 	LIST_NEXT((elm), field) = (listelm);				\
491*199767f8SToomas Soome 	*(listelm)->field.le_prev = (elm);				\
492*199767f8SToomas Soome 	(listelm)->field.le_prev = &LIST_NEXT((elm), field);		\
493*199767f8SToomas Soome } while (0)
494*199767f8SToomas Soome 
495*199767f8SToomas Soome #define	LIST_INSERT_HEAD(head, elm, field) do {				\
496*199767f8SToomas Soome 	QMD_LIST_CHECK_HEAD((head), field);				\
497*199767f8SToomas Soome 	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\
498*199767f8SToomas Soome 		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
499*199767f8SToomas Soome 	LIST_FIRST((head)) = (elm);					\
500*199767f8SToomas Soome 	(elm)->field.le_prev = &LIST_FIRST((head));			\
501*199767f8SToomas Soome } while (0)
502*199767f8SToomas Soome 
503*199767f8SToomas Soome #define	LIST_NEXT(elm, field)	((elm)->field.le_next)
504*199767f8SToomas Soome 
505*199767f8SToomas Soome #define	LIST_PREV(elm, head, type, field)			\
506*199767f8SToomas Soome 	((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL :	\
507*199767f8SToomas Soome 	    __containerof((elm)->field.le_prev,			\
508*199767f8SToomas Soome 	    QUEUE_TYPEOF(type), field.le_next))
509*199767f8SToomas Soome 
510*199767f8SToomas Soome #define	LIST_REMOVE(elm, field) do {					\
511*199767f8SToomas Soome 	QMD_SAVELINK(oldnext, (elm)->field.le_next);			\
512*199767f8SToomas Soome 	QMD_SAVELINK(oldprev, (elm)->field.le_prev);			\
513*199767f8SToomas Soome 	QMD_LIST_CHECK_NEXT(elm, field);				\
514*199767f8SToomas Soome 	QMD_LIST_CHECK_PREV(elm, field);				\
515*199767f8SToomas Soome 	if (LIST_NEXT((elm), field) != NULL)				\
516*199767f8SToomas Soome 		LIST_NEXT((elm), field)->field.le_prev = 		\
517*199767f8SToomas Soome 		    (elm)->field.le_prev;				\
518*199767f8SToomas Soome 	*(elm)->field.le_prev = LIST_NEXT((elm), field);		\
519*199767f8SToomas Soome 	TRASHIT(*oldnext);						\
520*199767f8SToomas Soome 	TRASHIT(*oldprev);						\
521*199767f8SToomas Soome } while (0)
522*199767f8SToomas Soome 
523*199767f8SToomas Soome #define LIST_SWAP(head1, head2, type, field) do {			\
524*199767f8SToomas Soome 	QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1);		\
525*199767f8SToomas Soome 	LIST_FIRST((head1)) = LIST_FIRST((head2));			\
526*199767f8SToomas Soome 	LIST_FIRST((head2)) = swap_tmp;					\
527*199767f8SToomas Soome 	if ((swap_tmp = LIST_FIRST((head1))) != NULL)			\
528*199767f8SToomas Soome 		swap_tmp->field.le_prev = &LIST_FIRST((head1));		\
529*199767f8SToomas Soome 	if ((swap_tmp = LIST_FIRST((head2))) != NULL)			\
530*199767f8SToomas Soome 		swap_tmp->field.le_prev = &LIST_FIRST((head2));		\
531*199767f8SToomas Soome } while (0)
532*199767f8SToomas Soome 
533*199767f8SToomas Soome /*
534*199767f8SToomas Soome  * Tail queue declarations.
535*199767f8SToomas Soome  */
536*199767f8SToomas Soome #define	TAILQ_HEAD(name, type)						\
537*199767f8SToomas Soome struct name {								\
538*199767f8SToomas Soome 	struct type *tqh_first;	/* first element */			\
539*199767f8SToomas Soome 	struct type **tqh_last;	/* addr of last next element */		\
540*199767f8SToomas Soome 	TRACEBUF							\
541*199767f8SToomas Soome }
542*199767f8SToomas Soome 
543*199767f8SToomas Soome #define	TAILQ_CLASS_HEAD(name, type)					\
544*199767f8SToomas Soome struct name {								\
545*199767f8SToomas Soome 	class type *tqh_first;	/* first element */			\
546*199767f8SToomas Soome 	class type **tqh_last;	/* addr of last next element */		\
547*199767f8SToomas Soome 	TRACEBUF							\
548*199767f8SToomas Soome }
549*199767f8SToomas Soome 
550*199767f8SToomas Soome #define	TAILQ_HEAD_INITIALIZER(head)					\
551*199767f8SToomas Soome 	{ NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
552*199767f8SToomas Soome 
553*199767f8SToomas Soome #define	TAILQ_ENTRY(type)						\
554*199767f8SToomas Soome struct {								\
555*199767f8SToomas Soome 	struct type *tqe_next;	/* next element */			\
556*199767f8SToomas Soome 	struct type **tqe_prev;	/* address of previous next element */	\
557*199767f8SToomas Soome 	TRACEBUF							\
558*199767f8SToomas Soome }
559*199767f8SToomas Soome 
560*199767f8SToomas Soome #define	TAILQ_CLASS_ENTRY(type)						\
561*199767f8SToomas Soome struct {								\
562*199767f8SToomas Soome 	class type *tqe_next;	/* next element */			\
563*199767f8SToomas Soome 	class type **tqe_prev;	/* address of previous next element */	\
564*199767f8SToomas Soome 	TRACEBUF							\
565*199767f8SToomas Soome }
566*199767f8SToomas Soome 
567*199767f8SToomas Soome /*
568*199767f8SToomas Soome  * Tail queue functions.
569*199767f8SToomas Soome  */
570*199767f8SToomas Soome #if (defined(_KERNEL) && defined(INVARIANTS))
571*199767f8SToomas Soome #define	QMD_TAILQ_CHECK_HEAD(head, field) do {				\
572*199767f8SToomas Soome 	if (!TAILQ_EMPTY(head) &&					\
573*199767f8SToomas Soome 	    TAILQ_FIRST((head))->field.tqe_prev !=			\
574*199767f8SToomas Soome 	     &TAILQ_FIRST((head)))					\
575*199767f8SToomas Soome 		panic("Bad tailq head %p first->prev != head", (head));	\
576*199767f8SToomas Soome } while (0)
577*199767f8SToomas Soome 
578*199767f8SToomas Soome #define	QMD_TAILQ_CHECK_TAIL(head, field) do {				\
579*199767f8SToomas Soome 	if (*(head)->tqh_last != NULL)					\
580*199767f8SToomas Soome 	    	panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); 	\
581*199767f8SToomas Soome } while (0)
582*199767f8SToomas Soome 
583*199767f8SToomas Soome #define	QMD_TAILQ_CHECK_NEXT(elm, field) do {				\
584*199767f8SToomas Soome 	if (TAILQ_NEXT((elm), field) != NULL &&				\
585*199767f8SToomas Soome 	    TAILQ_NEXT((elm), field)->field.tqe_prev !=			\
586*199767f8SToomas Soome 	     &((elm)->field.tqe_next))					\
587*199767f8SToomas Soome 		panic("Bad link elm %p next->prev != elm", (elm));	\
588*199767f8SToomas Soome } while (0)
589*199767f8SToomas Soome 
590*199767f8SToomas Soome #define	QMD_TAILQ_CHECK_PREV(elm, field) do {				\
591*199767f8SToomas Soome 	if (*(elm)->field.tqe_prev != (elm))				\
592*199767f8SToomas Soome 		panic("Bad link elm %p prev->next != elm", (elm));	\
593*199767f8SToomas Soome } while (0)
594*199767f8SToomas Soome #else
595*199767f8SToomas Soome #define	QMD_TAILQ_CHECK_HEAD(head, field)
596*199767f8SToomas Soome #define	QMD_TAILQ_CHECK_TAIL(head, headname)
597*199767f8SToomas Soome #define	QMD_TAILQ_CHECK_NEXT(elm, field)
598*199767f8SToomas Soome #define	QMD_TAILQ_CHECK_PREV(elm, field)
599*199767f8SToomas Soome #endif /* (_KERNEL && INVARIANTS) */
600*199767f8SToomas Soome 
601*199767f8SToomas Soome #define	TAILQ_CONCAT(head1, head2, field) do {				\
602*199767f8SToomas Soome 	if (!TAILQ_EMPTY(head2)) {					\
603*199767f8SToomas Soome 		*(head1)->tqh_last = (head2)->tqh_first;		\
604*199767f8SToomas Soome 		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
605*199767f8SToomas Soome 		(head1)->tqh_last = (head2)->tqh_last;			\
606*199767f8SToomas Soome 		TAILQ_INIT((head2));					\
607*199767f8SToomas Soome 		QMD_TRACE_HEAD(head1);					\
608*199767f8SToomas Soome 		QMD_TRACE_HEAD(head2);					\
609*199767f8SToomas Soome 	}								\
610*199767f8SToomas Soome } while (0)
611*199767f8SToomas Soome 
612*199767f8SToomas Soome #define	TAILQ_EMPTY(head)	((head)->tqh_first == NULL)
613*199767f8SToomas Soome 
614*199767f8SToomas Soome #define	TAILQ_FIRST(head)	((head)->tqh_first)
615*199767f8SToomas Soome 
616*199767f8SToomas Soome #define	TAILQ_FOREACH(var, head, field)					\
617*199767f8SToomas Soome 	for ((var) = TAILQ_FIRST((head));				\
618*199767f8SToomas Soome 	    (var);							\
619*199767f8SToomas Soome 	    (var) = TAILQ_NEXT((var), field))
620*199767f8SToomas Soome 
621*199767f8SToomas Soome #define	TAILQ_FOREACH_FROM(var, head, field)				\
622*199767f8SToomas Soome 	for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));		\
623*199767f8SToomas Soome 	    (var);							\
624*199767f8SToomas Soome 	    (var) = TAILQ_NEXT((var), field))
625*199767f8SToomas Soome 
626*199767f8SToomas Soome #define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
627*199767f8SToomas Soome 	for ((var) = TAILQ_FIRST((head));				\
628*199767f8SToomas Soome 	    (var) && ((tvar) = TAILQ_NEXT((var), field), 1);		\
629*199767f8SToomas Soome 	    (var) = (tvar))
630*199767f8SToomas Soome 
631*199767f8SToomas Soome #define	TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)			\
632*199767f8SToomas Soome 	for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));		\
633*199767f8SToomas Soome 	    (var) && ((tvar) = TAILQ_NEXT((var), field), 1);		\
634*199767f8SToomas Soome 	    (var) = (tvar))
635*199767f8SToomas Soome 
636*199767f8SToomas Soome #define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
637*199767f8SToomas Soome 	for ((var) = TAILQ_LAST((head), headname);			\
638*199767f8SToomas Soome 	    (var);							\
639*199767f8SToomas Soome 	    (var) = TAILQ_PREV((var), headname, field))
640*199767f8SToomas Soome 
641*199767f8SToomas Soome #define	TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field)		\
642*199767f8SToomas Soome 	for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));	\
643*199767f8SToomas Soome 	    (var);							\
644*199767f8SToomas Soome 	    (var) = TAILQ_PREV((var), headname, field))
645*199767f8SToomas Soome 
646*199767f8SToomas Soome #define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
647*199767f8SToomas Soome 	for ((var) = TAILQ_LAST((head), headname);			\
648*199767f8SToomas Soome 	    (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);	\
649*199767f8SToomas Soome 	    (var) = (tvar))
650*199767f8SToomas Soome 
651*199767f8SToomas Soome #define	TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
652*199767f8SToomas Soome 	for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));	\
653*199767f8SToomas Soome 	    (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);	\
654*199767f8SToomas Soome 	    (var) = (tvar))
655*199767f8SToomas Soome 
656*199767f8SToomas Soome #define	TAILQ_INIT(head) do {						\
657*199767f8SToomas Soome 	TAILQ_FIRST((head)) = NULL;					\
658*199767f8SToomas Soome 	(head)->tqh_last = &TAILQ_FIRST((head));			\
659*199767f8SToomas Soome 	QMD_TRACE_HEAD(head);						\
660*199767f8SToomas Soome } while (0)
661*199767f8SToomas Soome 
662*199767f8SToomas Soome #define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
663*199767f8SToomas Soome 	QMD_TAILQ_CHECK_NEXT(listelm, field);				\
664*199767f8SToomas Soome 	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
665*199767f8SToomas Soome 		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\
666*199767f8SToomas Soome 		    &TAILQ_NEXT((elm), field);				\
667*199767f8SToomas Soome 	else {								\
668*199767f8SToomas Soome 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
669*199767f8SToomas Soome 		QMD_TRACE_HEAD(head);					\
670*199767f8SToomas Soome 	}								\
671*199767f8SToomas Soome 	TAILQ_NEXT((listelm), field) = (elm);				\
672*199767f8SToomas Soome 	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);		\
673*199767f8SToomas Soome 	QMD_TRACE_ELEM(&(elm)->field);					\
674*199767f8SToomas Soome 	QMD_TRACE_ELEM(&(listelm)->field);				\
675*199767f8SToomas Soome } while (0)
676*199767f8SToomas Soome 
677*199767f8SToomas Soome #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
678*199767f8SToomas Soome 	QMD_TAILQ_CHECK_PREV(listelm, field);				\
679*199767f8SToomas Soome 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
680*199767f8SToomas Soome 	TAILQ_NEXT((elm), field) = (listelm);				\
681*199767f8SToomas Soome 	*(listelm)->field.tqe_prev = (elm);				\
682*199767f8SToomas Soome 	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);		\
683*199767f8SToomas Soome 	QMD_TRACE_ELEM(&(elm)->field);					\
684*199767f8SToomas Soome 	QMD_TRACE_ELEM(&(listelm)->field);				\
685*199767f8SToomas Soome } while (0)
686*199767f8SToomas Soome 
687*199767f8SToomas Soome #define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
688*199767f8SToomas Soome 	QMD_TAILQ_CHECK_HEAD(head, field);				\
689*199767f8SToomas Soome 	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)	\
690*199767f8SToomas Soome 		TAILQ_FIRST((head))->field.tqe_prev =			\
691*199767f8SToomas Soome 		    &TAILQ_NEXT((elm), field);				\
692*199767f8SToomas Soome 	else								\
693*199767f8SToomas Soome 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
694*199767f8SToomas Soome 	TAILQ_FIRST((head)) = (elm);					\
695*199767f8SToomas Soome 	(elm)->field.tqe_prev = &TAILQ_FIRST((head));			\
696*199767f8SToomas Soome 	QMD_TRACE_HEAD(head);						\
697*199767f8SToomas Soome 	QMD_TRACE_ELEM(&(elm)->field);					\
698*199767f8SToomas Soome } while (0)
699*199767f8SToomas Soome 
700*199767f8SToomas Soome #define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
701*199767f8SToomas Soome 	QMD_TAILQ_CHECK_TAIL(head, field);				\
702*199767f8SToomas Soome 	TAILQ_NEXT((elm), field) = NULL;				\
703*199767f8SToomas Soome 	(elm)->field.tqe_prev = (head)->tqh_last;			\
704*199767f8SToomas Soome 	*(head)->tqh_last = (elm);					\
705*199767f8SToomas Soome 	(head)->tqh_last = &TAILQ_NEXT((elm), field);			\
706*199767f8SToomas Soome 	QMD_TRACE_HEAD(head);						\
707*199767f8SToomas Soome 	QMD_TRACE_ELEM(&(elm)->field);					\
708*199767f8SToomas Soome } while (0)
709*199767f8SToomas Soome 
710*199767f8SToomas Soome #define	TAILQ_LAST(head, headname)					\
711*199767f8SToomas Soome 	(*(((struct headname *)((head)->tqh_last))->tqh_last))
712*199767f8SToomas Soome 
713*199767f8SToomas Soome #define	TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
714*199767f8SToomas Soome 
715*199767f8SToomas Soome #define	TAILQ_PREV(elm, headname, field)				\
716*199767f8SToomas Soome 	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
717*199767f8SToomas Soome 
718*199767f8SToomas Soome #define	TAILQ_REMOVE(head, elm, field) do {				\
719*199767f8SToomas Soome 	QMD_SAVELINK(oldnext, (elm)->field.tqe_next);			\
720*199767f8SToomas Soome 	QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);			\
721*199767f8SToomas Soome 	QMD_TAILQ_CHECK_NEXT(elm, field);				\
722*199767f8SToomas Soome 	QMD_TAILQ_CHECK_PREV(elm, field);				\
723*199767f8SToomas Soome 	if ((TAILQ_NEXT((elm), field)) != NULL)				\
724*199767f8SToomas Soome 		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\
725*199767f8SToomas Soome 		    (elm)->field.tqe_prev;				\
726*199767f8SToomas Soome 	else {								\
727*199767f8SToomas Soome 		(head)->tqh_last = (elm)->field.tqe_prev;		\
728*199767f8SToomas Soome 		QMD_TRACE_HEAD(head);					\
729*199767f8SToomas Soome 	}								\
730*199767f8SToomas Soome 	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);		\
731*199767f8SToomas Soome 	TRASHIT(*oldnext);						\
732*199767f8SToomas Soome 	TRASHIT(*oldprev);						\
733*199767f8SToomas Soome 	QMD_TRACE_ELEM(&(elm)->field);					\
734*199767f8SToomas Soome } while (0)
735*199767f8SToomas Soome 
736*199767f8SToomas Soome #define TAILQ_SWAP(head1, head2, type, field) do {			\
737*199767f8SToomas Soome 	QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first;		\
738*199767f8SToomas Soome 	QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last;		\
739*199767f8SToomas Soome 	(head1)->tqh_first = (head2)->tqh_first;			\
740*199767f8SToomas Soome 	(head1)->tqh_last = (head2)->tqh_last;				\
741*199767f8SToomas Soome 	(head2)->tqh_first = swap_first;				\
742*199767f8SToomas Soome