15a4dbb8des/*	$OpenBSD: queue.h,v 1.36 2012/04/11 13:29:14 naddy Exp $	*/
2666aa9cdes/*	$NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $	*/
3666aa9cdes
4666aa9cdes/*
5666aa9cdes * Copyright (c) 1991, 1993
6666aa9cdes *	The Regents of the University of California.  All rights reserved.
7666aa9cdes *
8666aa9cdes * Redistribution and use in source and binary forms, with or without
9666aa9cdes * modification, are permitted provided that the following conditions
10666aa9cdes * are met:
11666aa9cdes * 1. Redistributions of source code must retain the above copyright
12666aa9cdes *    notice, this list of conditions and the following disclaimer.
13666aa9cdes * 2. Redistributions in binary form must reproduce the above copyright
14666aa9cdes *    notice, this list of conditions and the following disclaimer in the
15666aa9cdes *    documentation and/or other materials provided with the distribution.
16666aa9cdes * 3. Neither the name of the University nor the names of its contributors
17666aa9cdes *    may be used to endorse or promote products derived from this software
18666aa9cdes *    without specific prior written permission.
19666aa9cdes *
20666aa9cdes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21666aa9cdes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22666aa9cdes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23666aa9cdes * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24666aa9cdes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25666aa9cdes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26666aa9cdes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27666aa9cdes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28666aa9cdes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29666aa9cdes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30666aa9cdes * SUCH DAMAGE.
31666aa9cdes *
32666aa9cdes *	@(#)queue.h	8.5 (Berkeley) 8/20/94
33666aa9cdes */
34666aa9cdes
35666aa9cdes/* OPENBSD ORIGINAL: sys/sys/queue.h */
36666aa9cdes
37666aa9cdes#ifndef	_FAKE_QUEUE_H_
38666aa9cdes#define	_FAKE_QUEUE_H_
39666aa9cdes
40666aa9cdes/*
41666aa9cdes * Require for OS/X and other platforms that have old/broken/incomplete
42666aa9cdes * <sys/queue.h>.
43666aa9cdes */
44666aa9cdes#undef SLIST_HEAD
45666aa9cdes#undef SLIST_HEAD_INITIALIZER
46666aa9cdes#undef SLIST_ENTRY
47666aa9cdes#undef SLIST_FOREACH_PREVPTR
48705433fdes#undef SLIST_FOREACH_SAFE
49666aa9cdes#undef SLIST_FIRST
50666aa9cdes#undef SLIST_END
51666aa9cdes#undef SLIST_EMPTY
52666aa9cdes#undef SLIST_NEXT
53666aa9cdes#undef SLIST_FOREACH
54666aa9cdes#undef SLIST_INIT
55666aa9cdes#undef SLIST_INSERT_AFTER
56666aa9cdes#undef SLIST_INSERT_HEAD
57666aa9cdes#undef SLIST_REMOVE_HEAD
58705433fdes#undef SLIST_REMOVE_AFTER
59666aa9cdes#undef SLIST_REMOVE
60666aa9cdes#undef SLIST_REMOVE_NEXT
61666aa9cdes#undef LIST_HEAD
62666aa9cdes#undef LIST_HEAD_INITIALIZER
63666aa9cdes#undef LIST_ENTRY
64666aa9cdes#undef LIST_FIRST
65666aa9cdes#undef LIST_END
66666aa9cdes#undef LIST_EMPTY
67666aa9cdes#undef LIST_NEXT
68666aa9cdes#undef LIST_FOREACH
69705433fdes#undef LIST_FOREACH_SAFE
70666aa9cdes#undef LIST_INIT
71666aa9cdes#undef LIST_INSERT_AFTER
72666aa9cdes#undef LIST_INSERT_BEFORE
73666aa9cdes#undef LIST_INSERT_HEAD
74666aa9cdes#undef LIST_REMOVE
75666aa9cdes#undef LIST_REPLACE
76666aa9cdes#undef SIMPLEQ_HEAD
77666aa9cdes#undef SIMPLEQ_HEAD_INITIALIZER
78666aa9cdes#undef SIMPLEQ_ENTRY
79666aa9cdes#undef SIMPLEQ_FIRST
80666aa9cdes#undef SIMPLEQ_END
81666aa9cdes#undef SIMPLEQ_EMPTY
82666aa9cdes#undef SIMPLEQ_NEXT
83666aa9cdes#undef SIMPLEQ_FOREACH
84666aa9cdes#undef SIMPLEQ_INIT
85666aa9cdes#undef SIMPLEQ_INSERT_HEAD
86666aa9cdes#undef SIMPLEQ_INSERT_TAIL
87666aa9cdes#undef SIMPLEQ_INSERT_AFTER
88666aa9cdes#undef SIMPLEQ_REMOVE_HEAD
89666aa9cdes#undef TAILQ_HEAD
90666aa9cdes#undef TAILQ_HEAD_INITIALIZER
91666aa9cdes#undef TAILQ_ENTRY
92666aa9cdes#undef TAILQ_FIRST
93666aa9cdes#undef TAILQ_END
94666aa9cdes#undef TAILQ_NEXT
95666aa9cdes#undef TAILQ_LAST
96666aa9cdes#undef TAILQ_PREV
97666aa9cdes#undef TAILQ_EMPTY
98666aa9cdes#undef TAILQ_FOREACH
99666aa9cdes#undef TAILQ_FOREACH_REVERSE
100705433fdes#undef TAILQ_FOREACH_SAFE
101705433fdes#undef TAILQ_FOREACH_REVERSE_SAFE
102666aa9cdes#undef TAILQ_INIT
103666aa9cdes#undef TAILQ_INSERT_HEAD
104666aa9cdes#undef TAILQ_INSERT_TAIL
105666aa9cdes#undef TAILQ_INSERT_AFTER
106666aa9cdes#undef TAILQ_INSERT_BEFORE
107666aa9cdes#undef TAILQ_REMOVE
108666aa9cdes#undef TAILQ_REPLACE
109666aa9cdes#undef CIRCLEQ_HEAD
110666aa9cdes#undef CIRCLEQ_HEAD_INITIALIZER
111666aa9cdes#undef CIRCLEQ_ENTRY
112666aa9cdes#undef CIRCLEQ_FIRST
113666aa9cdes#undef CIRCLEQ_LAST
114666aa9cdes#undef CIRCLEQ_END
115666aa9cdes#undef CIRCLEQ_NEXT
116666aa9cdes#undef CIRCLEQ_PREV
117666aa9cdes#undef CIRCLEQ_EMPTY
118666aa9cdes#undef CIRCLEQ_FOREACH
119666aa9cdes#undef CIRCLEQ_FOREACH_REVERSE
120666aa9cdes#undef CIRCLEQ_INIT
121666aa9cdes#undef CIRCLEQ_INSERT_AFTER
122666aa9cdes#undef CIRCLEQ_INSERT_BEFORE
123666aa9cdes#undef CIRCLEQ_INSERT_HEAD
124666aa9cdes#undef CIRCLEQ_INSERT_TAIL
125666aa9cdes#undef CIRCLEQ_REMOVE
126666aa9cdes#undef CIRCLEQ_REPLACE
127666aa9cdes
128666aa9cdes/*
129666aa9cdes * This file defines five types of data structures: singly-linked lists,
130666aa9cdes * lists, simple queues, tail queues, and circular queues.
131666aa9cdes *
132666aa9cdes *
133666aa9cdes * A singly-linked list is headed by a single forward pointer. The elements
134666aa9cdes * are singly linked for minimum space and pointer manipulation overhead at
135666aa9cdes * the expense of O(n) removal for arbitrary elements. New elements can be
136666aa9cdes * added to the list after an existing element or at the head of the list.
137666aa9cdes * Elements being removed from the head of the list should use the explicit
138666aa9cdes * macro for this purpose for optimum efficiency. A singly-linked list may
139666aa9cdes * only be traversed in the forward direction.  Singly-linked lists are ideal
140666aa9cdes * for applications with large datasets and few or no removals or for
141666aa9cdes * implementing a LIFO queue.
142666aa9cdes *
143666aa9cdes * A list is headed by a single forward pointer (or an array of forward
144666aa9cdes * pointers for a hash table header). The elements are doubly linked
145666aa9cdes * so that an arbitrary element can be removed without a need to
146666aa9cdes * traverse the list. New elements can be added to the list before
147666aa9cdes * or after an existing element or at the head of the list. A list
148666aa9cdes * may only be traversed in the forward direction.
149666aa9cdes *
150666aa9cdes * A simple queue is headed by a pair of pointers, one the head of the
151666aa9cdes * list and the other to the tail of the list. The elements are singly
152666aa9cdes * linked to save space, so elements can only be removed from the
153666aa9cdes * head of the list. New elements can be added to the list before or after
154666aa9cdes * an existing element, at the head of the list, or at the end of the
155666aa9cdes * list. A simple queue may only be traversed in the forward direction.
156666aa9cdes *
157666aa9cdes * A tail queue is headed by a pair of pointers, one to the head of the
158666aa9cdes * list and the other to the tail of the list. The elements are doubly
159666aa9cdes * linked so that an arbitrary element can be removed without a need to
160666aa9cdes * traverse the list. New elements can be added to the list before or
161666aa9cdes * after an existing element, at the head of the list, or at the end of
162666aa9cdes * the list. A tail queue may be traversed in either direction.
163666aa9cdes *
164666aa9cdes * A circle queue is headed by a pair of pointers, one to the head of the
165666aa9cdes * list and the other to the tail of the list. The elements are doubly
166666aa9cdes * linked so that an arbitrary element can be removed without a need to
167666aa9cdes * traverse the list. New elements can be added to the list before or after
168666aa9cdes * an existing element, at the head of the list, or at the end of the list.
169666aa9cdes * A circle queue may be traversed in either direction, but has a more
170666aa9cdes * complex end of list detection.
171666aa9cdes *
172666aa9cdes * For details on the use of these macros, see the queue(3) manual page.
173666aa9cdes */
174666aa9cdes
17558ec145des#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
17658ec145des#define _Q_INVALIDATE(a) (a) = ((void *)-1)
17758ec145des#else
17858ec145des#define _Q_INVALIDATE(a)
17958ec145des#endif
18058ec145des
181666aa9cdes/*
182666aa9cdes * Singly-linked List definitions.
183666aa9cdes */
184666aa9cdes#define SLIST_HEAD(name, type)						\
185666aa9cdesstruct name {								\
186666aa9cdes	struct type *slh_first;	/* first element */			\
187666aa9cdes}
188666aa9cdes
189666aa9cdes#define	SLIST_HEAD_INITIALIZER(head)					\
190666aa9cdes	{ NULL }
191666aa9cdes
192666aa9cdes#define SLIST_ENTRY(type)						\
193666aa9cdesstruct {								\
194666aa9cdes	struct type *sle_next;	/* next element */			\
195666aa9cdes}
196666aa9cdes
197666aa9cdes/*
198666aa9cdes * Singly-linked List access methods.
199666aa9cdes */
200666aa9cdes#define	SLIST_FIRST(head)	((head)->slh_first)
201666aa9cdes#define	SLIST_END(head)		NULL
202666aa9cdes#define	SLIST_EMPTY(head)	(SLIST_FIRST(head) == SLIST_END(head))
203666aa9cdes#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
204666aa9cdes
205666aa9cdes#define	SLIST_FOREACH(var, head, field)					\
206666aa9cdes	for((var) = SLIST_FIRST(head);					\
207666aa9cdes	    (var) != SLIST_END(head);					\
208666aa9cdes	    (var) = SLIST_NEXT(var, field))
209666aa9cdes
2105a4dbb8des#define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
2115a4dbb8des	for ((var) = SLIST_FIRST(head);				\
2125a4dbb8des	    (var) && ((tvar) = SLIST_NEXT(var, field), 1);		\
2135a4dbb8des	    (var) = (tvar))
214666aa9cdes
215666aa9cdes/*
216666aa9cdes * Singly-linked List functions.
217666aa9cdes */
218666aa9cdes#define	SLIST_INIT(head) {						\
219666aa9cdes	SLIST_FIRST(head) = SLIST_END(head);				\
220666aa9cdes}
221666aa9cdes
222666aa9cdes#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
223666aa9cdes	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
224666aa9cdes	(slistelm)->field.sle_next = (elm);				\
225666aa9cdes} while (0)
226666aa9cdes
227666aa9cdes#define	SLIST_INSERT_HEAD(head, elm, field) do {			\
228666aa9cdes	(elm)->field.sle_next = (head)->slh_first;			\
229666aa9cdes	(head)->slh_first = (elm);					\
230666aa9cdes} while (0)
231666aa9cdes
2325a4dbb8des#define	SLIST_REMOVE_AFTER(elm, field) do {				\
233666aa9cdes	(elm)->field.sle_next = (elm)->field.sle_next->field.sle_next;	\
234666aa9cdes} while (0)
235666aa9cdes
236666aa9cdes#define	SLIST_REMOVE_HEAD(head, field) do {				\
237666aa9cdes	(head)->slh_first = (head)->slh_first->field.sle_next;		\
238666aa9cdes} while (0)
239666aa9cdes
240666aa9cdes#define SLIST_REMOVE(head, elm, type, field) do {			\
241666aa9cdes	if ((head)->slh_first == (elm)) {				\
242666aa9cdes		SLIST_REMOVE_HEAD((head), field);			\
24358ec145des	} else {							\
244666aa9cdes		struct type *curelm = (head)->slh_first;		\
24558ec145des									\
24658ec145des		while (curelm->field.sle_next != (elm))			\
247666aa9cdes			curelm = curelm->field.sle_next;		\
248666aa9cdes		curelm->field.sle_next =				\
249666aa9cdes		    curelm->field.sle_next->field.sle_next;		\
25058ec145des		_Q_INVALIDATE((elm)->field.sle_next);			\
251666aa9cdes	}								\
252666aa9cdes} while (0)
253666aa9cdes
254666aa9cdes/*
255666aa9cdes * List definitions.
256666aa9cdes */
257666aa9cdes#define LIST_HEAD(name, type)						\
258666aa9cdesstruct name {								\
259666aa9cdes	struct type *lh_first;	/* first element */			\
260666aa9cdes}
261666aa9cdes
262666aa9cdes#define LIST_HEAD_INITIALIZER(head)					\
263666aa9cdes	{ NULL }
264666aa9cdes
265666aa9cdes#define LIST_ENTRY(type)						\
266666aa9cdesstruct {								\
267666aa9cdes	struct type *le_next;	/* next element */			\
268666aa9cdes	struct type **le_prev;	/* address of previous next element */	\
269666aa9cdes}
270666aa9cdes
271666aa9cdes/*
272666aa9cdes * List access methods
273666aa9cdes */
274666aa9cdes#define	LIST_FIRST(head)		((head)->lh_first)
275666aa9cdes#define	LIST_END(head)			NULL
276666aa9cdes#define	LIST_EMPTY(head)		(LIST_FIRST(head) == LIST_END(head))
277666aa9cdes#define	LIST_NEXT(elm, field)		((elm)->field.le_next)
278666aa9cdes
279666aa9cdes#define LIST_FOREACH(var, head, field)					\
280666aa9cdes	for((var) = LIST_FIRST(head);					\
281666aa9cdes	    (var)!= LIST_END(head);					\
282666aa9cdes	    (var) = LIST_NEXT(var, field))
283666aa9cdes
2845a4dbb8des#define	LIST_FOREACH_SAFE(var, head, field, tvar)			\
2855a4dbb8des	for ((var) = LIST_FIRST(head);				\
2865a4dbb8des	    (var) && ((tvar) = LIST_NEXT(var, field), 1);		\
2875a4dbb8des	    (var) = (tvar))
2885a4dbb8des
289666aa9cdes/*
290666aa9cdes * List functions.
291666aa9cdes */
292666aa9cdes#define	LIST_INIT(head) do {						\
293666aa9cdes	LIST_FIRST(head) = LIST_END(head);				\
294666aa9cdes} while (0)
295666aa9cdes
296666aa9cdes#define LIST_INSERT_AFTER(listelm, elm, field) do {			\
297666aa9cdes	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
298666aa9cdes		(listelm)->field.le_next->field.le_prev =		\
299666aa9cdes		    &(elm)->field.le_next;				\
300666aa9cdes	(listelm)->field.le_next = (elm);				\
301666aa9cdes	(elm)->field.le_prev = &(listelm)->field.le_next;		\
302666aa9cdes} while (0)
303666aa9cdes
304666aa9cdes#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
305666aa9cdes	(elm)->field.le_prev = (listelm)->field.le_prev;		\
306666aa9cdes	(elm)->field.le_next = (listelm);				\
307666aa9cdes	*(listelm)->field.le_prev = (elm);				\
308666aa9cdes	(listelm)->field.le_prev = &(elm)->field.le_next;		\
309666aa9cdes} while (0)
310666aa9cdes
311666aa9cdes#define LIST_INSERT_HEAD(head, elm, field) do {				\
312666aa9cdes	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
313666aa9cdes		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
314666aa9cdes	(head)->lh_first = (elm);					\
315666aa9cdes	(elm)->field.le_prev = &(head)->lh_first;			\
316666aa9cdes} while (0)
317666aa9cdes
318666aa9cdes#define LIST_REMOVE(elm, field) do {					\
319666aa9cdes	if ((elm)->field.le_next != NULL)				\
320666aa9cdes		(elm)->field.le_next->field.le_prev =			\
321666aa9cdes		    (elm)->field.le_prev;				\
322666aa9cdes	*(elm)->field.le_prev = (elm)->field.le_next;			\
32358ec145des	_Q_INVALIDATE((elm)->field.le_prev);				\
32458ec145des	_Q_INVALIDATE((elm)->field.le_next);				\
325666aa9cdes} while (0)
326666aa9cdes
327666aa9cdes#define LIST_REPLACE(elm, elm2, field) do {				\
328666aa9cdes	if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)	\
329666aa9cdes		(elm2)->field.le_next->field.le_prev =			\
330666aa9cdes		    &(elm2)->field.le_next;				\
331666aa9cdes	(elm2)->field.le_prev = (elm)->field.le_prev;			\
332666aa9cdes	*(elm2)->field.le_prev = (elm2);				\
33358ec145des	_Q_INVALIDATE((elm)->field.le_prev);				\
33458ec145des	_Q_INVALIDATE((elm)->field.le_next);				\
335666aa9cdes} while (0)
336666aa9cdes
337666aa9cdes/*
338666aa9cdes * Simple queue definitions.
339666aa9cdes */
340666aa9cdes#define SIMPLEQ_HEAD(name, type)					\
341666aa9cdesstruct name {								\
342666aa9cdes	struct type *sqh_first;	/* first element */			\
343666aa9cdes	struct type **sqh_last;	/* addr of last next element */		\
344666aa9cdes}
345666aa9cdes
346666aa9cdes#define SIMPLEQ_HEAD_INITIALIZER(head)					\
347666aa9cdes	{ NULL, &(head).sqh_first }
348666aa9cdes
349666aa9cdes#define SIMPLEQ_ENTRY(type)						\
350666aa9cdesstruct {								\
351666aa9cdes	struct type *sqe_next;	/* next element */			\
352666aa9cdes}
353666aa9cdes
354666aa9cdes/*
355666aa9cdes * Simple queue access methods.
356666aa9cdes */
357666aa9cdes#define	SIMPLEQ_FIRST(head)	    ((head)->sqh_first)
358666aa9cdes#define	SIMPLEQ_END(head)	    NULL
359666aa9cdes#define	SIMPLEQ_EMPTY(head)	    (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
360666aa9cdes#define	SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)
361666aa9cdes
362666aa9cdes#define SIMPLEQ_FOREACH(var, head, field)				\
363666aa9cdes	for((var) = SIMPLEQ_FIRST(head);				\
364666aa9cdes	    (var) != SIMPLEQ_END(head);					\
365666aa9cdes	    (var) = SIMPLEQ_NEXT(var, field))
366666aa9cdes
3675a4dbb8des#define	SIMPLEQ_FOREACH_SAFE(var, head, field, tvar)			\
3685a4dbb8des	for ((var) = SIMPLEQ_FIRST(head);				\
3695a4dbb8des	    (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1);		\
3705a4dbb8des	    (var) = (tvar))
3715a4dbb8des
372666aa9cdes/*
373666aa9cdes * Simple queue functions.
374666aa9cdes */
375666aa9cdes#define	SIMPLEQ_INIT(head) do {						\
376666aa9cdes	(head)->sqh_first = NULL;					\
377666aa9cdes	(head)->sqh_last = &(head)->sqh_first;				\
378666aa9cdes} while (0)
379666aa9cdes
380666aa9cdes#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
381666aa9cdes	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
382666aa9cdes		(head)->sqh_last = &(elm)->field.sqe_next;		\
383666aa9cdes	(head)->sqh_first = (elm);					\
384666aa9cdes} while (0)
385666aa9cdes
386666aa9cdes#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
387666aa9cdes	(elm)->field.sqe_next = NULL;					\
388666aa9cdes	*(head)->sqh_last = (elm);					\
389666aa9cdes	(head)->sqh_last = &(elm)->field.sqe_next;			\
390666aa9cdes} while (0)
391666aa9cdes
392666aa9cdes#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
393666aa9cdes	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
394666aa9cdes		(head)->sqh_last = &(elm)->field.sqe_next;		\
395666aa9cdes	(listelm)->field.sqe_next = (elm);				\
396666aa9cdes} while (0)
397666aa9cdes
39858ec145des#define SIMPLEQ_REMOVE_HEAD(head, field) do {			\
39958ec145des	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
400666aa9cdes		(head)->sqh_last = &(head)->sqh_first;			\
401666aa9cdes} while (0)
402666aa9cdes
4035a4dbb8des#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do {			\
4045a4dbb8des	if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
4055a4dbb8des	    == NULL)							\
4065a4dbb8des		(head)->sqh_last = &(elm)->field.sqe_next;		\
4075a4dbb8des} while (0)
4085a4dbb8des
409666aa9cdes/*
410666aa9cdes * Tail queue definitions.
411666aa9cdes */
412666aa9cdes#define TAILQ_HEAD(name, type)						\
413666aa9cdesstruct name {								\
414666aa9cdes	struct type *tqh_first;	/* first element */			\
415666aa9cdes	struct type **tqh_last;	/* addr of last next element */		\
416666aa9cdes}
417666aa9cdes
418666aa9cdes#define TAILQ_HEAD_INITIALIZER(head)					\
419666aa9cdes	{ NULL, &(head).tqh_first }
420666aa9cdes
421666aa9cdes#define TAILQ_ENTRY(type)						\
422666aa9cdesstruct {								\
423666aa9cdes	struct type *tqe_next;	/* next element */			\
424666aa9cdes	struct type **tqe_prev;	/* address of previous next element */	\
425666aa9cdes}
426666aa9cdes
427666aa9cdes/*
428666aa9cdes * tail queue access methods
429666aa9cdes */
430666aa9cdes#define	TAILQ_FIRST(head)		((head)->tqh_first)
431666aa9cdes#define	TAILQ_END(head)			NULL
432666aa9cdes#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
433666aa9cdes#define TAILQ_LAST(head, headname)					\
434666aa9cdes	(*(((struct headname *)((head)->tqh_last))->tqh_last))
435666aa9cdes/* XXX */
436666aa9cdes#define TAILQ_PREV(elm, headname, field)				\
437666aa9cdes	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
438666aa9cdes#define	TAILQ_EMPTY(head)						\
439666aa9cdes	(TAILQ_FIRST(head) == TAILQ_END(head))
440666aa9cdes
441666aa9cdes#define TAILQ_FOREACH(var, head, field)					\
442666aa9cdes	for((var) = TAILQ_FIRST(head);					\
443666aa9cdes	    (var) != TAILQ_END(head);					\
444666aa9cdes	    (var) = TAILQ_NEXT(var, field))
445666aa9cdes
4465a4dbb8des#define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
4475a4dbb8des	for ((var) = TAILQ_FIRST(head);					\
4485a4dbb8des	    (var) != TAILQ_END(head) &&					\
4495a4dbb8des	    ((tvar) = TAILQ_NEXT(var, field), 1);			\
4505a4dbb8des	    (var) = (tvar))
4515a4dbb8des
4525a4dbb8des
453666aa9cdes#define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
454666aa9cdes	for((var) = TAILQ_LAST(head, headname);				\
455666aa9cdes	    (var) != TAILQ_END(head);					\
456666aa9cdes	    (var) = TAILQ_PREV(var, headname, field))
457666aa9cdes
4585a4dbb8des#define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
4595a4dbb8des	for ((var) = TAILQ_LAST(head, headname);			\
4605a4dbb8des	    (var) != TAILQ_END(head) &&					\
4615a4dbb8des	    ((tvar) = TAILQ_PREV(var, headname, field), 1);		\
4625a4dbb8des	    (var) = (tvar))
4635a4dbb8des
464666aa9cdes/*
465666aa9cdes * Tail queue functions.
466666aa9cdes */
467666aa9cdes#define	TAILQ_INIT(head) do {						\
468666aa9cdes	(head)->tqh_first = NULL;					\
469666aa9cdes	(head)->tqh_last = &(head)->tqh_first;				\
470666aa9cdes} while (0)
471666aa9cdes
472666aa9cdes#define TAILQ_INSERT_HEAD(head, elm, field) do {			\
473666aa9cdes	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
474666aa9cdes		(head)->tqh_first->field.tqe_prev =			\
475666aa9cdes		    &(elm)->field.tqe_next;				\
476666aa9cdes	else								\
477666aa9cdes		(head)->tqh_last = &(elm)->field.tqe_next;		\
478666aa9cdes	(head)->tqh_first = (elm);					\
479666aa9cdes	(elm)->field.tqe_prev = &(head)->tqh_first;			\
480666aa9cdes} while (0)
481666aa9cdes
482666aa9cdes#define TAILQ_INSERT_TAIL(head, elm, field) do {			\
483666aa9cdes	(elm)->field.tqe_next = NULL;					\
484666aa9cdes	(elm)->field.tqe_prev = (head)->tqh_last;			\
485666aa9cdes	*(head)->tqh_last = (elm);					\
486666aa9cdes	(head)->tqh_last = &(elm)->field.tqe_next;			\
487666aa9cdes} while (0)
488666aa9cdes
489666aa9cdes#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
490666aa9cdes	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
491666aa9cdes		(elm)->field.tqe_next->field.tqe_prev =			\
492666aa9cdes		    &(elm)->field.tqe_next;				\
493666aa9cdes	else								\
494666aa9cdes		(head)->tqh_last = &(elm)->field.tqe_next;		\
495666aa9cdes	(listelm)->field.tqe_next = (elm);				\
496666aa9cdes	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
497666aa9cdes} while (0)
498666aa9cdes
499666aa9cdes#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
500666aa9cdes	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
501666aa9cdes	(elm)->field.tqe_next = (listelm);				\
502666aa9cdes	*(listelm)->field.tqe_prev = (elm);				\
503666aa9cdes	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
504666aa9cdes} while (0)
505666aa9cdes
506666aa9cdes#define TAILQ_REMOVE(head, elm, field) do {				\
507666aa9cdes	if (((elm)->field.tqe_next) != NULL)				\
508666aa9cdes		(elm)->field.tqe_next->field.tqe_prev =			\
509666aa9cdes		    (elm)->field.tqe_prev;				\
510666aa9cdes	else								\
511666aa9cdes		(head)->tqh_last = (elm)->field.tqe_prev;		\
512666aa9cdes	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
51358ec145des	_Q_INVALIDATE((elm)->field.tqe_prev);				\
51458ec145des	_Q_INVALIDATE((elm)->field.tqe_next);				\
515666aa9cdes} while (0)
516666aa9cdes
517666aa9cdes#define TAILQ_REPLACE(head, elm, elm2, field) do {			\
518666aa9cdes	if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)	\
519666aa9cdes		(elm2)->field.tqe_next->field.tqe_prev =		\
520666aa9cdes		    &(elm2)->field.tqe_next;				\
521666aa9cdes	else								\
522666aa9cdes		(head)->tqh_last = &(elm2)->field.tqe_next;		\
523666aa9cdes	(elm2)->field.tqe_prev = (elm)->field.tqe_prev;			\
524666aa9cdes	*(elm2)->field.tqe_prev = (elm2);				\
52558ec145des	_Q_INVALIDATE((elm)->field.tqe_prev);				\
52658ec145des	_Q_INVALIDATE((elm)->field.tqe_next);				\
527666aa9cdes} while (0)
528666aa9cdes
529666aa9cdes/*
530666aa9cdes * Circular queue definitions.
531666aa9cdes */
532666aa9cdes#define CIRCLEQ_HEAD(name, type)					\
533666aa9cdesstruct name {								\
534666aa9cdes	struct type *cqh_first;		/* first element */		\
535666aa9cdes	struct type *cqh_last;		/* last element */		\
536666aa9cdes}
537666aa9cdes
538666aa9cdes#define CIRCLEQ_HEAD_INITIALIZER(head)					\
539666aa9cdes	{ CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
540666aa9cdes
541666aa9cdes#define CIRCLEQ_ENTRY(type)						\
542666aa9cdesstruct {								\
543666aa9cdes	struct type *cqe_next;		/* next element */		\
544666aa9cdes	struct type *cqe_prev;		/* previous element */		\
545666aa9cdes}
546666aa9cdes
547666aa9cdes/*
548666aa9cdes * Circular queue access methods
549666aa9cdes */
550666aa9cdes#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
551666aa9cdes#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
552666aa9cdes#define	CIRCLEQ_END(head)		((void *)(head))
553666aa9cdes#define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
554666aa9cdes#define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
555666aa9cdes#define	CIRCLEQ_EMPTY(head)						\
556666aa9cdes	(CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
557666aa9cdes
558666aa9cdes#define CIRCLEQ_FOREACH(var, head, field)				\
559666aa9cdes	for((var) = CIRCLEQ_FIRST(head);				\
560666aa9cdes	    (var) != CIRCLEQ_END(head);					\
561666aa9cdes	    (var) = CIRCLEQ_NEXT(var, field))
562666aa9cdes
5635a4dbb8des#define	CIRCLEQ_FOREACH_SAFE(var, head, field, tvar)			\
5645a4dbb8des	for ((var) = CIRCLEQ_FIRST(head);				\
5655a4dbb8des	    (var) != CIRCLEQ_END(head) &&				\
5665a4dbb8des	    ((tvar) = CIRCLEQ_NEXT(var, field), 1);			\
5675a4dbb8des	    (var) = (tvar))
5685a4dbb8des
569666aa9cdes#define CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
570666aa9cdes	for((var) = CIRCLEQ_LAST(head);					\
571666aa9cdes	    (var) != CIRCLEQ_END(head);					\
572666aa9cdes	    (var) = CIRCLEQ_PREV(var, field))
573666aa9cdes
5745a4dbb8des#define	CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
5755a4dbb8des	for ((var) = CIRCLEQ_LAST(head, headname);			\
5765a4dbb8des	    (var) != CIRCLEQ_END(head) && 				\
5775a4dbb8des	    ((tvar) = CIRCLEQ_PREV(var, headname, field), 1);		\
5785a4dbb8des	    (var) = (tvar))
5795a4dbb8des
580666aa9cdes/*
581666aa9cdes * Circular queue functions.
582666aa9cdes */
583666aa9cdes#define	CIRCLEQ_INIT(head) do {						\
584666aa9cdes	(head)->cqh_first = CIRCLEQ_END(head);				\
585666aa9cdes	(head)->cqh_last = CIRCLEQ_END(head);				\
586666aa9cdes} while (0)
587666aa9cdes
588666aa9cdes#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
589666aa9cdes	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
590666aa9cdes	(elm)->field.cqe_prev = (listelm);				\
591666aa9cdes	if ((listelm)->field.cqe_next == CIRCLEQ_END(head))		\
592666aa9cdes		(head)->cqh_last = (elm);				\
593666aa9cdes	else								\
594666aa9cdes		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
595666aa9cdes	(listelm)->field.cqe_next = (elm);				\
596666aa9cdes} while (0)
597666aa9cdes
598666aa9cdes#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
599666aa9cdes	(elm)->field.cqe_next = (listelm);				\
600666aa9cdes	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
601666aa9cdes	if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))		\
602666aa9cdes		(head)->cqh_first = (elm);				\
603666aa9cdes	else								\
604666aa9cdes		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
605666aa9cdes	(listelm)->field.cqe_prev = (elm);				\
606666aa9cdes} while (0)
607666aa9cdes
608666aa9cdes#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
609666aa9cdes	(elm)->field.cqe_next = (head)->cqh_first;			\
610666aa9cdes	(elm)->field.cqe_prev = CIRCLEQ_END(head);			\
611666aa9cdes	if ((head)->cqh_last == CIRCLEQ_END(head))			\
612666aa9cdes		(head)->cqh_last = (elm);				\
613666aa9cdes	else								\
614666aa9cdes		(head)->cqh_first->field.cqe_prev = (elm);		\
615666aa9cdes	(head)->cqh_first = (elm);					\
616666aa9cdes} while (0)
617666aa9cdes
618666aa9cdes#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
619666aa9cdes	(elm)->field.cqe_next = CIRCLEQ_END(head);			\
620666aa9cdes	(elm)->field.cqe_prev = (head)->cqh_last;			\
621666aa9cdes	if ((head)->cqh_first == CIRCLEQ_END(head))			\
622666aa9cdes		(head)->cqh_first = (elm);				\
623666aa9cdes	else								\
624666aa9cdes		(head)->cqh_last->field.cqe_next = (elm);		\
625666aa9cdes	(head)->cqh_last = (elm);					\
626666aa9cdes} while (0)
627666aa9cdes
628666aa9cdes#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
629666aa9cdes	if ((elm)->field.cqe_next == CIRCLEQ_END(head))			\
630666aa9cdes		(head)->cqh_last = (elm)->field.cqe_prev;		\
631666aa9cdes	else								\
632666aa9cdes		(elm)->field.cqe_next->field.cqe_prev =			\
633666aa9cdes		    (elm)->field.cqe_prev;				\
634666aa9cdes	if ((elm)->field.cqe_prev == CIRCLEQ_END(head))			\
635666aa9cdes		(head)->cqh_first = (elm)->field.cqe_next;		\
636666aa9cdes	else								\
637666aa9cdes		(elm)->field.cqe_prev->field.cqe_next =			\
638666aa9cdes		    (elm)->field.cqe_next;				\
63958ec145des	_Q_INVALIDATE((elm)->field.cqe_prev);				\
64058ec145des	_Q_INVALIDATE((elm)->field.cqe_next);				\
641666aa9cdes} while (0)
642666aa9cdes
643666aa9cdes#define CIRCLEQ_REPLACE(head, elm, elm2, field) do {			\
644666aa9cdes	if (((elm2)->field.cqe_next = (elm)->field.cqe_next) ==		\
645666aa9cdes	    CIRCLEQ_END(head))						\
646666aa9cdes		(head).cqh_last = (elm2);				\
647666aa9cdes	else								\
648666aa9cdes		(elm2)->field.cqe_next->field.cqe_prev = (elm2);	\
649666aa9cdes	if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) ==		\
650666aa9cdes	    CIRCLEQ_END(head))						\
651666aa9cdes		(head).cqh_first = (elm2);				\
652666aa9cdes	else								\
653666aa9cdes		(elm2)->field.cqe_prev->field.cqe_next = (elm2);	\
65458ec145des	_Q_INVALIDATE((elm)->field.cqe_prev);				\
65558ec145des	_Q_INVALIDATE((elm)->field.cqe_next);				\
656666aa9cdes} while (0)
657666aa9cdes
658666aa9cdes#endif	/* !_FAKE_QUEUE_H_ */
659