[gtk/wip/otte/css: 1/12] css: Add fast-path for parent selector matching



commit a25ec4eda2a9b129292d123395b00b20d8ff2e78
Author: Benjamin Otte <otte redhat com>
Date:   Sun Jan 26 04:37:17 2020 +0100

    css: Add fast-path for parent selector matching
    
    Add a fast path for parent selector matching that uses a bloom filter to
    quickly discard selectors that can't possibly match.
    
    Keep in mind that we match using a bloom filter, so we might
    accidentally include too many selectors when hash/bucket collisions
    occur.
    That's not a correctness problem though, because we'll do a real check
    afterwards.
    
    The idea for this change is taken from browsers, in particular WebKit.

 gtk/gtkcountingbloomfilterprivate.h | 158 ++++++++++++++++++++++++++++++++++++
 gtk/gtkcssnode.c                    |  55 +++++++++----
 gtk/gtkcssnodedeclaration.c         |  34 ++++++++
 gtk/gtkcssnodedeclarationprivate.h  |   6 ++
 gtk/gtkcssnodeprivate.h             |   2 +
 gtk/gtkcssprovider.c                |  11 +--
 gtk/gtkcssselector.c                | 111 +++++++++++++++++++------
 gtk/gtkcssselectorprivate.h         |   2 +
 gtk/gtkcssstaticstyle.c             |  10 ++-
 gtk/gtkcssstaticstyleprivate.h      |  27 +++---
 gtk/gtkcsstransientnode.c           |  11 +--
 gtk/gtkstylecascade.c               |  11 +--
 gtk/gtkstyleprovider.c              |  11 +--
 gtk/gtkstyleproviderprivate.h       |   3 +
 14 files changed, 373 insertions(+), 79 deletions(-)
