![[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 [GnuMach] / OSKit-Mach / kern|
Return to queue.h CVS log | Up to [GnuMach] / OSKit-Mach / kern |
1.1 root 1: /*
2: * Mach Operating System
3: * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
4: * All Rights Reserved.
5: *
6: * Permission to use, copy, modify and distribute this software and its
7: * documentation is hereby granted, provided that both the copyright
8: * notice and this permission notice appear in all copies of the
9: * software, derivative works or modified versions, and any portions
10: * thereof, and that both notices appear in supporting documentation.
11: *
12: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
13: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
14: * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
15: *
16: * Carnegie Mellon requests users of this software to return to
17: *
18: * Software Distribution Coordinator or [email protected]
19: * School of Computer Science
20: * Carnegie Mellon University
21: * Pittsburgh PA 15213-3890
22: *
23: * any improvements or extensions that they make and grant Carnegie Mellon rights
24: * to redistribute these changes.
25: */
26: /*
27: * File: queue.h
28: * Author: Avadis Tevanian, Jr.
29: * Date: 1985
30: *
31: * Type definitions for generic queues.
32: *
33: */
34:
35: #ifndef _KERN_QUEUE_H_
36: #define _KERN_QUEUE_H_
37:
38: #include <kern/lock.h>
39:
40: /*
41: * Queue of abstract objects. Queue is maintained
42: * within that object.
43: *
44: * Supports fast removal from within the queue.
45: *
46: * How to declare a queue of elements of type "foo_t":
47: * In the "*foo_t" type, you must have a field of
48: * type "queue_chain_t" to hold together this queue.
49: * There may be more than one chain through a
50: * "foo_t", for use by different queues.
51: *
52: * Declare the queue as a "queue_t" type.
53: *
54: * Elements of the queue (of type "foo_t", that is)
55: * are referred to by reference, and cast to type
56: * "queue_entry_t" within this module.
57: */
58:
59: /*
60: * A generic doubly-linked list (queue).
61: */
62:
63: struct queue_entry {
64: struct queue_entry *next; /* next element */
65: struct queue_entry *prev; /* previous element */
66: };
67:
68: typedef struct queue_entry *queue_t;
69: typedef struct queue_entry queue_head_t;
70: typedef struct queue_entry queue_chain_t;
71: typedef struct queue_entry *queue_entry_t;
72:
73: /*
74: * enqueue puts "elt" on the "queue".
75: * dequeue returns the first element in the "queue".
76: * remqueue removes the specified "elt" from the specified "queue".
77: */
78:
79: #define enqueue(queue,elt) enqueue_tail(queue, elt)
80: #define dequeue(queue) dequeue_head(queue)
81:
82: void enqueue_head();
83: void enqueue_tail();
84: queue_entry_t dequeue_head();
85: queue_entry_t dequeue_tail();
86: void remqueue();
87:
88: /*
89: * Macro: queue_init
90: * Function:
91: * Initialize the given queue.
92: * Header:
93: * void queue_init(q)
94: * queue_t q; *MODIFIED*
95: */
96: #define queue_init(q) ((q)->next = (q)->prev = q)
97:
98: /*
99: * Macro: queue_first
100: * Function:
101: * Returns the first entry in the queue,
102: * Header:
103: * queue_entry_t queue_first(q)
104: * queue_t q; *IN*
105: */
106: #define queue_first(q) ((q)->next)
107:
108: /*
109: * Macro: queue_next
110: * Function:
111: * Returns the entry after an item in the queue.
112: * Header:
113: * queue_entry_t queue_next(qc)
114: * queue_t qc;
115: */
116: #define queue_next(qc) ((qc)->next)
117:
118: /*
119: * Macro: queue_last
120: * Function:
121: * Returns the last entry in the queue.
122: * Header:
123: * queue_entry_t queue_last(q)
124: * queue_t q; *IN*
125: */
126: #define queue_last(q) ((q)->prev)
127:
128: /*
129: * Macro: queue_prev
130: * Function:
131: * Returns the entry before an item in the queue.
132: * Header:
133: * queue_entry_t queue_prev(qc)
134: * queue_t qc;
135: */
136: #define queue_prev(qc) ((qc)->prev)
137:
138: /*
139: * Macro: queue_end
140: * Function:
141: * Tests whether a new entry is really the end of
142: * the queue.
143: * Header:
144: * boolean_t queue_end(q, qe)
145: * queue_t q;
146: * queue_entry_t qe;
147: */
148: #define queue_end(q, qe) ((q) == (qe))
149:
150: /*
151: * Macro: queue_empty
152: * Function:
153: * Tests whether a queue is empty.
154: * Header:
155: * boolean_t queue_empty(q)
156: * queue_t q;
157: */
158: #define queue_empty(q) queue_end((q), queue_first(q))
159:
160:
161: /*----------------------------------------------------------------*/
162: /*
163: * Macros that operate on generic structures. The queue
164: * chain may be at any location within the structure, and there
165: * may be more than one chain.
166: */
167:
168: /*
169: * Macro: queue_enter
170: * Function:
171: * Insert a new element at the tail of the queue.
172: * Header:
173: * void queue_enter(q, elt, type, field)
174: * queue_t q;
175: * <type> elt;
176: * <type> is what's in our queue
177: * <field> is the chain field in (*<type>)
178: */
179: #define queue_enter(head, elt, type, field) \
180: { \
181: register queue_entry_t prev; \
182: \
183: prev = (head)->prev; \
184: if ((head) == prev) { \
185: (head)->next = (queue_entry_t) (elt); \
186: } \
187: else { \
188: ((type)prev)->field.next = (queue_entry_t)(elt);\
189: } \
190: (elt)->field.prev = prev; \
191: (elt)->field.next = head; \
192: (head)->prev = (queue_entry_t) elt; \
193: }
194:
195: /*
196: * Macro: queue_enter_first
197: * Function:
198: * Insert a new element at the head of the queue.
199: * Header:
200: * void queue_enter_first(q, elt, type, field)
201: * queue_t q;
202: * <type> elt;
203: * <type> is what's in our queue
204: * <field> is the chain field in (*<type>)
205: */
206: #define queue_enter_first(head, elt, type, field) \
207: { \
208: register queue_entry_t next; \
209: \
210: next = (head)->next; \
211: if ((head) == next) { \
212: (head)->prev = (queue_entry_t) (elt); \
213: } \
214: else { \
215: ((type)next)->field.prev = (queue_entry_t)(elt);\
216: } \
217: (elt)->field.next = next; \
218: (elt)->field.prev = head; \
219: (head)->next = (queue_entry_t) elt; \
220: }
221:
222: /*
223: * Macro: queue_field [internal use only]
224: * Function:
225: * Find the queue_chain_t (or queue_t) for the
226: * given element (thing) in the given queue (head)
227: */
228: #define queue_field(head, thing, type, field) \
229: (((head) == (thing)) ? (head) : &((type)(thing))->field)
230:
231: /*
232: * Macro: queue_remove
233: * Function:
234: * Remove an arbitrary item from the queue.
235: * Header:
236: * void queue_remove(q, qe, type, field)
237: * arguments as in queue_enter
238: */
239: #define queue_remove(head, elt, type, field) \
240: { \
241: register queue_entry_t next, prev; \
242: \
243: next = (elt)->field.next; \
244: prev = (elt)->field.prev; \
245: \
246: if ((head) == next) \
247: (head)->prev = prev; \
248: else \
249: ((type)next)->field.prev = prev; \
250: \
251: if ((head) == prev) \
252: (head)->next = next; \
253: else \
254: ((type)prev)->field.next = next; \
255: }
256:
257: /*
258: * Macro: queue_remove_first
259: * Function:
260: * Remove and return the entry at the head of
261: * the queue.
262: * Header:
263: * queue_remove_first(head, entry, type, field)
264: * entry is returned by reference
265: */
266: #define queue_remove_first(head, entry, type, field) \
267: { \
268: register queue_entry_t next; \
269: \
270: (entry) = (type) ((head)->next); \
271: next = (entry)->field.next; \
272: \
273: if ((head) == next) \
274: (head)->prev = (head); \
275: else \
276: ((type)(next))->field.prev = (head); \
277: (head)->next = next; \
278: }
279:
280: /*
281: * Macro: queue_remove_last
282: * Function:
283: * Remove and return the entry at the tail of
284: * the queue.
285: * Header:
286: * queue_remove_last(head, entry, type, field)
287: * entry is returned by reference
288: */
289: #define queue_remove_last(head, entry, type, field) \
290: { \
291: register queue_entry_t prev; \
292: \
293: (entry) = (type) ((head)->prev); \
294: prev = (entry)->field.prev; \
295: \
296: if ((head) == prev) \
297: (head)->next = (head); \
298: else \
299: ((type)(prev))->field.next = (head); \
300: (head)->prev = prev; \
301: }
302:
303: /*
304: * Macro: queue_assign
305: */
306: #define queue_assign(to, from, type, field) \
307: { \
308: ((type)((from)->prev))->field.next = (to); \
309: ((type)((from)->next))->field.prev = (to); \
310: *to = *from; \
311: }
312:
313: /*
314: * Macro: queue_iterate
315: * Function:
316: * iterate over each item in the queue.
317: * Generates a 'for' loop, setting elt to
318: * each item in turn (by reference).
319: * Header:
320: * queue_iterate(q, elt, type, field)
321: * queue_t q;
322: * <type> elt;
323: * <type> is what's in our queue
324: * <field> is the chain field in (*<type>)
325: */
326: #define queue_iterate(head, elt, type, field) \
327: for ((elt) = (type) queue_first(head); \
328: !queue_end((head), (queue_entry_t)(elt)); \
329: (elt) = (type) queue_next(&(elt)->field))
330:
331:
332:
333: /*----------------------------------------------------------------*/
334: /*
335: * Define macros for queues with locks.
336: */
337: struct mpqueue_head {
338: struct queue_entry head; /* header for queue */
339: struct slock lock; /* lock for queue */
340: };
341:
342: typedef struct mpqueue_head mpqueue_head_t;
343:
344: #define round_mpq(size) (size)
345:
346: #define mpqueue_init(q) \
347: { \
348: queue_init(&(q)->head); \
349: simple_lock_init(&(q)->lock); \
350: }
351:
352: #define mpenqueue_tail(q, elt) \
353: simple_lock(&(q)->lock); \
354: enqueue_tail(&(q)->head, elt); \
355: simple_unlock(&(q)->lock);
356:
357: #define mpdequeue_head(q, elt) \
358: simple_lock(&(q)->lock); \
359: if (queue_empty(&(q)->head)) \
360: *(elt) = 0; \
361: else \
362: *(elt) = dequeue_head(&(q)->head); \
363: simple_unlock(&(q)->lock);
364:
365: /*
366: * Old queue stuff, will go away soon.
367: */
368:
369: #endif /* _KERN_QUEUE_H_ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.