tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

hb-priority-queue.hh (4658B)

      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 public:
     49  typedef hb_pair_t<K, unsigned> item_t;
     50 
     51 private:
     52  hb_vector_t<item_t> heap;
     53 
     54 public:
     55 
     56  hb_priority_queue_t () = default;
     57  hb_priority_queue_t (hb_vector_t<item_t>&& other) : heap (std::move (other))
     58  {
     59    // Heapify the vector.
     60    for (int i = (heap.length / 2) - 1; i >= 0; i--)
     61      bubble_down (i);
     62  }
     63 
     64  void reset () { heap.resize (0); }
     65 
     66  bool in_error () const { return heap.in_error (); }
     67 
     68  bool alloc (unsigned size)
     69  { return heap.alloc (size); }
     70 
     71 #ifndef HB_OPTIMIZE_SIZE
     72  HB_ALWAYS_INLINE
     73 #endif
     74  void insert (K priority, unsigned value)
     75  {
     76    heap.push (item_t (priority, value));
     77    if (unlikely (heap.in_error ())) return;
     78    bubble_up (heap.length - 1);
     79  }
     80 
     81 #ifndef HB_OPTIMIZE_SIZE
     82  HB_ALWAYS_INLINE
     83 #endif
     84  item_t pop_minimum ()
     85  {
     86    assert (!is_empty ());
     87 
     88    item_t result = heap.arrayZ[0];
     89 
     90    heap.arrayZ[0] = heap.arrayZ[heap.length - 1];
     91    heap.resize (heap.length - 1);
     92 
     93    if (!is_empty ())
     94      bubble_down (0);
     95 
     96    return result;
     97  }
     98 
     99  const item_t& minimum ()
    100  {
    101    return heap[0];
    102  }
    103 
    104  bool is_empty () const { return heap.length == 0; }
    105  explicit operator bool () const { return !is_empty (); }
    106  unsigned int get_population () const { return heap.length; }
    107 
    108  /* Sink interface. */
    109  hb_priority_queue_t& operator << (item_t item)
    110  { insert (item.first, item.second); return *this; }
    111 
    112 private:
    113 
    114  static constexpr unsigned parent (unsigned index)
    115  {
    116    return (index - 1) / 2;
    117  }
    118 
    119  static constexpr unsigned left_child (unsigned index)
    120  {
    121    return 2 * index + 1;
    122  }
    123 
    124  static constexpr unsigned right_child (unsigned index)
    125  {
    126    return 2 * index + 2;
    127  }
    128 
    129  HB_ALWAYS_INLINE
    130  void bubble_down (unsigned index)
    131  {
    132    repeat:
    133    assert (index < heap.length);
    134 
    135    unsigned left = left_child (index);
    136    unsigned right = right_child (index);
    137 
    138    bool has_left = left < heap.length;
    139    if (!has_left)
    140      // If there's no left, then there's also no right.
    141      return;
    142 
    143    bool has_right = right < heap.length;
    144    if (heap.arrayZ[index].first <= heap.arrayZ[left].first
    145        && (!has_right || heap.arrayZ[index].first <= heap.arrayZ[right].first))
    146      return;
    147 
    148    unsigned child;
    149    if (!has_right || heap.arrayZ[left].first < heap.arrayZ[right].first)
    150      child = left;
    151    else
    152      child = right;
    153 
    154    swap (index, child);
    155    index = child;
    156    goto repeat;
    157  }
    158 
    159  HB_ALWAYS_INLINE
    160  void bubble_up (unsigned index)
    161  {
    162    repeat:
    163    assert (index < heap.length);
    164 
    165    if (index == 0) return;
    166 
    167    unsigned parent_index = parent (index);
    168    if (heap.arrayZ[parent_index].first <= heap.arrayZ[index].first)
    169      return;
    170 
    171    swap (index, parent_index);
    172    index = parent_index;
    173    goto repeat;
    174  }
    175 
    176  void swap (unsigned a, unsigned b) noexcept
    177  {
    178    assert (a < heap.length);
    179    assert (b < heap.length);
    180    hb_swap (heap.arrayZ[a], heap.arrayZ[b]);
    181  }
    182 };
    183 
    184 #endif /* HB_PRIORITY_QUEUE_HH */