1 files changed, 113 insertions, 106 deletions

diff --git a/thirdparty/harfbuzz/src/hb-map.hh b/thirdparty/harfbuzz/src/hb-map.hh
index 8302e3f8c7..bfb1b3f768 100644
--- a/thirdparty/harfbuzz/src/hb-map.hh
+++ b/thirdparty/harfbuzz/src/hb-map.hh
@@ -43,9 +43,9 @@ struct hb_hashmap_t
   hb_hashmap_t ()  { init (); }
   ~hb_hashmap_t () { fini (); }
 
-  hb_hashmap_t (const hb_hashmap_t& o) : hb_hashmap_t () { resize (population); hb_copy (o, *this); }
+  hb_hashmap_t (const hb_hashmap_t& o) : hb_hashmap_t () { resize (o.population); hb_copy (o, *this); }
   hb_hashmap_t (hb_hashmap_t&& o) : hb_hashmap_t () { hb_swap (*this, o); }
-  hb_hashmap_t& operator= (const hb_hashmap_t& o)  { resize (population); hb_copy (o, *this); return *this; }
+  hb_hashmap_t& operator= (const hb_hashmap_t& o)  { reset (); resize (o.population); hb_copy (o, *this); return *this; }
   hb_hashmap_t& operator= (hb_hashmap_t&& o)  { hb_swap (*this, o); return *this; }
 
   hb_hashmap_t (std::initializer_list<hb_pair_t<K, V>> lst) : hb_hashmap_t ()
@@ -71,6 +71,11 @@ struct hb_hashmap_t
     uint32_t is_tombstone_ : 1;
     V value;
 
+    item_t () : key (),
+		hash (0),
+		is_used_ (false), is_tombstone_ (false),
+		value () {}
+
     bool is_used () const { return is_used_; }
     void set_used (bool is_used) { is_used_ = is_used; }
     bool is_tombstone () const { return is_tombstone_; }
@@ -88,17 +93,8 @@ struct hb_hashmap_t
       return minus_1;
     };
 
-    void clear ()
-    {
-      new (std::addressof (key)) K ();
-      new (std::addressof (value)) V ();
-      hash = 0;
-      is_used_ = false;
-      is_tombstone_ = false;
-    }
-
-    bool operator == (const K &o) { return hb_deref (key) == hb_deref (o); }
-    bool operator == (const item_t &o) { return *this == o.key; }
+    bool operator == (const K &o) const { return hb_deref (key) == hb_deref (o); }
+    bool operator == (const item_t &o) const { return *this == o.key; }
     hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); }
     hb_pair_t<const K &, const V &> get_pair_ref() const { return hb_pair_t<const K &, const V &> (key, value); }
 
@@ -107,8 +103,8 @@ struct hb_hashmap_t
   };
 
   hb_object_header_t header;
-  bool successful; /* Allocations successful */
-  unsigned int population; /* Not including tombstones. */
+  unsigned int successful : 1; /* Allocations successful */
+  unsigned int population : 31; /* Not including tombstones. */
   unsigned int occupancy; /* Including tombstones. */
   unsigned int mask;
   unsigned int prime;
@@ -118,7 +114,10 @@ struct hb_hashmap_t
   {
     if (unlikely (!a.successful || !b.successful))
       return;
-    hb_swap (a.population, b.population);
+    unsigned tmp = a.population;
+    a.population = b.population;
+    b.population = tmp;
+    //hb_swap (a.population, b.population);
     hb_swap (a.occupancy, b.occupancy);
     hb_swap (a.mask, b.mask);
     hb_swap (a.prime, b.prime);
@@ -160,7 +159,9 @@ struct hb_hashmap_t
   {
     if (unlikely (!successful)) return false;
 
-    unsigned int power = hb_bit_storage (hb_max (population, new_population) * 2 + 8);
+    if (new_population != 0 && (new_population + new_population / 2) < mask) return true;
+
+    unsigned int power = hb_bit_storage (hb_max ((unsigned) population, new_population) * 2 + 8);
     unsigned int new_size = 1u << power;
     item_t *new_items = (item_t *) hb_malloc ((size_t) new_size * sizeof (item_t));
     if (unlikely (!new_items))
@@ -169,9 +170,9 @@ struct hb_hashmap_t
       return false;
     }
     for (auto &_ : hb_iter (new_items, new_size))
-      _.clear ();
+      new (&_) item_t ();
 
-    unsigned int old_size = mask + 1;
+    unsigned int old_size = size ();
     item_t *old_items = items;
 
     /* Switch to new, empty, array. */
@@ -181,47 +182,82 @@ struct hb_hashmap_t
     items = new_items;
 
     /* Insert back old items. */
-    if (old_items)
-      for (unsigned int i = 0; i < old_size; i++)
+    for (unsigned int i = 0; i < old_size; i++)
+    {
+      if (old_items[i].is_real ())
       {
-	if (old_items[i].is_real ())
-	{
-	  set_with_hash (old_items[i].key,
-			 old_items[i].hash,
-			 std::move (old_items[i].value));
-	}
-	old_items[i].~item_t ();
+	set_with_hash (std::move (old_items[i].key),
+		       old_items[i].hash,
+		       std::move (old_items[i].value));
       }
+      old_items[i].~item_t ();
+    }
 
     hb_free (old_items);
 
     return true;
   }
 
