kc3-lang/harfbuzz/src/hb-priority-queue.hh

Branch - branch -main

• Show log

  Commit

• Hash : aba798dd
  Author :
  Date : 2025-09-12T00:52:40
  

  [instancer/varstore] Use heapify() instead of inserts()
  

Download

• src/hb-priority-queue.hh

• /*
   * Copyright © 2020  Google, Inc.
   *
   *  This is part of HarfBuzz, a text shaping library.
   *
   * Permission is hereby granted, without written agreement and without
   * license or royalty fees, to use, copy, modify, and distribute this
   * software and its documentation for any purpose, provided that the
   * above copyright notice and the following two paragraphs appear in
   * all copies of this software.
   *
   * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
   * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
   * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
   * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
   * DAMAGE.
   *
   * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
   * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
   * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
   * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
   * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
   *
   * Google Author(s): Garret Rieger
   */
  
  #ifndef HB_PRIORITY_QUEUE_HH
  #define HB_PRIORITY_QUEUE_HH
  
  #include "hb.hh"
  #include "hb-vector.hh"
  
  /*
   * hb_priority_queue_t
   *
   * 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
  {
   public:
    typedef hb_pair_t<K, unsigned> item_t;
  
   private:
    hb_vector_t<item_t> heap;
  
   public:
  
    hb_priority_queue_t () = default;
    hb_priority_queue_t (hb_vector_t<item_t>&& other) : heap (std::move (other))
    {
      // Heapify the vector.
      for (int i = (heap.length / 2) - 1; i >= 0; i--)
        bubble_down (i);
    }
  
    void reset () { heap.resize (0); }
  
    bool in_error () const { return heap.in_error (); }
  
    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 ());
  
      item_t result = heap.arrayZ[0];
  
      heap.arrayZ[0] = heap.arrayZ[heap.length - 1];
      heap.resize (heap.length - 1);
  
      if (!is_empty ())
        bubble_down (0);
  
      return result;
    }
  
    const item_t& minimum ()
    {
      return heap[0];
    }
  
    bool is_empty () const { return heap.length == 0; }
    explicit operator bool () const { return !is_empty (); }
    unsigned int get_population () const { return heap.length; }
  
    /* Sink interface. */
    hb_priority_queue_t& operator << (item_t item)
    { insert (item.first, item.second); return *this; }
  
   private:
  
    static constexpr unsigned parent (unsigned index)
    {
      return (index - 1) / 2;
    }
  
    static constexpr unsigned left_child (unsigned index)
    {
      return 2 * index + 1;
    }
  
    static constexpr unsigned right_child (unsigned index)
    {
      return 2 * index + 2;
    }
  
    HB_ALWAYS_INLINE
    void bubble_down (unsigned index)
    {
      repeat:
      assert (index < heap.length);
  
      unsigned left = left_child (index);
      unsigned right = right_child (index);
  
      bool has_left = left < heap.length;
      if (!has_left)
        // If there's no left, then there's also no right.
        return;
  
      bool has_right = right < heap.length;
      if (heap.arrayZ[index].first <= heap.arrayZ[left].first
          && (!has_right || heap.arrayZ[index].first <= heap.arrayZ[right].first))
        return;
  
      unsigned child;
      if (!has_right || heap.arrayZ[left].first < heap.arrayZ[right].first)
        child = left;
      else
        child = 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;
  
      unsigned parent_index = parent (index);
      if (heap.arrayZ[parent_index].first <= heap.arrayZ[index].first)
        return;
  
      swap (index, parent_index);
      index = parent_index;
      goto repeat;
    }
  
    void swap (unsigned a, unsigned b) noexcept
    {
      assert (a < heap.length);
      assert (b < heap.length);
      hb_swap (heap.arrayZ[a], heap.arrayZ[b]);
    }
  };
  
  #endif /* HB_PRIORITY_QUEUE_HH */
  

Download