xref: /titanic_41/usr/src/uts/common/io/drm/queue.h (revision 60405de4d8688d96dd05157c28db3ade5c9bc234)
1 /* BEGIN CSTYLED */
2 /*-
3  * Copyright (c) 1991, 1993
4  *	The Regents of the University of California.  All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  * 4. Neither the name of the University nor the names of its contributors
15  *    may be used to endorse or promote products derived from this software
16  *    without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
19  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
22  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28  * SUCH DAMAGE.
29  *
30  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
31  * $FreeBSD: /repoman/r/ncvs/src/sys/sys/queue.h,v 1.66 2006/05/26 18:17:53 emaste Exp $
32  */
33 
34 #ifndef _SYS_QUEUE_H_
35 #define	_SYS_QUEUE_H_
36 
37 #pragma ident	"%Z%%M%	%I%	%E% SMI"
38 
39 /*
40  * This file defines four types of data structures: singly-linked lists,
41  * singly-linked tail queues, lists and tail queues.
42  *
43  * A singly-linked list is headed by a single forward pointer. The elements
44  * are singly linked for minimum space and pointer manipulation overhead at
45  * the expense of O(n) removal for arbitrary elements. New elements can be
46  * added to the list after an existing element or at the head of the list.
47  * Elements being removed from the head of the list should use the explicit
48  * macro for this purpose for optimum efficiency. A singly-linked list may
49  * only be traversed in the forward direction.  Singly-linked lists are ideal
50  * for applications with large datasets and few or no removals or for
51  * implementing a LIFO queue.
52  *
53  * A singly-linked tail queue is headed by a pair of pointers, one to the
54  * head of the list and the other to the tail of the list. The elements are
55  * singly linked for minimum space and pointer manipulation overhead at the
56  * expense of O(n) removal for arbitrary elements. New elements can be added
57  * to the list after an existing element, at the head of the list, or at the
58  * end of the list. Elements being removed from the head of the tail queue
59  * should use the explicit macro for this purpose for optimum efficiency.
60  * A singly-linked tail queue may only be traversed in the forward direction.
61  * Singly-linked tail queues are ideal for applications with large datasets
62  * and few or no removals or for implementing a FIFO queue.
63  *
64  * A list is headed by a single forward pointer (or an array of forward
65  * pointers for a hash table header). The elements are doubly linked
66  * so that an arbitrary element can be removed without a need to
67  * traverse the list. New elements can be added to the list before
68  * or after an existing element or at the head of the list. A list
69  * may only be traversed in the forward direction.
70  *
71  * A tail queue is headed by a pair of pointers, one to the head of the
72  * list and the other to the tail of the list. The elements are doubly
73  * linked so that an arbitrary element can be removed without a need to
74  * traverse the list. New elements can be added to the list before or
75  * after an existing element, at the head of the list, or at the end of
76  * the list. A tail queue may be traversed in either direction.
77  *
78  * For details on the use of these macros, see the queue(3) manual page.
79  *
80  *
81  *				SLIST	LIST	STAILQ	TAILQ
82  * _HEAD			+	+	+	+
83  * _HEAD_INITIALIZER		+	+	+	+
84  * _ENTRY			+	+	+	+
85  * _INIT			+	+	+	+
86  * _EMPTY			+	+	+	+
87  * _FIRST			+	+	+	+
88  * _NEXT			+	+	+	+
89  * _PREV			-	-	-	+
90  * _LAST			-	-	+	+
91  * _FOREACH			+	+	+	+
92  * _FOREACH_SAFE		+	+	+	+
93  * _FOREACH_REVERSE		-	-	-	+
94  * _FOREACH_REVERSE_SAFE	-	-	-	+
95  * _INSERT_HEAD			+	+	+	+
96  * _INSERT_BEFORE		-	+	-	+
97  * _INSERT_AFTER		+	+	+	+
98  * _INSERT_TAIL			-	-	+	+
99  * _CONCAT			-	-	+	+
100  * _REMOVE_HEAD			+	-	+	-
101  * _REMOVE			+	+	+	+
102  *
103  */
104 #ifdef QUEUE_MACRO_DEBUG
105 /* Store the last 2 places the queue element or head was altered */
106 struct qm_trace {
107 	char * lastfile;
108 	int lastline;
109 	char * prevfile;
110 	int prevline;
111 };
112 
113 #define	TRACEBUF	struct qm_trace trace;
114 #define	TRASHIT(x)	do {(x) = (void *)-1;} while (*"\0")
115 
116 #define	QMD_TRACE_HEAD(head) do {					\
117 	(head)->trace.prevline = (head)->trace.lastline;		\
118 	(head)->trace.prevfile = (head)->trace.lastfile;		\
119 	(head)->trace.lastline = __LINE__;				\
120 	(head)->trace.lastfile = __FILE__;				\
121 } while (*"\0")
122 
123 #define	QMD_TRACE_ELEM(elem) do {					\
124 	(elem)->trace.prevline = (elem)->trace.lastline;		\
125 	(elem)->trace.prevfile = (elem)->trace.lastfile;		\
126 	(elem)->trace.lastline = __LINE__;				\
127 	(elem)->trace.lastfile = __FILE__;				\
128 } while (*"\0")
129 
130 #else
131 #define	QMD_TRACE_ELEM(elem)
132 #define	QMD_TRACE_HEAD(head)
133 #define	TRACEBUF
134 #define	TRASHIT(x)
135 #endif	/* QUEUE_MACRO_DEBUG */
136 
137 /*
138  * Singly-linked List declarations.
139  */
140 #define	SLIST_HEAD(name, type)						\
141 struct name {								\
142 	struct type *slh_first;	/* first element */			\
143 }
144 
145 #define	SLIST_HEAD_INITIALIZER(head)					\
146 	{ NULL }
147 
148 #define	SLIST_ENTRY(type)						\
149 struct {								\
150 	struct type *sle_next;	/* next element */			\
151 }
152 
153 /*
154  * Singly-linked List functions.
155  */
156 #define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
157 
158 #define	SLIST_FIRST(head)	((head)->slh_first)
159 
160 #define	SLIST_FOREACH(var, head, field)					\
161 	for ((var) = SLIST_FIRST((head));				\
162 	    (var);							\
163 	    (var) = SLIST_NEXT((var), field))
164 
165 #define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
166 	for ((var) = SLIST_FIRST((head));				\
167 	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);		\
168 	    (var) = (tvar))
169 
170 #define	SLIST_FOREACH_PREVPTR(var, varp, head, field)			\
171 	for ((varp) = &SLIST_FIRST((head));				\
172 	    ((var) = *(varp)) != NULL;					\
173 	    (varp) = &SLIST_NEXT((var), field))
174 
175 #define	SLIST_INIT(head) do {						\
176 	SLIST_FIRST((head)) = NULL;					\
177 } while (*"\0")
178 
179 #define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
180 	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);	\
181 	SLIST_NEXT((slistelm), field) = (elm);				\
182 } while (*"\0")
183 
184 #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
185 	SLIST_NEXT((elm), field) = SLIST_FIRST((head));			\
186 	SLIST_FIRST((head)) = (elm);					\
187 } while (*"\0")
188 
189 #define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
190 
191 #define	SLIST_REMOVE(head, elm, type, field) do {			\
192 	if (SLIST_FIRST((head)) == (elm)) {				\
193 		SLIST_REMOVE_HEAD((head), field);			\
194 	}								\
195 	else {								\
196 		struct type *curelm = SLIST_FIRST((head));		\
197 		while (SLIST_NEXT(curelm, field) != (elm))		\
198 			curelm = SLIST_NEXT(curelm, field);		\
199 		SLIST_NEXT(curelm, field) =				\
200 		    SLIST_NEXT(SLIST_NEXT(curelm, field), field);	\
201 	}								\
202 	TRASHIT((elm)->field.sle_next);					\
203 } while (*"\0")
204 
205 #define	SLIST_REMOVE_HEAD(head, field) do {				\
206 	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
207 } while (*"\0")
208 
209 /*
210  * Singly-linked Tail queue declarations.
211  */
212 #define	STAILQ_HEAD(name, type)						\
213 struct name {								\
214 	struct type *stqh_first;/* first element */			\
215 	struct type **stqh_last;/* addr of last next element */		\
216 }
217 
218 #define	STAILQ_HEAD_INITIALIZER(head)					\
219 	{ NULL, &(head).stqh_first }
220 
221 #define	STAILQ_ENTRY(type)						\
222 struct {								\
223 	struct type *stqe_next;	/* next element */			\
224 }
225 
226 /*
227  * Singly-linked Tail queue functions.
228  */
229 #define	STAILQ_CONCAT(head1, head2) do {				\
230 	if (!STAILQ_EMPTY((head2))) {					\
231 		*(head1)->stqh_last = (head2)->stqh_first;		\
232 		(head1)->stqh_last = (head2)->stqh_last;		\
233 		STAILQ_INIT((head2));					\
234 	}								\
235 } while (*"\0")
236 
237 #define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)
238 
239 #define	STAILQ_FIRST(head)	((head)->stqh_first)
240 
241 #define	STAILQ_FOREACH(var, head, field)				\
242 	for((var) = STAILQ_FIRST((head));				\
243 	   (var);							\
244 	   (var) = STAILQ_NEXT((var), field))
245 
246 
247 #define	STAILQ_FOREACH_SAFE(var, head, field, tvar)			\
248 	for ((var) = STAILQ_FIRST((head));				\
249 	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\
250 	    (var) = (tvar))
251 
252 #define	STAILQ_INIT(head) do {						\
253 	STAILQ_FIRST((head)) = NULL;					\
254 	(head)->stqh_last = &STAILQ_FIRST((head));			\
255 } while (*"\0")
256 
257 #define	STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\
258 	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
259 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
260 	STAILQ_NEXT((tqelm), field) = (elm);				\
261 } while (*"\0")
262 
263 #define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
264 	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)	\
265 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
266 	STAILQ_FIRST((head)) = (elm);					\
267 } while (*"\0")
268 
269 #define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
270 	STAILQ_NEXT((elm), field) = NULL;				\
271 	*(head)->stqh_last = (elm);					\
272 	(head)->stqh_last = &STAILQ_NEXT((elm), field);			\
273 } while (*"\0")
274 
275 #define	STAILQ_LAST(head, type, field)					\
276 	(STAILQ_EMPTY((head)) ?						\
277 		NULL :							\
278 	        ((struct type *)(void *)				\
279 		((char *)((head)->stqh_last) - __offsetof(struct type, field))))
280 
281 #define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
282 
283 #define	STAILQ_REMOVE(head, elm, type, field) do {			\
284 	if (STAILQ_FIRST((head)) == (elm)) {				\
285 		STAILQ_REMOVE_HEAD((head), field);			\
286 	}								\
287 	else {								\
288 		struct type *curelm = STAILQ_FIRST((head));		\
289 		while (STAILQ_NEXT(curelm, field) != (elm))		\
290 			curelm = STAILQ_NEXT(curelm, field);		\
291 		if ((STAILQ_NEXT(curelm, field) =			\
292 		     STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\
293 			(head)->stqh_last = &STAILQ_NEXT((curelm), field);\
294 	}								\
295 	TRASHIT((elm)->field.stqe_next);				\
296 } while (*"\0")
297 
298 #define	STAILQ_REMOVE_HEAD(head, field) do {				\
299 	if ((STAILQ_FIRST((head)) =					\
300 	     STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)		\
301 		(head)->stqh_last = &STAILQ_FIRST((head));		\
302 } while (*"\0")
303 
304 #define	STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {			\
305 	if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL)	\
306 		(head)->stqh_last = &STAILQ_FIRST((head));		\
307 } while (*"\0")
308 
309 /*
310  * List declarations.
311  */
312 #define	LIST_HEAD(name, type)						\
313 struct name {								\
314 	struct type *lh_first;	/* first element */			\
315 }
316 
317 #define	LIST_HEAD_INITIALIZER(head)					\
318 	{ NULL }
319 
320 #define	LIST_ENTRY(type)						\
321 struct {								\
322 	struct type *le_next;	/* next element */			\
323 	struct type **le_prev;	/* address of previous next element */	\
324 }
325 
326 /*
327  * List functions.
328  */
329 
330 #if (defined(_KERNEL) && defined(INVARIANTS))
331 #define	QMD_LIST_CHECK_HEAD(head, field) do {				\
332 	if (LIST_FIRST((head)) != NULL &&				\
333 	    LIST_FIRST((head))->field.le_prev !=			\
334 	     &LIST_FIRST((head)))					\
335 		panic("Bad list head %p first->prev != head", (head));	\
336 } while (*"\0")
337 
338 #define	QMD_LIST_CHECK_NEXT(elm, field) do {				\
339 	if (LIST_NEXT((elm), field) != NULL &&				\
340 	    LIST_NEXT((elm), field)->field.le_prev !=			\
341 	     &((elm)->field.le_next))					\
342 	     	panic("Bad link elm %p next->prev != elm", (elm));	\
343 } while (*"\0")
344 
345 #define	QMD_LIST_CHECK_PREV(elm, field) do {				\
346 	if (*(elm)->field.le_prev != (elm))				\
347 		panic("Bad link elm %p prev->next != elm", (elm));	\
348 } while (*"\0")
349 #else
350 #define	QMD_LIST_CHECK_HEAD(head, field)
351 #define	QMD_LIST_CHECK_NEXT(elm, field)
352 #define	QMD_LIST_CHECK_PREV(elm, field)
353 #endif /* (_KERNEL && INVARIANTS) */
354 
355 #define	LIST_EMPTY(head)	((head)->lh_first == NULL)
356 
357 #define	LIST_FIRST(head)	((head)->lh_first)
358 
359 #define	LIST_FOREACH(var, head, field)					\
360 	for ((var) = LIST_FIRST((head));				\
361 	    (var);							\
362 	    (var) = LIST_NEXT((var), field))
363 
364 #define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
365 	for ((var) = LIST_FIRST((head));				\
366 	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\
367 	    (var) = (tvar))
368 
369 #define	LIST_INIT(head) do {						\
370 	LIST_FIRST((head)) = NULL;					\
371 } while (*"\0")
372 
373 #define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
374 	QMD_LIST_CHECK_NEXT(listelm, field);				\
375 	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
376 		LIST_NEXT((listelm), field)->field.le_prev =		\
377 		    &LIST_NEXT((elm), field);				\
378 	LIST_NEXT((listelm), field) = (elm);				\
379 	(elm)->field.le_prev = &LIST_NEXT((listelm), field);		\
380 } while (*"\0")
381 
382 #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
383 	QMD_LIST_CHECK_PREV(listelm, field);				\
384 	(elm)->field.le_prev = (listelm)->field.le_prev;		\
385 	LIST_NEXT((elm), field) = (listelm);				\
386 	*(listelm)->field.le_prev = (elm);				\
387 	(listelm)->field.le_prev = &LIST_NEXT((elm), field);		\
388 } while (*"\0")
389 
390 #define	LIST_INSERT_HEAD(head, elm, field) do {				\
391 	QMD_LIST_CHECK_HEAD((head), field);				\
392 	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\
393 		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\
394 	LIST_FIRST((head)) = (elm);					\
395 	(elm)->field.le_prev = &LIST_FIRST((head));			\
396 } while (*"\0")
397 
398 #define	LIST_NEXT(elm, field)	((elm)->field.le_next)
399 
400 #define	LIST_REMOVE(elm, field) do {					\
401 	QMD_LIST_CHECK_NEXT(elm, field);				\
402 	QMD_LIST_CHECK_PREV(elm, field);				\
403 	if (LIST_NEXT((elm), field) != NULL)				\
404 		LIST_NEXT((elm), field)->field.le_prev = 		\
405 		    (elm)->field.le_prev;				\
406 	*(elm)->field.le_prev = LIST_NEXT((elm), field);		\
407 	TRASHIT((elm)->field.le_next);					\
408 	TRASHIT((elm)->field.le_prev);					\
409 } while (*"\0")
410 
411 /*
412  * Tail queue declarations.
413  */
414 #define	TAILQ_HEAD(name, type)						\
415 struct name {								\
416 	struct type *tqh_first;	/* first element */			\
417 	struct type **tqh_last;	/* addr of last next element */		\
418 	TRACEBUF							\
419 }
420 
421 #define	TAILQ_HEAD_INITIALIZER(head)					\
422 	{ NULL, &(head).tqh_first }
423 
424 #define	TAILQ_ENTRY(type)						\
425 struct {								\
426 	struct type *tqe_next;	/* next element */			\
427 	struct type **tqe_prev;	/* address of previous next element */	\
428 	TRACEBUF							\
429 }
430 
431 /*
432  * Tail queue functions.
433  */
434 #if (defined(_KERNEL) && defined(INVARIANTS))
435 #define	QMD_TAILQ_CHECK_HEAD(head, field) do {				\
436 	if (!TAILQ_EMPTY(head) &&					\
437 	    TAILQ_FIRST((head))->field.tqe_prev !=			\
438 	     &TAILQ_FIRST((head)))					\
439 		panic("Bad tailq head %p first->prev != head", (head));	\
440 } while (*"\0")
441 
442 #define	QMD_TAILQ_CHECK_TAIL(head, field) do {				\
443 	if (*(head)->tqh_last != NULL)					\
444 	    	panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); 	\
445 } while (*"\0")
446 
447 #define	QMD_TAILQ_CHECK_NEXT(elm, field) do {				\
448 	if (TAILQ_NEXT((elm), field) != NULL &&				\
449 	    TAILQ_NEXT((elm), field)->field.tqe_prev !=			\
450 	     &((elm)->field.tqe_next))					\
451 		panic("Bad link elm %p next->prev != elm", (elm));	\
452 } while (*"\0")
453 
454 #define	QMD_TAILQ_CHECK_PREV(elm, field) do {				\
455 	if (*(elm)->field.tqe_prev != (elm))				\
456 		panic("Bad link elm %p prev->next != elm", (elm));	\
457 } while (*"\0")
458 #else
459 #define	QMD_TAILQ_CHECK_HEAD(head, field)
460 #define	QMD_TAILQ_CHECK_TAIL(head, headname)
461 #define	QMD_TAILQ_CHECK_NEXT(elm, field)
462 #define	QMD_TAILQ_CHECK_PREV(elm, field)
463 #endif /* (_KERNEL && INVARIANTS) */
464 
465 #define	TAILQ_CONCAT(head1, head2, field) do {				\
466 	if (!TAILQ_EMPTY(head2)) {					\
467 		*(head1)->tqh_last = (head2)->tqh_first;		\
468 		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
469 		(head1)->tqh_last = (head2)->tqh_last;			\
470 		TAILQ_INIT((head2));					\
471 		QMD_TRACE_HEAD(head1);					\
472 		QMD_TRACE_HEAD(head2);					\
473 	}								\
474 } while (*"\0")
475 
476 #define	TAILQ_EMPTY(head)	((head)->tqh_first == NULL)
477 
478 #define	TAILQ_FIRST(head)	((head)->tqh_first)
479 
480 #define	TAILQ_FOREACH(var, head, field)					\
481 	for ((var) = TAILQ_FIRST((head));				\
482 	    (var);							\
483 	    (var) = TAILQ_NEXT((var), field))
484 
485 #define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
486 	for ((var) = TAILQ_FIRST((head));				\
487 	    (var) && ((tvar) = TAILQ_NEXT((var), field), 1);		\
488 	    (var) = (tvar))
489 
490 #define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
491 	for ((var) = TAILQ_LAST((head), headname);			\
492 	    (var);							\
493 	    (var) = TAILQ_PREV((var), headname, field))
494 
495 #define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
496 	for ((var) = TAILQ_LAST((head), headname);			\
497 	    (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);	\
498 	    (var) = (tvar))
499 
500 #define	TAILQ_INIT(head) do {						\
501 	TAILQ_FIRST((head)) = NULL;					\
502 	(head)->tqh_last = &TAILQ_FIRST((head));			\
503 	QMD_TRACE_HEAD(head);						\
504 } while (*"\0")
505 
506 #define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
507 	QMD_TAILQ_CHECK_NEXT(listelm, field);				\
508 	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
509 		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\
510 		    &TAILQ_NEXT((elm), field);				\
511 	else {								\
512 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
513 		QMD_TRACE_HEAD(head);					\
514 	}								\
515 	TAILQ_NEXT((listelm), field) = (elm);				\
516 	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);		\
517 	QMD_TRACE_ELEM(&(elm)->field);					\
518 	QMD_TRACE_ELEM(&listelm->field);				\
519 } while (*"\0")
520 
521 #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
522 	QMD_TAILQ_CHECK_PREV(listelm, field);				\
523 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
524 	TAILQ_NEXT((elm), field) = (listelm);				\
525 	*(listelm)->field.tqe_prev = (elm);				\
526 	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);		\
527 	QMD_TRACE_ELEM(&(elm)->field);					\
528 	QMD_TRACE_ELEM(&listelm->field);				\
529 } while (*"\0")
530 
531 #define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
532 	QMD_TAILQ_CHECK_HEAD(head, field);				\
533 	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)	\
534 		TAILQ_FIRST((head))->field.tqe_prev =			\
535 		    &TAILQ_NEXT((elm), field);				\
536 	else								\
537 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
538 	TAILQ_FIRST((head)) = (elm);					\
539 	(elm)->field.tqe_prev = &TAILQ_FIRST((head));			\
540 	QMD_TRACE_HEAD(head);						\
541 	QMD_TRACE_ELEM(&(elm)->field);					\
542 } while (*"\0")
543 
544 #define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
545 	QMD_TAILQ_CHECK_TAIL(head, field);				\
546 	TAILQ_NEXT((elm), field) = NULL;				\
547 	(elm)->field.tqe_prev = (head)->tqh_last;			\
548 	*(head)->tqh_last = (elm);					\
549 	(head)->tqh_last = &TAILQ_NEXT((elm), field);			\
550 	QMD_TRACE_HEAD(head);						\
551 	QMD_TRACE_ELEM(&(elm)->field);					\
552 } while (*"\0")
553 
554 #define	TAILQ_LAST(head, headname)					\
555 	(*(((struct headname *)((head)->tqh_last))->tqh_last))
556 
557 #define	TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
558 
559 #define	TAILQ_PREV(elm, headname, field)				\
560 	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
561 
562 #define	TAILQ_REMOVE(head, elm, field) do {				\
563 	QMD_TAILQ_CHECK_NEXT(elm, field);				\
564 	QMD_TAILQ_CHECK_PREV(elm, field);				\
565 	if ((TAILQ_NEXT((elm), field)) != NULL)				\
566 		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\
567 		    (elm)->field.tqe_prev;				\
568 	else {								\
569 		(head)->tqh_last = (elm)->field.tqe_prev;		\
570 		QMD_TRACE_HEAD(head);					\
571 	}								\
572 	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);		\
573 	TRASHIT((elm)->field.tqe_next);					\
574 	TRASHIT((elm)->field.tqe_prev);					\
575 	QMD_TRACE_ELEM(&(elm)->field);					\
576 } while (*"\0")
577 
578 
579 #ifdef _KERNEL
580 
581 #endif /* _KERNEL */
582 
583 #endif /* !_SYS_QUEUE_H_ */
584 
585 /* END CSTYLED */
586