1130803f2SJérôme Duval/*	$NetBSD: queue.h,v 1.31 2002/06/01 23:51:05 lukem Exp $	*/
2130803f2SJérôme Duval
3130803f2SJérôme Duval/*
4130803f2SJérôme Duval * Copyright (c) 1991, 1993
5130803f2SJérôme Duval *	The Regents of the University of California.  All rights reserved.
6130803f2SJérôme Duval *
7130803f2SJérôme Duval * Redistribution and use in source and binary forms, with or without
8130803f2SJérôme Duval * modification, are permitted provided that the following conditions
9130803f2SJérôme Duval * are met:
10130803f2SJérôme Duval * 1. Redistributions of source code must retain the above copyright
11130803f2SJérôme Duval *    notice, this list of conditions and the following disclaimer.
12130803f2SJérôme Duval * 2. Redistributions in binary form must reproduce the above copyright
13130803f2SJérôme Duval *    notice, this list of conditions and the following disclaimer in the
14130803f2SJérôme Duval *    documentation and/or other materials provided with the distribution.
15130803f2SJérôme Duval * 3. All advertising materials mentioning features or use of this software
16130803f2SJérôme Duval *    must display the following acknowledgement:
17130803f2SJérôme Duval *	This product includes software developed by the University of
18130803f2SJérôme Duval *	California, Berkeley and its contributors.
19130803f2SJérôme Duval * 4. Neither the name of the University nor the names of its contributors
20130803f2SJérôme Duval *    may be used to endorse or promote products derived from this software
21130803f2SJérôme Duval *    without specific prior written permission.
22130803f2SJérôme Duval *
23130803f2SJérôme Duval * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24130803f2SJérôme Duval * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25130803f2SJérôme Duval * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26130803f2SJérôme Duval * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27130803f2SJérôme Duval * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28130803f2SJérôme Duval * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29130803f2SJérôme Duval * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30130803f2SJérôme Duval * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31130803f2SJérôme Duval * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32130803f2SJérôme Duval * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33130803f2SJérôme Duval * SUCH DAMAGE.
34130803f2SJérôme Duval *
35130803f2SJérôme Duval *	@(#)queue.h	8.5 (Berkeley) 8/20/94
36130803f2SJérôme Duval */
37130803f2SJérôme Duval
38130803f2SJérôme Duval#ifndef	_SYS_QUEUE_H_
39130803f2SJérôme Duval#define	_SYS_QUEUE_H_
40130803f2SJérôme Duval
41130803f2SJérôme Duval/*
42130803f2SJérôme Duval * This file defines five types of data structures: singly-linked lists,
43130803f2SJérôme Duval * lists, simple queues, tail queues, and circular queues.
44130803f2SJérôme Duval *
45130803f2SJérôme Duval * A singly-linked list is headed by a single forward pointer. The
46130803f2SJérôme Duval * elements are singly linked for minimum space and pointer manipulation
47130803f2SJérôme Duval * overhead at the expense of O(n) removal for arbitrary elements. New
48130803f2SJérôme Duval * elements can be added to the list after an existing element or at the
49130803f2SJérôme Duval * head of the list.  Elements being removed from the head of the list
50130803f2SJérôme Duval * should use the explicit macro for this purpose for optimum
51130803f2SJérôme Duval * efficiency. A singly-linked list may only be traversed in the forward
52130803f2SJérôme Duval * direction.  Singly-linked lists are ideal for applications with large
53130803f2SJérôme Duval * datasets and few or no removals or for implementing a LIFO queue.
54130803f2SJérôme Duval *
55130803f2SJérôme Duval * A list is headed by a single forward pointer (or an array of forward
56130803f2SJérôme Duval * pointers for a hash table header). The elements are doubly linked
57130803f2SJérôme Duval * so that an arbitrary element can be removed without a need to
58130803f2SJérôme Duval * traverse the list. New elements can be added to the list before
59130803f2SJérôme Duval * or after an existing element or at the head of the list. A list
60130803f2SJérôme Duval * may only be traversed in the forward direction.
61130803f2SJérôme Duval *
62130803f2SJérôme Duval * A simple queue is headed by a pair of pointers, one the head of the
63130803f2SJérôme Duval * list and the other to the tail of the list. The elements are singly
64130803f2SJérôme Duval * linked to save space, so only elements can only be removed from the
65130803f2SJérôme Duval * head of the list. New elements can be added to the list after
66130803f2SJérôme Duval * an existing element, at the head of the list, or at the end of the
67130803f2SJérôme Duval * list. A simple queue may only be traversed in the forward direction.
68130803f2SJérôme Duval *
69130803f2SJérôme Duval * A tail queue is headed by a pair of pointers, one to the head of the
70130803f2SJérôme Duval * list and the other to the tail of the list. The elements are doubly
71130803f2SJérôme Duval * linked so that an arbitrary element can be removed without a need to
72130803f2SJérôme Duval * traverse the list. New elements can be added to the list before or
73130803f2SJérôme Duval * after an existing element, at the head of the list, or at the end of
74130803f2SJérôme Duval * the list. A tail queue may be traversed in either direction.
75130803f2SJérôme Duval *
76130803f2SJérôme Duval * A circle queue is headed by a pair of pointers, one to the head of the
77130803f2SJérôme Duval * list and the other to the tail of the list. The elements are doubly
78130803f2SJérôme Duval * linked so that an arbitrary element can be removed without a need to
79130803f2SJérôme Duval * traverse the list. New elements can be added to the list before or after
80130803f2SJérôme Duval * an existing element, at the head of the list, or at the end of the list.
81130803f2SJérôme Duval * A circle queue may be traversed in either direction, but has a more
82130803f2SJérôme Duval * complex end of list detection.
83130803f2SJérôme Duval *
84130803f2SJérôme Duval * For details on the use of these macros, see the queue(3) manual page.
85130803f2SJérôme Duval */
86130803f2SJérôme Duval
87130803f2SJérôme Duval/*
88130803f2SJérôme Duval * List definitions.
89130803f2SJérôme Duval */
90130803f2SJérôme Duval#define LIST_HEAD(name, type)						\
91130803f2SJérôme Duvalstruct name {								\
92130803f2SJérôme Duval	struct type *lh_first;	/* first element */			\
93130803f2SJérôme Duval}
94130803f2SJérôme Duval
95130803f2SJérôme Duval#define LIST_HEAD_INITIALIZER(head)					\
96130803f2SJérôme Duval	{ NULL }
97130803f2SJérôme Duval
98130803f2SJérôme Duval#define LIST_ENTRY(type)						\
99130803f2SJérôme Duvalstruct {								\
100130803f2SJérôme Duval	struct type *le_next;	/* next element */			\
101130803f2SJérôme Duval	struct type **le_prev;	/* address of previous next element */	\
102130803f2SJérôme Duval}
103130803f2SJérôme Duval
104130803f2SJérôme Duval/*
105130803f2SJérôme Duval * List functions.
106130803f2SJérôme Duval */
107130803f2SJérôme Duval#if defined(_KERNEL) && defined(QUEUEDEBUG)
108130803f2SJérôme Duval#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)			\
109130803f2SJérôme Duval	if ((head)->lh_first &&						\
110130803f2SJérôme Duval	    (head)->lh_first->field.le_prev != &(head)->lh_first)	\
111130803f2SJérôme Duval		panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
112130803f2SJérôme Duval#define QUEUEDEBUG_LIST_OP(elm, field)					\
113130803f2SJérôme Duval	if ((elm)->field.le_next &&					\
114130803f2SJérôme Duval	    (elm)->field.le_next->field.le_prev !=			\
115130803f2SJérôme Duval	    &(elm)->field.le_next)					\
116130803f2SJérôme Duval		panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
117130803f2SJérôme Duval	if (*(elm)->field.le_prev != (elm))				\
118130803f2SJérôme Duval		panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__);
119130803f2SJérôme Duval#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)				\
120130803f2SJérôme Duval	(elm)->field.le_next = (void *)1L;				\
121130803f2SJérôme Duval	(elm)->field.le_prev = (void *)1L;
122130803f2SJérôme Duval#else
123130803f2SJérôme Duval#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
124130803f2SJérôme Duval#define QUEUEDEBUG_LIST_OP(elm, field)
125130803f2SJérôme Duval#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
126130803f2SJérôme Duval#endif
127130803f2SJérôme Duval
128130803f2SJérôme Duval#define	LIST_INIT(head) do {						\
129130803f2SJérôme Duval	(head)->lh_first = NULL;					\
130130803f2SJérôme Duval} while (/*CONSTCOND*/0)
131130803f2SJérôme Duval
132130803f2SJérôme Duval#define LIST_INSERT_AFTER(listelm, elm, field) do {			\
133130803f2SJérôme Duval	QUEUEDEBUG_LIST_OP((listelm), field)				\
134130803f2SJérôme Duval	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
135130803f2SJérôme Duval		(listelm)->field.le_next->field.le_prev =		\
136130803f2SJérôme Duval		    &(elm)->field.le_next;				\
137130803f2SJérôme Duval	(listelm)->field.le_next = (elm);				\
138130803f2SJérôme Duval	(elm)->field.le_prev = &(listelm)->field.le_next;		\
139130803f2SJérôme Duval} while (/*CONSTCOND*/0)
140130803f2SJérôme Duval
141130803f2SJérôme Duval#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
142130803f2SJérôme Duval	QUEUEDEBUG_LIST_OP((listelm), field)				\
143130803f2SJérôme Duval	(elm)->field.le_prev = (listelm)->field.le_prev;		\
144130803f2SJérôme Duval	(elm)->field.le_next = (listelm);				\
145130803f2SJérôme Duval	*(listelm)->field.le_prev = (elm);				\
146130803f2SJérôme Duval	(listelm)->field.le_prev = &(elm)->field.le_next;		\
147130803f2SJérôme Duval} while (/*CONSTCOND*/0)
148130803f2SJérôme Duval
149130803f2SJérôme Duval#define LIST_INSERT_HEAD(head, elm, field) do {				\
150130803f2SJérôme Duval	QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field)		\
151130803f2SJérôme Duval	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
152130803f2SJérôme Duval		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
153130803f2SJérôme Duval	(head)->lh_first = (elm);					\
154130803f2SJérôme Duval	(elm)->field.le_prev = &(head)->lh_first;			\
155130803f2SJérôme Duval} while (/*CONSTCOND*/0)
156130803f2SJérôme Duval
157130803f2SJérôme Duval#define LIST_REMOVE(elm, field) do {					\
158130803f2SJérôme Duval	QUEUEDEBUG_LIST_OP((elm), field)				\
159130803f2SJérôme Duval	if ((elm)->field.le_next != NULL)				\
160130803f2SJérôme Duval		(elm)->field.le_next->field.le_prev = 			\
161130803f2SJérôme Duval		    (elm)->field.le_prev;				\
162130803f2SJérôme Duval	*(elm)->field.le_prev = (elm)->field.le_next;			\
163130803f2SJérôme Duval	QUEUEDEBUG_LIST_POSTREMOVE((elm), field)			\
164130803f2SJérôme Duval} while (/*CONSTCOND*/0)
165130803f2SJérôme Duval
166130803f2SJérôme Duval#define LIST_FOREACH(var, head, field)					\
167130803f2SJérôme Duval	for ((var) = ((head)->lh_first);				\
168130803f2SJérôme Duval		(var);							\
169130803f2SJérôme Duval		(var) = ((var)->field.le_next))
170130803f2SJérôme Duval
171130803f2SJérôme Duval/*
172130803f2SJérôme Duval * List access methods.
173130803f2SJérôme Duval */
174130803f2SJérôme Duval#define	LIST_EMPTY(head)		((head)->lh_first == NULL)
175130803f2SJérôme Duval#define	LIST_FIRST(head)		((head)->lh_first)
176130803f2SJérôme Duval#define	LIST_NEXT(elm, field)		((elm)->field.le_next)
177130803f2SJérôme Duval
178130803f2SJérôme Duval/*
179130803f2SJérôme Duval * Singly-linked List definitions.
180130803f2SJérôme Duval */
181130803f2SJérôme Duval#define SLIST_HEAD(name, type)						\
182130803f2SJérôme Duvalstruct name {								\
183130803f2SJérôme Duval	struct type *slh_first;	/* first element */			\
184130803f2SJérôme Duval}
185130803f2SJérôme Duval
186130803f2SJérôme Duval#define SLIST_HEAD_INITIALIZER(head)					\
187130803f2SJérôme Duval	{ NULL }
188130803f2SJérôme Duval
189130803f2SJérôme Duval#define SLIST_ENTRY(type)						\
190130803f2SJérôme Duvalstruct {								\
191130803f2SJérôme Duval	struct type *sle_next;	/* next element */			\
192130803f2SJérôme Duval}
193130803f2SJérôme Duval
194130803f2SJérôme Duval/*
195130803f2SJérôme Duval * Singly-linked List functions.
196130803f2SJérôme Duval */
197130803f2SJérôme Duval#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
198130803f2SJérôme Duval#define	SLIST_FIRST(head)	((head)->slh_first)
199130803f2SJérôme Duval#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
200130803f2SJérôme Duval
201130803f2SJérôme Duval#define SLIST_FOREACH(var, head, field)					\
202130803f2SJérôme Duval	for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
203130803f2SJérôme Duval
204130803f2SJérôme Duval#define SLIST_INIT(head) do {						\
205130803f2SJérôme Duval	(head)->slh_first = NULL;					\
206130803f2SJérôme Duval} while (/*CONSTCOND*/0)
207130803f2SJérôme Duval
208130803f2SJérôme Duval#define SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
209130803f2SJérôme Duval	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
210130803f2SJérôme Duval	(slistelm)->field.sle_next = (elm);				\
211130803f2SJérôme Duval} while (/*CONSTCOND*/0)
212130803f2SJérôme Duval
213130803f2SJérôme Duval#define SLIST_INSERT_HEAD(head, elm, field) do {			\
214130803f2SJérôme Duval	(elm)->field.sle_next = (head)->slh_first;			\
215130803f2SJérôme Duval	(head)->slh_first = (elm);					\
216130803f2SJérôme Duval} while (/*CONSTCOND*/0)
217130803f2SJérôme Duval
218130803f2SJérôme Duval#define SLIST_NEXT(elm, field)	((elm)->field.sle_next)
219130803f2SJérôme Duval
220130803f2SJérôme Duval#define SLIST_REMOVE_HEAD(head, field) do {				\
221130803f2SJérôme Duval	(head)->slh_first = (head)->slh_first->field.sle_next;		\
222130803f2SJérôme Duval} while (/*CONSTCOND*/0)
223130803f2SJérôme Duval
224130803f2SJérôme Duval#define SLIST_REMOVE(head, elm, type, field) do {			\
225130803f2SJérôme Duval	if ((head)->slh_first == (elm)) {				\
226130803f2SJérôme Duval		SLIST_REMOVE_HEAD((head), field);			\
227130803f2SJérôme Duval	}								\
228130803f2SJérôme Duval	else {								\
229130803f2SJérôme Duval		struct type *curelm = (head)->slh_first;		\
230130803f2SJérôme Duval		while(curelm->field.sle_next != (elm))			\
231130803f2SJérôme Duval			curelm = curelm->field.sle_next;		\
232130803f2SJérôme Duval		curelm->field.sle_next =				\
233130803f2SJérôme Duval		    curelm->field.sle_next->field.sle_next;		\
234130803f2SJérôme Duval	}								\
235130803f2SJérôme Duval} while (/*CONSTCOND*/0)
236130803f2SJérôme Duval
237130803f2SJérôme Duval/*
238130803f2SJérôme Duval * Simple queue definitions.
239130803f2SJérôme Duval */
240130803f2SJérôme Duval#define SIMPLEQ_HEAD(name, type)					\
241130803f2SJérôme Duvalstruct name {								\
242130803f2SJérôme Duval	struct type *sqh_first;	/* first element */			\
243130803f2SJérôme Duval	struct type **sqh_last;	/* addr of last next element */		\
244130803f2SJérôme Duval}
245130803f2SJérôme Duval
246130803f2SJérôme Duval#define SIMPLEQ_HEAD_INITIALIZER(head)					\
247130803f2SJérôme Duval	{ NULL, &(head).sqh_first }
248130803f2SJérôme Duval
249130803f2SJérôme Duval#define SIMPLEQ_ENTRY(type)						\
250130803f2SJérôme Duvalstruct {								\
251130803f2SJérôme Duval	struct type *sqe_next;	/* next element */			\
252130803f2SJérôme Duval}
253130803f2SJérôme Duval
254130803f2SJérôme Duval/*
255130803f2SJérôme Duval * Simple queue functions.
256130803f2SJérôme Duval */
257130803f2SJérôme Duval#define	SIMPLEQ_INIT(head) do {						\
258130803f2SJérôme Duval	(head)->sqh_first = NULL;					\
259130803f2SJérôme Duval	(head)->sqh_last = &(head)->sqh_first;				\
260130803f2SJérôme Duval} while (/*CONSTCOND*/0)
261130803f2SJérôme Duval
262130803f2SJérôme Duval#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
263130803f2SJérôme Duval	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
264130803f2SJérôme Duval		(head)->sqh_last = &(elm)->field.sqe_next;		\
265130803f2SJérôme Duval	(head)->sqh_first = (elm);					\
266130803f2SJérôme Duval} while (/*CONSTCOND*/0)
267130803f2SJérôme Duval
268130803f2SJérôme Duval#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
269130803f2SJérôme Duval	(elm)->field.sqe_next = NULL;					\
270130803f2SJérôme Duval	*(head)->sqh_last = (elm);					\
271130803f2SJérôme Duval	(head)->sqh_last = &(elm)->field.sqe_next;			\
272130803f2SJérôme Duval} while (/*CONSTCOND*/0)
273130803f2SJérôme Duval
274130803f2SJérôme Duval#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
275130803f2SJérôme Duval	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
276130803f2SJérôme Duval		(head)->sqh_last = &(elm)->field.sqe_next;		\
277130803f2SJérôme Duval	(listelm)->field.sqe_next = (elm);				\
278130803f2SJérôme Duval} while (/*CONSTCOND*/0)
279130803f2SJérôme Duval
280130803f2SJérôme Duval#define SIMPLEQ_REMOVE_HEAD(head, field) do {				\
281130803f2SJérôme Duval	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
282130803f2SJérôme Duval		(head)->sqh_last = &(head)->sqh_first;			\
283130803f2SJérôme Duval} while (/*CONSTCOND*/0)
284130803f2SJérôme Duval
285130803f2SJérôme Duval#define SIMPLEQ_REMOVE(head, elm, type, field) do {			\
286130803f2SJérôme Duval	if ((head)->sqh_first == (elm)) {				\
287130803f2SJérôme Duval		SIMPLEQ_REMOVE_HEAD((head), field);			\
288130803f2SJérôme Duval	} else {							\
289130803f2SJérôme Duval		struct type *curelm = (head)->sqh_first;		\
290130803f2SJérôme Duval		while (curelm->field.sqe_next != (elm))			\
291130803f2SJérôme Duval			curelm = curelm->field.sqe_next;		\
292130803f2SJérôme Duval		if ((curelm->field.sqe_next =				\
293130803f2SJérôme Duval			curelm->field.sqe_next->field.sqe_next) == NULL) \
294130803f2SJérôme Duval			    (head)->sqh_last = &(curelm)->field.sqe_next; \
295130803f2SJérôme Duval	}								\
296130803f2SJérôme Duval} while (/*CONSTCOND*/0)
297130803f2SJérôme Duval
298130803f2SJérôme Duval#define SIMPLEQ_FOREACH(var, head, field)				\
299130803f2SJérôme Duval	for ((var) = ((head)->sqh_first);				\
300130803f2SJérôme Duval		(var);							\
301130803f2SJérôme Duval		(var) = ((var)->field.sqe_next))
302130803f2SJérôme Duval
303130803f2SJérôme Duval/*
304130803f2SJérôme Duval * Simple queue access methods.
305130803f2SJérôme Duval */
306130803f2SJérôme Duval#define	SIMPLEQ_EMPTY(head)		((head)->sqh_first == NULL)
307130803f2SJérôme Duval#define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
308130803f2SJérôme Duval#define	SIMPLEQ_NEXT(elm, field)	((elm)->field.sqe_next)
309130803f2SJérôme Duval
310130803f2SJérôme Duval/*
311130803f2SJérôme Duval * Tail queue definitions.
312130803f2SJérôme Duval */
313130803f2SJérôme Duval#define TAILQ_HEAD(name, type)						\
314130803f2SJérôme Duvalstruct name {								\
315130803f2SJérôme Duval	struct type *tqh_first;	/* first element */			\
316130803f2SJérôme Duval	struct type **tqh_last;	/* addr of last next element */		\
317130803f2SJérôme Duval}
318130803f2SJérôme Duval
319130803f2SJérôme Duval#define TAILQ_HEAD_INITIALIZER(head)					\
320130803f2SJérôme Duval	{ NULL, &(head).tqh_first }
321130803f2SJérôme Duval
322130803f2SJérôme Duval#define TAILQ_ENTRY(type)						\
323130803f2SJérôme Duvalstruct {								\
324130803f2SJérôme Duval	struct type *tqe_next;	/* next element */			\
325130803f2SJérôme Duval	struct type **tqe_prev;	/* address of previous next element */	\
326130803f2SJérôme Duval}
327130803f2SJérôme Duval
328130803f2SJérôme Duval/*
329130803f2SJérôme Duval * Tail queue functions.
330130803f2SJérôme Duval */
331130803f2SJérôme Duval#if defined(_KERNEL) && defined(QUEUEDEBUG)
332130803f2SJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)			\
333130803f2SJérôme Duval	if ((head)->tqh_first &&					\
334130803f2SJérôme Duval	    (head)->tqh_first->field.tqe_prev != &(head)->tqh_first)	\
335130803f2SJérôme Duval		panic("TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
336130803f2SJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)			\
337130803f2SJérôme Duval	if (*(head)->tqh_last != NULL)					\
338130803f2SJérôme Duval		panic("TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__);
339130803f2SJérôme Duval#define QUEUEDEBUG_TAILQ_OP(elm, field)					\
340130803f2SJérôme Duval	if ((elm)->field.tqe_next &&					\
341130803f2SJérôme Duval	    (elm)->field.tqe_next->field.tqe_prev !=			\
342130803f2SJérôme Duval	    &(elm)->field.tqe_next)					\
343130803f2SJérôme Duval		panic("TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
344130803f2SJérôme Duval	if (*(elm)->field.tqe_prev != (elm))				\
345130803f2SJérôme Duval		panic("TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__);
346130803f2SJérôme Duval#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)				\
347130803f2SJérôme Duval	(elm)->field.tqe_next = (void *)1L;				\
348130803f2SJérôme Duval	(elm)->field.tqe_prev = (void *)1L;
349130803f2SJérôme Duval#else
350130803f2SJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
351130803f2SJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
352130803f2SJérôme Duval#define QUEUEDEBUG_TAILQ_OP(elm, field)
353130803f2SJérôme Duval#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
354130803f2SJérôme Duval#endif
355130803f2SJérôme Duval
356130803f2SJérôme Duval#define	TAILQ_INIT(head) do {						\
357130803f2SJérôme Duval	(head)->tqh_first = NULL;					\
358130803f2SJérôme Duval	(head)->tqh_last = &(head)->tqh_first;				\
359130803f2SJérôme Duval} while (/*CONSTCOND*/0)
360130803f2SJérôme Duval
361130803f2SJérôme Duval#define TAILQ_INSERT_HEAD(head, elm, field) do {			\
362130803f2SJérôme Duval	QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field)		\
363130803f2SJérôme Duval	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
364130803f2SJérôme Duval		(head)->tqh_first->field.tqe_prev =			\
365130803f2SJérôme Duval		    &(elm)->field.tqe_next;				\
366130803f2SJérôme Duval	else								\
367130803f2SJérôme Duval		(head)->tqh_last = &(elm)->field.tqe_next;		\
368130803f2SJérôme Duval	(head)->tqh_first = (elm);					\
369130803f2SJérôme Duval	(elm)->field.tqe_prev = &(head)->tqh_first;			\
370130803f2SJérôme Duval} while (/*CONSTCOND*/0)
371130803f2SJérôme Duval
372130803f2SJérôme Duval#define TAILQ_INSERT_TAIL(head, elm, field) do {			\
373130803f2SJérôme Duval	QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field)		\
374130803f2SJérôme Duval	(elm)->field.tqe_next = NULL;					\
375130803f2SJérôme Duval	(elm)->field.tqe_prev = (head)->tqh_last;			\
376130803f2SJérôme Duval	*(head)->tqh_last = (elm);					\
377130803f2SJérôme Duval	(head)->tqh_last = &(elm)->field.tqe_next;			\
378130803f2SJérôme Duval} while (/*CONSTCOND*/0)
379130803f2SJérôme Duval
380130803f2SJérôme Duval#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
381130803f2SJérôme Duval	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
382130803f2SJérôme Duval	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
383130803f2SJérôme Duval		(elm)->field.tqe_next->field.tqe_prev = 		\
384130803f2SJérôme Duval		    &(elm)->field.tqe_next;				\
385130803f2SJérôme Duval	else								\
386130803f2SJérôme Duval		(head)->tqh_last = &(elm)->field.tqe_next;		\
387130803f2SJérôme Duval	(listelm)->field.tqe_next = (elm);				\
388130803f2SJérôme Duval	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
389130803f2SJérôme Duval} while (/*CONSTCOND*/0)
390130803f2SJérôme Duval
391130803f2SJérôme Duval#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
392130803f2SJérôme Duval	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
393130803f2SJérôme Duval	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
394130803f2SJérôme Duval	(elm)->field.tqe_next = (listelm);				\
395130803f2SJérôme Duval	*(listelm)->field.tqe_prev = (elm);				\
396130803f2SJérôme Duval	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
397130803f2SJérôme Duval} while (/*CONSTCOND*/0)
398130803f2SJérôme Duval
399130803f2SJérôme Duval#define TAILQ_REMOVE(head, elm, field) do {				\
400130803f2SJérôme Duval	QUEUEDEBUG_TAILQ_OP((elm), field)				\
401130803f2SJérôme Duval	if (((elm)->field.tqe_next) != NULL)				\
402130803f2SJérôme Duval		(elm)->field.tqe_next->field.tqe_prev = 		\
403130803f2SJérôme Duval		    (elm)->field.tqe_prev;				\
404130803f2SJérôme Duval	else								\
405130803f2SJérôme Duval		(head)->tqh_last = (elm)->field.tqe_prev;		\
406130803f2SJérôme Duval	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
407130803f2SJérôme Duval	QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field);			\
408130803f2SJérôme Duval} while (/*CONSTCOND*/0)
409130803f2SJérôme Duval
410130803f2SJérôme Duval/*
411130803f2SJérôme Duval * Tail queue access methods.
412130803f2SJérôme Duval */
413130803f2SJérôme Duval#define	TAILQ_EMPTY(head)		((head)->tqh_first == NULL)
414130803f2SJérôme Duval#define	TAILQ_FIRST(head)		((head)->tqh_first)
415130803f2SJérôme Duval#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
416130803f2SJérôme Duval
417130803f2SJérôme Duval#define TAILQ_LAST(head, headname) \
418130803f2SJérôme Duval	(*(((struct headname *)((head)->tqh_last))->tqh_last))
419130803f2SJérôme Duval#define TAILQ_PREV(elm, headname, field) \
420130803f2SJérôme Duval	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
421130803f2SJérôme Duval
422130803f2SJérôme Duval#define TAILQ_FOREACH(var, head, field)					\
423130803f2SJérôme Duval	for ((var) = ((head)->tqh_first);				\
424130803f2SJérôme Duval		(var);							\
425130803f2SJérôme Duval		(var) = ((var)->field.tqe_next))
426130803f2SJérôme Duval
427130803f2SJérôme Duval#define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
428130803f2SJérôme Duval	for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));	\
429130803f2SJérôme Duval		(var);							\
430130803f2SJérôme Duval		(var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
431130803f2SJérôme Duval
432130803f2SJérôme Duval/*
433130803f2SJérôme Duval * Circular queue definitions.
434130803f2SJérôme Duval */
435130803f2SJérôme Duval#define CIRCLEQ_HEAD(name, type)					\
436130803f2SJérôme Duvalstruct name {								\
437130803f2SJérôme Duval	struct type *cqh_first;		/* first element */		\
438130803f2SJérôme Duval	struct type *cqh_last;		/* last element */		\
439130803f2SJérôme Duval}
440130803f2SJérôme Duval
441130803f2SJérôme Duval#define CIRCLEQ_HEAD_INITIALIZER(head)					\
442130803f2SJérôme Duval	{ (void *)&head, (void *)&head }
443130803f2SJérôme Duval
444130803f2SJérôme Duval#define CIRCLEQ_ENTRY(type)						\
445130803f2SJérôme Duvalstruct {								\
446130803f2SJérôme Duval	struct type *cqe_next;		/* next element */		\
447130803f2SJérôme Duval	struct type *cqe_prev;		/* previous element */		\
448130803f2SJérôme Duval}
449130803f2SJérôme Duval
450130803f2SJérôme Duval/*
451130803f2SJérôme Duval * Circular queue functions.
452130803f2SJérôme Duval */
453130803f2SJérôme Duval#define	CIRCLEQ_INIT(head) do {						\
454130803f2SJérôme Duval	(head)->cqh_first = (void *)(head);				\
455130803f2SJérôme Duval	(head)->cqh_last = (void *)(head);				\
456130803f2SJérôme Duval} while (/*CONSTCOND*/0)
457130803f2SJérôme Duval
458130803f2SJérôme Duval#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
459130803f2SJérôme Duval	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
460130803f2SJérôme Duval	(elm)->field.cqe_prev = (listelm);				\
461130803f2SJérôme Duval	if ((listelm)->field.cqe_next == (void *)(head))		\
462130803f2SJérôme Duval		(head)->cqh_last = (elm);				\
463130803f2SJérôme Duval	else								\
464130803f2SJérôme Duval		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
465130803f2SJérôme Duval	(listelm)->field.cqe_next = (elm);				\
466130803f2SJérôme Duval} while (/*CONSTCOND*/0)
467130803f2SJérôme Duval
468130803f2SJérôme Duval#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
469130803f2SJérôme Duval	(elm)->field.cqe_next = (listelm);				\
470130803f2SJérôme Duval	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
471130803f2SJérôme Duval	if ((listelm)->field.cqe_prev == (void *)(head))		\
472130803f2SJérôme Duval		(head)->cqh_first = (elm);				\
473130803f2SJérôme Duval	else								\
474130803f2SJérôme Duval		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
475130803f2SJérôme Duval	(listelm)->field.cqe_prev = (elm);				\
476130803f2SJérôme Duval} while (/*CONSTCOND*/0)
477130803f2SJérôme Duval
478130803f2SJérôme Duval#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
479130803f2SJérôme Duval	(elm)->field.cqe_next = (head)->cqh_first;			\
480130803f2SJérôme Duval	(elm)->field.cqe_prev = (void *)(head);				\
481130803f2SJérôme Duval	if ((head)->cqh_last == (void *)(head))				\
482130803f2SJérôme Duval		(head)->cqh_last = (elm);				\
483130803f2SJérôme Duval	else								\
484130803f2SJérôme Duval		(head)->cqh_first->field.cqe_prev = (elm);		\
485130803f2SJérôme Duval	(head)->cqh_first = (elm);					\
486130803f2SJérôme Duval} while (/*CONSTCOND*/0)
487130803f2SJérôme Duval
488130803f2SJérôme Duval#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
489130803f2SJérôme Duval	(elm)->field.cqe_next = (void *)(head);				\
490130803f2SJérôme Duval	(elm)->field.cqe_prev = (head)->cqh_last;			\
491130803f2SJérôme Duval	if ((head)->cqh_first == (void *)(head))			\
492130803f2SJérôme Duval		(head)->cqh_first = (elm);				\
493130803f2SJérôme Duval	else								\
494130803f2SJérôme Duval		(head)->cqh_last->field.cqe_next = (elm);		\
495130803f2SJérôme Duval	(head)->cqh_last = (elm);					\
496130803f2SJérôme Duval} while (/*CONSTCOND*/0)
497130803f2SJérôme Duval
498130803f2SJérôme Duval#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
499130803f2SJérôme Duval	if ((elm)->field.cqe_next == (void *)(head))			\
500130803f2SJérôme Duval		(head)->cqh_last = (elm)->field.cqe_prev;		\
501130803f2SJérôme Duval	else								\
502130803f2SJérôme Duval		(elm)->field.cqe_next->field.cqe_prev =			\
503130803f2SJérôme Duval		    (elm)->field.cqe_prev;				\
504130803f2SJérôme Duval	if ((elm)->field.cqe_prev == (void *)(head))			\
505130803f2SJérôme Duval		(head)->cqh_first = (elm)->field.cqe_next;		\
506130803f2SJérôme Duval	else								\
507130803f2SJérôme Duval		(elm)->field.cqe_prev->field.cqe_next =			\
508130803f2SJérôme Duval		    (elm)->field.cqe_next;				\
509130803f2SJérôme Duval} while (/*CONSTCOND*/0)
510130803f2SJérôme Duval
511130803f2SJérôme Duval#define CIRCLEQ_FOREACH(var, head, field)				\
512130803f2SJérôme Duval	for ((var) = ((head)->cqh_first);				\
513130803f2SJérôme Duval		(var) != (void *)(head);				\
514130803f2SJérôme Duval		(var) = ((var)->field.cqe_next))
515130803f2SJérôme Duval
516130803f2SJérôme Duval#define CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
517130803f2SJérôme Duval	for ((var) = ((head)->cqh_last);				\
518130803f2SJérôme Duval		(var) != (void *)(head);				\
519130803f2SJérôme Duval		(var) = ((var)->field.cqe_prev))
520130803f2SJérôme Duval
521130803f2SJérôme Duval/*
522130803f2SJérôme Duval * Circular queue access methods.
523130803f2SJérôme Duval */
524130803f2SJérôme Duval#define	CIRCLEQ_EMPTY(head)		((head)->cqh_first == (void *)(head))
525130803f2SJérôme Duval#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
526130803f2SJérôme Duval#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
527130803f2SJérôme Duval#define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
528130803f2SJérôme Duval#define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
529130803f2SJérôme Duval#endif	/* !_SYS_QUEUE_H_ */
530