15adb129eSJérôme Duval/*	$NetBSD: queue.h,v 1.31 2002/06/01 23:51:05 lukem Exp $	*/
25adb129eSJérôme Duval
35adb129eSJérôme Duval/*
45adb129eSJérôme Duval * Copyright (c) 1991, 1993
55adb129eSJérôme Duval *	The Regents of the University of California.  All rights reserved.
65adb129eSJérôme Duval *
75adb129eSJérôme Duval * Redistribution and use in source and binary forms, with or without
85adb129eSJérôme Duval * modification, are permitted provided that the following conditions
95adb129eSJérôme Duval * are met:
105adb129eSJérôme Duval * 1. Redistributions of source code must retain the above copyright
115adb129eSJérôme Duval *    notice, this list of conditions and the following disclaimer.
125adb129eSJérôme Duval * 2. Redistributions in binary form must reproduce the above copyright
135adb129eSJérôme Duval *    notice, this list of conditions and the following disclaimer in the
145adb129eSJérôme Duval *    documentation and/or other materials provided with the distribution.
155adb129eSJérôme Duval * 3. All advertising materials mentioning features or use of this software
165adb129eSJérôme Duval *    must display the following acknowledgement:
175adb129eSJérôme Duval *	This product includes software developed by the University of
185adb129eSJérôme Duval *	California, Berkeley and its contributors.
195adb129eSJérôme Duval * 4. Neither the name of the University nor the names of its contributors
205adb129eSJérôme Duval *    may be used to endorse or promote products derived from this software
215adb129eSJérôme Duval *    without specific prior written permission.
225adb129eSJérôme Duval *
235adb129eSJérôme Duval * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
245adb129eSJérôme Duval * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
255adb129eSJérôme Duval * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
265adb129eSJérôme Duval * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
275adb129eSJérôme Duval * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
285adb129eSJérôme Duval * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
295adb129eSJérôme Duval * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
305adb129eSJérôme Duval * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
315adb129eSJérôme Duval * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
325adb129eSJérôme Duval * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
335adb129eSJérôme Duval * SUCH DAMAGE.
345adb129eSJérôme Duval *
355adb129eSJérôme Duval *	@(#)queue.h	8.5 (Berkeley) 8/20/94
365adb129eSJérôme Duval */
375adb129eSJérôme Duval
385adb129eSJérôme Duval#ifndef	_SYS_QUEUE_H_
395adb129eSJérôme Duval#define	_SYS_QUEUE_H_
405adb129eSJérôme Duval
415adb129eSJérôme Duval/*
425adb129eSJérôme Duval * This file defines five types of data structures: singly-linked lists,
435adb129eSJérôme Duval * lists, simple queues, tail queues, and circular queues.
445adb129eSJérôme Duval *
455adb129eSJérôme Duval * A singly-linked list is headed by a single forward pointer. The
465adb129eSJérôme Duval * elements are singly linked for minimum space and pointer manipulation
475adb129eSJérôme Duval * overhead at the expense of O(n) removal for arbitrary elements. New
485adb129eSJérôme Duval * elements can be added to the list after an existing element or at the
495adb129eSJérôme Duval * head of the list.  Elements being removed from the head of the list
505adb129eSJérôme Duval * should use the explicit macro for this purpose for optimum
515adb129eSJérôme Duval * efficiency. A singly-linked list may only be traversed in the forward
525adb129eSJérôme Duval * direction.  Singly-linked lists are ideal for applications with large
535adb129eSJérôme Duval * datasets and few or no removals or for implementing a LIFO queue.
545adb129eSJérôme Duval *
555adb129eSJérôme Duval * A list is headed by a single forward pointer (or an array of forward
565adb129eSJérôme Duval * pointers for a hash table header). The elements are doubly linked
575adb129eSJérôme Duval * so that an arbitrary element can be removed without a need to
585adb129eSJérôme Duval * traverse the list. New elements can be added to the list before
595adb129eSJérôme Duval * or after an existing element or at the head of the list. A list
605adb129eSJérôme Duval * may only be traversed in the forward direction.
615adb129eSJérôme Duval *
625adb129eSJérôme Duval * A simple queue is headed by a pair of pointers, one the head of the
635adb129eSJérôme Duval * list and the other to the tail of the list. The elements are singly
645adb129eSJérôme Duval * linked to save space, so only elements can only be removed from the
655adb129eSJérôme Duval * head of the list. New elements can be added to the list after
665adb129eSJérôme Duval * an existing element, at the head of the list, or at the end of the
675adb129eSJérôme Duval * list. A simple queue may only be traversed in the forward direction.
685adb129eSJérôme Duval *
695adb129eSJérôme Duval * A tail queue is headed by a pair of pointers, one to the head of the
705adb129eSJérôme Duval * list and the other to the tail of the list. The elements are doubly
715adb129eSJérôme Duval * linked so that an arbitrary element can be removed without a need to
725adb129eSJérôme Duval * traverse the list. New elements can be added to the list before or
735adb129eSJérôme Duval * after an existing element, at the head of the list, or at the end of
745adb129eSJérôme Duval * the list. A tail queue may be traversed in either direction.
755adb129eSJérôme Duval *
765adb129eSJérôme Duval * A circle queue is headed by a pair of pointers, one to the head of the
775adb129eSJérôme Duval * list and the other to the tail of the list. The elements are doubly
785adb129eSJérôme Duval * linked so that an arbitrary element can be removed without a need to
795adb129eSJérôme Duval * traverse the list. New elements can be added to the list before or after
805adb129eSJérôme Duval * an existing element, at the head of the list, or at the end of the list.
815adb129eSJérôme Duval * A circle queue may be traversed in either direction, but has a more
825adb129eSJérôme Duval * complex end of list detection.
835adb129eSJérôme Duval *
845adb129eSJérôme Duval * For details on the use of these macros, see the queue(3) manual page.
855adb129eSJérôme Duval */
865adb129eSJérôme Duval
875adb129eSJérôme Duval/*
885adb129eSJérôme Duval * List definitions.
895adb129eSJérôme Duval */
905adb129eSJérôme Duval#define LIST_HEAD(name, type)						\
915adb129eSJérôme Duvalstruct name {								\
925adb129eSJérôme Duval	struct type *lh_first;	/* first element */			\
935adb129eSJérôme Duval}
945adb129eSJérôme Duval
955adb129eSJérôme Duval#define LIST_HEAD_INITIALIZER(head)					\
965adb129eSJérôme Duval	{ NULL }
975adb129eSJérôme Duval
985adb129eSJérôme Duval#define LIST_ENTRY(type)						\
995adb129eSJérôme Duvalstruct {								\
1005adb129eSJérôme Duval	struct type *le_next;	/* next element */			\
1015adb129eSJérôme Duval	struct type **le_prev;	/* address of previous next element */	\
1025adb129eSJérôme Duval}
1035adb129eSJérôme Duval
1045adb129eSJérôme Duval/*
1055adb129eSJérôme Duval * List functions.
1065adb129eSJérôme Duval */
1075adb129eSJérôme Duval#if defined(_KERNEL) && defined(QUEUEDEBUG)
1085adb129eSJérôme Duval#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)			\
1095adb129eSJérôme Duval	if ((head)->lh_first &&						\
1105adb129eSJérôme Duval	    (head)->lh_first->field.le_prev != &(head)->lh_first)	\
1115adb129eSJérôme Duval		panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
1125adb129eSJérôme Duval#define QUEUEDEBUG_LIST_OP(elm, field)					\
1135adb129eSJérôme Duval	if ((elm)->field.le_next &&					\
1145adb129eSJérôme Duval	    (elm)->field.le_next->field.le_prev !=			\
1155adb129eSJérôme Duval	    &(elm)->field.le_next)					\
1165adb129eSJérôme Duval		panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
1175adb129eSJérôme Duval	if (*(elm)->field.le_prev != (elm))				\
1185adb129eSJérôme Duval		panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__);
1195adb129eSJérôme Duval#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)				\
1205adb129eSJérôme Duval	(elm)->field.le_next = (void *)1L;				\
1215adb129eSJérôme Duval	(elm)->field.le_prev = (void *)1L;
1225adb129eSJérôme Duval#else
1235adb129eSJérôme Duval#define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
1245adb129eSJérôme Duval#define QUEUEDEBUG_LIST_OP(elm, field)
1255adb129eSJérôme Duval#define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
1265adb129eSJérôme Duval#endif
1275adb129eSJérôme Duval
1285adb129eSJérôme Duval#define	LIST_INIT(head) do {						\
1295adb129eSJérôme Duval	(head)->lh_first = NULL;					\
1305adb129eSJérôme Duval} while (/*CONSTCOND*/0)
1315adb129eSJérôme Duval
1325adb129eSJérôme Duval#define LIST_INSERT_AFTER(listelm, elm, field) do {			\
1335adb129eSJérôme Duval	QUEUEDEBUG_LIST_OP((listelm), field)				\
1345adb129eSJérôme Duval	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
1355adb129eSJérôme Duval		(listelm)->field.le_next->field.le_prev =		\
1365adb129eSJérôme Duval		    &(elm)->field.le_next;				\
1375adb129eSJérôme Duval	(listelm)->field.le_next = (elm);				\
1385adb129eSJérôme Duval	(elm)->field.le_prev = &(listelm)->field.le_next;		\
1395adb129eSJérôme Duval} while (/*CONSTCOND*/0)
1405adb129eSJérôme Duval
1415adb129eSJérôme Duval#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
1425adb129eSJérôme Duval	QUEUEDEBUG_LIST_OP((listelm), field)				\
1435adb129eSJérôme Duval	(elm)->field.le_prev = (listelm)->field.le_prev;		\
1445adb129eSJérôme Duval	(elm)->field.le_next = (listelm);				\
1455adb129eSJérôme Duval	*(listelm)->field.le_prev = (elm);				\
1465adb129eSJérôme Duval	(listelm)->field.le_prev = &(elm)->field.le_next;		\
1475adb129eSJérôme Duval} while (/*CONSTCOND*/0)
1485adb129eSJérôme Duval
1495adb129eSJérôme Duval#define LIST_INSERT_HEAD(head, elm, field) do {				\
1505adb129eSJérôme Duval	QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field)		\
1515adb129eSJérôme Duval	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
1525adb129eSJérôme Duval		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
1535adb129eSJérôme Duval	(head)->lh_first = (elm);					\
1545adb129eSJérôme Duval	(elm)->field.le_prev = &(head)->lh_first;			\
1555adb129eSJérôme Duval} while (/*CONSTCOND*/0)
1565adb129eSJérôme Duval
1575adb129eSJérôme Duval#define LIST_REMOVE(elm, field) do {					\
1585adb129eSJérôme Duval	QUEUEDEBUG_LIST_OP((elm), field)				\
1595adb129eSJérôme Duval	if ((elm)->field.le_next != NULL)				\
1605adb129eSJérôme Duval		(elm)->field.le_next->field.le_prev = 			\
1615adb129eSJérôme Duval		    (elm)->field.le_prev;				\
1625adb129eSJérôme Duval	*(elm)->field.le_prev = (elm)->field.le_next;			\
1635adb129eSJérôme Duval	QUEUEDEBUG_LIST_POSTREMOVE((elm), field)			\
1645adb129eSJérôme Duval} while (/*CONSTCOND*/0)
1655adb129eSJérôme Duval
1665adb129eSJérôme Duval#define LIST_FOREACH(var, head, field)					\
1675adb129eSJérôme Duval	for ((var) = ((head)->lh_first);				\
1685adb129eSJérôme Duval		(var);							\
1695adb129eSJérôme Duval		(var) = ((var)->field.le_next))
1705adb129eSJérôme Duval
1715adb129eSJérôme Duval/*
1725adb129eSJérôme Duval * List access methods.
1735adb129eSJérôme Duval */
1745adb129eSJérôme Duval#define	LIST_EMPTY(head)		((head)->lh_first == NULL)
1755adb129eSJérôme Duval#define	LIST_FIRST(head)		((head)->lh_first)
1765adb129eSJérôme Duval#define	LIST_NEXT(elm, field)		((elm)->field.le_next)
1775adb129eSJérôme Duval
1785adb129eSJérôme Duval/*
1795adb129eSJérôme Duval * Singly-linked List definitions.
1805adb129eSJérôme Duval */
1815adb129eSJérôme Duval#define SLIST_HEAD(name, type)						\
1825adb129eSJérôme Duvalstruct name {								\
1835adb129eSJérôme Duval	struct type *slh_first;	/* first element */			\
1845adb129eSJérôme Duval}
1855adb129eSJérôme Duval
1865adb129eSJérôme Duval#define SLIST_HEAD_INITIALIZER(head)					\
1875adb129eSJérôme Duval	{ NULL }
1885adb129eSJérôme Duval
1895adb129eSJérôme Duval#define SLIST_ENTRY(type)						\
1905adb129eSJérôme Duvalstruct {								\
1915adb129eSJérôme Duval	struct type *sle_next;	/* next element */			\
1925adb129eSJérôme Duval}
1935adb129eSJérôme Duval
1945adb129eSJérôme Duval/*
1955adb129eSJérôme Duval * Singly-linked List functions.
1965adb129eSJérôme Duval */
1975adb129eSJérôme Duval#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)
1985adb129eSJérôme Duval#define	SLIST_FIRST(head)	((head)->slh_first)
1995adb129eSJérôme Duval#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)
2005adb129eSJérôme Duval
2015adb129eSJérôme Duval#define SLIST_FOREACH(var, head, field)					\
2025adb129eSJérôme Duval	for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
2035adb129eSJérôme Duval
2045adb129eSJérôme Duval#define SLIST_INIT(head) do {						\
2055adb129eSJérôme Duval	(head)->slh_first = NULL;					\
2065adb129eSJérôme Duval} while (/*CONSTCOND*/0)
2075adb129eSJérôme Duval
2085adb129eSJérôme Duval#define SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
2095adb129eSJérôme Duval	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
2105adb129eSJérôme Duval	(slistelm)->field.sle_next = (elm);				\
2115adb129eSJérôme Duval} while (/*CONSTCOND*/0)
2125adb129eSJérôme Duval
2135adb129eSJérôme Duval#define SLIST_INSERT_HEAD(head, elm, field) do {			\
2145adb129eSJérôme Duval	(elm)->field.sle_next = (head)->slh_first;			\
2155adb129eSJérôme Duval	(head)->slh_first = (elm);					\
2165adb129eSJérôme Duval} while (/*CONSTCOND*/0)
2175adb129eSJérôme Duval
2185adb129eSJérôme Duval#define SLIST_NEXT(elm, field)	((elm)->field.sle_next)
2195adb129eSJérôme Duval
2205adb129eSJérôme Duval#define SLIST_REMOVE_HEAD(head, field) do {				\
2215adb129eSJérôme Duval	(head)->slh_first = (head)->slh_first->field.sle_next;		\
2225adb129eSJérôme Duval} while (/*CONSTCOND*/0)
2235adb129eSJérôme Duval
2245adb129eSJérôme Duval#define SLIST_REMOVE(head, elm, type, field) do {			\
2255adb129eSJérôme Duval	if ((head)->slh_first == (elm)) {				\
2265adb129eSJérôme Duval		SLIST_REMOVE_HEAD((head), field);			\
2275adb129eSJérôme Duval	}								\
2285adb129eSJérôme Duval	else {								\
2295adb129eSJérôme Duval		struct type *curelm = (head)->slh_first;		\
2305adb129eSJérôme Duval		while(curelm->field.sle_next != (elm))			\
2315adb129eSJérôme Duval			curelm = curelm->field.sle_next;		\
2325adb129eSJérôme Duval		curelm->field.sle_next =				\
2335adb129eSJérôme Duval		    curelm->field.sle_next->field.sle_next;		\
2345adb129eSJérôme Duval	}								\
2355adb129eSJérôme Duval} while (/*CONSTCOND*/0)
2365adb129eSJérôme Duval
2375adb129eSJérôme Duval/*
2385adb129eSJérôme Duval * Simple queue definitions.
2395adb129eSJérôme Duval */
2405adb129eSJérôme Duval#define SIMPLEQ_HEAD(name, type)					\
2415adb129eSJérôme Duvalstruct name {								\
2425adb129eSJérôme Duval	struct type *sqh_first;	/* first element */			\
2435adb129eSJérôme Duval	struct type **sqh_last;	/* addr of last next element */		\
2445adb129eSJérôme Duval}
2455adb129eSJérôme Duval
2465adb129eSJérôme Duval#define SIMPLEQ_HEAD_INITIALIZER(head)					\
2475adb129eSJérôme Duval	{ NULL, &(head).sqh_first }
2485adb129eSJérôme Duval
2495adb129eSJérôme Duval#define SIMPLEQ_ENTRY(type)						\
2505adb129eSJérôme Duvalstruct {								\
2515adb129eSJérôme Duval	struct type *sqe_next;	/* next element */			\
2525adb129eSJérôme Duval}
2535adb129eSJérôme Duval
2545adb129eSJérôme Duval/*
2555adb129eSJérôme Duval * Simple queue functions.
2565adb129eSJérôme Duval */
2575adb129eSJérôme Duval#define	SIMPLEQ_INIT(head) do {						\
2585adb129eSJérôme Duval	(head)->sqh_first = NULL;					\
2595adb129eSJérôme Duval	(head)->sqh_last = &(head)->sqh_first;				\
2605adb129eSJérôme Duval} while (/*CONSTCOND*/0)
2615adb129eSJérôme Duval
2625adb129eSJérôme Duval#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {			\
2635adb129eSJérôme Duval	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)	\
2645adb129eSJérôme Duval		(head)->sqh_last = &(elm)->field.sqe_next;		\
2655adb129eSJérôme Duval	(head)->sqh_first = (elm);					\
2665adb129eSJérôme Duval} while (/*CONSTCOND*/0)
2675adb129eSJérôme Duval
2685adb129eSJérôme Duval#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {			\
2695adb129eSJérôme Duval	(elm)->field.sqe_next = NULL;					\
2705adb129eSJérôme Duval	*(head)->sqh_last = (elm);					\
2715adb129eSJérôme Duval	(head)->sqh_last = &(elm)->field.sqe_next;			\
2725adb129eSJérôme Duval} while (/*CONSTCOND*/0)
2735adb129eSJérôme Duval
2745adb129eSJérôme Duval#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
2755adb129eSJérôme Duval	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
2765adb129eSJérôme Duval		(head)->sqh_last = &(elm)->field.sqe_next;		\
2775adb129eSJérôme Duval	(listelm)->field.sqe_next = (elm);				\
2785adb129eSJérôme Duval} while (/*CONSTCOND*/0)
2795adb129eSJérôme Duval
2805adb129eSJérôme Duval#define SIMPLEQ_REMOVE_HEAD(head, field) do {				\
2815adb129eSJérôme Duval	if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
2825adb129eSJérôme Duval		(head)->sqh_last = &(head)->sqh_first;			\
2835adb129eSJérôme Duval} while (/*CONSTCOND*/0)
2845adb129eSJérôme Duval
2855adb129eSJérôme Duval#define SIMPLEQ_REMOVE(head, elm, type, field) do {			\
2865adb129eSJérôme Duval	if ((head)->sqh_first == (elm)) {				\
2875adb129eSJérôme Duval		SIMPLEQ_REMOVE_HEAD((head), field);			\
2885adb129eSJérôme Duval	} else {							\
2895adb129eSJérôme Duval		struct type *curelm = (head)->sqh_first;		\
2905adb129eSJérôme Duval		while (curelm->field.sqe_next != (elm))			\
2915adb129eSJérôme Duval			curelm = curelm->field.sqe_next;		\
2925adb129eSJérôme Duval		if ((curelm->field.sqe_next =				\
2935adb129eSJérôme Duval			curelm->field.sqe_next->field.sqe_next) == NULL) \
2945adb129eSJérôme Duval			    (head)->sqh_last = &(curelm)->field.sqe_next; \
2955adb129eSJérôme Duval	}								\
2965adb129eSJérôme Duval} while (/*CONSTCOND*/0)
2975adb129eSJérôme Duval
2985adb129eSJérôme Duval#define SIMPLEQ_FOREACH(var, head, field)				\
2995adb129eSJérôme Duval	for ((var) = ((head)->sqh_first);				\
3005adb129eSJérôme Duval		(var);							\
3015adb129eSJérôme Duval		(var) = ((var)->field.sqe_next))
3025adb129eSJérôme Duval
3035adb129eSJérôme Duval/*
3045adb129eSJérôme Duval * Simple queue access methods.
3055adb129eSJérôme Duval */
3065adb129eSJérôme Duval#define	SIMPLEQ_EMPTY(head)		((head)->sqh_first == NULL)
3075adb129eSJérôme Duval#define	SIMPLEQ_FIRST(head)		((head)->sqh_first)
3085adb129eSJérôme Duval#define	SIMPLEQ_NEXT(elm, field)	((elm)->field.sqe_next)
3095adb129eSJérôme Duval
3105adb129eSJérôme Duval/*
3115adb129eSJérôme Duval * Tail queue definitions.
3125adb129eSJérôme Duval */
3135adb129eSJérôme Duval#define TAILQ_HEAD(name, type)						\
3145adb129eSJérôme Duvalstruct name {								\
3155adb129eSJérôme Duval	struct type *tqh_first;	/* first element */			\
3165adb129eSJérôme Duval	struct type **tqh_last;	/* addr of last next element */		\
3175adb129eSJérôme Duval}
3185adb129eSJérôme Duval
3195adb129eSJérôme Duval#define TAILQ_HEAD_INITIALIZER(head)					\
3205adb129eSJérôme Duval	{ NULL, &(head).tqh_first }
3215adb129eSJérôme Duval
3225adb129eSJérôme Duval#define TAILQ_ENTRY(type)						\
3235adb129eSJérôme Duvalstruct {								\
3245adb129eSJérôme Duval	struct type *tqe_next;	/* next element */			\
3255adb129eSJérôme Duval	struct type **tqe_prev;	/* address of previous next element */	\
3265adb129eSJérôme Duval}
3275adb129eSJérôme Duval
3285adb129eSJérôme Duval/*
3295adb129eSJérôme Duval * Tail queue functions.
3305adb129eSJérôme Duval */
3315adb129eSJérôme Duval#if defined(_KERNEL) && defined(QUEUEDEBUG)
3325adb129eSJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)			\
3335adb129eSJérôme Duval	if ((head)->tqh_first &&					\
3345adb129eSJérôme Duval	    (head)->tqh_first->field.tqe_prev != &(head)->tqh_first)	\
3355adb129eSJérôme Duval		panic("TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
3365adb129eSJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)			\
3375adb129eSJérôme Duval	if (*(head)->tqh_last != NULL)					\
3385adb129eSJérôme Duval		panic("TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__);
3395adb129eSJérôme Duval#define QUEUEDEBUG_TAILQ_OP(elm, field)					\
3405adb129eSJérôme Duval	if ((elm)->field.tqe_next &&					\
3415adb129eSJérôme Duval	    (elm)->field.tqe_next->field.tqe_prev !=			\
3425adb129eSJérôme Duval	    &(elm)->field.tqe_next)					\
3435adb129eSJérôme Duval		panic("TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
3445adb129eSJérôme Duval	if (*(elm)->field.tqe_prev != (elm))				\
3455adb129eSJérôme Duval		panic("TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__);
3465adb129eSJérôme Duval#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)				\
3475adb129eSJérôme Duval	(elm)->field.tqe_next = (void *)1L;				\
3485adb129eSJérôme Duval	(elm)->field.tqe_prev = (void *)1L;
3495adb129eSJérôme Duval#else
3505adb129eSJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
3515adb129eSJérôme Duval#define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
3525adb129eSJérôme Duval#define QUEUEDEBUG_TAILQ_OP(elm, field)
3535adb129eSJérôme Duval#define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
3545adb129eSJérôme Duval#endif
3555adb129eSJérôme Duval
3565adb129eSJérôme Duval#define	TAILQ_INIT(head) do {						\
3575adb129eSJérôme Duval	(head)->tqh_first = NULL;					\
3585adb129eSJérôme Duval	(head)->tqh_last = &(head)->tqh_first;				\
3595adb129eSJérôme Duval} while (/*CONSTCOND*/0)
3605adb129eSJérôme Duval
3615adb129eSJérôme Duval#define TAILQ_INSERT_HEAD(head, elm, field) do {			\
3625adb129eSJérôme Duval	QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field)		\
3635adb129eSJérôme Duval	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
3645adb129eSJérôme Duval		(head)->tqh_first->field.tqe_prev =			\
3655adb129eSJérôme Duval		    &(elm)->field.tqe_next;				\
3665adb129eSJérôme Duval	else								\
3675adb129eSJérôme Duval		(head)->tqh_last = &(elm)->field.tqe_next;		\
3685adb129eSJérôme Duval	(head)->tqh_first = (elm);					\
3695adb129eSJérôme Duval	(elm)->field.tqe_prev = &(head)->tqh_first;			\
3705adb129eSJérôme Duval} while (/*CONSTCOND*/0)
3715adb129eSJérôme Duval
3725adb129eSJérôme Duval#define TAILQ_INSERT_TAIL(head, elm, field) do {			\
3735adb129eSJérôme Duval	QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field)		\
3745adb129eSJérôme Duval	(elm)->field.tqe_next = NULL;					\
3755adb129eSJérôme Duval	(elm)->field.tqe_prev = (head)->tqh_last;			\
3765adb129eSJérôme Duval	*(head)->tqh_last = (elm);					\
3775adb129eSJérôme Duval	(head)->tqh_last = &(elm)->field.tqe_next;			\
3785adb129eSJérôme Duval} while (/*CONSTCOND*/0)
3795adb129eSJérôme Duval
3805adb129eSJérôme Duval#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
3815adb129eSJérôme Duval	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
3825adb129eSJérôme Duval	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
3835adb129eSJérôme Duval		(elm)->field.tqe_next->field.tqe_prev = 		\
3845adb129eSJérôme Duval		    &(elm)->field.tqe_next;				\
3855adb129eSJérôme Duval	else								\
3865adb129eSJérôme Duval		(head)->tqh_last = &(elm)->field.tqe_next;		\
3875adb129eSJérôme Duval	(listelm)->field.tqe_next = (elm);				\
3885adb129eSJérôme Duval	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
3895adb129eSJérôme Duval} while (/*CONSTCOND*/0)
3905adb129eSJérôme Duval
3915adb129eSJérôme Duval#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
3925adb129eSJérôme Duval	QUEUEDEBUG_TAILQ_OP((listelm), field)				\
3935adb129eSJérôme Duval	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
3945adb129eSJérôme Duval	(elm)->field.tqe_next = (listelm);				\
3955adb129eSJérôme Duval	*(listelm)->field.tqe_prev = (elm);				\
3965adb129eSJérôme Duval	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
3975adb129eSJérôme Duval} while (/*CONSTCOND*/0)
3985adb129eSJérôme Duval
3995adb129eSJérôme Duval#define TAILQ_REMOVE(head, elm, field) do {				\
4005adb129eSJérôme Duval	QUEUEDEBUG_TAILQ_OP((elm), field)				\
4015adb129eSJérôme Duval	if (((elm)->field.tqe_next) != NULL)				\
4025adb129eSJérôme Duval		(elm)->field.tqe_next->field.tqe_prev = 		\
4035adb129eSJérôme Duval		    (elm)->field.tqe_prev;				\
4045adb129eSJérôme Duval	else								\
4055adb129eSJérôme Duval		(head)->tqh_last = (elm)->field.tqe_prev;		\
4065adb129eSJérôme Duval	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
4075adb129eSJérôme Duval	QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field);			\
4085adb129eSJérôme Duval} while (/*CONSTCOND*/0)
4095adb129eSJérôme Duval
4105adb129eSJérôme Duval/*
4115adb129eSJérôme Duval * Tail queue access methods.
4125adb129eSJérôme Duval */
4135adb129eSJérôme Duval#define	TAILQ_EMPTY(head)		((head)->tqh_first == NULL)
4145adb129eSJérôme Duval#define	TAILQ_FIRST(head)		((head)->tqh_first)
4155adb129eSJérôme Duval#define	TAILQ_NEXT(elm, field)		((elm)->field.tqe_next)
4165adb129eSJérôme Duval
4175adb129eSJérôme Duval#define TAILQ_LAST(head, headname) \
4185adb129eSJérôme Duval	(*(((struct headname *)((head)->tqh_last))->tqh_last))
4195adb129eSJérôme Duval#define TAILQ_PREV(elm, headname, field) \
4205adb129eSJérôme Duval	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
4215adb129eSJérôme Duval
4225adb129eSJérôme Duval#define TAILQ_FOREACH(var, head, field)					\
4235adb129eSJérôme Duval	for ((var) = ((head)->tqh_first);				\
4245adb129eSJérôme Duval		(var);							\
4255adb129eSJérôme Duval		(var) = ((var)->field.tqe_next))
4265adb129eSJérôme Duval
4275adb129eSJérôme Duval#define TAILQ_FOREACH_REVERSE(var, head, headname, field)		\
4285adb129eSJérôme Duval	for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));	\
4295adb129eSJérôme Duval		(var);							\
4305adb129eSJérôme Duval		(var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
4315adb129eSJérôme Duval
4325adb129eSJérôme Duval/*
4335adb129eSJérôme Duval * Circular queue definitions.
4345adb129eSJérôme Duval */
4355adb129eSJérôme Duval#define CIRCLEQ_HEAD(name, type)					\
4365adb129eSJérôme Duvalstruct name {								\
4375adb129eSJérôme Duval	struct type *cqh_first;		/* first element */		\
4385adb129eSJérôme Duval	struct type *cqh_last;		/* last element */		\
4395adb129eSJérôme Duval}
4405adb129eSJérôme Duval
4415adb129eSJérôme Duval#define CIRCLEQ_HEAD_INITIALIZER(head)					\
4425adb129eSJérôme Duval	{ (void *)&head, (void *)&head }
4435adb129eSJérôme Duval
4445adb129eSJérôme Duval#define CIRCLEQ_ENTRY(type)						\
4455adb129eSJérôme Duvalstruct {								\
4465adb129eSJérôme Duval	struct type *cqe_next;		/* next element */		\
4475adb129eSJérôme Duval	struct type *cqe_prev;		/* previous element */		\
4485adb129eSJérôme Duval}
4495adb129eSJérôme Duval
4505adb129eSJérôme Duval/*
4515adb129eSJérôme Duval * Circular queue functions.
4525adb129eSJérôme Duval */
4535adb129eSJérôme Duval#define	CIRCLEQ_INIT(head) do {						\
4545adb129eSJérôme Duval	(head)->cqh_first = (void *)(head);				\
4555adb129eSJérôme Duval	(head)->cqh_last = (void *)(head);				\
4565adb129eSJérôme Duval} while (/*CONSTCOND*/0)
4575adb129eSJérôme Duval
4585adb129eSJérôme Duval#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
4595adb129eSJérôme Duval	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
4605adb129eSJérôme Duval	(elm)->field.cqe_prev = (listelm);				\
4615adb129eSJérôme Duval	if ((listelm)->field.cqe_next == (void *)(head))		\
4625adb129eSJérôme Duval		(head)->cqh_last = (elm);				\
4635adb129eSJérôme Duval	else								\
4645adb129eSJérôme Duval		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
4655adb129eSJérôme Duval	(listelm)->field.cqe_next = (elm);				\
4665adb129eSJérôme Duval} while (/*CONSTCOND*/0)
4675adb129eSJérôme Duval
4685adb129eSJérôme Duval#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
4695adb129eSJérôme Duval	(elm)->field.cqe_next = (listelm);				\
4705adb129eSJérôme Duval	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
4715adb129eSJérôme Duval	if ((listelm)->field.cqe_prev == (void *)(head))		\
4725adb129eSJérôme Duval		(head)->cqh_first = (elm);				\
4735adb129eSJérôme Duval	else								\
4745adb129eSJérôme Duval		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
4755adb129eSJérôme Duval	(listelm)->field.cqe_prev = (elm);				\
4765adb129eSJérôme Duval} while (/*CONSTCOND*/0)
4775adb129eSJérôme Duval
4785adb129eSJérôme Duval#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
4795adb129eSJérôme Duval	(elm)->field.cqe_next = (head)->cqh_first;			\
4805adb129eSJérôme Duval	(elm)->field.cqe_prev = (void *)(head);				\
4815adb129eSJérôme Duval	if ((head)->cqh_last == (void *)(head))				\
4825adb129eSJérôme Duval		(head)->cqh_last = (elm);				\
4835adb129eSJérôme Duval	else								\
4845adb129eSJérôme Duval		(head)->cqh_first->field.cqe_prev = (elm);		\
4855adb129eSJérôme Duval	(head)->cqh_first = (elm);					\
4865adb129eSJérôme Duval} while (/*CONSTCOND*/0)
4875adb129eSJérôme Duval
4885adb129eSJérôme Duval#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
4895adb129eSJérôme Duval	(elm)->field.cqe_next = (void *)(head);				\
4905adb129eSJérôme Duval	(elm)->field.cqe_prev = (head)->cqh_last;			\
4915adb129eSJérôme Duval	if ((head)->cqh_first == (void *)(head))			\
4925adb129eSJérôme Duval		(head)->cqh_first = (elm);				\
4935adb129eSJérôme Duval	else								\
4945adb129eSJérôme Duval		(head)->cqh_last->field.cqe_next = (elm);		\
4955adb129eSJérôme Duval	(head)->cqh_last = (elm);					\
4965adb129eSJérôme Duval} while (/*CONSTCOND*/0)
4975adb129eSJérôme Duval
4985adb129eSJérôme Duval#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
4995adb129eSJérôme Duval	if ((elm)->field.cqe_next == (void *)(head))			\
5005adb129eSJérôme Duval		(head)->cqh_last = (elm)->field.cqe_prev;		\
5015adb129eSJérôme Duval	else								\
5025adb129eSJérôme Duval		(elm)->field.cqe_next->field.cqe_prev =			\
5035adb129eSJérôme Duval		    (elm)->field.cqe_prev;				\
5045adb129eSJérôme Duval	if ((elm)->field.cqe_prev == (void *)(head))			\
5055adb129eSJérôme Duval		(head)->cqh_first = (elm)->field.cqe_next;		\
5065adb129eSJérôme Duval	else								\
5075adb129eSJérôme Duval		(elm)->field.cqe_prev->field.cqe_next =			\
5085adb129eSJérôme Duval		    (elm)->field.cqe_next;				\
5095adb129eSJérôme Duval} while (/*CONSTCOND*/0)
5105adb129eSJérôme Duval
5115adb129eSJérôme Duval#define CIRCLEQ_FOREACH(var, head, field)				\
5125adb129eSJérôme Duval	for ((var) = ((head)->cqh_first);				\
5135adb129eSJérôme Duval		(var) != (void *)(head);				\
5145adb129eSJérôme Duval		(var) = ((var)->field.cqe_next))
5155adb129eSJérôme Duval
5165adb129eSJérôme Duval#define CIRCLEQ_FOREACH_REVERSE(var, head, field)			\
5175adb129eSJérôme Duval	for ((var) = ((head)->cqh_last);				\
5185adb129eSJérôme Duval		(var) != (void *)(head);				\
5195adb129eSJérôme Duval		(var) = ((var)->field.cqe_prev))
5205adb129eSJérôme Duval
5215adb129eSJérôme Duval/*
5225adb129eSJérôme Duval * Circular queue access methods.
5235adb129eSJérôme Duval */
5245adb129eSJérôme Duval#define	CIRCLEQ_EMPTY(head)		((head)->cqh_first == (void *)(head))
5255adb129eSJérôme Duval#define	CIRCLEQ_FIRST(head)		((head)->cqh_first)
5265adb129eSJérôme Duval#define	CIRCLEQ_LAST(head)		((head)->cqh_last)
5275adb129eSJérôme Duval#define	CIRCLEQ_NEXT(elm, field)	((elm)->field.cqe_next)
5285adb129eSJérôme Duval#define	CIRCLEQ_PREV(elm, field)	((elm)->field.cqe_prev)
5295adb129eSJérôme Duval#endif	/* !_SYS_QUEUE_H_ */
530