[gobject-introspection] Optimize g_irepository_find_by_gtype

[Colin Walters <walters src gnome org>]

commit 99a7287bb152dc4df299255f42b04ab1766ca6a6
Author: Daniel Drake <dsd laptop org>
Date:   Tue Mar 19 11:04:42 2013 -0600

    Optimize g_irepository_find_by_gtype
    
    When g_irepository_find_by_gtype() doesn't succeed on a simple prefix
    match (the current 'fastpass' mechanism), it ends up taking a
    considerable amount of CPU time, traversing the contents of all typelibs.
    
    I imagine that the reasons to have the exhaustive search fallback are
    not as strong as they used to be. For example, the case mentioned
    (Clutter including Cogl) no longer seems to be true.
    
    Also, typelibs (as generated by g-ir-scanner) now provide
    comma-separated C prefix info for cases when the typelib includes
    introspection info for multiple prefixes. For example, the Sugar typelib
    has a c_prefix string of Sugar,EggSM,Gsm,Acme. So I imagine there are
    not many remaining justified cases where the exhaustive search is needed.
    
    With that in mind, I found two ways to optimize this function:
    
    1. Support comma-separated C prefixes
    
    2. Don't bother with an exhaustive search if we did find a typelib
       claiming support for the prefix. For example, if we're looking for
       GdkDeviceManagerXI2 (currently non-introspectable) and we already found
       typelib files providing the 'Gdk' prefix that didn't offer this, lets
       not bother with the exhaustive search, we aren't going to find anything.

 girepository/girepository.c       |  105 +++++++++++++++++++++++++------------
 girepository/gitypelib-internal.h |    8 ++-
 girepository/gitypelib.c          |   84 +++++++++++++++---------------
 3 files changed, 118 insertions(+), 79 deletions(-)
---
diff --git a/girepository/girepository.c b/girepository/girepository.c
index ccdd361..0922fb0 100644
--- a/girepository/girepository.c
+++ b/girepository/girepository.c
@@ -593,28 +593,39 @@ g_irepository_get_info (GIRepository *repository,
 }
 
 typedef struct {
-  GIRepository *repository;
-  GType type;
-
-  gboolean fastpass;
+  const gchar *gtype_name;
   GITypelib *result_typelib;
-  DirEntry *result;
+  gboolean found_prefix;
 } FindByGTypeData;
 
-static void
-find_by_gtype_foreach (gpointer key,
-                      gpointer value,
-                      gpointer datap)
+static DirEntry *
+find_by_gtype (GHashTable *table, FindByGTypeData *data, gboolean check_prefix)
 {
-  GITypelib *typelib = (GITypelib*)value;
-  FindByGTypeData *data = datap;
+  GHashTableIter iter;
+  gpointer key, value;
+  DirEntry *ret;
 
-  if (data->result != NULL)
-    return;
+  g_hash_table_iter_init (&iter, table);
+  while (g_hash_table_iter_next (&iter, &key, &value))
+    {
+      GITypelib *typelib = (GITypelib*)value;
+      if (check_prefix)
+        {
+          if (!g_typelib_matches_gtype_name_prefix (typelib, data->gtype_name))
+            continue;
 
-  data->result = g_typelib_get_dir_entry_by_gtype (typelib, data->fastpass, data->type);
-  if (data->result)
-    data->result_typelib = typelib;
+          data->found_prefix = TRUE;
+        }
+
+      ret = g_typelib_get_dir_entry_by_gtype_name (typelib, data->gtype_name);
+      if (ret)
+        {
+          data->result_typelib = typelib;
+          return ret;
+        }
+    }
+
+  return NULL;
 }
 
 /**
@@ -637,6 +648,7 @@ g_irepository_find_by_gtype (GIRepository *repository,
 {
   FindByGTypeData data;
   GIBaseInfo *cached;
+  DirEntry *entry;
 
   repository = get_repository (repository);
 
@@ -646,30 +658,55 @@ g_irepository_find_by_gtype (GIRepository *repository,
   if (cached != NULL)
     return g_base_info_ref (cached);
 
-  data.repository = repository;
-  data.fastpass = TRUE;
-  data.type = gtype;
+  data.gtype_name = g_type_name (gtype);
   data.result_typelib = NULL;
-  data.result = NULL;
+  data.found_prefix = FALSE;
+
+  /* There is a corner case regarding GdkRectangle.  GdkRectangle is a
+   * boxed type, but it is just an alias to boxed struct
+   * CairoRectangleInt.  Scanner automatically converts all references
+   * to GdkRectangle to CairoRectangleInt, so GdkRectangle does not
+   * appear in the typelibs at all, although user code might query it.
+   * So if we get such query, we also change it to lookup of
+   * CairoRectangleInt.
+   * https://bugzilla.gnome.org/show_bug.cgi?id=655423
+   */
+  if (G_UNLIKELY (!strcmp (data.gtype_name, "GdkRectangle")))
+    data.gtype_name = "CairoRectangleInt";
+
+  /* Inside each typelib, we include the "C prefix" which acts as
+   * a namespace mechanism.  For GtkTreeView, the C prefix is Gtk.
+   * Given the assumption that GTypes for a library also use the
+   * C prefix, we know we can skip examining a typelib if our
+   * target type does not have this typelib's C prefix. Use this
+   * assumption as our first attempt at locating the DirEntry.
+   */
+  entry = find_by_gtype (repository->priv->typelibs, &data, TRUE);
+  if (entry == NULL)
+    entry = find_by_gtype (repository->priv->lazy_typelibs, &data, TRUE);
 
