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
20#include "gtkrbtreeprivate.h"
21
22#include "gtkdebug.h"
23
24/* Define the following to print adds and removals to stdout.
25 * The format of the printout will be suitable for addition as a new test to
26 * testsuite/gtk/rbtree-crash.c
27 * by just grepping the printouts from the relevant rbtree.
28 *
29 * This is meant to be a trivial way to add rbtree tests to the testsuite.
30 */
31#undef DUMP_MODIFICATION
32
33typedef struct _GtkRbNode GtkRbNode;
34
35struct _GtkRbTree
36{
37 guint ref_count;
38
39 gsize element_size;
40 gsize augment_size;
41 GtkRbTreeAugmentFunc augment_func;
42 GDestroyNotify clear_func;
43 GDestroyNotify clear_augment_func;
44
45 GtkRbNode *root;
46};
47
48struct _GtkRbNode
49{
50 guint red :1;
51 guint dirty :1;
52
53 GtkRbNode *left;
54 GtkRbNode *right;
55 /* The difference between tree and parent here is that we OR the tree with 1 and because
56 * pointers are always multiples of 4, we can know if we've stored a parent or the tree here */
57 union {
58 gpointer parent_or_tree;
59 GtkRbNode *parent;
60 GtkRbTree *tree;
61 };
62};
63
64#define NODE_FROM_POINTER(ptr) ((GtkRbNode *) (((guchar *) (ptr)) - sizeof (GtkRbNode)))
65#define NODE_TO_POINTER(node) ((node) ? ((gpointer) (((guchar *) (node)) + sizeof (GtkRbNode))) : NULL)
66#define NODE_TO_AUG_POINTER(tree, node) ((gpointer) ((node) ? (((guchar *) (node)) + sizeof (GtkRbNode) + (tree)->element_size) : NULL))
67
68static inline gboolean
69is_root (GtkRbNode *node)
70{
71 return GPOINTER_TO_SIZE (node->parent_or_tree) & 1 ? TRUE : FALSE;
72}
73
74static inline GtkRbNode *
75parent (GtkRbNode *node)
76{
77 if (is_root (node))
78 return NULL;
79 else
80 return node->parent;
81}
82
83static GtkRbTree *
84tree (GtkRbNode *node)
85{
86 while (!is_root (node))
87 node = parent (node);
88
89 return GSIZE_TO_POINTER (GPOINTER_TO_SIZE (node->tree) & ~1);
90}
91
92static void
93set_parent (GtkRbTree *tree,
94 GtkRbNode *node,
95 GtkRbNode *new_parent)
96{
97
98 if (new_parent != NULL)
99 {
100 node->parent = new_parent;
101 }
102 else
103 {
104 node->tree = GSIZE_TO_POINTER (GPOINTER_TO_SIZE (tree) | 1);
105 tree->root = node;
106 }
107}
108
109static inline gsize
110gtk_rb_node_get_size (GtkRbTree *tree)
111{
112 return sizeof (GtkRbNode) + tree->element_size + tree->augment_size;
113}
114
115static GtkRbNode *
116gtk_rb_node_new (GtkRbTree *tree)
117{
118 GtkRbNode *result;
119
120 result = g_slice_alloc0 (block_size: gtk_rb_node_get_size (tree));
121
122 result->red = TRUE;
123 result->dirty = TRUE;
124
125 return result;
126}
127
128static void
129gtk_rb_node_free (GtkRbTree *tree,
130 GtkRbNode *node)
131{
132 if (tree->clear_func)
133 tree->clear_func (NODE_TO_POINTER (node));
134 if (tree->clear_augment_func)
135 tree->clear_augment_func (NODE_TO_AUG_POINTER (tree, node));
136
137 g_slice_free1 (block_size: gtk_rb_node_get_size (tree), mem_block: node);
138}
139
140static void
141gtk_rb_node_free_deep (GtkRbTree *tree,
142 GtkRbNode *node)
143{
144 GtkRbNode *right = node->right;
145
146 if (node->left)
147 gtk_rb_node_free_deep (tree, node: node->left);
148
149 gtk_rb_node_free (tree, node);
150
151 if (right)
152 gtk_rb_node_free_deep (tree, node: right);
153}
154
155static void
156gtk_rb_node_mark_dirty (GtkRbNode *node,
157 gboolean mark_parent)
158{
159 if (node->dirty)
160 return;
161
162 node->dirty = TRUE;
163
164 if (mark_parent && parent (node))
165 gtk_rb_node_mark_dirty (node: parent (node), TRUE);
166}
167
168static void
169gtk_rb_node_clean (GtkRbTree *tree,
170 GtkRbNode *node)
171{
172 if (!node->dirty)
173 return;
174
175 node->dirty = FALSE;
176 if (tree->augment_func)
177 tree->augment_func (tree,
178 NODE_TO_AUG_POINTER (tree, node),
179 NODE_TO_POINTER (node),
180 NODE_TO_POINTER (node->left),
181 NODE_TO_POINTER (node->right));
182}
183
184static GtkRbNode *
185gtk_rb_node_get_first (GtkRbNode *node)
186{
187 while (node->left)
188 node = node->left;
189
190 return node;
191}
192
193static GtkRbNode *
194gtk_rb_node_get_last (GtkRbNode *node)
195{
196 while (node->right)
197 node = node->right;
198
199 return node;
200}
201
202static GtkRbNode *
203gtk_rb_node_get_previous (GtkRbNode *node)
204{
205 GtkRbNode *p;
206
207 if (node->left)
208 return gtk_rb_node_get_last (node: node->left);
209
210 for (p = parent (node); p != NULL; p = parent (node))
211 {
212 if (p->right == node)
213 return p;
214
215 node = p;
216 }
217
218 return NULL;
219}
220
221static GtkRbNode *
222gtk_rb_node_get_next (GtkRbNode *node)
223{
224 GtkRbNode *p;
225
226 if (node->right)
227 return gtk_rb_node_get_first (node: node->right);
228
229 for (p = parent (node); p != NULL; p = parent (node))
230 {
231 if (p->left == node)
232 return p;
233
234 node = p;
235 }
236
237 return NULL;
238}
239
240#ifdef DUMP_MODIFICATION
241static guint
242position (GtkRbTree *tree,
243 GtkRbNode *node)
244{
245 GtkRbNode *n;
246 guint i;
247
248 i = 0;
249 for (n = gtk_rb_node_get_first (tree->root);
250 n != node;
251 n = gtk_rb_node_get_next (n))
252 i++;
253
254 return i;
255}
256#endif
257
258static void
259gtk_rb_node_rotate_left (GtkRbTree *tree,
260 GtkRbNode *node)
261{
262 GtkRbNode *right, *p;
263
264 right = node->right;
265 p = parent (node);
266
267 node->right = right->left;
268 if (right->left)
269 set_parent (tree, node: right->left, new_parent: node);
270
271 set_parent (tree, node: right, new_parent: p);
272 if (p)
273 {
274 if (node == p->left)
275 p->left = right;
276 else
277 p->right = right;
278 }
279
280 right->left = node;
281 set_parent (tree, node, new_parent: right);
282
283 gtk_rb_node_mark_dirty (node, FALSE);
284 gtk_rb_node_mark_dirty (node: right, FALSE);
285}
286
287static void
288gtk_rb_node_rotate_right (GtkRbTree *tree,
289 GtkRbNode *node)
290{
291 GtkRbNode *left, *p;
292
293 left = node->left;
294 p = parent (node);
295
296 node->left = left->right;
297 if (left->right)
298 set_parent (tree, node: left->right, new_parent: node);
299
300 set_parent (tree, node: left, new_parent: p);
301 if (p)
302 {
303 if (node == p->right)
304 p->right = left;
305 else
306 p->left = left;
307 }
308
309 /* link node and left */
310 left->right = node;
311 set_parent (tree, node, new_parent: left);
312
313 gtk_rb_node_mark_dirty (node, FALSE);
314 gtk_rb_node_mark_dirty (node: left, FALSE);
315}
316
317static gboolean
318is_red (GtkRbNode *node_or_null)
319{
320 if (node_or_null == NULL)
321 return FALSE;
322 else
323 return node_or_null->red;
324}
325
326static inline gboolean
327is_black (GtkRbNode *node_or_null)
328{
329 return !is_red (node_or_null);
330}
331
332static void
333set_black (GtkRbNode *node_or_null)
334{
335 if (node_or_null == NULL)
336 return;
337
338 node_or_null->red = FALSE;
339}
340
341static void
342set_red (GtkRbNode *node_or_null)
343{
344 if (node_or_null == NULL)
345 return;
346
347 node_or_null->red = TRUE;
348}
349
350static void
351gtk_rb_tree_insert_fixup (GtkRbTree *tree,
352 GtkRbNode *node)
353{
354 GtkRbNode *p;
355
356 /* check Red-Black properties */
357 for (p = parent (node);
358 p && is_red (node_or_null: p);
359 p = parent (node))
360 {
361 GtkRbNode *pp = parent (node: p);
362
363 /* we have a violation */
364 g_assert (pp);
365
366 if (p == pp->left)
367 {
368 GtkRbNode *uncle = pp->right;
369
370 if (is_red (node_or_null: uncle))
371 {
372 /* uncle is red */
373 set_black (p);
374 set_black (uncle);
375 set_red (pp);
376 node = pp;
377 }
378 else
379 {
380 /* uncle is black */
381 if (node == p->right)
382 {
383 /* make node a left child */
384 gtk_rb_node_rotate_left (tree, node: p);
385 p = node;
386 node = p->left;
387 }
388 /* recolor and rotate */
389 set_black (p);
390 set_red (pp);
391 gtk_rb_node_rotate_right (tree, node: pp);
392 }
393 }
394 else
395 {
396 /* mirror image of above code */
397 GtkRbNode *uncle = pp->left;
398
399 if (is_red (node_or_null: uncle))
400 {
401 /* uncle is red */
402 set_black (p);
403 set_black (uncle);
404 set_red (pp);
405 node = pp;
406 }
407 else
408 {
409 /* uncle is black */
410 if (node == p->left)
411 {
412 gtk_rb_node_rotate_right (tree, node: p);
413 p = node;
414 node = p->right;
415 }
416 set_black (p);
417 set_red (pp);
418 gtk_rb_node_rotate_left (tree, node: pp);
419 }
420 }
421 }
422
423 set_black (tree->root);
424}
425
426static void
427gtk_rb_tree_remove_node_fixup (GtkRbTree *tree,
428 GtkRbNode *node,
429 GtkRbNode *p)
430{
431 while (node != tree->root && is_black (node_or_null: node))
432 {
433 if (node == p->left)
434 {
435 GtkRbNode *w = p->right;
436
437 if (is_red (node_or_null: w))
438 {
439 set_black (w);
440 set_red (p);
441 gtk_rb_node_rotate_left (tree, node: p);
442 w = p->right;
443 }
444 g_assert (w);
445 if (is_black (node_or_null: w->left) && is_black (node_or_null: w->right))
446 {
447 set_red (w);
448 node = p;
449 }
450 else
451 {
452 if (is_black (node_or_null: w->right))
453 {
454 set_black (w->left);
455 set_red (w);
456 gtk_rb_node_rotate_right (tree, node: w);
457 w = p->right;
458 }
459 w->red = p->red;
460 set_black (p);
461 set_black (w->right);
462 gtk_rb_node_rotate_left (tree, node: p);
463 node = tree->root;
464 }
465 }
466 else
467 {
468 GtkRbNode *w = p->left;
469 if (is_red (node_or_null: w))
470 {
471 set_black (w);
472 set_red (p);
473 gtk_rb_node_rotate_right (tree, node: p);
474 w = p->left;
475 }
476 g_assert (w);
477 if (is_black (node_or_null: w->right) && is_black (node_or_null: w->left))
478 {
479 set_red (w);
480 node = p;
481 }
482 else
483 {
484 if (is_black (node_or_null: w->left))
485 {
486 set_black (w->right);
487 set_red (w);
488 gtk_rb_node_rotate_left (tree, node: w);
489 w = p->left;
490 }
491 w->red = p->red;
492 set_black (p);
493 set_black (w->left);
494 gtk_rb_node_rotate_right (tree, node: p);
495 node = tree->root;
496 }
497 }
498
499 p = parent (node);
500 }
501
502 set_black (node);
503}
504
505GtkRbTree *
506gtk_rb_tree_new_for_size (gsize element_size,
507 gsize augment_size,
508 GtkRbTreeAugmentFunc augment_func,
509 GDestroyNotify clear_func,
510 GDestroyNotify clear_augment_func)
511{
512 GtkRbTree *tree;
513
514 tree = g_slice_new0 (GtkRbTree);
515 tree->ref_count = 1;
516
517 tree->element_size = element_size;
518 tree->augment_size = augment_size;
519 tree->augment_func = augment_func;
520 tree->clear_func = clear_func;
521 tree->clear_augment_func = clear_augment_func;
522
523 return tree;
524}
525
526GtkRbTree *
527gtk_rb_tree_ref (GtkRbTree *tree)
528{
529 tree->ref_count++;
530
531 return tree;
532}
533
534void
535gtk_rb_tree_unref (GtkRbTree *tree)
536{
537 tree->ref_count--;
538 if (tree->ref_count > 0)
539 return;
540
541 if (tree->root)
542 gtk_rb_node_free_deep (tree, node: tree->root);
543
544 g_slice_free (GtkRbTree, tree);
545}
546
547gpointer
548gtk_rb_tree_get_first (GtkRbTree *tree)
549{
550 if (tree->root == NULL)
551 return NULL;
552
553 return NODE_TO_POINTER (gtk_rb_node_get_first (tree->root));
554}
555
556gpointer
557gtk_rb_tree_get_last (GtkRbTree *tree)
558{
559 if (tree->root == NULL)
560 return NULL;
561
562 return NODE_TO_POINTER (gtk_rb_node_get_last (tree->root));
563}
564
565gpointer
566gtk_rb_tree_node_get_previous (gpointer node)
567{
568 return NODE_TO_POINTER (gtk_rb_node_get_previous (NODE_FROM_POINTER (node)));
569}
570
571gpointer
572gtk_rb_tree_node_get_next (gpointer node)
573{
574 return NODE_TO_POINTER (gtk_rb_node_get_next (NODE_FROM_POINTER (node)));
575}
576
577gpointer
578gtk_rb_tree_get_root (GtkRbTree *tree)
579{
580 return NODE_TO_POINTER (tree->root);
581}
582
583gpointer
584gtk_rb_tree_node_get_parent (gpointer node)
585{
586 return NODE_TO_POINTER (parent (NODE_FROM_POINTER (node)));
587}
588
589gpointer
590gtk_rb_tree_node_get_left (gpointer node)
591{
592 return NODE_TO_POINTER (NODE_FROM_POINTER (node)->left);
593}
594
595gpointer
596gtk_rb_tree_node_get_right (gpointer node)
597{
598 return NODE_TO_POINTER (NODE_FROM_POINTER (node)->right);
599}
600
601gpointer
602gtk_rb_tree_get_augment (GtkRbTree *tree,
603 gpointer node)
604{
605 GtkRbNode *rbnode = NODE_FROM_POINTER (node);
606
607 gtk_rb_node_clean (tree, node: rbnode);
608
609 return NODE_TO_AUG_POINTER (tree, rbnode);
610}
611
612GtkRbTree *
613gtk_rb_tree_node_get_tree (gpointer node)
614{
615 return tree (NODE_FROM_POINTER (node));
616}
617
618void
619gtk_rb_tree_node_mark_dirty (gpointer node)
620{
621 gtk_rb_node_mark_dirty (NODE_FROM_POINTER (node), TRUE);
622}
623
624gpointer
625gtk_rb_tree_insert_before (GtkRbTree *tree,
626 gpointer node)
627{
628 GtkRbNode *result;
629
630
631 if (tree->root == NULL)
632 {
633#ifdef DUMP_MODIFICATION
634 g_print ("add (tree, 0); /* 0x%p */\n", tree);
635#endif /* DUMP_MODIFICATION */
636
637 g_assert (node == NULL);
638
639 result = gtk_rb_node_new (tree);
640 tree->root = result;
641 }
642 else if (node == NULL)
643 {
644 return gtk_rb_tree_insert_after (tree, node: gtk_rb_tree_get_last (tree));
645 }
646 else
647 {
648 GtkRbNode *current = NODE_FROM_POINTER (node);
649
650#ifdef DUMP_MODIFICATION
651 g_print ("add (tree, %u); /* 0x%p */\n", position (tree, current), tree);
652#endif /* DUMP_MODIFICATION */
653
654 /* setup new node */
655 result = gtk_rb_node_new (tree);
656
657 if (current->left)
658 {
659 current = gtk_rb_node_get_last (node: current->left);
660 current->right = result;
661 }
662 else
663 {
664 current->left = result;
665 }
666 set_parent (tree, node: result, new_parent: current);
667 gtk_rb_node_mark_dirty (node: current, TRUE);
668 }
669
670 gtk_rb_tree_insert_fixup (tree, node: result);
671
672 return NODE_TO_POINTER (result);
673}
674
675gpointer
676gtk_rb_tree_insert_after (GtkRbTree *tree,
677 gpointer node)
678{
679 GtkRbNode *current, *result;
680
681 if (node == NULL)
682 return gtk_rb_tree_insert_before (tree, node: gtk_rb_tree_get_first (tree));
683
684 current = NODE_FROM_POINTER (node);
685
686#ifdef DUMP_MODIFICATION
687 g_print ("add (tree, %u); /* 0x%p */\n", position (tree, current) + 1, tree);
688#endif /* DUMP_MODIFICATION */
689
690 /* setup new node */
691 result = gtk_rb_node_new (tree);
692
693 if (current->right)
694 {
695 current = gtk_rb_node_get_first (node: current->right);
696 current->left = result;
697 }
698 else
699 {
700 current->right = result;
701 }
702 set_parent (tree, node: result, new_parent: current);
703 gtk_rb_node_mark_dirty (node: current, TRUE);
704
705 gtk_rb_tree_insert_fixup (tree, node: result);
706
707 return NODE_TO_POINTER (result);
708}
709
710void
711gtk_rb_tree_remove (GtkRbTree *tree,
712 gpointer node)
713{
714 GtkRbNode *x, *y, *p, *real_node;
715
716 real_node = NODE_FROM_POINTER (node);
717
718#ifdef DUMP_MODIFICATION
719 g_print ("delete (tree, %u); /* 0x%p */\n", position (tree, real_node), tree);
720#endif /* DUMP_MODIFICATION */
721
722 y = real_node;
723 if (y->left && y->right)
724 {
725 y = y->right;
726
727 while (y->left)
728 y = y->left;
729 }
730
731 /* x is y's only child, or nil */
732 if (y->left)
733 x = y->left;
734 else
735 x = y->right;
736
737 /* remove y from the parent chain */
738 p = parent (node: y);
739 if (x != NULL)
740 set_parent (tree, node: x, new_parent: p);
741 if (p)
742 {
743 if (y == p->left)
744 p->left = x;
745 else
746 p->right = x;
747 gtk_rb_node_mark_dirty (node: p, TRUE);
748 }
749 else
750 {
751 if (x == NULL)
752 tree->root = NULL;
753 }
754
755 /* We need to clean up the validity of the tree.
756 */
757 if (is_black (node_or_null: y))
758 gtk_rb_tree_remove_node_fixup (tree, node: x, p);
759
760 if (y != real_node)
761 {
762 /* Move the node over */
763 if (is_red (node_or_null: real_node) != is_red (node_or_null: y))
764 y->red = !y->red;
765
766 y->left = real_node->left;
767 if (y->left)
768 set_parent (tree, node: y->left, new_parent: y);
769 y->right = real_node->right;
770 if (y->right)
771 set_parent (tree, node: y->right, new_parent: y);
772 p = parent (node: real_node);
773 set_parent (tree, node: y, new_parent: p);
774 if (p)
775 {
776 if (p->left == real_node)
777 p->left = y;
778 else
779 p->right = y;
780 gtk_rb_node_mark_dirty (node: p, TRUE);
781 }
782 gtk_rb_node_mark_dirty (node: y, TRUE);
783 }
784
785 gtk_rb_node_free (tree, node: real_node);
786}
787
788void
789gtk_rb_tree_remove_all (GtkRbTree *tree)
790{
791#ifdef DUMP_MODIFICATION
792 g_print ("delete_all (tree); /* 0x%p */\n", tree);
793#endif /* DUMP_MODIFICATION */
794
795 if (tree->root)
796 gtk_rb_node_free_deep (tree, node: tree->root);
797
798 tree->root = NULL;
799}
800
801

source code of gtk/gtk/gtkrbtree.c