1/* gtktreerbtree.c
2 * Copyright (C) 2000 Red Hat, Inc., Jonathan Blandford <jrb@redhat.com>
3 *
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.
8 *
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.
13 *
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/>.
16 */
17
18#include "config.h"
19#include "gtktreerbtreeprivate.h"
20#include "gtkdebug.h"
21
22static GtkTreeRBNode *gtk_tree_rbnode_new (GtkTreeRBTree *tree,
23 int height);
24static void gtk_tree_rbnode_free (GtkTreeRBNode *node);
25static void gtk_tree_rbnode_rotate_left (GtkTreeRBTree *tree,
26 GtkTreeRBNode *node);
27static void gtk_tree_rbnode_rotate_right (GtkTreeRBTree *tree,
28 GtkTreeRBNode *node);
29static void gtk_tree_rbtree_insert_fixup (GtkTreeRBTree *tree,
30 GtkTreeRBNode *node);
31static void gtk_tree_rbtree_remove_node_fixup (GtkTreeRBTree *tree,
32 GtkTreeRBNode *node,
33 GtkTreeRBNode *parent);
34static inline void fixup_validation (GtkTreeRBTree *tree,
35 GtkTreeRBNode *node);
36static inline void fixup_total_count (GtkTreeRBTree *tree,
37 GtkTreeRBNode *node);
38#ifdef G_ENABLE_DEBUG
39static void gtk_tree_rbtree_test (const char *where,
40 GtkTreeRBTree *tree);
41static void gtk_tree_rbtree_debug_spew (GtkTreeRBTree *tree,
42 GString *s);
43#endif
44
45static const GtkTreeRBNode nil =
46{
47 /* .flags = */ GTK_TREE_RBNODE_BLACK,
48
49 /* rest is NULL */
50};
51
52gboolean
53gtk_tree_rbtree_is_nil (GtkTreeRBNode *node)
54{
55 return node == &nil;
56}
57
58static GtkTreeRBNode *
59gtk_tree_rbnode_new (GtkTreeRBTree *tree,
60 int height)
61{
62 GtkTreeRBNode *node = g_slice_new (GtkTreeRBNode);
63
64 node->left = (GtkTreeRBNode *) &nil;
65 node->right = (GtkTreeRBNode *) &nil;
66 node->parent = (GtkTreeRBNode *) &nil;
67 node->flags = GTK_TREE_RBNODE_RED;
68 node->total_count = 1;
69 node->count = 1;
70 node->children = NULL;
71 node->offset = height;
72 return node;
73}
74
75static void
76gtk_tree_rbnode_free (GtkTreeRBNode *node)
77{
78#ifdef G_ENABLE_DEBUG
79 if (GTK_DEBUG_CHECK (TREE))
80 {
81 node->left = (gpointer) 0xdeadbeef;
82 node->right = (gpointer) 0xdeadbeef;
83 node->parent = (gpointer) 0xdeadbeef;
84 node->total_count = 56789;
85 node->offset = 56789;
86 node->count = 56789;
87 node->flags = 0;
88 }
89#endif
90 g_slice_free (GtkTreeRBNode, node);
91}
92
93static void
94gtk_tree_rbnode_rotate_left (GtkTreeRBTree *tree,
95 GtkTreeRBNode *node)
96{
97 int node_height, right_height;
98 GtkTreeRBNode *right;
99
100 g_return_if_fail (!gtk_tree_rbtree_is_nil (node));
101 g_return_if_fail (!gtk_tree_rbtree_is_nil (node->right));
102
103 right = node->right;
104
105 node_height = GTK_TREE_RBNODE_GET_HEIGHT (node);
106 right_height = GTK_TREE_RBNODE_GET_HEIGHT (right);
107 node->right = right->left;
108 if (!gtk_tree_rbtree_is_nil (node: right->left))
109 right->left->parent = node;
110
111 right->parent = node->parent;
112 if (!gtk_tree_rbtree_is_nil (node: node->parent))
113 {
114 if (node == node->parent->left)
115 node->parent->left = right;
116 else
117 node->parent->right = right;
118 }
119 else
120 {
121 tree->root = right;
122 }
123
124 right->left = node;
125 node->parent = right;
126
127 node->count = 1 + node->left->count + node->right->count;
128 right->count = 1 + right->left->count + right->right->count;
129
130 node->offset = node_height + node->left->offset + node->right->offset +
131 (node->children ? node->children->root->offset : 0);
132 right->offset = right_height + right->left->offset + right->right->offset +
133 (right->children ? right->children->root->offset : 0);
134
135 fixup_validation (tree, node);
136 fixup_validation (tree, node: right);
137 fixup_total_count (tree, node);
138 fixup_total_count (tree, node: right);
139}
140
141static void
142gtk_tree_rbnode_rotate_right (GtkTreeRBTree *tree,
143 GtkTreeRBNode *node)
144{
145 int node_height, left_height;
146 GtkTreeRBNode *left;
147
148 g_return_if_fail (!gtk_tree_rbtree_is_nil (node));
149 g_return_if_fail (!gtk_tree_rbtree_is_nil (node->left));
150
151 left = node->left;
152
153 node_height = GTK_TREE_RBNODE_GET_HEIGHT (node);
154 left_height = GTK_TREE_RBNODE_GET_HEIGHT (left);
155
156 node->left = left->right;
157 if (!gtk_tree_rbtree_is_nil (node: left->right))
158 left->right->parent = node;
159
160 left->parent = node->parent;
161 if (!gtk_tree_rbtree_is_nil (node: node->parent))
162 {
163 if (node == node->parent->right)
164 node->parent->right = left;
165 else
166 node->parent->left = left;
167 }
168 else
169 {
170 tree->root = left;
171 }
172
173 /* link node and left */
174 left->right = node;
175 node->parent = left;
176
177 node->count = 1 + node->left->count + node->right->count;
178 left->count = 1 + left->left->count + left->right->count;
179
180 node->offset = node_height + node->left->offset + node->right->offset +
181 (node->children ? node->children->root->offset : 0);
182 left->offset = left_height + left->left->offset + left->right->offset +
183 (left->children ? left->children->root->offset : 0);
184
185 fixup_validation (tree, node);
186 fixup_validation (tree, node: left);
187 fixup_total_count (tree, node);
188 fixup_total_count (tree, node: left);
189}
190
191static void
192gtk_tree_rbtree_insert_fixup (GtkTreeRBTree *tree,
193 GtkTreeRBNode *node)
194{
195 /* check Red-Black properties */
196 while (node != tree->root && GTK_TREE_RBNODE_GET_COLOR (node->parent) == GTK_TREE_RBNODE_RED)
197 {
198 /* we have a violation */
199 if (node->parent == node->parent->parent->left)
200 {
201 GtkTreeRBNode *y = node->parent->parent->right;
202 if (GTK_TREE_RBNODE_GET_COLOR (y) == GTK_TREE_RBNODE_RED)
203 {
204 /* uncle is GTK_TREE_RBNODE_RED */
205 GTK_TREE_RBNODE_SET_COLOR (node->parent, GTK_TREE_RBNODE_BLACK);
206 GTK_TREE_RBNODE_SET_COLOR (y, GTK_TREE_RBNODE_BLACK);
207 GTK_TREE_RBNODE_SET_COLOR (node->parent->parent, GTK_TREE_RBNODE_RED);
208 node = node->parent->parent;
209 }
210 else
211 {
212 /* uncle is GTK_TREE_RBNODE_BLACK */
213 if (node == node->parent->right)
214 {
215 /* make node a left child */
216 node = node->parent;
217 gtk_tree_rbnode_rotate_left (tree, node);
218 }
219
220 /* recolor and rotate */
221 GTK_TREE_RBNODE_SET_COLOR (node->parent, GTK_TREE_RBNODE_BLACK);
222 GTK_TREE_RBNODE_SET_COLOR (node->parent->parent, GTK_TREE_RBNODE_RED);
223 gtk_tree_rbnode_rotate_right (tree, node: node->parent->parent);
224 }
225 }
226 else
227 {
228 /* mirror image of above code */
229 GtkTreeRBNode *y = node->parent->parent->left;
230 if (GTK_TREE_RBNODE_GET_COLOR (y) == GTK_TREE_RBNODE_RED)
231 {
232 /* uncle is GTK_TREE_RBNODE_RED */
233 GTK_TREE_RBNODE_SET_COLOR (node->parent, GTK_TREE_RBNODE_BLACK);
234 GTK_TREE_RBNODE_SET_COLOR (y, GTK_TREE_RBNODE_BLACK);
235 GTK_TREE_RBNODE_SET_COLOR (node->parent->parent, GTK_TREE_RBNODE_RED);
236 node = node->parent->parent;
237 }
238 else
239 {
240 /* uncle is GTK_TREE_RBNODE_BLACK */
241 if (node == node->parent->left)
242 {
243 node = node->parent;
244 gtk_tree_rbnode_rotate_right (tree, node);
245 }
246 GTK_TREE_RBNODE_SET_COLOR (node->parent, GTK_TREE_RBNODE_BLACK);
247 GTK_TREE_RBNODE_SET_COLOR (node->parent->parent, GTK_TREE_RBNODE_RED);
248 gtk_tree_rbnode_rotate_left (tree, node: node->parent->parent);
249 }
250 }
251 }
252 GTK_TREE_RBNODE_SET_COLOR (tree->root, GTK_TREE_RBNODE_BLACK);
253}
254
255static void
256gtk_tree_rbtree_remove_node_fixup (GtkTreeRBTree *tree,
257 GtkTreeRBNode *node,
258 GtkTreeRBNode *parent)
259{
260 while (node != tree->root && GTK_TREE_RBNODE_GET_COLOR (node) == GTK_TREE_RBNODE_BLACK)
261 {
262 if (node == parent->left)
263 {
264 GtkTreeRBNode *w = parent->right;
265 if (GTK_TREE_RBNODE_GET_COLOR (w) == GTK_TREE_RBNODE_RED)
266 {
267 GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_BLACK);
268 GTK_TREE_RBNODE_SET_COLOR (parent, GTK_TREE_RBNODE_RED);
269 gtk_tree_rbnode_rotate_left (tree, node: parent);
270 w = parent->right;
271 }
272 g_assert (w);
273 if (GTK_TREE_RBNODE_GET_COLOR (w->left) == GTK_TREE_RBNODE_BLACK && GTK_TREE_RBNODE_GET_COLOR (w->right) == GTK_TREE_RBNODE_BLACK)
274 {
275 GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_RED);
276 node = parent;
277 }
278 else
279 {
280 if (GTK_TREE_RBNODE_GET_COLOR (w->right) == GTK_TREE_RBNODE_BLACK)
281 {
282 GTK_TREE_RBNODE_SET_COLOR (w->left, GTK_TREE_RBNODE_BLACK);
283 GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_RED);
284 gtk_tree_rbnode_rotate_right (tree, node: w);
285 w = parent->right;
286 }
287 GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_GET_COLOR (parent));
288 GTK_TREE_RBNODE_SET_COLOR (parent, GTK_TREE_RBNODE_BLACK);
289 GTK_TREE_RBNODE_SET_COLOR (w->right, GTK_TREE_RBNODE_BLACK);
290 gtk_tree_rbnode_rotate_left (tree, node: parent);
291 node = tree->root;
292 }
293 }
294 else
295 {
296 GtkTreeRBNode *w = parent->left;
297 if (GTK_TREE_RBNODE_GET_COLOR (w) == GTK_TREE_RBNODE_RED)
298 {
299 GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_BLACK);
300 GTK_TREE_RBNODE_SET_COLOR (parent, GTK_TREE_RBNODE_RED);
301 gtk_tree_rbnode_rotate_right (tree, node: parent);
302 w = parent->left;
303 }
304 g_assert (w);
305 if (GTK_TREE_RBNODE_GET_COLOR (w->right) == GTK_TREE_RBNODE_BLACK && GTK_TREE_RBNODE_GET_COLOR (w->left) == GTK_TREE_RBNODE_BLACK)
306 {
307 GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_RED);
308 node = parent;
309 }
310 else
311 {
312 if (GTK_TREE_RBNODE_GET_COLOR (w->left) == GTK_TREE_RBNODE_BLACK)
313 {
314 GTK_TREE_RBNODE_SET_COLOR (w->right, GTK_TREE_RBNODE_BLACK);
315 GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_RED);
316 gtk_tree_rbnode_rotate_left (tree, node: w);
317 w = parent->left;
318 }
319 GTK_TREE_RBNODE_SET_COLOR (w, GTK_TREE_RBNODE_GET_COLOR (parent));
320 GTK_TREE_RBNODE_SET_COLOR (parent, GTK_TREE_RBNODE_BLACK);
321 GTK_TREE_RBNODE_SET_COLOR (w->left, GTK_TREE_RBNODE_BLACK);
322 gtk_tree_rbnode_rotate_right (tree, node: parent);
323 node = tree->root;
324 }
325 }
326
327 parent = node->parent;
328 }
329 GTK_TREE_RBNODE_SET_COLOR (node, GTK_TREE_RBNODE_BLACK);
330}
331
332GtkTreeRBTree *
333gtk_tree_rbtree_new (void)
334{
335 GtkTreeRBTree *retval;
336
337 retval = g_new (GtkTreeRBTree, 1);
338 retval->parent_tree = NULL;
339 retval->parent_node = NULL;
340
341 retval->root = (GtkTreeRBNode *) &nil;
342
343 return retval;
344}
345
346static void
347gtk_tree_rbtree_free_helper (GtkTreeRBTree *tree,
348 GtkTreeRBNode *node,
349 gpointer data)
350{
351 if (node->children)
352 gtk_tree_rbtree_free (tree: node->children);
353
354 gtk_tree_rbnode_free (node);
355}
356
357void
358gtk_tree_rbtree_free (GtkTreeRBTree *tree)
359{
360 gtk_tree_rbtree_traverse (tree,
361 node: tree->root,
362 order: G_POST_ORDER,
363 func: gtk_tree_rbtree_free_helper,
364 NULL);
365
366 if (tree->parent_node &&
367 tree->parent_node->children == tree)
368 tree->parent_node->children = NULL;
369 g_free (mem: tree);
370}
371
372static void
373gtk_rbnode_adjust (GtkTreeRBTree *tree,
374 GtkTreeRBNode *node,
375 int count_diff,
376 int total_count_diff,
377 int offset_diff)
378{
379 while (tree && node && !gtk_tree_rbtree_is_nil (node))
380 {
381 fixup_validation (tree, node);
382 node->offset += offset_diff;
383 node->count += count_diff;
384 node->total_count += total_count_diff;
385
386 node = node->parent;
387 if (gtk_tree_rbtree_is_nil (node))
388 {
389 node = tree->parent_node;
390 tree = tree->parent_tree;
391 count_diff = 0;
392 }
393 }
394}
395
396void
397gtk_tree_rbtree_remove (GtkTreeRBTree *tree)
398{
399#ifdef G_ENABLE_DEBUG
400 GtkTreeRBTree *tmp_tree;
401
402 if (GTK_DEBUG_CHECK (TREE))
403 gtk_tree_rbtree_test (G_STRLOC, tree);
404#endif
405
406 /* ugly hack to make fixup_validation work in the first iteration of the
407 * loop below */
408 GTK_TREE_RBNODE_UNSET_FLAG (tree->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
409
410 gtk_rbnode_adjust (tree: tree->parent_tree,
411 node: tree->parent_node,
412 count_diff: 0,
413 total_count_diff: -(int) tree->root->total_count,
414 offset_diff: -tree->root->offset);
415
416#ifdef G_ENABLE_DEBUG
417 tmp_tree = tree->parent_tree;
418#endif
419
420 gtk_tree_rbtree_free (tree);
421
422#ifdef G_ENABLE_DEBUG
423 if (GTK_DEBUG_CHECK (TREE))
424 gtk_tree_rbtree_test (G_STRLOC, tree: tmp_tree);
425#endif
426}
427
428
429GtkTreeRBNode *
430gtk_tree_rbtree_insert_after (GtkTreeRBTree *tree,
431 GtkTreeRBNode *current,
432 int height,
433 gboolean valid)
434{
435 GtkTreeRBNode *node;
436 gboolean right = TRUE;
437
438#ifdef G_ENABLE_DEBUG
439 if (GTK_DEBUG_CHECK (TREE))
440 {
441 GString *s;
442
443 s = g_string_new (init: "");
444 g_string_append_printf (string: s, format: "gtk_tree_rbtree_insert_after: %p\n", current);
445 gtk_tree_rbtree_debug_spew (tree, s);
446 g_message ("%s", s->str);
447 g_string_free (string: s, TRUE);
448 gtk_tree_rbtree_test (G_STRLOC, tree);
449 }
450#endif
451
452 if (current != NULL && !gtk_tree_rbtree_is_nil (node: current->right))
453 {
454 current = current->right;
455 while (!gtk_tree_rbtree_is_nil (node: current->left))
456 current = current->left;
457 right = FALSE;
458 }
459 /* setup new node */
460 node = gtk_tree_rbnode_new (tree, height);
461
462 /* insert node in tree */
463 if (current)
464 {
465 node->parent = current;
466 if (right)
467 current->right = node;
468 else
469 current->left = node;
470 gtk_rbnode_adjust (tree, node: node->parent,
471 count_diff: 1, total_count_diff: 1, offset_diff: height);
472 }
473 else
474 {
475 g_assert (gtk_tree_rbtree_is_nil (tree->root));
476 tree->root = node;
477 gtk_rbnode_adjust (tree: tree->parent_tree, node: tree->parent_node,
478 count_diff: 0, total_count_diff: 1, offset_diff: height);
479 }
480
481 if (valid)
482 gtk_tree_rbtree_node_mark_valid (tree, node);
483 else
484 gtk_tree_rbtree_node_mark_invalid (tree, node);
485
486 gtk_tree_rbtree_insert_fixup (tree, node);
487
488#ifdef G_ENABLE_DEBUG
489 if (GTK_DEBUG_CHECK (TREE))
490 {
491 GString *s;
492
493 s = g_string_new (init: "gtk_tree_rbtree_insert_after finished...\n");
494 gtk_tree_rbtree_debug_spew (tree, s);
495 g_message ("%s", s->str);
496 g_string_free (string: s, TRUE);
497 gtk_tree_rbtree_test (G_STRLOC, tree);
498 }
499#endif
500
501 return node;
502}
503
504GtkTreeRBNode *
505gtk_tree_rbtree_insert_before (GtkTreeRBTree *tree,
506 GtkTreeRBNode *current,
507 int height,
508 gboolean valid)
509{
510 GtkTreeRBNode *node;
511 gboolean left = TRUE;
512
513#ifdef G_ENABLE_DEBUG
514 if (GTK_DEBUG_CHECK (TREE))
515 {
516 GString *s;
517
518 s = g_string_new (init: "");
519 g_string_append_printf (string: s, format: "gtk_tree_rbtree_insert_before: %p\n", current);
520 gtk_tree_rbtree_debug_spew (tree, s);
521 g_message ("%s", s->str);
522 g_string_free (string: s, TRUE);
523 gtk_tree_rbtree_test (G_STRLOC, tree);
524 }
525#endif
526
527 if (current != NULL && !gtk_tree_rbtree_is_nil (node: current->left))
528 {
529 current = current->left;
530 while (!gtk_tree_rbtree_is_nil (node: current->right))
531 current = current->right;
532 left = FALSE;
533 }
534
535 /* setup new node */
536 node = gtk_tree_rbnode_new (tree, height);
537
538 /* insert node in tree */
539 if (current)
540 {
541 node->parent = current;
542 if (left)
543 current->left = node;
544 else
545 current->right = node;
546 gtk_rbnode_adjust (tree, node: node->parent,
547 count_diff: 1, total_count_diff: 1, offset_diff: height);
548 }
549 else
550 {
551 g_assert (gtk_tree_rbtree_is_nil (tree->root));
552 tree->root = node;
553 gtk_rbnode_adjust (tree: tree->parent_tree, node: tree->parent_node,
554 count_diff: 0, total_count_diff: 1, offset_diff: height);
555 }
556
557 if (valid)
558 gtk_tree_rbtree_node_mark_valid (tree, node);
559 else
560 gtk_tree_rbtree_node_mark_invalid (tree, node);
561
562 gtk_tree_rbtree_insert_fixup (tree, node);
563
564#ifdef G_ENABLE_DEBUG
565 if (GTK_DEBUG_CHECK (TREE))
566 {
567 GString *s;
568
569 s = g_string_new (init: "gtk_tree_rbtree_insert_before finished...\n");
570 gtk_tree_rbtree_debug_spew (tree, s);
571 g_message ("%s", s->str);
572 g_string_free (string: s, TRUE);
573 gtk_tree_rbtree_test (G_STRLOC, tree);
574 }
575#endif
576
577 return node;
578}
579
580GtkTreeRBNode *
581gtk_tree_rbtree_find_count (GtkTreeRBTree *tree,
582 int count)
583{
584 GtkTreeRBNode *node;
585
586 node = tree->root;
587 while (!gtk_tree_rbtree_is_nil (node) && (node->left->count + 1 != count))
588 {
589 if (node->left->count >= count)
590 node = node->left;
591 else
592 {
593 count -= (node->left->count + 1);
594 node = node->right;
595 }
596 }
597 if (gtk_tree_rbtree_is_nil (node))
598 return NULL;
599 return node;
600}
601
602void
603gtk_tree_rbtree_node_set_height (GtkTreeRBTree *tree,
604 GtkTreeRBNode *node,
605 int height)
606{
607 int diff = height - GTK_TREE_RBNODE_GET_HEIGHT (node);
608
609 if (diff == 0)
610 return;
611
612 gtk_rbnode_adjust (tree, node, count_diff: 0, total_count_diff: 0, offset_diff: diff);
613
614#ifdef G_ENABLE_DEBUG
615 if (GTK_DEBUG_CHECK (TREE))
616 gtk_tree_rbtree_test (G_STRLOC, tree);
617#endif
618}
619
620void
621gtk_tree_rbtree_node_mark_invalid (GtkTreeRBTree *tree,
622 GtkTreeRBNode *node)
623{
624 if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID))
625 return;
626
627 GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_INVALID);
628 do
629 {
630 if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID))
631 return;
632 GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
633 node = node->parent;
634 if (gtk_tree_rbtree_is_nil (node))
635 {
636 node = tree->parent_node;
637 tree = tree->parent_tree;
638 }
639 }
640 while (node);
641}
642
643#if 0
644/* Draconian version. */
645void
646gtk_tree_rbtree_node_mark_invalid (GtkTreeRBTree *tree,
647 GtkTreeRBNode *node)
648{
649 GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_INVALID);
650 do
651 {
652 fixup_validation (tree, node);
653 node = node->parent;
654 if (gtk_tree_rbtree_is_nil (node))
655 {
656 node = tree->parent_node;
657 tree = tree->parent_tree;
658 }
659 }
660 while (node);
661}
662#endif
663
664void
665gtk_tree_rbtree_node_mark_valid (GtkTreeRBTree *tree,
666 GtkTreeRBNode *node)
667{
668 if ((!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID)) &&
669 (!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID)))
670 return;
671
672 GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_INVALID);
673 GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_COLUMN_INVALID);
674
675 do
676 {
677 if ((GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID)) ||
678 (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID)) ||
679 (node->children && GTK_TREE_RBNODE_FLAG_SET (node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID)) ||
680 (GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID)) ||
681 (GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID)))
682 return;
683
684 GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
685 node = node->parent;
686 if (gtk_tree_rbtree_is_nil (node))
687 {
688 node = tree->parent_node;
689 tree = tree->parent_tree;
690 }
691 }
692 while (node);
693}
694
695#if 0
696/* Draconian version */
697void
698gtk_tree_rbtree_node_mark_valid (GtkTreeRBTree *tree,
699 GtkTreeRBNode *node)
700{
701 GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_INVALID);
702 GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_COLUMN_INVALID);
703
704 do
705 {
706 fixup_validation (tree, node);
707 node = node->parent;
708 if (gtk_tree_rbtree_is_nil (node))
709 {
710 node = tree->parent_node;
711 tree = tree->parent_tree;
712 }
713 }
714 while (node);
715}
716#endif
717/* Assume tree is the root node as it doesn't set DESCENDANTS_INVALID above.
718 */
719void
720gtk_tree_rbtree_column_invalid (GtkTreeRBTree *tree)
721{
722 GtkTreeRBNode *node;
723
724 if (tree == NULL)
725 return;
726
727 for (node = gtk_tree_rbtree_first (tree);
728 node != NULL;
729 node = gtk_tree_rbtree_next (tree, node))
730 {
731 if (!(GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID)))
732 GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_COLUMN_INVALID);
733 GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
734
735 if (node->children)
736 gtk_tree_rbtree_column_invalid (tree: node->children);
737 }
738}
739
740void
741gtk_tree_rbtree_mark_invalid (GtkTreeRBTree *tree)
742{
743 GtkTreeRBNode *node;
744
745 if (tree == NULL)
746 return;
747
748 for (node = gtk_tree_rbtree_first (tree);
749 node != NULL;
750 node = gtk_tree_rbtree_next (tree, node))
751 {
752 GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_INVALID);
753 GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
754
755 if (node->children)
756 gtk_tree_rbtree_mark_invalid (tree: node->children);
757 }
758}
759
760void
761gtk_tree_rbtree_set_fixed_height (GtkTreeRBTree *tree,
762 int height,
763 gboolean mark_valid)
764{
765 GtkTreeRBNode *node;
766
767 if (tree == NULL)
768 return;
769
770 for (node = gtk_tree_rbtree_first (tree);
771 node != NULL;
772 node = gtk_tree_rbtree_next (tree, node))
773 {
774 if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID))
775 {
776 gtk_tree_rbtree_node_set_height (tree, node, height);
777 if (mark_valid)
778 gtk_tree_rbtree_node_mark_valid (tree, node);
779 }
780
781 if (node->children)
782 gtk_tree_rbtree_set_fixed_height (tree: node->children, height, mark_valid);
783 }
784}
785
786static void
787reorder_prepare (GtkTreeRBTree *tree,
788 GtkTreeRBNode *node,
789 gpointer data)
790{
791 node->offset -= node->left->offset + node->right->offset;
792 GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
793}
794
795static void
796reorder_fixup (GtkTreeRBTree *tree,
797 GtkTreeRBNode *node,
798 gpointer data)
799{
800 node->offset += node->left->offset + node->right->offset;
801 node->count = 1 + node->left->count + node->right->count;
802 fixup_validation (tree, node);
803 fixup_total_count (tree, node);
804}
805
806static void
807reorder_copy_node (GtkTreeRBTree *tree,
808 GtkTreeRBNode *to,
809 GtkTreeRBNode *from)
810{
811 to->flags = (to->flags & GTK_TREE_RBNODE_NON_COLORS) | GTK_TREE_RBNODE_GET_COLOR (from);
812
813 to->left = from->left;
814 if (!gtk_tree_rbtree_is_nil (node: to->left))
815 to->left->parent = to;
816
817 to->right = from->right;
818 if (!gtk_tree_rbtree_is_nil (node: to->right))
819 to->right->parent = to;
820
821 to->parent = from->parent;
822 if (gtk_tree_rbtree_is_nil (node: to->parent))
823 tree->root = to;
824 else if (to->parent->left == from)
825 to->parent->left = to;
826 else if (to->parent->right == from)
827 to->parent->right = to;
828}
829
830/* It basically pulls everything out of the tree, rearranges it, and puts it
831 * back together. Our strategy is to keep the old RBTree intact, and just
832 * rearrange the contents. When that is done, we go through and update the
833 * heights. There is probably a more elegant way to write this function. If
834 * anyone wants to spend the time writing it, patches will be accepted.
835 */
836void
837gtk_tree_rbtree_reorder (GtkTreeRBTree *tree,
838 int *new_order,
839 int length)
840{
841 GtkTreeRBNode **nodes;
842 GtkTreeRBNode *node;
843 int i, j;
844
845 g_return_if_fail (tree != NULL);
846 g_return_if_fail (length > 0);
847 g_return_if_fail (tree->root->count == length);
848
849 nodes = g_new (GtkTreeRBNode *, length);
850
851 gtk_tree_rbtree_traverse (tree, node: tree->root, order: G_PRE_ORDER, func: reorder_prepare, NULL);
852
853 for (node = gtk_tree_rbtree_first (tree), i = 0;
854 node;
855 node = gtk_tree_rbtree_next (tree, node), i++)
856 {
857 nodes[i] = node;
858 }
859
860 for (i = 0; i < length; i++)
861 {
862 GtkTreeRBNode tmp = { 0, };
863 GSList *l, *cycle = NULL;
864
865 tmp.offset = -1;
866
867 /* already swapped */
868 if (nodes[i] == NULL)
869 continue;
870 /* no need to swap */
871 if (new_order[i] == i)
872 continue;
873
874 /* make a list out of the pending nodes */
875 for (j = i; new_order[j] != i; j = new_order[j])
876 {
877 cycle = g_slist_prepend (list: cycle, data: nodes[j]);
878 nodes[j] = NULL;
879 }
880
881 node = nodes[j];
882 reorder_copy_node (tree, to: &tmp, from: node);
883 for (l = cycle; l; l = l->next)
884 {
885 reorder_copy_node (tree, to: node, from: l->data);
886 node = l->data;
887 }
888
889 reorder_copy_node (tree, to: node, from: &tmp);
890 nodes[j] = NULL;
891 g_slist_free (list: cycle);
892 }
893
894 gtk_tree_rbtree_traverse (tree, node: tree->root, order: G_POST_ORDER, func: reorder_fixup, NULL);
895
896 g_free (mem: nodes);
897}
898
899/**
900 * gtk_tree_rbtree_contains:
901 * @tree: a tree
902 * @potential_child: a potential child of @tree
903 *
904 * Checks if @potential_child is a child (direct or via intermediate
905 * trees) of @tree.
906 *
907 * Returns: %TRUE if @potential_child is a child of @tree.
908 **/
909gboolean
910gtk_tree_rbtree_contains (GtkTreeRBTree *tree,
911 GtkTreeRBTree *potential_child)
912{
913 g_return_val_if_fail (tree != NULL, FALSE);
914 g_return_val_if_fail (potential_child != NULL, FALSE);
915
916 do
917 {
918 potential_child = potential_child->parent_tree;
919 if (potential_child == tree)
920 return TRUE;
921 }
922 while (potential_child != NULL);
923
924 return FALSE;
925}
926
927int
928gtk_tree_rbtree_node_find_offset (GtkTreeRBTree *tree,
929 GtkTreeRBNode *node)
930{
931 GtkTreeRBNode *last;
932 int retval;
933
934 g_assert (node);
935 g_assert (node->left);
936
937 retval = node->left->offset;
938
939 while (tree && node && !gtk_tree_rbtree_is_nil (node))
940 {
941 last = node;
942 node = node->parent;
943
944 /* Add left branch, plus children, iff we came from the right */
945 if (node->right == last)
946 retval += node->offset - node->right->offset;
947
948 if (gtk_tree_rbtree_is_nil (node))
949 {
950 node = tree->parent_node;
951 tree = tree->parent_tree;
952
953 /* Add the parent node, plus the left branch. */
954 if (node)
955 retval += node->left->offset + GTK_TREE_RBNODE_GET_HEIGHT (node);
956 }
957 }
958 return retval;
959}
960
961guint
962gtk_tree_rbtree_node_get_index (GtkTreeRBTree *tree,
963 GtkTreeRBNode *node)
964{
965 GtkTreeRBNode *last;
966 guint retval;
967
968 g_assert (node);
969 g_assert (node->left);
970
971 retval = node->left->total_count;
972
973 while (tree && node && !gtk_tree_rbtree_is_nil (node))
974 {
975 last = node;
976 node = node->parent;
977
978 /* Add left branch, plus children, iff we came from the right */
979 if (node->right == last)
980 retval += node->total_count - node->right->total_count;
981
982 if (gtk_tree_rbtree_is_nil (node))
983 {
984 node = tree->parent_node;
985 tree = tree->parent_tree;
986
987 /* Add the parent node, plus the left branch. */
988 if (node)
989 retval += node->left->total_count + 1; /* 1 == GTK_TREE_RBNODE_GET_PARITY() */
990 }
991 }
992
993 return retval;
994}
995
996static int
997gtk_rbtree_real_find_offset (GtkTreeRBTree *tree,
998 int height,
999 GtkTreeRBTree **new_tree,
1000 GtkTreeRBNode **new_node)
1001{
1002 GtkTreeRBNode *tmp_node;
1003
1004 g_assert (tree);
1005
1006 if (height < 0)
1007 {
1008 *new_tree = NULL;
1009 *new_node = NULL;
1010
1011 return 0;
1012 }
1013
1014
1015 tmp_node = tree->root;
1016 while (!gtk_tree_rbtree_is_nil (node: tmp_node) &&
1017 (tmp_node->left->offset > height ||
1018 (tmp_node->offset - tmp_node->right->offset) < height))
1019 {
1020 if (tmp_node->left->offset > height)
1021 tmp_node = tmp_node->left;
1022 else
1023 {
1024 height -= (tmp_node->offset - tmp_node->right->offset);
1025 tmp_node = tmp_node->right;
1026 }
1027 }
1028 if (gtk_tree_rbtree_is_nil (node: tmp_node))
1029 {
1030 *new_tree = NULL;
1031 *new_node = NULL;
1032 return 0;
1033 }
1034 if (tmp_node->children)
1035 {
1036 if ((tmp_node->offset -
1037 tmp_node->right->offset -
1038 tmp_node->children->root->offset) > height)
1039 {
1040 *new_tree = tree;
1041 *new_node = tmp_node;
1042 return (height - tmp_node->left->offset);
1043 }
1044 return gtk_rbtree_real_find_offset (tree: tmp_node->children,
1045 height: height - tmp_node->left->offset -
1046 (tmp_node->offset -
1047 tmp_node->left->offset -
1048 tmp_node->right->offset -
1049 tmp_node->children->root->offset),
1050 new_tree,
1051 new_node);
1052 }
1053 *new_tree = tree;
1054 *new_node = tmp_node;
1055 return (height - tmp_node->left->offset);
1056}
1057
1058int
1059gtk_tree_rbtree_find_offset (GtkTreeRBTree *tree,
1060 int height,
1061 GtkTreeRBTree **new_tree,
1062 GtkTreeRBNode **new_node)
1063{
1064 g_assert (tree);
1065
1066 if ((height < 0) ||
1067 (height >= tree->root->offset))
1068 {
1069 *new_tree = NULL;
1070 *new_node = NULL;
1071
1072 return 0;
1073 }
1074 return gtk_rbtree_real_find_offset (tree, height, new_tree, new_node);
1075}
1076
1077gboolean
1078gtk_tree_rbtree_find_index (GtkTreeRBTree *tree,
1079 guint index,
1080 GtkTreeRBTree **new_tree,
1081 GtkTreeRBNode **new_node)
1082{
1083 GtkTreeRBNode *tmp_node;
1084
1085 g_assert (tree);
1086
1087 tmp_node = tree->root;
1088 while (!gtk_tree_rbtree_is_nil (node: tmp_node))
1089 {
1090 if (tmp_node->left->total_count > index)
1091 {
1092 tmp_node = tmp_node->left;
1093 }
1094 else if (tmp_node->total_count - tmp_node->right->total_count <= index)
1095 {
1096 index -= tmp_node->total_count - tmp_node->right->total_count;
1097 tmp_node = tmp_node->right;
1098 }
1099 else
1100 {
1101 index -= tmp_node->left->total_count;
1102 break;
1103 }
1104 }
1105 if (gtk_tree_rbtree_is_nil (node: tmp_node))
1106 {
1107 *new_tree = NULL;
1108 *new_node = NULL;
1109 return FALSE;
1110 }
1111
1112 if (index > 0)
1113 {
1114 g_assert (tmp_node->children);
1115
1116 return gtk_tree_rbtree_find_index (tree: tmp_node->children,
1117 index: index - 1,
1118 new_tree,
1119 new_node);
1120 }
1121
1122 *new_tree = tree;
1123 *new_node = tmp_node;
1124 return TRUE;
1125}
1126
1127void
1128gtk_tree_rbtree_remove_node (GtkTreeRBTree *tree,
1129 GtkTreeRBNode *node)
1130{
1131 GtkTreeRBNode *x, *y;
1132 int y_height;
1133 guint y_total_count;
1134
1135 g_return_if_fail (tree != NULL);
1136 g_return_if_fail (node != NULL);
1137
1138
1139#ifdef G_ENABLE_DEBUG
1140 if (GTK_DEBUG_CHECK (TREE))
1141 {
1142 GString *s;
1143
1144 s = g_string_new (init: "");
1145 g_string_append_printf (string: s, format: "gtk_tree_rbtree_remove_node: %p\n", node);
1146 gtk_tree_rbtree_debug_spew (tree, s);
1147 g_message ("%s", s->str);
1148 g_string_free (string: s, TRUE);
1149 gtk_tree_rbtree_test (G_STRLOC, tree);
1150 }
1151#endif
1152
1153 /* make sure we're deleting a node that's actually in the tree */
1154 for (x = node; !gtk_tree_rbtree_is_nil (node: x->parent); x = x->parent)
1155 ;
1156 g_return_if_fail (x == tree->root);
1157
1158#ifdef G_ENABLE_DEBUG
1159 if (GTK_DEBUG_CHECK (TREE))
1160 gtk_tree_rbtree_test (G_STRLOC, tree);
1161#endif
1162
1163 if (gtk_tree_rbtree_is_nil (node: node->left) ||
1164 gtk_tree_rbtree_is_nil (node: node->right))
1165 {
1166 y = node;
1167 }
1168 else
1169 {
1170 y = node->right;
1171
1172 while (!gtk_tree_rbtree_is_nil (node: y->left))
1173 y = y->left;
1174 }
1175
1176 y_height = GTK_TREE_RBNODE_GET_HEIGHT (y)
1177 + (y->children ? y->children->root->offset : 0);
1178 y_total_count = 1 + (y->children ? y->children->root->total_count : 0);
1179
1180 /* x is y's only child, or nil */
1181 if (!gtk_tree_rbtree_is_nil (node: y->left))
1182 x = y->left;
1183 else
1184 x = y->right;
1185
1186 /* remove y from the parent chain */
1187 if (!gtk_tree_rbtree_is_nil (node: x))
1188 x->parent = y->parent;
1189 if (!gtk_tree_rbtree_is_nil (node: y->parent))
1190 {
1191 if (y == y->parent->left)
1192 y->parent->left = x;
1193 else
1194 y->parent->right = x;
1195 }
1196 else
1197 {
1198 tree->root = x;
1199 }
1200
1201 /* We need to clean up the validity of the tree.
1202 */
1203 gtk_rbnode_adjust (tree, node: y, count_diff: -1, total_count_diff: -y_total_count, offset_diff: -y_height);
1204
1205 if (GTK_TREE_RBNODE_GET_COLOR (y) == GTK_TREE_RBNODE_BLACK)
1206 gtk_tree_rbtree_remove_node_fixup (tree, node: x, parent: y->parent);
1207
1208 if (y != node)
1209 {
1210 int node_height, node_total_count;
1211
1212 /* We want to see how much we remove from the aggregate values.
1213 * This is all the children we remove plus the node's values.
1214 */
1215 node_height = GTK_TREE_RBNODE_GET_HEIGHT (node)
1216 + (node->children ? node->children->root->offset : 0);
1217 node_total_count = 1
1218 + (node->children ? node->children->root->total_count : 0);
1219
1220 /* Move the node over */
1221 if (GTK_TREE_RBNODE_GET_COLOR (node) != GTK_TREE_RBNODE_GET_COLOR (y))
1222 y->flags ^= (GTK_TREE_RBNODE_BLACK | GTK_TREE_RBNODE_RED);
1223
1224 y->left = node->left;
1225 if (!gtk_tree_rbtree_is_nil (node: y->left))
1226 y->left->parent = y;
1227 y->right = node->right;
1228 if (!gtk_tree_rbtree_is_nil (node: y->right))
1229 y->right->parent = y;
1230 y->parent = node->parent;
1231 if (!gtk_tree_rbtree_is_nil (node: y->parent))
1232 {
1233 if (y->parent->left == node)
1234 y->parent->left = y;
1235 else
1236 y->parent->right = y;
1237 }
1238 else
1239 {
1240 tree->root = y;
1241 }
1242 y->count = node->count;
1243 y->total_count = node->total_count;
1244 y->offset = node->offset;
1245
1246 gtk_rbnode_adjust (tree, node: y,
1247 count_diff: 0,
1248 total_count_diff: y_total_count - node_total_count,
1249 offset_diff: y_height - node_height);
1250 }
1251
1252 gtk_tree_rbnode_free (node);
1253
1254#ifdef G_ENABLE_DEBUG
1255 if (GTK_DEBUG_CHECK (TREE))
1256 {
1257 GString *s;
1258
1259 s = g_string_new (init: "gtk_tree_rbtree_remove_node finished...\n");
1260 gtk_tree_rbtree_debug_spew (tree, s);
1261 g_message ("%s", s->str);
1262 g_string_free (string: s, TRUE);
1263 gtk_tree_rbtree_test (G_STRLOC, tree);
1264 }
1265#endif
1266}
1267
1268GtkTreeRBNode *
1269gtk_tree_rbtree_first (GtkTreeRBTree *tree)
1270{
1271 GtkTreeRBNode *node;
1272
1273 node = tree->root;
1274
1275 if (gtk_tree_rbtree_is_nil (node))
1276 return NULL;
1277
1278 while (!gtk_tree_rbtree_is_nil (node: node->left))
1279 node = node->left;
1280
1281 return node;
1282}
1283
1284GtkTreeRBNode *
1285gtk_tree_rbtree_next (GtkTreeRBTree *tree,
1286 GtkTreeRBNode *node)
1287{
1288 g_return_val_if_fail (tree != NULL, NULL);
1289 g_return_val_if_fail (node != NULL, NULL);
1290
1291 /* Case 1: the node's below us. */
1292 if (!gtk_tree_rbtree_is_nil (node: node->right))
1293 {
1294 node = node->right;
1295 while (!gtk_tree_rbtree_is_nil (node: node->left))
1296 node = node->left;
1297 return node;
1298 }
1299
1300 /* Case 2: it's an ancestor */
1301 while (!gtk_tree_rbtree_is_nil (node: node->parent))
1302 {
1303 if (node->parent->right == node)
1304 node = node->parent;
1305 else
1306 return (node->parent);
1307 }
1308
1309 /* Case 3: There is no next node */
1310 return NULL;
1311}
1312
1313GtkTreeRBNode *
1314gtk_tree_rbtree_prev (GtkTreeRBTree *tree,
1315 GtkTreeRBNode *node)
1316{
1317 g_return_val_if_fail (tree != NULL, NULL);
1318 g_return_val_if_fail (node != NULL, NULL);
1319
1320 /* Case 1: the node's below us. */
1321 if (!gtk_tree_rbtree_is_nil (node: node->left))
1322 {
1323 node = node->left;
1324 while (!gtk_tree_rbtree_is_nil (node: node->right))
1325 node = node->right;
1326 return node;
1327 }
1328
1329 /* Case 2: it's an ancestor */
1330 while (!gtk_tree_rbtree_is_nil (node: node->parent))
1331 {
1332 if (node->parent->left == node)
1333 node = node->parent;
1334 else
1335 return (node->parent);
1336 }
1337
1338 /* Case 3: There is no next node */
1339 return NULL;
1340}
1341
1342void
1343gtk_tree_rbtree_next_full (GtkTreeRBTree *tree,
1344 GtkTreeRBNode *node,
1345 GtkTreeRBTree **new_tree,
1346 GtkTreeRBNode **new_node)
1347{
1348 g_return_if_fail (tree != NULL);
1349 g_return_if_fail (node != NULL);
1350 g_return_if_fail (new_tree != NULL);
1351 g_return_if_fail (new_node != NULL);
1352
1353 if (node->children)
1354 {
1355 *new_tree = node->children;
1356 *new_node = (*new_tree)->root;
1357 while (!gtk_tree_rbtree_is_nil (node: (*new_node)->left))
1358 *new_node = (*new_node)->left;
1359 return;
1360 }
1361
1362 *new_tree = tree;
1363 *new_node = gtk_tree_rbtree_next (tree, node);
1364
1365 while ((*new_node == NULL) &&
1366 (*new_tree != NULL))
1367 {
1368 *new_node = (*new_tree)->parent_node;
1369 *new_tree = (*new_tree)->parent_tree;
1370 if (*new_tree)
1371 *new_node = gtk_tree_rbtree_next (tree: *new_tree, node: *new_node);
1372 }
1373}
1374
1375void
1376gtk_tree_rbtree_prev_full (GtkTreeRBTree *tree,
1377 GtkTreeRBNode *node,
1378 GtkTreeRBTree **new_tree,
1379 GtkTreeRBNode **new_node)
1380{
1381 g_return_if_fail (tree != NULL);
1382 g_return_if_fail (node != NULL);
1383 g_return_if_fail (new_tree != NULL);
1384 g_return_if_fail (new_node != NULL);
1385
1386 *new_tree = tree;
1387 *new_node = gtk_tree_rbtree_prev (tree, node);
1388
1389 if (*new_node == NULL)
1390 {
1391 *new_node = (*new_tree)->parent_node;
1392 *new_tree = (*new_tree)->parent_tree;
1393 }
1394 else
1395 {
1396 while ((*new_node)->children)
1397 {
1398 *new_tree = (*new_node)->children;
1399 *new_node = (*new_tree)->root;
1400 while (!gtk_tree_rbtree_is_nil (node: (*new_node)->right))
1401 *new_node = (*new_node)->right;
1402 }
1403 }
1404}
1405
1406int
1407gtk_tree_rbtree_get_depth (GtkTreeRBTree *tree)
1408{
1409 GtkTreeRBTree *tmp_tree;
1410 int depth = 0;
1411
1412 tmp_tree = tree->parent_tree;
1413 while (tmp_tree)
1414 {
1415 ++depth;
1416 tmp_tree = tmp_tree->parent_tree;
1417 }
1418
1419 return depth;
1420}
1421
1422static void
1423gtk_tree_rbtree_traverse_pre_order (GtkTreeRBTree *tree,
1424 GtkTreeRBNode *node,
1425 GtkTreeRBTreeTraverseFunc func,
1426 gpointer data)
1427{
1428 if (gtk_tree_rbtree_is_nil (node))
1429 return;
1430
1431 (*func)(tree, node, data);
1432 gtk_tree_rbtree_traverse_pre_order (tree, node: node->left, func, data);
1433 gtk_tree_rbtree_traverse_pre_order (tree, node: node->right, func, data);
1434}
1435
1436static void
1437gtk_tree_rbtree_traverse_post_order (GtkTreeRBTree *tree,
1438 GtkTreeRBNode *node,
1439 GtkTreeRBTreeTraverseFunc func,
1440 gpointer data)
1441{
1442 if (gtk_tree_rbtree_is_nil (node))
1443 return;
1444
1445 gtk_tree_rbtree_traverse_post_order (tree, node: node->left, func, data);
1446 gtk_tree_rbtree_traverse_post_order (tree, node: node->right, func, data);
1447 (*func)(tree, node, data);
1448}
1449
1450void
1451gtk_tree_rbtree_traverse (GtkTreeRBTree *tree,
1452 GtkTreeRBNode *node,
1453 GTraverseType order,
1454 GtkTreeRBTreeTraverseFunc func,
1455 gpointer data)
1456{
1457 g_return_if_fail (tree != NULL);
1458 g_return_if_fail (node != NULL);
1459 g_return_if_fail (func != NULL);
1460 g_return_if_fail (order <= G_LEVEL_ORDER);
1461
1462 switch (order)
1463 {
1464 case G_PRE_ORDER:
1465 gtk_tree_rbtree_traverse_pre_order (tree, node, func, data);
1466 break;
1467
1468 case G_POST_ORDER:
1469 gtk_tree_rbtree_traverse_post_order (tree, node, func, data);
1470 break;
1471
1472 case G_IN_ORDER:
1473 case G_LEVEL_ORDER:
1474 default:
1475 g_warning ("unsupported traversal order.");
1476 break;
1477 }
1478}
1479
1480static inline
1481void fixup_validation (GtkTreeRBTree *tree,
1482 GtkTreeRBNode *node)
1483{
1484 if (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) ||
1485 GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID) ||
1486 GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
1487 GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
1488 (node->children != NULL && GTK_TREE_RBNODE_FLAG_SET (node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID)))
1489 {
1490 GTK_TREE_RBNODE_SET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
1491 }
1492 else
1493 {
1494 GTK_TREE_RBNODE_UNSET_FLAG (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID);
1495 }
1496}
1497
1498static inline
1499void fixup_total_count (GtkTreeRBTree *tree,
1500 GtkTreeRBNode *node)
1501{
1502 node->total_count = 1 +
1503 (node->children != NULL ? node->children->root->total_count : 0) +
1504 node->left->total_count + node->right->total_count;
1505}
1506
1507#ifdef G_ENABLE_DEBUG
1508static guint
1509get_total_count (GtkTreeRBNode *node)
1510{
1511 guint child_total = 0;
1512
1513 child_total += (guint) node->left->total_count;
1514 child_total += (guint) node->right->total_count;
1515
1516 if (node->children)
1517 child_total += (guint) node->children->root->total_count;
1518
1519 return child_total + 1;
1520}
1521
1522static guint
1523count_total (GtkTreeRBTree *tree,
1524 GtkTreeRBNode *node)
1525{
1526 guint res;
1527
1528 if (gtk_tree_rbtree_is_nil (node))
1529 return 0;
1530
1531 res =
1532 count_total (tree, node: node->left) +
1533 count_total (tree, node: node->right) +
1534 (guint) 1 +
1535 (node->children ? count_total (tree: node->children, node: node->children->root) : 0);
1536
1537 if (res != node->total_count)
1538 g_error ("total count incorrect for node");
1539
1540 if (get_total_count (node) != node->total_count)
1541 g_error ("Node has incorrect total count %u, should be %u", node->total_count, get_total_count (node));
1542
1543 return res;
1544}
1545
1546static int
1547_count_nodes (GtkTreeRBTree *tree,
1548 GtkTreeRBNode *node)
1549{
1550 int res;
1551 if (gtk_tree_rbtree_is_nil (node))
1552 return 0;
1553
1554 g_assert (node->left);
1555 g_assert (node->right);
1556
1557 res = (_count_nodes (tree, node: node->left) +
1558 _count_nodes (tree, node: node->right) + 1);
1559
1560 if (res != node->count)
1561 g_error ("Tree failed");
1562 return res;
1563}
1564
1565static void
1566gtk_tree_rbtree_test_height (GtkTreeRBTree *tree,
1567 GtkTreeRBNode *node)
1568{
1569 int computed_offset = 0;
1570
1571 /* This whole test is sort of a useless truism. */
1572
1573 if (!gtk_tree_rbtree_is_nil (node: node->left))
1574 computed_offset += node->left->offset;
1575
1576 if (!gtk_tree_rbtree_is_nil (node: node->right))
1577 computed_offset += node->right->offset;
1578
1579 if (node->children && !gtk_tree_rbtree_is_nil (node: node->children->root))
1580 computed_offset += node->children->root->offset;
1581
1582 if (GTK_TREE_RBNODE_GET_HEIGHT (node) + computed_offset != node->offset)
1583 g_error ("node has broken offset");
1584
1585 if (!gtk_tree_rbtree_is_nil (node: node->left))
1586 gtk_tree_rbtree_test_height (tree, node: node->left);
1587
1588 if (!gtk_tree_rbtree_is_nil (node: node->right))
1589 gtk_tree_rbtree_test_height (tree, node: node->right);
1590
1591 if (node->children && !gtk_tree_rbtree_is_nil (node: node->children->root))
1592 gtk_tree_rbtree_test_height (tree: node->children, node: node->children->root);
1593}
1594
1595static void
1596gtk_tree_rbtree_test_dirty (GtkTreeRBTree *tree,
1597 GtkTreeRBNode *node,
1598 int expected_dirtyness)
1599{
1600 g_assert (node);
1601
1602 if (expected_dirtyness)
1603 {
1604 g_assert (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID) ||
1605 GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID) ||
1606 GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
1607 GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID) ||
1608 (node->children && GTK_TREE_RBNODE_FLAG_SET (node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID)));
1609 }
1610 else
1611 {
1612 g_assert (!GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID) &&
1613 !GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID));
1614 if (!gtk_tree_rbtree_is_nil (node: node->left))
1615 g_assert (!GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
1616 if (!gtk_tree_rbtree_is_nil (node: node->right))
1617 g_assert (!GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
1618 if (node->children != NULL)
1619 g_assert (!GTK_TREE_RBNODE_FLAG_SET (node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
1620 }
1621
1622 if (!gtk_tree_rbtree_is_nil (node: node->left))
1623 gtk_tree_rbtree_test_dirty (tree, node: node->left, GTK_TREE_RBNODE_FLAG_SET (node->left, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
1624 if (!gtk_tree_rbtree_is_nil (node: node->right))
1625 gtk_tree_rbtree_test_dirty (tree, node: node->right, GTK_TREE_RBNODE_FLAG_SET (node->right, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
1626 if (node->children != NULL && !gtk_tree_rbtree_is_nil (node: node->children->root))
1627 gtk_tree_rbtree_test_dirty (tree: node->children, node: node->children->root, GTK_TREE_RBNODE_FLAG_SET (node->children->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
1628}
1629
1630static void gtk_tree_rbtree_test_structure (GtkTreeRBTree *tree);
1631
1632static void
1633gtk_tree_rbtree_test_structure_helper (GtkTreeRBTree *tree,
1634 GtkTreeRBNode *node)
1635{
1636 g_assert (!gtk_tree_rbtree_is_nil (node));
1637
1638 g_assert (node->left != NULL);
1639 g_assert (node->right != NULL);
1640 g_assert (node->parent != NULL);
1641
1642 if (!gtk_tree_rbtree_is_nil (node: node->left))
1643 {
1644 g_assert (node->left->parent == node);
1645 gtk_tree_rbtree_test_structure_helper (tree, node: node->left);
1646 }
1647 if (!gtk_tree_rbtree_is_nil (node: node->right))
1648 {
1649 g_assert (node->right->parent == node);
1650 gtk_tree_rbtree_test_structure_helper (tree, node: node->right);
1651 }
1652
1653 if (node->children != NULL)
1654 {
1655 g_assert (node->children->parent_tree == tree);
1656 g_assert (node->children->parent_node == node);
1657
1658 gtk_tree_rbtree_test_structure (tree: node->children);
1659 }
1660}
1661static void
1662gtk_tree_rbtree_test_structure (GtkTreeRBTree *tree)
1663{
1664 g_assert (tree->root);
1665 if (gtk_tree_rbtree_is_nil (node: tree->root))
1666 return;
1667
1668 g_assert (gtk_tree_rbtree_is_nil (tree->root->parent));
1669 gtk_tree_rbtree_test_structure_helper (tree, node: tree->root);
1670}
1671
1672static void
1673gtk_tree_rbtree_test (const char *where,
1674 GtkTreeRBTree *tree)
1675{
1676 GtkTreeRBTree *tmp_tree;
1677
1678 if (tree == NULL)
1679 return;
1680
1681 /* Test the entire tree */
1682 tmp_tree = tree;
1683 while (tmp_tree->parent_tree)
1684 tmp_tree = tmp_tree->parent_tree;
1685
1686 if (gtk_tree_rbtree_is_nil (node: tmp_tree->root))
1687 return;
1688
1689 gtk_tree_rbtree_test_structure (tree: tmp_tree);
1690
1691 g_assert ((_count_nodes (tmp_tree, tmp_tree->root->left) +
1692 _count_nodes (tmp_tree, tmp_tree->root->right) + 1) == tmp_tree->root->count);
1693
1694
1695 gtk_tree_rbtree_test_height (tree: tmp_tree, node: tmp_tree->root);
1696 gtk_tree_rbtree_test_dirty (tree: tmp_tree, node: tmp_tree->root, GTK_TREE_RBNODE_FLAG_SET (tmp_tree->root, GTK_TREE_RBNODE_DESCENDANTS_INVALID));
1697 g_assert (count_total (tmp_tree, tmp_tree->root) == tmp_tree->root->total_count);
1698}
1699
1700static void
1701gtk_tree_rbtree_debug_spew_helper (GtkTreeRBTree *tree,
1702 GtkTreeRBNode *node,
1703 GString *s,
1704 int depth)
1705{
1706 int i;
1707 for (i = 0; i < depth; i++)
1708 g_string_append (string: s, val: "\t");
1709
1710 g_string_append_printf (string: s, format: "(%p - %s) (Offset %d) (Parity %d) (Validity %d%d%d)\n",
1711 node,
1712 (GTK_TREE_RBNODE_GET_COLOR (node) == GTK_TREE_RBNODE_BLACK) ? "BLACK" : " RED ",
1713 node->offset,
1714 node->total_count,
1715 (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_DESCENDANTS_INVALID)) ? 1 : 0,
1716 (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_INVALID)) ? 1 : 0,
1717 (GTK_TREE_RBNODE_FLAG_SET (node, GTK_TREE_RBNODE_COLUMN_INVALID)) ? 1 : 0);
1718 if (node->children != NULL)
1719 {
1720 g_string_append (string: s, val: "Looking at child.\n");
1721 gtk_tree_rbtree_debug_spew (tree: node->children, s);
1722 g_string_append (string: s, val: "Done looking at child.\n");
1723 }
1724 if (!gtk_tree_rbtree_is_nil (node: node->left))
1725 {
1726 gtk_tree_rbtree_debug_spew_helper (tree, node: node->left, s, depth: depth + 1);
1727 }
1728 if (!gtk_tree_rbtree_is_nil (node: node->right))
1729 {
1730 gtk_tree_rbtree_debug_spew_helper (tree, node: node->right, s, depth: depth + 1);
1731 }
1732}
1733
1734static void
1735gtk_tree_rbtree_debug_spew (GtkTreeRBTree *tree,
1736 GString *s)
1737{
1738 g_return_if_fail (tree != NULL);
1739
1740 if (gtk_tree_rbtree_is_nil (node: tree->root))
1741 g_string_append (string: s, val: "Empty tree...");
1742 else
1743 gtk_tree_rbtree_debug_spew_helper (tree, node: tree->root, s, depth: 0);
1744}
1745#endif /* G_ENABLE_DEBUG */
1746

source code of gtk/gtk/gtktreerbtree.c