1 files changed, 33 insertions, 12 deletions

diff --git a/src/3rdparty/harfbuzz-ng/src/hb-priority-queue.hh b/src/3rdparty/harfbuzz-ng/src/hb-priority-queue.hh
index ac76b7d955..274d5df4c5 100644
--- a/src/3rdparty/harfbuzz-ng/src/hb-priority-queue.hh
+++ b/src/3rdparty/harfbuzz-ng/src/hb-priority-queue.hh
@@ -35,11 +35,18 @@
  *
  * Priority queue implemented as a binary heap. Supports extract minimum
  * and insert operations.
+ *
+ * The priority queue is implemented as a binary heap, which is a complete
+ * binary tree. The root of the tree is the minimum element. The heap
+ * property is that the priority of a node is less than or equal to the
+ * priority of its children. The heap is stored in an array, with the
+ * children of node i stored at indices 2i + 1 and 2i + 2.
  */
+template <typename K>
 struct hb_priority_queue_t
 {
  private:
-  typedef hb_pair_t<int64_t, unsigned> item_t;
+  typedef hb_pair_t<K, unsigned> item_t;
   hb_vector_t<item_t> heap;
 
  public:
@@ -48,13 +55,22 @@ struct hb_priority_queue_t
 
   bool in_error () const { return heap.in_error (); }
 
-  void insert (int64_t priority, unsigned value)
+  bool alloc (unsigned size)
+  { return heap.alloc (size); }
+
+#ifndef HB_OPTIMIZE_SIZE
+  HB_ALWAYS_INLINE
+#endif
+  void insert (K priority, unsigned value)
   {
     heap.push (item_t (priority, value));
     if (unlikely (heap.in_error ())) return;
     bubble_up (heap.length - 1);
   }
 
+#ifndef HB_OPTIMIZE_SIZE
+  HB_ALWAYS_INLINE
+#endif
   item_t pop_minimum ()
   {
     assert (!is_empty ());
@@ -62,7 +78,7 @@ struct hb_priority_queue_t
     item_t result = heap.arrayZ[0];
 
     heap.arrayZ[0] = heap.arrayZ[heap.length - 1];
-    heap.shrink (heap.length - 1);
+    heap.resize (heap.length - 1);
 
     if (!is_empty ())
       bubble_down (0);
@@ -100,8 +116,10 @@ struct hb_priority_queue_t
     return 2 * index + 2;
   }
 
+  HB_ALWAYS_INLINE
   void bubble_down (unsigned index)
   {
+    repeat:
     assert (index < heap.length);
 
     unsigned left = left_child (index);
@@ -117,19 +135,21 @@ struct hb_priority_queue_t
         && (!has_right || heap.arrayZ[index].first <= heap.arrayZ[right].first))
       return;
 
+    unsigned child;
     if (!has_right || heap.arrayZ[left].first < heap.arrayZ[right].first)
-    {
-      swap (index, left);
-      bubble_down (left);
-      return;
-    }
+      child = left;
+    else
+      child = right;
 
-    swap (index, right);
-    bubble_down (right);
+    swap (index, child);
+    index = child;
+    goto repeat;
   }
 
+  HB_ALWAYS_INLINE
   void bubble_up (unsigned index)
   {
+    repeat:
     assert (index < heap.length);
 
     if (index == 0) return;
@@ -139,10 +159,11 @@ struct hb_priority_queue_t
       return;
 
     swap (index, parent_index);
-    bubble_up (parent_index);
+    index = parent_index;
+    goto repeat;
   }
 
-  void swap (unsigned a, unsigned b)
+  void swap (unsigned a, unsigned b) noexcept
   {
     assert (a < heap.length);
     assert (b < heap.length);