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
122typedef 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 */
130typedef 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
150typedef 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 */
164typedef 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 */
180typedef 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 */
187static inline int
188priority_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 */
224struct 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) \
295MACRO_BEGIN \
296 uintptr_t __flags = (q)->pq_root_packed & PRIORITY_QUEUE_ROOT_FLAGS_MASK; \
297 (q)->pq_root_packed = (uintptr_t)(root_ptr) | __flags; \
298MACRO_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 */
323static inline void
324pqueue_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 */
354static inline priority_queue_entry_t
355pqueue_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 */
399priority_queue_entry_t
400pqueue_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 */
416static inline void
417pqueue_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 */
440static inline priority_queue_entry_t
441pqueue_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 */
462static inline priority_queue_entry_t
463pqueue_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 */
505void
506pqueue_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) \
553MACRO_BEGIN \
554 pqueue_pack_root((q), NULL); \
555 (q)->pq_root_packed = (flags); \
556MACRO_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) \
569MACRO_BEGIN \
570 (qe)->next = NULL; \
571 (qe)->prev = NULL; \
572 pqueue_entry_pack_child((qe), NULL); \
573 (qe)->key = PRIORITY_QUEUE_KEY_NONE; \
574MACRO_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 */
589static inline boolean_t
590priority_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 */
613static inline boolean_t
614priority_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 */
652static inline boolean_t
653priority_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 */
686static inline boolean_t
687priority_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_ */
833