[apple/xnu.git] / osfmk / kern / queue.h

/*
 * Copyright (c) 2000-2005 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@
 */
/*
 * @OSF_COPYRIGHT@
 */
/* 
 * Mach Operating System
 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
 * All Rights Reserved.
 * 
 * Permission to use, copy, modify and distribute this software and its
 * documentation is hereby granted, provided that both the copyright
 * notice and this permission notice appear in all copies of the
 * software, derivative works or modified versions, and any portions
 * thereof, and that both notices appear in supporting documentation.
 * 
 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
 * 
 * Carnegie Mellon requests users of this software to return to
 *
 *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
 *  School of Computer Science
 *  Carnegie Mellon University
 *  Pittsburgh PA 15213-3890
 *
 * any improvements or extensions that they make and grant Carnegie Mellon rights
 * to redistribute these changes.
 */
/*
 */
/*
 *	File:	queue.h
 *	Author:	Avadis Tevanian, Jr.
 *	Date:	1985
 *
 *	Type definitions for generic queues.
 *
 */

#ifndef	_KERN_QUEUE_H_
#define	_KERN_QUEUE_H_

#include <mach/mach_types.h>
#include <kern/macro_help.h>

/*
 *	Queue of abstract objects.  Queue is maintained
 *	within that object.
 *
 *	Supports fast removal from within the queue.
 *
 *	How to declare a queue of elements of type "foo_t":
 *		In the "*foo_t" type, you must have a field of
 *		type "queue_chain_t" to hold together this queue.
 *		There may be more than one chain through a
 *		"foo_t", for use by different queues.
 *
 *		Declare the queue as a "queue_t" type.
 *
 *		Elements of the queue (of type "foo_t", that is)
 *		are referred to by reference, and cast to type
 *		"queue_entry_t" within this module.
 */

/*
 *	A generic doubly-linked list (queue).
 */

struct queue_entry {
	struct queue_entry	*next;		/* next element */
	struct queue_entry	*prev;		/* previous element */
};

typedef struct queue_entry	*queue_t;
typedef	struct queue_entry	queue_head_t;
typedef	struct queue_entry	queue_chain_t;
typedef	struct queue_entry	*queue_entry_t;

/*
 *	enqueue puts "elt" on the "queue".
 *	dequeue returns the first element in the "queue".
 *	remqueue removes the specified "elt" from the specified "queue".
 */

#define enqueue(queue,elt)	enqueue_tail(queue, elt)
#define	dequeue(queue)		dequeue_head(queue)

#if	!defined(__GNUC__)

#include <sys/cdefs.h>
__BEGIN_DECLS

/* Enqueue element to head of queue */
extern void		enqueue_head(
				queue_t		que,
				queue_entry_t	elt);

/* Enqueue element to tail of queue */
extern void		enqueue_tail(
				queue_t		que,
				queue_entry_t	elt);

/* Dequeue element from head of queue */
extern queue_entry_t	dequeue_head(
				queue_t	que);

/* Dequeue element from tail of queue */
extern queue_entry_t	dequeue_tail(
				queue_t	que);

/* Dequeue element */
extern void		remqueue(
				queue_t		que,
				queue_entry_t	elt);

/* Enqueue element after a particular elem */
extern void		insque(
				queue_entry_t	entry,
				queue_entry_t	pred);

/* Dequeue element */
extern void		remque(
				queue_entry_t elt);

__END_DECLS

#else	/* !__GNUC__ */

static __inline__ void
enqueue_head(
	queue_t		que,
	queue_entry_t	elt)
{
	elt->next = que->next;
	elt->prev = que;
	elt->next->prev = elt;
	que->next = elt;
}

static __inline__ void
enqueue_tail(
		queue_t		que,
		queue_entry_t	elt)
{
	elt->next = que;
	elt->prev = que->prev;
	elt->prev->next = elt;
	que->prev = elt;
}

static __inline__ queue_entry_t
dequeue_head(
	queue_t	que)
{
	register queue_entry_t	elt = (queue_entry_t) 0;

	if (que->next != que) {
		elt = que->next;
		elt->next->prev = que;
		que->next = elt->next;
	}

	return (elt);
}

static __inline__ queue_entry_t
dequeue_tail(
	queue_t	que)
{
	register queue_entry_t	elt = (queue_entry_t) 0;

	if (que->prev != que) {
		elt = que->prev;
		elt->prev->next = que;
		que->prev = elt->prev;
	}

	return (elt);
}

static __inline__ void
remqueue(
	__unused queue_t		que,
	queue_entry_t	elt)
{
	elt->next->prev = elt->prev;
	elt->prev->next = elt->next;
}

static __inline__ void
insque(
	queue_entry_t	entry,
	queue_entry_t	pred)
{
	entry->next = pred->next;
	entry->prev = pred;
	(pred->next)->prev = entry;
	pred->next = entry;
}

