X-Git-Url: http://pileus.org/git/?a=blobdiff_plain;f=gtk%2Fgtkrbtree.c;h=d3e1fef7a61b37624aac786e780daa1db567e56d;hb=e09957a47da9425cc26d1b33cb4e9cc3e92e9ac7;hp=9b0aaf5047b38787fc37957590a909cb5a659d99;hpb=050625298e15a57543ffefcce79ef2bf8edcc184;p=~andy%2Fgtk diff --git a/gtk/gtkrbtree.c b/gtk/gtkrbtree.c index 9b0aaf504..d3e1fef7a 100644 --- a/gtk/gtkrbtree.c +++ b/gtk/gtkrbtree.c @@ -12,105 +12,58 @@ * Library General Public License for more details. * * You should have received a copy of the GNU Library General Public - * License along with this library; if not, write to the - * Free Software Foundation, Inc., 59 Temple Place - Suite 330, - * Boston, MA 02111-1307, USA. + * License along with this library. If not, see . */ +#include "config.h" #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); - - -/* node allocation - */ -struct _GAllocator /* from gmem.c */ -{ - gchar *name; - guint16 n_preallocs; - guint is_unused : 1; - guint type : 4; - GAllocator *last; - GMemChunk *mem_chunk; - GtkRBNode *free_nodes; /* implementation specific */ +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, + GtkRBNode *parent); +static inline void _fixup_validation (GtkRBTree *tree, + GtkRBNode *node); +static inline void _fixup_total_count (GtkRBTree *tree, + GtkRBNode *node); +#ifdef G_ENABLE_DEBUG +static void _gtk_rbtree_test (const gchar *where, + GtkRBTree *tree); +static void _gtk_rbtree_debug_spew (GtkRBTree *tree); +#endif + +static const GtkRBNode nil = { + /* .flags = */ GTK_RBNODE_BLACK, + + /* rest is NULL */ }; - -G_LOCK_DEFINE_STATIC (current_allocator); -static GAllocator *current_allocator = NULL; - -/* HOLDS: current_allocator_lock */ -static void -_gtk_rbnode_validate_allocator (GAllocator *allocator) +gboolean +_gtk_rbtree_is_nil (GtkRBNode *node) { - g_return_if_fail (allocator != NULL); - g_return_if_fail (allocator->is_unused == TRUE); - - if (allocator->type != G_ALLOCATOR_NODE) - { - allocator->type = G_ALLOCATOR_NODE; - if (allocator->mem_chunk) - { - g_mem_chunk_destroy (allocator->mem_chunk); - allocator->mem_chunk = NULL; - } - } - - if (!allocator->mem_chunk) - { - allocator->mem_chunk = g_mem_chunk_new (allocator->name, - sizeof (GtkRBNode), - sizeof (GtkRBNode) * allocator->n_preallocs, - G_ALLOC_ONLY); - allocator->free_nodes = NULL; - } - - allocator->is_unused = FALSE; + return node == &nil; } static GtkRBNode * _gtk_rbnode_new (GtkRBTree *tree, gint height) { - GtkRBNode *node; + GtkRBNode *node = g_slice_new (GtkRBNode); - G_LOCK (current_allocator); - if (!current_allocator) - { - GAllocator *allocator = g_allocator_new ("GTK+ default GtkRBNode allocator", - 128); - _gtk_rbnode_validate_allocator (allocator); - allocator->last = NULL; - current_allocator = allocator; - } - if (!current_allocator->free_nodes) - node = g_chunk_new (GtkRBNode, current_allocator->mem_chunk); - else - { - node = current_allocator->free_nodes; - current_allocator->free_nodes = node->left; - } - G_UNLOCK (current_allocator); - - node->left = tree->nil; - node->right = tree->nil; - node->parent = tree->nil; + node->left = (GtkRBNode *) &nil; + node->right = (GtkRBNode *) &nil; + node->parent = (GtkRBNode *) &nil; node->flags = GTK_RBNODE_RED; - node->parity = 1; + node->total_count = 1; node->count = 1; node->children = NULL; node->offset = height; @@ -120,21 +73,19 @@ _gtk_rbnode_new (GtkRBTree *tree, static void _gtk_rbnode_free (GtkRBNode *node) { - G_LOCK (current_allocator); - node->left = current_allocator->free_nodes; - current_allocator->free_nodes = node; - if (gtk_debug_flags & GTK_DEBUG_TREE) +#ifdef G_ENABLE_DEBUG + if (gtk_get_debug_flags () & GTK_DEBUG_TREE) { - /* unfortunately node->left has to continue to point to - * a node... - */ + node->left = (gpointer) 0xdeadbeef; node->right = (gpointer) 0xdeadbeef; node->parent = (gpointer) 0xdeadbeef; + node->total_count = 56789; node->offset = 56789; node->count = 56789; node->flags = 0; } - G_UNLOCK (current_allocator); +#endif + g_slice_free (GtkRBNode, node); } static void @@ -142,36 +93,21 @@ _gtk_rbnode_rotate_left (GtkRBTree *tree, GtkRBNode *node) { gint node_height, right_height; - guint node_parity, right_parity; - GtkRBNode *right = node->right; - - g_return_if_fail (node != tree->nil); - - node_height = node->offset - - (node->left?node->left->offset:0) - - (node->right?node->right->offset:0) - - (node->children?node->children->root->offset:0); - right_height = right->offset - - (right->left?right->left->offset:0) - - (right->right?right->right->offset:0) - - (right->children?right->children->root->offset:0); - - node_parity = node->parity - - (node->left?node->left->parity:0) - - (node->right?node->right->parity:0) - - (node->children?node->children->root->parity:0); - right_parity = right->parity - - (right->left?right->left->parity:0) - - (right->right?right->right->parity:0) - - (right->children?right->children->root->parity:0); - + GtkRBNode *right; + + g_return_if_fail (!_gtk_rbtree_is_nil (node)); + g_return_if_fail (!_gtk_rbtree_is_nil (node->right)); + + right = node->right; + + node_height = GTK_RBNODE_GET_HEIGHT (node); + right_height = GTK_RBNODE_GET_HEIGHT (right); node->right = right->left; - if (right->left != tree->nil) + if (!_gtk_rbtree_is_nil (right->left)) right->left->parent = node; - if (right != tree->nil) - right->parent = node->parent; - if (node->parent != tree->nil) + right->parent = node->parent; + if (!_gtk_rbtree_is_nil (node->parent)) { if (node == node->parent->left) node->parent->left = right; @@ -182,48 +118,20 @@ _gtk_rbnode_rotate_left (GtkRBTree *tree, } right->left = node; - if (node != tree->nil) - node->parent = right; - - node->count = 1 + (node->left?node->left->count:0) + - (node->right?node->right->count:0); - right->count = 1 + (right->left?right->left->count:0) + - (right->right?right->right->count:0); - - node->offset = node_height + - (node->left?node->left->offset:0) + - (node->right?node->right->offset:0) + - (node->children?node->children->root->offset:0); - right->offset = right_height + - (right->left?right->left->offset:0) + - (right->right?right->right->offset:0) + - (right->children?right->children->root->offset:0); - - node->parity = node_parity + - (node->left?node->left->parity:0) + - (node->right?node->right->parity:0) + - (node->children?node->children->root->parity:0); - right->parity = right_parity + - (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); - } + node->parent = right; + + node->count = 1 + node->left->count + node->right->count; + right->count = 1 + right->left->count + right->right->count; + + node->offset = node_height + node->left->offset + node->right->offset + + (node->children ? node->children->root->offset : 0); + right->offset = right_height + right->left->offset + right->right->offset + + (right->children ? right->children->root->offset : 0); + + _fixup_validation (tree, node); + _fixup_validation (tree, right); + _fixup_total_count (tree, node); + _fixup_total_count (tree, right); } static void @@ -231,36 +139,22 @@ _gtk_rbnode_rotate_right (GtkRBTree *tree, GtkRBNode *node) { gint node_height, left_height; - guint node_parity, left_parity; - GtkRBNode *left = node->left; - - g_return_if_fail (node != tree->nil); - - node_height = node->offset - - (node->left?node->left->offset:0) - - (node->right?node->right->offset:0) - - (node->children?node->children->root->offset:0); - left_height = left->offset - - (left->left?left->left->offset:0) - - (left->right?left->right->offset:0) - - (left->children?left->children->root->offset:0); - - node_parity = node->parity - - (node->left?node->left->parity:0) - - (node->right?node->right->parity:0) - - (node->children?node->children->root->parity:0); - left_parity = left->parity - - (left->left?left->left->parity:0) - - (left->right?left->right->parity:0) - - (left->children?left->children->root->parity:0); + GtkRBNode *left; + + g_return_if_fail (!_gtk_rbtree_is_nil (node)); + g_return_if_fail (!_gtk_rbtree_is_nil (node->left)); + + left = node->left; + + node_height = GTK_RBNODE_GET_HEIGHT (node); + left_height = GTK_RBNODE_GET_HEIGHT (left); node->left = left->right; - if (left->right != tree->nil) + if (!_gtk_rbtree_is_nil (left->right)) left->right->parent = node; - if (left != tree->nil) - left->parent = node->parent; - if (node->parent != tree->nil) + left->parent = node->parent; + if (!_gtk_rbtree_is_nil (node->parent)) { if (node == node->parent->right) node->parent->right = left; @@ -274,48 +168,20 @@ _gtk_rbnode_rotate_right (GtkRBTree *tree, /* link node and left */ left->right = node; - if (node != tree->nil) - node->parent = left; - - node->count = 1 + (node->left?node->left->count:0) + - (node->right?node->right->count:0); - left->count = 1 + (left->left?left->left->count:0) + - (left->right?left->right->count:0); - - node->offset = node_height + - (node->left?node->left->offset:0) + - (node->right?node->right->offset:0) + - (node->children?node->children->root->offset:0); - left->offset = left_height + - (left->left?left->left->offset:0) + - (left->right?left->right->offset:0) + - (left->children?left->children->root->offset:0); - - node->parity = node_parity + - (node->left?node->left->parity:0) + - (node->right?node->right->parity:0) + - (node->children?node->children->root->parity:0); - left->parity = left_parity + - (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); - } + node->parent = left; + + node->count = 1 + node->left->count + node->right->count; + left->count = 1 + left->left->count + left->right->count; + + node->offset = node_height + node->left->offset + node->right->offset + + (node->children ? node->children->root->offset : 0); + left->offset = left_height + left->left->offset + left->right->offset + + (left->children?left->children->root->offset:0); + + _fixup_validation (tree, node); + _fixup_validation (tree, left); + _fixup_total_count (tree, node); + _fixup_total_count (tree, left); } static void @@ -385,24 +251,25 @@ _gtk_rbtree_insert_fixup (GtkRBTree *tree, static void _gtk_rbtree_remove_node_fixup (GtkRBTree *tree, - GtkRBNode *node) + GtkRBNode *node, + GtkRBNode *parent) { while (node != tree->root && GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK) { - if (node == node->parent->left) + if (node == parent->left) { - GtkRBNode *w = node->parent->right; + GtkRBNode *w = parent->right; if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED) { GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK); - GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED); - _gtk_rbnode_rotate_left (tree, node->parent); - w = node->parent->right; + GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_RED); + _gtk_rbnode_rotate_left (tree, parent); + w = parent->right; } if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK) { GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED); - node = node->parent; + node = parent; } else { @@ -411,29 +278,29 @@ _gtk_rbtree_remove_node_fixup (GtkRBTree *tree, GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK); GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED); _gtk_rbnode_rotate_right (tree, w); - w = node->parent->right; + w = parent->right; } - GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent)); - GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK); + GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (parent)); + GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_BLACK); GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK); - _gtk_rbnode_rotate_left (tree, node->parent); + _gtk_rbnode_rotate_left (tree, parent); node = tree->root; } } else { - GtkRBNode *w = node->parent->left; + GtkRBNode *w = parent->left; if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED) { GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK); - GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED); - _gtk_rbnode_rotate_right (tree, node->parent); - w = node->parent->left; + GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_RED); + _gtk_rbnode_rotate_right (tree, parent); + w = parent->left; } if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK) { GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED); - node = node->parent; + node = parent; } else { @@ -442,44 +309,19 @@ _gtk_rbtree_remove_node_fixup (GtkRBTree *tree, GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK); GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED); _gtk_rbnode_rotate_left (tree, w); - w = node->parent->left; + w = parent->left; } - GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent)); - GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK); + GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (parent)); + GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_BLACK); GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK); - _gtk_rbnode_rotate_right (tree, node->parent); + _gtk_rbnode_rotate_right (tree, parent); node = tree->root; } } - } - GTK_RBNODE_SET_COLOR (node, GTK_RBNODE_BLACK); -} - -/* Public functions */ -void -_gtk_rbnode_push_allocator (GAllocator *allocator) -{ - G_LOCK (current_allocator); - _gtk_rbnode_validate_allocator ( allocator ); - allocator->last = current_allocator; - current_allocator = allocator; - G_UNLOCK (current_allocator); -} - -void -_gtk_rbnode_pop_allocator (void) -{ - G_LOCK (current_allocator); - if (current_allocator) - { - GAllocator *allocator; - allocator = current_allocator; - current_allocator = allocator->last; - allocator->last = NULL; - allocator->is_unused = TRUE; + parent = node->parent; } - G_UNLOCK (current_allocator); + GTK_RBNODE_SET_COLOR (node, GTK_RBNODE_BLACK); } GtkRBTree * @@ -487,20 +329,12 @@ _gtk_rbtree_new (void) { GtkRBTree *retval; - retval = (GtkRBTree *) g_new (GtkRBTree, 1); + retval = g_new (GtkRBTree, 1); retval->parent_tree = NULL; retval->parent_node = NULL; - retval->nil = g_new0 (GtkRBNode, 1); - retval->nil->left = NULL; - retval->nil->right = NULL; - retval->nil->parent = NULL; - retval->nil->flags = GTK_RBNODE_BLACK; - retval->nil->count = 0; - retval->nil->offset = 0; - retval->nil->parity = 0; + retval->root = (GtkRBNode *) &nil; - retval->root = retval->nil; return retval; } @@ -527,177 +361,197 @@ _gtk_rbtree_free (GtkRBTree *tree) if (tree->parent_node && tree->parent_node->children == tree) tree->parent_node->children = NULL; - _gtk_rbnode_free (tree->nil); g_free (tree); } +static void +gtk_rbnode_adjust (GtkRBTree *tree, + GtkRBNode *node, + int count_diff, + int total_count_diff, + int offset_diff) +{ + while (tree && node && !_gtk_rbtree_is_nil (node)) + { + _fixup_validation (tree, node); + node->offset += offset_diff; + node->count += count_diff; + node->total_count += total_count_diff; + + node = node->parent; + if (_gtk_rbtree_is_nil (node)) + { + node = tree->parent_node; + tree = tree->parent_tree; + count_diff = 0; + } + } +} + void _gtk_rbtree_remove (GtkRBTree *tree) { +#ifdef G_ENABLE_DEBUG GtkRBTree *tmp_tree; - GtkRBNode *tmp_node; - gint height = tree->root->offset; - - if (gtk_debug_flags & GTK_DEBUG_TREE) + if (gtk_get_debug_flags () & GTK_DEBUG_TREE) _gtk_rbtree_test (G_STRLOC, tree); +#endif - tmp_tree = tree->parent_tree; - tmp_node = tree->parent_node; - - while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil) - { - tmp_node->offset -= height; - - /* If the removed tree was odd, flip all parents */ - if (tree->root->parity) - tmp_node->parity = !tmp_node->parity; - - tmp_node = tmp_node->parent; - if (tmp_node == tmp_tree->nil) - { - tmp_node = tmp_tree->parent_node; - tmp_tree = tmp_tree->parent_tree; - } - } + /* 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); + + gtk_rbnode_adjust (tree->parent_tree, + tree->parent_node, + 0, + - (int) tree->root->total_count, + - tree->root->offset); +#ifdef G_ENABLE_DEBUG tmp_tree = tree->parent_tree; - tmp_node = tree->parent_node; +#endif + _gtk_rbtree_free (tree); - if (gtk_debug_flags & GTK_DEBUG_TREE) +#ifdef G_ENABLE_DEBUG + if (gtk_get_debug_flags () & GTK_DEBUG_TREE) _gtk_rbtree_test (G_STRLOC, tmp_tree); +#endif } GtkRBNode * -_gtk_rbtree_insert_after (GtkRBTree *tree, - GtkRBNode *current, - gint height) +_gtk_rbtree_insert_after (GtkRBTree *tree, + GtkRBNode *current, + gint height, + gboolean valid) { GtkRBNode *node; gboolean right = TRUE; - 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) +#ifdef G_ENABLE_DEBUG + if (gtk_get_debug_flags () & GTK_DEBUG_TREE) + { + g_print ("\n\n_gtk_rbtree_insert_after: %p\n", current); + _gtk_rbtree_debug_spew (tree); + _gtk_rbtree_test (G_STRLOC, tree); + } +#endif /* G_ENABLE_DEBUG */ + + if (current != NULL && !_gtk_rbtree_is_nil (current->right)) { current = current->right; - while (current->left != tree->nil) + while (!_gtk_rbtree_is_nil (current->left)) current = current->left; right = FALSE; } - /* setup new node */ node = _gtk_rbnode_new (tree, height); - node->parent = (current?current:tree->nil); /* insert node in tree */ if (current) { + node->parent = current; if (right) current->right = node; else current->left = node; - tmp_node = node->parent; - tmp_tree = tree; + gtk_rbnode_adjust (tree, node->parent, + 1, 1, height); } else { + g_assert (_gtk_rbtree_is_nil (tree->root)); tree->root = node; - tmp_node = tree->parent_node; - tmp_tree = tree->parent_tree; + gtk_rbnode_adjust (tree->parent_tree, tree->parent_node, + 0, 1, height); } - while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil) - { - /* We only want to propagate the count if we are in the tree we - * started in. */ - if (tmp_tree == tree) - tmp_node->count++; + if (valid) + _gtk_rbtree_node_mark_valid (tree, node); + else + _gtk_rbtree_node_mark_invalid (tree, node); - tmp_node->parity += 1; - tmp_node->offset += height; - tmp_node = tmp_node->parent; - if (tmp_node == tmp_tree->nil) - { - tmp_node = tmp_tree->parent_node; - 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); - +#ifdef G_ENABLE_DEBUG + if (gtk_get_debug_flags () & GTK_DEBUG_TREE) + { + g_print ("_gtk_rbtree_insert_after finished...\n"); + _gtk_rbtree_debug_spew (tree); + g_print ("\n\n"); + _gtk_rbtree_test (G_STRLOC, tree); + } +#endif /* G_ENABLE_DEBUG */ + return node; } GtkRBNode * -_gtk_rbtree_insert_before (GtkRBTree *tree, - GtkRBNode *current, - gint height) +_gtk_rbtree_insert_before (GtkRBTree *tree, + GtkRBNode *current, + gint height, + gboolean valid) { GtkRBNode *node; gboolean left = TRUE; - GtkRBNode *tmp_node; - GtkRBTree *tmp_tree; - if (gtk_debug_flags & GTK_DEBUG_TREE) - _gtk_rbtree_test (G_STRLOC, tree); +#ifdef G_ENABLE_DEBUG + if (gtk_get_debug_flags () & GTK_DEBUG_TREE) + { + g_print ("\n\n_gtk_rbtree_insert_before: %p\n", current); + _gtk_rbtree_debug_spew (tree); + _gtk_rbtree_test (G_STRLOC, tree); + } +#endif /* G_ENABLE_DEBUG */ - if (current != NULL && current->left != tree->nil) + if (current != NULL && !_gtk_rbtree_is_nil (current->left)) { current = current->left; - while (current->right != tree->nil) + while (!_gtk_rbtree_is_nil (current->right)) current = current->right; left = FALSE; } /* setup new node */ node = _gtk_rbnode_new (tree, height); - node->parent = (current?current:tree->nil); /* insert node in tree */ if (current) { + node->parent = current; if (left) current->left = node; else current->right = node; - tmp_node = node->parent; - tmp_tree = tree; + gtk_rbnode_adjust (tree, node->parent, + 1, 1, height); } else { + g_assert (_gtk_rbtree_is_nil (tree->root)); tree->root = node; - tmp_node = tree->parent_node; - tmp_tree = tree->parent_tree; + gtk_rbnode_adjust (tree->parent_tree, tree->parent_node, + 0, 1, height); } - while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil) - { - /* We only want to propagate the count if we are in the tree we - * started in. */ - if (tmp_tree == tree) - tmp_node->count++; + if (valid) + _gtk_rbtree_node_mark_valid (tree, node); + else + _gtk_rbtree_node_mark_invalid (tree, node); - tmp_node->parity += 1; - tmp_node->offset += height; - tmp_node = tmp_node->parent; - if (tmp_node == tmp_tree->nil) - { - tmp_node = tmp_tree->parent_node; - 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); +#ifdef G_ENABLE_DEBUG + if (gtk_get_debug_flags () & GTK_DEBUG_TREE) + { + g_print ("_gtk_rbtree_insert_before finished...\n"); + _gtk_rbtree_debug_spew (tree); + g_print ("\n\n"); + _gtk_rbtree_test (G_STRLOC, tree); + } +#endif /* G_ENABLE_DEBUG */ return node; } @@ -709,7 +563,7 @@ _gtk_rbtree_find_count (GtkRBTree *tree, GtkRBNode *node; node = tree->root; - while (node != tree->nil && (node->left->count + 1 != count)) + while (!_gtk_rbtree_is_nil (node) && (node->left->count + 1 != count)) { if (node->left->count >= count) node = node->left; @@ -719,7 +573,7 @@ _gtk_rbtree_find_count (GtkRBTree *tree, node = node->right; } } - if (node == tree->nil) + if (_gtk_rbtree_is_nil (node)) return NULL; return node; } @@ -730,22 +584,16 @@ _gtk_rbtree_node_set_height (GtkRBTree *tree, gint height) { gint diff = height - GTK_RBNODE_GET_HEIGHT (node); - GtkRBNode *tmp_node = node; - GtkRBTree *tmp_tree = tree; if (diff == 0) return; - while (tmp_tree && tmp_node && 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; - } - } + gtk_rbnode_adjust (tree, node, 0, 0, diff); + +#ifdef G_ENABLE_DEBUG + if (gtk_get_debug_flags () & GTK_DEBUG_TREE) + _gtk_rbtree_test (G_STRLOC, tree); +#endif } void @@ -762,7 +610,27 @@ _gtk_rbtree_node_mark_invalid (GtkRBTree *tree, return; GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID); node = node->parent; - if (node == NULL) + if (_gtk_rbtree_is_nil (node)) + { + node = tree->parent_node; + tree = tree->parent_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 (_gtk_rbtree_is_nil (node)) { node = tree->parent_node; tree = tree->parent_tree; @@ -770,26 +638,31 @@ _gtk_rbtree_node_mark_invalid (GtkRBTree *tree, } while (node); } +#endif void _gtk_rbtree_node_mark_valid (GtkRBTree *tree, GtkRBNode *node) { - if (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) + if ((!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) && + (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))) return; GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID); + GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID); + do { - if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) || + if ((GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) || + (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_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))) + (GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) || + (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) + if (_gtk_rbtree_is_nil (node)) { node = tree->parent_node; tree = tree->parent_tree; @@ -798,57 +671,142 @@ _gtk_rbtree_node_mark_valid (GtkRBTree *tree, while (node); } -typedef struct _GtkRBReorder -{ - GtkRBTree *children; - gint height; - gint flags; - gint order; - gint invert_order; - gint parity; -} GtkRBReorder; - -static int -gtk_rbtree_reorder_sort_func (gconstpointer a, - gconstpointer b) +#if 0 +/* Draconian version */ +void +_gtk_rbtree_node_mark_valid (GtkRBTree *tree, + GtkRBNode *node) { - return ((GtkRBReorder *) a)->order > ((GtkRBReorder *) b)->order; -} + GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID); + GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID); -static int -gtk_rbtree_reorder_invert_func (gconstpointer a, - gconstpointer b) -{ - return ((GtkRBReorder *) a)->invert_order > ((GtkRBReorder *) b)->invert_order; + do + { + _fixup_validation (tree, node); + node = node->parent; + if (_gtk_rbtree_is_nil (node)) + { + node = tree->parent_node; + tree = tree->parent_tree; + } + } + while (node); } - -static void -gtk_rbtree_reorder_fixup (GtkRBTree *tree, - GtkRBNode *node) +#endif +/* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above. + */ +void +_gtk_rbtree_column_invalid (GtkRBTree *tree) { - if (node == tree->nil) + GtkRBNode *node; + + if (tree == NULL) return; - node->parity = 1; + node = _gtk_rbtree_first (tree); - if (node->left != tree->nil) + do { - gtk_rbtree_reorder_fixup (tree, node->left); - node->offset += node->left->offset; - node->parity += node->left->parity; + if (! (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))) + GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_COLUMN_INVALID); + GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID); + + if (node->children) + _gtk_rbtree_column_invalid (node->children); } - if (node->right != tree->nil) + while ((node = _gtk_rbtree_next (tree, node)) != NULL); +} + +void +_gtk_rbtree_mark_invalid (GtkRBTree *tree) +{ + GtkRBNode *node; + + if (tree == NULL) + return; + + node = _gtk_rbtree_first (tree); + + do { - gtk_rbtree_reorder_fixup (tree, node->right); - node->offset += node->right->offset; - node->parity += node->right->parity; + GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID); + GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID); + + if (node->children) + _gtk_rbtree_mark_invalid (node->children); } - - if (node->children) + while ((node = _gtk_rbtree_next (tree, node)) != NULL); +} + +void +_gtk_rbtree_set_fixed_height (GtkRBTree *tree, + gint height, + gboolean mark_valid) +{ + GtkRBNode *node; + + if (tree == NULL) + return; + + node = _gtk_rbtree_first (tree); + + do { - node->offset += node->children->root->offset; - node->parity += node->children->root->parity; + if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) + { + _gtk_rbtree_node_set_height (tree, node, height); + if (mark_valid) + _gtk_rbtree_node_mark_valid (tree, node); + } + + if (node->children) + _gtk_rbtree_set_fixed_height (node->children, height, mark_valid); } + while ((node = _gtk_rbtree_next (tree, node)) != NULL); +} + +static void +reorder_prepare (GtkRBTree *tree, + GtkRBNode *node, + gpointer data) +{ + node->offset -= node->left->offset + node->right->offset; + GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID); +} + +static void +reorder_fixup (GtkRBTree *tree, + GtkRBNode *node, + gpointer data) +{ + node->offset += node->left->offset + node->right->offset; + node->count = 1 + node->left->count + node->right->count; + _fixup_validation (tree, node); + _fixup_total_count (tree, node); +} + +static void +reorder_copy_node (GtkRBTree *tree, + GtkRBNode *to, + GtkRBNode *from) +{ + to->flags = (to->flags & GTK_RBNODE_NON_COLORS) | GTK_RBNODE_GET_COLOR (from); + + to->left = from->left; + if (!_gtk_rbtree_is_nil (to->left)) + to->left->parent = to; + + to->right = from->right; + if (!_gtk_rbtree_is_nil (to->right)) + to->right->parent = to; + + to->parent = from->parent; + if (_gtk_rbtree_is_nil (to->parent)) + tree->root = to; + else if (to->parent->left == from) + to->parent->left = to; + else if (to->parent->right == from) + to->parent->right = to; } /* It basically pulls everything out of the tree, rearranges it, and puts it @@ -862,63 +820,89 @@ _gtk_rbtree_reorder (GtkRBTree *tree, gint *new_order, gint length) { - GtkRBReorder reorder; - GArray *array; + GtkRBNode **nodes; GtkRBNode *node; - gint i; + gint i, j; g_return_if_fail (tree != NULL); g_return_if_fail (length > 0); g_return_if_fail (tree->root->count == length); - /* Sort the trees values in the new tree. */ - array = g_array_sized_new (FALSE, FALSE, sizeof (GtkRBReorder), length); - for (i = 0; i < length; i++) - { - reorder.order = new_order[i]; - reorder.invert_order = i; - g_array_append_val (array, reorder); - } - - g_array_sort(array, gtk_rbtree_reorder_sort_func); + nodes = g_new (GtkRBNode *, length); - /* rewind node*/ - node = tree->root; - while (node && node->left != tree->nil) - node = node->left; + _gtk_rbtree_traverse (tree, tree->root, G_PRE_ORDER, reorder_prepare, NULL); - for (i = 0; i < length; i++) + for (node = _gtk_rbtree_first (tree), i = 0; + node; + node = _gtk_rbtree_next (tree, node), i++) { - g_assert (node != tree->nil); - g_array_index (array, GtkRBReorder, i).children = node->children; - g_array_index (array, GtkRBReorder, i).flags = GTK_RBNODE_NON_COLORS & node->flags; - g_array_index (array, GtkRBReorder, i).height = GTK_RBNODE_GET_HEIGHT (node); - - node = _gtk_rbtree_next (tree, node); + nodes[i] = node; } - g_array_sort (array, gtk_rbtree_reorder_invert_func); - - /* rewind node*/ - node = tree->root; - while (node && node->left != tree->nil) - node = node->left; - - /* Go through the tree and change the values to the new ones. */ for (i = 0; i < length; i++) { - reorder = g_array_index (array, GtkRBReorder, i); - node->children = reorder.children; - if (node->children) - node->children->parent_node = node; - node->flags = GTK_RBNODE_GET_COLOR (node) | reorder.flags; - /* We temporarily set the height to this. */ - node->offset = reorder.height; - node = _gtk_rbtree_next (tree, node); + GtkRBNode tmp = { 0, }; + GSList *l, *cycle = NULL; + + tmp.offset = -1; + + /* already swapped */ + if (nodes[i] == NULL) + continue; + /* no need to swap */ + if (new_order[i] == i) + continue; + + /* make a list out of the pending nodes */ + for (j = i; new_order[j] != i; j = new_order[j]) + { + cycle = g_slist_prepend (cycle, nodes[j]); + nodes[j] = NULL; + } + + node = nodes[j]; + reorder_copy_node (tree, &tmp, node); + for (l = cycle; l; l = l->next) + { + reorder_copy_node (tree, node, l->data); + node = l->data; + } + + reorder_copy_node (tree, node, &tmp); + nodes[j] = NULL; + g_slist_free (cycle); } - gtk_rbtree_reorder_fixup (tree, tree->root); + + _gtk_rbtree_traverse (tree, tree->root, G_POST_ORDER, reorder_fixup, NULL); + + g_free (nodes); } +/** + * _gtk_rbtree_contains: + * @tree: a tree + * @potential_child: a potential child of @tree + * + * Checks if @potential_child is a child (direct or via intermediate + * trees) of @tree. + * + * Returns: %TRUE if @potentitial_child is a child of @tree. + **/ +gboolean +_gtk_rbtree_contains (GtkRBTree *tree, + GtkRBTree *potential_child) +{ + g_return_val_if_fail (tree != NULL, FALSE); + g_return_val_if_fail (potential_child != NULL, FALSE); + + do { + potential_child = potential_child->parent_tree; + if (potential_child == tree) + return TRUE; + } while (potential_child != NULL); + + return FALSE; +} gint _gtk_rbtree_node_find_offset (GtkRBTree *tree, @@ -932,7 +916,7 @@ _gtk_rbtree_node_find_offset (GtkRBTree *tree, retval = node->left->offset; - while (tree && node && node != tree->nil) + while (tree && node && !_gtk_rbtree_is_nil (node)) { last = node; node = node->parent; @@ -941,7 +925,7 @@ _gtk_rbtree_node_find_offset (GtkRBTree *tree, if (node->right == last) retval += node->offset - node->right->offset; - if (node == tree->nil) + if (_gtk_rbtree_is_nil (node)) { node = tree->parent_node; tree = tree->parent_tree; @@ -954,58 +938,62 @@ _gtk_rbtree_node_find_offset (GtkRBTree *tree, return retval; } -gint -_gtk_rbtree_node_find_parity (GtkRBTree *tree, - GtkRBNode *node) +guint +_gtk_rbtree_node_get_index (GtkRBTree *tree, + GtkRBNode *node) { GtkRBNode *last; - gint retval; + guint retval; g_assert (node); g_assert (node->left); - retval = node->left->parity; + retval = node->left->total_count; - while (tree && node && node != tree->nil) + while (tree && node && !_gtk_rbtree_is_nil (node)) { last = node; node = node->parent; /* Add left branch, plus children, iff we came from the right */ if (node->right == last) - retval += node->parity - node->right->parity; + retval += node->total_count - node->right->total_count; - if (node == tree->nil) + if (_gtk_rbtree_is_nil (node)) { node = tree->parent_node; tree = tree->parent_tree; /* Add the parent node, plus the left branch. */ if (node) - retval += node->left->parity + 1; /* 1 == GTK_RBNODE_GET_PARITY() */ + retval += node->left->total_count + 1; /* 1 == GTK_RBNODE_GET_PARITY() */ } } - return retval % 2; + return retval; } -gint -_gtk_rbtree_find_offset (GtkRBTree *tree, - gint height, - GtkRBTree **new_tree, - GtkRBNode **new_node) +static gint +gtk_rbtree_real_find_offset (GtkRBTree *tree, + gint height, + GtkRBTree **new_tree, + GtkRBNode **new_node) { GtkRBNode *tmp_node; + g_assert (tree); + if (height < 0) { *new_tree = NULL; *new_node = NULL; + return 0; } + tmp_node = tree->root; - while (tmp_node != tree->nil && + while (!_gtk_rbtree_is_nil (tmp_node) && (tmp_node->left->offset > height || (tmp_node->offset - tmp_node->right->offset) < height)) { @@ -1017,7 +1005,7 @@ _gtk_rbtree_find_offset (GtkRBTree *tree, tmp_node = tmp_node->right; } } - if (tmp_node == tree->nil) + if (_gtk_rbtree_is_nil (tmp_node)) { *new_tree = NULL; *new_node = NULL; @@ -1033,44 +1021,122 @@ _gtk_rbtree_find_offset (GtkRBTree *tree, *new_node = tmp_node; return (height - tmp_node->left->offset); } - return _gtk_rbtree_find_offset (tmp_node->children, - height - tmp_node->left->offset - - (tmp_node->offset - - tmp_node->left->offset - - tmp_node->right->offset - - tmp_node->children->root->offset), - new_tree, - new_node); + return gtk_rbtree_real_find_offset (tmp_node->children, + height - tmp_node->left->offset - + (tmp_node->offset - + tmp_node->left->offset - + tmp_node->right->offset - + tmp_node->children->root->offset), + new_tree, + new_node); } *new_tree = tree; *new_node = tmp_node; return (height - tmp_node->left->offset); } +gint +_gtk_rbtree_find_offset (GtkRBTree *tree, + gint height, + GtkRBTree **new_tree, + GtkRBNode **new_node) +{ + g_assert (tree); + + if ((height < 0) || + (height >= tree->root->offset)) + { + *new_tree = NULL; + *new_node = NULL; + + return 0; + } + return gtk_rbtree_real_find_offset (tree, height, new_tree, new_node); +} + +gboolean +_gtk_rbtree_find_index (GtkRBTree *tree, + guint index, + GtkRBTree **new_tree, + GtkRBNode **new_node) +{ + GtkRBNode *tmp_node; + + g_assert (tree); + + tmp_node = tree->root; + while (!_gtk_rbtree_is_nil (tmp_node)) + { + if (tmp_node->left->total_count > index) + { + tmp_node = tmp_node->left; + } + else if (tmp_node->total_count - tmp_node->right->total_count <= index) + { + index -= tmp_node->total_count - tmp_node->right->total_count; + tmp_node = tmp_node->right; + } + else + { + index -= tmp_node->left->total_count; + break; + } + } + if (_gtk_rbtree_is_nil (tmp_node)) + { + *new_tree = NULL; + *new_node = NULL; + return FALSE; + } + + if (index > 0) + { + g_assert (tmp_node->children); + + return _gtk_rbtree_find_index (tmp_node->children, + index - 1, + new_tree, + new_node); + } + + *new_tree = tree; + *new_node = tmp_node; + return TRUE; +} void _gtk_rbtree_remove_node (GtkRBTree *tree, GtkRBNode *node) { GtkRBNode *x, *y; - GtkRBTree *tmp_tree; - GtkRBNode *tmp_node; - gint node_height; gint y_height; + guint y_total_count; g_return_if_fail (tree != NULL); g_return_if_fail (node != NULL); + + +#ifdef G_ENABLE_DEBUG + if (gtk_get_debug_flags () & GTK_DEBUG_TREE) + { + g_print ("\n\n_gtk_rbtree_remove_node: %p\n", node); + _gtk_rbtree_debug_spew (tree); + _gtk_rbtree_test (G_STRLOC, tree); + } +#endif /* G_ENABLE_DEBUG */ /* make sure we're deleting a node that's actually in the tree */ - for (x = node; x->parent != tree->nil; x = x->parent) + for (x = node; !_gtk_rbtree_is_nil (x->parent); x = x->parent) ; g_return_if_fail (x == tree->root); - if (gtk_debug_flags & GTK_DEBUG_TREE) +#ifdef G_ENABLE_DEBUG + if (gtk_get_debug_flags () & GTK_DEBUG_TREE) _gtk_rbtree_test (G_STRLOC, tree); - - - if (node->left == tree->nil || node->right == tree->nil) +#endif + + if (_gtk_rbtree_is_nil (node->left) || + _gtk_rbtree_is_nil (node->right)) { y = node; } @@ -1078,92 +1144,113 @@ _gtk_rbtree_remove_node (GtkRBTree *tree, { y = node->right; - while (y->left != tree->nil) + while (!_gtk_rbtree_is_nil (y->left)) y = y->left; } - /* adjust count only beneath tree */ - for (x = y; x != tree->nil; x = x->parent) - x->count--; - - /* y->count = node->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)); + y_height = GTK_RBNODE_GET_HEIGHT (y) + + (y->children ? y->children->root->offset : 0); + y_total_count = 1 + (y->children ? y->children->root->total_count : 0); - tmp_node = tmp_node->parent; - if (tmp_node == tmp_tree->nil) - { - tmp_node = tmp_tree->parent_node; - tmp_tree = tmp_tree->parent_tree; - } - } - - /* x is y's only child */ - if (y->left != tree->nil) + /* x is y's only child, or nil */ + if (!_gtk_rbtree_is_nil (y->left)) x = y->left; else x = y->right; /* 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 (!_gtk_rbtree_is_nil (x)) + x->parent = y->parent; + if (!_gtk_rbtree_is_nil (y->parent)) + { + 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. + */ + 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 diff; + gint node_height, 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); + /* We want to see how much we remove from the aggregate values. + * This is all the children we remove plus the node's values. + */ + 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)) + y->flags ^= (GTK_RBNODE_BLACK | GTK_RBNODE_RED); + + y->left = node->left; + if (!_gtk_rbtree_is_nil (y->left)) + y->left->parent = y; + y->right = node->right; + if (!_gtk_rbtree_is_nil (y->right)) + y->right->parent = y; + y->parent = node->parent; + if (!_gtk_rbtree_is_nil (y->parent)) + { + if (y->parent->left == node) + y->parent->left = y; + else + y->parent->right = y; + } else - node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_RED); - node->children = y->children; + { + tree->root = y; + } + y->count = node->count; + y->total_count = node->total_count; + y->offset = node->offset; + + gtk_rbnode_adjust (tree, y, + 0, + y_total_count - node_total_count, + y_height - node_height); + } - /* 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; + _gtk_rbnode_free (node); - while (tmp_tree && tmp_node && 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; - } - } - } +#ifdef G_ENABLE_DEBUG + if (gtk_get_debug_flags () & GTK_DEBUG_TREE) + { + g_print ("_gtk_rbtree_remove_node finished...\n"); + _gtk_rbtree_debug_spew (tree); + g_print ("\n\n"); + _gtk_rbtree_test (G_STRLOC, tree); } +#endif /* G_ENABLE_DEBUG */ +} - if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK) - _gtk_rbtree_remove_node_fixup (tree, x); +GtkRBNode * +_gtk_rbtree_first (GtkRBTree *tree) +{ + GtkRBNode *node; - _gtk_rbnode_free (y); + node = tree->root; - if (gtk_debug_flags & GTK_DEBUG_TREE) - _gtk_rbtree_test (G_STRLOC, tree); + if (_gtk_rbtree_is_nil (node)) + return NULL; + + while (!_gtk_rbtree_is_nil (node->left)) + node = node->left; + + return node; } GtkRBNode * @@ -1174,16 +1261,16 @@ _gtk_rbtree_next (GtkRBTree *tree, g_return_val_if_fail (node != NULL, NULL); /* Case 1: the node's below us. */ - if (node->right != tree->nil) + if (!_gtk_rbtree_is_nil (node->right)) { node = node->right; - while (node->left != tree->nil) + while (!_gtk_rbtree_is_nil (node->left)) node = node->left; return node; } /* Case 2: it's an ancestor */ - while (node->parent != tree->nil) + while (!_gtk_rbtree_is_nil (node->parent)) { if (node->parent->right == node) node = node->parent; @@ -1203,16 +1290,16 @@ _gtk_rbtree_prev (GtkRBTree *tree, g_return_val_if_fail (node != NULL, NULL); /* Case 1: the node's below us. */ - if (node->left != tree->nil) + if (!_gtk_rbtree_is_nil (node->left)) { node = node->left; - while (node->right != tree->nil) + while (!_gtk_rbtree_is_nil (node->right)) node = node->right; return node; } /* Case 2: it's an ancestor */ - while (node->parent != tree->nil) + while (!_gtk_rbtree_is_nil (node->parent)) { if (node->parent->left == node) node = node->parent; @@ -1239,7 +1326,7 @@ _gtk_rbtree_next_full (GtkRBTree *tree, { *new_tree = node->children; *new_node = (*new_tree)->root; - while ((*new_node)->left != (*new_tree)->nil) + while (!_gtk_rbtree_is_nil ((*new_node)->left)) *new_node = (*new_node)->left; return; } @@ -1282,7 +1369,7 @@ _gtk_rbtree_prev_full (GtkRBTree *tree, { *new_tree = (*new_node)->children; *new_node = (*new_tree)->root; - while ((*new_node)->right != (*new_tree)->nil) + while (!_gtk_rbtree_is_nil ((*new_node)->right)) *new_node = (*new_node)->right; } } @@ -1310,7 +1397,7 @@ _gtk_rbtree_traverse_pre_order (GtkRBTree *tree, GtkRBTreeTraverseFunc func, gpointer data) { - if (node == tree->nil) + if (_gtk_rbtree_is_nil (node)) return; (* func) (tree, node, data); @@ -1324,7 +1411,7 @@ _gtk_rbtree_traverse_post_order (GtkRBTree *tree, GtkRBTreeTraverseFunc func, gpointer data) { - if (node == tree->nil) + if (_gtk_rbtree_is_nil (node)) return; _gtk_rbtree_traverse_post_order (tree, node->left, func, data); @@ -1360,80 +1447,91 @@ _gtk_rbtree_traverse (GtkRBTree *tree, } } -static gint -_count_nodes (GtkRBTree *tree, - GtkRBNode *node) +static inline +void _fixup_validation (GtkRBTree *tree, + GtkRBNode *node) { - gint res; - if (node == tree->nil) - return 0; - - g_assert (node->left); - g_assert (node->right); - - res = (_count_nodes (tree, node->left) + - _count_nodes (tree, node->right) + 1); + if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) || + GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) || + GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) || + 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); + } +} - if (res != node->count) - g_print ("Tree failed\n"); - return res; +static inline +void _fixup_total_count (GtkRBTree *tree, + GtkRBNode *node) +{ + node->total_count = 1 + + (node->children != NULL ? node->children->root->total_count : 0) + + node->left->total_count + node->right->total_count; } +#ifdef G_ENABLE_DEBUG static guint -get_parity (GtkRBNode *node) +get_total_count (GtkRBNode *node) { guint child_total = 0; - guint rem; - - /* The parity of a node is node->parity minus - * the parity of left, right, and children. - * - * This is equivalent to saying that if left, right, children - * sum to 0 parity, then node->parity is the parity of node, - * and if left, right, children are odd parity, then - * node->parity is the reverse of the node's parity. - */ - - child_total += (guint) node->left->parity; - child_total += (guint) node->right->parity; + + child_total += (guint) node->left->total_count; + child_total += (guint) node->right->total_count; if (node->children) - child_total += (guint) node->children->root->parity; + child_total += (guint) node->children->root->total_count; - rem = child_total % 2; - - if (rem == 0) - return node->parity; - else - return !node->parity; + return child_total + 1; } static guint -count_parity (GtkRBTree *tree, - GtkRBNode *node) +count_total (GtkRBTree *tree, + GtkRBNode *node) { guint res; - if (node == tree->nil) + if (_gtk_rbtree_is_nil (node)) return 0; res = - count_parity (tree, node->left) + - count_parity (tree, node->right) + + count_total (tree, node->left) + + count_total (tree, node->right) + (guint)1 + - (node->children ? count_parity (node->children, node->children->root) : 0); + (node->children ? count_total (node->children, node->children->root) : 0); - res = res % (guint)2; - - if (res != node->parity) - g_print ("parity incorrect for node\n"); + if (res != node->total_count) + g_print ("total count incorrect for node\n"); - if (get_parity (node) != 1) - g_error ("Node has incorrect parity %d", get_parity (node)); + if (get_total_count (node) != node->total_count) + g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node)); return res; } +static gint +_count_nodes (GtkRBTree *tree, + GtkRBNode *node) +{ + gint res; + if (_gtk_rbtree_is_nil (node)) + return 0; + + g_assert (node->left); + g_assert (node->right); + + res = (_count_nodes (tree, node->left) + + _count_nodes (tree, node->right) + 1); + + if (res != node->count) + g_print ("Tree failed\n"); + return res; +} + static void _gtk_rbtree_test_height (GtkRBTree *tree, GtkRBNode *node) @@ -1442,50 +1540,173 @@ _gtk_rbtree_test_height (GtkRBTree *tree, /* This whole test is sort of a useless truism. */ - if (node->left != tree->nil) + if (!_gtk_rbtree_is_nil (node->left)) computed_offset += node->left->offset; - if (node->right != tree->nil) + if (!_gtk_rbtree_is_nil (node->right)) computed_offset += node->right->offset; - if (node->children && node->children->root != node->children->nil) + if (node->children && !_gtk_rbtree_is_nil (node->children->root)) computed_offset += node->children->root->offset; if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset) g_error ("node has broken offset\n"); - if (node->left != tree->nil) + if (!_gtk_rbtree_is_nil (node->left)) _gtk_rbtree_test_height (tree, node->left); - if (node->right != tree->nil) + if (!_gtk_rbtree_is_nil (node->right)) _gtk_rbtree_test_height (tree, node->right); - if (node->children && node->children->root != node->children->nil) + if (node->children && !_gtk_rbtree_is_nil (node->children->root)) _gtk_rbtree_test_height (node->children, node->children->root); } -void +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) || + GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) || + 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 (!_gtk_rbtree_is_nil (node->left)) + g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)); + if (!_gtk_rbtree_is_nil (node->right)) + 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 (!_gtk_rbtree_is_nil (node->left)) + _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)); + if (!_gtk_rbtree_is_nil (node->right)) + _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)); + if (node->children != NULL && !_gtk_rbtree_is_nil (node->children->root)) + _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 (!_gtk_rbtree_is_nil (node)); + + g_assert (node->left != NULL); + g_assert (node->right != NULL); + g_assert (node->parent != NULL); + + if (!_gtk_rbtree_is_nil (node->left)) + { + g_assert (node->left->parent == node); + _gtk_rbtree_test_structure_helper (tree, node->left); + } + if (!_gtk_rbtree_is_nil (node->right)) + { + 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); + if (_gtk_rbtree_is_nil (tree->root)) + return; + + g_assert (_gtk_rbtree_is_nil (tree->root->parent)); + _gtk_rbtree_test_structure_helper (tree, tree->root); +} + +static 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 (_gtk_rbtree_is_nil (tmp_tree->root)) + return; - 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); + _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_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count); +} + +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 ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n", + node, + (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ", + node->offset, + node->total_count, + (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->children != NULL) + { + g_print ("Looking at child.\n"); + _gtk_rbtree_debug_spew (node->children); + g_print ("Done looking at child.\n"); + } + if (!_gtk_rbtree_is_nil (node->left)) + { + _gtk_rbtree_debug_spew_helper (tree, node->left, depth+1); + } + if (!_gtk_rbtree_is_nil (node->right)) + { + _gtk_rbtree_debug_spew_helper (tree, node->right, depth+1); } } +static void +_gtk_rbtree_debug_spew (GtkRBTree *tree) +{ + g_return_if_fail (tree != NULL); + + if (_gtk_rbtree_is_nil (tree->root)) + g_print ("Empty tree...\n"); + else + _gtk_rbtree_debug_spew_helper (tree, tree->root, 0); +} +#endif /* G_ENABLE_DEBUG */