[apple/xnu.git] / bsd / sys / queue.h

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 * 
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */
/*
 * Copyright (c) 1991, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)queue.h	8.5 (Berkeley) 8/20/94
 */

#ifndef _SYS_QUEUE_H_
#define	_SYS_QUEUE_H_

/*
 * This file defines five types of data structures: singly-linked lists,
 * slingly-linked tail queues, lists, tail queues, and circular queues.
 *
 * A singly-linked list is headed by a single forward pointer. The elements
 * are singly linked for minimum space and pointer manipulation overhead at
 * the expense of O(n) removal for arbitrary elements. New elements can be
 * added to the list after an existing element or at the head of the list.
 * Elements being removed from the head of the list should use the explicit
 * macro for this purpose for optimum efficiency. A singly-linked list may
 * only be traversed in the forward direction.  Singly-linked lists are ideal
 * for applications with large datasets and few or no removals or for
 * implementing a LIFO queue.
 *
 * A singly-linked tail queue is headed by a pair of pointers, one to the
 * head of the list and the other to the tail of the list. The elements are
 * singly linked for minimum space and pointer manipulation overhead at the
 * expense of O(n) removal for arbitrary elements. New elements can be added
 * to the list after an existing element, at the head of the list, or at the
 * end of the list. Elements being removed from the head of the tail queue
 * should use the explicit macro for this purpose for optimum efficiency.
 * A singly-linked tail queue may only be traversed in the forward direction.
 * Singly-linked tail queues are ideal for applications with large datasets
 * and few or no removals or for implementing a FIFO queue.
 *
 * A list is headed by a single forward pointer (or an array of forward
 * pointers for a hash table header). The elements are doubly linked
 * so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before
 * or after an existing element or at the head of the list. A list
 * may only be traversed in the forward direction.
 *
 * A tail queue is headed by a pair of pointers, one to the head of the
 * list and the other to the tail of the list. The elements are doubly
 * linked so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before or
 * after an existing element, at the head of the list, or at the end of
 * the list. A tail queue may only be traversed in the forward direction.
 *
 * A circle queue is headed by a pair of pointers, one to the head of the
 * list and the other to the tail of the list. The elements are doubly
 * linked so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before or after
 * an existing element, at the head of the list, or at the end of the list.
 * A circle queue may be traversed in either direction, but has a more
 * complex end of list detection.
 *
 * For details on the use of these macros, see the queue(3) manual page.
 *
 *
 *			SLIST	LIST	STAILQ	TAILQ	CIRCLEQ
 * _HEAD		+	+	+	+	+
 * _ENTRY		+	+	+	+	+
 * _INIT		+	+	+	+	+
 * _EMPTY		+	+	+	+	+
 * _FIRST		+	+	+	+	+
 * _NEXT		+	+	+	+	+
 * _PREV		-	-	-	+	+
 * _LAST		-	-	+	+	+
 * _FOREACH		+	+	-	+	+
 * _INSERT_HEAD		+	+	+	+	+
 * _INSERT_BEFORE	-	+	-	+	+
 * _INSERT_AFTER	+	+	+	+	+
 * _INSERT_TAIL		-	-	+	+	+
 * _REMOVE_HEAD		+	-	+	-	-
 * _REMOVE		+	+	+	+	+
 *
 */

/*
 * Singly-linked List definitions.
 */
#define SLIST_HEAD(name, type)						\
struct name {								\
	struct type *slh_first;	/* first element */			\
}
 
#define SLIST_ENTRY(type)						\
struct {								\
	struct type *sle_next;	/* next element */			\
}
 
/*
 * Singly-linked List functions.
 */
#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)

#define	SLIST_FIRST(head)	((head)->slh_first)

#define SLIST_FOREACH(var, head, field)					\
	for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)

#define SLIST_INIT(head) {						\
	(head)->slh_first = NULL;					\
}

#define SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
	(elm)->field.sle_next = (slistelm)->field.sle_next;		\
	(slistelm)->field.sle_next = (elm);				\
} while (0)

#define SLIST_INSERT_HEAD(head, elm, field) do {			\
	(elm)->field.sle_next = (head)->slh_first;			\
	(head)->slh_first = (elm);					\
} while (0)

#define SLIST_NEXT(elm, field)	((elm)->field.sle_next)

#define SLIST_REMOVE_HEAD(head, field) do {				\
	(head)->slh_first = (head)->slh_first->field.sle_next;		\
} while (0)

#define SLIST_REMOVE(head, elm, type, field) do {			\
	if ((head)->slh_first == (elm)) {				\
		SLIST_REMOVE_HEAD((head), field);			\
	}								\
	else {								\
		struct type *curelm = (head)->slh_first;		\
		while( curelm->field.sle_next != (elm) )		\
			curelm = curelm->field.sle_next;		\
		curelm->field.sle_next =				\
		    curelm->field.sle_next->field.sle_next;		\
	}								\
} while (0)