static __inline__ void
remque(
	register queue_entry_t elt)
{
	(elt->next)->prev = elt->prev;
	(elt->prev)->next = elt->next;
}

#endif	/* !__GNUC__ */

/*
 *	Macro:		queue_init
 *	Function:
 *		Initialize the given queue.
 *	Header:
 *		void queue_init(q)
 *			queue_t		q;	\* MODIFIED *\
 */
#define queue_init(q)	\
MACRO_BEGIN		\
	(q)->next = (q);\
	(q)->prev = (q);\
MACRO_END

/*
 *	Macro:		queue_first
 *	Function:
 *		Returns the first entry in the queue,
 *	Header:
 *		queue_entry_t queue_first(q)
 *			queue_t	q;		\* IN *\
 */
#define	queue_first(q)	((q)->next)

/*
 *	Macro:		queue_next
 *	Function:
 *		Returns the entry after an item in the queue.
 *	Header:
 *		queue_entry_t queue_next(qc)
 *			queue_t qc;
 */
#define	queue_next(qc)	((qc)->next)

/*
 *	Macro:		queue_last
 *	Function:
 *		Returns the last entry in the queue.
 *	Header:
 *		queue_entry_t queue_last(q)
 *			queue_t	q;		\* IN *\
 */
#define	queue_last(q)	((q)->prev)

/*
 *	Macro:		queue_prev
 *	Function:
 *		Returns the entry before an item in the queue.
 *	Header:
 *		queue_entry_t queue_prev(qc)
 *			queue_t qc;
 */
#define	queue_prev(qc)	((qc)->prev)

/*
 *	Macro:		queue_end
 *	Function:
 *		Tests whether a new entry is really the end of
 *		the queue.
 *	Header:
 *		boolean_t queue_end(q, qe)
 *			queue_t q;
 *			queue_entry_t qe;
 */
#define	queue_end(q, qe)	((q) == (qe))

/*
 *	Macro:		queue_empty
 *	Function:
 *		Tests whether a queue is empty.
 *	Header:
 *		boolean_t queue_empty(q)
 *			queue_t q;
 */
#define	queue_empty(q)		queue_end((q), queue_first(q))


/*----------------------------------------------------------------*/
/*
 * Macros that operate on generic structures.  The queue
 * chain may be at any location within the structure, and there
 * may be more than one chain.
 */

/*
 *	Macro:		queue_enter
 *	Function:
 *		Insert a new element at the tail of the queue.
 *	Header:
 *		void queue_enter(q, elt, type, field)
 *			queue_t q;
 *			<type> elt;
 *			<type> is what's in our queue
 *			<field> is the chain field in (*<type>)
 */
#define queue_enter(head, elt, type, field)			\
MACRO_BEGIN							\
	register queue_entry_t __prev;				\
								\
	__prev = (head)->prev;					\
	if ((head) == __prev) {					\
		(head)->next = (queue_entry_t) (elt);		\
	}							\
	else {							\
		((type)__prev)->field.next = (queue_entry_t)(elt);\
	}							\
	(elt)->field.prev = __prev;				\
	(elt)->field.next = head;				\
	(head)->prev = (queue_entry_t) elt;			\
MACRO_END

/*
 *	Macro:		queue_enter_first
 *	Function:
 *		Insert a new element at the head of the queue.
 *	Header:
 *		void queue_enter_first(q, elt, type, field)
 *			queue_t q;
 *			<type> elt;
 *			<type> is what's in our queue
 *			<field> is the chain field in (*<type>)
 */
#define queue_enter_first(head, elt, type, field)		\
MACRO_BEGIN							\
	register queue_entry_t __next;				\
								\
	__next = (head)->next;					\
	if ((head) == __next) {					\
		(head)->prev = (queue_entry_t) (elt);		\
	}							\
	else {							\
		((type)__next)->field.prev = (queue_entry_t)(elt);\
	}							\
	(elt)->field.next = __next;				\
	(elt)->field.prev = head;				\
	(head)->next = (queue_entry_t) elt;			\
MACRO_END

/*
 *	Macro:		queue_insert_before
 *	Function:
 *		Insert a new element before a given element.
 *	Header:
 *		void queue_insert_before(q, elt, cur, type, field)
 *			queue_t q;
 *			<type> elt;
 *			<type> cur;
 *			<type> is what's in our queue
 *			<field> is the chain field in (*<type>)
 */
