osfmk/kern/priority_queue.c

   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) {
  91                                 tail = tail->next;
  92                         }
  93                 }
  94
  95                 priority_queue_entry_t elt = head;
  96                 head = head->next;
  97                 callback((void *)elt - offset);
  98         }
  99
 100         /* poison the queue now that it's destroyed */
 101         q->pq_root_packed = ~0UL;
 102 }