[apple/xnu.git] / osfmk / kern / 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@
 */
/*
 * @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 <kern/lock.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__)

/* 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 int		remque(
				queue_entry_t elt);

#else

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(
	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__ integer_t
remque(
	register queue_entry_t elt)
{
	(elt->next)->prev = elt->prev;
	(elt->prev)->next = elt->next;

	return((integer_t)elt);
}

#endif	/* defined(__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;		\
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;					\
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;					\
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(new)) {				\
		*(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))

#include <sys/appleapiopts.h>

#ifdef	__APPLE_API_PRIVATE

#ifdef	MACH_KERNEL_PRIVATE

/*----------------------------------------------------------------*/
/*
 *	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, ETAP_MISC_Q);	\
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	/* __APPLE_API_PRIVATE */

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