#define queue_insert_before(head, elt, cur, type, field)		\
MACRO_BEGIN								\
	register queue_entry_t __prev;					\
									\
	if ((head) == (queue_entry_t)(cur)) {				\
		(elt)->field.next = (head);				\
		if ((head)->next == (head)) {	/* only element */	\
			(elt)->field.prev = (head);			\
			(head)->next = (queue_entry_t)(elt);		\
		} else {			/* last element */	\
			__prev = (elt)->field.prev = (head)->prev;	\
			((type)__prev)->field.next = (queue_entry_t)(elt);\
		}							\
		(head)->prev = (queue_entry_t)(elt);			\
	} else {							\
		(elt)->field.next = (queue_entry_t)(cur);		\
		if ((head)->next == (queue_entry_t)(cur)) {		\
						/* first element */	\
			(elt)->field.prev = (head);			\
			(head)->next = (queue_entry_t)(elt);		\
		} else {			/* middle element */	\
			__prev = (elt)->field.prev = (cur)->field.prev;	\
			((type)__prev)->field.next = (queue_entry_t)(elt);\
		}							\
		(cur)->field.prev = (queue_entry_t)(elt);		\
	}								\
MACRO_END

/*
 *	Macro:		queue_insert_after
 *	Function:
 *		Insert a new element after a given element.
 *	Header:
 *		void queue_insert_after(q, elt, cur, type, field)
 *			queue_t q;
 *			<type> elt;
 *			<type> cur;
 *			<type> is what's in our queue
 *			<field> is the chain field in (*<type>)
 */
#define queue_insert_after(head, elt, cur, type, field)			\
MACRO_BEGIN								\
	register queue_entry_t __next;					\
									\
	if ((head) == (queue_entry_t)(cur)) {				\
		(elt)->field.prev = (head);				\
		if ((head)->next == (head)) {	/* only element */	\
			(elt)->field.next = (head);			\
			(head)->prev = (queue_entry_t)(elt);		\
		} else {			/* first element */	\
			__next = (elt)->field.next = (head)->next;	\
			((type)__next)->field.prev = (queue_entry_t)(elt);\
		}							\
		(head)->next = (queue_entry_t)(elt);			\
	} else {							\
		(elt)->field.prev = (queue_entry_t)(cur);		\
		if ((head)->prev == (queue_entry_t)(cur)) {		\
						/* last element */	\
			(elt)->field.next = (head);			\
			(head)->prev = (queue_entry_t)(elt);		\
		} else {			/* middle element */	\
			__next = (elt)->field.next = (cur)->field.next;	\
			((type)__next)->field.prev = (queue_entry_t)(elt);\
		}							\
		(cur)->field.next = (queue_entry_t)(elt);		\
	}								\
MACRO_END

/*
 *	Macro:		queue_field [internal use only]
 *	Function:
 *		Find the queue_chain_t (or queue_t) for the
 *		given element (thing) in the given queue (head)
 */
#define	queue_field(head, thing, type, field)			\
		(((head) == (thing)) ? (head) : &((type)(thing))->field)

/*
 *	Macro:		queue_remove
 *	Function:
 *		Remove an arbitrary item from the queue.
 *	Header:
 *		void queue_remove(q, qe, type, field)
 *			arguments as in queue_enter
 */
#define	queue_remove(head, elt, type, field)			\
MACRO_BEGIN							\
	register queue_entry_t	__next, __prev;			\
								\
	__next = (elt)->field.next;				\
	__prev = (elt)->field.prev;				\
								\
	if ((head) == __next)					\
		(head)->prev = __prev;				\
	else							\
		((type)__next)->field.prev = __prev;		\
								\
	if ((head) == __prev)					\
		(head)->next = __next;				\
	else							\
		((type)__prev)->field.next = __next;		\
								\
	(elt)->field.next = NULL;				\
	(elt)->field.prev = NULL;				\
MACRO_END

/*
 *	Macro:		queue_remove_first
 *	Function:
 *		Remove and return the entry at the head of
 *		the queue.
 *	Header:
 *		queue_remove_first(head, entry, type, field)
 *		entry is returned by reference
 */
#define	queue_remove_first(head, entry, type, field)		\
MACRO_BEGIN							\
	register queue_entry_t	__next;				\
								\
	(entry) = (type) ((head)->next);			\
	__next = (entry)->field.next;				\
								\
	if ((head) == __next)					\
		(head)->prev = (head);				\
	else							\
		((type)(__next))->field.prev = (head);		\
	(head)->next = __next;					\
								\
	(entry)->field.next = NULL;				\
	(entry)->field.prev = NULL;				\
MACRO_END

/*
 *	Macro:		queue_remove_last
 *	Function:
 *		Remove and return the entry at the tail of
 *		the queue.
 *	Header:
 *		queue_remove_last(head, entry, type, field)
 *		entry is returned by reference
 */
#define	queue_remove_last(head, entry, type, field)		\
MACRO_BEGIN							\
	register queue_entry_t	__prev;				\
								\
	(entry) = (type) ((head)->prev);			\
	__prev = (entry)->field.prev;				\
								\
	if ((head) == __prev)					\
		(head)->next = (head);				\
	else							\
		((type)(__prev))->field.next = (head);		\
	(head)->prev = __prev;					\
								\
	(entry)->field.next = NULL;				\
	(entry)->field.prev = NULL;				\
MACRO_END

/*
 *	Macro:		queue_assign
 */
