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/.
38 #define MAX_GTREE_HEIGHT 40
40 typedef struct _GTreeNode GTreeNode
;
45 GCompareDataFunc key_compare
;
46 GDestroyNotify key_destroy_func
;
47 GDestroyNotify value_destroy_func
;
48 gpointer key_compare_data
;
54 gpointer key
; /* key for this node */
55 gpointer value
; /* value stored at this node */
56 GTreeNode
*left
; /* left subtree */
57 GTreeNode
*right
; /* right subtree */
58 gint8 balance
; /* height (left) - height (right) */
64 static GTreeNode
* g_tree_node_new (gpointer key
,
66 static void g_tree_insert_internal (GTree
*tree
,
70 static gboolean
g_tree_remove_internal (GTree
*tree
,
73 static GTreeNode
* g_tree_node_balance (GTreeNode
*node
);
74 static GTreeNode
*g_tree_find_node (GTree
*tree
,
76 static gint
g_tree_node_pre_order (GTreeNode
*node
,
77 GTraverseFunc traverse_func
,
79 static gint
g_tree_node_in_order (GTreeNode
*node
,
80 GTraverseFunc traverse_func
,
82 static gint
g_tree_node_post_order (GTreeNode
*node
,
83 GTraverseFunc traverse_func
,
85 static gpointer
g_tree_node_search (GTreeNode
*node
,
86 GCompareFunc search_func
,
88 static GTreeNode
* g_tree_node_rotate_left (GTreeNode
*node
);
89 static GTreeNode
* g_tree_node_rotate_right (GTreeNode
*node
);
91 static void g_tree_node_check (GTreeNode
*node
);
96 g_tree_node_new (gpointer key
,
99 GTreeNode
*node
= g_slice_new (GTreeNode
);
104 node
->left_child
= FALSE
;
105 node
->right_child
= FALSE
;
114 * @key_compare_func: the function used to order the nodes in the #GTree.
115 * It should return values similar to the standard strcmp() function -
116 * 0 if the two arguments are equal, a negative value if the first argument
117 * comes before the second, or a positive value if the first argument comes
120 * Creates a new #GTree.
122 * Return value: a new #GTree.
125 g_tree_new (GCompareFunc key_compare_func
)
127 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
129 return g_tree_new_full ((GCompareDataFunc
) key_compare_func
, NULL
,
134 * g_tree_new_with_data:
135 * @key_compare_func: qsort()-style comparison function.
136 * @key_compare_data: data to pass to comparison function.
138 * Creates a new #GTree with a comparison function that accepts user data.
139 * See g_tree_new() for more details.
141 * Return value: a new #GTree.
144 g_tree_new_with_data (GCompareDataFunc key_compare_func
,
145 gpointer key_compare_data
)
147 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
149 return g_tree_new_full (key_compare_func
, key_compare_data
,
155 * @key_compare_func: qsort()-style comparison function.
156 * @key_compare_data: data to pass to comparison function.
157 * @key_destroy_func: a function to free the memory allocated for the key
158 * used when removing the entry from the #GTree or %NULL if you don't
159 * want to supply such a function.
160 * @value_destroy_func: a function to free the memory allocated for the
161 * value used when removing the entry from the #GTree or %NULL if you
162 * don't want to supply such a function.
164 * Creates a new #GTree like g_tree_new() and allows to specify functions
165 * to free the memory allocated for the key and value that get called when
166 * removing the entry from the #GTree.
168 * Return value: a new #GTree.
171 g_tree_new_full (GCompareDataFunc key_compare_func
,
172 gpointer key_compare_data
,
173 GDestroyNotify key_destroy_func
,
174 GDestroyNotify value_destroy_func
)
178 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
180 tree
= g_new (GTree
, 1);
182 tree
->key_compare
= key_compare_func
;
183 tree
->key_destroy_func
= key_destroy_func
;
184 tree
->value_destroy_func
= value_destroy_func
;
185 tree
->key_compare_data
= key_compare_data
;
191 static inline GTreeNode
*
192 g_tree_first_node (GTree
*tree
)
201 while (tmp
->left_child
)
207 static inline GTreeNode
*
208 g_tree_node_previous (GTreeNode
*node
)
214 if (node
->left_child
)
215 while (tmp
->right_child
)
221 static inline GTreeNode
*
222 g_tree_node_next (GTreeNode
*node
)
228 if (node
->right_child
)
229 while (tmp
->left_child
)
239 * Destroys the #GTree. If keys and/or values are dynamically allocated, you
240 * should either free them first or create the #GTree using g_tree_new_full().
241 * In the latter case the destroy functions you supplied will be called on
242 * all keys and values before destroying the #GTree.
245 g_tree_destroy (GTree
*tree
)
250 g_return_if_fail (tree
!= NULL
);
252 node
= g_tree_first_node (tree
);
256 next
= g_tree_node_next (node
);
258 if (tree
->key_destroy_func
)
259 tree
->key_destroy_func (node
->key
);
260 if (tree
->value_destroy_func
)
261 tree
->value_destroy_func (node
->value
);
262 g_slice_free (GTreeNode
, node
);
273 * @key: the key to insert.
274 * @value: the value corresponding to the key.
276 * Inserts a key/value pair into a #GTree. If the given key already exists
277 * in the #GTree its corresponding value is set to the new value. If you
278 * supplied a value_destroy_func when creating the #GTree, the old value is
279 * freed using that function. If you supplied a @key_destroy_func when
280 * creating the #GTree, the passed key is freed using that function.
282 * The tree is automatically 'balanced' as new key/value pairs are added,
283 * so that the distance from the root to every leaf is as small as possible.
286 g_tree_insert (GTree
*tree
,
290 g_return_if_fail (tree
!= NULL
);
292 g_tree_insert_internal (tree
, key
, value
, FALSE
);
295 g_tree_node_check (tree
->root
);
302 * @key: the key to insert.
303 * @value: the value corresponding to the key.
305 * Inserts a new key and value into a #GTree similar to g_tree_insert().
306 * The difference is that if the key already exists in the #GTree, it gets
307 * replaced by the new key. If you supplied a @value_destroy_func when
308 * creating the #GTree, the old value is freed using that function. If you
309 * supplied a @key_destroy_func when creating the #GTree, the old key is
310 * freed using that function.
312 * The tree is automatically 'balanced' as new key/value pairs are added,
313 * so that the distance from the root to every leaf is as small as possible.
316 g_tree_replace (GTree
*tree
,
320 g_return_if_fail (tree
!= NULL
);
322 g_tree_insert_internal (tree
, key
, value
, TRUE
);
325 g_tree_node_check (tree
->root
);
329 /* internal insert routine */
331 g_tree_insert_internal (GTree
*tree
,
337 GTreeNode
*path
[MAX_GTREE_HEIGHT
];
340 g_return_if_fail (tree
!= NULL
);
344 tree
->root
= g_tree_node_new (key
, value
);
355 int cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
359 if (tree
->value_destroy_func
)
360 tree
->value_destroy_func (node
->value
);
366 if (tree
->key_destroy_func
)
367 tree
->key_destroy_func (node
->key
);
373 /* free the passed key */
374 if (tree
->key_destroy_func
)
375 tree
->key_destroy_func (key
);
382 if (node
->left_child
)
389 GTreeNode
*child
= g_tree_node_new (key
, value
);
391 child
->left
= node
->left
;
394 node
->left_child
= TRUE
;
404 if (node
->right_child
)
411 GTreeNode
*child
= g_tree_node_new (key
, value
);
413 child
->right
= node
->right
;
416 node
->right_child
= TRUE
;
426 /* restore balance. This is the goodness of a non-recursive
427 implementation, when we are done with balancing we 'break'
428 the loop and we are done. */
431 GTreeNode
*bparent
= path
[--idx
];
432 gboolean left_node
= (bparent
&& node
== bparent
->left
);
433 g_assert (!bparent
|| bparent
->left
== node
|| bparent
->right
== node
);
435 if (node
->balance
< -1 || node
->balance
> 1)
437 node
= g_tree_node_balance (node
);
441 bparent
->left
= node
;
443 bparent
->right
= node
;
446 if (node
->balance
== 0 || bparent
== NULL
)
450 bparent
->balance
-= 1;
452 bparent
->balance
+= 1;
461 * @key: the key to remove.
463 * Removes a key/value pair from a #GTree.
465 * If the #GTree was created using g_tree_new_full(), the key and value
466 * are freed using the supplied destroy functions, otherwise you have to
467 * make sure that any dynamically allocated values are freed yourself.
468 * If the key does not exist in the #GTree, the function does nothing.
470 * Returns: %TRUE if the key was found (prior to 2.8, this function returned
474 g_tree_remove (GTree
*tree
,
479 g_return_val_if_fail (tree
!= NULL
, FALSE
);
481 removed
= g_tree_remove_internal (tree
, key
, FALSE
);
484 g_tree_node_check (tree
->root
);
493 * @key: the key to remove.
495 * Removes a key and its associated value from a #GTree without calling
496 * the key and value destroy functions.
498 * If the key does not exist in the #GTree, the function does nothing.
500 * Returns: %TRUE if the key was found (prior to 2.8, this function returned
504 g_tree_steal (GTree
*tree
,
509 g_return_val_if_fail (tree
!= NULL
, FALSE
);
511 removed
= g_tree_remove_internal (tree
, key
, TRUE
);
514 g_tree_node_check (tree
->root
);
520 /* internal remove routine */
522 g_tree_remove_internal (GTree
*tree
,
526 GTreeNode
*node
, *parent
, *balance
;
527 GTreeNode
*path
[MAX_GTREE_HEIGHT
];
531 g_return_val_if_fail (tree
!= NULL
, FALSE
);
542 int cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
548 if (!node
->left_child
)
556 if (!node
->right_child
)
564 /* the following code is almost equal to g_tree_remove_node,
565 except that we do not have to call g_tree_node_parent. */
566 balance
= parent
= path
[--idx
];
567 g_assert (!parent
|| parent
->left
== node
|| parent
->right
== node
);
568 left_node
= (parent
&& node
== parent
->left
);
570 if (!node
->left_child
)
572 if (!node
->right_child
)
578 parent
->left_child
= FALSE
;
579 parent
->left
= node
->left
;
580 parent
->balance
+= 1;
584 parent
->right_child
= FALSE
;
585 parent
->right
= node
->right
;
586 parent
->balance
-= 1;
589 else /* node has a right child */
591 GTreeNode
*tmp
= g_tree_node_next (node
);
592 tmp
->left
= node
->left
;
595 tree
->root
= node
->right
;
598 parent
->left
= node
->right
;
599 parent
->balance
+= 1;
603 parent
->right
= node
->right
;
604 parent
->balance
-= 1;
608 else /* node has a left child */
610 if (!node
->right_child
)
612 GTreeNode
*tmp
= g_tree_node_previous (node
);
613 tmp
->right
= node
->right
;
616 tree
->root
= node
->left
;
619 parent
->left
= node
->left
;
620 parent
->balance
+= 1;
624 parent
->right
= node
->left
;
625 parent
->balance
-= 1;
628 else /* node has a both children (pant, pant!) */
630 GTreeNode
*prev
= node
->left
;
631 GTreeNode
*next
= node
->right
;
632 GTreeNode
*nextp
= node
;
633 int old_idx
= idx
+ 1;
636 /* path[idx] == parent */
637 /* find the immediately next node (and its parent) */
638 while (next
->left_child
)
640 path
[++idx
] = nextp
= next
;
644 path
[old_idx
] = next
;
647 /* remove 'next' from the tree */
650 if (next
->right_child
)
651 nextp
->left
= next
->right
;
653 nextp
->left_child
= FALSE
;
656 next
->right_child
= TRUE
;
657 next
->right
= node
->right
;
662 /* set the prev to point to the right place */
663 while (prev
->right_child
)
667 /* prepare 'next' to replace 'node' */
668 next
->left_child
= TRUE
;
669 next
->left
= node
->left
;
670 next
->balance
= node
->balance
;
677 parent
->right
= next
;
681 /* restore balance */
685 GTreeNode
*bparent
= path
[--idx
];
686 g_assert (!bparent
|| bparent
->left
== balance
|| bparent
->right
== balance
);
687 left_node
= (bparent
&& balance
== bparent
->left
);
689 if(balance
->balance
< -1 || balance
->balance
> 1)
691 balance
= g_tree_node_balance (balance
);
693 tree
->root
= balance
;
695 bparent
->left
= balance
;
697 bparent
->right
= balance
;
700 if (balance
->balance
!= 0 || !bparent
)
704 bparent
->balance
+= 1;
706 bparent
->balance
-= 1;
713 if (tree
->key_destroy_func
)
714 tree
->key_destroy_func (node
->key
);
715 if (tree
->value_destroy_func
)
716 tree
->value_destroy_func (node
->value
);
719 g_slice_free (GTreeNode
, node
);
729 * @key: the key to look up.
731 * Gets the value corresponding to the given key. Since a #GTree is
732 * automatically balanced as key/value pairs are added, key lookup is very
735 * Return value: the value corresponding to the key, or %NULL if the key was
739 g_tree_lookup (GTree
*tree
,
744 g_return_val_if_fail (tree
!= NULL
, NULL
);
746 node
= g_tree_find_node (tree
, key
);
748 return node
? node
->value
: NULL
;
752 * g_tree_lookup_extended:
754 * @lookup_key: the key to look up.
755 * @orig_key: returns the original key.
756 * @value: returns the value associated with the key.
758 * Looks up a key in the #GTree, returning the original key and the
759 * associated value and a #gboolean which is %TRUE if the key was found. This
760 * is useful if you need to free the memory allocated for the original key,
761 * for example before calling g_tree_remove().
763 * Return value: %TRUE if the key was found in the #GTree.
766 g_tree_lookup_extended (GTree
*tree
,
767 gconstpointer lookup_key
,
773 g_return_val_if_fail (tree
!= NULL
, FALSE
);
775 node
= g_tree_find_node (tree
, lookup_key
);
780 *orig_key
= node
->key
;
782 *value
= node
->value
;
792 * @func: the function to call for each node visited. If this function
793 * returns %TRUE, the traversal is stopped.
794 * @user_data: user data to pass to the function.
796 * Calls the given function for each of the key/value pairs in the #GTree.
797 * The function is passed the key and value of each pair, and the given
798 * @data parameter. The tree is traversed in sorted order.
800 * The tree may not be modified while iterating over it (you can't
801 * add/remove items). To remove all items matching a predicate, you need
802 * to add each item to a list in your #GTraverseFunc as you walk over
803 * the tree, then walk the list and remove each item.
806 g_tree_foreach (GTree
*tree
,
812 g_return_if_fail (tree
!= NULL
);
817 node
= g_tree_first_node (tree
);
821 if ((*func
) (node
->key
, node
->value
, user_data
))
824 node
= g_tree_node_next (node
);
831 * @traverse_func: the function to call for each node visited. If this
832 * function returns %TRUE, the traversal is stopped.
833 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
834 * %G_PRE_ORDER and %G_POST_ORDER.
835 * @user_data: user data to pass to the function.
837 * Calls the given function for each node in the #GTree.
839 * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary. If you
840 * just want to visit all nodes in sorted order, use g_tree_foreach()
841 * instead. If you really need to visit nodes in a different order, consider
842 * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
845 g_tree_traverse (GTree
*tree
,
846 GTraverseFunc traverse_func
,
847 GTraverseType traverse_type
,
850 g_return_if_fail (tree
!= NULL
);
855 switch (traverse_type
)
858 g_tree_node_pre_order (tree
->root
, traverse_func
, user_data
);
862 g_tree_node_in_order (tree
->root
, traverse_func
, user_data
);
866 g_tree_node_post_order (tree
->root
, traverse_func
, user_data
);
870 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
878 * @search_func: a function used to search the #GTree.
879 * @user_data: the data passed as the second argument to the @search_func
882 * Searches a #GTree using @search_func.
884 * The @search_func is called with a pointer to the key of a key/value pair in
885 * the tree, and the passed in @user_data. If @search_func returns 0 for a
886 * key/value pair, then g_tree_search_func() will return the value of that
887 * pair. If @search_func returns -1, searching will proceed among the
888 * key/value pairs that have a smaller key; if @search_func returns 1,
889 * searching will proceed among the key/value pairs that have a larger key.
891 * Return value: the value corresponding to the found key, or %NULL if the key
895 g_tree_search (GTree
*tree
,
896 GCompareFunc search_func
,
897 gconstpointer user_data
)
899 g_return_val_if_fail (tree
!= NULL
, NULL
);
902 return g_tree_node_search (tree
->root
, search_func
, user_data
);
911 * Gets the height of a #GTree.
913 * If the #GTree contains no nodes, the height is 0.
914 * If the #GTree contains only one root node the height is 1.
915 * If the root node has children the height is 2, etc.
917 * Return value: the height of the #GTree.
920 g_tree_height (GTree
*tree
)
925 g_return_val_if_fail (tree
!= NULL
, 0);
935 height
+= 1 + MAX(node
->balance
, 0);
937 if (!node
->left_child
)
948 * Gets the number of nodes in a #GTree.
950 * Return value: the number of nodes in the #GTree.
953 g_tree_nnodes (GTree
*tree
)
955 g_return_val_if_fail (tree
!= NULL
, 0);
961 g_tree_node_balance (GTreeNode
*node
)
963 if (node
->balance
< -1)
965 if (node
->left
->balance
> 0)
966 node
->left
= g_tree_node_rotate_left (node
->left
);
967 node
= g_tree_node_rotate_right (node
);
969 else if (node
->balance
> 1)
971 if (node
->right
->balance
< 0)
972 node
->right
= g_tree_node_rotate_right (node
->right
);
973 node
= g_tree_node_rotate_left (node
);
980 g_tree_find_node (GTree
*tree
,
992 cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
997 if (!node
->left_child
)
1004 if (!node
->right_child
)
1013 g_tree_node_pre_order (GTreeNode
*node
,
1014 GTraverseFunc traverse_func
,
1017 if ((*traverse_func
) (node
->key
, node
->value
, data
))
1020 if (node
->left_child
)
1022 if (g_tree_node_pre_order (node
->left
, traverse_func
, data
))
1026 if (node
->right_child
)
1028 if (g_tree_node_pre_order (node
->right
, traverse_func
, data
))
1036 g_tree_node_in_order (GTreeNode
*node
,
1037 GTraverseFunc traverse_func
,
1040 if (node
->left_child
)
1042 if (g_tree_node_in_order (node
->left
, traverse_func
, data
))
1046 if ((*traverse_func
) (node
->key
, node
->value
, data
))
1049 if (node
->right_child
)
1051 if (g_tree_node_in_order (node
->right
, traverse_func
, data
))
1059 g_tree_node_post_order (GTreeNode
*node
,
1060 GTraverseFunc traverse_func
,
1063 if (node
->left_child
)
1065 if (g_tree_node_post_order (node
->left
, traverse_func
, data
))
1069 if (node
->right_child
)
1071 if (g_tree_node_post_order (node
->right
, traverse_func
, data
))
1075 if ((*traverse_func
) (node
->key
, node
->value
, data
))
1082 g_tree_node_search (GTreeNode
*node
,
1083 GCompareFunc search_func
,
1093 dir
= (* search_func
) (node
->key
, data
);
1098 if (!node
->left_child
)
1105 if (!node
->right_child
)
1114 g_tree_node_rotate_left (GTreeNode
*node
)
1120 right
= node
->right
;
1122 if (right
->left_child
)
1123 node
->right
= right
->left
;
1126 node
->right_child
= FALSE
;
1127 node
->right
= right
;
1128 right
->left_child
= TRUE
;
1132 a_bal
= node
->balance
;
1133 b_bal
= right
->balance
;
1138 right
->balance
= b_bal
- 1;
1140 right
->balance
= a_bal
+ b_bal
- 2;
1141 node
->balance
= a_bal
- 1;
1146 right
->balance
= a_bal
- 2;
1148 right
->balance
= b_bal
- 1;
1149 node
->balance
= a_bal
- b_bal
- 1;
1156 g_tree_node_rotate_right (GTreeNode
*node
)
1164 if (left
->right_child
)
1165 node
->left
= left
->right
;
1168 node
->left_child
= FALSE
;
1170 left
->right_child
= TRUE
;
1174 a_bal
= node
->balance
;
1175 b_bal
= left
->balance
;
1180 left
->balance
= b_bal
+ 1;
1182 left
->balance
= a_bal
+ 2;
1183 node
->balance
= a_bal
- b_bal
+ 1;
1188 left
->balance
= b_bal
+ 1;
1190 left
->balance
= a_bal
+ b_bal
+ 2;
1191 node
->balance
= a_bal
+ 1;
1199 g_tree_node_height (GTreeNode
*node
)
1209 if (node
->left_child
)
1210 left_height
= g_tree_node_height (node
->left
);
1212 if (node
->right_child
)
1213 right_height
= g_tree_node_height (node
->right
);
1215 return MAX (left_height
, right_height
) + 1;
1222 g_tree_node_check (GTreeNode
*node
)
1231 if (node
->left_child
)
1233 tmp
= g_tree_node_previous (node
);
1234 g_assert (tmp
->right
== node
);
1237 if (node
->right_child
)
1239 tmp
= g_tree_node_next (node
);
1240 g_assert (tmp
->left
== node
);
1246 if (node
->left_child
)
1247 left_height
= g_tree_node_height (node
->left
);
1248 if (node
->right_child
)
1249 right_height
= g_tree_node_height (node
->right
);
1251 balance
= right_height
- left_height
;
1252 g_assert (balance
== node
->balance
);
1254 if (node
->left_child
)
1255 g_tree_node_check (node
->left
);
1256 if (node
->right_child
)
1257 g_tree_node_check (node
->right
);
1262 g_tree_node_dump (GTreeNode
*node
,
1265 g_print ("%*s%c\n", indent
, "", *(char *)node
->key
);
1267 if (node
->left_child
)
1268 g_tree_node_dump (node
->left
, indent
+ 2);
1269 else if (node
->left
)
1270 g_print ("%*s<%c\n", indent
+ 2, "", *(char *)node
->left
->key
);
1272 if (node
->right_child
)
1273 g_tree_node_dump (node
->right
, indent
+ 2);
1274 else if (node
->right
)
1275 g_print ("%*s>%c\n", indent
+ 2, "", *(char *)node
->right
->key
);
1280 g_tree_dump (GTree
*tree
)
1283 g_tree_node_dump (tree
->root
, 0);
1288 #define __G_TREE_C__
1289 #include "galiasdef.c"