---
diff --git a/gtk/gtkcountingbloomfilterprivate.h b/gtk/gtkcountingbloomfilterprivate.h
new file mode 100644
index 0000000000..9151901d75
--- /dev/null
+++ b/gtk/gtkcountingbloomfilterprivate.h
@@ -0,0 +1,158 @@
+/*
+ * Copyright © 2020 Benjamin Otte
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Benjamin Otte <otte gnome org>
+ */
+
+#ifndef __GTK_COUNTING_BLOOM_FILTER_PRIVATE_H__
+#define __GTK_COUNTING_BLOOM_FILTER_PRIVATE_H__
+
+#include <glib.h>
+
+
+G_BEGIN_DECLS
+
+/*
+ * SECTION:gtkcountingbloomfilter
+ * @Short_description: A counting bloom filter
+ * @Title: GtkCountingBloomFilter
+ * @See_also: https://en.wikipedia.org/wiki/Bloom_filter,
+ *            https://en.wikipedia.org/wiki/Counting_Bloom_filter
+ *
+ * This implements a counting bloom filter. A bloom filter is a space-efficient
+ * probabilistic data structure that is used to test whether an element may be
+ * a member of a set.  
+ * The Wikipedia links provide a lot more details into how and why this data
+ * structure works and when to use it.
+ *
+ * This implementation is based on similar implementations in web browsers, because it's
+ * original use case is the same: Making CSS lookups fast.
+ *
+ * As such, the number of bits is hardcoded to 12 and the elements in the set
+ * are 16bit hash values.  
+ * It is possible to use 32bit hash values or a different number of bits, should this
+ * be considered useful.
+ */
+
+/* The number of bits from the hash we care about */
+#define GTK_COUNTING_BLOOM_FILTER_BITS (12)
+
+/* The necessary size of the filter */
+#define GTK_COUNTING_BLOOM_FILTER_SIZE (1 << GTK_COUNTING_BLOOM_FILTER_BITS)
+
+typedef struct _GtkCountingBloomFilter GtkCountingBloomFilter;
+
+struct _GtkCountingBloomFilter
+{
+  guint8        buckets[GTK_COUNTING_BLOOM_FILTER_SIZE];
+};
+
+static inline void      gtk_counting_bloom_filter_add           (GtkCountingBloomFilter         *self,
+                                                                 guint16                         hash);
+static inline void      gtk_counting_bloom_filter_remove        (GtkCountingBloomFilter         *self,
+                                                                 guint16                         hash);
+static inline gboolean  gtk_counting_bloom_filter_may_contain   (const GtkCountingBloomFilter   *self,
+                                                                 guint16                         hash);
+
+
+/*
+ * GTK_COUNTING_BLOOM_FILTER_INIT:
+ *
+ * Initialize the bloom filter. As bloom filters are always stack-allocated,
+ * initialization should happen when defining them, like:
+ * ```c
+ * GtkCountingBloomFilter filter = GTK_COUNTING_BLOOM_FILTER_INIT;
+ * ```
+ *
+ * The filter does not need to be freed.
+ */
+#define GTK_COUNTING_BLOOM_FILTER_INIT { 0, }
+
+/*
+ * gtk_counting_bloom_filter_add:
+ * @self: a #GtkCountingBloomFilter
+ * @hash: a hash value to add to the filter
+ *
+ * Adds the hash value to the filter.
+ *
+ * If the same hash value gets added multiple times, it will
+ * be considered as contained in the hash until it has been
+ * removed as many times.
+ **/
+static inline void
+gtk_counting_bloom_filter_add (GtkCountingBloomFilter *self,
+                               guint16                 hash)
+{
+  guint16 bucket = hash % GTK_COUNTING_BLOOM_FILTER_SIZE;
+
+  if (self->buckets[bucket] == 255)
+    return;
+
+  self->buckets[bucket]++;
+}
+
+/*
+ * gtk_counting_bloom_filter_remove:
+ * @self: a #GtkCountingBloomFilter
+ * @hash: a hash value to remove from the filter
+ *
+ * Removes a hash value from the filter that has previously
+ * been added via gtk_counting_bloom_filter_add().
+ **/
+static inline void
+gtk_counting_bloom_filter_remove (GtkCountingBloomFilter *self,
+                                  guint16                 hash)
+{
+  guint16 bucket = hash % GTK_COUNTING_BLOOM_FILTER_SIZE;
+
+  if (self->buckets[bucket] == 255)
+    return;
+
+  g_assert (self->buckets[bucket] > 0);
+
+  self->buckets[bucket]--;
+}
+
+/*
+ * gtk_counting_bloom_filter_may_contain:
+ * @self: a #GtkCountingBloomFilter
+ * @hash: the hash value to check
+ *
+ * Checks if @hash may be contained in @self.
+ *
+ * A return value of %FALSE means that @hash is definitely not part
+ * of @self.
+ *
+ * A return value of %TRUE means that @hash may or may not have been
+ * added to @self. In that case a different method must be used to
+ * confirm that @hash is indeed part of the set.
+ *
+ * Returns: %FALSE if @hash is not part of @self.
+ **/
+static inline gboolean
+gtk_counting_bloom_filter_may_contain (const GtkCountingBloomFilter *self,
+                                       guint16                       hash)
+{
+  guint16 bucket = hash % GTK_COUNTING_BLOOM_FILTER_SIZE;
+
+  return self->buckets[bucket] != 0;
+}
+
+
+G_END_DECLS
+
+
+#endif /* __GTK_COUNTING_BLOOM_FILTER_PRIVATE_H_ */
diff --git a/gtk/gtkcssnode.c b/gtk/gtkcssnode.c
index 013e9a26f5..b88e9f4fa3 100644
--- a/gtk/gtkcssnode.c
+++ b/gtk/gtkcssnode.c
@@ -354,8 +354,9 @@ store_in_global_parent_cache (GtkCssNode                  *node,
 }
 
 static GtkCssStyle *
