+static void
+_gtk_rbtree_test_dirty (GtkRBTree *tree,
+ GtkRBNode *node,
+ gint expected_dirtyness)
+{
+
+ if (expected_dirtyness)
+ {
+ g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
+ GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
+ GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) ||
+ GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID) ||
+ (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)));
+ }
+ else
+ {
+ g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
+ ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
+ if (!_gtk_rbtree_is_nil (node->left))
+ g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
+ if (!_gtk_rbtree_is_nil (node->right))
+ g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
+ if (node->children != NULL)
+ g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
+ }
+
+ if (!_gtk_rbtree_is_nil (node->left))
+ _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
+ if (!_gtk_rbtree_is_nil (node->right))
+ _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
+ if (node->children != NULL && !_gtk_rbtree_is_nil (node->children->root))
+ _gtk_rbtree_test_dirty (node->children, node->children->root, GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
+}
+
+static void _gtk_rbtree_test_structure (GtkRBTree *tree);
+
+static void
+_gtk_rbtree_test_structure_helper (GtkRBTree *tree,
+ GtkRBNode *node)
+{
+ g_assert (!_gtk_rbtree_is_nil (node));
+
+ g_assert (node->left != NULL);
+ g_assert (node->right != NULL);
+ g_assert (node->parent != NULL);
+
+ if (!_gtk_rbtree_is_nil (node->left))
+ {
+ g_assert (node->left->parent == node);
+ _gtk_rbtree_test_structure_helper (tree, node->left);
+ }
+ if (!_gtk_rbtree_is_nil (node->right))
+ {
+ g_assert (node->right->parent == node);
+ _gtk_rbtree_test_structure_helper (tree, node->right);
+ }
+
+ if (node->children != NULL)
+ {
+ g_assert (node->children->parent_tree == tree);
+ g_assert (node->children->parent_node == node);
+
+ _gtk_rbtree_test_structure (node->children);
+ }
+}
+static void
+_gtk_rbtree_test_structure (GtkRBTree *tree)
+{
+ g_assert (tree->root);
+ if (_gtk_rbtree_is_nil (tree->root))
+ return;
+
+ g_assert (_gtk_rbtree_is_nil (tree->root->parent));
+ _gtk_rbtree_test_structure_helper (tree, tree->root);
+}
+
+static void