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__
33static_assert(PRIORITY_QUEUE_ENTRY_CHILD_BITS >= VM_KERNEL_POINTER_SIGNIFICANT_BITS,
34 "Priority Queue child pointer packing failed");
35#endif
36
37priority_queue_entry_t
38pqueue_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
78void
79pqueue_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