/*
 * Singly-linked Tail queue definitions.
 */
#define STAILQ_HEAD(name, type)						\
struct name {								\
	struct type *stqh_first;/* first element */			\
	struct type **stqh_last;/* addr of last next element */		\
}

#define STAILQ_HEAD_INITIALIZER(head)					\
	{ NULL, &(head).stqh_first }

#define STAILQ_ENTRY(type)						\
struct {								\
	struct type *stqe_next;	/* next element */			\
}

/*
 * Singly-linked Tail queue functions.
 */
#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)

#define	STAILQ_INIT(head) do {						\
	(head)->stqh_first = NULL;					\
	(head)->stqh_last = &(head)->stqh_first;			\
} while (0)

#define STAILQ_FIRST(head)	((head)->stqh_first)
#define STAILQ_LAST(head)	(*(head)->stqh_last)

#define STAILQ_INSERT_HEAD(head, elm, field) do {			\
	if (((elm)->field.stqe_next = (head)->stqh_first) == NULL)	\
		(head)->stqh_last = &(elm)->field.stqe_next;		\
	(head)->stqh_first = (elm);					\
} while (0)

#define STAILQ_INSERT_TAIL(head, elm, field) do {			\
	(elm)->field.stqe_next = NULL;					\
	*(head)->stqh_last = (elm);					\
	(head)->stqh_last = &(elm)->field.stqe_next;			\
} while (0)

#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\
	if (((elm)->field.stqe_next = (tqelm)->field.stqe_next) == NULL)\
		(head)->stqh_last = &(elm)->field.stqe_next;		\
	(tqelm)->field.stqe_next = (elm);				\
} while (0)

#define STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)

#define STAILQ_REMOVE_HEAD(head, field) do {				\
	if (((head)->stqh_first =					\
	     (head)->stqh_first->field.stqe_next) == NULL)		\
		(head)->stqh_last = &(head)->stqh_first;		\
} while (0)

#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do {			\
	if (((head)->stqh_first = (elm)->field.stqe_next) == NULL)	\
		(head)->stqh_last = &(head)->stqh_first;		\
} while (0)


#define STAILQ_REMOVE(head, elm, type, field) do {			\
	if ((head)->stqh_first == (elm)) {				\
		STAILQ_REMOVE_HEAD(head, field);			\
	}								\
	else {								\
		struct type *curelm = (head)->stqh_first;		\
		while( curelm->field.stqe_next != (elm) )		\
			curelm = curelm->field.stqe_next;		\
		if((curelm->field.stqe_next =				\
		    curelm->field.stqe_next->field.stqe_next) == NULL)	\
			(head)->stqh_last = &(curelm)->field.stqe_next;	\
	}								\
} while (0)

/*
 * List definitions.
 */
#define LIST_HEAD(name, type)						\
struct name {								\
	struct type *lh_first;	/* first element */			\
}

#define LIST_HEAD_INITIALIZER(head)					\
	{ NULL }

#define LIST_ENTRY(type)						\
struct {								\
	struct type *le_next;	/* next element */			\
	struct type **le_prev;	/* address of previous next element */	\
}

/*
 * List functions.
 */

#define	LIST_EMPTY(head) ((head)->lh_first == NULL)

#define LIST_FIRST(head)	((head)->lh_first)

#define LIST_FOREACH(var, head, field)					\
	for((var) = (head)->lh_first; (var); (var) = (var)->field.le_next)

#define	LIST_INIT(head) do {						\
	(head)->lh_first = NULL;					\
} while (0)

#define LIST_INSERT_AFTER(listelm, elm, field) do {			\
	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)	\
		(listelm)->field.le_next->field.le_prev =		\
		    &(elm)->field.le_next;				\
	(listelm)->field.le_next = (elm);				\
	(elm)->field.le_prev = &(listelm)->field.le_next;		\
} while (0)

#define LIST_INSERT_BEFORE(listelm, elm, field) do {			\
	(elm)->field.le_prev = (listelm)->field.le_prev;		\
	(elm)->field.le_next = (listelm);				\
	*(listelm)->field.le_prev = (elm);				\
	(listelm)->field.le_prev = &(elm)->field.le_next;		\
} while (0)

#define LIST_INSERT_HEAD(head, elm, field) do {				\
	if (((elm)->field.le_next = (head)->lh_first) != NULL)		\
		(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
	(head)->lh_first = (elm);					\
	(elm)->field.le_prev = &(head)->lh_first;			\
} while (0)

