![[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 XNU] / XNU / osfmk / kern|
Return to queue.h CVS log | Up to [Apple XNU] / XNU / osfmk / kern |
1.1 root 1: /*
2: * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3: *
4: * @APPLE_LICENSE_HEADER_START@
5: *
6: * The contents of this file constitute Original Code as defined in and
7: * are subject to the Apple Public Source License Version 1.1 (the
8: * "License"). You may not use this file except in compliance with the
9: * License. Please obtain a copy of the License at
10: * http://www.apple.com/publicsource and read it before using this file.
11: *
12: * This Original Code and all software distributed under the License are
13: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17: * License for the specific language governing rights and limitations
18: * under the License.
19: *
20: * @APPLE_LICENSE_HEADER_END@
21: */
22: /*
23: * @OSF_COPYRIGHT@
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: */
52: /*
53: * File: queue.h
54: * Author: Avadis Tevanian, Jr.
55: * Date: 1985
56: *
57: * Type definitions for generic queues.
58: *
59: */
60:
61: #ifndef _KERN_QUEUE_H_
62: #define _KERN_QUEUE_H_
63:
64: #include <kern/lock.h>
65: #include <kern/macro_help.h>
66:
67: /*
68: * Queue of abstract objects. Queue is maintained
69: * within that object.
70: *
71: * Supports fast removal from within the queue.
72: *
73: * How to declare a queue of elements of type "foo_t":
74: * In the "*foo_t" type, you must have a field of
75: * type "queue_chain_t" to hold together this queue.
76: * There may be more than one chain through a
77: * "foo_t", for use by different queues.
78: *
79: * Declare the queue as a "queue_t" type.
80: *
81: * Elements of the queue (of type "foo_t", that is)
82: * are referred to by reference, and cast to type
83: * "queue_entry_t" within this module.
84: */
85:
86: /*
87: * A generic doubly-linked list (queue).
88: */
89:
90: struct queue_entry {
91: struct queue_entry *next; /* next element */
92: struct queue_entry *prev; /* previous element */
93: };
94:
95: typedef struct queue_entry *queue_t;
96: typedef struct queue_entry queue_head_t;
97: typedef struct queue_entry queue_chain_t;
98: typedef struct queue_entry *queue_entry_t;
99:
100: /*
101: * enqueue puts "elt" on the "queue".
102: * dequeue returns the first element in the "queue".
103: * remqueue removes the specified "elt" from the specified "queue".
104: */
105:
106: #define enqueue(queue,elt) enqueue_tail(queue, elt)
107: #define dequeue(queue) dequeue_head(queue)
108:
109: #if !defined(__GNUC__)
110:
111: /* Enqueue element to head of queue */
112: extern void enqueue_head(
113: queue_t que,
114: queue_entry_t elt);
115:
116: /* Enqueue element to tail of queue */
117: extern void enqueue_tail(
118: queue_t que,
119: queue_entry_t elt);
120:
121: /* Dequeue element from head of queue */
122: extern queue_entry_t dequeue_head(
123: queue_t que);
124:
125: /* Dequeue element from tail of queue */
126: extern queue_entry_t dequeue_tail(
127: queue_t que);
128:
129: /* Dequeue element */
130: extern void remqueue(
131: queue_t que,
132: queue_entry_t elt);
133:
134: /* Enqueue element after a particular elem */
135: extern void insque(
136: queue_entry_t entry,
137: queue_entry_t pred);
138:
139: /* Dequeue element */
140: extern int remque(
141: queue_entry_t elt);
142:
143: #else
144:
145: static __inline__ void
146: enqueue_head(
147: queue_t que,
148: queue_entry_t elt)
149: {
150: elt->next = que->next;
151: elt->prev = que;
152: elt->next->prev = elt;
153: que->next = elt;
154: }
155:
156: static __inline__ void
157: enqueue_tail(
158: queue_t que,
159: queue_entry_t elt)
160: {
161: elt->next = que;
162: elt->prev = que->prev;
163: elt->prev->next = elt;
164: que->prev = elt;
165: }
166:
167: static __inline__ queue_entry_t
168: dequeue_head(
169: queue_t que)
170: {
171: register queue_entry_t elt = (queue_entry_t) 0;
172:
173: if (que->next != que) {
174: elt = que->next;
175: elt->next->prev = que;
176: que->next = elt->next;
177: }
178:
179: return (elt);
180: }
181:
182: static __inline__ queue_entry_t
183: dequeue_tail(
184: queue_t que)
185: {
186: register queue_entry_t elt = (queue_entry_t) 0;
187:
188: if (que->prev != que) {
189: elt = que->prev;
190: elt->prev->next = que;
191: que->prev = elt->prev;
192: }
193:
194: return (elt);
195: }
196:
197: static __inline__ void
198: remqueue(
199: queue_t que,
200: queue_entry_t elt)
201: {
202: elt->next->prev = elt->prev;
203: elt->prev->next = elt->next;
204: }
205:
206: static __inline__ void
207: insque(
208: queue_entry_t entry,
209: queue_entry_t pred)
210: {
211: entry->next = pred->next;
212: entry->prev = pred;
213: (pred->next)->prev = entry;
214: pred->next = entry;
215: }
216:
217: static __inline__ integer_t
218: remque(
219: register queue_entry_t elt)
220: {
221: (elt->next)->prev = elt->prev;
222: (elt->prev)->next = elt->next;
223:
224: return((integer_t)elt);
225: }
226:
227: #endif /* defined(__GNUC__) */
228:
229: /*
230: * Macro: queue_init
231: * Function:
232: * Initialize the given queue.
233: * Header:
234: * void queue_init(q)
235: * queue_t q; \* MODIFIED *\
236: */
237: #define queue_init(q) \
238: MACRO_BEGIN \
239: (q)->next = (q);\
240: (q)->prev = (q);\
241: MACRO_END
242:
243: /*
244: * Macro: queue_first
245: * Function:
246: * Returns the first entry in the queue,
247: * Header:
248: * queue_entry_t queue_first(q)
249: * queue_t q; \* IN *\
250: */
251: #define queue_first(q) ((q)->next)
252:
253: /*
254: * Macro: queue_next
255: * Function:
256: * Returns the entry after an item in the queue.
257: * Header:
258: * queue_entry_t queue_next(qc)
259: * queue_t qc;
260: */
261: #define queue_next(qc) ((qc)->next)
262:
263: /*
264: * Macro: queue_last
265: * Function:
266: * Returns the last entry in the queue.
267: * Header:
268: * queue_entry_t queue_last(q)
269: * queue_t q; \* IN *\
270: */
271: #define queue_last(q) ((q)->prev)
272:
273: /*
274: * Macro: queue_prev
275: * Function:
276: * Returns the entry before an item in the queue.
277: * Header:
278: * queue_entry_t queue_prev(qc)
279: * queue_t qc;
280: */
281: #define queue_prev(qc) ((qc)->prev)
282:
283: /*
284: * Macro: queue_end
285: * Function:
286: * Tests whether a new entry is really the end of
287: * the queue.
288: * Header:
289: * boolean_t queue_end(q, qe)
290: * queue_t q;
291: * queue_entry_t qe;
292: */
293: #define queue_end(q, qe) ((q) == (qe))
294:
295: /*
296: * Macro: queue_empty
297: * Function:
298: * Tests whether a queue is empty.
299: * Header:
300: * boolean_t queue_empty(q)
301: * queue_t q;
302: */
303: #define queue_empty(q) queue_end((q), queue_first(q))
304:
305:
306: /*----------------------------------------------------------------*/
307: /*
308: * Macros that operate on generic structures. The queue
309: * chain may be at any location within the structure, and there
310: * may be more than one chain.
311: */
312:
313: /*
314: * Macro: queue_enter
315: * Function:
316: * Insert a new element at the tail of the queue.
317: * Header:
318: * void queue_enter(q, elt, type, field)
319: * queue_t q;
320: * <type> elt;
321: * <type> is what's in our queue
322: * <field> is the chain field in (*<type>)
323: */
324: #define queue_enter(head, elt, type, field) \
325: MACRO_BEGIN \
326: register queue_entry_t prev; \
327: \
328: prev = (head)->prev; \
329: if ((head) == prev) { \
330: (head)->next = (queue_entry_t) (elt); \
331: } \
332: else { \
333: ((type)prev)->field.next = (queue_entry_t)(elt);\
334: } \
335: (elt)->field.prev = prev; \
336: (elt)->field.next = head; \
337: (head)->prev = (queue_entry_t) elt; \
338: MACRO_END
339:
340: /*
341: * Macro: queue_enter_first
342: * Function:
343: * Insert a new element at the head of the queue.
344: * Header:
345: * void queue_enter_first(q, elt, type, field)
346: * queue_t q;
347: * <type> elt;
348: * <type> is what's in our queue
349: * <field> is the chain field in (*<type>)
350: */
351: #define queue_enter_first(head, elt, type, field) \
352: MACRO_BEGIN \
353: register queue_entry_t next; \
354: \
355: next = (head)->next; \
356: if ((head) == next) { \
357: (head)->prev = (queue_entry_t) (elt); \
358: } \
359: else { \
360: ((type)next)->field.prev = (queue_entry_t)(elt);\
361: } \
362: (elt)->field.next = next; \
363: (elt)->field.prev = head; \
364: (head)->next = (queue_entry_t) elt; \
365: MACRO_END
366:
367: /*
368: * Macro: queue_insert_before
369: * Function:
370: * Insert a new element before a given element.
371: * Header:
372: * void queue_insert_before(q, elt, cur, type, field)
373: * queue_t q;
374: * <type> elt;
375: * <type> cur;
376: * <type> is what's in our queue
377: * <field> is the chain field in (*<type>)
378: */
379: #define queue_insert_before(head, elt, cur, type, field) \
380: MACRO_BEGIN \
381: register queue_entry_t prev; \
382: \
383: if ((head) == (queue_entry_t)(cur)) { \
384: (elt)->field.next = (head); \
385: if ((head)->next == (head)) { /* only element */ \
386: (elt)->field.prev = (head); \
387: (head)->next = (queue_entry_t)(elt); \
388: } else { /* last element */ \
389: prev = (elt)->field.prev = (head)->prev; \
390: ((type)prev)->field.next = (queue_entry_t)(elt);\
391: } \
392: (head)->prev = (queue_entry_t)(elt); \
393: } else { \
394: (elt)->field.next = (queue_entry_t)(cur); \
395: if ((head)->next == (queue_entry_t)(cur)) { \
396: /* first element */ \
397: (elt)->field.prev = (head); \
398: (head)->next = (queue_entry_t)(elt); \
399: } else { /* middle element */ \
400: prev = (elt)->field.prev = (cur)->field.prev; \
401: ((type)prev)->field.next = (queue_entry_t)(elt);\
402: } \
403: (cur)->field.prev = (queue_entry_t)(elt); \
404: } \
405: MACRO_END
406:
407: /*
408: * Macro: queue_insert_after
409: * Function:
410: * Insert a new element after a given element.
411: * Header:
412: * void queue_insert_after(q, elt, cur, type, field)
413: * queue_t q;
414: * <type> elt;
415: * <type> cur;
416: * <type> is what's in our queue
417: * <field> is the chain field in (*<type>)
418: */
419: #define queue_insert_after(head, elt, cur, type, field) \
420: MACRO_BEGIN \
421: register queue_entry_t next; \
422: \
423: if ((head) == (queue_entry_t)(cur)) { \
424: (elt)->field.prev = (head); \
425: if ((head)->next == (head)) { /* only element */ \
426: (elt)->field.next = (head); \
427: (head)->prev = (queue_entry_t)(elt); \
428: } else { /* first element */ \
429: next = (elt)->field.next = (head)->next; \
430: ((type)next)->field.prev = (queue_entry_t)(elt);\
431: } \
432: (head)->next = (queue_entry_t)(elt); \
433: } else { \
434: (elt)->field.prev = (queue_entry_t)(cur); \
435: if ((head)->prev == (queue_entry_t)(cur)) { \
436: /* last element */ \
437: (elt)->field.next = (head); \
438: (head)->prev = (queue_entry_t)(elt); \
439: } else { /* middle element */ \
440: next = (elt)->field.next = (cur)->field.next; \
441: ((type)next)->field.prev = (queue_entry_t)(elt);\
442: } \
443: (cur)->field.next = (queue_entry_t)(elt); \
444: } \
445: MACRO_END
446:
447: /*
448: * Macro: queue_field [internal use only]
449: * Function:
450: * Find the queue_chain_t (or queue_t) for the
451: * given element (thing) in the given queue (head)
452: */
453: #define queue_field(head, thing, type, field) \
454: (((head) == (thing)) ? (head) : &((type)(thing))->field)
455:
456: /*
457: * Macro: queue_remove
458: * Function:
459: * Remove an arbitrary item from the queue.
460: * Header:
461: * void queue_remove(q, qe, type, field)
462: * arguments as in queue_enter
463: */
464: #define queue_remove(head, elt, type, field) \
465: MACRO_BEGIN \
466: register queue_entry_t next, prev; \
467: \
468: next = (elt)->field.next; \
469: prev = (elt)->field.prev; \
470: \
471: if ((head) == next) \
472: (head)->prev = prev; \
473: else \
474: ((type)next)->field.prev = prev; \
475: \
476: if ((head) == prev) \
477: (head)->next = next; \
478: else \
479: ((type)prev)->field.next = next; \
480: MACRO_END
481:
482: /*
483: * Macro: queue_remove_first
484: * Function:
485: * Remove and return the entry at the head of
486: * the queue.
487: * Header:
488: * queue_remove_first(head, entry, type, field)
489: * entry is returned by reference
490: */
491: #define queue_remove_first(head, entry, type, field) \
492: MACRO_BEGIN \
493: register queue_entry_t next; \
494: \
495: (entry) = (type) ((head)->next); \
496: next = (entry)->field.next; \
497: \
498: if ((head) == next) \
499: (head)->prev = (head); \
500: else \
501: ((type)(next))->field.prev = (head); \
502: (head)->next = next; \
503: MACRO_END
504:
505: /*
506: * Macro: queue_remove_last
507: * Function:
508: * Remove and return the entry at the tail of
509: * the queue.
510: * Header:
511: * queue_remove_last(head, entry, type, field)
512: * entry is returned by reference
513: */
514: #define queue_remove_last(head, entry, type, field) \
515: MACRO_BEGIN \
516: register queue_entry_t prev; \
517: \
518: (entry) = (type) ((head)->prev); \
519: prev = (entry)->field.prev; \
520: \
521: if ((head) == prev) \
522: (head)->next = (head); \
523: else \
524: ((type)(prev))->field.next = (head); \
525: (head)->prev = prev; \
526: MACRO_END
527:
528: /*
529: * Macro: queue_assign
530: */
531: #define queue_assign(to, from, type, field) \
532: MACRO_BEGIN \
533: ((type)((from)->prev))->field.next = (to); \
534: ((type)((from)->next))->field.prev = (to); \
535: *to = *from; \
536: MACRO_END
537:
538: /*
539: * Macro: queue_new_head
540: * Function:
541: * rebase old queue to new queue head
542: * Header:
543: * queue_new_head(old, new, type, field)
544: * queue_t old;
545: * queue_t new;
546: * <type> is what's in our queue
547: * <field> is the chain field in (*<type>)
548: */
549: #define queue_new_head(old, new, type, field) \
550: MACRO_BEGIN \
551: if (!queue_empty(new)) { \
552: *(new) = *(old); \
553: ((type)((new)->next))->field.prev = (new); \
554: ((type)((new)->prev))->field.next = (new); \
555: } else { \
556: queue_init(new); \
557: } \
558: MACRO_END
559:
560: /*
561: * Macro: queue_iterate
562: * Function:
563: * iterate over each item in the queue.
564: * Generates a 'for' loop, setting elt to
565: * each item in turn (by reference).
566: * Header:
567: * queue_iterate(q, elt, type, field)
568: * queue_t q;
569: * <type> elt;
570: * <type> is what's in our queue
571: * <field> is the chain field in (*<type>)
572: */
573: #define queue_iterate(head, elt, type, field) \
574: for ((elt) = (type) queue_first(head); \
575: !queue_end((head), (queue_entry_t)(elt)); \
576: (elt) = (type) queue_next(&(elt)->field))
577:
578:
579: #ifdef MACH_KERNEL_PRIVATE
580: /*----------------------------------------------------------------*/
581: /*
582: * Define macros for queues with locks.
583: */
584: struct mpqueue_head {
585: struct queue_entry head; /* header for queue */
586: decl_simple_lock_data(, lock) /* lock for queue */
587: };
588:
589: typedef struct mpqueue_head mpqueue_head_t;
590:
591: #define round_mpq(size) (size)
592:
593: #define mpqueue_init(q) \
594: MACRO_BEGIN \
595: queue_init(&(q)->head); \
596: simple_lock_init(&(q)->lock, ETAP_MISC_Q); \
597: MACRO_END
598:
599: #define mpenqueue_tail(q, elt) \
600: MACRO_BEGIN \
601: simple_lock(&(q)->lock); \
602: enqueue_tail(&(q)->head, elt); \
603: simple_unlock(&(q)->lock); \
604: MACRO_END
605:
606: #define mpdequeue_head(q, elt) \
607: MACRO_BEGIN \
608: simple_lock(&(q)->lock); \
609: if (queue_empty(&(q)->head)) \
610: *(elt) = 0; \
611: else \
612: *(elt) = dequeue_head(&(q)->head); \
613: simple_unlock(&(q)->lock); \
614: MACRO_END
615:
616: #endif /* MACH_KERNEL_PRIVATE */
617:
618: #endif /* _KERN_QUEUE_H_ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.