+  template <typename KK, typename VV>
+  bool set_with_hash (KK&& key, uint32_t hash, VV&& value, bool is_delete=false)
+  {
+    if (unlikely (!successful)) return false;
+    if (unlikely ((occupancy + occupancy / 2) >= mask && !resize ())) return false;
+    item_t &item = item_for_hash (key, hash);
+
+    if (is_delete && !(item == key))
+      return true; /* Trying to delete non-existent key. */
+
+    if (item.is_used ())
+    {
+      occupancy--;
+      if (!item.is_tombstone ())
+	population--;
+    }
+
+    item.key = std::forward<KK> (key);
+    item.value = std::forward<VV> (value);
+    item.hash = hash;
+    item.set_used (true);
+    item.set_tombstone (is_delete);
+
+    occupancy++;
+    if (!is_delete)
+      population++;
+
+    return true;
+  }
+
+  template <typename VV>
+  bool set (const K &key, VV&& value) { return set_with_hash (key, hb_hash (key), std::forward<VV> (value)); }
   template <typename VV>
-  bool set (K key, VV&& value) { return set_with_hash (key, hb_hash (key), std::forward<VV> (value)); }
+  bool set (K &&key, VV&& value) { return set_with_hash (std::move (key), hb_hash (key), std::forward<VV> (value)); }
 
-  const V& get (K key) const
+  const V& get_with_hash (const K &key, uint32_t hash) const
+  {
+    if (unlikely (!items)) return item_t::default_value ();
+    auto &item = item_for_hash (key, hash);
+    return item.is_real () && item == key ? item.value : item_t::default_value ();
+  }
+  const V& get (const K &key) const
   {
     if (unlikely (!items)) return item_t::default_value ();
-    unsigned int i = bucket_for (key);
-    return items[i].is_real () && items[i] == key ? items[i].value : item_t::default_value ();
+    return get_with_hash (key, hb_hash (key));
   }
 
-  void del (K key) { set_with_hash (key, hb_hash (key), item_t::default_value (), true); }
+  void del (const K &key) { set_with_hash (key, hb_hash (key), item_t::default_value (), true); }
 
   /* Has interface. */
