Merge branch 'speed-up-event-matching' into 'master'

keymap: Cache key info

See merge request GNOME/gtk!1800

7 files changed, 144 insertions, 84 deletions

diff --git a/gdk/broadway/gdkkeys-broadway.c b/gdk/broadway/gdkkeys-broadway.c
index f58f332dc6..60d8715663 100644
--- a/gdk/broadway/gdkkeys-broadway.c
+++ b/gdk/broadway/gdkkeys-broadway.c
@@ -123,17 +123,16 @@ gdk_broadway_keymap_get_scroll_lock_state (GdkKeymap *keymap)
 
 static gboolean
 gdk_broadway_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
-					    guint          keyval,
-					    GdkKeymapKey **keys,
-					    gint          *n_keys)
+                                            guint          keyval,
+                                            GArray        *retval)
 {
-  if (n_keys)
-    *n_keys = 1;
-  if (keys)
-    {
-      *keys = g_new0 (GdkKeymapKey, 1);
-      (*keys)->keycode = keyval;
-    }
+  GdkKeymapKey key;
+
+  key.keycode = keyval;
+  key.group = 0;
+  key.level = 0;
+
+  g_array_append_val (retval, key);
 
   return TRUE;
 }
diff --git a/gdk/gdkevents.c b/gdk/gdkevents.c
index 41706885af..9d2a689381 100644
--- a/gdk/gdkevents.c
+++ b/gdk/gdkevents.c
@@ -1604,6 +1604,7 @@ gdk_key_event_matches (GdkEvent        *event,
                        GdkModifierType  modifiers)
 {
   GdkKeyEvent *self = (GdkKeyEvent *) event;
+  GdkKeymap *keymap;
   guint keycode;
   GdkModifierType state;
   guint ev_keyval;
@@ -1644,7 +1645,7 @@ gdk_key_event_matches (GdkEvent        *event,
     {
       /* modifier match */
       GdkKeymapKey *keys;
-      int n_keys;
+      guint n_keys;
       int i;
       guint key;
 
@@ -1667,7 +1668,8 @@ gdk_key_event_matches (GdkEvent        *event,
           return GDK_KEY_MATCH_EXACT;
         }
 
-      gdk_display_map_keyval (gdk_event_get_display (event), keyval, &keys, &n_keys);
+      keymap = gdk_display_get_keymap (gdk_event_get_display (event));
+      gdk_keymap_get_cached_entries_for_keyval (keymap, keyval, &keys, &n_keys);
 
       for (i = 0; i < n_keys; i++)
         {
@@ -1676,14 +1678,9 @@ gdk_key_event_matches (GdkEvent        *event,
               /* Only match for group if it's an accel mod */
               (!group_mod_is_accel_mod || keys[i].group == layout))
             {
-              /* partial match */
-              g_free (keys);
-
               return GDK_KEY_MATCH_PARTIAL;
             }
         }
-
-      g_free (keys);
     }
 
   return GDK_KEY_MATCH_NONE;
diff --git a/gdk/gdkkeys.c b/gdk/gdkkeys.c
index 469d204e0b..4d8978e552 100644
--- a/gdk/gdkkeys.c
+++ b/gdk/gdkkeys.c
@@ -196,13 +196,43 @@ gdk_keymap_set_property (GObject      *object,
 }
 
 static void
+gdk_keymap_finalize (GObject *object)
+{
+  GdkKeymap *keymap = GDK_KEYMAP (object);
+
+  g_array_free (keymap->cached_keys, TRUE);
+  g_hash_table_unref (keymap->cache);
+
+  G_OBJECT_CLASS (gdk_keymap_parent_class)->finalize (object);
+}
+
+static void
+gdk_keymap_keys_changed (GdkKeymap *keymap)
+{
+  GdkKeymapKey key;
+
+  g_array_set_size (keymap->cached_keys, 0);
+
+  key.keycode = 0;
+  key.group = 0;
+  key.level = 0;
+
+  g_array_append_val (keymap->cached_keys, key);
+
+  g_hash_table_remove_all (keymap->cache);
+}
+
+static void
 gdk_keymap_class_init (GdkKeymapClass *klass)
 {
   GObjectClass *object_class = G_OBJECT_CLASS (klass);
 
+  object_class->finalize = gdk_keymap_finalize;
   object_class->get_property = gdk_keymap_get_property;
   object_class->set_property = gdk_keymap_set_property;
 
+  klass->keys_changed = gdk_keymap_keys_changed;
+
   props[PROP_DISPLAY] =
     g_param_spec_object ("display",
                          "Display",
@@ -237,13 +267,13 @@ gdk_keymap_class_init (GdkKeymapClass *klass)
    */
   signals[KEYS_CHANGED] =
     g_signal_new (g_intern_static_string ("keys-changed"),
-		  G_OBJECT_CLASS_TYPE (object_class),
-		  G_SIGNAL_RUN_LAST,
-		  G_STRUCT_OFFSET (GdkKeymapClass, keys_changed),
-		  NULL, NULL,
-		  NULL,
-		  G_TYPE_NONE,
-		  0);
+                  G_OBJECT_CLASS_TYPE (object_class),
+                  G_SIGNAL_RUN_FIRST,
+                  G_STRUCT_OFFSET (GdkKeymapClass, keys_changed),
+                  NULL, NULL,
+                  NULL,
+                  G_TYPE_NONE,
+                  0);
 
   /**
    * GdkKeymap::state-changed:
@@ -267,6 +297,17 @@ gdk_keymap_class_init (GdkKeymapClass *klass)
 static void
 gdk_keymap_init (GdkKeymap *keymap)
 {
+  GdkKeymapKey key;
+
+  keymap->cached_keys = g_array_new (FALSE, FALSE, sizeof (GdkKeymapKey));
+
+  key.keycode = 0;
+  key.group = 0;
+  key.level = 0;
+
+  g_array_append_val (keymap->cached_keys, key);
+
+  keymap->cache = g_hash_table_new (g_direct_hash, g_direct_equal);
 }
 
 /**
@@ -502,13 +543,62 @@ gdk_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
                                    GdkKeymapKey **keys,
                                    gint          *n_keys)
 {
+  GArray *array;
+
   g_return_val_if_fail (GDK_IS_KEYMAP (keymap), FALSE);
   g_return_val_if_fail (keys != NULL, FALSE);
   g_return_val_if_fail (n_keys != NULL, FALSE);
   g_return_val_if_fail (keyval != 0, FALSE);
 
-  return GDK_KEYMAP_GET_CLASS (keymap)->get_entries_for_keyval (keymap, keyval,
-                                                                keys, n_keys);
+  array = g_array_new (FALSE, FALSE, sizeof (GdkKeymapKey));
+
+  GDK_KEYMAP_GET_CLASS (keymap)->get_entries_for_keyval (keymap, keyval, array);
+
+  *n_keys = array->len;
+  *keys = (GdkKeymapKey *)g_array_free (array, FALSE);
+
+  return TRUE;
+}
+
+void
+gdk_keymap_get_cached_entries_for_keyval (GdkKeymap     *keymap,
+                                          guint          keyval,
+                                          GdkKeymapKey **keys,
+                                          guint         *n_keys)
+{
+  guint cached;
+  guint offset;
+  guint len;
+
+  /* avoid using the first entry in cached_keys, so we can
+   * use 0 to mean 'not cached'
+   */
+  cached = GPOINTER_TO_UINT (g_hash_table_lookup (keymap->cache, GUINT_TO_POINTER (keyval)));
+  if (cached == 0)
+    {
+      GdkKeymapKey key;
+
+      offset = keymap->cached_keys->len;
+
+      GDK_KEYMAP_GET_CLASS (keymap)->get_entries_for_keyval (keymap, keyval, keymap->cached_keys);
+
+      g_array_append_val (keymap->cached_keys, key);
+
+      len = keymap->cached_keys->len - offset;
+      g_assert (len <= 255);
+
+      cached = (offset << 8) | len;
+
+      g_hash_table_insert (keymap->cache, GUINT_TO_POINTER (keyval), GUINT_TO_POINTER (cached));
+    }
+  else
+    {
+      len = cached & 255;
+      offset = cached >> 8;
+    }
+
+  *n_keys = len;
+  *keys = (GdkKeymapKey *)&g_array_index (keymap->cached_keys, GdkKeymapKey, offset);
 }
 
 /**
diff --git a/gdk/gdkkeysprivate.h b/gdk/gdkkeysprivate.h
index c7cf7424b6..79ad146b14 100644
--- a/gdk/gdkkeysprivate.h
+++ b/gdk/gdkkeysprivate.h
@@ -43,8 +43,7 @@ struct _GdkKeymapClass
   gboolean (* get_scroll_lock_state)    (GdkKeymap *keymap);
   gboolean (* get_entries_for_keyval)   (GdkKeymap     *keymap,
                                          guint          keyval,
-                                         GdkKeymapKey **keys,
-                                         gint          *n_keys);
+                                         GArray        *array);
   gboolean (* get_entries_for_keycode)  (GdkKeymap     *keymap,
                                          guint          hardware_keycode,
                                          GdkKeymapKey **keys,
@@ -73,6 +72,17 @@ struct _GdkKeymap
 {
   GObject     parent_instance;
   GdkDisplay *display;
+
+  /* We cache an array of GdkKeymapKey entries for keyval -> keycode
+   * lookup. Position 0 is unused.
+   *
+   * The hash table maps keyvals to values that have the number of keys
+   * in the low 8 bits, and the position in the array in the rest.
+   *
+   * The cache is cleared before ::keys-changed is emitted.
+   */
+  GArray *cached_keys;
+  GHashTable *cache;
 };
 
 GType gdk_keymap_get_type (void) G_GNUC_CONST;
@@ -106,6 +116,11 @@ gboolean       gdk_keymap_get_num_lock_state       (GdkKeymap           *keymap)
 gboolean       gdk_keymap_get_scroll_lock_state    (GdkKeymap           *keymap);
 guint          gdk_keymap_get_modifier_state       (GdkKeymap           *keymap);
 
+void           gdk_keymap_get_cached_entries_for_keyval (GdkKeymap     *keymap,
+                                                         guint          keyval,
+                                                         GdkKeymapKey **keys,
+                                                         guint         *n_keys);
+
 G_END_DECLS
 
 #endif
diff --git a/gdk/wayland/gdkkeys-wayland.c b/gdk/wayland/gdkkeys-wayland.c
index 1b98c73e85..802463298e 100644
--- a/gdk/wayland/gdkkeys-wayland.c
+++ b/gdk/wayland/gdkkeys-wayland.c
@@ -126,17 +126,14 @@ gdk_wayland_keymap_get_scroll_lock_state (GdkKeymap *keymap)
 }
 
 static gboolean
