xref: /illumos-gate/usr/src/uts/common/sys/queue.h (revision 85280f08e3cfa2e404951ad6817bbb974b576858)
1 /*
2  * Copyright (c) 1991, 1993
3  *	The Regents of the University of California.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  * 3. Neither the name of the University nor the names of its contributors
14  *    may be used to endorse or promote products derived from this software
15  *    without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  *
29  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
30  */
31 /*
32  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
33  * Use is subject to license terms.
34  */
35 
36 #ifndef	_SYS_QUEUE_H
37 #define	_SYS_QUEUE_H
38 
39 #include <sys/note.h>
40 #include <sys/containerof.h>
41 
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45 
46 /*
47  * This file defines five types of data structures: singly-linked lists,
48  * lists, simple queues, tail queues, and circular queues.
49  *
50  * A singly-linked list is headed by a single forward pointer. The
51  * elements are singly linked for minimum space and pointer manipulation
52  * overhead at the expense of O(n) removal for arbitrary elements. New
53  * elements can be added to the list after an existing element or at the
54  * head of the list.  Elements being removed from the head of the list
55  * should use the explicit macro for this purpose for optimum
56  * efficiency. A singly-linked list may only be traversed in the forward
57  * direction.  Singly-linked lists are ideal for applications with large
58  * datasets and few or no removals or for implementing a LIFO queue.
59  *
60  * A list is headed by a single forward pointer (or an array of forward
61  * pointers for a hash table header). The elements are doubly linked
62  * so that an arbitrary element can be removed without a need to
63  * traverse the list. New elements can be added to the list before
64  * or after an existing element or at the head of the list. A list
65  * may only be traversed in the forward direction.
66  *
67  * A simple queue is headed by a pair of pointers, one the head of the
68  * list and the other to the tail of the list. The elements are singly
69  * linked to save space, so elements can only be removed from the
70  * head of the list. New elements can be added to the list after
71  * an existing element, at the head of the list, or at the end of the
72  * list. A simple queue may only be traversed in the forward direction.
73  *
74  * A tail queue is headed by a pair of pointers, one to the head of the
75  * list and the other to the tail of the list. The elements are doubly
76  * linked so that an arbitrary element can be removed without a need to
77  * traverse the list. New elements can be added to the list before or
78  * after an existing element, at the head of the list, or at the end of
79  * the list. A tail queue may be traversed in either direction.
80  *
81  * A circle queue is headed by a pair of pointers, one to the head of the
82  * list and the other to the tail of the list. The elements are doubly
83  * linked so that an arbitrary element can be removed without a need to
84  * traverse the list. New elements can be added to the list before or after
85  * an existing element, at the head of the list, or at the end of the list.
86  * A circle queue may be traversed in either direction, but has a more
87  * complex end of list detection.
88  *
89  * For details on the use of these macros, see the queue.h(3HEAD) manual page.
90  */
91 
92 #ifdef QUEUE_MACRO_DEBUG
93 #warn Use QUEUE_MACRO_DEBUG_TRACE and/or QUEUE_MACRO_DEBUG_TRASH
94 #define	QUEUE_MACRO_DEBUG_TRACE
95 #define	QUEUE_MACRO_DEBUG_TRASH
96 #endif
97 
98 #ifdef QUEUE_MACRO_DEBUG_TRACE
99 /* Store the last 2 places the queue element or head was altered */
100 struct qm_trace {
101 	unsigned long	lastline;
102 	unsigned long	prevline;
103 	const char	*lastfile;
104 	const char	*prevfile;
105 };
106 
107 #define	TRACEBUF	struct qm_trace trace;
108 #define	TRACEBUF_INITIALIZER	{ __LINE__, 0, __FILE__, NULL },
109 
110 #define	QMD_TRACE_HEAD(head) do {					\
111 	(head)->trace.prevline = (head)->trace.lastline;		\
112 	(head)->trace.prevfile = (head)->trace.lastfile;		\
113 	(head)->trace.lastline = __LINE__;				\
114 	(head)->trace.lastfile = __FILE__;				\
115 	_NOTE(CONSTCOND)						\
116 } while (0)
117 
118 #define	QMD_TRACE_ELEM(elem) do {					\
119 	(elem)->trace.prevline = (elem)->trace.lastline;		\
120 	(elem)->trace.prevfile = (elem)->trace.lastfile;		\
121 	(elem)->trace.lastline = __LINE__;				\
122 	(elem)->trace.lastfile = __FILE__;				\
123 	_NOTE(CONSTCOND)						\
124 } while (0)
125 
126 #else	/* !QUEUE_MACRO_DEBUG_TRACE */
127 #define	QMD_TRACE_ELEM(elem)
128 #define	QMD_TRACE_HEAD(head)
129 #define	TRACEBUF
130 #define	TRACEBUF_INITIALIZER
131 #endif	/* QUEUE_MACRO_DEBUG_TRACE */
132 
133 #ifdef QUEUE_MACRO_DEBUG_TRASH
134 #define	TRASHIT(x)		do {(x) = (void *)-1; } while (0)
135 #define	QMD_IS_TRASHED(x)	((x) == (void *)(intptr_t)-1)
136 #else	/* !QUEUE_MACRO_DEBUG_TRASH */
137 #define	TRASHIT(x)
138 #define	QMD_IS_TRASHED(x)	0
139 #endif	/* QUEUE_MACRO_DEBUG_TRASH */
140 
141 #if defined(QUEUE_MACRO_DEBUG_TRACE) || defined(QUEUE_MACRO_DEBUG_TRASH)
142 #define	QMD_SAVELINK(name, link)	void **name = (void *)&(link)
143 #else	/* !QUEUE_MACRO_DEBUG_TRACE && !QUEUE_MACRO_DEBUG_TRASH */
144 #define	QMD_SAVELINK(name, link)
145 #endif	/* QUEUE_MACRO_DEBUG_TRACE || QUEUE_MACRO_DEBUG_TRASH */
146 
147 #ifdef __cplusplus
148 /*
149  * In C++ there can be structure lists and class lists:
150  */
151 #define	QUEUE_TYPEOF(type) type
152 #else
153 #define	QUEUE_TYPEOF(type) struct type
154 #endif
155 
156 /*
157  * Singly-linked List definitions.
158  */
159 #define	SLIST_HEAD(name, type)						\
160 struct name {								\
161 	struct type *slh_first;	/* first element */			\
162 }
163 
164 #define	SLIST_CLASS_HEAD(name, type)					\
165 struct name {								\
166 	class type *slh_first;	/* first element */			\
167 }
168 
169 #define	SLIST_HEAD_INITIALIZER(head)					\
170 	{ NULL }
171 
172 #define	SLIST_ENTRY(type)						\
173 struct {								\
174 	struct type *sle_next;	/* next element */			\
175 }
176 
177 #define	SLIST_CLASS_ENTRY(type)						\
178 struct {								\
179 	class type *sle_next;		/* next element */		\
180 }
181 
182 /*
183  * Singly-linked List access methods.
184  */
185 #define	SLIST_FIRST(head)	((head)->slh_first)
186 #define	SLIST_END(head)		NULL
187 #define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
188 #define	SLIST_EMPTY(head)	((head)->slh_first == SLIST_END(head))
189 
190 #define	SLIST_FOREACH(var, head, field)					\
191 	for ((var) = SLIST_FIRST((head));				\
192 		(var) != SLIST_END(head);				\
193 		(var) = SLIST_NEXT((var), field))
194 
195 #define	SLIST_FOREACH_FROM(var, head, field)				\
196 	for ((var) = ((var) != SLIST_END(head) ? (var) : SLIST_FIRST((head))); \
197 		(var) != SLIST_END(head);				\
198 		(var) = SLIST_NEXT((var), field))
199 
200 #define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
201 	for ((var) = SLIST_FIRST((head));				\
202 		(var) != SLIST_END(head) &&				\
203 		((tvar) = SLIST_NEXT((var), field), 1);			\
204 		(var) = (tvar))
205 
206 #define	SLIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
207 	for ((var) = ((var) != SLIST_END(head) ? (var) : SLIST_FIRST((head))); \
208 		(var) != SLIST_END(head) &&				\
209 		((tvar) = SLIST_NEXT((var), field), 1);			\
210 		(var) = (tvar))
211 
212 /*
213  * Singly-linked List functions.
214  */
215 #define	SLIST_INIT(head) do {						\
216 	(head)->slh_first = SLIST_END(head);				\
217 	_NOTE(CONSTCOND)						\
218 } while (0)
219 
220 #define	SLIST_CONCAT(head1, head2, type, field) do {			\
221 	QUEUE_TYPEOF(type) *curelm = SLIST_FIRST(head1);		\
222 	if (curelm == SLIST_END(head1)) {				\
223 		if ((SLIST_FIRST(head1) = SLIST_FIRST(head2)) !=	\
224 		    SLIST_END(head1))					\
225 			SLIST_INIT(head2);				\
226 	} else if (SLIST_FIRST(head2) != SLIST_END(head2)) {		\
227 		while (SLIST_NEXT(curelm, field) != SLIST_END(head1))	\
228 			curelm = SLIST_NEXT(curelm, field);		\
229 		SLIST_NEXT(curelm, field) = SLIST_FIRST(head2);		\
230 		SLIST_INIT(head2);					\
231 	}								\
232 	_NOTE(CONSTCOND)						\
233 } while (0)
234 
235 #define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
236 	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);	\
237 	SLIST_NEXT((slistelm), field) = (elm);				\
238 	_NOTE(CONSTCOND)						\
239 } while (0)
240 
241 #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
242 	SLIST_NEXT((elm), field) = SLIST_FIRST((head));			\
243 	SLIST_FIRST((head)) = (elm);					\
244 	_NOTE(CONSTCOND)						\
245 } while (0)
246 
247 #define	SLIST_REMOVE_HEAD(head, field) do {				\
248 	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
249 	_NOTE(CONSTCOND)						\
250 } while (0)
251 
252 #define	SLIST_REMOVE_AFTER(slistelm, field) do {			\
253 	SLIST_NEXT((slistelm), field) =					\
254 	    SLIST_NEXT(SLIST_NEXT((slistelm), field), field);		\
255 	_NOTE(CONSTCOND)						\
256 } while (0)
257 
258 #define	SLIST_REMOVE(head, elm, type, field) do {			\
259 	QMD_SAVELINK(oldnext, SLIST_NEXT((elm), field));		\
260 	if (SLIST_FIRST((head)) == (elm)) {				\
261 		SLIST_REMOVE_HEAD((head), field);			\
262 	}								\
263 	else {								\
264 		QUEUE_TYPEOF(type) *curelm = SLIST_FIRST((head));	\
265 		while (SLIST_NEXT(curelm, field) != (elm))		\
266 			curelm = SLIST_NEXT(curelm, field);		\
267 		SLIST_REMOVE_AFTER(curelm, field);			\
268 	}								\
269 	TRASHIT(*oldnext);						\
270 	_NOTE(CONSTCOND)						\
271 } while (0)
272 
273 #define	SLIST_SWAP(head1, head2, type) do {				\
274 	QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1);		\
275 	SLIST_FIRST(head1) = SLIST_FIRST(head2);			\
276 	SLIST_FIRST(head2) = swap_first;				\
277 } while (0)
278 
279 /*
280  * Singly-linked Tail queue declarations.
281  */
282 #define	STAILQ_HEAD(name, type)						\
283 struct name {								\
284 	struct type *stqh_first;	/* first element */		\
285 	struct type **stqh_last;	/* addr of last next element */	\
286 }
287 
288 #define	STAILQ_CLASS_HEAD(name, type)					\
289 struct name {								\
290 	class type *stqh_first;	/* first element */			\
291 	class type **stqh_last;	/* addr of last next element */		\
292 }
293 
294 #define	STAILQ_HEAD_INITIALIZER(head)					\
295 	{ NULL, &(head).stqh_first }
296 
297 #define	STAILQ_ENTRY(type)						\
298 struct {								\
299 	struct type *stqe_next;	/* next element */			\
300 }
301 
302 #define	STAILQ_CLASS_ENTRY(type)					\
303 struct {								\
304 	class type *stqe_next;	/* next element */			\
305 }
306 
307 /*
308  * Singly-linked Tail queue access methods.
309  */
310 #define	STAILQ_FIRST(head)	((head)->stqh_first)
311 #define	STAILQ_END(head)	NULL
312 #define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
313 #define	STAILQ_EMPTY(head)	((head)->stqh_first == STAILQ_END(head))
314 
315 #define	STAILQ_FOREACH(var, head, field)				\
316 	for ((var) = STAILQ_FIRST(head);				\
317 	    (var) != STAILQ_END(head);					\
318 	    (var) = STAILQ_NEXT((var), field))
319 
320 #define	STAILQ_FOREACH_FROM(var, head, field)				\
321 	for ((var) =							\
322 	    ((var) != STAILQ_END(head) ? (var) : STAILQ_FIRST((head))); \
323 	    (var) != STAILQ_END(head);					\
324 	    (var) = STAILQ_NEXT((var), field))
325 
326 #define	STAILQ_FOREACH_SAFE(var, head, field, tvar)			\
327 	for ((var) = STAILQ_FIRST(head);				\
328 	    (var) != STAILQ_END(head) &&				\
329 	    ((tvar) = STAILQ_NEXT((var), field), 1);			\
330 	    (var) = (tvar))
331 
332 #define	STAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)		\
333 	for ((var) =							\
334 	    ((var) != STAILQ_END(head) ? (var) : STAILQ_FIRST((head))); \
335 	    (var) != STAILQ_END(head) &&				\
336 	    ((tvar) = STAILQ_NEXT((var), field), 1);			\
337 	    (var) = (tvar))
338 
339 /*
340  * Singly-linked Tail queue functions.
341  */
342 #define	STAILQ_INIT(head) do {						\
343 	STAILQ_FIRST(head) = STAILQ_END(head);				\
344 	(head)->stqh_last = &STAILQ_FIRST((head));			\
345 	_NOTE(CONSTCOND)						\
346 } while (0)
347 
348 #define	STAILQ_CONCAT(head1, head2) do {				\
349 	if (!STAILQ_EMPTY((head2))) {					\
350 		*(head1)->stqh_last = STAILQ_FIRST((head2));		\
351 		(head1)->stqh_last = (head2)->stqh_last;		\
352 		STAILQ_INIT((head2));					\
353 	}								\
354 	_NOTE(CONSTCOND)						\
355 } while (0)
356 
357 #define	STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\
358 	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
359 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
360 	STAILQ_NEXT((tqelm), field) = (elm);				\
361 	_NOTE(CONSTCOND)						\
362 } while (0)
363 
364 #define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
365 	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)	\
366 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
367 	STAILQ_FIRST((head)) = (elm);					\
368 	_NOTE(CONSTCOND)						\
369 } while (0)
370 
371 #define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
372 	STAILQ_NEXT((elm), field) = NULL;				\
373 	*(head)->stqh_last = (elm);					\
374 	(head)->stqh_last = &STAILQ_NEXT((elm), field);			\
375 	_NOTE(CONSTCOND)						\
376 } while (0)
377 
378 #define	STAILQ_LAST(head, type, field)					\
379 	(STAILQ_EMPTY((head)) ? NULL :					\
380 	    __containerof((head)->stqh_last,				\
381 	    QUEUE_TYPEOF(type), field.stqe_next))
382 
383 #define	STAILQ_REMOVE_HEAD(head, field) do {				\
384 	if ((STAILQ_FIRST((head)) =					\
385 	    STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)		\
386 		(head)->stqh_last = &STAILQ_FIRST((head));		\
387 	_NOTE(CONSTCOND)						\
388 } while (0)
389 
390 #define	STAILQ_REMOVE_AFTER(head, elm, field) do {			\
391 	if ((STAILQ_NEXT(elm, field) =					\
392 	    STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)	\
393 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
394 	_NOTE(CONSTCOND)						\
395 } while (0)
396 
397 #define	STAILQ_REMOVE(head, elm, type, field) do {			\
398 	QMD_SAVELINK(oldnext, (elm)->field.stqe_next);			\
399 	if (STAILQ_FIRST((head)) == (elm)) {				\
400 		STAILQ_REMOVE_HEAD((head), field);			\
401 	} else {							\
402 		QUEUE_TYPEOF(type) *curelm = STAILQ_FIRST(head);	\
403 		while (STAILQ_NEXT(curelm, field) != (elm))		\
404 			curelm = STAILQ_NEXT(curelm, field);		\
405 		STAILQ_REMOVE_AFTER(head, curelm, field);		\
406 	}								\
407 	TRASHIT(*oldnext);						\
408 	_NOTE(CONSTCOND)						\
409 } while (0)
410 
411 #define	STAILQ_SWAP(head1, head2, type) do {				\
412 	QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1);		\
413 	QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last;		\
414 	STAILQ_FIRST(head1) = STAILQ_FIRST(head2);			\
415 	(head1)->stqh_last = (head2)->stqh_last;			\
416 	STAILQ_FIRST(head2) = swap_first;				\
417 	(head2)->stqh_last = swap_last;					\
418 	if (STAILQ_EMPTY(head1))					\
419 		(head1)->stqh_last = &STAILQ_FIRST(head1);		\
420 	if (STAILQ_EMPTY(head2))					\
421 		(head2)->stqh_last = &STAILQ_FIRST(head2);		\
422 	_NOTE(CONSTCOND)						\
423 } while (0)
424 
425 /*
426  * List definitions.
427  */
428 #define	LIST_HEAD(name, type)						\
429 struct name {								\
430 	struct type *lh_first;	/* first element */			\
431 }
432 
433 #define	LIST_CLASS_HEAD(name, type)					\
434 struct name {								\
435 	class type *lh_first;	/* first element */			\
436 }
437 
438 #define	LIST_HEAD_INITIALIZER(head)					\
439 	{ NULL }
440 
441 #define	LIST_ENTRY(type)						\
442 struct {								\
443 	struct type *le_next;	/* next element */			\
444 	struct type **le_prev;	/* address of previous next element */	\
445 }
446 
447 #define	LIST_CLASS_ENTRY(type)						\
448 struct {								\
449 	class type *le_next;	/* next element */			\
450 	class type **le_prev;	/* address of previous next element */	\
451 }
452 
453 /*
454  * List access methods.
455  */
456 #define	LIST_FIRST(head)		((head)->lh_first)
457 #define	LIST_END(head)			NULL
458 #define	LIST_EMPTY(head)		((head)->lh_first == LIST_END(head))
459 #define	LIST_NEXT(elm, field)		((elm)->field.le_next)
460 #define	LIST_PREV(elm, head, type, field)				\
461 	((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL :		\
462 	__containerof((elm)->field.le_prev, type, field.le_next))
463 
464 #define	LIST_FOREACH(var, head, field)					\
465 	for ((var) = LIST_FIRST((head));				\
466 	    (var) != LIST_END(head);					\
467 	    (var) = LIST_NEXT((var), field))
468 
469 #define	LIST_FOREACH_FROM(var, head, field)				\
470 	for ((var) = ((var) != LIST_END(head) ? (var) : LIST_FIRST((head));\
471 	    (var) != LIST_END(head);					\
472 	    (var) = LIST_NEXT((var), field))
473 
474 #define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
475 	for ((var) = LIST_FIRST((head));				\
476 	    (var) != LIST_END(head) &&				\
477 	    ((tvar) = LIST_NEXT((var), field), 1);			\
478 	    (var) = (tvar))
479 
480 #define	LIST_FOREACH_FROM_SAFE(var, head, field, tvar)			\
481 	for ((var) = ((var) != LIST_END(head) ? (var) : LIST_FIRST((head));\
482 	    (var) != LIST_END(head) &&				\
483 	    ((tvar) = LIST_NEXT((var), field), 1);			\
484 	    (var) = (tvar))
485 
486 /*
487  * List functions.
488  */
489 #if defined(_KERNEL) && defined(QUEUEDEBUG)
490 #define	QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)			\
491 	if ((head)->lh_first &&						\
492 	    (head)->lh_first->field.le_prev != &(head)->lh_first)	\
493 		panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
494 #define	QUEUEDEBUG_LIST_OP(elm, field)					\
495 	if ((elm)->field.le_next &&					\
496 	    (elm)->field.le_next->field.le_prev !=			\
497 	    &(elm)->field.le_next)					\
498 		panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
499 	if (*(elm)->field.le_prev != (elm))				\
500 		panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__);
501 #define	QUEUEDEBUG_LIST_POSTREMOVE(elm, field)				\
502 	(elm)->field.le_next = (void *)1L;				\
503 	(elm)->field.le_prev = (void *)1L;
504 #else
505 #define	QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
506 #define	QUEUEDEBUG_LIST_OP(elm, field)
507 #define	QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
508 #endif
509 
510 #define	LIST_INIT(head) do {						\
511 	LIST_FIRST((head)) = LIST_END(head);				\
512 	_NOTE(CONSTCOND)						\
513 } while (0)
514 
515 #define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
516 	QUEUEDEBUG_LIST_OP((listelm), field)				\
517 	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
518 		LIST_NEXT((listelm), field)->field.le_prev =		\
519 		    &LIST_NEXT((elm), field);				\
520 	LIST_NEXT((listelm), field) = (elm);				\
521 	(elm)->field.le_prev = &LIST_NEXT((listelm), field);		\
522 	_NOTE(CONSTCOND)						\
523 } while (0)
524 
525 #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
526 	QUEUEDEBUG_LIST_OP((listelm), field)				\
527 	(elm)->field.le_prev = (listelm)->field.le_prev;		\
528 	LIST_NEXT((elm), field) = (listelm);				\
529 	*(listelm)->field.le_prev = (elm);				\
530 	(listelm)->field.le_prev = &LIST_NEXT((elm), field);		\
531 	_NOTE(CONSTCOND)						\
532 } while (0)
533 
534 #define	LIST_INSERT_HEAD(head, elm, field) do {				\
535 	QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field)		\
536 	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\
537 		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
538 	LIST_FIRST((head)) = (elm);					\
539 	(elm)->field.le_prev = &LIST_FIRST((head));			\
540 	_NOTE(CONSTCOND)						\
541 } while (0)
542 
543 #define	LIST_REMOVE(elm, field) do {					\
544 	QUEUEDEBUG_LIST_OP((elm), field)				\
545 	if (LIST_NEXT((elm), field) != NULL)				\
546 		LIST_NEXT((elm), field)->field.le_prev =		\
547 		    (elm)->field.le_prev;				\
548 	*(elm)->field.le_prev = LIST_NEXT((elm), field);		\
549 	QUEUEDEBUG_LIST_POSTREMOVE((elm), field)			\
550 	_NOTE(CONSTCOND)						\
551 } while (0)
552 
553 #define	LIST_SWAP(head1, head2, type, field) do {                       \
554 	QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1);               \
555 	LIST_FIRST((head1)) = LIST_FIRST((head2));                      \
556 	LIST_FIRST((head2)) = swap_tmp;                                 \
557 	if ((swap_tmp = LIST_FIRST((head1))) != NULL)                   \
558 		swap_tmp->field.le_prev = &LIST_FIRST((head1));         \
559 	if ((swap_tmp = LIST_FIRST((head2))) != NULL)                   \
560 		swap_tmp->field.le_prev = &LIST_FIRST((head2));         \
561 	_NOTE(CONSTCOND)						\
562 } while (0)
563 
564 /*
565  * Simple queue definitions.
566  */
567 #define	SIMPLEQ_HEAD(name, type)					\
568 struct name {								\
569 	struct type *sqh_first;	/* first element */		\
570 	struct type **sqh_last;	/* addr of last next element */	\
571 }
572 
573 #define	SIMPLEQ_CLASS_HEAD(name, type)					\
574 struct name {								\
575 	class type *sqh_first;	/* first element */		\
576 	class type **sqh_last;	/* addr of last next element */	\
577 }
578 
579 #define	SIMPLEQ_HEAD_INITIALIZER(head)					\
580 	{ NULL, &(head).sqh_first }
581 
582 #define	SIMPLEQ_ENTRY(type)						\
583 struct {								\
584 	struct type *sqe_next;	/* next element */			\
585 }
586 
587 #define	SIMPLEQ_CLASS_ENTRY(type)					\
588 struct {								\
589 	class type *sqe_next;	/* next element */			\
590 }
591 
592 /*
593  * Simple queue access methods.
594  */
595 #define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
596 #define	SIMPLEQ_END(head)		NULL
597 #define	SIMPLEQ_EMPTY(head)		((head)->sqh_first == SIMPLEQ_END(head))
598 #define	SIMPLEQ_NEXT(elm, field)	((elm)->field.sqe_next)
599 
600 #define	SIMPLEQ_FOREACH(var, head, field)				\
601 	for ((var) = SIMPLEQ_FIRST((head));				\
602 	    (var) != SIMPLEQ_END(head);					\
603 	    (var) = SIMPLEQ_NEXT((var), field))
604 
605 #define	SIMPLEQ_FOREACH_FROM(var, head, field)				\
606 	for ((var) =							\
607 	    ((var) != SIMPLEQ_END(head) ? (var) : SIMPLEQ_FIRST((head)));\
608 	    (var) != SIMPLEQ_END(head);					\
609 	    (var) = SIMPLEQ_NEXT((var), field))
610 
611 #define	SIMPLEQ_FOREACH_SAFE(var, head, field, tvar)			\
612 	for ((var) = SIMPLEQ_FIRST((head));				\
613 	    (var) != SIMPLEQ_END(head) &&				\
614 	    ((tvar) = SIMPLEQ_NEXT((var), field), 1);			\
615 	    (var) = (tvar))
616 
617 #define	SIMPLEQ_FOREACH_FROM_SAFE(var, head, field, tvar)		\
618 	for ((var) =							\
619 	    ((var) != SIMPLEQ_END(head) ? (var) : SIMPLEQ_FIRST((head)));\
620 	    (var) != SIMPLEQ_END(head) &&				\
621 	    ((tvar) = SIMPLEQ_NEXT((var), field), 1);			\
622 	    (var) = (tvar))
623 
624 /*
625  * Simple queue functions.
626  */
627 #define	SIMPLEQ_INIT(head) do {						\
628 	SIMPLEQ_FIRST((head)) = NULL;					\
629 	(head)->sqh_last = &SIMPLEQ_FIRST((head));			\
630 	_NOTE(CONSTCOND)						\
631 } while (0)
632 
633 #define	SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
634 	if ((SIMPLEQ_NEXT((elm), field) = SIMPLEQ_FIRST((head))) == NULL)\
635 		(head)->sqh_last = &SIMPLEQ_NEXT((elm), field);		\
636 	SIMPLEQ_FIRST((head)) = (elm);					\
637 	_NOTE(CONSTCOND)						\
638 } while (0)
639 
640 #define	SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
641 	SIMPLEQ_NEXT((elm), field) = NULL;				\
642 	*(head)->sqh_last = (elm);					\
643 	(head)->sqh_last = &SIMPLEQ_NEXT((elm), field);			\
644 	_NOTE(CONSTCOND)						\
645 } while (0)
646 
647 #define	SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
648 	if ((SIMPLEQ_NEXT((elm), field) = SIMPLEQ_NEXT((listelm), field)) == \
649 	    NULL)							\
650 		(head)->sqh_last = &SIMPLEQ_NEXT((elm), field);		\
651 	SIMPLEQ_NEXT((listelm), field) = (elm);				\
652 	_NOTE(CONSTCOND)						\
653 } while (0)
654 
655 #define	SIMPLEQ_REMOVE_HEAD(head, field) do {				\
656 	if ((SIMPLEQ_FIRST((head)) =					\
657 	    SIMPLEQ_NEXT(SIMPLEQ_FIRST((head)), field)) == NULL)	\
658 		(head)->sqh_last = &SIMPLEQ_FIRST((head));		\
659 	_NOTE(CONSTCOND)						\
660 } while (0)
661 
662 #define	SIMPLEQ_REMOVE_AFTER(head, elm, field) do {			\
663 	if ((SIMPLEQ_NEXT((elm)) =					\
664 	    SIMPLEQ_NEXT(SIMPLEQ_NEXT((elm), field), field)) == NULL)	\
665 		(head)->sqh_last = &SIMPLEQ_NEXT((elm), field);		\
666 	_NOTE(CONSTCOND)						\
667 } while (0)
668 
669 #define	SIMPLEQ_REMOVE(head, elm, type, field) do {			\
670 	if (SIMPLEQ_FIRST((head)) == (elm)) {				\
671 		SIMPLEQ_REMOVE_HEAD((head), field);			\
672 	} else {							\
673 		QUEUE_TYPEOF(type) *curelm = SIMPLEQ_FIRST((head));	\
674 		while (SIMPLEQ_NEXT(curelm, field) != (elm))		\
675 			curelm = SIMPLEQ_NEXT(curelm, field);		\
676 		SIMPLEQ_REMOVE_AFTER((head), curelm, field);		\
677 	}								\
678 	_NOTE(CONSTCOND)						\
679 } while (0)
680 
681 #define	SIMPLEQ_CONCAT(head1, head2) do {				\
682 	if (!SIMPLEQ_EMPTY((head2))) {					\
683 		*(head1)->sqh_last = (head2)->sqh_first;		\
684 		(head1)->sqh_last = (head2)->sqh_last;			\
685 		SIMPLEQ_INIT((head2));					\
686 	}								\
687 	_NOTE(CONSTCOND)						\
688 } while (0)
689 
690 #define	SIMPLEQ_LAST(head, type, field)					\
691 	(SIMPLEQ_EMPTY((head)) ?					\
692 	    NULL :							\
693 	    ((QUEUE_TYPEOF(type) *)(void *)				\
694 	    ((char *)((head)->sqh_last) - offsetof(QUEUE_TYPEOF(type), field))))
695 
696 /*
697  * Tail queue definitions.
698  */
699 #define	TAILQ_HEAD(name, type)						\
700 struct name {								\
701 	struct type *tqh_first;		/* first element */		\
702 	struct type **tqh_last;	/* addr of last next element */		\
703 	TRACEBUF							\
704 }
705 
706 #define	TAILQ_CLASS_HEAD(name, type)					\
707 struct name {								\
708 	class type *tqh_first;		/* first element */		\
709 	class type **tqh_last;	/* addr of last next element */		\
710 	TRACEBUF							\
711 }
712 
713 #define	TAILQ_HEAD_INITIALIZER(head)					\
714 	{ NULL, &(head).tqh_first }
715 
716 #define	TAILQ_ENTRY(type)						\
717 struct {								\
718 	struct type *tqe_next;	/* next element */			\
719 	struct type **tqe_prev;	/* address of previous next element */	\
720 	TRACEBUF							\
721 }
722 
723 #define	TAILQ_CLASS_ENTRY(type)						\
724 struct {								\
725 	class type *tqe_next;	/* next element */			\
726 	class type **tqe_prev;	/* address of previous next element */	\
727 	TRACEBUF							\
728 }
729 
730 /*
731  * Tail queue access methods.
732  */
733 #define	TAILQ_FIRST(head)		((head)->tqh_first)
734 #define	TAILQ_END(head)			NULL
735 #define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
736 #define	TAILQ_LAST(head, headname) \
737 	(*(((struct headname *)((head)->tqh_last))->tqh_last))
738 #define	TAILQ_PREV(elm, headname, field) \
739 	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
740 #define	TAILQ_EMPTY(head)		((head)->tqh_first == TAILQ_END(head))
741 
742 
743 #define	TAILQ_FOREACH(var, head, field)					\
744 	for ((var) = TAILQ_FIRST((head));				\
745 	    (var) != TAILQ_END(head);					\
746 	    (var) = TAILQ_NEXT((var), field))
747 
748 #define	TAILQ_FOREACH_FROM(var, head, field)				\
749 	for ((var) = ((var) != TAILQ_END((head)) ?			\
750 	    (var) : TAILQ_FIRST((head)));				\
751 	    (var) != TAILQ_END(head);					\
752 	    (var) = TAILQ_NEXT((var), field))
753 
754 #define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
755 	for ((var) = TAILQ_FIRST((head));				\
756 	    (var) != TAILQ_END(head) &&					\
757 	    ((tvar) = TAILQ_NEXT((var), field), 1);			\
758 	    (var) = (tvar))
759 
760 #define	TAILQ_FOREACH_FROM_SAFE(var, head, field, tvar)			\
761 	for ((var) = ((var) != TAILQ_END((head)) ?			\
762 	    (var) : TAILQ_FIRST((head)));				\
763 	    (var) != TAILQ_END(head) &&					\
764 	    ((tvar) = TAILQ_NEXT((var), field), 1);			\
765 	    (var) = (tvar))
766 
767 #define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
768 	for ((var) = TAILQ_LAST((head), headname);			\
769 	    (var) != TAILQ_END(head);					\
770 	    (var) = TAILQ_PREV((var), headname, field))
771 
772 #define	TAILQ_FOREACH_REVERSE_FROM(var, head, headname, field)		\
773 	for ((var) = ((var) != TAILQ_END((head)) ?			\
774 	    (var) : TAILQ_LAST((head), headname));			\
775 	    (var) != TAILQ_END(head);					\
776 	    (var) = TAILQ_PREV((var), headname, field))
777 
778 #define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
779 	for ((var) = TAILQ_LAST((head), headname);			\
780 	    (var) != TAILQ_END(head) &&					\
781 	    ((tvar) = TAILQ_PREV((var), headname, field), 1);		\
782 	    (var) = (tvar))
783 
784 #define	TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar)\
785 	for ((var) = ((var) != TAILQ_END((head)) ?			\
786 	    (var) : TAILQ_LAST((head), headname));			\
787 	    (var) != TAILQ_END(head) &&					\
788 	    ((tvar) = TAILQ_PREV((var), headname, field), 1);		\
789 	    (var) = (tvar))
790 
791 /*
792  * Tail queue functions.
793  */
794 #if defined(_KERNEL) && defined(QUEUEDEBUG)
795 #define	QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)			\
796 	if ((head)->tqh_first &&					\
797 	    (head)->tqh_first->field.tqe_prev != &(head)->tqh_first)	\
798 		panic("TAILQ_INSERT_HEAD %p %s:%d", (void *)(head),	\
799 		    __FILE__, __LINE__);
800 #define	QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)			\
801 	if (*(head)->tqh_last != NULL)					\
802 		panic("TAILQ_INSERT_TAIL %p %s:%d", (void *)(head),	\
803 		    __FILE__, __LINE__);
804 #define	QUEUEDEBUG_TAILQ_OP(elm, field)					\
805 	if ((elm)->field.tqe_next &&					\
806 	    (elm)->field.tqe_next->field.tqe_prev !=			\
807 	    &(elm)->field.tqe_next)					\
808 		panic("TAILQ_* forw %p %s:%d", (void *)(elm),		\
809 		    __FILE__, __LINE__);\
810 	if (*(elm)->field.tqe_prev != (elm))				\
811 		panic("TAILQ_* back %p %s:%d", (void *)(elm),		\
812 		    __FILE__, __LINE__);
813 #define	QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)			\
814 	if ((elm)->field.tqe_next == NULL &&				\
815 	    (head)->tqh_last != &(elm)->field.tqe_next)			\
816 		panic("TAILQ_PREREMOVE head %p elm %p %s:%d",		\
817 		    (void *)(head), (void *)(elm), __FILE__, __LINE__);
818 #define	QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)				\
819 	(elm)->field.tqe_next = (void *)1L;				\
820 	(elm)->field.tqe_prev = (void *)1L;
821 #else
822 #define	QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
823 #define	QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
824 #define	QUEUEDEBUG_TAILQ_OP(elm, field)
825 #define	QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)
826 #define	QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
827 #endif
828 
829 #define	TAILQ_INIT(head) do {						\
830 	TAILQ_FIRST((head)) = TAILQ_END((head));			\
831 	(head)->tqh_last = &TAILQ_FIRST((head));			\
832 	_NOTE(CONSTCOND)						\
833 } while (0)
834 
835 #define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
836 	QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field)		\
837 	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)	\
838 		TAILQ_FIRST((head))->field.tqe_prev =			\
839 		    &TAILQ_NEXT((elm), field);				\
840 	else								\
841 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
842 	TAILQ_FIRST((head)) = (elm);					\
843 	(elm)->field.tqe_prev = &TAILQ_FIRST((head));			\
844 	_NOTE(CONSTCOND)						\
845 } while (0)
846 
847 #define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
848 	QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field)		\
849 	TAILQ_NEXT((elm), field) = NULL;				\
850 	(elm)->field.tqe_prev = (head)->tqh_last;			\
851 	*(head)->tqh_last = (elm);					\
852 	(head)->tqh_last = &TAILQ_NEXT((elm), field);			\
853 	_NOTE(CONSTCOND)						\
854 } while (0)
855 
856 #define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
857 	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
858 	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
859 		TAILQ_NEXT((elm), field)->field.tqe_prev =		\
860 		    &TAILQ_NEXT((elm), field);				\
861 	else								\
862 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
863 	TAILQ_NEXT((listelm), field) = (elm);				\
864 	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);		\
865 	_NOTE(CONSTCOND)						\
866 } while (0)
867 
868 #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
869 	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
870 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
871 	TAILQ_NEXT((elm), field) = (listelm);				\
872 	*(listelm)->field.tqe_prev = (elm);				\
873 	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);		\
874 	_NOTE(CONSTCOND)						\
875 } while (0)
876 
877 #define	TAILQ_REMOVE(head, elm, field) do {				\
878 	QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field)		\
879 	QUEUEDEBUG_TAILQ_OP((elm), field)				\
880 	if ((TAILQ_NEXT((elm), field)) != NULL)				\
881 		TAILQ_NEXT((elm), field)->field.tqe_prev =		\
882 		    (elm)->field.tqe_prev;				\
883 	else								\
884 		(head)->tqh_last = (elm)->field.tqe_prev;		\
885 	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);		\
886 	QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field);			\
887 	_NOTE(CONSTCOND)						\
888 } while (0)
889 
890 #define	TAILQ_SWAP(head1, head2, type, field) do {			\
891 	QUEUE_TYPEOF(type) *swap_first = TAILQ_FIRST((head1));		\
892 	QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last;		\
893 	TAILQ_FIRST((head1)) = TAILQ_FIRST((head2));			\
894 	(head1)->tqh_last = (head2)->tqh_last;				\
895 	TAILQ_FIRST((head2)) = swap_first;				\
896 	(head2)->tqh_last = swap_last;					\
897 	if ((swap_first = TAILQ_FIRST((head1))) != NULL)		\
898 		swap_first->field.tqe_prev = &TAILQ_FIRST((head1));	\
899 	else								\
900 		(head1)->tqh_last = &TAILQ_FIRST((head1));		\
901 	if ((swap_first = TAILQ_FIRST((head2))) != NULL)		\
902 		swap_first->field.tqe_prev = &TAILQ_FIRST((head2));	\
903 	else								\
904 		(head2)->tqh_last = &TAILQ_FIRST((head2));		\
905 	_NOTE(CONSTCOND)						\
906 } while (0)
907 
908 /*
909  * Circular queue definitions. Do not use. We still keep the macros
910  * for compatibility but because of pointer aliasing issues their use
911  * is discouraged!
912  */
913 #define	CIRCLEQ_HEAD(name, type)					\
914 struct name {								\
915 	struct type *cqh_first;		/* first element */	\
916 	struct type *cqh_last;		/* last element */		\
917 }
918 
919 #define	CIRCLEQ_HEAD_INITIALIZER(head)					\
920 	{ (void *)&head, (void *)&head }
921 
922 #define	CIRCLEQ_ENTRY(type)						\
923 struct {								\
924 	struct type *cqe_next;		/* next element */		\
925 	struct type *cqe_prev;		/* previous element */		\
926 }
927 
928 /*
929  * Circular queue access methods.
930  */
931 #define	CIRCLEQ_EMPTY(head)		((head)->cqh_first == (void *)(head))
932 #define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
933 #define	CIRCLEQ_LAST(head)		((head)->cqh_last)
934 #define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
935 #define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
936 
937 #define	CIRCLEQ_LOOP_NEXT(head, elm, field)				\
938 	(((elm)->field.cqe_next == (void *)(head))			\
939 	    ? ((head)->cqh_first)					\
940 	    : (elm->field.cqe_next))
941 #define	CIRCLEQ_LOOP_PREV(head, elm, field)				\
942 	(((elm)->field.cqe_prev == (void *)(head))			\
943 	    ? ((head)->cqh_last)					\
944 	    : (elm->field.cqe_prev))
945 
946 #define	CIRCLEQ_FOREACH(var, head, field)				\
947 	for ((var) = CIRCLEQ_FIRST((head));				\
948 		(var) != (void *)(head);				\
949 		(var) = CIRCLEQ_NEXT((var), field))
950 
951 #define	CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
952 	for ((var) = CIRCLEQ_LAST((head));				\
953 		(var) != (void *)(head);				\
954 		(var) = CIRCLEQ_PREV((var), field))
955 
956 /*
957  * Circular queue functions.
958  */
959 #define	CIRCLEQ_INIT(head) do {						\
960 	(head)->cqh_first = (void *)(head);				\
961 	(head)->cqh_last = (void *)(head);				\
962 	_NOTE(CONSTCOND)						\
963 } while (0)
964 
965 #define	CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
966 	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
967 	(elm)->field.cqe_prev = (listelm);				\
968 	if ((listelm)->field.cqe_next == (void *)(head))		\
969 		(head)->cqh_last = (elm);				\
970 	else								\
971 		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
972 	(listelm)->field.cqe_next = (elm);				\
973 	_NOTE(CONSTCOND)						\
974 } while (0)
975 
976 #define	CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
977 	(elm)->field.cqe_next = (listelm);				\
978 	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
979 	if ((listelm)->field.cqe_prev == (void *)(head))		\
980 		(head)->cqh_first = (elm);				\
981 	else								\
982 		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
983 	(listelm)->field.cqe_prev = (elm);				\
984 	_NOTE(CONSTCOND)						\
985 } while (0)
986 
987 #define	CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
988 	(elm)->field.cqe_next = (head)->cqh_first;			\
989 	(elm)->field.cqe_prev = (void *)(head);				\
990 	if ((head)->cqh_last == (void *)(head))			\
991 		(head)->cqh_last = (elm);				\
992 	else								\
993 		(head)->cqh_first->field.cqe_prev = (elm);		\
994 	(head)->cqh_first = (elm);					\
995 	_NOTE(CONSTCOND)						\
996 } while (0)
997 
998 #define	CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
999 	(elm)->field.cqe_next = (void *)(head);				\
1000 	(elm)->field.cqe_prev = (head)->cqh_last;			\
1001 	if ((head)->cqh_first == (void *)(head))			\
1002 		(head)->cqh_first = (elm);				\
1003 	else								\
1004 		(head)->cqh_last->field.cqe_next = (elm);		\
1005 	(head)->cqh_last = (elm);					\
1006 	_NOTE(CONSTCOND)						\
1007 } while (0)
1008 
1009 #define	CIRCLEQ_REMOVE(head, elm, field) do {				\
1010 	if ((elm)->field.cqe_next == (void *)(head))			\
1011 		(head)->cqh_last = (elm)->field.cqe_prev;		\
1012 	else								\
1013 		(elm)->field.cqe_next->field.cqe_prev =			\
1014 		    (elm)->field.cqe_prev;				\
1015 	if ((elm)->field.cqe_prev == (void *)(head))			\
1016 		(head)->cqh_first = (elm)->field.cqe_next;		\
1017 	else								\
1018 		(elm)->field.cqe_prev->field.cqe_next =			\
1019 		    (elm)->field.cqe_next;				\
1020 	_NOTE(CONSTCOND)						\
1021 } while (0)
1022 
1023 #ifdef __cplusplus
1024 }
1025 #endif
1026 
1027 #endif	/* !_SYS_QUEUE_H */
1028