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

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