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