[gtk/css-lookup-caching: 19/26] lookup: Merge rulesets more efficiently

[Matthias Clasen <matthiasc src gnome org>]

commit 05e3ad9f1ea46e2754f3d3bca6c35512792a4e14
Author: Matthias Clasen <mclasen redhat com>
Date:   Tue Feb 11 17:30:28 2020 -0500

    lookup: Merge rulesets more efficiently
    
    Keep lookups sorted, and take advantage of the fact
    that the rulesets are sorted, too. We can merge them
    in a linear sweep.

 gtk/gtkcsslookup.c        | 72 ++++++++++++++++++++++++++++-------------------
 gtk/gtkcsslookupprivate.h |  8 ++----
 gtk/gtkcssprovider.c      | 11 +-------
 3 files changed, 47 insertions(+), 44 deletions(-)
---
diff --git a/gtk/gtkcsslookup.c b/gtk/gtkcsslookup.c
index bcce8d2a49..7e52359b65 100644
--- a/gtk/gtkcsslookup.c
+++ b/gtk/gtkcsslookup.c
@@ -68,41 +68,55 @@ gtk_css_lookup_unref (GtkCssLookup *lookup)
     gtk_css_lookup_free (lookup);
 }
 
-gboolean
-gtk_css_lookup_is_missing (const GtkCssLookup *lookup,
-                           guint               id)
-{
-  gtk_internal_return_val_if_fail (lookup != NULL, FALSE);
-
-  return !_gtk_bitmask_get (lookup->set_values, id);
-}
-
-/**
- * _gtk_css_lookup_set:
- * @lookup: the lookup
- * @id: id of the property to set, see _gtk_style_property_get_id()
- * @section: (allow-none): The @section the value was defined in or %NULL
- * @value: the “cascading value” to use
- *
- * Sets the @value for a given @id. No value may have been set for @id
- * before. See _gtk_css_lookup_is_missing(). This function is used to
- * set the “winning declaration” of a lookup. Note that for performance
- * reasons @value and @section are not copied. It is your responsibility
- * to ensure they are kept alive until _gtk_css_lookup_free() is called.
- **/
 void
-gtk_css_lookup_set (GtkCssLookup      *lookup,
-                    guint              id,
-                    GtkCssLookupValue *value)
+gtk_css_lookup_merge (GtkCssLookup      *lookup,
+                      GtkCssLookupValue *values,
+                      guint              n_values)
 {
+  int i, j;
+
   gtk_internal_return_if_fail (lookup != NULL);
-  gtk_internal_return_if_fail (value != NULL);
+  gtk_internal_return_if_fail (values != NULL);
 
   if (!lookup->values)
-    lookup->values = g_ptr_array_sized_new (16);
+    lookup->values = g_ptr_array_sized_new (MAX (16, n_values));
+
+  i = j = 0;
+  while (j < n_values)
+    {
+      GtkCssLookupValue *v;
+
+      if (i == lookup->values->len)
+        break;
+
+      v =  g_ptr_array_index (lookup->values, i);
 
-  g_ptr_array_add (lookup->values, value);
-  lookup->set_values = _gtk_bitmask_set (lookup->set_values, id, TRUE);
+      if (v->id < values[j].id)
+        {
+          i++;
+        }
+      else if (v->id > values[j].id)
+        {
+          /* insert value[j] here */
+          g_ptr_array_insert (lookup->values, i, &values[j]);
+          lookup->set_values = _gtk_bitmask_set (lookup->set_values, values[j].id, TRUE);
+          i++;
+          j++;
+        }
+      else
+        {
+          /* value[j] is already set, skip */
+          i++;
+          j++;
+        }
+    }
+
+  /* append remaining values */
+  for (; j < n_values; j++)
+    {
+      g_ptr_array_add (lookup->values, &values[j]);
+      lookup->set_values = _gtk_bitmask_set (lookup->set_values, values[j].id, TRUE);
+    }
 }
 
 GtkCssSection *
diff --git a/gtk/gtkcsslookupprivate.h b/gtk/gtkcsslookupprivate.h
index 2d61d9b2c0..f73d8f56de 100644
--- a/gtk/gtkcsslookupprivate.h
+++ b/gtk/gtkcsslookupprivate.h
@@ -46,11 +46,9 @@ GtkCssLookup *           gtk_css_lookup_new (void);
 GtkCssLookup *           gtk_css_lookup_ref (GtkCssLookup *lookup);
 void                     gtk_css_lookup_unref (GtkCssLookup *lookup);
 
-gboolean                 gtk_css_lookup_is_missing              (const GtkCssLookup         *lookup,
-                                                                 guint                       id);
-void                     gtk_css_lookup_set                     (GtkCssLookup               *lookup,
-                                                                 guint                       id,
-                                                                 GtkCssLookupValue          *value);
+void                     gtk_css_lookup_merge                   (GtkCssLookup               *lookup,
+                                                                 GtkCssLookupValue          *values,
+                                                                 guint                       n_values);
 GtkCssSection *          gtk_css_lookup_get_section             (GtkCssLookup               *lookup,
                                                                  guint                       id);
 
diff --git a/gtk/gtkcssprovider.c b/gtk/gtkcssprovider.c
index 6601d6564b..0489ba8bed 100644
--- a/gtk/gtkcssprovider.c
+++ b/gtk/gtkcssprovider.c
@@ -466,7 +466,6 @@ gtk_css_style_provider_lookup (GtkStyleProvider             *provider,
   GtkCssProvider *css_provider = GTK_CSS_PROVIDER (provider);
   GtkCssProviderPrivate *priv = gtk_css_provider_get_instance_private (css_provider);
   GtkCssRuleset *ruleset;
-  guint j;
   int i;
   GPtrArray *tree_rules;
 
@@ -485,15 +484,7 @@ gtk_css_style_provider_lookup (GtkStyleProvider             *provider,
           if (ruleset->styles == NULL)
             continue;
 
-          for (j = 0; j < ruleset->n_styles; j++)
-            {
-              guint id = ruleset->styles[j].id;
-
-              if (!gtk_css_lookup_is_missing (lookup, id))
-                continue;
-
-              gtk_css_lookup_set (lookup, id, (GtkCssLookupValue *)&ruleset->styles[j]);
-            }
+          gtk_css_lookup_merge (lookup, (GtkCssLookupValue *)ruleset->styles, ruleset->n_styles);
         }
 
       g_ptr_array_free (tree_rules, TRUE);