1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 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 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
16 */
17
18 /*
19 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
20 * file for a list of people on the GLib Team. See the ChangeLog
21 * files for a list of changes. These files are distributed with
22 * GLib at ftp://ftp.gtk.org/pub/gtk/.
23 */
24
25 /*
26 * MT safe
27 */
28
29 #include "config.h"
30
31 #include "gtree.h"
32
33 #include "gatomic.h"
34 #include "gtestutils.h"
35 #include "gslice.h"
36
37 /**
38 * SECTION:trees-binary
39 * @title: Balanced Binary Trees
40 * @short_description: a sorted collection of key/value pairs optimized
41 * for searching and traversing in order
42 *
43 * The #GTree structure and its associated functions provide a sorted
44 * collection of key/value pairs optimized for searching and traversing
45 * in order. This means that most of the operations (access, search,
46 * insertion, deletion, ...) on #GTree are O(log(n)) in average and O(n)
47 * in worst case for time complexity. But, note that maintaining a
48 * balanced sorted #GTree of n elements is done in time O(n log(n)).
49 *
50 * To create a new #GTree use g_tree_new().
51 *
52 * To insert a key/value pair into a #GTree use g_tree_insert()
53 * (O(n log(n))).
54 *
55 * To remove a key/value pair use g_tree_remove() (O(n log(n))).
56 *
57 * To look up the value corresponding to a given key, use
58 * g_tree_lookup() and g_tree_lookup_extended().
59 *
60 * To find out the number of nodes in a #GTree, use g_tree_nnodes(). To
61 * get the height of a #GTree, use g_tree_height().
62 *
63 * To traverse a #GTree, calling a function for each node visited in
64 * the traversal, use g_tree_foreach().
65 *
66 * To destroy a #GTree, use g_tree_destroy().
67 **/
68
69 #define MAX_GTREE_HEIGHT 40
70
71 /**
72 * GTree:
73 *
74 * The GTree struct is an opaque data structure representing a
75 * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be
76 * accessed only by using the following functions.
77 */
78 struct _GTree
79 {
80 GTreeNode *root;
81 GCompareDataFunc key_compare;
82 GDestroyNotify key_destroy_func;
83 GDestroyNotify value_destroy_func;
84 gpointer key_compare_data;
85 guint nnodes;
86 gint ref_count;
87 };
88
89 struct _GTreeNode
90 {
91 gpointer key; /* key for this node */
92 gpointer value; /* value stored at this node */
93 GTreeNode *left; /* left subtree */
94 GTreeNode *right; /* right subtree */
95 gint8 balance; /* height (right) - height (left) */
96 guint8 left_child;
97 guint8 right_child;
98 };
99
100
101 static GTreeNode* g_tree_node_new (gpointer key,
102 gpointer value);
103 static GTreeNode *g_tree_insert_internal (GTree *tree,
104 gpointer key,
105 gpointer value,
106 gboolean replace);
107 static gboolean g_tree_remove_internal (GTree *tree,
108 gconstpointer key,
109 gboolean steal);
110 static GTreeNode* g_tree_node_balance (GTreeNode *node);
111 static GTreeNode *g_tree_find_node (GTree *tree,
112 gconstpointer key);
113 static gint g_tree_node_pre_order (GTreeNode *node,
114 GTraverseFunc traverse_func,
115 gpointer data);
116 static gint g_tree_node_in_order (GTreeNode *node,
117 GTraverseFunc traverse_func,
118 gpointer data);
119 static gint g_tree_node_post_order (GTreeNode *node,
120 GTraverseFunc traverse_func,
121 gpointer data);
122 static GTreeNode *g_tree_node_search (GTreeNode *node,
123 GCompareFunc search_func,
124 gconstpointer data);
125 static GTreeNode* g_tree_node_rotate_left (GTreeNode *node);
126 static GTreeNode* g_tree_node_rotate_right (GTreeNode *node);
127 #ifdef G_TREE_DEBUG
128 static void g_tree_node_check (GTreeNode *node);
129 #endif
130
131
132 static GTreeNode*
g_tree_node_new(gpointer key,gpointer value)133 g_tree_node_new (gpointer key,
134 gpointer value)
135 {
136 GTreeNode *node = g_slice_new (GTreeNode);
137
138 node->balance = 0;
139 node->left = NULL;
140 node->right = NULL;
141 node->left_child = FALSE;
142 node->right_child = FALSE;
143 node->key = key;
144 node->value = value;
145
146 return node;
147 }
148
149 /**
150 * g_tree_new:
151 * @key_compare_func: the function used to order the nodes in the #GTree.
152 * It should return values similar to the standard strcmp() function -
153 * 0 if the two arguments are equal, a negative value if the first argument
154 * comes before the second, or a positive value if the first argument comes
155 * after the second.
156 *
157 * Creates a new #GTree.
158 *
159 * Returns: a newly allocated #GTree
160 */
161 GTree *
g_tree_new(GCompareFunc key_compare_func)162 g_tree_new (GCompareFunc key_compare_func)
163 {
164 g_return_val_if_fail (key_compare_func != NULL, NULL);
165
166 return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
167 NULL, NULL);
168 }
169
170 /**
171 * g_tree_new_with_data:
172 * @key_compare_func: qsort()-style comparison function
173 * @key_compare_data: data to pass to comparison function
174 *
175 * Creates a new #GTree with a comparison function that accepts user data.
176 * See g_tree_new() for more details.
177 *
178 * Returns: a newly allocated #GTree
179 */
180 GTree *
g_tree_new_with_data(GCompareDataFunc key_compare_func,gpointer key_compare_data)181 g_tree_new_with_data (GCompareDataFunc key_compare_func,
182 gpointer key_compare_data)
183 {
184 g_return_val_if_fail (key_compare_func != NULL, NULL);
185
186 return g_tree_new_full (key_compare_func, key_compare_data,
187 NULL, NULL);
188 }
189
190 /**
191 * g_tree_new_full:
192 * @key_compare_func: qsort()-style comparison function
193 * @key_compare_data: data to pass to comparison function
194 * @key_destroy_func: a function to free the memory allocated for the key
195 * used when removing the entry from the #GTree or %NULL if you don't
196 * want to supply such a function
197 * @value_destroy_func: a function to free the memory allocated for the
198 * value used when removing the entry from the #GTree or %NULL if you
199 * don't want to supply such a function
200 *
201 * Creates a new #GTree like g_tree_new() and allows to specify functions
202 * to free the memory allocated for the key and value that get called when
203 * removing the entry from the #GTree.
204 *
205 * Returns: a newly allocated #GTree
206 */
207 GTree *
g_tree_new_full(GCompareDataFunc key_compare_func,gpointer key_compare_data,GDestroyNotify key_destroy_func,GDestroyNotify value_destroy_func)208 g_tree_new_full (GCompareDataFunc key_compare_func,
209 gpointer key_compare_data,
210 GDestroyNotify key_destroy_func,
211 GDestroyNotify value_destroy_func)
212 {
213 GTree *tree;
214
215 g_return_val_if_fail (key_compare_func != NULL, NULL);
216
217 tree = g_slice_new (GTree);
218 tree->root = NULL;
219 tree->key_compare = key_compare_func;
220 tree->key_destroy_func = key_destroy_func;
221 tree->value_destroy_func = value_destroy_func;
222 tree->key_compare_data = key_compare_data;
223 tree->nnodes = 0;
224 tree->ref_count = 1;
225
226 return tree;
227 }
228
229 /**
230 * g_tree_node_first:
231 * @tree: a #GTree
232 *
233 * Returns the first in-order node of the tree, or %NULL
234 * for an empty tree.
235 *
236 * Returns: (nullable) (transfer none): the first node in the tree
237 *
238 * Since: 2.68
239 */
240 GTreeNode *
g_tree_node_first(GTree * tree)241 g_tree_node_first (GTree *tree)
242 {
243 GTreeNode *tmp;
244
245 g_return_val_if_fail (tree != NULL, NULL);
246
247 if (!tree->root)
248 return NULL;
249
250 tmp = tree->root;
251
252 while (tmp->left_child)
253 tmp = tmp->left;
254
255 return tmp;
256 }
257
258 /**
259 * g_tree_node_last:
260 * @tree: a #GTree
261 *
262 * Returns the last in-order node of the tree, or %NULL
263 * for an empty tree.
264 *
265 * Returns: (nullable) (transfer none): the last node in the tree
266 *
267 * Since: 2.68
268 */
269 GTreeNode *
g_tree_node_last(GTree * tree)270 g_tree_node_last (GTree *tree)
271 {
272 GTreeNode *tmp;
273
274 g_return_val_if_fail (tree != NULL, NULL);
275
276 if (!tree->root)
277 return NULL;
278
279 tmp = tree->root;
280
281 while (tmp->right_child)
282 tmp = tmp->right;
283
284 return tmp;
285 }
286
287 /**
288 * g_tree_node_previous
289 * @node: a #GTree node
290 *
291 * Returns the previous in-order node of the tree, or %NULL
292 * if the passed node was already the first one.
293 *
294 * Returns: (nullable) (transfer none): the previous node in the tree
295 *
296 * Since: 2.68
297 */
298 GTreeNode *
g_tree_node_previous(GTreeNode * node)299 g_tree_node_previous (GTreeNode *node)
300 {
301 GTreeNode *tmp;
302
303 g_return_val_if_fail (node != NULL, NULL);
304
305 tmp = node->left;
306
307 if (node->left_child)
308 while (tmp->right_child)
309 tmp = tmp->right;
310
311 return tmp;
312 }
313
314 /**
315 * g_tree_node_next
316 * @node: a #GTree node
317 *
318 * Returns the next in-order node of the tree, or %NULL
319 * if the passed node was already the last one.
320 *
321 * Returns: (nullable) (transfer none): the next node in the tree
322 *
323 * Since: 2.68
324 */
325 GTreeNode *
g_tree_node_next(GTreeNode * node)326 g_tree_node_next (GTreeNode *node)
327 {
328 GTreeNode *tmp;
329
330 g_return_val_if_fail (node != NULL, NULL);
331
332 tmp = node->right;
333
334 if (node->right_child)
335 while (tmp->left_child)
336 tmp = tmp->left;
337
338 return tmp;
339 }
340
341 static void
g_tree_remove_all(GTree * tree)342 g_tree_remove_all (GTree *tree)
343 {
344 GTreeNode *node;
345 GTreeNode *next;
346
347 g_return_if_fail (tree != NULL);
348
349 node = g_tree_node_first (tree);
350
351 while (node)
352 {
353 next = g_tree_node_next (node);
354
355 if (tree->key_destroy_func)
356 tree->key_destroy_func (node->key);
357 if (tree->value_destroy_func)
358 tree->value_destroy_func (node->value);
359 g_slice_free (GTreeNode, node);
360
361 #ifdef G_TREE_DEBUG
362 g_assert (tree->nnodes > 0);
363 tree->nnodes--;
364 #endif
365
366 node = next;
367 }
368
369 #ifdef G_TREE_DEBUG
370 g_assert (tree->nnodes == 0);
371 #endif
372
373 tree->root = NULL;
374 #ifndef G_TREE_DEBUG
375 tree->nnodes = 0;
376 #endif
377 }
378
379 /**
380 * g_tree_ref:
381 * @tree: a #GTree
382 *
383 * Increments the reference count of @tree by one.
384 *
385 * It is safe to call this function from any thread.
386 *
387 * Returns: the passed in #GTree
388 *
389 * Since: 2.22
390 */
391 GTree *
g_tree_ref(GTree * tree)392 g_tree_ref (GTree *tree)
393 {
394 g_return_val_if_fail (tree != NULL, NULL);
395
396 g_atomic_int_inc (&tree->ref_count);
397
398 return tree;
399 }
400
401 /**
402 * g_tree_unref:
403 * @tree: a #GTree
404 *
405 * Decrements the reference count of @tree by one.
406 * If the reference count drops to 0, all keys and values will
407 * be destroyed (if destroy functions were specified) and all
408 * memory allocated by @tree will be released.
409 *
410 * It is safe to call this function from any thread.
411 *
412 * Since: 2.22
413 */
414 void
g_tree_unref(GTree * tree)415 g_tree_unref (GTree *tree)
416 {
417 g_return_if_fail (tree != NULL);
418
419 if (g_atomic_int_dec_and_test (&tree->ref_count))
420 {
421 g_tree_remove_all (tree);
422 g_slice_free (GTree, tree);
423 }
424 }
425
426 /**
427 * g_tree_destroy:
428 * @tree: a #GTree
429 *
430 * Removes all keys and values from the #GTree and decreases its
431 * reference count by one. If keys and/or values are dynamically
432 * allocated, you should either free them first or create the #GTree
433 * using g_tree_new_full(). In the latter case the destroy functions
434 * you supplied will be called on all keys and values before destroying
435 * the #GTree.
436 */
437 void
g_tree_destroy(GTree * tree)438 g_tree_destroy (GTree *tree)
439 {
440 g_return_if_fail (tree != NULL);
441
442 g_tree_remove_all (tree);
443 g_tree_unref (tree);
444 }
445
446 /**
447 * g_tree_insert_node:
448 * @tree: a #GTree
449 * @key: the key to insert
450 * @value: the value corresponding to the key
451 *
452 * Inserts a key/value pair into a #GTree.
453 *
454 * If the given key already exists in the #GTree its corresponding value
455 * is set to the new value. If you supplied a @value_destroy_func when
456 * creating the #GTree, the old value is freed using that function. If
457 * you supplied a @key_destroy_func when creating the #GTree, the passed
458 * key is freed using that function.
459 *
460 * The tree is automatically 'balanced' as new key/value pairs are added,
461 * so that the distance from the root to every leaf is as small as possible.
462 * The cost of maintaining a balanced tree while inserting new key/value
463 * result in a O(n log(n)) operation where most of the other operations
464 * are O(log(n)).
465 *
466 * Returns: (transfer none): the inserted (or set) node.
467 *
468 * Since: 2.68
469 */
470 GTreeNode *
g_tree_insert_node(GTree * tree,gpointer key,gpointer value)471 g_tree_insert_node (GTree *tree,
472 gpointer key,
473 gpointer value)
474 {
475 GTreeNode *node;
476
477 g_return_val_if_fail (tree != NULL, NULL);
478
479 node = g_tree_insert_internal (tree, key, value, FALSE);
480
481 #ifdef G_TREE_DEBUG
482 g_tree_node_check (tree->root);
483 #endif
484
485 return node;
486 }
487
488 /**
489 * g_tree_insert:
490 * @tree: a #GTree
491 * @key: the key to insert
492 * @value: the value corresponding to the key
493 *
494 * Inserts a key/value pair into a #GTree.
495 *
496 * Inserts a new key and value into a #GTree as g_tree_insert_node() does,
497 * only this function does not return the inserted or set node.
498 */
499 void
g_tree_insert(GTree * tree,gpointer key,gpointer value)500 g_tree_insert (GTree *tree,
501 gpointer key,
502 gpointer value)
503 {
504 g_tree_insert_node (tree, key, value);
505 }
506
507 /**
508 * g_tree_replace_node:
509 * @tree: a #GTree
510 * @key: the key to insert
511 * @value: the value corresponding to the key
512 *
513 * Inserts a new key and value into a #GTree similar to g_tree_insert_node().
514 * The difference is that if the key already exists in the #GTree, it gets
515 * replaced by the new key. If you supplied a @value_destroy_func when
516 * creating the #GTree, the old value is freed using that function. If you
517 * supplied a @key_destroy_func when creating the #GTree, the old key is
518 * freed using that function.
519 *
520 * The tree is automatically 'balanced' as new key/value pairs are added,
521 * so that the distance from the root to every leaf is as small as possible.
522 *
523 * Returns: (transfer none): the inserted (or set) node.
524 *
525 * Since: 2.68
526 */
527 GTreeNode *
g_tree_replace_node(GTree * tree,gpointer key,gpointer value)528 g_tree_replace_node (GTree *tree,
529 gpointer key,
530 gpointer value)
531 {
532 GTreeNode *node;
533
534 g_return_val_if_fail (tree != NULL, NULL);
535
536 node = g_tree_insert_internal (tree, key, value, TRUE);
537
538 #ifdef G_TREE_DEBUG
539 g_tree_node_check (tree->root);
540 #endif
541
542 return node;
543 }
544
545 /**
546 * g_tree_replace:
547 * @tree: a #GTree
548 * @key: the key to insert
549 * @value: the value corresponding to the key
550 *
551 * Inserts a new key and value into a #GTree as g_tree_replace_node() does,
552 * only this function does not return the inserted or set node.
553 */
554 void
g_tree_replace(GTree * tree,gpointer key,gpointer value)555 g_tree_replace (GTree *tree,
556 gpointer key,
557 gpointer value)
558 {
559 g_tree_replace_node (tree, key, value);
560 }
561
562 /* internal insert routine */
563 static GTreeNode *
g_tree_insert_internal(GTree * tree,gpointer key,gpointer value,gboolean replace)564 g_tree_insert_internal (GTree *tree,
565 gpointer key,
566 gpointer value,
567 gboolean replace)
568 {
569 GTreeNode *node, *retnode;
570 GTreeNode *path[MAX_GTREE_HEIGHT];
571 int idx;
572
573 g_return_val_if_fail (tree != NULL, NULL);
574
575 if (!tree->root)
576 {
577 tree->root = g_tree_node_new (key, value);
578 tree->nnodes++;
579 return tree->root;
580 }
581
582 idx = 0;
583 path[idx++] = NULL;
584 node = tree->root;
585
586 while (1)
587 {
588 int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
589
590 if (cmp == 0)
591 {
592 if (tree->value_destroy_func)
593 tree->value_destroy_func (node->value);
594
595 node->value = value;
596
597 if (replace)
598 {
599 if (tree->key_destroy_func)
600 tree->key_destroy_func (node->key);
601
602 node->key = key;
603 }
604 else
605 {
606 /* free the passed key */
607 if (tree->key_destroy_func)
608 tree->key_destroy_func (key);
609 }
610
611 return node;
612 }
613 else if (cmp < 0)
614 {
615 if (node->left_child)
616 {
617 path[idx++] = node;
618 node = node->left;
619 }
620 else
621 {
622 GTreeNode *child = g_tree_node_new (key, value);
623
624 child->left = node->left;
625 child->right = node;
626 node->left = child;
627 node->left_child = TRUE;
628 node->balance -= 1;
629
630 tree->nnodes++;
631
632 retnode = child;
633 break;
634 }
635 }
636 else
637 {
638 if (node->right_child)
639 {
640 path[idx++] = node;
641 node = node->right;
642 }
643 else
644 {
645 GTreeNode *child = g_tree_node_new (key, value);
646
647 child->right = node->right;
648 child->left = node;
649 node->right = child;
650 node->right_child = TRUE;
651 node->balance += 1;
652
653 tree->nnodes++;
654
655 retnode = child;
656 break;
657 }
658 }
659 }
660
661 /* Restore balance. This is the goodness of a non-recursive
662 * implementation, when we are done with balancing we 'break'
663 * the loop and we are done.
664 */
665 while (1)
666 {
667 GTreeNode *bparent = path[--idx];
668 gboolean left_node = (bparent && node == bparent->left);
669 g_assert (!bparent || bparent->left == node || bparent->right == node);
670
671 if (node->balance < -1 || node->balance > 1)
672 {
673 node = g_tree_node_balance (node);
674 if (bparent == NULL)
675 tree->root = node;
676 else if (left_node)
677 bparent->left = node;
678 else
679 bparent->right = node;
680 }
681
682 if (node->balance == 0 || bparent == NULL)
683 break;
684
685 if (left_node)
686 bparent->balance -= 1;
687 else
688 bparent->balance += 1;
689
690 node = bparent;
691 }
692
693 return retnode;
694 }
695
696 /**
697 * g_tree_remove:
698 * @tree: a #GTree
699 * @key: the key to remove
700 *
701 * Removes a key/value pair from a #GTree.
702 *
703 * If the #GTree was created using g_tree_new_full(), the key and value
704 * are freed using the supplied destroy functions, otherwise you have to
705 * make sure that any dynamically allocated values are freed yourself.
706 * If the key does not exist in the #GTree, the function does nothing.
707 *
708 * The cost of maintaining a balanced tree while removing a key/value
709 * result in a O(n log(n)) operation where most of the other operations
710 * are O(log(n)).
711 *
712 * Returns: %TRUE if the key was found (prior to 2.8, this function
713 * returned nothing)
714 */
715 gboolean
g_tree_remove(GTree * tree,gconstpointer key)716 g_tree_remove (GTree *tree,
717 gconstpointer key)
718 {
719 gboolean removed;
720
721 g_return_val_if_fail (tree != NULL, FALSE);
722
723 removed = g_tree_remove_internal (tree, key, FALSE);
724
725 #ifdef G_TREE_DEBUG
726 g_tree_node_check (tree->root);
727 #endif
728
729 return removed;
730 }
731
732 /**
733 * g_tree_steal:
734 * @tree: a #GTree
735 * @key: the key to remove
736 *
737 * Removes a key and its associated value from a #GTree without calling
738 * the key and value destroy functions.
739 *
740 * If the key does not exist in the #GTree, the function does nothing.
741 *
742 * Returns: %TRUE if the key was found (prior to 2.8, this function
743 * returned nothing)
744 */
745 gboolean
g_tree_steal(GTree * tree,gconstpointer key)746 g_tree_steal (GTree *tree,
747 gconstpointer key)
748 {
749 gboolean removed;
750
751 g_return_val_if_fail (tree != NULL, FALSE);
752
753 removed = g_tree_remove_internal (tree, key, TRUE);
754
755 #ifdef G_TREE_DEBUG
756 g_tree_node_check (tree->root);
757 #endif
758
759 return removed;
760 }
761
762 /* internal remove routine */
763 static gboolean
g_tree_remove_internal(GTree * tree,gconstpointer key,gboolean steal)764 g_tree_remove_internal (GTree *tree,
765 gconstpointer key,
766 gboolean steal)
767 {
768 GTreeNode *node, *parent, *balance;
769 GTreeNode *path[MAX_GTREE_HEIGHT];
770 int idx;
771 gboolean left_node;
772
773 g_return_val_if_fail (tree != NULL, FALSE);
774
775 if (!tree->root)
776 return FALSE;
777
778 idx = 0;
779 path[idx++] = NULL;
780 node = tree->root;
781
782 while (1)
783 {
784 int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
785
786 if (cmp == 0)
787 break;
788 else if (cmp < 0)
789 {
790 if (!node->left_child)
791 return FALSE;
792
793 path[idx++] = node;
794 node = node->left;
795 }
796 else
797 {
798 if (!node->right_child)
799 return FALSE;
800
801 path[idx++] = node;
802 node = node->right;
803 }
804 }
805
806 /* The following code is almost equal to g_tree_remove_node,
807 * except that we do not have to call g_tree_node_parent.
808 */
809 balance = parent = path[--idx];
810 g_assert (!parent || parent->left == node || parent->right == node);
811 left_node = (parent && node == parent->left);
812
813 if (!node->left_child)
814 {
815 if (!node->right_child)
816 {
817 if (!parent)
818 tree->root = NULL;
819 else if (left_node)
820 {
821 parent->left_child = FALSE;
822 parent->left = node->left;
823 parent->balance += 1;
824 }
825 else
826 {
827 parent->right_child = FALSE;
828 parent->right = node->right;
829 parent->balance -= 1;
830 }
831 }
832 else /* node has a right child */
833 {
834 GTreeNode *tmp = g_tree_node_next (node);
835 tmp->left = node->left;
836
837 if (!parent)
838 tree->root = node->right;
839 else if (left_node)
840 {
841 parent->left = node->right;
842 parent->balance += 1;
843 }
844 else
845 {
846 parent->right = node->right;
847 parent->balance -= 1;
848 }
849 }
850 }
851 else /* node has a left child */
852 {
853 if (!node->right_child)
854 {
855 GTreeNode *tmp = g_tree_node_previous (node);
856 tmp->right = node->right;
857
858 if (parent == NULL)
859 tree->root = node->left;
860 else if (left_node)
861 {
862 parent->left = node->left;
863 parent->balance += 1;
864 }
865 else
866 {
867 parent->right = node->left;
868 parent->balance -= 1;
869 }
870 }
871 else /* node has a both children (pant, pant!) */
872 {
873 GTreeNode *prev = node->left;
874 GTreeNode *next = node->right;
875 GTreeNode *nextp = node;
876 int old_idx = idx + 1;
877 idx++;
878
879 /* path[idx] == parent */
880 /* find the immediately next node (and its parent) */
881 while (next->left_child)
882 {
883 path[++idx] = nextp = next;
884 next = next->left;
885 }
886
887 path[old_idx] = next;
888 balance = path[idx];
889
890 /* remove 'next' from the tree */
891 if (nextp != node)
892 {
893 if (next->right_child)
894 nextp->left = next->right;
895 else
896 nextp->left_child = FALSE;
897 nextp->balance += 1;
898
899 next->right_child = TRUE;
900 next->right = node->right;
901 }
902 else
903 node->balance -= 1;
904
905 /* set the prev to point to the right place */
906 while (prev->right_child)
907 prev = prev->right;
908 prev->right = next;
909
910 /* prepare 'next' to replace 'node' */
911 next->left_child = TRUE;
912 next->left = node->left;
913 next->balance = node->balance;
914
915 if (!parent)
916 tree->root = next;
917 else if (left_node)
918 parent->left = next;
919 else
920 parent->right = next;
921 }
922 }
923
924 /* restore balance */
925 if (balance)
926 while (1)
927 {
928 GTreeNode *bparent = path[--idx];
929 g_assert (!bparent || bparent->left == balance || bparent->right == balance);
930 left_node = (bparent && balance == bparent->left);
931
932 if(balance->balance < -1 || balance->balance > 1)
933 {
934 balance = g_tree_node_balance (balance);
935 if (!bparent)
936 tree->root = balance;
937 else if (left_node)
938 bparent->left = balance;
939 else
940 bparent->right = balance;
941 }
942
943 if (balance->balance != 0 || !bparent)
944 break;
945
946 if (left_node)
947 bparent->balance += 1;
948 else
949 bparent->balance -= 1;
950
951 balance = bparent;
952 }
953
954 if (!steal)
955 {
956 if (tree->key_destroy_func)
957 tree->key_destroy_func (node->key);
958 if (tree->value_destroy_func)
959 tree->value_destroy_func (node->value);
960 }
961
962 g_slice_free (GTreeNode, node);
963
964 tree->nnodes--;
965
966 return TRUE;
967 }
968
969 /**
970 * g_tree_node_key:
971 * @node: a #GTree node
972 *
973 * Gets the key stored at a particular tree node.
974 *
975 * Returns: (nullable) (transfer none): the key at the node.
976 *
977 * Since: 2.68
978 */
979 gpointer
g_tree_node_key(GTreeNode * node)980 g_tree_node_key (GTreeNode *node)
981 {
982 g_return_val_if_fail (node != NULL, NULL);
983
984 return node->key;
985 }
986
987 /**
988 * g_tree_node_value:
989 * @node: a #GTree node
990 *
991 * Gets the value stored at a particular tree node.
992 *
993 * Returns: (nullable) (transfer none): the value at the node.
994 *
995 * Since: 2.68
996 */
997 gpointer
g_tree_node_value(GTreeNode * node)998 g_tree_node_value (GTreeNode *node)
999 {
1000 g_return_val_if_fail (node != NULL, NULL);
1001
1002 return node->value;
1003 }
1004
1005 /**
1006 * g_tree_lookup_node:
1007 * @tree: a #GTree
1008 * @key: the key to look up
1009 *
1010 * Gets the tree node corresponding to the given key. Since a #GTree is
1011 * automatically balanced as key/value pairs are added, key lookup
1012 * is O(log n) (where n is the number of key/value pairs in the tree).
1013 *
1014 * Returns: (nullable) (transfer none): the tree node corresponding to
1015 * the key, or %NULL if the key was not found
1016 *
1017 * Since: 2.68
1018 */
1019 GTreeNode *
g_tree_lookup_node(GTree * tree,gconstpointer key)1020 g_tree_lookup_node (GTree *tree,
1021 gconstpointer key)
1022 {
1023 g_return_val_if_fail (tree != NULL, NULL);
1024
1025 return g_tree_find_node (tree, key);
1026 }
1027
1028 /**
1029 * g_tree_lookup:
1030 * @tree: a #GTree
1031 * @key: the key to look up
1032 *
1033 * Gets the value corresponding to the given key. Since a #GTree is
1034 * automatically balanced as key/value pairs are added, key lookup
1035 * is O(log n) (where n is the number of key/value pairs in the tree).
1036 *
1037 * Returns: the value corresponding to the key, or %NULL
1038 * if the key was not found
1039 */
1040 gpointer
g_tree_lookup(GTree * tree,gconstpointer key)1041 g_tree_lookup (GTree *tree,
1042 gconstpointer key)
1043 {
1044 GTreeNode *node;
1045
1046 node = g_tree_lookup_node (tree, key);
1047
1048 return node ? node->value : NULL;
1049 }
1050
1051 /**
1052 * g_tree_lookup_extended:
1053 * @tree: a #GTree
1054 * @lookup_key: the key to look up
1055 * @orig_key: (out) (optional) (nullable): returns the original key
1056 * @value: (out) (optional) (nullable): returns the value associated with the key
1057 *
1058 * Looks up a key in the #GTree, returning the original key and the
1059 * associated value. This is useful if you need to free the memory
1060 * allocated for the original key, for example before calling
1061 * g_tree_remove().
1062 *
1063 * Returns: %TRUE if the key was found in the #GTree
1064 */
1065 gboolean
g_tree_lookup_extended(GTree * tree,gconstpointer lookup_key,gpointer * orig_key,gpointer * value)1066 g_tree_lookup_extended (GTree *tree,
1067 gconstpointer lookup_key,
1068 gpointer *orig_key,
1069 gpointer *value)
1070 {
1071 GTreeNode *node;
1072
1073 g_return_val_if_fail (tree != NULL, FALSE);
1074
1075 node = g_tree_find_node (tree, lookup_key);
1076
1077 if (node)
1078 {
1079 if (orig_key)
1080 *orig_key = node->key;
1081 if (value)
1082 *value = node->value;
1083 return TRUE;
1084 }
1085 else
1086 return FALSE;
1087 }
1088
1089 /**
1090 * g_tree_foreach:
1091 * @tree: a #GTree
1092 * @func: the function to call for each node visited.
1093 * If this function returns %TRUE, the traversal is stopped.
1094 * @user_data: user data to pass to the function
1095 *
1096 * Calls the given function for each of the key/value pairs in the #GTree.
1097 * The function is passed the key and value of each pair, and the given
1098 * @data parameter. The tree is traversed in sorted order.
1099 *
1100 * The tree may not be modified while iterating over it (you can't
1101 * add/remove items). To remove all items matching a predicate, you need
1102 * to add each item to a list in your #GTraverseFunc as you walk over
1103 * the tree, then walk the list and remove each item.
1104 */
1105 void
g_tree_foreach(GTree * tree,GTraverseFunc func,gpointer user_data)1106 g_tree_foreach (GTree *tree,
1107 GTraverseFunc func,
1108 gpointer user_data)
1109 {
1110 GTreeNode *node;
1111
1112 g_return_if_fail (tree != NULL);
1113
1114 if (!tree->root)
1115 return;
1116
1117 node = g_tree_node_first (tree);
1118
1119 while (node)
1120 {
1121 if ((*func) (node->key, node->value, user_data))
1122 break;
1123
1124 node = g_tree_node_next (node);
1125 }
1126 }
1127
1128 /**
1129 * g_tree_foreach_node:
1130 * @tree: a #GTree
1131 * @func: the function to call for each node visited.
1132 * If this function returns %TRUE, the traversal is stopped.
1133 * @user_data: user data to pass to the function
1134 *
1135 * Calls the given function for each of the nodes in the #GTree.
1136 * The function is passed the pointer to the particular node, and the given
1137 * @data parameter. The tree traversal happens in-order.
1138 *
1139 * The tree may not be modified while iterating over it (you can't
1140 * add/remove items). To remove all items matching a predicate, you need
1141 * to add each item to a list in your #GTraverseFunc as you walk over
1142 * the tree, then walk the list and remove each item.
1143 *
1144 * Since: 2.68
1145 */
1146 void
g_tree_foreach_node(GTree * tree,GTraverseNodeFunc func,gpointer user_data)1147 g_tree_foreach_node (GTree *tree,
1148 GTraverseNodeFunc func,
1149 gpointer user_data)
1150 {
1151 GTreeNode *node;
1152
1153 g_return_if_fail (tree != NULL);
1154
1155 if (!tree->root)
1156 return;
1157
1158 node = g_tree_node_first (tree);
1159
1160 while (node)
1161 {
1162 if ((*func) (node, user_data))
1163 break;
1164
1165 node = g_tree_node_next (node);
1166 }
1167 }
1168
1169 /**
1170 * g_tree_traverse:
1171 * @tree: a #GTree
1172 * @traverse_func: the function to call for each node visited. If this
1173 * function returns %TRUE, the traversal is stopped.
1174 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
1175 * %G_PRE_ORDER and %G_POST_ORDER
1176 * @user_data: user data to pass to the function
1177 *
1178 * Calls the given function for each node in the #GTree.
1179 *
1180 * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary.
1181 * If you just want to visit all nodes in sorted order, use
1182 * g_tree_foreach() instead. If you really need to visit nodes in
1183 * a different order, consider using an [n-ary tree][glib-N-ary-Trees].
1184 */
1185 /**
1186 * GTraverseFunc:
1187 * @key: a key of a #GTree node
1188 * @value: the value corresponding to the key
1189 * @data: user data passed to g_tree_traverse()
1190 *
1191 * Specifies the type of function passed to g_tree_traverse(). It is
1192 * passed the key and value of each node, together with the @user_data
1193 * parameter passed to g_tree_traverse(). If the function returns
1194 * %TRUE, the traversal is stopped.
1195 *
1196 * Returns: %TRUE to stop the traversal
1197 */
1198 void
g_tree_traverse(GTree * tree,GTraverseFunc traverse_func,GTraverseType traverse_type,gpointer user_data)1199 g_tree_traverse (GTree *tree,
1200 GTraverseFunc traverse_func,
1201 GTraverseType traverse_type,
1202 gpointer user_data)
1203 {
1204 g_return_if_fail (tree != NULL);
1205
1206 if (!tree->root)
1207 return;
1208
1209 switch (traverse_type)
1210 {
1211 case G_PRE_ORDER:
1212 g_tree_node_pre_order (tree->root, traverse_func, user_data);
1213 break;
1214
1215 case G_IN_ORDER:
1216 g_tree_node_in_order (tree->root, traverse_func, user_data);
1217 break;
1218
1219 case G_POST_ORDER:
1220 g_tree_node_post_order (tree->root, traverse_func, user_data);
1221 break;
1222
1223 case G_LEVEL_ORDER:
1224 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
1225 break;
1226 }
1227 }
1228
1229 /**
1230 * g_tree_search_node:
1231 * @tree: a #GTree
1232 * @search_func: a function used to search the #GTree
1233 * @user_data: the data passed as the second argument to @search_func
1234 *
1235 * Searches a #GTree using @search_func.
1236 *
1237 * The @search_func is called with a pointer to the key of a key/value
1238 * pair in the tree, and the passed in @user_data. If @search_func returns
1239 * 0 for a key/value pair, then the corresponding node is returned as
1240 * the result of g_tree_search(). If @search_func returns -1, searching
1241 * will proceed among the key/value pairs that have a smaller key; if
1242 * @search_func returns 1, searching will proceed among the key/value
1243 * pairs that have a larger key.
1244 *
1245 * Returns: (nullable) (transfer none): the node corresponding to the
1246 * found key, or %NULL if the key was not found
1247 *
1248 * Since: 2.68
1249 */
1250 GTreeNode *
g_tree_search_node(GTree * tree,GCompareFunc search_func,gconstpointer user_data)1251 g_tree_search_node (GTree *tree,
1252 GCompareFunc search_func,
1253 gconstpointer user_data)
1254 {
1255 g_return_val_if_fail (tree != NULL, NULL);
1256
1257 if (!tree->root)
1258 return NULL;
1259
1260 return g_tree_node_search (tree->root, search_func, user_data);
1261 }
1262
1263 /**
1264 * g_tree_search:
1265 * @tree: a #GTree
1266 * @search_func: a function used to search the #GTree
1267 * @user_data: the data passed as the second argument to @search_func
1268 *
1269 * Searches a #GTree using @search_func.
1270 *
1271 * The @search_func is called with a pointer to the key of a key/value
1272 * pair in the tree, and the passed in @user_data. If @search_func returns
1273 * 0 for a key/value pair, then the corresponding value is returned as
1274 * the result of g_tree_search(). If @search_func returns -1, searching
1275 * will proceed among the key/value pairs that have a smaller key; if
1276 * @search_func returns 1, searching will proceed among the key/value
1277 * pairs that have a larger key.
1278 *
1279 * Returns: the value corresponding to the found key, or %NULL
1280 * if the key was not found
1281 */
1282 gpointer
g_tree_search(GTree * tree,GCompareFunc search_func,gconstpointer user_data)1283 g_tree_search (GTree *tree,
1284 GCompareFunc search_func,
1285 gconstpointer user_data)
1286 {
1287 GTreeNode *node;
1288
1289 node = g_tree_search_node (tree, search_func, user_data);
1290
1291 return node ? node->value : NULL;
1292 }
1293
1294 /**
1295 * g_tree_lower_bound:
1296 * @tree: a #GTree
1297 * @key: the key to calculate the lower bound for
1298 *
1299 * Gets the lower bound node corresponding to the given key,
1300 * or %NULL if the tree is empty or all the nodes in the tree
1301 * have keys that are strictly lower than the searched key.
1302 *
1303 * The lower bound is the first node that has its key greater
1304 * than or equal to the searched key.
1305 *
1306 * Returns: (nullable) (transfer none): the tree node corresponding to
1307 * the lower bound, or %NULL if the tree is empty or has only
1308 * keys strictly lower than the searched key.
1309 *
1310 * Since: 2.68
1311 */
1312 GTreeNode *
g_tree_lower_bound(GTree * tree,gconstpointer key)1313 g_tree_lower_bound (GTree *tree,
1314 gconstpointer key)
1315 {
1316 GTreeNode *node, *result;
1317 gint cmp;
1318
1319 g_return_val_if_fail (tree != NULL, NULL);
1320
1321 node = tree->root;
1322 if (!node)
1323 return NULL;
1324
1325 result = NULL;
1326 while (1)
1327 {
1328 cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1329 if (cmp <= 0)
1330 {
1331 result = node;
1332
1333 if (!node->left_child)
1334 return result;
1335
1336 node = node->left;
1337 }
1338 else
1339 {
1340 if (!node->right_child)
1341 return result;
1342
1343 node = node->right;
1344 }
1345 }
1346 }
1347
1348 /**
1349 * g_tree_upper_bound:
1350 * @tree: a #GTree
1351 * @key: the key to calculate the upper bound for
1352 *
1353 * Gets the upper bound node corresponding to the given key,
1354 * or %NULL if the tree is empty or all the nodes in the tree
1355 * have keys that are lower than or equal to the searched key.
1356 *
1357 * The upper bound is the first node that has its key strictly greater
1358 * than the searched key.
1359 *
1360 * Returns: (nullable) (transfer none): the tree node corresponding to the
1361 * upper bound, or %NULL if the tree is empty or has only keys
1362 * lower than or equal to the searched key.
1363 *
1364 * Since: 2.68
1365 */
1366 GTreeNode *
g_tree_upper_bound(GTree * tree,gconstpointer key)1367 g_tree_upper_bound (GTree *tree,
1368 gconstpointer key)
1369 {
1370 GTreeNode *node, *result;
1371 gint cmp;
1372
1373 g_return_val_if_fail (tree != NULL, NULL);
1374
1375 node = tree->root;
1376 if (!node)
1377 return NULL;
1378
1379 result = NULL;
1380 while (1)
1381 {
1382 cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1383 if (cmp < 0)
1384 {
1385 result = node;
1386
1387 if (!node->left_child)
1388 return result;
1389
1390 node = node->left;
1391 }
1392 else
1393 {
1394 if (!node->right_child)
1395 return result;
1396
1397 node = node->right;
1398 }
1399 }
1400 }
1401
1402 /**
1403 * g_tree_height:
1404 * @tree: a #GTree
1405 *
1406 * Gets the height of a #GTree.
1407 *
1408 * If the #GTree contains no nodes, the height is 0.
1409 * If the #GTree contains only one root node the height is 1.
1410 * If the root node has children the height is 2, etc.
1411 *
1412 * Returns: the height of @tree
1413 */
1414 gint
g_tree_height(GTree * tree)1415 g_tree_height (GTree *tree)
1416 {
1417 GTreeNode *node;
1418 gint height;
1419
1420 g_return_val_if_fail (tree != NULL, 0);
1421
1422 if (!tree->root)
1423 return 0;
1424
1425 height = 0;
1426 node = tree->root;
1427
1428 while (1)
1429 {
1430 height += 1 + MAX(node->balance, 0);
1431
1432 if (!node->left_child)
1433 return height;
1434
1435 node = node->left;
1436 }
1437 }
1438
1439 /**
1440 * g_tree_nnodes:
1441 * @tree: a #GTree
1442 *
1443 * Gets the number of nodes in a #GTree.
1444 *
1445 * Returns: the number of nodes in @tree
1446 */
1447 gint
g_tree_nnodes(GTree * tree)1448 g_tree_nnodes (GTree *tree)
1449 {
1450 g_return_val_if_fail (tree != NULL, 0);
1451
1452 return tree->nnodes;
1453 }
1454
1455 static GTreeNode *
g_tree_node_balance(GTreeNode * node)1456 g_tree_node_balance (GTreeNode *node)
1457 {
1458 if (node->balance < -1)
1459 {
1460 if (node->left->balance > 0)
1461 node->left = g_tree_node_rotate_left (node->left);
1462 node = g_tree_node_rotate_right (node);
1463 }
1464 else if (node->balance > 1)
1465 {
1466 if (node->right->balance < 0)
1467 node->right = g_tree_node_rotate_right (node->right);
1468 node = g_tree_node_rotate_left (node);
1469 }
1470
1471 return node;
1472 }
1473
1474 static GTreeNode *
g_tree_find_node(GTree * tree,gconstpointer key)1475 g_tree_find_node (GTree *tree,
1476 gconstpointer key)
1477 {
1478 GTreeNode *node;
1479 gint cmp;
1480
1481 node = tree->root;
1482 if (!node)
1483 return NULL;
1484
1485 while (1)
1486 {
1487 cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1488 if (cmp == 0)
1489 return node;
1490 else if (cmp < 0)
1491 {
1492 if (!node->left_child)
1493 return NULL;
1494
1495 node = node->left;
1496 }
1497 else
1498 {
1499 if (!node->right_child)
1500 return NULL;
1501
1502 node = node->right;
1503 }
1504 }
1505 }
1506
1507 static gint
g_tree_node_pre_order(GTreeNode * node,GTraverseFunc traverse_func,gpointer data)1508 g_tree_node_pre_order (GTreeNode *node,
1509 GTraverseFunc traverse_func,
1510 gpointer data)
1511 {
1512 if ((*traverse_func) (node->key, node->value, data))
1513 return TRUE;
1514
1515 if (node->left_child)
1516 {
1517 if (g_tree_node_pre_order (node->left, traverse_func, data))
1518 return TRUE;
1519 }
1520
1521 if (node->right_child)
1522 {
1523 if (g_tree_node_pre_order (node->right, traverse_func, data))
1524 return TRUE;
1525 }
1526
1527 return FALSE;
1528 }
1529
1530 static gint
g_tree_node_in_order(GTreeNode * node,GTraverseFunc traverse_func,gpointer data)1531 g_tree_node_in_order (GTreeNode *node,
1532 GTraverseFunc traverse_func,
1533 gpointer data)
1534 {
1535 if (node->left_child)
1536 {
1537 if (g_tree_node_in_order (node->left, traverse_func, data))
1538 return TRUE;
1539 }
1540
1541 if ((*traverse_func) (node->key, node->value, data))
1542 return TRUE;
1543
1544 if (node->right_child)
1545 {
1546 if (g_tree_node_in_order (node->right, traverse_func, data))
1547 return TRUE;
1548 }
1549
1550 return FALSE;
1551 }
1552
1553 static gint
g_tree_node_post_order(GTreeNode * node,GTraverseFunc traverse_func,gpointer data)1554 g_tree_node_post_order (GTreeNode *node,
1555 GTraverseFunc traverse_func,
1556 gpointer data)
1557 {
1558 if (node->left_child)
1559 {
1560 if (g_tree_node_post_order (node->left, traverse_func, data))
1561 return TRUE;
1562 }
1563
1564 if (node->right_child)
1565 {
1566 if (g_tree_node_post_order (node->right, traverse_func, data))
1567 return TRUE;
1568 }
1569
1570 if ((*traverse_func) (node->key, node->value, data))
1571 return TRUE;
1572
1573 return FALSE;
1574 }
1575
1576 static GTreeNode *
g_tree_node_search(GTreeNode * node,GCompareFunc search_func,gconstpointer data)1577 g_tree_node_search (GTreeNode *node,
1578 GCompareFunc search_func,
1579 gconstpointer data)
1580 {
1581 gint dir;
1582
1583 if (!node)
1584 return NULL;
1585
1586 while (1)
1587 {
1588 dir = (* search_func) (node->key, data);
1589 if (dir == 0)
1590 return node;
1591 else if (dir < 0)
1592 {
1593 if (!node->left_child)
1594 return NULL;
1595
1596 node = node->left;
1597 }
1598 else
1599 {
1600 if (!node->right_child)
1601 return NULL;
1602
1603 node = node->right;
1604 }
1605 }
1606 }
1607
1608 static GTreeNode *
g_tree_node_rotate_left(GTreeNode * node)1609 g_tree_node_rotate_left (GTreeNode *node)
1610 {
1611 GTreeNode *right;
1612 gint a_bal;
1613 gint b_bal;
1614
1615 right = node->right;
1616
1617 if (right->left_child)
1618 node->right = right->left;
1619 else
1620 {
1621 node->right_child = FALSE;
1622 right->left_child = TRUE;
1623 }
1624 right->left = node;
1625
1626 a_bal = node->balance;
1627 b_bal = right->balance;
1628
1629 if (b_bal <= 0)
1630 {
1631 if (a_bal >= 1)
1632 right->balance = b_bal - 1;
1633 else
1634 right->balance = a_bal + b_bal - 2;
1635 node->balance = a_bal - 1;
1636 }
1637 else
1638 {
1639 if (a_bal <= b_bal)
1640 right->balance = a_bal - 2;
1641 else
1642 right->balance = b_bal - 1;
1643 node->balance = a_bal - b_bal - 1;
1644 }
1645
1646 return right;
1647 }
1648
1649 static GTreeNode *
g_tree_node_rotate_right(GTreeNode * node)1650 g_tree_node_rotate_right (GTreeNode *node)
1651 {
1652 GTreeNode *left;
1653 gint a_bal;
1654 gint b_bal;
1655
1656 left = node->left;
1657
1658 if (left->right_child)
1659 node->left = left->right;
1660 else
1661 {
1662 node->left_child = FALSE;
1663 left->right_child = TRUE;
1664 }
1665 left->right = node;
1666
1667 a_bal = node->balance;
1668 b_bal = left->balance;
1669
1670 if (b_bal <= 0)
1671 {
1672 if (b_bal > a_bal)
1673 left->balance = b_bal + 1;
1674 else
1675 left->balance = a_bal + 2;
1676 node->balance = a_bal - b_bal + 1;
1677 }
1678 else
1679 {
1680 if (a_bal <= -1)
1681 left->balance = b_bal + 1;
1682 else
1683 left->balance = a_bal + b_bal + 2;
1684 node->balance = a_bal + 1;
1685 }
1686
1687 return left;
1688 }
1689
1690 #ifdef G_TREE_DEBUG
1691 static gint
g_tree_node_height(GTreeNode * node)1692 g_tree_node_height (GTreeNode *node)
1693 {
1694 gint left_height;
1695 gint right_height;
1696
1697 if (node)
1698 {
1699 left_height = 0;
1700 right_height = 0;
1701
1702 if (node->left_child)
1703 left_height = g_tree_node_height (node->left);
1704
1705 if (node->right_child)
1706 right_height = g_tree_node_height (node->right);
1707
1708 return MAX (left_height, right_height) + 1;
1709 }
1710
1711 return 0;
1712 }
1713
1714 static void
g_tree_node_check(GTreeNode * node)1715 g_tree_node_check (GTreeNode *node)
1716 {
1717 gint left_height;
1718 gint right_height;
1719 gint balance;
1720 GTreeNode *tmp;
1721
1722 if (node)
1723 {
1724 if (node->left_child)
1725 {
1726 tmp = g_tree_node_previous (node);
1727 g_assert (tmp->right == node);
1728 }
1729
1730 if (node->right_child)
1731 {
1732 tmp = g_tree_node_next (node);
1733 g_assert (tmp->left == node);
1734 }
1735
1736 left_height = 0;
1737 right_height = 0;
1738
1739 if (node->left_child)
1740 left_height = g_tree_node_height (node->left);
1741 if (node->right_child)
1742 right_height = g_tree_node_height (node->right);
1743
1744 balance = right_height - left_height;
1745 g_assert (balance == node->balance);
1746
1747 if (node->left_child)
1748 g_tree_node_check (node->left);
1749 if (node->right_child)
1750 g_tree_node_check (node->right);
1751 }
1752 }
1753
1754 static void
g_tree_node_dump(GTreeNode * node,gint indent)1755 g_tree_node_dump (GTreeNode *node,
1756 gint indent)
1757 {
1758 g_print ("%*s%c\n", indent, "", *(char *)node->key);
1759
1760 if (node->left_child)
1761 {
1762 g_print ("%*sLEFT\n", indent, "");
1763 g_tree_node_dump (node->left, indent + 2);
1764 }
1765 else if (node->left)
1766 g_print ("%*s<%c\n", indent + 2, "", *(char *)node->left->key);
1767
1768 if (node->right_child)
1769 {
1770 g_print ("%*sRIGHT\n", indent, "");
1771 g_tree_node_dump (node->right, indent + 2);
1772 }
1773 else if (node->right)
1774 g_print ("%*s>%c\n", indent + 2, "", *(char *)node->right->key);
1775 }
1776
1777 void
g_tree_dump(GTree * tree)1778 g_tree_dump (GTree *tree)
1779 {
1780 if (tree->root)
1781 g_tree_node_dump (tree->root, 0);
1782 }
1783 #endif
1784