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 #include <mach/mach_types.h>
  33 #include <kern/macro_help.h>
  34 #include <kern/assert.h>
  35
  36 #include <sys/cdefs.h>
  37
  38 __BEGIN_DECLS
  39
  40 /*
  41  * A generic priorty ordered queue implementation based on pairing heaps.
  42  *
  43  * Reference Papers:
  44  * - A Back-to-Basics Empirical Study of Priority Queues (https://arxiv.org/abs/1403.0252)
  45  * - The Pairing Heap: A New Form of Self-Adjusting Heap (https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf)
  46  *
  47  * The XNU implementation is a basic version of the pairing heap. It allows for O(1) insertion and amortized O(log n)
  48  * deletion. It is not a stable data structure since adding stability would need more pointers and hence more memory.
  49  *
  50  * The implementation supports two types of key storage:
  51  *
  52  *     Type 1: PRIORITY_QUEUE_GENERIC_KEY
  53  *
  54  *         This flag is useful when the priorities are either larger than 8-bits or the node comparision needs
  55  *         extra information other than the priority. The nodes do not store the priorities themselves and on
  56  *         comparision, callout to the comparator (of type priority_queue_compare_fn_t) provided as part of
  57  *         initialization.
  58  *
  59  *         Sample Initialization:
  60  *
  61  *         {
  62  *             static struct priority_queue pq;
  63  *             priority_queue_init(pq, PRIORITY_QUEUE_MAX_HEAP | PRIORITY_QUEUE_GENERIC_KEY);
  64  *         }
  65  *
  66  *         For this type, all insertions, priority_increase, priority_decrease must pass PRIORITY_QUEUE_KEY_NONE
  67  *         as the priority key field.
  68  *
  69  *     Type 2: PRIORITY_QUEUE_BUILTIN_KEY
  70  *
  71  *         This type is useful when the priorities need to be stored within the data structure itself.
  72  *         Each node in the priority queue maintains a 8-bit priority key.
  73  *
  74  *         Sample Initialization:
  75  *         {
  76  *             static struct priority_queue pq;
  77  *             priority_queue_init(pq, PRIORITY_QUEUE_MAX_HEAP | PRIORITY_QUEUE_BUILTIN_KEY);
  78  *         }
  79  *
  80  *
  81  * Min / Max Heap:
  82  *
  83  *     The semantics of Min/Max heap are not used by the implementation, it assumes that the comparison block
  84  *     that is passed to the insertion / removal / ... macros provides the right ordering.
  85  *
  86  *     However for human readability purposes, whether this heap is a MIN or MAX heap is passed
  87  *     at initialization time, and will influence whether accessors like priority_queue_min
  88  *     or priority_queue_max can be used.
  89  *
  90  *
  91  * Element Linkage:
  92  *
  93  *         Both types use a common queue head and linkage pattern.
  94  *         The head of a priority queue is declared as:
  95  *
  96  *              struct priority_queue pq_head;
  97  *
  98  *         Elements in this queue are linked together using struct priority_queue_entry objects embedded within a structure:
  99  *              struct some_data {
 100  *                      int field1;
 101  *                      int field2;
 102  *                      ...
 103  *                      struct priority_queue_entry link;
 104  *                      ...
 105  *                      int last_field;
 106  *              };
 107  *         struct some_data is referred to as the queue "element"
 108  *
 109  *         This method uses the next, prev and child pointers of the struct priority_queue_entry linkage object embedded in a
 110  *         queue element to point to other elements in the queue. The head of the priority queue (the priority_queue
 111  *         object) will point to the root of the pairing heap (NULL if heap is empty). This method allows multiple chains
 112  *         through a given object, by embedding multiple priority_queue_entry objects in the structure, while simultaneously
 113  *         providing fast removal and insertion into the heap using only priority_queue_entry object pointers.
 114  */
 115
 116
 117 /*
 118  * Priority keys maintained by the data structure.
 119  * Since the priority is packed in the node itself, it restricts keys to be 8-bits only.
 120  */
 121 #define PRIORITY_QUEUE_KEY_NONE             0
 122 typedef uint8_t priority_queue_key_t;
 123
 124 /*
 125  * Flags passed to priority_queue_init()
 126  *
 127  * One key type must be picked (default is BUILTIN_KEY)
 128  * Min or Max heap must be picked (default is MAX_HEAP)
 129  */
 130 typedef enum priority_queue_flags {
 131         PRIORITY_QUEUE_BUILTIN_KEY    = 0x0,
 132         PRIORITY_QUEUE_GENERIC_KEY    = 0x1,
 133         PRIORITY_QUEUE_MAX_HEAP       = 0x0,
 134         PRIORITY_QUEUE_MIN_HEAP       = 0x2,
 135 #define PRIORITY_QUEUE_BUILTIN_MAX_HEAP (PRIORITY_QUEUE_MAX_HEAP | PRIORITY_QUEUE_BUILTIN_KEY)
 136 } priority_queue_flags_t;
 137
 138 #ifdef __LP64__
 139
 140 /*
 141  * For 64-bit platforms, pack the priority key into the child pointer
 142  * The packing/unpacking is done using a compiler trick to sign extend long.
 143  * This avoids additional NULL checks which are needed in typical packing
 144  * implementation. The idea is to define the packed location as a long and
 145  * for unpacking simply cast it to a full pointer which sign extends it.
 146  */
 147 #define PRIORITY_QUEUE_ENTRY_CHILD_BITS     56
 148 #define PRIORITY_QUEUE_ENTRY_KEY_BITS       8
 149
 150 typedef struct priority_queue_entry {
 151         struct priority_queue_entry         *next;
 152         struct priority_queue_entry         *prev;
 153         long                                key: PRIORITY_QUEUE_ENTRY_KEY_BITS;
 154         long                                child: PRIORITY_QUEUE_ENTRY_CHILD_BITS;
 155 } *priority_queue_entry_t;
 156
 157 #else /* __LP64__ */
 158
 159 /*
 160  * For 32-bit platforms, use an extra field to store the key since child pointer packing
 161  * is not an option. The child is maintained as a long to use the same packing/unpacking
 162  * routines that work for 64-bit platforms.
 163  */
 164 typedef struct priority_queue_entry {
 165         struct priority_queue_entry         *next;
 166         struct priority_queue_entry         *prev;
 167         long                                child;
 168         priority_queue_key_t                key;
 169 } *priority_queue_entry_t;
 170
 171 #endif /* __LP64__ */
 172
 173 /*
 174  * Comparator block prototype
 175  * Args:
 176  *      - elements to compare
 177  * Return:
 178  * comparision result to indicate relative ordering of elements according to the heap type
 179  */
 180 typedef int (^priority_queue_compare_fn_t)(struct priority_queue_entry *e1,
 181                 struct priority_queue_entry *e2);
 182
 183 /*
 184  * Standard comparision routines for max and min heap.
 185  * Must be used with PRIORITY_QUEUE_BUILTIN_KEY only.
 186  */
 187 static inline int
 188 priority_queue_element_builtin_key_compare(priority_queue_entry_t e1, priority_queue_entry_t e2)
 189 {
 190         return (int)e2->key - (int)e1->key;
 191 }
 192
 193 #define priority_heap_make_comparator(name1, name2, type, field, ...) \
 194         (^int(priority_queue_entry_t __e1, priority_queue_entry_t __e2){                                        \
 195             type *name1 = pqe_element_fast(__e1, type, field);                                                  \
 196             type *name2 = pqe_element_fast(__e2, type, field);                                                  \
 197             __VA_ARGS__;                                                                                        \
 198         })
 199
 200 #define PRIORITY_QUEUE_SCHED_PRI_MAX_HEAP_COMPARE                                                               \
 201         (^int(priority_queue_entry_t e1, priority_queue_entry_t e2){                                            \
 202             return -priority_queue_element_builtin_key_compare(e1, e2);                                         \
 203         })
 204
 205 #define PRIORITY_QUEUE_SCHED_PRI_MIN_HEAP_COMPARE                                                               \
 206         (^int(priority_queue_entry_t e1, priority_queue_entry_t e2){                                            \
 207             return priority_queue_element_builtin_key_compare(e1, e2);                                          \
 208         })
 209
 210 /*
 211  * Helper routines for packing/unpacking the child pointer in heap nodes.
 212  * On 64-bit platforms, these routines rely on the fact that the sign extension
 213  * for the lower 56-bits of a kernel pointer results in the real pointer. The trick
 214  * works for NULL pointers as well.
 215  * */
 216 #define pqueue_entry_pack_child(qe, child_ptr)      ((qe)->child = (long)(child_ptr))
 217 #define pqueue_entry_unpack_child(qe)               ((struct priority_queue_entry *)((qe)->child))
 218
 219 /*
 220  * Priority queue head structure.
 221  * Stores the comparision function using pointer packing. The remaining bit is used
 222  * for type of the queue.
 223  */
 224 struct priority_queue {
 225 /*
 226  * we pack priority_queue_flags_t in the least significant two bits
 227  * of the root pointer.
 228  */
 229 #define PRIORITY_QUEUE_ROOT_FLAGS_MASK    (3ul)
 230 #define PRIORITY_QUEUE_ROOT_POINTER_MASK  (~PRIORITY_QUEUE_ROOT_FLAGS_MASK)
 231         unsigned long                       pq_root_packed;
 232 };
 233
 234 /*
 235  *      Macro:          pqe_element_fast
 236  *      Function:
 237  *              Convert a priority_queue_entry_t to a queue element pointer.
 238  *              Get a pointer to the user-defined element containing
 239  *              a given priority_queue_entry_t
 240  *
 241  *              The fast variant assumes that `qe` is not NULL
 242  *      Header:
 243  *              pqe_element_fast(qe, type, field)
 244  *                      <priority_queue_entry_t> qe
 245  *                      <type> type of element in priority queue
 246  *                      <field> chain field in (*<type>)
 247  *      Returns:
 248  *              <type *> containing qe
 249  */
 250 #define pqe_element_fast(qe, type, field)  __container_of(qe, type, field)
 251
 252 /*
 253  *      Macro:          pqe_element
 254  *      Function:
 255  *              Convert a priority_queue_entry_t to a queue element pointer.
 256  *              Get a pointer to the user-defined element containing
 257  *              a given priority_queue_entry_t
 258  *
 259  *              The non fast variant handles NULL `qe`
 260  *      Header:
 261  *              pqe_element(qe, type, field)
 262  *                      <priority_queue_entry_t> qe
 263  *                      <type> type of element in priority queue
 264  *                      <field> chain field in (*<type>)
 265  *      Returns:
 266  *              <type *> containing qe
 267  */
 268 #define pqe_element(qe, type, field)  ({                                                                        \
 269         priority_queue_entry_t _tmp_entry = (qe);                                                               \
 270         _tmp_entry ? pqe_element_fast(_tmp_entry, type, field) : ((type *)NULL);                                \
 271 })
 272
 273 #define pqueue_has_generic_keys(p) \
 274         (((p)->pq_root_packed & PRIORITY_QUEUE_GENERIC_KEY) != 0)
 275
 276 #define pqueue_has_builtin_keys(p) \
 277         (((p)->pq_root_packed & PRIORITY_QUEUE_GENERIC_KEY) == 0)
 278
 279 #define pqueue_is_min_heap(p) \
 280         (((p)->pq_root_packed & PRIORITY_QUEUE_MIN_HEAP) != 0)
 281
 282 #define pqueue_is_max_heap(p) \
 283         (((p)->pq_root_packed & PRIORITY_QUEUE_MIN_HEAP) == 0)
 284
 285 /*
 286  *      Macro:          pqueue_pack_root
 287  *      Function:
 288  *              Pack the root pointer of the head.
 289  *      Header:
 290  *              pqueue_pack_root(q, root_ptr)
 291  *                      <struct priority_queue *> q
 292  *                      <priority_queue_entry_t> root_ptr
 293  */
 294 #define pqueue_pack_root(q, root_ptr)                                                                           \
 295 MACRO_BEGIN                                                                                                     \
 296         uintptr_t __flags = (q)->pq_root_packed & PRIORITY_QUEUE_ROOT_FLAGS_MASK;                               \
 297         (q)->pq_root_packed = (uintptr_t)(root_ptr) | __flags;                                                  \
 298 MACRO_END
 299
 300 /*
 301  *      Macro:          pqueue_unpack_root
 302  *      Function:
 303  *              Unpack the root pointer from the head of the priority queue.
 304  *      Header:
 305  *              pqueue_unpack_root(q)
 306  *                      <struct priority_queue *> q
 307  *      Returns:
 308  *              <priority_queue_entry_t>
 309  */
 310 #define pqueue_unpack_root(q) \
 311         ((priority_queue_entry_t)((q)->pq_root_packed & PRIORITY_QUEUE_ROOT_POINTER_MASK))
 312
 313 /*
 314  *      Macro:          pqueue_list_remove
 315  *      Function:
 316  *              Helper routine to remove an element from the list at its level
 317  *      Header:
 318  *              pqueue_list_remove(elt)
 319  *                      <priority_queue_entry_t> elt
 320  *      Returns:
 321  *              None
 322  */
 323 static inline void
 324 pqueue_list_remove(priority_queue_entry_t elt)
 325 {
 326         assert(elt->prev != NULL);
 327         /* Check if elt is head of list at its level;        */
 328         /* If yes, make the next node the head at that level */
 329         /* Else, remove elt from the list at that level      */
 330         if (pqueue_entry_unpack_child(elt->prev) == elt) {
 331                 pqueue_entry_pack_child(elt->prev, elt->next);
 332         } else {
 333                 elt->prev->next = elt->next;
 334         }
 335         /* Update prev for next element in list */
 336         if (elt->next != NULL)
 337                 elt->next->prev = elt->prev;
 338 }
 339
 340 /*
 341  *      Macro:          pqueue_merge
 342  *      Function:
 343  *              Helper routine to merge two subtrees of the heap to form a single tree and
 344  *              maintain the parent > child invariant. If the two keys are equal, the current
 345  *              implementation makes the first subtree the parent and the second one the child.
 346  *      Header:
 347  *              pqueue_merge(subtree_a, subtree_b, cmp_fn)
 348  *                      <priority_queue_entry_t> subtree_a
 349  *                      <priority_queue_entry_t> subtree_b
 350  *                      <cmp_fn> comparator function
 351  *      Returns:
 352  *              <priority_queue_entry_t> pointing to root of the merged tree
 353  */
 354 static inline priority_queue_entry_t
 355 pqueue_merge(priority_queue_entry_t subtree_a, priority_queue_entry_t subtree_b,
 356                 priority_queue_compare_fn_t cmp_fn)
 357 {
 358         priority_queue_entry_t merge_result = NULL;
 359         if (subtree_a == NULL) {
 360                 merge_result = subtree_b;
 361         } else if (subtree_b == NULL || (subtree_a == subtree_b)) {
 362                 merge_result = subtree_a;
 363         } else {
 364                 priority_queue_entry_t parent = subtree_a;
 365                 priority_queue_entry_t child = subtree_b;
 366                 if (cmp_fn(subtree_a, subtree_b) < 0) {
 367                         parent = subtree_b;
 368                         child = subtree_a;
 369                 }
 370                 /* Insert the child as the first element in the parent's child list */
 371                 child->next = pqueue_entry_unpack_child(parent);
 372                 child->prev = parent;
 373                 if (pqueue_entry_unpack_child(parent) != NULL)
 374                         pqueue_entry_unpack_child(parent)->prev = child;
 375                 /* Create the parent child relationship */
 376                 pqueue_entry_pack_child(parent, child);
 377                 parent->next = NULL;
 378                 parent->prev = NULL;
 379                 merge_result = parent;
 380         }
 381         return merge_result;
 382 }
 383
 384 /*
 385  *      Macro:          pqueue_pair_meld
 386  *      Function:
 387  *              Helper routine to splitwise pair a set of subtrees on a list at a given level and then
 388  *              meld them together to form a new tree while maintaining the invariant parent > child.
 389  *
 390  *              The caller must check the element is non NULL.
 391  *
 392  *      Header:
 393  *              pqueue_pair_meld(elt, cmp_fn)
 394  *                      <priority_queue_entry_t> elt
 395  *                      <cmp_fn> comparator function
 396  *      Returns:
 397  *              <priority_queue_entry_t> pointing to root of the melded tree
 398  */
 399 priority_queue_entry_t
 400 pqueue_pair_meld(priority_queue_entry_t e, priority_queue_compare_fn_t cmp_fn);
 401
 402 /*
 403  *      Macro:          pqueue_update_key
 404  *      Function:
 405  *              Helper routine to update the key for a node in the heap. Note that the priority keys are only
 406  *              maintained for the PRIORITY_QUEUE_BUILTIN_KEY type of priority queue. For PRIORITY_QUEUE_GENERIC_KEY,
 407  *              this routine does nothing.
 408  *      Header:
 409  *              pqueue_update_key(que, elt, new_key)
 410  *                      <struct priority_queue *> que
 411  *                      <priority_queue_entry_t> elt
 412  *                      <priority_queue_key_t> new_key
 413  *      Returns:
 414  *              None
 415  */
 416 static inline void
 417 pqueue_update_key(struct priority_queue *que, priority_queue_entry_t elt,
 418                 priority_queue_key_t new_key)
 419 {
 420         if (pqueue_has_builtin_keys(que)) {
 421                 assert(new_key <= UINT8_MAX);
 422                 elt->key = new_key;
 423         } else {
 424                 assert(new_key == PRIORITY_QUEUE_KEY_NONE);
 425         }
 426 }
 427
 428 /*
 429  *      Macro:          pqueue_remove_root
 430  *      Function:
 431  *              Helper routine to remove the root element in a priority queue.
 432  *      Header:
 433  *              pqueue_remove_root(que, cmp_fn)
 434  *                      <struct priority_queue *> que
 435  *                      <priority_queue_entry_t> old_root
 436  *                      <cmp_fn> comparator function
 437  *      Returns:
 438  *              old_root
 439  */
 440 static inline priority_queue_entry_t
 441 pqueue_remove_root(struct priority_queue *que, priority_queue_entry_t old_root,
 442                 priority_queue_compare_fn_t cmp_fn)
 443 {
 444         priority_queue_entry_t new_root = pqueue_entry_unpack_child(old_root);
 445         if (new_root) new_root = pqueue_pair_meld(new_root, cmp_fn);
 446         pqueue_pack_root(que, new_root);
 447         return old_root;
 448 }
 449
 450 /*
 451  *      Macro:          pqueue_remove_non_root
 452  *      Function:
 453  *              Helper routine to remove a non root element in a priority queue.
 454  *      Header:
 455  *              pqueue_remove_non_root(que, cmp_fn)
 456  *                      <struct priority_queue *> que
 457  *                      <priority_queue_entry_t> elt
 458  *                      <cmp_fn> comparator function
 459  *      Returns:
 460  *              elt
 461  */
 462 static inline priority_queue_entry_t
 463 pqueue_remove_non_root(struct priority_queue *que, priority_queue_entry_t elt,
 464                 priority_queue_compare_fn_t cmp_fn)
 465 {
 466         priority_queue_entry_t child, new_root;
 467
 468         /* To remove a non-root element with children levels, */
 469         /* - Remove element from its current level iist */
 470         /* - Pairwise split all the elements in the child level list */
 471         /* - Meld all these splits (right-to-left) to form new subtree */
 472         /* - Merge the root subtree with the newly formed subtree */
 473         pqueue_list_remove(elt);
 474
 475         child = pqueue_entry_unpack_child(elt);
 476         if (child) {
 477                 child = pqueue_pair_meld(child, cmp_fn);
 478                 new_root = pqueue_merge(pqueue_unpack_root(que), child, cmp_fn);
 479                 pqueue_pack_root(que, new_root);
 480         }
 481
 482         return elt;
 483 }
 484
 485 /*
 486  *      Macro:          pqueue_destroy
 487  *      Function:
 488  *              Destroy a priority queue safely. This routine accepts a callback
 489  *              to handle any cleanup for elements in the priority queue. The queue does
 490  *              not maintain its invariants while getting destroyed. The priority queue and
 491  *              the linkage nodes need to be re-initialized before re-using them.
 492  *
 493  *              Note: the offset is the offset to the linkage inside the elements
 494  *              That are linked inside the priority heap, because pqueue_destroy
 495  *              can't use pqe_element.
 496  *      Header:
 497  *              pqueue_destroy(q, offset, callback)
 498  *                      <struct priority_queue *> q
 499  *                      <size_t> offset
 500  *                      <callback> callback for each element
 501  *
 502  *      Returns:
 503  *              None
 504  */
 505 void
 506 pqueue_destroy(struct priority_queue *q, size_t offset,
 507                 void (^callback)(void *e));
 508
 509 /*
 510  * Priority Queue functionality routines
 511  */
 512
 513 /*
 514  *      Macro:          priority_queue_empty
 515  *      Function:
 516  *              Tests whether a priority queue is empty.
 517  *      Header:
 518  *              boolean_t priority_queue_empty(q)
 519  *                      <struct priority_queue *> q
 520  */
 521 #define priority_queue_empty(q)         (pqueue_unpack_root((q)) == NULL)
 522
 523 /*
 524  *      Macro:          priority_queue_entry_key
 525  *      Function:
 526  *              Returns the priority queue entry key for an element on a PRIORITY_QUEUE_BUILTIN_KEY
 527  *              queue. It should not be called for an element on a PRIORITY_QUEUE_GENERIC_KEY queue.
 528  *      Header:
 529  *              priority_queue_key_t priority_queue_entry_key(q, elt)
 530  *                      <struct priority_queue *> q
 531  *                      <struct priority_queue_entry *> elt
 532  */
 533 #define priority_queue_entry_key(q, elt) ({                                                                     \
 534         assert(pqueue_has_builtin_keys(q));                                                                     \
 535         (priority_queue_key_t)((elt)->key);                                                                     \
 536 })
 537
 538 /*
 539  *      Macro:          priority_queue_init
 540  *      Function:
 541  *              Initialze a <struct priority_queue *> by setting the flags
 542  *              Valid flags are:
 543  *              - PRIORITY_QUEUE_BUILTIN_KEY or PRIORITY_QUEUE_GENERIC_KEY
 544  *              - PRIORITY_QUEUE_MAX_HEAP or PRIORITY_QUEUE_MIN_HEAP
 545  *      Header:
 546  *              priority_queue_init(q, cmp_fn, queue_type)
 547  *                      <struct priority_queue *> q
 548  *                      <priority_queue_flags_t> queue_flags
 549  *      Returns:
 550  *              None
 551  */
 552 #define priority_queue_init(q, flags)                                                                           \
 553 MACRO_BEGIN                                                                                                     \
 554         pqueue_pack_root((q), NULL);                                                                            \
 555         (q)->pq_root_packed = (flags);                                                                          \
 556 MACRO_END
 557
 558 /*
 559  *      Macro:          priority_queue_entry_init
 560  *      Function:
 561  *              Initialze a priority_queue_entry_t
 562  *      Header:
 563  *              priority_queue_entry_init(qe)
 564  *                      <priority_queue_entry_t> qe
 565  *      Returns:
 566  *              None
 567  */
 568 #define priority_queue_entry_init(qe)                                                                           \
 569 MACRO_BEGIN                                                                                                     \
 570         (qe)->next = NULL;                                                                                      \
 571         (qe)->prev = NULL;                                                                                      \
 572         pqueue_entry_pack_child((qe), NULL);                                                                    \
 573         (qe)->key = PRIORITY_QUEUE_KEY_NONE;                                                                    \
 574 MACRO_END
 575
 576 /*
 577  *      Macro:          priority_queue_insert
 578  *      Function:
 579  *              Insert an element into the priority queue
 580  *      Header:
 581  *              priority_queue_insert(que, elt, new_key, cmp_fn)
 582  *                      <struct priority_queue *> que
 583  *                      <priority_queue_entry_t> elt
 584  *                      <priority_queue_key_t> new_key
 585  *                      <cmp_fn> comparator function
 586  *      Returns:
 587  *              Whether the inserted element became the new root
 588  */
 589 static inline boolean_t
 590 priority_queue_insert(struct priority_queue *que, priority_queue_entry_t elt,
 591                 priority_queue_key_t new_key, priority_queue_compare_fn_t cmp_fn)
 592 {
 593         priority_queue_entry_t new_root;
 594
 595         pqueue_update_key(que, elt, new_key);
 596         new_root = pqueue_merge(pqueue_unpack_root(que), elt, cmp_fn);
 597         pqueue_pack_root(que, new_root);
 598         return new_root == elt;
 599 }
 600
 601 /*
 602  *      Macro:          priority_queue_remove
 603  *      Function:
 604  *              Removes an element from the priority queue
 605  *      Header:
 606  *              priority_queue_remove(que, elt, cmp_fn)
 607  *                      <struct priority_queue *> que
 608  *                      <priority_queue_entry_t> elt
 609  *                      <cmp_fn> comparator function
 610  *      Returns:
 611  *              Whether the removed element was the root
 612  */
 613 static inline boolean_t
 614 priority_queue_remove(struct priority_queue *que, priority_queue_entry_t elt,
 615                 priority_queue_compare_fn_t cmp_fn)
 616 {
 617         if (elt == pqueue_unpack_root(que)) {
 618                 pqueue_remove_root(que, elt, cmp_fn);
 619                 priority_queue_entry_init(elt);
 620                 return TRUE;
 621         } else {
 622                 pqueue_remove_non_root(que, elt, cmp_fn);
 623                 priority_queue_entry_init(elt);
 624                 return FALSE;
 625         }
 626 }
 627
 628 /*
 629  *      Macro:          priority_queue_entry_decrease
 630  *
 631  *      WARNING:
 632  *              This function is badly named for a min-heap, as it means the element
 633  *              moves toward the root, which happens if the key value became smaller.
 634  *
 635  *      Function:
 636  *              Decrease the priority of an element in the priority queue. Since the heap invariant is to always
 637  *              have the maximum element at the root, the most efficient way to implement this is to remove
 638  *              the element and re-insert it into the heap.
 639  *
 640  *              For PRIORITY_QUEUE_BUILTIN_KEY, the new_key is passed into this routine since the priority is
 641  *              maintained by the data structure. For PRIORITY_QUEUE_GENERIC_KEY, the caller must update the priority
 642  *              in the element and then call this routine. For the new_key field, it must pass PRIORITY_QUEUE_KEY_NONE.
 643  *      Header:
 644  *              priority_queue_entry_decrease(que, elt, new_key, cmp_fn)
 645  *                      <struct priority_queue *> que
 646  *                      <priority_queue_entry_t> elt
 647  *                      <priority_queue_key_t> new_key
 648  *                      <cmp_fn> comparator function
 649  *      Returns:
 650  *              Whether the update caused the root or its key to change.
 651  */
 652 static inline boolean_t
 653 priority_queue_entry_decrease(struct priority_queue *que, priority_queue_entry_t elt,
 654                 priority_queue_key_t new_key, priority_queue_compare_fn_t cmp_fn)
 655 {
 656         boolean_t was_root = priority_queue_remove(que, elt, cmp_fn);
 657         /* Insert it back in the heap; insertion also causes the priority update in the element */
 658         priority_queue_insert(que, elt, new_key, cmp_fn);
 659         return was_root;
 660 }
 661
 662 /*
 663  *      Macro:          priority_queue_entry_increase
 664  *
 665  *      WARNING:
 666  *              This function is badly named for a min-heap, as it means the element
 667  *              moves away from the root, which happens if the key value became larger.
 668  *
 669  *      Function:
 670  *              Increase the priority of an element in the priority queue. If the root is being increased, no change
 671  *              to the data structure is needed. For elements at any other level, unhook it from that level and
 672  *              re-merge it.
 673  *
 674  *              For PRIORITY_QUEUE_BUILTIN_KEY, the new_key is passed into this routine since the priority is
 675  *              maintained by the data structure. For PRIORITY_QUEUE_GENERIC_KEY, the caller must update the priority
 676  *              in the element and then call this routine. For the new_key field, it must pass PRIORITY_QUEUE_KEY_NONE.
 677  *      Header:
 678  *              priority_queue_entry_increase(que, elt, new_key, cmp_fn)
 679  *                      <struct priority_queue *> que
 680  *                      <priority_queue_entry_t> elt
 681  *                      <priority_queue_key_t> new_key
 682  *                      <cmp_fn> comparator function
 683  *      Returns:
 684  *              Whether the update caused the root or its key to change.
 685  */
 686 static inline boolean_t
 687 priority_queue_entry_increase(struct priority_queue *que, priority_queue_entry_t elt,
 688                 priority_queue_key_t new_key, priority_queue_compare_fn_t cmp_fn)
 689 {
 690         if (elt == pqueue_unpack_root(que)) {
 691                 pqueue_update_key(que, elt, new_key);
 692                 return TRUE;
 693         }
 694
 695         /* Remove the element from its current level list */
 696         pqueue_list_remove(elt);
 697         /* Re-insert the element into the heap with a merge */
 698         return priority_queue_insert(que, elt, new_key, cmp_fn);
 699 }
 700
 701 /*
 702  * Min/Max nodes lookup and removal routines
 703  * Since the data structure is unaware of the type of heap being constructed, it provides both the min
 704  * and max variants of the lookup and removal routines. Both variants do the exact same operation and
 705  * it is up to the callers to call the right variant which makes semantic sense for the type of heap.
 706  */
 707
 708 /*
 709  *      Macro:          priority_queue_max
 710  *      Function:
 711  *              Lookup the max element in a priority queue. It simply returns the root of the
 712  *              priority queue.
 713  *      Header:
 714  *              priority_queue_max(q, type, field)
 715  *                      <struct priority_queue *> q
 716  *                      <type> type of element in priority queue
 717  *                      <field> chain field in (*<type>)
 718  *      Returns:
 719  *              <type *> max element
 720  */
 721 #define priority_queue_max(q, type, field) ({                                                                   \
 722         assert(pqueue_is_max_heap(q));                                                                          \
 723         pqe_element(pqueue_unpack_root(q), type, field);                                                        \
 724 })
 725
 726 /*
 727  *      Macro:          priority_queue_min
 728  *      Function:
 729  *              Lookup the min element in a priority queue. It simply returns the root of the
 730  *              priority queue.
 731  *      Header:
 732  *              priority_queue_min(q, type, field)
 733  *                      <struct priority_queue *> q
 734  *                      <type> type of element in priority queue
 735  *                      <field> chain field in (*<type>)
 736  *      Returns:
 737  *              <type *> min element
 738  */
 739 #define priority_queue_min(q, type, field) ({                                                                   \
 740         assert(pqueue_is_min_heap(que));                                                                         \
 741         priority_queue_entry_key(pqueue_unpack_root(q), type, field);                                           \
 742 })
 743
 744 /*
 745  *      Macro:          priority_queue_max_key
 746  *      Function:
 747  *              Lookup the max key in a priority queue.
 748  *      Header:
 749  *              priority_queue_max_key(q)
 750  *                      <struct priority_queue *> q
 751  *      Returns:
 752  *              <type *> max key
 753  */
 754 #define priority_queue_max_key(q) ({                                                                            \
 755         assert(pqueue_is_max_heap(q));                                                                          \
 756         priority_queue_entry_key(q, pqueue_unpack_root(q));                                                     \
 757 })
 758
 759 /*
 760  *      Macro:          priority_queue_min_key
 761  *      Function:
 762  *              Lookup the min key in a priority queue.
 763  *      Header:
 764  *              priority_queue_min_key(q)
 765  *                      <struct priority_queue *> q
 766  *      Returns:
 767  *              <type *> min key
 768  */
 769 #define priority_queue_min_key(q) ({                                                                            \
 770         assert(pqueue_is_min_heap(q));                                                                          \
 771         priority_queue_entry_key(pqueue_unpack_root(q));                                                        \
 772 })
 773
 774 /*
 775  *      Macro:          priority_queue_remove_max
 776  *      Function:
 777  *              Remove the max element in a priority queue.
 778  *              Uses the priority_queue_remove() routine to actually do the removal.
 779  *      Header:
 780  *              priority_queue_remove_max(q, type, field)
 781  *                      <struct priority_queue *> q
 782  *                      <type> type of element in priority queue
 783  *                      <field> chain field in (*<type>)
 784  *      Returns:
 785  *              <type *> max element
 786  */
 787 #define priority_queue_remove_max(q, type, field, cmp_fn) ({                                                    \
 788         assert(pqueue_is_max_heap(q));                                                                          \
 789         pqe_element(pqueue_remove_root(q, pqueue_unpack_root(q), cmp_fn), type, field);                         \
 790 })
 791
 792 /*
 793  *      Macro:          priority_queue_remove_min
 794  *      Function:
 795  *              Remove the min element in a priority queue.
 796  *              Uses the priority_queue_remove() routine to actually do the removal.
 797  *      Header:
 798  *              priority_queue_remove_min(q, type, field)
 799  *                      <struct priority_queue *> q
 800  *                      <type> type of element in priority queue
 801  *                      <field> chain field in (*<type>)
 802  *      Returns:
 803  *              <type *> min element
 804  */
 805 #define priority_queue_remove_min(q, type, field, cmp_fn) ({                                                    \
 806         assert(pqueue_is_min_heap(que));                                                                         \
 807         pqe_element(pqueue_remove_root(q, pqueue_unpack_root(q), cmp_fn), type, field);                         \
 808 })
 809
 810 /*
 811  *      Macro:          priority_queue_destroy
 812  *      Function:
 813  *              Destroy a priority queue safely. This routine accepts a callback
 814  *              to handle any cleanup for elements in the priority queue. The queue does
 815  *              not maintain its invariants while getting destroyed. The priority queue and
 816  *              the linkage nodes need to be re-initialized before re-using them.
 817  *      Header:
 818  *              priority_queue_destroy(q, type, field, callback)
 819  *                      <struct priority_queue *> q
 820  *                      <type> type of element in priority queue
 821  *                      <field> chain field in (*<type>)
 822  *                      <callback> callback for each element
 823  *
 824  *      Returns:
 825  *              None
 826  */
 827 #define priority_queue_destroy(q, type, field, callback, ...) \
 828         pqueue_destroy(q, offsetof(type, field), callback, ##__VA_ARGS__)
 829
 830 __END_DECLS
 831
 832 #endif /* _KERN_PRIORITY_QUEUE_H_ */