From 675214574cfc5e49cb25988c126836b2487e56f9 Mon Sep 17 00:00:00 2001 From: Matthias Clasen Date: Sun, 19 Jan 2020 11:34:53 -0500 Subject: css: Break the selector tree into many Since we can only match one name, doing a hash by matcher name lets us quickly discard most initial selectors, and having much smaller trees. We can apply the same idea for style classes, as well, by looking up a tree for each class. Comparing the number of gtk_css_selector_match() calls while moving the pointer outside the window, I see: Before: 65773 selector matches (12863 positive) After: 32704 selector matches (12278 positive) So this cuts the numer of selectors we need to check roughly in half, at the cost of a handful of hash table lookups. --- gtk/gtkcssprovider.c | 2 +- gtk/gtkcssselector.c | 230 ++++++++++++++++++++++++++++++++++++++++---- gtk/gtkcssselectorprivate.h | 11 ++- 3 files changed, 216 insertions(+), 27 deletions(-) diff --git a/gtk/gtkcssprovider.c b/gtk/gtkcssprovider.c index 5201e00c0a..9b8e37515f 100644 --- a/gtk/gtkcssprovider.c +++ b/gtk/gtkcssprovider.c @@ -118,7 +118,7 @@ struct _GtkCssProviderPrivate GHashTable *keyframes; GArray *rulesets; - GtkCssSelectorTree *tree; + GtkCssSelectorTrees *tree; GResource *resource; gchar *path; }; diff --git a/gtk/gtkcssselector.c b/gtk/gtkcssselector.c index aabffb3e3e..0f8792f5ab 100644 --- a/gtk/gtkcssselector.c +++ b/gtk/gtkcssselector.c @@ -111,6 +111,12 @@ struct _GtkCssSelectorTree gint32 matches_offset; /* pointers that we return as matches if selector matches */ }; +struct _GtkCssSelectorTrees { + GHashTable *by_name; + GHashTable *by_class; + GtkCssSelectorTree *remaining; +}; + static gboolean gtk_css_selector_equal (const GtkCssSelector *a, const GtkCssSelector *b) @@ -1844,15 +1850,43 @@ gtk_css_selector_tree_match_foreach (const GtkCssSelector *selector, return FALSE; } +static void +gtk_css_selector_tree_match_one (const GtkCssSelectorTree *tree, + const GtkCssMatcher *matcher, + gpointer res) +{ + for (; tree != NULL; + tree = gtk_css_selector_tree_get_sibling (tree)) + gtk_css_selector_foreach (&tree->selector, matcher, gtk_css_selector_tree_match_foreach, res); +} + GPtrArray * -_gtk_css_selector_tree_match_all (const GtkCssSelectorTree *tree, +_gtk_css_selector_tree_match_all (const GtkCssSelectorTrees *trees, const GtkCssMatcher *matcher) { GPtrArray *array = NULL; + const char *name; + GQuark *classes; + guint n_classes; + gboolean allocated; + const GtkCssSelectorTree *tree; + int i; - for (; tree != NULL; - tree = gtk_css_selector_tree_get_sibling (tree)) - gtk_css_selector_foreach (&tree->selector, matcher, gtk_css_selector_tree_match_foreach, &array); + name = _gtk_css_matcher_get_name (matcher); + + tree = (const GtkCssSelectorTree *)g_hash_table_lookup (trees->by_name, (gpointer)name); + gtk_css_selector_tree_match_one (tree, matcher, &array); + + classes = _gtk_css_matcher_get_classes (matcher, &n_classes, &allocated); + for (i = 0; i < n_classes; i++) + { + tree = (const GtkCssSelectorTree *)g_hash_table_lookup (trees->by_class, GUINT_TO_POINTER (classes[i])); + gtk_css_selector_tree_match_one (tree, matcher, &array); + } + if (allocated) + g_free (classes); + + gtk_css_selector_tree_match_one (trees->remaining, matcher, &array); return array; } @@ -1924,14 +1958,19 @@ gtk_css_selector_tree_get_change (const GtkCssSelectorTree *tree, } gboolean -_gtk_css_selector_tree_is_empty (const GtkCssSelectorTree *tree) +_gtk_css_selector_tree_is_empty (const GtkCssSelectorTrees *tree) { - return tree == NULL; + if (!tree) + return TRUE; + + return g_hash_table_size (tree->by_name) == 0 && + g_hash_table_size (tree->by_class) == 0 && + tree->remaining == NULL; } -GtkCssChange -_gtk_css_selector_tree_get_change_all (const GtkCssSelectorTree *tree, - const GtkCssMatcher *matcher) +static GtkCssChange +gtk_css_selector_tree_get_change_for_one (const GtkCssSelectorTree *tree, + const GtkCssMatcher *matcher) { GtkCssChange change; @@ -1946,6 +1985,37 @@ _gtk_css_selector_tree_get_change_all (const GtkCssSelectorTree *tree, return change & ~GTK_CSS_CHANGE_RESERVED_BIT; } +GtkCssChange +_gtk_css_selector_tree_get_change_all (const GtkCssSelectorTrees *trees, + const GtkCssMatcher *matcher) +{ + GtkCssChange change = 0; + const char *name; + GQuark *classes; + guint n_classes; + gboolean allocated; + const GtkCssSelectorTree *tree; + int i; + + name = _gtk_css_matcher_get_name (matcher); + + tree = (const GtkCssSelectorTree *)g_hash_table_lookup (trees->by_name, (gpointer)name); + change |= gtk_css_selector_tree_get_change_for_one (tree, matcher); + + classes = _gtk_css_matcher_get_classes (matcher, &n_classes, &allocated); + for (i = 0; i < n_classes; i++) + { + tree = (const GtkCssSelectorTree *)g_hash_table_lookup (trees->by_class, GUINT_TO_POINTER (classes[i])); + change |= gtk_css_selector_tree_get_change_for_one (tree, matcher); + } + if (allocated) + g_free (classes); + + change |= gtk_css_selector_tree_get_change_for_one (trees->remaining, matcher); + + return change; +} + #ifdef PRINT_TREE static void _gtk_css_selector_tree_print (const GtkCssSelectorTree *tree, GString *str, char *prefix) @@ -2050,12 +2120,24 @@ _gtk_css_selector_tree_match_print (const GtkCssSelectorTree *tree, } void -_gtk_css_selector_tree_free (GtkCssSelectorTree *tree) +_gtk_css_selector_tree_free (GtkCssSelectorTrees *trees) { - if (tree == NULL) + GHashTableIter iter; + gpointer key; + gpointer tree; + + if (trees == NULL) return; - g_free (tree); + g_hash_table_iter_init (&iter, trees->by_name); + while (g_hash_table_iter_next (&iter, &key, (gpointer *)&tree)) + g_free (tree); + + g_hash_table_unref (trees->by_name); + + g_free (trees->remaining); + + g_free (trees); } @@ -2063,6 +2145,8 @@ typedef struct { gpointer match; GtkCssSelector *current_selector; GtkCssSelectorTree **selector_match; + const char *name; + GQuark class; } GtkCssSelectorRuleSetInfo; static GtkCssSelectorTree * @@ -2186,22 +2270,73 @@ subdivide_infos (GByteArray *array, GList *infos, gint32 parent_offset) } struct _GtkCssSelectorTreeBuilder { - GList *infos; + GHashTable *by_name; + GHashTable *by_class; + GList *remaining; }; GtkCssSelectorTreeBuilder * _gtk_css_selector_tree_builder_new (void) { - return g_new0 (GtkCssSelectorTreeBuilder, 1); + GtkCssSelectorTreeBuilder *builder; + + builder = g_new0 (GtkCssSelectorTreeBuilder, 1); + builder->by_name = g_hash_table_new (NULL, NULL); + builder->by_class = g_hash_table_new (NULL, NULL); + + return builder; } void -_gtk_css_selector_tree_builder_free (GtkCssSelectorTreeBuilder *builder) +_gtk_css_selector_tree_builder_free (GtkCssSelectorTreeBuilder *builder) { - g_list_free_full (builder->infos, g_free); + GHashTableIter iter; + gpointer key; + GList *infos; + + g_hash_table_iter_init (&iter, builder->by_name); + while (g_hash_table_iter_next (&iter, &key, (gpointer *)&infos)) + g_list_free_full (infos, g_free); + g_hash_table_unref (builder->by_name); + + g_hash_table_iter_init (&iter, builder->by_class); + while (g_hash_table_iter_next (&iter, &key, (gpointer *)&infos)) + g_list_free_full (infos, g_free); + g_hash_table_unref (builder->by_class); + + g_list_free_full (builder->remaining, g_free); + g_free (builder); } +static const char * +find_name (const GtkCssSelector *selector) +{ + for (; + selector && selector->class->is_simple; + selector = gtk_css_selector_previous (selector)) + { + if (selector->class == >K_CSS_SELECTOR_NAME) + return selector->name.name; + } + + return NULL; +} + +static GQuark +find_class (const GtkCssSelector *selector) +{ + for (; + selector && selector->class->is_simple; + selector = gtk_css_selector_previous (selector)) + { + if (selector->class == >K_CSS_SELECTOR_CLASS) + return selector->style_class.style_class; + } + + return 0; +} + void _gtk_css_selector_tree_builder_add (GtkCssSelectorTreeBuilder *builder, GtkCssSelector *selectors, @@ -2213,7 +2348,27 @@ _gtk_css_selector_tree_builder_add (GtkCssSelectorTreeBuilder *builder, info->match = match; info->current_selector = selectors; info->selector_match = selector_match; - builder->infos = g_list_prepend (builder->infos, info); + info->name = find_name (selectors); + + if (info->name) + { + GList *infos = g_hash_table_lookup (builder->by_name, (gpointer)info->name); + infos = g_list_prepend (infos, info); + g_hash_table_replace (builder->by_name, (gpointer)info->name, infos); + return; + } + + info->class = find_class (selectors); + + if (info->class) + { + GList *infos = g_hash_table_lookup (builder->by_class, GUINT_TO_POINTER (info->class)); + infos = g_list_prepend (infos, info); + g_hash_table_replace (builder->by_class, GUINT_TO_POINTER (info->class), infos); + return; + } + + builder->remaining = g_list_prepend (builder->remaining, info); } /* Convert all offsets to node-relative */ @@ -2240,8 +2395,8 @@ fixup_offsets (GtkCssSelectorTree *tree, guint8 *data) } } -GtkCssSelectorTree * -_gtk_css_selector_tree_builder_build (GtkCssSelectorTreeBuilder *builder) +static GtkCssSelectorTree * +_gtk_css_selector_tree_builder_build_one (GList *infos) { GtkCssSelectorTree *tree; GByteArray *array; @@ -2251,7 +2406,7 @@ _gtk_css_selector_tree_builder_build (GtkCssSelectorTreeBuilder *builder) GtkCssSelectorRuleSetInfo *info; array = g_byte_array_new (); - subdivide_infos (array, builder->infos, GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET); + subdivide_infos (array, infos, GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET); len = array->len; data = g_byte_array_free (array, FALSE); @@ -2264,7 +2419,7 @@ _gtk_css_selector_tree_builder_build (GtkCssSelectorTreeBuilder *builder) fixup_offsets (tree, data); /* Convert offsets to final pointers */ - for (l = builder->infos; l != NULL; l = l->next) + for (l = infos; l != NULL; l = l->next) { info = l->data; if (info->selector_match) @@ -2282,3 +2437,36 @@ _gtk_css_selector_tree_builder_build (GtkCssSelectorTreeBuilder *builder) return tree; } + +GtkCssSelectorTrees * +_gtk_css_selector_tree_builder_build (GtkCssSelectorTreeBuilder *builder) +{ + GtkCssSelectorTrees *trees; + GHashTableIter iter; + const char *name; + GList *infos; + gpointer key; + + trees = g_new0 (GtkCssSelectorTrees, 1); + trees->by_name = g_hash_table_new (NULL, NULL); + trees->by_class = g_hash_table_new (NULL, NULL); + + g_hash_table_iter_init (&iter, builder->by_name); + while (g_hash_table_iter_next (&iter, (gpointer *)&name, (gpointer *)&infos)) + { + GtkCssSelectorTree *tree = _gtk_css_selector_tree_builder_build_one (infos); + g_hash_table_insert (trees->by_name, (gpointer)name, tree); + } + + g_hash_table_iter_init (&iter, builder->by_class); + while (g_hash_table_iter_next (&iter, &key, (gpointer *)&infos)) + { + GtkCssSelectorTree *tree = _gtk_css_selector_tree_builder_build_one (infos); + g_hash_table_insert (trees->by_class, key, tree); + } + + if (builder->remaining) + trees->remaining = _gtk_css_selector_tree_builder_build_one (builder->remaining); + + return trees; +} diff --git a/gtk/gtkcssselectorprivate.h b/gtk/gtkcssselectorprivate.h index 6f35917c6e..579d27c013 100644 --- a/gtk/gtkcssselectorprivate.h +++ b/gtk/gtkcssselectorprivate.h @@ -25,6 +25,7 @@ G_BEGIN_DECLS typedef union _GtkCssSelector GtkCssSelector; typedef struct _GtkCssSelectorTree GtkCssSelectorTree; +typedef struct _GtkCssSelectorTrees GtkCssSelectorTrees; typedef struct _GtkCssSelectorTreeBuilder GtkCssSelectorTreeBuilder; GtkCssSelector * _gtk_css_selector_parse (GtkCssParser *parser); @@ -40,14 +41,14 @@ GtkCssChange _gtk_css_selector_get_change (const GtkCssSelector *sel int _gtk_css_selector_compare (const GtkCssSelector *a, const GtkCssSelector *b); -void _gtk_css_selector_tree_free (GtkCssSelectorTree *tree); -GPtrArray * _gtk_css_selector_tree_match_all (const GtkCssSelectorTree *tree, +void _gtk_css_selector_tree_free (GtkCssSelectorTrees *tree); +GPtrArray * _gtk_css_selector_tree_match_all (const GtkCssSelectorTrees *tree, const GtkCssMatcher *matcher); -GtkCssChange _gtk_css_selector_tree_get_change_all (const GtkCssSelectorTree *tree, +GtkCssChange _gtk_css_selector_tree_get_change_all (const GtkCssSelectorTrees *tree, const GtkCssMatcher *matcher); void _gtk_css_selector_tree_match_print (const GtkCssSelectorTree *tree, GString *str); -gboolean _gtk_css_selector_tree_is_empty (const GtkCssSelectorTree *tree) G_GNUC_CONST; +gboolean _gtk_css_selector_tree_is_empty (const GtkCssSelectorTrees *tree) G_GNUC_CONST; @@ -56,7 +57,7 @@ void _gtk_css_selector_tree_builder_add (GtkCssSelectorT GtkCssSelector *selectors, GtkCssSelectorTree **selector_match, gpointer match); -GtkCssSelectorTree * _gtk_css_selector_tree_builder_build (GtkCssSelectorTreeBuilder *builder); +GtkCssSelectorTrees * _gtk_css_selector_tree_builder_build (GtkCssSelectorTreeBuilder *builder); void _gtk_css_selector_tree_builder_free (GtkCssSelectorTreeBuilder *builder); const char *gtk_css_pseudoclass_name (GtkStateFlags flags); -- cgit v1.2.1