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