1f9a21cf8SJérôme Duval/*-
2f9a21cf8SJérôme Duval * Copyright (c) 1991, 1993
3f9a21cf8SJérôme Duval *	The Regents of the University of California.  All rights reserved.
4f9a21cf8SJérôme Duval *
5f9a21cf8SJérôme Duval * Redistribution and use in source and binary forms, with or without
6f9a21cf8SJérôme Duval * modification, are permitted provided that the following conditions
7f9a21cf8SJérôme Duval * are met:
8f9a21cf8SJérôme Duval * 1. Redistributions of source code must retain the above copyright
9f9a21cf8SJérôme Duval *    notice, this list of conditions and the following disclaimer.
10f9a21cf8SJérôme Duval * 2. Redistributions in binary form must reproduce the above copyright
11f9a21cf8SJérôme Duval *    notice, this list of conditions and the following disclaimer in the
12f9a21cf8SJérôme Duval *    documentation and/or other materials provided with the distribution.
13f9a21cf8SJérôme Duval * 4. Neither the name of the University nor the names of its contributors
14f9a21cf8SJérôme Duval *    may be used to endorse or promote products derived from this software
15f9a21cf8SJérôme Duval *    without specific prior written permission.
16f9a21cf8SJérôme Duval *
17f9a21cf8SJérôme Duval * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18f9a21cf8SJérôme Duval * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19f9a21cf8SJérôme Duval * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20f9a21cf8SJérôme Duval * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21f9a21cf8SJérôme Duval * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22f9a21cf8SJérôme Duval * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23f9a21cf8SJérôme Duval * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24f9a21cf8SJérôme Duval * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25f9a21cf8SJérôme Duval * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26f9a21cf8SJérôme Duval * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27f9a21cf8SJérôme Duval * SUCH DAMAGE.
28f9a21cf8SJérôme Duval *
29f9a21cf8SJérôme Duval *	@(#)queue.h	8.5 (Berkeley) 8/20/94
30562ec567SAugustin Cavalier * $FreeBSD: releng/11.1/sys/sys/queue.h 307533 2016-10-17 21:44:41Z mckusick $
31f9a21cf8SJérôme Duval */
32562ec567SAugustin Cavalier
33f9a21cf8SJérôme Duval#ifndef _SYS_QUEUE_H_
34f9a21cf8SJérôme Duval#define	_SYS_QUEUE_H_
35f9a21cf8SJérôme Duval
36f9a21cf8SJérôme Duval#include <sys/cdefs.h>
37f9a21cf8SJérôme Duval
38f9a21cf8SJérôme Duval/*
39f9a21cf8SJérôme Duval * This file defines four types of data structures: singly-linked lists,
40f9a21cf8SJérôme Duval * singly-linked tail queues, lists and tail queues.
41f9a21cf8SJérôme Duval *
42f9a21cf8SJérôme Duval * A singly-linked list is headed by a single forward pointer. The elements
43f9a21cf8SJérôme Duval * are singly linked for minimum space and pointer manipulation overhead at
44f9a21cf8SJérôme Duval * the expense of O(n) removal for arbitrary elements. New elements can be
45f9a21cf8SJérôme Duval * added to the list after an existing element or at the head of the list.
46f9a21cf8SJérôme Duval * Elements being removed from the head of the list should use the explicit
47f9a21cf8SJérôme Duval * macro for this purpose for optimum efficiency. A singly-linked list may
48f9a21cf8SJérôme Duval * only be traversed in the forward direction.  Singly-linked lists are ideal
49f9a21cf8SJérôme Duval * for applications with large datasets and few or no removals or for
50f9a21cf8SJérôme Duval * implementing a LIFO queue.
51f9a21cf8SJérôme Duval *
52f9a21cf8SJérôme Duval * A singly-linked tail queue is headed by a pair of pointers, one to the
53f9a21cf8SJérôme Duval * head of the list and the other to the tail of the list. The elements are
54f9a21cf8SJérôme Duval * singly linked for minimum space and pointer manipulation overhead at the
55f9a21cf8SJérôme Duval * expense of O(n) removal for arbitrary elements. New elements can be added
56f9a21cf8SJérôme Duval * to the list after an existing element, at the head of the list, or at the
57f9a21cf8SJérôme Duval * end of the list. Elements being removed from the head of the tail queue
58f9a21cf8SJérôme Duval * should use the explicit macro for this purpose for optimum efficiency.
59f9a21cf8SJérôme Duval * A singly-linked tail queue may only be traversed in the forward direction.
60f9a21cf8SJérôme Duval * Singly-linked tail queues are ideal for applications with large datasets
61f9a21cf8SJérôme Duval * and few or no removals or for implementing a FIFO queue.
62f9a21cf8SJérôme Duval *
63f9a21cf8SJérôme Duval * A list is headed by a single forward pointer (or an array of forward
64f9a21cf8SJérôme Duval * pointers for a hash table header). The elements are doubly linked
65f9a21cf8SJérôme Duval * so that an arbitrary element can be removed without a need to
66f9a21cf8SJérôme Duval * traverse the list. New elements can be added to the list before
67f9a21cf8SJérôme Duval * or after an existing element or at the head of the list. A list
68562ec567SAugustin Cavalier * may be traversed in either direction.
69f9a21cf8SJérôme Duval *
70f9a21cf8SJérôme Duval * A tail queue is headed by a pair of pointers, one to the head of the
71f9a21cf8SJérôme Duval * list and the other to the tail of the list. The elements are doubly
72f9a21cf8SJérôme Duval * linked so that an arbitrary element can be removed without a need to
73f9a21cf8SJérôme Duval * traverse the list. New elements can be added to the list before or
74f9a21cf8SJérôme Duval * after an existing element, at the head of the list, or at the end of
75f9a21cf8SJérôme Duval * the list. A tail queue may be traversed in either direction.
76f9a21cf8SJérôme Duval *
77f9a21cf8SJérôme Duval * For details on the use of these macros, see the queue(3) manual page.
78f9a21cf8SJérôme Duval *
79562ec567SAugustin Cavalier * Below is a summary of implemented functions where:
80562ec567SAugustin Cavalier *  +  means the macro is available
81562ec567SAugustin Cavalier *  -  means the macro is not available
82562ec567SAugustin Cavalier *  s  means the macro is available but is slow (runs in O(n) time)
83f9a21cf8SJérôme Duval *
84f9a21cf8SJérôme Duval *				SLIST	LIST	STAILQ	TAILQ
85f9a21cf8SJérôme Duval * _HEAD			+	+	+	+
86562ec567SAugustin Cavalier * _CLASS_HEAD			+	+	+	+
87f9a21cf8SJérôme Duval * _HEAD_INITIALIZER		+	+	+	+
88f9a21cf8SJérôme Duval * _ENTRY			+	+	+	+
89562ec567SAugustin Cavalier * _CLASS_ENTRY			+	+	+	+
90f9a21cf8SJérôme Duval * _INIT			+	+	+	+
91f9a21cf8SJérôme Duval * _EMPTY			+	+	+	+
92f9a21cf8SJérôme Duval * _FIRST			+	+	+	+
93f9a21cf8SJérôme Duval * _NEXT			+	+	+	+
94562ec567SAugustin Cavalier * _PREV			-	+	-	+
95f9a21cf8SJérôme Duval * _LAST			-	-	+	+
96f9a21cf8SJérôme Duval * _FOREACH			+	+	+	+
97562ec567SAugustin Cavalier * _FOREACH_FROM		+	+	+	+
98f9a21cf8SJérôme Duval * _FOREACH_SAFE		+	+	+	+
99562ec567SAugustin Cavalier * _FOREACH_FROM_SAFE		+	+	+	+
100f9a21cf8SJérôme Duval * _FOREACH_REVERSE		-	-	-	+
101562ec567SAugustin Cavalier * _FOREACH_REVERSE_FROM	-	-	-	+
102f9a21cf8SJérôme Duval * _FOREACH_REVERSE_SAFE	-	-	-	+
103562ec567SAugustin Cavalier * _FOREACH_REVERSE_FROM_SAFE	-	-	-	+
104f9a21cf8SJérôme Duval * _INSERT_HEAD			+	+	+	+
105f9a21cf8SJérôme Duval * _INSERT_BEFORE		-	+	-	+
106f9a21cf8SJérôme Duval * _INSERT_AFTER		+	+	+	+
107f9a21cf8SJérôme Duval * _INSERT_TAIL			-	-	+	+
108562ec567SAugustin Cavalier * _CONCAT			s	s	+	+
109562ec567SAugustin Cavalier * _REMOVE_AFTER		+	-	+	-
110f9a21cf8SJérôme Duval * _REMOVE_HEAD			+	-	+	-
111562ec567SAugustin Cavalier * _REMOVE			s	+	s	+
112562ec567SAugustin Cavalier * _SWAP			+	+	+	+
113f9a21cf8SJérôme Duval *
114f9a21cf8SJérôme Duval */
115562ec567SAugustin Cavalier#ifdef QUEUE_MACRO_DEBUG
116f9a21cf8SJérôme Duval/* Store the last 2 places the queue element or head was altered */
117f9a21cf8SJérôme Duvalstruct qm_trace {
118562ec567SAugustin Cavalier	unsigned long	 lastline;
119562ec567SAugustin Cavalier	unsigned long	 prevline;
120562ec567SAugustin Cavalier	const char	*lastfile;
121562ec567SAugustin Cavalier	const char	*prevfile;
122f9a21cf8SJérôme Duval};
123f9a21cf8SJérôme Duval
124f9a21cf8SJérôme Duval#define	TRACEBUF	struct qm_trace trace;
125562ec567SAugustin Cavalier#define	TRACEBUF_INITIALIZER	{ __LINE__, 0, __FILE__, NULL } ,
126f9a21cf8SJérôme Duval#define	TRASHIT(x)	do {(x) = (void *)-1;} while (0)
127562ec567SAugustin Cavalier#define	QMD_SAVELINK(name, link)	void **name = (void *)&(link)
128f9a21cf8SJérôme Duval
129f9a21cf8SJérôme Duval#define	QMD_TRACE_HEAD(head) do {					\
130f9a21cf8SJérôme Duval	(head)->trace.prevline = (head)->trace.lastline;		\
131f9a21cf8SJérôme Duval	(head)->trace.prevfile = (head)->trace.lastfile;		\
132f9a21cf8SJérôme Duval	(head)->trace.lastline = __LINE__;				\
133f9a21cf8SJérôme Duval	(head)->trace.lastfile = __FILE__;				\
134f9a21cf8SJérôme Duval} while (0)
135f9a21cf8SJérôme Duval
136f9a21cf8SJérôme Duval#define	QMD_TRACE_ELEM(elem) do {					\
137f9a21cf8SJérôme Duval	(elem)->trace.prevline = (elem)->trace.lastline;		\
138f9a21cf8SJérôme Duval	(elem)->trace.prevfile = (elem)->trace.lastfile;		\
139f9a21cf8SJérôme Duval	(elem)->trace.lastline = __LINE__;				\
140f9a21cf8SJérôme Duval	(elem)->trace.lastfile = __FILE__;				\
141f9a21cf8SJérôme Duval} while (0)
142f9a21cf8SJérôme Duval
143f9a21cf8SJérôme Duval#else
144f9a21cf8SJérôme Duval#define	QMD_TRACE_ELEM(elem)
145f9a21cf8SJérôme Duval#define	QMD_TRACE_HEAD(head)
146562ec567SAugustin Cavalier#define	QMD_SAVELINK(name, link)
147f9a21cf8SJérôme Duval#define	TRACEBUF
148562ec567SAugustin Cavalier#define	TRACEBUF_INITIALIZER
149f9a21cf8SJérôme Duval#define	TRASHIT(x)
150f9a21cf8SJérôme Duval#endif	/* QUEUE_MACRO_DEBUG */
151f9a21cf8SJérôme Duval
152562ec567SAugustin Cavalier#ifdef __cplusplus
153562ec567SAugustin Cavalier/*
154562ec567SAugustin Cavalier * In C++ there can be structure lists and class lists:
155562ec567SAugustin Cavalier */
156562ec567SAugustin Cavalier#define	QUEUE_TYPEOF(type) type
157562ec567SAugustin Cavalier#else
158562ec567SAugustin Cavalier#define	QUEUE_TYPEOF(type) struct type
159562ec567SAugustin Cavalier#endif
160562ec567SAugustin Cavalier
161f9a21cf8SJérôme Duval/*
162f9a21cf8SJérôme Duval * Singly-linked List declarations.
163f9a21cf8SJérôme Duval */
164f9a21cf8SJérôme Duval#define	SLIST_HEAD(name, type)						\
165f9a21cf8SJérôme Duvalstruct name {								\
166f9a21cf8SJérôme Duval	struct type *slh_first;	/* first element */			\
167f9a21cf8SJérôme Duval}
168f9a21cf8SJérôme Duval
169562ec567SAugustin Cavalier#define	SLIST_CLASS_HEAD(name, type)					\
170562ec567SAugustin Cavalierstruct name {								\
171562ec567SAugustin Cavalier	class type *slh_first;	/* first element */			\
172562ec567SAugustin Cavalier}
173562ec567SAugustin Cavalier
174f9a21cf8SJérôme Duval#define	SLIST_HEAD_INITIALIZER(head)					\
175f9a21cf8SJérôme Duval	{ NULL }
176f9a21cf8SJérôme Duval
177f9a21cf8SJérôme Duval#define	SLIST_ENTRY(type)						\
178f9a21cf8SJérôme Duvalstruct {								\
179f9a21cf8SJérôme Duval	struct type *sle_next;	/* next element */			\
180f9a21cf8SJérôme Duval}
181f9a21cf8SJérôme Duval
182562ec567SAugustin Cavalier#define	SLIST_CLASS_ENTRY(type)						\
183562ec567SAugustin Cavalierstruct {								\
184562ec567SAugustin Cavalier	class type *sle_next;		/* next element */		\
185562ec567SAugustin Cavalier}
186562ec567SAugustin Cavalier
187f9a21cf8SJérôme Duval/*
188f9a21cf8SJérôme Duval * Singly-linked List functions.
189f9a21cf8SJérôme Duval */
190562ec567SAugustin Cavalier#define SLIST_CONCAT(head1, head2, type, field) do {			\
191562ec567SAugustin Cavalier	QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1);		\
192562ec567SAugustin Cavalier	if (curelm == NULL) {						\
193562ec567SAugustin Cavalier		if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL)	\
194562ec567SAugustin Cavalier			SLIST_INIT(head2);				\
195562ec567SAugustin Cavalier	} else if (SLIST_FIRST(head2) != NULL) {			\
196562ec567SAugustin Cavalier		while (SLIST_NEXT(curelm, field) != NULL)		\
197562ec567SAugustin Cavalier			curelm = SLIST_NEXT(curelm, field);		\
198562ec567SAugustin Cavalier		SLIST_NEXT(curelm, field) = SLIST_FIRST(head2);		\
199562ec567SAugustin Cavalier		SLIST_INIT(head2);					\
200562ec567SAugustin Cavalier	}								\
201562ec567SAugustin Cavalier} while (0)
202562ec567SAugustin Cavalier
203f9a21cf8SJérôme Duval#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
204f9a21cf8SJérôme Duval
205f9a21cf8SJérôme Duval#define	SLIST_FIRST(head)	((head)->slh_first)
206f9a21cf8SJérôme Duval
207f9a21cf8SJérôme Duval#define	SLIST_FOREACH(var, head, field)					\
208f9a21cf8SJérôme Duval	for ((var) = SLIST_FIRST((head));				\
209f9a21cf8SJérôme Duval	    (var);							\
210f9a21cf8SJérôme Duval	    (var) = SLIST_NEXT((var), field))
211f9a21cf8SJérôme Duval
212562ec567SAugustin Cavalier#define	SLIST_FOREACH_FROM(var, head, field)				\
213562ec567SAugustin Cavalier	for ((var) = ((var) ? (var) : SLIST_FIRST((head)));		\
214562ec567SAugustin Cavalier	    (var);							\
215562ec567SAugustin Cavalier	    (var) = SLIST_NEXT((var), field))
216562ec567SAugustin Cavalier
217f9a21cf8SJérôme Duval#define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
218f9a21cf8SJérôme Duval	for ((var) = SLIST_FIRST((head));				\
219f9a21cf8SJérôme Duval	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);		\
220f9a21cf8SJérôme Duval	    (var) = (tvar))
221f9a21cf8SJérôme Duval
222562ec567SAugustin Cavalier#define	SLIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
223562ec567SAugustin Cavalier	for ((var) = ((var) ? (var) : SLIST_FIRST((head)));		\
224562ec567SAugustin Cavalier	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);		\
225562ec567SAugustin Cavalier	    (var) = (tvar))
226562ec567SAugustin Cavalier
227f9a21cf8SJérôme Duval#define	SLIST_FOREACH_PREVPTR(var, varp, head, field)			\
228f9a21cf8SJérôme Duval	for ((varp) = &SLIST_FIRST((head));				\
229f9a21cf8SJérôme Duval	    ((var) = *(varp)) != NULL;					\
230f9a21cf8SJérôme Duval	    (varp) = &SLIST_NEXT((var), field))
231f9a21cf8SJérôme Duval
232f9a21cf8SJérôme Duval#define	SLIST_INIT(head) do {						\
233f9a21cf8SJérôme Duval	SLIST_FIRST((head)) = NULL;					\
234f9a21cf8SJérôme Duval} while (0)
235f9a21cf8SJérôme Duval
236f9a21cf8SJérôme Duval#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
237f9a21cf8SJérôme Duval	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);	\
238f9a21cf8SJérôme Duval	SLIST_NEXT((slistelm), field) = (elm);				\
239f9a21cf8SJérôme Duval} while (0)
240f9a21cf8SJérôme Duval
241f9a21cf8SJérôme Duval#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
242f9a21cf8SJérôme Duval	SLIST_NEXT((elm), field) = SLIST_FIRST((head));			\
243f9a21cf8SJérôme Duval	SLIST_FIRST((head)) = (elm);					\
244f9a21cf8SJérôme Duval} while (0)
245f9a21cf8SJérôme Duval
246f9a21cf8SJérôme Duval#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
247f9a21cf8SJérôme Duval
248f9a21cf8SJérôme Duval#define	SLIST_REMOVE(head, elm, type, field) do {			\
249562ec567SAugustin Cavalier	QMD_SAVELINK(oldnext, (elm)->field.sle_next);			\
250f9a21cf8SJérôme Duval	if (SLIST_FIRST((head)) == (elm)) {				\
251f9a21cf8SJérôme Duval		SLIST_REMOVE_HEAD((head), field);			\
252f9a21cf8SJérôme Duval	}								\
253f9a21cf8SJérôme Duval	else {								\
254562ec567SAugustin Cavalier		QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head);		\
255f9a21cf8SJérôme Duval		while (SLIST_NEXT(curelm, field) != (elm))		\
256f9a21cf8SJérôme Duval			curelm = SLIST_NEXT(curelm, field);		\
257562ec567SAugustin Cavalier		SLIST_REMOVE_AFTER(curelm, field);			\
258f9a21cf8SJérôme Duval	}								\
259562ec567SAugustin Cavalier	TRASHIT(*oldnext);						\
260562ec567SAugustin Cavalier} while (0)
261562ec567SAugustin Cavalier
262562ec567SAugustin Cavalier#define SLIST_REMOVE_AFTER(elm, field) do {				\
263562ec567SAugustin Cavalier	SLIST_NEXT(elm, field) =					\
264562ec567SAugustin Cavalier	    SLIST_NEXT(SLIST_NEXT(elm, field), field);			\
265f9a21cf8SJérôme Duval} while (0)
266f9a21cf8SJérôme Duval
267f9a21cf8SJérôme Duval#define	SLIST_REMOVE_HEAD(head, field) do {				\
268f9a21cf8SJérôme Duval	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
269f9a21cf8SJérôme Duval} while (0)
270f9a21cf8SJérôme Duval
271562ec567SAugustin Cavalier#define SLIST_SWAP(head1, head2, type) do {				\
272562ec567SAugustin Cavalier	QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1);		\
273562ec567SAugustin Cavalier	SLIST_FIRST(head1) = SLIST_FIRST(head2);			\
274562ec567SAugustin Cavalier	SLIST_FIRST(head2) = swap_first;				\
275562ec567SAugustin Cavalier} while (0)
276562ec567SAugustin Cavalier
277f9a21cf8SJérôme Duval/*
278f9a21cf8SJérôme Duval * Singly-linked Tail queue declarations.
279f9a21cf8SJérôme Duval */
280f9a21cf8SJérôme Duval#define	STAILQ_HEAD(name, type)						\
281f9a21cf8SJérôme Duvalstruct name {								\
282f9a21cf8SJérôme Duval	struct type *stqh_first;/* first element */			\
283f9a21cf8SJérôme Duval	struct type **stqh_last;/* addr of last next element */		\
284f9a21cf8SJérôme Duval}
285f9a21cf8SJérôme Duval
286562ec567SAugustin Cavalier#define	STAILQ_CLASS_HEAD(name, type)					\
287562ec567SAugustin Cavalierstruct name {								\
288562ec567SAugustin Cavalier	class type *stqh_first;	/* first element */			\
289562ec567SAugustin Cavalier	class type **stqh_last;	/* addr of last next element */		\
290562ec567SAugustin Cavalier}
291562ec567SAugustin Cavalier
292f9a21cf8SJérôme Duval#define	STAILQ_HEAD_INITIALIZER(head)					\
293f9a21cf8SJérôme Duval	{ NULL, &(head).stqh_first }
294f9a21cf8SJérôme Duval
295f9a21cf8SJérôme Duval#define	STAILQ_ENTRY(type)						\
296f9a21cf8SJérôme Duvalstruct {								\
297f9a21cf8SJérôme Duval	struct type *stqe_next;	/* next element */			\
298f9a21cf8SJérôme Duval}
299f9a21cf8SJérôme Duval
300562ec567SAugustin Cavalier#define	STAILQ_CLASS_ENTRY(type)					\
301562ec567SAugustin Cavalierstruct {								\
302562ec567SAugustin Cavalier	class type *stqe_next;	/* next element */			\
303562ec567SAugustin Cavalier}
304562ec567SAugustin Cavalier
305f9a21cf8SJérôme Duval/*
306f9a21cf8SJérôme Duval * Singly-linked Tail queue functions.
307f9a21cf8SJérôme Duval */
308f9a21cf8SJérôme Duval#define	STAILQ_CONCAT(head1, head2) do {				\
309f9a21cf8SJérôme Duval	if (!STAILQ_EMPTY((head2))) {					\
310f9a21cf8SJérôme Duval		*(head1)->stqh_last = (head2)->stqh_first;		\
311f9a21cf8SJérôme Duval		(head1)->stqh_last = (head2)->stqh_last;		\
312f9a21cf8SJérôme Duval		STAILQ_INIT((head2));					\
313f9a21cf8SJérôme Duval	}								\
314f9a21cf8SJérôme Duval} while (0)
315f9a21cf8SJérôme Duval
316f9a21cf8SJérôme Duval#define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)
317f9a21cf8SJérôme Duval
318f9a21cf8SJérôme Duval#define	STAILQ_FIRST(head)	((head)->stqh_first)
319f9a21cf8SJérôme Duval
320f9a21cf8SJérôme Duval#define	STAILQ_FOREACH(var, head, field)				\
321f9a21cf8SJérôme Duval	for((var) = STAILQ_FIRST((head));				\
322f9a21cf8SJérôme Duval	   (var);							\
323f9a21cf8SJérôme Duval	   (var) = STAILQ_NEXT((var), field))
324f9a21cf8SJérôme Duval
325562ec567SAugustin Cavalier#define	STAILQ_FOREACH_FROM(var, head, field)				\
326562ec567SAugustin Cavalier	for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));		\
327562ec567SAugustin Cavalier	   (var);							\
328562ec567SAugustin Cavalier	   (var) = STAILQ_NEXT((var), field))
329f9a21cf8SJérôme Duval
330f9a21cf8SJérôme Duval#define	STAILQ_FOREACH_SAFE(var, head, field, tvar)			\
331f9a21cf8SJérôme Duval	for ((var) = STAILQ_FIRST((head));				\
332f9a21cf8SJérôme Duval	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\
333f9a21cf8SJérôme Duval	    (var) = (tvar))
334f9a21cf8SJérôme Duval
335562ec567SAugustin Cavalier#define	STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)		\
336562ec567SAugustin Cavalier	for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));		\
337562ec567SAugustin Cavalier	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\
338562ec567SAugustin Cavalier	    (var) = (tvar))
339562ec567SAugustin Cavalier
340f9a21cf8SJérôme Duval#define	STAILQ_INIT(head) do {						\
341f9a21cf8SJérôme Duval	STAILQ_FIRST((head)) = NULL;					\
342f9a21cf8SJérôme Duval	(head)->stqh_last = &STAILQ_FIRST((head));			\
343f9a21cf8SJérôme Duval} while (0)
344f9a21cf8SJérôme Duval
345f9a21cf8SJérôme Duval#define	STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\
346f9a21cf8SJérôme Duval	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
347f9a21cf8SJérôme Duval		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
348f9a21cf8SJérôme Duval	STAILQ_NEXT((tqelm), field) = (elm);				\
349f9a21cf8SJérôme Duval} while (0)
350f9a21cf8SJérôme Duval
351f9a21cf8SJérôme Duval#define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
352f9a21cf8SJérôme Duval	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)	\
353f9a21cf8SJérôme Duval		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
354f9a21cf8SJérôme Duval	STAILQ_FIRST((head)) = (elm);					\
355f9a21cf8SJérôme Duval} while (0)
356f9a21cf8SJérôme Duval
357f9a21cf8SJérôme Duval#define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
358f9a21cf8SJérôme Duval	STAILQ_NEXT((elm), field) = NULL;				\
359f9a21cf8SJérôme Duval	*(head)->stqh_last = (elm);					\
360f9a21cf8SJérôme Duval	(head)->stqh_last = &STAILQ_NEXT((elm), field);			\
361f9a21cf8SJérôme Duval} while (0)
362f9a21cf8SJérôme Duval
363562ec567SAugustin Cavalier#define	STAILQ_LAST(head, type, field)				\
364562ec567SAugustin Cavalier	(STAILQ_EMPTY((head)) ? NULL :				\
365562ec567SAugustin Cavalier	    __containerof((head)->stqh_last,			\
366562ec567SAugustin Cavalier	    QUEUE_TYPEOF(type), field.stqe_next))
367f9a21cf8SJérôme Duval
368f9a21cf8SJérôme Duval#define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
369f9a21cf8SJérôme Duval
370f9a21cf8SJérôme Duval#define	STAILQ_REMOVE(head, elm, type, field) do {			\
371562ec567SAugustin Cavalier	QMD_SAVELINK(oldnext, (elm)->field.stqe_next);			\
372f9a21cf8SJérôme Duval	if (STAILQ_FIRST((head)) == (elm)) {				\
373f9a21cf8SJérôme Duval		STAILQ_REMOVE_HEAD((head), field);			\
374f9a21cf8SJérôme Duval	}								\
375f9a21cf8SJérôme Duval	else {								\
376562ec567SAugustin Cavalier		QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head);	\
377f9a21cf8SJérôme Duval		while (STAILQ_NEXT(curelm, field) != (elm))		\
378f9a21cf8SJérôme Duval			curelm = STAILQ_NEXT(curelm, field);		\
379562ec567SAugustin Cavalier		STAILQ_REMOVE_AFTER(head, curelm, field);		\
380f9a21cf8SJérôme Duval	}								\
381562ec567SAugustin Cavalier	TRASHIT(*oldnext);						\
382562ec567SAugustin Cavalier} while (0)
383562ec567SAugustin Cavalier
384562ec567SAugustin Cavalier#define STAILQ_REMOVE_AFTER(head, elm, field) do {			\
385562ec567SAugustin Cavalier	if ((STAILQ_NEXT(elm, field) =					\
386562ec567SAugustin Cavalier	     STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)	\
387562ec567SAugustin Cavalier		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
388f9a21cf8SJérôme Duval} while (0)
389f9a21cf8SJérôme Duval
390f9a21cf8SJérôme Duval#define	STAILQ_REMOVE_HEAD(head, field) do {				\
391f9a21cf8SJérôme Duval	if ((STAILQ_FIRST((head)) =					\
392f9a21cf8SJérôme Duval	     STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)		\
393f9a21cf8SJérôme Duval		(head)->stqh_last = &STAILQ_FIRST((head));		\
394f9a21cf8SJérôme Duval} while (0)
395f9a21cf8SJérôme Duval
396562ec567SAugustin Cavalier#define STAILQ_SWAP(head1, head2, type) do {				\
397562ec567SAugustin Cavalier	QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1);		\
398562ec567SAugustin Cavalier	QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last;		\
399562ec567SAugustin Cavalier	STAILQ_FIRST(head1) = STAILQ_FIRST(head2);			\
400562ec567SAugustin Cavalier	(head1)->stqh_last = (head2)->stqh_last;			\
401562ec567SAugustin Cavalier	STAILQ_FIRST(head2) = swap_first;				\
402562ec567SAugustin Cavalier	(head2)->stqh_last = swap_last;					\
403562ec567SAugustin Cavalier	if (STAILQ_EMPTY(head1))					\
404562ec567SAugustin Cavalier		(head1)->stqh_last = &STAILQ_FIRST(head1);		\
405562ec567SAugustin Cavalier	if (STAILQ_EMPTY(head2))					\
406562ec567SAugustin Cavalier		(head2)->stqh_last = &STAILQ_FIRST(head2);		\
407f9a21cf8SJérôme Duval} while (0)
408f9a21cf8SJérôme Duval
409562ec567SAugustin Cavalier
410f9a21cf8SJérôme Duval/*
411f9a21cf8SJérôme Duval * List declarations.
412f9a21cf8SJérôme Duval */
413f9a21cf8SJérôme Duval#define	LIST_HEAD(name, type)						\
414f9a21cf8SJérôme Duvalstruct name {								\
415f9a21cf8SJérôme Duval	struct type *lh_first;	/* first element */			\
416f9a21cf8SJérôme Duval}
417f9a21cf8SJérôme Duval
418562ec567SAugustin Cavalier#define	LIST_CLASS_HEAD(name, type)					\
419562ec567SAugustin Cavalierstruct name {								\
420562ec567SAugustin Cavalier	class type *lh_first;	/* first element */			\
421562ec567SAugustin Cavalier}
422562ec567SAugustin Cavalier
423f9a21cf8SJérôme Duval#define	LIST_HEAD_INITIALIZER(head)					\
424f9a21cf8SJérôme Duval	{ NULL }
425f9a21cf8SJérôme Duval
426f9a21cf8SJérôme Duval#define	LIST_ENTRY(type)						\
427f9a21cf8SJérôme Duvalstruct {								\
428f9a21cf8SJérôme Duval	struct type *le_next;	/* next element */			\
429f9a21cf8SJérôme Duval	struct type **le_prev;	/* address of previous next element */	\
430f9a21cf8SJérôme Duval}
431f9a21cf8SJérôme Duval
432562ec567SAugustin Cavalier#define	LIST_CLASS_ENTRY(type)						\
433562ec567SAugustin Cavalierstruct {								\
434562ec567SAugustin Cavalier	class type *le_next;	/* next element */			\
435562ec567SAugustin Cavalier	class type **le_prev;	/* address of previous next element */	\
436562ec567SAugustin Cavalier}
437562ec567SAugustin Cavalier
438f9a21cf8SJérôme Duval/*
439f9a21cf8SJérôme Duval * List functions.
440f9a21cf8SJérôme Duval */
441f9a21cf8SJérôme Duval
442562ec567SAugustin Cavalier#if (defined(_KERNEL) && defined(INVARIANTS))
443562ec567SAugustin Cavalier#define	QMD_LIST_CHECK_HEAD(head, field) do {				\
444562ec567SAugustin Cavalier	if (LIST_FIRST((head)) != NULL &&				\
445562ec567SAugustin Cavalier	    LIST_FIRST((head))->field.le_prev !=			\
446562ec567SAugustin Cavalier	     &LIST_FIRST((head)))					\
447562ec567SAugustin Cavalier		panic("Bad list head %p first->prev != head", (head));	\
448562ec567SAugustin Cavalier} while (0)
449562ec567SAugustin Cavalier
450562ec567SAugustin Cavalier#define	QMD_LIST_CHECK_NEXT(elm, field) do {				\
451562ec567SAugustin Cavalier	if (LIST_NEXT((elm), field) != NULL &&				\
452562ec567SAugustin Cavalier	    LIST_NEXT((elm), field)->field.le_prev !=			\
453562ec567SAugustin Cavalier	     &((elm)->field.le_next))					\
454562ec567SAugustin Cavalier	     	panic("Bad link elm %p next->prev != elm", (elm));	\
455562ec567SAugustin Cavalier} while (0)
456562ec567SAugustin Cavalier
457562ec567SAugustin Cavalier#define	QMD_LIST_CHECK_PREV(elm, field) do {				\
458562ec567SAugustin Cavalier	if (*(elm)->field.le_prev != (elm))				\
459562ec567SAugustin Cavalier		panic("Bad link elm %p prev->next != elm", (elm));	\
460562ec567SAugustin Cavalier} while (0)
461562ec567SAugustin Cavalier#else
462562ec567SAugustin Cavalier#define	QMD_LIST_CHECK_HEAD(head, field)
463562ec567SAugustin Cavalier#define	QMD_LIST_CHECK_NEXT(elm, field)
464562ec567SAugustin Cavalier#define	QMD_LIST_CHECK_PREV(elm, field)
465562ec567SAugustin Cavalier#endif /* (_KERNEL && INVARIANTS) */
466562ec567SAugustin Cavalier
467562ec567SAugustin Cavalier#define LIST_CONCAT(head1, head2, type, field) do {			      \
468562ec567SAugustin Cavalier	QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1);			      \
469562ec567SAugustin Cavalier	if (curelm == NULL) {						      \
470562ec567SAugustin Cavalier		if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) {	      \
471562ec567SAugustin Cavalier			LIST_FIRST(head2)->field.le_prev =		      \
472562ec567SAugustin Cavalier			    &LIST_FIRST((head1));			      \
473562ec567SAugustin Cavalier			LIST_INIT(head2);				      \
474562ec567SAugustin Cavalier		}							      \
475562ec567SAugustin Cavalier	} else if (LIST_FIRST(head2) != NULL) {				      \
476562ec567SAugustin Cavalier		while (LIST_NEXT(curelm, field) != NULL)		      \
477562ec567SAugustin Cavalier			curelm = LIST_NEXT(curelm, field);		      \
478562ec567SAugustin Cavalier		LIST_NEXT(curelm, field) = LIST_FIRST(head2);		      \
479562ec567SAugustin Cavalier		LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \
480562ec567SAugustin Cavalier		LIST_INIT(head2);					      \
481562ec567SAugustin Cavalier	}								      \
482562ec567SAugustin Cavalier} while (0)
483562ec567SAugustin Cavalier
484f9a21cf8SJérôme Duval#define	LIST_EMPTY(head)	((head)->lh_first == NULL)
485f9a21cf8SJérôme Duval
486f9a21cf8SJérôme Duval#define	LIST_FIRST(head)	((head)->lh_first)
487f9a21cf8SJérôme Duval
488f9a21cf8SJérôme Duval#define	LIST_FOREACH(var, head, field)					\
489f9a21cf8SJérôme Duval	for ((var) = LIST_FIRST((head));				\
490f9a21cf8SJérôme Duval	    (var);							\
491f9a21cf8SJérôme Duval	    (var) = LIST_NEXT((var), field))
492f9a21cf8SJérôme Duval
493562ec567SAugustin Cavalier#define	LIST_FOREACH_FROM(var, head, field)				\
494562ec567SAugustin Cavalier	for ((var) = ((var) ? (var) : LIST_FIRST((head)));		\
495562ec567SAugustin Cavalier	    (var);							\
496562ec567SAugustin Cavalier	    (var) = LIST_NEXT((var), field))
497562ec567SAugustin Cavalier
498f9a21cf8SJérôme Duval#define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
499f9a21cf8SJérôme Duval	for ((var) = LIST_FIRST((head));				\
500f9a21cf8SJérôme Duval	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\
501f9a21cf8SJérôme Duval	    (var) = (tvar))
502f9a21cf8SJérôme Duval
503562ec567SAugustin Cavalier#define	LIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
504562ec567SAugustin Cavalier	for ((var) = ((var) ? (var) : LIST_FIRST((head)));		\
505562ec567SAugustin Cavalier	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\
506562ec567SAugustin Cavalier	    (var) = (tvar))
507562ec567SAugustin Cavalier
508f9a21cf8SJérôme Duval#define	LIST_INIT(head) do {						\
509f9a21cf8SJérôme Duval	LIST_FIRST((head)) = NULL;					\
510f9a21cf8SJérôme Duval} while (0)
511f9a21cf8SJérôme Duval
512f9a21cf8SJérôme Duval#define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
513562ec567SAugustin Cavalier	QMD_LIST_CHECK_NEXT(listelm, field);				\
514f9a21cf8SJérôme Duval	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
515f9a21cf8SJérôme Duval		LIST_NEXT((listelm), field)->field.le_prev =		\
516f9a21cf8SJérôme Duval		    &LIST_NEXT((elm), field);				\
517f9a21cf8SJérôme Duval	LIST_NEXT((listelm), field) = (elm);				\
518f9a21cf8SJérôme Duval	(elm)->field.le_prev = &LIST_NEXT((listelm), field);		\
519f9a21cf8SJérôme Duval} while (0)
520f9a21cf8SJérôme Duval
521f9a21cf8SJérôme Duval#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
522562ec567SAugustin Cavalier	QMD_LIST_CHECK_PREV(listelm, field);				\
523f9a21cf8SJérôme Duval	(elm)->field.le_prev = (listelm)->field.le_prev;		\
524f9a21cf8SJérôme Duval	LIST_NEXT((elm), field) = (listelm);				\
525f9a21cf8SJérôme Duval	*(listelm)->field.le_prev = (elm);				\
526f9a21cf8SJérôme Duval	(listelm)->field.le_prev = &LIST_NEXT((elm), field);		\
527f9a21cf8SJérôme Duval} while (0)
528f9a21cf8SJérôme Duval
529f9a21cf8SJérôme Duval#define	LIST_INSERT_HEAD(head, elm, field) do {				\
530562ec567SAugustin Cavalier	QMD_LIST_CHECK_HEAD((head), field);				\
531f9a21cf8SJérôme Duval	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\
532f9a21cf8SJérôme Duval		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
533f9a21cf8SJérôme Duval	LIST_FIRST((head)) = (elm);					\
534f9a21cf8SJérôme Duval	(elm)->field.le_prev = &LIST_FIRST((head));			\
535f9a21cf8SJérôme Duval} while (0)
536f9a21cf8SJérôme Duval
537f9a21cf8SJérôme Duval#define	LIST_NEXT(elm, field)	((elm)->field.le_next)
538f9a21cf8SJérôme Duval
539562ec567SAugustin Cavalier#define	LIST_PREV(elm, head, type, field)			\
540562ec567SAugustin Cavalier	((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL :	\
541562ec567SAugustin Cavalier	    __containerof((elm)->field.le_prev,			\
542562ec567SAugustin Cavalier	    QUEUE_TYPEOF(type), field.le_next))
543562ec567SAugustin Cavalier
544f9a21cf8SJérôme Duval#define	LIST_REMOVE(elm, field) do {					\
545562ec567SAugustin Cavalier	QMD_SAVELINK(oldnext, (elm)->field.le_next);			\
546562ec567SAugustin Cavalier	QMD_SAVELINK(oldprev, (elm)->field.le_prev);			\
547562ec567SAugustin Cavalier	QMD_LIST_CHECK_NEXT(elm, field);				\
548562ec567SAugustin Cavalier	QMD_LIST_CHECK_PREV(elm, field);				\
549f9a21cf8SJérôme Duval	if (LIST_NEXT((elm), field) != NULL)				\
550f9a21cf8SJérôme Duval		LIST_NEXT((elm), field)->field.le_prev = 		\
551f9a21cf8SJérôme Duval		    (elm)->field.le_prev;				\
552f9a21cf8SJérôme Duval	*(elm)->field.le_prev = LIST_NEXT((elm), field);		\
553562ec567SAugustin Cavalier	TRASHIT(*oldnext);						\
554562ec567SAugustin Cavalier	TRASHIT(*oldprev);						\
555562ec567SAugustin Cavalier} while (0)
556562ec567SAugustin Cavalier
557562ec567SAugustin Cavalier#define LIST_SWAP(head1, head2, type, field) do {			\
558562ec567SAugustin Cavalier	QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1);		\
559562ec567SAugustin Cavalier	LIST_FIRST((head1)) = LIST_FIRST((head2));			\
560562ec567SAugustin Cavalier	LIST_FIRST((head2)) = swap_tmp;					\
561562ec567SAugustin Cavalier	if ((swap_tmp = LIST_FIRST((head1))) != NULL)			\
562562ec567SAugustin Cavalier		swap_tmp->field.le_prev = &LIST_FIRST((head1));		\
563562ec567SAugustin Cavalier	if ((swap_tmp = LIST_FIRST((head2))) != NULL)			\
564562ec567SAugustin Cavalier		swap_tmp->field.le_prev = &LIST_FIRST((head2));		\
565f9a21cf8SJérôme Duval} while (0)
566f9a21cf8SJérôme Duval
567f9a21cf8SJérôme Duval/*
568f9a21cf8SJérôme Duval * Tail queue declarations.
569f9a21cf8SJérôme Duval */
570f9a21cf8SJérôme Duval#define	TAILQ_HEAD(name, type)						\
571f9a21cf8SJérôme Duvalstruct name {								\
572f9a21cf8SJérôme Duval	struct type *tqh_first;	/* first element */			\
573f9a21cf8SJérôme Duval	struct type **tqh_last;	/* addr of last next element */		\
574f9a21cf8SJérôme Duval	TRACEBUF							\
575f9a21cf8SJérôme Duval}
576f9a21cf8SJérôme Duval
577562ec567SAugustin Cavalier#define	TAILQ_CLASS_HEAD(name, type)					\
578562ec567SAugustin Cavalierstruct name {								\
579562ec567SAugustin Cavalier	class type *tqh_first;	/* first element */			\
580562ec567SAugustin Cavalier	class type **tqh_last;	/* addr of last next element */		\
581562ec567SAugustin Cavalier	TRACEBUF							\
582562ec567SAugustin Cavalier}
583562ec567SAugustin Cavalier
584f9a21cf8SJérôme Duval#define	TAILQ_HEAD_INITIALIZER(head)					\
585562ec567SAugustin Cavalier	{ NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
586f9a21cf8SJérôme Duval
587f9a21cf8SJérôme Duval#define	TAILQ_ENTRY(type)						\
588f9a21cf8SJérôme Duvalstruct {								\
589f9a21cf8SJérôme Duval	struct type *tqe_next;	/* next element */			\
590f9a21cf8SJérôme Duval	struct type **tqe_prev;	/* address of previous next element */	\
591f9a21cf8SJérôme Duval	TRACEBUF							\
592f9a21cf8SJérôme Duval}
593f9a21cf8SJérôme Duval
594562ec567SAugustin Cavalier#define	TAILQ_CLASS_ENTRY(type)						\
595562ec567SAugustin Cavalierstruct {								\
596562ec567SAugustin Cavalier	class type *tqe_next;	/* next element */			\
597562ec567SAugustin Cavalier	class type **tqe_prev;	/* address of previous next element */	\
598562ec567SAugustin Cavalier	TRACEBUF							\
599562ec567SAugustin Cavalier}
600562ec567SAugustin Cavalier
601f9a21cf8SJérôme Duval/*
602f9a21cf8SJérôme Duval * Tail queue functions.
603f9a21cf8SJérôme Duval */
604562ec567SAugustin Cavalier#if (defined(_KERNEL) && defined(INVARIANTS))
605562ec567SAugustin Cavalier#define	QMD_TAILQ_CHECK_HEAD(head, field) do {				\
606562ec567SAugustin Cavalier	if (!TAILQ_EMPTY(head) &&					\
607562ec567SAugustin Cavalier	    TAILQ_FIRST((head))->field.tqe_prev !=			\
608562ec567SAugustin Cavalier	     &TAILQ_FIRST((head)))					\
609562ec567SAugustin Cavalier		panic("Bad tailq head %p first->prev != head", (head));	\
610562ec567SAugustin Cavalier} while (0)
611562ec567SAugustin Cavalier
612562ec567SAugustin Cavalier#define	QMD_TAILQ_CHECK_TAIL(head, field) do {				\
613562ec567SAugustin Cavalier	if (*(head)->tqh_last != NULL)					\
614562ec567SAugustin Cavalier	    	panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); 	\
615562ec567SAugustin Cavalier} while (0)
616562ec567SAugustin Cavalier
617562ec567SAugustin Cavalier#define	QMD_TAILQ_CHECK_NEXT(elm, field) do {				\
618562ec567SAugustin Cavalier	if (TAILQ_NEXT((elm), field) != NULL &&				\
619562ec567SAugustin Cavalier	    TAILQ_NEXT((elm), field)->field.tqe_prev !=			\
620562ec567SAugustin Cavalier	     &((elm)->field.tqe_next))					\
621562ec567SAugustin Cavalier		panic("Bad link elm %p next->prev != elm", (elm));	\
622562ec567SAugustin Cavalier} while (0)
623562ec567SAugustin Cavalier
624562ec567SAugustin Cavalier#define	QMD_TAILQ_CHECK_PREV(elm, field) do {				\
625562ec567SAugustin Cavalier	if (*(elm)->field.tqe_prev != (elm))				\
626562ec567SAugustin Cavalier		panic("Bad link elm %p prev->next != elm", (elm));	\
627562ec567SAugustin Cavalier} while (0)
628562ec567SAugustin Cavalier#else
629562ec567SAugustin Cavalier#define	QMD_TAILQ_CHECK_HEAD(head, field)
630562ec567SAugustin Cavalier#define	QMD_TAILQ_CHECK_TAIL(head, headname)
631562ec567SAugustin Cavalier#define	QMD_TAILQ_CHECK_NEXT(elm, field)
632562ec567SAugustin Cavalier#define	QMD_TAILQ_CHECK_PREV(elm, field)
633562ec567SAugustin Cavalier#endif /* (_KERNEL && INVARIANTS) */
634562ec567SAugustin Cavalier
635f9a21cf8SJérôme Duval#define	TAILQ_CONCAT(head1, head2, field) do {				\
636f9a21cf8SJérôme Duval	if (!TAILQ_EMPTY(head2)) {					\
637f9a21cf8SJérôme Duval		*(head1)->tqh_last = (head2)->tqh_first;		\
638f9a21cf8SJérôme Duval		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
639f9a21cf8SJérôme Duval		(head1)->tqh_last = (head2)->tqh_last;			\
640f9a21cf8SJérôme Duval		TAILQ_INIT((head2));					\
641f9a21cf8SJérôme Duval		QMD_TRACE_HEAD(head1);					\
642f9a21cf8SJérôme Duval		QMD_TRACE_HEAD(head2);					\
643f9a21cf8SJérôme Duval	}								\
644f9a21cf8SJérôme Duval} while (0)
645f9a21cf8SJérôme Duval
646f9a21cf8SJérôme Duval#define	TAILQ_EMPTY(head)	((head)->tqh_first == NULL)
647f9a21cf8SJérôme Duval
648f9a21cf8SJérôme Duval#define	TAILQ_FIRST(head)	((head)->tqh_first)
649f9a21cf8SJérôme Duval
650f9a21cf8SJérôme Duval#define	TAILQ_FOREACH(var, head, field)					\
651f9a21cf8SJérôme Duval	for ((var) = TAILQ_FIRST((head));				\
652f9a21cf8SJérôme Duval	    (var);							\
653f9a21cf8SJérôme Duval	    (var) = TAILQ_NEXT((var), field))
654f9a21cf8SJérôme Duval
655562ec567SAugustin Cavalier#define	TAILQ_FOREACH_FROM(var, head, field)				\
656562ec567SAugustin Cavalier	for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));		\
657562ec567SAugustin Cavalier	    (var);							\
658562ec567SAugustin Cavalier	    (var) = TAILQ_NEXT((var), field))
659562ec567SAugustin Cavalier
660f9a21cf8SJérôme Duval#define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
661f9a21cf8SJérôme Duval	for ((var) = TAILQ_FIRST((head));				\
662f9a21cf8SJérôme Duval	    (var) && ((tvar) = TAILQ_NEXT((var), field), 1);		\
663f9a21cf8SJérôme Duval	    (var) = (tvar))
664f9a21cf8SJérôme Duval
665562ec567SAugustin Cavalier#define	TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)			\
666562ec567SAugustin Cavalier	for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));		\
667562ec567SAugustin Cavalier	    (var) && ((tvar) = TAILQ_NEXT((var), field), 1);		\
668562ec567SAugustin Cavalier	    (var) = (tvar))
669562ec567SAugustin Cavalier
670f9a21cf8SJérôme Duval#define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
671f9a21cf8SJérôme Duval	for ((var) = TAILQ_LAST((head), headname);			\
672f9a21cf8SJérôme Duval	    (var);							\
673f9a21cf8SJérôme Duval	    (var) = TAILQ_PREV((var), headname, field))
674f9a21cf8SJérôme Duval
675562ec567SAugustin Cavalier#define	TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field)		\
676562ec567SAugustin Cavalier	for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));	\
677562ec567SAugustin Cavalier	    (var);							\
678562ec567SAugustin Cavalier	    (var) = TAILQ_PREV((var), headname, field))
679562ec567SAugustin Cavalier
680f9a21cf8SJérôme Duval#define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
681f9a21cf8SJérôme Duval	for ((var) = TAILQ_LAST((head), headname);			\
682f9a21cf8SJérôme Duval	    (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);	\
683f9a21cf8SJérôme Duval	    (var) = (tvar))
684f9a21cf8SJérôme Duval
685562ec567SAugustin Cavalier#define	TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
686562ec567SAugustin Cavalier	for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));	\
687562ec567SAugustin Cavalier	    (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);	\
688562ec567SAugustin Cavalier	    (var) = (tvar))
689562ec567SAugustin Cavalier
690f9a21cf8SJérôme Duval#define	TAILQ_INIT(head) do {						\
691f9a21cf8SJérôme Duval	TAILQ_FIRST((head)) = NULL;					\
692f9a21cf8SJérôme Duval	(head)->tqh_last = &TAILQ_FIRST((head));			\
693f9a21cf8SJérôme Duval	QMD_TRACE_HEAD(head);						\
694f9a21cf8SJérôme Duval} while (0)
695f9a21cf8SJérôme Duval
696f9a21cf8SJérôme Duval#define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
697562ec567SAugustin Cavalier	QMD_TAILQ_CHECK_NEXT(listelm, field);				\
698f9a21cf8SJérôme Duval	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
699f9a21cf8SJérôme Duval		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\
700f9a21cf8SJérôme Duval		    &TAILQ_NEXT((elm), field);				\
701f9a21cf8SJérôme Duval	else {								\
702f9a21cf8SJérôme Duval		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
703f9a21cf8SJérôme Duval		QMD_TRACE_HEAD(head);					\
704f9a21cf8SJérôme Duval	}								\
705f9a21cf8SJérôme Duval	TAILQ_NEXT((listelm), field) = (elm);				\
706f9a21cf8SJérôme Duval	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);		\
707f9a21cf8SJérôme Duval	QMD_TRACE_ELEM(&(elm)->field);					\
708562ec567SAugustin Cavalier	QMD_TRACE_ELEM(&(listelm)->field);				\
709f9a21cf8SJérôme Duval} while (0)
710f9a21cf8SJérôme Duval
711f9a21cf8SJérôme Duval#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
712562ec567SAugustin Cavalier	QMD_TAILQ_CHECK_PREV(listelm, field);				\
713f9a21cf8SJérôme Duval	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
714f9a21cf8SJérôme Duval	TAILQ_NEXT((elm), field) = (listelm);				\
715f9a21cf8SJérôme Duval	*(listelm)->field.tqe_prev = (elm);				\
716f9a21cf8SJérôme Duval	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);		\
717f9a21cf8SJérôme Duval	QMD_TRACE_ELEM(&(elm)->field);					\
718562ec567SAugustin Cavalier	QMD_TRACE_ELEM(&(listelm)->field);				\
719f9a21cf8SJérôme Duval} while (0)
720f9a21cf8SJérôme Duval
721f9a21cf8SJérôme Duval#define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
722562ec567SAugustin Cavalier	QMD_TAILQ_CHECK_HEAD(head, field);				\
723f9a21cf8SJérôme Duval	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)	\
724f9a21cf8SJérôme Duval		TAILQ_FIRST((head))->field.tqe_prev =			\
725f9a21cf8SJérôme Duval		    &TAILQ_NEXT((elm), field);				\
726f9a21cf8SJérôme Duval	else								\
727f9a21cf8SJérôme Duval		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
728f9a21cf8SJérôme Duval	TAILQ_FIRST((head)) = (elm);					\
729f9a21cf8SJérôme Duval	(elm)->field.tqe_prev = &TAILQ_FIRST((head));			\
730f9a21cf8SJérôme Duval	QMD_TRACE_HEAD(head);						\
731f9a21cf8SJérôme Duval	QMD_TRACE_ELEM(&(elm)->field);					\
732f9a21cf8SJérôme Duval} while (0)
733f9a21cf8SJérôme Duval
734f9a21cf8SJérôme Duval#define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
735562ec567SAugustin Cavalier	QMD_TAILQ_CHECK_TAIL(head, field);				\
736f9a21cf8SJérôme Duval	TAILQ_NEXT((elm), field) = NULL;				\
737f9a21cf8SJérôme Duval	(elm)->field.tqe_prev = (head)->tqh_last;			\
738f9a21cf8SJérôme Duval	*(head)->tqh_last = (elm);					\
739f9a21cf8SJérôme Duval	(head)->tqh_last = &TAILQ_NEXT((elm), field);			\
740f9a21cf8SJérôme Duval	QMD_TRACE_HEAD(head);						\
741f9a21cf8SJérôme Duval	QMD_TRACE_ELEM(&(elm)->field);					\
742f9a21cf8SJérôme Duval} while (0)
743f9a21cf8SJérôme Duval
744f9a21cf8SJérôme Duval#define	TAILQ_LAST(head, headname)					\
745f9a21cf8SJérôme Duval	(*(((struct headname *)((head)->tqh_last))->tqh_last))
746f9a21cf8SJérôme Duval
747f9a21cf8SJérôme Duval#define	TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
748f9a21cf8SJérôme Duval
749f9a21cf8SJérôme Duval#define	TAILQ_PREV(elm, headname, field)				\
750f9a21cf8SJérôme Duval	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
751f9a21cf8SJérôme Duval
752f9a21cf8SJérôme Duval#define	TAILQ_REMOVE(head, elm, field) do {				\
753562ec567SAugustin Cavalier	QMD_SAVELINK(oldnext, (elm)->field.tqe_next);			\
754562ec567SAugustin Cavalier	QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);			\
755562ec567SAugustin Cavalier	QMD_TAILQ_CHECK_NEXT(elm, field);				\
756562ec567SAugustin Cavalier	QMD_TAILQ_CHECK_PREV(elm, field);				\
757f9a21cf8SJérôme Duval	if ((TAILQ_NEXT((elm), field)) != NULL)				\
758f9a21cf8SJérôme Duval		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\
759f9a21cf8SJérôme Duval		    (elm)->field.tqe_prev;				\
760f9a21cf8SJérôme Duval	else {								\
761f9a21cf8SJérôme Duval		(head)->tqh_last = (elm)->field.tqe_prev;		\
762f9a21cf8SJérôme Duval		QMD_TRACE_HEAD(head);					\
763f9a21cf8SJérôme Duval	}								\
764f9a21cf8SJérôme Duval	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);		\
765562ec567SAugustin Cavalier	TRASHIT(*oldnext);						\
766562ec567SAugustin Cavalier	TRASHIT(*oldprev);						\
767f9a21cf8SJérôme Duval	QMD_TRACE_ELEM(&(elm)->field);					\
768f9a21cf8SJérôme Duval} while (0)
769f9a21cf8SJérôme Duval
770562ec567SAugustin Cavalier#define TAILQ_SWAP(head1, head2, type, field) do {			\
771562ec567SAugustin Cavalier	QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first;		\
772562ec567SAugustin Cavalier	QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last;		\
773562ec567SAugustin Cavalier	(head1)->tqh_first = (head2)->tqh_first;			\
774562ec567SAugustin Cavalier	(head1)->tqh_last = (head2)->tqh_last;				\
775562ec567SAugustin Cavalier	(head2)->tqh_first = swap_first;				\
776562ec567SAugustin Cavalier	(head2)->tqh_last = swap_last;					\
777562ec567SAugustin Cavalier	if ((swap_first = (head1)->tqh_first) != NULL)			\
778562ec567SAugustin Cavalier		swap_first->field.tqe_prev = &(head1)->tqh_first;	\
779562ec567SAugustin Cavalier	else								\
780562ec567SAugustin Cavalier		(head1)->tqh_last = &(head1)->tqh_first;		\
781562ec567SAugustin Cavalier	if ((swap_first = (head2)->tqh_first) != NULL)			\
782562ec567SAugustin Cavalier		swap_first->field.tqe_prev = &(head2)->tqh_first;	\
783562ec567SAugustin Cavalier	else								\
784562ec567SAugustin Cavalier		(head2)->tqh_last = &(head2)->tqh_first;		\
785562ec567SAugustin Cavalier} while (0)
786f9a21cf8SJérôme Duval
787f9a21cf8SJérôme Duval#endif /* !_SYS_QUEUE_H_ */
788