]> git.saurik.com Git - apple/xnu.git/blob - osfmk/kern/queue.h
xnu-4570.20.62.tar.gz
[apple/xnu.git] / osfmk / kern / queue.h
1 /*
2 * Copyright (c) 2000-2009 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28 /*
29 * @OSF_COPYRIGHT@
30 */
31 /*
32 * Mach Operating System
33 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
34 * All Rights Reserved.
35 *
36 * Permission to use, copy, modify and distribute this software and its
37 * documentation is hereby granted, provided that both the copyright
38 * notice and this permission notice appear in all copies of the
39 * software, derivative works or modified versions, and any portions
40 * thereof, and that both notices appear in supporting documentation.
41 *
42 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
43 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
44 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
45 *
46 * Carnegie Mellon requests users of this software to return to
47 *
48 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
49 * School of Computer Science
50 * Carnegie Mellon University
51 * Pittsburgh PA 15213-3890
52 *
53 * any improvements or extensions that they make and grant Carnegie Mellon rights
54 * to redistribute these changes.
55 */
56 /*
57 */
58 /*
59 * File: queue.h
60 * Author: Avadis Tevanian, Jr.
61 * Date: 1985
62 *
63 * Type definitions for generic queues.
64 *
65 */
66
67 #ifndef _KERN_QUEUE_H_
68 #define _KERN_QUEUE_H_
69
70 #include <mach/mach_types.h>
71 #include <kern/macro_help.h>
72
73 #include <sys/cdefs.h>
74
75 __BEGIN_DECLS
76
77 /*
78 * Queue Management APIs
79 *
80 * There are currently two subtly different methods of maintining
81 * a queue of objects. Both APIs are contained in this file, and
82 * unfortunately overlap.
83 * (there is also a third way maintained in bsd/sys/queue.h)
84 *
85 * Both methods use a common queue head and linkage pattern:
86 * The head of a queue is declared as:
87 * queue_head_t q_head;
88 *
89 * Elements in this queue are chained together using
90 * struct queue_entry objects embedded within a structure:
91 * struct some_data {
92 * int field1;
93 * int field2;
94 * ...
95 * queue_chain_t link;
96 * ...
97 * int last_field;
98 * };
99 * struct some_data is referred to as the queue "element."
100 * (note that queue_chain_t is typedef'd to struct queue_entry)
101 *
102 * IMPORTANT: The two queue iteration methods described below are not
103 * compatible with one another. You must choose one and be careful
104 * to use only the supported APIs for that method.
105 *
106 * Method 1: chaining of queue_chain_t (linkage chains)
107 * This method uses the next and prev pointers of the struct queue_entry
108 * linkage object embedded in a queue element to point to the next or
109 * previous queue_entry structure in the chain. The head of the queue
110 * (the queue_head_t object) will point to the first and last
111 * struct queue_entry object, and both the next and prev pointer will
112 * point back to the head if the queue is empty.
113 *
114 * This method is the most flexible method of chaining objects together
115 * as it allows multiple chains through a given object, by embedding
116 * multiple queue_chain_t objects in the structure, while simultaneously
117 * providing fast removal and insertion into the queue using only
118 * struct queue_entry object pointers.
119 *
120 * ++ Valid APIs for this style queue ++
121 * -------------------------------------
122 * [C] queue_init
123 * [C] queue_first
124 * [C] queue_next
125 * [C] queue_last
126 * [C] queue_prev
127 * [C] queue_end
128 * [C] queue_empty
129 *
130 * [1] enqueue
131 * [1] dequeue
132 * [1] enqueue_head
133 * [1] enqueue_tail
134 * [1] dequeue_head
135 * [1] dequeue_tail
136 * [1] remqueue
137 * [1] insque
138 * [1] remque
139 * [1] re_queue_head
140 * [1] re_queue_tail
141 * [1] movqueue
142 * [1] qe_element
143 * [1] qe_foreach
144 * [1] qe_foreach_safe
145 * [1] qe_foreach_element
146 * [1] qe_foreach_element_safe
147 *
148 * Method 2: chaining of elements (element chains)
149 * This method uses the next and prev pointers of the struct queue_entry
150 * linkage object embedded in a queue element to point to the next or
151 * previous queue element (not another queue_entry). The head of the
152 * queue will point to the first and last queue element (struct some_data
153 * from the above example) NOT the embedded queue_entry structure. The
154 * first queue element will have a prev pointer that points to the
155 * queue_head_t, and the last queue element will have a next pointer
156 * that points to the queue_head_t.
157 *
158 * This method requires knowledge of the queue_head_t of the queue on
159 * which an element resides in order to remove the element. Iterating
160 * through the elements of the queue is also more cumbersome because
161 * a check against the head pointer plus a cast then offset operation
162 * must be performed at each step of the iteration.
163 *
164 * ++ Valid APIs for this style queue ++
165 * -------------------------------------
166 * [C] queue_init
167 * [C] queue_first
168 * [C] queue_next
169 * [C] queue_last
170 * [C] queue_prev
171 * [C] queue_end
172 * [C] queue_empty
173 *
174 * [2] queue_enter
175 * [2] queue_enter_first
176 * [2] queue_insert_before
177 * [2] queue_insert_after
178 * [2] queue_field
179 * [2] queue_remove
180 * [2] queue_remove_first
181 * [2] queue_remove_last
182 * [2] queue_assign
183 * [2] queue_new_head
184 * [2] queue_iterate
185 *
186 * Legend:
187 * [C] -> API common to both methods
188 * [1] -> API used only in method 1 (linkage chains)
189 * [2] -> API used only in method 2 (element chains)
190 */
191
192 /*
193 * A generic doubly-linked list (queue).
194 */
195
196 struct queue_entry {
197 struct queue_entry *next; /* next element */
198 struct queue_entry *prev; /* previous element */
199
200 #if __arm__ && (__BIGGEST_ALIGNMENT__ > 4)
201 /* For the newer ARMv7k ABI where 64-bit types are 64-bit aligned, but pointers
202 * are 32-bit:
203 * Since this type is so often cast to various 64-bit aligned types
204 * aligning it to 64-bits will avoid -wcast-align without needing
205 * to disable it entirely. The impact on memory footprint should be
206 * negligible.
207 */
208 } __attribute__ ((aligned (8)));
209 #else
210 };
211 #endif
212
213 typedef struct queue_entry *queue_t;
214 typedef struct queue_entry queue_head_t;
215 typedef struct queue_entry queue_chain_t;
216 typedef struct queue_entry *queue_entry_t;
217
218 /*
219 * enqueue puts "elt" on the "queue".
220 * dequeue returns the first element in the "queue".
221 * remqueue removes the specified "elt" from its queue.
222 */
223
224 #define enqueue(queue,elt) enqueue_tail(queue, elt)
225 #define dequeue(queue) dequeue_head(queue)
226
227 #ifdef XNU_KERNEL_PRIVATE
228 #include <kern/debug.h>
229 #include <mach/branch_predicates.h>
230 static inline void __QUEUE_ELT_VALIDATE(queue_entry_t elt) {
231 queue_entry_t elt_next, elt_prev;
232
233 if (__improbable(elt == (queue_entry_t)0)) {
234 panic("Invalid queue element %p", elt);
235 }
236
237 elt_next = elt->next;
238 elt_prev = elt->prev;
239
240 if (__improbable(elt_next == (queue_entry_t)0 || elt_prev == (queue_entry_t)0)) {
241 panic("Invalid queue element pointers for %p: next %p prev %p", elt, elt_next, elt_prev);
242 }
243 if (__improbable(elt_next->prev != elt || elt_prev->next != elt)) {
244 panic("Invalid queue element linkage for %p: next %p next->prev %p prev %p prev->next %p",
245 elt, elt_next, elt_next->prev, elt_prev, elt_prev->next);
246 }
247 }
248
249 static inline void __DEQUEUE_ELT_CLEANUP(queue_entry_t elt) {
250 (elt)->next = (queue_entry_t) 0;
251 (elt)->prev = (queue_entry_t) 0;
252 }
253 #else
254 #define __QUEUE_ELT_VALIDATE(elt) do { } while (0)
255 #define __DEQUEUE_ELT_CLEANUP(elt) do { } while(0)
256 #endif /* !XNU_KERNEL_PRIVATE */
257
258 static __inline__ void
259 enqueue_head(
260 queue_t que,
261 queue_entry_t elt)
262 {
263 queue_entry_t old_head;
264
265 __QUEUE_ELT_VALIDATE((queue_entry_t)que);
266 old_head = que->next;
267 elt->next = old_head;
268 elt->prev = que;
269 old_head->prev = elt;
270 que->next = elt;
271 }
272
273 static __inline__ void
274 enqueue_tail(
275 queue_t que,
276 queue_entry_t elt)
277 {
278 queue_entry_t old_tail;
279
280 __QUEUE_ELT_VALIDATE((queue_entry_t)que);
281 old_tail = que->prev;
282 elt->next = que;
283 elt->prev = old_tail;
284 old_tail->next = elt;
285 que->prev = elt;
286 }
287
288 static __inline__ queue_entry_t
289 dequeue_head(
290 queue_t que)
291 {
292 queue_entry_t elt = (queue_entry_t) 0;
293 queue_entry_t new_head;
294
295 if (que->next != que) {
296 elt = que->next;
297 __QUEUE_ELT_VALIDATE(elt);
298 new_head = elt->next; /* new_head may point to que if elt was the only element */
299 new_head->prev = que;
300 que->next = new_head;
301 __DEQUEUE_ELT_CLEANUP(elt);
302 }
303
304 return (elt);
305 }
306
307 static __inline__ queue_entry_t
308 dequeue_tail(
309 queue_t que)
310 {
311 queue_entry_t elt = (queue_entry_t) 0;
312 queue_entry_t new_tail;
313
314 if (que->prev != que) {
315 elt = que->prev;
316 __QUEUE_ELT_VALIDATE(elt);
317 new_tail = elt->prev; /* new_tail may point to queue if elt was the only element */
318 new_tail->next = que;
319 que->prev = new_tail;
320 __DEQUEUE_ELT_CLEANUP(elt);
321 }
322
323 return (elt);
324 }
325
326 static __inline__ void
327 remqueue(
328 queue_entry_t elt)
329 {
330 queue_entry_t next_elt, prev_elt;
331
332 __QUEUE_ELT_VALIDATE(elt);
333 next_elt = elt->next;
334 prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
335 next_elt->prev = prev_elt;
336 prev_elt->next = next_elt;
337 __DEQUEUE_ELT_CLEANUP(elt);
338 }
339
340 static __inline__ void
341 insque(
342 queue_entry_t entry,
343 queue_entry_t pred)
344 {
345 queue_entry_t successor;
346
347 __QUEUE_ELT_VALIDATE(pred);
348 successor = pred->next;
349 entry->next = successor;
350 entry->prev = pred;
351 successor->prev = entry;
352 pred->next = entry;
353 }
354
355 static __inline__ void
356 remque(
357 queue_entry_t elt)
358 {
359 queue_entry_t next_elt, prev_elt;
360
361 __QUEUE_ELT_VALIDATE(elt);
362 next_elt = elt->next;
363 prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
364 next_elt->prev = prev_elt;
365 prev_elt->next = next_elt;
366 __DEQUEUE_ELT_CLEANUP(elt);
367 }
368
369 /*
370 * Function: re_queue_head
371 * Parameters:
372 * queue_t que : queue onto which elt will be pre-pended
373 * queue_entry_t elt : element to re-queue
374 * Description:
375 * Remove elt from its current queue and put it onto the
376 * head of a new queue
377 * Note:
378 * This should only be used with Method 1 queue iteration (linkage chains)
379 */
380 static __inline__ void
381 re_queue_head(queue_t que, queue_entry_t elt)
382 {
383 queue_entry_t n_elt, p_elt;
384
385 __QUEUE_ELT_VALIDATE(elt);
386 __QUEUE_ELT_VALIDATE((queue_entry_t)que);
387
388 /* remqueue */
389 n_elt = elt->next;
390 p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
391 n_elt->prev = p_elt;
392 p_elt->next = n_elt;
393
394 /* enqueue_head */
395 n_elt = que->next;
396 elt->next = n_elt;
397 elt->prev = que;
398 n_elt->prev = elt;
399 que->next = elt;
400 }
401
402 /*
403 * Function: re_queue_tail
404 * Parameters:
405 * queue_t que : queue onto which elt will be appended
406 * queue_entry_t elt : element to re-queue
407 * Description:
408 * Remove elt from its current queue and put it onto the
409 * end of a new queue
410 * Note:
411 * This should only be used with Method 1 queue iteration (linkage chains)
412 */
413 static __inline__ void
414 re_queue_tail(queue_t que, queue_entry_t elt)
415 {
416 queue_entry_t n_elt, p_elt;
417
418 __QUEUE_ELT_VALIDATE(elt);
419 __QUEUE_ELT_VALIDATE((queue_entry_t)que);
420
421 /* remqueue */
422 n_elt = elt->next;
423 p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
424 n_elt->prev = p_elt;
425 p_elt->next = n_elt;
426
427 /* enqueue_tail */
428 p_elt = que->prev;
429 elt->next = que;
430 elt->prev = p_elt;
431 p_elt->next = elt;
432 que->prev = elt;
433 }
434
435 /*
436 * Macro: qe_element
437 * Function:
438 * Convert a queue_entry_t to a queue element pointer.
439 * Get a pointer to the user-defined element containing
440 * a given queue_entry_t
441 * Header:
442 * <type> * qe_element(queue_entry_t qe, <type>, field)
443 * qe - queue entry to convert
444 * <type> - what's in the queue (e.g., struct some_data)
445 * <field> - is the chain field in <type>
446 * Note:
447 * Do not use pointer types for <type>
448 */
449 #define qe_element(qe, type, field) \
450 ((type *)((void *)((char *)(qe) - __offsetof(type, field))))
451
452 /*
453 * Macro: qe_foreach
454 * Function:
455 * Iterate over each queue_entry_t structure.
456 * Generates a 'for' loop, setting 'qe' to
457 * each queue_entry_t in the queue.
458 * Header:
459 * qe_foreach(queue_entry_t qe, queue_t head)
460 * qe - iteration variable
461 * head - pointer to queue_head_t (head of queue)
462 * Note:
463 * This should only be used with Method 1 queue iteration (linkage chains)
464 */
465 #define qe_foreach(qe, head) \
466 for (qe = (head)->next; qe != (head); qe = (qe)->next)
467
468 /*
469 * Macro: qe_foreach_safe
470 * Function:
471 * Safely iterate over each queue_entry_t structure.
472 *
473 * Use this iterator macro if you plan to remove the
474 * queue_entry_t, qe, from the queue during the
475 * iteration.
476 * Header:
477 * qe_foreach_safe(queue_entry_t qe, queue_t head)
478 * qe - iteration variable
479 * head - pointer to queue_head_t (head of queue)
480 * Note:
481 * This should only be used with Method 1 queue iteration (linkage chains)
482 */
483 #define qe_foreach_safe(qe, head) \
484 for (queue_entry_t _ne = ((head)->next)->next, \
485 __ ## qe ## _unused_shadow __unused = (qe = (head)->next); \
486 qe != (head); \
487 qe = _ne, _ne = (qe)->next)
488
489 /*
490 * Macro: qe_foreach_element
491 * Function:
492 * Iterate over each _element_ in a queue
493 * where each queue_entry_t points to another
494 * queue_entry_t, i.e., managed by the [de|en]queue_head/
495 * [de|en]queue_tail / remqueue / etc. function.
496 * Header:
497 * qe_foreach_element(<type> *elt, queue_t head, <field>)
498 * elt - iteration variable
499 * <type> - what's in the queue (e.g., struct some_data)
500 * <field> - is the chain field in <type>
501 * Note:
502 * This should only be used with Method 1 queue iteration (linkage chains)
503 */
504 #define qe_foreach_element(elt, head, field) \
505 for (elt = qe_element((head)->next, typeof(*(elt)), field); \
506 &((elt)->field) != (head); \
507 elt = qe_element((elt)->field.next, typeof(*(elt)), field))
508
509 /*
510 * Macro: qe_foreach_element_safe
511 * Function:
512 * Safely iterate over each _element_ in a queue
513 * where each queue_entry_t points to another
514 * queue_entry_t, i.e., managed by the [de|en]queue_head/
515 * [de|en]queue_tail / remqueue / etc. function.
516 *
517 * Use this iterator macro if you plan to remove the
518 * element, elt, from the queue during the iteration.
519 * Header:
520 * qe_foreach_element_safe(<type> *elt, queue_t head, <field>)
521 * elt - iteration variable
522 * <type> - what's in the queue (e.g., struct some_data)
523 * <field> - is the chain field in <type>
524 * Note:
525 * This should only be used with Method 1 queue iteration (linkage chains)
526 */
527 #define qe_foreach_element_safe(elt, head, field) \
528 for (typeof(*(elt)) *_nelt = qe_element(((head)->next)->next, typeof(*(elt)), field), \
529 *__ ## elt ## _unused_shadow __unused = \
530 (elt = qe_element((head)->next, typeof(*(elt)), field)); \
531 &((elt)->field) != (head); \
532 elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \
533
534 #ifdef XNU_KERNEL_PRIVATE
535
536 /* Dequeue an element from head, or return NULL if the queue is empty */
537 #define qe_dequeue_head(head, type, field) ({ \
538 queue_entry_t _tmp_entry = dequeue_head((head)); \
539 type *_tmp_element = (type*) NULL; \
540 if (_tmp_entry != (queue_entry_t) NULL) \
541 _tmp_element = qe_element(_tmp_entry, type, field); \
542 _tmp_element; \
543 })
544
545 /* Dequeue an element from tail, or return NULL if the queue is empty */
546 #define qe_dequeue_tail(head, type, field) ({ \
547 queue_entry_t _tmp_entry = dequeue_tail((head)); \
548 type *_tmp_element = (type*) NULL; \
549 if (_tmp_entry != (queue_entry_t) NULL) \
550 _tmp_element = qe_element(_tmp_entry, type, field); \
551 _tmp_element; \
552 })
553
554 /* Peek at the first element, or return NULL if the queue is empty */
555 #define qe_queue_first(head, type, field) ({ \
556 queue_entry_t _tmp_entry = queue_first((head)); \
557 type *_tmp_element = (type*) NULL; \
558 if (_tmp_entry != (queue_entry_t) head) \
559 _tmp_element = qe_element(_tmp_entry, type, field); \
560 _tmp_element; \
561 })
562
563 /* Peek at the last element, or return NULL if the queue is empty */
564 #define qe_queue_last(head, type, field) ({ \
565 queue_entry_t _tmp_entry = queue_last((head)); \
566 type *_tmp_element = (type*) NULL; \
567 if (_tmp_entry != (queue_entry_t) head) \
568 _tmp_element = qe_element(_tmp_entry, type, field); \
569 _tmp_element; \
570 })
571
572 #endif /* XNU_KERNEL_PRIVATE */
573
574 /*
575 * Macro: queue_init
576 * Function:
577 * Initialize the given queue.
578 * Header:
579 * void queue_init(q)
580 * queue_t q; \* MODIFIED *\
581 */
582 #define queue_init(q) \
583 MACRO_BEGIN \
584 (q)->next = (q);\
585 (q)->prev = (q);\
586 MACRO_END
587
588 /*
589 * Macro: queue_head_init
590 * Function:
591 * Initialize the given queue head
592 * Header:
593 * void queue_head_init(q)
594 * queue_head_t q; \* MODIFIED *\
595 */
596 #define queue_head_init(q) \
597 queue_init(&(q))
598
599 /*
600 * Macro: queue_chain_init
601 * Function:
602 * Initialize the given queue chain element
603 * Header:
604 * void queue_chain_init(q)
605 * queue_chain_t q; \* MODIFIED *\
606 */
607 #define queue_chain_init(q) \
608 queue_init(&(q))
609
610 /*
611 * Macro: queue_first
612 * Function:
613 * Returns the first entry in the queue,
614 * Header:
615 * queue_entry_t queue_first(q)
616 * queue_t q; \* IN *\
617 */
618 #define queue_first(q) ((q)->next)
619
620 /*
621 * Macro: queue_next
622 * Function:
623 * Returns the entry after an item in the queue.
624 * Header:
625 * queue_entry_t queue_next(qc)
626 * queue_t qc;
627 */
628 #define queue_next(qc) ((qc)->next)
629
630 /*
631 * Macro: queue_last
632 * Function:
633 * Returns the last entry in the queue.
634 * Header:
635 * queue_entry_t queue_last(q)
636 * queue_t q; \* IN *\
637 */
638 #define queue_last(q) ((q)->prev)
639
640 /*
641 * Macro: queue_prev
642 * Function:
643 * Returns the entry before an item in the queue.
644 * Header:
645 * queue_entry_t queue_prev(qc)
646 * queue_t qc;
647 */
648 #define queue_prev(qc) ((qc)->prev)
649
650 /*
651 * Macro: queue_end
652 * Function:
653 * Tests whether a new entry is really the end of
654 * the queue.
655 * Header:
656 * boolean_t queue_end(q, qe)
657 * queue_t q;
658 * queue_entry_t qe;
659 */
660 #define queue_end(q, qe) ((q) == (qe))
661
662 /*
663 * Macro: queue_empty
664 * Function:
665 * Tests whether a queue is empty.
666 * Header:
667 * boolean_t queue_empty(q)
668 * queue_t q;
669 */
670 #define queue_empty(q) queue_end((q), queue_first(q))
671
672 /*
673 * Function: movqueue
674 * Parameters:
675 * queue_t _old : head of a queue whose items will be moved
676 * queue_t _new : new queue head onto which items will be moved
677 * Description:
678 * Rebase queue items in _old onto _new then re-initialize
679 * the _old object to an empty queue.
680 * Equivalent to the queue_new_head Method 2 macro
681 * Note:
682 * Similar to the queue_new_head macro, this macros is intented
683 * to function as an initializer method for '_new' and thus may
684 * leak any list items that happen to be on the '_new' list.
685 * This should only be used with Method 1 queue iteration (linkage chains)
686 */
687 static __inline__ void
688 movqueue(queue_t _old, queue_t _new)
689 {
690 queue_entry_t next_elt, prev_elt;
691
692 __QUEUE_ELT_VALIDATE((queue_entry_t)_old);
693
694 if (queue_empty(_old)) {
695 queue_init(_new);
696 return;
697 }
698
699 /*
700 * move the queue at _old to _new
701 * and re-initialize _old
702 */
703 next_elt = _old->next;
704 prev_elt = _old->prev;
705
706 _new->next = next_elt;
707 _new->prev = prev_elt;
708 next_elt->prev = _new;
709 prev_elt->next = _new;
710
711 queue_init(_old);
712 }
713
714 /*----------------------------------------------------------------*/
715 /*
716 * Macros that operate on generic structures. The queue
717 * chain may be at any location within the structure, and there
718 * may be more than one chain.
719 */
720
721 /*
722 * Macro: queue_enter
723 * Function:
724 * Insert a new element at the tail of the queue.
725 * Header:
726 * void queue_enter(q, elt, type, field)
727 * queue_t q;
728 * <type> elt;
729 * <type> is what's in our queue
730 * <field> is the chain field in (*<type>)
731 * Note:
732 * This should only be used with Method 2 queue iteration (element chains)
733 */
734 #define queue_enter(head, elt, type, field) \
735 MACRO_BEGIN \
736 queue_entry_t __prev; \
737 \
738 __prev = (head)->prev; \
739 if ((head) == __prev) { \
740 (head)->next = (queue_entry_t) (elt); \
741 } \
742 else { \
743 ((type)(void *)__prev)->field.next = \
744 (queue_entry_t)(elt); \
745 } \
746 (elt)->field.prev = __prev; \
747 (elt)->field.next = head; \
748 (head)->prev = (queue_entry_t) elt; \
749 MACRO_END
750
751 /*
752 * Macro: queue_enter_first
753 * Function:
754 * Insert a new element at the head of the queue.
755 * Header:
756 * void queue_enter_first(q, elt, type, field)
757 * queue_t q;
758 * <type> elt;
759 * <type> is what's in our queue
760 * <field> is the chain field in (*<type>)
761 * Note:
762 * This should only be used with Method 2 queue iteration (element chains)
763 */
764 #define queue_enter_first(head, elt, type, field) \
765 MACRO_BEGIN \
766 queue_entry_t __next; \
767 \
768 __next = (head)->next; \
769 if ((head) == __next) { \
770 (head)->prev = (queue_entry_t) (elt); \
771 } \
772 else { \
773 ((type)(void *)__next)->field.prev = \
774 (queue_entry_t)(elt); \
775 } \
776 (elt)->field.next = __next; \
777 (elt)->field.prev = head; \
778 (head)->next = (queue_entry_t) elt; \
779 MACRO_END
780
781 /*
782 * Macro: queue_insert_before
783 * Function:
784 * Insert a new element before a given element.
785 * Header:
786 * void queue_insert_before(q, elt, cur, type, field)
787 * queue_t q;
788 * <type> elt;
789 * <type> cur;
790 * <type> is what's in our queue
791 * <field> is the chain field in (*<type>)
792 * Note:
793 * This should only be used with Method 2 queue iteration (element chains)
794 */
795 #define queue_insert_before(head, elt, cur, type, field) \
796 MACRO_BEGIN \
797 queue_entry_t __prev; \
798 \
799 if ((head) == (queue_entry_t)(cur)) { \
800 (elt)->field.next = (head); \
801 if ((head)->next == (head)) { /* only element */ \
802 (elt)->field.prev = (head); \
803 (head)->next = (queue_entry_t)(elt); \
804 } else { /* last element */ \
805 __prev = (elt)->field.prev = (head)->prev; \
806 ((type)(void *)__prev)->field.next = \
807 (queue_entry_t)(elt); \
808 } \
809 (head)->prev = (queue_entry_t)(elt); \
810 } else { \
811 (elt)->field.next = (queue_entry_t)(cur); \
812 if ((head)->next == (queue_entry_t)(cur)) { \
813 /* first element */ \
814 (elt)->field.prev = (head); \
815 (head)->next = (queue_entry_t)(elt); \
816 } else { /* middle element */ \
817 __prev = (elt)->field.prev = (cur)->field.prev; \
818 ((type)(void *)__prev)->field.next = \
819 (queue_entry_t)(elt); \
820 } \
821 (cur)->field.prev = (queue_entry_t)(elt); \
822 } \
823 MACRO_END
824
825 /*
826 * Macro: queue_insert_after
827 * Function:
828 * Insert a new element after a given element.
829 * Header:
830 * void queue_insert_after(q, elt, cur, type, field)
831 * queue_t q;
832 * <type> elt;
833 * <type> cur;
834 * <type> is what's in our queue
835 * <field> is the chain field in (*<type>)
836 * Note:
837 * This should only be used with Method 2 queue iteration (element chains)
838 */
839 #define queue_insert_after(head, elt, cur, type, field) \
840 MACRO_BEGIN \
841 queue_entry_t __next; \
842 \
843 if ((head) == (queue_entry_t)(cur)) { \
844 (elt)->field.prev = (head); \
845 if ((head)->next == (head)) { /* only element */ \
846 (elt)->field.next = (head); \
847 (head)->prev = (queue_entry_t)(elt); \
848 } else { /* first element */ \
849 __next = (elt)->field.next = (head)->next; \
850 ((type)(void *)__next)->field.prev = \
851 (queue_entry_t)(elt); \
852 } \
853 (head)->next = (queue_entry_t)(elt); \
854 } else { \
855 (elt)->field.prev = (queue_entry_t)(cur); \
856 if ((head)->prev == (queue_entry_t)(cur)) { \
857 /* last element */ \
858 (elt)->field.next = (head); \
859 (head)->prev = (queue_entry_t)(elt); \
860 } else { /* middle element */ \
861 __next = (elt)->field.next = (cur)->field.next; \
862 ((type)(void *)__next)->field.prev = \
863 (queue_entry_t)(elt); \
864 } \
865 (cur)->field.next = (queue_entry_t)(elt); \
866 } \
867 MACRO_END
868
869 /*
870 * Macro: queue_field [internal use only]
871 * Function:
872 * Find the queue_chain_t (or queue_t) for the
873 * given element (thing) in the given queue (head)
874 * Note:
875 * This should only be used with Method 2 queue iteration (element chains)
876 */
877 #define queue_field(head, thing, type, field) \
878 (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field)
879
880 /*
881 * Macro: queue_remove
882 * Function:
883 * Remove an arbitrary item from the queue.
884 * Header:
885 * void queue_remove(q, qe, type, field)
886 * arguments as in queue_enter
887 * Note:
888 * This should only be used with Method 2 queue iteration (element chains)
889 */
890 #define queue_remove(head, elt, type, field) \
891 MACRO_BEGIN \
892 queue_entry_t __next, __prev; \
893 \
894 __next = (elt)->field.next; \
895 __prev = (elt)->field.prev; \
896 \
897 if ((head) == __next) \
898 (head)->prev = __prev; \
899 else \
900 ((type)(void *)__next)->field.prev = __prev; \
901 \
902 if ((head) == __prev) \
903 (head)->next = __next; \
904 else \
905 ((type)(void *)__prev)->field.next = __next; \
906 \
907 (elt)->field.next = NULL; \
908 (elt)->field.prev = NULL; \
909 MACRO_END
910
911 /*
912 * Macro: queue_remove_first
913 * Function:
914 * Remove and return the entry at the head of
915 * the queue.
916 * Header:
917 * queue_remove_first(head, entry, type, field)
918 * entry is returned by reference
919 * Note:
920 * This should only be used with Method 2 queue iteration (element chains)
921 */
922 #define queue_remove_first(head, entry, type, field) \
923 MACRO_BEGIN \
924 queue_entry_t __next; \
925 \
926 (entry) = (type)(void *) ((head)->next); \
927 __next = (entry)->field.next; \
928 \
929 if ((head) == __next) \
930 (head)->prev = (head); \
931 else \
932 ((type)(void *)(__next))->field.prev = (head); \
933 (head)->next = __next; \
934 \
935 (entry)->field.next = NULL; \
936 (entry)->field.prev = NULL; \
937 MACRO_END
938
939 /*
940 * Macro: queue_remove_last
941 * Function:
942 * Remove and return the entry at the tail of
943 * the queue.
944 * Header:
945 * queue_remove_last(head, entry, type, field)
946 * entry is returned by reference
947 * Note:
948 * This should only be used with Method 2 queue iteration (element chains)
949 */
950 #define queue_remove_last(head, entry, type, field) \
951 MACRO_BEGIN \
952 queue_entry_t __prev; \
953 \
954 (entry) = (type)(void *) ((head)->prev); \
955 __prev = (entry)->field.prev; \
956 \
957 if ((head) == __prev) \
958 (head)->next = (head); \
959 else \
960 ((type)(void *)(__prev))->field.next = (head); \
961 (head)->prev = __prev; \
962 \
963 (entry)->field.next = NULL; \
964 (entry)->field.prev = NULL; \
965 MACRO_END
966
967 /*
968 * Macro: queue_assign
969 * Note:
970 * This should only be used with Method 2 queue iteration (element chains)
971 */
972 #define queue_assign(to, from, type, field) \
973 MACRO_BEGIN \
974 ((type)(void *)((from)->prev))->field.next = (to); \
975 ((type)(void *)((from)->next))->field.prev = (to); \
976 *to = *from; \
977 MACRO_END
978
979 /*
980 * Macro: queue_new_head
981 * Function:
982 * rebase old queue to new queue head
983 * Header:
984 * queue_new_head(old, new, type, field)
985 * queue_t old;
986 * queue_t new;
987 * <type> is what's in our queue
988 * <field> is the chain field in (*<type>)
989 * Note:
990 * This should only be used with Method 2 queue iteration (element chains)
991 */
992 #define queue_new_head(old, new, type, field) \
993 MACRO_BEGIN \
994 if (!queue_empty(old)) { \
995 *(new) = *(old); \
996 ((type)(void *)((new)->next))->field.prev = \
997 (new); \
998 ((type)(void *)((new)->prev))->field.next = \
999 (new); \
1000 } else { \
1001 queue_init(new); \
1002 } \
1003 MACRO_END
1004
1005 /*
1006 * Macro: queue_iterate
1007 * Function:
1008 * iterate over each item in the queue.
1009 * Generates a 'for' loop, setting elt to
1010 * each item in turn (by reference).
1011 * Header:
1012 * queue_iterate(q, elt, type, field)
1013 * queue_t q;
1014 * <type> elt;
1015 * <type> is what's in our queue
1016 * <field> is the chain field in (*<type>)
1017 * Note:
1018 * This should only be used with Method 2 queue iteration (element chains)
1019 */
1020 #define queue_iterate(head, elt, type, field) \
1021 for ((elt) = (type)(void *) queue_first(head); \
1022 !queue_end((head), (queue_entry_t)(elt)); \
1023 (elt) = (type)(void *) queue_next(&(elt)->field))
1024
1025 #ifdef MACH_KERNEL_PRIVATE
1026
1027 #include <kern/locks.h>
1028
1029 /*----------------------------------------------------------------*/
1030 /*
1031 * Define macros for queues with locks.
1032 */
1033 struct mpqueue_head {
1034 struct queue_entry head; /* header for queue */
1035 uint64_t earliest_soft_deadline;
1036 uint64_t count;
1037 lck_mtx_t lock_data;
1038 #if defined(__i386__) || defined(__x86_64__)
1039 lck_mtx_ext_t lock_data_ext;
1040 #endif
1041 };
1042
1043 typedef struct mpqueue_head mpqueue_head_t;
1044
1045 #define round_mpq(size) (size)
1046
1047
1048 #if defined(__i386__) || defined(__x86_64__)
1049
1050 #define mpqueue_init(q, lck_grp, lck_attr) \
1051 MACRO_BEGIN \
1052 queue_init(&(q)->head); \
1053 lck_mtx_init_ext(&(q)->lock_data, \
1054 &(q)->lock_data_ext, \
1055 lck_grp, \
1056 lck_attr); \
1057 (q)->earliest_soft_deadline = UINT64_MAX; \
1058 (q)->count = 0; \
1059 MACRO_END
1060
1061 #else
1062
1063 #define mpqueue_init(q, lck_grp, lck_attr) \
1064 MACRO_BEGIN \
1065 queue_init(&(q)->head); \
1066 lck_mtx_init(&(q)->lock_data, \
1067 lck_grp, \
1068 lck_attr); \
1069 MACRO_END
1070 #endif
1071
1072
1073 #define mpenqueue_tail(q, elt) \
1074 MACRO_BEGIN \
1075 lck_mtx_lock_spin_always(&(q)->lock_data); \
1076 enqueue_tail(&(q)->head, elt); \
1077 lck_mtx_unlock_always(&(q)->lock_data); \
1078 MACRO_END
1079
1080 #define mpdequeue_head(q, elt) \
1081 MACRO_BEGIN \
1082 lck_mtx_lock_spin_always(&(q)->lock_data); \
1083 if (queue_empty(&(q)->head)) \
1084 *(elt) = 0; \
1085 else \
1086 *(elt) = dequeue_head(&(q)->head); \
1087 lck_mtx_unlock_always(&(q)->lock_data); \
1088 MACRO_END
1089
1090 #endif /* MACH_KERNEL_PRIVATE */
1091
1092 __END_DECLS
1093
1094 #endif /* _KERN_QUEUE_H_ */