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