-  g_hash_table_foreach (repository->priv->typelibs, find_by_gtype_foreach, &data);
-  if (data.result == NULL)
-    g_hash_table_foreach (repository->priv->lazy_typelibs, find_by_gtype_foreach, &data);
+  /* If we have no result, but we did find a typelib claiming to
+   * offer bindings for such a prefix, bail out now on the assumption
+   * that a more exhaustive search would not produce any results.
+   */
+  if (entry == NULL && data.found_prefix)
+      return NULL;
 
-  /* We do two passes; see comment in find_interface */
-  if (data.result == NULL)
-    {
-      data.fastpass = FALSE;
-      g_hash_table_foreach (repository->priv->typelibs, find_by_gtype_foreach, &data);
-    }
-  if (data.result == NULL)
-    g_hash_table_foreach (repository->priv->lazy_typelibs, find_by_gtype_foreach, &data);
+  /* Not ever class library necessarily specifies a correct c_prefix,
+   * so take a second pass. This time we will try a global lookup,
+   * ignoring prefixes.
+   * See http://bugzilla.gnome.org/show_bug.cgi?id=564016
+   */
+  if (entry == NULL)
+    entry = find_by_gtype (repository->priv->typelibs, &data, FALSE);
+  if (entry == NULL)
+    entry = find_by_gtype (repository->priv->lazy_typelibs, &data, FALSE);
 
