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, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
21 #include "gtkrbtree.h"
24 static GtkRBNode * _gtk_rbnode_new (GtkRBTree *tree,
26 static void _gtk_rbnode_free (GtkRBNode *node);
27 static void _gtk_rbnode_rotate_left (GtkRBTree *tree,
29 static void _gtk_rbnode_rotate_right (GtkRBTree *tree,
31 static void _gtk_rbtree_insert_fixup (GtkRBTree *tree,
33 static void _gtk_rbtree_remove_node_fixup (GtkRBTree *tree,
35 static inline void _fixup_validation (GtkRBTree *tree,
37 static inline void _fixup_total_count (GtkRBTree *tree,
40 static void _gtk_rbtree_test (const gchar *where,
42 static void _gtk_rbtree_debug_spew (GtkRBTree *tree);
48 _gtk_rbnode_new (GtkRBTree *tree,
51 GtkRBNode *node = g_slice_new (GtkRBNode);
53 node->left = tree->nil;
54 node->right = tree->nil;
55 node->parent = tree->nil;
56 node->flags = GTK_RBNODE_RED;
57 node->total_count = 1;
59 node->children = NULL;
60 node->offset = height;
65 _gtk_rbnode_free (GtkRBNode *node)
68 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
70 node->left = (gpointer) 0xdeadbeef;
71 node->right = (gpointer) 0xdeadbeef;
72 node->parent = (gpointer) 0xdeadbeef;
73 node->total_count = 56789;
79 g_slice_free (GtkRBNode, node);
83 _gtk_rbnode_rotate_left (GtkRBTree *tree,
86 gint node_height, right_height;
87 GtkRBNode *right = node->right;
89 g_return_if_fail (node != tree->nil);
91 node_height = node->offset -
92 (node->left?node->left->offset:0) -
93 (node->right?node->right->offset:0) -
94 (node->children?node->children->root->offset:0);
95 right_height = right->offset -
96 (right->left?right->left->offset:0) -
97 (right->right?right->right->offset:0) -
98 (right->children?right->children->root->offset:0);
99 node->right = right->left;
100 if (right->left != tree->nil)
101 right->left->parent = node;
103 if (right != tree->nil)
104 right->parent = node->parent;
105 if (node->parent != tree->nil)
107 if (node == node->parent->left)
108 node->parent->left = right;
110 node->parent->right = right;
116 if (node != tree->nil)
117 node->parent = right;
119 node->count = 1 + (node->left?node->left->count:0) +
120 (node->right?node->right->count:0);
121 right->count = 1 + (right->left?right->left->count:0) +
122 (right->right?right->right->count:0);
124 node->offset = node_height +
125 (node->left?node->left->offset:0) +
126 (node->right?node->right->offset:0) +
127 (node->children?node->children->root->offset:0);
128 right->offset = right_height +
129 (right->left?right->left->offset:0) +
130 (right->right?right->right->offset:0) +
131 (right->children?right->children->root->offset:0);
133 _fixup_validation (tree, node);
134 _fixup_validation (tree, right);
135 _fixup_total_count (tree, node);
136 _fixup_total_count (tree, right);
140 _gtk_rbnode_rotate_right (GtkRBTree *tree,
143 gint node_height, left_height;
144 GtkRBNode *left = node->left;
146 g_return_if_fail (node != tree->nil);
148 node_height = node->offset -
149 (node->left?node->left->offset:0) -
150 (node->right?node->right->offset:0) -
151 (node->children?node->children->root->offset:0);
152 left_height = left->offset -
153 (left->left?left->left->offset:0) -
154 (left->right?left->right->offset:0) -
155 (left->children?left->children->root->offset:0);
157 node->left = left->right;
158 if (left->right != tree->nil)
159 left->right->parent = node;
161 if (left != tree->nil)
162 left->parent = node->parent;
163 if (node->parent != tree->nil)
165 if (node == node->parent->right)
166 node->parent->right = left;
168 node->parent->left = left;
175 /* link node and left */
177 if (node != tree->nil)
180 node->count = 1 + (node->left?node->left->count:0) +
181 (node->right?node->right->count:0);
182 left->count = 1 + (left->left?left->left->count:0) +
183 (left->right?left->right->count:0);
185 node->offset = node_height +
186 (node->left?node->left->offset:0) +
187 (node->right?node->right->offset:0) +
188 (node->children?node->children->root->offset:0);
189 left->offset = left_height +
190 (left->left?left->left->offset:0) +
191 (left->right?left->right->offset:0) +
192 (left->children?left->children->root->offset:0);
194 _fixup_validation (tree, node);
195 _fixup_validation (tree, left);
196 _fixup_total_count (tree, node);
197 _fixup_total_count (tree, left);
201 _gtk_rbtree_insert_fixup (GtkRBTree *tree,
205 /* check Red-Black properties */
206 while (node != tree->root && GTK_RBNODE_GET_COLOR (node->parent) == GTK_RBNODE_RED)
208 /* we have a violation */
209 if (node->parent == node->parent->parent->left)
211 GtkRBNode *y = node->parent->parent->right;
212 if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
214 /* uncle is GTK_RBNODE_RED */
215 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
216 GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
217 GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
218 node = node->parent->parent;
222 /* uncle is GTK_RBNODE_BLACK */
223 if (node == node->parent->right)
225 /* make node a left child */
227 _gtk_rbnode_rotate_left (tree, node);
230 /* recolor and rotate */
231 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
232 GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
233 _gtk_rbnode_rotate_right(tree, node->parent->parent);
238 /* mirror image of above code */
239 GtkRBNode *y = node->parent->parent->left;
240 if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_RED)
242 /* uncle is GTK_RBNODE_RED */
243 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
244 GTK_RBNODE_SET_COLOR (y, GTK_RBNODE_BLACK);
245 GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
246 node = node->parent->parent;
250 /* uncle is GTK_RBNODE_BLACK */
251 if (node == node->parent->left)
254 _gtk_rbnode_rotate_right (tree, node);
256 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
257 GTK_RBNODE_SET_COLOR (node->parent->parent, GTK_RBNODE_RED);
258 _gtk_rbnode_rotate_left (tree, node->parent->parent);
262 GTK_RBNODE_SET_COLOR (tree->root, GTK_RBNODE_BLACK);
266 _gtk_rbtree_remove_node_fixup (GtkRBTree *tree,
269 while (node != tree->root && GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
271 if (node == node->parent->left)
273 GtkRBNode *w = node->parent->right;
274 if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
276 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
277 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED);
278 _gtk_rbnode_rotate_left (tree, node->parent);
279 w = node->parent->right;
281 if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
283 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
288 if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK)
290 GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
291 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
292 _gtk_rbnode_rotate_right (tree, w);
293 w = node->parent->right;
295 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent));
296 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
297 GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
298 _gtk_rbnode_rotate_left (tree, node->parent);
304 GtkRBNode *w = node->parent->left;
305 if (GTK_RBNODE_GET_COLOR (w) == GTK_RBNODE_RED)
307 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_BLACK);
308 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_RED);
309 _gtk_rbnode_rotate_right (tree, node->parent);
310 w = node->parent->left;
312 if (GTK_RBNODE_GET_COLOR (w->right) == GTK_RBNODE_BLACK && GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
314 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
319 if (GTK_RBNODE_GET_COLOR (w->left) == GTK_RBNODE_BLACK)
321 GTK_RBNODE_SET_COLOR (w->right, GTK_RBNODE_BLACK);
322 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_RED);
323 _gtk_rbnode_rotate_left (tree, w);
324 w = node->parent->left;
326 GTK_RBNODE_SET_COLOR (w, GTK_RBNODE_GET_COLOR (node->parent));
327 GTK_RBNODE_SET_COLOR (node->parent, GTK_RBNODE_BLACK);
328 GTK_RBNODE_SET_COLOR (w->left, GTK_RBNODE_BLACK);
329 _gtk_rbnode_rotate_right (tree, node->parent);
334 GTK_RBNODE_SET_COLOR (node, GTK_RBNODE_BLACK);
338 _gtk_rbtree_new (void)
342 retval = g_new (GtkRBTree, 1);
343 retval->parent_tree = NULL;
344 retval->parent_node = NULL;
346 retval->nil = g_slice_new (GtkRBNode);
347 retval->nil->left = NULL;
348 retval->nil->right = NULL;
349 retval->nil->parent = NULL;
350 retval->nil->flags = GTK_RBNODE_BLACK;
351 retval->nil->count = 0;
352 retval->nil->offset = 0;
353 retval->nil->total_count = 0;
355 retval->root = retval->nil;
360 _gtk_rbtree_free_helper (GtkRBTree *tree,
365 _gtk_rbtree_free (node->children);
367 _gtk_rbnode_free (node);
371 _gtk_rbtree_free (GtkRBTree *tree)
373 _gtk_rbtree_traverse (tree,
376 _gtk_rbtree_free_helper,
379 if (tree->parent_node &&
380 tree->parent_node->children == tree)
381 tree->parent_node->children = NULL;
382 _gtk_rbnode_free (tree->nil);
387 gtk_rbnode_adjust (GtkRBTree *tree,
390 int total_count_diff,
393 while (tree && node && node != tree->nil)
395 _fixup_validation (tree, node);
396 node->offset += offset_diff;
397 node->count += count_diff;
398 node->total_count += total_count_diff;
401 if (node == tree->nil)
403 node = tree->parent_node;
404 tree = tree->parent_tree;
411 _gtk_rbtree_remove (GtkRBTree *tree)
413 #ifdef G_ENABLE_DEBUG
416 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
417 _gtk_rbtree_test (G_STRLOC, tree);
420 /* ugly hack to make _fixup_validation work in the first iteration of the
422 GTK_RBNODE_UNSET_FLAG (tree->root, GTK_RBNODE_DESCENDANTS_INVALID);
424 gtk_rbnode_adjust (tree->parent_tree,
427 - (int) tree->root->total_count,
428 - tree->root->offset);
430 #ifdef G_ENABLE_DEBUG
431 tmp_tree = tree->parent_tree;
434 _gtk_rbtree_free (tree);
436 #ifdef G_ENABLE_DEBUG
437 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
438 _gtk_rbtree_test (G_STRLOC, tmp_tree);
444 _gtk_rbtree_insert_after (GtkRBTree *tree,
450 gboolean right = TRUE;
452 #ifdef G_ENABLE_DEBUG
453 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
455 g_print ("\n\n_gtk_rbtree_insert_after: %p\n", current);
456 _gtk_rbtree_debug_spew (tree);
457 _gtk_rbtree_test (G_STRLOC, tree);
459 #endif /* G_ENABLE_DEBUG */
461 if (current != NULL && current->right != tree->nil)
463 current = current->right;
464 while (current->left != tree->nil)
465 current = current->left;
469 node = _gtk_rbnode_new (tree, height);
470 node->parent = (current?current:tree->nil);
472 /* insert node in tree */
476 current->right = node;
478 current->left = node;
479 gtk_rbnode_adjust (tree, node->parent,
484 g_assert (tree->root == tree->nil);
486 gtk_rbnode_adjust (tree->parent_tree, tree->parent_node,
491 _gtk_rbtree_node_mark_valid (tree, node);
493 _gtk_rbtree_node_mark_invalid (tree, node);
495 _gtk_rbtree_insert_fixup (tree, node);
497 #ifdef G_ENABLE_DEBUG
498 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
500 g_print ("_gtk_rbtree_insert_after finished...\n");
501 _gtk_rbtree_debug_spew (tree);
503 _gtk_rbtree_test (G_STRLOC, tree);
505 #endif /* G_ENABLE_DEBUG */
511 _gtk_rbtree_insert_before (GtkRBTree *tree,
517 gboolean left = TRUE;
519 #ifdef G_ENABLE_DEBUG
520 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
522 g_print ("\n\n_gtk_rbtree_insert_before: %p\n", current);
523 _gtk_rbtree_debug_spew (tree);
524 _gtk_rbtree_test (G_STRLOC, tree);
526 #endif /* G_ENABLE_DEBUG */
528 if (current != NULL && current->left != tree->nil)
530 current = current->left;
531 while (current->right != tree->nil)
532 current = current->right;
537 node = _gtk_rbnode_new (tree, height);
538 node->parent = (current?current:tree->nil);
540 /* insert node in tree */
544 current->left = node;
546 current->right = node;
547 gtk_rbnode_adjust (tree, node->parent,
552 g_assert (tree->root == tree->nil);
554 gtk_rbnode_adjust (tree->parent_tree, tree->parent_node,
559 _gtk_rbtree_node_mark_valid (tree, node);
561 _gtk_rbtree_node_mark_invalid (tree, node);
563 _gtk_rbtree_insert_fixup (tree, node);
565 #ifdef G_ENABLE_DEBUG
566 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
568 g_print ("_gtk_rbtree_insert_before finished...\n");
569 _gtk_rbtree_debug_spew (tree);
571 _gtk_rbtree_test (G_STRLOC, tree);
573 #endif /* G_ENABLE_DEBUG */
579 _gtk_rbtree_find_count (GtkRBTree *tree,
585 while (node != tree->nil && (node->left->count + 1 != count))
587 if (node->left->count >= count)
591 count -= (node->left->count + 1);
595 if (node == tree->nil)
601 _gtk_rbtree_node_set_height (GtkRBTree *tree,
605 gint diff = height - GTK_RBNODE_GET_HEIGHT (node);
610 gtk_rbnode_adjust (tree, node, 0, 0, diff);
612 #ifdef G_ENABLE_DEBUG
613 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
614 _gtk_rbtree_test (G_STRLOC, tree);
619 _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
622 if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
625 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
628 if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))
630 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
632 if (node == tree->nil)
634 node = tree->parent_node;
635 tree = tree->parent_tree;
642 /* Draconian version. */
644 _gtk_rbtree_node_mark_invalid (GtkRBTree *tree,
647 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
650 _fixup_validation (tree, node);
652 if (node == tree->nil)
654 node = tree->parent_node;
655 tree = tree->parent_tree;
663 _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
666 if ((!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) &&
667 (!GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)))
670 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
671 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
675 if ((GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)) ||
676 (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID)) ||
677 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)) ||
678 (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
679 (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)))
682 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
684 if (node == tree->nil)
686 node = tree->parent_node;
687 tree = tree->parent_tree;
694 /* Draconian version */
696 _gtk_rbtree_node_mark_valid (GtkRBTree *tree,
699 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_INVALID);
700 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
704 _fixup_validation (tree, node);
706 if (node == tree->nil)
708 node = tree->parent_node;
709 tree = tree->parent_tree;
715 /* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above.
718 _gtk_rbtree_column_invalid (GtkRBTree *tree)
727 while (node->left != tree->nil)
732 if (! (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID)))
733 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_COLUMN_INVALID);
734 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
737 _gtk_rbtree_column_invalid (node->children);
739 while ((node = _gtk_rbtree_next (tree, node)) != NULL);
743 _gtk_rbtree_mark_invalid (GtkRBTree *tree)
752 while (node->left != tree->nil)
757 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_INVALID);
758 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
761 _gtk_rbtree_mark_invalid (node->children);
763 while ((node = _gtk_rbtree_next (tree, node)) != NULL);
767 _gtk_rbtree_set_fixed_height (GtkRBTree *tree,
779 while (node->left != tree->nil)
784 if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))
786 _gtk_rbtree_node_set_height (tree, node, height);
788 _gtk_rbtree_node_mark_valid (tree, node);
792 _gtk_rbtree_set_fixed_height (node->children, height, mark_valid);
794 while ((node = _gtk_rbtree_next (tree, node)) != NULL);
797 typedef struct _GtkRBReorder
808 gtk_rbtree_reorder_sort_func (gconstpointer a,
811 return ((GtkRBReorder *) a)->order - ((GtkRBReorder *) b)->order;
815 gtk_rbtree_reorder_invert_func (gconstpointer a,
818 return ((GtkRBReorder *) a)->invert_order - ((GtkRBReorder *) b)->invert_order;
822 gtk_rbtree_reorder_fixup (GtkRBTree *tree,
825 if (node == tree->nil)
828 node->total_count = 1;
830 if (node->left != tree->nil)
832 gtk_rbtree_reorder_fixup (tree, node->left);
833 node->offset += node->left->offset;
834 node->total_count += node->left->total_count;
836 if (node->right != tree->nil)
838 gtk_rbtree_reorder_fixup (tree, node->right);
839 node->offset += node->right->offset;
840 node->total_count += node->right->total_count;
845 node->offset += node->children->root->offset;
846 node->total_count += node->children->root->total_count;
849 if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
850 (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
851 (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
852 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
853 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
855 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
858 /* It basically pulls everything out of the tree, rearranges it, and puts it
859 * back together. Our strategy is to keep the old RBTree intact, and just
860 * rearrange the contents. When that is done, we go through and update the
861 * heights. There is probably a more elegant way to write this function. If
862 * anyone wants to spend the time writing it, patches will be accepted.
865 _gtk_rbtree_reorder (GtkRBTree *tree,
869 GtkRBReorder reorder = { NULL };
874 g_return_if_fail (tree != NULL);
875 g_return_if_fail (length > 0);
876 g_return_if_fail (tree->root->count == length);
878 /* Sort the trees values in the new tree. */
879 array = g_array_sized_new (FALSE, FALSE, sizeof (GtkRBReorder), length);
880 for (i = 0; i < length; i++)
882 reorder.order = new_order[i];
883 reorder.invert_order = i;
884 g_array_append_val (array, reorder);
887 g_array_sort(array, gtk_rbtree_reorder_sort_func);
891 while (node && node->left != tree->nil)
894 for (i = 0; i < length; i++)
896 g_assert (node != tree->nil);
897 g_array_index (array, GtkRBReorder, i).children = node->children;
898 g_array_index (array, GtkRBReorder, i).flags = GTK_RBNODE_NON_COLORS & node->flags;
899 g_array_index (array, GtkRBReorder, i).height = GTK_RBNODE_GET_HEIGHT (node);
901 node = _gtk_rbtree_next (tree, node);
904 g_array_sort (array, gtk_rbtree_reorder_invert_func);
908 while (node && node->left != tree->nil)
911 /* Go through the tree and change the values to the new ones. */
912 for (i = 0; i < length; i++)
914 reorder = g_array_index (array, GtkRBReorder, i);
915 node->children = reorder.children;
917 node->children->parent_node = node;
918 node->flags = GTK_RBNODE_GET_COLOR (node) | reorder.flags;
919 /* We temporarily set the height to this. */
920 node->offset = reorder.height;
921 node = _gtk_rbtree_next (tree, node);
923 gtk_rbtree_reorder_fixup (tree, tree->root);
925 g_array_free (array, TRUE);
930 _gtk_rbtree_node_find_offset (GtkRBTree *tree,
937 g_assert (node->left);
939 retval = node->left->offset;
941 while (tree && node && node != tree->nil)
946 /* Add left branch, plus children, iff we came from the right */
947 if (node->right == last)
948 retval += node->offset - node->right->offset;
950 if (node == tree->nil)
952 node = tree->parent_node;
953 tree = tree->parent_tree;
955 /* Add the parent node, plus the left branch. */
957 retval += node->left->offset + GTK_RBNODE_GET_HEIGHT (node);
964 _gtk_rbtree_node_get_index (GtkRBTree *tree,
971 g_assert (node->left);
973 retval = node->left->total_count;
975 while (tree && node && node != tree->nil)
980 /* Add left branch, plus children, iff we came from the right */
981 if (node->right == last)
982 retval += node->total_count - node->right->total_count;
984 if (node == tree->nil)
986 node = tree->parent_node;
987 tree = tree->parent_tree;
989 /* Add the parent node, plus the left branch. */
991 retval += node->left->total_count + 1; /* 1 == GTK_RBNODE_GET_PARITY() */
999 _gtk_rbtree_real_find_offset (GtkRBTree *tree,
1001 GtkRBTree **new_tree,
1002 GtkRBNode **new_node)
1004 GtkRBNode *tmp_node;
1017 tmp_node = tree->root;
1018 while (tmp_node != tree->nil &&
1019 (tmp_node->left->offset > height ||
1020 (tmp_node->offset - tmp_node->right->offset) < height))
1022 if (tmp_node->left->offset > height)
1023 tmp_node = tmp_node->left;
1026 height -= (tmp_node->offset - tmp_node->right->offset);
1027 tmp_node = tmp_node->right;
1030 if (tmp_node == tree->nil)
1036 if (tmp_node->children)
1038 if ((tmp_node->offset -
1039 tmp_node->right->offset -
1040 tmp_node->children->root->offset) > height)
1043 *new_node = tmp_node;
1044 return (height - tmp_node->left->offset);
1046 return _gtk_rbtree_real_find_offset (tmp_node->children,
1047 height - tmp_node->left->offset -
1049 tmp_node->left->offset -
1050 tmp_node->right->offset -
1051 tmp_node->children->root->offset),
1056 *new_node = tmp_node;
1057 return (height - tmp_node->left->offset);
1061 _gtk_rbtree_find_offset (GtkRBTree *tree,
1063 GtkRBTree **new_tree,
1064 GtkRBNode **new_node)
1069 (height >= tree->root->offset))
1076 return _gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
1080 _gtk_rbtree_find_index (GtkRBTree *tree,
1082 GtkRBTree **new_tree,
1083 GtkRBNode **new_node)
1085 GtkRBNode *tmp_node;
1089 tmp_node = tree->root;
1090 while (tmp_node != tree->nil)
1092 if (tmp_node->left->total_count > index)
1094 tmp_node = tmp_node->left;
1096 else if (tmp_node->total_count - tmp_node->right->total_count <= index)
1098 index -= tmp_node->total_count - tmp_node->right->total_count;
1099 tmp_node = tmp_node->right;
1103 index -= tmp_node->left->total_count;
1107 if (tmp_node == tree->nil)
1116 g_assert (tmp_node->children);
1118 return _gtk_rbtree_find_index (tmp_node->children,
1125 *new_node = tmp_node;
1130 _gtk_rbtree_remove_node (GtkRBTree *tree,
1134 GtkRBTree *tmp_tree;
1135 GtkRBNode *tmp_node;
1138 g_return_if_fail (tree != NULL);
1139 g_return_if_fail (node != NULL);
1142 #ifdef G_ENABLE_DEBUG
1143 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1145 g_print ("\n\n_gtk_rbtree_remove_node: %p\n", node);
1146 _gtk_rbtree_debug_spew (tree);
1147 _gtk_rbtree_test (G_STRLOC, tree);
1149 #endif /* G_ENABLE_DEBUG */
1151 /* make sure we're deleting a node that's actually in the tree */
1152 for (x = node; x->parent != tree->nil; x = x->parent)
1154 g_return_if_fail (x == tree->root);
1156 #ifdef G_ENABLE_DEBUG
1157 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1158 _gtk_rbtree_test (G_STRLOC, tree);
1161 if (node->left == tree->nil || node->right == tree->nil)
1169 while (y->left != tree->nil)
1173 y_height = GTK_RBNODE_GET_HEIGHT (y);
1175 /* x is y's only child, or nil */
1176 if (y->left != tree->nil)
1181 /* remove y from the parent chain */
1182 x->parent = y->parent;
1183 if (y->parent != tree->nil)
1185 if (y == y->parent->left)
1186 y->parent->left = x;
1188 y->parent->right = x;
1195 /* We need to clean up the validity of the tree.
1197 gtk_rbnode_adjust (tree, y,
1199 - (y_height + (y->children?y->children->root->offset:0)));
1205 /* Copy the node over */
1206 if (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)
1207 node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_BLACK);
1209 node->flags = ((y->flags & (GTK_RBNODE_NON_COLORS)) | GTK_RBNODE_RED);
1212 node->children = y->children;
1213 node->children->parent_node = node;
1217 node->children = NULL;
1219 _fixup_validation (tree, node);
1220 _fixup_total_count (tree, node);
1221 /* We want to see how different our height is from the previous node.
1222 * To do this, we compare our current height with our supposed height.
1224 diff = y_height - GTK_RBNODE_GET_HEIGHT (node);
1228 while (tmp_tree && tmp_node && tmp_node != tmp_tree->nil)
1230 tmp_node->offset += diff;
1231 _fixup_validation (tmp_tree, tmp_node);
1232 _fixup_total_count (tmp_tree, tmp_node);
1233 tmp_node = tmp_node->parent;
1234 if (tmp_node == tmp_tree->nil)
1236 tmp_node = tmp_tree->parent_node;
1237 tmp_tree = tmp_tree->parent_tree;
1242 if (GTK_RBNODE_GET_COLOR (y) == GTK_RBNODE_BLACK)
1243 _gtk_rbtree_remove_node_fixup (tree, x);
1244 _gtk_rbnode_free (y);
1246 #ifdef G_ENABLE_DEBUG
1247 if (gtk_get_debug_flags () & GTK_DEBUG_TREE)
1249 g_print ("_gtk_rbtree_remove_node finished...\n");
1250 _gtk_rbtree_debug_spew (tree);
1252 _gtk_rbtree_test (G_STRLOC, tree);
1254 #endif /* G_ENABLE_DEBUG */
1258 _gtk_rbtree_next (GtkRBTree *tree,
1261 g_return_val_if_fail (tree != NULL, NULL);
1262 g_return_val_if_fail (node != NULL, NULL);
1264 /* Case 1: the node's below us. */
1265 if (node->right != tree->nil)
1268 while (node->left != tree->nil)
1273 /* Case 2: it's an ancestor */
1274 while (node->parent != tree->nil)
1276 if (node->parent->right == node)
1277 node = node->parent;
1279 return (node->parent);
1282 /* Case 3: There is no next node */
1287 _gtk_rbtree_prev (GtkRBTree *tree,
1290 g_return_val_if_fail (tree != NULL, NULL);
1291 g_return_val_if_fail (node != NULL, NULL);
1293 /* Case 1: the node's below us. */
1294 if (node->left != tree->nil)
1297 while (node->right != tree->nil)
1302 /* Case 2: it's an ancestor */
1303 while (node->parent != tree->nil)
1305 if (node->parent->left == node)
1306 node = node->parent;
1308 return (node->parent);
1311 /* Case 3: There is no next node */
1316 _gtk_rbtree_next_full (GtkRBTree *tree,
1318 GtkRBTree **new_tree,
1319 GtkRBNode **new_node)
1321 g_return_if_fail (tree != NULL);
1322 g_return_if_fail (node != NULL);
1323 g_return_if_fail (new_tree != NULL);
1324 g_return_if_fail (new_node != NULL);
1328 *new_tree = node->children;
1329 *new_node = (*new_tree)->root;
1330 while ((*new_node)->left != (*new_tree)->nil)
1331 *new_node = (*new_node)->left;
1336 *new_node = _gtk_rbtree_next (tree, node);
1338 while ((*new_node == NULL) &&
1339 (*new_tree != NULL))
1341 *new_node = (*new_tree)->parent_node;
1342 *new_tree = (*new_tree)->parent_tree;
1344 *new_node = _gtk_rbtree_next (*new_tree, *new_node);
1349 _gtk_rbtree_prev_full (GtkRBTree *tree,
1351 GtkRBTree **new_tree,
1352 GtkRBNode **new_node)
1354 g_return_if_fail (tree != NULL);
1355 g_return_if_fail (node != NULL);
1356 g_return_if_fail (new_tree != NULL);
1357 g_return_if_fail (new_node != NULL);
1360 *new_node = _gtk_rbtree_prev (tree, node);
1362 if (*new_node == NULL)
1364 *new_node = (*new_tree)->parent_node;
1365 *new_tree = (*new_tree)->parent_tree;
1369 while ((*new_node)->children)
1371 *new_tree = (*new_node)->children;
1372 *new_node = (*new_tree)->root;
1373 while ((*new_node)->right != (*new_tree)->nil)
1374 *new_node = (*new_node)->right;
1380 _gtk_rbtree_get_depth (GtkRBTree *tree)
1382 GtkRBTree *tmp_tree;
1385 tmp_tree = tree->parent_tree;
1389 tmp_tree = tmp_tree->parent_tree;
1396 _gtk_rbtree_traverse_pre_order (GtkRBTree *tree,
1398 GtkRBTreeTraverseFunc func,
1401 if (node == tree->nil)
1404 (* func) (tree, node, data);
1405 _gtk_rbtree_traverse_pre_order (tree, node->left, func, data);
1406 _gtk_rbtree_traverse_pre_order (tree, node->right, func, data);
1410 _gtk_rbtree_traverse_post_order (GtkRBTree *tree,
1412 GtkRBTreeTraverseFunc func,
1415 if (node == tree->nil)
1418 _gtk_rbtree_traverse_post_order (tree, node->left, func, data);
1419 _gtk_rbtree_traverse_post_order (tree, node->right, func, data);
1420 (* func) (tree, node, data);
1424 _gtk_rbtree_traverse (GtkRBTree *tree,
1426 GTraverseType order,
1427 GtkRBTreeTraverseFunc func,
1430 g_return_if_fail (tree != NULL);
1431 g_return_if_fail (node != NULL);
1432 g_return_if_fail (func != NULL);
1433 g_return_if_fail (order <= G_LEVEL_ORDER);
1438 _gtk_rbtree_traverse_pre_order (tree, node, func, data);
1441 _gtk_rbtree_traverse_post_order (tree, node, func, data);
1446 g_warning ("unsupported traversal order.");
1452 void _fixup_validation (GtkRBTree *tree,
1455 if (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1456 GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1457 (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1458 (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1459 (node->children != NULL && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)))
1461 GTK_RBNODE_SET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1465 GTK_RBNODE_UNSET_FLAG (node, GTK_RBNODE_DESCENDANTS_INVALID);
1470 void _fixup_total_count (GtkRBTree *tree,
1473 node->total_count = 1 +
1474 (node->children != NULL ? node->children->root->total_count : 0) +
1475 node->left->total_count + node->right->total_count;
1478 #ifdef G_ENABLE_DEBUG
1480 get_total_count (GtkRBNode *node)
1482 guint child_total = 0;
1484 child_total += (guint) node->left->total_count;
1485 child_total += (guint) node->right->total_count;
1488 child_total += (guint) node->children->root->total_count;
1490 return child_total + 1;
1494 count_total (GtkRBTree *tree,
1499 if (node == tree->nil)
1503 count_total (tree, node->left) +
1504 count_total (tree, node->right) +
1506 (node->children ? count_total (node->children, node->children->root) : 0);
1508 if (res != node->total_count)
1509 g_print ("total count incorrect for node\n");
1511 if (get_total_count (node) != node->total_count)
1512 g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
1518 _count_nodes (GtkRBTree *tree,
1522 if (node == tree->nil)
1525 g_assert (node->left);
1526 g_assert (node->right);
1528 res = (_count_nodes (tree, node->left) +
1529 _count_nodes (tree, node->right) + 1);
1531 if (res != node->count)
1532 g_print ("Tree failed\n");
1537 _gtk_rbtree_test_height (GtkRBTree *tree,
1540 gint computed_offset = 0;
1542 /* This whole test is sort of a useless truism. */
1544 if (node->left != tree->nil)
1545 computed_offset += node->left->offset;
1547 if (node->right != tree->nil)
1548 computed_offset += node->right->offset;
1550 if (node->children && node->children->root != node->children->nil)
1551 computed_offset += node->children->root->offset;
1553 if (GTK_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1554 g_error ("node has broken offset\n");
1556 if (node->left != tree->nil)
1557 _gtk_rbtree_test_height (tree, node->left);
1559 if (node->right != tree->nil)
1560 _gtk_rbtree_test_height (tree, node->right);
1562 if (node->children && node->children->root != node->children->nil)
1563 _gtk_rbtree_test_height (node->children, node->children->root);
1567 _gtk_rbtree_test_dirty (GtkRBTree *tree,
1569 gint expected_dirtyness)
1572 if (expected_dirtyness)
1574 g_assert (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) ||
1575 GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID) ||
1576 (node->left != tree->nil && GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1577 (node->right != tree->nil && GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID)) ||
1578 (node->children && GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID)));
1582 g_assert (! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID) &&
1583 ! GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID));
1584 if (node->left != tree->nil)
1585 g_assert (! GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1586 if (node->right != tree->nil)
1587 g_assert (! GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1588 if (node->children != NULL)
1589 g_assert (! GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1592 if (node->left != tree->nil)
1593 _gtk_rbtree_test_dirty (tree, node->left, GTK_RBNODE_FLAG_SET (node->left, GTK_RBNODE_DESCENDANTS_INVALID));
1594 if (node->right != tree->nil)
1595 _gtk_rbtree_test_dirty (tree, node->right, GTK_RBNODE_FLAG_SET (node->right, GTK_RBNODE_DESCENDANTS_INVALID));
1596 if (node->children != NULL && node->children->root != node->children->nil)
1597 _gtk_rbtree_test_dirty (node->children, node->children->root, GTK_RBNODE_FLAG_SET (node->children->root, GTK_RBNODE_DESCENDANTS_INVALID));
1600 static void _gtk_rbtree_test_structure (GtkRBTree *tree);
1603 _gtk_rbtree_test_structure_helper (GtkRBTree *tree,
1606 g_assert (node != tree->nil);
1608 g_assert (node->left != NULL);
1609 g_assert (node->right != NULL);
1610 g_assert (node->parent != NULL);
1612 if (node->left != tree->nil)
1614 g_assert (node->left->parent == node);
1615 _gtk_rbtree_test_structure_helper (tree, node->left);
1617 if (node->right != tree->nil)
1619 g_assert (node->right->parent == node);
1620 _gtk_rbtree_test_structure_helper (tree, node->right);
1623 if (node->children != NULL)
1625 g_assert (node->children->parent_tree == tree);
1626 g_assert (node->children->parent_node == node);
1628 _gtk_rbtree_test_structure (node->children);
1632 _gtk_rbtree_test_structure (GtkRBTree *tree)
1634 g_assert (tree->root);
1635 if (tree->root == tree->nil)
1638 g_assert (tree->root->parent == tree->nil);
1639 _gtk_rbtree_test_structure_helper (tree, tree->root);
1643 _gtk_rbtree_test (const gchar *where,
1646 GtkRBTree *tmp_tree;
1651 /* Test the entire tree */
1653 while (tmp_tree->parent_tree)
1654 tmp_tree = tmp_tree->parent_tree;
1656 g_assert (tmp_tree->nil != NULL);
1658 if (tmp_tree->root == tmp_tree->nil)
1661 _gtk_rbtree_test_structure (tmp_tree);
1663 g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1664 _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1667 _gtk_rbtree_test_height (tmp_tree, tmp_tree->root);
1668 _gtk_rbtree_test_dirty (tmp_tree, tmp_tree->root, GTK_RBNODE_FLAG_SET (tmp_tree->root, GTK_RBNODE_DESCENDANTS_INVALID));
1669 g_assert (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count);
1673 _gtk_rbtree_debug_spew_helper (GtkRBTree *tree,
1678 for (i = 0; i < depth; i++)
1681 g_print ("(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
1683 (GTK_RBNODE_GET_COLOR (node) == GTK_RBNODE_BLACK)?"BLACK":" RED ",
1686 (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_DESCENDANTS_INVALID))?1:0,
1687 (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_INVALID))?1:0,
1688 (GTK_RBNODE_FLAG_SET (node, GTK_RBNODE_COLUMN_INVALID))?1:0);
1689 if (node->children != NULL)
1691 g_print ("Looking at child.\n");
1692 _gtk_rbtree_debug_spew (node->children);
1693 g_print ("Done looking at child.\n");
1695 if (node->left != tree->nil)
1697 _gtk_rbtree_debug_spew_helper (tree, node->left, depth+1);
1699 if (node->right != tree->nil)
1701 _gtk_rbtree_debug_spew_helper (tree, node->right, depth+1);
1706 _gtk_rbtree_debug_spew (GtkRBTree *tree)
1708 g_return_if_fail (tree != NULL);
1710 if (tree->root == tree->nil)
1711 g_print ("Empty tree...\n");
1713 _gtk_rbtree_debug_spew_helper (tree, tree->root, 0);
1715 #endif /* G_ENABLE_DEBUG */