get logic right, #66249

Fri Dec  7 20:06:14 2001  Jonathan Blandford  <jrb@redhat.com>

	* gtk/gtktreeview.c (validate_visible_area): get logic right,
	#66249

	* gtk/gtkrbtree.c (_gtk_rbtree_remove_node): fix bug where
	removing a node ended up with a corrupt tree.  Really really nasty
	bug.
	(_gtk_rbtree_debug_spew): new debug helper function
	(_fixup_validation): new inline function to clean up code
	readability a lot.

1 files changed, 283 insertions, 101 deletions

diff --git a/gtk/gtkrbtree.c b/gtk/gtkrbtree.c
index 9bba7ab666..e40c8d1ed3 100644
--- a/gtk/gtkrbtree.c
+++ b/gtk/gtkrbtree.c
@@ -20,20 +20,23 @@
 #include "gtkrbtree.h"
 #include "gtkdebug.h"
 
-static void       _gtk_rbnode_validate_allocator (GAllocator *allocator);
-static GtkRBNode *_gtk_rbnode_new                (GtkRBTree  *tree,
-						  gint        height);
-static void       _gtk_rbnode_free               (GtkRBNode  *node);
-static void       _gtk_rbnode_rotate_left        (GtkRBTree  *tree,
-						  GtkRBNode  *node);
-static void       _gtk_rbnode_rotate_right       (GtkRBTree  *tree,
-						  GtkRBNode  *node);
-static void       _gtk_rbtree_insert_fixup       (GtkRBTree  *tree,
-						  GtkRBNode  *node);
-static void       _gtk_rbtree_remove_node_fixup  (GtkRBTree  *tree,
-						  GtkRBNode  *node);
-static gint       _count_nodes                   (GtkRBTree  *tree,
-						  GtkRBNode  *node);
+static void        _gtk_rbnode_validate_allocator (GAllocator *allocator);
+static GtkRBNode * _gtk_rbnode_new                (GtkRBTree  *tree,
+						   gint        height);
+static void        _gtk_rbnode_free               (GtkRBNode  *node);
+static void        _gtk_rbnode_rotate_left        (GtkRBTree  *tree,
+						   GtkRBNode  *node);
+static void        _gtk_rbnode_rotate_right       (GtkRBTree  *tree,
+						   GtkRBNode  *node);
+static void        _gtk_rbtree_insert_fixup       (GtkRBTree  *tree,
+						   GtkRBNode  *node);
+static void        _gtk_rbtree_remove_node_fixup  (GtkRBTree  *tree,
+						   GtkRBNode  *node);
+static gint        _count_nodes                   (GtkRBTree  *tree,
+						   GtkRBNode  *node);
+static inline void _fixup_validation              (GtkRBTree  *tree,
+						   GtkRBNode  *node);
+
 
 
 /* node allocation
@@ -53,6 +56,7 @@ struct _GAllocator /* from gmem.c */
 G_LOCK_DEFINE_STATIC (current_allocator);
 static GAllocator *current_allocator = NULL;
 
+
 /* HOLDS: current_allocator_lock */
 static void
 _gtk_rbnode_validate_allocator (GAllocator *allocator)
