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 | |
201 | struct queue_entry { |
202 | struct queue_entry *next; /* next element */ |
203 | struct queue_entry *prev; /* previous element */ |
204 | }; |
205 | |
206 | typedef struct queue_entry *queue_t; |
207 | typedef struct queue_entry queue_head_t; |
208 | typedef struct queue_entry queue_chain_t; |
209 | typedef struct queue_entry *queue_entry_t; |
210 | |
211 | #if defined(XNU_KERNEL_PRIVATE) || DRIVERKIT_FRAMEWORK_INCLUDE |
212 | |
213 | #if KERNEL |
214 | __abortlike |
215 | extern void __queue_element_linkage_invalid(queue_entry_t e); |
216 | #else |
217 | #define __queue_element_linkage_invalid(e) __builtin_trap() |
218 | #endif |
219 | |
220 | static 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 | |
228 | static 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 | |
249 | static __inline__ void |
250 | enqueue_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 | |
264 | static __inline__ void |
265 | enqueue_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 | |
279 | static __inline__ queue_entry_t |
280 | dequeue_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 | |
298 | static __inline__ queue_entry_t |
299 | dequeue_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 | |
317 | static __inline__ void |
318 | remqueue( |
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 | |
331 | static __inline__ void |
332 | insque( |
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 | |
346 | static __inline__ void |
347 | remque( |
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 | */ |
364 | static __inline__ void |
365 | re_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 | */ |
397 | static __inline__ void |
398 | re_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) \ |
592 | MACRO_BEGIN \ |
593 | (q)->next = (q);\ |
594 | (q)->prev = (q);\ |
595 | MACRO_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 | */ |
696 | static __inline__ void |
697 | movqueue(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) \ |
753 | MACRO_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; \ |
768 | MACRO_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) \ |
784 | MACRO_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; \ |
798 | MACRO_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) \ |
815 | MACRO_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 | } \ |
842 | MACRO_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) \ |
859 | MACRO_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 | } \ |
886 | MACRO_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) \ |
910 | MACRO_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; \ |
928 | MACRO_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) \ |
942 | MACRO_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; \ |
956 | MACRO_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) \ |
970 | MACRO_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; \ |
984 | MACRO_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) \ |
992 | MACRO_BEGIN \ |
993 | ((type)(void *)((from)->prev))->field.next = (to); \ |
994 | ((type)(void *)((from)->next))->field.prev = (to); \ |
995 | *to = *from; \ |
996 | MACRO_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) \ |
1012 | MACRO_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 | } \ |
1022 | MACRO_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 | |