[gtk+] rbtree: Move to an approach where we don't move contents
- From: Benjamin Otte <otte src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk+] rbtree: Move to an approach where we don't move contents
- Date: Mon, 21 Nov 2011 21:36:52 +0000 (UTC)
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)
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]