#define	queue_assign(to, from, type, field)			\
MACRO_BEGIN							\
	((type)((from)->prev))->field.next = (to);		\
	((type)((from)->next))->field.prev = (to);		\
	*to = *from;						\
MACRO_END

/*
 *	Macro:		queue_new_head
 *	Function:
 *		rebase old queue to new queue head
 *	Header:
 *		queue_new_head(old, new, type, field)
 *			queue_t old;
 *			queue_t new;
 *			<type> is what's in our queue
 *                      <field> is the chain field in (*<type>)
 */
#define queue_new_head(old, new, type, field)			\
MACRO_BEGIN							\
	if (!queue_empty(old)) {				\
		*(new) = *(old);				\
		((type)((new)->next))->field.prev = (new);	\
		((type)((new)->prev))->field.next = (new);	\
	} else {						\
		queue_init(new);				\
	}							\
MACRO_END

/*
 *	Macro:		queue_iterate
 *	Function:
 *		iterate over each item in the queue.
 *		Generates a 'for' loop, setting elt to
 *		each item in turn (by reference).
 *	Header:
 *		queue_iterate(q, elt, type, field)
 *			queue_t q;
 *			<type> elt;
 *			<type> is what's in our queue
 *			<field> is the chain field in (*<type>)
 */
#define queue_iterate(head, elt, type, field)			\
	for ((elt) = (type) queue_first(head);			\
	     !queue_end((head), (queue_entry_t)(elt));		\
	     (elt) = (type) queue_next(&(elt)->field))

#ifdef	MACH_KERNEL_PRIVATE

#include <kern/lock.h>

/*----------------------------------------------------------------*/
/*
 *	Define macros for queues with locks.
 */
struct mpqueue_head {
	struct queue_entry	head;		/* header for queue */
	decl_simple_lock_data(,	lock)		/* lock for queue */
};

typedef struct mpqueue_head	mpqueue_head_t;

#define	round_mpq(size)		(size)

#define mpqueue_init(q)					\
MACRO_BEGIN						\
	queue_init(&(q)->head);				\
	simple_lock_init(&(q)->lock, 0);	\
MACRO_END

#define mpenqueue_tail(q, elt)				\
MACRO_BEGIN						\
	simple_lock(&(q)->lock);			\
	enqueue_tail(&(q)->head, elt);			\
	simple_unlock(&(q)->lock);			\
MACRO_END

#define mpdequeue_head(q, elt)				\
MACRO_BEGIN						\
	simple_lock(&(q)->lock);			\
	if (queue_empty(&(q)->head))			\
		*(elt) = 0;				\
	else						\
		*(elt) = dequeue_head(&(q)->head);	\
	simple_unlock(&(q)->lock);			\
MACRO_END

#endif	/* MACH_KERNEL_PRIVATE */

#endif	/* _KERN_QUEUE_H_ */
Commit	Line	Data
1c79356b	1	/*
91447636	2	* Copyright (c) 2000-2005 Apple Computer, Inc. All rights reserved.
1c79356b	3	*
2d21ac55	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
1c79356b	5	*
2d21ac55 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.
8f6c56a5	14	*
2d21ac55 A	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
8f6c56a5 A	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
8f6c56a5 A	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
2d21ac55 A	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
	24	* limitations under the License.
8f6c56a5	25	*
2d21ac55	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
1c79356b A	27	*/
	28	/*
	29	* @OSF_COPYRIGHT@
	30	*/
	31	/*
	32	* Mach Operating System
	33	* Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
	34	* All Rights Reserved.
	35	*
	36	* Permission to use, copy, modify and distribute this software and its
	37	* documentation is hereby granted, provided that both the copyright
	38	* notice and this permission notice appear in all copies of the
	39	* software, derivative works or modified versions, and any portions
	40	* thereof, and that both notices appear in supporting documentation.
	41	*
	42	* CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
	43	* CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
	44	* ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
	45	*
	46	* Carnegie Mellon requests users of this software to return to
	47	*
	48	* Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
	49	* School of Computer Science
	50	* Carnegie Mellon University
	51	* Pittsburgh PA 15213-3890
	52	*
	53	* any improvements or extensions that they make and grant Carnegie Mellon rights
	54	* to redistribute these changes.
	55	*/
	56	/*
	57	*/
	58	/*
	59	* File: queue.h
	60	* Author: Avadis Tevanian, Jr.
	61	* Date: 1985
	62	*
	63	* Type definitions for generic queues.
	64	*
	65	*/
	66
	67	#ifndef _KERN_QUEUE_H_
	68	#define _KERN_QUEUE_H_
	69
