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/.
37 typedef struct _GTreeNode GTreeNode
;
42 GCompareDataFunc key_compare
;
43 GDestroyNotify key_destroy_func
;
44 GDestroyNotify value_destroy_func
;
45 gpointer key_compare_data
;
50 gint balance
; /* height (left) - height (right) */
51 GTreeNode
*left
; /* left subtree */
52 GTreeNode
*right
; /* right subtree */
53 gpointer key
; /* key for this node */
54 gpointer value
; /* value stored at this node */
58 static GTreeNode
* g_tree_node_new (gpointer key
,
60 static void g_tree_node_destroy (GTreeNode
*node
,
61 GDestroyNotify key_destroy_func
,
62 GDestroyNotify value_destroy_func
);
63 static GTreeNode
* g_tree_node_insert (GTree
*tree
,
69 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
);
105 g_tree_node_new (gpointer key
,
108 GTreeNode
*node
= g_slice_new (GTreeNode
);
120 g_tree_node_destroy (GTreeNode
*node
,
121 GDestroyNotify key_destroy_func
,
122 GDestroyNotify value_destroy_func
)
126 g_tree_node_destroy (node
->right
,
127 key_destroy_func
, value_destroy_func
);
128 g_tree_node_destroy (node
->left
,
129 key_destroy_func
, value_destroy_func
);
131 if (key_destroy_func
)
132 key_destroy_func (node
->key
);
133 if (value_destroy_func
)
134 value_destroy_func (node
->value
);
136 #ifdef ENABLE_GC_FRIENDLY
140 #endif /* ENABLE_GC_FRIENDLY */
142 g_slice_free (GTreeNode
, node
);
148 * @key_compare_func: the function used to order the nodes in the #GTree.
149 * It should return values similar to the standard strcmp() function -
150 * 0 if the two arguments are equal, a negative value if the first argument
151 * comes before the second, or a positive value if the first argument comes
154 * Creates a new #GTree.
156 * Return value: a new #GTree.
159 g_tree_new (GCompareFunc key_compare_func
)
161 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
163 return g_tree_new_full ((GCompareDataFunc
) key_compare_func
, NULL
,
168 * g_tree_new_with_data:
169 * @key_compare_func: qsort()-style comparison function.
170 * @key_compare_data: data to pass to comparison function.
172 * Creates a new #GTree with a comparison function that accepts user data.
173 * See g_tree_new() for more details.
175 * Return value: a new #GTree.
178 g_tree_new_with_data (GCompareDataFunc key_compare_func
,
179 gpointer key_compare_data
)
181 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
183 return g_tree_new_full (key_compare_func
, key_compare_data
,
189 * @key_compare_func: qsort()-style comparison function.
190 * @key_compare_data: data to pass to comparison function.
191 * @key_destroy_func: a function to free the memory allocated for the key
192 * used when removing the entry from the #GTree or %NULL if you don't
193 * want to supply such a function.
194 * @value_destroy_func: a function to free the memory allocated for the
195 * value used when removing the entry from the #GTree or %NULL if you
196 * don't want to supply such a function.
198 * Creates a new #GTree like g_tree_new() and allows to specify functions
199 * to free the memory allocated for the key and value that get called when
200 * removing the entry from the #GTree.
202 * Return value: a new #GTree.
205 g_tree_new_full (GCompareDataFunc key_compare_func
,
206 gpointer key_compare_data
,
207 GDestroyNotify key_destroy_func
,
208 GDestroyNotify value_destroy_func
)
212 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
214 tree
= g_new (GTree
, 1);
216 tree
->key_compare
= key_compare_func
;
217 tree
->key_destroy_func
= key_destroy_func
;
218 tree
->value_destroy_func
= value_destroy_func
;
219 tree
->key_compare_data
= key_compare_data
;
228 * Destroys the #GTree. If keys and/or values are dynamically allocated, you
229 * should either free them first or create the #GTree using g_tree_new_full().
230 * In the latter case the destroy functions you supplied will be called on
231 * all keys and values before destroying the #GTree.
234 g_tree_destroy (GTree
*tree
)
236 g_return_if_fail (tree
!= NULL
);
238 g_tree_node_destroy (tree
->root
,
239 tree
->key_destroy_func
,
240 tree
->value_destroy_func
);
248 * @key: the key to insert.
249 * @value: the value corresponding to the key.
251 * Inserts a key/value pair into a #GTree. If the given key already exists
252 * in the #GTree its corresponding value is set to the new value. If you
253 * supplied a value_destroy_func when creating the #GTree, the old value is
254 * freed using that function. If you supplied a @key_destroy_func when
255 * creating the #GTree, the passed key is freed using that function.
257 * The tree is automatically 'balanced' as new key/value pairs are added,
258 * so that the distance from the root to every leaf is as small as possible.
261 g_tree_insert (GTree
*tree
,
267 g_return_if_fail (tree
!= NULL
);
270 tree
->root
= g_tree_node_insert (tree
,
279 * @key: the key to insert.
280 * @value: the value corresponding to the key.
282 * Inserts a new key and value into a #GTree similar to g_tree_insert().
283 * The difference is that if the key already exists in the #GTree, it gets
284 * replaced by the new key. If you supplied a @value_destroy_func when
285 * creating the #GTree, the old value is freed using that function. If you
286 * supplied a @key_destroy_func when creating the #GTree, the old key is
287 * freed using that function.
289 * The tree is automatically 'balanced' as new key/value pairs are added,
290 * so that the distance from the root to every leaf is as small as possible.
293 g_tree_replace (GTree
*tree
,
299 g_return_if_fail (tree
!= NULL
);
302 tree
->root
= g_tree_node_insert (tree
,
311 * @key: the key to remove.
313 * Removes a key/value pair from a #GTree.
315 * If the #GTree was created using g_tree_new_full(), the key and value
316 * are freed using the supplied destroy functions, otherwise you have to
317 * make sure that any dynamically allocated values are freed yourself.
318 * If the key does not exist in the #GTree, the function does nothing.
320 * Returns: %TRUE if the key was found (prior to 2.8, this function returned
324 g_tree_remove (GTree
*tree
,
329 g_return_val_if_fail (tree
!= NULL
, FALSE
);
331 tree
->root
= g_tree_node_remove (tree
, tree
->root
, key
, TRUE
, &removed
);
339 * @key: the key to remove.
341 * Removes a key and its associated value from a #GTree without calling
342 * the key and value destroy functions.
344 * If the key does not exist in the #GTree, the function does nothing.
346 * Returns: %TRUE if the key was found (prior to 2.8, this function returned
350 g_tree_steal (GTree
*tree
,
355 g_return_val_if_fail (tree
!= NULL
, FALSE
);
357 tree
->root
= g_tree_node_remove (tree
, tree
->root
, key
, FALSE
, &removed
);
365 * @key: the key to look up.
367 * Gets the value corresponding to the given key. Since a #GTree is
368 * automatically balanced as key/value pairs are added, key lookup is very
371 * Return value: the value corresponding to the key, or %NULL if the key was
375 g_tree_lookup (GTree
*tree
,
380 g_return_val_if_fail (tree
!= NULL
, NULL
);
382 node
= g_tree_node_lookup (tree
->root
,
383 tree
->key_compare
, tree
->key_compare_data
, key
);
385 return node
? node
->value
: NULL
;
389 * g_tree_lookup_extended:
391 * @lookup_key: the key to look up.
392 * @orig_key: returns the original key.
393 * @value: returns the value associated with the key.
395 * Looks up a key in the #GTree, returning the original key and the
396 * associated value and a #gboolean which is %TRUE if the key was found. This
397 * is useful if you need to free the memory allocated for the original key,
398 * for example before calling g_tree_remove().
400 * Return value: %TRUE if the key was found in the #GTree.
403 g_tree_lookup_extended (GTree
*tree
,
404 gconstpointer lookup_key
,
410 g_return_val_if_fail (tree
!= NULL
, FALSE
);
412 node
= g_tree_node_lookup (tree
->root
,
413 tree
->key_compare
, tree
->key_compare_data
, lookup_key
);
418 *orig_key
= node
->key
;
420 *value
= node
->value
;
430 * @func: the function to call for each node visited. If this function
431 * returns %TRUE, the traversal is stopped.
432 * @user_data: user data to pass to the function.
434 * Calls the given function for each of the key/value pairs in the #GTree.
435 * The function is passed the key and value of each pair, and the given
436 * @data parameter. The tree is traversed in sorted order.
438 * The tree may not be modified while iterating over it (you can't
439 * add/remove items). To remove all items matching a predicate, you need
440 * to add each item to a list in your #GTraverseFunc as you walk over
441 * the tree, then walk the list and remove each item.
444 g_tree_foreach (GTree
*tree
,
448 g_return_if_fail (tree
!= NULL
);
453 g_tree_node_in_order (tree
->root
, func
, user_data
);
459 * @traverse_func: the function to call for each node visited. If this
460 * function returns %TRUE, the traversal is stopped.
461 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
462 * %G_PRE_ORDER and %G_POST_ORDER.
463 * @user_data: user data to pass to the function.
465 * Calls the given function for each node in the #GTree.
467 * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary. If you
468 * just want to visit all nodes in sorted order, use g_tree_foreach()
469 * instead. If you really need to visit nodes in a different order, consider
470 * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
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: a 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 @search_func.
512 * The @search_func is called with a pointer to the key of a key/value pair in
513 * the tree, and the passed in @user_data. If @search_func returns 0 for a
514 * key/value pair, then g_tree_search_func() will return the value of that
515 * pair. If @search_func returns -1, searching will proceed among the
516 * key/value pairs that have a smaller key; if @search_func returns 1,
517 * searching will proceed among the key/value pairs that have a larger key.
519 * Return value: the value corresponding to the found key, or %NULL if the key
523 g_tree_search (GTree
*tree
,
524 GCompareFunc search_func
,
525 gconstpointer user_data
)
527 g_return_val_if_fail (tree
!= NULL
, NULL
);
530 return g_tree_node_search (tree
->root
, search_func
, user_data
);
539 * Gets the height of a #GTree.
541 * If the #GTree contains no nodes, the height is 0.
542 * If the #GTree contains only one root node the height is 1.
543 * If the root node has children the height is 2, etc.
545 * Return value: the height of the #GTree.
548 g_tree_height (GTree
*tree
)
550 g_return_val_if_fail (tree
!= NULL
, 0);
553 return g_tree_node_height (tree
->root
);
562 * Gets the number of nodes in a #GTree.
564 * Return value: the number of nodes in the #GTree.
567 g_tree_nnodes (GTree
*tree
)
569 g_return_val_if_fail (tree
!= NULL
, 0);
572 return g_tree_node_count (tree
->root
);
578 g_tree_node_insert (GTree
*tree
,
591 return g_tree_node_new (key
, value
);
594 cmp
= tree
->key_compare (key
, node
->key
, tree
->key_compare_data
);
599 if (tree
->value_destroy_func
)
600 tree
->value_destroy_func (node
->value
);
606 if (tree
->key_destroy_func
)
607 tree
->key_destroy_func (node
->key
);
613 /* free the passed key */
614 if (tree
->key_destroy_func
)
615 tree
->key_destroy_func (key
);
625 old_balance
= node
->left
->balance
;
626 node
->left
= g_tree_node_insert (tree
,
631 if ((old_balance
!= node
->left
->balance
) && node
->left
->balance
)
637 node
->left
= g_tree_node_new (key
, value
);
645 old_balance
= node
->right
->balance
;
646 node
->right
= g_tree_node_insert (tree
,
651 if ((old_balance
!= node
->right
->balance
) && node
->right
->balance
)
657 node
->right
= g_tree_node_new (key
, value
);
664 if ((node
->balance
< -1) || (node
->balance
> 1))
665 node
= g_tree_node_balance (node
);
672 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_slice_free (GTreeNode
, garbage
);
730 old_balance
= node
->left
->balance
;
731 node
->left
= g_tree_node_remove (tree
, node
->left
, key
, notify
, removed
);
732 node
= g_tree_node_restore_left_balance (node
, old_balance
);
739 old_balance
= node
->right
->balance
;
740 node
->right
= g_tree_node_remove (tree
, node
->right
, key
, notify
, removed
);
741 node
= g_tree_node_restore_right_balance (node
, old_balance
);
749 g_tree_node_balance (GTreeNode
*node
)
751 if (node
->balance
< -1)
753 if (node
->left
->balance
> 0)
754 node
->left
= g_tree_node_rotate_left (node
->left
);
755 node
= g_tree_node_rotate_right (node
);
757 else if (node
->balance
> 1)
759 if (node
->right
->balance
< 0)
760 node
->right
= g_tree_node_rotate_right (node
->right
);
761 node
= g_tree_node_rotate_left (node
);
768 g_tree_node_remove_leftmost (GTreeNode
*node
,
769 GTreeNode
**leftmost
)
779 old_balance
= node
->left
->balance
;
780 node
->left
= g_tree_node_remove_leftmost (node
->left
, leftmost
);
781 return g_tree_node_restore_left_balance (node
, old_balance
);
785 g_tree_node_restore_left_balance (GTreeNode
*node
,
790 else if ((node
->left
->balance
!= old_balance
) &&
791 (node
->left
->balance
== 0))
794 if (node
->balance
> 1)
795 return g_tree_node_balance (node
);
800 g_tree_node_restore_right_balance (GTreeNode
*node
,
805 else if ((node
->right
->balance
!= old_balance
) &&
806 (node
->right
->balance
== 0))
809 if (node
->balance
< -1)
810 return g_tree_node_balance (node
);
815 g_tree_node_lookup (GTreeNode
*node
,
816 GCompareDataFunc compare
,
817 gpointer compare_data
,
825 cmp
= (* compare
) (key
, node
->key
, compare_data
);
832 return g_tree_node_lookup (node
->left
, compare
, compare_data
, key
);
837 return g_tree_node_lookup (node
->right
, compare
, compare_data
, key
);
844 g_tree_node_count (GTreeNode
*node
)
850 count
+= g_tree_node_count (node
->left
);
852 count
+= g_tree_node_count (node
->right
);
858 g_tree_node_pre_order (GTreeNode
*node
,
859 GTraverseFunc traverse_func
,
862 if ((*traverse_func
) (node
->key
, node
->value
, data
))
866 if (g_tree_node_pre_order (node
->left
, traverse_func
, data
))
871 if (g_tree_node_pre_order (node
->right
, traverse_func
, data
))
879 g_tree_node_in_order (GTreeNode
*node
,
880 GTraverseFunc traverse_func
,
885 if (g_tree_node_in_order (node
->left
, traverse_func
, data
))
888 if ((*traverse_func
) (node
->key
, node
->value
, data
))
892 if (g_tree_node_in_order (node
->right
, traverse_func
, data
))
900 g_tree_node_post_order (GTreeNode
*node
,
901 GTraverseFunc traverse_func
,
906 if (g_tree_node_post_order (node
->left
, traverse_func
, data
))
911 if (g_tree_node_post_order (node
->right
, traverse_func
, data
))
914 if ((*traverse_func
) (node
->key
, node
->value
, data
))
921 g_tree_node_search (GTreeNode
*node
,
922 GCompareFunc search_func
,
931 dir
= (* search_func
) (node
->key
, data
);
945 g_tree_node_height (GTreeNode
*node
)
956 left_height
= g_tree_node_height (node
->left
);
959 right_height
= g_tree_node_height (node
->right
);
961 return MAX (left_height
, right_height
) + 1;
968 g_tree_node_rotate_left (GTreeNode
*node
)
976 node
->right
= right
->left
;
979 a_bal
= node
->balance
;
980 b_bal
= right
->balance
;
985 right
->balance
= b_bal
- 1;
987 right
->balance
= a_bal
+ b_bal
- 2;
988 node
->balance
= a_bal
- 1;
993 right
->balance
= a_bal
- 2;
995 right
->balance
= b_bal
- 1;
996 node
->balance
= a_bal
- b_bal
- 1;
1003 g_tree_node_rotate_right (GTreeNode
*node
)
1011 node
->left
= left
->right
;
1014 a_bal
= node
->balance
;
1015 b_bal
= left
->balance
;
1020 left
->balance
= b_bal
+ 1;
1022 left
->balance
= a_bal
+ 2;
1023 node
->balance
= a_bal
- b_bal
+ 1;
1028 left
->balance
= b_bal
+ 1;
1030 left
->balance
= a_bal
+ b_bal
+ 2;
1031 node
->balance
= a_bal
+ 1;
1038 g_tree_node_check (GTreeNode
*node
)
1050 left_height
= g_tree_node_height (node
->left
);
1052 right_height
= g_tree_node_height (node
->right
);
1054 balance
= right_height
- left_height
;
1055 if (balance
!= node
->balance
)
1056 g_log (G_LOG_DOMAIN
, G_LOG_LEVEL_INFO
,
1057 "g_tree_node_check: failed: %d ( %d )\n",
1058 balance
, node
->balance
);
1061 g_tree_node_check (node
->left
);
1063 g_tree_node_check (node
->right
);
1067 #define __G_TREE_C__
1068 #include "galiasdef.c"