@@ -208,22 +212,8 @@ _gtk_rbnode_rotate_left (GtkRBTree *tree,
     (right->right?right->right->parity:0) +
     (right->children?right->children->root->parity:0);
 
-  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))
-    {
-      if ((! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&
-	  (node->right != tree->nil && ! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) &&
-	  (node->left != tree->nil && ! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) &&
-	  (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
-	GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
-    }
-  if (GTK_RBNODE_FLAG_SET (right, GTK_RBNODE_DESCENDANTS_INVALID))
-    {
-      if ((! GTK_RBNODE_FLAG_SET (right, GTK_RBNODE_INVALID)) &&
-	  (right->right != tree->nil && ! GTK_RBNODE_FLAG_SET (right->right, GTK_RBNODE_DESCENDANTS_INVALID)) &&
-	  (right->left != tree->nil && ! GTK_RBNODE_FLAG_SET (right->left, GTK_RBNODE_DESCENDANTS_INVALID)) &&
-	  (right->children && GTK_RBNODE_FLAG_SET (right->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
-	GTK_RBNODE_UNSET_FLAG (right, GTK_RBNODE_DESCENDANTS_INVALID);
-    }
+  _fixup_validation (tree, node);
+  _fixup_validation (tree, right);
 }
 
 static void
@@ -300,22 +290,8 @@ _gtk_rbnode_rotate_right (GtkRBTree *tree,
     (left->right?left->right->parity:0) +
     (left->children?left->children->root->parity:0);
 
-  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))
-    {
-      if ((! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&
-	  (node->right != tree->nil && ! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) &&
-	  (node->left != tree->nil && ! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) &&
-	  (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
-	GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
-    }
-  if (GTK_RBNODE_FLAG_SET (left, GTK_RBNODE_DESCENDANTS_INVALID))
-    {
-      if ((! GTK_RBNODE_FLAG_SET (left, GTK_RBNODE_INVALID)) &&
-	  (left->right != tree->nil && ! GTK_RBNODE_FLAG_SET (left->right, GTK_RBNODE_DESCENDANTS_INVALID)) &&
-	  (left->left != tree->nil && ! GTK_RBNODE_FLAG_SET (left->left, GTK_RBNODE_DESCENDANTS_INVALID)) &&
-	  (left->children && GTK_RBNODE_FLAG_SET (left->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
-	GTK_RBNODE_UNSET_FLAG (left, GTK_RBNODE_DESCENDANTS_INVALID);
-    }
+  _fixup_validation (tree, node);
+  _fixup_validation (tree, left);
 }
 
 static void
@@ -545,8 +521,13 @@ _gtk_rbtree_remove (GtkRBTree *tree)
   tmp_tree = tree->parent_tree;
   tmp_node = tree->parent_node;
 
+  /* ugly hack to make _fixup_validation work in the first iteration of the
+   * loop below */
+  GTK_RBNODE_UNSET_FLAG (tree->root, GTK_RBNODE_DESCENDANTS_INVALID);
+  
   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
     {
+      _fixup_validation (tmp_tree, tmp_node);
       tmp_node->offset -= height;
 
       /* If the removed tree was odd, flip all parents */
@@ -581,9 +562,6 @@ _gtk_rbtree_insert_after (GtkRBTree *tree,
   GtkRBNode *tmp_node;
   GtkRBTree *tmp_tree;  
 
-  if (gtk_debug_flags & GTK_DEBUG_TREE)
-    _gtk_rbtree_test (G_STRLOC, tree);
-  
   if (current != NULL && current->right != tree->nil)
     {
       current = current->right;
@@ -591,7 +569,6 @@ _gtk_rbtree_insert_after (GtkRBTree *tree,
 	current = current->left;
       right = FALSE;
     }
-
   /* setup new node */
   node = _gtk_rbnode_new (tree, height);
   node->parent = (current?current:tree->nil);
@@ -629,16 +606,17 @@ _gtk_rbtree_insert_after (GtkRBTree *tree,
 	  tmp_tree = tmp_tree->parent_tree;
 	}
     }
-  _gtk_rbtree_insert_fixup (tree, node);
-
-  if (gtk_debug_flags & GTK_DEBUG_TREE)
-    _gtk_rbtree_test (G_STRLOC, tree);
 
   if (valid)
     _gtk_rbtree_node_mark_valid (tree, node);
   else
     _gtk_rbtree_node_mark_invalid (tree, node);
 
+  _gtk_rbtree_insert_fixup (tree, node);
+
+  if (gtk_debug_flags & GTK_DEBUG_TREE)
+    _gtk_rbtree_test (G_STRLOC, tree);
+
   return node;
 }
 
@@ -652,9 +630,6 @@ _gtk_rbtree_insert_before (GtkRBTree *tree,
   gboolean left = TRUE;
   GtkRBNode *tmp_node;
   GtkRBTree *tmp_tree;
-
-  if (gtk_debug_flags & GTK_DEBUG_TREE)
-    _gtk_rbtree_test (G_STRLOC, tree);
   
   if (current != NULL && current->left != tree->nil)
     {
@@ -701,16 +676,17 @@ _gtk_rbtree_insert_before (GtkRBTree *tree,
 	  tmp_tree = tmp_tree->parent_tree;
 	}
     }
-  _gtk_rbtree_insert_fixup (tree, node);
-
-  if (gtk_debug_flags & GTK_DEBUG_TREE)
-    _gtk_rbtree_test (G_STRLOC, tree);
 
   if (valid)
     _gtk_rbtree_node_mark_valid (tree, node);
   else
     _gtk_rbtree_node_mark_invalid (tree, node);
 
+  _gtk_rbtree_insert_fixup (tree, node);
+
+  if (gtk_debug_flags & GTK_DEBUG_TREE)
+    _gtk_rbtree_test (G_STRLOC, tree);
+
   return node;
 }
 
@@ -758,6 +734,8 @@ _gtk_rbtree_node_set_height (GtkRBTree *tree,
 	  tmp_tree = tmp_tree->parent_tree;
 	}
     }
+  if (gtk_debug_flags & GTK_DEBUG_TREE)
+    _gtk_rbtree_test (G_STRLOC, tree);
 }
 
 void
@@ -774,7 +752,7 @@ _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
 	return;
       GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
       node = node->parent;
-      if (node == NULL)
+      if (node == tree->nil)
 	{
 	  node = tree->parent_node;
 	  tree = tree->parent_tree;
@@ -783,6 +761,27 @@ _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
   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 (node == tree->nil)
+	{
+	  node = tree->parent_node;
+	  tree = tree->parent_tree;
+	}
+    }
+  while (node);
+}
+#endif
+
 void
 _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
 			     GtkRBNode *node)
@@ -805,7 +804,7 @@ _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
 
       GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
       node = node->parent;
-      if (node == NULL)
+      if (node == tree->nil)
 	{
 	  node = tree->parent_node;
 	  tree = tree->parent_tree;
@@ -814,7 +813,28 @@ _gtk_rbtree_node_mark_valid (GtkRBTree *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 (node == tree->nil)
+	{
+	  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
@@ -1109,8 +1129,6 @@ _gtk_rbtree_find_offset (GtkRBTree  *tree,
 			      GtkRBTree **new_tree,
 			      GtkRBNode **new_node)
 {
-  GtkRBNode *tmp_node;
-
   g_assert (tree);
 
   if ((height < 0) ||
@@ -1121,7 +1139,7 @@ _gtk_rbtree_find_offset (GtkRBTree  *tree,
 
       return 0;
     }
-  _gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
+  return _gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
 }
 
 void
@@ -1136,7 +1154,12 @@ _gtk_rbtree_remove_node (GtkRBTree *tree,
   
   g_return_if_fail (tree != NULL);
   g_return_if_fail (node != NULL);
-  
+
+  if (gtk_debug_flags & GTK_DEBUG_TREE)
+    {
+      _gtk_rbtree_debug_spew (tree);
+      _gtk_rbtree_test (G_STRLOC, tree);
+    }
   /* make sure we're deleting a node that's actually in the tree */
   for (x = node; x->parent != tree->nil; x = x->parent)
     ;
@@ -1159,21 +1182,21 @@ _gtk_rbtree_remove_node (GtkRBTree *tree,
 
   /* adjust count only beneath tree */
   for (x = y; x != tree->nil; x = x->parent)
-    x->count--;
-
-  /*   y->count = node->count; */
+    {
+      x->count--;
+    }
 
   /* offsets and parity adjust all the way up through parent trees */
   y_height = GTK_RBNODE_GET_HEIGHT (y);
   node_height = GTK_RBNODE_GET_HEIGHT (node) + (node->children?node->children->root->offset:0);
 
-  /* Do this twice for code clarities sake. */
   tmp_tree = tree;
   tmp_node = y;
   while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
     {
       tmp_node->offset -= (y_height + (y->children?y->children->root->offset:0));
       tmp_node->parity -= (1 + (y->children?y->children->root->parity:0));
+      _fixup_validation (tmp_tree, tmp_node);
 
       tmp_node = tmp_node->parent;
       if (tmp_node == tmp_tree->nil)
@@ -1183,7 +1206,7 @@ _gtk_rbtree_remove_node (GtkRBTree *tree,
 	}
     }
 
-  /* x is y's only child */
+  /* x is y's only child, or nil */
   if (y->left != tree->nil)
     x = y->left;
   else
@@ -1192,12 +1215,37 @@ _gtk_rbtree_remove_node (GtkRBTree *tree,
   /* remove y from the parent chain */
   x->parent = y->parent;
   if (y->parent != tree->nil)
-    if (y == y->parent->left)
-      y->parent->left = x;
-    else
-      y->parent->right = x;
+    {
+      if (y == y->parent->left)
+	y->parent->left = x;
+      else
+	y->parent->right = x;
+    }
   else
-    tree->root = x;
+    {
+      tree->root = x;
+    }
+
+  /* We need to clean up the validity of the tree.
+   */
+
+  tmp_tree = tree;
+  tmp_node = x;
+  do
+    {
+      if (tmp_node != tmp_tree->nil)
+	{
+	  /* We skip the first time, iff x is nil */
+	  _fixup_validation (tmp_tree, tmp_node);
+	}
+      tmp_node = tmp_node->parent;
+      if (tmp_node == tmp_tree->nil)
+	{
+	  tmp_node = tmp_tree->parent_node;
+	  tmp_tree = tmp_tree->parent_tree;
+	}
+    }
+  while (tmp_tree != NULL);
 
   if (y != node)
     {
@@ -1209,36 +1257,45 @@ _gtk_rbtree_remove_node (GtkRBTree *tree,
       else
 	node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_RED);
       node->children = y->children;
-
+      if (y->children)
+	{
+	  node->children = y->children;
+	  node->children->parent_node = node;
+	}
+      else
+	{
+	  node->children = NULL;
+	}
+      _fixup_validation (tree, node);
       /* We want to see how different our height is from the previous node.
        * To do this, we compare our current height with our supposed height.
        */
       diff = y_height - GTK_RBNODE_GET_HEIGHT (node);
-      if (diff != 0)
-	{
-	  tmp_tree = tree;
-	  tmp_node = node;
+      tmp_tree = tree;
+      tmp_node = node;
 
-	  while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
+      while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
+	{
+	  tmp_node->offset += diff;
+	  _fixup_validation (tmp_tree, tmp_node);
+	  tmp_node = tmp_node->parent;
+	  if (tmp_node == tmp_tree->nil)
 	    {
-	      tmp_node->offset += diff;
-	      tmp_node = tmp_node->parent;
-	      if (tmp_node == tmp_tree->nil)
-		{
-		  tmp_node = tmp_tree->parent_node;
-		  tmp_tree = tmp_tree->parent_tree;
-		}
+	      tmp_node = tmp_tree->parent_node;
+	      tmp_tree = tmp_tree->parent_tree;
 	    }
 	}
     }
 
   if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
     _gtk_rbtree_remove_node_fixup (tree, x);
-
   _gtk_rbnode_free (y);
 
   if (gtk_debug_flags & GTK_DEBUG_TREE)
-    _gtk_rbtree_test (G_STRLOC, tree);
+    {
+      _gtk_rbtree_debug_spew (tree);
+      _gtk_rbtree_test (G_STRLOC, tree);
+    }
 }
 
 GtkRBNode *
@@ -1454,6 +1511,24 @@ _count_nodes (GtkRBTree *tree,
   return res;
 }
 
+static inline
+void _fixup_validation (GtkRBTree *tree,
+			GtkRBNode *node)
+{
+  if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
+      GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
+      (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
+      (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
+      (node->children != NULL && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
+    {
+      GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
+    }
+  else
+    {
+      GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
+    }
+}
+
 static guint
 get_parity (GtkRBNode *node)
 {
@@ -1539,28 +1614,135 @@ _gtk_rbtree_test_height (GtkRBTree *tree,
     _gtk_rbtree_test_height (node->children, node->children->root);
 }
 
+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) ||
+		(node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
+		(node->right != tree->nil && 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 (node->left != tree->nil)
+	g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
+      if (node->right != tree->nil)
+	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 (node->left != tree->nil)
+    _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
+  if (node->right != tree->nil)
+    _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
+  if (node->children != NULL)
+    _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 (node != tree->nil);
+
+  g_assert (node->left != NULL);
+  g_assert (node->right != NULL);
+  g_assert (node->parent != NULL);
+
+  if (node->left != tree->nil)
+    {
+      g_assert (node->left->parent == node);
+      _gtk_rbtree_test_structure_helper (tree, node->left);
+    }
+  if (node->right != tree->nil)
+    {
+      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);
+  g_assert (tree->root->parent == tree->nil);
+
+  _gtk_rbtree_test_structure_helper (tree, tree->root);
+}
+			    
 void
 _gtk_rbtree_test (const gchar *where,
                   GtkRBTree   *tree)
 {
   GtkRBTree *tmp_tree;
 
+  if (tree == NULL)
+    return;
+
   /* Test the entire tree */
   tmp_tree = tree;
   while (tmp_tree->parent_tree)
     tmp_tree = tmp_tree->parent_tree;
   
-  g_print ("%s: whole tree offset is %d\n", where, tmp_tree->root->offset);
 
-  if (tmp_tree->root != tmp_tree->nil)
-    {
-      g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
-                 _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
+  g_assert (tmp_tree->root && tmp_tree->root != tmp_tree->nil);
+
+  _gtk_rbtree_test_structure (tmp_tree);
+
+  g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
+	     _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
       
       
-      _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
-  
-      g_assert (count_parity (tmp_tree, tmp_tree->root) == tmp_tree->root->parity);
-    }
+  _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
+  _gtk_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_RBNODE_FLAG_SET (tmp_tree->root, GTK_RBNODE_DESCENDANTS_INVALID));
+  g_assert (count_parity (tmp_tree, tmp_tree->root) == tmp_tree->root->parity);
 }
 
+static void
+_gtk_rbtree_debug_spew_helper (GtkRBTree *tree,
+			       GtkRBNode *node,
+			       gint       depth)
+{
+  gint i;
+  for (i = 0; i < depth; i++)
+    g_print ("\t");
+
+  g_print ("(%x - %s) %d%d%d\n",
+	   (gint) node,
+	   (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
+	   (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))?1:0,
+	   (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))?1:0,
+	   (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))?1:0);
+  if (node->left != tree->nil)
+    _gtk_rbtree_debug_spew_helper (tree, node->left, depth+1);
+  if (node->right != tree->nil)
+    _gtk_rbtree_debug_spew_helper (tree, node->right, depth+1);
+}
+
+void
+_gtk_rbtree_debug_spew (GtkRBTree *tree)
+{
+  g_return_if_fail (tree != NULL);
+
+  g_print ("=====\n");
+  _gtk_rbtree_debug_spew_helper (tree, tree->root, 0);
+  g_print ("=====\n\n\n");
+}