91447636	70	#include <mach/mach_types.h>
1c79356b A	71	#include <kern/macro_help.h>
	72
	73	/*
	74	* Queue of abstract objects. Queue is maintained
	75	* within that object.
	76	*
	77	* Supports fast removal from within the queue.
	78	*
	79	* How to declare a queue of elements of type "foo_t":
	80	* In the "*foo_t" type, you must have a field of
	81	* type "queue_chain_t" to hold together this queue.
	82	* There may be more than one chain through a
	83	* "foo_t", for use by different queues.
	84	*
	85	* Declare the queue as a "queue_t" type.
	86	*
	87	* Elements of the queue (of type "foo_t", that is)
	88	* are referred to by reference, and cast to type
	89	* "queue_entry_t" within this module.
	90	*/
	91
	92	/*
	93	* A generic doubly-linked list (queue).
	94	*/
	95
	96	struct queue_entry {
	97	struct queue_entry next; / next element */
	98	struct queue_entry prev; / previous element */
	99	};
	100
	101	typedef struct queue_entry *queue_t;
	102	typedef struct queue_entry queue_head_t;
	103	typedef struct queue_entry queue_chain_t;
	104	typedef struct queue_entry *queue_entry_t;
	105
	106	/*
	107	* enqueue puts "elt" on the "queue".
	108	* dequeue returns the first element in the "queue".
	109	* remqueue removes the specified "elt" from the specified "queue".
	110	*/
	111
	112	#define enqueue(queue,elt) enqueue_tail(queue, elt)
	113	#define dequeue(queue) dequeue_head(queue)
	114
	115	#if !defined(__GNUC__)
	116
91447636 A	117	#include <sys/cdefs.h>
	118	__BEGIN_DECLS
	119
1c79356b A	120	/* Enqueue element to head of queue */
	121	extern void enqueue_head(
	122	queue_t que,
	123	queue_entry_t elt);
	124
	125	/* Enqueue element to tail of queue */
	126	extern void enqueue_tail(
	127	queue_t que,
	128	queue_entry_t elt);
	129
	130	/* Dequeue element from head of queue */
	131	extern queue_entry_t dequeue_head(
	132	queue_t que);
	133
	134	/* Dequeue element from tail of queue */
	135	extern queue_entry_t dequeue_tail(
	136	queue_t que);
	137
	138	/* Dequeue element */
	139	extern void remqueue(
	140	queue_t que,
	141	queue_entry_t elt);
	142
	143	/* Enqueue element after a particular elem */
	144	extern void insque(
	145	queue_entry_t entry,
	146	queue_entry_t pred);
	147
	148	/* Dequeue element */
b0d623f7	149	extern void remque(
1c79356b A	150	queue_entry_t elt);
1c79356b A	151
91447636 A	152	__END_DECLS
	153
	154	#else /* !__GNUC__ */
1c79356b A	155
	156	static __inline__ void
	157	enqueue_head(
	158	queue_t que,
	159	queue_entry_t elt)
	160	{
	161	elt->next = que->next;
	162	elt->prev = que;
	163	elt->next->prev = elt;
	164	que->next = elt;
	165	}
	166
	167	static __inline__ void
	168	enqueue_tail(
	169	queue_t que,
	170	queue_entry_t elt)
	171	{
	172	elt->next = que;
	173	elt->prev = que->prev;
	174	elt->prev->next = elt;
	175	que->prev = elt;
	176	}
	177
	178	static __inline__ queue_entry_t
	179	dequeue_head(
	180	queue_t que)
	181	{
	182	register queue_entry_t elt = (queue_entry_t) 0;
	183
	184	if (que->next != que) {
	185	elt = que->next;
	186	elt->next->prev = que;
	187	que->next = elt->next;
	188	}
	189
	190	return (elt);
	191	}
	192
	193	static __inline__ queue_entry_t
	194	dequeue_tail(
	195	queue_t que)
	196	{
	197	register queue_entry_t elt = (queue_entry_t) 0;
	198
	199	if (que->prev != que) {
	200	elt = que->prev;
	201	elt->prev->next = que;
	202	que->prev = elt->prev;
	203	}
	204
	205	return (elt);
	206	}
	207
	208	static __inline__ void
	209	remqueue(
91447636	210	__unused queue_t que,
1c79356b A	211	queue_entry_t elt)
	212	{
	213	elt->next->prev = elt->prev;
	214	elt->prev->next = elt->next;
	215	}
	216
	217	static __inline__ void
	218	insque(
	219	queue_entry_t entry,
	220	queue_entry_t pred)
	221	{
	222	entry->next = pred->next;
	223	entry->prev = pred;
	224	(pred->next)->prev = entry;
	225	pred->next = entry;
	226	}
	227
