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"
39 * SECTION: trees-binary
40 * @title: Balanced Binary Trees
41 * @short_description: a sorted collection of key/value pairs optimized
42 * for searching and traversing in order
44 * The #GTree structure and its associated functions provide a sorted
45 * collection of key/value pairs optimized for searching and traversing
48 * To create a new #GTree use g_tree_new().
50 * To insert a key/value pair into a #GTree use g_tree_insert().
52 * To lookup the value corresponding to a given key, use
53 * g_tree_lookup() and g_tree_lookup_extended().
55 * To find out the number of nodes in a #GTree, use g_tree_nnodes(). To
56 * get the height of a #GTree, use g_tree_height().
58 * To traverse a #GTree, calling a function for each node visited in
59 * the traversal, use g_tree_foreach().
61 * To remove a key/value pair use g_tree_remove().
63 * To destroy a #GTree, use g_tree_destroy().
68 #define MAX_GTREE_HEIGHT 40
70 typedef struct _GTreeNode GTreeNode
;
75 * The <structname>GTree</structname> struct is an opaque data
76 * structure representing a <link
77 * linkend="glib-Balanced-Binary-Trees">Balanced Binary Tree</link>. It
78 * should be accessed only by using the following functions.
83 GCompareDataFunc key_compare
;
84 GDestroyNotify key_destroy_func
;
85 GDestroyNotify value_destroy_func
;
86 gpointer key_compare_data
;
93 gpointer key
; /* key for this node */
94 gpointer value
; /* value stored at this node */
95 GTreeNode
*left
; /* left subtree */
96 GTreeNode
*right
; /* right subtree */
97 gint8 balance
; /* height (left) - height (right) */
103 static GTreeNode
* g_tree_node_new (gpointer key
,
105 static void g_tree_insert_internal (GTree
*tree
,
109 static gboolean
g_tree_remove_internal (GTree
*tree
,
112 static GTreeNode
* g_tree_node_balance (GTreeNode
*node
);
113 static GTreeNode
*g_tree_find_node (GTree
*tree
,
115 static gint
g_tree_node_pre_order (GTreeNode
*node
,
116 GTraverseFunc traverse_func
,
118 static gint
g_tree_node_in_order (GTreeNode
*node
,
119 GTraverseFunc traverse_func
,
121 static gint
g_tree_node_post_order (GTreeNode
*node
,
122 GTraverseFunc traverse_func
,
124 static gpointer
g_tree_node_search (GTreeNode
*node
,
125 GCompareFunc search_func
,
127 static GTreeNode
* g_tree_node_rotate_left (GTreeNode
*node
);
128 static GTreeNode
* g_tree_node_rotate_right (GTreeNode
*node
);
130 static void g_tree_node_check (GTreeNode
*node
);
135 g_tree_node_new (gpointer key
,
138 GTreeNode
*node
= g_slice_new (GTreeNode
);
143 node
->left_child
= FALSE
;
144 node
->right_child
= FALSE
;
153 * @key_compare_func: the function used to order the nodes in the #GTree.
154 * It should return values similar to the standard strcmp() function -
155 * 0 if the two arguments are equal, a negative value if the first argument
156 * comes before the second, or a positive value if the first argument comes
159 * Creates a new #GTree.
161 * Return value: a new #GTree.
164 g_tree_new (GCompareFunc key_compare_func
)
166 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
168 return g_tree_new_full ((GCompareDataFunc
) key_compare_func
, NULL
,
173 * g_tree_new_with_data:
174 * @key_compare_func: qsort()-style comparison function.
175 * @key_compare_data: data to pass to comparison function.
177 * Creates a new #GTree with a comparison function that accepts user data.
178 * See g_tree_new() for more details.
180 * Return value: a new #GTree.
183 g_tree_new_with_data (GCompareDataFunc key_compare_func
,
184 gpointer key_compare_data
)
186 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
188 return g_tree_new_full (key_compare_func
, key_compare_data
,
194 * @key_compare_func: qsort()-style comparison function.
195 * @key_compare_data: data to pass to comparison function.
196 * @key_destroy_func: a function to free the memory allocated for the key
197 * used when removing the entry from the #GTree or %NULL if you don't
198 * want to supply such a function.
199 * @value_destroy_func: a function to free the memory allocated for the
200 * value used when removing the entry from the #GTree or %NULL if you
201 * don't want to supply such a function.
203 * Creates a new #GTree like g_tree_new() and allows to specify functions
204 * to free the memory allocated for the key and value that get called when
205 * removing the entry from the #GTree.
207 * Return value: a new #GTree.
210 g_tree_new_full (GCompareDataFunc key_compare_func
,
211 gpointer key_compare_data
,
212 GDestroyNotify key_destroy_func
,
213 GDestroyNotify value_destroy_func
)
217 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
219 tree
= g_slice_new (GTree
);
221 tree
->key_compare
= key_compare_func
;
222 tree
->key_destroy_func
= key_destroy_func
;
223 tree
->value_destroy_func
= value_destroy_func
;
224 tree
->key_compare_data
= key_compare_data
;
231 static inline GTreeNode
*
232 g_tree_first_node (GTree
*tree
)
241 while (tmp
->left_child
)
247 static inline GTreeNode
*
248 g_tree_node_previous (GTreeNode
*node
)
254 if (node
->left_child
)
255 while (tmp
->right_child
)
261 static inline GTreeNode
*
262 g_tree_node_next (GTreeNode
*node
)
268 if (node
->right_child
)
269 while (tmp
->left_child
)
276 g_tree_remove_all (GTree
*tree
)
281 g_return_if_fail (tree
!= NULL
);
283 node
= g_tree_first_node (tree
);
287 next
= g_tree_node_next (node
);
289 if (tree
->key_destroy_func
)
290 tree
->key_destroy_func (node
->key
);
291 if (tree
->value_destroy_func
)
292 tree
->value_destroy_func (node
->value
);
293 g_slice_free (GTreeNode
, node
);
306 * Increments the reference count of @tree by one. It is safe to call
307 * this function from any thread.
309 * Return value: the passed in #GTree.
314 g_tree_ref (GTree
*tree
)
316 g_return_val_if_fail (tree
!= NULL
, NULL
);
318 g_atomic_int_inc (&tree
->ref_count
);
327 * Decrements the reference count of @tree by one. If the reference count
328 * drops to 0, all keys and values will be destroyed (if destroy
329 * functions were specified) and all memory allocated by @tree will be
332 * It is safe to call this function from any thread.
337 g_tree_unref (GTree
*tree
)
339 g_return_if_fail (tree
!= NULL
);
341 if (g_atomic_int_dec_and_test (&tree
->ref_count
))
343 g_tree_remove_all (tree
);
344 g_slice_free (GTree
, tree
);
352 * Removes all keys and values from the #GTree and decreases its
353 * reference count by one. If keys and/or values are dynamically
354 * allocated, you should either free them first or create the #GTree
355 * using g_tree_new_full(). In the latter case the destroy functions
356 * you supplied will be called on all keys and values before destroying
360 g_tree_destroy (GTree
*tree
)
362 g_return_if_fail (tree
!= NULL
);
364 g_tree_remove_all (tree
);
371 * @key: the key to insert.
372 * @value: the value corresponding to the key.
374 * Inserts a key/value pair into a #GTree. If the given key already exists
375 * in the #GTree its corresponding value is set to the new value. If you
376 * supplied a value_destroy_func when creating the #GTree, the old value is
377 * freed using that function. If you supplied a @key_destroy_func when
378 * creating the #GTree, the passed key is freed using that function.
380 * The tree is automatically 'balanced' as new key/value pairs are added,
381 * so that the distance from the root to every leaf is as small as possible.
384 g_tree_insert (GTree
*tree
,
388 g_return_if_fail (tree
!= NULL
);
390 g_tree_insert_internal (tree
, key
, value
, FALSE
);
393 g_tree_node_check (tree
->root
);
400 * @key: the key to insert.
401 * @value: the value corresponding to the key.
403 * Inserts a new key and value into a #GTree similar to g_tree_insert().
404 * The difference is that if the key already exists in the #GTree, it gets
405 * replaced by the new key. If you supplied a @value_destroy_func when
406 * creating the #GTree, the old value is freed using that function. If you
407 * supplied a @key_destroy_func when creating the #GTree, the old key is
408 * freed using that function.
410 * The tree is automatically 'balanced' as new key/value pairs are added,
411 * so that the distance from the root to every leaf is as small as possible.
414 g_tree_replace (GTree
*tree
,
418 g_return_if_fail (tree
!= NULL
);
420 g_tree_insert_internal (tree
, key
, value
, TRUE
);
423 g_tree_node_check (tree
->root
);
427 /* internal insert routine */
429 g_tree_insert_internal (GTree
*tree
,
435 GTreeNode
*path
[MAX_GTREE_HEIGHT
];
438 g_return_if_fail (tree
!= NULL
);
442 tree
->root
= g_tree_node_new (key
, value
);
453 int cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
457 if (tree
->value_destroy_func
)
458 tree
->value_destroy_func (node
->value
);
464 if (tree
->key_destroy_func
)
465 tree
->key_destroy_func (node
->key
);
471 /* free the passed key */
472 if (tree
->key_destroy_func
)
473 tree
->key_destroy_func (key
);
480 if (node
->left_child
)
487 GTreeNode
*child
= g_tree_node_new (key
, value
);
489 child
->left
= node
->left
;
492 node
->left_child
= TRUE
;
502 if (node
->right_child
)
509 GTreeNode
*child
= g_tree_node_new (key
, value
);
511 child
->right
= node
->right
;
514 node
->right_child
= TRUE
;
524 /* restore balance. This is the goodness of a non-recursive
525 implementation, when we are done with balancing we 'break'
526 the loop and we are done. */
529 GTreeNode
*bparent
= path
[--idx
];
530 gboolean left_node
= (bparent
&& node
== bparent
->left
);
531 g_assert (!bparent
|| bparent
->left
== node
|| bparent
->right
== node
);
533 if (node
->balance
< -1 || node
->balance
> 1)
535 node
= g_tree_node_balance (node
);
539 bparent
->left
= node
;
541 bparent
->right
= node
;
544 if (node
->balance
== 0 || bparent
== NULL
)
548 bparent
->balance
-= 1;
550 bparent
->balance
+= 1;
559 * @key: the key to remove.
561 * Removes a key/value pair from a #GTree.
563 * If the #GTree was created using g_tree_new_full(), the key and value
564 * are freed using the supplied destroy functions, otherwise you have to
565 * make sure that any dynamically allocated values are freed yourself.
566 * If the key does not exist in the #GTree, the function does nothing.
568 * Returns: %TRUE if the key was found (prior to 2.8, this function returned
572 g_tree_remove (GTree
*tree
,
577 g_return_val_if_fail (tree
!= NULL
, FALSE
);
579 removed
= g_tree_remove_internal (tree
, key
, FALSE
);
582 g_tree_node_check (tree
->root
);
591 * @key: the key to remove.
593 * Removes a key and its associated value from a #GTree without calling
594 * the key and value destroy functions.
596 * If the key does not exist in the #GTree, the function does nothing.
598 * Returns: %TRUE if the key was found (prior to 2.8, this function returned
602 g_tree_steal (GTree
*tree
,
607 g_return_val_if_fail (tree
!= NULL
, FALSE
);
609 removed
= g_tree_remove_internal (tree
, key
, TRUE
);
612 g_tree_node_check (tree
->root
);
618 /* internal remove routine */
620 g_tree_remove_internal (GTree
*tree
,
624 GTreeNode
*node
, *parent
, *balance
;
625 GTreeNode
*path
[MAX_GTREE_HEIGHT
];
629 g_return_val_if_fail (tree
!= NULL
, FALSE
);
640 int cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
646 if (!node
->left_child
)
654 if (!node
->right_child
)
662 /* the following code is almost equal to g_tree_remove_node,
663 except that we do not have to call g_tree_node_parent. */
664 balance
= parent
= path
[--idx
];
665 g_assert (!parent
|| parent
->left
== node
|| parent
->right
== node
);
666 left_node
= (parent
&& node
== parent
->left
);
668 if (!node
->left_child
)
670 if (!node
->right_child
)
676 parent
->left_child
= FALSE
;
677 parent
->left
= node
->left
;
678 parent
->balance
+= 1;
682 parent
->right_child
= FALSE
;
683 parent
->right
= node
->right
;
684 parent
->balance
-= 1;
687 else /* node has a right child */
689 GTreeNode
*tmp
= g_tree_node_next (node
);
690 tmp
->left
= node
->left
;
693 tree
->root
= node
->right
;
696 parent
->left
= node
->right
;
697 parent
->balance
+= 1;
701 parent
->right
= node
->right
;
702 parent
->balance
-= 1;
706 else /* node has a left child */
708 if (!node
->right_child
)
710 GTreeNode
*tmp
= g_tree_node_previous (node
);
711 tmp
->right
= node
->right
;
714 tree
->root
= node
->left
;
717 parent
->left
= node
->left
;
718 parent
->balance
+= 1;
722 parent
->right
= node
->left
;
723 parent
->balance
-= 1;
726 else /* node has a both children (pant, pant!) */
728 GTreeNode
*prev
= node
->left
;
729 GTreeNode
*next
= node
->right
;
730 GTreeNode
*nextp
= node
;
731 int old_idx
= idx
+ 1;
734 /* path[idx] == parent */
735 /* find the immediately next node (and its parent) */
736 while (next
->left_child
)
738 path
[++idx
] = nextp
= next
;
742 path
[old_idx
] = next
;
745 /* remove 'next' from the tree */
748 if (next
->right_child
)
749 nextp
->left
= next
->right
;
751 nextp
->left_child
= FALSE
;
754 next
->right_child
= TRUE
;
755 next
->right
= node
->right
;
760 /* set the prev to point to the right place */
761 while (prev
->right_child
)
765 /* prepare 'next' to replace 'node' */
766 next
->left_child
= TRUE
;
767 next
->left
= node
->left
;
768 next
->balance
= node
->balance
;
775 parent
->right
= next
;
779 /* restore balance */
783 GTreeNode
*bparent
= path
[--idx
];
784 g_assert (!bparent
|| bparent
->left
== balance
|| bparent
->right
== balance
);
785 left_node
= (bparent
&& balance
== bparent
->left
);
787 if(balance
->balance
< -1 || balance
->balance
> 1)
789 balance
= g_tree_node_balance (balance
);
791 tree
->root
= balance
;
793 bparent
->left
= balance
;
795 bparent
->right
= balance
;
798 if (balance
->balance
!= 0 || !bparent
)
802 bparent
->balance
+= 1;
804 bparent
->balance
-= 1;
811 if (tree
->key_destroy_func
)
812 tree
->key_destroy_func (node
->key
);
813 if (tree
->value_destroy_func
)
814 tree
->value_destroy_func (node
->value
);
817 g_slice_free (GTreeNode
, node
);
827 * @key: the key to look up.
829 * Gets the value corresponding to the given key. Since a #GTree is
830 * automatically balanced as key/value pairs are added, key lookup is very
833 * Return value: the value corresponding to the key, or %NULL if the key was
837 g_tree_lookup (GTree
*tree
,
842 g_return_val_if_fail (tree
!= NULL
, NULL
);
844 node
= g_tree_find_node (tree
, key
);
846 return node
? node
->value
: NULL
;
850 * g_tree_lookup_extended:
852 * @lookup_key: the key to look up.
853 * @orig_key: returns the original key.
854 * @value: returns the value associated with the key.
856 * Looks up a key in the #GTree, returning the original key and the
857 * associated value and a #gboolean which is %TRUE if the key was found. This
858 * is useful if you need to free the memory allocated for the original key,
859 * for example before calling g_tree_remove().
861 * Return value: %TRUE if the key was found in the #GTree.
864 g_tree_lookup_extended (GTree
*tree
,
865 gconstpointer lookup_key
,
871 g_return_val_if_fail (tree
!= NULL
, FALSE
);
873 node
= g_tree_find_node (tree
, lookup_key
);
878 *orig_key
= node
->key
;
880 *value
= node
->value
;
890 * @func: the function to call for each node visited. If this function
891 * returns %TRUE, the traversal is stopped.
892 * @user_data: user data to pass to the function.
894 * Calls the given function for each of the key/value pairs in the #GTree.
895 * The function is passed the key and value of each pair, and the given
896 * @data parameter. The tree is traversed in sorted order.
898 * The tree may not be modified while iterating over it (you can't
899 * add/remove items). To remove all items matching a predicate, you need
900 * to add each item to a list in your #GTraverseFunc as you walk over
901 * the tree, then walk the list and remove each item.
904 g_tree_foreach (GTree
*tree
,
910 g_return_if_fail (tree
!= NULL
);
915 node
= g_tree_first_node (tree
);
919 if ((*func
) (node
->key
, node
->value
, user_data
))
922 node
= g_tree_node_next (node
);
929 * @traverse_func: the function to call for each node visited. If this
930 * function returns %TRUE, the traversal is stopped.
931 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
932 * %G_PRE_ORDER and %G_POST_ORDER.
933 * @user_data: user data to pass to the function.
935 * Calls the given function for each node in the #GTree.
937 * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary. If you
938 * just want to visit all nodes in sorted order, use g_tree_foreach()
939 * instead. If you really need to visit nodes in a different order, consider
940 * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
944 * @key: a key of a #GTree node.
945 * @value: the value corresponding to the key.
946 * @data: user data passed to g_tree_traverse().
947 * @Returns: %TRUE to stop the traversal.
949 * Specifies the type of function passed to g_tree_traverse(). It is
950 * passed the key and value of each node, together with the @user_data
951 * parameter passed to g_tree_traverse(). If the function returns
952 * %TRUE, the traversal is stopped.
956 * @G_IN_ORDER: vists a node's left child first, then the node itself,
957 * then its right child. This is the one to use if you
958 * want the output sorted according to the compare
960 * @G_PRE_ORDER: visits a node, then its children.
961 * @G_POST_ORDER: visits the node's children, then the node itself.
962 * @G_LEVEL_ORDER: is not implemented for <link
963 * linkend="glib-Balanced-Binary-Trees">Balanced Binary
964 * Trees</link>. For <link
965 * linkend="glib-N-ary-Trees">N-ary Trees</link>, it
966 * vists the root node first, then its children, then
967 * its grandchildren, and so on. Note that this is less
968 * efficient than the other orders.
970 * Specifies the type of traveral performed by g_tree_traverse(),
971 * g_node_traverse() and g_node_find().
974 g_tree_traverse (GTree
*tree
,
975 GTraverseFunc traverse_func
,
976 GTraverseType traverse_type
,
979 g_return_if_fail (tree
!= NULL
);
984 switch (traverse_type
)
987 g_tree_node_pre_order (tree
->root
, traverse_func
, user_data
);
991 g_tree_node_in_order (tree
->root
, traverse_func
, user_data
);
995 g_tree_node_post_order (tree
->root
, traverse_func
, user_data
);
999 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
1007 * @search_func: a function used to search the #GTree.
1008 * @user_data: the data passed as the second argument to the @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 pair in
1014 * the tree, and the passed in @user_data. If @search_func returns 0 for a
1015 * key/value pair, then g_tree_search_func() will return the value of that
1016 * pair. If @search_func returns -1, searching will proceed among the
1017 * key/value pairs that have a smaller key; if @search_func returns 1,
1018 * searching will proceed among the key/value pairs that have a larger key.
1020 * Return value: the value corresponding to the found key, or %NULL if the key
1024 g_tree_search (GTree
*tree
,
1025 GCompareFunc search_func
,
1026 gconstpointer user_data
)
1028 g_return_val_if_fail (tree
!= NULL
, NULL
);
1031 return g_tree_node_search (tree
->root
, search_func
, user_data
);
1040 * Gets the height of a #GTree.
1042 * If the #GTree contains no nodes, the height is 0.
1043 * If the #GTree contains only one root node the height is 1.
1044 * If the root node has children the height is 2, etc.
1046 * Return value: the height of the #GTree.
1049 g_tree_height (GTree
*tree
)
1054 g_return_val_if_fail (tree
!= NULL
, 0);
1064 height
+= 1 + MAX(node
->balance
, 0);
1066 if (!node
->left_child
)
1077 * Gets the number of nodes in a #GTree.
1079 * Return value: the number of nodes in the #GTree.
1082 g_tree_nnodes (GTree
*tree
)
1084 g_return_val_if_fail (tree
!= NULL
, 0);
1086 return tree
->nnodes
;
1090 g_tree_node_balance (GTreeNode
*node
)
1092 if (node
->balance
< -1)
1094 if (node
->left
->balance
> 0)
1095 node
->left
= g_tree_node_rotate_left (node
->left
);
1096 node
= g_tree_node_rotate_right (node
);
1098 else if (node
->balance
> 1)
1100 if (node
->right
->balance
< 0)
1101 node
->right
= g_tree_node_rotate_right (node
->right
);
1102 node
= g_tree_node_rotate_left (node
);
1109 g_tree_find_node (GTree
*tree
,
1121 cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
1126 if (!node
->left_child
)
1133 if (!node
->right_child
)
1142 g_tree_node_pre_order (GTreeNode
*node
,
1143 GTraverseFunc traverse_func
,
1146 if ((*traverse_func
) (node
->key
, node
->value
, data
))
1149 if (node
->left_child
)
1151 if (g_tree_node_pre_order (node
->left
, traverse_func
, data
))
1155 if (node
->right_child
)
1157 if (g_tree_node_pre_order (node
->right
, traverse_func
, data
))
1165 g_tree_node_in_order (GTreeNode
*node
,
1166 GTraverseFunc traverse_func
,
1169 if (node
->left_child
)
1171 if (g_tree_node_in_order (node
->left
, traverse_func
, data
))
1175 if ((*traverse_func
) (node
->key
, node
->value
, data
))
1178 if (node
->right_child
)
1180 if (g_tree_node_in_order (node
->right
, traverse_func
, data
))
1188 g_tree_node_post_order (GTreeNode
*node
,
1189 GTraverseFunc traverse_func
,
1192 if (node
->left_child
)
1194 if (g_tree_node_post_order (node
->left
, traverse_func
, data
))
1198 if (node
->right_child
)
1200 if (g_tree_node_post_order (node
->right
, traverse_func
, data
))
1204 if ((*traverse_func
) (node
->key
, node
->value
, data
))
1211 g_tree_node_search (GTreeNode
*node
,
1212 GCompareFunc search_func
,
1222 dir
= (* search_func
) (node
->key
, data
);
1227 if (!node
->left_child
)
1234 if (!node
->right_child
)
1243 g_tree_node_rotate_left (GTreeNode
*node
)
1249 right
= node
->right
;
1251 if (right
->left_child
)
1252 node
->right
= right
->left
;
1255 node
->right_child
= FALSE
;
1256 node
->right
= right
;
1257 right
->left_child
= TRUE
;
1261 a_bal
= node
->balance
;
1262 b_bal
= right
->balance
;
1267 right
->balance
= b_bal
- 1;
1269 right
->balance
= a_bal
+ b_bal
- 2;
1270 node
->balance
= a_bal
- 1;
1275 right
->balance
= a_bal
- 2;
1277 right
->balance
= b_bal
- 1;
1278 node
->balance
= a_bal
- b_bal
- 1;
1285 g_tree_node_rotate_right (GTreeNode
*node
)
1293 if (left
->right_child
)
1294 node
->left
= left
->right
;
1297 node
->left_child
= FALSE
;
1299 left
->right_child
= TRUE
;
1303 a_bal
= node
->balance
;
1304 b_bal
= left
->balance
;
1309 left
->balance
= b_bal
+ 1;
1311 left
->balance
= a_bal
+ 2;
1312 node
->balance
= a_bal
- b_bal
+ 1;
1317 left
->balance
= b_bal
+ 1;
1319 left
->balance
= a_bal
+ b_bal
+ 2;
1320 node
->balance
= a_bal
+ 1;
1328 g_tree_node_height (GTreeNode
*node
)
1338 if (node
->left_child
)
1339 left_height
= g_tree_node_height (node
->left
);
1341 if (node
->right_child
)
1342 right_height
= g_tree_node_height (node
->right
);
1344 return MAX (left_height
, right_height
) + 1;
1351 g_tree_node_check (GTreeNode
*node
)
1360 if (node
->left_child
)
1362 tmp
= g_tree_node_previous (node
);
1363 g_assert (tmp
->right
== node
);
1366 if (node
->right_child
)
1368 tmp
= g_tree_node_next (node
);
1369 g_assert (tmp
->left
== node
);
1375 if (node
->left_child
)
1376 left_height
= g_tree_node_height (node
->left
);
1377 if (node
->right_child
)
1378 right_height
= g_tree_node_height (node
->right
);
1380 balance
= right_height
- left_height
;
1381 g_assert (balance
== node
->balance
);
1383 if (node
->left_child
)
1384 g_tree_node_check (node
->left
);
1385 if (node
->right_child
)
1386 g_tree_node_check (node
->right
);
1391 g_tree_node_dump (GTreeNode
*node
,
1394 g_print ("%*s%c\n", indent
, "", *(char *)node
->key
);
1396 if (node
->left_child
)
1397 g_tree_node_dump (node
->left
, indent
+ 2);
1398 else if (node
->left
)
1399 g_print ("%*s<%c\n", indent
+ 2, "", *(char *)node
->left
->key
);
1401 if (node
->right_child
)
1402 g_tree_node_dump (node
->right
, indent
+ 2);
1403 else if (node
->right
)
1404 g_print ("%*s>%c\n", indent
+ 2, "", *(char *)node
->right
->key
);
1409 g_tree_dump (GTree
*tree
)
1412 g_tree_node_dump (tree
->root
, 0);