1 files changed, 162 insertions, 84 deletions

diff --git a/src/3rdparty/harfbuzz-ng/src/hb-map.hh b/src/3rdparty/harfbuzz-ng/src/hb-map.hh
index 041b8829af..6521b1a41d 100644
--- a/src/3rdparty/harfbuzz-ng/src/hb-map.hh
+++ b/src/3rdparty/harfbuzz-ng/src/hb-map.hh
@@ -42,13 +42,37 @@ template <typename K, typename V,
 	  bool minus_one = false>
 struct hb_hashmap_t
 {
+  static constexpr bool realloc_move = true;
+
   hb_hashmap_t ()  { init (); }
   ~hb_hashmap_t () { fini (); }
 
-  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)  { 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 (const hb_hashmap_t& o) : hb_hashmap_t ()
+  {
+    if (unlikely (!o.mask)) return;
+
+    if (item_t::is_trivial)
+    {
+      items = (item_t *) hb_malloc (sizeof (item_t) * (o.mask + 1));
+      if (unlikely (!items))
+      {
+	successful = false;
+	return;
+      }
+      population = o.population;
+      occupancy = o.occupancy;
+      mask = o.mask;
+      prime = o.prime;
+      max_chain_length = o.max_chain_length;
+      memcpy (items, o.items, sizeof (item_t) * (mask + 1));
+      return;
+    }
+
+    alloc (o.population); hb_copy (o, *this);
+  }
+  hb_hashmap_t (hb_hashmap_t&& o)  noexcept : hb_hashmap_t () { hb_swap (*this, o); }
+  hb_hashmap_t& operator= (const hb_hashmap_t& o)  { reset (); alloc (o.population); hb_copy (o, *this); return *this; }
+  hb_hashmap_t& operator= (hb_hashmap_t&& o)   noexcept { hb_swap (*this, o); return *this; }
 
   hb_hashmap_t (std::initializer_list<hb_pair_t<K, V>> lst) : hb_hashmap_t ()
   {
@@ -60,29 +84,32 @@ struct hb_hashmap_t
   hb_hashmap_t (const Iterable &o) : hb_hashmap_t ()
   {
     auto iter = hb_iter (o);
-    if (iter.is_random_access_iterator)
-      resize (hb_len (iter));
+    if (iter.is_random_access_iterator || iter.has_fast_len)
+      alloc (hb_len (iter));
     hb_copy (iter, *this);
   }
 
   struct item_t
   {
     K key;
-    uint32_t hash : 30;
+    uint32_t is_real_ : 1;
     uint32_t is_used_ : 1;
-    uint32_t is_tombstone_ : 1;
+    uint32_t hash : 30;
     V value;
 
     item_t () : key (),
+		is_real_ (false), is_used_ (false),
 		hash (0),
-		is_used_ (false), is_tombstone_ (false),
 		value () {}
 
+    // Needed for https://github.com/harfbuzz/harfbuzz/issues/4138
+    K& get_key () { return key; }
+    V& get_value () { return 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_; }
-    void set_tombstone (bool is_tombstone) { is_tombstone_ = is_tombstone; }
-    bool is_real () const { return is_used_ && !is_tombstone_; }
+    void set_real (bool is_real) { is_real_ = is_real; }
+    bool is_real () const { return is_real_; }
 
     template <bool v = minus_one,
 	      hb_enable_if (v == false)>
@@ -98,28 +125,32 @@ struct hb_hashmap_t
     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); }
+    hb_pair_t<const K &, V &> get_pair_ref() { return hb_pair_t<const K &, V &> (key, value); }
 
     uint32_t total_hash () const
-    { return (hash * 31) + hb_hash (value); }
+    { return (hash * 31u) + hb_hash (value); }
+
+    static constexpr bool is_trivial = hb_is_trivially_constructible(K) &&
+				       hb_is_trivially_destructible(K) &&
+				       hb_is_trivially_constructible(V) &&
+				       hb_is_trivially_destructible(V);
   };
 
   hb_object_header_t header;
-  unsigned int successful : 1; /* Allocations successful */
-  unsigned int population : 31; /* Not including tombstones. */
+  bool successful; /* Allocations successful */
+  unsigned short max_chain_length;
+  unsigned int population; /* Not including tombstones. */
   unsigned int occupancy; /* Including tombstones. */
   unsigned int mask;
   unsigned int prime;
   item_t *items;
 
