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.

12 files changed, 396 insertions, 124 deletions

diff --git a/ChangeLog b/ChangeLog
index 54875ad42c..1d1223036c 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,15 @@
+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. 
+
 Fri Dec  7 19:34:51 2001  Owen Taylor  <otaylor@redhat.com>
 
 	* gtk/gtktoolbar.c (gtk_toolbar_insert_element):
diff --git a/ChangeLog.pre-2-0 b/ChangeLog.pre-2-0
index 54875ad42c..1d1223036c 100644
--- a/ChangeLog.pre-2-0
+++ b/ChangeLog.pre-2-0
@@ -1,3 +1,15 @@
+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. 
+
 Fri Dec  7 19:34:51 2001  Owen Taylor  <otaylor@redhat.com>
 
 	* gtk/gtktoolbar.c (gtk_toolbar_insert_element):
diff --git a/ChangeLog.pre-2-10 b/ChangeLog.pre-2-10
index 54875ad42c..1d1223036c 100644
--- a/ChangeLog.pre-2-10
+++ b/ChangeLog.pre-2-10
@@ -1,3 +1,15 @@
+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. 
+
 Fri Dec  7 19:34:51 2001  Owen Taylor  <otaylor@redhat.com>
 
 	* gtk/gtktoolbar.c (gtk_toolbar_insert_element):
diff --git a/ChangeLog.pre-2-2 b/ChangeLog.pre-2-2
index 54875ad42c..1d1223036c 100644
--- a/ChangeLog.pre-2-2
+++ b/ChangeLog.pre-2-2
@@ -1,3 +1,15 @@
+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. 
+
 Fri Dec  7 19:34:51 2001  Owen Taylor  <otaylor@redhat.com>
 
 	* gtk/gtktoolbar.c (gtk_toolbar_insert_element):
diff --git a/ChangeLog.pre-2-4 b/ChangeLog.pre-2-4
index 54875ad42c..1d1223036c 100644
--- a/ChangeLog.pre-2-4
+++ b/ChangeLog.pre-2-4
@@ -1,3 +1,15 @@
+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. 
+
 Fri Dec  7 19:34:51 2001  Owen Taylor  <otaylor@redhat.com>
 
 	* gtk/gtktoolbar.c (gtk_toolbar_insert_element):
diff --git a/ChangeLog.pre-2-6 b/ChangeLog.pre-2-6
index 54875ad42c..1d1223036c 100644
--- a/ChangeLog.pre-2-6
+++ b/ChangeLog.pre-2-6
@@ -1,3 +1,15 @@
+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. 
+
 Fri Dec  7 19:34:51 2001  Owen Taylor  <otaylor@redhat.com>
 
 	* gtk/gtktoolbar.c (gtk_toolbar_insert_element):
diff --git a/ChangeLog.pre-2-8 b/ChangeLog.pre-2-8
index 54875ad42c..1d1223036c 100644
--- a/ChangeLog.pre-2-8
+++ b/ChangeLog.pre-2-8
@@ -1,3 +1,15 @@
+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. 
+
 Fri Dec  7 19:34:51 2001  Owen Taylor  <otaylor@redhat.com>
 
 	* gtk/gtktoolbar.c (gtk_toolbar_insert_element):
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");
+}
diff --git a/gtk/gtkrbtree.h b/gtk/gtkrbtree.h
index 9db2ae2c26..04c5b0d925 100644
--- a/gtk/gtkrbtree.h
+++ b/gtk/gtkrbtree.h
@@ -167,10 +167,10 @@ void       _gtk_rbtree_prev_full        (GtkRBTree              *tree,
 
 gint       _gtk_rbtree_get_depth        (GtkRBTree              *tree);
 
-/* This func just checks the integrity of the tree */
-/* It will go away later. */
+/* This func checks the integrity of the tree */
 void       _gtk_rbtree_test             (const gchar            *where,
                                          GtkRBTree              *tree);
+void       _gtk_rbtree_debug_spew       (GtkRBTree              *tree);
 
 
 #ifdef __cplusplus
diff --git a/gtk/gtktreeview.c b/gtk/gtktreeview.c
index f9dfd99642..ecf3e6b393 100644
--- a/gtk/gtktreeview.c
+++ b/gtk/gtktreeview.c
@@ -891,7 +891,6 @@ static void
 gtk_tree_view_init (GtkTreeView *tree_view)
 {
   tree_view->priv = g_new0 (GtkTreeViewPrivate, 1);
-
   GTK_WIDGET_SET_FLAGS (tree_view, GTK_CAN_FOCUS);
 
   tree_view->priv->flags = GTK_TREE_VIEW_IS_LIST | GTK_TREE_VIEW_SHOW_EXPANDERS | GTK_TREE_VIEW_DRAW_KEYFOCUS | GTK_TREE_VIEW_HEADERS_VISIBLE;
@@ -3195,14 +3194,13 @@ validate_visible_area (GtkTreeView *tree_view)
   GtkRBNode *node;
   gint y, height, offset;
   gboolean validated_area = FALSE;
-
+  gboolean size_changed = FALSE;
   
   if (tree_view->priv->tree == NULL)
     return;
   
   if (! GTK_RBNODE_FLAG_SET (tree_view->priv->tree->root, GTK_RBNODE_DESCENDANTS_INVALID))
     return;
-
   
   height = GTK_WIDGET (tree_view)->allocation.height - TREE_VIEW_HEADER_HEIGHT (tree_view);
 
@@ -3224,8 +3222,17 @@ validate_visible_area (GtkTreeView *tree_view)
   gtk_tree_model_get_iter (tree_view->priv->model, &iter, path);
   do
     {
-      validated_area = validate_row (tree_view, tree, node, &iter, path) || validated_area;
+      gint old_height;
+
+      if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
+	  GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))
+	{
+	  validated_area = TRUE;
+	  if (validate_row (tree_view, tree, node, &iter, path))
+	    size_changed = TRUE;
+	}
       height -= GTK_RBNODE_GET_HEIGHT (node);
+
       if (node->children)
 	{
 	  GtkTreeIter parent = iter;
@@ -3280,8 +3287,10 @@ validate_visible_area (GtkTreeView *tree_view)
     }
   while (node && height > 0);
 
-  if (validated_area)
+  if (size_changed)
     gtk_widget_queue_resize (GTK_WIDGET (tree_view));
+  if (validated_area)
+    gtk_widget_queue_draw (GTK_WIDGET (tree_view));
 }
 
 /* Our strategy for finding nodes to validate is a little convoluted.  We find
@@ -3353,11 +3362,14 @@ validate_rows_handler (GtkTreeView *tree_view)
 		{
 		  break;
 		}
-	      else
+	      else if (node->children != NULL)
 		{
 		  tree = node->children;
 		  node = tree->root;
 		}
+	      else
+		/* RBTree corruption!  All bad */
+		g_assert_not_reached ();
 	    }
 	  while (TRUE);
 	  path = _gtk_tree_view_find_path (tree_view, tree, node);
