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

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