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/gtkcssnode.c

@@ -27,7 +27,6 @@
 #include "gtksettingsprivate.h"
 #include "gtktypebuiltins.h"
 #include "gtkprivate.h"
-#include "gdkprofilerprivate.h"
 
 /*
  * CSS nodes are the backbone of the GtkStyleContext implementation and
@@ -123,13 +122,6 @@ gtk_css_node_get_style_provider_or_null (GtkCssNode *cssnode)
   return GTK_CSS_NODE_GET_CLASS (cssnode)->get_style_provider (cssnode);
 }
 
-#ifdef G_ENABLE_DEBUG
-static int invalidated_nodes;
-static int created_styles;
-static guint invalidated_nodes_counter;
-static guint created_styles_counter;
-#endif
-
 static void
 gtk_css_node_set_invalid (GtkCssNode *node,
                           gboolean    invalid)
@@ -139,11 +131,6 @@ gtk_css_node_set_invalid (GtkCssNode *node,
 
   node->invalid = invalid;
 
-#ifdef G_ENABLE_DEBUG
-  if (invalid)
-    invalidated_nodes++;
-#endif
-
   if (node->visible)
     {
       if (node->parent)
@@ -382,10 +369,6 @@ gtk_css_node_create_style (GtkCssNode   *cssnode,
   if (style)
     return g_object_ref (style);
 
-#ifdef G_ENABLE_DEBUG
-  created_styles++;
-#endif
-
   parent = cssnode->parent ? cssnode->parent->style : NULL;
 
   if (change & GTK_CSS_CHANGE_NEEDS_RECOMPUTE)
@@ -682,14 +665,6 @@ gtk_css_node_class_init (GtkCssNodeClass *klass)
                         | G_PARAM_EXPLICIT_NOTIFY | G_PARAM_STATIC_STRINGS);
 
   g_object_class_install_properties (object_class, NUM_PROPERTIES, cssnode_properties);
-
-#ifdef G_ENABLE_DEBUG
-  if (invalidated_nodes_counter == 0)
-    {
-      invalidated_nodes_counter = gdk_profiler_define_int_counter ("invalidated-nodes", "CSS Node Invalidations");
-      created_styles_counter = gdk_profiler_define_int_counter ("created-styles", "CSS Style Creations");
-    }
-#endif
 }
 
 static void
@@ -1404,28 +1379,10 @@ void
 gtk_css_node_validate (GtkCssNode *cssnode)
 {
   gint64 timestamp;
-#ifdef G_ENABLE_DEBUG
-  gint64 before = g_get_monotonic_time ();
-#endif
 
   timestamp = gtk_css_node_get_timestamp (cssnode);
 
   gtk_css_node_validate_internal (cssnode, timestamp);
-
-#ifdef G_ENABLE_DEBUG
-  if (cssnode->parent == NULL)
-    {
-      if (gdk_profiler_is_running ())
-        {
-          gint64 after = g_get_monotonic_time ();
-          gdk_profiler_add_mark (before * 1000, (after - before) * 1000, "style", "");
-          gdk_profiler_set_int_counter (invalidated_nodes_counter, after * 1000, invalidated_nodes);
-          gdk_profiler_set_int_counter (created_styles_counter, after * 1000, created_styles);
-          invalidated_nodes = 0;
-          created_styles = 0;
-        }
-    }
-#endif
 }
 
 gboolean

gtk/gtkcssprovider.c

@@ -118,7 +118,7 @@ struct _GtkCssProviderPrivate
   GHashTable *keyframes;
 
   GArray *rulesets;
-  GtkCssSelectorTree *tree;
+  GtkCssSelectorTrees *tree;
   GResource *resource;
   gchar *path;
 };

gtk/gtkcssselector.c

@@ -101,20 +101,6 @@ union _GtkCssSelector
   }                              position;
 };
 
-typedef struct {
-  const char *name;
-  gint32 offset;
-} TreeNameMatch;
-
-typedef struct {
-  GQuark class;
-  gint32 offset;
-} TreeClassMatch;
-
-typedef struct {
-  gint32 offset;
-} TreeOtherMatch;
-
 #define GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET G_MAXINT32
 struct _GtkCssSelectorTree
 {
@@ -123,12 +109,12 @@ struct _GtkCssSelectorTree
   gint32 previous_offset;
   gint32 sibling_offset;
   gint32 matches_offset; /* pointers that we return as matches if selector matches */
-  gint32 name_offset;
-  gint32 class_offset;
-  gint32 other_offset;
-  guint32 n_names;
-  guint32 n_classes;
-  guint32 n_other;
+};
+
+struct _GtkCssSelectorTrees {
+  GHashTable *by_name;
+  GHashTable *by_class;
+  GtkCssSelectorTree *remaining;
 };
 
 static gboolean
