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 | |
33 | typedef struct _GtkRbNode GtkRbNode; |
34 | |
35 | struct _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 | |
48 | struct _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 | |
68 | static inline gboolean |
69 | is_root (GtkRbNode *node) |
70 | { |
71 | return GPOINTER_TO_SIZE (node->parent_or_tree) & 1 ? TRUE : FALSE; |
72 | } |
73 | |
74 | static inline GtkRbNode * |
75 | parent (GtkRbNode *node) |
76 | { |
77 | if (is_root (node)) |
78 | return NULL; |
79 | else |
80 | return node->parent; |
81 | } |
82 | |
83 | static GtkRbTree * |
84 | tree (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 | |
92 | static void |
93 | set_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 | |
109 | static inline gsize |
110 | gtk_rb_node_get_size (GtkRbTree *tree) |
111 | { |
112 | return sizeof (GtkRbNode) + tree->element_size + tree->augment_size; |
113 | } |
114 | |
115 | static GtkRbNode * |
116 | gtk_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 | |
128 | static void |
129 | gtk_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 | |
140 | static void |
141 | gtk_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 | |
155 | static void |
156 | gtk_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 | |
168 | static void |
169 | gtk_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 | |
184 | static GtkRbNode * |
185 | gtk_rb_node_get_first (GtkRbNode *node) |
186 | { |
187 | while (node->left) |
188 | node = node->left; |
189 | |
190 | return node; |
191 | } |
192 | |
193 | static GtkRbNode * |
194 | gtk_rb_node_get_last (GtkRbNode *node) |
195 | { |
196 | while (node->right) |
197 | node = node->right; |
198 | |
199 | return node; |
200 | } |
201 | |
202 | static GtkRbNode * |
203 | gtk_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 | |
221 | static GtkRbNode * |
222 | gtk_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 |
241 | static guint |
242 | position (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 | |
258 | static void |
259 | gtk_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 | |
287 | static void |
288 | gtk_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 | |
317 | static gboolean |
318 | is_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 | |
326 | static inline gboolean |
327 | is_black (GtkRbNode *node_or_null) |
328 | { |
329 | return !is_red (node_or_null); |
330 | } |
331 | |
332 | static void |
333 | set_black (GtkRbNode *node_or_null) |
334 | { |
335 | if (node_or_null == NULL) |
336 | return; |
337 | |
338 | node_or_null->red = FALSE; |
339 | } |
340 | |
341 | static void |
342 | set_red (GtkRbNode *node_or_null) |
343 | { |
344 | if (node_or_null == NULL) |
345 | return; |
346 | |
347 | node_or_null->red = TRUE; |
348 | } |
349 | |
350 | static void |
351 | gtk_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 | |
426 | static void |
427 | gtk_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 | |
505 | GtkRbTree * |
506 | gtk_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 | |
526 | GtkRbTree * |
527 | gtk_rb_tree_ref (GtkRbTree *tree) |
528 | { |
529 | tree->ref_count++; |
530 | |
531 | return tree; |
532 | } |
533 | |
534 | void |
535 | gtk_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 | |
547 | gpointer |
548 | gtk_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 | |
556 | gpointer |
557 | gtk_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 | |
565 | gpointer |
566 | gtk_rb_tree_node_get_previous (gpointer node) |
567 | { |
568 | return NODE_TO_POINTER (gtk_rb_node_get_previous (NODE_FROM_POINTER (node))); |
569 | } |
570 | |
571 | gpointer |
572 | gtk_rb_tree_node_get_next (gpointer node) |
573 | { |
574 | return NODE_TO_POINTER (gtk_rb_node_get_next (NODE_FROM_POINTER (node))); |
575 | } |
576 | |
577 | gpointer |
578 | gtk_rb_tree_get_root (GtkRbTree *tree) |
579 | { |
580 | return NODE_TO_POINTER (tree->root); |
581 | } |
582 | |
583 | gpointer |
584 | gtk_rb_tree_node_get_parent (gpointer node) |
585 | { |
586 | return NODE_TO_POINTER (parent (NODE_FROM_POINTER (node))); |
587 | } |
588 | |
589 | gpointer |
590 | gtk_rb_tree_node_get_left (gpointer node) |
591 | { |
592 | return NODE_TO_POINTER (NODE_FROM_POINTER (node)->left); |
593 | } |
594 | |
595 | gpointer |
596 | gtk_rb_tree_node_get_right (gpointer node) |
597 | { |
598 | return NODE_TO_POINTER (NODE_FROM_POINTER (node)->right); |
599 | } |
600 | |
601 | gpointer |
602 | gtk_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 | |
612 | GtkRbTree * |
613 | gtk_rb_tree_node_get_tree (gpointer node) |
614 | { |
615 | return tree (NODE_FROM_POINTER (node)); |
616 | } |
617 | |
618 | void |
619 | gtk_rb_tree_node_mark_dirty (gpointer node) |
620 | { |
621 | gtk_rb_node_mark_dirty (NODE_FROM_POINTER (node), TRUE); |
622 | } |
623 | |
624 | gpointer |
625 | gtk_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 | |
675 | gpointer |
676 | gtk_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 | |
710 | void |
711 | gtk_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 | |
788 | void |
789 | gtk_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 | |