xref: /titanic_50/usr/src/uts/common/sys/queue.h (revision 381a2a9a387f449fab7d0c7e97c4184c26963abf)
1*381a2a9aSdr146992 /*	$NetBSD: queue.h,v 1.42 2005/07/13 15:08:24 wiz Exp $	*/
2*381a2a9aSdr146992 
3*381a2a9aSdr146992 /*
4*381a2a9aSdr146992  * Copyright (c) 1991, 1993
5*381a2a9aSdr146992  *	The Regents of the University of California.  All rights reserved.
6*381a2a9aSdr146992  *
7*381a2a9aSdr146992  * Redistribution and use in source and binary forms, with or without
8*381a2a9aSdr146992  * modification, are permitted provided that the following conditions
9*381a2a9aSdr146992  * are met:
10*381a2a9aSdr146992  * 1. Redistributions of source code must retain the above copyright
11*381a2a9aSdr146992  *    notice, this list of conditions and the following disclaimer.
12*381a2a9aSdr146992  * 2. Redistributions in binary form must reproduce the above copyright
13*381a2a9aSdr146992  *    notice, this list of conditions and the following disclaimer in the
14*381a2a9aSdr146992  *    documentation and/or other materials provided with the distribution.
15*381a2a9aSdr146992  * 3. Neither the name of the University nor the names of its contributors
16*381a2a9aSdr146992  *    may be used to endorse or promote products derived from this software
17*381a2a9aSdr146992  *    without specific prior written permission.
18*381a2a9aSdr146992  *
19*381a2a9aSdr146992  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20*381a2a9aSdr146992  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21*381a2a9aSdr146992  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22*381a2a9aSdr146992  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23*381a2a9aSdr146992  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24*381a2a9aSdr146992  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25*381a2a9aSdr146992  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26*381a2a9aSdr146992  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27*381a2a9aSdr146992  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28*381a2a9aSdr146992  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29*381a2a9aSdr146992  * SUCH DAMAGE.
30*381a2a9aSdr146992  *
31*381a2a9aSdr146992  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
32*381a2a9aSdr146992  */
33*381a2a9aSdr146992 /*
34*381a2a9aSdr146992  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
35*381a2a9aSdr146992  * Use is subject to license terms.
36*381a2a9aSdr146992  */
37*381a2a9aSdr146992 
38*381a2a9aSdr146992 #ifndef	_SYS_QUEUE_H
39*381a2a9aSdr146992 #define	_SYS_QUEUE_H
40*381a2a9aSdr146992 
41*381a2a9aSdr146992 #pragma ident	"%Z%%M%	%I%	%E% SMI"
42*381a2a9aSdr146992 
43*381a2a9aSdr146992 #include <sys/note.h>
44*381a2a9aSdr146992 
45*381a2a9aSdr146992 #ifdef	__cplusplus
46*381a2a9aSdr146992 extern "C" {
47*381a2a9aSdr146992 #endif
48*381a2a9aSdr146992 
49*381a2a9aSdr146992 /*
50*381a2a9aSdr146992  * This file defines five types of data structures: singly-linked lists,
51*381a2a9aSdr146992  * lists, simple queues, tail queues, and circular queues.
52*381a2a9aSdr146992  *
53*381a2a9aSdr146992  * A singly-linked list is headed by a single forward pointer. The
54*381a2a9aSdr146992  * elements are singly linked for minimum space and pointer manipulation
55*381a2a9aSdr146992  * overhead at the expense of O(n) removal for arbitrary elements. New
56*381a2a9aSdr146992  * elements can be added to the list after an existing element or at the
57*381a2a9aSdr146992  * head of the list.  Elements being removed from the head of the list
58*381a2a9aSdr146992  * should use the explicit macro for this purpose for optimum
59*381a2a9aSdr146992  * efficiency. A singly-linked list may only be traversed in the forward
60*381a2a9aSdr146992  * direction.  Singly-linked lists are ideal for applications with large
61*381a2a9aSdr146992  * datasets and few or no removals or for implementing a LIFO queue.
62*381a2a9aSdr146992  *
63*381a2a9aSdr146992  * A list is headed by a single forward pointer (or an array of forward
64*381a2a9aSdr146992  * pointers for a hash table header). The elements are doubly linked
65*381a2a9aSdr146992  * so that an arbitrary element can be removed without a need to
66*381a2a9aSdr146992  * traverse the list. New elements can be added to the list before
67*381a2a9aSdr146992  * or after an existing element or at the head of the list. A list
68*381a2a9aSdr146992  * may only be traversed in the forward direction.
69*381a2a9aSdr146992  *
70*381a2a9aSdr146992  * A simple queue is headed by a pair of pointers, one the head of the
71*381a2a9aSdr146992  * list and the other to the tail of the list. The elements are singly
72*381a2a9aSdr146992  * linked to save space, so elements can only be removed from the
73*381a2a9aSdr146992  * head of the list. New elements can be added to the list after
74*381a2a9aSdr146992  * an existing element, at the head of the list, or at the end of the
75*381a2a9aSdr146992  * list. A simple queue may only be traversed in the forward direction.
76*381a2a9aSdr146992  *
77*381a2a9aSdr146992  * A tail queue is headed by a pair of pointers, one to the head of the
78*381a2a9aSdr146992  * list and the other to the tail of the list. The elements are doubly
79*381a2a9aSdr146992  * linked so that an arbitrary element can be removed without a need to
80*381a2a9aSdr146992  * traverse the list. New elements can be added to the list before or
81*381a2a9aSdr146992  * after an existing element, at the head of the list, or at the end of
82*381a2a9aSdr146992  * the list. A tail queue may be traversed in either direction.
83*381a2a9aSdr146992  *
84*381a2a9aSdr146992  * A circle queue is headed by a pair of pointers, one to the head of the
85*381a2a9aSdr146992  * list and the other to the tail of the list. The elements are doubly
86*381a2a9aSdr146992  * linked so that an arbitrary element can be removed without a need to
87*381a2a9aSdr146992  * traverse the list. New elements can be added to the list before or after
88*381a2a9aSdr146992  * an existing element, at the head of the list, or at the end of the list.
89*381a2a9aSdr146992  * A circle queue may be traversed in either direction, but has a more
90*381a2a9aSdr146992  * complex end of list detection.
91*381a2a9aSdr146992  *
92*381a2a9aSdr146992  * For details on the use of these macros, see the queue(3) manual page.
93*381a2a9aSdr146992  */
94*381a2a9aSdr146992 
95*381a2a9aSdr146992 /*
96*381a2a9aSdr146992  * List definitions.
97*381a2a9aSdr146992  */
98*381a2a9aSdr146992 #define	LIST_HEAD(name, type)						\
99*381a2a9aSdr146992 struct name {								\
100*381a2a9aSdr146992 	struct type *lh_first;	/* first element */			\
101*381a2a9aSdr146992 }
102*381a2a9aSdr146992 
103*381a2a9aSdr146992 #define	LIST_HEAD_INITIALIZER(head)					\
104*381a2a9aSdr146992 	{ NULL }
105*381a2a9aSdr146992 
106*381a2a9aSdr146992 #define	LIST_ENTRY(type)						\
107*381a2a9aSdr146992 struct {								\
108*381a2a9aSdr146992 	struct type *le_next;	/* next element */			\
109*381a2a9aSdr146992 	struct type **le_prev;	/* address of previous next element */	\
110*381a2a9aSdr146992 }
111*381a2a9aSdr146992 
112*381a2a9aSdr146992 /*
113*381a2a9aSdr146992  * List functions.
114*381a2a9aSdr146992  */
115*381a2a9aSdr146992 #if defined(_KERNEL) && defined(QUEUEDEBUG)
116*381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)			\
117*381a2a9aSdr146992 	if ((head)->lh_first &&						\
118*381a2a9aSdr146992 	    (head)->lh_first->field.le_prev != &(head)->lh_first)	\
119*381a2a9aSdr146992 		panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
120*381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_OP(elm, field)					\
121*381a2a9aSdr146992 	if ((elm)->field.le_next &&					\
122*381a2a9aSdr146992 	    (elm)->field.le_next->field.le_prev !=			\
123*381a2a9aSdr146992 	    &(elm)->field.le_next)					\
124*381a2a9aSdr146992 		panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
125*381a2a9aSdr146992 	if (*(elm)->field.le_prev != (elm))				\
126*381a2a9aSdr146992 		panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__);
127*381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_POSTREMOVE(elm, field)				\
128*381a2a9aSdr146992 	(elm)->field.le_next = (void *)1L;				\
129*381a2a9aSdr146992 	(elm)->field.le_prev = (void *)1L;
130*381a2a9aSdr146992 #else
131*381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
132*381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_OP(elm, field)
133*381a2a9aSdr146992 #define	QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
134*381a2a9aSdr146992 #endif
135*381a2a9aSdr146992 
136*381a2a9aSdr146992 #define	LIST_INIT(head) do {						\
137*381a2a9aSdr146992 	(head)->lh_first = NULL;					\
138*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
139*381a2a9aSdr146992 } while (0)
140*381a2a9aSdr146992 
141*381a2a9aSdr146992 #define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
142*381a2a9aSdr146992 	QUEUEDEBUG_LIST_OP((listelm), field)				\
143*381a2a9aSdr146992 	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
144*381a2a9aSdr146992 		(listelm)->field.le_next->field.le_prev =		\
145*381a2a9aSdr146992 		    &(elm)->field.le_next;				\
146*381a2a9aSdr146992 	(listelm)->field.le_next = (elm);				\
147*381a2a9aSdr146992 	(elm)->field.le_prev = &(listelm)->field.le_next;		\
148*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
149*381a2a9aSdr146992 } while (0)
150*381a2a9aSdr146992 
151*381a2a9aSdr146992 #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
152*381a2a9aSdr146992 	QUEUEDEBUG_LIST_OP((listelm), field)				\
153*381a2a9aSdr146992 	(elm)->field.le_prev = (listelm)->field.le_prev;		\
154*381a2a9aSdr146992 	(elm)->field.le_next = (listelm);				\
155*381a2a9aSdr146992 	*(listelm)->field.le_prev = (elm);				\
156*381a2a9aSdr146992 	(listelm)->field.le_prev = &(elm)->field.le_next;		\
157*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
158*381a2a9aSdr146992 } while (0)
159*381a2a9aSdr146992 
160*381a2a9aSdr146992 #define	LIST_INSERT_HEAD(head, elm, field) do {				\
161*381a2a9aSdr146992 	QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field)		\
162*381a2a9aSdr146992 	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
163*381a2a9aSdr146992 		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
164*381a2a9aSdr146992 	(head)->lh_first = (elm);					\
165*381a2a9aSdr146992 	(elm)->field.le_prev = &(head)->lh_first;			\
166*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
167*381a2a9aSdr146992 } while (0)
168*381a2a9aSdr146992 
169*381a2a9aSdr146992 #define	LIST_REMOVE(elm, field) do {					\
170*381a2a9aSdr146992 	QUEUEDEBUG_LIST_OP((elm), field)				\
171*381a2a9aSdr146992 	if ((elm)->field.le_next != NULL)				\
172*381a2a9aSdr146992 		(elm)->field.le_next->field.le_prev = 			\
173*381a2a9aSdr146992 		    (elm)->field.le_prev;				\
174*381a2a9aSdr146992 	*(elm)->field.le_prev = (elm)->field.le_next;			\
175*381a2a9aSdr146992 	QUEUEDEBUG_LIST_POSTREMOVE((elm), field)			\
176*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
177*381a2a9aSdr146992 } while (0)
178*381a2a9aSdr146992 
179*381a2a9aSdr146992 #define	LIST_FOREACH(var, head, field)					\
180*381a2a9aSdr146992 	for ((var) = ((head)->lh_first);				\
181*381a2a9aSdr146992 		(var);							\
182*381a2a9aSdr146992 		(var) = ((var)->field.le_next))
183*381a2a9aSdr146992 
184*381a2a9aSdr146992 /*
185*381a2a9aSdr146992  * List access methods.
186*381a2a9aSdr146992  */
187*381a2a9aSdr146992 #define	LIST_EMPTY(head)		((head)->lh_first == NULL)
188*381a2a9aSdr146992 #define	LIST_FIRST(head)		((head)->lh_first)
189*381a2a9aSdr146992 #define	LIST_NEXT(elm, field)		((elm)->field.le_next)
190*381a2a9aSdr146992 
191*381a2a9aSdr146992 
192*381a2a9aSdr146992 /*
193*381a2a9aSdr146992  * Singly-linked List definitions.
194*381a2a9aSdr146992  */
195*381a2a9aSdr146992 #define	SLIST_HEAD(name, type)						\
196*381a2a9aSdr146992 struct name {								\
197*381a2a9aSdr146992 	struct type *slh_first;	/* first element */			\
198*381a2a9aSdr146992 }
199*381a2a9aSdr146992 
200*381a2a9aSdr146992 #define	SLIST_HEAD_INITIALIZER(head)					\
201*381a2a9aSdr146992 	{ NULL }
202*381a2a9aSdr146992 
203*381a2a9aSdr146992 #define	SLIST_ENTRY(type)						\
204*381a2a9aSdr146992 struct {								\
205*381a2a9aSdr146992 	struct type *sle_next;	/* next element */			\
206*381a2a9aSdr146992 }
207*381a2a9aSdr146992 
208*381a2a9aSdr146992 /*
209*381a2a9aSdr146992  * Singly-linked List functions.
210*381a2a9aSdr146992  */
211*381a2a9aSdr146992 #define	SLIST_INIT(head) do {						\
212*381a2a9aSdr146992 	(head)->slh_first = NULL;					\
213*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
214*381a2a9aSdr146992 } while (0)
215*381a2a9aSdr146992 
216*381a2a9aSdr146992 #define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
217*381a2a9aSdr146992 	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
218*381a2a9aSdr146992 	(slistelm)->field.sle_next = (elm);				\
219*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
220*381a2a9aSdr146992 } while (0)
221*381a2a9aSdr146992 
222*381a2a9aSdr146992 #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
223*381a2a9aSdr146992 	(elm)->field.sle_next = (head)->slh_first;			\
224*381a2a9aSdr146992 	(head)->slh_first = (elm);					\
225*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
226*381a2a9aSdr146992 } while (0)
227*381a2a9aSdr146992 
228*381a2a9aSdr146992 #define	SLIST_REMOVE_HEAD(head, field) do {				\
229*381a2a9aSdr146992 	(head)->slh_first = (head)->slh_first->field.sle_next;		\
230*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
231*381a2a9aSdr146992 } while (0)
232*381a2a9aSdr146992 
233*381a2a9aSdr146992 #define	SLIST_REMOVE(head, elm, type, field) do {			\
234*381a2a9aSdr146992 	if ((head)->slh_first == (elm)) {				\
235*381a2a9aSdr146992 		SLIST_REMOVE_HEAD((head), field);			\
236*381a2a9aSdr146992 	}								\
237*381a2a9aSdr146992 	else {								\
238*381a2a9aSdr146992 		struct type *curelm = (head)->slh_first;		\
239*381a2a9aSdr146992 		while (curelm->field.sle_next != (elm))			\
240*381a2a9aSdr146992 			curelm = curelm->field.sle_next;		\
241*381a2a9aSdr146992 		curelm->field.sle_next =				\
242*381a2a9aSdr146992 		    curelm->field.sle_next->field.sle_next;		\
243*381a2a9aSdr146992 	}								\
244*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
245*381a2a9aSdr146992 } while (0)
246*381a2a9aSdr146992 
247*381a2a9aSdr146992 #define	SLIST_FOREACH(var, head, field)					\
248*381a2a9aSdr146992 	for ((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
249*381a2a9aSdr146992 
250*381a2a9aSdr146992 /*
251*381a2a9aSdr146992  * Singly-linked List access methods.
252*381a2a9aSdr146992  */
253*381a2a9aSdr146992 #define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
254*381a2a9aSdr146992 #define	SLIST_FIRST(head)	((head)->slh_first)
255*381a2a9aSdr146992 #define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
256*381a2a9aSdr146992 
257*381a2a9aSdr146992 
258*381a2a9aSdr146992 /*
259*381a2a9aSdr146992  * Singly-linked Tail queue declarations.
260*381a2a9aSdr146992  */
261*381a2a9aSdr146992 #define	STAILQ_HEAD(name, type)						\
262*381a2a9aSdr146992 struct name {								\
263*381a2a9aSdr146992 	struct type *stqh_first;	/* first element */		\
264*381a2a9aSdr146992 	struct type **stqh_last;	/* addr of last next element */	\
265*381a2a9aSdr146992 }
266*381a2a9aSdr146992 
267*381a2a9aSdr146992 #define	STAILQ_HEAD_INITIALIZER(head)					\
268*381a2a9aSdr146992 	{ NULL, &(head).stqh_first }
269*381a2a9aSdr146992 
270*381a2a9aSdr146992 #define	STAILQ_ENTRY(type)						\
271*381a2a9aSdr146992 struct {								\
272*381a2a9aSdr146992 	struct type *stqe_next;	/* next element */		\
273*381a2a9aSdr146992 }
274*381a2a9aSdr146992 
275*381a2a9aSdr146992 /*
276*381a2a9aSdr146992  * Singly-linked Tail queue functions.
277*381a2a9aSdr146992  */
278*381a2a9aSdr146992 #define	STAILQ_INIT(head) do {						\
279*381a2a9aSdr146992 	(head)->stqh_first = NULL;					\
280*381a2a9aSdr146992 	(head)->stqh_last = &(head)->stqh_first;			\
281*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
282*381a2a9aSdr146992 } while (0)
283*381a2a9aSdr146992 
284*381a2a9aSdr146992 #define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
285*381a2a9aSdr146992 	if (((elm)->field.stqe_next = (head)->stqh_first) == NULL)	\
286*381a2a9aSdr146992 		(head)->stqh_last = &(elm)->field.stqe_next;		\
287*381a2a9aSdr146992 	(head)->stqh_first = (elm);					\
288*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
289*381a2a9aSdr146992 } while (0)
290*381a2a9aSdr146992 
291*381a2a9aSdr146992 #define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
292*381a2a9aSdr146992 	(elm)->field.stqe_next = NULL;					\
293*381a2a9aSdr146992 	*(head)->stqh_last = (elm);					\
294*381a2a9aSdr146992 	(head)->stqh_last = &(elm)->field.stqe_next;			\
295*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
296*381a2a9aSdr146992 } while (0)
297*381a2a9aSdr146992 
298*381a2a9aSdr146992 #define	STAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
299*381a2a9aSdr146992 	if (((elm)->field.stqe_next = (listelm)->field.stqe_next)	\
300*381a2a9aSdr146992 	    == NULL)							\
301*381a2a9aSdr146992 		(head)->stqh_last = &(elm)->field.stqe_next;		\
302*381a2a9aSdr146992 	(listelm)->field.stqe_next = (elm);				\
303*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
304*381a2a9aSdr146992 } while (0)
305*381a2a9aSdr146992 
306*381a2a9aSdr146992 #define	STAILQ_REMOVE_HEAD(head, field) do {				\
307*381a2a9aSdr146992 	if (((head)->stqh_first = (head)->stqh_first->field.stqe_next)	\
308*381a2a9aSdr146992 	    == NULL) 							\
309*381a2a9aSdr146992 		(head)->stqh_last = &(head)->stqh_first;		\
310*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
311*381a2a9aSdr146992 } while (0)
312*381a2a9aSdr146992 
313*381a2a9aSdr146992 #define	STAILQ_REMOVE(head, elm, type, field) do {			\
314*381a2a9aSdr146992 	if ((head)->stqh_first == (elm)) {				\
315*381a2a9aSdr146992 		STAILQ_REMOVE_HEAD((head), field);			\
316*381a2a9aSdr146992 	} else {							\
317*381a2a9aSdr146992 		struct type *curelm = (head)->stqh_first;		\
318*381a2a9aSdr146992 		while (curelm->field.stqe_next != (elm))		\
319*381a2a9aSdr146992 			curelm = curelm->field.stqe_next;		\
320*381a2a9aSdr146992 		if ((curelm->field.stqe_next =				\
321*381a2a9aSdr146992 			curelm->field.stqe_next->field.stqe_next) == NULL) \
322*381a2a9aSdr146992 			    (head)->stqh_last = &(curelm)->field.stqe_next; \
323*381a2a9aSdr146992 	}								\
324*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
325*381a2a9aSdr146992 } while (0)
326*381a2a9aSdr146992 
327*381a2a9aSdr146992 #define	STAILQ_FOREACH(var, head, field)				\
328*381a2a9aSdr146992 	for ((var) = ((head)->stqh_first);				\
329*381a2a9aSdr146992 		(var);							\
330*381a2a9aSdr146992 		(var) = ((var)->field.stqe_next))
331*381a2a9aSdr146992 
332*381a2a9aSdr146992 /*
333*381a2a9aSdr146992  * Singly-linked Tail queue access methods.
334*381a2a9aSdr146992  */
335*381a2a9aSdr146992 #define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)
336*381a2a9aSdr146992 #define	STAILQ_FIRST(head)	((head)->stqh_first)
337*381a2a9aSdr146992 #define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
338*381a2a9aSdr146992 
339*381a2a9aSdr146992 
340*381a2a9aSdr146992 /*
341*381a2a9aSdr146992  * Simple queue definitions.
342*381a2a9aSdr146992  */
343*381a2a9aSdr146992 #define	SIMPLEQ_HEAD(name, type)					\
344*381a2a9aSdr146992 struct name {								\
345*381a2a9aSdr146992 	struct type *sqh_first;	/* first element */		\
346*381a2a9aSdr146992 	struct type **sqh_last;	/* addr of last next element */	\
347*381a2a9aSdr146992 }
348*381a2a9aSdr146992 
349*381a2a9aSdr146992 #define	SIMPLEQ_HEAD_INITIALIZER(head)					\
350*381a2a9aSdr146992 	{ NULL, &(head).sqh_first }
351*381a2a9aSdr146992 
352*381a2a9aSdr146992 #define	SIMPLEQ_ENTRY(type)						\
353*381a2a9aSdr146992 struct {								\
354*381a2a9aSdr146992 	struct type *sqe_next;	/* next element */			\
355*381a2a9aSdr146992 }
356*381a2a9aSdr146992 
357*381a2a9aSdr146992 /*
358*381a2a9aSdr146992  * Simple queue functions.
359*381a2a9aSdr146992  */
360*381a2a9aSdr146992 #define	SIMPLEQ_INIT(head) do {						\
361*381a2a9aSdr146992 	(head)->sqh_first = NULL;					\
362*381a2a9aSdr146992 	(head)->sqh_last = &(head)->sqh_first;				\
363*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
364*381a2a9aSdr146992 } while (0)
365*381a2a9aSdr146992 
366*381a2a9aSdr146992 #define	SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
367*381a2a9aSdr146992 	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
368*381a2a9aSdr146992 		(head)->sqh_last = &(elm)->field.sqe_next;		\
369*381a2a9aSdr146992 	(head)->sqh_first = (elm);					\
370*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
371*381a2a9aSdr146992 } while (0)
372*381a2a9aSdr146992 
373*381a2a9aSdr146992 #define	SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
374*381a2a9aSdr146992 	(elm)->field.sqe_next = NULL;					\
375*381a2a9aSdr146992 	*(head)->sqh_last = (elm);					\
376*381a2a9aSdr146992 	(head)->sqh_last = &(elm)->field.sqe_next;			\
377*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
378*381a2a9aSdr146992 } while (0)
379*381a2a9aSdr146992 
380*381a2a9aSdr146992 #define	SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
381*381a2a9aSdr146992 	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
382*381a2a9aSdr146992 		(head)->sqh_last = &(elm)->field.sqe_next;		\
383*381a2a9aSdr146992 	(listelm)->field.sqe_next = (elm);				\
384*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
385*381a2a9aSdr146992 } while (0)
386*381a2a9aSdr146992 
387*381a2a9aSdr146992 #define	SIMPLEQ_REMOVE_HEAD(head, field) do {				\
388*381a2a9aSdr146992 	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
389*381a2a9aSdr146992 		(head)->sqh_last = &(head)->sqh_first;			\
390*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
391*381a2a9aSdr146992 } while (0)
392*381a2a9aSdr146992 
393*381a2a9aSdr146992 #define	SIMPLEQ_REMOVE(head, elm, type, field) do {			\
394*381a2a9aSdr146992 	if ((head)->sqh_first == (elm)) {				\
395*381a2a9aSdr146992 		SIMPLEQ_REMOVE_HEAD((head), field);			\
396*381a2a9aSdr146992 	} else {							\
397*381a2a9aSdr146992 		struct type *curelm = (head)->sqh_first;		\
398*381a2a9aSdr146992 		while (curelm->field.sqe_next != (elm))			\
399*381a2a9aSdr146992 			curelm = curelm->field.sqe_next;		\
400*381a2a9aSdr146992 		if ((curelm->field.sqe_next =				\
401*381a2a9aSdr146992 			curelm->field.sqe_next->field.sqe_next) == NULL) \
402*381a2a9aSdr146992 			    (head)->sqh_last = &(curelm)->field.sqe_next; \
403*381a2a9aSdr146992 	}								\
404*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
405*381a2a9aSdr146992 } while (0)
406*381a2a9aSdr146992 
407*381a2a9aSdr146992 #define	SIMPLEQ_FOREACH(var, head, field)				\
408*381a2a9aSdr146992 	for ((var) = ((head)->sqh_first);				\
409*381a2a9aSdr146992 		(var);							\
410*381a2a9aSdr146992 		(var) = ((var)->field.sqe_next))
411*381a2a9aSdr146992 
412*381a2a9aSdr146992 /*
413*381a2a9aSdr146992  * Simple queue access methods.
414*381a2a9aSdr146992  */
415*381a2a9aSdr146992 #define	SIMPLEQ_EMPTY(head)		((head)->sqh_first == NULL)
416*381a2a9aSdr146992 #define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
417*381a2a9aSdr146992 #define	SIMPLEQ_NEXT(elm, field)	((elm)->field.sqe_next)
418*381a2a9aSdr146992 
419*381a2a9aSdr146992 
420*381a2a9aSdr146992 /*
421*381a2a9aSdr146992  * Tail queue definitions.
422*381a2a9aSdr146992  */
423*381a2a9aSdr146992 #define	_TAILQ_HEAD(name, type)						\
424*381a2a9aSdr146992 struct name {								\
425*381a2a9aSdr146992 	type *tqh_first;		/* first element */		\
426*381a2a9aSdr146992 	type **tqh_last;	/* addr of last next element */		\
427*381a2a9aSdr146992 }
428*381a2a9aSdr146992 #define	TAILQ_HEAD(name, type)	_TAILQ_HEAD(name, struct type)
429*381a2a9aSdr146992 
430*381a2a9aSdr146992 #define	TAILQ_HEAD_INITIALIZER(head)					\
431*381a2a9aSdr146992 	{ NULL, &(head).tqh_first }
432*381a2a9aSdr146992 
433*381a2a9aSdr146992 #define	_TAILQ_ENTRY(type)						\
434*381a2a9aSdr146992 struct {								\
435*381a2a9aSdr146992 	type *tqe_next;		/* next element */			\
436*381a2a9aSdr146992 	type **tqe_prev;	/* address of previous next element */\
437*381a2a9aSdr146992 }
438*381a2a9aSdr146992 #define	TAILQ_ENTRY(type)	_TAILQ_ENTRY(struct type)
439*381a2a9aSdr146992 
440*381a2a9aSdr146992 /*
441*381a2a9aSdr146992  * Tail queue functions.
442*381a2a9aSdr146992  */
443*381a2a9aSdr146992 #if defined(_KERNEL) && defined(QUEUEDEBUG)
444*381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)			\
445*381a2a9aSdr146992 	if ((head)->tqh_first &&					\
446*381a2a9aSdr146992 	    (head)->tqh_first->field.tqe_prev != &(head)->tqh_first)	\
447*381a2a9aSdr146992 		panic("TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
448*381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)			\
449*381a2a9aSdr146992 	if (*(head)->tqh_last != NULL)					\
450*381a2a9aSdr146992 		panic("TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__);
451*381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_OP(elm, field)					\
452*381a2a9aSdr146992 	if ((elm)->field.tqe_next &&					\
453*381a2a9aSdr146992 	    (elm)->field.tqe_next->field.tqe_prev !=			\
454*381a2a9aSdr146992 	    &(elm)->field.tqe_next)					\
455*381a2a9aSdr146992 		panic("TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
456*381a2a9aSdr146992 	if (*(elm)->field.tqe_prev != (elm))				\
457*381a2a9aSdr146992 		panic("TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__);
458*381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)			\
459*381a2a9aSdr146992 	if ((elm)->field.tqe_next == NULL &&				\
460*381a2a9aSdr146992 	    (head)->tqh_last != &(elm)->field.tqe_next)			\
461*381a2a9aSdr146992 		panic("TAILQ_PREREMOVE head %p elm %p %s:%d",		\
462*381a2a9aSdr146992 		(head), (elm), __FILE__, __LINE__);
463*381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)				\
464*381a2a9aSdr146992 	(elm)->field.tqe_next = (void *)1L;				\
465*381a2a9aSdr146992 	(elm)->field.tqe_prev = (void *)1L;
466*381a2a9aSdr146992 #else
467*381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
468*381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
469*381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_OP(elm, field)
470*381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)
471*381a2a9aSdr146992 #define	QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
472*381a2a9aSdr146992 #endif
473*381a2a9aSdr146992 
474*381a2a9aSdr146992 #define	TAILQ_INIT(head) do {						\
475*381a2a9aSdr146992 	(head)->tqh_first = NULL;					\
476*381a2a9aSdr146992 	(head)->tqh_last = &(head)->tqh_first;				\
477*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
478*381a2a9aSdr146992 } while (0)
479*381a2a9aSdr146992 
480*381a2a9aSdr146992 #define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
481*381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field)		\
482*381a2a9aSdr146992 	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
483*381a2a9aSdr146992 		(head)->tqh_first->field.tqe_prev =			\
484*381a2a9aSdr146992 		    &(elm)->field.tqe_next;				\
485*381a2a9aSdr146992 	else								\
486*381a2a9aSdr146992 		(head)->tqh_last = &(elm)->field.tqe_next;		\
487*381a2a9aSdr146992 	(head)->tqh_first = (elm);					\
488*381a2a9aSdr146992 	(elm)->field.tqe_prev = &(head)->tqh_first;			\
489*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
490*381a2a9aSdr146992 } while (0)
491*381a2a9aSdr146992 
492*381a2a9aSdr146992 #define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
493*381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field)		\
494*381a2a9aSdr146992 	(elm)->field.tqe_next = NULL;					\
495*381a2a9aSdr146992 	(elm)->field.tqe_prev = (head)->tqh_last;			\
496*381a2a9aSdr146992 	*(head)->tqh_last = (elm);					\
497*381a2a9aSdr146992 	(head)->tqh_last = &(elm)->field.tqe_next;			\
498*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
499*381a2a9aSdr146992 } while (0)
500*381a2a9aSdr146992 
501*381a2a9aSdr146992 #define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
502*381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
503*381a2a9aSdr146992 	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
504*381a2a9aSdr146992 		(elm)->field.tqe_next->field.tqe_prev = 		\
505*381a2a9aSdr146992 		    &(elm)->field.tqe_next;				\
506*381a2a9aSdr146992 	else								\
507*381a2a9aSdr146992 		(head)->tqh_last = &(elm)->field.tqe_next;		\
508*381a2a9aSdr146992 	(listelm)->field.tqe_next = (elm);				\
509*381a2a9aSdr146992 	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
510*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
511*381a2a9aSdr146992 } while (0)
512*381a2a9aSdr146992 
513*381a2a9aSdr146992 #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
514*381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
515*381a2a9aSdr146992 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
516*381a2a9aSdr146992 	(elm)->field.tqe_next = (listelm);				\
517*381a2a9aSdr146992 	*(listelm)->field.tqe_prev = (elm);				\
518*381a2a9aSdr146992 	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
519*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
520*381a2a9aSdr146992 } while (0)
521*381a2a9aSdr146992 
522*381a2a9aSdr146992 #define	TAILQ_REMOVE(head, elm, field) do {				\
523*381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field)		\
524*381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_OP((elm), field)				\
525*381a2a9aSdr146992 	if (((elm)->field.tqe_next) != NULL)				\
526*381a2a9aSdr146992 		(elm)->field.tqe_next->field.tqe_prev = 		\
527*381a2a9aSdr146992 		    (elm)->field.tqe_prev;				\
528*381a2a9aSdr146992 	else								\
529*381a2a9aSdr146992 		(head)->tqh_last = (elm)->field.tqe_prev;		\
530*381a2a9aSdr146992 	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
531*381a2a9aSdr146992 	QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field);			\
532*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
533*381a2a9aSdr146992 } while (0)
534*381a2a9aSdr146992 
535*381a2a9aSdr146992 #define	TAILQ_FOREACH(var, head, field)					\
536*381a2a9aSdr146992 	for ((var) = ((head)->tqh_first);				\
537*381a2a9aSdr146992 		(var);							\
538*381a2a9aSdr146992 		(var) = ((var)->field.tqe_next))
539*381a2a9aSdr146992 
540*381a2a9aSdr146992 #define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
541*381a2a9aSdr146992 	for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));\
542*381a2a9aSdr146992 		(var);							\
543*381a2a9aSdr146992 		(var) = 						\
544*381a2a9aSdr146992 		    (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
545*381a2a9aSdr146992 
546*381a2a9aSdr146992 /*
547*381a2a9aSdr146992  * Tail queue access methods.
548*381a2a9aSdr146992  */
549*381a2a9aSdr146992 #define	TAILQ_EMPTY(head)		((head)->tqh_first == NULL)
550*381a2a9aSdr146992 #define	TAILQ_FIRST(head)		((head)->tqh_first)
551*381a2a9aSdr146992 #define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
552*381a2a9aSdr146992 
553*381a2a9aSdr146992 #define	TAILQ_LAST(head, headname) \
554*381a2a9aSdr146992 	(*(((struct headname *)((head)->tqh_last))->tqh_last))
555*381a2a9aSdr146992 #define	TAILQ_PREV(elm, headname, field) \
556*381a2a9aSdr146992 	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
557*381a2a9aSdr146992 
558*381a2a9aSdr146992 
559*381a2a9aSdr146992 /*
560*381a2a9aSdr146992  * Circular queue definitions.
561*381a2a9aSdr146992  */
562*381a2a9aSdr146992 #define	CIRCLEQ_HEAD(name, type)					\
563*381a2a9aSdr146992 struct name {								\
564*381a2a9aSdr146992 	struct type *cqh_first;		/* first element */	\
565*381a2a9aSdr146992 	struct type *cqh_last;		/* last element */		\
566*381a2a9aSdr146992 }
567*381a2a9aSdr146992 
568*381a2a9aSdr146992 #define	CIRCLEQ_HEAD_INITIALIZER(head)					\
569*381a2a9aSdr146992 	{ (void *)&head, (void *)&head }
570*381a2a9aSdr146992 
571*381a2a9aSdr146992 #define	CIRCLEQ_ENTRY(type)						\
572*381a2a9aSdr146992 struct {								\
573*381a2a9aSdr146992 	struct type *cqe_next;		/* next element */		\
574*381a2a9aSdr146992 	struct type *cqe_prev;		/* previous element */		\
575*381a2a9aSdr146992 }
576*381a2a9aSdr146992 
577*381a2a9aSdr146992 /*
578*381a2a9aSdr146992  * Circular queue functions.
579*381a2a9aSdr146992  */
580*381a2a9aSdr146992 #define	CIRCLEQ_INIT(head) do {						\
581*381a2a9aSdr146992 	(head)->cqh_first = (void *)(head);				\
582*381a2a9aSdr146992 	(head)->cqh_last = (void *)(head);				\
583*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
584*381a2a9aSdr146992 } while (0)
585*381a2a9aSdr146992 
586*381a2a9aSdr146992 #define	CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
587*381a2a9aSdr146992 	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
588*381a2a9aSdr146992 	(elm)->field.cqe_prev = (listelm);				\
589*381a2a9aSdr146992 	if ((listelm)->field.cqe_next == (void *)(head))		\
590*381a2a9aSdr146992 		(head)->cqh_last = (elm);				\
591*381a2a9aSdr146992 	else								\
592*381a2a9aSdr146992 		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
593*381a2a9aSdr146992 	(listelm)->field.cqe_next = (elm);				\
594*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
595*381a2a9aSdr146992 } while (0)
596*381a2a9aSdr146992 
597*381a2a9aSdr146992 #define	CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
598*381a2a9aSdr146992 	(elm)->field.cqe_next = (listelm);				\
599*381a2a9aSdr146992 	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
600*381a2a9aSdr146992 	if ((listelm)->field.cqe_prev == (void *)(head))		\
601*381a2a9aSdr146992 		(head)->cqh_first = (elm);				\
602*381a2a9aSdr146992 	else								\
603*381a2a9aSdr146992 		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
604*381a2a9aSdr146992 	(listelm)->field.cqe_prev = (elm);				\
605*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
606*381a2a9aSdr146992 } while (0)
607*381a2a9aSdr146992 
608*381a2a9aSdr146992 #define	CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
609*381a2a9aSdr146992 	(elm)->field.cqe_next = (head)->cqh_first;			\
610*381a2a9aSdr146992 	(elm)->field.cqe_prev = (void *)(head);				\
611*381a2a9aSdr146992 	if ((head)->cqh_last == (void *)(head))			\
612*381a2a9aSdr146992 		(head)->cqh_last = (elm);				\
613*381a2a9aSdr146992 	else								\
614*381a2a9aSdr146992 		(head)->cqh_first->field.cqe_prev = (elm);		\
615*381a2a9aSdr146992 	(head)->cqh_first = (elm);					\
616*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
617*381a2a9aSdr146992 } while (0)
618*381a2a9aSdr146992 
619*381a2a9aSdr146992 #define	CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
620*381a2a9aSdr146992 	(elm)->field.cqe_next = (void *)(head);				\
621*381a2a9aSdr146992 	(elm)->field.cqe_prev = (head)->cqh_last;			\
622*381a2a9aSdr146992 	if ((head)->cqh_first == (void *)(head))			\
623*381a2a9aSdr146992 		(head)->cqh_first = (elm);				\
624*381a2a9aSdr146992 	else								\
625*381a2a9aSdr146992 		(head)->cqh_last->field.cqe_next = (elm);		\
626*381a2a9aSdr146992 	(head)->cqh_last = (elm);					\
627*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
628*381a2a9aSdr146992 } while (0)
629*381a2a9aSdr146992 
630*381a2a9aSdr146992 #define	CIRCLEQ_REMOVE(head, elm, field) do {				\
631*381a2a9aSdr146992 	if ((elm)->field.cqe_next == (void *)(head))			\
632*381a2a9aSdr146992 		(head)->cqh_last = (elm)->field.cqe_prev;		\
633*381a2a9aSdr146992 	else								\
634*381a2a9aSdr146992 		(elm)->field.cqe_next->field.cqe_prev =			\
635*381a2a9aSdr146992 		    (elm)->field.cqe_prev;				\
636*381a2a9aSdr146992 	if ((elm)->field.cqe_prev == (void *)(head))			\
637*381a2a9aSdr146992 		(head)->cqh_first = (elm)->field.cqe_next;		\
638*381a2a9aSdr146992 	else								\
639*381a2a9aSdr146992 		(elm)->field.cqe_prev->field.cqe_next =			\
640*381a2a9aSdr146992 		    (elm)->field.cqe_next;				\
641*381a2a9aSdr146992 	_NOTE(CONSTCOND)						\
642*381a2a9aSdr146992 } while (0)
643*381a2a9aSdr146992 
644*381a2a9aSdr146992 #define	CIRCLEQ_FOREACH(var, head, field)				\
645*381a2a9aSdr146992 	for ((var) = ((head)->cqh_first);				\
646*381a2a9aSdr146992 		(var) != (void *)(head);				\
647*381a2a9aSdr146992 		(var) = ((var)->field.cqe_next))
648*381a2a9aSdr146992 
649*381a2a9aSdr146992 #define	CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
650*381a2a9aSdr146992 	for ((var) = ((head)->cqh_last);				\
651*381a2a9aSdr146992 		(var) != (void *)(head);				\
652*381a2a9aSdr146992 		(var) = ((var)->field.cqe_prev))
653*381a2a9aSdr146992 
654*381a2a9aSdr146992 /*
655*381a2a9aSdr146992  * Circular queue access methods.
656*381a2a9aSdr146992  */
657*381a2a9aSdr146992 #define	CIRCLEQ_EMPTY(head)		((head)->cqh_first == (void *)(head))
658*381a2a9aSdr146992 #define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
659*381a2a9aSdr146992 #define	CIRCLEQ_LAST(head)		((head)->cqh_last)
660*381a2a9aSdr146992 #define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
661*381a2a9aSdr146992 #define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
662*381a2a9aSdr146992 
663*381a2a9aSdr146992 #ifdef	__cplusplus
664*381a2a9aSdr146992 }
665*381a2a9aSdr146992 #endif
666*381a2a9aSdr146992 
667*381a2a9aSdr146992 #endif	/* !_SYS_QUEUE_H */
668