@@ -155,33 +141,6 @@ gtk_css_selector_tree_get_matches (const GtkCssSelectorTree *tree)
   return (gpointer *) ((guint8 *)tree + tree->matches_offset);
 }
 
-static inline TreeNameMatch *
-gtk_css_selector_tree_get_names (const GtkCssSelectorTree *tree)
-{
-  if (tree->name_offset == GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
-    return NULL;
-
-  return (TreeNameMatch *) ((guint8 *)tree + tree->name_offset);
-}
-
-static inline TreeClassMatch *
-gtk_css_selector_tree_get_classes (const GtkCssSelectorTree *tree)
-{
-  if (tree->class_offset == GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
-    return NULL;
-
-  return (TreeClassMatch *) ((guint8 *)tree + tree->class_offset);
-}
-
-static inline TreeOtherMatch *
-gtk_css_selector_tree_get_others (const GtkCssSelectorTree *tree)
-{
-  if (tree->other_offset == GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
-    return NULL;
-
-  return (TreeOtherMatch *) ((guint8 *)tree + tree->other_offset);
-}
-
 static void
 g_ptr_array_insert_sorted (GPtrArray *array,
                            gpointer   data)
@@ -1870,138 +1829,64 @@ gtk_css_selectors_skip_initial_selector (GtkCssSelector *selector, const GtkCssS
   return (GtkCssSelector *)gtk_css_selector_previous (selector);
 }
 
-typedef struct {
-  TreeNameMatch *names;
-  int n_names;
-  TreeClassMatch *classes;
-  int n_classes;
-  TreeOtherMatch *other;
-  int n_other;
-} TreeMatchData;
-
-static int
-name_sort_func (gconstpointer a, gconstpointer b)
-{
-  const TreeNameMatch *na = a;
-  const TreeNameMatch *nb = b;
-
-  if (na->name < nb->name)
-    return -1;
-  else if (na->name > nb->name)
-    return 1;
-  else
-    return 0;
-}
-
-static int
-class_sort_func (gconstpointer a, gconstpointer b)
-{
-  const TreeClassMatch *ca = a;
-  const TreeClassMatch *cb = b;
-
-  if (ca->class < cb->class)
-    return -1;
-  else if (ca->class > cb->class)
-    return 1;
-  else
-    return 0;
-}
-
-static gboolean
-gtk_css_selector_tree_match_foreach_no_check (const GtkCssSelector *selector,
-                                              const GtkCssMatcher  *matcher,
-                                              gpointer              res);
-
 static gboolean
 gtk_css_selector_tree_match_foreach (const GtkCssSelector *selector,
                                      const GtkCssMatcher  *matcher,
                                      gpointer              res)
 {
+  const GtkCssSelectorTree *tree = (const GtkCssSelectorTree *) selector;
+  const GtkCssSelectorTree *prev;
+
   if (!gtk_css_selector_match (selector, matcher))
     return FALSE;
 
-  return gtk_css_selector_tree_match_foreach_no_check (selector, matcher, res);
-}
-
-static gboolean
-gtk_css_selector_tree_match_foreach_no_check (const GtkCssSelector *selector,
-                                              const GtkCssMatcher  *matcher,
-                                              gpointer              res)
-{
-  const GtkCssSelectorTree *tree = (const GtkCssSelectorTree *) selector;
-  const GtkCssSelectorTree *sub;
-
   gtk_css_selector_tree_found_match (tree, res);
 
-  if (tree->n_names > 0)
-    {
-      TreeNameMatch *names;
-      TreeNameMatch *match;
-      TreeNameMatch key;
-
-      key.name = _gtk_css_matcher_get_name (matcher);
-      names = gtk_css_selector_tree_get_names (tree);
-
-      match = bsearch (&key, names, tree->n_names, sizeof (TreeNameMatch), name_sort_func);
-      if (match)
-        {
-          sub = gtk_css_selector_tree_at_offset (tree, match->offset);
-          gtk_css_selector_tree_match_foreach_no_check (&sub->selector, matcher, res);
-        }
-    }
-
-  if (tree->n_classes > 0)
-    {
-      GQuark *classes;
-      guint n_classes;
-      gboolean allocated;
-      TreeClassMatch *tree_classes;
-      int i, j;
-
-      classes = _gtk_css_matcher_get_classes (matcher, &n_classes, &allocated);
-      tree_classes = gtk_css_selector_tree_get_classes (tree);
-      i = j = 0;
-      while (i < n_classes && j < tree->n_classes)
-        {
-          if (classes[i] < tree_classes[j].class)
-            i++;
-          else if (classes[i] > tree_classes[j].class)
-            j++;
-          else
-            {
-              sub = gtk_css_selector_tree_at_offset (tree, tree_classes[j].offset);
-              gtk_css_selector_tree_match_foreach_no_check (&sub->selector, matcher, res);
-              i++;
-              j++;
-            }
-        }
-      if (allocated)
-        g_free (classes);
-    }
-  
-  if (tree->n_other > 0)
-    {
-      TreeOtherMatch *other;
-      int i;
-
-      other = gtk_css_selector_tree_get_others (tree);
-      for (i = 0; i < tree->n_other; i++)
-        {
-          sub = gtk_css_selector_tree_at_offset (tree, other[i].offset);
-          gtk_css_selector_foreach (&sub->selector, matcher, gtk_css_selector_tree_match_foreach, res);
-        }
-    }
+  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, matcher, gtk_css_selector_tree_match_foreach, res);
 
   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;
 
-  gtk_css_selector_tree_match_foreach (&tree->selector, matcher, &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;
 }
@@ -2073,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;
 
@@ -2095,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)
@@ -2135,8 +2056,6 @@ _gtk_css_selector_tree_print (const GtkCssSelectorTree *tree, GString *str, char
           else
             g_string_append_printf (str, " (%d matches)", n);
         }
-      if (tree->n_names || tree->n_classes || tree->n_other)
-        g_string_append_printf (str, "(%d/%d/%d)", tree->n_names, tree->n_classes, tree->n_other);
       len = str->len - len;
 
       if (gtk_css_selector_tree_get_previous (tree))
@@ -2201,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);
 }
 
 
