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 nothing)
323 g_tree_remove (GTree *tree,
328 g_return_val_if_fail (tree != NULL, FALSE);
330 tree->root = g_tree_node_remove (tree, tree->root, key, TRUE, &removed);
338 * @key: the key to remove.
340 * Removes a key and its associated value from a #GTree without calling
341 * the key and value destroy functions.
343 * If the key does not exist in the #GTree, the function does nothing.
345 * Returns: %TRUE if the key was found (prior to 2.8, this function returned nothing)
348 g_tree_steal (GTree *tree,
353 g_return_val_if_fail (tree != NULL, FALSE);
355 tree->root = g_tree_node_remove (tree, tree->root, key, FALSE, &removed);
363 * @key: the key to look up.
365 * Gets the value corresponding to the given key. Since a #GTree is
366 * automatically balanced as key/value pairs are added, key lookup is very
369 * Return value: the value corresponding to the key, or %NULL if the key was
373 g_tree_lookup (GTree *tree,
378 g_return_val_if_fail (tree != NULL, NULL);
380 node = g_tree_node_lookup (tree->root,
381 tree->key_compare, tree->key_compare_data, key);
383 return node ? node->value : NULL;
387 * g_tree_lookup_extended:
389 * @lookup_key: the key to look up.
390 * @orig_key: returns the original key.
391 * @value: returns the value associated with the key.
393 * Looks up a key in the #GTree, returning the original key and the
394 * associated value and a #gboolean which is %TRUE if the key was found. This
395 * is useful if you need to free the memory allocated for the original key,
396 * for example before calling g_tree_remove().
398 * Return value: %TRUE if the key was found in the #GTree.
401 g_tree_lookup_extended (GTree *tree,
402 gconstpointer lookup_key,
408 g_return_val_if_fail (tree != NULL, FALSE);
410 node = g_tree_node_lookup (tree->root,
411 tree->key_compare, tree->key_compare_data, lookup_key);
416 *orig_key = node->key;
418 *value = node->value;
428 * @func: the function to call for each node visited. If this function
429 * returns %TRUE, the traversal is stopped.
430 * @user_data: user data to pass to the function.
432 * Calls the given function for each of the key/value pairs in the #GTree.
433 * The function is passed the key and value of each pair, and the given
434 * @data parameter. The tree is traversed in sorted order.
436 * The tree may not be modified while iterating over it (you can't
437 * add/remove items). To remove all items matching a predicate, you need
438 * to add each item to a list in your #GTraverseFunc as you walk over
439 * the tree, then walk the list and remove each item.
442 g_tree_foreach (GTree *tree,
446 g_return_if_fail (tree != NULL);
451 g_tree_node_in_order (tree->root, func, user_data);
457 * @traverse_func: the function to call for each node visited. If this
458 * function returns %TRUE, the traversal is stopped.
459 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
460 * %G_PRE_ORDER and %G_POST_ORDER.
461 * @user_data: user data to pass to the function.
463 * Calls the given function for each node in the #GTree.
465 * Deprecated: The order of a balanced tree is somewhat arbitrary. If you
466 * just want to visit all nodes in sorted order, use g_tree_foreach()
467 * instead. If you really need to visit nodes in a different order, consider
468 * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
471 g_tree_traverse (GTree *tree,
472 GTraverseFunc traverse_func,
473 GTraverseType traverse_type,
476 g_return_if_fail (tree != NULL);
481 switch (traverse_type)
484 g_tree_node_pre_order (tree->root, traverse_func, user_data);
488 g_tree_node_in_order (tree->root, traverse_func, user_data);
492 g_tree_node_post_order (tree->root, traverse_func, user_data);
496 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
504 * @search_func: a function used to search the #GTree.
505 * @user_data: the data passed as the second argument to the @search_func
508 * Searches a #GTree using @search_func.
510 * The @search_func is called with a pointer to the key of a key/value pair in the tree,
511 * and the passed in @user_data. If @search_func returns 0 for a key/value pair, then
512 * g_tree_search_func() will return the value of that pair. If @search_func returns -1,
513 * searching will proceed among the key/value pairs that have a smaller key; if @search_func
514 * returns 1, searching will proceed among the key/value pairs that have a larger key.
516 * Return value: the value corresponding to the found key, or %NULL if the key
520 g_tree_search (GTree *tree,
521 GCompareFunc search_func,
522 gconstpointer user_data)
524 g_return_val_if_fail (tree != NULL, NULL);
527 return g_tree_node_search (tree->root, search_func, user_data);
536 * Gets the height of a #GTree.
538 * If the #GTree contains no nodes, the height is 0.
539 * If the #GTree contains only one root node the height is 1.
540 * If the root node has children the height is 2, etc.
542 * Return value: the height of the #GTree.
545 g_tree_height (GTree *tree)
547 g_return_val_if_fail (tree != NULL, 0);
550 return g_tree_node_height (tree->root);
559 * Gets the number of nodes in a #GTree.
561 * Return value: the number of nodes in the #GTree.
564 g_tree_nnodes (GTree *tree)
566 g_return_val_if_fail (tree != NULL, 0);
569 return g_tree_node_count (tree->root);
575 g_tree_node_insert (GTree *tree,
588 return g_tree_node_new (key, value);
591 cmp = tree->key_compare (key, node->key, tree->key_compare_data);
596 if (tree->value_destroy_func)
597 tree->value_destroy_func (node->value);
603 if (tree->key_destroy_func)
604 tree->key_destroy_func (node->key);
610 /* free the passed key */
611 if (tree->key_destroy_func)
612 tree->key_destroy_func (key);
622 old_balance = node->left->balance;
623 node->left = g_tree_node_insert (tree,
628 if ((old_balance != node->left->balance) && node->left->balance)
634 node->left = g_tree_node_new (key, value);
642 old_balance = node->right->balance;
643 node->right = g_tree_node_insert (tree,
648 if ((old_balance != node->right->balance) && node->right->balance)
654 node->right = g_tree_node_new (key, value);
661 if ((node->balance < -1) || (node->balance > 1))
662 node = g_tree_node_balance (node);
669 g_tree_node_remove (GTree *tree,
684 cmp = tree->key_compare (key, node->key, tree->key_compare_data);
697 old_balance = node->right->balance;
698 node->right = g_tree_node_remove_leftmost (node->right, &new_root);
699 new_root->left = node->left;
700 new_root->right = node->right;
701 new_root->balance = node->balance;
702 node = g_tree_node_restore_right_balance (new_root, old_balance);
707 if (tree->key_destroy_func)
708 tree->key_destroy_func (garbage->key);
709 if (tree->value_destroy_func)
710 tree->value_destroy_func (garbage->value);
713 #ifdef ENABLE_GC_FRIENDLY
714 garbage->left = NULL;
716 garbage->value = NULL;
717 #endif /* ENABLE_GC_FRIENDLY */
719 g_slice_free (GTreeNode, garbage);
727 old_balance = node->left->balance;
728 node->left = g_tree_node_remove (tree, node->left, key, notify, removed);
729 node = g_tree_node_restore_left_balance (node, old_balance);
736 old_balance = node->right->balance;
737 node->right = g_tree_node_remove (tree, node->right, key, notify, removed);
738 node = g_tree_node_restore_right_balance (node, old_balance);
746 g_tree_node_balance (GTreeNode *node)
748 if (node->balance < -1)
750 if (node->left->balance > 0)
751 node->left = g_tree_node_rotate_left (node->left);
752 node = g_tree_node_rotate_right (node);
754 else if (node->balance > 1)
756 if (node->right->balance < 0)
757 node->right = g_tree_node_rotate_right (node->right);
758 node = g_tree_node_rotate_left (node);
765 g_tree_node_remove_leftmost (GTreeNode *node,
766 GTreeNode **leftmost)
776 old_balance = node->left->balance;
777 node->left = g_tree_node_remove_leftmost (node->left, leftmost);
778 return g_tree_node_restore_left_balance (node, old_balance);
782 g_tree_node_restore_left_balance (GTreeNode *node,
787 else if ((node->left->balance != old_balance) &&
788 (node->left->balance == 0))
791 if (node->balance > 1)
792 return g_tree_node_balance (node);
797 g_tree_node_restore_right_balance (GTreeNode *node,
802 else if ((node->right->balance != old_balance) &&
803 (node->right->balance == 0))
806 if (node->balance < -1)
807 return g_tree_node_balance (node);
812 g_tree_node_lookup (GTreeNode *node,
813 GCompareDataFunc compare,
814 gpointer compare_data,
822 cmp = (* compare) (key, node->key, compare_data);
829 return g_tree_node_lookup (node->left, compare, compare_data, key);
834 return g_tree_node_lookup (node->right, compare, compare_data, key);
841 g_tree_node_count (GTreeNode *node)
847 count += g_tree_node_count (node->left);
849 count += g_tree_node_count (node->right);
855 g_tree_node_pre_order (GTreeNode *node,
856 GTraverseFunc traverse_func,
859 if ((*traverse_func) (node->key, node->value, data))
863 if (g_tree_node_pre_order (node->left, traverse_func, data))
868 if (g_tree_node_pre_order (node->right, traverse_func, data))
876 g_tree_node_in_order (GTreeNode *node,
877 GTraverseFunc traverse_func,
882 if (g_tree_node_in_order (node->left, traverse_func, data))
885 if ((*traverse_func) (node->key, node->value, data))
889 if (g_tree_node_in_order (node->right, traverse_func, data))
897 g_tree_node_post_order (GTreeNode *node,
898 GTraverseFunc traverse_func,
903 if (g_tree_node_post_order (node->left, traverse_func, data))
908 if (g_tree_node_post_order (node->right, traverse_func, data))
911 if ((*traverse_func) (node->key, node->value, data))
918 g_tree_node_search (GTreeNode *node,
919 GCompareFunc search_func,
928 dir = (* search_func) (node->key, data);
942 g_tree_node_height (GTreeNode *node)
953 left_height = g_tree_node_height (node->left);
956 right_height = g_tree_node_height (node->right);
958 return MAX (left_height, right_height) + 1;
965 g_tree_node_rotate_left (GTreeNode *node)
973 node->right = right->left;
976 a_bal = node->balance;
977 b_bal = right->balance;
982 right->balance = b_bal - 1;
984 right->balance = a_bal + b_bal - 2;
985 node->balance = a_bal - 1;
990 right->balance = a_bal - 2;
992 right->balance = b_bal - 1;
993 node->balance = a_bal - b_bal - 1;
1000 g_tree_node_rotate_right (GTreeNode *node)
1008 node->left = left->right;
1011 a_bal = node->balance;
1012 b_bal = left->balance;
1017 left->balance = b_bal + 1;
1019 left->balance = a_bal + 2;
1020 node->balance = a_bal - b_bal + 1;
1025 left->balance = b_bal + 1;
1027 left->balance = a_bal + b_bal + 2;
1028 node->balance = a_bal + 1;
1035 g_tree_node_check (GTreeNode *node)
1047 left_height = g_tree_node_height (node->left);
1049 right_height = g_tree_node_height (node->right);
1051 balance = right_height - left_height;
1052 if (balance != node->balance)
1053 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO,
1054 "g_tree_node_check: failed: %d ( %d )\n",
1055 balance, node->balance);
1058 g_tree_node_check (node->left);
1060 g_tree_node_check (node->right);
1064 #define __G_TREE_C__
1065 #include "galiasdef.c"