1822fd939SJérôme Duval/*	$NetBSD: queue.h,v 1.31 2002/06/01 23:51:05 lukem Exp $	*/
2822fd939SJérôme Duval
3822fd939SJérôme Duval/*
4822fd939SJérôme Duval * Copyright (c) 1991, 1993
5822fd939SJérôme Duval *	The Regents of the University of California.  All rights reserved.
6822fd939SJérôme Duval *
7822fd939SJérôme Duval * Redistribution and use in source and binary forms, with or without
8822fd939SJérôme Duval * modification, are permitted provided that the following conditions
9822fd939SJérôme Duval * are met:
10822fd939SJérôme Duval * 1. Redistributions of source code must retain the above copyright
11822fd939SJérôme Duval *    notice, this list of conditions and the following disclaimer.
12822fd939SJérôme Duval * 2. Redistributions in binary form must reproduce the above copyright
13822fd939SJérôme Duval *    notice, this list of conditions and the following disclaimer in the
14822fd939SJérôme Duval *    documentation and/or other materials provided with the distribution.
15822fd939SJérôme Duval * 3. All advertising materials mentioning features or use of this software
16822fd939SJérôme Duval *    must display the following acknowledgement:
17822fd939SJérôme Duval *	This product includes software developed by the University of
18822fd939SJérôme Duval *	California, Berkeley and its contributors.
19822fd939SJérôme Duval * 4. Neither the name of the University nor the names of its contributors
20822fd939SJérôme Duval *    may be used to endorse or promote products derived from this software
21822fd939SJérôme Duval *    without specific prior written permission.
22822fd939SJérôme Duval *
23822fd939SJérôme Duval * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24822fd939SJérôme Duval * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25822fd939SJérôme Duval * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26822fd939SJérôme Duval * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27822fd939SJérôme Duval * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28822fd939SJérôme Duval * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29822fd939SJérôme Duval * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30822fd939SJérôme Duval * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31822fd939SJérôme Duval * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32822fd939SJérôme Duval * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33822fd939SJérôme Duval * SUCH DAMAGE.
34822fd939SJérôme Duval *
35822fd939SJérôme Duval *	@(#)queue.h	8.5 (Berkeley) 8/20/94
36822fd939SJérôme Duval */
37822fd939SJérôme Duval
38822fd939SJérôme Duval#ifndef	_SYS_QUEUE_H_
39822fd939SJérôme Duval#define	_SYS_QUEUE_H_
40822fd939SJérôme Duval
41822fd939SJérôme Duval/*
42822fd939SJérôme Duval * This file defines five types of data structures: singly-linked lists,
43822fd939SJérôme Duval * lists, simple queues, tail queues, and circular queues.
44822fd939SJérôme Duval *
45822fd939SJérôme Duval * A singly-linked list is headed by a single forward pointer. The
46822fd939SJérôme Duval * elements are singly linked for minimum space and pointer manipulation
47822fd939SJérôme Duval * overhead at the expense of O(n) removal for arbitrary elements. New
48822fd939SJérôme Duval * elements can be added to the list after an existing element or at the
49822fd939SJérôme Duval * head of the list.  Elements being removed from the head of the list
50822fd939SJérôme Duval * should use the explicit macro for this purpose for optimum
51822fd939SJérôme Duval * efficiency. A singly-linked list may only be traversed in the forward
52822fd939SJérôme Duval * direction.  Singly-linked lists are ideal for applications with large
53822fd939SJérôme Duval * datasets and few or no removals or for implementing a LIFO queue.
54822fd939SJérôme Duval *
55822fd939SJérôme Duval * A list is headed by a single forward pointer (or an array of forward
56822fd939SJérôme Duval * pointers for a hash table header). The elements are doubly linked
57822fd939SJérôme Duval * so that an arbitrary element can be removed without a need to
58822fd939SJérôme Duval * traverse the list. New elements can be added to the list before
59822fd939SJérôme Duval * or after an existing element or at the head of the list. A list
60822fd939SJérôme Duval * may only be traversed in the forward direction.
61822fd939SJérôme Duval *
62822fd939SJérôme Duval * A simple queue is headed by a pair of pointers, one the head of the
63822fd939SJérôme Duval * list and the other to the tail of the list. The elements are singly
64822fd939SJérôme Duval * linked to save space, so only elements can only be removed from the
65822fd939SJérôme Duval * head of the list. New elements can be added to the list after
66822fd939SJérôme Duval * an existing element, at the head of the list, or at the end of the
67822fd939SJérôme Duval * list. A simple queue may only be traversed in the forward direction.
68822fd939SJérôme Duval *
69822fd939SJérôme Duval * A tail queue is headed by a pair of pointers, one to the head of the
70822fd939SJérôme Duval * list and the other to the tail of the list. The elements are doubly
71822fd939SJérôme Duval * linked so that an arbitrary element can be removed without a need to
72822fd939SJérôme Duval * traverse the list. New elements can be added to the list before or
73822fd939SJérôme Duval * after an existing element, at the head of the list, or at the end of
74822fd939SJérôme Duval * the list. A tail queue may be traversed in either direction.
75822fd939SJérôme Duval *
76822fd939SJérôme Duval * A circle queue is headed by a pair of pointers, one to the head of the
77822fd939SJérôme Duval * list and the other to the tail of the list. The elements are doubly
78822fd939SJérôme Duval * linked so that an arbitrary element can be removed without a need to
79822fd939SJérôme Duval * traverse the list. New elements can be added to the list before or after
80822fd939SJérôme Duval * an existing element, at the head of the list, or at the end of the list.
81822fd939SJérôme Duval * A circle queue may be traversed in either direction, but has a more
82822fd939SJérôme Duval * complex end of list detection.
83822fd939SJérôme Duval *
84822fd939SJérôme Duval * For details on the use of these macros, see the queue(3) manual page.
85822fd939SJérôme Duval */
86822fd939SJérôme Duval
87822fd939SJérôme Duval/*
88822fd939SJérôme Duval * List definitions.
89822fd939SJérôme Duval */
90822fd939SJérôme Duval#define LIST_HEAD(name, type)						\
91822fd939SJérôme Duvalstruct name {								\
92822fd939SJérôme Duval	struct type *lh_first;	/* first element */			\
93822fd939SJérôme Duval}
94822fd939SJérôme Duval
95822fd939SJérôme Duval#define LIST_HEAD_INITIALIZER(head)					\
96822fd939SJérôme Duval	{ NULL }
97822fd939SJérôme Duval
98822fd939SJérôme Duval#define LIST_ENTRY(type)						\
99822fd939SJérôme Duvalstruct {								\
100822fd939SJérôme Duval	struct type *le_next;	/* next element */			\
101822fd939SJérôme Duval	struct type **le_prev;	/* address of previous next element */	\
102822fd939SJérôme Duval}
103822fd939SJérôme Duval
104822fd939SJérôme Duval/*
105822fd939SJérôme Duval * List functions.
106822fd939SJérôme Duval */
107822fd939SJérôme Duval#if defined(_KERNEL) && defined(QUEUEDEBUG)
108822fd939SJérôme Duval#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)			\
109822fd939SJérôme Duval	if ((head)->lh_first &&						\
110822fd939SJérôme Duval	    (head)->lh_first->field.le_prev != &(head)->lh_first)	\
111822fd939SJérôme Duval		panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
112822fd939SJérôme Duval#define QUEUEDEBUG_LIST_OP(elm, field)					\
113822fd939SJérôme Duval	if ((elm)->field.le_next &&					\
114822fd939SJérôme Duval	    (elm)->field.le_next->field.le_prev !=			\
115822fd939SJérôme Duval	    &(elm)->field.le_next)					\
116822fd939SJérôme Duval		panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
117822fd939SJérôme Duval	if (*(elm)->field.le_prev != (elm))				\
118822fd939SJérôme Duval		panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__);
119822fd939SJérôme Duval#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)				\
120822fd939SJérôme Duval	(elm)->field.le_next = (void *)1L;				\
121822fd939SJérôme Duval	(elm)->field.le_prev = (void *)1L;
122822fd939SJérôme Duval#else
123822fd939SJérôme Duval#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
124822fd939SJérôme Duval#define QUEUEDEBUG_LIST_OP(elm, field)
125822fd939SJérôme Duval#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
126822fd939SJérôme Duval#endif
127822fd939SJérôme Duval
128822fd939SJérôme Duval#define	LIST_INIT(head) do {						\
129822fd939SJérôme Duval	(head)->lh_first = NULL;					\
130822fd939SJérôme Duval} while (/*CONSTCOND*/0)
131822fd939SJérôme Duval
132822fd939SJérôme Duval#define LIST_INSERT_AFTER(listelm, elm, field) do {			\
133822fd939SJérôme Duval	QUEUEDEBUG_LIST_OP((listelm), field)				\
134822fd939SJérôme Duval	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
135822fd939SJérôme Duval		(listelm)->field.le_next->field.le_prev =		\
136822fd939SJérôme Duval		    &(elm)->field.le_next;				\
137822fd939SJérôme Duval	(listelm)->field.le_next = (elm);				\
138822fd939SJérôme Duval	(elm)->field.le_prev = &(listelm)->field.le_next;		\
139822fd939SJérôme Duval} while (/*CONSTCOND*/0)
140822fd939SJérôme Duval
141822fd939SJérôme Duval#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
142822fd939SJérôme Duval	QUEUEDEBUG_LIST_OP((listelm), field)				\
143822fd939SJérôme Duval	(elm)->field.le_prev = (listelm)->field.le_prev;		\
144822fd939SJérôme Duval	(elm)->field.le_next = (listelm);				\
145822fd939SJérôme Duval	*(listelm)->field.le_prev = (elm);				\
146822fd939SJérôme Duval	(listelm)->field.le_prev = &(elm)->field.le_next;		\
147822fd939SJérôme Duval} while (/*CONSTCOND*/0)
148822fd939SJérôme Duval
149822fd939SJérôme Duval#define LIST_INSERT_HEAD(head, elm, field) do {				\
150822fd939SJérôme Duval	QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field)		\
151822fd939SJérôme Duval	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
152822fd939SJérôme Duval		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
153822fd939SJérôme Duval	(head)->lh_first = (elm);					\
154822fd939SJérôme Duval	(elm)->field.le_prev = &(head)->lh_first;			\
155822fd939SJérôme Duval} while (/*CONSTCOND*/0)
156822fd939SJérôme Duval
157822fd939SJérôme Duval#define LIST_REMOVE(elm, field) do {					\
158822fd939SJérôme Duval	QUEUEDEBUG_LIST_OP((elm), field)				\
159822fd939SJérôme Duval	if ((elm)->field.le_next != NULL)				\
160822fd939SJérôme Duval		(elm)->field.le_next->field.le_prev = 			\
161822fd939SJérôme Duval		    (elm)->field.le_prev;				\
162822fd939SJérôme Duval	*(elm)->field.le_prev = (elm)->field.le_next;			\
163822fd939SJérôme Duval	QUEUEDEBUG_LIST_POSTREMOVE((elm), field)			\
164822fd939SJérôme Duval} while (/*CONSTCOND*/0)
165822fd939SJérôme Duval
166822fd939SJérôme Duval#define LIST_FOREACH(var, head, field)					\
167822fd939SJérôme Duval	for ((var) = ((head)->lh_first);				\
168822fd939SJérôme Duval		(var);							\
169822fd939SJérôme Duval		(var) = ((var)->field.le_next))
170822fd939SJérôme Duval
171822fd939SJérôme Duval/*
172822fd939SJérôme Duval * List access methods.
173822fd939SJérôme Duval */
174822fd939SJérôme Duval#define	LIST_EMPTY(head)		((head)->lh_first == NULL)
175822fd939SJérôme Duval#define	LIST_FIRST(head)		((head)->lh_first)
176822fd939SJérôme Duval#define	LIST_NEXT(elm, field)		((elm)->field.le_next)
177822fd939SJérôme Duval
178822fd939SJérôme Duval/*
179822fd939SJérôme Duval * Singly-linked List definitions.
180822fd939SJérôme Duval */
181822fd939SJérôme Duval#define SLIST_HEAD(name, type)						\
182822fd939SJérôme Duvalstruct name {								\
183822fd939SJérôme Duval	struct type *slh_first;	/* first element */			\
184822fd939SJérôme Duval}
185822fd939SJérôme Duval
186822fd939SJérôme Duval#define SLIST_HEAD_INITIALIZER(head)					\
187822fd939SJérôme Duval	{ NULL }
188822fd939SJérôme Duval
189822fd939SJérôme Duval#define SLIST_ENTRY(type)						\
190822fd939SJérôme Duvalstruct {								\
191822fd939SJérôme Duval	struct type *sle_next;	/* next element */			\
192822fd939SJérôme Duval}
193822fd939SJérôme Duval
194822fd939SJérôme Duval/*
195822fd939SJérôme Duval * Singly-linked List functions.
196822fd939SJérôme Duval */
197822fd939SJérôme Duval#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
198822fd939SJérôme Duval#define	SLIST_FIRST(head)	((head)->slh_first)
199822fd939SJérôme Duval#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
200822fd939SJérôme Duval
201822fd939SJérôme Duval#define SLIST_FOREACH(var, head, field)					\
202822fd939SJérôme Duval	for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
203822fd939SJérôme Duval
204822fd939SJérôme Duval#define SLIST_INIT(head) do {						\
205822fd939SJérôme Duval	(head)->slh_first = NULL;					\
206822fd939SJérôme Duval} while (/*CONSTCOND*/0)
207822fd939SJérôme Duval
208822fd939SJérôme Duval#define SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
209822fd939SJérôme Duval	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
210822fd939SJérôme Duval	(slistelm)->field.sle_next = (elm);				\
211822fd939SJérôme Duval} while (/*CONSTCOND*/0)
212822fd939SJérôme Duval
213822fd939SJérôme Duval#define SLIST_INSERT_HEAD(head, elm, field) do {			\
214822fd939SJérôme Duval	(elm)->field.sle_next = (head)->slh_first;			\
215822fd939SJérôme Duval	(head)->slh_first = (elm);					\
216822fd939SJérôme Duval} while (/*CONSTCOND*/0)
217822fd939SJérôme Duval
218822fd939SJérôme Duval#define SLIST_NEXT(elm, field)	((elm)->field.sle_next)
219822fd939SJérôme Duval
220822fd939SJérôme Duval#define SLIST_REMOVE_HEAD(head, field) do {				\
221822fd939SJérôme Duval	(head)->slh_first = (head)->slh_first->field.sle_next;		\
222822fd939SJérôme Duval} while (/*CONSTCOND*/0)
223822fd939SJérôme Duval
224822fd939SJérôme Duval#define SLIST_REMOVE(head, elm, type, field) do {			\
225822fd939SJérôme Duval	if ((head)->slh_first == (elm)) {				\
226822fd939SJérôme Duval		SLIST_REMOVE_HEAD((head), field);			\
227822fd939SJérôme Duval	}								\
228822fd939SJérôme Duval	else {								\
229822fd939SJérôme Duval		struct type *curelm = (head)->slh_first;		\
230822fd939SJérôme Duval		while(curelm->field.sle_next != (elm))			\
231822fd939SJérôme Duval			curelm = curelm->field.sle_next;		\
232822fd939SJérôme Duval		curelm->field.sle_next =				\
233822fd939SJérôme Duval		    curelm->field.sle_next->field.sle_next;		\
234822fd939SJérôme Duval	}								\
235822fd939SJérôme Duval} while (/*CONSTCOND*/0)
236822fd939SJérôme Duval
237822fd939SJérôme Duval/*
238822fd939SJérôme Duval * Simple queue definitions.
239822fd939SJérôme Duval */
240822fd939SJérôme Duval#define SIMPLEQ_HEAD(name, type)					\
241822fd939SJérôme Duvalstruct name {								\
242822fd939SJérôme Duval	struct type *sqh_first;	/* first element */			\
243822fd939SJérôme Duval	struct type **sqh_last;	/* addr of last next element */		\
244822fd939SJérôme Duval}
245822fd939SJérôme Duval
246822fd939SJérôme Duval#define SIMPLEQ_HEAD_INITIALIZER(head)					\
247822fd939SJérôme Duval	{ NULL, &(head).sqh_first }
248822fd939SJérôme Duval
249822fd939SJérôme Duval#define SIMPLEQ_ENTRY(type)						\
250822fd939SJérôme Duvalstruct {								\
251822fd939SJérôme Duval	struct type *sqe_next;	/* next element */			\
252822fd939SJérôme Duval}
253822fd939SJérôme Duval
254822fd939SJérôme Duval/*
255822fd939SJérôme Duval * Simple queue functions.
256822fd939SJérôme Duval */
257822fd939SJérôme Duval#define	SIMPLEQ_INIT(head) do {						\
258822fd939SJérôme Duval	(head)->sqh_first = NULL;					\
259822fd939SJérôme Duval	(head)->sqh_last = &(head)->sqh_first;				\
260822fd939SJérôme Duval} while (/*CONSTCOND*/0)
261822fd939SJérôme Duval
262822fd939SJérôme Duval#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
263822fd939SJérôme Duval	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
264822fd939SJérôme Duval		(head)->sqh_last = &(elm)->field.sqe_next;		\
265822fd939SJérôme Duval	(head)->sqh_first = (elm);					\
266822fd939SJérôme Duval} while (/*CONSTCOND*/0)
267822fd939SJérôme Duval
268822fd939SJérôme Duval#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
269822fd939SJérôme Duval	(elm)->field.sqe_next = NULL;					\
270822fd939SJérôme Duval	*(head)->sqh_last = (elm);					\
271822fd939SJérôme Duval	(head)->sqh_last = &(elm)->field.sqe_next;			\
272822fd939SJérôme Duval} while (/*CONSTCOND*/0)
273822fd939SJérôme Duval
274822fd939SJérôme Duval#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
275822fd939SJérôme Duval	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
276822fd939SJérôme Duval		(head)->sqh_last = &(elm)->field.sqe_next;		\
277822fd939SJérôme Duval	(listelm)->field.sqe_next = (elm);				\
278822fd939SJérôme Duval} while (/*CONSTCOND*/0)
279822fd939SJérôme Duval
280822fd939SJérôme Duval#define SIMPLEQ_REMOVE_HEAD(head, field) do {				\
281822fd939SJérôme Duval	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
282822fd939SJérôme Duval		(head)->sqh_last = &(head)->sqh_first;			\
283822fd939SJérôme Duval} while (/*CONSTCOND*/0)
284822fd939SJérôme Duval
285822fd939SJérôme Duval#define SIMPLEQ_REMOVE(head, elm, type, field) do {			\
286822fd939SJérôme Duval	if ((head)->sqh_first == (elm)) {				\
287822fd939SJérôme Duval		SIMPLEQ_REMOVE_HEAD((head), field);			\
288822fd939SJérôme Duval	} else {							\
289822fd939SJérôme Duval		struct type *curelm = (head)->sqh_first;		\
290822fd939SJérôme Duval		while (curelm->field.sqe_next != (elm))			\
291822fd939SJérôme Duval			curelm = curelm->field.sqe_next;		\
292822fd939SJérôme Duval		if ((curelm->field.sqe_next =				\
293822fd939SJérôme Duval			curelm->field.sqe_next->field.sqe_next) == NULL) \
294822fd939SJérôme Duval			    (head)->sqh_last = &(curelm)->field.sqe_next; \
295822fd939SJérôme Duval	}								\
296822fd939SJérôme Duval} while (/*CONSTCOND*/0)
297822fd939SJérôme Duval
298822fd939SJérôme Duval#define SIMPLEQ_FOREACH(var, head, field)				\
299822fd939SJérôme Duval	for ((var) = ((head)->sqh_first);				\
300822fd939SJérôme Duval		(var);							\
301822fd939SJérôme Duval		(var) = ((var)->field.sqe_next))
302822fd939SJérôme Duval
303822fd939SJérôme Duval/*
304822fd939SJérôme Duval * Simple queue access methods.
305822fd939SJérôme Duval */
306822fd939SJérôme Duval#define	SIMPLEQ_EMPTY(head)		((head)->sqh_first == NULL)
307822fd939SJérôme Duval#define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
308822fd939SJérôme Duval#define	SIMPLEQ_NEXT(elm, field)	((elm)->field.sqe_next)
309822fd939SJérôme Duval
310822fd939SJérôme Duval/*
311822fd939SJérôme Duval * Tail queue definitions.
312822fd939SJérôme Duval */
313822fd939SJérôme Duval#define TAILQ_HEAD(name, type)						\
314822fd939SJérôme Duvalstruct name {								\
315822fd939SJérôme Duval	struct type *tqh_first;	/* first element */			\
316822fd939SJérôme Duval	struct type **tqh_last;	/* addr of last next element */		\
317822fd939SJérôme Duval}
318822fd939SJérôme Duval
319822fd939SJérôme Duval#define TAILQ_HEAD_INITIALIZER(head)					\
320822fd939SJérôme Duval	{ NULL, &(head).tqh_first }
321822fd939SJérôme Duval
322822fd939SJérôme Duval#define TAILQ_ENTRY(type)						\
323822fd939SJérôme Duvalstruct {								\
324822fd939SJérôme Duval	struct type *tqe_next;	/* next element */			\
325822fd939SJérôme Duval	struct type **tqe_prev;	/* address of previous next element */	\
326822fd939SJérôme Duval}
327822fd939SJérôme Duval
328822fd939SJérôme Duval/*
329822fd939SJérôme Duval * Tail queue functions.
330822fd939SJérôme Duval */
331822fd939SJérôme Duval#if defined(_KERNEL) && defined(QUEUEDEBUG)
332822fd939SJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)			\
333822fd939SJérôme Duval	if ((head)->tqh_first &&					\
334822fd939SJérôme Duval	    (head)->tqh_first->field.tqe_prev != &(head)->tqh_first)	\
335822fd939SJérôme Duval		panic("TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
336822fd939SJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)			\
337822fd939SJérôme Duval	if (*(head)->tqh_last != NULL)					\
338822fd939SJérôme Duval		panic("TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__);
339822fd939SJérôme Duval#define QUEUEDEBUG_TAILQ_OP(elm, field)					\
340822fd939SJérôme Duval	if ((elm)->field.tqe_next &&					\
341822fd939SJérôme Duval	    (elm)->field.tqe_next->field.tqe_prev !=			\
342822fd939SJérôme Duval	    &(elm)->field.tqe_next)					\
343822fd939SJérôme Duval		panic("TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
344822fd939SJérôme Duval	if (*(elm)->field.tqe_prev != (elm))				\
345822fd939SJérôme Duval		panic("TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__);
346822fd939SJérôme Duval#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)				\
347822fd939SJérôme Duval	(elm)->field.tqe_next = (void *)1L;				\
348822fd939SJérôme Duval	(elm)->field.tqe_prev = (void *)1L;
349822fd939SJérôme Duval#else
350822fd939SJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
351822fd939SJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
352822fd939SJérôme Duval#define QUEUEDEBUG_TAILQ_OP(elm, field)
353822fd939SJérôme Duval#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
354822fd939SJérôme Duval#endif
355822fd939SJérôme Duval
356822fd939SJérôme Duval#define	TAILQ_INIT(head) do {						\
357822fd939SJérôme Duval	(head)->tqh_first = NULL;					\
358822fd939SJérôme Duval	(head)->tqh_last = &(head)->tqh_first;				\
359822fd939SJérôme Duval} while (/*CONSTCOND*/0)
360822fd939SJérôme Duval
361822fd939SJérôme Duval#define TAILQ_INSERT_HEAD(head, elm, field) do {			\
362822fd939SJérôme Duval	QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field)		\
363822fd939SJérôme Duval	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
364822fd939SJérôme Duval		(head)->tqh_first->field.tqe_prev =			\
365822fd939SJérôme Duval		    &(elm)->field.tqe_next;				\
366822fd939SJérôme Duval	else								\
367822fd939SJérôme Duval		(head)->tqh_last = &(elm)->field.tqe_next;		\
368822fd939SJérôme Duval	(head)->tqh_first = (elm);					\
369822fd939SJérôme Duval	(elm)->field.tqe_prev = &(head)->tqh_first;			\
370822fd939SJérôme Duval} while (/*CONSTCOND*/0)
371822fd939SJérôme Duval
372822fd939SJérôme Duval#define TAILQ_INSERT_TAIL(head, elm, field) do {			\
373822fd939SJérôme Duval	QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field)		\
374822fd939SJérôme Duval	(elm)->field.tqe_next = NULL;					\
375822fd939SJérôme Duval	(elm)->field.tqe_prev = (head)->tqh_last;			\
376822fd939SJérôme Duval	*(head)->tqh_last = (elm);					\
377822fd939SJérôme Duval	(head)->tqh_last = &(elm)->field.tqe_next;			\
378822fd939SJérôme Duval} while (/*CONSTCOND*/0)
379822fd939SJérôme Duval
380822fd939SJérôme Duval#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
381822fd939SJérôme Duval	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
382822fd939SJérôme Duval	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
383822fd939SJérôme Duval		(elm)->field.tqe_next->field.tqe_prev = 		\
384822fd939SJérôme Duval		    &(elm)->field.tqe_next;				\
385822fd939SJérôme Duval	else								\
386822fd939SJérôme Duval		(head)->tqh_last = &(elm)->field.tqe_next;		\
387822fd939SJérôme Duval	(listelm)->field.tqe_next = (elm);				\
388822fd939SJérôme Duval	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
389822fd939SJérôme Duval} while (/*CONSTCOND*/0)
390822fd939SJérôme Duval
391822fd939SJérôme Duval#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
392822fd939SJérôme Duval	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
393822fd939SJérôme Duval	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
394822fd939SJérôme Duval	(elm)->field.tqe_next = (listelm);				\
395822fd939SJérôme Duval	*(listelm)->field.tqe_prev = (elm);				\
396822fd939SJérôme Duval	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
397822fd939SJérôme Duval} while (/*CONSTCOND*/0)
398822fd939SJérôme Duval
399822fd939SJérôme Duval#define TAILQ_REMOVE(head, elm, field) do {				\
400822fd939SJérôme Duval	QUEUEDEBUG_TAILQ_OP((elm), field)				\
401822fd939SJérôme Duval	if (((elm)->field.tqe_next) != NULL)				\
402822fd939SJérôme Duval		(elm)->field.tqe_next->field.tqe_prev = 		\
403822fd939SJérôme Duval		    (elm)->field.tqe_prev;				\
404822fd939SJérôme Duval	else								\
405822fd939SJérôme Duval		(head)->tqh_last = (elm)->field.tqe_prev;		\
406822fd939SJérôme Duval	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
407822fd939SJérôme Duval	QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field);			\
408822fd939SJérôme Duval} while (/*CONSTCOND*/0)
409822fd939SJérôme Duval
410822fd939SJérôme Duval/*
411822fd939SJérôme Duval * Tail queue access methods.
412822fd939SJérôme Duval */
413822fd939SJérôme Duval#define	TAILQ_EMPTY(head)		((head)->tqh_first == NULL)
414822fd939SJérôme Duval#define	TAILQ_FIRST(head)		((head)->tqh_first)
415822fd939SJérôme Duval#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
416822fd939SJérôme Duval
417822fd939SJérôme Duval#define TAILQ_LAST(head, headname) \
418822fd939SJérôme Duval	(*(((struct headname *)((head)->tqh_last))->tqh_last))
419822fd939SJérôme Duval#define TAILQ_PREV(elm, headname, field) \
420822fd939SJérôme Duval	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
421822fd939SJérôme Duval
422822fd939SJérôme Duval#define TAILQ_FOREACH(var, head, field)					\
423822fd939SJérôme Duval	for ((var) = ((head)->tqh_first);				\
424822fd939SJérôme Duval		(var);							\
425822fd939SJérôme Duval		(var) = ((var)->field.tqe_next))
426822fd939SJérôme Duval
427822fd939SJérôme Duval#define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
428822fd939SJérôme Duval	for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));	\
429822fd939SJérôme Duval		(var);							\
430822fd939SJérôme Duval		(var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
431822fd939SJérôme Duval
432822fd939SJérôme Duval/*
433822fd939SJérôme Duval * Circular queue definitions.
434822fd939SJérôme Duval */
435822fd939SJérôme Duval#define CIRCLEQ_HEAD(name, type)					\
436822fd939SJérôme Duvalstruct name {								\
437822fd939SJérôme Duval	struct type *cqh_first;		/* first element */		\
438822fd939SJérôme Duval	struct type *cqh_last;		/* last element */		\
439822fd939SJérôme Duval}
440822fd939SJérôme Duval
441822fd939SJérôme Duval#define CIRCLEQ_HEAD_INITIALIZER(head)					\
442822fd939SJérôme Duval	{ (void *)&head, (void *)&head }
443822fd939SJérôme Duval
444822fd939SJérôme Duval#define CIRCLEQ_ENTRY(type)						\
445822fd939SJérôme Duvalstruct {								\
446822fd939SJérôme Duval	struct type *cqe_next;		/* next element */		\
447822fd939SJérôme Duval	struct type *cqe_prev;		/* previous element */		\
448822fd939SJérôme Duval}
449822fd939SJérôme Duval
450822fd939SJérôme Duval/*
451822fd939SJérôme Duval * Circular queue functions.
452822fd939SJérôme Duval */
453822fd939SJérôme Duval#define	CIRCLEQ_INIT(head) do {						\
454822fd939SJérôme Duval	(head)->cqh_first = (void *)(head);				\
455822fd939SJérôme Duval	(head)->cqh_last = (void *)(head);				\
456822fd939SJérôme Duval} while (/*CONSTCOND*/0)
457822fd939SJérôme Duval
458822fd939SJérôme Duval#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
459822fd939SJérôme Duval	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
460822fd939SJérôme Duval	(elm)->field.cqe_prev = (listelm);				\
461822fd939SJérôme Duval	if ((listelm)->field.cqe_next == (void *)(head))		\
462822fd939SJérôme Duval		(head)->cqh_last = (elm);				\
463822fd939SJérôme Duval	else								\
464822fd939SJérôme Duval		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
465822fd939SJérôme Duval	(listelm)->field.cqe_next = (elm);				\
466822fd939SJérôme Duval} while (/*CONSTCOND*/0)
467822fd939SJérôme Duval
468822fd939SJérôme Duval#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
469822fd939SJérôme Duval	(elm)->field.cqe_next = (listelm);				\
470822fd939SJérôme Duval	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
471822fd939SJérôme Duval	if ((listelm)->field.cqe_prev == (void *)(head))		\
472822fd939SJérôme Duval		(head)->cqh_first = (elm);				\
473822fd939SJérôme Duval	else								\
474822fd939SJérôme Duval		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
475822fd939SJérôme Duval	(listelm)->field.cqe_prev = (elm);				\
476822fd939SJérôme Duval} while (/*CONSTCOND*/0)
477822fd939SJérôme Duval
478822fd939SJérôme Duval#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
479822fd939SJérôme Duval	(elm)->field.cqe_next = (head)->cqh_first;			\
480822fd939SJérôme Duval	(elm)->field.cqe_prev = (void *)(head);				\
481822fd939SJérôme Duval	if ((head)->cqh_last == (void *)(head))				\
482822fd939SJérôme Duval		(head)->cqh_last = (elm);				\
483822fd939SJérôme Duval	else								\
484822fd939SJérôme Duval		(head)->cqh_first->field.cqe_prev = (elm);		\
485822fd939SJérôme Duval	(head)->cqh_first = (elm);					\
486822fd939SJérôme Duval} while (/*CONSTCOND*/0)
487822fd939SJérôme Duval
488822fd939SJérôme Duval#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
489822fd939SJérôme Duval	(elm)->field.cqe_next = (void *)(head);				\
490822fd939SJérôme Duval	(elm)->field.cqe_prev = (head)->cqh_last;			\
491822fd939SJérôme Duval	if ((head)->cqh_first == (void *)(head))			\
492822fd939SJérôme Duval		(head)->cqh_first = (elm);				\
493822fd939SJérôme Duval	else								\
494822fd939SJérôme Duval		(head)->cqh_last->field.cqe_next = (elm);		\
495822fd939SJérôme Duval	(head)->cqh_last = (elm);					\
496822fd939SJérôme Duval} while (/*CONSTCOND*/0)
497822fd939SJérôme Duval
498822fd939SJérôme Duval#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
499822fd939SJérôme Duval	if ((elm)->field.cqe_next == (void *)(head))			\
500822fd939SJérôme Duval		(head)->cqh_last = (elm)->field.cqe_prev;		\
501822fd939SJérôme Duval	else								\
502822fd939SJérôme Duval		(elm)->field.cqe_next->field.cqe_prev =			\
503822fd939SJérôme Duval		    (elm)->field.cqe_prev;				\
504822fd939SJérôme Duval	if ((elm)->field.cqe_prev == (void *)(head))			\
505822fd939SJérôme Duval		(head)->cqh_first = (elm)->field.cqe_next;		\
506822fd939SJérôme Duval	else								\
507822fd939SJérôme Duval		(elm)->field.cqe_prev->field.cqe_next =			\
508822fd939SJérôme Duval		    (elm)->field.cqe_next;				\
509822fd939SJérôme Duval} while (/*CONSTCOND*/0)
510822fd939SJérôme Duval
511822fd939SJérôme Duval#define CIRCLEQ_FOREACH(var, head, field)				\
512822fd939SJérôme Duval	for ((var) = ((head)->cqh_first);				\
513822fd939SJérôme Duval		(var) != (void *)(head);				\
514822fd939SJérôme Duval		(var) = ((var)->field.cqe_next))
515822fd939SJérôme Duval
516822fd939SJérôme Duval#define CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
517822fd939SJérôme Duval	for ((var) = ((head)->cqh_last);				\
518822fd939SJérôme Duval		(var) != (void *)(head);				\
519822fd939SJérôme Duval		(var) = ((var)->field.cqe_prev))
520822fd939SJérôme Duval
521822fd939SJérôme Duval/*
522822fd939SJérôme Duval * Circular queue access methods.
523822fd939SJérôme Duval */
524822fd939SJérôme Duval#define	CIRCLEQ_EMPTY(head)		((head)->cqh_first == (void *)(head))
525822fd939SJérôme Duval#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
526822fd939SJérôme Duval#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
527822fd939SJérôme Duval#define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
528822fd939SJérôme Duval#define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
529822fd939SJérôme Duval#endif	/* !_SYS_QUEUE_H_ */
530