-  typedef const V& value_t;
-  value_t operator [] (K k) const { return get (k); }
+  const V& operator [] (K k) const { return get (k); }
   template <typename VV=V>
   bool has (K key, VV **vp = nullptr) const
   {
     if (unlikely (!items))
       return false;
-    unsigned int i = bucket_for (key);
-    if (items[i].is_real () && items[i] == key)
+    auto &item = item_for_hash (key, hb_hash (key));
+    if (item.is_real () && item == key)
     {
-      if (vp) *vp = &items[i].value;
+      if (vp) *vp = std::addressof (item.value);
       return true;
     }
     else
@@ -230,13 +266,18 @@ struct hb_hashmap_t
   /* Projection. */
   V operator () (K k) const { return get (k); }
 
+  unsigned size () const { return mask ? mask + 1 : 0; }
+
   void clear ()
   {
     if (unlikely (!successful)) return;
 
-    if (items)
-      for (auto &_ : hb_iter (items, mask + 1))
-	_.clear ();
+    for (auto &_ : hb_iter (items, size ()))
+    {
+      /* Reconstruct items. */
+      _.~item_t ();
+      new (&_) item_t ();
+    }
 
     population = occupancy = 0;
   }
@@ -246,11 +287,10 @@ struct hb_hashmap_t
 
   uint32_t hash () const
   {
-    uint32_t h = 0;
-    for (const auto &item : + hb_array (items, mask ? mask + 1 : 0)
-			    | hb_filter (&item_t::is_real))
-      h ^= item.total_hash ();
-    return h;
+    return
+    + iter_items ()
+    | hb_reduce ([] (uint32_t h, const item_t &_) { return h ^ _.total_hash (); }, (uint32_t) 0u)
+    ;
   }
 
   bool is_equal (const hb_hashmap_t &other) const
@@ -258,7 +298,7 @@ struct hb_hashmap_t
     if (population != other.population) return false;
 
     for (auto pair : iter ())
-      if (get (pair.first) != pair.second)
+      if (other.get (pair.first) != pair.second)
         return false;
 
     return true;
@@ -271,87 +311,54 @@ struct hb_hashmap_t
   /*
    * Iterator
    */
-  auto iter () const HB_AUTO_RETURN
+
+  auto iter_items () const HB_AUTO_RETURN
   (
-    + hb_array (items, mask ? mask + 1 : 0)
+    + hb_iter (items, size ())
     | hb_filter (&item_t::is_real)
-    | hb_map (&item_t::get_pair)
   )
   auto iter_ref () const HB_AUTO_RETURN
   (
-    + hb_array (items, mask ? mask + 1 : 0)
-    | hb_filter (&item_t::is_real)
+    + iter_items ()
     | hb_map (&item_t::get_pair_ref)
   )
-  auto keys () const HB_AUTO_RETURN
+  auto iter () const HB_AUTO_RETURN
   (
-    + hb_array (items, mask ? mask + 1 : 0)
-    | hb_filter (&item_t::is_real)
-    | hb_map (&item_t::key)
-    | hb_map (hb_ridentity)
+    + iter_items ()
+    | hb_map (&item_t::get_pair)
   )
   auto keys_ref () const HB_AUTO_RETURN
   (
-    + hb_array (items, mask ? mask + 1 : 0)
-    | hb_filter (&item_t::is_real)
+    + iter_items ()
     | hb_map (&item_t::key)
   )
-  auto values () const HB_AUTO_RETURN
+  auto keys () const HB_AUTO_RETURN
   (
-    + hb_array (items, mask ? mask + 1 : 0)
-    | hb_filter (&item_t::is_real)
-    | hb_map (&item_t::value)
+    + keys_ref ()
     | hb_map (hb_ridentity)
   )
   auto values_ref () const HB_AUTO_RETURN
   (
-    + hb_array (items, mask ? mask + 1 : 0)
-    | hb_filter (&item_t::is_real)
+    + iter_items ()
     | hb_map (&item_t::value)
   )
+  auto values () const HB_AUTO_RETURN
+  (
+    + values_ref ()
+    | hb_map (hb_ridentity)
+  )
 
   /* Sink interface. */
   hb_hashmap_t& operator << (const hb_pair_t<K, V>& v)
   { set (v.first, v.second); return *this; }
-
-  protected:
-
-  template <typename VV>
-  bool set_with_hash (K key, uint32_t hash, VV&& value, bool is_delete=false)
-  {
-    if (unlikely (!successful)) return false;
-    if (unlikely ((occupancy + occupancy / 2) >= mask && !resize ())) return false;
-    unsigned int i = bucket_for_hash (key, hash);
-
-    if (is_delete && items[i].key != key)
-      return true; /* Trying to delete non-existent key. */
-
-    if (items[i].is_used ())
-    {
-      occupancy--;
-      if (!items[i].is_tombstone ())
-	population--;
-    }
-
-    items[i].key = key;
-    items[i].value = std::forward<VV> (value);
-    items[i].hash = hash;
-    items[i].set_used (true);
-    items[i].set_tombstone (is_delete);
-
-    occupancy++;
-    if (!is_delete)
-      population++;
-
-    return true;
-  }
-
-  unsigned int bucket_for (const K &key) const
-  {
-    return bucket_for_hash (key, hb_hash (key));
-  }
-
-  unsigned int bucket_for_hash (const K &key, uint32_t hash) const
+  hb_hashmap_t& operator << (const hb_pair_t<K, V&&>& v)
+  { set (v.first, std::move (v.second)); return *this; }
+  hb_hashmap_t& operator << (const hb_pair_t<K&&, V>& v)
+  { set (std::move (v.first), v.second); return *this; }
+  hb_hashmap_t& operator << (const hb_pair_t<K&&, V&&>& v)
+  { set (std::move (v.first), std::move (v.second)); return *this; }
+
+  item_t& item_for_hash (const K &key, uint32_t hash) const
   {
     hash &= 0x3FFFFFFF; // We only store lower 30bit of hash
     unsigned int i = hash % prime;
@@ -360,12 +367,12 @@ struct hb_hashmap_t
     while (items[i].is_used ())
     {
       if (items[i].hash == hash && items[i] == key)
-	return i;
+	return items[i];
       if (tombstone == (unsigned) -1 && items[i].is_tombstone ())
 	tombstone = i;
       i = (i + ++step) & mask;
     }
-    return tombstone == (unsigned) -1 ? i : tombstone;
+    return items[tombstone == (unsigned) -1 ? i : tombstone];
   }
 
   static unsigned int prime_for (unsigned int shift)