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);
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 strcmp() function -
176 * 0 if the two arguments are equal, a negative value if the first argument
177 * comes before the second, or a positive value if the first argument comes
180 * Creates a new #GTree.
182 * Return value: a new #GTree.
185 g_tree_new (GCompareFunc key_compare_func)
187 g_return_val_if_fail (key_compare_func != NULL, NULL);
189 return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
194 * g_tree_new_with_data:
195 * @key_compare_func: qsort()-style comparison function.
196 * @key_compare_data: data to pass to comparison function.
198 * Creates a new #GTree with a comparison function that accepts user data.
199 * See g_tree_new() for more details.
201 * Return value: a new #GTree.
204 g_tree_new_with_data (GCompareDataFunc key_compare_func,
205 gpointer key_compare_data)
207 g_return_val_if_fail (key_compare_func != NULL, NULL);
209 return g_tree_new_full (key_compare_func, key_compare_data,
215 * @key_compare_func: qsort()-style comparison function.
216 * @key_compare_data: data to pass to comparison function.
217 * @key_destroy_func: a function to free the memory allocated for the key
218 * used when removing the entry from the #GTree or %NULL if you don't
219 * want to supply such a function.
220 * @value_destroy_func: a function to free the memory allocated for the
221 * value used when removing the entry from the #GTree or %NULL if you
222 * don't want to supply such a function.
224 * Creates a new #GTree like g_tree_new() and allows to specify functions
225 * to free the memory allocated for the key and value that get called when
226 * removing the entry from the #GTree.
228 * Return value: a new #GTree.
231 g_tree_new_full (GCompareDataFunc key_compare_func,
232 gpointer key_compare_data,
233 GDestroyNotify key_destroy_func,
234 GDestroyNotify value_destroy_func)
238 g_return_val_if_fail (key_compare_func != NULL, NULL);
240 tree = g_new (GTree, 1);
242 tree->key_compare = key_compare_func;
243 tree->key_destroy_func = key_destroy_func;
244 tree->value_destroy_func = value_destroy_func;
245 tree->key_compare_data = key_compare_data;
254 * Destroys the #GTree. If keys and/or values are dynamically allocated, you
255 * should either free them first or create the #GTree using g_tree_new_full().
256 * In the latter case the destroy functions you supplied will be called on
257 * all keys and values before destroying the #GTree.
260 g_tree_destroy (GTree *tree)
262 g_return_if_fail (tree != NULL);
264 g_tree_node_destroy (tree->root,
265 tree->key_destroy_func,
266 tree->value_destroy_func);
274 * @key: the key to insert.
275 * @value: the value corresponding to the key.
277 * Inserts a key/value pair into a #GTree. If the given key already exists
278 * in the #GTree its corresponding value is set to the new value. If you
279 * supplied a value_destroy_func when creating the #GTree, the old value is
280 * freed using that function. If you supplied a @key_destroy_func when
281 * creating the #GTree, the passed key is freed using that function.
283 * The tree is automatically 'balanced' as new key/value pairs are added,
284 * so that the distance from the root to every leaf is as small as possible.
287 g_tree_insert (GTree *tree,
293 g_return_if_fail (tree != NULL);
296 tree->root = g_tree_node_insert (tree,
305 * @key: the key to insert.
306 * @value: the value corresponding to the key.
308 * Inserts a new key and value into a #GTree similar to g_tree_insert().
309 * The difference is that if the key already exists in the #GTree, it gets
310 * replaced by the new key. If you supplied a @value_destroy_func when
311 * creating the #GTree, the old value is freed using that function. If you
312 * supplied a @key_destroy_func when creating the #GTree, the old key is
313 * freed using that function.
315 * The tree is automatically 'balanced' as new key/value pairs are added,
316 * so that the distance from the root to every leaf is as small as possible.
319 g_tree_replace (GTree *tree,
325 g_return_if_fail (tree != NULL);
328 tree->root = g_tree_node_insert (tree,
337 * @key: the key to remove.
339 * Removes a key/value pair from a #GTree.
341 * If the #GTree was created using g_tree_new_full(), the key and value
342 * are freed using the supplied destroy functions, otherwise you have to
343 * make sure that any dynamically allocated values are freed yourself.
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 nothing)
349 g_tree_remove (GTree *tree,
354 g_return_val_if_fail (tree != NULL, FALSE);
356 tree->root = g_tree_node_remove (tree, tree->root, key, TRUE, &removed);
364 * @key: the key to remove.
366 * Removes a key and its associated value from a #GTree without calling
367 * the key and value destroy functions.
369 * If the key does not exist in the #GTree, the function does nothing.
371 * Returns: %TRUE if the key was found (prior to 2.8, this function returned nothing)
374 g_tree_steal (GTree *tree,
379 g_return_val_if_fail (tree != NULL, FALSE);
381 tree->root = g_tree_node_remove (tree, tree->root, key, FALSE, &removed);
389 * @key: the key to look up.
391 * Gets the value corresponding to the given key. Since a #GTree is
392 * automatically balanced as key/value pairs are added, key lookup is very
395 * Return value: the value corresponding to the key, or %NULL if the key was
399 g_tree_lookup (GTree *tree,
404 g_return_val_if_fail (tree != NULL, NULL);
406 node = g_tree_node_lookup (tree->root,
407 tree->key_compare, tree->key_compare_data, key);
409 return node ? node->value : NULL;
413 * g_tree_lookup_extended:
415 * @lookup_key: the key to look up.
416 * @orig_key: returns the original key.
417 * @value: returns the value associated with the key.
419 * Looks up a key in the #GTree, returning the original key and the
420 * associated value and a #gboolean which is %TRUE if the key was found. This
421 * is useful if you need to free the memory allocated for the original key,
422 * for example before calling g_tree_remove().
424 * Return value: %TRUE if the key was found in the #GTree.
427 g_tree_lookup_extended (GTree *tree,
428 gconstpointer lookup_key,
434 g_return_val_if_fail (tree != NULL, FALSE);
436 node = g_tree_node_lookup (tree->root,
437 tree->key_compare, tree->key_compare_data, lookup_key);
442 *orig_key = node->key;
444 *value = node->value;
454 * @func: the function to call for each node visited. If this function
455 * returns %TRUE, the traversal is stopped.
456 * @user_data: user data to pass to the function.
458 * Calls the given function for each of the key/value pairs in the #GTree.
459 * The function is passed the key and value of each pair, and the given
460 * @data parameter. The tree is traversed in sorted order.
462 * The tree may not be modified while iterating over it (you can't
463 * add/remove items). To remove all items matching a predicate, you need
464 * to add each item to a list in your #GTraverseFunc as you walk over
465 * the tree, then walk the list and remove each item.
468 g_tree_foreach (GTree *tree,
472 g_return_if_fail (tree != NULL);
477 g_tree_node_in_order (tree->root, func, user_data);
483 * @traverse_func: the function to call for each node visited. If this
484 * function returns %TRUE, the traversal is stopped.
485 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
486 * %G_PRE_ORDER and %G_POST_ORDER.
487 * @user_data: user data to pass to the function.
489 * Calls the given function for each node in the #GTree.
491 * Deprecated: The order of a balanced tree is somewhat arbitrary. If you
492 * just want to visit all nodes in sorted order, use g_tree_foreach()
493 * instead. If you really need to visit nodes in a different order, consider
494 * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
497 g_tree_traverse (GTree *tree,
498 GTraverseFunc traverse_func,
499 GTraverseType traverse_type,
502 g_return_if_fail (tree != NULL);
507 switch (traverse_type)
510 g_tree_node_pre_order (tree->root, traverse_func, user_data);
514 g_tree_node_in_order (tree->root, traverse_func, user_data);
518 g_tree_node_post_order (tree->root, traverse_func, user_data);
522 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
530 * @search_func: a function used to search the #GTree.
531 * @user_data: the data passed as the second argument to the @search_func
534 * Searches a #GTree using @search_func.
536 * The @search_func is called with a pointer to the key of a key/value pair in the tree,
537 * and the passed in @user_data. If @search_func returns 0 for a key/value pair, then
538 * g_tree_search_func() will return the value of that pair. If @search_func returns -1,
539 * searching will proceed among the key/value pairs that have a smaller key; if @search_func
540 * returns 1, searching will proceed among the key/value pairs that have a larger key.
542 * Return value: the value corresponding to the found key, or %NULL if the key
546 g_tree_search (GTree *tree,
547 GCompareFunc search_func,
548 gconstpointer user_data)
550 g_return_val_if_fail (tree != NULL, NULL);
553 return g_tree_node_search (tree->root, search_func, user_data);
562 * Gets the height of a #GTree.
564 * If the #GTree contains no nodes, the height is 0.
565 * If the #GTree contains only one root node the height is 1.
566 * If the root node has children the height is 2, etc.
568 * Return value: the height of the #GTree.
571 g_tree_height (GTree *tree)
573 g_return_val_if_fail (tree != NULL, 0);
576 return g_tree_node_height (tree->root);
585 * Gets the number of nodes in a #GTree.
587 * Return value: the number of nodes in the #GTree.
590 g_tree_nnodes (GTree *tree)
592 g_return_val_if_fail (tree != NULL, 0);
595 return g_tree_node_count (tree->root);
601 g_tree_node_insert (GTree *tree,
614 return g_tree_node_new (key, value);
617 cmp = tree->key_compare (key, node->key, tree->key_compare_data);
622 if (tree->value_destroy_func)
623 tree->value_destroy_func (node->value);
629 if (tree->key_destroy_func)
630 tree->key_destroy_func (node->key);
636 /* free the passed key */
637 if (tree->key_destroy_func)
638 tree->key_destroy_func (key);
648 old_balance = node->left->balance;
649 node->left = g_tree_node_insert (tree,
654 if ((old_balance != node->left->balance) && node->left->balance)
660 node->left = g_tree_node_new (key, value);
668 old_balance = node->right->balance;
669 node->right = g_tree_node_insert (tree,
674 if ((old_balance != node->right->balance) && node->right->balance)
680 node->right = g_tree_node_new (key, value);
687 if ((node->balance < -1) || (node->balance > 1))
688 node = g_tree_node_balance (node);
695 g_tree_node_remove (GTree *tree,
710 cmp = tree->key_compare (key, node->key, tree->key_compare_data);
723 old_balance = node->right->balance;
724 node->right = g_tree_node_remove_leftmost (node->right, &new_root);
725 new_root->left = node->left;
726 new_root->right = node->right;
727 new_root->balance = node->balance;
728 node = g_tree_node_restore_right_balance (new_root, old_balance);
733 if (tree->key_destroy_func)
734 tree->key_destroy_func (garbage->key);
735 if (tree->value_destroy_func)
736 tree->value_destroy_func (garbage->value);
739 #ifdef ENABLE_GC_FRIENDLY
740 garbage->left = NULL;
742 garbage->value = NULL;
743 #endif /* ENABLE_GC_FRIENDLY */
745 G_LOCK (g_tree_global);
746 garbage->right = node_free_list;
747 node_free_list = garbage;
748 G_UNLOCK (g_tree_global);
756 old_balance = node->left->balance;
757 node->left = g_tree_node_remove (tree, node->left, key, notify, removed);
758 node = g_tree_node_restore_left_balance (node, old_balance);
765 old_balance = node->right->balance;
766 node->right = g_tree_node_remove (tree, node->right, key, notify, removed);
767 node = g_tree_node_restore_right_balance (node, old_balance);
775 g_tree_node_balance (GTreeNode *node)
777 if (node->balance < -1)
779 if (node->left->balance > 0)
780 node->left = g_tree_node_rotate_left (node->left);
781 node = g_tree_node_rotate_right (node);
783 else if (node->balance > 1)
785 if (node->right->balance < 0)
786 node->right = g_tree_node_rotate_right (node->right);
787 node = g_tree_node_rotate_left (node);
794 g_tree_node_remove_leftmost (GTreeNode *node,
795 GTreeNode **leftmost)
805 old_balance = node->left->balance;
806 node->left = g_tree_node_remove_leftmost (node->left, leftmost);
807 return g_tree_node_restore_left_balance (node, old_balance);
811 g_tree_node_restore_left_balance (GTreeNode *node,
816 else if ((node->left->balance != old_balance) &&
817 (node->left->balance == 0))
820 if (node->balance > 1)
821 return g_tree_node_balance (node);
826 g_tree_node_restore_right_balance (GTreeNode *node,
831 else if ((node->right->balance != old_balance) &&
832 (node->right->balance == 0))
835 if (node->balance < -1)
836 return g_tree_node_balance (node);
841 g_tree_node_lookup (GTreeNode *node,
842 GCompareDataFunc compare,
843 gpointer compare_data,
851 cmp = (* compare) (key, node->key, compare_data);
858 return g_tree_node_lookup (node->left, compare, compare_data, key);
863 return g_tree_node_lookup (node->right, compare, compare_data, key);
870 g_tree_node_count (GTreeNode *node)
876 count += g_tree_node_count (node->left);
878 count += g_tree_node_count (node->right);
884 g_tree_node_pre_order (GTreeNode *node,
885 GTraverseFunc traverse_func,
888 if ((*traverse_func) (node->key, node->value, data))
892 if (g_tree_node_pre_order (node->left, traverse_func, data))
897 if (g_tree_node_pre_order (node->right, traverse_func, data))
905 g_tree_node_in_order (GTreeNode *node,
906 GTraverseFunc traverse_func,
911 if (g_tree_node_in_order (node->left, traverse_func, data))
914 if ((*traverse_func) (node->key, node->value, data))
918 if (g_tree_node_in_order (node->right, traverse_func, data))
926 g_tree_node_post_order (GTreeNode *node,
927 GTraverseFunc traverse_func,
932 if (g_tree_node_post_order (node->left, traverse_func, data))
937 if (g_tree_node_post_order (node->right, traverse_func, data))
940 if ((*traverse_func) (node->key, node->value, data))
947 g_tree_node_search (GTreeNode *node,
948 GCompareFunc search_func,
957 dir = (* search_func) (node->key, data);
971 g_tree_node_height (GTreeNode *node)
982 left_height = g_tree_node_height (node->left);
985 right_height = g_tree_node_height (node->right);
987 return MAX (left_height, right_height) + 1;
994 g_tree_node_rotate_left (GTreeNode *node)
1000 right = node->right;
1002 node->right = right->left;
1005 a_bal = node->balance;
1006 b_bal = right->balance;
1011 right->balance = b_bal - 1;
1013 right->balance = a_bal + b_bal - 2;
1014 node->balance = a_bal - 1;
1019 right->balance = a_bal - 2;
1021 right->balance = b_bal - 1;
1022 node->balance = a_bal - b_bal - 1;
1029 g_tree_node_rotate_right (GTreeNode *node)
1037 node->left = left->right;
1040 a_bal = node->balance;
1041 b_bal = left->balance;
1046 left->balance = b_bal + 1;
1048 left->balance = a_bal + 2;
1049 node->balance = a_bal - b_bal + 1;
1054 left->balance = b_bal + 1;
1056 left->balance = a_bal + b_bal + 2;
1057 node->balance = a_bal + 1;
1064 g_tree_node_check (GTreeNode *node)
1076 left_height = g_tree_node_height (node->left);
1078 right_height = g_tree_node_height (node->right);
1080 balance = right_height - left_height;
1081 if (balance != node->balance)
1082 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO,
1083 "g_tree_node_check: failed: %d ( %d )\n",
1084 balance, node->balance);
1087 g_tree_node_check (node->left);
1089 g_tree_node_check (node->right);
1093 #define __G_TREE_C__
1094 #include "galiasdef.c"