b0d623f7	228	static __inline__ void
1c79356b A	229	remque(
	230	register queue_entry_t elt)
	231	{
	232	(elt->next)->prev = elt->prev;
	233	(elt->prev)->next = elt->next;
1c79356b A	234	}
1c79356b A	235
91447636	236	#endif /* !__GNUC__ */
1c79356b A	237
	238	/*
	239	* Macro: queue_init
	240	* Function:
	241	* Initialize the given queue.
	242	* Header:
	243	* void queue_init(q)
	244	* queue_t q; \* MODIFIED *\
	245	*/
	246	#define queue_init(q) \
	247	MACRO_BEGIN \
	248	(q)->next = (q);\
	249	(q)->prev = (q);\
	250	MACRO_END
	251
	252	/*
	253	* Macro: queue_first
	254	* Function:
	255	* Returns the first entry in the queue,
	256	* Header:
	257	* queue_entry_t queue_first(q)
	258	* queue_t q; \* IN *\
	259	*/
	260	#define queue_first(q) ((q)->next)
	261
	262	/*
	263	* Macro: queue_next
	264	* Function:
	265	* Returns the entry after an item in the queue.
	266	* Header:
	267	* queue_entry_t queue_next(qc)
	268	* queue_t qc;
	269	*/
	270	#define queue_next(qc) ((qc)->next)
	271
	272	/*
	273	* Macro: queue_last
	274	* Function:
	275	* Returns the last entry in the queue.
	276	* Header:
	277	* queue_entry_t queue_last(q)
	278	* queue_t q; \* IN *\
	279	*/
	280	#define queue_last(q) ((q)->prev)
	281
	282	/*
	283	* Macro: queue_prev
	284	* Function:
	285	* Returns the entry before an item in the queue.
	286	* Header:
	287	* queue_entry_t queue_prev(qc)
	288	* queue_t qc;
	289	*/
	290	#define queue_prev(qc) ((qc)->prev)
	291
	292	/*
	293	* Macro: queue_end
	294	* Function:
	295	* Tests whether a new entry is really the end of
	296	* the queue.
	297	* Header:
	298	* boolean_t queue_end(q, qe)
	299	* queue_t q;
	300	* queue_entry_t qe;
301	*/
302	#define queue_end(q, qe) ((q) == (qe))
303
304	/*
305	* Macro: queue_empty
306	* Function:
307	* Tests whether a queue is empty.
308	* Header:
309	* boolean_t queue_empty(q)
310	* queue_t q;
311	*/
312	#define queue_empty(q) queue_end((q), queue_first(q))
313
314
315	/----------------------------------------------------------------/
316	/*
317	* Macros that operate on generic structures. The queue
318	* chain may be at any location within the structure, and there
319	* may be more than one chain.
320	*/
321
322	/*
323	* Macro: queue_enter
324	* Function:
325	* Insert a new element at the tail of the queue.
326	* Header:
327	* void queue_enter(q, elt, type, field)
328	* queue_t q;
329	* <type> elt;
330	* <type> is what's in our queue
331	* <field> is the chain field in (*<type>)
332	*/
333	#define queue_enter(head, elt, type, field) \
334	MACRO_BEGIN \
91447636	335	register queue_entry_t __prev; \
1c79356b	336	\
91447636 A	337	__prev = (head)->prev; \
91447636 A	338	if ((head) == __prev) { \
1c79356b A	339	(head)->next = (queue_entry_t) (elt); \
	340	} \
	341	else { \
91447636	342	((type)__prev)->field.next = (queue_entry_t)(elt);\
1c79356b	343	} \
91447636	344	(elt)->field.prev = __prev; \
1c79356b A	345	(elt)->field.next = head; \
	346	(head)->prev = (queue_entry_t) elt; \
	347	MACRO_END
	348
	349	/*
	350	* Macro: queue_enter_first
	351	* Function:
	352	* Insert a new element at the head of the queue.
	353	* Header:
	354	* void queue_enter_first(q, elt, type, field)
	355	* queue_t q;
	356	* <type> elt;
	357	* <type> is what's in our queue
	358	* <field> is the chain field in (*<type>)
	359	*/
	360	#define queue_enter_first(head, elt, type, field) \
	361	MACRO_BEGIN \
91447636	362	register queue_entry_t __next; \
1c79356b	363	\
91447636 A	364	__next = (head)->next; \
91447636 A	365	if ((head) == __next) { \
1c79356b A	366	(head)->prev = (queue_entry_t) (elt); \
	367	} \
	368	else { \
91447636	369	((type)__next)->field.prev = (queue_entry_t)(elt);\
1c79356b	370	} \
91447636	371	(elt)->field.next = __next; \
1c79356b A	372	(elt)->field.prev = head; \
	373	(head)->next = (queue_entry_t) elt; \
	374	MACRO_END
	375
	376	/*
	377	* Macro: queue_insert_before
	378	* Function:
	379	* Insert a new element before a given element.
	380	* Header:
	381	* void queue_insert_before(q, elt, cur, type, field)
	382	* queue_t q;
	383	* <type> elt;
	384	* <type> cur;
	385	* <type> is what's in our queue
	386	* <field> is the chain field in (*<type>)
	387	*/
	388	#define queue_insert_before(head, elt, cur, type, field) \
	389	MACRO_BEGIN \
