1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
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 of the License, or (at your option) any later version.
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.
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
21 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
22 * file for a list of people on the GLib Team. See the ChangeLog
23 * files for a list of changes. These files are distributed with
24 * GLib at ftp://ftp.gtk.org/pub/gtk/.
36 #include "gtestutils.h"
40 * SECTION:trees-binary
41 * @title: Balanced Binary Trees
42 * @short_description: a sorted collection of key/value pairs optimized
43 * for searching and traversing in order
45 * The #GTree structure and its associated functions provide a sorted
46 * collection of key/value pairs optimized for searching and traversing
49 * To create a new #GTree use g_tree_new().
51 * To insert a key/value pair into a #GTree use g_tree_insert().
53 * To lookup the value corresponding to a given key, use
54 * g_tree_lookup() and g_tree_lookup_extended().
56 * To find out the number of nodes in a #GTree, use g_tree_nnodes(). To
57 * get the height of a #GTree, use g_tree_height().
59 * To traverse a #GTree, calling a function for each node visited in
60 * the traversal, use g_tree_foreach().
62 * To remove a key/value pair use g_tree_remove().
64 * To destroy a #GTree, use g_tree_destroy().
69 #define MAX_GTREE_HEIGHT 40
71 typedef struct _GTreeNode GTreeNode
;
76 * The <structname>GTree</structname> struct is an opaque data
77 * structure representing a <link
78 * linkend="glib-Balanced-Binary-Trees">Balanced Binary Tree</link>. It
79 * should be accessed only by using the following functions.
84 GCompareDataFunc key_compare
;
85 GDestroyNotify key_destroy_func
;
86 GDestroyNotify value_destroy_func
;
87 gpointer key_compare_data
;
94 gpointer key
; /* key for this node */
95 gpointer value
; /* value stored at this node */
96 GTreeNode
*left
; /* left subtree */
97 GTreeNode
*right
; /* right subtree */
98 gint8 balance
; /* height (left) - height (right) */
104 static GTreeNode
* g_tree_node_new (gpointer key
,
106 static void g_tree_insert_internal (GTree
*tree
,
110 static gboolean
g_tree_remove_internal (GTree
*tree
,
113 static GTreeNode
* g_tree_node_balance (GTreeNode
*node
);
114 static GTreeNode
*g_tree_find_node (GTree
*tree
,
116 static gint
g_tree_node_pre_order (GTreeNode
*node
,
117 GTraverseFunc traverse_func
,
119 static gint
g_tree_node_in_order (GTreeNode
*node
,
120 GTraverseFunc traverse_func
,
122 static gint
g_tree_node_post_order (GTreeNode
*node
,
123 GTraverseFunc traverse_func
,
125 static gpointer
g_tree_node_search (GTreeNode
*node
,
126 GCompareFunc search_func
,
128 static GTreeNode
* g_tree_node_rotate_left (GTreeNode
*node
);
129 static GTreeNode
* g_tree_node_rotate_right (GTreeNode
*node
);
131 static void g_tree_node_check (GTreeNode
*node
);
136 g_tree_node_new (gpointer key
,
139 GTreeNode
*node
= g_slice_new (GTreeNode
);
144 node
->left_child
= FALSE
;
145 node
->right_child
= FALSE
;
154 * @key_compare_func: the function used to order the nodes in the #GTree.
155 * It should return values similar to the standard strcmp() function -
156 * 0 if the two arguments are equal, a negative value if the first argument
157 * comes before the second, or a positive value if the first argument comes
160 * Creates a new #GTree.
162 * Return value: a new #GTree.
165 g_tree_new (GCompareFunc key_compare_func
)
167 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
169 return g_tree_new_full ((GCompareDataFunc
) key_compare_func
, NULL
,
174 * g_tree_new_with_data:
175 * @key_compare_func: qsort()-style comparison function.
176 * @key_compare_data: data to pass to comparison function.
178 * Creates a new #GTree with a comparison function that accepts user data.
179 * See g_tree_new() for more details.
181 * Return value: a new #GTree.
184 g_tree_new_with_data (GCompareDataFunc key_compare_func
,
185 gpointer key_compare_data
)
187 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
189 return g_tree_new_full (key_compare_func
, key_compare_data
,
195 * @key_compare_func: qsort()-style comparison function.
196 * @key_compare_data: data to pass to comparison function.
197 * @key_destroy_func: a function to free the memory allocated for the key
198 * used when removing the entry from the #GTree or %NULL if you don't
199 * want to supply such a function.
200 * @value_destroy_func: a function to free the memory allocated for the
201 * value used when removing the entry from the #GTree or %NULL if you
202 * don't want to supply such a function.
204 * Creates a new #GTree like g_tree_new() and allows to specify functions
205 * to free the memory allocated for the key and value that get called when
206 * removing the entry from the #GTree.
208 * Return value: a new #GTree.
211 g_tree_new_full (GCompareDataFunc key_compare_func
,
212 gpointer key_compare_data
,
213 GDestroyNotify key_destroy_func
,
214 GDestroyNotify value_destroy_func
)
218 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
220 tree
= g_slice_new (GTree
);
222 tree
->key_compare
= key_compare_func
;
223 tree
->key_destroy_func
= key_destroy_func
;
224 tree
->value_destroy_func
= value_destroy_func
;
225 tree
->key_compare_data
= key_compare_data
;
232 static inline GTreeNode
*
233 g_tree_first_node (GTree
*tree
)
242 while (tmp
->left_child
)
248 static inline GTreeNode
*
249 g_tree_node_previous (GTreeNode
*node
)
255 if (node
->left_child
)
256 while (tmp
->right_child
)
262 static inline GTreeNode
*
263 g_tree_node_next (GTreeNode
*node
)
269 if (node
->right_child
)
270 while (tmp
->left_child
)
277 g_tree_remove_all (GTree
*tree
)
282 g_return_if_fail (tree
!= NULL
);
284 node
= g_tree_first_node (tree
);
288 next
= g_tree_node_next (node
);
290 if (tree
->key_destroy_func
)
291 tree
->key_destroy_func (node
->key
);
292 if (tree
->value_destroy_func
)
293 tree
->value_destroy_func (node
->value
);
294 g_slice_free (GTreeNode
, node
);
307 * Increments the reference count of @tree by one. It is safe to call
308 * this function from any thread.
310 * Return value: the passed in #GTree.
315 g_tree_ref (GTree
*tree
)
317 g_return_val_if_fail (tree
!= NULL
, NULL
);
319 g_atomic_int_inc (&tree
->ref_count
);
328 * Decrements the reference count of @tree by one. If the reference count
329 * drops to 0, all keys and values will be destroyed (if destroy
330 * functions were specified) and all memory allocated by @tree will be
333 * It is safe to call this function from any thread.
338 g_tree_unref (GTree
*tree
)
340 g_return_if_fail (tree
!= NULL
);
342 if (g_atomic_int_dec_and_test (&tree
->ref_count
))
344 g_tree_remove_all (tree
);
345 g_slice_free (GTree
, tree
);
353 * Removes all keys and values from the #GTree and decreases its
354 * reference count by one. If keys and/or values are dynamically
355 * allocated, you should either free them first or create the #GTree
356 * using g_tree_new_full(). In the latter case the destroy functions
357 * you supplied will be called on all keys and values before destroying
361 g_tree_destroy (GTree
*tree
)
363 g_return_if_fail (tree
!= NULL
);
365 g_tree_remove_all (tree
);
372 * @key: the key to insert.
373 * @value: the value corresponding to the key.
375 * Inserts a key/value pair into a #GTree. If the given key already exists
376 * in the #GTree its corresponding value is set to the new value. If you
377 * supplied a value_destroy_func when creating the #GTree, the old value is
378 * freed using that function. If you supplied a @key_destroy_func when
379 * creating the #GTree, the passed key is freed using that function.
381 * The tree is automatically 'balanced' as new key/value pairs are added,
382 * so that the distance from the root to every leaf is as small as possible.
385 g_tree_insert (GTree
*tree
,
389 g_return_if_fail (tree
!= NULL
);
391 g_tree_insert_internal (tree
, key
, value
, FALSE
);
394 g_tree_node_check (tree
->root
);
401 * @key: the key to insert.
402 * @value: the value corresponding to the key.
404 * Inserts a new key and value into a #GTree similar to g_tree_insert().
405 * The difference is that if the key already exists in the #GTree, it gets
406 * replaced by the new key. If you supplied a @value_destroy_func when
407 * creating the #GTree, the old value is freed using that function. If you
408 * supplied a @key_destroy_func when creating the #GTree, the old key is
409 * freed using that function.
411 * The tree is automatically 'balanced' as new key/value pairs are added,
412 * so that the distance from the root to every leaf is as small as possible.
415 g_tree_replace (GTree
*tree
,
419 g_return_if_fail (tree
!= NULL
);
421 g_tree_insert_internal (tree
, key
, value
, TRUE
);
424 g_tree_node_check (tree
->root
);
428 /* internal insert routine */
430 g_tree_insert_internal (GTree
*tree
,
436 GTreeNode
*path
[MAX_GTREE_HEIGHT
];
439 g_return_if_fail (tree
!= NULL
);
443 tree
->root
= g_tree_node_new (key
, value
);
454 int cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
458 if (tree
->value_destroy_func
)
459 tree
->value_destroy_func (node
->value
);
465 if (tree
->key_destroy_func
)
466 tree
->key_destroy_func (node
->key
);
472 /* free the passed key */
473 if (tree
->key_destroy_func
)
474 tree
->key_destroy_func (key
);
481 if (node
->left_child
)
488 GTreeNode
*child
= g_tree_node_new (key
, value
);
490 child
->left
= node
->left
;
493 node
->left_child
= TRUE
;
503 if (node
->right_child
)
510 GTreeNode
*child
= g_tree_node_new (key
, value
);
512 child
->right
= node
->right
;
515 node
->right_child
= TRUE
;
525 /* restore balance. This is the goodness of a non-recursive
526 implementation, when we are done with balancing we 'break'
527 the loop and we are done. */
530 GTreeNode
*bparent
= path
[--idx
];
531 gboolean left_node
= (bparent
&& node
== bparent
->left
);
532 g_assert (!bparent
|| bparent
->left
== node
|| bparent
->right
== node
);
534 if (node
->balance
< -1 || node
->balance
> 1)
536 node
= g_tree_node_balance (node
);
540 bparent
->left
= node
;
542 bparent
->right
= node
;
545 if (node
->balance
== 0 || bparent
== NULL
)
549 bparent
->balance
-= 1;
551 bparent
->balance
+= 1;
560 * @key: the key to remove.
562 * Removes a key/value pair from a #GTree.
564 * If the #GTree was created using g_tree_new_full(), the key and value
565 * are freed using the supplied destroy functions, otherwise you have to
566 * make sure that any dynamically allocated values are freed yourself.
567 * If the key does not exist in the #GTree, the function does nothing.
569 * Returns: %TRUE if the key was found (prior to 2.8, this function returned
573 g_tree_remove (GTree
*tree
,
578 g_return_val_if_fail (tree
!= NULL
, FALSE
);
580 removed
= g_tree_remove_internal (tree
, key
, FALSE
);
583 g_tree_node_check (tree
->root
);
592 * @key: the key to remove.
594 * Removes a key and its associated value from a #GTree without calling
595 * the key and value destroy functions.
597 * If the key does not exist in the #GTree, the function does nothing.
599 * Returns: %TRUE if the key was found (prior to 2.8, this function returned
603 g_tree_steal (GTree
*tree
,
608 g_return_val_if_fail (tree
!= NULL
, FALSE
);
610 removed
= g_tree_remove_internal (tree
, key
, TRUE
);
613 g_tree_node_check (tree
->root
);
619 /* internal remove routine */
621 g_tree_remove_internal (GTree
*tree
,
625 GTreeNode
*node
, *parent
, *balance
;
626 GTreeNode
*path
[MAX_GTREE_HEIGHT
];
630 g_return_val_if_fail (tree
!= NULL
, FALSE
);
641 int cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
647 if (!node
->left_child
)
655 if (!node
->right_child
)
663 /* the following code is almost equal to g_tree_remove_node,
664 except that we do not have to call g_tree_node_parent. */
665 balance
= parent
= path
[--idx
];
666 g_assert (!parent
|| parent
->left
== node
|| parent
->right
== node
);
667 left_node
= (parent
&& node
== parent
->left
);
669 if (!node
->left_child
)
671 if (!node
->right_child
)
677 parent
->left_child
= FALSE
;
678 parent
->left
= node
->left
;
679 parent
->balance
+= 1;
683 parent
->right_child
= FALSE
;
684 parent
->right
= node
->right
;
685 parent
->balance
-= 1;
688 else /* node has a right child */
690 GTreeNode
*tmp
= g_tree_node_next (node
);
691 tmp
->left
= node
->left
;
694 tree
->root
= node
->right
;
697 parent
->left
= node
->right
;
698 parent
->balance
+= 1;
702 parent
->right
= node
->right
;
703 parent
->balance
-= 1;
707 else /* node has a left child */
709 if (!node
->right_child
)
711 GTreeNode
*tmp
= g_tree_node_previous (node
);
712 tmp
->right
= node
->right
;
715 tree
->root
= node
->left
;
718 parent
->left
= node
->left
;
719 parent
->balance
+= 1;
723 parent
->right
= node
->left
;
724 parent
->balance
-= 1;
727 else /* node has a both children (pant, pant!) */
729 GTreeNode
*prev
= node
->left
;
730 GTreeNode
*next
= node
->right
;
731 GTreeNode
*nextp
= node
;
732 int old_idx
= idx
+ 1;
735 /* path[idx] == parent */
736 /* find the immediately next node (and its parent) */
737 while (next
->left_child
)
739 path
[++idx
] = nextp
= next
;
743 path
[old_idx
] = next
;
746 /* remove 'next' from the tree */
749 if (next
->right_child
)
750 nextp
->left
= next
->right
;
752 nextp
->left_child
= FALSE
;
755 next
->right_child
= TRUE
;
756 next
->right
= node
->right
;
761 /* set the prev to point to the right place */
762 while (prev
->right_child
)
766 /* prepare 'next' to replace 'node' */
767 next
->left_child
= TRUE
;
768 next
->left
= node
->left
;
769 next
->balance
= node
->balance
;
776 parent
->right
= next
;
780 /* restore balance */
784 GTreeNode
*bparent
= path
[--idx
];
785 g_assert (!bparent
|| bparent
->left
== balance
|| bparent
->right
== balance
);
786 left_node
= (bparent
&& balance
== bparent
->left
);
788 if(balance
->balance
< -1 || balance
->balance
> 1)
790 balance
= g_tree_node_balance (balance
);
792 tree
->root
= balance
;
794 bparent
->left
= balance
;
796 bparent
->right
= balance
;
799 if (balance
->balance
!= 0 || !bparent
)
803 bparent
->balance
+= 1;
805 bparent
->balance
-= 1;
812 if (tree
->key_destroy_func
)
813 tree
->key_destroy_func (node
->key
);
814 if (tree
->value_destroy_func
)
815 tree
->value_destroy_func (node
->value
);
818 g_slice_free (GTreeNode
, node
);
828 * @key: the key to look up.
830 * Gets the value corresponding to the given key. Since a #GTree is
831 * automatically balanced as key/value pairs are added, key lookup is very
834 * Return value: the value corresponding to the key, or %NULL if the key was
838 g_tree_lookup (GTree
*tree
,
843 g_return_val_if_fail (tree
!= NULL
, NULL
);
845 node
= g_tree_find_node (tree
, key
);
847 return node
? node
->value
: NULL
;
851 * g_tree_lookup_extended:
853 * @lookup_key: the key to look up.
854 * @orig_key: returns the original key.
855 * @value: returns the value associated with the key.
857 * Looks up a key in the #GTree, returning the original key and the
858 * associated value and a #gboolean which is %TRUE if the key was found. This
859 * is useful if you need to free the memory allocated for the original key,
860 * for example before calling g_tree_remove().
862 * Return value: %TRUE if the key was found in the #GTree.
865 g_tree_lookup_extended (GTree
*tree
,
866 gconstpointer lookup_key
,
872 g_return_val_if_fail (tree
!= NULL
, FALSE
);
874 node
= g_tree_find_node (tree
, lookup_key
);
879 *orig_key
= node
->key
;
881 *value
= node
->value
;
891 * @func: the function to call for each node visited. If this function
892 * returns %TRUE, the traversal is stopped.
893 * @user_data: user data to pass to the function.
895 * Calls the given function for each of the key/value pairs in the #GTree.
896 * The function is passed the key and value of each pair, and the given
897 * @data parameter. The tree is traversed in sorted order.
899 * The tree may not be modified while iterating over it (you can't
900 * add/remove items). To remove all items matching a predicate, you need
901 * to add each item to a list in your #GTraverseFunc as you walk over
902 * the tree, then walk the list and remove each item.
905 g_tree_foreach (GTree
*tree
,
911 g_return_if_fail (tree
!= NULL
);
916 node
= g_tree_first_node (tree
);
920 if ((*func
) (node
->key
, node
->value
, user_data
))
923 node
= g_tree_node_next (node
);
930 * @traverse_func: the function to call for each node visited. If this
931 * function returns %TRUE, the traversal is stopped.
932 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
933 * %G_PRE_ORDER and %G_POST_ORDER.
934 * @user_data: user data to pass to the function.
936 * Calls the given function for each node in the #GTree.
938 * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary. If you
939 * just want to visit all nodes in sorted order, use g_tree_foreach()
940 * instead. If you really need to visit nodes in a different order, consider
941 * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
945 * @key: a key of a #GTree node.
946 * @value: the value corresponding to the key.
947 * @data: user data passed to g_tree_traverse().
948 * @Returns: %TRUE to stop the traversal.
950 * Specifies the type of function passed to g_tree_traverse(). It is
951 * passed the key and value of each node, together with the @user_data
952 * parameter passed to g_tree_traverse(). If the function returns
953 * %TRUE, the traversal is stopped.
957 * @G_IN_ORDER: vists a node's left child first, then the node itself,
958 * then its right child. This is the one to use if you
959 * want the output sorted according to the compare
961 * @G_PRE_ORDER: visits a node, then its children.
962 * @G_POST_ORDER: visits the node's children, then the node itself.
963 * @G_LEVEL_ORDER: is not implemented for <link
964 * linkend="glib-Balanced-Binary-Trees">Balanced Binary
965 * Trees</link>. For <link
966 * linkend="glib-N-ary-Trees">N-ary Trees</link>, it
967 * vists the root node first, then its children, then
968 * its grandchildren, and so on. Note that this is less
969 * efficient than the other orders.
971 * Specifies the type of traveral performed by g_tree_traverse(),
972 * g_node_traverse() and g_node_find().
975 g_tree_traverse (GTree
*tree
,
976 GTraverseFunc traverse_func
,
977 GTraverseType traverse_type
,
980 g_return_if_fail (tree
!= NULL
);
985 switch (traverse_type
)
988 g_tree_node_pre_order (tree
->root
, traverse_func
, user_data
);
992 g_tree_node_in_order (tree
->root
, traverse_func
, user_data
);
996 g_tree_node_post_order (tree
->root
, traverse_func
, user_data
);
1000 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
1008 * @search_func: a function used to search the #GTree
1009 * @user_data: the data passed as the second argument to @search_func
1011 * Searches a #GTree using @search_func.
1013 * The @search_func is called with a pointer to the key of a key/value
1014 * pair in the tree, and the passed in @user_data. If @search_func returns
1015 * 0 for a key/value pair, then the corresponding value is returned as
1016 * the result of g_tree_search(). If @search_func returns -1, searching
1017 * will proceed among the key/value pairs that have a smaller key; if
1018 * @search_func returns 1, searching will proceed among the key/value
1019 * pairs that have a larger key.
1021 * Return value: the value corresponding to the found key, or %NULL if
1022 * the key was not found.
1025 g_tree_search (GTree
*tree
,
1026 GCompareFunc search_func
,
1027 gconstpointer user_data
)
1029 g_return_val_if_fail (tree
!= NULL
, NULL
);
1032 return g_tree_node_search (tree
->root
, search_func
, user_data
);
1041 * Gets the height of a #GTree.
1043 * If the #GTree contains no nodes, the height is 0.
1044 * If the #GTree contains only one root node the height is 1.
1045 * If the root node has children the height is 2, etc.
1047 * Return value: the height of the #GTree.
1050 g_tree_height (GTree
*tree
)
1055 g_return_val_if_fail (tree
!= NULL
, 0);
1065 height
+= 1 + MAX(node
->balance
, 0);
1067 if (!node
->left_child
)
1078 * Gets the number of nodes in a #GTree.
1080 * Return value: the number of nodes in the #GTree.
1083 g_tree_nnodes (GTree
*tree
)
1085 g_return_val_if_fail (tree
!= NULL
, 0);
1087 return tree
->nnodes
;
1091 g_tree_node_balance (GTreeNode
*node
)
1093 if (node
->balance
< -1)
1095 if (node
->left
->balance
> 0)
1096 node
->left
= g_tree_node_rotate_left (node
->left
);
1097 node
= g_tree_node_rotate_right (node
);
1099 else if (node
->balance
> 1)
1101 if (node
->right
->balance
< 0)
1102 node
->right
= g_tree_node_rotate_right (node
->right
);
1103 node
= g_tree_node_rotate_left (node
);
1110 g_tree_find_node (GTree
*tree
,
1122 cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
1127 if (!node
->left_child
)
1134 if (!node
->right_child
)
1143 g_tree_node_pre_order (GTreeNode
*node
,
1144 GTraverseFunc traverse_func
,
1147 if ((*traverse_func
) (node
->key
, node
->value
, data
))
1150 if (node
->left_child
)
1152 if (g_tree_node_pre_order (node
->left
, traverse_func
, data
))
1156 if (node
->right_child
)
1158 if (g_tree_node_pre_order (node
->right
, traverse_func
, data
))
1166 g_tree_node_in_order (GTreeNode
*node
,
1167 GTraverseFunc traverse_func
,
1170 if (node
->left_child
)
1172 if (g_tree_node_in_order (node
->left
, traverse_func
, data
))
1176 if ((*traverse_func
) (node
->key
, node
->value
, data
))
1179 if (node
->right_child
)
1181 if (g_tree_node_in_order (node
->right
, traverse_func
, data
))
1189 g_tree_node_post_order (GTreeNode
*node
,
1190 GTraverseFunc traverse_func
,
1193 if (node
->left_child
)
1195 if (g_tree_node_post_order (node
->left
, traverse_func
, data
))
1199 if (node
->right_child
)
1201 if (g_tree_node_post_order (node
->right
, traverse_func
, data
))
1205 if ((*traverse_func
) (node
->key
, node
->value
, data
))
1212 g_tree_node_search (GTreeNode
*node
,
1213 GCompareFunc search_func
,
1223 dir
= (* search_func
) (node
->key
, data
);
1228 if (!node
->left_child
)
1235 if (!node
->right_child
)
1244 g_tree_node_rotate_left (GTreeNode
*node
)
1250 right
= node
->right
;
1252 if (right
->left_child
)
1253 node
->right
= right
->left
;
1256 node
->right_child
= FALSE
;
1257 node
->right
= right
;
1258 right
->left_child
= TRUE
;
1262 a_bal
= node
->balance
;
1263 b_bal
= right
->balance
;
1268 right
->balance
= b_bal
- 1;
1270 right
->balance
= a_bal
+ b_bal
- 2;
1271 node
->balance
= a_bal
- 1;
1276 right
->balance
= a_bal
- 2;
1278 right
->balance
= b_bal
- 1;
1279 node
->balance
= a_bal
- b_bal
- 1;
1286 g_tree_node_rotate_right (GTreeNode
*node
)
1294 if (left
->right_child
)
1295 node
->left
= left
->right
;
1298 node
->left_child
= FALSE
;
1300 left
->right_child
= TRUE
;
1304 a_bal
= node
->balance
;
1305 b_bal
= left
->balance
;
1310 left
->balance
= b_bal
+ 1;
1312 left
->balance
= a_bal
+ 2;
1313 node
->balance
= a_bal
- b_bal
+ 1;
1318 left
->balance
= b_bal
+ 1;
1320 left
->balance
= a_bal
+ b_bal
+ 2;
1321 node
->balance
= a_bal
+ 1;
1329 g_tree_node_height (GTreeNode
*node
)
1339 if (node
->left_child
)
1340 left_height
= g_tree_node_height (node
->left
);
1342 if (node
->right_child
)
1343 right_height
= g_tree_node_height (node
->right
);
1345 return MAX (left_height
, right_height
) + 1;
1352 g_tree_node_check (GTreeNode
*node
)
1361 if (node
->left_child
)
1363 tmp
= g_tree_node_previous (node
);
1364 g_assert (tmp
->right
== node
);
1367 if (node
->right_child
)
1369 tmp
= g_tree_node_next (node
);
1370 g_assert (tmp
->left
== node
);
1376 if (node
->left_child
)
1377 left_height
= g_tree_node_height (node
->left
);
1378 if (node
->right_child
)
1379 right_height
= g_tree_node_height (node
->right
);
1381 balance
= right_height
- left_height
;
1382 g_assert (balance
== node
->balance
);
1384 if (node
->left_child
)
1385 g_tree_node_check (node
->left
);
1386 if (node
->right_child
)
1387 g_tree_node_check (node
->right
);
1392 g_tree_node_dump (GTreeNode
*node
,
1395 g_print ("%*s%c\n", indent
, "", *(char *)node
->key
);
1397 if (node
->left_child
)
1398 g_tree_node_dump (node
->left
, indent
+ 2);
1399 else if (node
->left
)
1400 g_print ("%*s<%c\n", indent
+ 2, "", *(char *)node
->left
->key
);
1402 if (node
->right_child
)
1403 g_tree_node_dump (node
->right
, indent
+ 2);
1404 else if (node
->right
)
1405 g_print ("%*s>%c\n", indent
+ 2, "", *(char *)node
->right
->key
);
1410 g_tree_dump (GTree
*tree
)
1413 g_tree_node_dump (tree
->root
, 0);