@@ -3389,7 +3401,8 @@ presize_handler_callback (gpointer data)
 
   if (tree_view->priv->mark_rows_col_dirty)
     {
-      _gtk_rbtree_column_invalid (tree_view->priv->tree);
+      if (tree_view->priv->tree)
+	_gtk_rbtree_column_invalid (tree_view->priv->tree);
       tree_view->priv->mark_rows_col_dirty = FALSE;
     }
   validate_visible_area (tree_view);
@@ -5857,7 +5870,6 @@ gtk_tree_view_queue_draw_node (GtkTreeView  *tree_view,
 
   rect.y = BACKGROUND_FIRST_PIXEL (tree_view, tree, node);
   rect.height = BACKGROUND_HEIGHT (node);
-  //  g_print ("gtk_tree_view_queue_draw_node: (%d %d) (%d %d)\n", rect.x, rect.y, rect.width, rect.height);
 
   if (clip_rect)
     {
diff --git a/gtk/gtktreeviewcolumn.h b/gtk/gtktreeviewcolumn.h
index c81e583f51..fc105fada4 100644
--- a/gtk/gtktreeviewcolumn.h
+++ b/gtk/gtktreeviewcolumn.h
@@ -216,12 +216,6 @@ void                    gtk_tree_view_column_cell_render         (GtkTreeViewCol
 								  GdkRectangle            *cell_area,
 								  GdkRectangle            *expose_area,
 								  guint                    flags);
-gboolean                gtk_tree_view_column_cell_event          (GtkTreeViewColumn       *tree_column,
-								  GdkEvent                *event,
-								  gchar                   *path_string,
-								  GdkRectangle            *background_area,
-								  GdkRectangle            *cell_area,
-								  guint                    flags);
 gboolean                gtk_tree_view_column_cell_focus          (GtkTreeViewColumn       *tree_column,
 								  gint                     direction);
 void                    gtk_tree_view_column_cell_draw_focus     (GtkTreeViewColumn       *tree_column,
diff --git a/tests/testtreeflow.c b/tests/testtreeflow.c
index d036f8cced..a47d507a91 100644
--- a/tests/testtreeflow.c
+++ b/tests/testtreeflow.c
@@ -60,11 +60,11 @@ futz_row (void)
     {
     case 0:
       /* insert */
-      gtk_list_store_insert_after (GTK_LIST_STORE (model),
-				   &iter2, &iter);
-      gtk_list_store_set (GTK_LIST_STORE (model), &iter2,
-			  TEXT_COLUMN, words[g_rand_int_range (rand, 0, NUM_WORDS)],
-			  -1);
+            gtk_list_store_insert_after (GTK_LIST_STORE (model),
+            				   &iter2, &iter);
+            gtk_list_store_set (GTK_LIST_STORE (model), &iter2,
+            			  TEXT_COLUMN, words[g_rand_int_range (rand, 0, NUM_WORDS)],
+            			  -1);
       break;
     case 1:
       /* delete */
@@ -77,8 +77,8 @@ futz_row (void)
       if (gtk_tree_model_iter_n_children (model, NULL) == 0)
 	return;
       gtk_list_store_set (GTK_LIST_STORE (model), &iter,
-			  TEXT_COLUMN, words[g_rand_int_range (rand, 0, NUM_WORDS)],
-			  -1);
+      			  TEXT_COLUMN, words[g_rand_int_range (rand, 0, NUM_WORDS)],
+      			  -1);
       break;
     }
 }