130ace1d7Sbeveloper/*	$NetBSD: queue.h,v 1.31 2002/06/01 23:51:05 lukem Exp $	*/
230ace1d7Sbeveloper
330ace1d7Sbeveloper/*
430ace1d7Sbeveloper * Copyright (c) 1991, 1993
530ace1d7Sbeveloper *	The Regents of the University of California.  All rights reserved.
630ace1d7Sbeveloper *
730ace1d7Sbeveloper * Redistribution and use in source and binary forms, with or without
830ace1d7Sbeveloper * modification, are permitted provided that the following conditions
930ace1d7Sbeveloper * are met:
1030ace1d7Sbeveloper * 1. Redistributions of source code must retain the above copyright
1130ace1d7Sbeveloper *    notice, this list of conditions and the following disclaimer.
1230ace1d7Sbeveloper * 2. Redistributions in binary form must reproduce the above copyright
1330ace1d7Sbeveloper *    notice, this list of conditions and the following disclaimer in the
1430ace1d7Sbeveloper *    documentation and/or other materials provided with the distribution.
1530ace1d7Sbeveloper * 3. All advertising materials mentioning features or use of this software
1630ace1d7Sbeveloper *    must display the following acknowledgement:
1730ace1d7Sbeveloper *	This product includes software developed by the University of
1830ace1d7Sbeveloper *	California, Berkeley and its contributors.
1930ace1d7Sbeveloper * 4. Neither the name of the University nor the names of its contributors
2030ace1d7Sbeveloper *    may be used to endorse or promote products derived from this software
2130ace1d7Sbeveloper *    without specific prior written permission.
2230ace1d7Sbeveloper *
2330ace1d7Sbeveloper * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
2430ace1d7Sbeveloper * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
2530ace1d7Sbeveloper * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2630ace1d7Sbeveloper * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
2730ace1d7Sbeveloper * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
2830ace1d7Sbeveloper * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
2930ace1d7Sbeveloper * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
3030ace1d7Sbeveloper * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
3130ace1d7Sbeveloper * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
3230ace1d7Sbeveloper * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
3330ace1d7Sbeveloper * SUCH DAMAGE.
3430ace1d7Sbeveloper *
3530ace1d7Sbeveloper *	@(#)queue.h	8.5 (Berkeley) 8/20/94
3630ace1d7Sbeveloper */
3730ace1d7Sbeveloper
3830ace1d7Sbeveloper#ifndef	_SYS_QUEUE_H_
3930ace1d7Sbeveloper#define	_SYS_QUEUE_H_
4030ace1d7Sbeveloper
4130ace1d7Sbeveloper/*
4230ace1d7Sbeveloper * This file defines five types of data structures: singly-linked lists,
4330ace1d7Sbeveloper * lists, simple queues, tail queues, and circular queues.
4430ace1d7Sbeveloper *
4530ace1d7Sbeveloper * A singly-linked list is headed by a single forward pointer. The
4630ace1d7Sbeveloper * elements are singly linked for minimum space and pointer manipulation
4730ace1d7Sbeveloper * overhead at the expense of O(n) removal for arbitrary elements. New
4830ace1d7Sbeveloper * elements can be added to the list after an existing element or at the
4930ace1d7Sbeveloper * head of the list.  Elements being removed from the head of the list
5030ace1d7Sbeveloper * should use the explicit macro for this purpose for optimum
5130ace1d7Sbeveloper * efficiency. A singly-linked list may only be traversed in the forward
5230ace1d7Sbeveloper * direction.  Singly-linked lists are ideal for applications with large
5330ace1d7Sbeveloper * datasets and few or no removals or for implementing a LIFO queue.
5430ace1d7Sbeveloper *
5530ace1d7Sbeveloper * A list is headed by a single forward pointer (or an array of forward
5630ace1d7Sbeveloper * pointers for a hash table header). The elements are doubly linked
5730ace1d7Sbeveloper * so that an arbitrary element can be removed without a need to
5830ace1d7Sbeveloper * traverse the list. New elements can be added to the list before
5930ace1d7Sbeveloper * or after an existing element or at the head of the list. A list
6030ace1d7Sbeveloper * may only be traversed in the forward direction.
6130ace1d7Sbeveloper *
6230ace1d7Sbeveloper * A simple queue is headed by a pair of pointers, one the head of the
6330ace1d7Sbeveloper * list and the other to the tail of the list. The elements are singly
6430ace1d7Sbeveloper * linked to save space, so only elements can only be removed from the
6530ace1d7Sbeveloper * head of the list. New elements can be added to the list after
6630ace1d7Sbeveloper * an existing element, at the head of the list, or at the end of the
6730ace1d7Sbeveloper * list. A simple queue may only be traversed in the forward direction.
6830ace1d7Sbeveloper *
6930ace1d7Sbeveloper * A tail queue is headed by a pair of pointers, one to the head of the
7030ace1d7Sbeveloper * list and the other to the tail of the list. The elements are doubly
7130ace1d7Sbeveloper * linked so that an arbitrary element can be removed without a need to
7230ace1d7Sbeveloper * traverse the list. New elements can be added to the list before or
7330ace1d7Sbeveloper * after an existing element, at the head of the list, or at the end of
7430ace1d7Sbeveloper * the list. A tail queue may be traversed in either direction.
7530ace1d7Sbeveloper *
7630ace1d7Sbeveloper * A circle queue is headed by a pair of pointers, one to the head of the
7730ace1d7Sbeveloper * list and the other to the tail of the list. The elements are doubly
7830ace1d7Sbeveloper * linked so that an arbitrary element can be removed without a need to
7930ace1d7Sbeveloper * traverse the list. New elements can be added to the list before or after
8030ace1d7Sbeveloper * an existing element, at the head of the list, or at the end of the list.
8130ace1d7Sbeveloper * A circle queue may be traversed in either direction, but has a more
8230ace1d7Sbeveloper * complex end of list detection.
8330ace1d7Sbeveloper *
8430ace1d7Sbeveloper * For details on the use of these macros, see the queue(3) manual page.
8530ace1d7Sbeveloper */
8630ace1d7Sbeveloper
8730ace1d7Sbeveloper/*
8830ace1d7Sbeveloper * List definitions.
8930ace1d7Sbeveloper */
9030ace1d7Sbeveloper#define LIST_HEAD(name, type)						\
9130ace1d7Sbeveloperstruct name {								\
9230ace1d7Sbeveloper	struct type *lh_first;	/* first element */			\
9330ace1d7Sbeveloper}
9430ace1d7Sbeveloper
9530ace1d7Sbeveloper#define LIST_HEAD_INITIALIZER(head)					\
9630ace1d7Sbeveloper	{ NULL }
9730ace1d7Sbeveloper
9830ace1d7Sbeveloper#define LIST_ENTRY(type)						\
9930ace1d7Sbeveloperstruct {								\
10030ace1d7Sbeveloper	struct type *le_next;	/* next element */			\
10130ace1d7Sbeveloper	struct type **le_prev;	/* address of previous next element */	\
10230ace1d7Sbeveloper}
10330ace1d7Sbeveloper
10430ace1d7Sbeveloper/*
10530ace1d7Sbeveloper * List functions.
10630ace1d7Sbeveloper */
10730ace1d7Sbeveloper#if defined(_KERNEL) && defined(QUEUEDEBUG)
10830ace1d7Sbeveloper#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)			\
10930ace1d7Sbeveloper	if ((head)->lh_first &&						\
11030ace1d7Sbeveloper	    (head)->lh_first->field.le_prev != &(head)->lh_first)	\
11130ace1d7Sbeveloper		panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
11230ace1d7Sbeveloper#define QUEUEDEBUG_LIST_OP(elm, field)					\
11330ace1d7Sbeveloper	if ((elm)->field.le_next &&					\
11430ace1d7Sbeveloper	    (elm)->field.le_next->field.le_prev !=			\
11530ace1d7Sbeveloper	    &(elm)->field.le_next)					\
11630ace1d7Sbeveloper		panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
11730ace1d7Sbeveloper	if (*(elm)->field.le_prev != (elm))				\
11830ace1d7Sbeveloper		panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__);
11930ace1d7Sbeveloper#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)				\
12030ace1d7Sbeveloper	(elm)->field.le_next = (void *)1L;				\
12130ace1d7Sbeveloper	(elm)->field.le_prev = (void *)1L;
12230ace1d7Sbeveloper#else
12330ace1d7Sbeveloper#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
12430ace1d7Sbeveloper#define QUEUEDEBUG_LIST_OP(elm, field)
12530ace1d7Sbeveloper#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
12630ace1d7Sbeveloper#endif
12730ace1d7Sbeveloper
12830ace1d7Sbeveloper#define	LIST_INIT(head) do {						\
12930ace1d7Sbeveloper	(head)->lh_first = NULL;					\
13030ace1d7Sbeveloper} while (/*CONSTCOND*/0)
13130ace1d7Sbeveloper
13230ace1d7Sbeveloper#define LIST_INSERT_AFTER(listelm, elm, field) do {			\
13330ace1d7Sbeveloper	QUEUEDEBUG_LIST_OP((listelm), field)				\
13430ace1d7Sbeveloper	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
13530ace1d7Sbeveloper		(listelm)->field.le_next->field.le_prev =		\
13630ace1d7Sbeveloper		    &(elm)->field.le_next;				\
13730ace1d7Sbeveloper	(listelm)->field.le_next = (elm);				\
13830ace1d7Sbeveloper	(elm)->field.le_prev = &(listelm)->field.le_next;		\
13930ace1d7Sbeveloper} while (/*CONSTCOND*/0)
14030ace1d7Sbeveloper
14130ace1d7Sbeveloper#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
14230ace1d7Sbeveloper	QUEUEDEBUG_LIST_OP((listelm), field)				\
14330ace1d7Sbeveloper	(elm)->field.le_prev = (listelm)->field.le_prev;		\
14430ace1d7Sbeveloper	(elm)->field.le_next = (listelm);				\
14530ace1d7Sbeveloper	*(listelm)->field.le_prev = (elm);				\
14630ace1d7Sbeveloper	(listelm)->field.le_prev = &(elm)->field.le_next;		\
14730ace1d7Sbeveloper} while (/*CONSTCOND*/0)
14830ace1d7Sbeveloper
14930ace1d7Sbeveloper#define LIST_INSERT_HEAD(head, elm, field) do {				\
15030ace1d7Sbeveloper	QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field)		\
15130ace1d7Sbeveloper	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
15230ace1d7Sbeveloper		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
15330ace1d7Sbeveloper	(head)->lh_first = (elm);					\
15430ace1d7Sbeveloper	(elm)->field.le_prev = &(head)->lh_first;			\
15530ace1d7Sbeveloper} while (/*CONSTCOND*/0)
15630ace1d7Sbeveloper
15730ace1d7Sbeveloper#define LIST_REMOVE(elm, field) do {					\
15830ace1d7Sbeveloper	QUEUEDEBUG_LIST_OP((elm), field)				\
15930ace1d7Sbeveloper	if ((elm)->field.le_next != NULL)				\
16030ace1d7Sbeveloper		(elm)->field.le_next->field.le_prev = 			\
16130ace1d7Sbeveloper		    (elm)->field.le_prev;				\
16230ace1d7Sbeveloper	*(elm)->field.le_prev = (elm)->field.le_next;			\
16330ace1d7Sbeveloper	QUEUEDEBUG_LIST_POSTREMOVE((elm), field)			\
16430ace1d7Sbeveloper} while (/*CONSTCOND*/0)
16530ace1d7Sbeveloper
16630ace1d7Sbeveloper#define LIST_FOREACH(var, head, field)					\
16730ace1d7Sbeveloper	for ((var) = ((head)->lh_first);				\
16830ace1d7Sbeveloper		(var);							\
16930ace1d7Sbeveloper		(var) = ((var)->field.le_next))
17030ace1d7Sbeveloper
17130ace1d7Sbeveloper/*
17230ace1d7Sbeveloper * List access methods.
17330ace1d7Sbeveloper */
17430ace1d7Sbeveloper#define	LIST_EMPTY(head)		((head)->lh_first == NULL)
17530ace1d7Sbeveloper#define	LIST_FIRST(head)		((head)->lh_first)
17630ace1d7Sbeveloper#define	LIST_NEXT(elm, field)		((elm)->field.le_next)
17730ace1d7Sbeveloper
17830ace1d7Sbeveloper/*
17930ace1d7Sbeveloper * Singly-linked List definitions.
18030ace1d7Sbeveloper */
18130ace1d7Sbeveloper#define SLIST_HEAD(name, type)						\
18230ace1d7Sbeveloperstruct name {								\
18330ace1d7Sbeveloper	struct type *slh_first;	/* first element */			\
18430ace1d7Sbeveloper}
18530ace1d7Sbeveloper
18630ace1d7Sbeveloper#define SLIST_HEAD_INITIALIZER(head)					\
18730ace1d7Sbeveloper	{ NULL }
18830ace1d7Sbeveloper
18930ace1d7Sbeveloper#define SLIST_ENTRY(type)						\
19030ace1d7Sbeveloperstruct {								\
19130ace1d7Sbeveloper	struct type *sle_next;	/* next element */			\
19230ace1d7Sbeveloper}
19330ace1d7Sbeveloper
19430ace1d7Sbeveloper/*
19530ace1d7Sbeveloper * Singly-linked List functions.
19630ace1d7Sbeveloper */
19730ace1d7Sbeveloper#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
19830ace1d7Sbeveloper#define	SLIST_FIRST(head)	((head)->slh_first)
19930ace1d7Sbeveloper#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
20030ace1d7Sbeveloper
20130ace1d7Sbeveloper#define SLIST_FOREACH(var, head, field)					\
20230ace1d7Sbeveloper	for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
20330ace1d7Sbeveloper
20430ace1d7Sbeveloper#define SLIST_INIT(head) do {						\
20530ace1d7Sbeveloper	(head)->slh_first = NULL;					\
20630ace1d7Sbeveloper} while (/*CONSTCOND*/0)
20730ace1d7Sbeveloper
20830ace1d7Sbeveloper#define SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
20930ace1d7Sbeveloper	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
21030ace1d7Sbeveloper	(slistelm)->field.sle_next = (elm);				\
21130ace1d7Sbeveloper} while (/*CONSTCOND*/0)
21230ace1d7Sbeveloper
21330ace1d7Sbeveloper#define SLIST_INSERT_HEAD(head, elm, field) do {			\
21430ace1d7Sbeveloper	(elm)->field.sle_next = (head)->slh_first;			\
21530ace1d7Sbeveloper	(head)->slh_first = (elm);					\
21630ace1d7Sbeveloper} while (/*CONSTCOND*/0)
21730ace1d7Sbeveloper
21830ace1d7Sbeveloper#define SLIST_NEXT(elm, field)	((elm)->field.sle_next)
21930ace1d7Sbeveloper
22030ace1d7Sbeveloper#define SLIST_REMOVE_HEAD(head, field) do {				\
22130ace1d7Sbeveloper	(head)->slh_first = (head)->slh_first->field.sle_next;		\
22230ace1d7Sbeveloper} while (/*CONSTCOND*/0)
22330ace1d7Sbeveloper
22430ace1d7Sbeveloper#define SLIST_REMOVE(head, elm, type, field) do {			\
22530ace1d7Sbeveloper	if ((head)->slh_first == (elm)) {				\
22630ace1d7Sbeveloper		SLIST_REMOVE_HEAD((head), field);			\
22730ace1d7Sbeveloper	}								\
22830ace1d7Sbeveloper	else {								\
22930ace1d7Sbeveloper		struct type *curelm = (head)->slh_first;		\
23030ace1d7Sbeveloper		while(curelm->field.sle_next != (elm))			\
23130ace1d7Sbeveloper			curelm = curelm->field.sle_next;		\
23230ace1d7Sbeveloper		curelm->field.sle_next =				\
23330ace1d7Sbeveloper		    curelm->field.sle_next->field.sle_next;		\
23430ace1d7Sbeveloper	}								\
23530ace1d7Sbeveloper} while (/*CONSTCOND*/0)
23630ace1d7Sbeveloper
23730ace1d7Sbeveloper/*
23830ace1d7Sbeveloper * Simple queue definitions.
23930ace1d7Sbeveloper */
24030ace1d7Sbeveloper#define SIMPLEQ_HEAD(name, type)					\
24130ace1d7Sbeveloperstruct name {								\
24230ace1d7Sbeveloper	struct type *sqh_first;	/* first element */			\
24330ace1d7Sbeveloper	struct type **sqh_last;	/* addr of last next element */		\
24430ace1d7Sbeveloper}
24530ace1d7Sbeveloper
24630ace1d7Sbeveloper#define SIMPLEQ_HEAD_INITIALIZER(head)					\
24730ace1d7Sbeveloper	{ NULL, &(head).sqh_first }
24830ace1d7Sbeveloper
24930ace1d7Sbeveloper#define SIMPLEQ_ENTRY(type)						\
25030ace1d7Sbeveloperstruct {								\
25130ace1d7Sbeveloper	struct type *sqe_next;	/* next element */			\
25230ace1d7Sbeveloper}
25330ace1d7Sbeveloper
25430ace1d7Sbeveloper/*
25530ace1d7Sbeveloper * Simple queue functions.
25630ace1d7Sbeveloper */
25730ace1d7Sbeveloper#define	SIMPLEQ_INIT(head) do {						\
25830ace1d7Sbeveloper	(head)->sqh_first = NULL;					\
25930ace1d7Sbeveloper	(head)->sqh_last = &(head)->sqh_first;				\
26030ace1d7Sbeveloper} while (/*CONSTCOND*/0)
26130ace1d7Sbeveloper
26230ace1d7Sbeveloper#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
26330ace1d7Sbeveloper	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
26430ace1d7Sbeveloper		(head)->sqh_last = &(elm)->field.sqe_next;		\
26530ace1d7Sbeveloper	(head)->sqh_first = (elm);					\
26630ace1d7Sbeveloper} while (/*CONSTCOND*/0)
26730ace1d7Sbeveloper
26830ace1d7Sbeveloper#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
26930ace1d7Sbeveloper	(elm)->field.sqe_next = NULL;					\
27030ace1d7Sbeveloper	*(head)->sqh_last = (elm);					\
27130ace1d7Sbeveloper	(head)->sqh_last = &(elm)->field.sqe_next;			\
27230ace1d7Sbeveloper} while (/*CONSTCOND*/0)
27330ace1d7Sbeveloper
27430ace1d7Sbeveloper#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
27530ace1d7Sbeveloper	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
27630ace1d7Sbeveloper		(head)->sqh_last = &(elm)->field.sqe_next;		\
27730ace1d7Sbeveloper	(listelm)->field.sqe_next = (elm);				\
27830ace1d7Sbeveloper} while (/*CONSTCOND*/0)
27930ace1d7Sbeveloper
28030ace1d7Sbeveloper#define SIMPLEQ_REMOVE_HEAD(head, field) do {				\
28130ace1d7Sbeveloper	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
28230ace1d7Sbeveloper		(head)->sqh_last = &(head)->sqh_first;			\
28330ace1d7Sbeveloper} while (/*CONSTCOND*/0)
28430ace1d7Sbeveloper
28530ace1d7Sbeveloper#define SIMPLEQ_REMOVE(head, elm, type, field) do {			\
28630ace1d7Sbeveloper	if ((head)->sqh_first == (elm)) {				\
28730ace1d7Sbeveloper		SIMPLEQ_REMOVE_HEAD((head), field);			\
28830ace1d7Sbeveloper	} else {							\
28930ace1d7Sbeveloper		struct type *curelm = (head)->sqh_first;		\
29030ace1d7Sbeveloper		while (curelm->field.sqe_next != (elm))			\
29130ace1d7Sbeveloper			curelm = curelm->field.sqe_next;		\
29230ace1d7Sbeveloper		if ((curelm->field.sqe_next =				\
29330ace1d7Sbeveloper			curelm->field.sqe_next->field.sqe_next) == NULL) \
29430ace1d7Sbeveloper			    (head)->sqh_last = &(curelm)->field.sqe_next; \
29530ace1d7Sbeveloper	}								\
29630ace1d7Sbeveloper} while (/*CONSTCOND*/0)
29730ace1d7Sbeveloper
29830ace1d7Sbeveloper#define SIMPLEQ_FOREACH(var, head, field)				\
29930ace1d7Sbeveloper	for ((var) = ((head)->sqh_first);				\
30030ace1d7Sbeveloper		(var);							\
30130ace1d7Sbeveloper		(var) = ((var)->field.sqe_next))
30230ace1d7Sbeveloper
30330ace1d7Sbeveloper/*
30430ace1d7Sbeveloper * Simple queue access methods.
30530ace1d7Sbeveloper */
30630ace1d7Sbeveloper#define	SIMPLEQ_EMPTY(head)		((head)->sqh_first == NULL)
30730ace1d7Sbeveloper#define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
30830ace1d7Sbeveloper#define	SIMPLEQ_NEXT(elm, field)	((elm)->field.sqe_next)
30930ace1d7Sbeveloper
31030ace1d7Sbeveloper/*
31130ace1d7Sbeveloper * Tail queue definitions.
31230ace1d7Sbeveloper */
31330ace1d7Sbeveloper#define TAILQ_HEAD(name, type)						\
31430ace1d7Sbeveloperstruct name {								\
31530ace1d7Sbeveloper	struct type *tqh_first;	/* first element */			\
31630ace1d7Sbeveloper	struct type **tqh_last;	/* addr of last next element */		\
31730ace1d7Sbeveloper}
31830ace1d7Sbeveloper
31930ace1d7Sbeveloper#define TAILQ_HEAD_INITIALIZER(head)					\
32030ace1d7Sbeveloper	{ NULL, &(head).tqh_first }
32130ace1d7Sbeveloper
32230ace1d7Sbeveloper#define TAILQ_ENTRY(type)						\
32330ace1d7Sbeveloperstruct {								\
32430ace1d7Sbeveloper	struct type *tqe_next;	/* next element */			\
32530ace1d7Sbeveloper	struct type **tqe_prev;	/* address of previous next element */	\
32630ace1d7Sbeveloper}
32730ace1d7Sbeveloper
32830ace1d7Sbeveloper/*
32930ace1d7Sbeveloper * Tail queue functions.
33030ace1d7Sbeveloper */
33130ace1d7Sbeveloper#if defined(_KERNEL) && defined(QUEUEDEBUG)
33230ace1d7Sbeveloper#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)			\
33330ace1d7Sbeveloper	if ((head)->tqh_first &&					\
33430ace1d7Sbeveloper	    (head)->tqh_first->field.tqe_prev != &(head)->tqh_first)	\
33530ace1d7Sbeveloper		panic("TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
33630ace1d7Sbeveloper#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)			\
33730ace1d7Sbeveloper	if (*(head)->tqh_last != NULL)					\
33830ace1d7Sbeveloper		panic("TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__);
33930ace1d7Sbeveloper#define QUEUEDEBUG_TAILQ_OP(elm, field)					\
34030ace1d7Sbeveloper	if ((elm)->field.tqe_next &&					\
34130ace1d7Sbeveloper	    (elm)->field.tqe_next->field.tqe_prev !=			\
34230ace1d7Sbeveloper	    &(elm)->field.tqe_next)					\
34330ace1d7Sbeveloper		panic("TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
34430ace1d7Sbeveloper	if (*(elm)->field.tqe_prev != (elm))				\
34530ace1d7Sbeveloper		panic("TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__);
34630ace1d7Sbeveloper#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)				\
34730ace1d7Sbeveloper	(elm)->field.tqe_next = (void *)1L;				\
34830ace1d7Sbeveloper	(elm)->field.tqe_prev = (void *)1L;
34930ace1d7Sbeveloper#else
35030ace1d7Sbeveloper#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
35130ace1d7Sbeveloper#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
35230ace1d7Sbeveloper#define QUEUEDEBUG_TAILQ_OP(elm, field)
35330ace1d7Sbeveloper#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
35430ace1d7Sbeveloper#endif
35530ace1d7Sbeveloper
35630ace1d7Sbeveloper#define	TAILQ_INIT(head) do {						\
35730ace1d7Sbeveloper	(head)->tqh_first = NULL;					\
35830ace1d7Sbeveloper	(head)->tqh_last = &(head)->tqh_first;				\
35930ace1d7Sbeveloper} while (/*CONSTCOND*/0)
36030ace1d7Sbeveloper
36130ace1d7Sbeveloper#define TAILQ_INSERT_HEAD(head, elm, field) do {			\
36230ace1d7Sbeveloper	QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field)		\
36330ace1d7Sbeveloper	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
36430ace1d7Sbeveloper		(head)->tqh_first->field.tqe_prev =			\
36530ace1d7Sbeveloper		    &(elm)->field.tqe_next;				\
36630ace1d7Sbeveloper	else								\
36730ace1d7Sbeveloper		(head)->tqh_last = &(elm)->field.tqe_next;		\
36830ace1d7Sbeveloper	(head)->tqh_first = (elm);					\
36930ace1d7Sbeveloper	(elm)->field.tqe_prev = &(head)->tqh_first;			\
37030ace1d7Sbeveloper} while (/*CONSTCOND*/0)
37130ace1d7Sbeveloper
37230ace1d7Sbeveloper#define TAILQ_INSERT_TAIL(head, elm, field) do {			\
37330ace1d7Sbeveloper	QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field)		\
37430ace1d7Sbeveloper	(elm)->field.tqe_next = NULL;					\
37530ace1d7Sbeveloper	(elm)->field.tqe_prev = (head)->tqh_last;			\
37630ace1d7Sbeveloper	*(head)->tqh_last = (elm);					\
37730ace1d7Sbeveloper	(head)->tqh_last = &(elm)->field.tqe_next;			\
37830ace1d7Sbeveloper} while (/*CONSTCOND*/0)
37930ace1d7Sbeveloper
38030ace1d7Sbeveloper#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
38130ace1d7Sbeveloper	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
38230ace1d7Sbeveloper	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
38330ace1d7Sbeveloper		(elm)->field.tqe_next->field.tqe_prev = 		\
38430ace1d7Sbeveloper		    &(elm)->field.tqe_next;				\
38530ace1d7Sbeveloper	else								\
38630ace1d7Sbeveloper		(head)->tqh_last = &(elm)->field.tqe_next;		\
38730ace1d7Sbeveloper	(listelm)->field.tqe_next = (elm);				\
38830ace1d7Sbeveloper	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
38930ace1d7Sbeveloper} while (/*CONSTCOND*/0)
39030ace1d7Sbeveloper
39130ace1d7Sbeveloper#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
39230ace1d7Sbeveloper	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
39330ace1d7Sbeveloper	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
39430ace1d7Sbeveloper	(elm)->field.tqe_next = (listelm);				\
39530ace1d7Sbeveloper	*(listelm)->field.tqe_prev = (elm);				\
39630ace1d7Sbeveloper	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
39730ace1d7Sbeveloper} while (/*CONSTCOND*/0)
39830ace1d7Sbeveloper
39930ace1d7Sbeveloper#define TAILQ_REMOVE(head, elm, field) do {				\
40030ace1d7Sbeveloper	QUEUEDEBUG_TAILQ_OP((elm), field)				\
40130ace1d7Sbeveloper	if (((elm)->field.tqe_next) != NULL)				\
40230ace1d7Sbeveloper		(elm)->field.tqe_next->field.tqe_prev = 		\
40330ace1d7Sbeveloper		    (elm)->field.tqe_prev;				\
40430ace1d7Sbeveloper	else								\
40530ace1d7Sbeveloper		(head)->tqh_last = (elm)->field.tqe_prev;		\
40630ace1d7Sbeveloper	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
40730ace1d7Sbeveloper	QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field);			\
40830ace1d7Sbeveloper} while (/*CONSTCOND*/0)
40930ace1d7Sbeveloper
41030ace1d7Sbeveloper/*
41130ace1d7Sbeveloper * Tail queue access methods.
41230ace1d7Sbeveloper */
41330ace1d7Sbeveloper#define	TAILQ_EMPTY(head)		((head)->tqh_first == NULL)
41430ace1d7Sbeveloper#define	TAILQ_FIRST(head)		((head)->tqh_first)
41530ace1d7Sbeveloper#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
41630ace1d7Sbeveloper
41730ace1d7Sbeveloper#define TAILQ_LAST(head, headname) \
41830ace1d7Sbeveloper	(*(((struct headname *)((head)->tqh_last))->tqh_last))
41930ace1d7Sbeveloper#define TAILQ_PREV(elm, headname, field) \
42030ace1d7Sbeveloper	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
42130ace1d7Sbeveloper
42230ace1d7Sbeveloper#define TAILQ_FOREACH(var, head, field)					\
42330ace1d7Sbeveloper	for ((var) = ((head)->tqh_first);				\
42430ace1d7Sbeveloper		(var);							\
42530ace1d7Sbeveloper		(var) = ((var)->field.tqe_next))
42630ace1d7Sbeveloper
42730ace1d7Sbeveloper#define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
42830ace1d7Sbeveloper	for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));	\
42930ace1d7Sbeveloper		(var);							\
43030ace1d7Sbeveloper		(var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
43130ace1d7Sbeveloper
43230ace1d7Sbeveloper/*
43330ace1d7Sbeveloper * Circular queue definitions.
43430ace1d7Sbeveloper */
43530ace1d7Sbeveloper#define CIRCLEQ_HEAD(name, type)					\
43630ace1d7Sbeveloperstruct name {								\
43730ace1d7Sbeveloper	struct type *cqh_first;		/* first element */		\
43830ace1d7Sbeveloper	struct type *cqh_last;		/* last element */		\
43930ace1d7Sbeveloper}
44030ace1d7Sbeveloper
44130ace1d7Sbeveloper#define CIRCLEQ_HEAD_INITIALIZER(head)					\
44230ace1d7Sbeveloper	{ (void *)&head, (void *)&head }
44330ace1d7Sbeveloper
44430ace1d7Sbeveloper#define CIRCLEQ_ENTRY(type)						\
44530ace1d7Sbeveloperstruct {								\
44630ace1d7Sbeveloper	struct type *cqe_next;		/* next element */		\
44730ace1d7Sbeveloper	struct type *cqe_prev;		/* previous element */		\
44830ace1d7Sbeveloper}
44930ace1d7Sbeveloper
45030ace1d7Sbeveloper/*
45130ace1d7Sbeveloper * Circular queue functions.
45230ace1d7Sbeveloper */
45330ace1d7Sbeveloper#define	CIRCLEQ_INIT(head) do {						\
45430ace1d7Sbeveloper	(head)->cqh_first = (void *)(head);				\
45530ace1d7Sbeveloper	(head)->cqh_last = (void *)(head);				\
45630ace1d7Sbeveloper} while (/*CONSTCOND*/0)
45730ace1d7Sbeveloper
45830ace1d7Sbeveloper#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
45930ace1d7Sbeveloper	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
46030ace1d7Sbeveloper	(elm)->field.cqe_prev = (listelm);				\
46130ace1d7Sbeveloper	if ((listelm)->field.cqe_next == (void *)(head))		\
46230ace1d7Sbeveloper		(head)->cqh_last = (elm);				\
46330ace1d7Sbeveloper	else								\
46430ace1d7Sbeveloper		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
46530ace1d7Sbeveloper	(listelm)->field.cqe_next = (elm);				\
46630ace1d7Sbeveloper} while (/*CONSTCOND*/0)
46730ace1d7Sbeveloper
46830ace1d7Sbeveloper#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
46930ace1d7Sbeveloper	(elm)->field.cqe_next = (listelm);				\
47030ace1d7Sbeveloper	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
47130ace1d7Sbeveloper	if ((listelm)->field.cqe_prev == (void *)(head))		\
47230ace1d7Sbeveloper		(head)->cqh_first = (elm);				\
47330ace1d7Sbeveloper	else								\
47430ace1d7Sbeveloper		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
47530ace1d7Sbeveloper	(listelm)->field.cqe_prev = (elm);				\
47630ace1d7Sbeveloper} while (/*CONSTCOND*/0)
47730ace1d7Sbeveloper
47830ace1d7Sbeveloper#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
47930ace1d7Sbeveloper	(elm)->field.cqe_next = (head)->cqh_first;			\
48030ace1d7Sbeveloper	(elm)->field.cqe_prev = (void *)(head);				\
48130ace1d7Sbeveloper	if ((head)->cqh_last == (void *)(head))				\
48230ace1d7Sbeveloper		(head)->cqh_last = (elm);				\
48330ace1d7Sbeveloper	else								\
48430ace1d7Sbeveloper		(head)->cqh_first->field.cqe_prev = (elm);		\
48530ace1d7Sbeveloper	(head)->cqh_first = (elm);					\
48630ace1d7Sbeveloper} while (/*CONSTCOND*/0)
48730ace1d7Sbeveloper
48830ace1d7Sbeveloper#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
48930ace1d7Sbeveloper	(elm)->field.cqe_next = (void *)(head);				\
49030ace1d7Sbeveloper	(elm)->field.cqe_prev = (head)->cqh_last;			\
49130ace1d7Sbeveloper	if ((head)->cqh_first == (void *)(head))			\
49230ace1d7Sbeveloper		(head)->cqh_first = (elm);				\
49330ace1d7Sbeveloper	else								\
49430ace1d7Sbeveloper		(head)->cqh_last->field.cqe_next = (elm);		\
49530ace1d7Sbeveloper	(head)->cqh_last = (elm);					\
49630ace1d7Sbeveloper} while (/*CONSTCOND*/0)
49730ace1d7Sbeveloper
49830ace1d7Sbeveloper#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
49930ace1d7Sbeveloper	if ((elm)->field.cqe_next == (void *)(head))			\
50030ace1d7Sbeveloper		(head)->cqh_last = (elm)->field.cqe_prev;		\
50130ace1d7Sbeveloper	else								\
50230ace1d7Sbeveloper		(elm)->field.cqe_next->field.cqe_prev =			\
50330ace1d7Sbeveloper		    (elm)->field.cqe_prev;				\
50430ace1d7Sbeveloper	if ((elm)->field.cqe_prev == (void *)(head))			\
50530ace1d7Sbeveloper		(head)->cqh_first = (elm)->field.cqe_next;		\
50630ace1d7Sbeveloper	else								\
50730ace1d7Sbeveloper		(elm)->field.cqe_prev->field.cqe_next =			\
50830ace1d7Sbeveloper		    (elm)->field.cqe_next;				\
50930ace1d7Sbeveloper} while (/*CONSTCOND*/0)
51030ace1d7Sbeveloper
51130ace1d7Sbeveloper#define CIRCLEQ_FOREACH(var, head, field)				\
51230ace1d7Sbeveloper	for ((var) = ((head)->cqh_first);				\
51330ace1d7Sbeveloper		(var) != (void *)(head);				\
51430ace1d7Sbeveloper		(var) = ((var)->field.cqe_next))
51530ace1d7Sbeveloper
51630ace1d7Sbeveloper#define CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
51730ace1d7Sbeveloper	for ((var) = ((head)->cqh_last);				\
51830ace1d7Sbeveloper		(var) != (void *)(head);				\
51930ace1d7Sbeveloper		(var) = ((var)->field.cqe_prev))
52030ace1d7Sbeveloper
52130ace1d7Sbeveloper/*
52230ace1d7Sbeveloper * Circular queue access methods.
52330ace1d7Sbeveloper */
52430ace1d7Sbeveloper#define	CIRCLEQ_EMPTY(head)		((head)->cqh_first == (void *)(head))
52530ace1d7Sbeveloper#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
52630ace1d7Sbeveloper#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
52730ace1d7Sbeveloper#define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
52830ace1d7Sbeveloper#define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
52930ace1d7Sbeveloper#endif	/* !_SYS_QUEUE_H_ */
530