@@ -2214,6 +2145,8 @@ typedef struct {
   gpointer match;
   GtkCssSelector *current_selector;
   GtkCssSelectorTree **selector_match;
+  const char *name;
+  GQuark class;
 } GtkCssSelectorRuleSetInfo;
 
 static GtkCssSelectorTree *
@@ -2284,12 +2217,6 @@ subdivide_infos (GByteArray *array, GList *infos, gint32 parent_offset)
   tree = alloc_tree (array, &tree_offset);
   tree->parent_offset = parent_offset;
   tree->selector = max_selector;
-  tree->name_offset = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-  tree->class_offset = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-  tree->other_offset = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-  tree->n_names = 0;
-  tree->n_classes = 0;
-  tree->n_other = 0;
 
   exact_matches = NULL;
   for (l = infos; l != NULL; l = l->next)
@@ -2343,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 == &GTK_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 == &GTK_CSS_SELECTOR_CLASS)
+        return selector->style_class.style_class;
+    }
+
+  return 0;
+}
+
 void
 _gtk_css_selector_tree_builder_add (GtkCssSelectorTreeBuilder *builder,
 				    GtkCssSelector            *selectors,
@@ -2370,18 +2348,33 @@ _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 */
 static void
 fixup_offsets (GtkCssSelectorTree *tree, guint8 *data)
 {
-  TreeNameMatch *names;
-  TreeClassMatch *classes;
-  TreeOtherMatch *others;
-  int i;
-
   while (tree != NULL)
     {
       if (tree->parent_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
@@ -2396,151 +2389,14 @@ fixup_offsets (GtkCssSelectorTree *tree, guint8 *data)
       if (tree->matches_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
 	tree->matches_offset -= ((guint8 *)tree - data);
 
-      if (tree->name_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
-	tree->name_offset -= ((guint8 *)tree - data);
-
-      if (tree->class_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
-	tree->class_offset -= ((guint8 *)tree - data);
-
-      if (tree->other_offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET)
-	tree->other_offset -= ((guint8 *)tree - data);
-
-      names = gtk_css_selector_tree_get_names (tree);
-      for (i = 0; i < tree->n_names; i++)
-        names[i].offset -= ((guint8 *)tree - data);
-
-      classes = gtk_css_selector_tree_get_classes (tree);
-      for (i = 0; i < tree->n_classes; i++)
-        classes[i].offset -= ((guint8 *)tree - data);
-
-      others = gtk_css_selector_tree_get_others (tree);
-      for (i = 0; i < tree->n_other; i++)
-        others[i].offset -= ((guint8 *)tree - data);
-
       fixup_offsets ((GtkCssSelectorTree *)gtk_css_selector_tree_get_previous (tree), data);
 
       tree = (GtkCssSelectorTree *)gtk_css_selector_tree_get_sibling (tree);
     }
 }
 
-static TreeMatchData *
-create_match_data (GByteArray *array, gint32 tree_offset)
-{
-  TreeMatchData *data;
-  const GtkCssSelectorTree *prev;
-  int n, c, o;
-  gint32 offset;
-
-  data = g_new0 (TreeMatchData, 1);
-
-  for (offset = get_tree (array, tree_offset)->previous_offset;
-       offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-       offset = get_tree (array, offset)->sibling_offset)
-    {
-      prev = get_tree (array, offset);
-      if (prev->selector.class == &GTK_CSS_SELECTOR_NAME)
-        data->n_names++;
-      else if (prev->selector.class == &GTK_CSS_SELECTOR_CLASS)
-        data->n_classes++;
-      else
-        data->n_other++;
-    }
-
-  data->names = g_new (TreeNameMatch, data->n_names);
-  data->classes = g_new (TreeClassMatch, data->n_classes);
-  data->other = g_new (TreeOtherMatch, data->n_other);
-
-  n = c = o = 0;
-  for (offset = get_tree (array, tree_offset)->previous_offset;
-       offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-       offset = get_tree (array, offset)->sibling_offset)
-    {
-      prev = get_tree (array, offset);
-      if (prev->selector.class == &GTK_CSS_SELECTOR_NAME)
-        { 
-          data->names[n].name = prev->selector.name.name;
-          data->names[n].offset = offset;
-          n++;
-        }
-      else if (prev->selector.class == &GTK_CSS_SELECTOR_CLASS)
-        {
-          data->classes[c].class = prev->selector.style_class.style_class;
-          data->classes[c].offset = offset;
-          c++;
-        }
-      else
-        {
-          data->other[o].offset = offset;
-          o++;
-        }
-    }
-  g_assert (n == data->n_names);
-  g_assert (c == data->n_classes);
-  g_assert (o == data->n_other);
-
-  if (data->n_names)
-    qsort ((void *)data->names, (unsigned)data->n_names, sizeof (TreeNameMatch), name_sort_func);
-  if (data->n_classes)
-    qsort ((void *)data->classes, (unsigned)data->n_classes, sizeof (TreeClassMatch), class_sort_func);
-
-  return data;
-}
-
-static void
-free_match_data (TreeMatchData *data)
-{
-  g_free (data->names);
-  g_free (data->classes);
-  g_free (data->other);
-  g_free (data);
-}
-
-static void
-create_tree_match_data (GByteArray *array, gint32 tree_offset)
-{
-  GtkCssSelectorTree *tree;
-  TreeMatchData *data;
-  gint32 offset;
-
-  data = create_match_data (array, tree_offset);
-
-  tree = get_tree (array, tree_offset);
-  if (data->n_names > 0)
-    {
-      tree->name_offset = array->len;
-      tree->n_names = data->n_names;
-      g_byte_array_append (array, (guint8 *)data->names, data->n_names * sizeof (TreeNameMatch));
-      tree = get_tree (array, tree_offset);
-    }
-
-  if (data->n_classes > 0)
-    {
-      tree->class_offset = array->len;
-      tree->n_classes = data->n_classes;
-      g_byte_array_append (array, (guint8 *)data->classes, data->n_classes * sizeof (TreeClassMatch));
-      tree = get_tree (array, tree_offset);
-    }
-  
-  if (data->n_other > 0)
-    {
-      tree->other_offset = array->len;
-      tree->n_other = data->n_other;
-      g_byte_array_append (array, (guint8 *)data->other, data->n_other * sizeof (TreeOtherMatch));
-      tree = get_tree (array, tree_offset);
-    }
-
-  free_match_data (data);
-
-  for (offset = tree->previous_offset;
-       offset != GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-       offset = get_tree (array, offset)->sibling_offset)
-    {
-      create_tree_match_data (array, offset);
-    }
-}
-
-GtkCssSelectorTree *
-_gtk_css_selector_tree_builder_build (GtkCssSelectorTreeBuilder *builder)
+static GtkCssSelectorTree *
+_gtk_css_selector_tree_builder_build_one (GList *infos)
 {
   GtkCssSelectorTree *tree;
   GByteArray *array;
@@ -2548,27 +2404,9 @@ _gtk_css_selector_tree_builder_build (GtkCssSelectorTreeBuilder *builder)
   guint len;
   GList *l;
   GtkCssSelectorRuleSetInfo *info;
-  gint32 tree_offset;
-  gint32 offset;
 
   array = g_byte_array_new ();
-
-  tree = alloc_tree (array, &tree_offset);
-  g_assert (tree_offset == 0);
-  tree->parent_offset = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-  tree->sibling_offset = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-  tree->matches_offset = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-  tree->selector.class = &GTK_CSS_SELECTOR_ANY;
-  tree->name_offset = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-  tree->class_offset = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-  tree->other_offset = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
-  tree->n_names = 0;
-  tree->n_classes = 0;
-  tree->n_other = 0;
-  offset = subdivide_infos (array, builder->infos, tree_offset);
-  get_tree (array, tree_offset)->previous_offset = offset;
-
-  create_tree_match_data (array, 0);
+  subdivide_infos (array, infos, GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET);
 
   len = array->len;
   data = g_byte_array_free (array, FALSE);
@@ -2581,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)
@@ -2599,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;
+}

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