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

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