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 #if defined(XNU_KERNEL_PRIVATE) || DRIVERKIT_FRAMEWORK_INCLUDE
224
225 #if KERNEL
226 __abortlike
227 extern void __queue_element_linkage_invalid(queue_entry_t e);
228 #else
229 #define __queue_element_linkage_invalid(e) __builtin_trap()
230 #endif
231
232 static inline void
__QUEUE_ELT_VALIDATE(queue_entry_t elt)233 __QUEUE_ELT_VALIDATE(queue_entry_t elt)
234 {
235 if (elt->prev->next != elt || elt->next->prev != elt) {
236 __queue_element_linkage_invalid(elt);
237 }
238 }
239
240 static inline void
__DEQUEUE_ELT_CLEANUP(queue_entry_t elt)241 __DEQUEUE_ELT_CLEANUP(queue_entry_t elt)
242 {
243 elt->next = elt->prev = (queue_entry_t)NULL;
244 }
245 #else
246 #define __QUEUE_ELT_VALIDATE(elt) ((void)0)
247 #define __DEQUEUE_ELT_CLEANUP(elt) ((void)0)
248 #endif /* !(XNU_KERNEL_PRIVATE || DRIVERKIT_FRAMEWORK_INCLUDE)*/
249
250 /*
251 * enqueue puts "elt" on the "queue".
252 * dequeue returns the first element in the "queue".
253 * remqueue removes the specified "elt" from its queue.
254 */
255
256 #if !DRIVERKIT_FRAMEWORK_INCLUDE
257 #define enqueue(queue, elt) enqueue_tail(queue, elt)
258 #define dequeue(queue) dequeue_head(queue)
259 #endif
260
261 static __inline__ void
enqueue_head(queue_t que,queue_entry_t elt)262 enqueue_head(
263 queue_t que,
264 queue_entry_t elt)
265 {
266 queue_entry_t old_head;
267
268 __QUEUE_ELT_VALIDATE((queue_entry_t)que);
269 old_head = que->next;
270 elt->next = old_head;
271 elt->prev = que;
272 old_head->prev = elt;
273 que->next = elt;
274 }
275
276 static __inline__ void
enqueue_tail(queue_t que,queue_entry_t elt)277 enqueue_tail(
278 queue_t que,
279 queue_entry_t elt)
280 {
281 queue_entry_t old_tail;
282
283 __QUEUE_ELT_VALIDATE((queue_entry_t)que);
284 old_tail = que->prev;
285 elt->next = que;
286 elt->prev = old_tail;
287 old_tail->next = elt;
288 que->prev = elt;
289 }
290
291 static __inline__ queue_entry_t
dequeue_head(queue_t que)292 dequeue_head(
293 queue_t que)
294 {
295 queue_entry_t elt = (queue_entry_t)NULL;
296 queue_entry_t new_head;
297
298 if (que->next != que) {
299 elt = que->next;
300 __QUEUE_ELT_VALIDATE(elt);
301 new_head = elt->next; /* new_head may point to que if elt was the only element */
302 new_head->prev = que;
303 que->next = new_head;
304 __DEQUEUE_ELT_CLEANUP(elt);
305 }
306
307 return elt;
308 }
309
310 static __inline__ queue_entry_t
dequeue_tail(queue_t que)311 dequeue_tail(
312 queue_t que)
313 {
314 queue_entry_t elt = (queue_entry_t)NULL;
315 queue_entry_t new_tail;
316
317 if (que->prev != que) {
318 elt = que->prev;
319 __QUEUE_ELT_VALIDATE(elt);
320 new_tail = elt->prev; /* new_tail may point to queue if elt was the only element */
321 new_tail->next = que;
322 que->prev = new_tail;
323 __DEQUEUE_ELT_CLEANUP(elt);
324 }
325
326 return elt;
327 }
328
329 static __inline__ void
remqueue(queue_entry_t elt)330 remqueue(
331 queue_entry_t elt)
332 {
333 queue_entry_t next_elt, prev_elt;
334
335 __QUEUE_ELT_VALIDATE(elt);
336 next_elt = elt->next;
337 prev_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
338 next_elt->prev = prev_elt;
339 prev_elt->next = next_elt;
340 __DEQUEUE_ELT_CLEANUP(elt);
341 }
342
343 static __inline__ void
insque(queue_entry_t entry,queue_entry_t pred)344 insque(
345 queue_entry_t entry,
346 queue_entry_t pred)
347 {
348 queue_entry_t successor;
349
350 __QUEUE_ELT_VALIDATE(pred);
351 successor = pred->next;
352 entry->next = successor;
353 entry->prev = pred;
354 successor->prev = entry;
355 pred->next = entry;
356 }
357
358 static __inline__ void
remque(queue_entry_t elt)359 remque(
360 queue_entry_t elt)
361 {
362 remqueue(elt);
363 }
364
365 /*
366 * Function: re_queue_head
367 * Parameters:
368 * queue_t que : queue onto which elt will be pre-pended
369 * queue_entry_t elt : element to re-queue
370 * Description:
371 * Remove elt from its current queue and put it onto the
372 * head of a new queue
373 * Note:
374 * This should only be used with Method 1 queue iteration (linkage chains)
375 */
376 static __inline__ void
re_queue_head(queue_t que,queue_entry_t elt)377 re_queue_head(queue_t que, queue_entry_t elt)
378 {
379 queue_entry_t n_elt, p_elt;
380
381 __QUEUE_ELT_VALIDATE(elt);
382 __QUEUE_ELT_VALIDATE((queue_entry_t)que);
383
384 /* remqueue */
385 n_elt = elt->next;
386 p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
387 n_elt->prev = p_elt;
388 p_elt->next = n_elt;
389
390 /* enqueue_head */
391 n_elt = que->next;
392 elt->next = n_elt;
393 elt->prev = que;
394 n_elt->prev = elt;
395 que->next = elt;
396 }
397
398 /*
399 * Function: re_queue_tail
400 * Parameters:
401 * queue_t que : queue onto which elt will be appended
402 * queue_entry_t elt : element to re-queue
403 * Description:
404 * Remove elt from its current queue and put it onto the
405 * end of a new queue
406 * Note:
407 * This should only be used with Method 1 queue iteration (linkage chains)
408 */
409 static __inline__ void
re_queue_tail(queue_t que,queue_entry_t elt)410 re_queue_tail(queue_t que, queue_entry_t elt)
411 {
412 queue_entry_t n_elt, p_elt;
413
414 __QUEUE_ELT_VALIDATE(elt);
415 __QUEUE_ELT_VALIDATE((queue_entry_t)que);
416
417 /* remqueue */
418 n_elt = elt->next;
419 p_elt = elt->prev; /* next_elt may equal prev_elt (and the queue head) if elt was the only element */
420 n_elt->prev = p_elt;
421 p_elt->next = n_elt;
422
423 /* enqueue_tail */
424 p_elt = que->prev;
425 elt->next = que;
426 elt->prev = p_elt;
427 p_elt->next = elt;
428 que->prev = elt;
429 }
430
431 /*
432 * Macro: qe_element
433 * Function:
434 * Convert a queue_entry_t to a queue element pointer.
435 * Get a pointer to the user-defined element containing
436 * a given queue_entry_t
437 * Header:
438 * <type> * qe_element(queue_entry_t qe, <type>, field)
439 * qe - queue entry to convert
440 * <type> - what's in the queue (e.g., struct some_data)
441 * <field> - is the chain field in <type>
442 * Note:
443 * Do not use pointer types for <type>
444 */
445 #define qe_element(qe, type, field) __container_of(qe, type, field)
446
447 /*
448 * Macro: qe_foreach
449 * Function:
450 * Iterate over each queue_entry_t structure.
451 * Generates a 'for' loop, setting 'qe' to
452 * each queue_entry_t in the queue.
453 * Header:
454 * qe_foreach(queue_entry_t qe, queue_t head)
455 * qe - iteration variable
456 * head - pointer to queue_head_t (head of queue)
457 * Note:
458 * This should only be used with Method 1 queue iteration (linkage chains)
459 */
460 #define qe_foreach(qe, head) \
461 for (qe = (head)->next; qe != (head); qe = (qe)->next)
462
463 /*
464 * Macro: qe_foreach_safe
465 * Function:
466 * Safely iterate over each queue_entry_t structure.
467 *
468 * Use this iterator macro if you plan to remove the
469 * queue_entry_t, qe, from the queue during the
470 * iteration.
471 * Header:
472 * qe_foreach_safe(queue_entry_t qe, queue_t head)
473 * qe - iteration variable
474 * head - pointer to queue_head_t (head of queue)
475 * Note:
476 * This should only be used with Method 1 queue iteration (linkage chains)
477 */
478 #define qe_foreach_safe(qe, head) \
479 for (queue_entry_t _ne = ((head)->next)->next, \
480 __ ## qe ## _unused_shadow __unused = (qe = (head)->next); \
481 qe != (head); \
482 qe = _ne, _ne = (qe)->next)
483
484 /*
485 * Macro: qe_foreach_element
486 * Function:
487 * Iterate over each _element_ in a queue
488 * where each queue_entry_t points to another
489 * queue_entry_t, i.e., managed by the [de|en]queue_head/
490 * [de|en]queue_tail / remqueue / etc. function.
491 * Header:
492 * qe_foreach_element(<type> *elt, queue_t head, <field>)
493 * elt - iteration variable
494 * <type> - what's in the queue (e.g., struct some_data)
495 * <field> - is the chain field in <type>
496 * Note:
497 * This should only be used with Method 1 queue iteration (linkage chains)
498 */
499 #define qe_foreach_element(elt, head, field) \
500 for (elt = qe_element((head)->next, typeof(*(elt)), field); \
501 &((elt)->field) != (head); \
502 elt = qe_element((elt)->field.next, typeof(*(elt)), field))
503
504 /*
505 * Macro: qe_foreach_element_safe
506 * Function:
507 * Safely iterate over each _element_ in a queue
508 * where each queue_entry_t points to another
509 * queue_entry_t, i.e., managed by the [de|en]queue_head/
510 * [de|en]queue_tail / remqueue / etc. function.
511 *
512 * Use this iterator macro if you plan to remove the
513 * element, elt, from the queue during the iteration.
514 * Header:
515 * qe_foreach_element_safe(<type> *elt, queue_t head, <field>)
516 * elt - iteration variable
517 * <type> - what's in the queue (e.g., struct some_data)
518 * <field> - is the chain field in <type>
519 * Note:
520 * This should only be used with Method 1 queue iteration (linkage chains)
521 */
522 #define qe_foreach_element_safe(elt, head, field) \
523 for (typeof(*(elt)) *_nelt = qe_element(((head)->next)->next, typeof(*(elt)), field), \
524 *__ ## elt ## _unused_shadow __unused = \
525 (elt = qe_element((head)->next, typeof(*(elt)), field)); \
526 &((elt)->field) != (head); \
527 elt = _nelt, _nelt = qe_element((elt)->field.next, typeof(*(elt)), field)) \
528
529 #ifdef XNU_KERNEL_PRIVATE
530
531 /* Dequeue an element from head, or return NULL if the queue is empty */
532 #define qe_dequeue_head(head, type, field) ({ \
533 queue_entry_t _tmp_entry = dequeue_head((head)); \
534 type *_tmp_element = (type*) NULL; \
535 if (_tmp_entry != (queue_entry_t) NULL) \
536 _tmp_element = qe_element(_tmp_entry, type, field); \
537 _tmp_element; \
538 })
539
540 /* Dequeue an element from tail, or return NULL if the queue is empty */
541 #define qe_dequeue_tail(head, type, field) ({ \
542 queue_entry_t _tmp_entry = dequeue_tail((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 /* Peek at the first element, or return NULL if the queue is empty */
550 #define qe_queue_first(head, type, field) ({ \
551 queue_entry_t _tmp_entry = queue_first((head)); \
552 type *_tmp_element = (type*) NULL; \
553 if (_tmp_entry != (queue_entry_t) head) \
554 _tmp_element = qe_element(_tmp_entry, type, field); \
555 _tmp_element; \
556 })
557
558 /* Peek at the last element, or return NULL if the queue is empty */
559 #define qe_queue_last(head, type, field) ({ \
560 queue_entry_t _tmp_entry = queue_last((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 next element, or return NULL if the next element is head (indicating queue_end) */
568 #define qe_queue_next(head, element, type, field) ({ \
569 queue_entry_t _tmp_entry = queue_next(&(element)->field); \
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 prev element, or return NULL if the prev element is head (indicating queue_end) */
577 #define qe_queue_prev(head, element, type, field) ({ \
578 queue_entry_t _tmp_entry = queue_prev(&(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 #endif /* XNU_KERNEL_PRIVATE */
586
587 /*
588 * Macro: QUEUE_HEAD_INITIALIZER()
589 * Function:
590 * Static queue head initializer
591 */
592 #define QUEUE_HEAD_INITIALIZER(name) \
593 { &name, &name }
594
595 /*
596 * Macro: queue_init
597 * Function:
598 * Initialize the given queue.
599 * Header:
600 * void queue_init(q)
601 * queue_t q; \* MODIFIED *\
602 */
603 #define queue_init(q) \
604 MACRO_BEGIN \
605 (q)->next = (q);\
606 (q)->prev = (q);\
607 MACRO_END
608
609 /*
610 * Macro: queue_head_init
611 * Function:
612 * Initialize the given queue head
613 * Header:
614 * void queue_head_init(q)
615 * queue_head_t q; \* MODIFIED *\
616 */
617 #define queue_head_init(q) \
618 queue_init(&(q))
619
620 /*
621 * Macro: queue_chain_init
622 * Function:
623 * Initialize the given queue chain element
624 * Header:
625 * void queue_chain_init(q)
626 * queue_chain_t q; \* MODIFIED *\
627 */
628 #define queue_chain_init(q) \
629 queue_init(&(q))
630
631 /*
632 * Macro: queue_first
633 * Function:
634 * Returns the first entry in the queue,
635 * Header:
636 * queue_entry_t queue_first(q)
637 * queue_t q; \* IN *\
638 */
639 #define queue_first(q) ((q)->next)
640
641 /*
642 * Macro: queue_next
643 * Function:
644 * Returns the entry after an item in the queue.
645 * Header:
646 * queue_entry_t queue_next(qc)
647 * queue_t qc;
648 */
649 #define queue_next(qc) ((qc)->next)
650
651 /*
652 * Macro: queue_last
653 * Function:
654 * Returns the last entry in the queue.
655 * Header:
656 * queue_entry_t queue_last(q)
657 * queue_t q; \* IN *\
658 */
659 #define queue_last(q) ((q)->prev)
660
661 /*
662 * Macro: queue_prev
663 * Function:
664 * Returns the entry before an item in the queue.
665 * Header:
666 * queue_entry_t queue_prev(qc)
667 * queue_t qc;
668 */
669 #define queue_prev(qc) ((qc)->prev)
670
671 /*
672 * Macro: queue_end
673 * Function:
674 * Tests whether a new entry is really the end of
675 * the queue.
676 * Header:
677 * boolean_t queue_end(q, qe)
678 * queue_t q;
679 * queue_entry_t qe;
680 */
681 #define queue_end(q, qe) ((q) == (qe))
682
683 /*
684 * Macro: queue_empty
685 * Function:
686 * Tests whether a queue is empty.
687 * Header:
688 * boolean_t queue_empty(q)
689 * queue_t q;
690 */
691 #define queue_empty(q) queue_end((q), queue_first(q))
692
693 /*
694 * Function: movqueue
695 * Parameters:
696 * queue_t _old : head of a queue whose items will be moved
697 * queue_t _new : new queue head onto which items will be moved
698 * Description:
699 * Rebase queue items in _old onto _new then re-initialize
700 * the _old object to an empty queue.
701 * Equivalent to the queue_new_head Method 2 macro
702 * Note:
703 * Similar to the queue_new_head macro, this macros is intented
704 * to function as an initializer method for '_new' and thus may
705 * leak any list items that happen to be on the '_new' list.
706 * This should only be used with Method 1 queue iteration (linkage chains)
707 */
708 static __inline__ void
movqueue(queue_t _old,queue_t _new)709 movqueue(queue_t _old, queue_t _new)
710 {
711 queue_entry_t next_elt, prev_elt;
712
713 __QUEUE_ELT_VALIDATE((queue_entry_t)_old);
714
715 if (queue_empty(_old)) {
716 queue_init(_new);
717 return;
718 }
719
720 /*
721 * move the queue at _old to _new
722 * and re-initialize _old
723 */
724 next_elt = _old->next;
725 prev_elt = _old->prev;
726
727 _new->next = next_elt;
728 _new->prev = prev_elt;
729 next_elt->prev = _new;
730 prev_elt->next = _new;
731
732 queue_init(_old);
733 }
734
735 /*----------------------------------------------------------------*/
736 /*
737 * Macros that operate on generic structures. The queue
738 * chain may be at any location within the structure, and there
739 * may be more than one chain.
740 */
741
742 /*
743 * Macro: queue_enter
744 * Function:
745 * Insert a new element at the tail of the queue.
746 * Header:
747 * void queue_enter(q, elt, type, field)
748 * queue_t q;
749 * <type> elt;
750 * <type> is what's in our queue
751 * <field> is the chain field in (*<type>)
752 * Note:
753 * This should only be used with Method 2 queue iteration (element chains)
754 *
755 * We insert a compiler barrier after setting the fields in the element
756 * to ensure that the element is updated before being added to the queue,
757 * which is especially important because stackshot, which operates from
758 * debugger context, iterates several queues that use this macro (the tasks
759 * lists and threads lists) without locks. Without this barrier, the
760 * compiler may re-order the instructions for this macro in a way that
761 * could cause stackshot to trip over an inconsistent queue during
762 * iteration.
763 */
764 #define queue_enter(head, elt, type, field) \
765 MACRO_BEGIN \
766 queue_entry_t __prev; \
767 \
768 __prev = (head)->prev; \
769 (elt)->field.prev = __prev; \
770 (elt)->field.next = head; \
771 __compiler_barrier(); \
772 if ((head) == __prev) { \
773 (head)->next = (queue_entry_t) (elt); \
774 } \
775 else { \
776 ((type)(void *)__prev)->field.next = \
777 (queue_entry_t)(elt); \
778 } \
779 (head)->prev = (queue_entry_t) elt; \
780 MACRO_END
781
782 /*
783 * Macro: queue_enter_first
784 * Function:
785 * Insert a new element at the head of the queue.
786 * Header:
787 * void queue_enter_first(q, elt, type, field)
788 * queue_t q;
789 * <type> elt;
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_enter_first(head, elt, type, field) \
796 MACRO_BEGIN \
797 queue_entry_t __next; \
798 \
799 __next = (head)->next; \
800 if ((head) == __next) { \
801 (head)->prev = (queue_entry_t) (elt); \
802 } \
803 else { \
804 ((type)(void *)__next)->field.prev = \
805 (queue_entry_t)(elt); \
806 } \
807 (elt)->field.next = __next; \
808 (elt)->field.prev = head; \
809 (head)->next = (queue_entry_t) elt; \
810 MACRO_END
811
812 /*
813 * Macro: queue_insert_before
814 * Function:
815 * Insert a new element before a given element.
816 * Header:
817 * void queue_insert_before(q, elt, cur, type, field)
818 * queue_t q;
819 * <type> elt;
820 * <type> cur;
821 * <type> is what's in our queue
822 * <field> is the chain field in (*<type>)
823 * Note:
824 * This should only be used with Method 2 queue iteration (element chains)
825 */
826 #define queue_insert_before(head, elt, cur, type, field) \
827 MACRO_BEGIN \
828 queue_entry_t __prev; \
829 \
830 if ((head) == (queue_entry_t)(cur)) { \
831 (elt)->field.next = (head); \
832 if ((head)->next == (head)) { /* only element */ \
833 (elt)->field.prev = (head); \
834 (head)->next = (queue_entry_t)(elt); \
835 } else { /* last element */ \
836 __prev = (elt)->field.prev = (head)->prev; \
837 ((type)(void *)__prev)->field.next = \
838 (queue_entry_t)(elt); \
839 } \
840 (head)->prev = (queue_entry_t)(elt); \
841 } else { \
842 (elt)->field.next = (queue_entry_t)(cur); \
843 if ((head)->next == (queue_entry_t)(cur)) { \
844 /* first element */ \
845 (elt)->field.prev = (head); \
846 (head)->next = (queue_entry_t)(elt); \
847 } else { /* middle element */ \
848 __prev = (elt)->field.prev = (cur)->field.prev; \
849 ((type)(void *)__prev)->field.next = \
850 (queue_entry_t)(elt); \
851 } \
852 (cur)->field.prev = (queue_entry_t)(elt); \
853 } \
854 MACRO_END
855
856 /*
857 * Macro: queue_insert_after
858 * Function:
859 * Insert a new element after a given element.
860 * Header:
861 * void queue_insert_after(q, elt, cur, type, field)
862 * queue_t q;
863 * <type> elt;
864 * <type> cur;
865 * <type> is what's in our queue
866 * <field> is the chain field in (*<type>)
867 * Note:
868 * This should only be used with Method 2 queue iteration (element chains)
869 */
870 #define queue_insert_after(head, elt, cur, type, field) \
871 MACRO_BEGIN \
872 queue_entry_t __next; \
873 \
874 if ((head) == (queue_entry_t)(cur)) { \
875 (elt)->field.prev = (head); \
876 if ((head)->next == (head)) { /* only element */ \
877 (elt)->field.next = (head); \
878 (head)->prev = (queue_entry_t)(elt); \
879 } else { /* first element */ \
880 __next = (elt)->field.next = (head)->next; \
881 ((type)(void *)__next)->field.prev = \
882 (queue_entry_t)(elt); \
883 } \
884 (head)->next = (queue_entry_t)(elt); \
885 } else { \
886 (elt)->field.prev = (queue_entry_t)(cur); \
887 if ((head)->prev == (queue_entry_t)(cur)) { \
888 /* last element */ \
889 (elt)->field.next = (head); \
890 (head)->prev = (queue_entry_t)(elt); \
891 } else { /* middle element */ \
892 __next = (elt)->field.next = (cur)->field.next; \
893 ((type)(void *)__next)->field.prev = \
894 (queue_entry_t)(elt); \
895 } \
896 (cur)->field.next = (queue_entry_t)(elt); \
897 } \
898 MACRO_END
899
900 /*
901 * Macro: queue_field [internal use only]
902 * Function:
903 * Find the queue_chain_t (or queue_t) for the
904 * given element (thing) in the given queue (head)
905 * Note:
906 * This should only be used with Method 2 queue iteration (element chains)
907 */
908 #define queue_field(head, thing, type, field) \
909 (((head) == (thing)) ? (head) : &((type)(void *)(thing))->field)
910
911 /*
912 * Macro: queue_remove
913 * Function:
914 * Remove an arbitrary item from the queue.
915 * Header:
916 * void queue_remove(q, qe, type, field)
917 * arguments as in queue_enter
918 * Note:
919 * This should only be used with Method 2 queue iteration (element chains)
920 */
921 #define queue_remove(head, elt, type, field) \
922 MACRO_BEGIN \
923 queue_entry_t __next, __prev; \
924 \
925 __next = (elt)->field.next; \
926 __prev = (elt)->field.prev; \
927 \
928 if ((head) == __next) \
929 (head)->prev = __prev; \
930 else \
931 ((type)(void *)__next)->field.prev = __prev; \
932 \
933 if ((head) == __prev) \
934 (head)->next = __next; \
935 else \
936 ((type)(void *)__prev)->field.next = __next; \
937 \
938 (elt)->field.next = NULL; \
939 (elt)->field.prev = NULL; \
940 MACRO_END
941
942 /*
943 * Macro: queue_remove_first
944 * Function:
945 * Remove and return the entry at the head of
946 * the queue.
947 * Header:
948 * queue_remove_first(head, entry, type, field)
949 * entry is returned by reference
950 * Note:
951 * This should only be used with Method 2 queue iteration (element chains)
952 */
953 #define queue_remove_first(head, entry, type, field) \
954 MACRO_BEGIN \
955 queue_entry_t __next; \
956 \
957 (entry) = (type)(void *) ((head)->next); \
958 __next = (entry)->field.next; \
959 \
960 if ((head) == __next) \
961 (head)->prev = (head); \
962 else \
963 ((type)(void *)(__next))->field.prev = (head); \
964 (head)->next = __next; \
965 \
966 (entry)->field.next = NULL; \
967 (entry)->field.prev = NULL; \
968 MACRO_END
969
970 /*
971 * Macro: queue_remove_last
972 * Function:
973 * Remove and return the entry at the tail of
974 * the queue.
975 * Header:
976 * queue_remove_last(head, entry, type, field)
977 * entry is returned by reference
978 * Note:
979 * This should only be used with Method 2 queue iteration (element chains)
980 */
981 #define queue_remove_last(head, entry, type, field) \
982 MACRO_BEGIN \
983 queue_entry_t __prev; \
984 \
985 (entry) = (type)(void *) ((head)->prev); \
986 __prev = (entry)->field.prev; \
987 \
988 if ((head) == __prev) \
989 (head)->next = (head); \
990 else \
991 ((type)(void *)(__prev))->field.next = (head); \
992 (head)->prev = __prev; \
993 \
994 (entry)->field.next = NULL; \
995 (entry)->field.prev = NULL; \
996 MACRO_END
997
998 /*
999 * Macro: queue_assign
1000 * Note:
1001 * This should only be used with Method 2 queue iteration (element chains)
1002 */
1003 #define queue_assign(to, from, type, field) \
1004 MACRO_BEGIN \
1005 ((type)(void *)((from)->prev))->field.next = (to); \
1006 ((type)(void *)((from)->next))->field.prev = (to); \
1007 *to = *from; \
1008 MACRO_END
1009
1010 /*
1011 * Macro: queue_new_head
1012 * Function:
1013 * rebase old queue to new queue head
1014 * Header:
1015 * queue_new_head(old, new, type, field)
1016 * queue_t old;
1017 * queue_t new;
1018 * <type> is what's in our queue
1019 * <field> is the chain field in (*<type>)
1020 * Note:
1021 * This should only be used with Method 2 queue iteration (element chains)
1022 */
1023 #define queue_new_head(old, new, type, field) \
1024 MACRO_BEGIN \
1025 if (!queue_empty(old)) { \
1026 *(new) = *(old); \
1027 ((type)(void *)((new)->next))->field.prev = \
1028 (new); \
1029 ((type)(void *)((new)->prev))->field.next = \
1030 (new); \
1031 } else { \
1032 queue_init(new); \
1033 } \
1034 MACRO_END
1035
1036 /*
1037 * Macro: queue_iterate
1038 * Function:
1039 * iterate over each item in the queue.
1040 * Generates a 'for' loop, setting elt to
1041 * each item in turn (by reference).
1042 * Header:
1043 * queue_iterate(q, elt, type, field)
1044 * queue_t q;
1045 * <type> elt;
1046 * <type> is what's in our queue
1047 * <field> is the chain field in (*<type>)
1048 * Note:
1049 * This should only be used with Method 2 queue iteration (element chains)
1050 */
1051 #define queue_iterate(head, elt, type, field) \
1052 for ((elt) = (type)(void *) queue_first(head); \
1053 !queue_end((head), (queue_entry_t)(elt)); \
1054 (elt) = (type)(void *) queue_next(&(elt)->field))
1055
1056
1057 __END_DECLS
1058
1059 #endif /* _KERN_QUEUE_H_ */
1060