-  friend void swap (hb_hashmap_t& a, hb_hashmap_t& b)
+  friend void swap (hb_hashmap_t& a, hb_hashmap_t& b) noexcept
   {
     if (unlikely (!a.successful || !b.successful))
       return;
-    unsigned tmp = a.population;
-    a.population = b.population;
-    b.population = tmp;
-    //hb_swap (a.population, b.population);
+    hb_swap (a.max_chain_length, b.max_chain_length);
+    hb_swap (a.population, b.population);
     hb_swap (a.occupancy, b.occupancy);
     hb_swap (a.mask, b.mask);
     hb_swap (a.prime, b.prime);
@@ -130,6 +161,7 @@ struct hb_hashmap_t
     hb_object_init (this);
 
     successful = true;
+    max_chain_length = 0;
     population = occupancy = 0;
     mask = 0;
     prime = 0;
@@ -139,10 +171,12 @@ struct hb_hashmap_t
   {
     hb_object_fini (this);
 
-    if (likely (items)) {
+    if (likely (items))
+    {
       unsigned size = mask + 1;
-      for (unsigned i = 0; i < size; i++)
-        items[i].~item_t ();
+      if (!item_t::is_trivial)
+	for (unsigned i = 0; i < size; i++)
+	  items[i].~item_t ();
       hb_free (items);
       items = nullptr;
     }
@@ -157,7 +191,7 @@ struct hb_hashmap_t
 
   bool in_error () const { return !successful; }
 
-  bool resize (unsigned new_population = 0)
+  bool alloc (unsigned new_population = 0)
   {
     if (unlikely (!successful)) return false;
 
@@ -171,8 +205,11 @@ struct hb_hashmap_t
       successful = false;
       return false;
     }
-    for (auto &_ : hb_iter (new_items, new_size))
-      new (&_) item_t ();
+    if (!item_t::is_trivial)
+      for (auto &_ : hb_iter (new_items, new_size))
+	new (&_) item_t ();
+    else
+      hb_memset (new_items, 0, (size_t) new_size * sizeof (item_t));
 
     unsigned int old_size = size ();
     item_t *old_items = items;
@@ -181,6 +218,7 @@ struct hb_hashmap_t
     population = occupancy = 0;
     mask = new_size - 1;
     prime = prime_for (power);
+    max_chain_length = power * 2;
     items = new_items;
 
     /* Insert back old items. */
@@ -192,8 +230,10 @@ struct hb_hashmap_t
 		       old_items[i].hash,
 		       std::move (old_items[i].value));
       }
-      old_items[i].~item_t ();
     }
+    if (!item_t::is_trivial)
+      for (unsigned int i = 0; i < old_size; i++)
+	old_items[i].~item_t ();
 
     hb_free (old_items);
 
@@ -201,72 +241,129 @@ struct hb_hashmap_t
   }
 
   template <typename KK, typename VV>
-  bool set_with_hash (KK&& key, uint32_t hash, VV&& value, bool is_delete=false)
+  bool set_with_hash (KK&& key, uint32_t hash, VV&& value, bool overwrite = true)
   {
     if (unlikely (!successful)) return false;
-    if (unlikely ((occupancy + occupancy / 2) >= mask && !resize ())) return false;
-    item_t &item = item_for_hash (key, hash);
+    if (unlikely ((occupancy + occupancy / 2) >= mask && !alloc ())) return false;
+
+    hash &= 0x3FFFFFFF; // We only store lower 30bit of hash
+    unsigned int tombstone = (unsigned int) -1;
+    unsigned int i = hash % prime;
+    unsigned length = 0;
+    unsigned step = 0;
+    while (items[i].is_used ())
+    {
+      if ((std::is_integral<K>::value || items[i].hash == hash) &&
+	  items[i] == key)
+      {
+        if (!overwrite)
+	  return false;
+        else
+	  break;
+      }
+      if (!items[i].is_real () && tombstone == (unsigned) -1)
+        tombstone = i;
+      i = (i + ++step) & mask;
+      length++;
+    }
 
-    if (is_delete && !(item == key))
-      return true; /* Trying to delete non-existent key. */
+    item_t &item = items[tombstone == (unsigned) -1 ? i : tombstone];
 
     if (item.is_used ())
     {
       occupancy--;
-      if (!item.is_tombstone ())
-	population--;
+      population -= item.is_real ();
     }
 
     item.key = std::forward<KK> (key);
     item.value = std::forward<VV> (value);
     item.hash = hash;
     item.set_used (true);
-    item.set_tombstone (is_delete);
+    item.set_real (true);
 
     occupancy++;
-    if (!is_delete)
-      population++;
+    population++;
+
+    if (unlikely (length > max_chain_length) && occupancy * 8 > mask)
+      alloc (mask - 8); // This ensures we jump to next larger size
 
     return true;
   }
 
   template <typename VV>
-  bool set (const K &key, VV&& value) { return set_with_hash (key, hb_hash (key), std::forward<VV> (value)); }
+  bool set (const K &key, VV&& value, bool overwrite = true) { return set_with_hash (key, hb_hash (key), std::forward<VV> (value), overwrite); }
   template <typename VV>
-  bool set (K &&key, VV&& value) { return set_with_hash (std::move (key), hb_hash (key), std::forward<VV> (value)); }
+  bool set (K &&key, VV&& value, bool overwrite = true)
+  {
+    uint32_t hash = hb_hash (key);
+    return set_with_hash (std::move (key), hash, std::forward<VV> (value), overwrite);
+  }
+  bool add (const K &key)
+  {
+    uint32_t hash = hb_hash (key);
+    return set_with_hash (key, hash, item_t::default_value ());
+  }
 
   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 ();
