[gtk/wip/otte/css: 10/16] selector: Hash differently

[Benjamin Otte <otte src gnome org>]

commit 8260df0e53b0142cff896ce6a26291d979803eb9
Author: Benjamin Otte <otte redhat com>
Date:   Fri Jan 24 17:56:53 2020 +0100

    selector: Hash differently
    
    This will be relevant for a bloom filter. And bloom filters want 12bit
    hashes, so we try to produce hash values < 4096.

 gtk/gtkcssselector.c     | 10 +++++-----
 gtk/gtkcsstypesprivate.h | 25 +++++++++++++++++++++++++
 2 files changed, 30 insertions(+), 5 deletions(-)
---
diff --git a/gtk/gtkcssselector.c b/gtk/gtkcssselector.c
index 96993966e3..2268c025d5 100644
--- a/gtk/gtkcssselector.c
+++ b/gtk/gtkcssselector.c
@@ -138,7 +138,7 @@ gtk_css_selector_equal (const GtkCssSelector *a,
 static guint
 gtk_css_selector_hash_one (const GtkCssSelector *selector)
 {
-  return GPOINTER_TO_UINT (selector->class) ^ selector->class->hash_one (selector);
+  return selector->class->hash_one (selector);
 }
 
 static inline gpointer *
@@ -277,7 +277,7 @@ gtk_css_selector_default_match_one (const GtkCssSelector *selector,
 static guint
 gtk_css_selector_default_hash_one (const GtkCssSelector *selector)
 {
-  return 0;
+  return GPOINTER_TO_UINT (selector->class);
 }
 
 static int
@@ -610,7 +610,7 @@ match_name (const GtkCssSelector *selector,
 static guint
 hash_name (const GtkCssSelector *a)
 {
-  return a->name.name;
+  return gtk_css_hash_name (a->name.name);
 }
 
 static int
@@ -642,7 +642,7 @@ match_class (const GtkCssSelector *selector,
 static guint
 hash_class (const GtkCssSelector *a)
 {
-  return a->style_class.style_class;
+  return gtk_css_hash_class (a->style_class.style_class);
 }
 
 static int
@@ -679,7 +679,7 @@ match_id (const GtkCssSelector *selector,
 static guint
 hash_id (const GtkCssSelector *a)
 {
-  return a->id.name;
+  return gtk_css_hash_id (a->id.name);
 }
 
 static int
diff --git a/gtk/gtkcsstypesprivate.h b/gtk/gtkcsstypesprivate.h
index af552e13fd..647379b343 100644
--- a/gtk/gtkcsstypesprivate.h
+++ b/gtk/gtkcsstypesprivate.h
@@ -459,6 +459,31 @@ void                    gtk_css_change_print                     (GtkCssChange
 
 const char *            gtk_css_pseudoclass_name                 (GtkStateFlags      flags);
 
+/* These hash functions are selected so they achieve 2 things:
+ * 1. collision free among each other
+ *    Hashing the CSS selectors "button", ".button" and "#button" should give different results.
+ *    So we multiply the hash values with distinct prime numbers.
+ * 2. generate small numbers
+ *    It's why the code uses quarks instead of interned strings. Interned strings are random
+ *    pointers, quarks are numbers increasing from 0.
+ * Both of these goals should achieve a bloom filter for selector matching that is as free
+ * of collisions as possible.
+ */
+static inline guint
+gtk_css_hash_class (GQuark klass)
+{
+  return klass * 5;
+}
+static inline guint
+gtk_css_hash_name (GQuark name)
+{
+  return name * 7;
+}
+static inline guint
+gtk_css_hash_id (GQuark id)
+{
+  return id * 11;
+}
 
 G_END_DECLS