187ebb10aSJérôme Duval/*	$NetBSD: queue.h,v 1.31 2002/06/01 23:51:05 lukem Exp $	*/
287ebb10aSJérôme Duval
387ebb10aSJérôme Duval/*
487ebb10aSJérôme Duval * Copyright (c) 1991, 1993
587ebb10aSJérôme Duval *	The Regents of the University of California.  All rights reserved.
687ebb10aSJérôme Duval *
787ebb10aSJérôme Duval * Redistribution and use in source and binary forms, with or without
887ebb10aSJérôme Duval * modification, are permitted provided that the following conditions
987ebb10aSJérôme Duval * are met:
1087ebb10aSJérôme Duval * 1. Redistributions of source code must retain the above copyright
1187ebb10aSJérôme Duval *    notice, this list of conditions and the following disclaimer.
1287ebb10aSJérôme Duval * 2. Redistributions in binary form must reproduce the above copyright
1387ebb10aSJérôme Duval *    notice, this list of conditions and the following disclaimer in the
1487ebb10aSJérôme Duval *    documentation and/or other materials provided with the distribution.
1587ebb10aSJérôme Duval * 3. All advertising materials mentioning features or use of this software
1687ebb10aSJérôme Duval *    must display the following acknowledgement:
1787ebb10aSJérôme Duval *	This product includes software developed by the University of
1887ebb10aSJérôme Duval *	California, Berkeley and its contributors.
1987ebb10aSJérôme Duval * 4. Neither the name of the University nor the names of its contributors
2087ebb10aSJérôme Duval *    may be used to endorse or promote products derived from this software
2187ebb10aSJérôme Duval *    without specific prior written permission.
2287ebb10aSJérôme Duval *
2387ebb10aSJérôme Duval * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
2487ebb10aSJérôme Duval * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
2587ebb10aSJérôme Duval * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2687ebb10aSJérôme Duval * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
2787ebb10aSJérôme Duval * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
2887ebb10aSJérôme Duval * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
2987ebb10aSJérôme Duval * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
3087ebb10aSJérôme Duval * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
3187ebb10aSJérôme Duval * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
3287ebb10aSJérôme Duval * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
3387ebb10aSJérôme Duval * SUCH DAMAGE.
3487ebb10aSJérôme Duval *
3587ebb10aSJérôme Duval *	@(#)queue.h	8.5 (Berkeley) 8/20/94
3687ebb10aSJérôme Duval */
3787ebb10aSJérôme Duval
3887ebb10aSJérôme Duval#ifndef	_SYS_QUEUE_H_
3987ebb10aSJérôme Duval#define	_SYS_QUEUE_H_
4087ebb10aSJérôme Duval
4187ebb10aSJérôme Duval/*
4287ebb10aSJérôme Duval * This file defines five types of data structures: singly-linked lists,
4387ebb10aSJérôme Duval * lists, simple queues, tail queues, and circular queues.
4487ebb10aSJérôme Duval *
4587ebb10aSJérôme Duval * A singly-linked list is headed by a single forward pointer. The
4687ebb10aSJérôme Duval * elements are singly linked for minimum space and pointer manipulation
4787ebb10aSJérôme Duval * overhead at the expense of O(n) removal for arbitrary elements. New
4887ebb10aSJérôme Duval * elements can be added to the list after an existing element or at the
4987ebb10aSJérôme Duval * head of the list.  Elements being removed from the head of the list
5087ebb10aSJérôme Duval * should use the explicit macro for this purpose for optimum
5187ebb10aSJérôme Duval * efficiency. A singly-linked list may only be traversed in the forward
5287ebb10aSJérôme Duval * direction.  Singly-linked lists are ideal for applications with large
5387ebb10aSJérôme Duval * datasets and few or no removals or for implementing a LIFO queue.
5487ebb10aSJérôme Duval *
5587ebb10aSJérôme Duval * A list is headed by a single forward pointer (or an array of forward
5687ebb10aSJérôme Duval * pointers for a hash table header). The elements are doubly linked
5787ebb10aSJérôme Duval * so that an arbitrary element can be removed without a need to
5887ebb10aSJérôme Duval * traverse the list. New elements can be added to the list before
5987ebb10aSJérôme Duval * or after an existing element or at the head of the list. A list
6087ebb10aSJérôme Duval * may only be traversed in the forward direction.
6187ebb10aSJérôme Duval *
6287ebb10aSJérôme Duval * A simple queue is headed by a pair of pointers, one the head of the
6387ebb10aSJérôme Duval * list and the other to the tail of the list. The elements are singly
6487ebb10aSJérôme Duval * linked to save space, so only elements can only be removed from the
6587ebb10aSJérôme Duval * head of the list. New elements can be added to the list after
6687ebb10aSJérôme Duval * an existing element, at the head of the list, or at the end of the
6787ebb10aSJérôme Duval * list. A simple queue may only be traversed in the forward direction.
6887ebb10aSJérôme Duval *
6987ebb10aSJérôme Duval * A tail queue is headed by a pair of pointers, one to the head of the
7087ebb10aSJérôme Duval * list and the other to the tail of the list. The elements are doubly
7187ebb10aSJérôme Duval * linked so that an arbitrary element can be removed without a need to
7287ebb10aSJérôme Duval * traverse the list. New elements can be added to the list before or
7387ebb10aSJérôme Duval * after an existing element, at the head of the list, or at the end of
7487ebb10aSJérôme Duval * the list. A tail queue may be traversed in either direction.
7587ebb10aSJérôme Duval *
7687ebb10aSJérôme Duval * A circle queue is headed by a pair of pointers, one to the head of the
7787ebb10aSJérôme Duval * list and the other to the tail of the list. The elements are doubly
7887ebb10aSJérôme Duval * linked so that an arbitrary element can be removed without a need to
7987ebb10aSJérôme Duval * traverse the list. New elements can be added to the list before or after
8087ebb10aSJérôme Duval * an existing element, at the head of the list, or at the end of the list.
8187ebb10aSJérôme Duval * A circle queue may be traversed in either direction, but has a more
8287ebb10aSJérôme Duval * complex end of list detection.
8387ebb10aSJérôme Duval *
8487ebb10aSJérôme Duval * For details on the use of these macros, see the queue(3) manual page.
8587ebb10aSJérôme Duval */
8687ebb10aSJérôme Duval
8787ebb10aSJérôme Duval/*
8887ebb10aSJérôme Duval * List definitions.
8987ebb10aSJérôme Duval */
9087ebb10aSJérôme Duval#define LIST_HEAD(name, type)						\
9187ebb10aSJérôme Duvalstruct name {								\
9287ebb10aSJérôme Duval	struct type *lh_first;	/* first element */			\
9387ebb10aSJérôme Duval}
9487ebb10aSJérôme Duval
9587ebb10aSJérôme Duval#define LIST_HEAD_INITIALIZER(head)					\
9687ebb10aSJérôme Duval	{ NULL }
9787ebb10aSJérôme Duval
9887ebb10aSJérôme Duval#define LIST_ENTRY(type)						\
9987ebb10aSJérôme Duvalstruct {								\
10087ebb10aSJérôme Duval	struct type *le_next;	/* next element */			\
10187ebb10aSJérôme Duval	struct type **le_prev;	/* address of previous next element */	\
10287ebb10aSJérôme Duval}
10387ebb10aSJérôme Duval
10487ebb10aSJérôme Duval/*
10587ebb10aSJérôme Duval * List functions.
10687ebb10aSJérôme Duval */
10787ebb10aSJérôme Duval#if defined(_KERNEL) && defined(QUEUEDEBUG)
10887ebb10aSJérôme Duval#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)			\
10987ebb10aSJérôme Duval	if ((head)->lh_first &&						\
11087ebb10aSJérôme Duval	    (head)->lh_first->field.le_prev != &(head)->lh_first)	\
11187ebb10aSJérôme Duval		panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
11287ebb10aSJérôme Duval#define QUEUEDEBUG_LIST_OP(elm, field)					\
11387ebb10aSJérôme Duval	if ((elm)->field.le_next &&					\
11487ebb10aSJérôme Duval	    (elm)->field.le_next->field.le_prev !=			\
11587ebb10aSJérôme Duval	    &(elm)->field.le_next)					\
11687ebb10aSJérôme Duval		panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
11787ebb10aSJérôme Duval	if (*(elm)->field.le_prev != (elm))				\
11887ebb10aSJérôme Duval		panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__);
11987ebb10aSJérôme Duval#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)				\
12087ebb10aSJérôme Duval	(elm)->field.le_next = (void *)1L;				\
12187ebb10aSJérôme Duval	(elm)->field.le_prev = (void *)1L;
12287ebb10aSJérôme Duval#else
12387ebb10aSJérôme Duval#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
12487ebb10aSJérôme Duval#define QUEUEDEBUG_LIST_OP(elm, field)
12587ebb10aSJérôme Duval#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
12687ebb10aSJérôme Duval#endif
12787ebb10aSJérôme Duval
12887ebb10aSJérôme Duval#define	LIST_INIT(head) do {						\
12987ebb10aSJérôme Duval	(head)->lh_first = NULL;					\
13087ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
13187ebb10aSJérôme Duval
13287ebb10aSJérôme Duval#define LIST_INSERT_AFTER(listelm, elm, field) do {			\
13387ebb10aSJérôme Duval	QUEUEDEBUG_LIST_OP((listelm), field)				\
13487ebb10aSJérôme Duval	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
13587ebb10aSJérôme Duval		(listelm)->field.le_next->field.le_prev =		\
13687ebb10aSJérôme Duval		    &(elm)->field.le_next;				\
13787ebb10aSJérôme Duval	(listelm)->field.le_next = (elm);				\
13887ebb10aSJérôme Duval	(elm)->field.le_prev = &(listelm)->field.le_next;		\
13987ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
14087ebb10aSJérôme Duval
14187ebb10aSJérôme Duval#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
14287ebb10aSJérôme Duval	QUEUEDEBUG_LIST_OP((listelm), field)				\
14387ebb10aSJérôme Duval	(elm)->field.le_prev = (listelm)->field.le_prev;		\
14487ebb10aSJérôme Duval	(elm)->field.le_next = (listelm);				\
14587ebb10aSJérôme Duval	*(listelm)->field.le_prev = (elm);				\
14687ebb10aSJérôme Duval	(listelm)->field.le_prev = &(elm)->field.le_next;		\
14787ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
14887ebb10aSJérôme Duval
14987ebb10aSJérôme Duval#define LIST_INSERT_HEAD(head, elm, field) do {				\
15087ebb10aSJérôme Duval	QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field)		\
15187ebb10aSJérôme Duval	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
15287ebb10aSJérôme Duval		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
15387ebb10aSJérôme Duval	(head)->lh_first = (elm);					\
15487ebb10aSJérôme Duval	(elm)->field.le_prev = &(head)->lh_first;			\
15587ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
15687ebb10aSJérôme Duval
15787ebb10aSJérôme Duval#define LIST_REMOVE(elm, field) do {					\
15887ebb10aSJérôme Duval	QUEUEDEBUG_LIST_OP((elm), field)				\
15987ebb10aSJérôme Duval	if ((elm)->field.le_next != NULL)				\
16087ebb10aSJérôme Duval		(elm)->field.le_next->field.le_prev = 			\
16187ebb10aSJérôme Duval		    (elm)->field.le_prev;				\
16287ebb10aSJérôme Duval	*(elm)->field.le_prev = (elm)->field.le_next;			\
16387ebb10aSJérôme Duval	QUEUEDEBUG_LIST_POSTREMOVE((elm), field)			\
16487ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
16587ebb10aSJérôme Duval
16687ebb10aSJérôme Duval#define LIST_FOREACH(var, head, field)					\
16787ebb10aSJérôme Duval	for ((var) = ((head)->lh_first);				\
16887ebb10aSJérôme Duval		(var);							\
16987ebb10aSJérôme Duval		(var) = ((var)->field.le_next))
17087ebb10aSJérôme Duval
17187ebb10aSJérôme Duval/*
17287ebb10aSJérôme Duval * List access methods.
17387ebb10aSJérôme Duval */
17487ebb10aSJérôme Duval#define	LIST_EMPTY(head)		((head)->lh_first == NULL)
17587ebb10aSJérôme Duval#define	LIST_FIRST(head)		((head)->lh_first)
17687ebb10aSJérôme Duval#define	LIST_NEXT(elm, field)		((elm)->field.le_next)
17787ebb10aSJérôme Duval
17887ebb10aSJérôme Duval/*
17987ebb10aSJérôme Duval * Singly-linked List definitions.
18087ebb10aSJérôme Duval */
18187ebb10aSJérôme Duval#define SLIST_HEAD(name, type)						\
18287ebb10aSJérôme Duvalstruct name {								\
18387ebb10aSJérôme Duval	struct type *slh_first;	/* first element */			\
18487ebb10aSJérôme Duval}
18587ebb10aSJérôme Duval
18687ebb10aSJérôme Duval#define SLIST_HEAD_INITIALIZER(head)					\
18787ebb10aSJérôme Duval	{ NULL }
18887ebb10aSJérôme Duval
18987ebb10aSJérôme Duval#define SLIST_ENTRY(type)						\
19087ebb10aSJérôme Duvalstruct {								\
19187ebb10aSJérôme Duval	struct type *sle_next;	/* next element */			\
19287ebb10aSJérôme Duval}
19387ebb10aSJérôme Duval
19487ebb10aSJérôme Duval/*
19587ebb10aSJérôme Duval * Singly-linked List functions.
19687ebb10aSJérôme Duval */
19787ebb10aSJérôme Duval#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
19887ebb10aSJérôme Duval#define	SLIST_FIRST(head)	((head)->slh_first)
19987ebb10aSJérôme Duval#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
20087ebb10aSJérôme Duval
20187ebb10aSJérôme Duval#define SLIST_FOREACH(var, head, field)					\
20287ebb10aSJérôme Duval	for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
20387ebb10aSJérôme Duval
20487ebb10aSJérôme Duval#define SLIST_INIT(head) do {						\
20587ebb10aSJérôme Duval	(head)->slh_first = NULL;					\
20687ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
20787ebb10aSJérôme Duval
20887ebb10aSJérôme Duval#define SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
20987ebb10aSJérôme Duval	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
21087ebb10aSJérôme Duval	(slistelm)->field.sle_next = (elm);				\
21187ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
21287ebb10aSJérôme Duval
21387ebb10aSJérôme Duval#define SLIST_INSERT_HEAD(head, elm, field) do {			\
21487ebb10aSJérôme Duval	(elm)->field.sle_next = (head)->slh_first;			\
21587ebb10aSJérôme Duval	(head)->slh_first = (elm);					\
21687ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
21787ebb10aSJérôme Duval
21887ebb10aSJérôme Duval#define SLIST_NEXT(elm, field)	((elm)->field.sle_next)
21987ebb10aSJérôme Duval
22087ebb10aSJérôme Duval#define SLIST_REMOVE_HEAD(head, field) do {				\
22187ebb10aSJérôme Duval	(head)->slh_first = (head)->slh_first->field.sle_next;		\
22287ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
22387ebb10aSJérôme Duval
22487ebb10aSJérôme Duval#define SLIST_REMOVE(head, elm, type, field) do {			\
22587ebb10aSJérôme Duval	if ((head)->slh_first == (elm)) {				\
22687ebb10aSJérôme Duval		SLIST_REMOVE_HEAD((head), field);			\
22787ebb10aSJérôme Duval	}								\
22887ebb10aSJérôme Duval	else {								\
22987ebb10aSJérôme Duval		struct type *curelm = (head)->slh_first;		\
23087ebb10aSJérôme Duval		while(curelm->field.sle_next != (elm))			\
23187ebb10aSJérôme Duval			curelm = curelm->field.sle_next;		\
23287ebb10aSJérôme Duval		curelm->field.sle_next =				\
23387ebb10aSJérôme Duval		    curelm->field.sle_next->field.sle_next;		\
23487ebb10aSJérôme Duval	}								\
23587ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
23687ebb10aSJérôme Duval
23787ebb10aSJérôme Duval/*
23887ebb10aSJérôme Duval * Simple queue definitions.
23987ebb10aSJérôme Duval */
24087ebb10aSJérôme Duval#define SIMPLEQ_HEAD(name, type)					\
24187ebb10aSJérôme Duvalstruct name {								\
24287ebb10aSJérôme Duval	struct type *sqh_first;	/* first element */			\
24387ebb10aSJérôme Duval	struct type **sqh_last;	/* addr of last next element */		\
24487ebb10aSJérôme Duval}
24587ebb10aSJérôme Duval
24687ebb10aSJérôme Duval#define SIMPLEQ_HEAD_INITIALIZER(head)					\
24787ebb10aSJérôme Duval	{ NULL, &(head).sqh_first }
24887ebb10aSJérôme Duval
24987ebb10aSJérôme Duval#define SIMPLEQ_ENTRY(type)						\
25087ebb10aSJérôme Duvalstruct {								\
25187ebb10aSJérôme Duval	struct type *sqe_next;	/* next element */			\
25287ebb10aSJérôme Duval}
25387ebb10aSJérôme Duval
25487ebb10aSJérôme Duval/*
25587ebb10aSJérôme Duval * Simple queue functions.
25687ebb10aSJérôme Duval */
25787ebb10aSJérôme Duval#define	SIMPLEQ_INIT(head) do {						\
25887ebb10aSJérôme Duval	(head)->sqh_first = NULL;					\
25987ebb10aSJérôme Duval	(head)->sqh_last = &(head)->sqh_first;				\
26087ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
26187ebb10aSJérôme Duval
26287ebb10aSJérôme Duval#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
26387ebb10aSJérôme Duval	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
26487ebb10aSJérôme Duval		(head)->sqh_last = &(elm)->field.sqe_next;		\
26587ebb10aSJérôme Duval	(head)->sqh_first = (elm);					\
26687ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
26787ebb10aSJérôme Duval
26887ebb10aSJérôme Duval#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
26987ebb10aSJérôme Duval	(elm)->field.sqe_next = NULL;					\
27087ebb10aSJérôme Duval	*(head)->sqh_last = (elm);					\
27187ebb10aSJérôme Duval	(head)->sqh_last = &(elm)->field.sqe_next;			\
27287ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
27387ebb10aSJérôme Duval
27487ebb10aSJérôme Duval#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
27587ebb10aSJérôme Duval	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
27687ebb10aSJérôme Duval		(head)->sqh_last = &(elm)->field.sqe_next;		\
27787ebb10aSJérôme Duval	(listelm)->field.sqe_next = (elm);				\
27887ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
27987ebb10aSJérôme Duval
28087ebb10aSJérôme Duval#define SIMPLEQ_REMOVE_HEAD(head, field) do {				\
28187ebb10aSJérôme Duval	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
28287ebb10aSJérôme Duval		(head)->sqh_last = &(head)->sqh_first;			\
28387ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
28487ebb10aSJérôme Duval
28587ebb10aSJérôme Duval#define SIMPLEQ_REMOVE(head, elm, type, field) do {			\
28687ebb10aSJérôme Duval	if ((head)->sqh_first == (elm)) {				\
28787ebb10aSJérôme Duval		SIMPLEQ_REMOVE_HEAD((head), field);			\
28887ebb10aSJérôme Duval	} else {							\
28987ebb10aSJérôme Duval		struct type *curelm = (head)->sqh_first;		\
29087ebb10aSJérôme Duval		while (curelm->field.sqe_next != (elm))			\
29187ebb10aSJérôme Duval			curelm = curelm->field.sqe_next;		\
29287ebb10aSJérôme Duval		if ((curelm->field.sqe_next =				\
29387ebb10aSJérôme Duval			curelm->field.sqe_next->field.sqe_next) == NULL) \
29487ebb10aSJérôme Duval			    (head)->sqh_last = &(curelm)->field.sqe_next; \
29587ebb10aSJérôme Duval	}								\
29687ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
29787ebb10aSJérôme Duval
29887ebb10aSJérôme Duval#define SIMPLEQ_FOREACH(var, head, field)				\
29987ebb10aSJérôme Duval	for ((var) = ((head)->sqh_first);				\
30087ebb10aSJérôme Duval		(var);							\
30187ebb10aSJérôme Duval		(var) = ((var)->field.sqe_next))
30287ebb10aSJérôme Duval
30387ebb10aSJérôme Duval/*
30487ebb10aSJérôme Duval * Simple queue access methods.
30587ebb10aSJérôme Duval */
30687ebb10aSJérôme Duval#define	SIMPLEQ_EMPTY(head)		((head)->sqh_first == NULL)
30787ebb10aSJérôme Duval#define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
30887ebb10aSJérôme Duval#define	SIMPLEQ_NEXT(elm, field)	((elm)->field.sqe_next)
30987ebb10aSJérôme Duval
31087ebb10aSJérôme Duval/*
31187ebb10aSJérôme Duval * Tail queue definitions.
31287ebb10aSJérôme Duval */
31387ebb10aSJérôme Duval#define TAILQ_HEAD(name, type)						\
31487ebb10aSJérôme Duvalstruct name {								\
31587ebb10aSJérôme Duval	struct type *tqh_first;	/* first element */			\
31687ebb10aSJérôme Duval	struct type **tqh_last;	/* addr of last next element */		\
31787ebb10aSJérôme Duval}
31887ebb10aSJérôme Duval
31987ebb10aSJérôme Duval#define TAILQ_HEAD_INITIALIZER(head)					\
32087ebb10aSJérôme Duval	{ NULL, &(head).tqh_first }
32187ebb10aSJérôme Duval
32287ebb10aSJérôme Duval#define TAILQ_ENTRY(type)						\
32387ebb10aSJérôme Duvalstruct {								\
32487ebb10aSJérôme Duval	struct type *tqe_next;	/* next element */			\
32587ebb10aSJérôme Duval	struct type **tqe_prev;	/* address of previous next element */	\
32687ebb10aSJérôme Duval}
32787ebb10aSJérôme Duval
32887ebb10aSJérôme Duval/*
32987ebb10aSJérôme Duval * Tail queue functions.
33087ebb10aSJérôme Duval */
33187ebb10aSJérôme Duval#if defined(_KERNEL) && defined(QUEUEDEBUG)
33287ebb10aSJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)			\
33387ebb10aSJérôme Duval	if ((head)->tqh_first &&					\
33487ebb10aSJérôme Duval	    (head)->tqh_first->field.tqe_prev != &(head)->tqh_first)	\
33587ebb10aSJérôme Duval		panic("TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
33687ebb10aSJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)			\
33787ebb10aSJérôme Duval	if (*(head)->tqh_last != NULL)					\
33887ebb10aSJérôme Duval		panic("TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__);
33987ebb10aSJérôme Duval#define QUEUEDEBUG_TAILQ_OP(elm, field)					\
34087ebb10aSJérôme Duval	if ((elm)->field.tqe_next &&					\
34187ebb10aSJérôme Duval	    (elm)->field.tqe_next->field.tqe_prev !=			\
34287ebb10aSJérôme Duval	    &(elm)->field.tqe_next)					\
34387ebb10aSJérôme Duval		panic("TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
34487ebb10aSJérôme Duval	if (*(elm)->field.tqe_prev != (elm))				\
34587ebb10aSJérôme Duval		panic("TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__);
34687ebb10aSJérôme Duval#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)				\
34787ebb10aSJérôme Duval	(elm)->field.tqe_next = (void *)1L;				\
34887ebb10aSJérôme Duval	(elm)->field.tqe_prev = (void *)1L;
34987ebb10aSJérôme Duval#else
35087ebb10aSJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
35187ebb10aSJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
35287ebb10aSJérôme Duval#define QUEUEDEBUG_TAILQ_OP(elm, field)
35387ebb10aSJérôme Duval#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
35487ebb10aSJérôme Duval#endif
35587ebb10aSJérôme Duval
35687ebb10aSJérôme Duval#define	TAILQ_INIT(head) do {						\
35787ebb10aSJérôme Duval	(head)->tqh_first = NULL;					\
35887ebb10aSJérôme Duval	(head)->tqh_last = &(head)->tqh_first;				\
35987ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
36087ebb10aSJérôme Duval
36187ebb10aSJérôme Duval#define TAILQ_INSERT_HEAD(head, elm, field) do {			\
36287ebb10aSJérôme Duval	QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field)		\
36387ebb10aSJérôme Duval	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
36487ebb10aSJérôme Duval		(head)->tqh_first->field.tqe_prev =			\
36587ebb10aSJérôme Duval		    &(elm)->field.tqe_next;				\
36687ebb10aSJérôme Duval	else								\
36787ebb10aSJérôme Duval		(head)->tqh_last = &(elm)->field.tqe_next;		\
36887ebb10aSJérôme Duval	(head)->tqh_first = (elm);					\
36987ebb10aSJérôme Duval	(elm)->field.tqe_prev = &(head)->tqh_first;			\
37087ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
37187ebb10aSJérôme Duval
37287ebb10aSJérôme Duval#define TAILQ_INSERT_TAIL(head, elm, field) do {			\
37387ebb10aSJérôme Duval	QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field)		\
37487ebb10aSJérôme Duval	(elm)->field.tqe_next = NULL;					\
37587ebb10aSJérôme Duval	(elm)->field.tqe_prev = (head)->tqh_last;			\
37687ebb10aSJérôme Duval	*(head)->tqh_last = (elm);					\
37787ebb10aSJérôme Duval	(head)->tqh_last = &(elm)->field.tqe_next;			\
37887ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
37987ebb10aSJérôme Duval
38087ebb10aSJérôme Duval#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
38187ebb10aSJérôme Duval	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
38287ebb10aSJérôme Duval	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
38387ebb10aSJérôme Duval		(elm)->field.tqe_next->field.tqe_prev = 		\
38487ebb10aSJérôme Duval		    &(elm)->field.tqe_next;				\
38587ebb10aSJérôme Duval	else								\
38687ebb10aSJérôme Duval		(head)->tqh_last = &(elm)->field.tqe_next;		\
38787ebb10aSJérôme Duval	(listelm)->field.tqe_next = (elm);				\
38887ebb10aSJérôme Duval	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
38987ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
39087ebb10aSJérôme Duval
39187ebb10aSJérôme Duval#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
39287ebb10aSJérôme Duval	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
39387ebb10aSJérôme Duval	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
39487ebb10aSJérôme Duval	(elm)->field.tqe_next = (listelm);				\
39587ebb10aSJérôme Duval	*(listelm)->field.tqe_prev = (elm);				\
39687ebb10aSJérôme Duval	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
39787ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
39887ebb10aSJérôme Duval
39987ebb10aSJérôme Duval#define TAILQ_REMOVE(head, elm, field) do {				\
40087ebb10aSJérôme Duval	QUEUEDEBUG_TAILQ_OP((elm), field)				\
40187ebb10aSJérôme Duval	if (((elm)->field.tqe_next) != NULL)				\
40287ebb10aSJérôme Duval		(elm)->field.tqe_next->field.tqe_prev = 		\
40387ebb10aSJérôme Duval		    (elm)->field.tqe_prev;				\
40487ebb10aSJérôme Duval	else								\
40587ebb10aSJérôme Duval		(head)->tqh_last = (elm)->field.tqe_prev;		\
40687ebb10aSJérôme Duval	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
40787ebb10aSJérôme Duval	QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field);			\
40887ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
40987ebb10aSJérôme Duval
41087ebb10aSJérôme Duval/*
41187ebb10aSJérôme Duval * Tail queue access methods.
41287ebb10aSJérôme Duval */
41387ebb10aSJérôme Duval#define	TAILQ_EMPTY(head)		((head)->tqh_first == NULL)
41487ebb10aSJérôme Duval#define	TAILQ_FIRST(head)		((head)->tqh_first)
41587ebb10aSJérôme Duval#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
41687ebb10aSJérôme Duval
41787ebb10aSJérôme Duval#define TAILQ_LAST(head, headname) \
41887ebb10aSJérôme Duval	(*(((struct headname *)((head)->tqh_last))->tqh_last))
41987ebb10aSJérôme Duval#define TAILQ_PREV(elm, headname, field) \
42087ebb10aSJérôme Duval	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
42187ebb10aSJérôme Duval
42287ebb10aSJérôme Duval#define TAILQ_FOREACH(var, head, field)					\
42387ebb10aSJérôme Duval	for ((var) = ((head)->tqh_first);				\
42487ebb10aSJérôme Duval		(var);							\
42587ebb10aSJérôme Duval		(var) = ((var)->field.tqe_next))
42687ebb10aSJérôme Duval
42787ebb10aSJérôme Duval#define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
42887ebb10aSJérôme Duval	for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));	\
42987ebb10aSJérôme Duval		(var);							\
43087ebb10aSJérôme Duval		(var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
43187ebb10aSJérôme Duval
43287ebb10aSJérôme Duval/*
43387ebb10aSJérôme Duval * Circular queue definitions.
43487ebb10aSJérôme Duval */
43587ebb10aSJérôme Duval#define CIRCLEQ_HEAD(name, type)					\
43687ebb10aSJérôme Duvalstruct name {								\
43787ebb10aSJérôme Duval	struct type *cqh_first;		/* first element */		\
43887ebb10aSJérôme Duval	struct type *cqh_last;		/* last element */		\
43987ebb10aSJérôme Duval}
44087ebb10aSJérôme Duval
44187ebb10aSJérôme Duval#define CIRCLEQ_HEAD_INITIALIZER(head)					\
44287ebb10aSJérôme Duval	{ (void *)&head, (void *)&head }
44387ebb10aSJérôme Duval
44487ebb10aSJérôme Duval#define CIRCLEQ_ENTRY(type)						\
44587ebb10aSJérôme Duvalstruct {								\
44687ebb10aSJérôme Duval	struct type *cqe_next;		/* next element */		\
44787ebb10aSJérôme Duval	struct type *cqe_prev;		/* previous element */		\
44887ebb10aSJérôme Duval}
44987ebb10aSJérôme Duval
45087ebb10aSJérôme Duval/*
45187ebb10aSJérôme Duval * Circular queue functions.
45287ebb10aSJérôme Duval */
45387ebb10aSJérôme Duval#define	CIRCLEQ_INIT(head) do {						\
45487ebb10aSJérôme Duval	(head)->cqh_first = (void *)(head);				\
45587ebb10aSJérôme Duval	(head)->cqh_last = (void *)(head);				\
45687ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
45787ebb10aSJérôme Duval
45887ebb10aSJérôme Duval#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
45987ebb10aSJérôme Duval	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
46087ebb10aSJérôme Duval	(elm)->field.cqe_prev = (listelm);				\
46187ebb10aSJérôme Duval	if ((listelm)->field.cqe_next == (void *)(head))		\
46287ebb10aSJérôme Duval		(head)->cqh_last = (elm);				\
46387ebb10aSJérôme Duval	else								\
46487ebb10aSJérôme Duval		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
46587ebb10aSJérôme Duval	(listelm)->field.cqe_next = (elm);				\
46687ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
46787ebb10aSJérôme Duval
46887ebb10aSJérôme Duval#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
46987ebb10aSJérôme Duval	(elm)->field.cqe_next = (listelm);				\
47087ebb10aSJérôme Duval	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
47187ebb10aSJérôme Duval	if ((listelm)->field.cqe_prev == (void *)(head))		\
47287ebb10aSJérôme Duval		(head)->cqh_first = (elm);				\
47387ebb10aSJérôme Duval	else								\
47487ebb10aSJérôme Duval		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
47587ebb10aSJérôme Duval	(listelm)->field.cqe_prev = (elm);				\
47687ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
47787ebb10aSJérôme Duval
47887ebb10aSJérôme Duval#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
47987ebb10aSJérôme Duval	(elm)->field.cqe_next = (head)->cqh_first;			\
48087ebb10aSJérôme Duval	(elm)->field.cqe_prev = (void *)(head);				\
48187ebb10aSJérôme Duval	if ((head)->cqh_last == (void *)(head))				\
48287ebb10aSJérôme Duval		(head)->cqh_last = (elm);				\
48387ebb10aSJérôme Duval	else								\
48487ebb10aSJérôme Duval		(head)->cqh_first->field.cqe_prev = (elm);		\
48587ebb10aSJérôme Duval	(head)->cqh_first = (elm);					\
48687ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
48787ebb10aSJérôme Duval
48887ebb10aSJérôme Duval#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
48987ebb10aSJérôme Duval	(elm)->field.cqe_next = (void *)(head);				\
49087ebb10aSJérôme Duval	(elm)->field.cqe_prev = (head)->cqh_last;			\
49187ebb10aSJérôme Duval	if ((head)->cqh_first == (void *)(head))			\
49287ebb10aSJérôme Duval		(head)->cqh_first = (elm);				\
49387ebb10aSJérôme Duval	else								\
49487ebb10aSJérôme Duval		(head)->cqh_last->field.cqe_next = (elm);		\
49587ebb10aSJérôme Duval	(head)->cqh_last = (elm);					\
49687ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
49787ebb10aSJérôme Duval
49887ebb10aSJérôme Duval#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
49987ebb10aSJérôme Duval	if ((elm)->field.cqe_next == (void *)(head))			\
50087ebb10aSJérôme Duval		(head)->cqh_last = (elm)->field.cqe_prev;		\
50187ebb10aSJérôme Duval	else								\
50287ebb10aSJérôme Duval		(elm)->field.cqe_next->field.cqe_prev =			\
50387ebb10aSJérôme Duval		    (elm)->field.cqe_prev;				\
50487ebb10aSJérôme Duval	if ((elm)->field.cqe_prev == (void *)(head))			\
50587ebb10aSJérôme Duval		(head)->cqh_first = (elm)->field.cqe_next;		\
50687ebb10aSJérôme Duval	else								\
50787ebb10aSJérôme Duval		(elm)->field.cqe_prev->field.cqe_next =			\
50887ebb10aSJérôme Duval		    (elm)->field.cqe_next;				\
50987ebb10aSJérôme Duval} while (/*CONSTCOND*/0)
51087ebb10aSJérôme Duval
51187ebb10aSJérôme Duval#define CIRCLEQ_FOREACH(var, head, field)				\
51287ebb10aSJérôme Duval	for ((var) = ((head)->cqh_first);				\
51387ebb10aSJérôme Duval		(var) != (void *)(head);				\
51487ebb10aSJérôme Duval		(var) = ((var)->field.cqe_next))
51587ebb10aSJérôme Duval
51687ebb10aSJérôme Duval#define CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
51787ebb10aSJérôme Duval	for ((var) = ((head)->cqh_last);				\
51887ebb10aSJérôme Duval		(var) != (void *)(head);				\
51987ebb10aSJérôme Duval		(var) = ((var)->field.cqe_prev))
52087ebb10aSJérôme Duval
52187ebb10aSJérôme Duval/*
52287ebb10aSJérôme Duval * Circular queue access methods.
52387ebb10aSJérôme Duval */
52487ebb10aSJérôme Duval#define	CIRCLEQ_EMPTY(head)		((head)->cqh_first == (void *)(head))
52587ebb10aSJérôme Duval#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
52687ebb10aSJérôme Duval#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
52787ebb10aSJérôme Duval#define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
52887ebb10aSJérôme Duval#define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
52987ebb10aSJérôme Duval#endif	/* !_SYS_QUEUE_H_ */
530