1 | /* |
2 | * Copyright (c) 2018 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 | #ifndef _KERN_PRIORITY_QUEUE_H_ |
30 | #define _KERN_PRIORITY_QUEUE_H_ |
31 | |
32 | #if KERNEL |
33 | #include <kern/kern_types.h> |
34 | #include <kern/macro_help.h> |
35 | #include <kern/assert.h> |
36 | #endif |
37 | |
38 | #include <stdbool.h> |
39 | #include <sys/cdefs.h> |
40 | |
41 | #pragma GCC visibility push(hidden) |
42 | |
43 | __BEGIN_DECLS |
44 | |
45 | /* |
46 | * A generic priorty ordered queue implementation based on pairing heaps. |
47 | * |
48 | * Reference Papers: |
49 | * - A Back-to-Basics Empirical Study of Priority Queues (https://arxiv.org/abs/1403.0252) |
50 | * - The Pairing Heap: A New Form of Self-Adjusting Heap |
51 | * (https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf) |
52 | * |
53 | * The XNU implementation is a basic version of the pairing heap. |
54 | * It allows for O(1) insertion and amortized O(log n) deletion. |
55 | * |
56 | * It is not a stable data structure by default since adding stability would |
57 | * need more pointers and hence more memory. |
58 | * |
59 | * Type of queues |
60 | * |
61 | * There are several types of priority queues, with types named: |
62 | * |
63 | * struct priority_queue_<subtype>_<min|max> |
64 | * |
65 | * In the rest of this header, `struct priority_queue` is used as |
66 | * a generic type to mean any priority_queue type. |
67 | * |
68 | * min/max refers to whether the priority queue is a min or a max heap. |
69 | * |
70 | * the subtype can be: |
71 | * |
72 | * - sched, in which case the key is built in the linkage and assumed to |
73 | * be a scheduler priority. |
74 | * |
75 | * - sched_stable, in which case the key is a combination of: |
76 | * * a scheduler priority |
77 | * * whether the entry was preempted or not |
78 | * * a timestamp. |
79 | * |
80 | * - generic, in which case a comparison function must be passed to |
81 | * the priority_queue_init. |
82 | * |
83 | * Element Linkage: |
84 | * |
85 | * Both types use a common queue head and linkage pattern. |
86 | * The head of a priority queue is declared as: |
87 | * |
88 | * struct priority_queue_<subtype>_<min|max> pq_head; |
89 | * |
90 | * Elements in this queue are linked together using one of the struct |
91 | * priority_queue_entry_<subtype> objects embedded within a structure: |
92 | * |
93 | * struct some_data { |
94 | * int field1; |
95 | * int field2; |
96 | * ... |
97 | * struct priority_queue_entry link; |
98 | * ... |
99 | * int last_field; |
100 | * }; |
101 | * struct some_data is referred to as the queue "element" |
102 | * |
103 | * This method uses the next, prev and child pointers of the struct |
104 | * priority_queue_entry linkage object embedded in a queue element to |
105 | * point to other elements in the queue. The head of the priority queue |
106 | * (the priority_queue object) will point to the root of the pairing |
107 | * heap (NULL if heap is empty). This method allows multiple chains |
108 | * through a given object, by embedding multiple priority_queue_entry |
109 | * objects in the structure, while simultaneously providing fast removal |
110 | * and insertion into the heap using only priority_queue_entry object |
111 | * pointers. |
112 | */ |
113 | |
114 | |
115 | /* |
116 | * Priority keys maintained by the data structure. |
117 | * Since the priority is packed in the node itself, it restricts keys to be 16-bits only. |
118 | */ |
119 | #define PRIORITY_QUEUE_KEY_NONE 0 |
120 | typedef uint16_t priority_queue_key_t; |
121 | |
122 | #ifdef __LP64__ |
123 | |
124 | /* |
125 | * For 64-bit platforms, pack the priority key into the child pointer |
126 | * The packing/unpacking is done using a compiler trick to sign extend long. |
127 | * This avoids additional NULL checks which are needed in typical packing |
128 | * implementation. The idea is to define the packed location as a long and |
129 | * for unpacking simply cast it to a full pointer which sign extends it. |
130 | */ |
131 | #if CONFIG_KERNEL_TAGGING |
132 | #define PRIORITY_QUEUE_ENTRY_CHILD_BITS 44 |
133 | #define PRIORITY_QUEUE_ENTRY_TAG_BITS 4 |
134 | #define PRIORITY_QUEUE_ENTRY_KEY_BITS 16 |
135 | #else /* CONFIG_KERNEL_TAGGING */ |
136 | #define PRIORITY_QUEUE_ENTRY_CHILD_BITS 48 |
137 | #define PRIORITY_QUEUE_ENTRY_KEY_BITS 16 |
138 | #endif /* CONFIG_KERNEL_TAGGING */ |
139 | |
140 | typedef struct priority_queue_entry { |
141 | struct priority_queue_entry *next; |
142 | struct priority_queue_entry *prev; |
143 | long __key: PRIORITY_QUEUE_ENTRY_KEY_BITS; |
144 | #if CONFIG_KERNEL_TAGGING |
145 | unsigned long tag: PRIORITY_QUEUE_ENTRY_TAG_BITS; |
146 | #endif /* CONFIG_KERNEL_TAGGING */ |
147 | long child: PRIORITY_QUEUE_ENTRY_CHILD_BITS; |
148 | } *priority_queue_entry_t; |
149 | |
150 | typedef struct priority_queue_entry_deadline { |
151 | struct priority_queue_entry_deadline *next; |
152 | struct priority_queue_entry_deadline *prev; |
153 | long __key: PRIORITY_QUEUE_ENTRY_KEY_BITS; |
154 | #if CONFIG_KERNEL_TAGGING |
155 | unsigned long tag: PRIORITY_QUEUE_ENTRY_TAG_BITS; |
156 | #endif /* CONFIG_KERNEL_TAGGING */ |
157 | long child: PRIORITY_QUEUE_ENTRY_CHILD_BITS; |
158 | uint64_t deadline; |
159 | } *priority_queue_entry_deadline_t; |
160 | |
161 | typedef struct priority_queue_entry_sched { |
162 | struct priority_queue_entry_sched *next; |
163 | struct priority_queue_entry_sched *prev; |
164 | long key: PRIORITY_QUEUE_ENTRY_KEY_BITS; |
165 | #if CONFIG_KERNEL_TAGGING |
166 | unsigned long tag: PRIORITY_QUEUE_ENTRY_TAG_BITS; |
167 | #endif /* CONFIG_KERNEL_TAGGING */ |
168 | long child: PRIORITY_QUEUE_ENTRY_CHILD_BITS; |
169 | } *priority_queue_entry_sched_t; |
170 | |
171 | typedef struct priority_queue_entry_stable { |
172 | struct priority_queue_entry_stable *next; |
173 | struct priority_queue_entry_stable *prev; |
174 | long key: PRIORITY_QUEUE_ENTRY_KEY_BITS; |
175 | #if CONFIG_KERNEL_TAGGING |
176 | unsigned long tag: PRIORITY_QUEUE_ENTRY_TAG_BITS; |
177 | #endif /* CONFIG_KERNEL_TAGGING */ |
178 | long child: PRIORITY_QUEUE_ENTRY_CHILD_BITS; |
179 | uint64_t stamp; |
180 | } *priority_queue_entry_stable_t; |
181 | |
182 | #else /* __LP64__ */ |
183 | |
184 | typedef struct priority_queue_entry { |
185 | struct priority_queue_entry *next; |
186 | struct priority_queue_entry *prev; |
187 | long child; |
188 | } *priority_queue_entry_t; |
189 | |
190 | typedef struct priority_queue_entry_deadline { |
191 | struct priority_queue_entry_deadline *next; |
192 | struct priority_queue_entry_deadline *prev; |
193 | long child; |
194 | uint64_t deadline; |
195 | } *priority_queue_entry_deadline_t; |
196 | |
197 | /* |
198 | * For 32-bit platforms, use an extra field to store the key since child pointer packing |
199 | * is not an option. The child is maintained as a long to use the same packing/unpacking |
200 | * routines that work for 64-bit platforms. |
201 | */ |
202 | typedef struct priority_queue_entry_sched { |
203 | struct priority_queue_entry_sched *next; |
204 | struct priority_queue_entry_sched *prev; |
205 | long child; |
206 | priority_queue_key_t key; |
207 | } *priority_queue_entry_sched_t; |
208 | |
209 | typedef struct priority_queue_entry_stable { |
210 | struct priority_queue_entry_stable *next; |
211 | struct priority_queue_entry_stable *prev; |
212 | long child; |
213 | priority_queue_key_t key; |
214 | uint64_t stamp; |
215 | } *priority_queue_entry_stable_t; |
216 | |
217 | #endif /* __LP64__ */ |
218 | |
219 | /* |
220 | * Comparator block prototype |
221 | * Args: |
222 | * - elements to compare |
223 | * Return: |
224 | * comparision result to indicate relative ordering of elements according to the heap type |
225 | */ |
226 | typedef int (^priority_queue_compare_fn_t)(struct priority_queue_entry *e1, |
227 | struct priority_queue_entry *e2); |
228 | |
229 | #define priority_heap_compare_ints(a, b) ((a) < (b) ? 1 : -1) |
230 | |
231 | #define priority_heap_make_comparator(name1, name2, type, field, ...) \ |
232 | (^int(priority_queue_entry_t __e1, priority_queue_entry_t __e2){ \ |
233 | type *name1 = pqe_element_fast(__e1, type, field); \ |
234 | type *name2 = pqe_element_fast(__e2, type, field); \ |
235 | __VA_ARGS__; \ |
236 | }) |
237 | |
238 | /* |
239 | * Type for any priority queue, only used for documentation purposes. |
240 | */ |
241 | struct priority_queue; |
242 | |
243 | /* |
244 | * Type of generic heaps |
245 | */ |
246 | struct priority_queue_min { |
247 | struct priority_queue_entry *pq_root; |
248 | priority_queue_compare_fn_t pq_cmp_fn; |
249 | }; |
250 | struct priority_queue_max { |
251 | struct priority_queue_entry *pq_root; |
252 | priority_queue_compare_fn_t pq_cmp_fn; |
253 | }; |
254 | |
255 | /* |
256 | * Type of deadline heaps |
257 | */ |
258 | struct priority_queue_deadline_min { |
259 | struct priority_queue_entry_deadline *pq_root; |
260 | }; |
261 | struct priority_queue_deadline_max { |
262 | struct priority_queue_entry_deadline *pq_root; |
263 | }; |
264 | |
265 | /* |
266 | * Type of scheduler priority based heaps |
267 | */ |
268 | struct priority_queue_sched_min { |
269 | struct priority_queue_entry_sched *pq_root; |
270 | }; |
271 | struct priority_queue_sched_max { |
272 | struct priority_queue_entry_sched *pq_root; |
273 | }; |
274 | |
275 | /* |
276 | * Type of scheduler priority based stable heaps |
277 | */ |
278 | struct priority_queue_sched_stable_min { |
279 | struct priority_queue_entry_stable *pq_root; |
280 | }; |
281 | struct priority_queue_sched_stable_max { |
282 | struct priority_queue_entry_stable *pq_root; |
283 | }; |
284 | |
285 | #pragma mark generic interface |
286 | |
287 | #define PRIORITY_QUEUE_INITIALIZER { .pq_root = NULL } |
288 | |
289 | #define __pqueue_overloadable __attribute__((overloadable)) |
290 | |
291 | #define priority_queue_is_min_heap(pq) _Generic(pq, \ |
292 | struct priority_queue_min *: true, \ |
293 | struct priority_queue_max *: false, \ |
294 | struct priority_queue_deadline_min *: true, \ |
295 | struct priority_queue_deadline_max *: false, \ |
296 | struct priority_queue_sched_min *: true, \ |
297 | struct priority_queue_sched_max *: false, \ |
298 | struct priority_queue_sched_stable_min *: true, \ |
299 | struct priority_queue_sched_stable_max *: false) |
300 | |
301 | #define priority_queue_is_max_heap(pq) \ |
302 | (!priority_queue_is_min_heap(pq)) |
303 | |
304 | /* |
305 | * Macro: pqe_element_fast |
306 | * Function: |
307 | * Convert a priority_queue_entry_t to a queue element pointer. |
308 | * Get a pointer to the user-defined element containing |
309 | * a given priority_queue_entry_t |
310 | * |
311 | * The fast variant assumes that `qe` is not NULL |
312 | * Header: |
313 | * pqe_element_fast(qe, type, field) |
314 | * <priority_queue_entry_t> qe |
315 | * <type> type of element in priority queue |
316 | * <field> chain field in (*<type>) |
317 | * Returns: |
318 | * <type *> containing qe |
319 | */ |
320 | #define pqe_element_fast(qe, type, field) __container_of(qe, type, field) |
321 | |
322 | /* |
323 | * Macro: pqe_element |
324 | * Function: |
325 | * Convert a priority_queue_entry_t to a queue element pointer. |
326 | * Get a pointer to the user-defined element containing |
327 | * a given priority_queue_entry_t |
328 | * |
329 | * The non fast variant handles NULL `qe` |
330 | * Header: |
331 | * pqe_element(qe, type, field) |
332 | * <priority_queue_entry_t> qe |
333 | * <type> type of element in priority queue |
334 | * <field> chain field in (*<type>) |
335 | * Returns: |
336 | * <type *> containing qe |
337 | */ |
338 | #define pqe_element(qe, type, field) ({ \ |
339 | __auto_type _tmp_entry = (qe); \ |
340 | _tmp_entry ? pqe_element_fast(_tmp_entry, type, field) : ((type *)NULL);\ |
341 | }) |
342 | |
343 | /* |
344 | * Priority Queue functionality routines |
345 | */ |
346 | |
347 | /* |
348 | * Macro: priority_queue_empty |
349 | * Function: |
350 | * Tests whether a priority queue is empty. |
351 | * Header: |
352 | * boolean_t priority_queue_empty(pq) |
353 | * <struct priority_queue *> pq |
354 | */ |
355 | #define priority_queue_empty(pq) ((pq)->pq_root == NULL) |
356 | |
357 | /* |
358 | * Macro: priority_queue_init |
359 | * Function: |
360 | * Initialize a <struct priority_queue *>. |
361 | * Header: |
362 | * priority_queue_init(pq) |
363 | * <struct priority_queue *> pq |
364 | * (optional) <cmp_fn> comparator function |
365 | * Returns: |
366 | * None |
367 | */ |
368 | __pqueue_overloadable |
369 | extern void |
370 | priority_queue_init(struct priority_queue *pq, ...); |
371 | |
372 | /* |
373 | * Macro: priority_queue_entry_init |
374 | * Function: |
375 | * Initialize a priority_queue_entry_t |
376 | * Header: |
377 | * priority_queue_entry_init(qe) |
378 | * <priority_queue_entry_t> qe |
379 | * Returns: |
380 | * None |
381 | */ |
382 | #define priority_queue_entry_init(qe) \ |
383 | __builtin_bzero(qe, sizeof(*(qe))) |
384 | |
385 | /* |
386 | * Macro: priority_queue_destroy |
387 | * Function: |
388 | * Destroy a priority queue safely. This routine accepts a callback |
389 | * to handle any cleanup for elements in the priority queue. The queue does |
390 | * not maintain its invariants while getting destroyed. The priority queue and |
391 | * the linkage nodes need to be re-initialized before re-using them. |
392 | * Header: |
393 | * priority_queue_destroy(pq, type, field, callback) |
394 | * <struct priority_queue *> pq |
395 | * <callback> callback for each element |
396 | * |
397 | * Returns: |
398 | * None |
399 | */ |
400 | #define priority_queue_destroy(pq, type, field, callback) \ |
401 | MACRO_BEGIN \ |
402 | void (^__callback)(type *) = (callback); /* type check */ \ |
403 | _priority_queue_destroy(pq, offsetof(type, field), \ |
404 | (void (^)(void *))(__callback)); \ |
405 | MACRO_END |
406 | |
407 | /* |
408 | * Macro: priority_queue_min |
409 | * Function: |
410 | * Lookup the minimum in a min-priority queue. |
411 | * |
412 | * Header: |
413 | * priority_queue_min(pq, type, field) |
414 | * <struct priority_queue *> pq |
415 | * <type> type of element in priority queue |
416 | * <field> chain field in (*<type>) |
417 | * Returns: |
418 | * <type *> root element |
419 | */ |
420 | #define priority_queue_min(pq, type, field) ({ \ |
421 | static_assert(priority_queue_is_min_heap(pq), "queue is min heap"); \ |
422 | pqe_element((pq)->pq_root, type, field); \ |
423 | }) |
424 | |
425 | /* |
426 | * Macro: priority_queue_max |
427 | * Function: |
428 | * Lookup the maximum element in a max-priority queue. |
429 | * |
430 | * Header: |
431 | * priority_queue_max(pq, type, field) |
432 | * <struct priority_queue *> pq |
433 | * <type> type of element in priority queue |
434 | * <field> chain field in (*<type>) |
435 | * Returns: |
436 | * <type *> root element |
437 | */ |
438 | #define priority_queue_max(pq, type, field) ({ \ |
439 | static_assert(priority_queue_is_max_heap(pq), "queue is max heap"); \ |
440 | pqe_element((pq)->pq_root, type, field); \ |
441 | }) |
442 | |
443 | /* |
444 | * Macro: priority_queue_insert |
445 | * Function: |
446 | * Insert an element into the priority queue |
447 | * |
448 | * The caller must have set the key prio to insertion |
449 | * |
450 | * Header: |
451 | * priority_queue_insert(pq, elt, new_key) |
452 | * <struct priority_queue *> pq |
453 | * <priority_queue_entry_t> elt |
454 | * Returns: |
455 | * Whether the inserted element became the new root |
456 | */ |
457 | extern bool |
458 | priority_queue_insert(struct priority_queue *pq, |
459 | struct priority_queue_entry *elt) __pqueue_overloadable; |
460 | |
461 | /* |
462 | * Macro: priority_queue_remove_min |
463 | * Function: |
464 | * Remove the minimum element in a min-heap priority queue. |
465 | * Header: |
466 | * priority_queue_remove_min(pq, type, field) |
467 | * <struct priority_queue *> pq |
468 | * <type> type of element in priority queue |
469 | * <field> chain field in (*<type>) |
470 | * Returns: |
471 | * <type *> max element |
472 | */ |
473 | #define priority_queue_remove_min(pq, type, field) ({ \ |
474 | static_assert(priority_queue_is_min_heap(pq), "queue is min heap"); \ |
475 | pqe_element(_priority_queue_remove_root(pq), type, field); \ |
476 | }) |
477 | |
478 | /* |
479 | * Macro: priority_queue_remove_max |
480 | * Function: |
481 | * Remove the maximum element in a max-heap priority queue. |
482 | * Header: |
483 | * priority_queue_remove_max(pq, type, field) |
484 | * <struct priority_queue *> pq |
485 | * <type> type of element in priority queue |
486 | * <field> chain field in (*<type>) |
487 | * Returns: |
488 | * <type *> max element |
489 | */ |
490 | #define priority_queue_remove_max(pq, type, field) ({ \ |
491 | static_assert(priority_queue_is_max_heap(pq), "queue is max heap"); \ |
492 | pqe_element(_priority_queue_remove_root(pq), type, field); \ |
493 | }) |
494 | |
495 | /* |
496 | * Macro: priority_queue_remove |
497 | * Function: |
498 | * Removes an element from the priority queue |
499 | * Header: |
500 | * priority_queue_remove(pq, elt) |
501 | * <struct priority_queue *> pq |
502 | * <priority_queue_entry_t> elt |
503 | * Returns: |
504 | * Whether the removed element was the root |
505 | */ |
506 | extern bool |
507 | priority_queue_remove(struct priority_queue *pq, |
508 | struct priority_queue_entry *elt) __pqueue_overloadable; |
509 | |
510 | |
511 | /* |
512 | * Macro: priority_queue_entry_decreased |
513 | * |
514 | * Function: |
515 | * Signal the priority queue that the entry priority has decreased. |
516 | * |
517 | * The new value for the element priority must have been set |
518 | * prior to calling this function. |
519 | * |
520 | * Header: |
521 | * priority_queue_entry_decreased(pq, elt) |
522 | * <struct priority_queue *> pq |
523 | * <priority_queue_entry_t> elt |
524 | * Returns: |
525 | * Whether the update caused the root or its key to change. |
526 | */ |
527 | extern bool |
528 | priority_queue_entry_decreased(struct priority_queue *pq, |
529 | struct priority_queue_entry *elt) __pqueue_overloadable; |
530 | |
531 | /* |
532 | * Macro: priority_queue_entry_increased |
533 | * |
534 | * Function: |
535 | * Signal the priority queue that the entry priority has increased. |
536 | * |
537 | * The new value for the element priority must have been set |
538 | * prior to calling this function. |
539 | * |
540 | * Header: |
541 | * priority_queue_entry_increased(pq, elt, new_key) |
542 | * <struct priority_queue *> pq |
543 | * <priority_queue_entry_t> elt |
544 | * Returns: |
545 | * Whether the update caused the root or its key to change. |
546 | */ |
547 | extern bool |
548 | priority_queue_entry_increased(struct priority_queue *pq, |
549 | struct priority_queue_entry *elt) __pqueue_overloadable; |
550 | |
551 | |
552 | #pragma mark priority_queue_sched_* |
553 | |
554 | __enum_decl(priority_queue_entry_sched_modifier_t, uint8_t, { |
555 | PRIORITY_QUEUE_ENTRY_NONE = 0, |
556 | PRIORITY_QUEUE_ENTRY_PREEMPTED = 1, |
557 | }); |
558 | |
559 | #define priority_queue_is_sched_heap(pq) _Generic(pq, \ |
560 | struct priority_queue_sched_min *: true, \ |
561 | struct priority_queue_sched_max *: true, \ |
562 | struct priority_queue_sched_stable_min *: true, \ |
563 | struct priority_queue_sched_stable_max *: true, \ |
564 | default: false) |
565 | |
566 | /* |
567 | * Macro: priority_queue_entry_set_sched_pri |
568 | * |
569 | * Function: |
570 | * Sets the scheduler priority on an entry supporting this concept. |
571 | * |
572 | * The priority is expected to fit on 8 bits. |
573 | * An optional sorting modifier. |
574 | * |
575 | * Header: |
576 | * priority_queue_entry_set_sched_pri(pq, elt, pri, modifier) |
577 | * <struct priority_queue *> pq |
578 | * <priority_queue_entry_t> elt |
579 | * <uint8_t> pri |
580 | * <priority_queue_entry_sched_modifier_t> modifier |
581 | */ |
582 | #define priority_queue_entry_set_sched_pri(pq, elt, pri, modifier) \ |
583 | MACRO_BEGIN \ |
584 | static_assert(priority_queue_is_sched_heap(pq), "is a sched heap"); \ |
585 | (elt)->key = (priority_queue_key_t)(((pri) << 8) + (modifier)); \ |
586 | MACRO_END |
587 | |
588 | /* |
589 | * Macro: priority_queue_entry_sched_pri |
590 | * |
591 | * Function: |
592 | * Return the scheduler priority on an entry supporting this |
593 | * concept. |
594 | * |
595 | * Header: |
596 | * priority_queue_entry_sched_pri(pq, elt) |
597 | * <struct priority_queue *> pq |
598 | * <priority_queue_entry_t> elt |
599 | * |
600 | * Returns: |
601 | * The scheduler priority of this entry |
602 | */ |
603 | #define priority_queue_entry_sched_pri(pq, elt) ({ \ |
604 | static_assert(priority_queue_is_sched_heap(pq), "is a sched heap"); \ |
605 | (priority_queue_key_t)((elt)->key >> 8); \ |
606 | }) |
607 | |
608 | /* |
609 | * Macro: priority_queue_entry_sched_modifier |
610 | * |
611 | * Function: |
612 | * Return the scheduler modifier on an entry supporting this |
613 | * concept. |
614 | * |
615 | * Header: |
616 | * priority_queue_entry_sched_modifier(pq, elt) |
617 | * <struct priority_queue *> pq |
618 | * <priority_queue_entry_t> elt |
619 | * |
620 | * Returns: |
621 | * The scheduler priority of this entry |
622 | */ |
623 | #define priority_queue_entry_sched_modifier(pq, elt) ({ \ |
624 | static_assert(priority_queue_is_sched_heap(pq), "is a sched heap"); \ |
625 | (priority_queue_entry_sched_modifier_t)(elt)->key; \ |
626 | }) |
627 | |
628 | /* |
629 | * Macro: priority_queue_min_sched_pri |
630 | * |
631 | * Function: |
632 | * Return the scheduler priority of the minimum element |
633 | * of a scheduler priority queue. |
634 | * |
635 | * Header: |
636 | * priority_queue_min_sched_pri(pq) |
637 | * <struct priority_queue *> pq |
638 | * |
639 | * Returns: |
640 | * The scheduler priority of this entry |
641 | */ |
642 | #define priority_queue_min_sched_pri(pq) ({ \ |
643 | static_assert(priority_queue_is_min_heap(pq), "queue is min heap"); \ |
644 | priority_queue_entry_sched_pri(pq, (pq)->pq_root); \ |
645 | }) |
646 | |
647 | /* |
648 | * Macro: priority_queue_max_sched_pri |
649 | * |
650 | * Function: |
651 | * Return the scheduler priority of the maximum element |
652 | * of a scheduler priority queue. |
653 | * |
654 | * Header: |
655 | * priority_queue_max_sched_pri(pq) |
656 | * <struct priority_queue *> pq |
657 | * |
658 | * Returns: |
659 | * The scheduler priority of this entry |
660 | */ |
661 | #define priority_queue_max_sched_pri(pq) ({ \ |
662 | static_assert(priority_queue_is_max_heap(pq), "queue is max heap"); \ |
663 | priority_queue_entry_sched_pri(pq, (pq)->pq_root); \ |
664 | }) |
665 | |
666 | |
667 | #pragma mark implementation details |
668 | |
669 | #define PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t) \ |
670 | \ |
671 | __pqueue_overloadable extern void \ |
672 | _priority_queue_destroy(pqueue_t pq, uintptr_t offset, void (^cb)(void *)); \ |
673 | \ |
674 | __pqueue_overloadable extern bool \ |
675 | priority_queue_insert(pqueue_t que, pqelem_t elt); \ |
676 | \ |
677 | __pqueue_overloadable extern pqelem_t \ |
678 | _priority_queue_remove_root(pqueue_t que); \ |
679 | \ |
680 | __pqueue_overloadable extern bool \ |
681 | priority_queue_remove(pqueue_t que, pqelem_t elt); \ |
682 | \ |
683 | __pqueue_overloadable extern bool \ |
684 | priority_queue_entry_decreased(pqueue_t que, pqelem_t elt); \ |
685 | \ |
686 | __pqueue_overloadable extern bool \ |
687 | priority_queue_entry_increased(pqueue_t que, pqelem_t elt) |
688 | |
689 | #define PRIORITY_QUEUE_MAKE(pqueue_t, pqelem_t) \ |
690 | __pqueue_overloadable \ |
691 | static inline void \ |
692 | priority_queue_init(pqueue_t que) \ |
693 | { \ |
694 | __builtin_bzero(que, sizeof(*que)); \ |
695 | } \ |
696 | \ |
697 | PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t) |
698 | |
699 | #define PRIORITY_QUEUE_MAKE_CB(pqueue_t, pqelem_t) \ |
700 | __pqueue_overloadable \ |
701 | static inline void \ |
702 | priority_queue_init(pqueue_t pq, priority_queue_compare_fn_t cmp_fn) \ |
703 | { \ |
704 | pq->pq_root = NULL; \ |
705 | pq->pq_cmp_fn = cmp_fn; \ |
706 | } \ |
707 | \ |
708 | PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t) |
709 | |
710 | PRIORITY_QUEUE_MAKE_CB(struct priority_queue_min *, priority_queue_entry_t); |
711 | PRIORITY_QUEUE_MAKE_CB(struct priority_queue_max *, priority_queue_entry_t); |
712 | |
713 | PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_min *, priority_queue_entry_deadline_t); |
714 | PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_max *, priority_queue_entry_deadline_t); |
715 | |
716 | PRIORITY_QUEUE_MAKE(struct priority_queue_sched_min *, priority_queue_entry_sched_t); |
717 | PRIORITY_QUEUE_MAKE(struct priority_queue_sched_max *, priority_queue_entry_sched_t); |
718 | |
719 | PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t); |
720 | PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t); |
721 | |
722 | __END_DECLS |
723 | |
724 | #pragma GCC visibility pop |
725 | |
726 | #endif /* _KERN_PRIORITY_QUEUE_H_ */ |
727 | |