1/*-
2 * SPDX-License-Identifier: BSD-3-Clause
3 *
4 * Copyright (c) 1991, 1993
5 *	The Regents of the University of California.  All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 *    may be used to endorse or promote products derived from this software
17 *    without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 *
31 *	@(#)queue.h	8.5 (Berkeley) 8/20/94
32 * $FreeBSD$
33 */
34
35#ifndef _SYS_QUEUE_H_
36#define	_SYS_QUEUE_H_
37
38#include <sys/cdefs.h>
39
40/*
41 * This file defines four types of data structures: singly-linked lists,
42 * singly-linked tail queues, lists and tail queues.
43 *
44 * A singly-linked list is headed by a single forward pointer. The elements
45 * are singly linked for minimum space and pointer manipulation overhead at
46 * the expense of O(n) removal for arbitrary elements. New elements can be
47 * added to the list after an existing element or at the head of the list.
48 * Elements being removed from the head of the list should use the explicit
49 * macro for this purpose for optimum efficiency. A singly-linked list may
50 * only be traversed in the forward direction.  Singly-linked lists are ideal
51 * for applications with large datasets and few or no removals or for
52 * implementing a LIFO queue.
53 *
54 * A singly-linked tail queue is headed by a pair of pointers, one to the
55 * head of the list and the other to the tail of the list. The elements are
56 * singly linked for minimum space and pointer manipulation overhead at the
57 * expense of O(n) removal for arbitrary elements. New elements can be added
58 * to the list after an existing element, at the head of the list, or at the
59 * end of the list. Elements being removed from the head of the tail queue
60 * should use the explicit macro for this purpose for optimum efficiency.
61 * A singly-linked tail queue may only be traversed in the forward direction.
62 * Singly-linked tail queues are ideal for applications with large datasets
63 * and few or no removals or for implementing a FIFO queue.
64 *
65 * A list is headed by a single forward pointer (or an array of forward
66 * pointers for a hash table header). The elements are doubly linked
67 * so that an arbitrary element can be removed without a need to
68 * traverse the list. New elements can be added to the list before
69 * or after an existing element or at the head of the list. A list
70 * may be traversed in either direction.
71 *
72 * A tail queue is headed by a pair of pointers, one to the head of the
73 * list and the other to the tail of the list. The elements are doubly
74 * linked so that an arbitrary element can be removed without a need to
75 * traverse the list. New elements can be added to the list before or
76 * after an existing element, at the head of the list, or at the end of
77 * the list. A tail queue may be traversed in either direction.
78 *
79 * For details on the use of these macros, see the queue(3) manual page.
80 *
81 * Below is a summary of implemented functions where:
82 *  +  means the macro is available
83 *  -  means the macro is not available
84 *  s  means the macro is available but is slow (runs in O(n) time)
85 *
86 *				SLIST	LIST	STAILQ	TAILQ
87 * _HEAD			+	+	+	+
88 * _CLASS_HEAD			+	+	+	+
89 * _HEAD_INITIALIZER		+	+	+	+
90 * _ENTRY			+	+	+	+
91 * _CLASS_ENTRY			+	+	+	+
92 * _INIT			+	+	+	+
93 * _EMPTY			+	+	+	+
94 * _FIRST			+	+	+	+
95 * _NEXT			+	+	+	+
96 * _PREV			-	+	-	+
97 * _LAST			-	-	+	+
98 * _LAST_FAST			-	-	-	+
99 * _FOREACH			+	+	+	+
100 * _FOREACH_FROM		+	+	+	+
101 * _FOREACH_SAFE		+	+	+	+
102 * _FOREACH_FROM_SAFE		+	+	+	+
103 * _FOREACH_REVERSE		-	-	-	+
104 * _FOREACH_REVERSE_FROM	-	-	-	+
105 * _FOREACH_REVERSE_SAFE	-	-	-	+
106 * _FOREACH_REVERSE_FROM_SAFE	-	-	-	+
107 * _INSERT_HEAD			+	+	+	+
108 * _INSERT_BEFORE		-	+	-	+
109 * _INSERT_AFTER		+	+	+	+
110 * _INSERT_TAIL			-	-	+	+
111 * _CONCAT			s	s	+	+
112 * _REMOVE_AFTER		+	-	+	-
113 * _REMOVE_HEAD			+	-	+	-
114 * _REMOVE			s	+	s	+
115 * _SWAP			+	+	+	+
116 *
117 */
118#ifdef QUEUE_MACRO_DEBUG
119#warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH
120#define	QUEUE_MACRO_DEBUG_TRACE
121#define	QUEUE_MACRO_DEBUG_TRASH
122#endif
123
124#ifdef QUEUE_MACRO_DEBUG_TRACE
125/* Store the last 2 places the queue element or head was altered */
126struct qm_trace {
127	unsigned long	 lastline;
128	unsigned long	 prevline;
129	const char	*lastfile;
130	const char	*prevfile;
131};
132
133#define	TRACEBUF	struct qm_trace trace;
134#define	TRACEBUF_INITIALIZER	{ __LINE__, 0, __FILE__, NULL } ,
135
136#define	QMD_TRACE_HEAD(head) do {					\
137	(head)->trace.prevline = (head)->trace.lastline;		\
138	(head)->trace.prevfile = (head)->trace.lastfile;		\
139	(head)->trace.lastline = __LINE__;				\
140	(head)->trace.lastfile = __FILE__;				\
141} while (0)
142
143#define	QMD_TRACE_ELEM(elem) do {					\
144	(elem)->trace.prevline = (elem)->trace.lastline;		\
145	(elem)->trace.prevfile = (elem)->trace.lastfile;		\
146	(elem)->trace.lastline = __LINE__;				\
147	(elem)->trace.lastfile = __FILE__;				\
148} while (0)
149
150#else	/* !QUEUE_MACRO_DEBUG_TRACE */
151#define	QMD_TRACE_ELEM(elem)
152#define	QMD_TRACE_HEAD(head)
153#define	TRACEBUF
154#define	TRACEBUF_INITIALIZER
155#endif	/* QUEUE_MACRO_DEBUG_TRACE */
156
157#ifdef QUEUE_MACRO_DEBUG_TRASH
158#define	QMD_SAVELINK(name, link)	void **name = (void *)&(link)
159#define	TRASHIT(x)		do {(x) = (void *)-1;} while (0)
160#define	QMD_IS_TRASHED(x)	((x) == (void *)(intptr_t)-1)
161#else	/* !QUEUE_MACRO_DEBUG_TRASH */
162#define	QMD_SAVELINK(name, link)
163#define	TRASHIT(x)
164#define	QMD_IS_TRASHED(x)	0
165#endif	/* QUEUE_MACRO_DEBUG_TRASH */
166
167#ifdef __cplusplus
168/*
169 * In C++ there can be structure lists and class lists:
170 */
171#define	QUEUE_TYPEOF(type) type
172#else
173#define	QUEUE_TYPEOF(type) struct type
174#endif
175
176/*
177 * Singly-linked List declarations.
178 */
179#define	SLIST_HEAD(name, type)						\
180struct name {								\
181	struct type *slh_first;	/* first element */			\
182}
183
184#define	SLIST_CLASS_HEAD(name, type)					\
185struct name {								\
186	class type *slh_first;	/* first element */			\
187}
188
189#define	SLIST_HEAD_INITIALIZER(head)					\
190	{ NULL }
191
192#define	SLIST_ENTRY(type)						\
193struct {								\
194	struct type *sle_next;	/* next element */			\
195}
196
197#define	SLIST_CLASS_ENTRY(type)						\
198struct {								\
199	class type *sle_next;		/* next element */		\
200}
201
202/*
203 * Singly-linked List functions.
204 */
205#if (defined(_KERNEL) && defined(INVARIANTS))
206#define	QMD_SLIST_CHECK_PREVPTR(prevp, elm) do {			\
207	if (*(prevp) != (elm))						\
208		panic("Bad prevptr *(%p) == %p != %p",			\
209		    (prevp), *(prevp), (elm));				\
210} while (0)
211#else
212#define	QMD_SLIST_CHECK_PREVPTR(prevp, elm)
213#endif
214
215#define SLIST_CONCAT(head1, head2, type, field) do {			\
216	QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1);		\
217	if (curelm == NULL) {						\
218		if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) != NULL)	\
219			SLIST_INIT(head2);				\
220	} else if (SLIST_FIRST(head2) != NULL) {			\
221		while (SLIST_NEXT(curelm, field) != NULL)		\
222			curelm = SLIST_NEXT(curelm, field);		\
223		SLIST_NEXT(curelm, field) = SLIST_FIRST(head2);		\
224		SLIST_INIT(head2);					\
225	}								\
226} while (0)
227
228#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
229
230#define	SLIST_FIRST(head)	((head)->slh_first)
231
232#define	SLIST_FOREACH(var, head, field)					\
233	for ((var) = SLIST_FIRST((head));				\
234	    (var);							\
235	    (var) = SLIST_NEXT((var), field))
236
237#define	SLIST_FOREACH_FROM(var, head, field)				\
238	for ((var) = ((var) ? (var) : SLIST_FIRST((head)));		\
239	    (var);							\
240	    (var) = SLIST_NEXT((var), field))
241
242#define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
243	for ((var) = SLIST_FIRST((head));				\
244	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);		\
245	    (var) = (tvar))
246
247#define	SLIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
248	for ((var) = ((var) ? (var) : SLIST_FIRST((head)));		\
249	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);		\
250	    (var) = (tvar))
251
252#define	SLIST_FOREACH_PREVPTR(var, varp, head, field)			\
253	for ((varp) = &SLIST_FIRST((head));				\
254	    ((var) = *(varp)) != NULL;					\
255	    (varp) = &SLIST_NEXT((var), field))
256
257#define	SLIST_INIT(head) do {						\
258	SLIST_FIRST((head)) = NULL;					\
259} while (0)
260
261#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
262	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);	\
263	SLIST_NEXT((slistelm), field) = (elm);				\
264} while (0)
265
266#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
267	SLIST_NEXT((elm), field) = SLIST_FIRST((head));			\
268	SLIST_FIRST((head)) = (elm);					\
269} while (0)
270
271#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
272
273#define	SLIST_REMOVE(head, elm, type, field) do {			\
274	QMD_SAVELINK(oldnext, (elm)->field.sle_next);			\
275	if (SLIST_FIRST((head)) == (elm)) {				\
276		SLIST_REMOVE_HEAD((head), field);			\
277	}								\
278	else {								\
279		QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head);		\
280		while (SLIST_NEXT(curelm, field) != (elm))		\
281			curelm = SLIST_NEXT(curelm, field);		\
282		SLIST_REMOVE_AFTER(curelm, field);			\
283	}								\
284	TRASHIT(*oldnext);						\
285} while (0)
286
287#define SLIST_REMOVE_AFTER(elm, field) do {				\
288	SLIST_NEXT(elm, field) =					\
289	    SLIST_NEXT(SLIST_NEXT(elm, field), field);			\
290} while (0)
291
292#define	SLIST_REMOVE_HEAD(head, field) do {				\
293	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
294} while (0)
295
296#define	SLIST_REMOVE_PREVPTR(prevp, elm, field) do {			\
297	QMD_SLIST_CHECK_PREVPTR(prevp, elm);				\
298	*(prevp) = SLIST_NEXT(elm, field);				\
299	TRASHIT((elm)->field.sle_next);					\
300} while (0)
301
302#define SLIST_SWAP(head1, head2, type) do {				\
303	QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1);		\
304	SLIST_FIRST(head1) = SLIST_FIRST(head2);			\
305	SLIST_FIRST(head2) = swap_first;				\
306} while (0)
307
308/*
309 * Singly-linked Tail queue declarations.
310 */
311#define	STAILQ_HEAD(name, type)						\
312struct name {								\
313	struct type *stqh_first;/* first element */			\
314	struct type **stqh_last;/* addr of last next element */		\
315}
316
317#define	STAILQ_CLASS_HEAD(name, type)					\
318struct name {								\
319	class type *stqh_first;	/* first element */			\
320	class type **stqh_last;	/* addr of last next element */		\
321}
322
323#define	STAILQ_HEAD_INITIALIZER(head)					\
324	{ NULL, &(head).stqh_first }
325
326#define	STAILQ_ENTRY(type)						\
327struct {								\
328	struct type *stqe_next;	/* next element */			\
329}
330
331#define	STAILQ_CLASS_ENTRY(type)					\
332struct {								\
333	class type *stqe_next;	/* next element */			\
334}
335
336/*
337 * Singly-linked Tail queue functions.
338 */
339#define	STAILQ_CONCAT(head1, head2) do {				\
340	if (!STAILQ_EMPTY((head2))) {					\
341		*(head1)->stqh_last = (head2)->stqh_first;		\
342		(head1)->stqh_last = (head2)->stqh_last;		\
343		STAILQ_INIT((head2));					\
344	}								\
345} while (0)
346
347#define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)
348
349#define	STAILQ_FIRST(head)	((head)->stqh_first)
350
351#define	STAILQ_FOREACH(var, head, field)				\
352	for((var) = STAILQ_FIRST((head));				\
353	   (var);							\
354	   (var) = STAILQ_NEXT((var), field))
355
356#define	STAILQ_FOREACH_FROM(var, head, field)				\
357	for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));		\
358	   (var);							\
359	   (var) = STAILQ_NEXT((var), field))
360
361#define	STAILQ_FOREACH_SAFE(var, head, field, tvar)			\
362	for ((var) = STAILQ_FIRST((head));				\
363	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\
364	    (var) = (tvar))
365
366#define	STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)		\
367	for ((var) = ((var) ? (var) : STAILQ_FIRST((head)));		\
368	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\
369	    (var) = (tvar))
370
371#define	STAILQ_INIT(head) do {						\
372	STAILQ_FIRST((head)) = NULL;					\
373	(head)->stqh_last = &STAILQ_FIRST((head));			\
374} while (0)
375
376#define	STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\
377	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
378		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
379	STAILQ_NEXT((tqelm), field) = (elm);				\
380} while (0)
381
382#define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
383	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)	\
384		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
385	STAILQ_FIRST((head)) = (elm);					\
386} while (0)
387
388#define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
389	STAILQ_NEXT((elm), field) = NULL;				\
390	*(head)->stqh_last = (elm);					\
391	(head)->stqh_last = &STAILQ_NEXT((elm), field);			\
392} while (0)
393
394#define	STAILQ_LAST(head, type, field)				\
395	(STAILQ_EMPTY((head)) ? NULL :				\
396	    __containerof((head)->stqh_last,			\
397	    QUEUE_TYPEOF(type), field.stqe_next))
398
399#define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
400
401#define	STAILQ_REMOVE(head, elm, type, field) do {			\
402	QMD_SAVELINK(oldnext, (elm)->field.stqe_next);			\
403	if (STAILQ_FIRST((head)) == (elm)) {				\
404		STAILQ_REMOVE_HEAD((head), field);			\
405	}								\
406	else {								\
407		QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head);	\
408		while (STAILQ_NEXT(curelm, field) != (elm))		\
409			curelm = STAILQ_NEXT(curelm, field);		\
410		STAILQ_REMOVE_AFTER(head, curelm, field);		\
411	}								\
412	TRASHIT(*oldnext);						\
413} while (0)
414
415#define STAILQ_REMOVE_AFTER(head, elm, field) do {			\
416	if ((STAILQ_NEXT(elm, field) =					\
417	     STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)	\
418		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
419} while (0)
420
421#define	STAILQ_REMOVE_HEAD(head, field) do {				\
422	if ((STAILQ_FIRST((head)) =					\
423	     STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)		\
424		(head)->stqh_last = &STAILQ_FIRST((head));		\
425} while (0)
426
427#define STAILQ_SWAP(head1, head2, type) do {				\
428	QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1);		\
429	QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last;		\
430	STAILQ_FIRST(head1) = STAILQ_FIRST(head2);			\
431	(head1)->stqh_last = (head2)->stqh_last;			\
432	STAILQ_FIRST(head2) = swap_first;				\
433	(head2)->stqh_last = swap_last;					\
434	if (STAILQ_EMPTY(head1))					\
435		(head1)->stqh_last = &STAILQ_FIRST(head1);		\
436	if (STAILQ_EMPTY(head2))					\
437		(head2)->stqh_last = &STAILQ_FIRST(head2);		\
438} while (0)
439
440
441/*
442 * List declarations.
443 */
444#define	LIST_HEAD(name, type)						\
445struct name {								\
446	struct type *lh_first;	/* first element */			\
447}
448
449#define	LIST_CLASS_HEAD(name, type)					\
450struct name {								\
451	class type *lh_first;	/* first element */			\
452}
453
454#define	LIST_HEAD_INITIALIZER(head)					\
455	{ NULL }
456
457#define	LIST_ENTRY(type)						\
458struct {								\
459	struct type *le_next;	/* next element */			\
460	struct type **le_prev;	/* address of previous next element */	\
461}
462
463#define	LIST_CLASS_ENTRY(type)						\
464struct {								\
465	class type *le_next;	/* next element */			\
466	class type **le_prev;	/* address of previous next element */	\
467}
468
469/*
470 * List functions.
471 */
472
473#if (defined(_KERNEL) && defined(INVARIANTS))
474/*
475 * QMD_LIST_CHECK_HEAD(LIST_HEAD *head, LIST_ENTRY NAME)
476 *
477 * If the list is non-empty, validates that the first element of the list
478 * points back at 'head.'
479 */
480#define	QMD_LIST_CHECK_HEAD(head, field) do {				\
481	if (LIST_FIRST((head)) != NULL &&				\
482	    LIST_FIRST((head))->field.le_prev !=			\
483	     &LIST_FIRST((head)))					\
484		panic("Bad list head %p first->prev != head", (head));	\
485} while (0)
486
487/*
488 * QMD_LIST_CHECK_NEXT(TYPE *elm, LIST_ENTRY NAME)
489 *
490 * If an element follows 'elm' in the list, validates that the next element
491 * points back at 'elm.'
492 */
493#define	QMD_LIST_CHECK_NEXT(elm, field) do {				\
494	if (LIST_NEXT((elm), field) != NULL &&				\
495	    LIST_NEXT((elm), field)->field.le_prev !=			\
496	     &((elm)->field.le_next))					\
497	     	panic("Bad link elm %p next->prev != elm", (elm));	\
498} while (0)
499
500/*
501 * QMD_LIST_CHECK_PREV(TYPE *elm, LIST_ENTRY NAME)
502 *
503 * Validates that the previous element (or head of the list) points to 'elm.'
504 */
505#define	QMD_LIST_CHECK_PREV(elm, field) do {				\
506	if (*(elm)->field.le_prev != (elm))				\
507		panic("Bad link elm %p prev->next != elm", (elm));	\
508} while (0)
509#else
510#define	QMD_LIST_CHECK_HEAD(head, field)
511#define	QMD_LIST_CHECK_NEXT(elm, field)
512#define	QMD_LIST_CHECK_PREV(elm, field)
513#endif /* (_KERNEL && INVARIANTS) */
514
515#define LIST_CONCAT(head1, head2, type, field) do {			      \
516	QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1);			      \
517	if (curelm == NULL) {						      \
518		if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) {	      \
519			LIST_FIRST(head2)->field.le_prev =		      \
520			    &LIST_FIRST((head1));			      \
521			LIST_INIT(head2);				      \
522		}							      \
523	} else if (LIST_FIRST(head2) != NULL) {				      \
524		while (LIST_NEXT(curelm, field) != NULL)		      \
525			curelm = LIST_NEXT(curelm, field);		      \
526		LIST_NEXT(curelm, field) = LIST_FIRST(head2);		      \
527		LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \
528		LIST_INIT(head2);					      \
529	}								      \
530} while (0)
531
532#define	LIST_EMPTY(head)	((head)->lh_first == NULL)
533
534#define	LIST_FIRST(head)	((head)->lh_first)
535
536#define	LIST_FOREACH(var, head, field)					\
537	for ((var) = LIST_FIRST((head));				\
538	    (var);							\
539	    (var) = LIST_NEXT((var), field))
540
541#define	LIST_FOREACH_FROM(var, head, field)				\
542	for ((var) = ((var) ? (var) : LIST_FIRST((head)));		\
543	    (var);							\
544	    (var) = LIST_NEXT((var), field))
545
546#define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
547	for ((var) = LIST_FIRST((head));				\
548	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\
549	    (var) = (tvar))
550
551#define	LIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
552	for ((var) = ((var) ? (var) : LIST_FIRST((head)));		\
553	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\
554	    (var) = (tvar))
555
556#define	LIST_INIT(head) do {						\
557	LIST_FIRST((head)) = NULL;					\
558} while (0)
559
560#define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
561	QMD_LIST_CHECK_NEXT(listelm, field);				\
562	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
563		LIST_NEXT((listelm), field)->field.le_prev =		\
564		    &LIST_NEXT((elm), field);				\
565	LIST_NEXT((listelm), field) = (elm);				\
566	(elm)->field.le_prev = &LIST_NEXT((listelm), field);		\
567} while (0)
568
569#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
570	QMD_LIST_CHECK_PREV(listelm, field);				\
571	(elm)->field.le_prev = (listelm)->field.le_prev;		\
572	LIST_NEXT((elm), field) = (listelm);				\
573	*(listelm)->field.le_prev = (elm);				\
574	(listelm)->field.le_prev = &LIST_NEXT((elm), field);		\
575} while (0)
576
577#define	LIST_INSERT_HEAD(head, elm, field) do {				\
578	QMD_LIST_CHECK_HEAD((head), field);				\
579	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\
580		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
581	LIST_FIRST((head)) = (elm);					\
582	(elm)->field.le_prev = &LIST_FIRST((head));			\
583} while (0)
584
585#define	LIST_NEXT(elm, field)	((elm)->field.le_next)
586
587#define	LIST_PREV(elm, head, type, field)			\
588	((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL :	\
589	    __containerof((elm)->field.le_prev,			\
590	    QUEUE_TYPEOF(type), field.le_next))
591
592#define	LIST_REMOVE(elm, field) do {					\
593	QMD_SAVELINK(oldnext, (elm)->field.le_next);			\
594	QMD_SAVELINK(oldprev, (elm)->field.le_prev);			\
595	QMD_LIST_CHECK_NEXT(elm, field);				\
596	QMD_LIST_CHECK_PREV(elm, field);				\
597	if (LIST_NEXT((elm), field) != NULL)				\
598		LIST_NEXT((elm), field)->field.le_prev = 		\
599		    (elm)->field.le_prev;				\
600	*(elm)->field.le_prev = LIST_NEXT((elm), field);		\
601	TRASHIT(*oldnext);						\
602	TRASHIT(*oldprev);						\
603} while (0)
604
605#define LIST_SWAP(head1, head2, type, field) do {			\
606	QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1);		\
607	LIST_FIRST((head1)) = LIST_FIRST((head2));			\
608	LIST_FIRST((head2)) = swap_tmp;					\
609	if ((swap_tmp = LIST_FIRST((head1))) != NULL)			\
610		swap_tmp->field.le_prev = &LIST_FIRST((head1));		\
611	if ((swap_tmp = LIST_FIRST((head2))) != NULL)			\
612		swap_tmp->field.le_prev = &LIST_FIRST((head2));		\
613} while (0)
614
615/*
616 * Tail queue declarations.
617 */
618#define	TAILQ_HEAD(name, type)						\
619struct name {								\
620	struct type *tqh_first;	/* first element */			\
621	struct type **tqh_last;	/* addr of last next element */		\
622	TRACEBUF							\
623}
624
625#define	TAILQ_CLASS_HEAD(name, type)					\
626struct name {								\
627	class type *tqh_first;	/* first element */			\
628	class type **tqh_last;	/* addr of last next element */		\
629	TRACEBUF							\
630}
631
632#define	TAILQ_HEAD_INITIALIZER(head)					\
633	{ NULL, &(head).tqh_first, TRACEBUF_INITIALIZER }
634
635#define	TAILQ_ENTRY(type)						\
636struct {								\
637	struct type *tqe_next;	/* next element */			\
638	struct type **tqe_prev;	/* address of previous next element */	\
639	TRACEBUF							\
640}
641
642#define	TAILQ_CLASS_ENTRY(type)						\
643struct {								\
644	class type *tqe_next;	/* next element */			\
645	class type **tqe_prev;	/* address of previous next element */	\
646	TRACEBUF							\
647}
648
649/*
650 * Tail queue functions.
651 */
652#if (defined(_KERNEL) && defined(INVARIANTS))
653/*
654 * QMD_TAILQ_CHECK_HEAD(TAILQ_HEAD *head, TAILQ_ENTRY NAME)
655 *
656 * If the tailq is non-empty, validates that the first element of the tailq
657 * points back at 'head.'
658 */
659#define	QMD_TAILQ_CHECK_HEAD(head, field) do {				\
660	if (!TAILQ_EMPTY(head) &&					\
661	    TAILQ_FIRST((head))->field.tqe_prev !=			\
662	     &TAILQ_FIRST((head)))					\
663		panic("Bad tailq head %p first->prev != head", (head));	\
664} while (0)
665
666/*
667 * QMD_TAILQ_CHECK_TAIL(TAILQ_HEAD *head, TAILQ_ENTRY NAME)
668 *
669 * Validates that the tail of the tailq is a pointer to pointer to NULL.
670 */
671#define	QMD_TAILQ_CHECK_TAIL(head, field) do {				\
672	if (*(head)->tqh_last != NULL)					\
673	    	panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); 	\
674} while (0)
675
676/*
677 * QMD_TAILQ_CHECK_NEXT(TYPE *elm, TAILQ_ENTRY NAME)
678 *
679 * If an element follows 'elm' in the tailq, validates that the next element
680 * points back at 'elm.'
681 */
682#define	QMD_TAILQ_CHECK_NEXT(elm, field) do {				\
683	if (TAILQ_NEXT((elm), field) != NULL &&				\
684	    TAILQ_NEXT((elm), field)->field.tqe_prev !=			\
685	     &((elm)->field.tqe_next))					\
686		panic("Bad link elm %p next->prev != elm", (elm));	\
687} while (0)
688
689/*
690 * QMD_TAILQ_CHECK_PREV(TYPE *elm, TAILQ_ENTRY NAME)
691 *
692 * Validates that the previous element (or head of the tailq) points to 'elm.'
693 */
694#define	QMD_TAILQ_CHECK_PREV(elm, field) do {				\
695	if (*(elm)->field.tqe_prev != (elm))				\
696		panic("Bad link elm %p prev->next != elm", (elm));	\
697} while (0)
698#else
699#define	QMD_TAILQ_CHECK_HEAD(head, field)
700#define	QMD_TAILQ_CHECK_TAIL(head, headname)
701#define	QMD_TAILQ_CHECK_NEXT(elm, field)
702#define	QMD_TAILQ_CHECK_PREV(elm, field)
703#endif /* (_KERNEL && INVARIANTS) */
704
705#define	TAILQ_CONCAT(head1, head2, field) do {				\
706	if (!TAILQ_EMPTY(head2)) {					\
707		*(head1)->tqh_last = (head2)->tqh_first;		\
708		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
709		(head1)->tqh_last = (head2)->tqh_last;			\
710		TAILQ_INIT((head2));					\
711		QMD_TRACE_HEAD(head1);					\
712		QMD_TRACE_HEAD(head2);					\
713	}								\
714} while (0)
715
716#define	TAILQ_EMPTY(head)	((head)->tqh_first == NULL)
717
718#define	TAILQ_FIRST(head)	((head)->tqh_first)
719
720#define	TAILQ_FOREACH(var, head, field)					\
721	for ((var) = TAILQ_FIRST((head));				\
722	    (var);							\
723	    (var) = TAILQ_NEXT((var), field))
724
725#define	TAILQ_FOREACH_FROM(var, head, field)				\
726	for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));		\
727	    (var);							\
728	    (var) = TAILQ_NEXT((var), field))
729
730#define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
731	for ((var) = TAILQ_FIRST((head));				\
732	    (var) && ((tvar) = TAILQ_NEXT((var), field), 1);		\
733	    (var) = (tvar))
734
735#define	TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)			\
736	for ((var) = ((var) ? (var) : TAILQ_FIRST((head)));		\
737	    (var) && ((tvar) = TAILQ_NEXT((var), field), 1);		\
738	    (var) = (tvar))
739
740#define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
741	for ((var) = TAILQ_LAST((head), headname);			\
742	    (var);							\
743	    (var) = TAILQ_PREV((var), headname, field))
744
745#define	TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field)		\
746	for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));	\
747	    (var);							\
748	    (var) = TAILQ_PREV((var), headname, field))
749
750#define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
751	for ((var) = TAILQ_LAST((head), headname);			\
752	    (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);	\
753	    (var) = (tvar))
754
755#define	TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
756	for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname));	\
757	    (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);	\
758	    (var) = (tvar))
759
760#define	TAILQ_INIT(head) do {						\
761	TAILQ_FIRST((head)) = NULL;					\
762	(head)->tqh_last = &TAILQ_FIRST((head));			\
763	QMD_TRACE_HEAD(head);						\
764} while (0)
765
766#define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
767	QMD_TAILQ_CHECK_NEXT(listelm, field);				\
768	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
769		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\
770		    &TAILQ_NEXT((elm), field);				\
771	else {								\
772		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
773		QMD_TRACE_HEAD(head);					\
774	}								\
775	TAILQ_NEXT((listelm), field) = (elm);				\
776	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);		\
777	QMD_TRACE_ELEM(&(elm)->field);					\
778	QMD_TRACE_ELEM(&(listelm)->field);				\
779} while (0)
780
781#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
782	QMD_TAILQ_CHECK_PREV(listelm, field);				\
783	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
784	TAILQ_NEXT((elm), field) = (listelm);				\
785	*(listelm)->field.tqe_prev = (elm);				\
786	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);		\
787	QMD_TRACE_ELEM(&(elm)->field);					\
788	QMD_TRACE_ELEM(&(listelm)->field);				\
789} while (0)
790
791#define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
792	QMD_TAILQ_CHECK_HEAD(head, field);				\
793	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)	\
794		TAILQ_FIRST((head))->field.tqe_prev =			\
795		    &TAILQ_NEXT((elm), field);				\
796	else								\
797		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
798	TAILQ_FIRST((head)) = (elm);					\
799	(elm)->field.tqe_prev = &TAILQ_FIRST((head));			\
800	QMD_TRACE_HEAD(head);						\
801	QMD_TRACE_ELEM(&(elm)->field);					\
802} while (0)
803
804#define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
805	QMD_TAILQ_CHECK_TAIL(head, field);				\
806	TAILQ_NEXT((elm), field) = NULL;				\
807	(elm)->field.tqe_prev = (head)->tqh_last;			\
808	*(head)->tqh_last = (elm);					\
809	(head)->tqh_last = &TAILQ_NEXT((elm), field);			\
810	QMD_TRACE_HEAD(head);						\
811	QMD_TRACE_ELEM(&(elm)->field);					\
812} while (0)
813
814#define	TAILQ_LAST(head, headname)					\
815	(*(((struct headname *)((head)->tqh_last))->tqh_last))
816
817/*
818 * The FAST function is fast in that it causes no data access other
819 * then the access to the head. The standard LAST function above
820 * will cause a data access of both the element you want and
821 * the previous element. FAST is very useful for instances when
822 * you may want to prefetch the last data element.
823 */
824#define	TAILQ_LAST_FAST(head, type, field)			\
825    (TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, QUEUE_TYPEOF(type), field.tqe_next))
826
827#define	TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
828
829#define	TAILQ_PREV(elm, headname, field)				\
830	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
831
832#define	TAILQ_PREV_FAST(elm, head, type, field)				\
833    ((elm)->field.tqe_prev == &(head)->tqh_first ? NULL :		\
834     __containerof((elm)->field.tqe_prev, QUEUE_TYPEOF(type), field.tqe_next))
835
836#define	TAILQ_REMOVE(head, elm, field) do {				\
837	QMD_SAVELINK(oldnext, (elm)->field.tqe_next);			\
838	QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);			\
839	QMD_TAILQ_CHECK_NEXT(elm, field);				\
840	QMD_TAILQ_CHECK_PREV(elm, field);				\
841	if ((TAILQ_NEXT((elm), field)) != NULL)				\
842		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\
843		    (elm)->field.tqe_prev;				\
844	else {								\
845		(head)->tqh_last = (elm)->field.tqe_prev;		\
846		QMD_TRACE_HEAD(head);					\
847	}								\
848	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);		\
849	TRASHIT(*oldnext);						\
850	TRASHIT(*oldprev);						\
851	QMD_TRACE_ELEM(&(elm)->field);					\
852} while (0)
853
854#define TAILQ_SWAP(head1, head2, type, field) do {			\
855	QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first;		\
856	QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last;		\
857	(head1)->tqh_first = (head2)->tqh_first;			\
858	(head1)->tqh_last = (head2)->tqh_last;				\
859	(head2)->tqh_first = swap_first;				\
860	(head2)->tqh_last = swap_last;					\
861	if ((swap_first = (head1)->tqh_first) != NULL)			\
862		swap_first->field.tqe_prev = &(head1)->tqh_first;	\
863	else								\
864		(head1)->tqh_last = &(head1)->tqh_first;		\
865	if ((swap_first = (head2)->tqh_first) != NULL)			\
866		swap_first->field.tqe_prev = &(head2)->tqh_first;	\
867	else								\
868		(head2)->tqh_last = &(head2)->tqh_first;		\
869} while (0)
870
871#endif /* !_SYS_QUEUE_H_ */
872