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  * 4. 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  * $FreeBSD: src/sys/sys/queue.h,v 1.58 2004/04/07 04:19:49 imp Exp $
31  */
32  
33  #ifndef _QUEUE_H_
34  #define _QUEUE_H_
35  
36  /*
37   * This file defines four types of data structures: singly-linked lists,
38   * singly-linked tail queues, lists and tail queues.
39   *
40   * A singly-linked list is headed by a single forward pointer. The elements
41   * are singly linked for minimum space and pointer manipulation overhead at
42   * the expense of O(n) removal for arbitrary elements. New elements can be
43   * added to the list after an existing element or at the head of the list.
44   * Elements being removed from the head of the list should use the explicit
45   * macro for this purpose for optimum efficiency. A singly-linked list may
46   * only be traversed in the forward direction.  Singly-linked lists are ideal
47   * for applications with large datasets and few or no removals or for
48   * implementing a LIFO queue.
49   *
50   * A singly-linked tail queue is headed by a pair of pointers, one to the
51   * head of the list and the other to the tail of the list. The elements are
52   * singly linked for minimum space and pointer manipulation overhead at the
53   * expense of O(n) removal for arbitrary elements. New elements can be added
54   * to the list after an existing element, at the head of the list, or at the
55   * end of the list. Elements being removed from the head of the tail queue
56   * should use the explicit macro for this purpose for optimum efficiency.
57   * A singly-linked tail queue may only be traversed in the forward direction.
58   * Singly-linked tail queues are ideal for applications with large datasets
59   * and few or no removals or for implementing a FIFO queue.
60   *
61   * A list is headed by a single forward pointer (or an array of forward
62   * pointers for a hash table header). The elements are doubly linked
63   * so that an arbitrary element can be removed without a need to
64   * traverse the list. New elements can be added to the list before
65   * or after an existing element or at the head of the list. A list
66   * may only be traversed in the forward direction.
67   *
68   * A tail queue is headed by a pair of pointers, one to the head of the
69   * list and the other to the tail of the list. The elements are doubly
70   * linked so that an arbitrary element can be removed without a need to
71   * traverse the list. New elements can be added to the list before or
72   * after an existing element, at the head of the list, or at the end of
73   * the list. A tail queue may be traversed in either direction.
74   *
75   * For details on the use of these macros, see the queue(3) manual page.
76   *
77   *
78   *                SLIST    LIST    STAILQ    TAILQ
79   * _HEAD            +    +    +    +
80   * _HEAD_INITIALIZER        +    +    +    +
81   * _ENTRY            +    +    +    +
82   * _INIT            +    +    +    +
83   * _EMPTY            +    +    +    +
84   * _FIRST            +    +    +    +
85   * _NEXT            +    +    +    +
86   * _PREV            -    -    -    +
87   * _LAST            -    -    +    +
88   * _FOREACH            +    +    +    +
89   * _FOREACH_SAFE        +    +    +    +
90   * _FOREACH_REVERSE        -    -    -    +
91   * _FOREACH_REVERSE_SAFE    -    -    -    +
92   * _INSERT_HEAD            +    +    +    +
93   * _INSERT_BEFORE        -    +    -    +
94   * _INSERT_AFTER        +    +    +    +
95   * _INSERT_TAIL            -    -    +    +
96   * _CONCAT            -    -    +    +
97   * _REMOVE_HEAD            +    -    +    -
98   * _REMOVE            +    +    +    +
99   *
100   */
101  #define    QUEUE_MACRO_DEBUG 0
102  #if QUEUE_MACRO_DEBUG
103  /*
104   * Store the last 2 places the queue element or head was altered
105   */
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 *)NULL; } 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) do {(x) = (void *)0; } while (0)
135  #endif /* QUEUE_MACRO_DEBUG */
136  
137  #ifdef ATHR_RNWF
138  /*
139   * NDIS contains a defn for SLIST_ENTRY and SINGLE_LIST_ENTRY
140   */
141  #endif
142  
143  /*
144   * Singly-linked List declarations.
145   */
146  #define    SLIST_HEAD(name, type)			 \
147  	struct name {				     \
148  		struct type *slh_first; /* first element */	       \
149  	}
150  
151  #define    SLIST_HEAD_INITIALIZER(head)			   \
152  	{ NULL }
153  
154  #define    SING_LIST_ENTRY(type)			\
155  	struct {				\
156  		struct type *sle_next; /* next element */	     \
157  	}
158  
159  /*
160   * Singly-linked List functions.
161   */
162  #define    SLIST_EMPTY(head)    ((head)->slh_first == NULL)
163  
164  #define    SLIST_FIRST(head)    ((head)->slh_first)
165  
166  #define    SLIST_FOREACH(var, head, field)		      \
167  	for ((var) = SLIST_FIRST((head));		 \
168  	     (var);			       \
169  	     (var) = SLIST_NEXT((var), field))
170  
171  #define    SLIST_FOREACH_SAFE(var, head, field, tvar)		 \
172  	for ((var) = SLIST_FIRST((head));		 \
173  	     (var) && ((tvar) = SLIST_NEXT((var), field), 1);	     \
174  	     (var) = (tvar))
175  
176  #define    SLIST_FOREACH_PREVPTR(var, varp, head, field)	    \
177  	for ((varp) = &SLIST_FIRST((head));		   \
178  	     ((var) = *(varp)) != NULL;			   \
179  	     (varp) = &SLIST_NEXT((var), field))
180  
181  #define    SLIST_INIT(head) do {			\
182  		SLIST_FIRST((head)) = NULL;		       \
183  } while (0)
184  
185  #define    SLIST_INSERT_AFTER(slistelm, elm, field) do {	    \
186  		SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);    \
187  		SLIST_NEXT((slistelm), field) = (elm);		      \
188  } while (0)
189  
190  #define    SLIST_INSERT_HEAD(head, elm, field) do {	       \
191  		SLIST_NEXT((elm), field) = SLIST_FIRST((head));		   \
192  		SLIST_FIRST((head)) = (elm);			\
193  } while (0)
194  
195  #define    SLIST_NEXT(elm, field)    ((elm)->field.sle_next)
196  
197  #define    SLIST_REMOVE(head, elm, type, field) do {		\
198  		if (SLIST_FIRST((head)) == (elm)) {		   \
199  			SLIST_REMOVE_HEAD((head), field);	     \
200  		}				 \
201  		else {				      \
202  			struct type *curelm = SLIST_FIRST((head));	  \
203  			while (SLIST_NEXT(curelm, field) != (elm))	  \
204  				curelm = SLIST_NEXT(curelm, field);	   \
205  			SLIST_NEXT(curelm, field) =		   \
206  				SLIST_NEXT(SLIST_NEXT(curelm, field), field);\
207  		}				 \
208  } while (0)
209  
210  #define    SLIST_REMOVE_HEAD(head, field) do {		      \
211  		SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)),	\
212  						 field);	 \
213  } while (0)
214  
215  /*
216   * Singly-linked Tail queue declarations.
217   */
218  #define    STAILQ_HEAD(name, type)			  \
219  	struct name {				     \
220  		struct type *stqh_first;		\
221  		struct type **stqh_last;	 \
222  	}
223  
224  #define    STAILQ_HEAD_INITIALIZER(head)		    \
225  	{ NULL, &(head).stqh_first }
226  
227  #define    STAILQ_ENTRY(type)			     \
228  	struct {				\
229  		struct type *stqe_next; /* next element */	      \
230  	}
231  
232  /*
233   * Singly-linked Tail queue functions.
234   */
235  #define    STAILQ_CONCAT(head1, head2) do {		   \
236  		if (!STAILQ_EMPTY((head2))) {			 \
237  			*(head1)->stqh_last = (head2)->stqh_first;	  \
238  			(head1)->stqh_last = (head2)->stqh_last;	\
239  			STAILQ_INIT((head2));			 \
240  		}				 \
241  } while (0)
242  
243  #define    STAILQ_EMPTY(head)    ((head)->stqh_first == NULL)
244  
245  #define    STAILQ_FIRST(head)    ((head)->stqh_first)
246  
247  #define    STAILQ_FOREACH(var, head, field)		   \
248  	for ((var) = STAILQ_FIRST((head));		 \
249  	    (var);			      \
250  	    (var) = STAILQ_NEXT((var), field))
251  
252  #define    STAILQ_FOREACH_SAFE(var, head, field, tvar)		  \
253  	for ((var) = STAILQ_FIRST((head));		  \
254  	     (var) && ((tvar) = STAILQ_NEXT((var), field), 1);	      \
255  	     (var) = (tvar))
256  
257  #define    STAILQ_INIT(head) do {			 \
258  		STAILQ_FIRST((head)) = NULL;			\
259  		(head)->stqh_last = &STAILQ_FIRST((head));	      \
260  } while (0)
261  
262  #define    STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {	    \
263  		if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm),	\
264  							     field)) == NULL) \
265  			(head)->stqh_last = &STAILQ_NEXT((elm), field);	       \
266  		STAILQ_NEXT((tqelm), field) = (elm);		    \
267  } while (0)
268  
269  #define    STAILQ_INSERT_HEAD(head, elm, field) do {		\
270  		if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == \
271  		    NULL)	\
272  			(head)->stqh_last = &STAILQ_NEXT((elm), field);	       \
273  		STAILQ_FIRST((head)) = (elm);			 \
274  } while (0)
275  
276  #define    STAILQ_INSERT_TAIL(head, elm, field) do {		\
277  		STAILQ_NEXT((elm), field) = NULL;		 \
278  		*(head)->stqh_last = (elm);		       \
279  		(head)->stqh_last = &STAILQ_NEXT((elm), field);		   \
280  } while (0)
281  
282  #define    STAILQ_LAST(head, type, field)		     \
283  	(STAILQ_EMPTY((head)) ?			       \
284  	 NULL :				   \
285  	 ((struct type *)		     \
286  	  ((char *)((head)->stqh_last) - __offsetof(struct type, field))))
287  
288  #define    STAILQ_NEXT(elm, field)    ((elm)->field.stqe_next)
289  
290  #define    STAILQ_REMOVE(head, elm, type, field) do {		 \
291  		if (STAILQ_FIRST((head)) == (elm)) {		    \
292  			STAILQ_REMOVE_HEAD((head), field);	      \
293  		}				 \
294  		else {				      \
295  			struct type *curelm = STAILQ_FIRST((head));	   \
296  			while (STAILQ_NEXT(curelm, field) != (elm))	   \
297  				curelm = STAILQ_NEXT(curelm, field);	    \
298  			if ((STAILQ_NEXT(curelm, field) =	     \
299  				     STAILQ_NEXT(STAILQ_NEXT(curelm, field), \
300  						 field)) == NULL) \
301  				(head)->stqh_last = &STAILQ_NEXT((curelm),\
302  								 field); \
303  		}				 \
304  } while (0)
305  
306  #define    STAILQ_REMOVE_AFTER(head, elm, field) do {		 \
307  		if (STAILQ_NEXT(elm, field)) {	      \
308  			if ((STAILQ_NEXT(elm, field) =		  \
309  				     STAILQ_NEXT(STAILQ_NEXT(elm, field), \
310  							     field)) == NULL) \
311  				(head)->stqh_last =		\
312  					&STAILQ_NEXT((elm), field);	\
313  		}				 \
314  } while (0)
315  
316  #define    STAILQ_REMOVE_HEAD(head, field) do {		       \
317  		if ((STAILQ_FIRST((head)) =		       \
318  			     STAILQ_NEXT(STAILQ_FIRST((head)), field)) == \
319  									NULL)\
320  			(head)->stqh_last = &STAILQ_FIRST((head));	  \
321  } while (0)
322  
323  #define    STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {	      \
324  		if ((STAILQ_FIRST((head)) =		\
325  				STAILQ_NEXT((elm), field)) == NULL)	   \
326  			(head)->stqh_last = &STAILQ_FIRST((head));	  \
327  } while (0)
328  
329  /*
330   * List declarations.
331   */
332  #define    ATH_LIST_HEAD(name, type)			\
333  	struct name {				     \
334  		struct type *lh_first;	      \
335  	}
336  
337  #ifndef LIST_HEAD
338  #define LIST_HEAD ATH_LIST_HEAD
339  #endif
340  
341  #define    LIST_HEAD_INITIALIZER(head)			  \
342  	{ NULL }
343  
344  #define    LIST_ENTRY(type)			   \
345  	struct {				\
346  		struct type *le_next;		\
347  		struct type **le_prev;		\
348  	}
349  
350  /*
351   * List functions.
352   */
353  
354  #define    LIST_EMPTY(head)    ((head)->lh_first == NULL)
355  
356  #define    LIST_FIRST(head)    ((head)->lh_first)
357  
358  #define    LIST_FOREACH(var, head, field)		     \
359  	for ((var) = LIST_FIRST((head));		\
360  	     (var);			       \
361  	     (var) = LIST_NEXT((var), field))
362  
363  #define    LIST_FOREACH_SAFE(var, head, field, tvar)		\
364  	for ((var) = LIST_FIRST((head));		\
365  	     (var) && ((tvar) = LIST_NEXT((var), field), 1);	    \
366  	     (var) = (tvar))
367  
368  #define    LIST_INIT(head) do {			       \
369  		LIST_FIRST((head)) = NULL;		      \
370  } while (0)
371  
372  #define    LIST_INSERT_AFTER(listelm, elm, field) do {		  \
373  		if ((LIST_NEXT((elm), field) =		\
374  					LIST_NEXT((listelm), field)) != NULL) \
375  			LIST_NEXT((listelm), field)->field.le_prev =	    \
376  				&LIST_NEXT((elm), field);		 \
377  		LIST_NEXT((listelm), field) = (elm);		    \
378  		(elm)->field.le_prev = &LIST_NEXT((listelm), field);	    \
379  } while (0)
380  
381  #define    LIST_INSERT_BEFORE(listelm, elm, field) do {		   \
382  		(elm)->field.le_prev = (listelm)->field.le_prev;	\
383  		LIST_NEXT((elm), field) = (listelm);		    \
384  		*(listelm)->field.le_prev = (elm);		  \
385  		(listelm)->field.le_prev = &LIST_NEXT((elm), field);	    \
386  } while (0)
387  
388  #define    LIST_INSERT_HEAD(head, elm, field) do {		  \
389  		if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)    \
390  			LIST_FIRST((head))->field.le_prev =		\
391  						&LIST_NEXT((elm), field); \
392  		LIST_FIRST((head)) = (elm);		       \
393  		(elm)->field.le_prev = &LIST_FIRST((head));	       \
394  } while (0)
395  
396  #define    LIST_NEXT(elm, field)    ((elm)->field.le_next)
397  
398  #define    LIST_REMOVE(elm, field) do {			   \
399  		if (LIST_NEXT((elm), field) != NULL)		    \
400  			LIST_NEXT((elm), field)->field.le_prev =	 \
401  				(elm)->field.le_prev;		     \
402  		*(elm)->field.le_prev = LIST_NEXT((elm), field);	\
403  } while (0)
404  
405  /*
406   * Tail queue declarations.
407   */
408  #ifndef TRACE_TX_LEAK
409  #define TRACE_TX_LEAK 0
410  #endif
411  
412  #if TRACE_TX_LEAK
413  #define  HEADNAME        char   headname[64];
414  #define  COPY_HEADNAME(head)  OS_MEMCPY((head)->headname, #head, sizeof(#head))
415  #else
416  #define  HEADNAME
417  #define  COPY_HEADNAME(head)
418  #endif
419  
420  #define    TAILQ_HEAD(name, type)			 \
421  	struct name {				     \
422  		struct type *tqh_first;	       \
423  		struct type **tqh_last; 	\
424  		HEADNAME			\
425  			TRACEBUF			    \
426  	}
427  
428  #define    TAILQ_HEAD_INITIALIZER(head)			   \
429  	{ NULL, &(head).tqh_first }
430  
431  #define    TAILQ_ENTRY(type)			    \
432  	struct {				\
433  		struct type *tqe_next;		\
434  		struct type **tqe_prev;		\
435  		TRACEBUF			    \
436  	}
437  
438  /*
439   * Tail queue functions.
440   */
441  
442  #define    TAILQ_EMPTY(head)    ((head)->tqh_first == NULL)
443  
444  #define    TAILQ_FIRST(head)    ((head)->tqh_first)
445  
446  #define    TAILQ_FOREACH(var, head, field)		      \
447  	for ((var) = TAILQ_FIRST((head));		 \
448  	     (var);			       \
449  	     (var) = TAILQ_NEXT((var), field))
450  
451  #define    TAILQ_FOREACH_SAFE(var, head, field, tvar)		 \
452  	for ((var) = TAILQ_FIRST((head));		 \
453  	     (var) && ((tvar) = TAILQ_NEXT((var), field), 1);	     \
454  	     (var) = (tvar))
455  
456  #define    TAILQ_FOREACH_REVERSE(var, head, headname, field)	    \
457  	for ((var) = TAILQ_LAST((head), headname);	      \
458  	     (var);			       \
459  	     (var) = TAILQ_PREV((var), headname, field))
460  
461  #define    TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	   \
462  	for ((var) = TAILQ_LAST((head), headname);	      \
463  	     (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);	   \
464  	     (var) = (tvar))
465  
466  #define    TAILQ_INIT(head) do {			\
467  		TAILQ_FIRST((head)) = NULL;		       \
468  		(head)->tqh_last = &TAILQ_FIRST((head));	    \
469  		COPY_HEADNAME(head);			     \
470  		QMD_TRACE_HEAD(head);			     \
471  } while (0)
472  
473  #define    TAILQ_INSERT_AFTER(head, listelm, elm, field) do {	     \
474  		if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), \
475  		     field)) != NULL) \
476  			TAILQ_NEXT((elm), field)->field.tqe_prev =	   \
477  				&TAILQ_NEXT((elm), field);		  \
478  		else {				      \
479  			(head)->tqh_last = &TAILQ_NEXT((elm), field);	     \
480  			QMD_TRACE_HEAD(head);			 \
481  		}				 \
482  		TAILQ_NEXT((listelm), field) = (elm);		     \
483  		(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);	      \
484  		QMD_TRACE_ELEM(&(elm)->field);			  \
485  		QMD_TRACE_ELEM(&listelm->field);		\
486  } while (0)
487  
488  #define    TAILQ_INSERT_BEFORE(listelm, elm, field) do {	    \
489  		(elm)->field.tqe_prev = (listelm)->field.tqe_prev;	  \
490  		TAILQ_NEXT((elm), field) = (listelm);		     \
491  		*(listelm)->field.tqe_prev = (elm);		   \
492  		(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);	      \
493  		QMD_TRACE_ELEM(&(elm)->field);			  \
494  		QMD_TRACE_ELEM(&listelm->field);		\
495  } while (0)
496  
497  #define    TAILQ_INSERT_HEAD(head, elm, field) do {	       \
498  		if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)\
499  			TAILQ_FIRST((head))->field.tqe_prev =		 \
500  				&TAILQ_NEXT((elm), field);		  \
501  		else				    \
502  			(head)->tqh_last = &TAILQ_NEXT((elm), field);	     \
503  		TAILQ_FIRST((head)) = (elm);			\
504  		(elm)->field.tqe_prev = &TAILQ_FIRST((head));		 \
505  		QMD_TRACE_HEAD(head);			     \
506  		QMD_TRACE_ELEM(&(elm)->field);			  \
507  } while (0)
508  
509  #define    TAILQ_INSERT_TAIL(head, elm, field) do {	       \
510  		TAILQ_NEXT((elm), field) = NULL;		\
511  		(elm)->field.tqe_prev = (head)->tqh_last;	     \
512  		*(head)->tqh_last = (elm);		      \
513  		(head)->tqh_last = &TAILQ_NEXT((elm), field);		 \
514  		QMD_TRACE_HEAD(head);			     \
515  		QMD_TRACE_ELEM(&(elm)->field);			  \
516  } while (0)
517  
518  #define    TAILQ_LAST(head, headname)			 \
519  	(*(((struct headname *)((head)->tqh_last))->tqh_last))
520  
521  #define    TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
522  
523  #define    TAILQ_PREV(elm, headname, field)		   \
524  	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
525  
526  #define    TAILQ_REMOVE(head, elm, field) do {		      \
527  		if ((TAILQ_NEXT((elm), field)) != NULL)		       \
528  			TAILQ_NEXT((elm), field)->field.tqe_prev =	   \
529  				(elm)->field.tqe_prev;		      \
530  		else {				      \
531  			(head)->tqh_last = (elm)->field.tqe_prev;	 \
532  			QMD_TRACE_HEAD(head);			 \
533  		}				 \
534  		*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);	  \
535  		TRASHIT((elm)->field.tqe_next);			   \
536  		TRASHIT((elm)->field.tqe_prev);			   \
537  		QMD_TRACE_ELEM(&(elm)->field);			  \
538  } while (0)
539  
540  #define TAILQ_CONCAT(head1, head2, field)  do {			 \
541  		if (!TAILQ_EMPTY(head2)) {			\
542  			*(head1)->tqh_last = (head2)->tqh_first;	\
543  			(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;\
544  			(head1)->tqh_last  = (head2)->tqh_last;		\
545  			TAILQ_INIT((head2));				\
546  		}						\
547  } while (0)
548  
549  #ifdef _KERNEL
550  
551  /*
552   * XXX insque() and remque() are an old way of handling certain queues.
553   * They bogusly assumes that all queue heads look alike.
554   */
555  
556  struct quehead {
557  	struct quehead *qh_link;
558  	struct quehead *qh_rlink;
559  };
560  
561  #if defined(__GNUC__) || defined(__INTEL_COMPILER)
562  
insque(void * a,void * b)563  static inline void insque(void *a, void *b)
564  {
565  	struct quehead *element = (struct quehead *)a,
566  	*head = (struct quehead *)b;
567  
568  	element->qh_link = head->qh_link;
569  	element->qh_rlink = head;
570  	head->qh_link = element;
571  	element->qh_link->qh_rlink = element;
572  }
573  
remque(void * a)574  static inline void remque(void *a)
575  {
576  	struct quehead *element = (struct quehead *)a;
577  
578  	element->qh_link->qh_rlink = element->qh_rlink;
579  	element->qh_rlink->qh_link = element->qh_link;
580  	element->qh_rlink = 0;
581  }
582  
583  #else                           /* !(__GNUC__ || __INTEL_COMPILER) */
584  
585  void insque(void *a, void *b);
586  void remque(void *a);
587  
588  #endif /* __GNUC__ || __INTEL_COMPILER */
589  
590  #endif /* _KERNEL */
591  
592  #endif /* _QUEUE_H_ */
593