1f0bf889imp/*-
24736ccfpfg * SPDX-License-Identifier: BSD-3-Clause
34736ccfpfg *
48fb65cergrimes * Copyright (c) 1991, 1993
58fb65cergrimes *	The Regents of the University of California.  All rights reserved.
68fb65cergrimes *
78fb65cergrimes * Redistribution and use in source and binary forms, with or without
88fb65cergrimes * modification, are permitted provided that the following conditions
98fb65cergrimes * are met:
108fb65cergrimes * 1. Redistributions of source code must retain the above copyright
118fb65cergrimes *    notice, this list of conditions and the following disclaimer.
128fb65cergrimes * 2. Redistributions in binary form must reproduce the above copyright
138fb65cergrimes *    notice, this list of conditions and the following disclaimer in the
148fb65cergrimes *    documentation and/or other materials provided with the distribution.
157e6cabdimp * 3. Neither the name of the University nor the names of its contributors
168fb65cergrimes *    may be used to endorse or promote products derived from this software
178fb65cergrimes *    without specific prior written permission.
188fb65cergrimes *
198fb65cergrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
208fb65cergrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
218fb65cergrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
228fb65cergrimes * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
238fb65cergrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
248fb65cergrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
258fb65cergrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
268fb65cergrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
278fb65cergrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
288fb65cergrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
298fb65cergrimes * SUCH DAMAGE.
308fb65cergrimes *
31c74a394hsu *	@(#)queue.h	8.5 (Berkeley) 8/20/94
323b842d3peter * $FreeBSD$
338fb65cergrimes */
348fb65cergrimes
3535ee958bde#ifndef _SYS_QUEUE_H_
368fb65cergrimes#define	_SYS_QUEUE_H_
378fb65cergrimes
38ebfda4cmike#include <sys/cdefs.h>
3954ca484phk
408fb65cergrimes/*
41b7ccf76sheldonh * This file defines four types of data structures: singly-linked lists,
42b7ccf76sheldonh * singly-linked tail queues, lists and tail queues.
431f23347gibbs *
441f23347gibbs * A singly-linked list is headed by a single forward pointer. The elements
451f23347gibbs * are singly linked for minimum space and pointer manipulation overhead at
461f23347gibbs * the expense of O(n) removal for arbitrary elements. New elements can be
471f23347gibbs * added to the list after an existing element or at the head of the list.
481f23347gibbs * Elements being removed from the head of the list should use the explicit
491f23347gibbs * macro for this purpose for optimum efficiency. A singly-linked list may
501f23347gibbs * only be traversed in the forward direction.  Singly-linked lists are ideal
511f23347gibbs * for applications with large datasets and few or no removals or for
521f23347gibbs * implementing a LIFO queue.
531f23347gibbs *
541f23347gibbs * A singly-linked tail queue is headed by a pair of pointers, one to the
551f23347gibbs * head of the list and the other to the tail of the list. The elements are
561f23347gibbs * singly linked for minimum space and pointer manipulation overhead at the
571f23347gibbs * expense of O(n) removal for arbitrary elements. New elements can be added
581f23347gibbs * to the list after an existing element, at the head of the list, or at the
591f23347gibbs * end of the list. Elements being removed from the head of the tail queue
601f23347gibbs * should use the explicit macro for this purpose for optimum efficiency.
611f23347gibbs * A singly-linked tail queue may only be traversed in the forward direction.
621f23347gibbs * Singly-linked tail queues are ideal for applications with large datasets
631f23347gibbs * and few or no removals or for implementing a FIFO queue.
648fb65cergrimes *
658fb65cergrimes * A list is headed by a single forward pointer (or an array of forward
668fb65cergrimes * pointers for a hash table header). The elements are doubly linked
678fb65cergrimes * so that an arbitrary element can be removed without a need to
68c74a394hsu * traverse the list. New elements can be added to the list before
69c74a394hsu * or after an existing element or at the head of the list. A list
700fa239bed * may be traversed in either direction.
718fb65cergrimes *
728fb65cergrimes * A tail queue is headed by a pair of pointers, one to the head of the
738fb65cergrimes * list and the other to the tail of the list. The elements are doubly
748fb65cergrimes * linked so that an arbitrary element can be removed without a need to
75c74a394hsu * traverse the list. New elements can be added to the list before or
76c74a394hsu * after an existing element, at the head of the list, or at the end of
770a725efarchie * the list. A tail queue may be traversed in either direction.
788fb65cergrimes *
798fb65cergrimes * For details on the use of these macros, see the queue(3) manual page.
804941314phk *
810aeae89mckusick * Below is a summary of implemented functions where:
820aeae89mckusick *  +  means the macro is available
830aeae89mckusick *  -  means the macro is not available
840aeae89mckusick *  s  means the macro is available but is slow (runs in O(n) time)
854941314phk *
86d822b4akan *				SLIST	LIST	STAILQ	TAILQ
87d822b4akan * _HEAD			+	+	+	+
880647fddhselasky * _CLASS_HEAD			+	+	+	+
89d822b4akan * _HEAD_INITIALIZER		+	+	+	+
90d822b4akan * _ENTRY			+	+	+	+
910647fddhselasky * _CLASS_ENTRY			+	+	+	+
92d822b4akan * _INIT			+	+	+	+
93d822b4akan * _EMPTY			+	+	+	+
94d822b4akan * _FIRST			+	+	+	+
95d822b4akan * _NEXT			+	+	+	+
960fa239bed * _PREV			-	+	-	+
97d822b4akan * _LAST			-	-	+	+
98e4ec942rrs * _LAST_FAST			-	-	-	+
99d822b4akan * _FOREACH			+	+	+	+
100aa062bflstewart * _FOREACH_FROM		+	+	+	+
101d822b4akan * _FOREACH_SAFE		+	+	+	+
102aa062bflstewart * _FOREACH_FROM_SAFE		+	+	+	+
103d822b4akan * _FOREACH_REVERSE		-	-	-	+
104aa062bflstewart * _FOREACH_REVERSE_FROM	-	-	-	+
105d822b4akan * _FOREACH_REVERSE_SAFE	-	-	-	+
106aa062bflstewart * _FOREACH_REVERSE_FROM_SAFE	-	-	-	+
107d822b4akan * _INSERT_HEAD			+	+	+	+
108d822b4akan * _INSERT_BEFORE		-	+	-	+
109d822b4akan * _INSERT_AFTER		+	+	+	+
110d822b4akan * _INSERT_TAIL			-	-	+	+
1110aeae89mckusick * _CONCAT			s	s	+	+
1123779b68ed * _REMOVE_AFTER		+	-	+	-
113d822b4akan * _REMOVE_HEAD			+	-	+	-
1140aeae89mckusick * _REMOVE			s	+	s	+
1155e42f0amdf * _SWAP			+	+	+	+
1164941314phk *
1178fb65cergrimes */
11850b1ba7emaste#ifdef QUEUE_MACRO_DEBUG
11926315f8cem#warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH
12026315f8cem#define	QUEUE_MACRO_DEBUG_TRACE
12126315f8cem#define	QUEUE_MACRO_DEBUG_TRASH
12226315f8cem#endif
12326315f8cem
12426315f8cem#ifdef QUEUE_MACRO_DEBUG_TRACE
1251cf028djulian/* Store the last 2 places the queue element or head was altered */
126aa2dc0ajulianstruct qm_trace {
12740a2400glebius	unsigned long	 lastline;
12840a2400glebius	unsigned long	 prevline;
12940a2400glebius	const char	*lastfile;
13040a2400glebius	const char	*prevfile;
131aa2dc0ajulian};
132aa2dc0ajulian
133d822b4akan#define	TRACEBUF	struct qm_trace trace;
1347903c02hselasky#define	TRACEBUF_INITIALIZER	{ __LINE__, 0, __FILE__, NULL } ,
135aa2dc0ajulian
136d822b4akan#define	QMD_TRACE_HEAD(head) do {					\
137aa2dc0ajulian	(head)->trace.prevline = (head)->trace.lastline;		\
138aa2dc0ajulian	(head)->trace.prevfile = (head)->trace.lastfile;		\
139aa2dc0ajulian	(head)->trace.lastline = __LINE__;				\
140aa2dc0ajulian	(head)->trace.lastfile = __FILE__;				\
141aa2dc0ajulian} while (0)
142aa2dc0ajulian
143d822b4akan#define	QMD_TRACE_ELEM(elem) do {					\
144aa2dc0ajulian	(elem)->trace.prevline = (elem)->trace.lastline;		\
145aa2dc0ajulian	(elem)->trace.prevfile = (elem)->trace.lastfile;		\
146aa2dc0ajulian	(elem)->trace.lastline = __LINE__;				\
147aa2dc0ajulian	(elem)->trace.lastfile = __FILE__;				\
148aa2dc0ajulian} while (0)
149aa2dc0ajulian
15026315f8cem#else	/* !QUEUE_MACRO_DEBUG_TRACE */
151d822b4akan#define	QMD_TRACE_ELEM(elem)
152d822b4akan#define	QMD_TRACE_HEAD(head)
153d822b4akan#define	TRACEBUF
15440a2400glebius#define	TRACEBUF_INITIALIZER
15526315f8cem#endif	/* QUEUE_MACRO_DEBUG_TRACE */
15626315f8cem
15726315f8cem#ifdef QUEUE_MACRO_DEBUG_TRASH
158fceb834glebius#define	QMD_SAVELINK(name, link)	void **name = (void *)&(link)
15926315f8cem#define	TRASHIT(x)		do {(x) = (void *)-1;} while (0)
16026315f8cem#define	QMD_IS_TRASHED(x)	((x) == (void *)(intptr_t)-1)
16126315f8cem#else	/* !QUEUE_MACRO_DEBUG_TRASH */
162fceb834glebius#define	QMD_SAVELINK(name, link)
163d822b4akan#define	TRASHIT(x)
16426315f8cem#define	QMD_IS_TRASHED(x)	0
16526315f8cem#endif	/* QUEUE_MACRO_DEBUG_TRASH */
16626315f8cem
1670647fddhselasky#ifdef __cplusplus
1680647fddhselasky/*
1690647fddhselasky * In C++ there can be structure lists and class lists:
1700647fddhselasky */
1710647fddhselasky#define	QUEUE_TYPEOF(type) type
1720647fddhselasky#else
1730647fddhselasky#define	QUEUE_TYPEOF(type) struct type
1740647fddhselasky#endif
1750647fddhselasky
1768fb65cergrimes/*
1778846e3bjake * Singly-linked List declarations.
1781f23347gibbs */
1798846e3bjake#define	SLIST_HEAD(name, type)						\
1801f23347gibbsstruct name {								\
181961b97djake	struct type *slh_first;	/* first element */			\
1821f23347gibbs}
183bb81fe9n_hibma
1840647fddhselasky#define	SLIST_CLASS_HEAD(name, type)					\
1850647fddhselaskystruct name {								\
1860647fddhselasky	class type *slh_first;	/* first element */			\
1870647fddhselasky}
1880647fddhselasky
1898846e3bjake#define	SLIST_HEAD_INITIALIZER(head)					\
190bb81fe9n_hibma	{ NULL }
191d822b4akan
1928846e3bjake#define	SLIST_ENTRY(type)						\
1931f23347gibbsstruct {								\
194961b97djake	struct type *sle_next;	/* next element */			\
1951f23347gibbs}
196d822b4akan
1970647fddhselasky#define	SLIST_CLASS_ENTRY(type)						\
1980647fddhselaskystruct {								\
1990647fddhselasky	class type *sle_next;		/* next element */		\
2000647fddhselasky}
2010647fddhselasky
2021f23347gibbs/*
2031f23347gibbs * Singly-linked List functions.
2041f23347gibbs */
20526315f8cem#if (defined(_KERNEL) && defined(INVARIANTS))
20626315f8cem#define	QMD_SLIST_CHECK_PREVPTR(prevp, elm) do {			\
20726315f8cem	if (*(prevp) != (elm))						\
20826315f8cem		panic("Bad prevptr *(%p) == %p != %p",			\
20926315f8cem		    (prevp), *(prevp), (elm));				\
21026315f8cem} while (0)
21126315f8cem#else
21226315f8cem#define	QMD_SLIST_CHECK_PREVPTR(prevp, elm)
21326315f8cem#endif
21426315f8cem
2150aeae89mckusick#define SLIST_CONCAT(head1, head2, type, field) do {			\
2160aeae89mckusick	QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1);		\
2170aeae89mckusick	if (curelm == NULL) {						\
2180aeae89mckusick		if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL)	\
2190aeae89mckusick			SLIST_INIT(head2);				\
2200aeae89mckusick	} else if (SLIST_FIRST(head2) != NULL) {			\
2210aeae89mckusick		while (SLIST_NEXT(curelm, field) != NULL)		\
2220aeae89mckusick			curelm = SLIST_NEXT(curelm, field);		\
2230aeae89mckusick		SLIST_NEXT(curelm, field) = SLIST_FIRST(head2);		\
2240aeae89mckusick		SLIST_INIT(head2);					\
2250aeae89mckusick	}								\
2260aeae89mckusick} while (0)
2270aeae89mckusick
228f1d17a4phk#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
229f1d17a4phk
230f1d17a4phk#define	SLIST_FIRST(head)	((head)->slh_first)
231f1d17a4phk
2328846e3bjake#define	SLIST_FOREACH(var, head, field)					\
2338846e3bjake	for ((var) = SLIST_FIRST((head));				\
2348846e3bjake	    (var);							\
2358846e3bjake	    (var) = SLIST_NEXT((var), field))
236bd600a2phk
237aa062bflstewart#define	SLIST_FOREACH_FROM(var, head, field)				\
238aa062bflstewart	for ((var) = ((var) ? (var) : SLIST_FIRST((head)));		\
239aa062bflstewart	    (var);							\
240aa062bflstewart	    (var) = SLIST_NEXT((var), field))
241aa062bflstewart
242d822b4akan#define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
243d822b4akan	for ((var) = SLIST_FIRST((head));				\
244d822b4akan	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);		\
245d822b4akan	    (var) = (tvar))
246d822b4akan
247aa062bflstewart#define	SLIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
248aa062bflstewart	for ((var) = ((var) ? (var) : SLIST_FIRST((head)));		\
249aa062bflstewart	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);		\
250aa062bflstewart	    (var) = (tvar))
251aa062bflstewart
252d822b4akan#define	SLIST_FOREACH_PREVPTR(var, varp, head, field)			\
253e7bcbc4alfred	for ((varp) = &SLIST_FIRST((head));				\
254e7bcbc4alfred	    ((var) = *(varp)) != NULL;					\
255e7bcbc4alfred	    (varp) = &SLIST_NEXT((var), field))
256e7bcbc4alfred
2578846e3bjake#define	SLIST_INIT(head) do {						\
2588846e3bjake	SLIST_FIRST((head)) = NULL;					\
2594f3c123julian} while (0)
2601f23347gibbs
2618846e3bjake#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
2628846e3bjake	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);	\
2638846e3bjake	SLIST_NEXT((slistelm), field) = (elm);				\
2644f3c123julian} while (0)
2651f23347gibbs
2668846e3bjake#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
2678846e3bjake	SLIST_NEXT((elm), field) = SLIST_FIRST((head));			\
2688846e3bjake	SLIST_FIRST((head)) = (elm);					\
2694f3c123julian} while (0)
2701f23347gibbs
2718846e3bjake#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
2728846e3bjake
2738846e3bjake#define	SLIST_REMOVE(head, elm, type, field) do {			\
2741739980emaste	QMD_SAVELINK(oldnext, (elm)->field.sle_next);			\
2758846e3bjake	if (SLIST_FIRST((head)) == (elm)) {				\
2761f23347gibbs		SLIST_REMOVE_HEAD((head), field);			\
2771f23347gibbs	}								\
2781f23347gibbs	else {								\
2790647fddhselasky		QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head);		\
2808846e3bjake		while (SLIST_NEXT(curelm, field) != (elm))		\
2818846e3bjake			curelm = SLIST_NEXT(curelm, field);		\
2823779b68ed		SLIST_REMOVE_AFTER(curelm, field);			\
2831f23347gibbs	}								\
2841739980emaste	TRASHIT(*oldnext);						\
2854f3c123julian} while (0)
2861f23347gibbs
2873779b68ed#define SLIST_REMOVE_AFTER(elm, field) do {				\
288d5f5839ed	SLIST_NEXT(elm, field) =					\
289d5f5839ed	    SLIST_NEXT(SLIST_NEXT(elm, field), field);			\
290d5f5839ed} while (0)
291d5f5839ed
2928846e3bjake#define	SLIST_REMOVE_HEAD(head, field) do {				\
2938846e3bjake	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
2948846e3bjake} while (0)
2958846e3bjake
29626315f8cem#define	SLIST_REMOVE_PREVPTR(prevp, elm, field) do {			\
29726315f8cem	QMD_SLIST_CHECK_PREVPTR(prevp, elm);				\
29826315f8cem	*(prevp) = SLIST_NEXT(elm, field);				\
29926315f8cem	TRASHIT((elm)->field.sle_next);					\
30026315f8cem} while (0)
30126315f8cem
302ff0f2f7kib#define SLIST_SWAP(head1, head2, type) do {				\
3030647fddhselasky	QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1);		\
304ff0f2f7kib	SLIST_FIRST(head1) = SLIST_FIRST(head2);			\
305ff0f2f7kib	SLIST_FIRST(head2) = swap_first;				\
306ff0f2f7kib} while (0)
307ff0f2f7kib
3081f23347gibbs/*
3098846e3bjake * Singly-linked Tail queue declarations.
3101f23347gibbs */
3118846e3bjake#define	STAILQ_HEAD(name, type)						\
3121f23347gibbsstruct name {								\
313961b97djake	struct type *stqh_first;/* first element */			\
314961b97djake	struct type **stqh_last;/* addr of last next element */		\
3151f23347gibbs}
3161f23347gibbs
3170647fddhselasky#define	STAILQ_CLASS_HEAD(name, type)					\
3180647fddhselaskystruct name {								\
3190647fddhselasky	class type *stqh_first;	/* first element */			\
3200647fddhselasky	class type **stqh_last;	/* addr of last next element */		\
3210647fddhselasky}
3220647fddhselasky
3238846e3bjake#define	STAILQ_HEAD_INITIALIZER(head)					\
3246b0a11cn_hibma	{ NULL, &(head).stqh_first }
3256b0a11cn_hibma
3268846e3bjake#define	STAILQ_ENTRY(type)						\
3271f23347gibbsstruct {								\
328961b97djake	struct type *stqe_next;	/* next element */			\
3291f23347gibbs}
3301f23347gibbs
3310647fddhselasky#define	STAILQ_CLASS_ENTRY(type)					\
3320647fddhselaskystruct {								\
3330647fddhselasky	class type *stqe_next;	/* next element */			\
3340647fddhselasky}
3350647fddhselasky
3361f23347gibbs/*
3371f23347gibbs * Singly-linked Tail queue functions.
3381f23347gibbs */
339c62faa9tmm#define	STAILQ_CONCAT(head1, head2) do {				\
340c62faa9tmm	if (!STAILQ_EMPTY((head2))) {					\
341c62faa9tmm		*(head1)->stqh_last = (head2)->stqh_first;		\
342c62faa9tmm		(head1)->stqh_last = (head2)->stqh_last;		\
343c62faa9tmm		STAILQ_INIT((head2));					\
344c62faa9tmm	}								\
345c62faa9tmm} while (0)
346c62faa9tmm
3478846e3bjake#define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)
3484941314phk
3498846e3bjake#define	STAILQ_FIRST(head)	((head)->stqh_first)
3501f23347gibbs
3518846e3bjake#define	STAILQ_FOREACH(var, head, field)				\
3528846e3bjake	for((var) = STAILQ_FIRST((head));				\
3538846e3bjake	   (var);							\
3548846e3bjake	   (var) = STAILQ_NEXT((var), field))
3553ff0dc0dfr
356aa062bflstewart#define	STAILQ_FOREACH_FROM(var, head, field)				\
357aa062bflstewart	for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));		\
358aa062bflstewart	   (var);							\
359aa062bflstewart	   (var) = STAILQ_NEXT((var), field))
360d822b4akan
361d822b4akan#define	STAILQ_FOREACH_SAFE(var, head, field, tvar)			\
362d822b4akan	for ((var) = STAILQ_FIRST((head));				\
363d822b4akan	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\
364d822b4akan	    (var) = (tvar))
365d822b4akan
366aa062bflstewart#define	STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)		\
367aa062bflstewart	for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));		\
368aa062bflstewart	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\
369aa062bflstewart	    (var) = (tvar))
370aa062bflstewart
3718846e3bjake#define	STAILQ_INIT(head) do {						\
3728846e3bjake	STAILQ_FIRST((head)) = NULL;					\
3738846e3bjake	(head)->stqh_last = &STAILQ_FIRST((head));			\
3744f3c123julian} while (0)
3751f23347gibbs
3768846e3bjake#define	STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\
3778846e3bjake	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
3788846e3bjake		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
3798846e3bjake	STAILQ_NEXT((tqelm), field) = (elm);				\
3804f3c123julian} while (0)
3811f23347gibbs
3828846e3bjake#define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
3838846e3bjake	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)	\
3848846e3bjake		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
3858846e3bjake	STAILQ_FIRST((head)) = (elm);					\
3864f3c123julian} while (0)
3871f23347gibbs
3888846e3bjake#define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
3898846e3bjake	STAILQ_NEXT((elm), field) = NULL;				\
3905fdba51hsu	*(head)->stqh_last = (elm);					\
3918846e3bjake	(head)->stqh_last = &STAILQ_NEXT((elm), field);			\
3924f3c123julian} while (0)
3931f23347gibbs
3940647fddhselasky#define	STAILQ_LAST(head, type, field)				\
3950647fddhselasky	(STAILQ_EMPTY((head)) ? NULL :				\
3960647fddhselasky	    __containerof((head)->stqh_last,			\
3970647fddhselasky	    QUEUE_TYPEOF(type), field.stqe_next))
3988846e3bjake
3998846e3bjake#define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
4006b0a11cn_hibma
4018846e3bjake#define	STAILQ_REMOVE(head, elm, type, field) do {			\
4021739980emaste	QMD_SAVELINK(oldnext, (elm)->field.stqe_next);			\
4038846e3bjake	if (STAILQ_FIRST((head)) == (elm)) {				\
40418d687dtmm		STAILQ_REMOVE_HEAD((head), field);			\
4051f23347gibbs	}								\
4061f23347gibbs	else {								\
4070647fddhselasky		QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head);	\
4088846e3bjake		while (STAILQ_NEXT(curelm, field) != (elm))		\
4098846e3bjake			curelm = STAILQ_NEXT(curelm, field);		\
4103779b68ed		STAILQ_REMOVE_AFTER(head, curelm, field);		\
4111f23347gibbs	}								\
4121739980emaste	TRASHIT(*oldnext);						\
4134f3c123julian} while (0)
4141f23347gibbs
4153779b68ed#define STAILQ_REMOVE_AFTER(head, elm, field) do {			\
416d5f5839ed	if ((STAILQ_NEXT(elm, field) =					\
417d5f5839ed	     STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)	\
418d5f5839ed		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
419d5f5839ed} while (0)
420d5f5839ed
4215e42f0amdf#define	STAILQ_REMOVE_HEAD(head, field) do {				\
4225e42f0amdf	if ((STAILQ_FIRST((head)) =					\
4235e42f0amdf	     STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)		\
4245e42f0amdf		(head)->stqh_last = &STAILQ_FIRST((head));		\
4255e42f0amdf} while (0)
4265e42f0amdf
427b5e46dazml#define STAILQ_SWAP(head1, head2, type) do {				\
4280647fddhselasky	QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1);		\
4290647fddhselasky	QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last;		\
430b5e46dazml	STAILQ_FIRST(head1) = STAILQ_FIRST(head2);			\
431b5e46dazml	(head1)->stqh_last = (head2)->stqh_last;			\
432b5e46dazml	STAILQ_FIRST(head2) = swap_first;				\
433b5e46dazml	(head2)->stqh_last = swap_last;					\
434b5e46dazml	if (STAILQ_EMPTY(head1))					\
435b5e46dazml		(head1)->stqh_last = &STAILQ_FIRST(head1);		\
436b5e46dazml	if (STAILQ_EMPTY(head2))					\
437b5e46dazml		(head2)->stqh_last = &STAILQ_FIRST(head2);		\
438b5e46dazml} while (0)
439b5e46dazml
440b5e46dazml
4411f23347gibbs/*
4428846e3bjake * List declarations.
4438fb65cergrimes */
4448846e3bjake#define	LIST_HEAD(name, type)						\
4458fb65cergrimesstruct name {								\
446961b97djake	struct type *lh_first;	/* first element */			\
4478fb65cergrimes}
4488fb65cergrimes
4490647fddhselasky#define	LIST_CLASS_HEAD(name, type)					\
4500647fddhselaskystruct name {								\
4510647fddhselasky	class type *lh_first;	/* first element */			\
4520647fddhselasky}
4530647fddhselasky
4548846e3bjake#define	LIST_HEAD_INITIALIZER(head)					\
4556b0a11cn_hibma	{ NULL }
4566b0a11cn_hibma
4578846e3bjake#define	LIST_ENTRY(type)						\
4588fb65cergrimesstruct {								\
459961b97djake	struct type *le_next;	/* next element */			\
460961b97djake	struct type **le_prev;	/* address of previous next element */	\
4618fb65cergrimes}
4628fb65cergrimes
4630647fddhselasky#define	LIST_CLASS_ENTRY(type)						\
4640647fddhselaskystruct {								\
4650647fddhselasky	class type *le_next;	/* next element */			\
4660647fddhselasky	class type **le_prev;	/* address of previous next element */	\
4670647fddhselasky}
4680647fddhselasky
4698fb65cergrimes/*
4708fb65cergrimes * List functions.
4718fb65cergrimes */
4724941314phk
47392d97b5emaste#if (defined(_KERNEL) && defined(INVARIANTS))
474185a929cem/*
475185a929cem * QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME)
476185a929cem *
477185a929cem * If the list is non-empty, validates that the first element of the list
478185a929cem * points back at 'head.'
479185a929cem */
48050b1ba7emaste#define	QMD_LIST_CHECK_HEAD(head, field) do {				\
48150b1ba7emaste	if (LIST_FIRST((head)) != NULL &&				\
48250b1ba7emaste	    LIST_FIRST((head))->field.le_prev !=			\
48350b1ba7emaste	     &LIST_FIRST((head)))					\
48450b1ba7emaste		panic("Bad list head %p first->prev != head", (head));	\
48550b1ba7emaste} while (0)
48650b1ba7emaste
487185a929cem/*
488185a929cem * QMD_LIST_CHECK_NEXT(TYPE *elm, LIST_ENTRY NAME)
489185a929cem *
490185a929cem * If an element follows 'elm' in the list, validates that the next element
491185a929cem * points back at 'elm.'
492185a929cem */
49350b1ba7emaste#define	QMD_LIST_CHECK_NEXT(elm, field) do {				\
49450b1ba7emaste	if (LIST_NEXT((elm), field) != NULL &&				\
49550b1ba7emaste	    LIST_NEXT((elm), field)->field.le_prev !=			\
49650b1ba7emaste	     &((elm)->field.le_next))					\
49750b1ba7emaste	     	panic("Bad link elm %p next->prev != elm", (elm));	\
49850b1ba7emaste} while (0)
49950b1ba7emaste
500185a929cem/*
501185a929cem * QMD_LIST_CHECK_PREV(TYPE *elm, LIST_ENTRY NAME)
502185a929cem *
503185a929cem * Validates that the previous element (or head of the list) points to 'elm.'
504185a929cem */
50550b1ba7emaste#define	QMD_LIST_CHECK_PREV(elm, field) do {				\
50650b1ba7emaste	if (*(elm)->field.le_prev != (elm))				\
50750b1ba7emaste		panic("Bad link elm %p prev->next != elm", (elm));	\
50850b1ba7emaste} while (0)
50950b1ba7emaste#else
51050b1ba7emaste#define	QMD_LIST_CHECK_HEAD(head, field)
51150b1ba7emaste#define	QMD_LIST_CHECK_NEXT(elm, field)
51250b1ba7emaste#define	QMD_LIST_CHECK_PREV(elm, field)
51392d97b5emaste#endif /* (_KERNEL && INVARIANTS) */
51450b1ba7emaste
5150aeae89mckusick#define LIST_CONCAT(head1, head2, type, field) do {			      \
5160aeae89mckusick	QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1);			      \
5170aeae89mckusick	if (curelm == NULL) {						      \
5180aeae89mckusick		if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) {	      \
5190aeae89mckusick			LIST_FIRST(head2)->field.le_prev =		      \
5200aeae89mckusick			    &LIST_FIRST((head1));			      \
5210aeae89mckusick			LIST_INIT(head2);				      \
5220aeae89mckusick		}							      \
5230aeae89mckusick	} else if (LIST_FIRST(head2) != NULL) {				      \
5240aeae89mckusick		while (LIST_NEXT(curelm, field) != NULL)		      \
5250aeae89mckusick			curelm = LIST_NEXT(curelm, field);		      \
5260aeae89mckusick		LIST_NEXT(curelm, field) = LIST_FIRST(head2);		      \
5270aeae89mckusick		LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \
5280aeae89mckusick		LIST_INIT(head2);					      \
5290aeae89mckusick	}								      \
5300aeae89mckusick} while (0)
5310aeae89mckusick
5328846e3bjake#define	LIST_EMPTY(head)	((head)->lh_first == NULL)
5334941314phk
5348846e3bjake#define	LIST_FIRST(head)	((head)->lh_first)
535fe8656aphk
5368846e3bjake#define	LIST_FOREACH(var, head, field)					\
5378846e3bjake	for ((var) = LIST_FIRST((head));				\
5388846e3bjake	    (var);							\
5398846e3bjake	    (var) = LIST_NEXT((var), field))
540fe8656aphk
541aa062bflstewart#define	LIST_FOREACH_FROM(var, head, field)				\
542aa062bflstewart	for ((var) = ((var) ? (var) : LIST_FIRST((head)));		\
543aa062bflstewart	    (var);							\
544aa062bflstewart	    (var) = LIST_NEXT((var), field))
545aa062bflstewart
546d822b4akan#define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
547d822b4akan	for ((var) = LIST_FIRST((head));				\
548d822b4akan	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\
549d822b4akan	    (var) = (tvar))
5503fe501bbmilekic
551aa062bflstewart#define	LIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
552aa062bflstewart	for ((var) = ((var) ? (var) : LIST_FIRST((head)));		\
553aa062bflstewart	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\
554aa062bflstewart	    (var) = (tvar))
555aa062bflstewart
5564f3c123julian#define	LIST_INIT(head) do {						\
5578846e3bjake	LIST_FIRST((head)) = NULL;					\
5584f3c123julian} while (0)
5598fb65cergrimes
5608846e3bjake#define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
56150b1ba7emaste	QMD_LIST_CHECK_NEXT(listelm, field);				\
5628846e3bjake	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
5638846e3bjake		LIST_NEXT((listelm), field)->field.le_prev =		\
5648846e3bjake		    &LIST_NEXT((elm), field);				\
5658846e3bjake	LIST_NEXT((listelm), field) = (elm);				\
5668846e3bjake	(elm)->field.le_prev = &LIST_NEXT((listelm), field);		\
5674f3c123julian} while (0)
5688fb65cergrimes
5698846e3bjake#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
57050b1ba7emaste	QMD_LIST_CHECK_PREV(listelm, field);				\
5712d24ffegibbs	(elm)->field.le_prev = (listelm)->field.le_prev;		\
5728846e3bjake	LIST_NEXT((elm), field) = (listelm);				\
5732d24ffegibbs	*(listelm)->field.le_prev = (elm);				\
5748846e3bjake	(listelm)->field.le_prev = &LIST_NEXT((elm), field);		\
5754f3c123julian} while (0)
5762d24ffegibbs
5778846e3bjake#define	LIST_INSERT_HEAD(head, elm, field) do {				\
57850b1ba7emaste	QMD_LIST_CHECK_HEAD((head), field);				\
5798846e3bjake	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\
5808846e3bjake		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
5818846e3bjake	LIST_FIRST((head)) = (elm);					\
5828846e3bjake	(elm)->field.le_prev = &LIST_FIRST((head));			\
5834f3c123julian} while (0)
5848fb65cergrimes
5858846e3bjake#define	LIST_NEXT(elm, field)	((elm)->field.le_next)
5860fa239bed
5870647fddhselasky#define	LIST_PREV(elm, head, type, field)			\
5880647fddhselasky	((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL :	\
5890647fddhselasky	    __containerof((elm)->field.le_prev,			\
5900647fddhselasky	    QUEUE_TYPEOF(type), field.le_next))
591fe8656aphk
5928846e3bjake#define	LIST_REMOVE(elm, field) do {					\
5931739980emaste	QMD_SAVELINK(oldnext, (elm)->field.le_next);			\
5941739980emaste	QMD_SAVELINK(oldprev, (elm)->field.le_prev);			\
59550b1ba7emaste	QMD_LIST_CHECK_NEXT(elm, field);				\
59650b1ba7emaste	QMD_LIST_CHECK_PREV(elm, field);				\
5978846e3bjake	if (LIST_NEXT((elm), field) != NULL)				\
5988846e3bjake		LIST_NEXT((elm), field)->field.le_prev = 		\
5998fb65cergrimes		    (elm)->field.le_prev;				\
6008846e3bjake	*(elm)->field.le_prev = LIST_NEXT((elm), field);		\
6011739980emaste	TRASHIT(*oldnext);						\
6021739980emaste	TRASHIT(*oldprev);						\
6034f3c123julian} while (0)
6048fb65cergrimes
605b5e46dazml#define LIST_SWAP(head1, head2, type, field) do {			\
6060647fddhselasky	QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1);		\
607b5e46dazml	LIST_FIRST((head1)) = LIST_FIRST((head2));			\
608b5e46dazml	LIST_FIRST((head2)) = swap_tmp;					\
609b5e46dazml	if ((swap_tmp = LIST_FIRST((head1))) != NULL)			\
610b5e46dazml		swap_tmp->field.le_prev = &LIST_FIRST((head1));		\
611b5e46dazml	if ((swap_tmp = LIST_FIRST((head2))) != NULL)			\
612b5e46dazml		swap_tmp->field.le_prev = &LIST_FIRST((head2));		\
613b5e46dazml} while (0)
614b5e46dazml
6158fb65cergrimes/*
6168846e3bjake * Tail queue declarations.
6178fb65cergrimes */
6188846e3bjake#define	TAILQ_HEAD(name, type)						\
6198fb65cergrimesstruct name {								\
620961b97djake	struct type *tqh_first;	/* first element */			\
621961b97djake	struct type **tqh_last;	/* addr of last next element */		\
622aa2dc0ajulian	TRACEBUF							\
6238fb65cergrimes}
6248fb65cergrimes
6250647fddhselasky#define	TAILQ_CLASS_HEAD(name, type)					\
6260647fddhselaskystruct name {								\
6270647fddhselasky	class type *tqh_first;	/* first element */			\
6280647fddhselasky	class type **tqh_last;	/* addr of last next element */		\
6290647fddhselasky	TRACEBUF							\
6300647fddhselasky}
6310647fddhselasky
6328846e3bjake#define	TAILQ_HEAD_INITIALIZER(head)					\
63340a2400glebius	{ NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
634d9cbf62gibbs
6358846e3bjake#define	TAILQ_ENTRY(type)						\
6368fb65cergrimesstruct {								\
637961b97djake	struct type *tqe_next;	/* next element */			\
638961b97djake	struct type **tqe_prev;	/* address of previous next element */	\
639aa2dc0ajulian	TRACEBUF							\
6408fb65cergrimes}
6418fb65cergrimes
6420647fddhselasky#define	TAILQ_CLASS_ENTRY(type)						\
6430647fddhselaskystruct {								\
6440647fddhselasky	class type *tqe_next;	/* next element */			\
6450647fddhselasky	class type **tqe_prev;	/* address of previous next element */	\
6460647fddhselasky	TRACEBUF							\
6470647fddhselasky}
6480647fddhselasky
6498fb65cergrimes/*
6508fb65cergrimes * Tail queue functions.
6518fb65cergrimes */
652