-gtk_css_node_create_style (GtkCssNode   *cssnode,
-                           GtkCssChange  change)
+gtk_css_node_create_style (GtkCssNode                   *cssnode,
+                           const GtkCountingBloomFilter *filter,
+                           GtkCssChange                  change)
 {
   const GtkCssNodeDeclaration *decl;
   GtkCssStyle *style;
@@ -380,6 +381,7 @@ gtk_css_node_create_style (GtkCssNode   *cssnode,
     }
 
   style = gtk_css_static_style_new_compute (gtk_css_node_get_style_provider (cssnode),
+                                            filter,
                                             cssnode,
                                             style_change);
 
@@ -411,17 +413,18 @@ gtk_css_style_needs_recreation (GtkCssStyle  *style,
 }
 
 static GtkCssStyle *
-gtk_css_node_real_update_style (GtkCssNode   *cssnode,
-                                GtkCssChange  change,
-                                gint64        timestamp,
-                                GtkCssStyle  *style)
+gtk_css_node_real_update_style (GtkCssNode                   *cssnode,
+                                const GtkCountingBloomFilter *filter,
+                                GtkCssChange                  change,
+                                gint64                        timestamp,
+                                GtkCssStyle                  *style)
 {
   GtkCssStyle *static_style, *new_static_style, *new_style;
 
   static_style = GTK_CSS_STYLE (gtk_css_style_get_static_style (style));
 
   if (gtk_css_style_needs_recreation (static_style, change))
-    new_static_style = gtk_css_node_create_style (cssnode, change);
+    new_static_style = gtk_css_node_create_style (cssnode, filter, change);
   else
     new_static_style = g_object_ref (static_style);
 
@@ -950,8 +953,9 @@ gtk_css_node_needs_new_style (GtkCssNode *cssnode)
 }
 
 static void
-gtk_css_node_ensure_style (GtkCssNode *cssnode,
-                           gint64      current_time)
+gtk_css_node_ensure_style (GtkCssNode                   *cssnode,
+                           const GtkCountingBloomFilter *filter,
+                           gint64                        current_time)
 {
   gboolean style_changed;
 
@@ -959,18 +963,19 @@ gtk_css_node_ensure_style (GtkCssNode *cssnode,
     return;
 
   if (cssnode->parent)
-    gtk_css_node_ensure_style (cssnode->parent, current_time);
+    gtk_css_node_ensure_style (cssnode->parent, filter, current_time);
 
   if (cssnode->style_is_invalid)
     {
       GtkCssStyle *new_style;
 
       if (cssnode->previous_sibling)
-        gtk_css_node_ensure_style (cssnode->previous_sibling, current_time);
+        gtk_css_node_ensure_style (cssnode->previous_sibling, filter, current_time);
 
       g_clear_pointer (&cssnode->cache, gtk_css_node_style_cache_unref);
 
       new_style = GTK_CSS_NODE_GET_CLASS (cssnode)->update_style (cssnode,
+                                                                  filter,
                                                                   cssnode->pending_changes,
                                                                   current_time,
                                                                   cssnode->style);
@@ -996,7 +1001,7 @@ gtk_css_node_get_style (GtkCssNode *cssnode)
     {
       gint64 timestamp = gtk_css_node_get_timestamp (cssnode);
 
-      gtk_css_node_ensure_style (cssnode, timestamp);
+      gtk_css_node_ensure_style (cssnode, NULL, timestamp);
     }
 
   return cssnode->style;
@@ -1300,15 +1305,17 @@ gtk_css_node_invalidate (GtkCssNode   *cssnode,
 }
 
 static void
-gtk_css_node_validate_internal (GtkCssNode *cssnode,
-                                gint64      timestamp)
+gtk_css_node_validate_internal (GtkCssNode             *cssnode,
+                                GtkCountingBloomFilter *filter,
+                                gint64                  timestamp)
 {
   GtkCssNode *child;
+  gboolean bloomed = FALSE;
 
   if (!cssnode->invalid)
     return;
 
-  gtk_css_node_ensure_style (cssnode, timestamp);
+  gtk_css_node_ensure_style (cssnode, filter, timestamp);
 
   /* need to set to FALSE then to TRUE here to make it chain up */
   gtk_css_node_set_invalid (cssnode, FALSE);
@@ -1321,20 +1328,32 @@ gtk_css_node_validate_internal (GtkCssNode *cssnode,
        child;
        child = gtk_css_node_get_next_sibling (child))
     {
-      if (child->visible)
-        gtk_css_node_validate_internal (child, timestamp);
+      if (!child->visible)
+        continue;
+
+      if (!bloomed)
+        {
+          gtk_css_node_declaration_add_bloom_hashes (cssnode->decl, filter);
+          bloomed = TRUE;
+        }
+
+      gtk_css_node_validate_internal (child, filter, timestamp);
     }
+
+  if (bloomed)
+    gtk_css_node_declaration_remove_bloom_hashes (cssnode->decl, filter);
 }
 
 void
 gtk_css_node_validate (GtkCssNode *cssnode)
 {
+  GtkCountingBloomFilter filter = GTK_COUNTING_BLOOM_FILTER_INIT;
   gint64 timestamp;
   gint64 before = g_get_monotonic_time ();
 
   timestamp = gtk_css_node_get_timestamp (cssnode);
 
-  gtk_css_node_validate_internal (cssnode, timestamp);
+  gtk_css_node_validate_internal (cssnode, &filter, timestamp);
 
   if (cssnode->parent == NULL)
     {
diff --git a/gtk/gtkcssnodedeclaration.c b/gtk/gtkcssnodedeclaration.c
index 128037decf..266411435f 100644
--- a/gtk/gtkcssnodedeclaration.c
+++ b/gtk/gtkcssnodedeclaration.c
@@ -312,6 +312,40 @@ gtk_css_node_declaration_get_classes (const GtkCssNodeDeclaration *decl,
   return decl->classes;
 }
 
+void
+gtk_css_node_declaration_add_bloom_hashes (const GtkCssNodeDeclaration *decl,
+                                           GtkCountingBloomFilter      *filter)
+{
+  guint i;
+
+  if (decl->name)
+    gtk_counting_bloom_filter_add (filter, gtk_css_hash_name (decl->name));
+  if (decl->id)
+    gtk_counting_bloom_filter_add (filter, gtk_css_hash_id (decl->id));
+
+  for (i = 0; i < decl->n_classes; i++)
+    {
+      gtk_counting_bloom_filter_add (filter, gtk_css_hash_class (decl->classes[i]));
+    }
+}
+
+void
+gtk_css_node_declaration_remove_bloom_hashes (const GtkCssNodeDeclaration *decl,
+                                              GtkCountingBloomFilter      *filter)
+{
+  guint i;
+
+  if (decl->name)
+    gtk_counting_bloom_filter_remove (filter, gtk_css_hash_name (decl->name));
+  if (decl->id)
+    gtk_counting_bloom_filter_remove (filter, gtk_css_hash_id (decl->id));
+
+  for (i = 0; i < decl->n_classes; i++)
+    {
+      gtk_counting_bloom_filter_remove (filter, gtk_css_hash_class (decl->classes[i]));
+    }
+}
+
 guint
 gtk_css_node_declaration_hash (gconstpointer elem)
 {
diff --git a/gtk/gtkcssnodedeclarationprivate.h b/gtk/gtkcssnodedeclarationprivate.h
index d0dd6e43fa..663f713846 100644
--- a/gtk/gtkcssnodedeclarationprivate.h
+++ b/gtk/gtkcssnodedeclarationprivate.h
@@ -18,6 +18,7 @@
 #ifndef __GTK_CSS_NODE_DECLARATION_PRIVATE_H__
 #define __GTK_CSS_NODE_DECLARATION_PRIVATE_H__
 
+#include "gtkcountingbloomfilterprivate.h"
 #include "gtkcsstypesprivate.h"
 #include "gtkenums.h"
 
@@ -47,6 +48,11 @@ gboolean                gtk_css_node_declaration_has_class              (const G
 const GQuark *          gtk_css_node_declaration_get_classes            (const GtkCssNodeDeclaration   *decl,
                                                                          guint                         
*n_classes);
 
+void                    gtk_css_node_declaration_add_bloom_hashes       (const GtkCssNodeDeclaration   *decl,
+                                                                         GtkCountingBloomFilter        
*filter);
+void                    gtk_css_node_declaration_remove_bloom_hashes    (const GtkCssNodeDeclaration   *decl,
+                                                                         GtkCountingBloomFilter        
*filter);
+
 guint                   gtk_css_node_declaration_hash                   (gconstpointer                  
elem);
 gboolean                gtk_css_node_declaration_equal                  (gconstpointer                  
elem1,
                                                                          gconstpointer                  
elem2);
diff --git a/gtk/gtkcssnodeprivate.h b/gtk/gtkcssnodeprivate.h
index 0dab08ab72..ae07da00cb 100644
--- a/gtk/gtkcssnodeprivate.h
+++ b/gtk/gtkcssnodeprivate.h
@@ -18,6 +18,7 @@
 #ifndef __GTK_CSS_NODE_PRIVATE_H__
 #define __GTK_CSS_NODE_PRIVATE_H__
 
+#include "gtkcountingbloomfilterprivate.h"
 #include "gtkcssnodedeclarationprivate.h"
 #include "gtkcssnodestylecacheprivate.h"
 #include "gtkcssstylechangeprivate.h"
@@ -81,6 +82,7 @@ struct _GtkCssNodeClass
   /* get frame clock or NULL (only relevant for root node) */
   GdkFrameClock *       (* get_frame_clock)             (GtkCssNode            *cssnode);
   GtkCssStyle *         (* update_style)                (GtkCssNode            *cssnode,
+                                                         const GtkCountingBloomFilter *filter,
                                                          GtkCssChange           pending_changes,
                                                          gint64                 timestamp,
                                                          GtkCssStyle           *old_style);
diff --git a/gtk/gtkcssprovider.c b/gtk/gtkcssprovider.c
index 9b5761bb67..bf109506c4 100644
--- a/gtk/gtkcssprovider.c
+++ b/gtk/gtkcssprovider.c
@@ -446,10 +446,11 @@ gtk_css_style_provider_get_keyframes (GtkStyleProvider *provider,
 }
 
 static void
-gtk_css_style_provider_lookup (GtkStyleProvider    *provider,
-                               GtkCssNode          *node,
-                               GtkCssLookup        *lookup,
-                               GtkCssChange        *change)
+gtk_css_style_provider_lookup (GtkStyleProvider             *provider,
+                               const GtkCountingBloomFilter *filter,
+                               GtkCssNode                   *node,
+                               GtkCssLookup                 *lookup,
+                               GtkCssChange                 *change)
 {
   GtkCssProvider *css_provider = GTK_CSS_PROVIDER (provider);
   GtkCssProviderPrivate *priv = gtk_css_provider_get_instance_private (css_provider);
@@ -461,7 +462,7 @@ gtk_css_style_provider_lookup (GtkStyleProvider    *provider,
   if (_gtk_css_selector_tree_is_empty (priv->tree))
     return;
 
-  tree_rules = _gtk_css_selector_tree_match_all (priv->tree, node);
+  tree_rules = _gtk_css_selector_tree_match_all (priv->tree, filter, node);
   if (tree_rules)
     {
       verify_tree_match_results (css_provider, node, tree_rules);
diff --git a/gtk/gtkcssselector.c b/gtk/gtkcssselector.c
index 2268c025d5..bd1edb1240 100644
--- a/gtk/gtkcssselector.c
+++ b/gtk/gtkcssselector.c
@@ -168,24 +168,6 @@ g_ptr_array_insert_sorted (GPtrArray *array,
   g_ptr_array_insert (array, i, data);
 }
 
-static void
-gtk_css_selector_tree_found_match (const GtkCssSelectorTree  *tree,
-                                  GPtrArray                **array)
-{
-  int i;
-  gpointer *matches;
-
-  matches = gtk_css_selector_tree_get_matches (tree);
-  if (matches)
-    {
-      if (!*array)
-        *array = g_ptr_array_sized_new (16);
-
-      for (i = 0; matches[i] != NULL; i++)
-        g_ptr_array_insert_sorted (*array, matches[i]);
-    }
-}
-
 static inline gboolean
 gtk_css_selector_match (const GtkCssSelector *selector,
                         GtkCssNode           *node)
@@ -1864,38 +1846,115 @@ gtk_css_selectors_skip_initial_selector (GtkCssSelector *selector, const GtkCssS
   return (GtkCssSelector *)gtk_css_selector_previous (selector);
 }
 
+static gboolean
+gtk_css_selector_tree_match_bloom (const GtkCssSelectorTree     *tree,
+                                   const GtkCountingBloomFilter *filter,
+                                   gboolean                      skipping)
+{
+  const GtkCssSelectorTree *prev;
+
+  switch (tree->selector.class->category)
+    {
+      case GTK_CSS_SELECTOR_CATEGORY_SIMPLE:
+        break;
+      case GTK_CSS_SELECTOR_CATEGORY_SIMPLE_RADICAL:
+        if (skipping)
+          break;
+        if (!gtk_counting_bloom_filter_may_contain (filter,
+                                                    gtk_css_selector_hash_one (&tree->selector)))
+          return FALSE;
+        break;
+      case GTK_CSS_SELECTOR_CATEGORY_PARENT:
+        skipping = FALSE;
+        break;
+      case GTK_CSS_SELECTOR_CATEGORY_SIBLING:
+        skipping = TRUE;
+        break;
+      default:
+        g_assert_not_reached ();
+        return FALSE;
+    }
+
+  if (gtk_css_selector_tree_get_matches (tree))
+    return TRUE;
+
+  for (prev = gtk_css_selector_tree_get_previous (tree);
+       prev != NULL;
+       prev = gtk_css_selector_tree_get_sibling (prev))
+    {
+      if (gtk_css_selector_tree_match_bloom (prev, filter, skipping))
+        return TRUE;
+    }
+
+  return FALSE;
+}
+
+typedef struct
+{
+  const GtkCountingBloomFilter *filter;
+  GPtrArray *results;
+} TreeMatchData;
+
+static void
+gtk_css_selector_tree_found_match (const GtkCssSelectorTree *tree,
+                                  TreeMatchData            *tm)
+{
+  int i;
+  gpointer *matches;
+
+  matches = gtk_css_selector_tree_get_matches (tree);
+  if (matches)
+    {
+      if (tm->results == NULL)
+        tm->results = g_ptr_array_sized_new (16);
+
+      for (i = 0; matches[i] != NULL; i++)
+        g_ptr_array_insert_sorted (tm->results, matches[i]);
+    }
+}
+
 static gboolean
 gtk_css_selector_tree_match_foreach (const GtkCssSelector *selector,
                                      GtkCssNode           *node,
-                                     gpointer              res)
+                                     gpointer              data)
 {
+  TreeMatchData *tm = data;
   const GtkCssSelectorTree *tree = (const GtkCssSelectorTree *) selector;
   const GtkCssSelectorTree *prev;
 
   if (!gtk_css_selector_match (selector, node))
     return FALSE;
 
-  gtk_css_selector_tree_found_match (tree, res);
+  gtk_css_selector_tree_found_match (tree, tm);
+
+  if (tm->filter && !gtk_css_selector_is_simple (&tree->selector))
+    {
+      /* We can pass both TRUE or FALSE for skipping here, because the
+       * function will immediately update it. */
+      if (!gtk_css_selector_tree_match_bloom (tree, tm->filter, FALSE))
+          return FALSE;
+    }
 
   for (prev = gtk_css_selector_tree_get_previous (tree);
        prev != NULL;
        prev = gtk_css_selector_tree_get_sibling (prev))
-    gtk_css_selector_foreach (&prev->selector, node, gtk_css_selector_tree_match_foreach, res);
+    gtk_css_selector_foreach (&prev->selector, node, gtk_css_selector_tree_match_foreach, tm);
 
   return FALSE;
 }
 
 GPtrArray *
-_gtk_css_selector_tree_match_all (const GtkCssSelectorTree *tree,
-                                  GtkCssNode               *node)
+_gtk_css_selector_tree_match_all (const GtkCssSelectorTree     *tree,
+                                  const GtkCountingBloomFilter *filter,
+                                  GtkCssNode                   *node)
 {
-  GPtrArray *array = NULL;
+  TreeMatchData tm = { filter, NULL };
 
   for (; tree != NULL;
        tree = gtk_css_selector_tree_get_sibling (tree))
-    gtk_css_selector_foreach (&tree->selector, node, gtk_css_selector_tree_match_foreach, &array);
+    gtk_css_selector_foreach (&tree->selector, node, gtk_css_selector_tree_match_foreach, &tm);
 
-  return array;
+  return tm.results;
 }
 
 /* The code for collecting matches assumes that the name, id and classes
diff --git a/gtk/gtkcssselectorprivate.h b/gtk/gtkcssselectorprivate.h
index 64a05b63f7..a1e265d5d2 100644
--- a/gtk/gtkcssselectorprivate.h
+++ b/gtk/gtkcssselectorprivate.h
@@ -18,6 +18,7 @@
 #ifndef __GTK_CSS_SELECTOR_PRIVATE_H__
 #define __GTK_CSS_SELECTOR_PRIVATE_H__
 
+#include "gtk/gtkcountingbloomfilterprivate.h"
 #include "gtk/gtkcsstypesprivate.h"
 #include "gtk/gtkcssparserprivate.h"
 
@@ -42,6 +43,7 @@ int               _gtk_css_selector_compare         (const GtkCssSelector   *a,
 
 void         _gtk_css_selector_tree_free             (GtkCssSelectorTree       *tree);
 GPtrArray *  _gtk_css_selector_tree_match_all        (const GtkCssSelectorTree *tree,
+                                                      const GtkCountingBloomFilter *filter,
                                                      GtkCssNode               *node);
 GtkCssChange _gtk_css_selector_tree_get_change_all   (const GtkCssSelectorTree *tree,
                                                      GtkCssNode               *node);
diff --git a/gtk/gtkcssstaticstyle.c b/gtk/gtkcssstaticstyle.c
index bbae7098b4..6666128036 100644
--- a/gtk/gtkcssstaticstyle.c
+++ b/gtk/gtkcssstaticstyle.c
@@ -161,10 +161,12 @@ gtk_css_static_style_get_default (void)
    */
   if (default_style == NULL)
     {
+      GtkCountingBloomFilter filter = GTK_COUNTING_BLOOM_FILTER_INIT;
       GtkSettings *settings;
 
       settings = gtk_settings_get_default ();
       default_style = gtk_css_static_style_new_compute (GTK_STYLE_PROVIDER (settings),
+                                                        &filter,
                                                         NULL,
                                                         0);
       g_object_set_data_full (G_OBJECT (settings), I_("gtk-default-style"),
@@ -175,9 +177,10 @@ gtk_css_static_style_get_default (void)
 }
 
 GtkCssStyle *
-gtk_css_static_style_new_compute (GtkStyleProvider    *provider,
-                                  GtkCssNode          *node,
-                                  GtkCssChange         change)
+gtk_css_static_style_new_compute (GtkStyleProvider             *provider,
+                                  const GtkCountingBloomFilter *filter,
+                                  GtkCssNode                   *node,
+                                  GtkCssChange                  change)
 {
   GtkCssStaticStyle *result;
   GtkCssLookup lookup;
@@ -187,6 +190,7 @@ gtk_css_static_style_new_compute (GtkStyleProvider    *provider,
 
   if (node)
     gtk_style_provider_lookup (provider,
+                               filter,
                                node,
                                &lookup,
                                change == 0 ? &change : NULL);
diff --git a/gtk/gtkcssstaticstyleprivate.h b/gtk/gtkcssstaticstyleprivate.h
index 1073f7bb0a..8c1acf11b2 100644
--- a/gtk/gtkcssstaticstyleprivate.h
+++ b/gtk/gtkcssstaticstyleprivate.h
@@ -22,6 +22,8 @@
 
 #include "gtk/gtkcssstyleprivate.h"
 
+#include "gtk/gtkcountingbloomfilterprivate.h"
+
 G_BEGIN_DECLS
 
 #define GTK_TYPE_CSS_STATIC_STYLE           (gtk_css_static_style_get_type ())
@@ -51,18 +53,19 @@ struct _GtkCssStaticStyleClass
 GType                   gtk_css_static_style_get_type           (void) G_GNUC_CONST;
 
 GtkCssStyle *           gtk_css_static_style_get_default        (void);
-GtkCssStyle *           gtk_css_static_style_new_compute        (GtkStyleProvider       *provider,
-                                                                 GtkCssNode             *node,
-                                                                 GtkCssChange            change);
-
-void                    gtk_css_static_style_compute_value      (GtkCssStaticStyle      *style,
-                                                                 GtkStyleProvider       *provider,
-                                                                 GtkCssStyle            *parent_style,
-                                                                 guint                   id,
-                                                                 GtkCssValue            *specified,
-                                                                 GtkCssSection          *section);
-
-GtkCssChange            gtk_css_static_style_get_change         (GtkCssStaticStyle      *style);
+GtkCssStyle *           gtk_css_static_style_new_compute        (GtkStyleProvider               *provider,
+                                                                 const GtkCountingBloomFilter   *filter,
+                                                                 GtkCssNode                     *node,
+                                                                 GtkCssChange                    change);
+
+void                    gtk_css_static_style_compute_value      (GtkCssStaticStyle              *style,
+                                                                 GtkStyleProvider               *provider,
+                                                                 GtkCssStyle                    
*parent_style,
+                                                                 guint                           id,
+                                                                 GtkCssValue                    *specified,
+                                                                 GtkCssSection                  *section);
+
+GtkCssChange            gtk_css_static_style_get_change         (GtkCssStaticStyle              *style);
 
 G_END_DECLS
 
diff --git a/gtk/gtkcsstransientnode.c b/gtk/gtkcsstransientnode.c
index 218358005d..5c8373c862 100644
--- a/gtk/gtkcsstransientnode.c
+++ b/gtk/gtkcsstransientnode.c
@@ -23,13 +23,14 @@
 G_DEFINE_TYPE (GtkCssTransientNode, gtk_css_transient_node, GTK_TYPE_CSS_NODE)
 
 static GtkCssStyle *
-gtk_css_transient_node_update_style (GtkCssNode   *cssnode,
-                                     GtkCssChange  change,
-                                     gint64        timestamp,
-                                     GtkCssStyle  *style)
+gtk_css_transient_node_update_style (GtkCssNode                   *cssnode,
+                                     const GtkCountingBloomFilter *filter,
+                                     GtkCssChange                  change,
+                                     gint64                        timestamp,
+                                     GtkCssStyle                  *style)
 {
   /* This should get rid of animations */
-  return GTK_CSS_NODE_CLASS (gtk_css_transient_node_parent_class)->update_style (cssnode, change, 0, style);
+  return GTK_CSS_NODE_CLASS (gtk_css_transient_node_parent_class)->update_style (cssnode, filter, change, 0, 
style);
 }
 
 static void
diff --git a/gtk/gtkstylecascade.c b/gtk/gtkstylecascade.c
index 1bc60e12be..1871b7073e 100644
--- a/gtk/gtkstylecascade.c
+++ b/gtk/gtkstylecascade.c
@@ -179,10 +179,11 @@ gtk_style_cascade_get_keyframes (GtkStyleProvider *provider,
 }
 
 static void
-gtk_style_cascade_lookup (GtkStyleProvider    *provider,
-                          GtkCssNode          *node,
-                          GtkCssLookup        *lookup,
-                          GtkCssChange        *change)
+gtk_style_cascade_lookup (GtkStyleProvider             *provider,
+                          const GtkCountingBloomFilter *filter,
+                          GtkCssNode                   *node,
+                          GtkCssLookup                 *lookup,
+                          GtkCssChange                 *change)
 {
   GtkStyleCascade *cascade = GTK_STYLE_CASCADE (provider);
   GtkStyleCascadeIter iter;
@@ -193,7 +194,7 @@ gtk_style_cascade_lookup (GtkStyleProvider    *provider,
        item;
        item = gtk_style_cascade_iter_next (cascade, &iter))
     {
-      gtk_style_provider_lookup (item, node, lookup,
+      gtk_style_provider_lookup (item, filter, node, lookup,
                                  change ? &iter_change : NULL);
       if (change)
         *change |= iter_change;
diff --git a/gtk/gtkstyleprovider.c b/gtk/gtkstyleprovider.c
index 6dd380b95c..4bcd241054 100644
--- a/gtk/gtkstyleprovider.c
+++ b/gtk/gtkstyleprovider.c
@@ -92,10 +92,11 @@ gtk_style_provider_get_keyframes (GtkStyleProvider *provider,
 }
 
 void
-gtk_style_provider_lookup (GtkStyleProvider *provider,
-                           GtkCssNode       *node,
-                           GtkCssLookup     *lookup,
-                           GtkCssChange     *out_change)
+gtk_style_provider_lookup (GtkStyleProvider             *provider,
+                           const GtkCountingBloomFilter *filter,
+                           GtkCssNode                   *node,
+                           GtkCssLookup                 *lookup,
+                           GtkCssChange                 *out_change)
 {
   GtkStyleProviderInterface *iface;
 
@@ -111,7 +112,7 @@ gtk_style_provider_lookup (GtkStyleProvider *provider,
   if (!iface->lookup)
     return;
 
-  iface->lookup (provider, node, lookup, out_change);
+  iface->lookup (provider, filter, node, lookup, out_change);
 }
 
 void
diff --git a/gtk/gtkstyleproviderprivate.h b/gtk/gtkstyleproviderprivate.h
index 2cdfbed16b..5ee16e3d00 100644
--- a/gtk/gtkstyleproviderprivate.h
+++ b/gtk/gtkstyleproviderprivate.h
@@ -19,6 +19,7 @@
 #define __GTK_STYLE_PROVIDER_PRIVATE_H__
 
 #include <glib-object.h>
+#include "gtk/gtkcountingbloomfilterprivate.h"
 #include "gtk/gtkcsskeyframesprivate.h"
 #include "gtk/gtkcsslookupprivate.h"
 #include "gtk/gtkcssnodeprivate.h"
@@ -42,6 +43,7 @@ struct _GtkStyleProviderInterface
                                                  const char              *name);
   int                   (* get_scale)           (GtkStyleProvider        *provider);
   void                  (* lookup)              (GtkStyleProvider        *provider,
+                                                 const GtkCountingBloomFilter *filter,
                                                  GtkCssNode              *node,
                                                  GtkCssLookup            *lookup,
                                                  GtkCssChange            *out_change);
@@ -59,6 +61,7 @@ GtkCssKeyframes *       gtk_style_provider_get_keyframes         (GtkStyleProvid
                                                                   const char              *name);
 int                     gtk_style_provider_get_scale             (GtkStyleProvider        *provider);
 void                    gtk_style_provider_lookup                (GtkStyleProvider        *provider,
+                                                                  const GtkCountingBloomFilter *filter,
                                                                   GtkCssNode              *node,
                                                                   GtkCssLookup            *lookup,
                                                                   GtkCssChange            *out_change);


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]