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