xref: /illumos-gate/usr/src/uts/common/sys/queue.h (revision 85280f08)
1381a2a9aSdr /*
2381a2a9aSdr  * Copyright (c) 1991, 1993
3381a2a9aSdr  *	The Regents of the University of California.  All rights reserved.
4381a2a9aSdr  *
5381a2a9aSdr  * Redistribution and use in source and binary forms, with or without
6381a2a9aSdr  * modification, are permitted provided that the following conditions
7381a2a9aSdr  * are met:
8381a2a9aSdr  * 1. Redistributions of source code must retain the above copyright
9381a2a9aSdr  *    notice, this list of conditions and the following disclaimer.
10381a2a9aSdr  * 2. Redistributions in binary form must reproduce the above copyright
11381a2a9aSdr  *    notice, this list of conditions and the following disclaimer in the
12381a2a9aSdr  *    documentation and/or other materials provided with the distribution.
13381a2a9aSdr  * 3. Neither the name of the University nor the names of its contributors
14381a2a9aSdr  *    may be used to endorse or promote products derived from this software
15381a2a9aSdr  *    without specific prior written permission.
16381a2a9aSdr  *
17381a2a9aSdr  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18381a2a9aSdr  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19381a2a9aSdr  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20381a2a9aSdr  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21381a2a9aSdr  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22381a2a9aSdr  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23381a2a9aSdr  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24381a2a9aSdr  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25381a2a9aSdr  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26381a2a9aSdr  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27381a2a9aSdr  * SUCH DAMAGE.
28381a2a9aSdr  *
29381a2a9aSdr  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
30381a2a9aSdr  */
31381a2a9aSdr /*
32c1374a13SSurya Prakki  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
33381a2a9aSdr  * Use is subject to license terms.
34381a2a9aSdr  */
35381a2a9aSdr 
36381a2a9aSdr #ifndef	_SYS_QUEUE_H
37381a2a9aSdr #define	_SYS_QUEUE_H
38381a2a9aSdr 
39381a2a9aSdr #include <sys/note.h>
40*85280f08SToomas Soome #include <sys/containerof.h>
41381a2a9aSdr 
42*85280f08SToomas Soome #ifdef __cplusplus
43381a2a9aSdr extern "C" {
44381a2a9aSdr #endif
45381a2a9aSdr 
46381a2a9aSdr /*
47381a2a9aSdr  * This file defines five types of data structures: singly-linked lists,
48381a2a9aSdr  * lists, simple queues, tail queues, and circular queues.
49381a2a9aSdr  *
50381a2a9aSdr  * A singly-linked list is headed by a single forward pointer. The
51381a2a9aSdr  * elements are singly linked for minimum space and pointer manipulation
52381a2a9aSdr  * overhead at the expense of O(n) removal for arbitrary elements. New
53381a2a9aSdr  * elements can be added to the list after an existing element or at the
54381a2a9aSdr  * head of the list.  Elements being removed from the head of the list
55381a2a9aSdr  * should use the explicit macro for this purpose for optimum
56381a2a9aSdr  * efficiency. A singly-linked list may only be traversed in the forward
57381a2a9aSdr  * direction.  Singly-linked lists are ideal for applications with large
58381a2a9aSdr  * datasets and few or no removals or for implementing a LIFO queue.
59381a2a9aSdr  *
60381a2a9aSdr  * A list is headed by a single forward pointer (or an array of forward
61381a2a9aSdr  * pointers for a hash table header). The elements are doubly linked
62381a2a9aSdr  * so that an arbitrary element can be removed without a need to
63381a2a9aSdr  * traverse the list. New elements can be added to the list before
64381a2a9aSdr  * or after an existing element or at the head of the list. A list
65381a2a9aSdr  * may only be traversed in the forward direction.
66381a2a9aSdr  *
67381a2a9aSdr  * A simple queue is headed by a pair of pointers, one the head of the
68381a2a9aSdr  * list and the other to the tail of the list. The elements are singly
69381a2a9aSdr  * linked to save space, so elements can only be removed from the
70381a2a9aSdr  * head of the list. New elements can be added to the list after
71381a2a9aSdr  * an existing element, at the head of the list, or at the end of the
72381a2a9aSdr  * list. A simple queue may only be traversed in the forward direction.
73381a2a9aSdr  *
74381a2a9aSdr  * A tail queue is headed by a pair of pointers, one to the head of the
75381a2a9aSdr  * list and the other to the tail of the list. The elements are doubly
76381a2a9aSdr  * linked so that an arbitrary element can be removed without a need to
77381a2a9aSdr  * traverse the list. New elements can be added to the list before or
78381a2a9aSdr  * after an existing element, at the head of the list, or at the end of
79381a2a9aSdr  * the list. A tail queue may be traversed in either direction.
80381a2a9aSdr  *
81381a2a9aSdr  * A circle queue is headed by a pair of pointers, one to the head of the
82381a2a9aSdr  * list and the other to the tail of the list. The elements are doubly
83381a2a9aSdr  * linked so that an arbitrary element can be removed without a need to
84381a2a9aSdr  * traverse the list. New elements can be added to the list before or after
85381a2a9aSdr  * an existing element, at the head of the list, or at the end of the list.
86381a2a9aSdr  * A circle queue may be traversed in either direction, but has a more
87381a2a9aSdr  * complex end of list detection.
88381a2a9aSdr  *
89*85280f08SToomas Soome  * For details on the use of these macros, see the queue.h(3HEAD) manual page.
90381a2a9aSdr  */
91381a2a9aSdr 
92*85280f08SToomas Soome #ifdef QUEUE_MACRO_DEBUG
93*85280f08SToomas Soome #warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH
94*85280f08SToomas Soome #define	QUEUE_MACRO_DEBUG_TRACE
95*85280f08SToomas Soome #define	QUEUE_MACRO_DEBUG_TRASH
96381a2a9aSdr #endif
97381a2a9aSdr 
98*85280f08SToomas Soome #ifdef QUEUE_MACRO_DEBUG_TRACE
99*85280f08SToomas Soome /* Store the last 2 places the queue element or head was altered */
100*85280f08SToomas Soome struct qm_trace {
101*85280f08SToomas Soome 	unsigned long	lastline;
102*85280f08SToomas Soome 	unsigned long	prevline;
103*85280f08SToomas Soome 	const char	*lastfile;
104*85280f08SToomas Soome 	const char	*prevfile;
105*85280f08SToomas Soome };
106*85280f08SToomas Soome 
107*85280f08SToomas Soome #define	TRACEBUF	struct qm_trace trace;
108*85280f08SToomas Soome #define	TRACEBUF_INITIALIZER	{ __LINE__, 0, __FILE__, NULL },
109*85280f08SToomas Soome 
110*85280f08SToomas Soome #define	QMD_TRACE_HEAD(head) do {					\
111*85280f08SToomas Soome 	(head)->trace.prevline = (head)->trace.lastline;		\
112*85280f08SToomas Soome 	(head)->trace.prevfile = (head)->trace.lastfile;		\
113*85280f08SToomas Soome 	(head)->trace.lastline = __LINE__;				\
114*85280f08SToomas Soome 	(head)->trace.lastfile = __FILE__;				\
115381a2a9aSdr 	_NOTE(CONSTCOND)						\
116381a2a9aSdr } while (0)
117381a2a9aSdr 
118*85280f08SToomas Soome #define	QMD_TRACE_ELEM(elem) do {					\
119*85280f08SToomas Soome 	(elem)->trace.prevline = (elem)->trace.lastline;		\
120*85280f08SToomas Soome 	(elem)->trace.prevfile = (elem)->trace.lastfile;		\
121*85280f08SToomas Soome 	(elem)->trace.lastline = __LINE__;				\
122*85280f08SToomas Soome 	(elem)->trace.lastfile = __FILE__;				\
123381a2a9aSdr 	_NOTE(CONSTCOND)						\
124381a2a9aSdr } while (0)
125381a2a9aSdr 
126*85280f08SToomas Soome #else	/* !QUEUE_MACRO_DEBUG_TRACE */
127*85280f08SToomas Soome #define	QMD_TRACE_ELEM(elem)
128*85280f08SToomas Soome #define	QMD_TRACE_HEAD(head)
129*85280f08SToomas Soome #define	TRACEBUF
130*85280f08SToomas Soome #define	TRACEBUF_INITIALIZER
131*85280f08SToomas Soome #endif	/* QUEUE_MACRO_DEBUG_TRACE */
132*85280f08SToomas Soome 
133*85280f08SToomas Soome #ifdef QUEUE_MACRO_DEBUG_TRASH
134*85280f08SToomas Soome #define	TRASHIT(x)		do {(x) = (void *)-1; } while (0)
135*85280f08SToomas Soome #define	QMD_IS_TRASHED(x)	((x) == (void *)(intptr_t)-1)
136*85280f08SToomas Soome #else	/* !QUEUE_MACRO_DEBUG_TRASH */
137*85280f08SToomas Soome #define	TRASHIT(x)
138*85280f08SToomas Soome #define	QMD_IS_TRASHED(x)	0
139*85280f08SToomas Soome #endif	/* QUEUE_MACRO_DEBUG_TRASH */
140*85280f08SToomas Soome 
141*85280f08SToomas Soome #if defined(QUEUE_MACRO_DEBUG_TRACE) || defined(QUEUE_MACRO_DEBUG_TRASH)
142*85280f08SToomas Soome #define	QMD_SAVELINK(name, link)	void **name = (void *)&(link)
143*85280f08SToomas Soome #else	/* !QUEUE_MACRO_DEBUG_TRACE && !QUEUE_MACRO_DEBUG_TRASH */
144*85280f08SToomas Soome #define	QMD_SAVELINK(name, link)
145*85280f08SToomas Soome #endif	/* QUEUE_MACRO_DEBUG_TRACE || QUEUE_MACRO_DEBUG_TRASH */
146*85280f08SToomas Soome 
147*85280f08SToomas Soome #ifdef __cplusplus
148381a2a9aSdr /*
149*85280f08SToomas Soome  * In C++ there can be structure lists and class lists:
150381a2a9aSdr  */
151*85280f08SToomas Soome #define	QUEUE_TYPEOF(type) type
152*85280f08SToomas Soome #else
153*85280f08SToomas Soome #define	QUEUE_TYPEOF(type) struct type
154*85280f08SToomas Soome #endif
155381a2a9aSdr 
156381a2a9aSdr /*
157381a2a9aSdr  * Singly-linked List definitions.
158381a2a9aSdr  */
159381a2a9aSdr #define	SLIST_HEAD(name, type)						\
160381a2a9aSdr struct name {								\
161381a2a9aSdr 	struct type *slh_first;	/* first element */			\
162381a2a9aSdr }
163381a2a9aSdr 
164*85280f08SToomas Soome #define	SLIST_CLASS_HEAD(name, type)					\
165*85280f08SToomas Soome struct name {								\
166*85280f08SToomas Soome 	class type *slh_first;	/* first element */			\
167*85280f08SToomas Soome }
168*85280f08SToomas Soome 
169381a2a9aSdr #define	SLIST_HEAD_INITIALIZER(head)					\
170381a2a9aSdr 	{ NULL }
171381a2a9aSdr 
172381a2a9aSdr #define	SLIST_ENTRY(type)						\
173381a2a9aSdr struct {								\
174381a2a9aSdr 	struct type *sle_next;	/* next element */			\
175381a2a9aSdr }
176381a2a9aSdr 
177*85280f08SToomas Soome #define	SLIST_CLASS_ENTRY(type)						\
178*85280f08SToomas Soome struct {								\
179*85280f08SToomas Soome 	class type *sle_next;		/* next element */		\
180*85280f08SToomas Soome }
181*85280f08SToomas Soome 
182*85280f08SToomas Soome /*
183*85280f08SToomas Soome  * Singly-linked List access methods.
184*85280f08SToomas Soome  */
185*85280f08SToomas Soome #define	SLIST_FIRST(head)	((head)->slh_first)
186*85280f08SToomas Soome #define	SLIST_END(head)		NULL
187*85280f08SToomas Soome #define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
188*85280f08SToomas Soome #define	SLIST_EMPTY(head)	((head)->slh_first == SLIST_END(head))
189*85280f08SToomas Soome 
190*85280f08SToomas Soome #define	SLIST_FOREACH(var, head, field)					\
191*85280f08SToomas Soome 	for ((var) = SLIST_FIRST((head));				\
192*85280f08SToomas Soome 		(var) != SLIST_END(head);				\
193*85280f08SToomas Soome 		(var) = SLIST_NEXT((var), field))
194*85280f08SToomas Soome 
195*85280f08SToomas Soome #define	SLIST_FOREACH_FROM(var, head, field)				\
196*85280f08SToomas Soome 	for ((var) = ((var) != SLIST_END(head) ? (var) : SLIST_FIRST((head))); \
197*85280f08SToomas Soome 		(var) != SLIST_END(head);				\
198*85280f08SToomas Soome 		(var) = SLIST_NEXT((var), field))
199*85280f08SToomas Soome 
200*85280f08SToomas Soome #define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
201*85280f08SToomas Soome 	for ((var) = SLIST_FIRST((head));				\
202*85280f08SToomas Soome 		(var) != SLIST_END(head) &&				\
203*85280f08SToomas Soome 		((tvar) = SLIST_NEXT((var), field), 1);			\
204*85280f08SToomas Soome 		(var) = (tvar))
205*85280f08SToomas Soome 
206*85280f08SToomas Soome #define	SLIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
207*85280f08SToomas Soome 	for ((var) = ((var) != SLIST_END(head) ? (var) : SLIST_FIRST((head))); \
208*85280f08SToomas Soome 		(var) != SLIST_END(head) &&				\
209*85280f08SToomas Soome 		((tvar) = SLIST_NEXT((var), field), 1);			\
210*85280f08SToomas Soome 		(var) = (tvar))
211*85280f08SToomas Soome 
212381a2a9aSdr /*
213381a2a9aSdr  * Singly-linked List functions.
214381a2a9aSdr  */
215381a2a9aSdr #define	SLIST_INIT(head) do {						\
216*85280f08SToomas Soome 	(head)->slh_first = SLIST_END(head);				\
217*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
218*85280f08SToomas Soome } while (0)
219*85280f08SToomas Soome 
220*85280f08SToomas Soome #define	SLIST_CONCAT(head1, head2, type, field) do {			\
221*85280f08SToomas Soome 	QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1);		\
222*85280f08SToomas Soome 	if (curelm == SLIST_END(head1)) {				\
223*85280f08SToomas Soome 		if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) !=	\
224*85280f08SToomas Soome 		    SLIST_END(head1))					\
225*85280f08SToomas Soome 			SLIST_INIT(head2);				\
226*85280f08SToomas Soome 	} else if (SLIST_FIRST(head2) != SLIST_END(head2)) {		\
227*85280f08SToomas Soome 		while (SLIST_NEXT(curelm, field) != SLIST_END(head1))	\
228*85280f08SToomas Soome 			curelm = SLIST_NEXT(curelm, field);		\
229*85280f08SToomas Soome 		SLIST_NEXT(curelm, field) = SLIST_FIRST(head2);		\
230*85280f08SToomas Soome 		SLIST_INIT(head2);					\
231*85280f08SToomas Soome 	}								\
232381a2a9aSdr 	_NOTE(CONSTCOND)						\
233381a2a9aSdr } while (0)
234381a2a9aSdr 
235381a2a9aSdr #define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
236*85280f08SToomas Soome 	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);	\
237*85280f08SToomas Soome 	SLIST_NEXT((slistelm), field) = (elm);				\
238381a2a9aSdr 	_NOTE(CONSTCOND)						\
239381a2a9aSdr } while (0)
240381a2a9aSdr 
241381a2a9aSdr #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
242*85280f08SToomas Soome 	SLIST_NEXT((elm), field) = SLIST_FIRST((head));			\
243*85280f08SToomas Soome 	SLIST_FIRST((head)) = (elm);					\
244381a2a9aSdr 	_NOTE(CONSTCOND)						\
245381a2a9aSdr } while (0)
246381a2a9aSdr 
247381a2a9aSdr #define	SLIST_REMOVE_HEAD(head, field) do {				\
248*85280f08SToomas Soome 	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
249*85280f08SToomas Soome 	_NOTE(CONSTCOND)						\
250*85280f08SToomas Soome } while (0)
251*85280f08SToomas Soome 
252*85280f08SToomas Soome #define	SLIST_REMOVE_AFTER(slistelm, field) do {			\
253*85280f08SToomas Soome 	SLIST_NEXT((slistelm), field) =					\
254*85280f08SToomas Soome 	    SLIST_NEXT(SLIST_NEXT((slistelm), field), field);		\
255381a2a9aSdr 	_NOTE(CONSTCOND)						\
256381a2a9aSdr } while (0)
257381a2a9aSdr 
258381a2a9aSdr #define	SLIST_REMOVE(head, elm, type, field) do {			\
259*85280f08SToomas Soome 	QMD_SAVELINK(oldnext, SLIST_NEXT((elm), field));		\
260*85280f08SToomas Soome 	if (SLIST_FIRST((head)) == (elm)) {				\
261381a2a9aSdr 		SLIST_REMOVE_HEAD((head), field);			\
262381a2a9aSdr 	}								\
263381a2a9aSdr 	else {								\
264*85280f08SToomas Soome 		QUEUE_TYPEOF(type) *curelm = SLIST_FIRST((head));	\
265*85280f08SToomas Soome 		while (SLIST_NEXT(curelm, field) != (elm))		\
266*85280f08SToomas Soome 			curelm = SLIST_NEXT(curelm, field);		\
267*85280f08SToomas Soome 		SLIST_REMOVE_AFTER(curelm, field);			\
268381a2a9aSdr 	}								\
269*85280f08SToomas Soome 	TRASHIT(*oldnext);						\
270381a2a9aSdr 	_NOTE(CONSTCOND)						\
271381a2a9aSdr } while (0)
272381a2a9aSdr 
273*85280f08SToomas Soome #define	SLIST_SWAP(head1, head2, type) do {				\
274*85280f08SToomas Soome 	QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1);		\
275*85280f08SToomas Soome 	SLIST_FIRST(head1) = SLIST_FIRST(head2);			\
276*85280f08SToomas Soome 	SLIST_FIRST(head2) = swap_first;				\
277*85280f08SToomas Soome } while (0)
278381a2a9aSdr 
279381a2a9aSdr /*
280381a2a9aSdr  * Singly-linked Tail queue declarations.
281381a2a9aSdr  */
282381a2a9aSdr #define	STAILQ_HEAD(name, type)						\
283381a2a9aSdr struct name {								\
284381a2a9aSdr 	struct type *stqh_first;	/* first element */		\
285381a2a9aSdr 	struct type **stqh_last;	/* addr of last next element */	\
286381a2a9aSdr }
287381a2a9aSdr 
288*85280f08SToomas Soome #define	STAILQ_CLASS_HEAD(name, type)					\
289*85280f08SToomas Soome struct name {								\
290*85280f08SToomas Soome 	class type *stqh_first;	/* first element */			\
291*85280f08SToomas Soome 	class type **stqh_last;	/* addr of last next element */		\
292*85280f08SToomas Soome }
293*85280f08SToomas Soome 
294381a2a9aSdr #define	STAILQ_HEAD_INITIALIZER(head)					\
295381a2a9aSdr 	{ NULL, &(head).stqh_first }
296381a2a9aSdr 
297381a2a9aSdr #define	STAILQ_ENTRY(type)						\
298381a2a9aSdr struct {								\
299*85280f08SToomas Soome 	struct type *stqe_next;	/* next element */			\
300381a2a9aSdr }
301381a2a9aSdr 
302*85280f08SToomas Soome #define	STAILQ_CLASS_ENTRY(type)					\
303*85280f08SToomas Soome struct {								\
304*85280f08SToomas Soome 	class type *stqe_next;	/* next element */			\
305*85280f08SToomas Soome }
306*85280f08SToomas Soome 
307*85280f08SToomas Soome /*
308*85280f08SToomas Soome  * Singly-linked Tail queue access methods.
309*85280f08SToomas Soome  */
310*85280f08SToomas Soome #define	STAILQ_FIRST(head)	((head)->stqh_first)
311*85280f08SToomas Soome #define	STAILQ_END(head)	NULL
312*85280f08SToomas Soome #define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
313*85280f08SToomas Soome #define	STAILQ_EMPTY(head)	((head)->stqh_first == STAILQ_END(head))
314*85280f08SToomas Soome 
315*85280f08SToomas Soome #define	STAILQ_FOREACH(var, head, field)				\
316*85280f08SToomas Soome 	for ((var) = STAILQ_FIRST(head);				\
317*85280f08SToomas Soome 	    (var) != STAILQ_END(head);					\
318*85280f08SToomas Soome 	    (var) = STAILQ_NEXT((var), field))
319*85280f08SToomas Soome 
320*85280f08SToomas Soome #define	STAILQ_FOREACH_FROM(var, head, field)				\
321*85280f08SToomas Soome 	for ((var) =							\
322*85280f08SToomas Soome 	    ((var) != STAILQ_END(head) ? (var) : STAILQ_FIRST((head))); \
323*85280f08SToomas Soome 	    (var) != STAILQ_END(head);					\
324*85280f08SToomas Soome 	    (var) = STAILQ_NEXT((var), field))
325*85280f08SToomas Soome 
326*85280f08SToomas Soome #define	STAILQ_FOREACH_SAFE(var, head, field, tvar)			\
327*85280f08SToomas Soome 	for ((var) = STAILQ_FIRST(head);				\
328*85280f08SToomas Soome 	    (var) != STAILQ_END(head) &&				\
329*85280f08SToomas Soome 	    ((tvar) = STAILQ_NEXT((var), field), 1);			\
330*85280f08SToomas Soome 	    (var) = (tvar))
331*85280f08SToomas Soome 
332*85280f08SToomas Soome #define	STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)		\
333*85280f08SToomas Soome 	for ((var) =							\
334*85280f08SToomas Soome 	    ((var) != STAILQ_END(head) ? (var) : STAILQ_FIRST((head))); \
335*85280f08SToomas Soome 	    (var) != STAILQ_END(head) &&				\
336