+
+/******************** SelectorTree handling *****************/
+
+static GHashTable *
+gtk_css_selectors_count_initial_init (void)
+{
+ return g_hash_table_new ((GHashFunc)gtk_css_selector_hash, (GEqualFunc)gtk_css_selector_equal);
+}
+
+static void
+gtk_css_selectors_count_initial (const GtkCssSelector *selector, GHashTable *hash)
+{
+ if (!selector->class->is_simple || selector->class->must_keep_order)
+ {
+ guint count = GPOINTER_TO_INT (g_hash_table_lookup (hash, selector));
+ g_hash_table_replace (hash, (gpointer)selector, GUINT_TO_POINTER (count + 1));
+ return;
+ }
+
+ for (;
+ selector && selector->class->is_simple && !selector->class->must_keep_order;
+ selector = gtk_css_selector_previous (selector))
+ {
+ guint count = GPOINTER_TO_INT (g_hash_table_lookup (hash, selector));
+ g_hash_table_replace (hash, (gpointer)selector, GUINT_TO_POINTER (count + 1));
+ }
+}
+
+static gboolean
+gtk_css_selectors_has_initial_selector (const GtkCssSelector *selector, const GtkCssSelector *initial)
+{
+ if (!selector->class->is_simple || selector->class->must_keep_order)
+ return gtk_css_selector_equal (selector, initial);
+
+ for (;
+ selector && selector->class->is_simple && !selector->class->must_keep_order;
+ selector = gtk_css_selector_previous (selector))
+ {
+ if (gtk_css_selector_equal (selector, initial))
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+static GtkCssSelector *
+gtk_css_selectors_skip_initial_selector (GtkCssSelector *selector, const GtkCssSelector *initial)
+{
+ GtkCssSelector *found;
+ GtkCssSelector tmp;
+
+ /* If the initial simple selector is not first, move it there so we can skip it
+ without losing any other selectors */
+ if (!gtk_css_selector_equal (selector, initial))
+ {
+ for (found = selector; found && found->class->is_simple; found = (GtkCssSelector *)gtk_css_selector_previous (found))
+ {
+ if (gtk_css_selector_equal (found, initial))
+ break;
+ }
+
+ g_assert (found != NULL && found->class->is_simple);
+
+ tmp = *found;
+ *found = *selector;
+ *selector = tmp;
+ }
+
+ return (GtkCssSelector *)gtk_css_selector_previous (selector);
+}
+
+static int
+direct_ptr_compare (const void *_a, const void *_b)
+{
+ gpointer *a = (gpointer *)_a;
+ gpointer *b = (gpointer *)_b;
+ if (*a < *b)
+ return -1;
+ else if (*a == *b)
+ return 0;
+ return 1;
+}
+
+GPtrArray *
+_gtk_css_selector_tree_match_all (const GtkCssSelectorTree *tree,
+ const GtkCssMatcher *matcher)
+{
+ GHashTable *res;
+ GPtrArray *array;
+ GHashTableIter iter;
+ gpointer key;
+
+ update_type_references ();
+
+ res = g_hash_table_new (g_direct_hash, g_direct_equal);
+
+ for (; tree != NULL;
+ tree = gtk_css_selector_tree_get_sibling (tree))
+ gtk_css_selector_tree_match (tree, matcher, res);
+
+ array = g_ptr_array_sized_new (g_hash_table_size (res));
+
+ g_hash_table_iter_init (&iter, res);
+ while (g_hash_table_iter_next (&iter, &key, NULL))
+ g_ptr_array_add (array, key);
+
+ g_hash_table_destroy (res);
+
+ qsort (array->pdata, array->len, sizeof (gpointer), direct_ptr_compare);
+
+ return array;
+}
+
+GtkCssChange
+_gtk_css_selector_tree_get_change_all (const GtkCssSelectorTree *tree,
+ const GtkCssMatcher *matcher)
+{
+ GtkCssChange change;
+
+ change = 0;
+
+ for (; tree != NULL;
+ tree = gtk_css_selector_tree_get_sibling (tree))
+ change |= gtk_css_selector_tree_get_change (tree, matcher);
+
+ /* Never return reserved bit set */
+ return change & ~GTK_CSS_CHANGE_RESERVED_BIT;
+}
+
+#ifdef PRINT_TREE
+static void
+_gtk_css_selector_tree_print (GtkCssSelectorTree *tree, GString *str, char *prefix)
+{
+ gboolean first = TRUE;
+ int len, i;
+
+ for (; tree != NULL; tree = tree->siblings, first = FALSE)
+ {
+ if (!first)
+ g_string_append (str, prefix);
+
+ if (first)
+ {
+ if (tree->siblings)
+ g_string_append (str, "─┬─");
+ else
+ g_string_append (str, "───");
+ }
+ else
+ {
+ if (tree->siblings)
+ g_string_append (str, " ├─");
+ else
+ g_string_append (str, " └─");
+ }
+
+ len = str->len;
+ tree->selector.class->print (&tree->selector, str);
+ len = str->len - len;
+
+ if (gtk_css_selector_tree_get_previous (tree))
+ {
+ GString *prefix2 = g_string_new (prefix);
+
+ if (tree->siblings)
+ g_string_append (prefix2, " │ ");
+ else
+ g_string_append (prefix2, " ");
+ for (i = 0; i < len; i++)
+ g_string_append_c (prefix2, ' ');
+
+ _gtk_css_selector_tree_print (gtk_css_selector_tree_get_previous (tree), str, prefix2->str);
+ g_string_free (prefix2, TRUE);
+ }
+ else
+ g_string_append (str, "\n");
+ }
+}
+#endif
+
+void
+_gtk_css_selector_tree_match_print (const GtkCssSelectorTree *tree,
+ GString *str)
+{
+ const GtkCssSelectorTree *parent;
+
+ g_return_if_fail (tree != NULL);
+
+ tree->selector.class->print (&tree->selector, str);
+
+ parent = gtk_css_selector_tree_get_parent (tree);
+ if (parent != NULL)
+ _gtk_css_selector_tree_match_print (parent, str);
+}
+
+void
+_gtk_css_selector_tree_free (GtkCssSelectorTree *tree)
+{
+ if (tree == NULL)
+ return;
+
+ g_free (tree);
+}
+
+
+typedef struct {
+ gpointer match;
+ GtkCssSelector *current_selector;
+ GtkCssSelectorTree **selector_match;
+} GtkCssSelectorRuleSetInfo;
+
+static GtkCssSelectorTree *
+get_tree (GByteArray *array, gint32 offset)
+{
+ return (GtkCssSelectorTree *) (array->data + offset);
+}
+
+static GtkCssSelectorTree *
+alloc_tree (GByteArray *array, gint32 *offset)
+{
+ GtkCssSelectorTree tree = { { NULL} };
+
+ *offset = array->len;
+ g_byte_array_append (array, (guint8 *)&tree, sizeof (GtkCssSelectorTree));
+ return get_tree (array, *offset);
+}
+
+static gint32
+subdivide_infos (GByteArray *array, GList *infos, gint32 parent_offset)
+{
+ GHashTable *ht;
+ GList *l;
+ GList *matched;
+ GList *remaining;
+ gint32 tree_offset;
+ GtkCssSelectorTree *tree;
+ GtkCssSelectorRuleSetInfo *info;
+ GtkCssSelector max_selector;
+ GHashTableIter iter;
+ guint max_count;
+ gpointer key, value;
+ GPtrArray *exact_matches;
+ gint32 res;
+
+ if (infos == NULL)
+ return GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
+
+ ht = gtk_css_selectors_count_initial_init ();
+
+ for (l = infos; l != NULL; l = l->next)
+ {
+ info = l->data;
+ gtk_css_selectors_count_initial (info->current_selector, ht);
+ }
+
+ /* Pick the selector with highest count, and use as decision on this level
+ as that makes it possible to skip the largest amount of checks later */
+
+ max_count = 0;
+
+ g_hash_table_iter_init (&iter, ht);
+ while (g_hash_table_iter_next (&iter, &key, &value))
+ {
+ GtkCssSelector *selector = key;
+ if (GPOINTER_TO_UINT (value) > max_count ||
+ (GPOINTER_TO_UINT (value) == max_count &&
+ gtk_css_selector_compare_one (selector, &max_selector) < 0))
+ {
+ max_count = GPOINTER_TO_UINT (value);
+ max_selector = *selector;
+ }
+ }
+
+ matched = NULL;
+ remaining = NULL;
+
+ tree = alloc_tree (array, &tree_offset);
+ tree->parent_offset = parent_offset;
+ tree->selector = max_selector;
+
+ exact_matches = NULL;
+ for (l = infos; l != NULL; l = l->next)
+ {
+ info = l->data;
+
+ if (gtk_css_selectors_has_initial_selector (info->current_selector, &max_selector))
+ {
+ info->current_selector = gtk_css_selectors_skip_initial_selector (info->current_selector, &max_selector);
+ if (info->current_selector == NULL)
+ {
+ /* Matches current node */
+ if (exact_matches == NULL)
+ exact_matches = g_ptr_array_new ();
+ g_ptr_array_add (exact_matches, info->match);
+ if (info->selector_match != NULL)
+ *info->selector_match = GUINT_TO_POINTER (tree_offset);
+ }
+ else
+ matched = g_list_prepend (matched, info);
+ }
+ else
+ {
+ remaining = g_list_prepend (remaining, info);
+ }
+ }
+
+ if (exact_matches)
+ {
+ g_ptr_array_add (exact_matches, NULL); /* Null terminate */
+ res = array->len;
+ g_byte_array_append (array, (guint8 *)exact_matches->pdata,
+ exact_matches->len * sizeof (gpointer));
+ g_ptr_array_free (exact_matches, TRUE);
+ }
+ else
+ res = GTK_CSS_SELECTOR_TREE_EMPTY_OFFSET;
+ get_tree (array, tree_offset)->matches_offset = res;
+
+ res = subdivide_infos (array, matched, tree_offset);
+ get_tree (array, tree_offset)->previous_offset = res;
+
+ res = subdivide_infos (array, remaining, parent_offset);
+ get_tree (array, tree_offset)->sibling_offset = res;
+
+ g_list_free (matched);
+ g_list_free (remaining);
+ g_hash_table_unref (ht);
+
+ return tree_offset;
+}
+
+struct _GtkCssSelectorTreeBuilder {
+ GList *infos;
+};
+
+GtkCssSelectorTreeBuilder *
+_gtk_css_selector_tree_builder_new (void)
+{
+ return g_new0 (GtkCssSelectorTreeBuilder, 1);
+}
+
+void
+_gtk_css_selector_tree_builder_free (GtkCssSelectorTreeBuilder *builder)
+{
+ g_list_free_full (builder->infos, g_free);
+ g_free (builder);
+}
+
+void
+_gtk_css_selector_tree_builder_add (GtkCssSelectorTreeBuilder *builder,
+ GtkCssSelector *selectors,
+ GtkCssSelectorTree **selector_match,
+ gpointer match)
+{
+ GtkCssSelectorRuleSetInfo *info = g_new0 (GtkCssSelectorRuleSetInfo, 1);
+
+ info->match = match;
+ info->current_selector = selectors;
+ info->selector_match = selector_match;
+ builder->infos = g_list_prepend (builder->infos, info);
+}
+
+/* Convert all offsets to node-relative */
+static void
+fixup_offsets (GtkCssSelectorTree *tree, guint8 *data)