![[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] / Gnu-Mach / kern|
Return to queue.h CVS log | Up to [GnuMach] / Gnu-Mach / kern |
1.1.1.2 root 1: /*
1.1 root 2: * Mach Operating System
3: * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
4: * All Rights Reserved.
1.1.1.2 root 5: *
1.1 root 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.
1.1.1.2 root 11: *
1.1 root 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.
1.1.1.2 root 15: *
1.1 root 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:
1.1.1.3 root 82: void enqueue_head(queue_t, queue_entry_t);
83: void enqueue_tail(queue_t, queue_entry_t);
84: queue_entry_t dequeue_head(queue_t);
85: queue_entry_t dequeue_tail(queue_t);
86: void remqueue(queue_t, queue_entry_t);
87: void insque(queue_entry_t, queue_entry_t);
1.1 root 88:
89: /*
90: * Macro: queue_init
91: * Function:
92: * Initialize the given queue.
93: * Header:
94: * void queue_init(q)
95: * queue_t q; *MODIFIED*
96: */
97: #define queue_init(q) ((q)->next = (q)->prev = q)
98:
99: /*
100: * Macro: queue_first
101: * Function:
102: * Returns the first entry in the queue,
103: * Header:
104: * queue_entry_t queue_first(q)
105: * queue_t q; *IN*
106: */
107: #define queue_first(q) ((q)->next)
108:
109: /*
110: * Macro: queue_next
111: * Function:
112: * Returns the entry after an item in the queue.
113: * Header:
114: * queue_entry_t queue_next(qc)
115: * queue_t qc;
116: */
117: #define queue_next(qc) ((qc)->next)
118:
119: /*
120: * Macro: queue_last
121: * Function:
122: * Returns the last entry in the queue.
123: * Header:
124: * queue_entry_t queue_last(q)
125: * queue_t q; *IN*
126: */
127: #define queue_last(q) ((q)->prev)
128:
129: /*
130: * Macro: queue_prev
131: * Function:
132: * Returns the entry before an item in the queue.
133: * Header:
134: * queue_entry_t queue_prev(qc)
135: * queue_t qc;
136: */
137: #define queue_prev(qc) ((qc)->prev)
138:
139: /*
140: * Macro: queue_end
141: * Function:
142: * Tests whether a new entry is really the end of
143: * the queue.
144: * Header:
145: * boolean_t queue_end(q, qe)
146: * queue_t q;
147: * queue_entry_t qe;
148: */
149: #define queue_end(q, qe) ((q) == (qe))
150:
151: /*
152: * Macro: queue_empty
153: * Function:
154: * Tests whether a queue is empty.
155: * Header:
156: * boolean_t queue_empty(q)
157: * queue_t q;
158: */
159: #define queue_empty(q) queue_end((q), queue_first(q))
160:
161:
162: /*----------------------------------------------------------------*/
163: /*
164: * Macros that operate on generic structures. The queue
165: * chain may be at any location within the structure, and there
166: * may be more than one chain.
167: */
168:
169: /*
170: * Macro: queue_enter
171: * Function:
172: * Insert a new element at the tail of the queue.
173: * Header:
174: * void queue_enter(q, elt, type, field)
175: * queue_t q;
176: * <type> elt;
177: * <type> is what's in our queue
178: * <field> is the chain field in (*<type>)
179: */
180: #define queue_enter(head, elt, type, field) \
181: { \
1.1.1.4 ! root 182: queue_entry_t prev; \
1.1 root 183: \
184: prev = (head)->prev; \
185: if ((head) == prev) { \
186: (head)->next = (queue_entry_t) (elt); \
187: } \
188: else { \
189: ((type)prev)->field.next = (queue_entry_t)(elt);\
190: } \
191: (elt)->field.prev = prev; \
192: (elt)->field.next = head; \
193: (head)->prev = (queue_entry_t) elt; \
194: }
195:
196: /*
197: * Macro: queue_enter_first
198: * Function:
199: * Insert a new element at the head of the queue.
200: * Header:
201: * void queue_enter_first(q, elt, type, field)
202: * queue_t q;
203: * <type> elt;
204: * <type> is what's in our queue
205: * <field> is the chain field in (*<type>)
206: */
207: #define queue_enter_first(head, elt, type, field) \
208: { \
1.1.1.4 ! root 209: queue_entry_t next; \
1.1 root 210: \
211: next = (head)->next; \
212: if ((head) == next) { \
213: (head)->prev = (queue_entry_t) (elt); \
214: } \
215: else { \
216: ((type)next)->field.prev = (queue_entry_t)(elt);\
217: } \
218: (elt)->field.next = next; \
219: (elt)->field.prev = head; \
220: (head)->next = (queue_entry_t) elt; \
221: }
222:
223: /*
224: * Macro: queue_field [internal use only]
225: * Function:
226: * Find the queue_chain_t (or queue_t) for the
227: * given element (thing) in the given queue (head)
228: */
229: #define queue_field(head, thing, type, field) \
230: (((head) == (thing)) ? (head) : &((type)(thing))->field)
231:
232: /*
233: * Macro: queue_remove
234: * Function:
235: * Remove an arbitrary item from the queue.
236: * Header:
237: * void queue_remove(q, qe, type, field)
238: * arguments as in queue_enter
239: */
240: #define queue_remove(head, elt, type, field) \
241: { \
1.1.1.4 ! root 242: queue_entry_t next, prev; \
1.1 root 243: \
244: next = (elt)->field.next; \
245: prev = (elt)->field.prev; \
246: \
247: if ((head) == next) \
248: (head)->prev = prev; \
249: else \
250: ((type)next)->field.prev = prev; \
251: \
252: if ((head) == prev) \
253: (head)->next = next; \
254: else \
255: ((type)prev)->field.next = next; \
256: }
257:
258: /*
259: * Macro: queue_remove_first
260: * Function:
261: * Remove and return the entry at the head of
262: * the queue.
263: * Header:
264: * queue_remove_first(head, entry, type, field)
265: * entry is returned by reference
266: */
267: #define queue_remove_first(head, entry, type, field) \
268: { \
1.1.1.4 ! root 269: queue_entry_t next; \
1.1 root 270: \
271: (entry) = (type) ((head)->next); \
272: next = (entry)->field.next; \
273: \
274: if ((head) == next) \
275: (head)->prev = (head); \
276: else \
277: ((type)(next))->field.prev = (head); \
278: (head)->next = next; \
279: }
280:
281: /*
282: * Macro: queue_remove_last
283: * Function:
284: * Remove and return the entry at the tail of
285: * the queue.
286: * Header:
287: * queue_remove_last(head, entry, type, field)
288: * entry is returned by reference
289: */
290: #define queue_remove_last(head, entry, type, field) \
291: { \
1.1.1.4 ! root 292: queue_entry_t prev; \
1.1 root 293: \
294: (entry) = (type) ((head)->prev); \
295: prev = (entry)->field.prev; \
296: \
297: if ((head) == prev) \
298: (head)->next = (head); \
299: else \
300: ((type)(prev))->field.next = (head); \
301: (head)->prev = prev; \
302: }
303:
304: /*
305: * Macro: queue_assign
306: */
307: #define queue_assign(to, from, type, field) \
308: { \
309: ((type)((from)->prev))->field.next = (to); \
310: ((type)((from)->next))->field.prev = (to); \
311: *to = *from; \
312: }
313:
314: /*
315: * Macro: queue_iterate
316: * Function:
317: * iterate over each item in the queue.
318: * Generates a 'for' loop, setting elt to
319: * each item in turn (by reference).
320: * Header:
321: * queue_iterate(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_iterate(head, elt, type, field) \
328: for ((elt) = (type) queue_first(head); \
329: !queue_end((head), (queue_entry_t)(elt)); \
330: (elt) = (type) queue_next(&(elt)->field))
331:
332:
333:
334: /*----------------------------------------------------------------*/
335: /*
336: * Define macros for queues with locks.
337: */
338: struct mpqueue_head {
339: struct queue_entry head; /* header for queue */
340: struct slock lock; /* lock for queue */
341: };
342:
343: typedef struct mpqueue_head mpqueue_head_t;
344:
345: #define round_mpq(size) (size)
346:
347: #define mpqueue_init(q) \
348: { \
349: queue_init(&(q)->head); \
350: simple_lock_init(&(q)->lock); \
351: }
352:
353: #define mpenqueue_tail(q, elt) \
354: simple_lock(&(q)->lock); \
355: enqueue_tail(&(q)->head, elt); \
356: simple_unlock(&(q)->lock);
357:
358: #define mpdequeue_head(q, elt) \
359: simple_lock(&(q)->lock); \
360: if (queue_empty(&(q)->head)) \
361: *(elt) = 0; \
362: else \
363: *(elt) = dequeue_head(&(q)->head); \
364: simple_unlock(&(q)->lock);
365:
366: /*
367: * Old queue stuff, will go away soon.
368: */
369:
1.1.1.2 root 370: #endif /* _KERN_QUEUE_H_ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.