xref: /freebsd/contrib/openbsm/compat/queue.h (revision 348238dbd42306d9fb5d89ab393b840572cfeb0f)
13b97a967SRobert Watson /*-
23b97a967SRobert Watson  * Copyright (c) 1991, 1993
33b97a967SRobert Watson  *	The Regents of the University of California.  All rights reserved.
43b97a967SRobert Watson  *
53b97a967SRobert Watson  * Redistribution and use in source and binary forms, with or without
63b97a967SRobert Watson  * modification, are permitted provided that the following conditions
73b97a967SRobert Watson  * are met:
83b97a967SRobert Watson  * 1. Redistributions of source code must retain the above copyright
93b97a967SRobert Watson  *    notice, this list of conditions and the following disclaimer.
103b97a967SRobert Watson  * 2. Redistributions in binary form must reproduce the above copyright
113b97a967SRobert Watson  *    notice, this list of conditions and the following disclaimer in the
123b97a967SRobert Watson  *    documentation and/or other materials provided with the distribution.
13*fbbd9655SWarner Losh  * 3. Neither the name of the University nor the names of its contributors
143b97a967SRobert Watson  *    may be used to endorse or promote products derived from this software
153b97a967SRobert Watson  *    without specific prior written permission.
163b97a967SRobert Watson  *
173b97a967SRobert Watson  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
183b97a967SRobert Watson  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
193b97a967SRobert Watson  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
203b97a967SRobert Watson  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
213b97a967SRobert Watson  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
223b97a967SRobert Watson  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
233b97a967SRobert Watson  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
243b97a967SRobert Watson  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
253b97a967SRobert Watson  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
263b97a967SRobert Watson  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
273b97a967SRobert Watson  * SUCH DAMAGE.
283b97a967SRobert Watson  *
293b97a967SRobert Watson  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
303b97a967SRobert Watson  *
313b97a967SRobert Watson  * Derived from FreeBSD src/sys/sys/queue.h:1.63.
323b97a967SRobert Watson  */
333b97a967SRobert Watson 
343b97a967SRobert Watson #ifndef _COMPAT_QUEUE_H_
353b97a967SRobert Watson #define	_COMPAT_QUEUE_H_
363b97a967SRobert Watson 
373b97a967SRobert Watson #include <sys/cdefs.h>
383b97a967SRobert Watson 
393b97a967SRobert Watson /*
403b97a967SRobert Watson  * This file defines four types of data structures: singly-linked lists,
413b97a967SRobert Watson  * singly-linked tail queues, lists and tail queues.
423b97a967SRobert Watson  *
433b97a967SRobert Watson  * A singly-linked list is headed by a single forward pointer. The elements
443b97a967SRobert Watson  * are singly linked for minimum space and pointer manipulation overhead at
453b97a967SRobert Watson  * the expense of O(n) removal for arbitrary elements. New elements can be
463b97a967SRobert Watson  * added to the list after an existing element or at the head of the list.
473b97a967SRobert Watson  * Elements being removed from the head of the list should use the explicit
483b97a967SRobert Watson  * macro for this purpose for optimum efficiency. A singly-linked list may
493b97a967SRobert Watson  * only be traversed in the forward direction.  Singly-linked lists are ideal
503b97a967SRobert Watson  * for applications with large datasets and few or no removals or for
513b97a967SRobert Watson  * implementing a LIFO queue.
523b97a967SRobert Watson  *
533b97a967SRobert Watson  * A singly-linked tail queue is headed by a pair of pointers, one to the
543b97a967SRobert Watson  * head of the list and the other to the tail of the list. The elements are
553b97a967SRobert Watson  * singly linked for minimum space and pointer manipulation overhead at the
563b97a967SRobert Watson  * expense of O(n) removal for arbitrary elements. New elements can be added
573b97a967SRobert Watson  * to the list after an existing element, at the head of the list, or at the
583b97a967SRobert Watson  * end of the list. Elements being removed from the head of the tail queue
593b97a967SRobert Watson  * should use the explicit macro for this purpose for optimum efficiency.
603b97a967SRobert Watson  * A singly-linked tail queue may only be traversed in the forward direction.
613b97a967SRobert Watson  * Singly-linked tail queues are ideal for applications with large datasets
623b97a967SRobert Watson  * and few or no removals or for implementing a FIFO queue.
633b97a967SRobert Watson  *
643b97a967SRobert Watson  * A list is headed by a single forward pointer (or an array of forward
653b97a967SRobert Watson  * pointers for a hash table header). The elements are doubly linked
663b97a967SRobert Watson  * so that an arbitrary element can be removed without a need to
673b97a967SRobert Watson  * traverse the list. New elements can be added to the list before
683b97a967SRobert Watson  * or after an existing element or at the head of the list. A list
693b97a967SRobert Watson  * may only be traversed in the forward direction.
703b97a967SRobert Watson  *
713b97a967SRobert Watson  * A tail queue is headed by a pair of pointers, one to the head of the
723b97a967SRobert Watson  * list and the other to the tail of the list. The elements are doubly
733b97a967SRobert Watson  * linked so that an arbitrary element can be removed without a need to
743b97a967SRobert Watson  * traverse the list. New elements can be added to the list before or
753b97a967SRobert Watson  * after an existing element, at the head of the list, or at the end of
763b97a967SRobert Watson  * the list. A tail queue may be traversed in either direction.
773b97a967SRobert Watson  *
783b97a967SRobert Watson  * For details on the use of these macros, see the queue(3) manual page.
793b97a967SRobert Watson  *
803b97a967SRobert Watson  *
813b97a967SRobert Watson  *				SLIST	LIST	STAILQ	TAILQ
823b97a967SRobert Watson  * _HEAD			+	+	+	+
833b97a967SRobert Watson  * _HEAD_INITIALIZER		+	+	+	+
843b97a967SRobert Watson  * _ENTRY			+	+	+	+
853b97a967SRobert Watson  * _INIT			+	+	+	+
863b97a967SRobert Watson  * _EMPTY			+	+	+	+
873b97a967SRobert Watson  * _FIRST			+	+	+	+
883b97a967SRobert Watson  * _NEXT			+	+	+	+
893b97a967SRobert Watson  * _PREV			-	-	-	+
903b97a967SRobert Watson  * _LAST			-	-	+	+
913b97a967SRobert Watson  * _FOREACH			+	+	+	+
923b97a967SRobert Watson  * _FOREACH_SAFE		+	+	+	+
933b97a967SRobert Watson  * _FOREACH_REVERSE		-	-	-	+
943b97a967SRobert Watson  * _FOREACH_REVERSE_SAFE	-	-	-	+
953b97a967SRobert Watson  * _INSERT_HEAD			+	+	+	+
963b97a967SRobert Watson  * _INSERT_BEFORE		-	+	-	+
973b97a967SRobert Watson  * _INSERT_AFTER		+	+	+	+
983b97a967SRobert Watson  * _INSERT_TAIL			-	-	+	+
993b97a967SRobert Watson  * _CONCAT			-	-	+	+
1003b97a967SRobert Watson  * _REMOVE_HEAD			+	-	+	-
1013b97a967SRobert Watson  * _REMOVE			+	+	+	+
1023b97a967SRobert Watson  *
1033b97a967SRobert Watson  */
1043b97a967SRobert Watson #ifdef QUEUE_MACRO_DEBUG
1053b97a967SRobert Watson /* Store the last 2 places the queue element or head was altered */
1063b97a967SRobert Watson struct qm_trace {
1073b97a967SRobert Watson 	char * lastfile;
1083b97a967SRobert Watson 	int lastline;
1093b97a967SRobert Watson 	char * prevfile;
1103b97a967SRobert Watson 	int prevline;
1113b97a967SRobert Watson };
1123b97a967SRobert Watson 
1133b97a967SRobert Watson #define	TRACEBUF	struct qm_trace trace;
1143b97a967SRobert Watson #define	TRASHIT(x)	do {(x) = (void *)-1;} while (0)
1153b97a967SRobert Watson 
1163b97a967SRobert Watson #define	QMD_TRACE_HEAD(head) do {					\
1173b97a967SRobert Watson 	(head)->trace.prevline = (head)->trace.lastline;		\
1183b97a967SRobert Watson 	(head)->trace.prevfile = (head)->trace.lastfile;		\
1193b97a967SRobert Watson 	(head)->trace.lastline = __LINE__;				\
1203b97a967SRobert Watson 	(head)->trace.lastfile = __FILE__;				\
1213b97a967SRobert Watson } while (0)
1223b97a967SRobert Watson 
1233b97a967SRobert Watson #define	QMD_TRACE_ELEM(elem) do {					\
1243b97a967SRobert Watson 	(elem)->trace.prevline = (elem)->trace.lastline;		\
1253b97a967SRobert Watson 	(elem)->trace.prevfile = (elem)->trace.lastfile;		\
1263b97a967SRobert Watson 	(elem)->trace.lastline = __LINE__;				\
1273b97a967SRobert Watson 	(elem)->trace.lastfile = __FILE__;				\
1283b97a967SRobert Watson } while (0)
1293b97a967SRobert Watson 
1303b97a967SRobert Watson #else
1313b97a967SRobert Watson #define	QMD_TRACE_ELEM(elem)
1323b97a967SRobert Watson #define	QMD_TRACE_HEAD(head)
1333b97a967SRobert Watson #define	TRACEBUF
1343b97a967SRobert Watson #define	TRASHIT(x)
1353b97a967SRobert Watson #endif	/* QUEUE_MACRO_DEBUG */
1363b97a967SRobert Watson 
1373b97a967SRobert Watson /*
1383b97a967SRobert Watson  * Singly-linked List declarations.
1393b97a967SRobert Watson  */
1403b97a967SRobert Watson #define	SLIST_HEAD(name, type)						\
1413b97a967SRobert Watson struct name {								\
1423b97a967SRobert Watson 	struct type *slh_first;	/* first element */			\
1433b97a967SRobert Watson }
1443b97a967SRobert Watson 
1453b97a967SRobert Watson #define	SLIST_HEAD_INITIALIZER(head)					\
1463b97a967SRobert Watson 	{ NULL }
1473b97a967SRobert Watson 
1483b97a967SRobert Watson #define	SLIST_ENTRY(type)						\
1493b97a967SRobert Watson struct {								\
1503b97a967SRobert Watson 	struct type *sle_next;	/* next element */			\
1513b97a967SRobert Watson }
1523b97a967SRobert Watson 
1533b97a967SRobert Watson /*
1543b97a967SRobert Watson  * Singly-linked List functions.
1553b97a967SRobert Watson  */
1563b97a967SRobert Watson #define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
1573b97a967SRobert Watson 
1583b97a967SRobert Watson #define	SLIST_FIRST(head)	((head)->slh_first)
1593b97a967SRobert Watson 
1603b97a967SRobert Watson #define	SLIST_FOREACH(var, head, field)					\
1613b97a967SRobert Watson 	for ((var) = SLIST_FIRST((head));				\
1623b97a967SRobert Watson 	    (var);							\
1633b97a967SRobert Watson 	    (var) = SLIST_NEXT((var), field))
1643b97a967SRobert Watson 
1653b97a967SRobert Watson #define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
1663b97a967SRobert Watson 	for ((var) = SLIST_FIRST((head));				\
1673b97a967SRobert Watson 	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);		\
1683b97a967SRobert Watson 	    (var) = (tvar))
1693b97a967SRobert Watson 
1703b97a967SRobert Watson #define	SLIST_FOREACH_PREVPTR(var, varp, head, field)			\
1713b97a967SRobert Watson 	for ((varp) = &SLIST_FIRST((head));				\
1723b97a967SRobert Watson 	    ((var) = *(varp)) != NULL;					\
1733b97a967SRobert Watson 	    (varp) = &SLIST_NEXT((var), field))
1743b97a967SRobert Watson 
1753b97a967SRobert Watson #define	SLIST_INIT(head) do {						\
1763b97a967SRobert Watson 	SLIST_FIRST((head)) = NULL;					\
1773b97a967SRobert Watson } while (0)
1783b97a967SRobert Watson 
1793b97a967SRobert Watson #define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
1803b97a967SRobert Watson 	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);	\
1813b97a967SRobert Watson 	SLIST_NEXT((slistelm), field) = (elm);				\
1823b97a967SRobert Watson } while (0)
1833b97a967SRobert Watson 
1843b97a967SRobert Watson #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
1853b97a967SRobert Watson 	SLIST_NEXT((elm), field) = SLIST_FIRST((head));			\
1863b97a967SRobert Watson 	SLIST_FIRST((head)) = (elm);					\
1873b97a967SRobert Watson } while (0)
1883b97a967SRobert Watson 
1893b97a967SRobert Watson #define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
1903b97a967SRobert Watson 
1913b97a967SRobert Watson #define	SLIST_REMOVE(head, elm, type, field) do {			\
1923b97a967SRobert Watson 	if (SLIST_FIRST((head)) == (elm)) {				\
1933b97a967SRobert Watson 		SLIST_REMOVE_HEAD((head), field);			\
1943b97a967SRobert Watson 	}								\
1953b97a967SRobert Watson 	else {								\
1963b97a967SRobert Watson 		struct type *curelm = SLIST_FIRST((head));		\
1973b97a967SRobert Watson 		while (SLIST_NEXT(curelm, field) != (elm))		\
1983b97a967SRobert Watson 			curelm = SLIST_NEXT(curelm, field);		\
1993b97a967SRobert Watson 		SLIST_NEXT(curelm, field) =				\
2003b97a967SRobert Watson 		    SLIST_NEXT(SLIST_NEXT(curelm, field), field);	\
2013b97a967SRobert Watson 	}								\
2023b97a967SRobert Watson 	TRASHIT((elm)->field.sle_next);					\
2033b97a967SRobert Watson } while (0)
2043b97a967SRobert Watson 
2053b97a967SRobert Watson #define	SLIST_REMOVE_HEAD(head, field) do {				\
2063b97a967SRobert Watson 	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
2073b97a967SRobert Watson } while (0)
2083b97a967SRobert Watson 
2093b97a967SRobert Watson /*
2103b97a967SRobert Watson  * Singly-linked Tail queue declarations.
2113b97a967SRobert Watson  */
2123b97a967SRobert Watson #define	STAILQ_HEAD(name, type)						\
2133b97a967SRobert Watson struct name {								\
2143b97a967SRobert Watson 	struct type *stqh_first;/* first element */			\
2153b97a967SRobert Watson 	struct type **stqh_last;/* addr of last next element */		\
2163b97a967SRobert Watson }
2173b97a967SRobert Watson 
2183b97a967SRobert Watson #define	STAILQ_HEAD_INITIALIZER(head)					\
2193b97a967SRobert Watson 	{ NULL, &(head).stqh_first }
2203b97a967SRobert Watson 
2213b97a967SRobert Watson #define	STAILQ_ENTRY(type)						\
2223b97a967SRobert Watson struct {								\
2233b97a967SRobert Watson 	struct type *stqe_next;	/* next element */			\
2243b97a967SRobert Watson }
2253b97a967SRobert Watson 
2263b97a967SRobert Watson /*
2273b97a967SRobert Watson  * Singly-linked Tail queue functions.
2283b97a967SRobert Watson  */
2293b97a967SRobert Watson #define	STAILQ_CONCAT(head1, head2) do {				\
2303b97a967SRobert Watson 	if (!STAILQ_EMPTY((head2))) {					\
2313b97a967SRobert Watson 		*(head1)->stqh_last = (head2)->stqh_first;		\
2323b97a967SRobert Watson 		(head1)->stqh_last = (head2)->stqh_last;		\
2333b97a967SRobert Watson 		STAILQ_INIT((head2));					\
2343b97a967SRobert Watson 	}								\
2353b97a967SRobert Watson } while (0)
2363b97a967SRobert Watson 
2373b97a967SRobert Watson #define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)
2383b97a967SRobert Watson 
2393b97a967SRobert Watson #define	STAILQ_FIRST(head)	((head)->stqh_first)
2403b97a967SRobert Watson 
2413b97a967SRobert Watson #define	STAILQ_FOREACH(var, head, field)				\
2423b97a967SRobert Watson 	for((var) = STAILQ_FIRST((head));				\
2433b97a967SRobert Watson 	   (var);							\
2443b97a967SRobert Watson 	   (var) = STAILQ_NEXT((var), field))
2453b97a967SRobert Watson 
2463b97a967SRobert Watson 
2473b97a967SRobert Watson #define	STAILQ_FOREACH_SAFE(var, head, field, tvar)			\
2483b97a967SRobert Watson 	for ((var) = STAILQ_FIRST((head));				\
2493b97a967SRobert Watson 	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\
2503b97a967SRobert Watson 	    (var) = (tvar))
2513b97a967SRobert Watson 
2523b97a967SRobert Watson #define	STAILQ_INIT(head) do {						\
2533b97a967SRobert Watson 	STAILQ_FIRST((head)) = NULL;					\
2543b97a967SRobert Watson 	(head)->stqh_last = &STAILQ_FIRST((head));			\
2553b97a967SRobert Watson } while (0)
2563b97a967SRobert Watson 
2573b97a967SRobert Watson #define	STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\
2583b97a967SRobert Watson 	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
2593b97a967SRobert Watson 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
2603b97a967SRobert Watson 	STAILQ_NEXT((tqelm), field) = (elm);				\
2613b97a967SRobert Watson } while (0)
2623b97a967SRobert Watson 
2633b97a967SRobert Watson #define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
2643b97a967SRobert Watson 	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)	\
2653b97a967SRobert Watson 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
2663b97a967SRobert Watson 	STAILQ_FIRST((head)) = (elm);					\
2673b97a967SRobert Watson } while (0)
2683b97a967SRobert Watson 
2693b97a967SRobert Watson #define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
2703b97a967SRobert Watson 	STAILQ_NEXT((elm), field) = NULL;				\
2713b97a967SRobert Watson 	*(head)->stqh_last = (elm);					\
2723b97a967SRobert Watson 	(head)->stqh_last = &STAILQ_NEXT((elm), field);			\
2733b97a967SRobert Watson } while (0)
2743b97a967SRobert Watson 
2753b97a967SRobert Watson #define	STAILQ_LAST(head, type, field)					\
2763b97a967SRobert Watson 	(STAILQ_EMPTY((head)) ?						\
2773b97a967SRobert Watson 		NULL :							\
2783b97a967SRobert Watson 	        ((struct type *)					\
2793b97a967SRobert Watson 		((char *)((head)->stqh_last) - __offsetof(struct type, field))))
2803b97a967SRobert Watson 
2813b97a967SRobert Watson #define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
2823b97a967SRobert Watson 
2833b97a967SRobert Watson #define	STAILQ_REMOVE(head, elm, type, field) do {			\
2843b97a967SRobert Watson 	if (STAILQ_FIRST((head)) == (elm)) {				\
2853b97a967SRobert Watson 		STAILQ_REMOVE_HEAD((head), field);			\
2863b97a967SRobert Watson 	}								\
2873b97a967SRobert Watson 	else {								\
2883b97a967SRobert Watson 		struct type *curelm = STAILQ_FIRST((head));		\
2893b97a967SRobert Watson 		while (STAILQ_NEXT(curelm, field) != (elm))		\
2903b97a967SRobert Watson 			curelm = STAILQ_NEXT(curelm, field);		\
2913b97a967SRobert Watson 		if ((STAILQ_NEXT(curelm, field) =			\
2923b97a967SRobert Watson 		     STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
2933b97a967SRobert Watson 			(head)->stqh_last = &STAILQ_NEXT((curelm), field);\
2943b97a967SRobert Watson 	}								\
2953b97a967SRobert Watson 	TRASHIT((elm)->field.stqe_next);				\
2963b97a967SRobert Watson } while (0)
2973b97a967SRobert Watson 
2983b97a967SRobert Watson #define	STAILQ_REMOVE_HEAD(head, field) do {				\
2993b97a967SRobert Watson 	if ((STAILQ_FIRST((head)) =					\
3003b97a967SRobert Watson 	     STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)		\
3013b97a967SRobert Watson 		(head)->stqh_last = &STAILQ_FIRST((head));		\
3023b97a967SRobert Watson } while (0)
3033b97a967SRobert Watson 
3043b97a967SRobert Watson #define	STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {			\
3053b97a967SRobert Watson 	if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL)	\
3063b97a967SRobert Watson 		(head)->stqh_last = &STAILQ_FIRST((head));		\
3073b97a967SRobert Watson } while (0)
3083b97a967SRobert Watson 
3093b97a967SRobert Watson /*
3103b97a967SRobert Watson  * List declarations.
3113b97a967SRobert Watson  */
3123b97a967SRobert Watson #define	LIST_HEAD(name, type)						\
3133b97a967SRobert Watson struct name {								\
3143b97a967SRobert Watson 	struct type *lh_first;	/* first element */			\
3153b97a967SRobert Watson }
3163b97a967SRobert Watson 
3173b97a967SRobert Watson #define	LIST_HEAD_INITIALIZER(head)					\
3183b97a967SRobert Watson 	{ NULL }
3193b97a967SRobert Watson 
3203b97a967SRobert Watson #define	LIST_ENTRY(type)						\
3213b97a967SRobert Watson struct {								\
3223b97a967SRobert Watson 	struct type *le_next;	/* next element */			\
3233b97a967SRobert Watson 	struct type **le_prev;	/* address of previous next element */	\
3243b97a967SRobert Watson }
3253b97a967SRobert Watson 
3263b97a967SRobert Watson /*
3273b97a967SRobert Watson  * List functions.
3283b97a967SRobert Watson  */
3293b97a967SRobert Watson 
3303b97a967SRobert Watson #if (defined(_KERNEL) && defined(INVARIANTS)) || defined(QUEUE_MACRO_DEBUG)
3313b97a967SRobert Watson #define	QMD_LIST_CHECK_HEAD(head, field) do {				\
3323b97a967SRobert Watson 	if (LIST_FIRST((head)) != NULL &&				\
3333b97a967SRobert Watson 	    LIST_FIRST((head))->field.le_prev !=			\
3343b97a967SRobert Watson 	     &LIST_FIRST((head)))					\
3353b97a967SRobert Watson 		panic("Bad list head %p first->prev != head", (head));	\
3363b97a967SRobert Watson } while (0)
3373b97a967SRobert Watson 
3383b97a967SRobert Watson #define	QMD_LIST_CHECK_NEXT(elm, field) do {				\
3393b97a967SRobert Watson 	if (LIST_NEXT((elm), field) != NULL &&				\
3403b97a967SRobert Watson 	    LIST_NEXT((elm), field)->field.le_prev !=			\
3413b97a967SRobert Watson 	     &((elm)->field.le_next))					\
3423b97a967SRobert Watson 	     	panic("Bad link elm %p next->prev != elm", (elm));	\
3433b97a967SRobert Watson } while (0)
3443b97a967SRobert Watson 
3453b97a967SRobert Watson #define	QMD_LIST_CHECK_PREV(elm, field) do {				\
3463b97a967SRobert Watson 	if (*(elm)->field.le_prev != (elm))				\
3473b97a967SRobert Watson 		panic("Bad link elm %p prev->next != elm", (elm));	\
3483b97a967SRobert Watson } while (0)
3493b97a967SRobert Watson #else
3503b97a967SRobert Watson #define	QMD_LIST_CHECK_HEAD(head, field)
3513b97a967SRobert Watson #define	QMD_LIST_CHECK_NEXT(elm, field)
3523b97a967SRobert Watson #define	QMD_LIST_CHECK_PREV(elm, field)
3533b97a967SRobert Watson #endif /* (_KERNEL && INVARIANTS) || QUEUE_MACRO_DEBUG */
3543b97a967SRobert Watson 
3553b97a967SRobert Watson #define	LIST_EMPTY(head)	((head)->lh_first == NULL)
3563b97a967SRobert Watson 
3573b97a967SRobert Watson #define	LIST_FIRST(head)	((head)->lh_first)
3583b97a967SRobert Watson 
3593b97a967SRobert Watson #define	LIST_FOREACH(var, head, field)					\
3603b97a967SRobert Watson 	for ((var) = LIST_FIRST((head));				\
3613b97a967SRobert Watson 	    (var);							\
3623b97a967SRobert Watson 	    (var) = LIST_NEXT((var), field))
3633b97a967SRobert Watson 
3643b97a967SRobert Watson #define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
3653b97a967SRobert Watson 	for ((var) = LIST_FIRST((head));				\
3663b97a967SRobert Watson 	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\
3673b97a967SRobert Watson 	    (var) = (tvar))
3683b97a967SRobert Watson 
3693b97a967SRobert Watson #define	LIST_INIT(head) do {						\
3703b97a967SRobert Watson 	LIST_FIRST((head)) = NULL;					\
3713b97a967SRobert Watson } while (0)
3723b97a967SRobert Watson 
3733b97a967SRobert Watson #define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
3743b97a967SRobert Watson 	QMD_LIST_CHECK_NEXT(listelm, field);				\
3753b97a967SRobert Watson 	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
3763b97a967SRobert Watson 		LIST_NEXT((listelm), field)->field.le_prev =		\
3773b97a967SRobert Watson 		    &LIST_NEXT((elm), field);				\
3783b97a967SRobert Watson 	LIST_NEXT((listelm), field) = (elm);				\
3793b97a967SRobert Watson 	(elm)->field.le_prev = &LIST_NEXT((listelm), field);		\
3803b97a967SRobert Watson } while (0)
3813b97a967SRobert Watson 
3823b97a967SRobert Watson #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
3833b97a967SRobert Watson 	QMD_LIST_CHECK_PREV(listelm, field);				\
3843b97a967SRobert Watson 	(elm)->field.le_prev = (listelm)->field.le_prev;		\
3853b97a967SRobert Watson 	LIST_NEXT((elm), field) = (listelm);				\
3863b97a967SRobert Watson 	*(listelm)->field.le_prev = (elm);				\
3873b97a967SRobert Watson 	(listelm)->field.le_prev = &LIST_NEXT((elm), field);		\
3883b97a967SRobert Watson } while (0)
3893b97a967SRobert Watson 
3903b97a967SRobert Watson #define	LIST_INSERT_HEAD(head, elm, field) do {				\
3913b97a967SRobert Watson 	QMD_LIST_CHECK_HEAD((head), field);				\
3923b97a967SRobert Watson 	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\
3933b97a967SRobert Watson 		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
3943b97a967SRobert Watson 	LIST_FIRST((head)) = (elm);					\
3953b97a967SRobert Watson 	(elm)->field.le_prev = &LIST_FIRST((head));			\
3963b97a967SRobert Watson } while (0)
3973b97a967SRobert Watson 
3983b97a967SRobert Watson #define	LIST_NEXT(elm, field)	((elm)->field.le_next)
3993b97a967SRobert Watson 
4003b97a967SRobert Watson #define	LIST_REMOVE(elm, field) do {					\
4013b97a967SRobert Watson 	QMD_LIST_CHECK_NEXT(elm, field);				\
4023b97a967SRobert Watson 	QMD_LIST_CHECK_PREV(elm, field);				\
4033b97a967SRobert Watson 	if (LIST_NEXT((elm), field) != NULL)				\
4043b97a967SRobert Watson 		LIST_NEXT((elm), field)->field.le_prev = 		\
4053b97a967SRobert Watson 		    (elm)->field.le_prev;				\
4063b97a967SRobert Watson 	*(elm)->field.le_prev = LIST_NEXT((elm), field);		\
4073b97a967SRobert Watson 	TRASHIT((elm)->field.le_next);					\
4083b97a967SRobert Watson 	TRASHIT((elm)->field.le_prev);					\
4093b97a967SRobert Watson } while (0)
4103b97a967SRobert Watson 
4113b97a967SRobert Watson /*
4123b97a967SRobert Watson  * Tail queue declarations.
4133b97a967SRobert Watson  */
4143b97a967SRobert Watson #define	TAILQ_HEAD(name, type)						\
4153b97a967SRobert Watson struct name {								\
4163b97a967SRobert Watson 	struct type *tqh_first;	/* first element */			\
4173b97a967SRobert Watson 	struct type **tqh_last;	/* addr of last next element */		\
4183b97a967SRobert Watson 	TRACEBUF							\
4193b97a967SRobert Watson }
4203b97a967SRobert Watson 
4213b97a967SRobert Watson #define	TAILQ_HEAD_INITIALIZER(head)					\
4223b97a967SRobert Watson 	{ NULL, &(head).tqh_first }
4233b97a967SRobert Watson 
4243b97a967SRobert Watson #define	TAILQ_ENTRY(type)						\
4253b97a967SRobert Watson struct {								\
4263b97a967SRobert Watson 	struct type *tqe_next;	/* next element */			\
4273b97a967SRobert Watson 	struct type **tqe_prev;	/* address of previous next element */	\
4283b97a967SRobert Watson 	TRACEBUF							\
4293b97a967SRobert Watson }
4303b97a967SRobert Watson 
4313b97a967SRobert Watson /*
4323b97a967SRobert Watson  * Tail queue functions.
4333b97a967SRobert Watson  */
4343b97a967SRobert Watson #define	TAILQ_CONCAT(head1, head2, field) do {				\
4353b97a967SRobert Watson 	if (!TAILQ_EMPTY(head2)) {					\
4363b97a967SRobert Watson 		*(head1)->tqh_last = (head2)->tqh_first;		\
4373b97a967SRobert Watson 		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
4383b97a967SRobert Watson 		(head1)->tqh_last = (head2)->tqh_last;			\
4393b97a967SRobert Watson 		TAILQ_INIT((head2));					\
4403b97a967SRobert Watson 		QMD_TRACE_HEAD(head1);					\
4413b97a967SRobert Watson 		QMD_TRACE_HEAD(head2);					\
4423b97a967SRobert Watson 	}								\
4433b97a967SRobert Watson } while (0)
4443b97a967SRobert Watson 
4453b97a967SRobert Watson #define	TAILQ_EMPTY(head)	((head)->tqh_first == NULL)
4463b97a967SRobert Watson 
4473b97a967SRobert Watson #define	TAILQ_FIRST(head)	((head)->tqh_first)
4483b97a967SRobert Watson 
4493b97a967SRobert Watson #define	TAILQ_FOREACH(var, head, field)					\
4503b97a967SRobert Watson 	for ((var) = TAILQ_FIRST((head));				\
4513b97a967SRobert Watson 	    (var);							\
4523b97a967SRobert Watson 	    (var) = TAILQ_NEXT((var), field))
4533b97a967SRobert Watson 
4543b97a967SRobert Watson #define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
4553b97a967SRobert Watson 	for ((var) = TAILQ_FIRST((head));				\
4563b97a967SRobert Watson 	    (var) && ((tvar) = TAILQ_NEXT((var), field), 1);		\
4573b97a967SRobert Watson 	    (var) = (tvar))
4583b97a967SRobert Watson 
4593b97a967SRobert Watson #define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
4603b97a967SRobert Watson 	for ((var) = TAILQ_LAST((head), headname);			\
4613b97a967SRobert Watson 	    (var);							\
4623b97a967SRobert Watson 	    (var) = TAILQ_PREV((var), headname, field))
4633b97a967SRobert Watson 
4643b97a967SRobert Watson #define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
4653b97a967SRobert Watson 	for ((var) = TAILQ_LAST((head), headname);			\
4663b97a967SRobert Watson 	    (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);	\
4673b97a967SRobert Watson 	    (var) = (tvar))
4683b97a967SRobert Watson 
4693b97a967SRobert Watson #define	TAILQ_INIT(head) do {						\
4703b97a967SRobert Watson 	TAILQ_FIRST((head)) = NULL;					\
4713b97a967SRobert Watson 	(head)->tqh_last = &TAILQ_FIRST((head));			\
4723b97a967SRobert Watson 	QMD_TRACE_HEAD(head);						\
4733b97a967SRobert Watson } while (0)
4743b97a967SRobert Watson 
4753b97a967SRobert Watson #define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
4763b97a967SRobert Watson 	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
4773b97a967SRobert Watson 		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\
4783b97a967SRobert Watson 		    &TAILQ_NEXT((elm), field);				\
4793b97a967SRobert Watson 	else {								\
4803b97a967SRobert Watson 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
4813b97a967SRobert Watson 		QMD_TRACE_HEAD(head);					\
4823b97a967SRobert Watson 	}								\
4833b97a967SRobert Watson 	TAILQ_NEXT((listelm), field) = (elm);				\
4843b97a967SRobert Watson 	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);		\
4853b97a967SRobert Watson 	QMD_TRACE_ELEM(&(elm)->field);					\
4863b97a967SRobert Watson 	QMD_TRACE_ELEM(&listelm->field);				\
4873b97a967SRobert Watson } while (0)
4883b97a967SRobert Watson 
4893b97a967SRobert Watson #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
4903b97a967SRobert Watson 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
4913b97a967SRobert Watson 	TAILQ_NEXT((elm), field) = (listelm);				\
4923b97a967SRobert Watson 	*(listelm)->field.tqe_prev = (elm);				\
4933b97a967SRobert Watson 	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);		\
4943b97a967SRobert Watson 	QMD_TRACE_ELEM(&(elm)->field);					\
4953b97a967SRobert Watson 	QMD_TRACE_ELEM(&listelm->field);				\
4963b97a967SRobert Watson } while (0)
4973b97a967SRobert Watson 
4983b97a967SRobert Watson #define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
4993b97a967SRobert Watson 	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)	\
5003b97a967SRobert Watson 		TAILQ_FIRST((head))->field.tqe_prev =			\
5013b97a967SRobert Watson 		    &TAILQ_NEXT((elm), field);				\
5023b97a967SRobert Watson 	else								\
5033b97a967SRobert Watson 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
5043b97a967SRobert Watson 	TAILQ_FIRST((head)) = (elm);					\
5053b97a967SRobert Watson 	(elm)->field.tqe_prev = &TAILQ_FIRST((head));			\
5063b97a967SRobert Watson 	QMD_TRACE_HEAD(head);						\
5073b97a967SRobert Watson 	QMD_TRACE_ELEM(&(elm)->field);					\
5083b97a967SRobert Watson } while (0)
5093b97a967SRobert Watson 
5103b97a967SRobert Watson #define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
5113b97a967SRobert Watson 	TAILQ_NEXT((elm), field) = NULL;				\
5123b97a967SRobert Watson 	(elm)->field.tqe_prev = (head)->tqh_last;			\
5133b97a967SRobert Watson 	*(head)->tqh_last = (elm);					\
5143b97a967SRobert Watson 	(head)->tqh_last = &TAILQ_NEXT((elm), field);			\
5153b97a967SRobert Watson 	QMD_TRACE_HEAD(head);						\
5163b97a967SRobert Watson 	QMD_TRACE_ELEM(&(elm)->field);					\
5173b97a967SRobert Watson } while (0)
5183b97a967SRobert Watson 
5193b97a967SRobert Watson #define	TAILQ_LAST(head, headname)					\
5203b97a967SRobert Watson 	(*(((struct headname *)((head)->tqh_last))->tqh_last))
5213b97a967SRobert Watson 
5223b97a967SRobert Watson #define	TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
5233b97a967SRobert Watson 
5243b97a967SRobert Watson #define	TAILQ_PREV(elm, headname, field)				\
5253b97a967SRobert Watson 	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
5263b97a967SRobert Watson 
5273b97a967SRobert Watson #define	TAILQ_REMOVE(head, elm, field) do {				\
5283b97a967SRobert Watson 	if ((TAILQ_NEXT((elm), field)) != NULL)				\
5293b97a967SRobert Watson 		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\
5303b97a967SRobert Watson 		    (elm)->field.tqe_prev;				\
5313b97a967SRobert Watson 	else {								\
5323b97a967SRobert Watson 		(head)->tqh_last = (elm)->field.tqe_prev;		\
5333b97a967SRobert Watson 		QMD_TRACE_HEAD(head);					\
5343b97a967SRobert Watson 	}								\
5353b97a967SRobert Watson 	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);		\
5363b97a967SRobert Watson 	TRASHIT((elm)->field.tqe_next);					\
5373b97a967SRobert Watson 	TRASHIT((elm)->field.tqe_prev);					\
5383b97a967SRobert Watson 	QMD_TRACE_ELEM(&(elm)->field);					\
5393b97a967SRobert Watson } while (0)
5403b97a967SRobert Watson 
5413b97a967SRobert Watson #endif /* !_COMPAT_QUEUE_H_ */
542