91447636	390	register queue_entry_t __prev; \
1c79356b A	391	\
	392	if ((head) == (queue_entry_t)(cur)) { \
	393	(elt)->field.next = (head); \
	394	if ((head)->next == (head)) { /* only element */ \
	395	(elt)->field.prev = (head); \
	396	(head)->next = (queue_entry_t)(elt); \
	397	} else { /* last element */ \
91447636 A	398	__prev = (elt)->field.prev = (head)->prev; \
91447636 A	399	((type)__prev)->field.next = (queue_entry_t)(elt);\
1c79356b A	400	} \
	401	(head)->prev = (queue_entry_t)(elt); \
	402	} else { \
	403	(elt)->field.next = (queue_entry_t)(cur); \
	404	if ((head)->next == (queue_entry_t)(cur)) { \
	405	/* first element */ \
	406	(elt)->field.prev = (head); \
	407	(head)->next = (queue_entry_t)(elt); \
	408	} else { /* middle element */ \
91447636 A	409	__prev = (elt)->field.prev = (cur)->field.prev; \
91447636 A	410	((type)__prev)->field.next = (queue_entry_t)(elt);\
1c79356b A	411	} \
	412	(cur)->field.prev = (queue_entry_t)(elt); \
	413	} \
	414	MACRO_END
	415
	416	/*
	417	* Macro: queue_insert_after
	418	* Function:
	419	* Insert a new element after a given element.
	420	* Header:
	421	* void queue_insert_after(q, elt, cur, type, field)
	422	* queue_t q;
	423	* <type> elt;
	424	* <type> cur;
	425	* <type> is what's in our queue
	426	* <field> is the chain field in (*<type>)
	427	*/
	428	#define queue_insert_after(head, elt, cur, type, field) \
	429	MACRO_BEGIN \
91447636	430	register queue_entry_t __next; \
1c79356b A	431	\
	432	if ((head) == (queue_entry_t)(cur)) { \
	433	(elt)->field.prev = (head); \
	434	if ((head)->next == (head)) { /* only element */ \
	435	(elt)->field.next = (head); \
	436	(head)->prev = (queue_entry_t)(elt); \
	437	} else { /* first element */ \
91447636 A	438	__next = (elt)->field.next = (head)->next; \
91447636 A	439	((type)__next)->field.prev = (queue_entry_t)(elt);\
1c79356b A	440	} \
	441	(head)->next = (queue_entry_t)(elt); \
	442	} else { \
	443	(elt)->field.prev = (queue_entry_t)(cur); \
	444	if ((head)->prev == (queue_entry_t)(cur)) { \
	445	/* last element */ \
	446	(elt)->field.next = (head); \
	447	(head)->prev = (queue_entry_t)(elt); \
	448	} else { /* middle element */ \
91447636 A	449	__next = (elt)->field.next = (cur)->field.next; \
91447636 A	450	((type)__next)->field.prev = (queue_entry_t)(elt);\
1c79356b A	451	} \
	452	(cur)->field.next = (queue_entry_t)(elt); \
	453	} \
	454	MACRO_END
	455
	456	/*
	457	* Macro: queue_field [internal use only]
	458	* Function:
	459	* Find the queue_chain_t (or queue_t) for the
	460	* given element (thing) in the given queue (head)
	461	*/
	462	#define queue_field(head, thing, type, field) \
	463	(((head) == (thing)) ? (head) : &((type)(thing))->field)
	464
	465	/*
	466	* Macro: queue_remove
	467	* Function:
	468	* Remove an arbitrary item from the queue.
	469	* Header:
	470	* void queue_remove(q, qe, type, field)
	471	* arguments as in queue_enter
	472	*/
	473	#define queue_remove(head, elt, type, field) \
	474	MACRO_BEGIN \
91447636	475	register queue_entry_t __next, __prev; \
1c79356b	476	\
91447636 A	477	__next = (elt)->field.next; \
91447636 A	478	__prev = (elt)->field.prev; \
1c79356b	479	\
91447636 A	480	if ((head) == __next) \
91447636 A	481	(head)->prev = __prev; \
1c79356b	482	else \
91447636	483	((type)__next)->field.prev = __prev; \
1c79356b	484	\
91447636 A	485	if ((head) == __prev) \
91447636 A	486	(head)->next = __next; \
1c79356b	487	else \
91447636	488	((type)__prev)->field.next = __next; \
2d21ac55 A	489	\
	490	(elt)->field.next = NULL; \
	491	(elt)->field.prev = NULL; \
1c79356b A	492	MACRO_END
	493
	494	/*
	495	* Macro: queue_remove_first
	496	* Function:
	497	* Remove and return the entry at the head of
	498	* the queue.
	499	* Header:
	500	* queue_remove_first(head, entry, type, field)
	501	* entry is returned by reference
	502	*/
	503	#define queue_remove_first(head, entry, type, field) \
	504	MACRO_BEGIN \
