commit 87f1b80d27527d50d99b998a0d734115390bcd3f
author Behdad Esfahbod <behdad@behdad.org> Sun Jun 25 23:14:01 2023 -0600
committer Behdad Esfahbod <behdad@behdad.org> Sun Jun 25 23:14:01 2023 -0600
tree a5ea0c33ee70180beba3b522219e2291c8a906ce
parent e7ad017ca6607d9576c4292d82b6c417710a4e54

[bimap] Write with a map & vector combo

Faster for getting keys.

Speeds up 10% in:
BM_subset/subset_glyphs/RobotoFlex-Variable.ttf/retaingids/10

src/hb-bimap.hh

diff --git a/src/hb-bimap.hh b/src/hb-bimap.hh
index f690093..4006fc4 100644
--- a/src/hb-bimap.hh
+++ b/src/hb-bimap.hh
@@ -83,7 +83,6 @@
 
   unsigned int get_population () const { return forw_map.get_population (); }
 
-
   protected:
   hb_map_t  forw_map;
   hb_map_t  back_map;
@@ -95,8 +94,30 @@
 };
 
 /* Inremental bimap: only lhs is given, rhs is incrementally assigned */
-struct hb_inc_bimap_t : hb_bimap_t
+struct hb_inc_bimap_t
 {
+  bool in_error () const { return forw_map.in_error () || back_map.in_error (); }
+
+  unsigned int get_population () const { return forw_map.get_population (); }
+
+  void reset ()
+  {
+    forw_map.reset ();
+    back_map.reset ();
+  }
+
+  void alloc (unsigned pop)
+  {
+    forw_map.alloc (pop);
+    back_map.alloc (pop);
+  }
+
+  void clear ()
+  {
+    forw_map.clear ();
+    back_map.resize (0);
+  }
+
   /* Add a mapping from lhs to rhs with a unique value if lhs is unknown.
    * Return the rhs value as the result.
    */
@@ -105,20 +126,30 @@
     hb_codepoint_t  rhs = forw_map[lhs];
     if (rhs == HB_MAP_VALUE_INVALID)
     {
-      rhs = next_value++;
-      set (lhs, rhs);
+      rhs = back_map.length;
+      forw_map.set (lhs, rhs);
+      back_map.push (lhs);
     }
     return rhs;
   }
 
   hb_codepoint_t skip ()
-  { return next_value++; }
+  {
+    hb_codepoint_t start = back_map.length;
+    back_map.push (HB_MAP_VALUE_INVALID);
+    return start;
+  }
 
   hb_codepoint_t skip (unsigned count)
-  { return next_value += count; }
+  {
+    hb_codepoint_t start = back_map.length;
+    for (unsigned i = 0; i < count; i++)
+      back_map.push (HB_MAP_VALUE_INVALID);
+    return start;
+  }
 
   hb_codepoint_t get_next_value () const
-  { return next_value; }
+  { return back_map.length; }
 
   void add_set (const hb_set_t *set)
   {
@@ -129,7 +160,7 @@
   bool identity (unsigned int size)
   {
     clear ();
-    for (hb_codepoint_t i = 0; i < size; i++) set (i, i);
+    for (hb_codepoint_t i = 0; i < size; i++) add (i);
     return !in_error ();
   }
 
@@ -153,11 +184,21 @@
 
     clear ();
     for (hb_codepoint_t rhs = 0; rhs < count; rhs++)
-      set (work[rhs], rhs);
+      add (work.arrayZ[rhs]);
   }
 
+  hb_codepoint_t get (hb_codepoint_t lhs) const { return forw_map.get (lhs); }
+  hb_codepoint_t backward (hb_codepoint_t rhs) const { return back_map[rhs]; }
+
+  hb_codepoint_t operator [] (hb_codepoint_t lhs) const { return get (lhs); }
+  bool has (hb_codepoint_t lhs) const { return forw_map.has (lhs); }
+
   protected:
-  unsigned int next_value = 0;
+  hb_map_t forw_map;
+  hb_vector_t<hb_codepoint_t> back_map;
+
+  public:
+  auto keys () const HB_AUTO_RETURN (+ back_map.iter())
 };
 
 #endif /* HB_BIMAP_HH */

src/hb-ot-layout-common.hh

diff --git a/src/hb-ot-layout-common.hh b/src/hb-ot-layout-common.hh
index 90b1f36..b3af128 100644
--- a/src/hb-ot-layout-common.hh
+++ b/src/hb-ot-layout-common.hh
@@ -2382,7 +2382,7 @@
     return_trace (c->check_struct (this) && axesZ.sanitize (c, axisCount * regionCount));
   }
 
-  bool serialize (hb_serialize_context_t *c, const VarRegionList *src, const hb_bimap_t &region_map)
+  bool serialize (hb_serialize_context_t *c, const VarRegionList *src, const hb_inc_bimap_t &region_map)
   {
     TRACE_SERIALIZE (this);
     if (unlikely (!c->extend_min (this))) return_trace (false);
@@ -2499,7 +2499,7 @@
   bool serialize (hb_serialize_context_t *c,
 		  const VarData *src,
 		  const hb_inc_bimap_t &inner_map,
-		  const hb_bimap_t &region_map)
+		  const hb_inc_bimap_t &region_map)
   {
     TRACE_SERIALIZE (this);
     if (unlikely (!c->extend_min (this))) return_trace (false);