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 _GRealTree GRealTree;
39 typedef struct _GTreeNode GTreeNode;
44 GCompareDataFunc key_compare;
45 GDestroyNotify key_destroy_func;
46 GDestroyNotify value_destroy_func;
47 gpointer key_compare_data;
52 gint balance; /* height (left) - height (right) */
53 GTreeNode *left; /* left subtree */
54 GTreeNode *right; /* right subtree */
55 gpointer key; /* key for this node */
56 gpointer value; /* value stored at this node */
60 static GTreeNode* g_tree_node_new (gpointer key,
62 static void g_tree_node_destroy (GTreeNode *node,
63 GDestroyNotify key_destroy_func,
64 GDestroyNotify value_destroy_func);
65 static GTreeNode* g_tree_node_insert (GTree *tree,
71 static GTreeNode* g_tree_node_remove (GTree *tree,
75 static GTreeNode* g_tree_node_balance (GTreeNode *node);
76 static GTreeNode* g_tree_node_remove_leftmost (GTreeNode *node,
77 GTreeNode **leftmost);
78 static GTreeNode* g_tree_node_restore_left_balance (GTreeNode *node,
80 static GTreeNode* g_tree_node_restore_right_balance (GTreeNode *node,
82 static GTreeNode* g_tree_node_lookup (GTreeNode *node,
83 GCompareDataFunc compare,
86 static gint g_tree_node_count (GTreeNode *node);
87 static gint g_tree_node_pre_order (GTreeNode *node,
88 GTraverseFunc traverse_func,
90 static gint g_tree_node_in_order (GTreeNode *node,
91 GTraverseFunc traverse_func,
93 static gint g_tree_node_post_order (GTreeNode *node,
94 GTraverseFunc traverse_func,
96 static gpointer g_tree_node_search (GTreeNode *node,
97 GCompareFunc search_func,
99 static gint g_tree_node_height (GTreeNode *node);
100 static GTreeNode* g_tree_node_rotate_left (GTreeNode *node);
101 static GTreeNode* g_tree_node_rotate_right (GTreeNode *node);
102 static void g_tree_node_check (GTreeNode *node);
105 G_LOCK_DEFINE_STATIC (g_tree_global);
106 static GMemChunk *node_mem_chunk = NULL;
107 static GTreeNode *node_free_list = NULL;
111 g_tree_node_new (gpointer key,
116 G_LOCK (g_tree_global);
119 node = node_free_list;
120 node_free_list = node->right;
125 node_mem_chunk = g_mem_chunk_new ("GLib GTreeNode mem chunk",
130 node = g_chunk_new (GTreeNode, node_mem_chunk);
132 G_UNLOCK (g_tree_global);
144 g_tree_node_destroy (GTreeNode *node,
145 GDestroyNotify key_destroy_func,
146 GDestroyNotify value_destroy_func)
150 g_tree_node_destroy (node->right,
151 key_destroy_func, value_destroy_func);
152 g_tree_node_destroy (node->left,
153 key_destroy_func, value_destroy_func);
155 if (key_destroy_func)
156 key_destroy_func (node->key);
157 if (value_destroy_func)
158 value_destroy_func (node->value);
160 #ifdef ENABLE_GC_FRIENDLY
164 #endif /* ENABLE_GC_FRIENDLY */
166 G_LOCK (g_tree_global);
167 node->right = node_free_list;
168 node_free_list = node;
169 G_UNLOCK (g_tree_global);
175 * @key_compare_func: the function used to order the nodes in the #GTree.
176 * It should return values similar to the standard
177 * <function>strcmp()</function> function -
178 * 0 if the two arguments are equal, a negative value if the first argument
179 * comes before the second, or a positive value if the first argument comes
182 * Creates a new #GTree.
184 * Return value: a new #GTree.
187 g_tree_new (GCompareFunc key_compare_func)
189 g_return_val_if_fail (key_compare_func != NULL, NULL);
191 return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
196 * g_tree_new_with_data:
197 * @key_compare_func: qsort()-style comparison function.
198 * @key_compare_data: data to pass to comparison function.
200 * Creates a new #GTree with a comparison function that accepts user data.
201 * See g_tree_new() for more details.
203 * Return value: a new #GTree.
206 g_tree_new_with_data (GCompareDataFunc key_compare_func,
207 gpointer key_compare_data)
209 g_return_val_if_fail (key_compare_func != NULL, NULL);
211 return g_tree_new_full (key_compare_func, key_compare_data,
217 * @key_compare_func: qsort()-style comparison function.
218 * @key_compare_data: data to pass to comparison function.
219 * @key_destroy_func: a function to free the memory allocated for the key
220 * used when removing the entry from the #GTree or #NULL if you don't
221 * want to supply such a function.
222 * @value_destroy_func: a function to free the memory allocated for the
223 * value used when removing the entry from the #GTree or #NULL if you
224 * don't want to supply such a function.
226 * Creates a new #GTree like g_tree_new() and allows to specify functions
227 * to free the memory allocated for the key and value that get called when
228 * removing the entry from the #GTree.
230 * Return value: a new #GTree.
233 g_tree_new_full (GCompareDataFunc key_compare_func,
234 gpointer key_compare_data,
235 GDestroyNotify key_destroy_func,
236 GDestroyNotify value_destroy_func)
240 g_return_val_if_fail (key_compare_func != NULL, NULL);
242 rtree = g_new (GRealTree, 1);
244 rtree->key_compare = key_compare_func;
245 rtree->key_destroy_func = key_destroy_func;
246 rtree->value_destroy_func = value_destroy_func;
247 rtree->key_compare_data = key_compare_data;
249 return (GTree*) rtree;
256 * Destroys the #GTree. If keys and/or values are dynamically allocated, you
257 * should either free them first or create the #GTree using g_tree_new_full().
258 * In the latter case the destroy functions you supplied will be called on
259 * all keys and values before destroying the #GTree.
262 g_tree_destroy (GTree *tree)
266 g_return_if_fail (tree != NULL);
268 rtree = (GRealTree*) tree;
270 g_tree_node_destroy (rtree->root,
271 rtree->key_destroy_func,
272 rtree->value_destroy_func);
280 * @key: the key to insert.
281 * @value: the value corresponding to the key.
283 * Inserts a key/value pair into a #GTree. If the given key already exists
284 * in the #GTree it is set to the new value. If you supplied a
285 * value_destroy_func when creating the #GTree, the old value is freed using
286 * that function. If you supplied a key_destroy_func when creating the
287 * #GTree, the passed key is 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_insert (GTree *tree,
300 g_return_if_fail (tree != NULL);
302 rtree = (GRealTree*) tree;
305 rtree->root = g_tree_node_insert (tree,
314 * @key: the key to insert.
315 * @value: the value corresponding to the key.
317 * Inserts a new key and value into a #GTree similar to g_tree_insert().
318 * The difference is that if the key already exists in the #GTree, it gets
319 * replaced by the new key. If you supplied a value_destroy_func when
320 * creating the #GTree, the old value is freed using that function. If you
321 * supplied a key_destroy_func when creating the #GTree, the old key is
322 * freed using that function.
324 * The tree is automatically 'balanced' as new key/value pairs are added,
325 * so that the distance from the root to every leaf is as small as possible.
328 g_tree_replace (GTree *tree,
335 g_return_if_fail (tree != NULL);
337 rtree = (GRealTree*) tree;
340 rtree->root = g_tree_node_insert (tree,
349 * @key: the key to remove.
351 * Removes a key/value pair from a #GTree.
353 * If the #GTree was created using g_tree_new_full(), the key and value
354 * are freed using the supplied destroy_functions, otherwise you have to
355 * make sure that any dynamically allocated values are freed yourself.
358 g_tree_remove (GTree *tree,
363 g_return_if_fail (tree != NULL);
365 rtree = (GRealTree*) tree;
367 rtree->root = g_tree_node_remove (tree, rtree->root, key, TRUE);
373 * @key: the key to remove.
375 * Removes a key and its associated value from a #GTree without calling
376 * the key and value destroy functions.
379 g_tree_steal (GTree *tree,
384 g_return_if_fail (tree != NULL);
386 rtree = (GRealTree*) tree;
388 rtree->root = g_tree_node_remove (tree, rtree->root, key, FALSE);
394 * @key: the key to look up.
396 * Gets the value corresponding to the given key. Since a #GTree is
397 * automatically balanced as key/value pairs are added, key lookup is very
400 * Return value: the value corresponding to the key.
403 g_tree_lookup (GTree *tree,
409 g_return_val_if_fail (tree != NULL, NULL);
411 rtree = (GRealTree*) tree;
413 node = g_tree_node_lookup (rtree->root,
414 rtree->key_compare, rtree->key_compare_data, key);
416 return node ? node->value : NULL;
420 * g_tree_lookup_extended:
422 * @lookup_key: the key to look up.
423 * @orig_key: returns the original key.
424 * @value: returns the value associated with the key.
426 * Looks up a key in the #GTree, returning the original key and the
427 * associated value and a gboolean which is TRUE if the key was found. This
428 * is useful if you need to free the memory allocated for the original key,
429 * for example before calling g_tree_remove().
431 * Return value: #TRUE if the key was found in the #GTree.
434 g_tree_lookup_extended (GTree *tree,
435 gconstpointer lookup_key,
442 g_return_val_if_fail (tree != NULL, FALSE);
444 rtree = (GRealTree*) tree;
446 node = g_tree_node_lookup (rtree->root,
447 rtree->key_compare, rtree->key_compare_data, lookup_key);
452 *orig_key = node->key;
454 *value = node->value;
464 * @func: the function to call for each node visited. If this function
465 * returns TRUE, the traversal is stopped.
466 * @user_data: user data to pass to the function.
468 * Calls the given function for each of the key/value pairs in the #GTree.
469 * The function is passed the key and value of each pair, and the given
473 g_tree_foreach (GTree *tree,
479 g_return_if_fail (tree != NULL);
481 rtree = (GRealTree*) tree;
486 g_tree_node_in_order (rtree->root, func, user_data);
492 * @traverse_func: the function to call for each node visited. If this
493 * function returns TRUE, the traversal is stopped.
494 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
495 * %G_PRE_ORDER and %G_POST_ORDER.
496 * @user_data: user data to pass to the function.
498 * Calls the given function for each node in the GTree. This function is
499 * deprecated, use g_tree_foreach() instead.
502 g_tree_traverse (GTree *tree,
503 GTraverseFunc traverse_func,
504 GTraverseType traverse_type,
509 g_return_if_fail (tree != NULL);
511 rtree = (GRealTree*) tree;
516 switch (traverse_type)
519 g_tree_node_pre_order (rtree->root, traverse_func, user_data);
523 g_tree_node_in_order (rtree->root, traverse_func, user_data);
527 g_tree_node_post_order (rtree->root, traverse_func, user_data);
531 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
539 * @search_func: the comparison function used to search the #GTree.
540 * @user_data: the data passed as the second argument to the @search_func
543 * Searches a #GTree using an alternative form of the comparison function.
545 * This function is not as useful as it sounds.
546 * It allows you to use a different function for performing the lookup of
547 * a key. However, since the tree is ordered according to the @key_compare_func
548 * function passed to g_tree_new(), the function you pass to g_tree_search()
549 * must return exactly the same value as would be returned by the comparison
550 * function, for each pair of tree nodes, or the search will not work.
552 * To search for a specific value, you can use g_tree_foreach() or
555 * Return value: the value corresponding to the found key, or NULL if the key
559 g_tree_search (GTree *tree,
560 GCompareFunc search_func,
561 gconstpointer user_data)
565 g_return_val_if_fail (tree != NULL, NULL);
567 rtree = (GRealTree*) tree;
570 return g_tree_node_search (rtree->root, search_func, user_data);
579 * Gets the height of a #GTree.
581 * If the #GTree contains no nodes, the height is 0.
582 * If the #GTree contains only one root node the height is 1.
583 * If the root node has children the height is 2, etc.
585 * Return value: the height of the #GTree.
588 g_tree_height (GTree *tree)
592 g_return_val_if_fail (tree != NULL, 0);
594 rtree = (GRealTree*) tree;
597 return g_tree_node_height (rtree->root);
606 * Gets the number of nodes in a #GTree.
608 * Return value: the number of nodes in the #GTree.
611 g_tree_nnodes (GTree *tree)
615 g_return_val_if_fail (tree != NULL, 0);
617 rtree = (GRealTree*) tree;
620 return g_tree_node_count (rtree->root);
626 g_tree_node_insert (GTree *tree,
637 rtree = (GRealTree*) tree;
642 return g_tree_node_new (key, value);
645 cmp = rtree->key_compare (key, node->key, rtree->key_compare_data);
650 if (rtree->value_destroy_func)
651 rtree->value_destroy_func (node->value);
657 if (rtree->key_destroy_func)
658 rtree->key_destroy_func (node->key);
664 /* free the passed key */
665 if (rtree->key_destroy_func)
666 rtree->key_destroy_func (key);
676 old_balance = node->left->balance;
677 node->left = g_tree_node_insert (tree,
682 if ((old_balance != node->left->balance) && node->left->balance)
688 node->left = g_tree_node_new (key, value);
696 old_balance = node->right->balance;
697 node->right = g_tree_node_insert (tree,
702 if ((old_balance != node->right->balance) && node->right->balance)
708 node->right = g_tree_node_new (key, value);
715 if ((node->balance < -1) || (node->balance > 1))
716 node = g_tree_node_balance (node);
723 g_tree_node_remove (GTree *tree,
736 rtree = (GRealTree *) tree;
738 cmp = rtree->key_compare (key, node->key, rtree->key_compare_data);
751 old_balance = node->right->balance;
752 node->right = g_tree_node_remove_leftmost (node->right, &new_root);
753 new_root->left = node->left;
754 new_root->right = node->right;
755 new_root->balance = node->balance;
756 node = g_tree_node_restore_right_balance (new_root, old_balance);
761 if (rtree->key_destroy_func)
762 rtree->key_destroy_func (garbage->key);
763 if (rtree->value_destroy_func)
764 rtree->value_destroy_func (garbage->value);
767 #ifdef ENABLE_GC_FRIENDLY
768 garbage->left = NULL;
770 garbage->value = NULL;
771 #endif /* ENABLE_GC_FRIENDLY */
773 G_LOCK (g_tree_global);
774 garbage->right = node_free_list;
775 node_free_list = garbage;
776 G_UNLOCK (g_tree_global);
782 old_balance = node->left->balance;
783 node->left = g_tree_node_remove (tree, node->left, key, notify);
784 node = g_tree_node_restore_left_balance (node, old_balance);
791 old_balance = node->right->balance;
792 node->right = g_tree_node_remove (tree, node->right, key, notify);
793 node = g_tree_node_restore_right_balance (node, old_balance);
801 g_tree_node_balance (GTreeNode *node)
803 if (node->balance < -1)
805 if (node->left->balance > 0)
806 node->left = g_tree_node_rotate_left (node->left);
807 node = g_tree_node_rotate_right (node);
809 else if (node->balance > 1)
811 if (node->right->balance < 0)
812 node->right = g_tree_node_rotate_right (node->right);
813 node = g_tree_node_rotate_left (node);
820 g_tree_node_remove_leftmost (GTreeNode *node,
821 GTreeNode **leftmost)
831 old_balance = node->left->balance;
832 node->left = g_tree_node_remove_leftmost (node->left, leftmost);
833 return g_tree_node_restore_left_balance (node, old_balance);
837 g_tree_node_restore_left_balance (GTreeNode *node,
842 else if ((node->left->balance != old_balance) &&
843 (node->left->balance == 0))
846 if (node->balance > 1)
847 return g_tree_node_balance (node);
852 g_tree_node_restore_right_balance (GTreeNode *node,
857 else if ((node->right->balance != old_balance) &&
858 (node->right->balance == 0))
861 if (node->balance < -1)
862 return g_tree_node_balance (node);
867 g_tree_node_lookup (GTreeNode *node,
868 GCompareDataFunc compare,
869 gpointer compare_data,
877 cmp = (* compare) (key, node->key, compare_data);
884 return g_tree_node_lookup (node->left, compare, compare_data, key);
889 return g_tree_node_lookup (node->right, compare, compare_data, key);
896 g_tree_node_count (GTreeNode *node)
902 count += g_tree_node_count (node->left);
904 count += g_tree_node_count (node->right);
910 g_tree_node_pre_order (GTreeNode *node,
911 GTraverseFunc traverse_func,
914 if ((*traverse_func) (node->key, node->value, data))
918 if (g_tree_node_pre_order (node->left, traverse_func, data))
923 if (g_tree_node_pre_order (node->right, traverse_func, data))
931 g_tree_node_in_order (GTreeNode *node,
932 GTraverseFunc traverse_func,
937 if (g_tree_node_in_order (node->left, traverse_func, data))
940 if ((*traverse_func) (node->key, node->value, data))
944 if (g_tree_node_in_order (node->right, traverse_func, data))
952 g_tree_node_post_order (GTreeNode *node,
953 GTraverseFunc traverse_func,
958 if (g_tree_node_post_order (node->left, traverse_func, data))
963 if (g_tree_node_post_order (node->right, traverse_func, data))
966 if ((*traverse_func) (node->key, node->value, data))
973 g_tree_node_search (GTreeNode *node,
974 GCompareFunc search_func,
983 dir = (* search_func) (node->key, data);
997 g_tree_node_height (GTreeNode *node)
1008 left_height = g_tree_node_height (node->left);
1011 right_height = g_tree_node_height (node->right);
1013 return MAX (left_height, right_height) + 1;
1020 g_tree_node_rotate_left (GTreeNode *node)
1026 right = node->right;
1028 node->right = right->left;
1031 a_bal = node->balance;
1032 b_bal = right->balance;
1037 right->balance = b_bal - 1;
1039 right->balance = a_bal + b_bal - 2;
1040 node->balance = a_bal - 1;
1045 right->balance = a_bal - 2;
1047 right->balance = b_bal - 1;
1048 node->balance = a_bal - b_bal - 1;
1055 g_tree_node_rotate_right (GTreeNode *node)
1063 node->left = left->right;
1066 a_bal = node->balance;
1067 b_bal = left->balance;
1072 left->balance = b_bal + 1;
1074 left->balance = a_bal + 2;
1075 node->balance = a_bal - b_bal + 1;
1080 left->balance = b_bal + 1;
1082 left->balance = a_bal + b_bal + 2;
1083 node->balance = a_bal + 1;
1090 g_tree_node_check (GTreeNode *node)
1102 left_height = g_tree_node_height (node->left);
1104 right_height = g_tree_node_height (node->right);
1106 balance = right_height - left_height;
1107 if (balance != node->balance)
1108 g_log (g_log_domain_glib, G_LOG_LEVEL_INFO,
1109 "g_tree_node_check: failed: %d ( %d )\n",
1110 balance, node->balance);
1113 g_tree_node_check (node->left);
1115 g_tree_node_check (node->right);