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.

1 files changed, 34 insertions, 0 deletions

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)
 {