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
120typedef 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
140typedef 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
150typedef 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
161typedef 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
171typedef 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
184typedef 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
190typedef 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 */
202typedef 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
209typedef 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 */
226typedef 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 */
241struct priority_queue;
242
243/*
244 * Type of generic heaps
245 */
246struct priority_queue_min {
247 struct priority_queue_entry *pq_root;
248 priority_queue_compare_fn_t pq_cmp_fn;
249};
250struct 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 */
258struct priority_queue_deadline_min {
259 struct priority_queue_entry_deadline *pq_root;
260};
261struct priority_queue_deadline_max {
262 struct priority_queue_entry_deadline *pq_root;
263};
264
265/*
266 * Type of scheduler priority based heaps
267 */
268struct priority_queue_sched_min {
269 struct priority_queue_entry_sched *pq_root;
270};
271struct priority_queue_sched_max {
272 struct priority_queue_entry_sched *pq_root;
273};
274
275/*
276 * Type of scheduler priority based stable heaps
277 */
278struct priority_queue_sched_stable_min {
279 struct priority_queue_entry_stable *pq_root;
280};
281struct 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
369extern void
370priority_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) \
401MACRO_BEGIN \
402 void (^__callback)(type *) = (callback); /* type check */ \
403 _priority_queue_destroy(pq, offsetof(type, field), \
404 (void (^)(void *))(__callback)); \
405MACRO_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 */
457extern bool
458priority_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 */
506extern bool
507priority_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 */
527extern bool
528priority_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 */
547extern bool
548priority_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) \
583MACRO_BEGIN \
584 static_assert(priority_queue_is_sched_heap(pq), "is a sched heap"); \
585 (elt)->key = (priority_queue_key_t)(((pri) << 8) + (modifier)); \
586MACRO_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 \
675priority_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 \
681priority_queue_remove(pqueue_t que, pqelem_t elt); \
682 \
683__pqueue_overloadable extern bool \
684priority_queue_entry_decreased(pqueue_t que, pqelem_t elt); \
685 \
686__pqueue_overloadable extern bool \
687priority_queue_entry_increased(pqueue_t que, pqelem_t elt)
688
689#define PRIORITY_QUEUE_MAKE(pqueue_t, pqelem_t) \
690__pqueue_overloadable \
691static inline void \
692priority_queue_init(pqueue_t que) \
693{ \
694 __builtin_bzero(que, sizeof(*que)); \
695} \
696 \
697PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t)
698
699#define PRIORITY_QUEUE_MAKE_CB(pqueue_t, pqelem_t) \
700__pqueue_overloadable \
701static inline void \
702priority_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 \
708PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t)
709
710PRIORITY_QUEUE_MAKE_CB(struct priority_queue_min *, priority_queue_entry_t);
711PRIORITY_QUEUE_MAKE_CB(struct priority_queue_max *, priority_queue_entry_t);
712
713PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_min *, priority_queue_entry_deadline_t);
714PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_max *, priority_queue_entry_deadline_t);
715
716PRIORITY_QUEUE_MAKE(struct priority_queue_sched_min *, priority_queue_entry_sched_t);
717PRIORITY_QUEUE_MAKE(struct priority_queue_sched_max *, priority_queue_entry_sched_t);
718
719PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t);
720PRIORITY_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