[gtk+] rbtree: Move to an approach where we don't move contents

[Benjamin Otte <otte src gnome org>]

commit 02671f9ec9388276571a51ce9fbeb30b030bb1f7
Author: Benjamin Otte <otte redhat com>
Date:   Mon Nov 21 16:07:52 2011 +0100

    rbtree: Move to an approach where we don't move contents
    
    So instead of copying the children and height to the new node, we keep
    the old node and copy all the old stuff to it.
    
    This is necessary so the accessibility code can use the node as a key in
    the hash table or store the node as a reference to the row instead of
    GtkTreeRowReference. And because it already does that (oops), this fixes
    a bunch of segfaults with a11y enabled.

 gtk/gtkrbtree.c |   67 ++++++++++++++++++++++++++++++++++--------------------
 1 files changed, 42 insertions(+), 25 deletions(-)
---
diff --git a/gtk/gtkrbtree.c b/gtk/gtkrbtree.c
index b8f9122..d327268 100644
--- a/gtk/gtkrbtree.c
+++ b/gtk/gtkrbtree.c
@@ -1199,37 +1199,54 @@ _gtk_rbtree_remove_node (GtkRBTree *tree,
 
   if (y != node)
     {
-      gint count_diff, height_diff;
+      gint node_height, node_total_count;
 
-      /* 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.
+      /* We want to see how much we remove from the aggregate values.
+       * This is all the children we remove plus the node's values.
        */
-      height_diff = y_height 
-                    - GTK_RBNODE_GET_HEIGHT (node)
-                    - (node->children ? node->children->root->offset : 0);
-      count_diff = y->total_count - node->total_count;
-
-      /* Copy the node over */
-      if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
-	node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_BLACK);
-      else
-	node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_RED);
-      if (y->children)
-	{
-	  node->children = y->children;
-	  node->children->parent_node = node;
-	}
+      node_height = GTK_RBNODE_GET_HEIGHT (node)
+                    + (node->children ? node->children->root->offset : 0);
+      node_total_count = 1
+                         + (node->children ? node->children->root->total_count : 0);
+
+      /* Move the node over */
+      if (GTK_RBNODE_GET_COLOR (node) != GTK_RBNODE_GET_COLOR (y))
+        {
+	  node->flags ^= (GTK_RBNODE_BLACK | GTK_RBNODE_RED);
+	  y->flags ^= (GTK_RBNODE_BLACK | GTK_RBNODE_RED);
+        }
+
+      y->left = node->left;
+      if (y->left != tree->nil)
+        y->left->parent = y;
+      y->right = node->right;
+      if (y->right != tree->nil)
+        y->right->parent = y;
+      y->parent = node->parent;
+      if (y->parent != tree->nil)
+        {
+          if (y->parent->left == node)
+            y->parent->left = y;
+          else
+            y->parent->right = y;
+        }
       else
-	{
-	  node->children = NULL;
-	}
+        {
+          tree->root = y;
+        }
+      y->count = node->count;
+      y->total_count = node->total_count;
+      y->offset = node->offset;
 
-      gtk_rbnode_adjust (tree, node, 0, count_diff, height_diff);
+      gtk_rbnode_adjust (tree, y, 
+                         0,
+                         y_total_count - node_total_count,
+                         y_height - node_height);
     }
 
-  if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
+  if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
     _gtk_rbtree_remove_node_fixup (tree, x);
-  _gtk_rbnode_free (y);
+  _gtk_rbnode_free (node);
 
 #ifdef G_ENABLE_DEBUG  
   if (gtk_get_debug_flags () & GTK_DEBUG_TREE)