osfmk/kern/priority_queue.h

   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 #define PRIORITY_QUEUE_ENTRY_CHILD_BITS     48
 132 #define PRIORITY_QUEUE_ENTRY_KEY_BITS       16
 133
 134 typedef struct priority_queue_entry {
 135         struct priority_queue_entry        *next;
 136         struct priority_queue_entry        *prev;
 137         long                                __key: PRIORITY_QUEUE_ENTRY_KEY_BITS;
 138         long                                child: PRIORITY_QUEUE_ENTRY_CHILD_BITS;
 139 } *priority_queue_entry_t;
 140
 141 typedef struct priority_queue_entry_deadline {
 142         struct priority_queue_entry_deadline *next;
 143         struct priority_queue_entry_deadline *prev;
 144         long                                  __key: PRIORITY_QUEUE_ENTRY_KEY_BITS;
 145         long                                  child: PRIORITY_QUEUE_ENTRY_CHILD_BITS;
 146         uint64_t                              deadline;
 147 } *priority_queue_entry_deadline_t;
 148
 149 typedef struct priority_queue_entry_sched {
 150         struct priority_queue_entry_sched  *next;
 151         struct priority_queue_entry_sched  *prev;
 152         long                                key: PRIORITY_QUEUE_ENTRY_KEY_BITS;
 153         long                                child: PRIORITY_QUEUE_ENTRY_CHILD_BITS;
 154 } *priority_queue_entry_sched_t;
 155
 156 typedef struct priority_queue_entry_stable {
 157         struct priority_queue_entry_stable *next;
 158         struct priority_queue_entry_stable *prev;
 159         long                                key: PRIORITY_QUEUE_ENTRY_KEY_BITS;
 160         long                                child: PRIORITY_QUEUE_ENTRY_CHILD_BITS;
 161         uint64_t                            stamp;
 162 } *priority_queue_entry_stable_t;
 163
 164 #else /* __LP64__ */
 165
 166 typedef struct priority_queue_entry {
 167         struct priority_queue_entry        *next;
 168         struct priority_queue_entry        *prev;
 169         long                                child;
 170 } *priority_queue_entry_t;
 171
 172 typedef struct priority_queue_entry_deadline {
 173         struct priority_queue_entry_deadline *next;
 174         struct priority_queue_entry_deadline *prev;
 175         long                                  child;
 176         uint64_t                              deadline;
 177 } *priority_queue_entry_deadline_t;
 178
 179 /*
 180  * For 32-bit platforms, use an extra field to store the key since child pointer packing
 181  * is not an option. The child is maintained as a long to use the same packing/unpacking
 182  * routines that work for 64-bit platforms.
 183  */
 184 typedef struct priority_queue_entry_sched {
 185         struct priority_queue_entry_sched  *next;
 186         struct priority_queue_entry_sched  *prev;
 187         long                                child;
 188         priority_queue_key_t                key;
 189 } *priority_queue_entry_sched_t;
 190
 191 typedef struct priority_queue_entry_stable {
 192         struct priority_queue_entry_stable *next;
 193         struct priority_queue_entry_stable *prev;
 194         long                                child;
 195         priority_queue_key_t                key;
 196         uint64_t                            stamp;
 197 } *priority_queue_entry_stable_t;
 198
 199 #endif /* __LP64__ */
 200
 201 /*
 202  * Comparator block prototype
 203  * Args:
 204  *      - elements to compare
 205  * Return:
 206  * comparision result to indicate relative ordering of elements according to the heap type
 207  */
 208 typedef int (^priority_queue_compare_fn_t)(struct priority_queue_entry *e1,
 209     struct priority_queue_entry *e2);
 210
 211 #define priority_heap_compare_ints(a, b) ((a) < (b) ? 1 : -1)
 212
 213 #define priority_heap_make_comparator(name1, name2, type, field, ...) \
 214         (^int(priority_queue_entry_t __e1, priority_queue_entry_t __e2){        \
 215             type *name1 = pqe_element_fast(__e1, type, field);                  \
 216             type *name2 = pqe_element_fast(__e2, type, field);                  \
 217             __VA_ARGS__;                                                        \
 218         })
 219
 220 /*
 221  * Type for any priority queue, only used for documentation purposes.
 222  */
 223 struct priority_queue;
 224
 225 /*
 226  * Type of generic heaps
 227  */
 228 struct priority_queue_min {
 229         struct priority_queue_entry *pq_root;
 230         priority_queue_compare_fn_t  pq_cmp_fn;
 231 };
 232 struct priority_queue_max {
 233         struct priority_queue_entry *pq_root;
 234         priority_queue_compare_fn_t  pq_cmp_fn;
 235 };
 236
 237 /*
 238  * Type of deadline heaps
 239  */
 240 struct priority_queue_deadline_min {
 241         struct priority_queue_entry_deadline *pq_root;
 242 };
 243 struct priority_queue_deadline_max {
 244         struct priority_queue_entry_deadline *pq_root;
 245 };
 246
 247 /*
 248  * Type of scheduler priority based heaps
 249  */
 250 struct priority_queue_sched_min {
 251         struct priority_queue_entry_sched *pq_root;
 252 };
 253 struct priority_queue_sched_max {
 254         struct priority_queue_entry_sched *pq_root;
 255 };
 256
 257 /*
 258  * Type of scheduler priority based stable heaps
 259  */
 260 struct priority_queue_sched_stable_min {
 261         struct priority_queue_entry_stable *pq_root;
 262 };
 263 struct priority_queue_sched_stable_max {
 264         struct priority_queue_entry_stable *pq_root;
 265 };
 266
 267 #pragma mark generic interface
 268
 269 #define PRIORITY_QUEUE_INITIALIZER { .pq_root = NULL }
 270
 271 #define __pqueue_overloadable  __attribute__((overloadable))
 272
 273 #define priority_queue_is_min_heap(pq) _Generic(pq, \
 274         struct priority_queue_min *: true, \
 275         struct priority_queue_max *: false, \
 276         struct priority_queue_deadline_min *: true, \
 277         struct priority_queue_deadline_max *: false, \
 278         struct priority_queue_sched_min *: true, \
 279         struct priority_queue_sched_max *: false, \
 280         struct priority_queue_sched_stable_min *: true, \
 281         struct priority_queue_sched_stable_max *: false)
 282
 283 #define priority_queue_is_max_heap(pq) \
 284         (!priority_queue_is_min_heap(pq))
 285
 286 /*
 287  *      Macro:          pqe_element_fast
 288  *      Function:
 289  *              Convert a priority_queue_entry_t to a queue element pointer.
 290  *              Get a pointer to the user-defined element containing
 291  *              a given priority_queue_entry_t
 292  *
 293  *              The fast variant assumes that `qe` is not NULL
 294  *      Header:
 295  *              pqe_element_fast(qe, type, field)
 296  *                      <priority_queue_entry_t> qe
 297  *                      <type> type of element in priority queue
 298  *                      <field> chain field in (*<type>)
 299  *      Returns:
 300  *              <type *> containing qe
 301  */
 302 #define pqe_element_fast(qe, type, field)  __container_of(qe, type, field)
 303
 304 /*
 305  *      Macro:          pqe_element
 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 non fast variant handles NULL `qe`
 312  *      Header:
 313  *              pqe_element(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(qe, type, field)  ({                                        \
 321         __auto_type _tmp_entry = (qe);                                          \
 322         _tmp_entry ? pqe_element_fast(_tmp_entry, type, field) : ((type *)NULL);\
 323 })
 324
 325 /*
 326  * Priority Queue functionality routines
 327  */
 328
 329 /*
 330  *      Macro:          priority_queue_empty
 331  *      Function:
 332  *              Tests whether a priority queue is empty.
 333  *      Header:
 334  *              boolean_t priority_queue_empty(pq)
 335  *                      <struct priority_queue *> pq
 336  */
 337 #define priority_queue_empty(pq)         ((pq)->pq_root == NULL)
 338
 339 /*
 340  *      Macro:          priority_queue_init
 341  *      Function:
 342  *              Initialize a <struct priority_queue *>.
 343  *      Header:
 344  *              priority_queue_init(pq)
 345  *                      <struct priority_queue *> pq
 346  *                      (optional) <cmp_fn> comparator function
 347  *      Returns:
 348  *              None
 349  */
 350 __pqueue_overloadable
 351 extern void
 352 priority_queue_init(struct priority_queue *pq, ...);
 353
 354 /*
 355  *      Macro:          priority_queue_entry_init
 356  *      Function:
 357  *              Initialize a priority_queue_entry_t
 358  *      Header:
 359  *              priority_queue_entry_init(qe)
 360  *                      <priority_queue_entry_t> qe
 361  *      Returns:
 362  *              None
 363  */
 364 #define priority_queue_entry_init(qe) \
 365         __builtin_bzero(qe, sizeof(*(qe)))
 366
 367 /*
 368  *      Macro:          priority_queue_destroy
 369  *      Function:
 370  *              Destroy a priority queue safely. This routine accepts a callback
 371  *              to handle any cleanup for elements in the priority queue. The queue does
 372  *              not maintain its invariants while getting destroyed. The priority queue and
 373  *              the linkage nodes need to be re-initialized before re-using them.
 374  *      Header:
 375  *              priority_queue_destroy(pq, type, field, callback)
 376  *                      <struct priority_queue *> pq
 377  *                      <callback> callback for each element
 378  *
 379  *      Returns:
 380  *              None
 381  */
 382 #define priority_queue_destroy(pq, type, field, callback)                       \
 383 MACRO_BEGIN                                                                     \
 384         void (^__callback)(type *) = (callback); /* type check */               \
 385         _priority_queue_destroy(pq, offsetof(type, field),                      \
 386             (void (^)(void *))(__callback));                                    \
 387 MACRO_END
 388
 389 /*
 390  *      Macro:          priority_queue_min
 391  *      Function:
 392  *              Lookup the minimum in a min-priority queue.
 393  *
 394  *      Header:
 395  *              priority_queue_min(pq, type, field)
 396  *                      <struct priority_queue *> pq
 397  *                      <type> type of element in priority queue
 398  *                      <field> chain field in (*<type>)
 399  *      Returns:
 400  *              <type *> root element
 401  */
 402 #define priority_queue_min(pq, type, field) ({                                  \
 403         static_assert(priority_queue_is_min_heap(pq), "queue is min heap");     \
 404         pqe_element((pq)->pq_root, type, field);                                \
 405 })
 406
 407 /*
 408  *      Macro:          priority_queue_max
 409  *      Function:
 410  *              Lookup the maximum element in a max-priority queue.
 411  *
 412  *      Header:
 413  *              priority_queue_max(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_max(pq, type, field) ({                                  \
 421         static_assert(priority_queue_is_max_heap(pq), "queue is max heap");     \
 422         pqe_element((pq)->pq_root, type, field);                                \
 423 })
 424
 425 /*
 426  *      Macro:          priority_queue_insert
 427  *      Function:
 428  *              Insert an element into the priority queue
 429  *
 430  *              The caller must have set the key prio to insertion
 431  *
 432  *      Header:
 433  *              priority_queue_insert(pq, elt, new_key)
 434  *                      <struct priority_queue *> pq
 435  *                      <priority_queue_entry_t> elt
 436  *      Returns:
 437  *              Whether the inserted element became the new root
 438  */
 439 extern bool
 440 priority_queue_insert(struct priority_queue *pq,
 441     struct priority_queue_entry *elt) __pqueue_overloadable;
 442
 443 /*
 444  *      Macro:          priority_queue_remove_min
 445  *      Function:
 446  *              Remove the minimum element in a min-heap priority queue.
 447  *      Header:
 448  *              priority_queue_remove_min(pq, type, field)
 449  *                      <struct priority_queue *> pq
 450  *                      <type> type of element in priority queue
 451  *                      <field> chain field in (*<type>)
 452  *      Returns:
 453  *              <type *> max element
 454  */
 455 #define priority_queue_remove_min(pq, type, field) ({                           \
 456         static_assert(priority_queue_is_min_heap(pq), "queue is min heap");     \
 457         pqe_element(_priority_queue_remove_root(pq), type, field);              \
 458 })
 459
 460 /*
 461  *      Macro:          priority_queue_remove_max
 462  *      Function:
 463  *              Remove the maximum element in a max-heap priority queue.
 464  *      Header:
 465  *              priority_queue_remove_max(pq, type, field)
 466  *                      <struct priority_queue *> pq
 467  *                      <type> type of element in priority queue
 468  *                      <field> chain field in (*<type>)
 469  *      Returns:
 470  *              <type *> max element
 471  */
 472 #define priority_queue_remove_max(pq, type, field) ({                           \
 473         static_assert(priority_queue_is_max_heap(pq), "queue is max heap");     \
 474         pqe_element(_priority_queue_remove_root(pq), type, field);              \
 475 })
 476
 477 /*
 478  *      Macro:          priority_queue_remove
 479  *      Function:
 480  *              Removes an element from the priority queue
 481  *      Header:
 482  *              priority_queue_remove(pq, elt)
 483  *                      <struct priority_queue *> pq
 484  *                      <priority_queue_entry_t> elt
 485  *      Returns:
 486  *              Whether the removed element was the root
 487  */
 488 extern bool
 489 priority_queue_remove(struct priority_queue *pq,
 490     struct priority_queue_entry *elt) __pqueue_overloadable;
 491
 492
 493 /*
 494  *      Macro:          priority_queue_entry_decreased
 495  *
 496  *      Function:
 497  *              Signal the priority queue that the entry priority has decreased.
 498  *
 499  *              The new value for the element priority must have been set
 500  *              prior to calling this function.
 501  *
 502  *      Header:
 503  *              priority_queue_entry_decreased(pq, elt)
 504  *                      <struct priority_queue *> pq
 505  *                      <priority_queue_entry_t> elt
 506  *      Returns:
 507  *              Whether the update caused the root or its key to change.
 508  */
 509 extern bool
 510 priority_queue_entry_decreased(struct priority_queue *pq,
 511     struct priority_queue_entry *elt) __pqueue_overloadable;
 512
 513 /*
 514  *      Macro:          priority_queue_entry_increased
 515  *
 516  *      Function:
 517  *              Signal the priority queue that the entry priority has increased.
 518  *
 519  *              The new value for the element priority must have been set
 520  *              prior to calling this function.
 521  *
 522  *      Header:
 523  *              priority_queue_entry_increased(pq, elt, new_key)
 524  *                      <struct priority_queue *> pq
 525  *                      <priority_queue_entry_t> elt
 526  *      Returns:
 527  *              Whether the update caused the root or its key to change.
 528  */
 529 extern bool
 530 priority_queue_entry_increased(struct priority_queue *pq,
 531     struct priority_queue_entry *elt) __pqueue_overloadable;
 532
 533
 534 #pragma mark priority_queue_sched_*
 535
 536 __enum_decl(priority_queue_entry_sched_modifier_t, uint8_t, {
 537         PRIORITY_QUEUE_ENTRY_NONE      = 0,
 538         PRIORITY_QUEUE_ENTRY_PREEMPTED = 1,
 539 });
 540
 541 #define priority_queue_is_sched_heap(pq) _Generic(pq, \
 542         struct priority_queue_sched_min *: true, \
 543         struct priority_queue_sched_max *: true, \
 544         struct priority_queue_sched_stable_min *: true, \
 545         struct priority_queue_sched_stable_max *: true, \
 546         default: false)
 547
 548 /*
 549  *      Macro:          priority_queue_entry_set_sched_pri
 550  *
 551  *      Function:
 552  *              Sets the scheduler priority on an entry supporting this concept.
 553  *
 554  *              The priority is expected to fit on 8 bits.
 555  *              An optional sorting modifier.
 556  *
 557  *      Header:
 558  *              priority_queue_entry_set_sched_pri(pq, elt, pri, modifier)
 559  *                      <struct priority_queue *> pq
 560  *                      <priority_queue_entry_t> elt
 561  *                      <uint8_t> pri
 562  *                      <priority_queue_entry_sched_modifier_t> modifier
 563  */
 564 #define priority_queue_entry_set_sched_pri(pq, elt, pri, modifier)              \
 565 MACRO_BEGIN                                                                     \
 566         static_assert(priority_queue_is_sched_heap(pq), "is a sched heap");     \
 567         (elt)->key = (priority_queue_key_t)(((pri) << 8) + (modifier));         \
 568 MACRO_END
 569
 570 /*
 571  *      Macro:          priority_queue_entry_sched_pri
 572  *
 573  *      Function:
 574  *              Return the scheduler priority on an entry supporting this
 575  *              concept.
 576  *
 577  *      Header:
 578  *              priority_queue_entry_sched_pri(pq, elt)
 579  *                      <struct priority_queue *> pq
 580  *                      <priority_queue_entry_t> elt
 581  *
 582  *      Returns:
 583  *              The scheduler priority of this entry
 584  */
 585 #define priority_queue_entry_sched_pri(pq, elt) ({                              \
 586         static_assert(priority_queue_is_sched_heap(pq), "is a sched heap");     \
 587         (priority_queue_key_t)((elt)->key >> 8);                                \
 588 })
 589
 590 /*
 591  *      Macro:          priority_queue_entry_sched_modifier
 592  *
 593  *      Function:
 594  *              Return the scheduler modifier on an entry supporting this
 595  *              concept.
 596  *
 597  *      Header:
 598  *              priority_queue_entry_sched_modifier(pq, elt)
 599  *                      <struct priority_queue *> pq
 600  *                      <priority_queue_entry_t> elt
 601  *
 602  *      Returns:
 603  *              The scheduler priority of this entry
 604  */
 605 #define priority_queue_entry_sched_modifier(pq, elt) ({                         \
 606         static_assert(priority_queue_is_sched_heap(pq), "is a sched heap");     \
 607         (priority_queue_entry_sched_modifier_t)(elt)->key;                      \
 608 })
 609
 610 /*
 611  *      Macro:          priority_queue_min_sched_pri
 612  *
 613  *      Function:
 614  *              Return the scheduler priority of the minimum element
 615  *              of a scheduler priority queue.
 616  *
 617  *      Header:
 618  *              priority_queue_min_sched_pri(pq)
 619  *                      <struct priority_queue *> pq
 620  *
 621  *      Returns:
 622  *              The scheduler priority of this entry
 623  */
 624 #define priority_queue_min_sched_pri(pq) ({                                     \
 625         static_assert(priority_queue_is_min_heap(pq), "queue is min heap");     \
 626         priority_queue_entry_sched_pri(pq, (pq)->pq_root);                      \
 627 })
 628
 629 /*
 630  *      Macro:          priority_queue_max_sched_pri
 631  *
 632  *      Function:
 633  *              Return the scheduler priority of the maximum element
 634  *              of a scheduler priority queue.
 635  *
 636  *      Header:
 637  *              priority_queue_max_sched_pri(pq)
 638  *                      <struct priority_queue *> pq
 639  *
 640  *      Returns:
 641  *              The scheduler priority of this entry
 642  */
 643 #define priority_queue_max_sched_pri(pq) ({                                     \
 644         static_assert(priority_queue_is_max_heap(pq), "queue is max heap");     \
 645         priority_queue_entry_sched_pri(pq, (pq)->pq_root);                      \
 646 })
 647
 648
 649 #pragma mark implementation details
 650
 651 #define PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t) \
 652                                                                                 \
 653 __pqueue_overloadable extern void                                               \
 654 _priority_queue_destroy(pqueue_t pq, uintptr_t offset, void (^cb)(void *));     \
 655                                                                                 \
 656 __pqueue_overloadable extern bool                                               \
 657 priority_queue_insert(pqueue_t que, pqelem_t elt);                              \
 658                                                                                 \
 659 __pqueue_overloadable extern pqelem_t                                           \
 660 _priority_queue_remove_root(pqueue_t que);                                      \
 661                                                                                 \
 662 __pqueue_overloadable extern bool                                               \
 663 priority_queue_remove(pqueue_t que, pqelem_t elt);                              \
 664                                                                                 \
 665 __pqueue_overloadable extern bool                                               \
 666 priority_queue_entry_decreased(pqueue_t que, pqelem_t elt);                     \
 667                                                                                 \
 668 __pqueue_overloadable extern bool                                               \
 669 priority_queue_entry_increased(pqueue_t que, pqelem_t elt)
 670
 671 #define PRIORITY_QUEUE_MAKE(pqueue_t, pqelem_t) \
 672 __pqueue_overloadable                                                           \
 673 static inline void                                                              \
 674 priority_queue_init(pqueue_t que)                                               \
 675 {                                                                               \
 676         __builtin_bzero(que, sizeof(*que));                                     \
 677 }                                                                               \
 678                                                                                 \
 679 PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t)
 680
 681 #define PRIORITY_QUEUE_MAKE_CB(pqueue_t, pqelem_t) \
 682 __pqueue_overloadable                                                           \
 683 static inline void                                                              \
 684 priority_queue_init(pqueue_t pq, priority_queue_compare_fn_t cmp_fn)            \
 685 {                                                                               \
 686         pq->pq_root = NULL;                                                     \
 687         pq->pq_cmp_fn = cmp_fn;                                                 \
 688 }                                                                               \
 689                                                                                 \
 690 PRIORITY_QUEUE_MAKE_BASE(pqueue_t, pqelem_t)
 691
 692 PRIORITY_QUEUE_MAKE_CB(struct priority_queue_min *, priority_queue_entry_t);
 693 PRIORITY_QUEUE_MAKE_CB(struct priority_queue_max *, priority_queue_entry_t);
 694
 695 PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_min *, priority_queue_entry_deadline_t);
 696 PRIORITY_QUEUE_MAKE(struct priority_queue_deadline_max *, priority_queue_entry_deadline_t);
 697
 698 PRIORITY_QUEUE_MAKE(struct priority_queue_sched_min *, priority_queue_entry_sched_t);
 699 PRIORITY_QUEUE_MAKE(struct priority_queue_sched_max *, priority_queue_entry_sched_t);
 700
 701 PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_min *, priority_queue_entry_stable_t);
 702 PRIORITY_QUEUE_MAKE(struct priority_queue_sched_stable_max *, priority_queue_entry_stable_t);
 703
 704 __END_DECLS
 705
 706 #pragma GCC visibility pop
 707
 708 #endif /* _KERN_PRIORITY_QUEUE_H_ */