[glib] GDBus: Add mechanism to make lookup on interfaces constant-time

[David Zeuthen <davidz src gnome org>]

commit 5bcf54b29cfe65f07d362b48a7fce7ac7c9a6dc3
Author: David Zeuthen <davidz redhat com>
Date:   Mon Mar 28 11:31:05 2011 -0400

    GDBus: Add mechanism to make lookup on interfaces constant-time
    
    This is used both on the service- and client-side and is currently
    O(n).
    
    Signed-off-by: David Zeuthen <davidz redhat com>

 docs/reference/gio/gio-sections.txt |    2 +
 gio/gdbusintrospection.c            |  171 ++++++++++++++++++++++++++++++++++-
 gio/gdbusintrospection.h            |    3 +
 gio/gio.symbols                     |    2 +
 4 files changed, 175 insertions(+), 3 deletions(-)
---
diff --git a/docs/reference/gio/gio-sections.txt b/docs/reference/gio/gio-sections.txt
index 3448e8c..42c98dd 100644
--- a/docs/reference/gio/gio-sections.txt
+++ b/docs/reference/gio/gio-sections.txt
@@ -2613,6 +2613,8 @@ g_dbus_annotation_info_lookup
 g_dbus_interface_info_lookup_method
 g_dbus_interface_info_lookup_signal
 g_dbus_interface_info_lookup_property
+g_dbus_interface_info_cache_build
+g_dbus_interface_info_cache_release
 g_dbus_interface_info_generate_xml
 g_dbus_node_info_new_for_xml
 g_dbus_node_info_lookup_interface