#define LIST_NEXT(elm, field)	((elm)->field.le_next)

#define LIST_REMOVE(elm, field) do {					\
	if ((elm)->field.le_next != NULL)				\
		(elm)->field.le_next->field.le_prev = 			\
		    (elm)->field.le_prev;				\
	*(elm)->field.le_prev = (elm)->field.le_next;			\
} while (0)

/*
 * Tail queue definitions.
 */
#define TAILQ_HEAD(name, type)						\
struct name {								\
	struct type *tqh_first;	/* first element */			\
	struct type **tqh_last;	/* addr of last next element */		\
}

#define TAILQ_HEAD_INITIALIZER(head)					\
	{ NULL, &(head).tqh_first }

#define TAILQ_ENTRY(type)						\
struct {								\
	struct type *tqe_next;	/* next element */			\
	struct type **tqe_prev;	/* address of previous next element */	\
}

/*
 * Tail queue functions.
 */
#define	TAILQ_EMPTY(head) ((head)->tqh_first == NULL)

#define TAILQ_FOREACH(var, head, field)					\
	for (var = TAILQ_FIRST(head); var; var = TAILQ_NEXT(var, field))

#define TAILQ_FOREACH_REVERSE(var, head, field, headname)					\
	for (var = TAILQ_LAST(head, headname);		       \
	       var; var = TAILQ_PREV(var, headname, field))

#define	TAILQ_FIRST(head) ((head)->tqh_first)

#define	TAILQ_LAST(head, headname) \
	(*(((struct headname *)((head)->tqh_last))->tqh_last))

#define	TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)

#define TAILQ_PREV(elm, headname, field) \
	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

#define	TAILQ_INIT(head) do {						\
	(head)->tqh_first = NULL;					\
	(head)->tqh_last = &(head)->tqh_first;				\
} while (0)

#define TAILQ_INSERT_HEAD(head, elm, field) do {			\
	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)	\
		(head)->tqh_first->field.tqe_prev =			\
		    &(elm)->field.tqe_next;				\
	else								\
		(head)->tqh_last = &(elm)->field.tqe_next;		\
	(head)->tqh_first = (elm);					\
	(elm)->field.tqe_prev = &(head)->tqh_first;			\
} while (0)

#define TAILQ_INSERT_TAIL(head, elm, field) do {			\
	(elm)->field.tqe_next = NULL;					\
	(elm)->field.tqe_prev = (head)->tqh_last;			\
	*(head)->tqh_last = (elm);					\
	(head)->tqh_last = &(elm)->field.tqe_next;			\
} while (0)

#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
		(elm)->field.tqe_next->field.tqe_prev = 		\
		    &(elm)->field.tqe_next;				\
	else								\
		(head)->tqh_last = &(elm)->field.tqe_next;		\
	(listelm)->field.tqe_next = (elm);				\
	(elm)->field.tqe_prev = &(listelm)->field.tqe_next;		\
} while (0)

#define TAILQ_INSERT_BEFORE(listelm, elm, field) do {			\
	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
	(elm)->field.tqe_next = (listelm);				\
	*(listelm)->field.tqe_prev = (elm);				\
	(listelm)->field.tqe_prev = &(elm)->field.tqe_next;		\
} while (0)

#define TAILQ_REMOVE(head, elm, field) do {				\
	if (((elm)->field.tqe_next) != NULL)				\
		(elm)->field.tqe_next->field.tqe_prev = 		\
		    (elm)->field.tqe_prev;				\
	else								\
		(head)->tqh_last = (elm)->field.tqe_prev;		\
	*(elm)->field.tqe_prev = (elm)->field.tqe_next;			\
} while (0)

/*
 * Circular queue definitions.
 */
#define CIRCLEQ_HEAD(name, type)					\
struct name {								\
	struct type *cqh_first;		/* first element */		\
	struct type *cqh_last;		/* last element */		\
}

#define CIRCLEQ_ENTRY(type)						\
struct {								\
	struct type *cqe_next;		/* next element */		\
	struct type *cqe_prev;		/* previous element */		\
}

/*
 * Circular queue functions.
 */
#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))

#define CIRCLEQ_FIRST(head) ((head)->cqh_first)

#define CIRCLEQ_FOREACH(var, head, field)				\
	for((var) = (head)->cqh_first;					\
	    (var) != (void *)(head);					\
	    (var) = (var)->field.cqe_next)

#define	CIRCLEQ_INIT(head) do {						\
	(head)->cqh_first = (void *)(head);				\
	(head)->cqh_last = (void *)(head);				\
} while (0)

