1 /*
2 * Copyright 1991-1998 by Open Software Foundation, Inc.
3 * All Rights Reserved
4 *
5 * Permission to use, copy, modify, and distribute this software and
6 * its documentation for any purpose and without fee is hereby granted,
7 * provided that the above copyright notice appears in all copies and
8 * that both the copyright notice and this permission notice appear in
9 * supporting documentation.
10 *
11 * OSF DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE
12 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
13 * FOR A PARTICULAR PURPOSE.
14 *
15 * IN NO EVENT SHALL OSF BE LIABLE FOR ANY SPECIAL, INDIRECT, OR
16 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
17 * LOSS OF USE, DATA OR PROFITS, WHETHER IN ACTION OF CONTRACT,
18 * NEGLIGENCE, OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
19 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 */
21 /*
22 * MkLinux
23 */
24 /* CMU_HIST */
25 /*
26 * Revision 2.4 91/05/14 16:45:55 mrt
27 * Correcting copyright
28 *
29 * Revision 2.3 91/02/05 17:28:43 mrt
30 * Changed to new Mach copyright
31 * [91/02/01 16:16:28 mrt]
32 *
33 * Revision 2.2 89/09/08 11:26:11 dbg
34 * Streamlined generic queue macros.
35 * [89/08/17 dbg]
36 *
37 * 19-Dec-88 David Golub (dbg) at Carnegie-Mellon University
38 * Added queue_remove_last; removed round_queue. [Changes from
39 * mwyoung: 19 Dec 88.]
40 *
41 * 29-Nov-88 David Golub (dbg) at Carnegie-Mellon University
42 * Removed include of cputypes.h. Added queue_iterate.
43 * Split into two groups the macros that operate directly on
44 * queues (or expect the queue chain to be first in a structure)
45 * and those that operate on generic structures (where the chain
46 * may be anywhere).
47 *
48 * 17-Jan-88 Daniel Julin (dpj) at Carnegie-Mellon University
49 * Added queue_enter_first, queue_last and queue_prev for use by
50 * the TCP netport code.
51 *
52 * 12-Jun-85 Avadis Tevanian (avie) at Carnegie-Mellon University
53 * Created.
54 *
55 */
56 /* CMU_ENDHIST */
57 /*
58 * Mach Operating System
59 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
60 * All Rights Reserved.
61 *
62 * Permission to use, copy, modify and distribute this software and its
63 * documentation is hereby granted, provided that both the copyright
64 * notice and this permission notice appear in all copies of the
65 * software, derivative works or modified versions, and any portions
66 * thereof, and that both notices appear in supporting documentation.
67 *
68 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
69 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
70 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
71 *
72 * Carnegie Mellon requests users of this software to return to
73 *
74 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
75 * School of Computer Science
76 * Carnegie Mellon University
77 * Pittsburgh PA 15213-3890
78 *
79 * any improvements or extensions that they make and grant Carnegie Mellon rights
80 * to redistribute these changes.
81 */
82 /*
83 */
84 /*
85 * File: queue.h
86 * Author: Avadis Tevanian, Jr.
87 * Date: 1985
88 *
89 * Type definitions for generic queues.
90 *
91 */
92
93 #ifndef _KERN_QUEUE_H_
94 #define _KERN_QUEUE_H_
95
96 #include <sys/mach/macro_help.h>
97
98 /*
99 * Queue of abstract objects. Queue is maintained
100 * within that object.
101 *
102 * Supports fast removal from within the queue.
103 *
104 * How to declare a queue of elements of type "foo_t":
105 * In the "*foo_t" type, you must have a field of
106 * type "queue_chain_t" to hold together this queue.
107 * There may be more than one chain through a
108 * "foo_t", for use by different queues.
109 *
110 * Declare the queue as a "queue_t" type.
111 *
112 * Elements of the queue (of type "foo_t", that is)
113 * are referred to by reference, and cast to type
114 * "queue_entry_t" within this module.
115 */
116
117 /*
118 * A generic doubly-linked list (queue).
119 */
120
121 struct queue_entry {
122 struct queue_entry *next; /* next element */
123 struct queue_entry *prev; /* previous element */
124 };
125
126 typedef struct queue_entry *queue_t;
127 typedef struct queue_entry queue_head_t;
128 typedef struct queue_entry queue_chain_t;
129 typedef struct queue_entry *queue_entry_t;
130
131 /*
132 * enqueue puts "elt" on the "queue".
133 * dequeue returns the first element in the "queue".
134 * remqueue removes the specified "elt" from the specified "queue".
135 */
136
137 #define enqueue(queue,elt) enqueue_tail(queue, elt)
138 #define dequeue(queue) dequeue_head(queue)
139
140 #if !defined(__GNUC__)
141
142 /* Enqueue element to head of queue */
143 extern void enqueue_head(
144 queue_t que,
145 queue_entry_t elt);
146
147 /* Enqueue element to tail of queue */
148 extern void enqueue_tail(
149 queue_t que,
150 queue_entry_t elt);
151
152 /* Dequeue element from head of queue */
153 extern queue_entry_t dequeue_head(
154 queue_t que);
155
156 /* Dequeue element from tail of queue */
157 extern queue_entry_t dequeue_tail(
158 queue_t que);
159
160 /* Dequeue element */
161 extern void remqueue(
162 queue_t que,
163 queue_entry_t elt);
164
165 /* Enqueue element after a particular elem */
166 extern void insque(
167 queue_entry_t entry,
168 queue_entry_t pred);
169
170 /* Dequeue element */
171 extern int remque(
172 queue_entry_t elt);
173
174 #else
175
176 static __inline__ void
enqueue_head(queue_t que,queue_entry_t elt)177 enqueue_head(
178 queue_t que,
179 queue_entry_t elt)
180 {
181 elt->next = que->next;
182 elt->prev = que;
183 elt->next->prev = elt;
184 que->next = elt;
185 }
186
187 static __inline__ void
enqueue_tail(queue_t que,queue_entry_t elt)188 enqueue_tail(
189 queue_t que,
190 queue_entry_t elt)
191 {
192 elt->next = que;
193 elt->prev = que->prev;
194 elt->prev->next = elt;
195 que->prev = elt;
196 }
197
198 static __inline__ queue_entry_t
dequeue_head(queue_t que)199 dequeue_head(
200 queue_t que)
201 {
202 register queue_entry_t elt = (queue_entry_t) 0;
203
204 if (que->next != que) {
205 elt = que->next;
206 elt->next->prev = que;
207 que->next = elt->next;
208 }
209
210 return (elt);
211 }
212
213 static __inline__ queue_entry_t
dequeue_tail(queue_t que)214 dequeue_tail(
215 queue_t que)
216 {
217 register queue_entry_t elt = (queue_entry_t) 0;
218
219 if (que->prev != que) {
220 elt = que->prev;
221 elt->prev->next = que;
222 que->prev = elt->prev;
223 }
224
225 return (elt);
226 }
227
228 static __inline__ void
remqueue(queue_t que __unused,queue_entry_t elt)229 remqueue(
230 queue_t que __unused,
231 queue_entry_t elt)
232 {
233 elt->next->prev = elt->prev;
234 elt->prev->next = elt->next;
235 }
236
237 static __inline__ void
insque(queue_entry_t entry,queue_entry_t pred)238 insque(
239 queue_entry_t entry,
240 queue_entry_t pred)
241 {
242 entry->next = pred->next;
243 entry->prev = pred;
244 (pred->next)->prev = entry;
245 pred->next = entry;
246 }
247
248 static __inline__ uintptr_t
remque(register queue_entry_t elt)249 remque(
250 register queue_entry_t elt)
251 {
252 (elt->next)->prev = elt->prev;
253 (elt->prev)->next = elt->next;
254
255 return((uintptr_t)elt);
256 }
257
258 #endif /* defined(__GNUC__) */
259
260 /*
261 * Macro: queue_init
262 * Function:
263 * Initialize the given queue.
264 * Header:
265 * void queue_init(q)
266 * queue_t q; \* MODIFIED *\
267 */
268 #define queue_init(q) \
269 MACRO_BEGIN \
270 (q)->next = (q);\
271 (q)->prev = (q);\
272 MACRO_END
273
274 /*
275 * Macro: queue_first
276 * Function:
277 * Returns the first entry in the queue,
278 * Header:
279 * queue_entry_t queue_first(q)
280 * queue_t q; \* IN *\
281 */
282 #define queue_first(q) ((q)->next)
283
284 /*
285 * Macro: queue_next
286 * Function:
287 * Returns the entry after an item in the queue.
288 * Header:
289 * queue_entry_t queue_next(qc)
290 * queue_t qc;
291 */
292 #define queue_next(qc) ((qc)->next)
293
294 /*
295 * Macro: queue_last
296 * Function:
297 * Returns the last entry in the queue.
298 * Header:
299 * queue_entry_t queue_last(q)
300 * queue_t q; \* IN *\
301 */
302 #define queue_last(q) ((q)->prev)
303
304 /*
305 * Macro: queue_prev
306 * Function:
307 * Returns the entry before an item in the queue.
308 * Header:
309 * queue_entry_t queue_prev(qc)
310 * queue_t qc;
311 */
312 #define queue_prev(qc) ((qc)->prev)
313
314 /*
315 * Macro: queue_end
316 * Function:
317 * Tests whether a new entry is really the end of
318 * the queue.
319 * Header:
320 * boolean_t queue_end(q, qe)
321 * queue_t q;
322 * queue_entry_t qe;
323 */
324 #define queue_end(q, qe) ((q) == (qe))
325
326 /*
327 * Macro: queue_empty
328 * Function:
329 * Tests whether a queue is empty.
330 * Header:
331 * boolean_t queue_empty(q)
332 * queue_t q;
333 */
334 #define queue_empty(q) queue_end((q), queue_first(q))
335
336
337 /*----------------------------------------------------------------*/
338 /*
339 * Macros that operate on generic structures. The queue
340 * chain may be at any location within the structure, and there
341 * may be more than one chain.
342 */
343
344 /*
345 * Macro: queue_enter
346 * Function:
347 * Insert a new element at the tail of the queue.
348 * Header:
349 * void queue_enter(q, elt, type, field)
350 * queue_t q;
351 * <type> elt;
352 * <type> is what's in our queue
353 * <field> is the chain field in (*<type>)
354 */
355 #define queue_enter(head, elt, type, field) \
356 MACRO_BEGIN \
357 register queue_entry_t prev; \
358 \
359 prev = (head)->prev; \
360 if ((head) == prev) { \
361 (head)->next = (queue_entry_t) (elt); \
362 } \
363 else { \
364 ((type)prev)->field.next = (queue_entry_t)(elt);\
365 } \
366 (elt)->field.prev = prev; \
367 (elt)->field.next = head; \
368 (head)->prev = (queue_entry_t) elt; \
369 MACRO_END
370
371 /*
372 * Macro: queue_enter_first
373 * Function:
374 * Insert a new element at the head of the queue.
375 * Header:
376 * void queue_enter_first(q, elt, type, field)
377 * queue_t q;
378 * <type> elt;
379 * <type> is what's in our queue
380 * <field> is the chain field in (*<type>)
381 */
382 #define queue_enter_first(head, elt, type, field) \
383 MACRO_BEGIN \
384 register queue_entry_t next; \
385 \
386 next = (head)->next; \
387 if ((head) == next) { \
388 (head)->prev = (queue_entry_t) (elt); \
389 } \
390 else { \
391 ((type)next)->field.prev = (queue_entry_t)(elt);\
392 } \
393 (elt)->field.next = next; \
394 (elt)->field.prev = head; \
395 (head)->next = (queue_entry_t) elt; \
396 MACRO_END
397
398 /*
399 * Macro: queue_insert_before
400 * Function:
401 * Insert a new element before a given element.
402 * Header:
403 * void queue_insert_before(q, elt, cur, type, field)
404 * queue_t q;
405 * <type> elt;
406 * <type> cur;
407 * <type> is what's in our queue
408 * <field> is the chain field in (*<type>)
409 */
410 #define queue_insert_before(head, elt, cur, type, field) \
411 MACRO_BEGIN \
412 register queue_entry_t prev; \
413 \
414 if ((head) == (queue_entry_t)(cur)) { \
415 (elt)->field.next = (head); \
416 if ((head)->next == (head)) { /* only element */ \
417 (elt)->field.prev = (head); \
418 (head)->next = (queue_entry_t)(elt); \
419 } else { /* last element */ \
420 prev = (elt)->field.prev = (head)->prev; \
421 ((type)prev)->field.next = (queue_entry_t)(elt);\
422 } \
423 (head)->prev = (queue_entry_t)(elt); \
424 } else { \
425 (elt)->field.next = (queue_entry_t)(cur); \
426 if ((head)->next == (queue_entry_t)(cur)) { \
427 /* first element */ \
428 (elt)->field.prev = (head); \
429 (head)->next = (queue_entry_t)(elt); \
430 } else { /* middle element */ \
431 prev = (elt)->field.prev = (cur)->field.prev; \
432 ((type)prev)->field.next = (queue_entry_t)(elt);\
433 } \
434 (cur)->field.prev = (queue_entry_t)(elt); \
435 } \
436 MACRO_END
437
438 /*
439 * Macro: queue_insert_after
440 * Function:
441 * Insert a new element after a given element.
442 * Header:
443 * void queue_insert_after(q, elt, cur, type, field)
444 * queue_t q;
445 * <type> elt;
446 * <type> cur;
447 * <type> is what's in our queue
448 * <field> is the chain field in (*<type>)
449 */
450 #define queue_insert_after(head, elt, cur, type, field) \
451 MACRO_BEGIN \
452 register queue_entry_t next; \
453 \
454 if ((head) == (queue_entry_t)(cur)) { \
455 (elt)->field.prev = (head); \
456 if ((head)->next == (head)) { /* only element */ \
457 (elt)->field.next = (head); \
458 (head)->prev = (queue_entry_t)(elt); \
459 } else { /* first element */ \
460 next = (elt)->field.next = (head)->next; \
461 ((type)next)->field.prev = (queue_entry_t)(elt);\
462 } \
463 (head)->next = (queue_entry_t)(elt); \
464 } else { \
465 (elt)->field.prev = (queue_entry_t)(cur); \
466 if ((head)->prev == (queue_entry_t)(cur)) { \
467 /* last element */ \
468 (elt)->field.next = (head); \
469 (head)->prev = (queue_entry_t)(elt); \
470 } else { /* middle element */ \
471 next = (elt)->field.next = (cur)->field.next; \
472 ((type)next)->field.prev = (queue_entry_t)(elt);\
473 } \
474 (cur)->field.next = (queue_entry_t)(elt); \
475 } \
476 MACRO_END
477
478 /*
479 * Macro: queue_field [internal use only]
480 * Function:
481 * Find the queue_chain_t (or queue_t) for the
482 * given element (thing) in the given queue (head)
483 */
484 #define queue_field(head, thing, type, field) \
485 (((head) == (thing)) ? (head) : &((type)(thing))->field)
486
487 /*
488 * Macro: queue_remove
489 * Function:
490 * Remove an arbitrary item from the queue.
491 * Header:
492 * void queue_remove(q, qe, type, field)
493 * arguments as in queue_enter
494 */
495 #define queue_remove(head, elt, type, field) \
496 MACRO_BEGIN \
497 register queue_entry_t next, prev; \
498 \
499 next = (elt)->field.next; \
500 prev = (elt)->field.prev; \
501 \
502 if ((head) == next) \
503 (head)->prev = prev; \
504 else \
505 ((type)next)->field.prev = prev; \
506 \
507 if ((head) == prev) \
508 (head)->next = next; \
509 else \
510 ((type)prev)->field.next = next; \
511 MACRO_END
512
513 /*
514 * Macro: queue_remove_first
515 * Function:
516 * Remove and return the entry at the head of
517 * the queue.
518 * Header:
519 * queue_remove_first(head, entry, type, field)
520 * entry is returned by reference
521 */
522 #define queue_remove_first(head, entry, type, field) \
523 MACRO_BEGIN \
524 register queue_entry_t next; \
525 \
526 (entry) = (type) ((head)->next); \
527 next = (entry)->field.next; \
528 \
529 if ((head) == next) \
530 (head)->prev = (head); \
531 else \
532 ((type)(next))->field.prev = (head); \
533 (head)->next = next; \
534 MACRO_END
535
536 /*
537 * Macro: queue_remove_last
538 * Function:
539 * Remove and return the entry at the tail of
540 * the queue.
541 * Header:
542 * queue_remove_last(head, entry, type, field)
543 * entry is returned by reference
544 */
545 #define queue_remove_last(head, entry, type, field) \
546 MACRO_BEGIN \
547 register queue_entry_t prev; \
548 \
549 (entry) = (type) ((head)->prev); \
550 prev = (entry)->field.prev; \
551 \
552 if ((head) == prev) \
553 (head)->next = (head); \
554 else \
555 ((type)(prev))->field.next = (head); \
556 (head)->prev = prev; \
557 MACRO_END
558
559 /*
560 * Macro: queue_assign
561 */
562 #define queue_assign(to, from, type, field) \
563 MACRO_BEGIN \
564 ((type)((from)->prev))->field.next = (to); \
565 ((type)((from)->next))->field.prev = (to); \
566 *to = *from; \
567 MACRO_END
568
569 /*
570 * Macro: queue_new_head
571 * Function:
572 * rebase old queue to new queue head
573 * Header:
574 * queue_new_head(old, new, type, field)
575 * queue_t old;
576 * queue_t new;
577 * <type> is what's in our queue
578 * <field> is the chain field in (*<type>)
579 */
580 #define queue_new_head(old, new, type, field) \
581 MACRO_BEGIN \
582 if (!queue_empty(new)) { \
583 *(new) = *(old); \
584 ((type)((new)->next))->field.prev = (new); \
585 ((type)((new)->prev))->field.next = (new); \
586 } else { \
587 queue_init(new); \
588 } \
589 MACRO_END
590
591 /*
592 * Macro: queue_iterate
593 * Function:
594 * iterate over each item in the queue.
595 * Generates a 'for' loop, setting elt to
596 * each item in turn (by reference).
597 * Header:
598 * queue_iterate(q, elt, type, field)
599 * queue_t q;
600 * <type> elt;
601 * <type> is what's in our queue
602 * <field> is the chain field in (*<type>)
603 */
604 #define queue_iterate(head, elt, type, field) \
605 for ((elt) = (type) queue_first(head); \
606 !queue_end((head), (queue_entry_t)(elt)); \
607 (elt) = (type) queue_next(&(elt)->field))
608
609
610
611 /*----------------------------------------------------------------*/
612 /*
613 * Define macros for queues with locks.
614 */
615 struct mpqueue_head {
616 struct queue_entry head; /* header for queue */
617 decl_simple_lock_data(, lock) /* lock for queue */
618 };
619
620 typedef struct mpqueue_head mpqueue_head_t;
621
622 #define round_mpq(size) (size)
623
624 #define mpqueue_init(q) \
625 MACRO_BEGIN \
626 queue_init(&(q)->head); \
627 simple_lock_init(&(q)->lock, ETAP_MISC_Q); \
628 MACRO_END
629
630 #define mpenqueue_tail(q, elt) \
631 MACRO_BEGIN \
632 simple_lock(&(q)->lock); \
633 enqueue_tail(&(q)->head, elt); \
634 simple_unlock(&(q)->lock); \
635 MACRO_END
636
637 #define mpdequeue_head(q, elt) \
638 MACRO_BEGIN \
639 simple_lock(&(q)->lock); \
640 if (queue_empty(&(q)->head)) \
641 *(elt) = 0; \
642 else \
643 *(elt) = dequeue_head(&(q)->head); \
644 simple_unlock(&(q)->lock); \
645 MACRO_END
646
647 #endif /* _KERN_QUEUE_H_ */
648