diff options
| author | Benjamin Otte <otte@redhat.com> | 2011-11-21 21:13:53 +0100 |
|---|---|---|
| committer | Benjamin Otte <otte@redhat.com> | 2011-11-21 22:33:46 +0100 |
| commit | 647c441e2672e35ef92d697dabd90c372d2402cb (patch) | |
| tree | 08c87b24b76fb55005ec7ef40f3da6c770bf7e35 /gtk/gtkrbtree.c | |
| parent | f4fe921a174897844ec7f2896597f60b0a206903 (diff) | |
| download | gtk+-647c441e2672e35ef92d697dabd90c372d2402cb.tar.gz | |
rbtree: Don't write to nil node
The code used to set nil->parent, which could cause segfaults. Don't do
that. We also need to pass the parent explicitly to the fixup code,
because the node during fixup may be the nil node.
Diffstat (limited to 'gtk/gtkrbtree.c')
| -rw-r--r-- | gtk/gtkrbtree.c | 21 |
1 files changed, 10 insertions, 11 deletions
diff --git a/gtk/gtkrbtree.c b/gtk/gtkrbtree.c index 1b6f0298be..c9ad44585c 100644 --- a/gtk/gtkrbtree.c +++ b/gtk/gtkrbtree.c @@ -31,7 +31,8 @@ static void _gtk_rbnode_rotate_right (GtkRBTree *tree, static void _gtk_rbtree_insert_fixup (GtkRBTree *tree, GtkRBNode *node); static void _gtk_rbtree_remove_node_fixup (GtkRBTree *tree, - GtkRBNode *node); + GtkRBNode *node, + GtkRBNode *parent); static inline void _fixup_validation (GtkRBTree *tree, GtkRBNode *node); static inline void _fixup_total_count (GtkRBTree *tree, @@ -264,10 +265,9 @@ _gtk_rbtree_insert_fixup (GtkRBTree *tree, static void _gtk_rbtree_remove_node_fixup (GtkRBTree *tree, - GtkRBNode *node) + GtkRBNode *node, + GtkRBNode *parent) { - GtkRBNode *parent = node->parent; - while (node != tree->root && GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK) { if (node == parent->left) @@ -1184,7 +1184,8 @@ _gtk_rbtree_remove_node (GtkRBTree *tree, x = y->right; /* remove y from the parent chain */ - x->parent = y->parent; + if (x != tree->nil) + x->parent = y->parent; if (y->parent != tree->nil) { if (y == y->parent->left) @@ -1201,6 +1202,9 @@ _gtk_rbtree_remove_node (GtkRBTree *tree, */ gtk_rbnode_adjust (tree, y, -1, - y_total_count, - y_height); + if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK) + _gtk_rbtree_remove_node_fixup (tree, x, y->parent); + if (y != node) { gint node_height, node_total_count; @@ -1215,10 +1219,7 @@ _gtk_rbtree_remove_node (GtkRBTree *tree, /* 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->flags ^= (GTK_RBNODE_BLACK | GTK_RBNODE_RED); y->left = node->left; if (y->left != tree->nil) @@ -1248,8 +1249,6 @@ _gtk_rbtree_remove_node (GtkRBTree *tree, y_height - node_height); } - if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK) - _gtk_rbtree_remove_node_fixup (tree, x); _gtk_rbnode_free (node); #ifdef G_ENABLE_DEBUG |