#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {		\
	(elm)->field.cqe_next = (listelm)->field.cqe_next;		\
	(elm)->field.cqe_prev = (listelm);				\
	if ((listelm)->field.cqe_next == (void *)(head))		\
		(head)->cqh_last = (elm);				\
	else								\
		(listelm)->field.cqe_next->field.cqe_prev = (elm);	\
	(listelm)->field.cqe_next = (elm);				\
} while (0)

#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {		\
	(elm)->field.cqe_next = (listelm);				\
	(elm)->field.cqe_prev = (listelm)->field.cqe_prev;		\
	if ((listelm)->field.cqe_prev == (void *)(head))		\
		(head)->cqh_first = (elm);				\
	else								\
		(listelm)->field.cqe_prev->field.cqe_next = (elm);	\
	(listelm)->field.cqe_prev = (elm);				\
} while (0)

#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {			\
	(elm)->field.cqe_next = (head)->cqh_first;			\
	(elm)->field.cqe_prev = (void *)(head);				\
	if ((head)->cqh_last == (void *)(head))				\
		(head)->cqh_last = (elm);				\
	else								\
		(head)->cqh_first->field.cqe_prev = (elm);		\
	(head)->cqh_first = (elm);					\
} while (0)

#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {			\
	(elm)->field.cqe_next = (void *)(head);				\
	(elm)->field.cqe_prev = (head)->cqh_last;			\
	if ((head)->cqh_first == (void *)(head))			\
		(head)->cqh_first = (elm);				\
	else								\
		(head)->cqh_last->field.cqe_next = (elm);		\
	(head)->cqh_last = (elm);					\
} while (0)

#define CIRCLEQ_LAST(head) ((head)->cqh_last)

#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)

#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)

#define	CIRCLEQ_REMOVE(head, elm, field) do {				\
	if ((elm)->field.cqe_next == (void *)(head))			\
		(head)->cqh_last = (elm)->field.cqe_prev;		\
	else								\
		(elm)->field.cqe_next->field.cqe_prev =			\
		    (elm)->field.cqe_prev;				\
	if ((elm)->field.cqe_prev == (void *)(head))			\
		(head)->cqh_first = (elm)->field.cqe_next;		\
	else								\
		(elm)->field.cqe_prev->field.cqe_next =			\
		    (elm)->field.cqe_next;				\
} while (0)

#ifdef KERNEL

#if NOTFB31

/*
 * XXX insque() and remque() are an old way of handling certain queues.
 * They bogusly assumes that all queue heads look alike.
 */

struct quehead {
	struct quehead *qh_link;
	struct quehead *qh_rlink;
};

#ifdef	__GNUC__

static __inline void
insque(void *a, void *b)
{
	struct quehead *element = a, *head = b;

	element->qh_link = head->qh_link;
	element->qh_rlink = head;
	head->qh_link = element;
	element->qh_link->qh_rlink = element;
}

static __inline void
remque(void *a)
{
	struct quehead *element = a;

	element->qh_link->qh_rlink = element->qh_rlink;
	element->qh_rlink->qh_link = element->qh_link;
	element->qh_rlink = 0;
}

#else /* !__GNUC__ */

void	insque(void *a, void *b);
void	remque(void *a);

#endif /* __GNUC__ */

#endif
#endif /* KERNEL */

