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 | #include <kern/priority_queue.h> |
30 | #include <mach/vm_param.h> |
31 | |
32 | #ifdef __LP64__ |
33 | static_assert(PRIORITY_QUEUE_ENTRY_CHILD_BITS >= VM_KERNEL_POINTER_SIGNIFICANT_BITS, |
34 | "Priority Queue child pointer packing failed" ); |
35 | #endif |
36 | |
37 | priority_queue_entry_t |
38 | pqueue_pair_meld(priority_queue_entry_t elt, priority_queue_compare_fn_t cmp_fn) |
39 | { |
40 | priority_queue_entry_t pq_meld_result = NULL; |
41 | priority_queue_entry_t pair_list = NULL; |
42 | |
43 | assert(elt); // caller needs to check this. |
44 | |
45 | /* Phase 1: */ |
46 | /* Split the list into a set of pairs going front to back. */ |
47 | /* Hook these pairs onto an intermediary list in reverse order of traversal.*/ |
48 | |
49 | do { |
50 | /* Consider two elements at a time for pairing */ |
51 | priority_queue_entry_t pair_item_a = elt; |
52 | priority_queue_entry_t pair_item_b = elt->next; |
53 | if (pair_item_b == NULL) { |
54 | /* Odd number of elements in the list; link the odd element */ |
55 | /* as it is on the intermediate list. */ |
56 | pair_item_a->prev = pair_list; |
57 | pair_list = pair_item_a; |
58 | break; |
59 | } |
60 | /* Found two elements to pair up */ |
61 | elt = pair_item_b->next; |
62 | priority_queue_entry_t pair = pqueue_merge(pair_item_a, pair_item_b, cmp_fn); |
63 | /* Link the pair onto the intermediary list */ |
64 | pair->prev = pair_list; |
65 | pair_list = pair; |
66 | } while (elt != NULL); |
67 | |
68 | /* Phase 2: Merge all the pairs in the pair_list */ |
69 | do { |
70 | elt = pair_list->prev; |
71 | pq_meld_result = pqueue_merge(pq_meld_result, pair_list, cmp_fn); |
72 | pair_list = elt; |
73 | } while (pair_list != NULL); |
74 | |
75 | return pq_meld_result; |
76 | } |
77 | |
78 | void |
79 | pqueue_destroy(struct priority_queue *q, size_t offset, |
80 | void (^callback)(void *e)) |
81 | { |
82 | assert(callback != NULL); |
83 | priority_queue_entry_t head = pqueue_unpack_root(q); |
84 | priority_queue_entry_t tail = head; |
85 | |
86 | while (head != NULL) { |
87 | priority_queue_entry_t child_list = pqueue_entry_unpack_child(head); |
88 | if (child_list) { |
89 | tail->next = child_list; |
90 | while (tail->next) tail = tail->next; |
91 | } |
92 | |
93 | priority_queue_entry_t elt = head; |
94 | head = head->next; |
95 | callback((void *)elt - offset); |
96 | } |
97 | |
98 | /* poison the queue now that it's destroyed */ |
99 | q->pq_root_packed = ~0UL; |
100 | } |
101 | |