diff --git a/gio/gdbusintrospection.c b/gio/gdbusintrospection.c
index 5d9b6bd..9d9d337 100644
--- a/gio/gdbusintrospection.c
+++ b/gio/gdbusintrospection.c
@@ -1868,6 +1868,37 @@ g_dbus_annotation_info_lookup (GDBusAnnotationInfo **annotations,
 
 /* ---------------------------------------------------------------------------------------------------- */
 
+G_LOCK_DEFINE_STATIC (info_cache_lock);
+
+typedef struct
+{
+  gint use_count;
+
+  /* gchar* -> GDBusMethodInfo* */
+  GHashTable *method_name_to_data;
+
+  /* gchar* -> GDBusMethodInfo* */
+  GHashTable *signal_name_to_data;
+
+  /* gchar* -> GDBusMethodInfo* */
+  GHashTable *property_name_to_data;
+} InfoCacheEntry;
+
+static void
+info_cache_free (InfoCacheEntry *cache)
+{
+  g_assert (cache->use_count == 0);
+  g_hash_table_unref (cache->method_name_to_data);
+  g_hash_table_unref (cache->signal_name_to_data);
+  g_hash_table_unref (cache->property_name_to_data);
+  g_slice_free (InfoCacheEntry, cache);
+}
+
+/* maps from GDBusInterfaceInfo* to InfoCacheEntry* */
+static GHashTable *info_cache = NULL;
+
+/* ---------------------------------------------------------------------------------------------------- */
+
 /**
  * g_dbus_interface_info_lookup_method:
  * @info: A #GDBusInterfaceInfo.
@@ -1875,7 +1906,8 @@ g_dbus_annotation_info_lookup (GDBusAnnotationInfo **annotations,
  *
  * Looks up information about a method.
  *
- * This cost of this function is O(n) in number of methods.
+ * This cost of this function is O(n) in number of methods unless
+ * g_dbus_interface_info_cache_build() has been used on @info.
  *
  * Returns: A #GDBusMethodInfo or %NULL if not found. Do not free, it is owned by @info.
  *
@@ -1888,6 +1920,20 @@ g_dbus_interface_info_lookup_method (GDBusInterfaceInfo *info,
   guint n;
   GDBusMethodInfo *result;
 
+  G_LOCK (info_cache_lock);
+  if (G_LIKELY (info_cache != NULL))
+    {
+      InfoCacheEntry *cache;
+      cache = g_hash_table_lookup (info_cache, info);
+      if (G_LIKELY (cache != NULL))
+        {
+          result = g_hash_table_lookup (cache->method_name_to_data, name);
+          G_UNLOCK (info_cache_lock);
+          goto out;
+        }
+    }
+  G_UNLOCK (info_cache_lock);
+
   for (n = 0; info->methods != NULL && info->methods[n] != NULL; n++)
     {
       GDBusMethodInfo *i = info->methods[n];
@@ -1914,7 +1960,8 @@ g_dbus_interface_info_lookup_method (GDBusInterfaceInfo *info,
  *
  * Looks up information about a signal.
  *
- * This cost of this function is O(n) in number of signals.
+ * This cost of this function is O(n) in number of signals unless
+ * g_dbus_interface_info_cache_build() has been used on @info.
  *
  * Returns: A #GDBusSignalInfo or %NULL if not found. Do not free, it is owned by @info.
  *
@@ -1927,6 +1974,20 @@ g_dbus_interface_info_lookup_signal (GDBusInterfaceInfo *info,
   guint n;
   GDBusSignalInfo *result;
 
+  G_LOCK (info_cache_lock);
+  if (G_LIKELY (info_cache != NULL))
+    {
+      InfoCacheEntry *cache;
+      cache = g_hash_table_lookup (info_cache, info);
+      if (G_LIKELY (cache != NULL))
+        {
+          result = g_hash_table_lookup (cache->signal_name_to_data, name);
+          G_UNLOCK (info_cache_lock);
+          goto out;
+        }
+    }
+  G_UNLOCK (info_cache_lock);
+
   for (n = 0; info->signals != NULL && info->signals[n] != NULL; n++)
     {
       GDBusSignalInfo *i = info->signals[n];
@@ -1953,7 +2014,8 @@ g_dbus_interface_info_lookup_signal (GDBusInterfaceInfo *info,
  *
  * Looks up information about a property.
  *
- * This cost of this function is O(n) in number of properties.
+ * This cost of this function is O(n) in number of properties unless
+ * g_dbus_interface_info_cache_build() has been used on @info.
  *
  * Returns: A #GDBusPropertyInfo or %NULL if not found. Do not free, it is owned by @info.
  *
@@ -1966,6 +2028,20 @@ g_dbus_interface_info_lookup_property (GDBusInterfaceInfo *info,
   guint n;
   GDBusPropertyInfo *result;
 
+  G_LOCK (info_cache_lock);
+  if (G_LIKELY (info_cache != NULL))
+    {
+      InfoCacheEntry *cache;
+      cache = g_hash_table_lookup (info_cache, info);
+      if (G_LIKELY (cache != NULL))
+        {
+          result = g_hash_table_lookup (cache->property_name_to_data, name);
+          G_UNLOCK (info_cache_lock);
+          goto out;
+        }
+    }
+  G_UNLOCK (info_cache_lock);
+
   for (n = 0; info->properties != NULL && info->properties[n] != NULL; n++)
     {
       GDBusPropertyInfo *i = info->properties[n];
@@ -1986,6 +2062,95 @@ g_dbus_interface_info_lookup_property (GDBusInterfaceInfo *info,
 /* ---------------------------------------------------------------------------------------------------- */
 
 /**
+ * g_dbus_interface_info_cache_build:
+ * @info: A #GDBusInterfaceInfo.
+ *
+ * Builds a lookup-cache to speed up
+ * g_dbus_interface_info_lookup_method(),
+ * g_dbus_interface_info_lookup_signal() and
+ * g_dbus_interface_info_lookup_property().
+ *
+ * If this has already been called with @info, the existing cache is
+ * used and its use count is increased.
+ *
+ * Note that @info cannot be modified until
+ * g_dbus_interface_info_cache_release() is called.
+ *
+ * Since: 2.30
+ */
+void
+g_dbus_interface_info_cache_build (GDBusInterfaceInfo *info)
+{
+  InfoCacheEntry *cache;
+  guint n;
+
+  G_LOCK (info_cache_lock);
+  if (info_cache == NULL)
+    info_cache = g_hash_table_new_full (g_direct_hash, g_direct_equal, NULL, (GDestroyNotify) info_cache_free);
+  cache = g_hash_table_lookup (info_cache, info);
+  if (cache != NULL)
+    {
+      cache->use_count += 1;
+      goto out;
+    }
+  cache = g_slice_new0 (InfoCacheEntry);
+  cache->use_count = 1;
+  cache->method_name_to_data = g_hash_table_new (g_str_hash, g_str_equal);
+  cache->signal_name_to_data = g_hash_table_new (g_str_hash, g_str_equal);
+  cache->property_name_to_data = g_hash_table_new (g_str_hash, g_str_equal);
+  for (n = 0; info->methods != NULL && info->methods[n] != NULL; n++)
+    g_hash_table_insert (cache->method_name_to_data, info->methods[n]->name, info->methods[n]);
+  for (n = 0; info->signals != NULL && info->signals[n] != NULL; n++)
+    g_hash_table_insert (cache->signal_name_to_data, info->signals[n]->name, info->signals[n]);
+  for (n = 0; info->properties != NULL && info->properties[n] != NULL; n++)
+    g_hash_table_insert (cache->property_name_to_data, info->properties[n]->name, info->properties[n]);
+  g_hash_table_insert (info_cache, info, cache);
+ out:
+  G_UNLOCK (info_cache_lock);
+}
+
+/**
+ * g_dbus_interface_info_cache_release:
+ * @info: A GDBusInterfaceInfo
+ *
+ * Decrements the usage count for the cache for @info built by
+ * g_dbus_interface_info_cache_build() (if any) and frees the
+ * resources used by the cache if the usage count drops to zero.
+ *
+ * Since: 2.30
+ */
+void
+g_dbus_interface_info_cache_release (GDBusInterfaceInfo *info)
+{
+  InfoCacheEntry *cache;
+
+  G_LOCK (info_cache_lock);
+  if (G_UNLIKELY (info_cache == NULL))
+    {
+      g_warning ("%s called for interface %s but there is no cache", info->name, G_STRFUNC);
+      goto out;
+    }
+
+  cache = g_hash_table_lookup (info_cache, info);
+  if (G_UNLIKELY (cache == NULL))
+    {
+      g_warning ("%s called for interface %s but there is no cache entry", info->name, G_STRFUNC);
+      goto out;
+    }
+  cache->use_count -= 1;
+  if (cache->use_count == 0)
+    {
+      g_hash_table_remove (info_cache, info);
+      /* could nuke info_cache itself if empty */
+    }
+ out:
+  G_UNLOCK (info_cache_lock);
+}
+
+
+/* ---------------------------------------------------------------------------------------------------- */
+
+/**
  * g_dbus_node_info_lookup_interface:
  * @info: A #GDBusNodeInfo.
  * @name: A D-Bus interface name.
diff --git a/gio/gdbusintrospection.h b/gio/gdbusintrospection.h
index 2c02421..1280098 100644
--- a/gio/gdbusintrospection.h
+++ b/gio/gdbusintrospection.h
@@ -182,6 +182,9 @@ GDBusSignalInfo    *g_dbus_interface_info_lookup_signal    (GDBusInterfaceInfo
                                                             const gchar          *name);
 GDBusPropertyInfo  *g_dbus_interface_info_lookup_property  (GDBusInterfaceInfo   *info,
                                                             const gchar          *name);
+void                g_dbus_interface_info_cache_build      (GDBusInterfaceInfo   *info);
+void                g_dbus_interface_info_cache_release    (GDBusInterfaceInfo   *info);
+
 void                g_dbus_interface_info_generate_xml     (GDBusInterfaceInfo   *info,
                                                             guint                 indent,
                                                             GString              *string_builder);
diff --git a/gio/gio.symbols b/gio/gio.symbols
index 2a7853d..b46da2c 100644
--- a/gio/gio.symbols
+++ b/gio/gio.symbols
@@ -1725,6 +1725,8 @@ g_dbus_interface_info_generate_xml
 g_dbus_interface_info_lookup_method
 g_dbus_interface_info_lookup_property
 g_dbus_interface_info_lookup_signal
+g_dbus_interface_info_cache_build
+g_dbus_interface_info_cache_release
 g_dbus_node_info_new_for_xml
 g_dbus_node_info_generate_xml
 g_dbus_node_info_lookup_interface