From 889d64b46e877f72392d04e468a7b5cb69f71a74 Mon Sep 17 00:00:00 2001 From: Jonathan Blandford Date: Thu, 25 Oct 2001 20:32:40 +0000 Subject: Add support for invalid nodes. (_gtk_rbnode_rotate_right): Ditto. Thu Oct 25 16:27:29 2001 Jonathan Blandford * gtk/gtkrbtree.c (_gtk_rbnode_rotate_left): Add support for invalid nodes. (_gtk_rbnode_rotate_right): Ditto. (_gtk_rbtree_node_mark_invalid): New function. (_gtk_rbtree_node_mark_valid): New function. * gtk/gtktreemodelsort.c (gtk_tree_model_sort_class_init): We're a GObject, not a GtkObject. (gtk_tree_model_sort_row_has_child_toggled): Rewrote to be more correct. (gtk_tree_model_sort_row_deleted): ditto. (gtk_tree_model_sort_{un,}ref_node): Fix. * gtk/gtktreeview.c: Protean incremental reflow support (commented out) * gtk/gtktreeview.h (GtkTreeViewSearchEqualFunc): change char *key to const char *key. * gtk/gtktreemodel.c (gtk_tree_row_reference_unref_path_helper): Important 1 line fix to fix a lot of refcounting woes. --- gtk/gtkrbtree.c | 86 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 85 insertions(+), 1 deletion(-) (limited to 'gtk/gtkrbtree.c') diff --git a/gtk/gtkrbtree.c b/gtk/gtkrbtree.c index 86690ea918..c07d6b4527 100644 --- a/gtk/gtkrbtree.c +++ b/gtk/gtkrbtree.c @@ -26,7 +26,7 @@ static GtkRBNode *_gtk_rbnode_new (GtkRBTree *tree, static void _gtk_rbnode_free (GtkRBNode *node); static void _gtk_rbnode_rotate_left (GtkRBTree *tree, GtkRBNode *node); -static void _gtk_rbnode_rotate_left (GtkRBTree *tree, +static void _gtk_rbnode_rotate_right (GtkRBTree *tree, GtkRBNode *node); static void _gtk_rbtree_insert_fixup (GtkRBTree *tree, GtkRBNode *node); @@ -207,6 +207,23 @@ _gtk_rbnode_rotate_left (GtkRBTree *tree, (right->left?right->left->parity:0) + (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); + } } static void @@ -282,6 +299,23 @@ _gtk_rbnode_rotate_right (GtkRBTree *tree, (left->left?left->left->parity:0) + (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); + } } static void @@ -714,6 +748,56 @@ _gtk_rbtree_node_set_height (GtkRBTree *tree, } } +void +_gtk_rbtree_node_mark_invalid (GtkRBTree *tree, + GtkRBNode *node) +{ + if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) + return; + + GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID); + do + { + if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID)) + return; + GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID); + node = node->parent; + if (node == NULL) + { + node = tree->parent_node; + tree = tree->parent_tree; + } + } + while (node); +} + +void +_gtk_rbtree_node_mark_valid (GtkRBTree *tree, + GtkRBNode *node) +{ + if (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) + return; + + GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID); + do + { + if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) || + (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)) || + (node->left && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) || + (node->right && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID))) + return; + + GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID); + node = node->parent; + if (node == NULL) + { + node = tree->parent_node; + tree = tree->parent_tree; + } + } + while (node); +} + typedef struct _GtkRBReorder { GtkRBTree *children; -- cgit v1.2.1