1adfdbf12SDamien Miller /*	$OpenBSD: queue.h,v 1.45 2018/07/12 14:22:54 sashan Exp $	*/
29b481510SDamien Miller /*	$NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $	*/
39b481510SDamien Miller 
49b481510SDamien Miller /*
59b481510SDamien Miller  * Copyright (c) 1991, 1993
69b481510SDamien Miller  *	The Regents of the University of California.  All rights reserved.
79b481510SDamien Miller  *
89b481510SDamien Miller  * Redistribution and use in source and binary forms, with or without
99b481510SDamien Miller  * modification, are permitted provided that the following conditions
109b481510SDamien Miller  * are met:
119b481510SDamien Miller  * 1. Redistributions of source code must retain the above copyright
129b481510SDamien Miller  *    notice, this list of conditions and the following disclaimer.
139b481510SDamien Miller  * 2. Redistributions in binary form must reproduce the above copyright
149b481510SDamien Miller  *    notice, this list of conditions and the following disclaimer in the
159b481510SDamien Miller  *    documentation and/or other materials provided with the distribution.
16329638e4SDamien Miller  * 3. Neither the name of the University nor the names of its contributors
179b481510SDamien Miller  *    may be used to endorse or promote products derived from this software
189b481510SDamien Miller  *    without specific prior written permission.
199b481510SDamien Miller  *
209b481510SDamien Miller  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
219b481510SDamien Miller  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
229b481510SDamien Miller  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
239b481510SDamien Miller  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
249b481510SDamien Miller  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
259b481510SDamien Miller  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
269b481510SDamien Miller  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
279b481510SDamien Miller  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
289b481510SDamien Miller  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
299b481510SDamien Miller  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
309b481510SDamien Miller  * SUCH DAMAGE.
319b481510SDamien Miller  *
329b481510SDamien Miller  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
339b481510SDamien Miller  */
349b481510SDamien Miller 
357f24a0e6SDarren Tucker /* OPENBSD ORIGINAL: sys/sys/queue.h */
367f24a0e6SDarren Tucker 
37efec7c23SBen Lindstrom #ifndef	_FAKE_QUEUE_H_
38efec7c23SBen Lindstrom #define	_FAKE_QUEUE_H_
39efec7c23SBen Lindstrom 
40efec7c23SBen Lindstrom /*
41efec7c23SBen Lindstrom  * Require for OS/X and other platforms that have old/broken/incomplete
42efec7c23SBen Lindstrom  * <sys/queue.h>.
43efec7c23SBen Lindstrom  */
44*c9e3be9fSDamien Miller #undef CIRCLEQ_EMPTY
45*c9e3be9fSDamien Miller #undef CIRCLEQ_END
46efec7c23SBen Lindstrom #undef CIRCLEQ_ENTRY
47efec7c23SBen Lindstrom #undef CIRCLEQ_FIRST
48efec7c23SBen Lindstrom #undef CIRCLEQ_FOREACH
49efec7c23SBen Lindstrom #undef CIRCLEQ_FOREACH_REVERSE
50*c9e3be9fSDamien Miller #undef CIRCLEQ_HEAD
51*c9e3be9fSDamien Miller #undef CIRCLEQ_HEAD_INITIALIZER
52efec7c23SBen Lindstrom #undef CIRCLEQ_INIT
53efec7c23SBen Lindstrom #undef CIRCLEQ_INSERT_AFTER
54efec7c23SBen Lindstrom #undef CIRCLEQ_INSERT_BEFORE
55efec7c23SBen Lindstrom #undef CIRCLEQ_INSERT_HEAD
56efec7c23SBen Lindstrom #undef CIRCLEQ_INSERT_TAIL
57*c9e3be9fSDamien Miller #undef CIRCLEQ_LAST
58*c9e3be9fSDamien Miller #undef CIRCLEQ_NEXT
59*c9e3be9fSDamien Miller #undef CIRCLEQ_PREV
60efec7c23SBen Lindstrom #undef CIRCLEQ_REMOVE
61efec7c23SBen Lindstrom #undef CIRCLEQ_REPLACE
62*c9e3be9fSDamien Miller #undef LIST_EMPTY
63*c9e3be9fSDamien Miller #undef LIST_END
64*c9e3be9fSDamien Miller #undef LIST_ENTRY
65*c9e3be9fSDamien Miller #undef LIST_FIRST
66*c9e3be9fSDamien Miller #undef LIST_FOREACH
67*c9e3be9fSDamien Miller #undef LIST_FOREACH_SAFE
68*c9e3be9fSDamien Miller #undef LIST_HEAD
69*c9e3be9fSDamien Miller #undef LIST_HEAD_INITIALIZER
70*c9e3be9fSDamien Miller #undef LIST_INIT
71*c9e3be9fSDamien Miller #undef LIST_INSERT_AFTER
72*c9e3be9fSDamien Miller #undef LIST_INSERT_BEFORE
73*c9e3be9fSDamien Miller #undef LIST_INSERT_HEAD
74*c9e3be9fSDamien Miller #undef LIST_NEXT
75*c9e3be9fSDamien Miller #undef LIST_REMOVE
76*c9e3be9fSDamien Miller #undef LIST_REPLACE
77*c9e3be9fSDamien Miller #undef SIMPLEQ_CONCAT
78*c9e3be9fSDamien Miller #undef SIMPLEQ_EMPTY
79*c9e3be9fSDamien Miller #undef SIMPLEQ_END
80*c9e3be9fSDamien Miller #undef SIMPLEQ_ENTRY
81*c9e3be9fSDamien Miller #undef SIMPLEQ_FIRST
82*c9e3be9fSDamien Miller #undef SIMPLEQ_FOREACH
83*c9e3be9fSDamien Miller #undef SIMPLEQ_FOREACH_SAFE
84*c9e3be9fSDamien Miller #undef SIMPLEQ_HEAD
85*c9e3be9fSDamien Miller #undef SIMPLEQ_HEAD_INITIALIZER
86*c9e3be9fSDamien Miller #undef SIMPLEQ_INIT
87*c9e3be9fSDamien Miller #undef SIMPLEQ_INSERT_AFTER
88*c9e3be9fSDamien Miller #undef SIMPLEQ_INSERT_HEAD
89*c9e3be9fSDamien Miller #undef SIMPLEQ_INSERT_TAIL
90*c9e3be9fSDamien Miller #undef SIMPLEQ_NEXT
91*c9e3be9fSDamien Miller #undef SIMPLEQ_REMOVE_AFTER
92*c9e3be9fSDamien Miller #undef SIMPLEQ_REMOVE_HEAD
93*c9e3be9fSDamien Miller #undef SLIST_EMPTY
94*c9e3be9fSDamien Miller #undef SLIST_END
95*c9e3be9fSDamien Miller #undef SLIST_ENTRY
96*c9e3be9fSDamien Miller #undef SLIST_FIRST
97*c9e3be9fSDamien Miller #undef SLIST_FOREACH
98*c9e3be9fSDamien Miller #undef SLIST_FOREACH_PREVPTR
99*c9e3be9fSDamien Miller #undef SLIST_FOREACH_SAFE
100*c9e3be9fSDamien Miller #undef SLIST_HEAD
101*c9e3be9fSDamien Miller #undef SLIST_HEAD_INITIALIZER
102*c9e3be9fSDamien Miller #undef SLIST_INIT
103*c9e3be9fSDamien Miller #undef SLIST_INSERT_AFTER
104*c9e3be9fSDamien Miller #undef SLIST_INSERT_HEAD
105*c9e3be9fSDamien Miller #undef SLIST_NEXT
106*c9e3be9fSDamien Miller #undef SLIST_REMOVE
107*c9e3be9fSDamien Miller #undef SLIST_REMOVE_AFTER
108*c9e3be9fSDamien Miller #undef SLIST_REMOVE_HEAD
109*c9e3be9fSDamien Miller #undef SLIST_REMOVE_NEXT
110*c9e3be9fSDamien Miller #undef TAILQ_CONCAT
111*c9e3be9fSDamien Miller #undef TAILQ_EMPTY
112*c9e3be9fSDamien Miller #undef TAILQ_END
113*c9e3be9fSDamien Miller #undef TAILQ_ENTRY
114*c9e3be9fSDamien Miller #undef TAILQ_FIRST
115*c9e3be9fSDamien Miller #undef TAILQ_FOREACH
116*c9e3be9fSDamien Miller #undef TAILQ_FOREACH_REVERSE
117*c9e3be9fSDamien Miller #undef TAILQ_FOREACH_REVERSE_SAFE
118*c9e3be9fSDamien Miller #undef TAILQ_FOREACH_SAFE
119*c9e3be9fSDamien Miller #undef TAILQ_HEAD
120*c9e3be9fSDamien Miller #undef TAILQ_HEAD_INITIALIZER
121*c9e3be9fSDamien Miller #undef TAILQ_INIT
122*c9e3be9fSDamien Miller #undef TAILQ_INSERT_AFTER
123*c9e3be9fSDamien Miller #undef TAILQ_INSERT_BEFORE
124*c9e3be9fSDamien Miller #undef TAILQ_INSERT_HEAD
125*c9e3be9fSDamien Miller #undef TAILQ_INSERT_TAIL
126*c9e3be9fSDamien Miller #undef TAILQ_LAST
127*c9e3be9fSDamien Miller #undef TAILQ_NEXT
128*c9e3be9fSDamien Miller #undef TAILQ_PREV
129*c9e3be9fSDamien Miller #undef TAILQ_REMOVE
130*c9e3be9fSDamien Miller #undef TAILQ_REPLACE
1319b481510SDamien Miller 
1329b481510SDamien Miller /*
1339b481510SDamien Miller  * This file defines five types of data structures: singly-linked lists,
134adfdbf12SDamien Miller  * lists, simple queues, tail queues and XOR simple queues.
1359b481510SDamien Miller  *
1369b481510SDamien Miller  *
1379b481510SDamien Miller  * A singly-linked list is headed by a single forward pointer. The elements
1389b481510SDamien Miller  * are singly linked for minimum space and pointer manipulation overhead at
1399b481510SDamien Miller  * the expense of O(n) removal for arbitrary elements. New elements can be
1409b481510SDamien Miller  * added to the list after an existing element or at the head of the list.
1419b481510SDamien Miller  * Elements being removed from the head of the list should use the explicit
1429b481510SDamien Miller  * macro for this purpose for optimum efficiency. A singly-linked list may
1439b481510SDamien Miller  * only be traversed in the forward direction.  Singly-linked lists are ideal
1449b481510SDamien Miller  * for applications with large datasets and few or no removals or for
1459b481510SDamien Miller  * implementing a LIFO queue.
1469b481510SDamien Miller  *
1479b481510SDamien Miller  * A list is headed by a single forward pointer (or an array of forward
1489b481510SDamien Miller  * pointers for a hash table header). The elements are doubly linked
1499b481510SDamien Miller  * so that an arbitrary element can be removed without a need to
1509b481510SDamien Miller  * traverse the list. New elements can be added to the list before
1519b481510SDamien Miller  * or after an existing element or at the head of the list. A list
1529b481510SDamien Miller  * may only be traversed in the forward direction.
1539b481510SDamien Miller  *
154adfdbf12SDamien Miller  * A simple queue is headed by a pair of pointers, one to the head of the
1559b481510SDamien Miller  * list and the other to the tail of the list. The elements are singly
1569b481510SDamien Miller  * linked to save space, so elements can only be removed from the
1579b481510SDamien Miller  * head of the list. New elements can be added to the list before or after
1589b481510SDamien Miller  * an existing element, at the head of the list, or at the end of the
1599b481510SDamien Miller  * list. A simple queue may only be traversed in the forward direction.
1609b481510SDamien Miller  *
1619b481510SDamien Miller  * A tail queue is headed by a pair of pointers, one to the head of the
1629b481510SDamien Miller  * list and the other to the tail of the list. The elements are doubly
1639b481510SDamien Miller  * linked so that an arbitrary element can be removed without a need to
1649b481510SDamien Miller  * traverse the list. New elements can be added to the list before or
1659b481510SDamien Miller  * after an existing element, at the head of the list, or at the end of
1669b481510SDamien Miller  * the list. A tail queue may be traversed in either direction.
1679b481510SDamien Miller  *
168adfdbf12SDamien Miller  * An XOR simple queue is used in the same way as a regular simple queue.
169adfdbf12SDamien Miller  * The difference is that the head structure also includes a "cookie" that
170adfdbf12SDamien Miller  * is XOR'd with the queue pointer (first, last or next) to generate the
171adfdbf12SDamien Miller  * real pointer value.
1729b481510SDamien Miller  *
1739b481510SDamien Miller  * For details on the use of these macros, see the queue(3) manual page.
1749b481510SDamien Miller  */
1759b481510SDamien Miller 
176a95c0c22SDamien Miller #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
177adfdbf12SDamien Miller #define _Q_INVALID ((void *)-1)
178adfdbf12SDamien Miller #define _Q_INVALIDATE(a) (a) = _Q_INVALID
17903c618afSDamien Miller #else
18003c618afSDamien Miller #define _Q_INVALIDATE(a)
18103c618afSDamien Miller #endif
18203c618afSDamien Miller 
1839b481510SDamien Miller /*
1849b481510SDamien Miller  * Singly-linked List definitions.
1859b481510SDamien Miller  */
1869b481510SDamien Miller #define SLIST_HEAD(name, type)						\
1879b481510SDamien Miller struct name {								\
1889b481510SDamien Miller 	struct type *slh_first;	/* first element */			\
1899b481510SDamien Miller }
1909b481510SDamien Miller 
1919b481510SDamien Miller #define	SLIST_HEAD_INITIALIZER(head)					\
1929b481510SDamien Miller 	{ NULL }
1939b481510SDamien Miller 
1949b481510SDamien Miller #define SLIST_ENTRY(type)						\
1959b481510SDamien Miller struct {								\
1969b481510SDamien Miller 	struct type *sle_next;	/* next element */			\
1979b481510SDamien Miller }
1989b481510SDamien Miller 
1999b481510SDamien Miller /*
2009b481510SDamien Miller  * Singly-linked List access methods.
2019b481510SDamien Miller  */
2029b481510SDamien Miller #define	SLIST_FIRST(head)	((head)->slh_first)
2039b481510SDamien Miller #define	SLIST_END(head)		NULL
2049b481510SDamien Miller #define	SLIST_EMPTY(head)	(SLIST_FIRST(head) == SLIST_END(head))
2059b481510SDamien Miller #define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
2069b481510SDamien Miller 
2079b481510SDamien Miller #define	SLIST_FOREACH(var, head, field)					\
2089b481510SDamien Miller 	for((var) = SLIST_FIRST(head);					\
2099b481510SDamien Miller 	    (var) != SLIST_END(head);					\
2109b481510SDamien Miller 	    (var) = SLIST_NEXT(var, field))
2119b481510SDamien Miller 
212cf6ef137SDamien Miller #define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
213cf6ef137SDamien Miller 	for ((var) = SLIST_FIRST(head);				\
214cf6ef137SDamien Miller 	    (var) && ((tvar) = SLIST_NEXT(var, field), 1);		\
215cf6ef137SDamien Miller 	    (var) = (tvar))
2161824c071SDamien Miller 
2179b481510SDamien Miller /*
2189b481510SDamien Miller  * Singly-linked List functions.
2199b481510SDamien Miller  */
2209b481510SDamien Miller #define	SLIST_INIT(head) {						\
2219b481510SDamien Miller 	SLIST_FIRST(head) = SLIST_END(head);				\
2229b481510SDamien Miller }
2239b481510SDamien Miller 
2249b481510SDamien Miller #define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
2259b481510SDamien Miller 	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
2269b481510SDamien Miller 	(slistelm)->field.sle_next = (elm);				\
2279b481510SDamien Miller } while (0)
2289b481510SDamien Miller 
2299b481510SDamien Miller #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
2309b481510SDamien Miller 	(elm)->field.sle_next = (head)->slh_first;			\
2319b481510SDamien Miller 	(head)->slh_first = (elm);					\
2329b481510SDamien Miller } while (0)
2339b481510SDamien Miller 
234cf6ef137SDamien Miller #define	SLIST_REMOVE_AFTER(elm, field) do {				\
2351824c071SDamien Miller 	(elm)->field.sle_next = (elm)->field.sle_next->field.sle_next;	\
2361824c071SDamien Miller } while (0)
2371824c071SDamien Miller 
2389b481510SDamien Miller #define	SLIST_REMOVE_HEAD(head, field) do {				\
2399b481510SDamien Miller 	(head)->slh_first = (head)->slh_first->field.sle_next;		\
2409b481510SDamien Miller } while (0)
2419b481510SDamien Miller 
2429b481510SDamien Miller #define SLIST_REMOVE(head, elm, type, field) do {			\
2439b481510SDamien Miller 	if ((head)->slh_first == (elm)) {				\
2449b481510SDamien Miller 		SLIST_REMOVE_HEAD((head), field);			\
245d129ecb0SDamien Miller 	} else {							\
2469b481510SDamien Miller 		struct type *curelm = (head)->slh_first;		\
247d129ecb0SDamien Miller 									\
2489b481510SDamien Miller 		while (curelm->field.sle_next != (elm))			\
2499b481510SDamien Miller 			curelm = curelm->field.sle_next;		\
2509b481510SDamien Miller 		curelm->field.sle_next =				\
2519b481510SDamien Miller 		    curelm->field.sle_next->field.sle_next;		\
2529b481510SDamien Miller 	}								\
253adfdbf12SDamien Miller 	_Q_INVALIDATE((elm)->field.sle_next);				\
2549b481510SDamien Miller } while (0)
2559b481510SDamien Miller 
2569b481510SDamien Miller /*
2579b481510SDamien Miller  * List definitions.
2589b481510SDamien Miller  */
2599b481510SDamien Miller #define LIST_HEAD(name, type)						\
2609b481510SDamien Miller struct name {								\
2619b481510SDamien Miller 	struct type *lh_first;	/* first element */			\
2629b481510SDamien Miller }
2639b481510SDamien Miller 
2649b481510SDamien Miller #define LIST_HEAD_INITIALIZER(head)					\
2659b481510SDamien Miller 	{ NULL }
2669b481510SDamien Miller 
2679b481510SDamien Miller #define LIST_ENTRY(type)						\
2689b481510SDamien Miller struct {								\
2699b481510SDamien Miller 	struct type *le_next;	/* next element */			\
2709b481510SDamien Miller 	struct type **le_prev;	/* address of previous next element */	\
2719b481510SDamien Miller }
2729b481510SDamien Miller 
2739b481510SDamien Miller /*
274adfdbf12SDamien Miller  * List access methods.
2759b481510SDamien Miller  */
2769b481510SDamien Miller #define	LIST_FIRST(head)		((head)->lh_first)
2779b481510SDamien Miller #define	LIST_END(head)			NULL
2789b481510SDamien Miller #define	LIST_EMPTY(head)		(LIST_FIRST(head) == LIST_END(head))
2799b481510SDamien Miller #define	LIST_NEXT(elm, field)		((elm)->field.le_next)
2809b481510SDamien Miller 
2819b481510SDamien Miller #define LIST_FOREACH(var, head, field)					\
2829b481510SDamien Miller 	for((var) = LIST_FIRST(head);					\
2839b481510SDamien Miller 	    (var)!= LIST_END(head);					\
2849b481510SDamien Miller 	    (var) = LIST_NEXT(var, field))
2859b481510SDamien Miller 
286cf6ef137SDamien Miller #define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
287cf6ef137SDamien Miller 	for ((var) = LIST_FIRST(head);				\
288cf6ef137SDamien Miller 	    (var) && ((tvar) = LIST_NEXT(var, field), 1);		\
289cf6ef137SDamien Miller 	    (var) = (tvar))
290cf6ef137SDamien Miller 
2919b481510SDamien Miller /*
2929b481510SDamien Miller  * List functions.
2939b481510SDamien Miller  */
2949b481510SDamien Miller #define	LIST_INIT(head) do {						\
2959b481510SDamien Miller 	LIST_FIRST(head) = LIST_END(head);				\
2969b481510SDamien Miller } while (0)
2979b481510SDamien Miller 
2989b481510SDamien Miller #define LIST_INSERT_AFTER(listelm, elm, field) do {			\
2999b481510SDamien Miller 	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
3009b481510SDamien Miller 		(listelm)->field.le_next->field.le_prev =		\
3019b481510SDamien Miller 		    &(elm)->field.le_next;				\
3029b481510SDamien Miller 	(listelm)->field.le_next = (elm);				\
3039b481510SDamien Miller 	(elm)->field.le_prev = &(listelm)->field.le_next;		\
3049b481510SDamien Miller } while (0)
3059b481510SDamien Miller 
3069b481510SDamien Miller #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
3079b481510SDamien Miller 	(elm)->field.le_prev = (listelm)->field.le_prev;		\
3089b481510SDamien Miller 	(elm)->field.le_next = (listelm);				\
3099b481510SDamien Miller 	*(listelm)->field.le_prev = (elm);				\
3109b481510SDamien Miller 	(listelm)->field.le_prev = &(elm)->field.le_next;		\
3119b481510SDamien Miller } while (0)
3129b481510SDamien Miller 
3139b481510SDamien Miller #define LIST_INSERT_HEAD(head, elm, field) do {				\
3149b481510SDamien Miller 	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
3159b481510SDamien Miller 		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
3169b481510SDamien Miller 	(head)->lh_first = (elm);					\
3179b481510SDamien Miller 	(elm)->field.le_prev = &(head)->lh_first;			\
3189b481510SDamien Miller } while (0)
3199b481510SDamien Miller 
3209b481510SDamien Miller #define LIST_REMOVE(elm, field) do {					\
3219b481510SDamien Miller 	if ((elm)->field.le_next != NULL)				\
3229b481510SDamien Miller 		(elm)->field.le_next->field.le_prev =			\
3239b481510SDamien Miller 		    (elm)->field.le_prev;				\
3249b481510SDamien Miller 	*(elm)->field.le_prev = (elm)->field.le_next;			\
32503c618afSDamien Miller 	_Q_INVALIDATE((elm)->field.le_prev);				\
32603c618afSDamien Miller 	_Q_INVALIDATE((elm)->field.le_next);				\
3279b481510SDamien Miller } while (0)
3289b481510SDamien Miller 
3299b481510SDamien Miller #define LIST_REPLACE(elm, elm2, field) do {				\
3309b481510SDamien Miller 	if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)	\
3319b481510SDamien Miller 		(elm2)->field.le_next->field.le_prev =			\
3329b481510SDamien Miller 		    &(elm2)->field.le_next;				\
3339b481510SDamien Miller 	(elm2)->field.le_prev = (elm)->field.le_prev;			\
3349b481510SDamien Miller 	*(elm2)->field.le_prev = (elm2);				\
33503c618afSDamien Miller 	_Q_INVALIDATE((elm)->field.le_prev);				\
33603c618afSDamien Miller 	_Q_INVALIDATE((elm)->field.le_next);				\
3379b481510SDamien Miller } while (0)
3389b481510SDamien Miller 
3399b481510SDamien Miller /*
3409b481510SDamien Miller  * Simple queue definitions.
3419b481510SDamien Miller  */
3429b481510SDamien Miller #define SIMPLEQ_HEAD(name, type)					\
3439b481510SDamien Miller struct name {								\
3449b481510SDamien Miller 	struct type *sqh_first;	/* first element */			\
3459b481510SDamien Miller 	struct type **sqh_last;	/* addr of last next element */		\
3469b481510SDamien Miller }
3479b481510SDamien Miller 
3489b481510SDamien Miller #define SIMPLEQ_HEAD_INITIALIZER(head)					\
3499b481510SDamien Miller 	{ NULL, &(head).sqh_first }
3509b481510SDamien Miller 
3519b481510SDamien Miller #define SIMPLEQ_ENTRY(type)						\
3529b481510SDamien Miller struct {								\
3539b481510SDamien Miller 	struct type *sqe_next;	/* next element */			\
3549b481510SDamien Miller }
3559b481510SDamien Miller 
3569b481510SDamien Miller /*
3579b481510SDamien Miller  * Simple queue access methods.
3589b481510SDamien Miller  */
3599b481510SDamien Miller #define	SIMPLEQ_FIRST(head)	    ((head)->sqh_first)
3609b481510SDamien Miller #define	SIMPLEQ_END(head)	    NULL
3619b481510SDamien Miller #define	SIMPLEQ_EMPTY(head)	    (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
3629b481510SDamien Miller #define	SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)
3639b481510SDamien Miller 
3649b481510SDamien Miller #define SIMPLEQ_FOREACH(var, head, field)				\
3659b481510SDamien Miller 	for((var) = SIMPLEQ_FIRST(head);				\
3669b481510SDamien Miller 	    (var) != SIMPLEQ_END(head);					\
3679b481510SDamien Miller 	    (var) = SIMPLEQ_NEXT(var, field))
3689b481510SDamien Miller 
369cf6ef137SDamien Miller #define	SIMPLEQ_FOREACH_SAFE(var, head, field, tvar)			\
370cf6ef137SDamien Miller 	for ((var) = SIMPLEQ_FIRST(head);				\
371cf6ef137SDamien Miller 	    (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1);		\
372cf6ef137SDamien Miller 	    (var) = (tvar))
373cf6ef137SDamien Miller 
3749b481510SDamien Miller /*
3759b481510SDamien Miller  * Simple queue functions.
3769b481510SDamien Miller  */
3779b481510SDamien Miller #define	SIMPLEQ_INIT(head) do {						\
3789b481510SDamien Miller 	(head)->sqh_first = NULL;					\
3799b481510SDamien Miller 	(head)->sqh_last = &(head)->sqh_first;				\
3809b481510SDamien Miller } while (0)
3819b481510SDamien Miller 
3829b481510SDamien Miller #define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
3839b481510SDamien Miller 	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
3849b481510SDamien Miller 		(head)->sqh_last = &(elm)->field.sqe_next;		\
3859b481510SDamien Miller 	(head)->sqh_first = (elm);					\
3869b481510SDamien Miller } while (0)
3879b481510SDamien Miller 
3889b481510SDamien Miller #define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
3899b481510SDamien Miller 	(elm)->field.sqe_next = NULL;					\
3909b481510SDamien Miller 	*(head)->sqh_last = (elm);					\
3919b481510SDamien Miller 	(head)->sqh_last = &(elm)->field.sqe_next;			\
3929b481510SDamien Miller } while (0)
3939b481510SDamien Miller 
3949b481510SDamien Miller #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
3959b481510SDamien Miller 	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
3969b481510SDamien Miller 		(head)->sqh_last = &(elm)->field.sqe_next;		\
3979b481510SDamien Miller 	(listelm)->field.sqe_next = (elm);				\
3989b481510SDamien Miller } while (0)
3999b481510SDamien Miller 
400b99f5f71SDamien Miller #define SIMPLEQ_REMOVE_HEAD(head, field) do {			\
401b99f5f71SDamien Miller 	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
4029b481510SDamien Miller 		(head)->sqh_last = &(head)->sqh_first;			\
4039b481510SDamien Miller } while (0)
4049b481510SDamien Miller 
405cf6ef137SDamien Miller #define SIMPLEQ_REMOVE_AFTER(head, elm, field) do {			\
406cf6ef137SDamien Miller 	if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
407cf6ef137SDamien Miller 	    == NULL)							\
408cf6ef137SDamien Miller 		(head)->sqh_last = &(elm)->field.sqe_next;		\
409cf6ef137SDamien Miller } while (0)
410cf6ef137SDamien Miller 
411adfdbf12SDamien Miller #define SIMPLEQ_CONCAT(head1, head2) do {				\
412adfdbf12SDamien Miller 	if (!SIMPLEQ_EMPTY((head2))) {					\
413adfdbf12SDamien Miller 		*(head1)->sqh_last = (head2)->sqh_first;		\
414adfdbf12SDamien Miller 		(head1)->sqh_last = (head2)->sqh_last;			\
415adfdbf12SDamien Miller 		SIMPLEQ_INIT((head2));					\
416adfdbf12SDamien Miller 	}								\
417adfdbf12SDamien Miller } while (0)
418adfdbf12SDamien Miller 
419adfdbf12SDamien Miller /*
420adfdbf12SDamien Miller  * XOR Simple queue definitions.
421adfdbf12SDamien Miller  */
422adfdbf12SDamien Miller #define XSIMPLEQ_HEAD(name, type)					\
423adfdbf12SDamien Miller struct name {								\
424adfdbf12SDamien Miller 	struct type *sqx_first;	/* first element */			\
425adfdbf12SDamien Miller 	struct type **sqx_last;	/* addr of last next element */		\
426adfdbf12SDamien Miller 	unsigned long sqx_cookie;					\
427adfdbf12SDamien Miller }
428adfdbf12SDamien Miller 
429adfdbf12SDamien Miller #define XSIMPLEQ_ENTRY(type)						\
430adfdbf12SDamien Miller struct {								\
431adfdbf12SDamien Miller 	struct type *sqx_next;	/* next element */			\
432adfdbf12SDamien Miller }
433adfdbf12SDamien Miller 
434adfdbf12SDamien Miller /*
435adfdbf12SDamien Miller  * XOR Simple queue access methods.
436adfdbf12SDamien Miller  */
437adfdbf12SDamien Miller #define XSIMPLEQ_XOR(head, ptr)	    ((__typeof(ptr))((head)->sqx_cookie ^ \
438adfdbf12SDamien Miller 					(unsigned long)(ptr)))
439adfdbf12SDamien Miller #define	XSIMPLEQ_FIRST(head)	    XSIMPLEQ_XOR(head, ((head)->sqx_first))
440adfdbf12SDamien Miller #define	XSIMPLEQ_END(head)	    NULL
441adfdbf12SDamien Miller #define	XSIMPLEQ_EMPTY(head)	    (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
442adfdbf12SDamien Miller #define	XSIMPLEQ_NEXT(head, elm, field)    XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
443adfdbf12SDamien Miller 
444adfdbf12SDamien Miller 
445adfdbf12SDamien Miller #define XSIMPLEQ_FOREACH(var, head, field)				\
446adfdbf12SDamien Miller 	for ((var) = XSIMPLEQ_FIRST(head);				\
447adfdbf12SDamien Miller 	    (var) != XSIMPLEQ_END(head);				\
448adfdbf12SDamien Miller 	    (var) = XSIMPLEQ_NEXT(head, var, field))
449adfdbf12SDamien Miller 
450adfdbf12SDamien Miller #define	XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar)			\
451adfdbf12SDamien Miller 	for ((var) = XSIMPLEQ_FIRST(head);				\
452adfdbf12SDamien Miller 	    (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1);	\
453adfdbf12SDamien Miller 	    (var) = (tvar))
454adfdbf12SDamien Miller 
455adfdbf12SDamien Miller /*
456adfdbf12SDamien Miller  * XOR Simple queue functions.
457adfdbf12SDamien Miller  */
458adfdbf12SDamien Miller #define	XSIMPLEQ_INIT(head) do {					\
459adfdbf12SDamien Miller 	arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \
460adfdbf12SDamien Miller 	(head)->sqx_first = XSIMPLEQ_XOR(head, NULL);			\
461adfdbf12SDamien Miller 	(head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first);	\
462adfdbf12SDamien Miller } while (0)
463adfdbf12SDamien Miller 
464adfdbf12SDamien Miller #define XSIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
465adfdbf12SDamien Miller 	if (((elm)->field.sqx_next = (head)->sqx_first) ==		\
466adfdbf12SDamien Miller 	    XSIMPLEQ_XOR(head, NULL))					\
467adfdbf12SDamien Miller 		(head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
468adfdbf12SDamien Miller 	(head)->sqx_first = XSIMPLEQ_XOR(head, (elm));			\
469adfdbf12SDamien Miller } while (0)
470adfdbf12SDamien Miller 
471adfdbf12SDamien Miller #define XSIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
472adfdbf12SDamien Miller 	(elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL);		\
473adfdbf12SDamien Miller 	*(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \
474adfdbf12SDamien Miller 	(head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);	\
475adfdbf12SDamien Miller } while (0)
476adfdbf12SDamien Miller 
477adfdbf12SDamien Miller #define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
478adfdbf12SDamien Miller 	if (((elm)->field.sqx_next = (listelm)->field.sqx_next) ==	\
479adfdbf12SDamien Miller 	    XSIMPLEQ_XOR(head, NULL))					\
480adfdbf12SDamien Miller 		(head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
481adfdbf12SDamien Miller 	(listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm));		\
482adfdbf12SDamien Miller } while (0)
483adfdbf12SDamien Miller 
484adfdbf12SDamien Miller #define XSIMPLEQ_REMOVE_HEAD(head, field) do {				\
485adfdbf12SDamien Miller 	if (((head)->sqx_first = XSIMPLEQ_XOR(head,			\
486adfdbf12SDamien Miller 	    (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
487adfdbf12SDamien Miller 		(head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
488adfdbf12SDamien Miller } while (0)
489adfdbf12SDamien Miller 
490adfdbf12SDamien Miller #define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do {			\
491adfdbf12SDamien Miller 	if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head,			\
492adfdbf12SDamien Miller 	    (elm)->field.sqx_next)->field.sqx_next)			\
493adfdbf12SDamien Miller 	    == XSIMPLEQ_XOR(head, NULL))				\
494adfdbf12SDamien Miller 		(head)->sqx_last = 					\
495adfdbf12SDamien Miller 		    XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);		\
496adfdbf12SDamien Miller } while (0)
497adfdbf12SDamien Miller 
498adfdbf12SDamien Miller 
4999b481510SDamien Miller /*
5009b481510SDamien Miller  * Tail queue definitions.
5019b481510SDamien Miller  */
5029b481510SDamien Miller #define TAILQ_HEAD(name, type)						\
5039b481510SDamien Miller struct name {								\
5049b481510SDamien Miller 	struct type *tqh_first;	/* first element */			\
5059b481510SDamien Miller 	struct type **tqh_last;	/* addr of last next element */		\
5069b481510SDamien Miller }
5079b481510SDamien Miller 
5089b481510SDamien Miller #define TAILQ_HEAD_INITIALIZER(head)					\
5099b481510SDamien Miller 	{ NULL, &(head).tqh_first }
5109b481510SDamien Miller 
5119b481510SDamien Miller #define TAILQ_ENTRY(type)						\
5129b481510SDamien Miller struct {								\
5139b481510SDamien Miller 	struct type *tqe_next;	/* next element */			\
5149b481510SDamien Miller 	struct type **tqe_prev;	/* address of previous next element */	\
5159b481510SDamien Miller }
5169b481510SDamien Miller 
5179b481510SDamien Miller /*
518adfdbf12SDamien Miller  * Tail queue access methods.
5199b481510SDamien Miller  */
5209b481510SDamien Miller #define	TAILQ_FIRST(head)		((head)->tqh_first)
5219b481510SDamien Miller #define	TAILQ_END(head)			NULL
5229b481510SDamien Miller #define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
5239b481510SDamien Miller #define TAILQ_LAST(head, headname)					\
5249b481510SDamien Miller 	(*(((struct headname *)((head)->tqh_last))->tqh_last))
5259b481510SDamien Miller /* XXX */
5269b481510SDamien Miller #define TAILQ_PREV(elm, headname, field)				\
5279b481510SDamien Miller 	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
5289b481510SDamien Miller #define	TAILQ_EMPTY(head)						\
5299b481510SDamien Miller 	(TAILQ_FIRST(head) == TAILQ_END(head))
5309b481510SDamien Miller 
5319b481510SDamien Miller #define TAILQ_FOREACH(var, head, field)					\
5329b481510SDamien Miller 	for((var) = TAILQ_FIRST(head);					\
5339b481510SDamien Miller 	    (var) != TAILQ_END(head);					\
5349b481510SDamien Miller 	    (var) = TAILQ_NEXT(var, field))
5359b481510SDamien Miller 
536cf6ef137SDamien Miller #define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
537cf6ef137SDamien Miller 	for ((var) = TAILQ_FIRST(head);					\
538cf6ef137SDamien Miller 	    (var) != TAILQ_END(head) &&					\
539cf6ef137SDamien Miller 	    ((tvar) = TAILQ_NEXT(var, field), 1);			\
540cf6ef137SDamien Miller 	    (var) = (tvar))
541cf6ef137SDamien Miller 
542cf6ef137SDamien Miller 
5431824c071SDamien Miller #define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
5449b481510SDamien Miller 	for((var) = TAILQ_LAST(head, headname);				\
5459b481510SDamien Miller 	    (var) != TAILQ_END(head);					\
5469b481510SDamien Miller 	    (var) = TAILQ_PREV(var, headname, field))
5479b481510SDamien Miller 
548cf6ef137SDamien Miller #define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
549cf6ef137SDamien Miller 	for ((var) = TAILQ_LAST(head, headname);			\
550cf6ef137SDamien Miller 	    (var) != TAILQ_END(head) &&					\
551cf6ef137SDamien Miller 	    ((tvar) = TAILQ_PREV(var, headname, field), 1);		\
552cf6ef137SDamien Miller 	    (var) = (tvar))
553cf6ef137SDamien Miller 
5549b481510SDamien Miller /*
5559b481510SDamien Miller  * Tail queue functions.
5569b481510SDamien Miller  */
5579b481510SDamien Miller #define	TAILQ_INIT(head) do {						\
5589b481510SDamien Miller 	(head)->tqh_first = NULL;					\
5599b481510SDamien Miller 	(head)->tqh_last = &(head)->tqh_first;				\
5609b481510SDamien Miller } while (0)
5619b481510SDamien Miller 
5629b481510SDamien Miller #define TAILQ_INSERT_HEAD(head, elm, field) do {			\
5639b481510SDamien Miller 	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
5649b481510SDamien Miller 		(head)->tqh_first->field.tqe_prev =			\
5659b481510SDamien Miller 		    &(elm)->field.tqe_next;				\
5669b481510SDamien Miller 	else								\
5679b481510SDamien Miller 		(head)->tqh_last = &(elm)->field.tqe_next;		\
5689b481510SDamien Miller 	(head)->tqh_first = (elm);					\
5699b481510SDamien Miller 	(elm)->field.tqe_prev = &(head)->tqh_first;			\
5709b481510SDamien Miller } while (0)
5719b481510SDamien Miller 
5729b481510SDamien Miller #define TAILQ_INSERT_TAIL(head, elm, field) do {			\
5739b481510SDamien Miller 	(elm)->field.tqe_next = NULL;					\
5749b481510SDamien Miller 	(elm)->field.tqe_prev = (head)->tqh_last;			\
5759b481510SDamien Miller 	*(head)->tqh_last = (elm);					\
5769b481510SDamien Miller 	(head)->tqh_last = &(elm)->field.tqe_next;			\
5779b481510SDamien Miller } while (0)
5789b481510SDamien Miller 
5799b481510SDamien Miller #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
5809b481510SDamien Miller 	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
5819b481510SDamien Miller 		(elm)->field.tqe_next->field.tqe_prev =			\
5829b481510SDamien Miller 		    &(elm)->field.tqe_next;				\
5839b481510SDamien Miller 	else								\
5849b481510SDamien Miller 		(head)->tqh_last = &(elm)->field.tqe_next;		\
5859b481510SDamien Miller 	(listelm)->field.tqe_next = (elm);				\
5869b481510SDamien Miller 	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
5879b481510SDamien Miller } while (0)
5889b481510SDamien Miller 
5899b481510SDamien Miller #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
5909b481510SDamien Miller 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
5919b481510SDamien Miller 	(elm)->field.tqe_next = (listelm);				\
5929b481510SDamien Miller 	*(listelm)->field.tqe_prev = (elm);				\
5939b481510SDamien Miller 	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
5949b481510SDamien Miller } while (0)
5959b481510SDamien Miller 
5969b481510SDamien Miller #define TAILQ_REMOVE(head, elm, field) do {				\
5979b481510SDamien Miller 	if (((elm)->field.tqe_next) != NULL)				\
5989b481510SDamien Miller 		(elm)->field.tqe_next->field.tqe_prev =			\
5999b481510SDamien Miller 		    (elm)->field.tqe_prev;				\
6009b481510SDamien Miller 	else								\
6019b481510SDamien Miller 		(head)->tqh_last = (elm)->field.tqe_prev;		\
6029b481510SDamien Miller 	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
60303c618afSDamien Miller 	_Q_INVALIDATE((elm)->field.tqe_prev);				\
60403c618afSDamien Miller 	_Q_INVALIDATE((elm)->field.tqe_next);				\
6059b481510SDamien Miller } while (0)
6069b481510SDamien Miller 
6079b481510SDamien Miller #define TAILQ_REPLACE(head, elm, elm2, field) do {			\
6089b481510SDamien Miller 	if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)	\
6099b481510SDamien Miller 		(elm2)->field.tqe_next->field.tqe_prev =		\
6109b481510SDamien Miller 		    &(elm2)->field.tqe_next;				\
6119b481510SDamien Miller 	else								\
6129b481510SDamien Miller 		(head)->tqh_last = &(elm2)->field.tqe_next;		\
6139b481510SDamien Miller 	(elm2)->field.tqe_prev = (elm)->field.tqe_prev;			\
6149b481510SDamien Miller 	*(elm2)->field.tqe_prev = (elm2);				\
61503c618afSDamien Miller 	_Q_INVALIDATE((elm)->field.tqe_prev);				\
61603c618afSDamien Miller 	_Q_INVALIDATE((elm)->field.tqe_next);				\
6179b481510SDamien Miller } while (0)
6189b481510SDamien Miller 
619adfdbf12SDamien Miller #define TAILQ_CONCAT(head1, head2, field) do {				\
620adfdbf12SDamien Miller 	if (!TAILQ_EMPTY(head2)) {					\
621adfdbf12SDamien Miller 		*(head1)->tqh_last = (head2)->tqh_first;		\
622adfdbf12SDamien Miller 		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
623adfdbf12SDamien Miller 		(head1)->tqh_last = (head2)->tqh_last;			\
624adfdbf12SDamien Miller 		TAILQ_INIT((head2));					\
625adfdbf12SDamien Miller 	}								\
6269b481510SDamien Miller } while (0)
6279b481510SDamien Miller 
628adfdbf12SDamien Miller #endif	/* !_SYS_QUEUE_H_ */
629