[gtk/wip/otte/css: 3147/3150] selector: Hash differently

[Benjamin Otte <otte src gnome org>]

commit b23b43866c6cd1e45ccdeb1e7bce59a8a501dd6e
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 | 26 ++++++++++++++++++++++++++
 2 files changed, 31 insertions(+), 5 deletions(-)
---
diff --git a/gtk/gtkcssselector.c b/gtk/gtkcssselector.c
index 88cde68d66..6a51c85b4b 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 2cd1141008..0cfac59519 100644
--- a/gtk/gtkcsstypesprivate.h
+++ b/gtk/gtkcsstypesprivate.h
@@ -453,6 +453,32 @@ char *                  gtk_css_change_to_string                 (GtkCssChange
 void                    gtk_css_change_print                     (GtkCssChange       change,
                                                                   GString           *string);
 
+/* 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
 
 #endif /* __GTK_CSS_TYPES_PRIVATE_H__ */