![[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 / kern|
Return to queue.h CVS log | Up to [Apple Darwin 0.x] / kernel / kern |
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) 1991,1990,1989,1988,1987 Carnegie Mellon University
28: * All Rights Reserved.
29: *
30: * Permission to use, copy, modify and distribute this software and its
31: * documentation is hereby granted, provided that both the copyright
32: * notice and this permission notice appear in all copies of the
33: * software, derivative works or modified versions, and any portions
34: * thereof, and that both notices appear in supporting documentation.
35: *
36: * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
37: * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
38: * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
39: *
40: * Carnegie Mellon requests users of this software to return to
41: *
42: * Software Distribution Coordinator or [email protected]
43: * School of Computer Science
44: * Carnegie Mellon University
45: * Pittsburgh PA 15213-3890
46: *
47: * any improvements or extensions that they make and grant Carnegie Mellon rights
48: * to redistribute these changes.
49: */
50: /*
51: * File: queue.h
52: * Author: Avadis Tevanian, Jr.
53: * Date: 1985
54: *
55: * Type definitions for generic queues.
56: *
57: */
58:
59: #ifndef _KERN_QUEUE_H_
60: #define _KERN_QUEUE_H_
61:
62: #include <kern/lock.h>
63: #include <kern/macro_help.h>
64:
65: /*
66: * Queue of abstract objects. Queue is maintained
67: * within that object.
68: *
69: * Supports fast removal from within the queue.
70: *
71: * How to declare a queue of elements of type "foo_t":
72: * In the "*foo_t" type, you must have a field of
73: * type "queue_chain_t" to hold together this queue.
74: * There may be more than one chain through a
75: * "foo_t", for use by different queues.
76: *
77: * Declare the queue as a "queue_t" type.
78: *
79: * Elements of the queue (of type "foo_t", that is)
80: * are referred to by reference, and cast to type
81: * "queue_entry_t" within this module.
82: */
83:
84: /*
85: * A generic doubly-linked list (queue).
86: */
87:
88: struct queue_entry {
89: struct queue_entry *next; /* next element */
90: struct queue_entry *prev; /* previous element */
91: };
92:
93: typedef struct queue_entry *queue_t;
94: typedef struct queue_entry queue_head_t;
95: typedef struct queue_entry queue_chain_t;
96: typedef struct queue_entry *queue_entry_t;
97:
98: /*
99: * enqueue puts "elt" on the "queue".
100: * dequeue returns the first element in the "queue".
101: * remqueue removes the specified "elt" from the specified "queue".
102: */
103:
104: #define enqueue(queue,elt) enqueue_tail(queue, elt)
105: #define dequeue(queue) dequeue_head(queue)
106:
107: /*
108: * Routines to implement queue package.
109: */
110:
111: #ifndef _KERN_QUEUE_FUNCTION_SCOPE_
112: #define _KERN_QUEUE_FUNCTION_SCOPE_ static __inline__
113: #define _KERN_QUEUE_H_INTERNAL_SCOPING_
114: #endif
115:
116: /*
117: * Insert element at head of queue.
118: */
119: _KERN_QUEUE_FUNCTION_SCOPE_
120: void enqueue_head(
121: register queue_t que,
122: register queue_entry_t elt)
123: {
124: elt->next = que->next;
125: elt->prev = que;
126: elt->next->prev = elt;
127: que->next = elt;
128: }
129:
130: /*
131: * Insert element at tail of queue.
132: */
133: _KERN_QUEUE_FUNCTION_SCOPE_
134: void enqueue_tail(
135: register queue_t que,
136: register queue_entry_t elt)
137: {
138: elt->next = que;
139: elt->prev = que->prev;
140: elt->prev->next = elt;
141: que->prev = elt;
142: }
143:
144: /*
145: * Remove and return element at head of queue.
146: */
147: _KERN_QUEUE_FUNCTION_SCOPE_
148: queue_entry_t dequeue_head(
149: register queue_t que)
150: {
151: register queue_entry_t elt;
152:
153: if (que->next == que)
154: return((queue_entry_t)0);
155:
156: elt = que->next;
157: elt->next->prev = que;
158: que->next = elt->next;
159: return(elt);
160: }
161:
162: /*
163: * Remove and return element at tail of queue.
164: */
165: _KERN_QUEUE_FUNCTION_SCOPE_
166: queue_entry_t dequeue_tail(
167: register queue_t que)
168: {
169: register queue_entry_t elt;
170:
171: if (que->prev == que)
172: return((queue_entry_t)0);
173:
174: elt = que->prev;
175: elt->prev->next = que;
176: que->prev = elt->prev;
177: return(elt);
178: }
179:
180: /*
181: * Remove arbitrary element from queue.
182: * Does not check whether element is on queue - the world
183: * will go haywire if it isn't.
184: */
185:
186: _KERN_QUEUE_FUNCTION_SCOPE_
187: /*ARGSUSED*/
188: void remqueue(
189: queue_t que,
190: register queue_entry_t elt)
191: {
192: elt->next->prev = elt->prev;
193: elt->prev->next = elt->next;
194: }
195:
196: /*
197: * Routines to directly imitate the VAX hardware queue
198: * package.
199: */
200: _KERN_QUEUE_FUNCTION_SCOPE_
201: void insque(
202: register struct queue_entry *entry,
203: register struct queue_entry *pred)
204: {
205: entry->next = pred->next;
206: entry->prev = pred;
207: (pred->next)->prev = entry;
208: pred->next = entry;
209: }
210:
211: _KERN_QUEUE_FUNCTION_SCOPE_
212: struct queue_entry
213: *remque(
214: register struct queue_entry *elt)
215: {
216: (elt->next)->prev = elt->prev;
217: (elt->prev)->next = elt->next;
218: return(elt);
219: }
220:
221: #ifdef _KERN_QUEUE_H_INTERNAL_SCOPING_
222: #undef _KERN_QUEUE_H_INTERNAL_SCOPING_
223: #endif
224:
225: /*
226: * Macro: queue_init
227: * Function:
228: * Initialize the given queue.
229: * Header:
230: * void queue_init(q)
231: * queue_t q; *MODIFIED*
232: */
233: #define queue_init(q) ((q)->next = (q)->prev = q)
234:
235: /*
236: * Macro: queue_first
237: * Function:
238: * Returns the first entry in the queue,
239: * Header:
240: * queue_entry_t queue_first(q)
241: * queue_t q; *IN*
242: */
243: #define queue_first(q) ((q)->next)
244:
245: /*
246: * Macro: queue_next
247: * Function:
248: * Returns the entry after an item in the queue.
249: * Header:
250: * queue_entry_t queue_next(qc)
251: * queue_t qc;
252: */
253: #define queue_next(qc) ((qc)->next)
254:
255: /*
256: * Macro: queue_last
257: * Function:
258: * Returns the last entry in the queue.
259: * Header:
260: * queue_entry_t queue_last(q)
261: * queue_t q; *IN*
262: */
263: #define queue_last(q) ((q)->prev)
264:
265: /*
266: * Macro: queue_prev
267: * Function:
268: * Returns the entry before an item in the queue.
269: * Header:
270: * queue_entry_t queue_prev(qc)
271: * queue_t qc;
272: */
273: #define queue_prev(qc) ((qc)->prev)
274:
275: /*
276: * Macro: queue_end
277: * Function:
278: * Tests whether a new entry is really the end of
279: * the queue.
280: * Header:
281: * boolean_t queue_end(q, qe)
282: * queue_t q;
283: * queue_entry_t qe;
284: */
285: #define queue_end(q, qe) ((q) == (qe))
286:
287: /*
288: * Macro: queue_empty
289: * Function:
290: * Tests whether a queue is empty.
291: * Header:
292: * boolean_t queue_empty(q)
293: * queue_t q;
294: */
295: #define queue_empty(q) queue_end((q), queue_first(q))
296:
297:
298: /*----------------------------------------------------------------*/
299: /*
300: * Macros that operate on generic structures. The queue
301: * chain may be at any location within the structure, and there
302: * may be more than one chain.
303: */
304:
305: /*
306: * Macro: queue_enter
307: * Function:
308: * Insert a new element at the tail of the queue.
309: * Header:
310: * void queue_enter(q, elt, type, field)
311: * queue_t q;
312: * <type> elt;
313: * <type> is what's in our queue
314: * <field> is the chain field in (*<type>)
315: */
316: #define queue_enter(head, elt, type, field) \
317: MACRO_BEGIN \
318: register queue_entry_t prev; \
319: \
320: prev = (head)->prev; \
321: if ((head) == prev) { \
322: (head)->next = (queue_entry_t) (elt); \
323: } \
324: else { \
325: ((type)prev)->field.next = (queue_entry_t)(elt);\
326: } \
327: (elt)->field.prev = prev; \
328: (elt)->field.next = head; \
329: (head)->prev = (queue_entry_t) elt; \
330: MACRO_END
331:
332: /*
333: * Macro: queue_enter_first
334: * Function:
335: * Insert a new element at the head of the queue.
336: * Header:
337: * void queue_enter_first(q, elt, type, field)
338: * queue_t q;
339: * <type> elt;
340: * <type> is what's in our queue
341: * <field> is the chain field in (*<type>)
342: */
343: #define queue_enter_first(head, elt, type, field) \
344: MACRO_BEGIN \
345: register queue_entry_t next; \
346: \
347: next = (head)->next; \
348: if ((head) == next) { \
349: (head)->prev = (queue_entry_t) (elt); \
350: } \
351: else { \
352: ((type)next)->field.prev = (queue_entry_t)(elt);\
353: } \
354: (elt)->field.next = next; \
355: (elt)->field.prev = head; \
356: (head)->next = (queue_entry_t) elt; \
357: MACRO_END
358:
359: /*
360: * Macro: queue_field [internal use only]
361: * Function:
362: * Find the queue_chain_t (or queue_t) for the
363: * given element (thing) in the given queue (head)
364: */
365: #define queue_field(head, thing, type, field) \
366: (((head) == (thing)) ? (head) : &((type)(thing))->field)
367:
368: /*
369: * Macro: queue_remove
370: * Function:
371: * Remove an arbitrary item from the queue.
372: * Header:
373: * void queue_remove(q, qe, type, field)
374: * arguments as in queue_enter
375: */
376: #define queue_remove(head, elt, type, field) \
377: MACRO_BEGIN \
378: register queue_entry_t next, prev; \
379: \
380: next = (elt)->field.next; \
381: prev = (elt)->field.prev; \
382: \
383: if ((head) == next) \
384: (head)->prev = prev; \
385: else \
386: ((type)next)->field.prev = prev; \
387: \
388: if ((head) == prev) \
389: (head)->next = next; \
390: else \
391: ((type)prev)->field.next = next; \
392: MACRO_END
393:
394: /*
395: * Macro: queue_remove_first
396: * Function:
397: * Remove and return the entry at the head of
398: * the queue.
399: * Header:
400: * queue_remove_first(head, entry, type, field)
401: * entry is returned by reference
402: */
403: #define queue_remove_first(head, entry, type, field) \
404: MACRO_BEGIN \
405: register queue_entry_t next; \
406: \
407: (entry) = (type) ((head)->next); \
408: next = (entry)->field.next; \
409: \
410: if ((head) == next) \
411: (head)->prev = (head); \
412: else \
413: ((type)(next))->field.prev = (head); \
414: (head)->next = next; \
415: MACRO_END
416:
417: /*
418: * Macro: queue_remove_last
419: * Function:
420: * Remove and return the entry at the tail of
421: * the queue.
422: * Header:
423: * queue_remove_last(head, entry, type, field)
424: * entry is returned by reference
425: */
426: #define queue_remove_last(head, entry, type, field) \
427: MACRO_BEGIN \
428: register queue_entry_t prev; \
429: \
430: (entry) = (type) ((head)->prev); \
431: prev = (entry)->field.prev; \
432: \
433: if ((head) == prev) \
434: (head)->next = (head); \
435: else \
436: ((type)(prev))->field.next = (head); \
437: (head)->prev = prev; \
438: MACRO_END
439:
440: /*
441: * Macro: queue_assign
442: */
443: #define queue_assign(to, from, type, field) \
444: MACRO_BEGIN \
445: ((type)((from)->prev))->field.next = (to); \
446: ((type)((from)->next))->field.prev = (to); \
447: *to = *from; \
448: MACRO_END
449:
450: /*
451: * Macro: queue_iterate
452: * Function:
453: * iterate over each item in the queue.
454: * Generates a 'for' loop, setting elt to
455: * each item in turn (by reference).
456: * Header:
457: * queue_iterate(q, elt, type, field)
458: * queue_t q;
459: * <type> elt;
460: * <type> is what's in our queue
461: * <field> is the chain field in (*<type>)
462: */
463: #define queue_iterate(head, elt, type, field) \
464: for ((elt) = (type) queue_first(head); \
465: !queue_end((head), (queue_entry_t)(elt)); \
466: (elt) = (type) queue_next(&(elt)->field))
467:
468: #endif /* _KERN_QUEUE_H_ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.