91447636	505	register queue_entry_t __next; \
1c79356b A	506	\
1c79356b A	507	(entry) = (type) ((head)->next); \
91447636	508	__next = (entry)->field.next; \
1c79356b	509	\
91447636	510	if ((head) == __next) \
1c79356b A	511	(head)->prev = (head); \
1c79356b A	512	else \
91447636 A	513	((type)(__next))->field.prev = (head); \
91447636 A	514	(head)->next = __next; \
2d21ac55 A	515	\
	516	(entry)->field.next = NULL; \
	517	(entry)->field.prev = NULL; \
1c79356b A	518	MACRO_END
	519
	520	/*
	521	* Macro: queue_remove_last
	522	* Function:
	523	* Remove and return the entry at the tail of
	524	* the queue.
	525	* Header:
	526	* queue_remove_last(head, entry, type, field)
	527	* entry is returned by reference
	528	*/
	529	#define queue_remove_last(head, entry, type, field) \
	530	MACRO_BEGIN \
91447636	531	register queue_entry_t __prev; \
1c79356b A	532	\
1c79356b A	533	(entry) = (type) ((head)->prev); \
91447636	534	__prev = (entry)->field.prev; \
1c79356b	535	\
91447636	536	if ((head) == __prev) \
1c79356b A	537	(head)->next = (head); \
1c79356b A	538	else \
91447636 A	539	((type)(__prev))->field.next = (head); \
91447636 A	540	(head)->prev = __prev; \
2d21ac55 A	541	\
	542	(entry)->field.next = NULL; \
	543	(entry)->field.prev = NULL; \
1c79356b A	544	MACRO_END
	545
	546	/*
	547	* Macro: queue_assign
	548	*/
	549	#define queue_assign(to, from, type, field) \
	550	MACRO_BEGIN \
	551	((type)((from)->prev))->field.next = (to); \
	552	((type)((from)->next))->field.prev = (to); \
	553	to = from; \
	554	MACRO_END
	555
	556	/*
	557	* Macro: queue_new_head
	558	* Function:
	559	* rebase old queue to new queue head
	560	* Header:
	561	* queue_new_head(old, new, type, field)
	562	* queue_t old;
	563	* queue_t new;
	564	* <type> is what's in our queue
	565	* <field> is the chain field in (*<type>)
	566	*/
	567	#define queue_new_head(old, new, type, field) \
	568	MACRO_BEGIN \
91447636	569	if (!queue_empty(old)) { \
1c79356b A	570	(new) = (old); \
	571	((type)((new)->next))->field.prev = (new); \
	572	((type)((new)->prev))->field.next = (new); \
	573	} else { \
	574	queue_init(new); \
	575	} \
	576	MACRO_END
	577
	578	/*
	579	* Macro: queue_iterate
	580	* Function:
	581	* iterate over each item in the queue.
	582	* Generates a 'for' loop, setting elt to
	583	* each item in turn (by reference).
	584	* Header:
	585	* queue_iterate(q, elt, type, field)
	586	* queue_t q;
	587	* <type> elt;
	588	* <type> is what's in our queue
	589	* <field> is the chain field in (*<type>)
	590	*/
	591	#define queue_iterate(head, elt, type, field) \
	592	for ((elt) = (type) queue_first(head); \
	593	!queue_end((head), (queue_entry_t)(elt)); \
	594	(elt) = (type) queue_next(&(elt)->field))
	595
9bccf70c	596	#ifdef MACH_KERNEL_PRIVATE
1c79356b	597
91447636 A	598	#include <kern/lock.h>
91447636 A	599
1c79356b A	600	/----------------------------------------------------------------/
	601	/*
	602	* Define macros for queues with locks.
	603	*/
	604	struct mpqueue_head {
	605	struct queue_entry head; /* header for queue */
	606	decl_simple_lock_data(, lock) /* lock for queue */
	607	};
	608
	609	typedef struct mpqueue_head mpqueue_head_t;
	610
	611	#define round_mpq(size) (size)
	612
	613	#define mpqueue_init(q) \
	614	MACRO_BEGIN \
	615	queue_init(&(q)->head); \
91447636	616	simple_lock_init(&(q)->lock, 0); \
1c79356b A	617	MACRO_END
	618
	619	#define mpenqueue_tail(q, elt) \
	620	MACRO_BEGIN \
	621	simple_lock(&(q)->lock); \
	622	enqueue_tail(&(q)->head, elt); \
	623	simple_unlock(&(q)->lock); \
	624	MACRO_END
	625
	626	#define mpdequeue_head(q, elt) \
	627	MACRO_BEGIN \
	628	simple_lock(&(q)->lock); \
	629	if (queue_empty(&(q)->head)) \
	630	*(elt) = 0; \
	631	else \
	632	*(elt) = dequeue_head(&(q)->head); \
	633	simple_unlock(&(q)->lock); \
	634	MACRO_END
	635
9bccf70c A	636	#endif /* MACH_KERNEL_PRIVATE */
9bccf70c A	637
1c79356b	638	#endif /* _KERN_QUEUE_H_ */