-  if (data.result != NULL)
+  if (entry != NULL)
     {
-      cached = _g_info_new_full (data.result->blob_type,
+      cached = _g_info_new_full (entry->blob_type,
                                 repository,
-                                NULL, data.result_typelib, data.result->offset);
+                                NULL, data.result_typelib, entry->offset);
 
       g_hash_table_insert (repository->priv->info_by_gtype,
                           (gpointer) gtype,
diff --git a/girepository/gitypelib-internal.h b/girepository/gitypelib-internal.h
index 04662b4..ac71008 100644
--- a/girepository/gitypelib-internal.h
+++ b/girepository/gitypelib-internal.h
@@ -1126,13 +1126,15 @@ DirEntry *g_typelib_get_dir_entry (GITypelib *typelib,
 DirEntry *g_typelib_get_dir_entry_by_name (GITypelib *typelib,
                                           const char *name);
 
-DirEntry *g_typelib_get_dir_entry_by_gtype (GITypelib *typelib,
-                                           gboolean   fastpass,
-                                           GType      gtype);
+DirEntry *g_typelib_get_dir_entry_by_gtype_name (GITypelib *typelib,
+                                                const gchar *gtype_name);
 
 DirEntry *g_typelib_get_dir_entry_by_error_domain (GITypelib *typelib,
                                                   GQuark     error_domain);
 
+gboolean  g_typelib_matches_gtype_name_prefix (GITypelib *typelib,
+                                              const gchar *gtype_name);
+
 void      g_typelib_check_sanity (void);
 
 #define   g_typelib_get_string(typelib,offset) ((const gchar*)&(typelib->data)[(offset)])
diff --git a/girepository/gitypelib.c b/girepository/gitypelib.c
index 76a55de..2512e52 100644
--- a/girepository/gitypelib.c
+++ b/girepository/gitypelib.c
@@ -198,55 +198,17 @@ g_typelib_get_dir_entry_by_name (GITypelib *typelib,
 }
 
 DirEntry *
-g_typelib_get_dir_entry_by_gtype (GITypelib *typelib,
-                                 gboolean   fastpass,
-                                 GType      gtype)
+g_typelib_get_dir_entry_by_gtype_name (GITypelib *typelib,
+                                      const gchar *gtype_name)
 {
   Header *header = (Header *)typelib->data;
-  guint n_entries = header->n_local_entries;
-  const char *gtype_name = g_type_name (gtype);
-  DirEntry *entry;
   guint i;
-  const char *c_prefix;
 
-  /* There is a corner case regarding GdkRectangle.  GdkRectangle is a
-     boxed type, but it is just an alias to boxed struct
-     CairoRectangleInt.  Scanner automatically converts all references
-     to GdkRectangle to CairoRectangleInt, so GdkRectangle does not
-     appear in the typelibs at all, although user code might query it.
-     So if we get such query, we also change it to lookup of
-     CairoRectangleInt.
-     https://bugzilla.gnome.org/show_bug.cgi?id=655423 */
-  if (!fastpass && !strcmp (gtype_name, "GdkRectangle"))
-    gtype_name = "CairoRectangleInt";
-
-  /* Inside each typelib, we include the "C prefix" which acts as
-   * a namespace mechanism.  For GtkTreeView, the C prefix is Gtk.
-   * Given the assumption that GTypes for a library also use the
-   * C prefix, we know we can skip examining a typelib if our
-   * target type does not have this typelib's C prefix.
-   *
-   * However, not every class library necessarily conforms to this,
-   * e.g. Clutter has Cogl inside it.  So, we split this into two
-   * passes.  First we try a lookup, skipping things which don't
-   * have the prefix.  If that fails then we try a global lookup,
-   * ignoring the prefix.
-   *
-   * See http://bugzilla.gnome.org/show_bug.cgi?id=564016
-   */
-  c_prefix = g_typelib_get_string (typelib, header->c_prefix);
-  if (fastpass && c_prefix != NULL)
-    {
-      if (g_ascii_strncasecmp (c_prefix, gtype_name, strlen (c_prefix)) != 0)
-       return NULL;
-    }
-
-  for (i = 1; i <= n_entries; i++)
+  for (i = 1; i <= header->n_local_entries; i++)
     {
       RegisteredTypeBlob *blob;
       const char *type;
-
-      entry = g_typelib_get_dir_entry (typelib, i);
+      DirEntry *entry = g_typelib_get_dir_entry (typelib, i);
       if (!BLOB_IS_REGISTERED_TYPE (entry))
        continue;
 
@@ -261,6 +223,44 @@ g_typelib_get_dir_entry_by_gtype (GITypelib *typelib,
   return NULL;
 }
 
+gboolean
+g_typelib_matches_gtype_name_prefix (GITypelib *typelib,
+                                    const gchar *gtype_name)
+{
+  Header *header = (Header *)typelib->data;
+  const char *c_prefix;
+  gchar **prefixes;
+  gchar **prefix;
+  gboolean ret = FALSE;
+
+  c_prefix = g_typelib_get_string (typelib, header->c_prefix);
+  if (c_prefix == NULL)
+    return FALSE;
+
+  /* c_prefix is a comma separated string of supported prefixes
+   * in the typelib.
+   * We match the specified gtype_name if the gtype_name starts
+   * with the prefix, and is followed by a capital letter.
+   * For example, a typelib offering the 'Gdk' prefix does match
+   * GdkX11Cursor, however a typelib offering the 'G' prefix does not.
+   */
+  prefixes = g_strsplit (c_prefix, ",", 0);
+  for (prefix = prefixes; *prefix; prefix++)
+    {
+      size_t len = strlen (*prefix);
+      if (strncmp (*prefix, gtype_name, len))
+        continue;
+
+      if (strlen (gtype_name) > len && g_ascii_isupper (gtype_name[len]))
+        {
+          ret = TRUE;
+          break;
+        }
+    }
+  g_strfreev(prefixes);
+  return ret;
+}
+
 DirEntry *
 g_typelib_get_dir_entry_by_error_domain (GITypelib *typelib,
                                         GQuark     error_domain)