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