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_ */ |
833 | |