+    if (!items) return item_t::default_value ();
+    auto *item = fetch_item (key, hb_hash (key));
+    if (item)
+      return item->value;
+    return item_t::default_value ();
   }
   const V& get (const K &key) const
   {
-    if (unlikely (!items)) return item_t::default_value ();
+    if (!items) return item_t::default_value ();
     return get_with_hash (key, hb_hash (key));
   }
 
-  void del (const K &key) { set_with_hash (key, hb_hash (key), item_t::default_value (), true); }
+  void del (const K &key)
+  {
+    if (!items) return;
+    auto *item = fetch_item (key, hb_hash (key));
+    if (item)
+    {
+      item->set_real (false);
+      population--;
+    }
+  }
 
   /* Has interface. */
   const V& operator [] (K k) const { return get (k); }
   template <typename VV=V>
-  bool has (K key, VV **vp = nullptr) const
+  bool has (const K &key, VV **vp = nullptr) const
   {
-    if (unlikely (!items))
-      return false;
-    auto &item = item_for_hash (key, hb_hash (key));
-    if (item.is_real () && item == key)
+    if (!items) return false;
+    auto *item = fetch_item (key, hb_hash (key));
+    if (item)
     {
-      if (vp) *vp = std::addressof (item.value);
+      if (vp) *vp = std::addressof (item->value);
       return true;
     }
-    else
-      return false;
+    return false;
+  }
+  item_t *fetch_item (const K &key, uint32_t hash) const
+  {
+    hash &= 0x3FFFFFFF; // We only store lower 30bit of hash
+    unsigned int i = hash % prime;
+    unsigned step = 0;
+    while (items[i].is_used ())
+    {
+      if ((std::is_integral<K>::value || items[i].hash == hash) &&
+	  items[i] == key)
+      {
+	if (items[i].is_real ())
+	  return &items[i];
+	else
+	  return nullptr;
+      }
+      i = (i + ++step) & mask;
+    }
+    return nullptr;
   }
   /* Projection. */
-  V operator () (K k) const { return get (k); }
+  const V& operator () (K k) const { return get (k); }
 
   unsigned size () const { return mask ? mask + 1 : 0; }
 
@@ -323,39 +420,37 @@ struct hb_hashmap_t
 
   auto iter_items () const HB_AUTO_RETURN
   (
-    + hb_iter (items, size ())
+    + hb_iter (items, this->size ())
     | hb_filter (&item_t::is_real)
   )
   auto iter_ref () const HB_AUTO_RETURN
   (
-    + iter_items ()
+    + this->iter_items ()
     | hb_map (&item_t::get_pair_ref)
   )
   auto iter () const HB_AUTO_RETURN
   (
-    + iter_items ()
+    + this->iter_items ()
     | hb_map (&item_t::get_pair)
   )
   auto keys_ref () const HB_AUTO_RETURN
   (
-    + iter_items ()
-    | hb_map (&item_t::key)
+    + this->iter_items ()
+    | hb_map (&item_t::get_key)
   )
   auto keys () const HB_AUTO_RETURN
   (
-    + iter_items ()
-    | hb_map (&item_t::key)
+    + this->keys_ref ()
     | hb_map (hb_ridentity)
   )
   auto values_ref () const HB_AUTO_RETURN
   (
-    + iter_items ()
-    | hb_map (&item_t::value)
+    + this->iter_items ()
+    | hb_map (&item_t::get_value)
   )
   auto values () const HB_AUTO_RETURN
   (
-    + iter_items ()
-    | hb_map (&item_t::value)
+    + this->values_ref ()
     | hb_map (hb_ridentity)
   )
 
@@ -393,23 +488,6 @@ struct hb_hashmap_t
   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;
-    unsigned int step = 0;
-    unsigned int tombstone = (unsigned) -1;
-    while (items[i].is_used ())
-    {
-      if (items[i].hash == hash && items[i] == key)
-	return items[i];
-      if (tombstone == (unsigned) -1 && items[i].is_tombstone ())
-	tombstone = i;
-      i = (i + ++step) & mask;
-    }
-    return items[tombstone == (unsigned) -1 ? i : tombstone];
-  }
-
   static unsigned int prime_for (unsigned int shift)
   {
     /* Following comment and table copied from glib. */
@@ -477,10 +555,10 @@ struct hb_map_t : hb_hashmap_t<hb_codepoint_t,
   ~hb_map_t () = default;
   hb_map_t () : hashmap () {}
   hb_map_t (const hb_map_t &o) : hashmap ((hashmap &) o) {}
-  hb_map_t (hb_map_t &&o) : hashmap (std::move ((hashmap &) o)) {}
+  hb_map_t (hb_map_t &&o)  noexcept : hashmap (std::move ((hashmap &) o)) {}
   hb_map_t& operator= (const hb_map_t&) = default;
   hb_map_t& operator= (hb_map_t&&) = default;
-  hb_map_t (std::initializer_list<hb_pair_t<hb_codepoint_t, hb_codepoint_t>> lst) : hashmap (lst) {}
+  hb_map_t (std::initializer_list<hb_codepoint_pair_t> lst) : hashmap (lst) {}
   template <typename Iterable,
 	    hb_requires (hb_is_iterable (Iterable))>
   hb_map_t (const Iterable &o) : hashmap (o) {}