-gdk_wayland_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
-					   guint          keyval,
-					   GdkKeymapKey **keys,
-					   gint          *n_keys)
+gdk_wayland_keymap_get_entries_for_keyval (GdkKeymap *keymap,
+                                           guint      keyval,
+                                           GArray    *retval)
 {
   struct xkb_keymap *xkb_keymap = GDK_WAYLAND_KEYMAP (keymap)->xkb_keymap;
-  GArray *retval;
   guint keycode;
   xkb_keycode_t min_keycode, max_keycode;
-
-  retval = g_array_new (FALSE, FALSE, sizeof (GdkKeymapKey));
+  guint len = retval->len;
 
   min_keycode = xkb_keymap_min_keycode (xkb_keymap);
   max_keycode = xkb_keymap_max_keycode (xkb_keymap);
@@ -170,10 +167,7 @@ gdk_wayland_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
         }
     }
 
-  *n_keys = retval->len;
-  *keys = (GdkKeymapKey*) g_array_free (retval, FALSE);
-
-  return TRUE;
+  return retval->len > len;
 }
 
 static gboolean
diff --git a/gdk/win32/gdkkeys-win32.c b/gdk/win32/gdkkeys-win32.c
index bae9a8e24d..972008492d 100644
--- a/gdk/win32/gdkkeys-win32.c
+++ b/gdk/win32/gdkkeys-win32.c
@@ -1283,19 +1283,14 @@ gdk_win32_keymap_get_scroll_lock_state (GdkKeymap *keymap)
 static gboolean
 gdk_win32_keymap_get_entries_for_keyval (GdkKeymap     *gdk_keymap,
                                          guint          keyval,
-                                         GdkKeymapKey **keys,
-                                         gint          *n_keys)
+                                         GArray        *retval)
 {
-  GArray *retval;
   GdkKeymap *default_keymap = gdk_display_get_keymap (gdk_display_get_default ());
+  guint len = retval->len;
 
   g_return_val_if_fail (gdk_keymap == NULL || GDK_IS_KEYMAP (gdk_keymap), FALSE);
-  g_return_val_if_fail (keys != NULL, FALSE);
-  g_return_val_if_fail (n_keys != NULL, FALSE);
   g_return_val_if_fail (keyval != 0, FALSE);
 
-  retval = g_array_new (FALSE, FALSE, sizeof (GdkKeymapKey));
-
   /* Accept only the default keymap */
   if (gdk_keymap == NULL || gdk_keymap == default_keymap)
     {
@@ -1344,7 +1339,7 @@ gdk_win32_keymap_get_entries_for_keyval (GdkKeymap     *gdk_keymap,
 
       g_print ("gdk_keymap_get_entries_for_keyval: %#.04x (%s):",
                keyval, gdk_keyval_name (keyval));
-      for (i = 0; i < retval->len; i++)
+      for (i = len; i < retval->len; i++)
         {
           GdkKeymapKey *entry = (GdkKeymapKey *) retval->data + i;
           g_print ("  %#.02x %d %d", entry->keycode, entry->group, entry->level);
@@ -1353,20 +1348,7 @@ gdk_win32_keymap_get_entries_for_keyval (GdkKeymap     *gdk_keymap,
     }
 #endif
 
-  if (retval->len > 0)
-    {
-      *keys = (GdkKeymapKey*) retval->data;
-      *n_keys = retval->len;
-    }
-  else
-    {
-      *keys = NULL;
-      *n_keys = 0;
-    }
-
-  g_array_free (retval, retval->len > 0 ? FALSE : TRUE);
-
-  return *n_keys > 0;
+  return len < retval->len;
 }
 
 static gboolean
diff --git a/gdk/x11/gdkkeys-x11.c b/gdk/x11/gdkkeys-x11.c
index f3c777390d..a322ff27c0 100644
--- a/gdk/x11/gdkkeys-x11.c
+++ b/gdk/x11/gdkkeys-x11.c
@@ -819,15 +819,12 @@ gdk_x11_keymap_get_modifier_state (GdkKeymap *keymap)
 }
 
 static gboolean
-gdk_x11_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
-                                       guint          keyval,
-                                       GdkKeymapKey **keys,
-                                       gint          *n_keys)
+gdk_x11_keymap_get_entries_for_keyval (GdkKeymap *keymap,
+                                       guint      keyval,
+                                       GArray    *retval)
 {
   GdkX11Keymap *keymap_x11 = GDK_X11_KEYMAP (keymap);
-  GArray *retval;
-
-  retval = g_array_new (FALSE, FALSE, sizeof (GdkKeymapKey));
+  guint len = retval->len;
 
 #ifdef HAVE_XKB
   if (KEYMAP_USE_XKB (keymap))
@@ -870,8 +867,7 @@ gdk_x11_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
 
                   g_array_append_val (retval, key);
 
-                  g_assert (XkbKeySymEntry (xkb, keycode, level, group) ==
-                            keyval);
+                  g_assert (XkbKeySymEntry (xkb, keycode, level, group) == keyval);
                 }
 
               ++level;
@@ -923,20 +919,7 @@ gdk_x11_keymap_get_entries_for_keyval (GdkKeymap     *keymap,
         }
     }
 
-  if (retval->len > 0)
-    {
-      *keys = (GdkKeymapKey*) retval->data;
-      *n_keys = retval->len;
-    }
-  else
-    {
-      *keys = NULL;
-      *n_keys = 0;
-    }
-
-  g_array_free (retval, retval->len > 0 ? FALSE : TRUE);
-
-  return *n_keys > 0;
+  return retval->len > len;
 }
 
 static gboolean