1 /* 2 * Copyright © 2020 Google, Inc. 3 * 4 * This is part of HarfBuzz, a text shaping library. 5 * 6 * Permission is hereby granted, without written agreement and without 7 * license or royalty fees, to use, copy, modify, and distribute this 8 * software and its documentation for any purpose, provided that the 9 * above copyright notice and the following two paragraphs appear in 10 * all copies of this software. 11 * 12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 16 * DAMAGE. 17 * 18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 23 * 24 * Google Author(s): Garret Rieger 25 */ 26 27 #ifndef HB_PRIORITY_QUEUE_HH 28 #define HB_PRIORITY_QUEUE_HH 29 30 #include "hb.hh" 31 #include "hb-vector.hh" 32 33 /* 34 * hb_priority_queue_t 35 * 36 * Priority queue implemented as a binary heap. Supports extract minimum 37 * and insert operations. 38 * 39 * The priority queue is implemented as a binary heap, which is a complete 40 * binary tree. The root of the tree is the minimum element. The heap 41 * property is that the priority of a node is less than or equal to the 42 * priority of its children. The heap is stored in an array, with the 43 * children of node i stored at indices 2i + 1 and 2i + 2. 44 */ 45 template <typename K> 46 struct hb_priority_queue_t 47 { 48 private: 49 typedef hb_pair_t<K, unsigned> item_t; 50 hb_vector_t<item_t> heap; 51 52 public: 53 resethb_priority_queue_t54 void reset () { heap.resize (0); } 55 in_errorhb_priority_queue_t56 bool in_error () const { return heap.in_error (); } 57 allochb_priority_queue_t58 bool alloc (unsigned size) 59 { return heap.alloc (size); } 60 61 #ifndef HB_OPTIMIZE_SIZE 62 HB_ALWAYS_INLINE 63 #endif inserthb_priority_queue_t64 void insert (K priority, unsigned value) 65 { 66 heap.push (item_t (priority, value)); 67 if (unlikely (heap.in_error ())) return; 68 bubble_up (heap.length - 1); 69 } 70 71 #ifndef HB_OPTIMIZE_SIZE 72 HB_ALWAYS_INLINE 73 #endif pop_minimumhb_priority_queue_t74 item_t pop_minimum () 75 { 76 assert (!is_empty ()); 77 78 item_t result = heap.arrayZ[0]; 79 80 heap.arrayZ[0] = heap.arrayZ[heap.length - 1]; 81 heap.resize (heap.length - 1); 82 83 if (!is_empty ()) 84 bubble_down (0); 85 86 return result; 87 } 88 minimumhb_priority_queue_t89 const item_t& minimum () 90 { 91 return heap[0]; 92 } 93 is_emptyhb_priority_queue_t94 bool is_empty () const { return heap.length == 0; } operator boolhb_priority_queue_t95 explicit operator bool () const { return !is_empty (); } get_populationhb_priority_queue_t96 unsigned int get_population () const { return heap.length; } 97 98 /* Sink interface. */ operator <<hb_priority_queue_t99 hb_priority_queue_t& operator << (item_t item) 100 { insert (item.first, item.second); return *this; } 101 102 private: 103 parenthb_priority_queue_t104 static constexpr unsigned parent (unsigned index) 105 { 106 return (index - 1) / 2; 107 } 108 left_childhb_priority_queue_t109 static constexpr unsigned left_child (unsigned index) 110 { 111 return 2 * index + 1; 112 } 113 right_childhb_priority_queue_t114 static constexpr unsigned right_child (unsigned index) 115 { 116 return 2 * index + 2; 117 } 118 119 HB_ALWAYS_INLINE bubble_downhb_priority_queue_t120 void bubble_down (unsigned index) 121 { 122 repeat: 123 assert (index < heap.length); 124 125 unsigned left = left_child (index); 126 unsigned right = right_child (index); 127 128 bool has_left = left < heap.length; 129 if (!has_left) 130 // If there's no left, then there's also no right. 131 return; 132 133 bool has_right = right < heap.length; 134 if (heap.arrayZ[index].first <= heap.arrayZ[left].first 135 && (!has_right || heap.arrayZ[index].first <= heap.arrayZ[right].first)) 136 return; 137 138 unsigned child; 139 if (!has_right || heap.arrayZ[left].first < heap.arrayZ[right].first) 140 child = left; 141 else 142 child = right; 143 144 swap (index, child); 145 index = child; 146 goto repeat; 147 } 148 149 HB_ALWAYS_INLINE bubble_uphb_priority_queue_t150 void bubble_up (unsigned index) 151 { 152 repeat: 153 assert (index < heap.length); 154 155 if (index == 0) return; 156 157 unsigned parent_index = parent (index); 158 if (heap.arrayZ[parent_index].first <= heap.arrayZ[index].first) 159 return; 160 161 swap (index, parent_index); 162 index = parent_index; 163 goto repeat; 164 } 165 swaphb_priority_queue_t166 void swap (unsigned a, unsigned b) noexcept 167 { 168 assert (a < heap.length); 169 assert (b < heap.length); 170 hb_swap (heap.arrayZ[a], heap.arrayZ[b]); 171 } 172 }; 173 174 #endif /* HB_PRIORITY_QUEUE_HH */ 175