diff options
Diffstat (limited to 'src/3rdparty/harfbuzz-ng/src/hb-priority-queue.hh')
-rw-r--r-- | src/3rdparty/harfbuzz-ng/src/hb-priority-queue.hh | 43 |
1 files changed, 32 insertions, 11 deletions
diff --git a/src/3rdparty/harfbuzz-ng/src/hb-priority-queue.hh b/src/3rdparty/harfbuzz-ng/src/hb-priority-queue.hh index 93a7842eb0..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 ()); @@ -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); |