#endif /* !_SYS_QUEUE_H_ */
Commit	Line	Data
1c79356b	1	/*
5d5c5d0d A	2	* Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
5d5c5d0d A	3	*
8f6c56a5	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
1c79356b	5	*
8f6c56a5 A	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. The rights granted to you under the License
	10	* may not be used to create, or enable the creation or redistribution of,
	11	* unlawful or unlicensed copies of an Apple operating system, or to
	12	* circumvent, violate, or enable the circumvention or violation of, any
	13	* terms of an Apple operating system software license agreement.
	14	*
	15	* Please obtain a copy of the License at
	16	* http://www.opensource.apple.com/apsl/ and read it before using this file.
	17	*
	18	* The Original Code and all software distributed under the License are
	19	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
8ad349bb	24	* limitations under the License.
8f6c56a5 A	25	*
8f6c56a5 A	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
1c79356b A	27	*/
	28	/*
	29	* Copyright (c) 1991, 1993
	30	* The Regents of the University of California. All rights reserved.
	31	*
	32	* Redistribution and use in source and binary forms, with or without
	33	* modification, are permitted provided that the following conditions
	34	* are met:
	35	* 1. Redistributions of source code must retain the above copyright
	36	* notice, this list of conditions and the following disclaimer.
	37	* 2. Redistributions in binary form must reproduce the above copyright
	38	* notice, this list of conditions and the following disclaimer in the
	39	* documentation and/or other materials provided with the distribution.
	40	* 3. All advertising materials mentioning features or use of this software
	41	* must display the following acknowledgement:
	42	* This product includes software developed by the University of
	43	* California, Berkeley and its contributors.
	44	* 4. Neither the name of the University nor the names of its contributors
	45	* may be used to endorse or promote products derived from this software
	46	* without specific prior written permission.
	47	*
	48	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	49	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	50	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	51	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	52	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	53	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	54	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	55	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	56	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	57	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	58	* SUCH DAMAGE.
	59	*
	60	* @(#)queue.h 8.5 (Berkeley) 8/20/94
	61	*/
	62
	63	#ifndef _SYS_QUEUE_H_
	64	#define _SYS_QUEUE_H_
	65
	66	/*
	67	* This file defines five types of data structures: singly-linked lists,
	68	* slingly-linked tail queues, lists, tail queues, and circular queues.
	69	*
	70	* A singly-linked list is headed by a single forward pointer. The elements
	71	* are singly linked for minimum space and pointer manipulation overhead at
	72	* the expense of O(n) removal for arbitrary elements. New elements can be
	73	* added to the list after an existing element or at the head of the list.
	74	* Elements being removed from the head of the list should use the explicit
	75	* macro for this purpose for optimum efficiency. A singly-linked list may
	76	* only be traversed in the forward direction. Singly-linked lists are ideal
	77	* for applications with large datasets and few or no removals or for
	78	* implementing a LIFO queue.
	79	*
	80	* A singly-linked tail queue is headed by a pair of pointers, one to the
	81	* head of the list and the other to the tail of the list. The elements are
	82	* singly linked for minimum space and pointer manipulation overhead at the
	83	* expense of O(n) removal for arbitrary elements. New elements can be added
	84	* to the list after an existing element, at the head of the list, or at the
	85	* end of the list. Elements being removed from the head of the tail queue
	86	* should use the explicit macro for this purpose for optimum efficiency.
	87	* A singly-linked tail queue may only be traversed in the forward direction.
	88	* Singly-linked tail queues are ideal for applications with large datasets
	89	* and few or no removals or for implementing a FIFO queue.
	90	*
91	* A list is headed by a single forward pointer (or an array of forward
92	* pointers for a hash table header). The elements are doubly linked
93	* so that an arbitrary element can be removed without a need to
94	* traverse the list. New elements can be added to the list before
95	* or after an existing element or at the head of the list. A list
96	* may only be traversed in the forward direction.
97	*
98	* A tail queue is headed by a pair of pointers, one to the head of the
99	* list and the other to the tail of the list. The elements are doubly
100	* linked so that an arbitrary element can be removed without a need to
101	* traverse the list. New elements can be added to the list before or
102	* after an existing element, at the head of the list, or at the end of
103	* the list. A tail queue may only be traversed in the forward direction.
104	*
105	* A circle queue is headed by a pair of pointers, one to the head of the
106	* list and the other to the tail of the list. The elements are doubly
107	* linked so that an arbitrary element can be removed without a need to
108	* traverse the list. New elements can be added to the list before or after
109	* an existing element, at the head of the list, or at the end of the list.
110	* A circle queue may be traversed in either direction, but has a more
111	* complex end of list detection.
112	*
113	* For details on the use of these macros, see the queue(3) manual page.
114	*
115	*
116	* SLIST LIST STAILQ TAILQ CIRCLEQ
117	* _HEAD + + + + +
118	* _ENTRY + + + + +
119	* _INIT + + + + +
120	* _EMPTY + + + + +
121	* _FIRST + + + + +
122	* _NEXT + + + + +
123	* _PREV - - - + +
124	* _LAST - - + + +
125	* _FOREACH + + - + +
126	* _INSERT_HEAD + + + + +
127	* _INSERT_BEFORE - + - + +
128	* _INSERT_AFTER + + + + +
129	* _INSERT_TAIL - - + + +
130	* _REMOVE_HEAD + - + - -
131	* _REMOVE + + + + +
132	*
133	*/
134
135	/*
136	* Singly-linked List definitions.
137	*/
138	#define SLIST_HEAD(name, type) \
139	struct name { \
140	struct type slh_first; / first element */ \
141	}
142
143	#define SLIST_ENTRY(type) \
144	struct { \
145	struct type sle_next; / next element */ \
146	}
147
148	/*
149	* Singly-linked List functions.
150	*/
151	#define SLIST_EMPTY(head) ((head)->slh_first == NULL)
152
153	#define SLIST_FIRST(head) ((head)->slh_first)
154
155	#define SLIST_FOREACH(var, head, field) \
156	for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
157
158	#define SLIST_INIT(head) { \
159	(head)->slh_first = NULL; \
160	}
161
162	#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
163	(elm)->field.sle_next = (slistelm)->field.sle_next; \
164	(slistelm)->field.sle_next = (elm); \
165	} while (0)
166
167	#define SLIST_INSERT_HEAD(head, elm, field) do { \
168	(elm)->field.sle_next = (head)->slh_first; \
169	(head)->slh_first = (elm); \
170	} while (0)
171
172	#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
173
174	#define SLIST_REMOVE_HEAD(head, field) do { \
175	(head)->slh_first = (head)->slh_first->field.sle_next; \
176	} while (0)
177
178	#define SLIST_REMOVE(head, elm, type, field) do { \
179	if ((head)->slh_first == (elm)) { \
180	SLIST_REMOVE_HEAD((head), field); \
181	} \
182	else { \
183	struct type *curelm = (head)->slh_first; \
184	while( curelm->field.sle_next != (elm) ) \
185	curelm = curelm->field.sle_next; \
186	curelm->field.sle_next = \
187	curelm->field.sle_next->field.sle_next; \
188	} \
189	} while (0)
190
191	/*
192	* Singly-linked Tail queue definitions.
193	*/
194	#define STAILQ_HEAD(name, type) \
195	struct name { \
196	struct type stqh_first;/ first element */ \
197	struct type *stqh_last;/ addr of last next element */ \
198	}
199
200	#define STAILQ_HEAD_INITIALIZER(head) \
201	{ NULL, &(head).stqh_first }
202
203	#define STAILQ_ENTRY(type) \
204	struct { \
205	struct type stqe_next; / next element */ \
206	}
207
208	/*
209	* Singly-linked Tail queue functions.
210	*/
211	#define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
212
213	#define STAILQ_INIT(head) do { \
214	(head)->stqh_first = NULL; \
215	(head)->stqh_last = &(head)->stqh_first; \
216	} while (0)
217
218	#define STAILQ_FIRST(head) ((head)->stqh_first)
219	#define STAILQ_LAST(head) (*(head)->stqh_last)
220
221	#define STAILQ_INSERT_HEAD(head, elm, field) do { \
222	if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
223	(head)->stqh_last = &(elm)->field.stqe_next; \
224	(head)->stqh_first = (elm); \
225	} while (0)
226
227	#define STAILQ_INSERT_TAIL(head, elm, field) do { \
228	(elm)->field.stqe_next = NULL; \
229	*(head)->stqh_last = (elm); \
230	(head)->stqh_last = &(elm)->field.stqe_next; \
231	} while (0)
232
233	#define STAILQ_INSERT_AFTER(head, tqelm, elm, field) do { \
234	if (((elm)->field.stqe_next = (tqelm)->field.stqe_next) == NULL)\
235	(head)->stqh_last = &(elm)->field.stqe_next; \
236	(tqelm)->field.stqe_next = (elm); \
237	} while (0)
238
239	#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
240
241	#define STAILQ_REMOVE_HEAD(head, field) do { \
242	if (((head)->stqh_first = \
243	(head)->stqh_first->field.stqe_next) == NULL) \
244	(head)->stqh_last = &(head)->stqh_first; \
245	} while (0)
246
247	#define STAILQ_REMOVE_HEAD_UNTIL(head, elm, field) do { \
248	if (((head)->stqh_first = (elm)->field.stqe_next) == NULL) \
249	(head)->stqh_last = &(head)->stqh_first; \
250	} while (0)
251
252
253	#define STAILQ_REMOVE(head, elm, type, field) do { \
254	if ((head)->stqh_first == (elm)) { \
255	STAILQ_REMOVE_HEAD(head, field); \
256	} \
257	else { \
258	struct type *curelm = (head)->stqh_first; \
259	while( curelm->field.stqe_next != (elm) ) \
260	curelm = curelm->field.stqe_next; \
261	if((curelm->field.stqe_next = \
262	curelm->field.stqe_next->field.stqe_next) == NULL) \
263	(head)->stqh_last = &(curelm)->field.stqe_next; \
264	} \
265	} while (0)
266
267	/*
268	* List definitions.
269	*/
270	#define LIST_HEAD(name, type) \
271	struct name { \
272	struct type lh_first; / first element */ \
273	}
274
275	#define LIST_HEAD_INITIALIZER(head) \
276	{ NULL }
277
278	#define LIST_ENTRY(type) \
279	struct { \
280	struct type le_next; / next element */ \
281	struct type *le_prev; / address of previous next element */ \
282	}
283
284	/*
285	* List functions.
286	*/
287
288	#define LIST_EMPTY(head) ((head)->lh_first == NULL)
289
290	#define LIST_FIRST(head) ((head)->lh_first)
291
292	#define LIST_FOREACH(var, head, field) \
293	for((var) = (head)->lh_first; (var); (var) = (var)->field.le_next)
294
295	#define LIST_INIT(head) do { \
296	(head)->lh_first = NULL; \
297	} while (0)
298
299	#define LIST_INSERT_AFTER(listelm, elm, field) do { \
300	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
301	(listelm)->field.le_next->field.le_prev = \
302	&(elm)->field.le_next; \
303	(listelm)->field.le_next = (elm); \
304	(elm)->field.le_prev = &(listelm)->field.le_next; \
305	} while (0)
306
307	#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
308	(elm)->field.le_prev = (listelm)->field.le_prev; \
309	(elm)->field.le_next = (listelm); \
310	*(listelm)->field.le_prev = (elm); \
311	(listelm)->field.le_prev = &(elm)->field.le_next; \
312	} while (0)
313
314	#define LIST_INSERT_HEAD(head, elm, field) do { \
315	if (((elm)->field.le_next = (head)->lh_first) != NULL) \
316	(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
317	(head)->lh_first = (elm); \
318	(elm)->field.le_prev = &(head)->lh_first; \
319	} while (0)
320
321	#define LIST_NEXT(elm, field) ((elm)->field.le_next)
322
323	#define LIST_REMOVE(elm, field) do { \
324	if ((elm)->field.le_next != NULL) \
325	(elm)->field.le_next->field.le_prev = \
326	(elm)->field.le_prev; \
327	*(elm)->field.le_prev = (elm)->field.le_next; \
328	} while (0)
329
330	/*
331	* Tail queue definitions.
332	*/
333	#define TAILQ_HEAD(name, type) \
334	struct name { \
335	struct type tqh_first; / first element */ \
336	struct type *tqh_last; / addr of last next element */ \
337	}
338
339	#define TAILQ_HEAD_INITIALIZER(head) \
340	{ NULL, &(head).tqh_first }
341
342	#define TAILQ_ENTRY(type) \
343	struct { \
344	struct type tqe_next; / next element */ \
345	struct type *tqe_prev; / address of previous next element */ \
346	}
347
348	/*
349	* Tail queue functions.
350	*/
351	#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
352
353	#define TAILQ_FOREACH(var, head, field) \
354	for (var = TAILQ_FIRST(head); var; var = TAILQ_NEXT(var, field))
355
356	#define TAILQ_FOREACH_REVERSE(var, head, field, headname) \
357	for (var = TAILQ_LAST(head, headname); \
358	var; var = TAILQ_PREV(var, headname, field))
359
360	#define TAILQ_FIRST(head) ((head)->tqh_first)
361
362	#define TAILQ_LAST(head, headname) \
363	((((struct headname )((head)->tqh_last))->tqh_last))
364
365	#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
366
367	#define TAILQ_PREV(elm, headname, field) \
368	((((struct headname )((elm)->field.tqe_prev))->tqh_last))
369
370	#define TAILQ_INIT(head) do { \
371	(head)->tqh_first = NULL; \
372	(head)->tqh_last = &(head)->tqh_first; \
373	} while (0)
374
375	#define TAILQ_INSERT_HEAD(head, elm, field) do { \
376	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
377	(head)->tqh_first->field.tqe_prev = \
378	&(elm)->field.tqe_next; \
379	else \
380	(head)->tqh_last = &(elm)->field.tqe_next; \
381	(head)->tqh_first = (elm); \
382	(elm)->field.tqe_prev = &(head)->tqh_first; \
383	} while (0)
384
385	#define TAILQ_INSERT_TAIL(head, elm, field) do { \
386	(elm)->field.tqe_next = NULL; \
387	(elm)->field.tqe_prev = (head)->tqh_last; \
388	*(head)->tqh_last = (elm); \
389	(head)->tqh_last = &(elm)->field.tqe_next; \
390	} while (0)
391
392	#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
393	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
394	(elm)->field.tqe_next->field.tqe_prev = \
395	&(elm)->field.tqe_next; \
396	else \
397	(head)->tqh_last = &(elm)->field.tqe_next; \
398	(listelm)->field.tqe_next = (elm); \
399	(elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
400	} while (0)
401
402	#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
403	(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
404	(elm)->field.tqe_next = (listelm); \
405	*(listelm)->field.tqe_prev = (elm); \
406	(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
407	} while (0)
408
409	#define TAILQ_REMOVE(head, elm, field) do { \
410	if (((elm)->field.tqe_next) != NULL) \
411	(elm)->field.tqe_next->field.tqe_prev = \
412	(elm)->field.tqe_prev; \
413	else \
414	(head)->tqh_last = (elm)->field.tqe_prev; \
415	*(elm)->field.tqe_prev = (elm)->field.tqe_next; \
416	} while (0)
417
418	/*
419	* Circular queue definitions.
420	*/
421	#define CIRCLEQ_HEAD(name, type) \
422	struct name { \
423	struct type cqh_first; / first element */ \
424	struct type cqh_last; / last element */ \
425	}
426
427	#define CIRCLEQ_ENTRY(type) \
428	struct { \
429	struct type cqe_next; / next element */ \
430	struct type cqe_prev; / previous element */ \
431	}
432
433	/*
434	* Circular queue functions.
435	*/
436	#define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
437
438	#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
439
440	#define CIRCLEQ_FOREACH(var, head, field) \
441	for((var) = (head)->cqh_first; \
442	(var) != (void *)(head); \
443	(var) = (var)->field.cqe_next)
444
445	#define CIRCLEQ_INIT(head) do { \
446	(head)->cqh_first = (void *)(head); \
447	(head)->cqh_last = (void *)(head); \
448	} while (0)
449
450	#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
451	(elm)->field.cqe_next = (listelm)->field.cqe_next; \
452	(elm)->field.cqe_prev = (listelm); \
453	if ((listelm)->field.cqe_next == (void *)(head)) \
454	(head)->cqh_last = (elm); \
455	else \
456	(listelm)->field.cqe_next->field.cqe_prev = (elm); \
457	(listelm)->field.cqe_next = (elm); \
458	} while (0)
459
460	#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
461	(elm)->field.cqe_next = (listelm); \
462	(elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
463	if ((listelm)->field.cqe_prev == (void *)(head)) \
464	(head)->cqh_first = (elm); \
465	else \
466	(listelm)->field.cqe_prev->field.cqe_next = (elm); \
467	(listelm)->field.cqe_prev = (elm); \
468	} while (0)
469
470	#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
471	(elm)->field.cqe_next = (head)->cqh_first; \
472	(elm)->field.cqe_prev = (void *)(head); \
473	if ((head)->cqh_last == (void *)(head)) \
474	(head)->cqh_last = (elm); \
475	else \
476	(head)->cqh_first->field.cqe_prev = (elm); \
477	(head)->cqh_first = (elm); \
478	} while (0)
479
480	#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
481	(elm)->field.cqe_next = (void *)(head); \
482	(elm)->field.cqe_prev = (head)->cqh_last; \
483	if ((head)->cqh_first == (void *)(head)) \
484	(head)->cqh_first = (elm); \
485	else \
486	(head)->cqh_last->field.cqe_next = (elm); \
487	(head)->cqh_last = (elm); \
488	} while (0)
489
490	#define CIRCLEQ_LAST(head) ((head)->cqh_last)
491
492	#define CIRCLEQ_NEXT(elm,field) ((elm)->field.cqe_next)
493
494	#define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
495
496	#define CIRCLEQ_REMOVE(head, elm, field) do { \
497	if ((elm)->field.cqe_next == (void *)(head)) \
498	(head)->cqh_last = (elm)->field.cqe_prev; \
499	else \
500	(elm)->field.cqe_next->field.cqe_prev = \
501	(elm)->field.cqe_prev; \
502	if ((elm)->field.cqe_prev == (void *)(head)) \
503	(head)->cqh_first = (elm)->field.cqe_next; \
504	else \
505	(elm)->field.cqe_prev->field.cqe_next = \
506	(elm)->field.cqe_next; \
507	} while (0)
508
509	#ifdef KERNEL
510
511	#if NOTFB31
512
513	/*
514	* XXX insque() and remque() are an old way of handling certain queues.
515	* They bogusly assumes that all queue heads look alike.
516	*/
517
518	struct quehead {
519	struct quehead *qh_link;
520	struct quehead *qh_rlink;
521	};
522
523	#ifdef __GNUC__
524
525	static __inline void
526	insque(void a, void b)
527	{
528	struct quehead element = a, head = b;
529
530	element->qh_link = head->qh_link;
531	element->qh_rlink = head;
532	head->qh_link = element;
533	element->qh_link->qh_rlink = element;
534	}
535
536	static __inline void
537	remque(void *a)
538	{
539	struct quehead *element = a;
540
541	element->qh_link->qh_rlink = element->qh_rlink;
542	element->qh_rlink->qh_link = element->qh_link;
543	element->qh_rlink = 0;
544	}
545
546	#else /* !__GNUC__ */
547
91447636 A	548	void insque(void a, void b);
91447636 A	549	void remque(void *a);
1c79356b A	550
	551	#endif /* __GNUC__ */
	552
	553	#endif
	554	#endif /* KERNEL */
	555
	556	#endif /* !_SYS_QUEUE_H_ */