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