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  * © * © * Portions Copyright (c) 2007 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.

    29  *	@(#)queue.h	8.5 (Berkeley) 8/20/94

    30  * $FreeBSD: src/sys/sys/queue.h,v 1.60.2.1 2005/08/16 22:41:39 phk Exp $

    31  */

    32 

    33 #ifndef _SYS_QUEUE_H_

    34 #define	_SYS_QUEUE_H_

    35 

    36 #include <sys/cdefs.h>

    37 

    38 /*

    39  * This file defines four types of data structures: singly-linked lists,

    40  * singly-linked tail queues, lists and tail queues.

    41  *

    42  * A singly-linked list is headed by a single forward pointer. The elements

    43  * are singly linked for minimum space and pointer manipulation overhead at

    44  * the expense of O(n) removal for arbitrary elements. New elements can be

    45  * added to the list after an existing element or at the head of the list.

    46  * Elements being removed from the head of the list should use the explicit

    47  * macro for this purpose for optimum efficiency. A singly-linked list may

    48  * only be traversed in the forward direction.  Singly-linked lists are ideal

    49  * for applications with large datasets and few or no removals or for

    50  * implementing a LIFO queue.

    51  *

    52  * A singly-linked tail queue is headed by a pair of pointers, one to the

    53  * head of the list and the other to the tail of the list. The elements are

    54  * singly linked for minimum space and pointer manipulation overhead at the

    55  * expense of O(n) removal for arbitrary elements. New elements can be added

    56  * to the list after an existing element, at the head of the list, or at the

    57  * end of the list. Elements being removed from the head of the tail queue

    58  * should use the explicit macro for this purpose for optimum efficiency.

    59  * A singly-linked tail queue may only be traversed in the forward direction.

    60  * Singly-linked tail queues are ideal for applications with large datasets

    61  * and few or no removals or for implementing a FIFO queue.

    62  *

    63  * A list is headed by a single forward pointer (or an array of forward

    64  * pointers for a hash table header). The elements are doubly linked

    65  * so that an arbitrary element can be removed without a need to

    66  * traverse the list. New elements can be added to the list before

    67  * or after an existing element or at the head of the list. A list

    68  * may only be traversed in the forward direction.

    69  *

    70  * A tail queue is headed by a pair of pointers, one to the head of the

    71  * list and the other to the tail of the list. The elements are doubly

    72  * linked so that an arbitrary element can be removed without a need to

    73  * traverse the list. New elements can be added to the list before or

    74  * after an existing element, at the head of the list, or at the end of

    75  * the list. A tail queue may be traversed in either direction.

    76  *

    77  * For details on the use of these macros, see the queue(3) manual page.

    78  *

    79  *

    80  *				SLIST	LIST	STAILQ	TAILQ

    81  * _HEAD			+	+	+	+

    82  * _HEAD_INITIALIZER		+	+	+	+

    83  * _ENTRY			+	+	+	+

    84  * _INIT			+	+	+	+

    85  * _EMPTY			+	+	+	+

    86  * _FIRST			+	+	+	+

    87  * _NEXT			+	+	+	+

    88  * _PREV			-	-	-	+

    89  * _LAST			-	-	+	+

    90  * _FOREACH			+	+	+	+

    91  * _FOREACH_SAFE		+	+	+	+

    92  * _FOREACH_REVERSE		-	-	-	+

    93  * _FOREACH_REVERSE_SAFE	-	-	-	+

    94  * _INSERT_HEAD			+	+	+	+

    95  * _INSERT_BEFORE		-	+	-	+

    96  * _INSERT_AFTER		+	+	+	+

    97  * _INSERT_TAIL			-	-	+	+

    98  * _CONCAT			-	-	+	+

    99  * _REMOVE_HEAD			+	-	+	-

   100  * _REMOVE			+	+	+	+

   101  *

   102  */

   103 #define	QUEUE_MACRO_DEBUG 0

   104 #if 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 } while (0)

   203 

   204 #define	SLIST_REMOVE_HEAD(head, field) do {				\

   205 	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\

   206 } while (0)

   207 

   208 /*

   209  * Singly-linked Tail queue declarations.

   210  */

   211 #define	STAILQ_HEAD(name, type)						\

   212 struct name {								\

   213 	struct type *stqh_first;/* first element */			\

   214 	struct type **stqh_last;/* addr of last next element */		\

   215 }

   216 

   217 #define	STAILQ_HEAD_INITIALIZER(head)					\

   218 	{ NULL, &(head).stqh_first }

   219 

   220 #define	STAILQ_ENTRY(type)						\

   221 struct {								\

   222 	struct type *stqe_next;	/* next element */			\

   223 }

   224 

   225 /*

   226  * Singly-linked Tail queue functions.

   227  */

   228 #define	STAILQ_CONCAT(head1, head2) do {				\

   229 	if (!STAILQ_EMPTY((head2))) {					\

   230 		*(head1)->stqh_last = (head2)->stqh_first;		\

   231 		(head1)->stqh_last = (head2)->stqh_last;		\

   232 		STAILQ_INIT((head2));					\

   233 	}								\

   234 } while (0)

   235 

   236 #define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)

   237 

   238 #define	STAILQ_FIRST(head)	((head)->stqh_first)

   239 

   240 #define	STAILQ_FOREACH(var, head, field)				\

   241 	for((var) = STAILQ_FIRST((head));				\

   242 	   (var);							\

   243 	   (var) = STAILQ_NEXT((var), field))

   244 

   245 

   246 #define	STAILQ_FOREACH_SAFE(var, head, field, tvar)			\

   247 	for ((var) = STAILQ_FIRST((head));				\

   248 	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\

   249 	    (var) = (tvar))

   250 

   251 #define	STAILQ_INIT(head) do {						\

   252 	STAILQ_FIRST((head)) = NULL;					\

   253 	(head)->stqh_last = &STAILQ_FIRST((head));			\

   254 } while (0)

   255 

   256 #define	STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\

   257 	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\

   258 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\

   259 	STAILQ_NEXT((tqelm), field) = (elm);				\

   260 } while (0)

   261 

   262 #define	STAILQ_INSERT_HEAD(head, elm, field) do {			\

   263 	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)	\

   264 		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\

   265 	STAILQ_FIRST((head)) = (elm);					\

   266 } while (0)

   267 

   268 #define	STAILQ_INSERT_TAIL(head, elm, field) do {			\

   269 	STAILQ_NEXT((elm), field) = NULL;				\

   270 	*(head)->stqh_last = (elm);					\

   271 	(head)->stqh_last = &STAILQ_NEXT((elm), field);			\

   272 } while (0)

   273 

   274 #define	STAILQ_LAST(head, type, field)					\

   275 	(STAILQ_EMPTY((head)) ?						\

   276 		NULL :							\

   277 	        ((struct type *)					\

   278 		((char *)((head)->stqh_last) - __offsetof(struct type, field))))

   279 

   280 #define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)

   281 

   282 #define	STAILQ_REMOVE(head, elm, type, field) do {			\

   283 	if (STAILQ_FIRST((head)) == (elm)) {				\

   284 		STAILQ_REMOVE_HEAD((head), field);			\

   285 	}								\

   286 	else {								\

   287 		struct type *curelm = STAILQ_FIRST((head));		\

   288 		while (STAILQ_NEXT(curelm, field) != (elm))		\

   289 			curelm = STAILQ_NEXT(curelm, field);		\

   290 		if ((STAILQ_NEXT(curelm, field) =			\

   291 		     STAILQ_NEXT(STAILQ_NEXT(curelm, field), field)) == NULL)\

   292 			(head)->stqh_last = &STAILQ_NEXT((curelm), field);\

   293 	}								\

   294 } while (0)

   295 

   296 #define	STAILQ_REMOVE_HEAD(head, field) do {				\

   297 	if ((STAILQ_FIRST((head)) =					\

   298 	     STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)		\

   299 		(head)->stqh_last = &STAILQ_FIRST((head));		\

   300 } while (0)

   301 

   302 #define	STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {			\

   303 	if ((STAILQ_FIRST((head)) = STAILQ_NEXT((elm), field)) == NULL)	\

   304 		(head)->stqh_last = &STAILQ_FIRST((head));		\

   305 } while (0)

   306 

   307 /*

   308  * List declarations.

   309  */

   310 #define	LIST_HEAD(name, type)						\

   311 struct name {								\

   312 	struct type *lh_first;	/* first element */			\

   313 }

   314 

   315 #define	LIST_HEAD_INITIALIZER(head)					\

   316 	{ NULL }

   317 

   318 #define	LIST_ENTRY(type)						\

   319 struct {								\

   320 	struct type *le_next;	/* next element */			\

   321 	struct type **le_prev;	/* address of previous next element */	\

   322 }

   323 

   324 /*

   325  * List functions.

   326  */

   327 

   328 #define	LIST_EMPTY(head)	((head)->lh_first == NULL)

   329 

   330 #define	LIST_FIRST(head)	((head)->lh_first)

   331 

   332 #define	LIST_FOREACH(var, head, field)					\

   333 	for ((var) = LIST_FIRST((head));				\

   334 	    (var);							\

   335 	    (var) = LIST_NEXT((var), field))

   336 

   337 #define	LIST_FOREACH_SAFE(var, head, field, tvar)			\

   338 	for ((var) = LIST_FIRST((head));				\

   339 	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\

   340 	    (var) = (tvar))

   341 

   342 #define	LIST_INIT(head) do {						\

   343 	LIST_FIRST((head)) = NULL;					\

   344 } while (0)

   345 

   346 #define	LIST_INSERT_AFTER(listelm, elm, field) do {			\

   347 	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\

   348 		LIST_NEXT((listelm), field)->field.le_prev =		\

   349 		    &LIST_NEXT((elm), field);				\

   350 	LIST_NEXT((listelm), field) = (elm);				\

   351 	(elm)->field.le_prev = &LIST_NEXT((listelm), field);		\

   352 } while (0)

   353 

   354 #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\

   355 	(elm)->field.le_prev = (listelm)->field.le_prev;		\

   356 	LIST_NEXT((elm), field) = (listelm);				\

   357 	*(listelm)->field.le_prev = (elm);				\

   358 	(listelm)->field.le_prev = &LIST_NEXT((elm), field);		\

   359 } while (0)

   360 

   361 #define	LIST_INSERT_HEAD(head, elm, field) do {				\

   362 	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\

   363 		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);\

   364 	LIST_FIRST((head)) = (elm);					\

   365 	(elm)->field.le_prev = &LIST_FIRST((head));			\

   366 } while (0)

   367 

   368 #define	LIST_NEXT(elm, field)	((elm)->field.le_next)

   369 

   370 #define	LIST_REMOVE(elm, field) do {					\

   371 	if (LIST_NEXT((elm), field) != NULL)				\

   372 		LIST_NEXT((elm), field)->field.le_prev = 		\

   373 		    (elm)->field.le_prev;				\

   374 	*(elm)->field.le_prev = LIST_NEXT((elm), field);		\

   375 } while (0)

   376 

   377 /*

   378  * Tail queue declarations.

   379  */

   380 #define	TAILQ_HEAD(name, type)						\

   381 struct name {								\

   382 	struct type *tqh_first;	/* first element */			\

   383 	struct type **tqh_last;	/* addr of last next element */		\

   384 	TRACEBUF							\

   385 }

   386 

   387 #define	TAILQ_HEAD_INITIALIZER(head)					\

   388 	{ NULL, &(head).tqh_first }

   389 

   390 #define	TAILQ_ENTRY(type)						\

   391 struct {								\

   392 	struct type *tqe_next;	/* next element */			\

   393 	struct type **tqe_prev;	/* address of previous next element */	\

   394 	TRACEBUF							\

   395 }

   396 

   397 /*

   398  * Tail queue functions.

   399  */

   400 #define	TAILQ_CONCAT(head1, head2, field) do {				\

   401 	if (!TAILQ_EMPTY(head2)) {					\

   402 		*(head1)->tqh_last = (head2)->tqh_first;		\

   403 		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\

   404 		(head1)->tqh_last = (head2)->tqh_last;			\

   405 		TAILQ_INIT((head2));					\

   406 		QMD_TRACE_HEAD(head1);					\

   407 		QMD_TRACE_HEAD(head2);					\

   408 	}								\

   409 } while (0)

   410 

   411 #define	TAILQ_EMPTY(head)	((head)->tqh_first == NULL)

   412 

   413 #define	TAILQ_FIRST(head)	((head)->tqh_first)

   414 

   415 #define	TAILQ_FOREACH(var, head, field)					\

   416 	for ((var) = TAILQ_FIRST((head));				\

   417 	    (var);							\

   418 	    (var) = TAILQ_NEXT((var), field))

   419 

   420 #define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\

   421 	for ((var) = TAILQ_FIRST((head));				\

   422 	    (var) && ((tvar) = TAILQ_NEXT((var), field), 1);		\

   423 	    (var) = (tvar))

   424 

   425 #define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\

   426 	for ((var) = TAILQ_LAST((head), headname);			\

   427 	    (var);							\

   428 	    (var) = TAILQ_PREV((var), headname, field))

   429 

   430 #define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\

   431 	for ((var) = TAILQ_LAST((head), headname);			\

   432 	    (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);	\

   433 	    (var) = (tvar))

   434 

   435 #define	TAILQ_INIT(head) do {						\

   436 	TAILQ_FIRST((head)) = NULL;					\

   437 	(head)->tqh_last = &TAILQ_FIRST((head));			\

   438 	QMD_TRACE_HEAD(head);						\

   439 } while (0)

   440 

   441 #define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\

   442 	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\

   443 		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\

   444 		    &TAILQ_NEXT((elm), field);				\

   445 	else {								\

   446 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\

   447 		QMD_TRACE_HEAD(head);					\

   448 	}								\

   449 	TAILQ_NEXT((listelm), field) = (elm);				\

   450 	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);		\

   451 	QMD_TRACE_ELEM(&(elm)->field);					\

   452 	QMD_TRACE_ELEM(&listelm->field);				\

   453 } while (0)

   454 

   455 #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\

   456 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\

   457 	TAILQ_NEXT((elm), field) = (listelm);				\

   458 	*(listelm)->field.tqe_prev = (elm);				\

   459 	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);		\

   460 	QMD_TRACE_ELEM(&(elm)->field);					\

   461 	QMD_TRACE_ELEM(&listelm->field);				\

   462 } while (0)

   463 

   464 #define	TAILQ_INSERT_HEAD(head, elm, field) do {			\

   465 	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)	\

   466 		TAILQ_FIRST((head))->field.tqe_prev =			\

   467 		    &TAILQ_NEXT((elm), field);				\

   468 	else								\

   469 		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\

   470 	TAILQ_FIRST((head)) = (elm);					\

   471 	(elm)->field.tqe_prev = &TAILQ_FIRST((head));			\

   472 	QMD_TRACE_HEAD(head);						\

   473 	QMD_TRACE_ELEM(&(elm)->field);					\

   474 } while (0)

   475 

   476 #define	TAILQ_INSERT_TAIL(head, elm, field) do {			\

   477 	TAILQ_NEXT((elm), field) = NULL;				\

   478 	(elm)->field.tqe_prev = (head)->tqh_last;			\

   479 	*(head)->tqh_last = (elm);					\

   480 	(head)->tqh_last = &TAILQ_NEXT((elm), field);			\

   481 	QMD_TRACE_HEAD(head);						\

   482 	QMD_TRACE_ELEM(&(elm)->field);					\

   483 } while (0)

   484 

   485 #define	TAILQ_LAST(head, headname)					\

   486 	(*(((struct headname *)((head)->tqh_last))->tqh_last))

   487 

   488 #define	TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)

   489 

   490 #define	TAILQ_PREV(elm, headname, field)				\

   491 	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

   492 

   493 #define	TAILQ_REMOVE(head, elm, field) do {				\

   494 	if ((TAILQ_NEXT((elm), field)) != NULL)				\

   495 		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\

   496 		    (elm)->field.tqe_prev;				\

   497 	else {								\

   498 		(head)->tqh_last = (elm)->field.tqe_prev;		\

   499 		QMD_TRACE_HEAD(head);					\

   500 	}								\

   501 	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);		\

   502 	TRASHIT((elm)->field.tqe_next);					\

   503 	TRASHIT((elm)->field.tqe_prev);					\

   504 	QMD_TRACE_ELEM(&(elm)->field);					\

   505 } while (0)

   506 

   507 

   508 #ifdef _KERNEL

   509 

   510 /*

   511  * XXX insque() and remque() are an old way of handling certain queues.

   512  * They bogusly assumes that all queue heads look alike.

   513  */

   514 

   515 struct quehead {

   516 	struct quehead *qh_link;

   517 	struct quehead *qh_rlink;

   518 };

   519 

   520 #ifdef __CC_SUPPORTS___INLINE

   521 

   522 static __inline void

   523 insque(void *a, void *b)

   524 {

   525 	struct quehead *element = (struct quehead *)a,

   526 		 *head = (struct quehead *)b;

   527 

   528 	element->qh_link = head->qh_link;

   529 	element->qh_rlink = head;

   530 	head->qh_link = element;

   531 	element->qh_link->qh_rlink = element;

   532 }

   533 

   534 static __inline void

   535 remque(void *a)

   536 {

   537 	struct quehead *element = (struct quehead *)a;

   538 

   539 	element->qh_link->qh_rlink = element->qh_rlink;

   540 	element->qh_rlink->qh_link = element->qh_link;

   541 	element->qh_rlink = 0;

   542 }

   543 

   544 #endif /* __CC_SUPPORTS___INLINE */

   545 

   546 #endif /* _KERNEL */

   547 

   548 #endif /* !_SYS_QUEUE_H_ */