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