+ while (node);
+}
+
+#if 0
+/* Draconian version. */
+void
+_gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
+ GtkRBNode *node)
+{
+ GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
+ do
+ {
+ _fixup_validation (tree, node);
+ node = node->parent;
+ if (_gtk_rbtree_is_nil (node))
+ {
+ node = tree->parent_node;
+ tree = tree->parent_tree;
+ }
+ }
+ while (node);
+}
+#endif
+
+void
+_gtk_rbtree_node_mark_valid (GtkRBTree *tree,
+ GtkRBNode *node)
+{
+ if ((!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&
+ (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)))
+ return;
+
+ GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
+ GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
+
+ do
+ {
+ if ((GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) ||
+ (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)) ||
+ (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)) ||
+ (GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
+ (GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)))
+ return;
+
+ GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
+ node = node->parent;
+ if (_gtk_rbtree_is_nil (node))
+ {
+ node = tree->parent_node;
+ tree = tree->parent_tree;
+ }
+ }
+ while (node);
+}
+
+#if 0
+/* Draconian version */
+void
+_gtk_rbtree_node_mark_valid (GtkRBTree *tree,
+ GtkRBNode *node)
+{
+ GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
+ GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
+
+ do
+ {
+ _fixup_validation (tree, node);
+ node = node->parent;
+ if (_gtk_rbtree_is_nil (node))
+ {
+ node = tree->parent_node;
+ tree = tree->parent_tree;
+ }
+ }
+ while (node);
+}
+#endif
+/* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above.
+ */
+void
+_gtk_rbtree_column_invalid (GtkRBTree *tree)
+{
+ GtkRBNode *node;
+
+ if (tree == NULL)
+ return;
+
+ node = _gtk_rbtree_first (tree);
+
+ do
+ {
+ if (! (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)))
+ GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
+ GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
+
+ if (node->children)
+ _gtk_rbtree_column_invalid (node->children);
+ }
+ while ((node = _gtk_rbtree_next (tree, node)) != NULL);
+}
+
+void
+_gtk_rbtree_mark_invalid (GtkRBTree *tree)
+{
+ GtkRBNode *node;
+
+ if (tree == NULL)
+ return;
+
+ node = _gtk_rbtree_first (tree);
+
+ do
+ {
+ GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
+ GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
+
+ if (node->children)
+ _gtk_rbtree_mark_invalid (node->children);
+ }
+ while ((node = _gtk_rbtree_next (tree, node)) != NULL);
+}
+
+void
+_gtk_rbtree_set_fixed_height (GtkRBTree *tree,
+ gint height,
+ gboolean mark_valid)
+{
+ GtkRBNode *node;
+
+ if (tree == NULL)
+ return;
+
+ node = _gtk_rbtree_first (tree);
+
+ do
+ {
+ if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
+ {
+ _gtk_rbtree_node_set_height (tree, node, height);
+ if (mark_valid)
+ _gtk_rbtree_node_mark_valid (tree, node);
+ }
+
+ if (node->children)
+ _gtk_rbtree_set_fixed_height (node->children, height, mark_valid);
+ }
+ while ((node = _gtk_rbtree_next (tree, node)) != NULL);
+}
+
+static void
+reorder_prepare (GtkRBTree *tree,
+ GtkRBNode *node,
+ gpointer data)
+{
+ node->offset -= node->left->offset + node->right->offset;
+ GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
+}
+
+static void
+reorder_fixup (GtkRBTree *tree,
+ GtkRBNode *node,
+ gpointer data)
+{
+ node->offset += node->left->offset + node->right->offset;
+ node->count = 1 + node->left->count + node->right->count;
+ _fixup_validation (tree, node);
+ _fixup_total_count (tree, node);
+}
+
+static void
+reorder_copy_node (GtkRBTree *tree,
+ GtkRBNode *to,
+ GtkRBNode *from)
+{
+ to->flags = (to->flags & GTK_RBNODE_NON_COLORS) | GTK_RBNODE_GET_COLOR (from);
+
+ to->left = from->left;
+ if (!_gtk_rbtree_is_nil (to->left))
+ to->left->parent = to;
+
+ to->right = from->right;
+ if (!_gtk_rbtree_is_nil (to->right))
+ to->right->parent = to;
+
+ to->parent = from->parent;
+ if (_gtk_rbtree_is_nil (to->parent))
+ tree->root = to;
+ else if (to->parent->left == from)
+ to->parent->left = to;
+ else if (to->parent->right == from)
+ to->parent->right = to;
+}
+
+/* It basically pulls everything out of the tree, rearranges it, and puts it
+ * back together. Our strategy is to keep the old RBTree intact, and just
+ * rearrange the contents. When that is done, we go through and update the
+ * heights. There is probably a more elegant way to write this function. If
+ * anyone wants to spend the time writing it, patches will be accepted.
+ */
+void
+_gtk_rbtree_reorder (GtkRBTree *tree,
+ gint *new_order,
+ gint length)
+{
+ GtkRBNode **nodes;
+ GtkRBNode *node;
+ gint i, j;
+
+ g_return_if_fail (tree != NULL);
+ g_return_if_fail (length > 0);
+ g_return_if_fail (tree->root->count == length);
+
+ nodes = g_new (GtkRBNode *, length);
+
+ _gtk_rbtree_traverse (tree, tree->root, G_PRE_ORDER, reorder_prepare, NULL);
+
+ for (node = _gtk_rbtree_first (tree), i = 0;
+ node;
+ node = _gtk_rbtree_next (tree, node), i++)
+ {
+ nodes[i] = node;
+ }
+
+ for (i = 0; i < length; i++)
+ {
+ GtkRBNode tmp = { 0, };
+ GSList *l, *cycle = NULL;
+
+ tmp.offset = -1;
+
+ /* already swapped */
+ if (nodes[i] == NULL)
+ continue;
+ /* no need to swap */
+ if (new_order[i] == i)
+ continue;
+
+ /* make a list out of the pending nodes */
+ for (j = i; new_order[j] != i; j = new_order[j])
+ {
+ cycle = g_slist_prepend (cycle, nodes[j]);
+ nodes[j] = NULL;
+ }
+
+ node = nodes[j];
+ reorder_copy_node (tree, &tmp, node);
+ for (l = cycle; l; l = l->next)
+ {
+ reorder_copy_node (tree, node, l->data);
+ node = l->data;
+ }
+
+ reorder_copy_node (tree, node, &tmp);
+ nodes[j] = NULL;
+ g_slist_free (cycle);
+ }
+
+ _gtk_rbtree_traverse (tree, tree->root, G_POST_ORDER, reorder_fixup, NULL);
+
+ g_free (nodes);
+}
+
+/**
+ * _gtk_rbtree_contains:
+ * @tree: a tree
+ * @potential_child: a potential child of @tree
+ *
+ * Checks if @potential_child is a child (direct or via intermediate
+ * trees) of @tree.
+ *
+ * Returns: %TRUE if @potentitial_child is a child of @tree.
+ **/
+gboolean
+_gtk_rbtree_contains (GtkRBTree *tree,
+ GtkRBTree *potential_child)
+{
+ g_return_val_if_fail (tree != NULL, FALSE);
+ g_return_val_if_fail (potential_child != NULL, FALSE);
+
+ do {
+ potential_child = potential_child->parent_tree;
+ if (potential_child == tree)
+ return TRUE;
+ } while (potential_child != NULL);
+
+ return FALSE;