![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to queue.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / kernserv|
Return to queue.h CVS log | Up to [Apple Darwin 0.x] / kernel / kernserv |
1.1 root 1: /*
2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights
7: * Reserved. This file contains Original Code and/or Modifications of
8: * Original Code as defined in and that are subject to the Apple Public
9: * Source License Version 1.1 (the "License"). You may not use this file
10: * except in compliance with the License. Please obtain a copy of the
11: * License at http://www.apple.com/publicsource and read it before using
12: * this file.
13: *
14: * The Original Code and all software distributed under the License are
15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
19: * License for the specific language governing rights and limitations
20: * under the License.
21: *
22: * @APPLE_LICENSE_HEADER_END@
23: */
24:
25: /*
26: * Mach Operating System
27: * Copyright (c) 1989 Carnegie-Mellon University
28: * Copyright (c) 1988 Carnegie-Mellon University
29: * Copyright (c) 1987 Carnegie-Mellon University
30: * All rights reserved. The CMU software License Agreement specifies
31: * the terms and conditions for use and redistribution.
32: */
33: /*
34: * File: queue.h
35: *
36: * Type definitions for generic queues.
37: */
38:
39: #ifdef KERNEL_PRIVATE
40: #warning Obsolete header file: <kernserv/queue.h>, use <kern/queue.h> \
41: instead; or better yet, just say no!!
42: #import <kern/queue.h>
43:
44: #else /* KERNEL_PRIVATE */
45:
46: #ifndef _KERN_QUEUE_H_
47: #define _KERN_QUEUE_H_
48:
49: #import <mach/machine/vm_types.h>
50: #import <kernserv/lock.h>
51: #import <kernserv/macro_help.h>
52:
53: /*
54: * Queue of abstract objects. Queue is maintained
55: * within that object.
56: *
57: * Supports fast removal from within the queue.
58: *
59: * How to declare a queue of elements of type "foo_t":
60: * In the "*foo_t" type, you must have a field of
61: * type "queue_chain_t" to hold together this queue.
62: * There may be more than one chain through a
63: * "foo_t", for use by different queues.
64: *
65: * Declare the queue as a "queue_t" type.
66: *
67: * Elements of the queue (of type "foo_t", that is)
68: * are referred to by reference, and cast to type
69: * "queue_entry_t" within this module.
70: */
71:
72: /*
73: * A generic doubly-linked list (queue).
74: */
75:
76: struct queue_entry {
77: struct queue_entry *next; /* next element */
78: struct queue_entry *prev; /* previous element */
79: };
80:
81: typedef struct queue_entry *queue_t;
82: typedef struct queue_entry queue_head_t;
83: typedef struct queue_entry queue_chain_t;
84: typedef struct queue_entry *queue_entry_t;
85:
86: /*
87: * enqueue puts "elt" on the "queue".
88: * dequeue returns the first element in the "queue".
89: * remqueue removes the specified "elt" from the specified "queue".
90: */
91:
92: #define enqueue(queue,elt) enqueue_tail(queue, elt)
93: #define dequeue(queue) dequeue_head(queue)
94:
95: extern void enqueue_head();
96: extern void enqueue_tail();
97: extern queue_entry_t dequeue_head();
98: extern queue_entry_t dequeue_tail();
99: extern void remqueue();
100:
101:
102: /*
103: * Macro: queue_init
104: * Function:
105: * Initialize the given queue.
106: * Header:
107: * void queue_init(q)
108: * queue_t q; \* MODIFIED *\
109: */
110: #define queue_init(q) ((q)->next = (q)->prev = q)
111:
112: /*
113: * Macro: queue_first
114: * Function:
115: * Returns the first entry in the queue,
116: * Header:
117: * queue_entry_t queue_first(q)
118: * queue_t q; \* IN *\
119: */
120: #define queue_first(q) ((q)->next)
121:
122: /*
123: * Macro: queue_next
124: * Header:
125: * queue_entry_t queue_next(qc)
126: * queue_t qc;
127: */
128: #define queue_next(qc) ((qc)->next)
129:
130: /*
131: * Macro: queue_end
132: * Header:
133: * boolean_t queue_end(q, qe)
134: * queue_t q;
135: * queue_entry_t qe;
136: */
137: #define queue_end(q, qe) ((q) == (qe))
138:
139: #define queue_empty(q) queue_end((q), queue_first(q))
140:
141: /*
142: * Macro: queue_enter
143: * Header:
144: * void queue_enter(q, elt, type, field)
145: * queue_t q;
146: * <type> elt;
147: * <type> is what's in our queue
148: * <field> is the chain field in (*<type>)
149: */
150: #define queue_enter(head, elt, type, field) \
151: MACRO_BEGIN \
152: if (queue_empty((head))) { \
153: (head)->next = (queue_entry_t) elt; \
154: (head)->prev = (queue_entry_t) elt; \
155: (elt)->field.next = head; \
156: (elt)->field.prev = head; \
157: } \
158: else { \
159: register queue_entry_t prev; \
160: \
161: prev = (head)->prev; \
162: (elt)->field.prev = prev; \
163: (elt)->field.next = head; \
164: (head)->prev = (queue_entry_t)(elt); \
165: ((type)prev)->field.next = (queue_entry_t)(elt);\
166: } \
167: MACRO_END
168:
169: /*
170: * Macro: queue_field [internal use only]
171: * Function:
172: * Find the queue_chain_t (or queue_t) for the
173: * given element (thing) in the given queue (head)
174: */
175: #define queue_field(head, thing, type, field) \
176: (((head) == (thing)) ? (head) : &((type)(thing))->field)
177:
178: /*
179: * Macro: queue_remove
180: * Header:
181: * void queue_remove(q, qe, type, field)
182: * arguments as in queue_enter
183: */
184: #define queue_remove(head, elt, type, field) \
185: MACRO_BEGIN \
186: register queue_entry_t next, prev; \
187: \
188: next = (elt)->field.next; \
189: prev = (elt)->field.prev; \
190: \
191: queue_field((head), next, type, field)->prev = prev; \
192: queue_field((head), prev, type, field)->next = next; \
193: MACRO_END
194:
195: /*
196: * Macro: queue_assign
197: */
198: #define queue_assign(to, from, type, field) \
199: MACRO_BEGIN \
200: ((type)((from)->prev))->field.next = (to); \
201: ((type)((from)->next))->field.prev = (to); \
202: *to = *from; \
203: MACRO_END
204:
205: #define queue_remove_first(h, e, t, f) \
206: MACRO_BEGIN \
207: e = (t) queue_first((h)); \
208: queue_remove((h), (e), t, f); \
209: MACRO_END
210:
211: #define queue_remove_last(h, e, t, f) \
212: MACRO_BEGIN \
213: e = (t) queue_last((h)); \
214: queue_remove((h), (e), t, f); \
215: MACRO_END
216:
217: /*
218: * Macro: queue_enter_first
219: * Header:
220: * void queue_enter_first(q, elt, type, field)
221: * queue_t q;
222: * <type> elt;
223: * <type> is what's in our queue
224: * <field> is the chain field in (*<type>)
225: */
226: #define queue_enter_first(head, elt, type, field) \
227: MACRO_BEGIN \
228: if (queue_empty((head))) { \
229: (head)->next = (queue_entry_t) elt; \
230: (head)->prev = (queue_entry_t) elt; \
231: (elt)->field.next = head; \
232: (elt)->field.prev = head; \
233: } \
234: else { \
235: register queue_entry_t next; \
236: \
237: next = (head)->next; \
238: (elt)->field.prev = head; \
239: (elt)->field.next = next; \
240: (head)->next = (queue_entry_t)(elt); \
241: ((type)next)->field.prev = (queue_entry_t)(elt);\
242: } \
243: MACRO_END
244:
245: /*
246: * Macro: queue_last
247: * Function:
248: * Returns the last entry in the queue,
249: * Header:
250: * queue_entry_t queue_last(q)
251: * queue_t q; \* IN *\
252: */
253: #define queue_last(q) ((q)->prev)
254:
255: /*
256: * Macro: queue_prev
257: * Header:
258: * queue_entry_t queue_prev(qc)
259: * queue_t qc;
260: */
261: #define queue_prev(qc) ((qc)->prev)
262:
263: /*
264: * Macro: queue_iterate
265: * Function:
266: * iterate over each item in the queue.
267: * Generates a 'for' loop, setting elt to
268: * each item in turn (by reference).
269: * Header:
270: * queue_iterate(q, elt, type, field)
271: * queue_t q;
272: * <type> elt;
273: * <type> is what's in our queue
274: * <field> is the chain field in (*<type>)
275: */
276: #define queue_iterate(head, elt, type, field) \
277: for ((elt) = (type) queue_first(head); \
278: !queue_end((head), (queue_entry_t)(elt)); \
279: (elt) = (type) queue_next(&(elt)->field))
280:
281: #ifdef KERNEL
282:
283: /*
284: * Define macros for queues with locks.
285: */
286: struct mpqueue_head {
287: struct queue_entry head; /* header for queue */
288: simple_lock_data_t lock; /* lock for queue */
289: };
290:
291: typedef struct mpqueue_head mpqueue_head_t;
292:
293: #define round_mpq(size) (size)
294:
295: #define mpqueue_init(q) \
296: MACRO_BEGIN \
297: queue_init(&(q)->head); \
298: simple_lock_init(&(q)->lock); \
299: MACRO_END
300:
301: #define mpenqueue_tail(q, elt) \
302: MACRO_BEGIN \
303: simple_lock(&(q)->lock); \
304: enqueue_tail(&(q)->head, elt); \
305: simple_unlock(&(q)->lock); \
306: MACRO_END
307:
308: #define mpdequeue_head(q, elt) \
309: MACRO_BEGIN \
310: simple_lock(&(q)->lock); \
311: if (queue_empty(&(q)->head)) \
312: *(elt) = 0; \
313: else \
314: *(elt) = dequeue_head(&(q)->head); \
315: simple_unlock(&(q)->lock); \
316: MACRO_END
317:
318: #endif /* KERNEL */
319:
320: #endif /* _KERN_QUEUE_H_ */
321:
322: #endif /* KERNEL_PRIVATE */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.