pkgtools

morpheus pkg tools
git clone git://git.2f30.org/pkgtools
Log | Files | Refs | README | LICENSE

queue.h (19539B)


      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 #ifndef	_SYS_QUEUE_H_
     33 #define	_SYS_QUEUE_H_
     34 
     35 /*
     36  * This file defines five types of data structures: singly-linked lists,
     37  * lists, simple queues, tail queues, and circular queues.
     38  *
     39  * A singly-linked list is headed by a single forward pointer. The
     40  * elements are singly linked for minimum space and pointer manipulation
     41  * overhead at the expense of O(n) removal for arbitrary elements. New
     42  * elements can be added to the list after an existing element or at the
     43  * head of the list.  Elements being removed from the head of the list
     44  * should use the explicit macro for this purpose for optimum
     45  * efficiency. A singly-linked list may only be traversed in the forward
     46  * direction.  Singly-linked lists are ideal for applications with large
     47  * datasets and few or no removals or for implementing a LIFO queue.
     48  *
     49  * A list is headed by a single forward pointer (or an array of forward
     50  * pointers for a hash table header). The elements are doubly linked
     51  * so that an arbitrary element can be removed without a need to
     52  * traverse the list. New elements can be added to the list before
     53  * or after an existing element or at the head of the list. A list
     54  * may only be traversed in the forward direction.
     55  *
     56  * A simple queue is headed by a pair of pointers, one the head of the
     57  * list and the other to the tail of the list. The elements are singly
     58  * linked to save space, so elements can only be removed from the
     59  * head of the list. New elements can be added to the list after
     60  * an existing element, at the head of the list, or at the end of the
     61  * list. A simple queue may only be traversed in the forward direction.
     62  *
     63  * A tail queue is headed by a pair of pointers, one to the head of the
     64  * list and the other to the tail of the list. The elements are doubly
     65  * linked 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 or
     67  * after an existing element, at the head of the list, or at the end of
     68  * the list. A tail queue may be traversed in either direction.
     69  *
     70  * A circle 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 after
     74  * an existing element, at the head of the list, or at the end of the list.
     75  * A circle queue may be traversed in either direction, but has a more
     76  * complex end of list detection.
     77  *
     78  * For details on the use of these macros, see the queue(3) manual page.
     79  */
     80 
     81 /*
     82  * List definitions.
     83  */
     84 #define	LIST_HEAD(name, type)						\
     85 struct name {								\
     86 	struct type *lh_first;	/* first element */			\
     87 }
     88 
     89 #define	LIST_HEAD_INITIALIZER(head)					\
     90 	{ NULL }
     91 
     92 #define	LIST_ENTRY(type)						\
     93 struct {								\
     94 	struct type *le_next;	/* next element */			\
     95 	struct type **le_prev;	/* address of previous next element */	\
     96 }
     97 
     98 /*
     99  * List functions.
    100  */
    101 #define	LIST_INIT(head) do {						\
    102 	(head)->lh_first = NULL;					\
    103 } while (/*CONSTCOND*/0)
    104 
    105 #define	LIST_INSERT_AFTER(listelm, elm, field) do {			\
    106 	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
    107 		(listelm)->field.le_next->field.le_prev =		\
    108 		    &(elm)->field.le_next;				\
    109 	(listelm)->field.le_next = (elm);				\
    110 	(elm)->field.le_prev = &(listelm)->field.le_next;		\
    111 } while (/*CONSTCOND*/0)
    112 
    113 #define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
    114 	(elm)->field.le_prev = (listelm)->field.le_prev;		\
    115 	(elm)->field.le_next = (listelm);				\
    116 	*(listelm)->field.le_prev = (elm);				\
    117 	(listelm)->field.le_prev = &(elm)->field.le_next;		\
    118 } while (/*CONSTCOND*/0)
    119 
    120 #define	LIST_INSERT_HEAD(head, elm, field) do {				\
    121 	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
    122 		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
    123 	(head)->lh_first = (elm);					\
    124 	(elm)->field.le_prev = &(head)->lh_first;			\
    125 } while (/*CONSTCOND*/0)
    126 
    127 #define	LIST_REMOVE(elm, field) do {					\
    128 	if ((elm)->field.le_next != NULL)				\
    129 		(elm)->field.le_next->field.le_prev = 			\
    130 		    (elm)->field.le_prev;				\
    131 	*(elm)->field.le_prev = (elm)->field.le_next;			\
    132 } while (/*CONSTCOND*/0)
    133 
    134 #define	LIST_FOREACH(var, head, field)					\
    135 	for ((var) = ((head)->lh_first);				\
    136 		(var);							\
    137 		(var) = ((var)->field.le_next))
    138 
    139 /*
    140  * List access methods.
    141  */
    142 #define	LIST_EMPTY(head)		((head)->lh_first == NULL)
    143 #define	LIST_FIRST(head)		((head)->lh_first)
    144 #define	LIST_NEXT(elm, field)		((elm)->field.le_next)
    145 
    146 
    147 /*
    148  * Singly-linked List definitions.
    149  */
    150 #define	SLIST_HEAD(name, type)						\
    151 struct name {								\
    152 	struct type *slh_first;	/* first element */			\
    153 }
    154 
    155 #define	SLIST_HEAD_INITIALIZER(head)					\
    156 	{ NULL }
    157 
    158 #define	SLIST_ENTRY(type)						\
    159 struct {								\
    160 	struct type *sle_next;	/* next element */			\
    161 }
    162 
    163 /*
    164  * Singly-linked List functions.
    165  */
    166 #define	SLIST_INIT(head) do {						\
    167 	(head)->slh_first = NULL;					\
    168 } while (/*CONSTCOND*/0)
    169 
    170 #define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
    171 	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
    172 	(slistelm)->field.sle_next = (elm);				\
    173 } while (/*CONSTCOND*/0)
    174 
    175 #define	SLIST_INSERT_HEAD(head, elm, field) do {			\
    176 	(elm)->field.sle_next = (head)->slh_first;			\
    177 	(head)->slh_first = (elm);					\
    178 } while (/*CONSTCOND*/0)
    179 
    180 #define	SLIST_REMOVE_HEAD(head, field) do {				\
    181 	(head)->slh_first = (head)->slh_first->field.sle_next;		\
    182 } while (/*CONSTCOND*/0)
    183 
    184 #define	SLIST_REMOVE(head, elm, type, field) do {			\
    185 	if ((head)->slh_first == (elm)) {				\
    186 		SLIST_REMOVE_HEAD((head), field);			\
    187 	}								\
    188 	else {								\
    189 		struct type *curelm = (head)->slh_first;		\
    190 		while(curelm->field.sle_next != (elm))			\
    191 			curelm = curelm->field.sle_next;		\
    192 		curelm->field.sle_next =				\
    193 		    curelm->field.sle_next->field.sle_next;		\
    194 	}								\
    195 } while (/*CONSTCOND*/0)
    196 
    197 #define	SLIST_FOREACH(var, head, field)					\
    198 	for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
    199 
    200 /*
    201  * Singly-linked List access methods.
    202  */
    203 #define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
    204 #define	SLIST_FIRST(head)	((head)->slh_first)
    205 #define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
    206 
    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_INIT(head) do {						\
    229 	(head)->stqh_first = NULL;					\
    230 	(head)->stqh_last = &(head)->stqh_first;				\
    231 } while (/*CONSTCOND*/0)
    232 
    233 #define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
    234 	if (((elm)->field.stqe_next = (head)->stqh_first) == NULL)	\
    235 		(head)->stqh_last = &(elm)->field.stqe_next;		\
    236 	(head)->stqh_first = (elm);					\
    237 } while (/*CONSTCOND*/0)
    238 
    239 #define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
    240 	(elm)->field.stqe_next = NULL;					\
    241 	*(head)->stqh_last = (elm);					\
    242 	(head)->stqh_last = &(elm)->field.stqe_next;			\
    243 } while (/*CONSTCOND*/0)
    244 
    245 #define	STAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
    246 	if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
    247 		(head)->stqh_last = &(elm)->field.stqe_next;		\
    248 	(listelm)->field.stqe_next = (elm);				\
    249 } while (/*CONSTCOND*/0)
    250 
    251 #define	STAILQ_REMOVE_HEAD(head, field) do {				\
    252 	if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
    253 		(head)->stqh_last = &(head)->stqh_first;			\
    254 } while (/*CONSTCOND*/0)
    255 
    256 #define	STAILQ_REMOVE(head, elm, type, field) do {			\
    257 	if ((head)->stqh_first == (elm)) {				\
    258 		STAILQ_REMOVE_HEAD((head), field);			\
    259 	} else {							\
    260 		struct type *curelm = (head)->stqh_first;		\
    261 		while (curelm->field.stqe_next != (elm))			\
    262 			curelm = curelm->field.stqe_next;		\
    263 		if ((curelm->field.stqe_next =				\
    264 			curelm->field.stqe_next->field.stqe_next) == NULL) \
    265 			    (head)->stqh_last = &(curelm)->field.stqe_next; \
    266 	}								\
    267 } while (/*CONSTCOND*/0)
    268 
    269 #define	STAILQ_FOREACH(var, head, field)				\
    270 	for ((var) = ((head)->stqh_first);				\
    271 		(var);							\
    272 		(var) = ((var)->field.stqe_next))
    273 
    274 #define	STAILQ_CONCAT(head1, head2) do {				\
    275 	if (!STAILQ_EMPTY((head2))) {					\
    276 		*(head1)->stqh_last = (head2)->stqh_first;		\
    277 		(head1)->stqh_last = (head2)->stqh_last;		\
    278 		STAILQ_INIT((head2));					\
    279 	}								\
    280 } while (/*CONSTCOND*/0)
    281 
    282 /*
    283  * Singly-linked Tail queue access methods.
    284  */
    285 #define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)
    286 #define	STAILQ_FIRST(head)	((head)->stqh_first)
    287 #define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)
    288 
    289 
    290 /*
    291  * Simple queue definitions.
    292  */
    293 #define	SIMPLEQ_HEAD(name, type)					\
    294 struct name {								\
    295 	struct type *sqh_first;	/* first element */			\
    296 	struct type **sqh_last;	/* addr of last next element */		\
    297 }
    298 
    299 #define	SIMPLEQ_HEAD_INITIALIZER(head)					\
    300 	{ NULL, &(head).sqh_first }
    301 
    302 #define	SIMPLEQ_ENTRY(type)						\
    303 struct {								\
    304 	struct type *sqe_next;	/* next element */			\
    305 }
    306 
    307 /*
    308  * Simple queue functions.
    309  */
    310 #define	SIMPLEQ_INIT(head) do {						\
    311 	(head)->sqh_first = NULL;					\
    312 	(head)->sqh_last = &(head)->sqh_first;				\
    313 } while (/*CONSTCOND*/0)
    314 
    315 #define	SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
    316 	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
    317 		(head)->sqh_last = &(elm)->field.sqe_next;		\
    318 	(head)->sqh_first = (elm);					\
    319 } while (/*CONSTCOND*/0)
    320 
    321 #define	SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
    322 	(elm)->field.sqe_next = NULL;					\
    323 	*(head)->sqh_last = (elm);					\
    324 	(head)->sqh_last = &(elm)->field.sqe_next;			\
    325 } while (/*CONSTCOND*/0)
    326 
    327 #define	SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
    328 	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
    329 		(head)->sqh_last = &(elm)->field.sqe_next;		\
    330 	(listelm)->field.sqe_next = (elm);				\
    331 } while (/*CONSTCOND*/0)
    332 
    333 #define	SIMPLEQ_REMOVE_HEAD(head, field) do {				\
    334 	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
    335 		(head)->sqh_last = &(head)->sqh_first;			\
    336 } while (/*CONSTCOND*/0)
    337 
    338 #define	SIMPLEQ_REMOVE(head, elm, type, field) do {			\
    339 	if ((head)->sqh_first == (elm)) {				\
    340 		SIMPLEQ_REMOVE_HEAD((head), field);			\
    341 	} else {							\
    342 		struct type *curelm = (head)->sqh_first;		\
    343 		while (curelm->field.sqe_next != (elm))			\
    344 			curelm = curelm->field.sqe_next;		\
    345 		if ((curelm->field.sqe_next =				\
    346 			curelm->field.sqe_next->field.sqe_next) == NULL) \
    347 			    (head)->sqh_last = &(curelm)->field.sqe_next; \
    348 	}								\
    349 } while (/*CONSTCOND*/0)
    350 
    351 #define	SIMPLEQ_FOREACH(var, head, field)				\
    352 	for ((var) = ((head)->sqh_first);				\
    353 		(var);							\
    354 		(var) = ((var)->field.sqe_next))
    355 
    356 /*
    357  * Simple queue access methods.
    358  */
    359 #define	SIMPLEQ_EMPTY(head)		((head)->sqh_first == NULL)
    360 #define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
    361 #define	SIMPLEQ_NEXT(elm, field)	((elm)->field.sqe_next)
    362 
    363 
    364 /*
    365  * Tail queue definitions.
    366  */
    367 #define	_TAILQ_HEAD(name, type, qual)					\
    368 struct name {								\
    369 	qual type *tqh_first;		/* first element */		\
    370 	qual type *qual *tqh_last;	/* addr of last next element */	\
    371 }
    372 #define TAILQ_HEAD(name, type)	_TAILQ_HEAD(name, struct type,)
    373 
    374 #define	TAILQ_HEAD_INITIALIZER(head)					\
    375 	{ NULL, &(head).tqh_first }
    376 
    377 #define	_TAILQ_ENTRY(type, qual)					\
    378 struct {								\
    379 	qual type *tqe_next;		/* next element */		\
    380 	qual type *qual *tqe_prev;	/* address of previous next element */\
    381 }
    382 #define TAILQ_ENTRY(type)	_TAILQ_ENTRY(struct type,)
    383 
    384 /*
    385  * Tail queue functions.
    386  */
    387 #define	TAILQ_INIT(head) do {						\
    388 	(head)->tqh_first = NULL;					\
    389 	(head)->tqh_last = &(head)->tqh_first;				\
    390 } while (/*CONSTCOND*/0)
    391 
    392 #define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
    393 	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
    394 		(head)->tqh_first->field.tqe_prev =			\
    395 		    &(elm)->field.tqe_next;				\
    396 	else								\
    397 		(head)->tqh_last = &(elm)->field.tqe_next;		\
    398 	(head)->tqh_first = (elm);					\
    399 	(elm)->field.tqe_prev = &(head)->tqh_first;			\
    400 } while (/*CONSTCOND*/0)
    401 
    402 #define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
    403 	(elm)->field.tqe_next = NULL;					\
    404 	(elm)->field.tqe_prev = (head)->tqh_last;			\
    405 	*(head)->tqh_last = (elm);					\
    406 	(head)->tqh_last = &(elm)->field.tqe_next;			\
    407 } while (/*CONSTCOND*/0)
    408 
    409 #define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
    410 	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
    411 		(elm)->field.tqe_next->field.tqe_prev = 		\
    412 		    &(elm)->field.tqe_next;				\
    413 	else								\
    414 		(head)->tqh_last = &(elm)->field.tqe_next;		\
    415 	(listelm)->field.tqe_next = (elm);				\
    416 	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
    417 } while (/*CONSTCOND*/0)
    418 
    419 #define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
    420 	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
    421 	(elm)->field.tqe_next = (listelm);				\
    422 	*(listelm)->field.tqe_prev = (elm);				\
    423 	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
    424 } while (/*CONSTCOND*/0)
    425 
    426 #define	TAILQ_REMOVE(head, elm, field) do {				\
    427 	if (((elm)->field.tqe_next) != NULL)				\
    428 		(elm)->field.tqe_next->field.tqe_prev = 		\
    429 		    (elm)->field.tqe_prev;				\
    430 	else								\
    431 		(head)->tqh_last = (elm)->field.tqe_prev;		\
    432 	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
    433 } while (/*CONSTCOND*/0)
    434 
    435 #define	TAILQ_FOREACH(var, head, field)					\
    436 	for ((var) = ((head)->tqh_first);				\
    437 		(var);							\
    438 		(var) = ((var)->field.tqe_next))
    439 
    440 #define	TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
    441 	for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));	\
    442 		(var);							\
    443 		(var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
    444 
    445 #define	TAILQ_CONCAT(head1, head2, field) do {				\
    446 	if (!TAILQ_EMPTY(head2)) {					\
    447 		*(head1)->tqh_last = (head2)->tqh_first;		\
    448 		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	\
    449 		(head1)->tqh_last = (head2)->tqh_last;			\
    450 		TAILQ_INIT((head2));					\
    451 	}								\
    452 } while (/*CONSTCOND*/0)
    453 
    454 /*
    455  * Tail queue access methods.
    456  */
    457 #define	TAILQ_EMPTY(head)		((head)->tqh_first == NULL)
    458 #define	TAILQ_FIRST(head)		((head)->tqh_first)
    459 #define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
    460 
    461 #define	TAILQ_LAST(head, headname) \
    462 	(*(((struct headname *)((head)->tqh_last))->tqh_last))
    463 #define	TAILQ_PREV(elm, headname, field) \
    464 	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
    465 
    466 
    467 /*
    468  * Circular queue definitions.
    469  */
    470 #define	CIRCLEQ_HEAD(name, type)					\
    471 struct name {								\
    472 	struct type *cqh_first;		/* first element */		\
    473 	struct type *cqh_last;		/* last element */		\
    474 }
    475 
    476 #define	CIRCLEQ_HEAD_INITIALIZER(head)					\
    477 	{ (void *)&head, (void *)&head }
    478 
    479 #define	CIRCLEQ_ENTRY(type)						\
    480 struct {								\
    481 	struct type *cqe_next;		/* next element */		\
    482 	struct type *cqe_prev;		/* previous element */		\
    483 }
    484 
    485 /*
    486  * Circular queue functions.
    487  */
    488 #define	CIRCLEQ_INIT(head) do {						\
    489 	(head)->cqh_first = (void *)(head);				\
    490 	(head)->cqh_last = (void *)(head);				\
    491 } while (/*CONSTCOND*/0)
    492 
    493 #define	CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
    494 	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
    495 	(elm)->field.cqe_prev = (listelm);				\
    496 	if ((listelm)->field.cqe_next == (void *)(head))		\
    497 		(head)->cqh_last = (elm);				\
    498 	else								\
    499 		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
    500 	(listelm)->field.cqe_next = (elm);				\
    501 } while (/*CONSTCOND*/0)
    502 
    503 #define	CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
    504 	(elm)->field.cqe_next = (listelm);				\
    505 	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
    506 	if ((listelm)->field.cqe_prev == (void *)(head))		\
    507 		(head)->cqh_first = (elm);				\
    508 	else								\
    509 		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
    510 	(listelm)->field.cqe_prev = (elm);				\
    511 } while (/*CONSTCOND*/0)
    512 
    513 #define	CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
    514 	(elm)->field.cqe_next = (head)->cqh_first;			\
    515 	(elm)->field.cqe_prev = (void *)(head);				\
    516 	if ((head)->cqh_last == (void *)(head))				\
    517 		(head)->cqh_last = (elm);				\
    518 	else								\
    519 		(head)->cqh_first->field.cqe_prev = (elm);		\
    520 	(head)->cqh_first = (elm);					\
    521 } while (/*CONSTCOND*/0)
    522 
    523 #define	CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
    524 	(elm)->field.cqe_next = (void *)(head);				\
    525 	(elm)->field.cqe_prev = (head)->cqh_last;			\
    526 	if ((head)->cqh_first == (void *)(head))			\
    527 		(head)->cqh_first = (elm);				\
    528 	else								\
    529 		(head)->cqh_last->field.cqe_next = (elm);		\
    530 	(head)->cqh_last = (elm);					\
    531 } while (/*CONSTCOND*/0)
    532 
    533 #define	CIRCLEQ_REMOVE(head, elm, field) do {				\
    534 	if ((elm)->field.cqe_next == (void *)(head))			\
    535 		(head)->cqh_last = (elm)->field.cqe_prev;		\
    536 	else								\
    537 		(elm)->field.cqe_next->field.cqe_prev =			\
    538 		    (elm)->field.cqe_prev;				\
    539 	if ((elm)->field.cqe_prev == (void *)(head))			\
    540 		(head)->cqh_first = (elm)->field.cqe_next;		\
    541 	else								\
    542 		(elm)->field.cqe_prev->field.cqe_next =			\
    543 		    (elm)->field.cqe_next;				\
    544 } while (/*CONSTCOND*/0)
    545 
    546 #define	CIRCLEQ_FOREACH(var, head, field)				\
    547 	for ((var) = ((head)->cqh_first);				\
    548 		(var) != (const void *)(head);				\
    549 		(var) = ((var)->field.cqe_next))
    550 
    551 #define	CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
    552 	for ((var) = ((head)->cqh_last);				\
    553 		(var) != (const void *)(head);				\
    554 		(var) = ((var)->field.cqe_prev))
    555 
    556 /*
    557  * Circular queue access methods.
    558  */
    559 #define	CIRCLEQ_EMPTY(head)		((head)->cqh_first == (void *)(head))
    560 #define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
    561 #define	CIRCLEQ_LAST(head)		((head)->cqh_last)
    562 #define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
    563 #define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
    564 
    565 #define CIRCLEQ_LOOP_NEXT(head, elm, field)				\
    566 	(((elm)->field.cqe_next == (void *)(head))			\
    567 	    ? ((head)->cqh_first)					\
    568 	    : (elm->field.cqe_next))
    569 #define CIRCLEQ_LOOP_PREV(head, elm, field)				\
    570 	(((elm)->field.cqe_prev == (void *)(head))			\
    571 	    ? ((head)->cqh_last)					\
    572 	    : (elm->field.cqe_prev))
    573 
    574 #endif	/* sys/queue.h */