dedup

deduplicating backup program
git clone git://git.2f30.org/dedup
Log | Files | Refs | README | LICENSE

queue.h (18350B)


      1 /*	$OpenBSD: queue.h,v 1.45 2018/07/12 14:22:54 sashan Exp $	*/
      2 /*	$NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $	*/
      3 
      4 /*
      5  * Copyright (c) 1991, 1993
      6  *	The Regents of the University of California.  All rights reserved.
      7  *
      8  * Redistribution and use in source and binary forms, with or without
      9  * modification, are permitted provided that the following conditions
     10  * are met:
     11  * 1. Redistributions of source code must retain the above copyright
     12  *    notice, this list of conditions and the following disclaimer.
     13  * 2. Redistributions in binary form must reproduce the above copyright
     14  *    notice, this list of conditions and the following disclaimer in the
     15  *    documentation and/or other materials provided with the distribution.
     16  * 3. Neither the name of the University nor the names of its contributors
     17  *    may be used to endorse or promote products derived from this software
     18  *    without specific prior written permission.
     19  *
     20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     30  * SUCH DAMAGE.
     31  *
     32  *	@(#)queue.h	8.5 (Berkeley) 8/20/94
     33  */
     34 
     35 #ifndef	_SYS_QUEUE_H_
     36 #define	_SYS_QUEUE_H_
     37 
     38 /*
     39  * This file defines five types of data structures: singly-linked lists,
     40  * lists, simple queues, tail queues and XOR simple queues.
     41  *
     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 list is headed by a single forward pointer (or an array of forward
     54  * pointers for a hash table header). The elements are doubly linked
     55  * so that an arbitrary element can be removed without a need to
     56  * traverse the list. New elements can be added to the list before
     57  * or after an existing element or at the head of the list. A list
     58  * may only be traversed in the forward direction.
     59  *
     60  * A simple queue is headed by a pair of pointers, one to the head of the
     61  * list and the other to the tail of the list. The elements are singly
     62  * linked to save space, so elements can only be removed from the
     63  * head of the list. New elements can be added to the list before or after
     64  * an existing element, at the head of the list, or at the end of the
     65  * list. A simple queue may only be traversed in the forward direction.
     66  *
     67  * A tail queue is headed by a pair of pointers, one to the head of the
     68  * list and the other to the tail of the list. The elements are doubly
     69  * linked so that an arbitrary element can be removed without a need to
     70  * traverse the list. New elements can be added to the list before or
     71  * after an existing element, at the head of the list, or at the end of
     72  * the list. A tail queue may be traversed in either direction.
     73  *
     74  * An XOR simple queue is used in the same way as a regular simple queue.
     75  * The difference is that the head structure also includes a "cookie" that
     76  * is XOR'd with the queue pointer (first, last or next) to generate the
     77  * real pointer value.
     78  *
     79  * For details on the use of these macros, see the queue(3) manual page.
     80  */
     81 
     82 #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
     83 #define _Q_INVALID ((void *)-1)
     84 #define _Q_INVALIDATE(a) (a) = _Q_INVALID
     85 #else
     86 #define _Q_INVALIDATE(a)
     87 #endif
     88 
     89 /*
     90  * Singly-linked List definitions.
     91  */
     92 #define SLIST_HEAD(name, type)						\
     93 struct name {								\
     94 	struct type *slh_first;	/* first element */			\
     95 }
     96 
     97 #define	SLIST_HEAD_INITIALIZER(head)					\
     98 	{ NULL }
     99 
    100 #define SLIST_ENTRY(type)						\
    101 struct {								\
    102 	struct type *sle_next;	/* next element */			\
    103 }
    104 
    105 /*
    106  * Singly-linked List access methods.
    107  */
    108 #define	SLIST_FIRST(head)	((head)->slh_first)
    109 #define	SLIST_END(head)		NULL
    110 #define	SLIST_EMPTY(head)	(SLIST_FIRST(head) == SLIST_END(head))
    111 #define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
    112 
    113 #define	SLIST_FOREACH(var, head, field)					\
    114 	for((var) = SLIST_FIRST(head);					\
    115 	    (var) != SLIST_END(head);					\
    116 	    (var) = SLIST_NEXT(var, field))
    117 
    118 #define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
    119 	for ((var) = SLIST_FIRST(head);				\
    120 	    (var) && ((tvar) = SLIST_NEXT(var, field), 1);		\
    121 	    (var) = (tvar))
    122 
    123 /*
    124  * Singly-linked List functions.
    125  */
    126 #define	SLIST_INIT(head) {						\
    127 	SLIST_FIRST(head) = SLIST_END(head);				\
    128 }
    129 
    130 #define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
    131 	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
    132 	(slistelm)->field.sle_next = (elm);				\
    133 } while (0)
    134 
    135 #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
    136 	(elm)->field.sle_next = (head)->slh_first;			\
    137 	(head)->slh_first = (elm);					\
    138 } while (0)
    139 
    140 #define	SLIST_REMOVE_AFTER(elm, field) do {				\
    141 	(elm)->field.sle_next = (elm)->field.sle_next->field.sle_next;	\
    142 } while (0)
    143 
    144 #define	SLIST_REMOVE_HEAD(head, field) do {				\
    145 	(head)->slh_first = (head)->slh_first->field.sle_next;		\
    146 } while (0)
    147 
    148 #define SLIST_REMOVE(head, elm, type, field) do {			\
    149 	if ((head)->slh_first == (elm)) {				\
    150 		SLIST_REMOVE_HEAD((head), field);			\
    151 	} else {							\
    152 		struct type *curelm = (head)->slh_first;		\
    153 									\
    154 		while (curelm->field.sle_next != (elm))			\
    155 			curelm = curelm->field.sle_next;		\
    156 		curelm->field.sle_next =				\
    157 		    curelm->field.sle_next->field.sle_next;		\
    158 	}								\
    159 	_Q_INVALIDATE((elm)->field.sle_next);				\
    160 } while (0)
    161 
    162 /*
    163  * List definitions.
    164  */
    165 #define LIST_HEAD(name, type)						\
    166 struct name {								\
    167 	struct type *lh_first;	/* first element */			\
    168 }
    169 
    170 #define LIST_HEAD_INITIALIZER(head)					\
    171 	{ NULL }
    172 
    173 #define LIST_ENTRY(type)						\
    174 struct {								\
    175 	struct type *le_next;	/* next element */			\
    176 	struct type **le_prev;	/* address of previous next element */	\
    177 }
    178 
    179 /*
    180  * List access methods.
    181  */
    182 #define	LIST_FIRST(head)		((head)->lh_first)
    183 #define	LIST_END(head)			NULL
    184 #define	LIST_EMPTY(head)		(LIST_FIRST(head) == LIST_END(head))
    185 #define	LIST_NEXT(elm, field)		((elm)->field.le_next)
    186 
    187 #define LIST_FOREACH(var, head, field)					\
    188 	for((var) = LIST_FIRST(head);					\
    189 	    (var)!= LIST_END(head);					\
    190 	    (var) = LIST_NEXT(var, field))
    191 
    192 #define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
    193 	for ((var) = LIST_FIRST(head);				\
    194 	    (var) && ((tvar) = LIST_NEXT(var, field), 1);		\
    195 	    (var) = (tvar))
    196 
    197 /*
    198  * List functions.
    199  */
    200 #define	LIST_INIT(head) do {						\
    201 	LIST_FIRST(head) = LIST_END(head);				\
    202 } while (0)
    203 
    204 #define LIST_INSERT_AFTER(listelm, elm, field) do {			\
    205 	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
    206 		(listelm)->field.le_next->field.le_prev =		\
    207 		    &(elm)->field.le_next;				\
    208 	(listelm)->field.le_next = (elm);				\
    209 	(elm)->field.le_prev = &(listelm)->field.le_next;		\
    210 } while (0)
    211 
    212 #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
    213 	(elm)->field.le_prev = (listelm)->field.le_prev;		\
    214 	(elm)->field.le_next = (listelm);				\
    215 	*(listelm)->field.le_prev = (elm);				\
    216 	(listelm)->field.le_prev = &(elm)->field.le_next;		\
    217 } while (0)
    218 
    219 #define LIST_INSERT_HEAD(head, elm, field) do {				\
    220 	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
    221 		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
    222 	(head)->lh_first = (elm);					\
    223 	(elm)->field.le_prev = &(head)->lh_first;			\
    224 } while (0)
    225 
    226 #define LIST_REMOVE(elm, field) do {					\
    227 	if ((elm)->field.le_next != NULL)				\
    228 		(elm)->field.le_next->field.le_prev =			\
    229 		    (elm)->field.le_prev;				\
    230 	*(elm)->field.le_prev = (elm)->field.le_next;			\
    231 	_Q_INVALIDATE((elm)->field.le_prev);				\
    232 	_Q_INVALIDATE((elm)->field.le_next);				\
    233 } while (0)
    234 
    235 #define LIST_REPLACE(elm, elm2, field) do {				\
    236 	if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)	\
    237 		(elm2)->field.le_next->field.le_prev =			\
    238 		    &(elm2)->field.le_next;				\
    239 	(elm2)->field.le_prev = (elm)->field.le_prev;			\
    240 	*(elm2)->field.le_prev = (elm2);				\
    241 	_Q_INVALIDATE((elm)->field.le_prev);				\
    242 	_Q_INVALIDATE((elm)->field.le_next);				\
    243 } while (0)
    244 
    245 /*
    246  * Simple queue definitions.
    247  */
    248 #define SIMPLEQ_HEAD(name, type)					\
    249 struct name {								\
    250 	struct type *sqh_first;	/* first element */			\
    251 	struct type **sqh_last;	/* addr of last next element */		\
    252 }
    253 
    254 #define SIMPLEQ_HEAD_INITIALIZER(head)					\
    255 	{ NULL, &(head).sqh_first }
    256 
    257 #define SIMPLEQ_ENTRY(type)						\
    258 struct {								\
    259 	struct type *sqe_next;	/* next element */			\
    260 }
    261 
    262 /*
    263  * Simple queue access methods.
    264  */
    265 #define	SIMPLEQ_FIRST(head)	    ((head)->sqh_first)
    266 #define	SIMPLEQ_END(head)	    NULL
    267 #define	SIMPLEQ_EMPTY(head)	    (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
    268 #define	SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)
    269 
    270 #define SIMPLEQ_FOREACH(var, head, field)				\
    271 	for((var) = SIMPLEQ_FIRST(head);				\
    272 	    (var) != SIMPLEQ_END(head);					\
    273 	    (var) = SIMPLEQ_NEXT(var, field))
    274 
    275 #define	SIMPLEQ_FOREACH_SAFE(var, head, field, tvar)			\
    276 	for ((var) = SIMPLEQ_FIRST(head);				\
    277 	    (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1);		\
    278 	    (var) = (tvar))
    279 
    280 /*
    281  * Simple queue functions.
    282  */
    283 #define	SIMPLEQ_INIT(head) do {						\
    284 	(head)->sqh_first = NULL;					\
    285 	(head)->sqh_last = &(head)->sqh_first;				\
    286 } while (0)
    287 
    288 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
    289 	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
    290 		(head)->sqh_last = &(elm)->field.sqe_next;		\
    291 	(head)->sqh_first = (elm);					\
    292 } while (0)
    293 
    294 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
    295 	(elm)->field.sqe_next = NULL;					\
    296 	*(head)->sqh_last = (elm);					\
    297 	(head)->sqh_last = &(elm)->field.sqe_next;			\
    298 } while (0)
    299 
    300 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
    301 	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
    302 		(head)->sqh_last = &(elm)->field.sqe_next;		\
    303 	(listelm)->field.sqe_next = (elm);				\
    304 } while (0)
    305 
    306 #define SIMPLEQ_REMOVE_HEAD(head, field) do {			\
    307 	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
    308 		(head)->sqh_last = &(head)->sqh_first;			\
    309 } while (0)
    310 
    311 #define SIMPLEQ_REMOVE_AFTER(head, elm, field) do {			\
    312 	if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
    313 	    == NULL)							\
    314 		(head)->sqh_last = &(elm)->field.sqe_next;		\
    315 } while (0)
    316 
    317 #define SIMPLEQ_CONCAT(head1, head2) do {				\
    318 	if (!SIMPLEQ_EMPTY((head2))) {					\
    319 		*(head1)->sqh_last = (head2)->sqh_first;		\
    320 		(head1)->sqh_last = (head2)->sqh_last;			\
    321 		SIMPLEQ_INIT((head2));					\
    322 	}								\
    323 } while (0)
    324 
    325 /*
    326  * XOR Simple queue definitions.
    327  */
    328 #define XSIMPLEQ_HEAD(name, type)					\
    329 struct name {								\
    330 	struct type *sqx_first;	/* first element */			\
    331 	struct type **sqx_last;	/* addr of last next element */		\
    332 	unsigned long sqx_cookie;					\
    333 }
    334 
    335 #define XSIMPLEQ_ENTRY(type)						\
    336 struct {								\
    337 	struct type *sqx_next;	/* next element */			\
    338 }
    339 
    340 /*
    341  * XOR Simple queue access methods.
    342  */
    343 #define XSIMPLEQ_XOR(head, ptr)	    ((__typeof(ptr))((head)->sqx_cookie ^ \
    344 					(unsigned long)(ptr)))
    345 #define	XSIMPLEQ_FIRST(head)	    XSIMPLEQ_XOR(head, ((head)->sqx_first))
    346 #define	XSIMPLEQ_END(head)	    NULL
    347 #define	XSIMPLEQ_EMPTY(head)	    (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
    348 #define	XSIMPLEQ_NEXT(head, elm, field)    XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
    349 
    350 
    351 #define XSIMPLEQ_FOREACH(var, head, field)				\
    352 	for ((var) = XSIMPLEQ_FIRST(head);				\
    353 	    (var) != XSIMPLEQ_END(head);				\
    354 	    (var) = XSIMPLEQ_NEXT(head, var, field))
    355 
    356 #define	XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar)			\
    357 	for ((var) = XSIMPLEQ_FIRST(head);				\
    358 	    (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1);	\
    359 	    (var) = (tvar))
    360 
    361 /*
    362  * XOR Simple queue functions.
    363  */
    364 #define	XSIMPLEQ_INIT(head) do {					\
    365 	arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \
    366 	(head)->sqx_first = XSIMPLEQ_XOR(head, NULL);			\
    367 	(head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first);	\
    368 } while (0)
    369 
    370 #define XSIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
    371 	if (((elm)->field.sqx_next = (head)->sqx_first) ==		\
    372 	    XSIMPLEQ_XOR(head, NULL))					\
    373 		(head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
    374 	(head)->sqx_first = XSIMPLEQ_XOR(head, (elm));			\
    375 } while (0)
    376 
    377 #define XSIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
    378 	(elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL);		\
    379 	*(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \
    380 	(head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);	\
    381 } while (0)
    382 
    383 #define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
    384 	if (((elm)->field.sqx_next = (listelm)->field.sqx_next) ==	\
    385 	    XSIMPLEQ_XOR(head, NULL))					\
    386 		(head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
    387 	(listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm));		\
    388 } while (0)
    389 
    390 #define XSIMPLEQ_REMOVE_HEAD(head, field) do {				\
    391 	if (((head)->sqx_first = XSIMPLEQ_XOR(head,			\
    392 	    (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
    393 		(head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
    394 } while (0)
    395 
    396 #define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do {			\
    397 	if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head,			\
    398 	    (elm)->field.sqx_next)->field.sqx_next)			\
    399 	    == XSIMPLEQ_XOR(head, NULL))				\
    400 		(head)->sqx_last = 					\
    401 		    XSIMPLEQ_XOR(head, &(elm)->field.sqx_next);		\
    402 } while (0)
    403 
    404 
    405 /*
    406  * Tail queue definitions.
    407  */
    408 #define TAILQ_HEAD(name, type)						\
    409 struct name {								\
    410 	struct type *tqh_first;	/* first element */			\
    411 	struct type **tqh_last;	/* addr of last next element */		\
    412 }
    413 
    414 #define TAILQ_HEAD_INITIALIZER(head)					\
    415 	{ NULL, &(head).tqh_first }
    416 
    417 #define TAILQ_ENTRY(type)						\
    418 struct {								\
    419 	struct type *tqe_next;	/* next element */			\
    420 	struct type **tqe_prev;	/* address of previous next element */	\
    421 }
    422 
    423 /*
    424  * Tail queue access methods.
    425  */
    426 #define	TAILQ_FIRST(head)		((head)->tqh_first)
    427 #define	TAILQ_END(head)			NULL
    428 #define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
    429 #define TAILQ_LAST(head, headname)					\
    430 	(*(((struct headname *)((head)->tqh_last))->tqh_last))
    431 /* XXX */
    432 #define TAILQ_PREV(elm, headname, field)				\
    433 	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
    434 #define	TAILQ_EMPTY(head)						\
    435 	(TAILQ_FIRST(head) == TAILQ_END(head))
    436 
    437 #define TAILQ_FOREACH(var, head, field)					\
    438 	for((var) = TAILQ_FIRST(head);					\
    439 	    (var) != TAILQ_END(head);					\
    440 	    (var) = TAILQ_NEXT(var, field))
    441 
    442 #define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
    443 	for ((var) = TAILQ_FIRST(head);					\
    444 	    (var) != TAILQ_END(head) &&					\
    445 	    ((tvar) = TAILQ_NEXT(var, field), 1);			\
    446 	    (var) = (tvar))
    447 
    448 
    449 #define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
    450 	for((var) = TAILQ_LAST(head, headname);				\
    451 	    (var) != TAILQ_END(head);					\
    452 	    (var) = TAILQ_PREV(var, headname, field))
    453 
    454 #define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
    455 	for ((var) = TAILQ_LAST(head, headname);			\
    456 	    (var) != TAILQ_END(head) &&					\
    457 	    ((tvar) = TAILQ_PREV(var, headname, field), 1);		\
    458 	    (var) = (tvar))
    459 
    460 /*
    461  * Tail queue functions.
    462  */
    463 #define	TAILQ_INIT(head) do {						\
    464 	(head)->tqh_first = NULL;					\
    465 	(head)->tqh_last = &(head)->tqh_first;				\
    466 } while (0)
    467 
    468 #define TAILQ_INSERT_HEAD(head, elm, field) do {			\
    469 	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
    470 		(head)->tqh_first->field.tqe_prev =			\
    471 		    &(elm)->field.tqe_next;				\
    472 	else								\
    473 		(head)->tqh_last = &(elm)->field.tqe_next;		\
    474 	(head)->tqh_first = (elm);					\
    475 	(elm)->field.tqe_prev = &(head)->tqh_first;			\
    476 } while (0)
    477 
    478 #define TAILQ_INSERT_TAIL(head, elm, field) do {			\
    479 	(elm)->field.tqe_next = NULL;					\
    480 	(elm)->field.tqe_prev = (head)->tqh_last;			\
    481 	*(head)->tqh_last = (elm);					\
    482 	(head)->tqh_last = &(elm)->field.tqe_next;			\
    483 } while (0)
    484 
    485 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
    486 	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
    487 		(elm)->field.tqe_next->field.tqe_prev =			\
    488 		    &(elm)->field.tqe_next;				\
    489 	else								\
    490 		(head)->tqh_last = &(elm)->field.tqe_next;		\
    491 	(listelm)->field.tqe_next = (elm);				\
    492 	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
    493 } while (0)
    494 
    495 #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
    496 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
    497 	(elm)->field.tqe_next = (listelm);				\
    498 	*(listelm)->field.tqe_prev = (elm);				\
    499 	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
    500 } while (0)
    501 
    502 #define TAILQ_REMOVE(head, elm, field) do {				\
    503 	if (((elm)->field.tqe_next) != NULL)				\
    504 		(elm)->field.tqe_next->field.tqe_prev =			\
    505 		    (elm)->field.tqe_prev;				\
    506 	else								\
    507 		(head)->tqh_last = (elm)->field.tqe_prev;		\
    508 	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
    509 	_Q_INVALIDATE((elm)->field.tqe_prev);				\
    510 	_Q_INVALIDATE((elm)->field.tqe_next);				\
    511 } while (0)
    512 
    513 #define TAILQ_REPLACE(head, elm, elm2, field) do {			\
    514 	if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)	\
    515 		(elm2)->field.tqe_next->field.tqe_prev =		\
    516 		    &(elm2)->field.tqe_next;				\
    517 	else								\
    518 		(head)->tqh_last = &(elm2)->field.tqe_next;		\
    519 	(elm2)->field.tqe_prev = (elm)->field.tqe_prev;			\
    520 	*(elm2)->field.tqe_prev = (elm2);				\
    521 	_Q_INVALIDATE((elm)->field.tqe_prev);				\
    522 	_Q_INVALIDATE((elm)->field.tqe_next);				\
    523 } while (0)
    524 
    525 #define TAILQ_CONCAT(head1, head2, field) do {				\
    526 	if (!TAILQ_EMPTY(head2)) {					\
    527 		*(head1)->tqh_last = (head2)->tqh_first;		\
    528 		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
    529 		(head1)->tqh_last = (head2)->tqh_last;			\
    530 		TAILQ_INIT((head2));					\
    531 	}								\
    532 } while (0)
    533 
    534 #endif	/* !_SYS_QUEUE_H_ */