2 * Copyright (C) 2000 Red Hat, Inc., Jonathan Blandford <jrb@redhat.com>
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
14 * You should have received a copy of the GNU Library General Public
15 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
19 #include "gtkrbtree.h"
22 static GtkRBNode * _gtk_rbnode_new (GtkRBTree *tree,
24 static void _gtk_rbnode_free (GtkRBNode *node);
25 static void _gtk_rbnode_rotate_left (GtkRBTree *tree,
27 static void _gtk_rbnode_rotate_right (GtkRBTree *tree,
29 static void _gtk_rbtree_insert_fixup (GtkRBTree *tree,
31 static void _gtk_rbtree_remove_node_fixup (GtkRBTree *tree,
34 static inline void _fixup_validation (GtkRBTree *tree,
36 static inline void _fixup_total_count (GtkRBTree *tree,
39 static void _gtk_rbtree_test (const gchar *where,
41 static void _gtk_rbtree_debug_spew (GtkRBTree *tree);
44 static const GtkRBNode nil = {
45 /* .flags = */ GTK_RBNODE_BLACK,
51 _gtk_rbtree_is_nil (GtkRBNode *node)
57 _gtk_rbnode_new (GtkRBTree *tree,
60 GtkRBNode *node = g_slice_new (GtkRBNode);
62 node->left = (GtkRBNode *) &nil;
63 node->right = (GtkRBNode *) &nil;
64 node->parent = (GtkRBNode *) &nil;
65 node->flags = GTK_RBNODE_RED;
66 node->total_count = 1;
68 node->children = NULL;
69 node->offset = height;
74 _gtk_rbnode_free (GtkRBNode *node)
77 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
79 node->left = (gpointer) 0xdeadbeef;
80 node->right = (gpointer) 0xdeadbeef;
81 node->parent = (gpointer) 0xdeadbeef;
82 node->total_count = 56789;
88 g_slice_free (GtkRBNode, node);
92 _gtk_rbnode_rotate_left (GtkRBTree *tree,
95 gint node_height, right_height;
98 g_return_if_fail (!_gtk_rbtree_is_nil (node));
99 g_return_if_fail (!_gtk_rbtree_is_nil (node->right));
103 node_height = GTK_RBNODE_GET_HEIGHT (node);
104 right_height = GTK_RBNODE_GET_HEIGHT (right);
105 node->right = right->left;
106 if (!_gtk_rbtree_is_nil (right->left))
107 right->left->parent = node;
109 right->parent = node->parent;
110 if (!_gtk_rbtree_is_nil (node->parent))
112 if (node == node->parent->left)
113 node->parent->left = right;
115 node->parent->right = right;
121 node->parent = right;
123 node->count = 1 + node->left->count + node->right->count;
124 right->count = 1 + right->left->count + right->right->count;
126 node->offset = node_height + node->left->offset + node->right->offset +
127 (node->children ? node->children->root->offset : 0);
128 right->offset = right_height + right->left->offset + right->right->offset +
129 (right->children ? right->children->root->offset : 0);
131 _fixup_validation (tree, node);
132 _fixup_validation (tree, right);
133 _fixup_total_count (tree, node);
134 _fixup_total_count (tree, right);
138 _gtk_rbnode_rotate_right (GtkRBTree *tree,
141 gint node_height, left_height;
144 g_return_if_fail (!_gtk_rbtree_is_nil (node));
145 g_return_if_fail (!_gtk_rbtree_is_nil (node->left));
149 node_height = GTK_RBNODE_GET_HEIGHT (node);
150 left_height = GTK_RBNODE_GET_HEIGHT (left);
152 node->left = left->right;
153 if (!_gtk_rbtree_is_nil (left->right))
154 left->right->parent = node;
156 left->parent = node->parent;
157 if (!_gtk_rbtree_is_nil (node->parent))
159 if (node == node->parent->right)
160 node->parent->right = left;
162 node->parent->left = left;
169 /* link node and left */
173 node->count = 1 + node->left->count + node->right->count;
174 left->count = 1 + left->left->count + left->right->count;
176 node->offset = node_height + node->left->offset + node->right->offset +
177 (node->children ? node->children->root->offset : 0);
178 left->offset = left_height + left->left->offset + left->right->offset +
179 (left->children?left->children->root->offset:0);
181 _fixup_validation (tree, node);
182 _fixup_validation (tree, left);
183 _fixup_total_count (tree, node);
184 _fixup_total_count (tree, left);
188 _gtk_rbtree_insert_fixup (GtkRBTree *tree,
192 /* check Red-Black properties */
193 while (node != tree->root && GTK_RBNODE_GET_COLOR (node->parent) == GTK_RBNODE_RED)
195 /* we have a violation */
196 if (node->parent == node->parent->parent->left)
198 GtkRBNode *y = node->parent->parent->right;
199 if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
201 /* uncle is GTK_RBNODE_RED */
202 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
203 GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
204 GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
205 node = node->parent->parent;
209 /* uncle is GTK_RBNODE_BLACK */
210 if (node == node->parent->right)
212 /* make node a left child */
214 _gtk_rbnode_rotate_left (tree, node);
217 /* recolor and rotate */
218 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
219 GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
220 _gtk_rbnode_rotate_right(tree, node->parent->parent);
225 /* mirror image of above code */
226 GtkRBNode *y = node->parent->parent->left;
227 if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
229 /* uncle is GTK_RBNODE_RED */
230 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
231 GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
232 GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
233 node = node->parent->parent;
237 /* uncle is GTK_RBNODE_BLACK */
238 if (node == node->parent->left)
241 _gtk_rbnode_rotate_right (tree, node);
243 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
244 GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
245 _gtk_rbnode_rotate_left (tree, node->parent->parent);
249 GTK_RBNODE_SET_COLOR (tree->root, GTK_RBNODE_BLACK);
253 _gtk_rbtree_remove_node_fixup (GtkRBTree *tree,
257 while (node != tree->root && GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
259 if (node == parent->left)
261 GtkRBNode *w = parent->right;
262 if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
264 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
265 GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_RED);
266 _gtk_rbnode_rotate_left (tree, parent);
269 if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
271 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
276 if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
278 GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
279 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
280 _gtk_rbnode_rotate_right (tree, w);
283 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (parent));
284 GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_BLACK);
285 GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
286 _gtk_rbnode_rotate_left (tree, parent);
292 GtkRBNode *w = parent->left;
293 if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
295 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
296 GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_RED);
297 _gtk_rbnode_rotate_right (tree, parent);
300 if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
302 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
307 if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
309 GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
310 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
311 _gtk_rbnode_rotate_left (tree, w);
314 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (parent));
315 GTK_RBNODE_SET_COLOR (parent, GTK_RBNODE_BLACK);
316 GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
317 _gtk_rbnode_rotate_right (tree, parent);
322 parent = node->parent;
324 GTK_RBNODE_SET_COLOR (node, GTK_RBNODE_BLACK);
328 _gtk_rbtree_new (void)
332 retval = g_new (GtkRBTree, 1);
333 retval->parent_tree = NULL;
334 retval->parent_node = NULL;
336 retval->root = (GtkRBNode *) &nil;
342 _gtk_rbtree_free_helper (GtkRBTree *tree,
347 _gtk_rbtree_free (node->children);
349 _gtk_rbnode_free (node);
353 _gtk_rbtree_free (GtkRBTree *tree)
355 _gtk_rbtree_traverse (tree,
358 _gtk_rbtree_free_helper,
361 if (tree->parent_node &&
362 tree->parent_node->children == tree)
363 tree->parent_node->children = NULL;
368 gtk_rbnode_adjust (GtkRBTree *tree,
371 int total_count_diff,
374 while (tree && node && !_gtk_rbtree_is_nil (node))
376 _fixup_validation (tree, node);
377 node->offset += offset_diff;
378 node->count += count_diff;
379 node->total_count += total_count_diff;
382 if (_gtk_rbtree_is_nil (node))
384 node = tree->parent_node;
385 tree = tree->parent_tree;
392 _gtk_rbtree_remove (GtkRBTree *tree)
394 #ifdef G_ENABLE_DEBUG
397 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
398 _gtk_rbtree_test (G_STRLOC, tree);
401 /* ugly hack to make _fixup_validation work in the first iteration of the
403 GTK_RBNODE_UNSET_FLAG (tree->root, GTK_RBNODE_DESCENDANTS_INVALID);
405 gtk_rbnode_adjust (tree->parent_tree,
408 - (int) tree->root->total_count,
409 - tree->root->offset);
411 #ifdef G_ENABLE_DEBUG
412 tmp_tree = tree->parent_tree;
415 _gtk_rbtree_free (tree);
417 #ifdef G_ENABLE_DEBUG
418 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
419 _gtk_rbtree_test (G_STRLOC, tmp_tree);
425 _gtk_rbtree_insert_after (GtkRBTree *tree,
431 gboolean right = TRUE;
433 #ifdef G_ENABLE_DEBUG
434 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
436 g_print ("\n\n_gtk_rbtree_insert_after: %p\n", current);
437 _gtk_rbtree_debug_spew (tree);
438 _gtk_rbtree_test (G_STRLOC, tree);
440 #endif /* G_ENABLE_DEBUG */
442 if (current != NULL && !_gtk_rbtree_is_nil (current->right))
444 current = current->right;
445 while (!_gtk_rbtree_is_nil (current->left))
446 current = current->left;
450 node = _gtk_rbnode_new (tree, height);
452 /* insert node in tree */
455 node->parent = current;
457 current->right = node;
459 current->left = node;
460 gtk_rbnode_adjust (tree, node->parent,
465 g_assert (_gtk_rbtree_is_nil (tree->root));
467 gtk_rbnode_adjust (tree->parent_tree, tree->parent_node,
472 _gtk_rbtree_node_mark_valid (tree, node);
474 _gtk_rbtree_node_mark_invalid (tree, node);
476 _gtk_rbtree_insert_fixup (tree, node);
478 #ifdef G_ENABLE_DEBUG
479 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
481 g_print ("_gtk_rbtree_insert_after finished...\n");
482 _gtk_rbtree_debug_spew (tree);
484 _gtk_rbtree_test (G_STRLOC, tree);
486 #endif /* G_ENABLE_DEBUG */
492 _gtk_rbtree_insert_before (GtkRBTree *tree,
498 gboolean left = TRUE;
500 #ifdef G_ENABLE_DEBUG
501 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
503 g_print ("\n\n_gtk_rbtree_insert_before: %p\n", current);
504 _gtk_rbtree_debug_spew (tree);
505 _gtk_rbtree_test (G_STRLOC, tree);
507 #endif /* G_ENABLE_DEBUG */
509 if (current != NULL && !_gtk_rbtree_is_nil (current->left))
511 current = current->left;
512 while (!_gtk_rbtree_is_nil (current->right))
513 current = current->right;
518 node = _gtk_rbnode_new (tree, height);
520 /* insert node in tree */
523 node->parent = current;
525 current->left = node;
527 current->right = node;
528 gtk_rbnode_adjust (tree, node->parent,
533 g_assert (_gtk_rbtree_is_nil (tree->root));
535 gtk_rbnode_adjust (tree->parent_tree, tree->parent_node,
540 _gtk_rbtree_node_mark_valid (tree, node);
542 _gtk_rbtree_node_mark_invalid (tree, node);
544 _gtk_rbtree_insert_fixup (tree, node);
546 #ifdef G_ENABLE_DEBUG
547 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
549 g_print ("_gtk_rbtree_insert_before finished...\n");
550 _gtk_rbtree_debug_spew (tree);
552 _gtk_rbtree_test (G_STRLOC, tree);
554 #endif /* G_ENABLE_DEBUG */
560 _gtk_rbtree_find_count (GtkRBTree *tree,
566 while (!_gtk_rbtree_is_nil (node) && (node->left->count + 1 != count))
568 if (node->left->count >= count)
572 count -= (node->left->count + 1);
576 if (_gtk_rbtree_is_nil (node))
582 _gtk_rbtree_node_set_height (GtkRBTree *tree,
586 gint diff = height - GTK_RBNODE_GET_HEIGHT (node);
591 gtk_rbnode_adjust (tree, node, 0, 0, diff);
593 #ifdef G_ENABLE_DEBUG
594 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
595 _gtk_rbtree_test (G_STRLOC, tree);
600 _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
603 if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
606 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
609 if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))
611 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
613 if (_gtk_rbtree_is_nil (node))
615 node = tree->parent_node;
616 tree = tree->parent_tree;
623 /* Draconian version. */
625 _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
628 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
631 _fixup_validation (tree, node);
633 if (_gtk_rbtree_is_nil (node))
635 node = tree->parent_node;
636 tree = tree->parent_tree;
644 _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
647 if ((!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&
648 (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)))
651 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
652 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
656 if ((GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) ||
657 (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)) ||
658 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)) ||
659 (GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
660 (GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)))
663 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
665 if (_gtk_rbtree_is_nil (node))
667 node = tree->parent_node;
668 tree = tree->parent_tree;
675 /* Draconian version */
677 _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
680 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
681 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
685 _fixup_validation (tree, node);
687 if (_gtk_rbtree_is_nil (node))
689 node = tree->parent_node;
690 tree = tree->parent_tree;
696 /* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above.
699 _gtk_rbtree_column_invalid (GtkRBTree *tree)
706 node = _gtk_rbtree_first (tree);
710 if (! (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)))
711 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
712 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
715 _gtk_rbtree_column_invalid (node->children);
717 while ((node = _gtk_rbtree_next (tree, node)) != NULL);
721 _gtk_rbtree_mark_invalid (GtkRBTree *tree)
728 node = _gtk_rbtree_first (tree);
732 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
733 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
736 _gtk_rbtree_mark_invalid (node->children);
738 while ((node = _gtk_rbtree_next (tree, node)) != NULL);
742 _gtk_rbtree_set_fixed_height (GtkRBTree *tree,
751 node = _gtk_rbtree_first (tree);
755 if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
757 _gtk_rbtree_node_set_height (tree, node, height);
759 _gtk_rbtree_node_mark_valid (tree, node);
763 _gtk_rbtree_set_fixed_height (node->children, height, mark_valid);
765 while ((node = _gtk_rbtree_next (tree, node)) != NULL);
769 reorder_prepare (GtkRBTree *tree,
773 node->offset -= node->left->offset + node->right->offset;
774 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
778 reorder_fixup (GtkRBTree *tree,
782 node->offset += node->left->offset + node->right->offset;
783 node->count = 1 + node->left->count + node->right->count;
784 _fixup_validation (tree, node);
785 _fixup_total_count (tree, node);
789 reorder_copy_node (GtkRBTree *tree,
793 to->flags = (to->flags & GTK_RBNODE_NON_COLORS) | GTK_RBNODE_GET_COLOR (from);
795 to->left = from->left;
796 if (!_gtk_rbtree_is_nil (to->left))
797 to->left->parent = to;
799 to->right = from->right;
800 if (!_gtk_rbtree_is_nil (to->right))
801 to->right->parent = to;
803 to->parent = from->parent;
804 if (_gtk_rbtree_is_nil (to->parent))
806 else if (to->parent->left == from)
807 to->parent->left = to;
808 else if (to->parent->right == from)
809 to->parent->right = to;
812 /* It basically pulls everything out of the tree, rearranges it, and puts it
813 * back together. Our strategy is to keep the old RBTree intact, and just
814 * rearrange the contents. When that is done, we go through and update the
815 * heights. There is probably a more elegant way to write this function. If
816 * anyone wants to spend the time writing it, patches will be accepted.
819 _gtk_rbtree_reorder (GtkRBTree *tree,
827 g_return_if_fail (tree != NULL);
828 g_return_if_fail (length > 0);
829 g_return_if_fail (tree->root->count == length);
831 nodes = g_new (GtkRBNode *, length);
833 _gtk_rbtree_traverse (tree, tree->root, G_PRE_ORDER, reorder_prepare, NULL);
835 for (node = _gtk_rbtree_first (tree), i = 0;
837 node = _gtk_rbtree_next (tree, node), i++)
842 for (i = 0; i < length; i++)
844 GtkRBNode tmp = { 0, };
845 GSList *l, *cycle = NULL;
849 /* already swapped */
850 if (nodes[i] == NULL)
852 /* no need to swap */
853 if (new_order[i] == i)
856 /* make a list out of the pending nodes */
857 for (j = i; new_order[j] != i; j = new_order[j])
859 cycle = g_slist_prepend (cycle, nodes[j]);
864 reorder_copy_node (tree, &tmp, node);
865 for (l = cycle; l; l = l->next)
867 reorder_copy_node (tree, node, l->data);
871 reorder_copy_node (tree, node, &tmp);
873 g_slist_free (cycle);
876 _gtk_rbtree_traverse (tree, tree->root, G_POST_ORDER, reorder_fixup, NULL);
882 * _gtk_rbtree_contains:
884 * @potential_child: a potential child of @tree
886 * Checks if @potential_child is a child (direct or via intermediate
889 * Returns: %TRUE if @potentitial_child is a child of @tree.
892 _gtk_rbtree_contains (GtkRBTree *tree,
893 GtkRBTree *potential_child)
895 g_return_val_if_fail (tree != NULL, FALSE);
896 g_return_val_if_fail (potential_child != NULL, FALSE);
899 potential_child = potential_child->parent_tree;
900 if (potential_child == tree)
902 } while (potential_child != NULL);
908 _gtk_rbtree_node_find_offset (GtkRBTree *tree,
915 g_assert (node->left);
917 retval = node->left->offset;
919 while (tree && node && !_gtk_rbtree_is_nil (node))
924 /* Add left branch, plus children, iff we came from the right */
925 if (node->right == last)
926 retval += node->offset - node->right->offset;
928 if (_gtk_rbtree_is_nil (node))
930 node = tree->parent_node;
931 tree = tree->parent_tree;
933 /* Add the parent node, plus the left branch. */
935 retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
942 _gtk_rbtree_node_get_index (GtkRBTree *tree,
949 g_assert (node->left);
951 retval = node->left->total_count;
953 while (tree && node && !_gtk_rbtree_is_nil (node))
958 /* Add left branch, plus children, iff we came from the right */
959 if (node->right == last)
960 retval += node->total_count - node->right->total_count;
962 if (_gtk_rbtree_is_nil (node))
964 node = tree->parent_node;
965 tree = tree->parent_tree;
967 /* Add the parent node, plus the left branch. */
969 retval += node->left->total_count + 1; /* 1 == GTK_RBNODE_GET_PARITY() */
977 gtk_rbtree_real_find_offset (GtkRBTree *tree,
979 GtkRBTree **new_tree,
980 GtkRBNode **new_node)
995 tmp_node = tree->root;
996 while (!_gtk_rbtree_is_nil (tmp_node) &&
997 (tmp_node->left->offset > height ||
998 (tmp_node->offset - tmp_node->right->offset) < height))
1000 if (tmp_node->left->offset > height)
1001 tmp_node = tmp_node->left;
1004 height -= (tmp_node->offset - tmp_node->right->offset);
1005 tmp_node = tmp_node->right;
1008 if (_gtk_rbtree_is_nil (tmp_node))
1014 if (tmp_node->children)
1016 if ((tmp_node->offset -
1017 tmp_node->right->offset -
1018 tmp_node->children->root->offset) > height)
1021 *new_node = tmp_node;
1022 return (height - tmp_node->left->offset);
1024 return gtk_rbtree_real_find_offset (tmp_node->children,
1025 height - tmp_node->left->offset -
1027 tmp_node->left->offset -
1028 tmp_node->right->offset -
1029 tmp_node->children->root->offset),
1034 *new_node = tmp_node;
1035 return (height - tmp_node->left->offset);
1039 _gtk_rbtree_find_offset (GtkRBTree *tree,
1041 GtkRBTree **new_tree,
1042 GtkRBNode **new_node)
1047 (height >= tree->root->offset))
1054 return gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
1058 _gtk_rbtree_find_index (GtkRBTree *tree,
1060 GtkRBTree **new_tree,
1061 GtkRBNode **new_node)
1063 GtkRBNode *tmp_node;
1067 tmp_node = tree->root;
1068 while (!_gtk_rbtree_is_nil (tmp_node))
1070 if (tmp_node->left->total_count > index)
1072 tmp_node = tmp_node->left;
1074 else if (tmp_node->total_count - tmp_node->right->total_count <= index)
1076 index -= tmp_node->total_count - tmp_node->right->total_count;
1077 tmp_node = tmp_node->right;
1081 index -= tmp_node->left->total_count;
1085 if (_gtk_rbtree_is_nil (tmp_node))
1094 g_assert (tmp_node->children);
1096 return _gtk_rbtree_find_index (tmp_node->children,
1103 *new_node = tmp_node;
1108 _gtk_rbtree_remove_node (GtkRBTree *tree,
1113 guint y_total_count;
1115 g_return_if_fail (tree != NULL);
1116 g_return_if_fail (node != NULL);
1119 #ifdef G_ENABLE_DEBUG
1120 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1122 g_print ("\n\n_gtk_rbtree_remove_node: %p\n", node);
1123 _gtk_rbtree_debug_spew (tree);
1124 _gtk_rbtree_test (G_STRLOC, tree);
1126 #endif /* G_ENABLE_DEBUG */
1128 /* make sure we're deleting a node that's actually in the tree */
1129 for (x = node; !_gtk_rbtree_is_nil (x->parent); x = x->parent)
1131 g_return_if_fail (x == tree->root);
1133 #ifdef G_ENABLE_DEBUG
1134 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1135 _gtk_rbtree_test (G_STRLOC, tree);
1138 if (_gtk_rbtree_is_nil (node->left) ||
1139 _gtk_rbtree_is_nil (node->right))
1147 while (!_gtk_rbtree_is_nil (y->left))
1151 y_height = GTK_RBNODE_GET_HEIGHT (y)
1152 + (y->children ? y->children->root->offset : 0);
1153 y_total_count = 1 + (y->children ? y->children->root->total_count : 0);
1155 /* x is y's only child, or nil */
1156 if (!_gtk_rbtree_is_nil (y->left))
1161 /* remove y from the parent chain */
1162 if (!_gtk_rbtree_is_nil (x))
1163 x->parent = y->parent;
1164 if (!_gtk_rbtree_is_nil (y->parent))
1166 if (y == y->parent->left)
1167 y->parent->left = x;
1169 y->parent->right = x;
1176 /* We need to clean up the validity of the tree.
1178 gtk_rbnode_adjust (tree, y, -1, - y_total_count, - y_height);
1180 if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
1181 _gtk_rbtree_remove_node_fixup (tree, x, y->parent);
1185 gint node_height, node_total_count;
1187 /* We want to see how much we remove from the aggregate values.
1188 * This is all the children we remove plus the node's values.
1190 node_height = GTK_RBNODE_GET_HEIGHT (node)
1191 + (node->children ? node->children->root->offset : 0);
1192 node_total_count = 1
1193 + (node->children ? node->children->root->total_count : 0);
1195 /* Move the node over */
1196 if (GTK_RBNODE_GET_COLOR (node) != GTK_RBNODE_GET_COLOR (y))
1197 y->flags ^= (GTK_RBNODE_BLACK | GTK_RBNODE_RED);
1199 y->left = node->left;
1200 if (!_gtk_rbtree_is_nil (y->left))
1201 y->left->parent = y;
1202 y->right = node->right;
1203 if (!_gtk_rbtree_is_nil (y->right))
1204 y->right->parent = y;
1205 y->parent = node->parent;
1206 if (!_gtk_rbtree_is_nil (y->parent))
1208 if (y->parent->left == node)
1209 y->parent->left = y;
1211 y->parent->right = y;
1217 y->count = node->count;
1218 y->total_count = node->total_count;
1219 y->offset = node->offset;
1221 gtk_rbnode_adjust (tree, y,
1223 y_total_count - node_total_count,
1224 y_height - node_height);
1227 _gtk_rbnode_free (node);
1229 #ifdef G_ENABLE_DEBUG
1230 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1232 g_print ("_gtk_rbtree_remove_node finished...\n");
1233 _gtk_rbtree_debug_spew (tree);
1235 _gtk_rbtree_test (G_STRLOC, tree);
1237 #endif /* G_ENABLE_DEBUG */
1241 _gtk_rbtree_first (GtkRBTree *tree)
1247 if (_gtk_rbtree_is_nil (node))
1250 while (!_gtk_rbtree_is_nil (node->left))
1257 _gtk_rbtree_next (GtkRBTree *tree,
1260 g_return_val_if_fail (tree != NULL, NULL);
1261 g_return_val_if_fail (node != NULL, NULL);
1263 /* Case 1: the node's below us. */
1264 if (!_gtk_rbtree_is_nil (node->right))
1267 while (!_gtk_rbtree_is_nil (node->left))
1272 /* Case 2: it's an ancestor */
1273 while (!_gtk_rbtree_is_nil (node->parent))
1275 if (node->parent->right == node)
1276 node = node->parent;
1278 return (node->parent);
1281 /* Case 3: There is no next node */
1286 _gtk_rbtree_prev (GtkRBTree *tree,
1289 g_return_val_if_fail (tree != NULL, NULL);
1290 g_return_val_if_fail (node != NULL, NULL);
1292 /* Case 1: the node's below us. */
1293 if (!_gtk_rbtree_is_nil (node->left))
1296 while (!_gtk_rbtree_is_nil (node->right))
1301 /* Case 2: it's an ancestor */
1302 while (!_gtk_rbtree_is_nil (node->parent))
1304 if (node->parent->left == node)
1305 node = node->parent;
1307 return (node->parent);
1310 /* Case 3: There is no next node */
1315 _gtk_rbtree_next_full (GtkRBTree *tree,
1317 GtkRBTree **new_tree,
1318 GtkRBNode **new_node)
1320 g_return_if_fail (tree != NULL);
1321 g_return_if_fail (node != NULL);
1322 g_return_if_fail (new_tree != NULL);
1323 g_return_if_fail (new_node != NULL);
1327 *new_tree = node->children;
1328 *new_node = (*new_tree)->root;
1329 while (!_gtk_rbtree_is_nil ((*new_node)->left))
1330 *new_node = (*new_node)->left;
1335 *new_node = _gtk_rbtree_next (tree, node);
1337 while ((*new_node == NULL) &&
1338 (*new_tree != NULL))
1340 *new_node = (*new_tree)->parent_node;
1341 *new_tree = (*new_tree)->parent_tree;
1343 *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1348 _gtk_rbtree_prev_full (GtkRBTree *tree,
1350 GtkRBTree **new_tree,
1351 GtkRBNode **new_node)
1353 g_return_if_fail (tree != NULL);
1354 g_return_if_fail (node != NULL);
1355 g_return_if_fail (new_tree != NULL);
1356 g_return_if_fail (new_node != NULL);
1359 *new_node = _gtk_rbtree_prev (tree, node);
1361 if (*new_node == NULL)
1363 *new_node = (*new_tree)->parent_node;
1364 *new_tree = (*new_tree)->parent_tree;
1368 while ((*new_node)->children)
1370 *new_tree = (*new_node)->children;
1371 *new_node = (*new_tree)->root;
1372 while (!_gtk_rbtree_is_nil ((*new_node)->right))
1373 *new_node = (*new_node)->right;
1379 _gtk_rbtree_get_depth (GtkRBTree *tree)
1381 GtkRBTree *tmp_tree;
1384 tmp_tree = tree->parent_tree;
1388 tmp_tree = tmp_tree->parent_tree;
1395 _gtk_rbtree_traverse_pre_order (GtkRBTree *tree,
1397 GtkRBTreeTraverseFunc func,
1400 if (_gtk_rbtree_is_nil (node))
1403 (* func) (tree, node, data);
1404 _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1405 _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1409 _gtk_rbtree_traverse_post_order (GtkRBTree *tree,
1411 GtkRBTreeTraverseFunc func,
1414 if (_gtk_rbtree_is_nil (node))
1417 _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1418 _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1419 (* func) (tree, node, data);
1423 _gtk_rbtree_traverse (GtkRBTree *tree,
1425 GTraverseType order,
1426 GtkRBTreeTraverseFunc func,
1429 g_return_if_fail (tree != NULL);
1430 g_return_if_fail (node != NULL);
1431 g_return_if_fail (func != NULL);
1432 g_return_if_fail (order <= G_LEVEL_ORDER);
1437 _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1440 _gtk_rbtree_traverse_post_order (tree, node, func, data);
1445 g_warning ("unsupported traversal order.");
1451 void _fixup_validation (GtkRBTree *tree,
1454 if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1455 GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1456 GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) ||
1457 GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID) ||
1458 (node->children != NULL && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
1460 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1464 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1469 void _fixup_total_count (GtkRBTree *tree,
1472 node->total_count = 1 +
1473 (node->children != NULL ? node->children->root->total_count : 0) +
1474 node->left->total_count + node->right->total_count;
1477 #ifdef G_ENABLE_DEBUG
1479 get_total_count (GtkRBNode *node)
1481 guint child_total = 0;
1483 child_total += (guint) node->left->total_count;
1484 child_total += (guint) node->right->total_count;
1487 child_total += (guint) node->children->root->total_count;
1489 return child_total + 1;
1493 count_total (GtkRBTree *tree,
1498 if (_gtk_rbtree_is_nil (node))
1502 count_total (tree, node->left) +
1503 count_total (tree, node->right) +
1505 (node->children ? count_total (node->children, node->children->root) : 0);
1507 if (res != node->total_count)
1508 g_print ("total count incorrect for node\n");
1510 if (get_total_count (node) != node->total_count)
1511 g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
1517 _count_nodes (GtkRBTree *tree,
1521 if (_gtk_rbtree_is_nil (node))
1524 g_assert (node->left);
1525 g_assert (node->right);
1527 res = (_count_nodes (tree, node->left) +
1528 _count_nodes (tree, node->right) + 1);
1530 if (res != node->count)
1531 g_print ("Tree failed\n");
1536 _gtk_rbtree_test_height (GtkRBTree *tree,
1539 gint computed_offset = 0;
1541 /* This whole test is sort of a useless truism. */
1543 if (!_gtk_rbtree_is_nil (node->left))
1544 computed_offset += node->left->offset;
1546 if (!_gtk_rbtree_is_nil (node->right))
1547 computed_offset += node->right->offset;
1549 if (node->children && !_gtk_rbtree_is_nil (node->children->root))
1550 computed_offset += node->children->root->offset;
1552 if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1553 g_error ("node has broken offset\n");
1555 if (!_gtk_rbtree_is_nil (node->left))
1556 _gtk_rbtree_test_height (tree, node->left);
1558 if (!_gtk_rbtree_is_nil (node->right))
1559 _gtk_rbtree_test_height (tree, node->right);
1561 if (node->children && !_gtk_rbtree_is_nil (node->children->root))
1562 _gtk_rbtree_test_height (node->children, node->children->root);
1566 _gtk_rbtree_test_dirty (GtkRBTree *tree,
1568 gint expected_dirtyness)
1571 if (expected_dirtyness)
1573 g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1574 GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1575 GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID) ||
1576 GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID) ||
1577 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)));
1581 g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
1582 ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
1583 if (!_gtk_rbtree_is_nil (node->left))
1584 g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1585 if (!_gtk_rbtree_is_nil (node->right))
1586 g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1587 if (node->children != NULL)
1588 g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1591 if (!_gtk_rbtree_is_nil (node->left))
1592 _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1593 if (!_gtk_rbtree_is_nil (node->right))
1594 _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1595 if (node->children != NULL && !_gtk_rbtree_is_nil (node->children->root))
1596 _gtk_rbtree_test_dirty (node->children, node->children->root, GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1599 static void _gtk_rbtree_test_structure (GtkRBTree *tree);
1602 _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
1605 g_assert (!_gtk_rbtree_is_nil (node));
1607 g_assert (node->left != NULL);
1608 g_assert (node->right != NULL);
1609 g_assert (node->parent != NULL);
1611 if (!_gtk_rbtree_is_nil (node->left))
1613 g_assert (node->left->parent == node);
1614 _gtk_rbtree_test_structure_helper (tree, node->left);
1616 if (!_gtk_rbtree_is_nil (node->right))
1618 g_assert (node->right->parent == node);
1619 _gtk_rbtree_test_structure_helper (tree, node->right);
1622 if (node->children != NULL)
1624 g_assert (node->children->parent_tree == tree);
1625 g_assert (node->children->parent_node == node);
1627 _gtk_rbtree_test_structure (node->children);
1631 _gtk_rbtree_test_structure (GtkRBTree *tree)
1633 g_assert (tree->root);
1634 if (_gtk_rbtree_is_nil (tree->root))
1637 g_assert (_gtk_rbtree_is_nil (tree->root->parent));
1638 _gtk_rbtree_test_structure_helper (tree, tree->root);
1642 _gtk_rbtree_test (const gchar *where,
1645 GtkRBTree *tmp_tree;
1650 /* Test the entire tree */
1652 while (tmp_tree->parent_tree)
1653 tmp_tree = tmp_tree->parent_tree;
1655 if (_gtk_rbtree_is_nil (tmp_tree->root))
1658 _gtk_rbtree_test_structure (tmp_tree);
1660 g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1661 _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1664 _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1665 _gtk_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_RBNODE_FLAG_SET (tmp_tree->root, GTK_RBNODE_DESCENDANTS_INVALID));
1666 g_assert (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count);
1670 _gtk_rbtree_debug_spew_helper (GtkRBTree *tree,
1675 for (i = 0; i < depth; i++)
1678 g_print ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
1680 (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
1683 (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))?1:0,
1684 (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))?1:0,
1685 (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))?1:0);
1686 if (node->children != NULL)
1688 g_print ("Looking at child.\n");
1689 _gtk_rbtree_debug_spew (node->children);
1690 g_print ("Done looking at child.\n");
1692 if (!_gtk_rbtree_is_nil (node->left))
1694 _gtk_rbtree_debug_spew_helper (tree, node->left, depth+1);
1696 if (!_gtk_rbtree_is_nil (node->right))
1698 _gtk_rbtree_debug_spew_helper (tree, node->right, depth+1);
1703 _gtk_rbtree_debug_spew (GtkRBTree *tree)
1705 g_return_if_fail (tree != NULL);
1707 if (_gtk_rbtree_is_nil (tree->root))
1708 g_print ("Empty tree...\n");
1710 _gtk_rbtree_debug_spew_helper (tree, tree->root, 0);
1712 #endif /* G_ENABLE_DEBUG */