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