1047f369cy/*	$OpenBSD: queue.h,v 1.16 2000/09/07 19:47:59 art Exp $	*/
2047f369cy/*	$NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $	*/
3047f369cy
4047f369cy/*
5047f369cy * Copyright (c) 1991, 1993
6047f369cy *	The Regents of the University of California.  All rights reserved.
7047f369cy *
8047f369cy * Redistribution and use in source and binary forms, with or without
9047f369cy * modification, are permitted provided that the following conditions
10047f369cy * are met:
11047f369cy * 1. Redistributions of source code must retain the above copyright
12047f369cy *    notice, this list of conditions and the following disclaimer.
13047f369cy * 2. Redistributions in binary form must reproduce the above copyright
14047f369cy *    notice, this list of conditions and the following disclaimer in the
15047f369cy *    documentation and/or other materials provided with the distribution.
16047f369cy * 3. Neither the name of the University nor the names of its contributors
17047f369cy *    may be used to endorse or promote products derived from this software
18047f369cy *    without specific prior written permission.
19047f369cy *
20047f369cy * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21047f369cy * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22047f369cy * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23047f369cy * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24047f369cy * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25047f369cy * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26047f369cy * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27047f369cy * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28047f369cy * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29047f369cy * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30047f369cy * SUCH DAMAGE.
31047f369cy *
32047f369cy *	@(#)queue.h	8.5 (Berkeley) 8/20/94
33047f369cy */
34047f369cy
35047f369cy#ifndef	SYS_QUEUE_H__
36047f369cy#define	SYS_QUEUE_H__
37047f369cy
38047f369cy/*
39047f369cy * This file defines five types of data structures: singly-linked lists,
40047f369cy * lists, simple queues, tail queues, and circular queues.
41047f369cy *
42047f369cy *
43047f369cy * A singly-linked list is headed by a single forward pointer. The elements
44047f369cy * are singly linked for minimum space and pointer manipulation overhead at
45047f369cy * the expense of O(n) removal for arbitrary elements. New elements can be
46047f369cy * added to the list after an existing element or at the head of the list.
47047f369cy * Elements being removed from the head of the list should use the explicit
48047f369cy * macro for this purpose for optimum efficiency. A singly-linked list may
49047f369cy * only be traversed in the forward direction.  Singly-linked lists are ideal
50047f369cy * for applications with large datasets and few or no removals or for
51047f369cy * implementing a LIFO queue.
52047f369cy *
53047f369cy * A list is headed by a single forward pointer (or an array of forward
54047f369cy * pointers for a hash table header). The elements are doubly linked
55047f369cy * so that an arbitrary element can be removed without a need to
56047f369cy * traverse the list. New elements can be added to the list before
57047f369cy * or after an existing element or at the head of the list. A list
58047f369cy * may only be traversed in the forward direction.
59047f369cy *
60047f369cy * A simple queue is headed by a pair of pointers, one the head of the
61047f369cy * list and the other to the tail of the list. The elements are singly
62047f369cy * linked to save space, so elements can only be removed from the
63047f369cy * head of the list. New elements can be added to the list before or after
64047f369cy * an existing element, at the head of the list, or at the end of the
65047f369cy * list. A simple queue may only be traversed in the forward direction.
66047f369cy *
67047f369cy * A tail queue is headed by a pair of pointers, one to the head of the
68047f369cy * list and the other to the tail of the list. The elements are doubly
69047f369cy * linked so that an arbitrary element can be removed without a need to
70047f369cy * traverse the list. New elements can be added to the list before or
71047f369cy * after an existing element, at the head of the list, or at the end of
72047f369cy * the list. A tail queue may be traversed in either direction.
73047f369cy *
74047f369cy * A circle queue is headed by a pair of pointers, one to the head of the
75047f369cy * list and the other to the tail of the list. The elements are doubly
76047f369cy * linked so that an arbitrary element can be removed without a need to
77047f369cy * traverse the list. New elements can be added to the list before or after
78047f369cy * an existing element, at the head of the list, or at the end of the list.
79047f369cy * A circle queue may be traversed in either direction, but has a more
80047f369cy * complex end of list detection.
81047f369cy *
82047f369cy * For details on the use of these macros, see the queue(3) manual page.
83047f369cy */
84047f369cy
85047f369cy/*
86047f369cy * Singly-linked List definitions.
87047f369cy */
88047f369cy#define SLIST_HEAD(name, type)						\
89047f369cystruct name {								\
90047f369cy	struct type *slh_first;	/* first element */			\
91047f369cy}
92047f369cy
93047f369cy#define	SLIST_HEAD_INITIALIZER(head)					\
94047f369cy	{ NULL }
95047f369cy
96047f369cy#ifndef _WIN32
97047f369cy#define SLIST_ENTRY(type)						\
98047f369cystruct {								\
99047f369cy	struct type *sle_next;	/* next element */			\
100047f369cy}
101047f369cy#endif
102047f369cy
103047f369cy/*
104047f369cy * Singly-linked List access methods.
105047f369cy */
106047f369cy#define	SLIST_FIRST(head)	((head)->slh_first)
107047f369cy#define	SLIST_END(head)		NULL
108047f369cy#define	SLIST_EMPTY(head)	(SLIST_FIRST(head) == SLIST_END(head))
109047f369cy#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
110047f369cy
111047f369cy#define	SLIST_FOREACH(var, head, field)					\
112047f369cy	for((var) = SLIST_FIRST(head);					\
113047f369cy	    (var) != SLIST_END(head);					\
114047f369cy	    (var) = SLIST_NEXT(var, field))
115047f369cy
116047f369cy/*
117047f369cy * Singly-linked List functions.
118047f369cy */
119047f369cy#define	SLIST_INIT(head) {						\
120047f369cy	SLIST_FIRST(head) = SLIST_END(head);				\
121047f369cy}
122047f369cy
123047f369cy#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
124047f369cy	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
125047f369cy	(slistelm)->field.sle_next = (elm);				\
126047f369cy} while (0)
127047f369cy
128047f369cy#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
129047f369cy	(elm)->field.sle_next = (head)->slh_first;			\
130047f369cy	(head)->slh_first = (elm);					\
131047f369cy} while (0)
132047f369cy
133047f369cy#define	SLIST_REMOVE_HEAD(head, field) do {				\
134047f369cy	(head)->slh_first = (head)->slh_first->field.sle_next;		\
135047f369cy} while (0)
136047f369cy
137047f369cy/*
138047f369cy * List definitions.
139047f369cy */
140047f369cy#define LIST_HEAD(name, type)						\
141047f369cystruct name {								\
142047f369cy	struct type *lh_first;	/* first element */			\
143047f369cy}
144047f369cy
145047f369cy#define LIST_HEAD_INITIALIZER(head)					\
146047f369cy	{ NULL }
147047f369cy
148047f369cy#define LIST_ENTRY(type)						\
149047f369cystruct {								\
150047f369cy	struct type *le_next;	/* next element */			\
151047f369cy	struct type **le_prev;	/* address of previous next element */	\
152047f369cy}
153047f369cy
154047f369cy/*
155047f369cy * List access methods
156047f369cy */
157047f369cy#define	LIST_FIRST(head)		((head)->lh_first)
158047f369cy#define	LIST_END(head)			NULL
159047f369cy#define	LIST_EMPTY(head)		(LIST_FIRST(head) == LIST_END(head))
160047f369cy#define	LIST_NEXT(elm, field)		((elm)->field.le_next)
161047f369cy
162047f369cy#define LIST_FOREACH(var, head, field)					\
163047f369cy	for((var) = LIST_FIRST(head);					\
164047f369cy	    (var)!= LIST_END(head);					\
165047f369cy	    (var) = LIST_NEXT(var, field))
166047f369cy
167047f369cy/*
168047f369cy * List functions.
169047f369cy */
170047f369cy#define	LIST_INIT(head) do {						\
171047f369cy	LIST_FIRST(head) = LIST_END(head);				\
172047f369cy} while (0)
173047f369cy
174047f369cy#define LIST_INSERT_AFTER(listelm, elm, field) do {			\
175047f369cy	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
176047f369cy		(listelm)->field.le_next->field.le_prev =		\
177047f369cy		    &(elm)->field.le_next;				\
178047f369cy	(listelm)->field.le_next = (elm);				\
179047f369cy	(elm)->field.le_prev = &(listelm)->field.le_next;		\
180047f369cy} while (0)
181047f369cy
182047f369cy#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
183047f369cy	(elm)->field.le_prev = (listelm)->field.le_prev;		\
184047f369cy	(elm)->field.le_next = (listelm);				\
185047f369cy	*(listelm)->field.le_prev = (elm);				\
186047f369cy	(listelm)->field.le_prev = &(elm)->field.le_next;		\
187047f369cy} while (0)
188047f369cy
189047f369cy#define LIST_INSERT_HEAD(head, elm, field) do {				\
190047f369cy	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
191047f369cy		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
192047f369cy	(head)->lh_first = (elm);					\
193047f369cy	(elm)->field.le_prev = &(head)->lh_first;			\
194047f369cy} while (0)
195047f369cy
196047f369cy#define LIST_REMOVE(elm, field) do {					\
197047f369cy	if ((elm)->field.le_next != NULL)				\
198047f369cy		(elm)->field.le_next->field.le_prev =			\
199047f369cy		    (elm)->field.le_prev;				\
200047f369cy	*(elm)->field.le_prev = (elm)->field.le_next;			\
201047f369cy} while (0)
202047f369cy
203047f369cy#define LIST_REPLACE(elm, elm2, field) do {				\
204047f369cy	if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)	\
205047f369cy		(elm2)->field.le_next->field.le_prev =			\
206047f369cy		    &(elm2)->field.le_next;				\
207047f369cy	(elm2)->field.le_prev = (elm)->field.le_prev;			\
208047f369cy	*(elm2)->field.le_prev = (elm2);				\
209047f369cy} while (0)
210047f369cy
211047f369cy/*
212047f369cy * Simple queue definitions.
213047f369cy */
214047f369cy#define SIMPLEQ_HEAD(name, type)					\
215047f369cystruct name {								\
216047f369cy	struct type *sqh_first;	/* first element */			\
217047f369cy	struct type **sqh_last;	/* addr of last next element */		\
218047f369cy}
219047f369cy
220047f369cy#define SIMPLEQ_HEAD_INITIALIZER(head)					\
221047f369cy	{ NULL, &(head).sqh_first }
222047f369cy
223047f369cy#define SIMPLEQ_ENTRY(type)						\
224047f369cystruct {								\
225047f369cy	struct type *sqe_next;	/* next element */			\
226047f369cy}
227047f369cy
228047f369cy/*
229047f369cy * Simple queue access methods.
230047f369cy */
231047f369cy#define	SIMPLEQ_FIRST(head)	    ((head)->sqh_first)
232047f369cy#define	SIMPLEQ_END(head)	    NULL
233047f369cy#define	SIMPLEQ_EMPTY(head)	    (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
234047f369cy#define	SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)
235047f369cy
236047f369cy#define SIMPLEQ_FOREACH(var, head, field)				\
237047f369cy	for((var) = SIMPLEQ_FIRST(head);				\
238047f369cy	    (var) != SIMPLEQ_END(head);					\
239047f369cy	    (var) = SIMPLEQ_NEXT(var, field))
240047f369cy
241047f369cy/*
242047f369cy * Simple queue functions.
243047f369cy */
244047f369cy#define	SIMPLEQ_INIT(head) do {						\
245047f369cy	(head)->sqh_first = NULL;					\
246047f369cy	(head)->sqh_last = &(head)->sqh_first;				\
247047f369cy} while (0)
248047f369cy
249047f369cy#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
250047f369cy	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
251047f369cy		(head)->sqh_last = &(elm)->field.sqe_next;		\
252047f369cy	(head)->sqh_first = (elm);					\
253047f369cy} while (0)
254047f369cy
255047f369cy#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
256047f369cy	(elm)->field.sqe_next = NULL;					\
257047f369cy	*(head)->sqh_last = (elm);					\
258047f369cy	(head)->sqh_last = &(elm)->field.sqe_next;			\
259047f369cy} while (0)
260047f369cy
261047f369cy#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
262047f369cy	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
263047f369cy		(head)->sqh_last = &(elm)->field.sqe_next;		\
264047f369cy	(listelm)->field.sqe_next = (elm);				\
265047f369cy} while (0)
266047f369cy
267047f369cy#define SIMPLEQ_REMOVE_HEAD(head, elm, field) do {			\
268047f369cy	if (((head)->sqh_first = (elm)->field.sqe_next) == NULL)	\
269047f369cy		(head)->sqh_last = &(head)->sqh_first;			\
270047f369cy} while (0)
271047f369cy
272047f369cy/*
273047f369cy * Tail queue definitions.
274047f369cy */
275047f369cy#define TAILQ_HEAD(name, type)						\
276047f369cystruct name {								\
277047f369cy	struct type *tqh_first;	/* first element */			\
278047f369cy	struct type **tqh_last;	/* addr of last next element */		\
279047f369cy}
280047f369cy
281047f369cy#define TAILQ_HEAD_INITIALIZER(head)					\
282047f369cy	{ NULL, &(head).tqh_first }
283047f369cy
284047f369cy#define TAILQ_ENTRY(type)						\
285047f369cystruct {								\
286047f369cy	struct type *tqe_next;	/* next element */			\
287047f369cy	struct type **tqe_prev;	/* address of previous next element */	\
288047f369cy}
289047f369cy
290047f369cy/*
291047f369cy * tail queue access methods
292047f369cy */
293047f369cy#define	TAILQ_FIRST(head)		((head)->tqh_first)
294047f369cy#define	TAILQ_END(head)			NULL
295047f369cy#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
296047f369cy#define TAILQ_LAST(head, headname)					\
297047f369cy	(*(((struct headname *)((head)->tqh_last))->tqh_last))
298047f369cy/* XXX */
299047f369cy#define TAILQ_PREV(elm, headname, field)				\
300047f369cy	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
301047f369cy#define	TAILQ_EMPTY(head)						\
302047f369cy	(TAILQ_FIRST(head) == TAILQ_END(head))
303047f369cy
304047f369cy#define TAILQ_FOREACH(var, head, field)					\
305047f369cy	for((var) = TAILQ_FIRST(head);					\
306047f369cy	    (var) != TAILQ_END(head);					\
307047f369cy	    (var) = TAILQ_NEXT(var, field))
308047f369cy
309047f369cy#define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
310047f369cy	for((var) = TAILQ_LAST(head, headname);				\
311047f369cy	    (var) != TAILQ_END(head);					\
312047f369cy	    (var) = TAILQ_PREV(var, headname, field))
313047f369cy
314047f369cy/*
315047f369cy * Tail queue functions.
316047f369cy */
317047f369cy#define	TAILQ_INIT(head) do {						\
318047f369cy	(head)->tqh_first = NULL;					\
319047f369cy	(head)->tqh_last = &(head)->tqh_first;				\
320047f369cy} while (0)
321047f369cy
322047f369cy#define TAILQ_INSERT_HEAD(head, elm, field) do {			\
323047f369cy	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
324047f369cy		(head)->tqh_first->field.tqe_prev =			\
325047f369cy		    &(elm)->field.tqe_next;				\
326047f369cy	else								\
327047f369cy		(head)->tqh_last = &(elm)->field.tqe_next;		\
328047f369cy	(head)->tqh_first = (elm);					\
329047f369cy	(elm)->field.tqe_prev = &(head)->tqh_first;			\
330047f369cy} while (0)
331047f369cy
332047f369cy#define TAILQ_INSERT_TAIL(head, elm, field) do {			\
333047f369cy	(elm)->field.tqe_next = NULL;					\
334047f369cy	(elm)->field.tqe_prev = (head)->tqh_last;			\
335047f369cy	*(head)->tqh_last = (elm);					\
336047f369cy	(head)->tqh_last = &(elm)->field.tqe_next;			\
337047f369cy} while (0)
338047f369cy
339047f369cy#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
340047f369cy	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
341047f369cy		(elm)->field.tqe_next->field.tqe_prev =			\
342047f369cy		    &(elm)->field.tqe_next;				\
343047f369cy	else								\
344047f369cy		(head)->tqh_last = &(elm)->field.tqe_next;		\
345047f369cy	(listelm)->field.tqe_next = (elm);				\
346047f369cy	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
347047f369cy} while (0)
348047f369cy
349047f369cy#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
350047f369cy	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
351047f369cy	(elm)->field.tqe_next = (listelm);				\
352047f369cy	*(listelm)->field.tqe_prev = (elm);				\
353047f369cy	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
354047f369cy} while (0)
355047f369cy
356047f369cy#define TAILQ_REMOVE(head, elm, field) do {				\
357047f369cy	if (((elm)->field.tqe_next) != NULL)				\
358047f369cy		(elm)->field.tqe_next->field.tqe_prev =			\
359047f369cy		    (elm)->field.tqe_prev;				\
360047f369cy	else								\
361047f369cy		(head)->tqh_last = (elm)->field.tqe_prev;		\
362047f369cy	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
363047f369cy} while (0)
364047f369cy
365047f369cy#define TAILQ_REPLACE(head, elm, elm2, field) do {			\
366047f369cy	if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)	\
367047f369cy		(elm2)->field.tqe_next->field.tqe_prev =		\
368047f369cy		    &(elm2)->field.tqe_next;				\
369047f369cy	else								\
370047f369cy		(head)->tqh_last = &(elm2)->field.tqe_next;		\
371047f369cy	(elm2)->field.tqe_prev = (elm)->field.tqe_prev;			\
372047f369cy	*(elm2)->field.tqe_prev = (elm2);				\
373047f369cy} while (0)
374047f369cy
375047f369cy/*
376047f369cy * Circular queue definitions.
377047f369cy */
378047f369cy#define CIRCLEQ_HEAD(name, type)					\
379047f369cystruct name {								\
380047f369cy	struct type *cqh_first;		/* first element */		\
381047f369cy	struct type *cqh_last;		/* last element */		\
382047f369cy}
383047f369cy
384047f369cy#define CIRCLEQ_HEAD_INITIALIZER(head)					\
385047f369cy	{ CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
386047f369cy
387047f369cy#define CIRCLEQ_ENTRY(type)						\
388047f369cystruct {								\
389047f369cy	struct type *cqe_next;		/* next element */		\
390047f369cy	struct type *cqe_prev;		/* previous element */		\
391047f369cy}
392047f369cy
393047f369cy/*
394047f369cy * Circular queue access methods
395047f369cy */
396047f369cy#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
397047f369cy#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
398047f369cy#define	CIRCLEQ_END(head)		((void *)(head))
399047f369cy#define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
400047f369cy#define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
401047f369cy#define	CIRCLEQ_EMPTY(head)						\
402047f369cy	(CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
403047f369cy
404047f369cy#define CIRCLEQ_FOREACH(var, head, field)				\
405047f369cy	for((var) = CIRCLEQ_FIRST(head);				\
406047f369cy	    (var) != CIRCLEQ_END(head);					\
407047f369cy	    (var) = CIRCLEQ_NEXT(var, field))
408047f369cy
409047f369cy#define CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
410047f369cy	for((var) = CIRCLEQ_LAST(head);					\
411047f369cy	    (var) != CIRCLEQ_END(head);					\
412047f369cy	    (var) = CIRCLEQ_PREV(var, field))
413047f369cy
414047f369cy/*
415047f369cy * Circular queue functions.
416047f369cy */
417047f369cy#define	CIRCLEQ_INIT(head) do {						\
418047f369cy	(head)->cqh_first = CIRCLEQ_END(head);				\
419047f369cy	(head)->cqh_last = CIRCLEQ_END(head);				\
420047f369cy} while (0)
421047f369cy
422047f369cy#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
423047f369cy	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
424047f369cy	(elm)->field.cqe_prev = (listelm);				\
425047f369cy	if ((listelm)->field.cqe_next == CIRCLEQ_END(head))		\
426047f369cy		(head)->cqh_last = (elm);				\
427047f369cy	else								\
428047f369cy		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
429047f369cy	(listelm)->field.cqe_next = (elm);				\
430047f369cy} while (0)
431047f369cy
432047f369cy#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
433047f369cy	(elm)->field.cqe_next = (listelm);				\
434047f369cy	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
435047f369cy	if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))		\
436047f369cy		(head)->cqh_first = (elm);				\
437047f369cy	else								\
438047f369cy		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
439047f369cy	(listelm)->field.cqe_prev = (elm);				\
440047f369cy} while (0)
441047f369cy
442047f369cy#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
443047f369cy	(elm)->field.cqe_next = (head)->cqh_first;			\
444047f369cy	(elm)->field.cqe_prev = CIRCLEQ_END(head);			\
445047f369cy	if ((head)->cqh_last == CIRCLEQ_END(head))			\
446047f369cy		(head)->cqh_last = (elm);				\
447047f369cy	else								\
448047f369cy		(head)->cqh_first->field.cqe_prev = (elm);		\
449047f369cy	(head)->cqh_first = (elm);					\
450047f369cy} while (0)
451047f369cy
452047f369cy#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
453047f369cy	(elm)->field.cqe_next = CIRCLEQ_END(head);			\
454047f369cy	(elm)->field.cqe_prev = (head)->cqh_last;			\
455047f369cy	if ((head)->cqh_first == CIRCLEQ_END(head))			\
456047f369cy		(head)->cqh_first = (elm);				\
457047f369cy	else								\
458047f369cy		(head)->cqh_last->field.cqe_next = (elm);		\
459047f369cy	(head)->cqh_last = (elm);					\
460047f369cy} while (0)
461047f369cy
462047f369cy#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
463047f369cy	if ((elm)->field.cqe_next == CIRCLEQ_END(head))			\
464047f369cy		(head)->cqh_last = (elm)->field.cqe_prev;		\
465047f369cy	else								\
466047f369cy		(elm)->field.cqe_next->field.cqe_prev =			\
467047f369cy		    (elm)->field.cqe_prev;				\
468047f369cy	if ((elm)->field.cqe_prev == CIRCLEQ_END(head))			\
469047f369cy		(head)->cqh_first = (elm)->field.cqe_next;		\
470047f369cy	else								\
471047f369cy		(elm)->field.cqe_prev->field.cqe_next =			\
472047f369cy		    (elm)->field.cqe_next;				\
473047f369cy} while (0)
474047f369cy
475047f369cy#define CIRCLEQ_REPLACE(head, elm, elm2, field) do {			\
476047f369cy	if (((elm2)->field.cqe_next = (elm)->field.cqe_next) ==		\
477047f369cy	    CIRCLEQ_END(head))						\
478047f369cy		(head).cqh_last = (elm2);				\
479047f369cy	else								\
480047f369cy		(elm2)->field.cqe_next->field.cqe_prev = (elm2);	\
481047f369cy	if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) ==		\
482047f369cy	    CIRCLEQ_END(head))						\
483047f369cy		(head).cqh_first = (elm2);				\
484047f369cy	else								\
485047f369cy		(elm2)->field.cqe_prev->field.cqe_next = (elm2);	\
486047f369cy} while (0)
487047f369cy
488047f369cy#endif	/* !SYS_QUEUE_H__ */
489