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 typedef struct _GTreeNode GTreeNode
;
43 GCompareDataFunc key_compare
;
44 GDestroyNotify key_destroy_func
;
45 GDestroyNotify value_destroy_func
;
46 gpointer key_compare_data
;
51 gint balance
; /* height (left) - height (right) */
52 GTreeNode
*left
; /* left subtree */
53 GTreeNode
*right
; /* right subtree */
54 gpointer key
; /* key for this node */
55 gpointer value
; /* value stored at this node */
59 static GTreeNode
* g_tree_node_new (gpointer key
,
61 static void g_tree_node_destroy (GTreeNode
*node
,
62 GDestroyNotify key_destroy_func
,
63 GDestroyNotify value_destroy_func
);
64 static GTreeNode
* g_tree_node_insert (GTree
*tree
,
70 static GTreeNode
* g_tree_node_remove (GTree
*tree
,
74 static GTreeNode
* g_tree_node_balance (GTreeNode
*node
);
75 static GTreeNode
* g_tree_node_remove_leftmost (GTreeNode
*node
,
76 GTreeNode
**leftmost
);
77 static GTreeNode
* g_tree_node_restore_left_balance (GTreeNode
*node
,
79 static GTreeNode
* g_tree_node_restore_right_balance (GTreeNode
*node
,
81 static GTreeNode
* g_tree_node_lookup (GTreeNode
*node
,
82 GCompareDataFunc compare
,
85 static gint
g_tree_node_count (GTreeNode
*node
);
86 static gint
g_tree_node_pre_order (GTreeNode
*node
,
87 GTraverseFunc traverse_func
,
89 static gint
g_tree_node_in_order (GTreeNode
*node
,
90 GTraverseFunc traverse_func
,
92 static gint
g_tree_node_post_order (GTreeNode
*node
,
93 GTraverseFunc traverse_func
,
95 static gpointer
g_tree_node_search (GTreeNode
*node
,
96 GCompareFunc search_func
,
98 static gint
g_tree_node_height (GTreeNode
*node
);
99 static GTreeNode
* g_tree_node_rotate_left (GTreeNode
*node
);
100 static GTreeNode
* g_tree_node_rotate_right (GTreeNode
*node
);
101 static void g_tree_node_check (GTreeNode
*node
);
104 G_LOCK_DEFINE_STATIC (g_tree_global
);
105 static GMemChunk
*node_mem_chunk
= NULL
;
106 static GTreeNode
*node_free_list
= NULL
;
110 g_tree_node_new (gpointer key
,
115 G_LOCK (g_tree_global
);
118 node
= node_free_list
;
119 node_free_list
= node
->right
;
124 node_mem_chunk
= g_mem_chunk_new ("GLib GTreeNode mem chunk",
129 node
= g_chunk_new (GTreeNode
, node_mem_chunk
);
131 G_UNLOCK (g_tree_global
);
143 g_tree_node_destroy (GTreeNode
*node
,
144 GDestroyNotify key_destroy_func
,
145 GDestroyNotify value_destroy_func
)
149 g_tree_node_destroy (node
->right
,
150 key_destroy_func
, value_destroy_func
);
151 g_tree_node_destroy (node
->left
,
152 key_destroy_func
, value_destroy_func
);
154 if (key_destroy_func
)
155 key_destroy_func (node
->key
);
156 if (value_destroy_func
)
157 value_destroy_func (node
->value
);
159 #ifdef ENABLE_GC_FRIENDLY
163 #endif /* ENABLE_GC_FRIENDLY */
165 G_LOCK (g_tree_global
);
166 node
->right
= node_free_list
;
167 node_free_list
= node
;
168 G_UNLOCK (g_tree_global
);
174 * @key_compare_func: the function used to order the nodes in the #GTree.
175 * It should return values similar to the standard
176 * <function>strcmp()</function> function -
177 * 0 if the two arguments are equal, a negative value if the first argument
178 * comes before the second, or a positive value if the first argument comes
181 * Creates a new #GTree.
183 * Return value: a new #GTree.
186 g_tree_new (GCompareFunc key_compare_func
)
188 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
190 return g_tree_new_full ((GCompareDataFunc
) key_compare_func
, NULL
,
195 * g_tree_new_with_data:
196 * @key_compare_func: qsort()-style comparison function.
197 * @key_compare_data: data to pass to comparison function.
199 * Creates a new #GTree with a comparison function that accepts user data.
200 * See g_tree_new() for more details.
202 * Return value: a new #GTree.
205 g_tree_new_with_data (GCompareDataFunc key_compare_func
,
206 gpointer key_compare_data
)
208 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
210 return g_tree_new_full (key_compare_func
, key_compare_data
,
216 * @key_compare_func: qsort()-style comparison function.
217 * @key_compare_data: data to pass to comparison function.
218 * @key_destroy_func: a function to free the memory allocated for the key
219 * used when removing the entry from the #GTree or #NULL if you don't
220 * want to supply such a function.
221 * @value_destroy_func: a function to free the memory allocated for the
222 * value used when removing the entry from the #GTree or #NULL if you
223 * don't want to supply such a function.
225 * Creates a new #GTree like g_tree_new() and allows to specify functions
226 * to free the memory allocated for the key and value that get called when
227 * removing the entry from the #GTree.
229 * Return value: a new #GTree.
232 g_tree_new_full (GCompareDataFunc key_compare_func
,
233 gpointer key_compare_data
,
234 GDestroyNotify key_destroy_func
,
235 GDestroyNotify value_destroy_func
)
239 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
241 tree
= g_new (GTree
, 1);
243 tree
->key_compare
= key_compare_func
;
244 tree
->key_destroy_func
= key_destroy_func
;
245 tree
->value_destroy_func
= value_destroy_func
;
246 tree
->key_compare_data
= key_compare_data
;
255 * Destroys the #GTree. If keys and/or values are dynamically allocated, you
256 * should either free them first or create the #GTree using g_tree_new_full().
257 * In the latter case the destroy functions you supplied will be called on
258 * all keys and values before destroying the #GTree.
261 g_tree_destroy (GTree
*tree
)
263 g_return_if_fail (tree
!= NULL
);
265 g_tree_node_destroy (tree
->root
,
266 tree
->key_destroy_func
,
267 tree
->value_destroy_func
);
275 * @key: the key to insert.
276 * @value: the value corresponding to the key.
278 * Inserts a key/value pair into a #GTree. If the given key already exists
279 * in the #GTree its corresponding value is set to the new value. If you
280 * supplied a value_destroy_func when creating the #GTree, the old value is
281 * freed using that function. If you supplied a key_destroy_func when
282 * creating the #GTree, the passed key is freed using that function.
284 * The tree is automatically 'balanced' as new key/value pairs are added,
285 * so that the distance from the root to every leaf is as small as possible.
288 g_tree_insert (GTree
*tree
,
294 g_return_if_fail (tree
!= NULL
);
297 tree
->root
= g_tree_node_insert (tree
,
306 * @key: the key to insert.
307 * @value: the value corresponding to the key.
309 * Inserts a new key and value into a #GTree similar to g_tree_insert().
310 * The difference is that if the key already exists in the #GTree, it gets
311 * replaced by the new key. If you supplied a value_destroy_func when
312 * creating the #GTree, the old value is freed using that function. If you
313 * supplied a key_destroy_func when creating the #GTree, the old key is
314 * freed using that function.
316 * The tree is automatically 'balanced' as new key/value pairs are added,
317 * so that the distance from the root to every leaf is as small as possible.
320 g_tree_replace (GTree
*tree
,
326 g_return_if_fail (tree
!= NULL
);
329 tree
->root
= g_tree_node_insert (tree
,
338 * @key: the key to remove.
340 * Removes a key/value pair from a #GTree.
342 * If the #GTree was created using g_tree_new_full(), the key and value
343 * are freed using the supplied destroy_functions, otherwise you have to
344 * make sure that any dynamically allocated values are freed yourself.
347 g_tree_remove (GTree
*tree
,
350 g_return_if_fail (tree
!= NULL
);
352 tree
->root
= g_tree_node_remove (tree
, tree
->root
, key
, TRUE
);
358 * @key: the key to remove.
360 * Removes a key and its associated value from a #GTree without calling
361 * the key and value destroy functions.
364 g_tree_steal (GTree
*tree
,
367 g_return_if_fail (tree
!= NULL
);
369 tree
->root
= g_tree_node_remove (tree
, tree
->root
, key
, FALSE
);
375 * @key: the key to look up.
377 * Gets the value corresponding to the given key. Since a #GTree is
378 * automatically balanced as key/value pairs are added, key lookup is very
381 * Return value: the value corresponding to the key.
384 g_tree_lookup (GTree
*tree
,
389 g_return_val_if_fail (tree
!= NULL
, NULL
);
391 node
= g_tree_node_lookup (tree
->root
,
392 tree
->key_compare
, tree
->key_compare_data
, key
);
394 return node
? node
->value
: NULL
;
398 * g_tree_lookup_extended:
400 * @lookup_key: the key to look up.
401 * @orig_key: returns the original key.
402 * @value: returns the value associated with the key.
404 * Looks up a key in the #GTree, returning the original key and the
405 * associated value and a gboolean which is TRUE if the key was found. This
406 * is useful if you need to free the memory allocated for the original key,
407 * for example before calling g_tree_remove().
409 * Return value: #TRUE if the key was found in the #GTree.
412 g_tree_lookup_extended (GTree
*tree
,
413 gconstpointer lookup_key
,
419 g_return_val_if_fail (tree
!= NULL
, FALSE
);
421 node
= g_tree_node_lookup (tree
->root
,
422 tree
->key_compare
, tree
->key_compare_data
, lookup_key
);
427 *orig_key
= node
->key
;
429 *value
= node
->value
;
439 * @func: the function to call for each node visited. If this function
440 * returns TRUE, the traversal is stopped.
441 * @user_data: user data to pass to the function.
443 * Calls the given function for each of the key/value pairs in the #GTree.
444 * The function is passed the key and value of each pair, and the given
448 g_tree_foreach (GTree
*tree
,
452 g_return_if_fail (tree
!= NULL
);
457 g_tree_node_in_order (tree
->root
, func
, user_data
);
463 * @traverse_func: the function to call for each node visited. If this
464 * function returns TRUE, the traversal is stopped.
465 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
466 * %G_PRE_ORDER and %G_POST_ORDER.
467 * @user_data: user data to pass to the function.
469 * Calls the given function for each node in the GTree. This function is
470 * deprecated, use g_tree_foreach() instead.
473 g_tree_traverse (GTree
*tree
,
474 GTraverseFunc traverse_func
,
475 GTraverseType traverse_type
,
478 g_return_if_fail (tree
!= NULL
);
483 switch (traverse_type
)
486 g_tree_node_pre_order (tree
->root
, traverse_func
, user_data
);
490 g_tree_node_in_order (tree
->root
, traverse_func
, user_data
);
494 g_tree_node_post_order (tree
->root
, traverse_func
, user_data
);
498 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
506 * @search_func: the comparison function used to search the #GTree.
507 * @user_data: the data passed as the second argument to the @search_func
510 * Searches a #GTree using an alternative form of the comparison function.
512 * This function is not as useful as it sounds.
513 * It allows you to use a different function for performing the lookup of
514 * a key. However, since the tree is ordered according to the @key_compare_func
515 * function passed to g_tree_new(), the function you pass to g_tree_search()
516 * must return exactly the same value as would be returned by the comparison
517 * function, for each pair of tree nodes, or the search will not work.
519 * To search for a specific value, you can use g_tree_foreach() or
522 * Return value: the value corresponding to the found key, or NULL if the key
526 g_tree_search (GTree
*tree
,
527 GCompareFunc search_func
,
528 gconstpointer user_data
)
530 g_return_val_if_fail (tree
!= NULL
, NULL
);
533 return g_tree_node_search (tree
->root
, search_func
, user_data
);
542 * Gets the height of a #GTree.
544 * If the #GTree contains no nodes, the height is 0.
545 * If the #GTree contains only one root node the height is 1.
546 * If the root node has children the height is 2, etc.
548 * Return value: the height of the #GTree.
551 g_tree_height (GTree
*tree
)
553 g_return_val_if_fail (tree
!= NULL
, 0);
556 return g_tree_node_height (tree
->root
);
565 * Gets the number of nodes in a #GTree.
567 * Return value: the number of nodes in the #GTree.
570 g_tree_nnodes (GTree
*tree
)
572 g_return_val_if_fail (tree
!= NULL
, 0);
575 return g_tree_node_count (tree
->root
);
581 g_tree_node_insert (GTree
*tree
,
594 return g_tree_node_new (key
, value
);
597 cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
602 if (tree
->value_destroy_func
)
603 tree
->value_destroy_func (node
->value
);
609 if (tree
->key_destroy_func
)
610 tree
->key_destroy_func (node
->key
);
616 /* free the passed key */
617 if (tree
->key_destroy_func
)
618 tree
->key_destroy_func (key
);
628 old_balance
= node
->left
->balance
;
629 node
->left
= g_tree_node_insert (tree
,
634 if ((old_balance
!= node
->left
->balance
) && node
->left
->balance
)
640 node
->left
= g_tree_node_new (key
, value
);
648 old_balance
= node
->right
->balance
;
649 node
->right
= g_tree_node_insert (tree
,
654 if ((old_balance
!= node
->right
->balance
) && node
->right
->balance
)
660 node
->right
= g_tree_node_new (key
, value
);
667 if ((node
->balance
< -1) || (node
->balance
> 1))
668 node
= g_tree_node_balance (node
);
675 g_tree_node_remove (GTree
*tree
,
687 cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
700 old_balance
= node
->right
->balance
;
701 node
->right
= g_tree_node_remove_leftmost (node
->right
, &new_root
);
702 new_root
->left
= node
->left
;
703 new_root
->right
= node
->right
;
704 new_root
->balance
= node
->balance
;
705 node
= g_tree_node_restore_right_balance (new_root
, old_balance
);
710 if (tree
->key_destroy_func
)
711 tree
->key_destroy_func (garbage
->key
);
712 if (tree
->value_destroy_func
)
713 tree
->value_destroy_func (garbage
->value
);
716 #ifdef ENABLE_GC_FRIENDLY
717 garbage
->left
= NULL
;
719 garbage
->value
= NULL
;
720 #endif /* ENABLE_GC_FRIENDLY */
722 G_LOCK (g_tree_global
);
723 garbage
->right
= node_free_list
;
724 node_free_list
= garbage
;
725 G_UNLOCK (g_tree_global
);
731 old_balance
= node
->left
->balance
;
732 node
->left
= g_tree_node_remove (tree
, node
->left
, key
, notify
);
733 node
= g_tree_node_restore_left_balance (node
, old_balance
);
740 old_balance
= node
->right
->balance
;
741 node
->right
= g_tree_node_remove (tree
, node
->right
, key
, notify
);
742 node
= g_tree_node_restore_right_balance (node
, old_balance
);
750 g_tree_node_balance (GTreeNode
*node
)
752 if (node
->balance
< -1)
754 if (node
->left
->balance
> 0)
755 node
->left
= g_tree_node_rotate_left (node
->left
);
756 node
= g_tree_node_rotate_right (node
);
758 else if (node
->balance
> 1)
760 if (node
->right
->balance
< 0)
761 node
->right
= g_tree_node_rotate_right (node
->right
);
762 node
= g_tree_node_rotate_left (node
);
769 g_tree_node_remove_leftmost (GTreeNode
*node
,
770 GTreeNode
**leftmost
)
780 old_balance
= node
->left
->balance
;
781 node
->left
= g_tree_node_remove_leftmost (node
->left
, leftmost
);
782 return g_tree_node_restore_left_balance (node
, old_balance
);
786 g_tree_node_restore_left_balance (GTreeNode
*node
,
791 else if ((node
->left
->balance
!= old_balance
) &&
792 (node
->left
->balance
== 0))
795 if (node
->balance
> 1)
796 return g_tree_node_balance (node
);
801 g_tree_node_restore_right_balance (GTreeNode
*node
,
806 else if ((node
->right
->balance
!= old_balance
) &&
807 (node
->right
->balance
== 0))
810 if (node
->balance
< -1)
811 return g_tree_node_balance (node
);
816 g_tree_node_lookup (GTreeNode
*node
,
817 GCompareDataFunc compare
,
818 gpointer compare_data
,
826 cmp
= (* compare
) (key
, node
->key
, compare_data
);
833 return g_tree_node_lookup (node
->left
, compare
, compare_data
, key
);
838 return g_tree_node_lookup (node
->right
, compare
, compare_data
, key
);
845 g_tree_node_count (GTreeNode
*node
)
851 count
+= g_tree_node_count (node
->left
);
853 count
+= g_tree_node_count (node
->right
);
859 g_tree_node_pre_order (GTreeNode
*node
,
860 GTraverseFunc traverse_func
,
863 if ((*traverse_func
) (node
->key
, node
->value
, data
))
867 if (g_tree_node_pre_order (node
->left
, traverse_func
, data
))
872 if (g_tree_node_pre_order (node
->right
, traverse_func
, data
))
880 g_tree_node_in_order (GTreeNode
*node
,
881 GTraverseFunc traverse_func
,
886 if (g_tree_node_in_order (node
->left
, traverse_func
, data
))
889 if ((*traverse_func
) (node
->key
, node
->value
, data
))
893 if (g_tree_node_in_order (node
->right
, traverse_func
, data
))
901 g_tree_node_post_order (GTreeNode
*node
,
902 GTraverseFunc traverse_func
,
907 if (g_tree_node_post_order (node
->left
, traverse_func
, data
))
912 if (g_tree_node_post_order (node
->right
, traverse_func
, data
))
915 if ((*traverse_func
) (node
->key
, node
->value
, data
))
922 g_tree_node_search (GTreeNode
*node
,
923 GCompareFunc search_func
,
932 dir
= (* search_func
) (node
->key
, data
);
946 g_tree_node_height (GTreeNode
*node
)
957 left_height
= g_tree_node_height (node
->left
);
960 right_height
= g_tree_node_height (node
->right
);
962 return MAX (left_height
, right_height
) + 1;
969 g_tree_node_rotate_left (GTreeNode
*node
)
977 node
->right
= right
->left
;
980 a_bal
= node
->balance
;
981 b_bal
= right
->balance
;
986 right
->balance
= b_bal
- 1;
988 right
->balance
= a_bal
+ b_bal
- 2;
989 node
->balance
= a_bal
- 1;
994 right
->balance
= a_bal
- 2;
996 right
->balance
= b_bal
- 1;
997 node
->balance
= a_bal
- b_bal
- 1;
1004 g_tree_node_rotate_right (GTreeNode
*node
)
1012 node
->left
= left
->right
;
1015 a_bal
= node
->balance
;
1016 b_bal
= left
->balance
;
1021 left
->balance
= b_bal
+ 1;
1023 left
->balance
= a_bal
+ 2;
1024 node
->balance
= a_bal
- b_bal
+ 1;
1029 left
->balance
= b_bal
+ 1;
1031 left
->balance
= a_bal
+ b_bal
+ 2;
1032 node
->balance
= a_bal
+ 1;
1039 g_tree_node_check (GTreeNode
*node
)
1051 left_height
= g_tree_node_height (node
->left
);
1053 right_height
= g_tree_node_height (node
->right
);
1055 balance
= right_height
- left_height
;
1056 if (balance
!= node
->balance
)
1057 g_log (g_log_domain_glib
, G_LOG_LEVEL_INFO
,
1058 "g_tree_node_check: failed: %d ( %d )\n",
1059 balance
, node
->balance
);
1062 g_tree_node_check (node
->left
);
1064 g_tree_node_check (node
->right
);