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 #define MAX_GTREE_HEIGHT 40
40 typedef struct _GTreeNode GTreeNode;
45 GCompareDataFunc key_compare;
46 GDestroyNotify key_destroy_func;
47 GDestroyNotify value_destroy_func;
48 gpointer key_compare_data;
54 gpointer key; /* key for this node */
55 gpointer value; /* value stored at this node */
56 GTreeNode *left; /* left subtree */
57 GTreeNode *right; /* right subtree */
58 gint8 balance; /* height (left) - height (right) */
64 static GTreeNode* g_tree_node_new (gpointer key,
66 static void g_tree_insert_internal (GTree *tree,
70 static gboolean g_tree_remove_internal (GTree *tree,
73 static GTreeNode* g_tree_node_balance (GTreeNode *node);
74 static GTreeNode *g_tree_find_node (GTree *tree,
76 static gint g_tree_node_pre_order (GTreeNode *node,
77 GTraverseFunc traverse_func,
79 static gint g_tree_node_in_order (GTreeNode *node,
80 GTraverseFunc traverse_func,
82 static gint g_tree_node_post_order (GTreeNode *node,
83 GTraverseFunc traverse_func,
85 static gpointer g_tree_node_search (GTreeNode *node,
86 GCompareFunc search_func,
88 static GTreeNode* g_tree_node_rotate_left (GTreeNode *node);
89 static GTreeNode* g_tree_node_rotate_right (GTreeNode *node);
91 static void g_tree_node_check (GTreeNode *node);
96 g_tree_node_new (gpointer key,
99 GTreeNode *node = g_slice_new (GTreeNode);
104 node->left_child = FALSE;
105 node->right_child = FALSE;
114 * @key_compare_func: the function used to order the nodes in the #GTree.
115 * It should return values similar to the standard strcmp() function -
116 * 0 if the two arguments are equal, a negative value if the first argument
117 * comes before the second, or a positive value if the first argument comes
120 * Creates a new #GTree.
122 * Return value: a new #GTree.
125 g_tree_new (GCompareFunc key_compare_func)
127 g_return_val_if_fail (key_compare_func != NULL, NULL);
129 return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
134 * g_tree_new_with_data:
135 * @key_compare_func: qsort()-style comparison function.
136 * @key_compare_data: data to pass to comparison function.
138 * Creates a new #GTree with a comparison function that accepts user data.
139 * See g_tree_new() for more details.
141 * Return value: a new #GTree.
144 g_tree_new_with_data (GCompareDataFunc key_compare_func,
145 gpointer key_compare_data)
147 g_return_val_if_fail (key_compare_func != NULL, NULL);
149 return g_tree_new_full (key_compare_func, key_compare_data,
155 * @key_compare_func: qsort()-style comparison function.
156 * @key_compare_data: data to pass to comparison function.
157 * @key_destroy_func: a function to free the memory allocated for the key
158 * used when removing the entry from the #GTree or %NULL if you don't
159 * want to supply such a function.
160 * @value_destroy_func: a function to free the memory allocated for the
161 * value used when removing the entry from the #GTree or %NULL if you
162 * don't want to supply such a function.
164 * Creates a new #GTree like g_tree_new() and allows to specify functions
165 * to free the memory allocated for the key and value that get called when
166 * removing the entry from the #GTree.
168 * Return value: a new #GTree.
171 g_tree_new_full (GCompareDataFunc key_compare_func,
172 gpointer key_compare_data,
173 GDestroyNotify key_destroy_func,
174 GDestroyNotify value_destroy_func)
178 g_return_val_if_fail (key_compare_func != NULL, NULL);
180 tree = g_new (GTree, 1);
182 tree->key_compare = key_compare_func;
183 tree->key_destroy_func = key_destroy_func;
184 tree->value_destroy_func = value_destroy_func;
185 tree->key_compare_data = key_compare_data;
191 static inline GTreeNode *
192 g_tree_first_node (GTree *tree)
201 while (tmp->left_child)
207 static inline GTreeNode *
208 g_tree_node_previous (GTreeNode *node)
214 if (node->left_child)
215 while (tmp->right_child)
221 static inline GTreeNode *
222 g_tree_node_next (GTreeNode *node)
228 if (node->right_child)
229 while (tmp->left_child)
239 * Destroys the #GTree. If keys and/or values are dynamically allocated, you
240 * should either free them first or create the #GTree using g_tree_new_full().
241 * In the latter case the destroy functions you supplied will be called on
242 * all keys and values before destroying the #GTree.
245 g_tree_destroy (GTree *tree)
250 g_return_if_fail (tree != NULL);
252 node = g_tree_first_node (tree);
256 next = g_tree_node_next (node);
258 if (tree->key_destroy_func)
259 tree->key_destroy_func (node->key);
260 if (tree->value_destroy_func)
261 tree->value_destroy_func (node->value);
263 #ifdef ENABLE_GC_FRIENDLY
268 #endif /* ENABLE_GC_FRIENDLY */
270 g_slice_free (GTreeNode, node);
281 * @key: the key to insert.
282 * @value: the value corresponding to the key.
284 * Inserts a key/value pair into a #GTree. If the given key already exists
285 * in the #GTree its corresponding value is set to the new value. If you
286 * supplied a value_destroy_func when creating the #GTree, the old value is
287 * freed using that function. If you supplied a @key_destroy_func when
288 * creating the #GTree, the passed key is freed using that function.
290 * The tree is automatically 'balanced' as new key/value pairs are added,
291 * so that the distance from the root to every leaf is as small as possible.
294 g_tree_insert (GTree *tree,
298 g_return_if_fail (tree != NULL);
300 g_tree_insert_internal (tree, key, value, FALSE);
303 g_tree_node_check (tree->root);
310 * @key: the key to insert.
311 * @value: the value corresponding to the key.
313 * Inserts a new key and value into a #GTree similar to g_tree_insert().
314 * The difference is that if the key already exists in the #GTree, it gets
315 * replaced by the new key. If you supplied a @value_destroy_func when
316 * creating the #GTree, the old value is freed using that function. If you
317 * supplied a @key_destroy_func when creating the #GTree, the old key is
318 * freed using that function.
320 * The tree is automatically 'balanced' as new key/value pairs are added,
321 * so that the distance from the root to every leaf is as small as possible.
324 g_tree_replace (GTree *tree,
328 g_return_if_fail (tree != NULL);
330 g_tree_insert_internal (tree, key, value, TRUE);
333 g_tree_node_check (tree->root);
337 /* internal insert routine */
339 g_tree_insert_internal (GTree *tree,
345 GTreeNode *path[MAX_GTREE_HEIGHT];
348 g_return_if_fail (tree != NULL);
352 tree->root = g_tree_node_new (key, value);
363 int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
367 if (tree->value_destroy_func)
368 tree->value_destroy_func (node->value);
374 if (tree->key_destroy_func)
375 tree->key_destroy_func (node->key);
381 /* free the passed key */
382 if (tree->key_destroy_func)
383 tree->key_destroy_func (key);
390 if (node->left_child)
397 GTreeNode *child = g_tree_node_new (key, value);
399 child->left = node->left;
402 node->left_child = TRUE;
412 if (node->right_child)
419 GTreeNode *child = g_tree_node_new (key, value);
421 child->right = node->right;
424 node->right_child = TRUE;
434 /* restore balance. This is the goodness of a non-recursive
435 implementation, when we are done with balancing we 'break'
436 the loop and we are done. */
439 GTreeNode *bparent = path[--idx];
440 gboolean left_node = (bparent && node == bparent->left);
441 g_assert (!bparent || bparent->left == node || bparent->right == node);
443 if (node->balance < -1 || node->balance > 1)
445 node = g_tree_node_balance (node);
449 bparent->left = node;
451 bparent->right = node;
454 if (node->balance == 0 || bparent == NULL)
458 bparent->balance -= 1;
460 bparent->balance += 1;
469 * @key: the key to remove.
471 * Removes a key/value pair from a #GTree.
473 * If the #GTree was created using g_tree_new_full(), the key and value
474 * are freed using the supplied destroy functions, otherwise you have to
475 * make sure that any dynamically allocated values are freed yourself.
476 * If the key does not exist in the #GTree, the function does nothing.
478 * Returns: %TRUE if the key was found (prior to 2.8, this function returned
482 g_tree_remove (GTree *tree,
487 g_return_val_if_fail (tree != NULL, FALSE);
489 removed = g_tree_remove_internal (tree, key, FALSE);
492 g_tree_node_check (tree->root);
501 * @key: the key to remove.
503 * Removes a key and its associated value from a #GTree without calling
504 * the key and value destroy functions.
506 * If the key does not exist in the #GTree, the function does nothing.
508 * Returns: %TRUE if the key was found (prior to 2.8, this function returned
512 g_tree_steal (GTree *tree,
517 g_return_val_if_fail (tree != NULL, FALSE);
519 removed = g_tree_remove_internal (tree, key, TRUE);
522 g_tree_node_check (tree->root);
528 /* internal remove routine */
530 g_tree_remove_internal (GTree *tree,
534 GTreeNode *node, *parent, *balance;
535 GTreeNode *path[MAX_GTREE_HEIGHT];
539 g_return_val_if_fail (tree != NULL, FALSE);
550 int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
556 if (!node->left_child)
564 if (!node->right_child)
572 /* the following code is almost equal to g_tree_remove_node,
573 except that we do not have to call g_tree_node_parent. */
574 balance = parent = path[--idx];
575 g_assert (!parent || parent->left == node || parent->right == node);
576 left_node = (parent && node == parent->left);
578 if (!node->left_child)
580 if (!node->right_child)
586 parent->left_child = FALSE;
587 parent->left = node->left;
588 parent->balance += 1;
592 parent->right_child = FALSE;
593 parent->right = node->right;
594 parent->balance -= 1;
597 else /* node has a right child */
599 GTreeNode *tmp = g_tree_node_next (node);
600 tmp->left = node->left;
603 tree->root = node->right;
606 parent->left = node->right;
607 parent->balance += 1;
611 parent->right = node->right;
612 parent->balance -= 1;
616 else /* node has a left child */
618 if (!node->right_child)
620 GTreeNode *tmp = g_tree_node_previous (node);
621 tmp->right = node->right;
624 tree->root = node->left;
627 parent->left = node->left;
628 parent->balance += 1;
632 parent->right = node->left;
633 parent->balance -= 1;
636 else /* node has a both children (pant, pant!) */
638 GTreeNode *prev = node->left;
639 GTreeNode *next = node->right;
640 GTreeNode *nextp = node;
641 int old_idx = idx + 1;
644 /* path[idx] == parent */
645 /* find the immediately next node (and its parent) */
646 while (next->left_child)
648 path[++idx] = nextp = next;
652 path[old_idx] = next;
655 /* remove 'next' from the tree */
658 if (next->right_child)
659 nextp->left = next->right;
661 nextp->left_child = FALSE;
664 next->right_child = TRUE;
665 next->right = node->right;
670 /* set the prev to point to the right place */
671 while (prev->right_child)
675 /* prepare 'next' to replace 'node' */
676 next->left_child = TRUE;
677 next->left = node->left;
678 next->balance = node->balance;
685 parent->right = next;
689 /* restore balance */
693 GTreeNode *bparent = path[--idx];
694 g_assert (!bparent || bparent->left == balance || bparent->right == balance);
695 left_node = (bparent && balance == bparent->left);
697 if(balance->balance < -1 || balance->balance > 1)
699 balance = g_tree_node_balance (balance);
701 tree->root = balance;
703 bparent->left = balance;
705 bparent->right = balance;
708 if (balance->balance != 0 || !bparent)
712 bparent->balance += 1;
714 bparent->balance -= 1;
721 if (tree->key_destroy_func)
722 tree->key_destroy_func (node->key);
723 if (tree->value_destroy_func)
724 tree->value_destroy_func (node->value);
727 #ifdef ENABLE_GC_FRIENDLY
732 #endif /* ENABLE_GC_FRIENDLY */
734 g_slice_free (GTreeNode, node);
744 * @key: the key to look up.
746 * Gets the value corresponding to the given key. Since a #GTree is
747 * automatically balanced as key/value pairs are added, key lookup is very
750 * Return value: the value corresponding to the key, or %NULL if the key was
754 g_tree_lookup (GTree *tree,
759 g_return_val_if_fail (tree != NULL, NULL);
761 node = g_tree_find_node (tree, key);
763 return node ? node->value : NULL;
767 * g_tree_lookup_extended:
769 * @lookup_key: the key to look up.
770 * @orig_key: returns the original key.
771 * @value: returns the value associated with the key.
773 * Looks up a key in the #GTree, returning the original key and the
774 * associated value and a #gboolean which is %TRUE if the key was found. This
775 * is useful if you need to free the memory allocated for the original key,
776 * for example before calling g_tree_remove().
778 * Return value: %TRUE if the key was found in the #GTree.
781 g_tree_lookup_extended (GTree *tree,
782 gconstpointer lookup_key,
788 g_return_val_if_fail (tree != NULL, FALSE);
790 node = g_tree_find_node (tree, lookup_key);
795 *orig_key = node->key;
797 *value = node->value;
807 * @func: the function to call for each node visited. If this function
808 * returns %TRUE, the traversal is stopped.
809 * @user_data: user data to pass to the function.
811 * Calls the given function for each of the key/value pairs in the #GTree.
812 * The function is passed the key and value of each pair, and the given
813 * @data parameter. The tree is traversed in sorted order.
815 * The tree may not be modified while iterating over it (you can't
816 * add/remove items). To remove all items matching a predicate, you need
817 * to add each item to a list in your #GTraverseFunc as you walk over
818 * the tree, then walk the list and remove each item.
821 g_tree_foreach (GTree *tree,
827 g_return_if_fail (tree != NULL);
832 node = g_tree_first_node (tree);
836 if ((*func) (node->key, node->value, user_data))
839 node = g_tree_node_next (node);
846 * @traverse_func: the function to call for each node visited. If this
847 * function returns %TRUE, the traversal is stopped.
848 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
849 * %G_PRE_ORDER and %G_POST_ORDER.
850 * @user_data: user data to pass to the function.
852 * Calls the given function for each node in the #GTree.
854 * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary. If you
855 * just want to visit all nodes in sorted order, use g_tree_foreach()
856 * instead. If you really need to visit nodes in a different order, consider
857 * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
860 g_tree_traverse (GTree *tree,
861 GTraverseFunc traverse_func,
862 GTraverseType traverse_type,
865 g_return_if_fail (tree != NULL);
870 switch (traverse_type)
873 g_tree_node_pre_order (tree->root, traverse_func, user_data);
877 g_tree_node_in_order (tree->root, traverse_func, user_data);
881 g_tree_node_post_order (tree->root, traverse_func, user_data);
885 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
893 * @search_func: a function used to search the #GTree.
894 * @user_data: the data passed as the second argument to the @search_func
897 * Searches a #GTree using @search_func.
899 * The @search_func is called with a pointer to the key of a key/value pair in
900 * the tree, and the passed in @user_data. If @search_func returns 0 for a
901 * key/value pair, then g_tree_search_func() will return the value of that
902 * pair. If @search_func returns -1, searching will proceed among the
903 * key/value pairs that have a smaller key; if @search_func returns 1,
904 * searching will proceed among the key/value pairs that have a larger key.
906 * Return value: the value corresponding to the found key, or %NULL if the key
910 g_tree_search (GTree *tree,
911 GCompareFunc search_func,
912 gconstpointer user_data)
914 g_return_val_if_fail (tree != NULL, NULL);
917 return g_tree_node_search (tree->root, search_func, user_data);
926 * Gets the height of a #GTree.
928 * If the #GTree contains no nodes, the height is 0.
929 * If the #GTree contains only one root node the height is 1.
930 * If the root node has children the height is 2, etc.
932 * Return value: the height of the #GTree.
935 g_tree_height (GTree *tree)
940 g_return_val_if_fail (tree != NULL, 0);
950 height += 1 + MAX(node->balance, 0);
952 if (!node->left_child)
963 * Gets the number of nodes in a #GTree.
965 * Return value: the number of nodes in the #GTree.
968 g_tree_nnodes (GTree *tree)
970 g_return_val_if_fail (tree != NULL, 0);
976 g_tree_node_balance (GTreeNode *node)
978 if (node->balance < -1)
980 if (node->left->balance > 0)
981 node->left = g_tree_node_rotate_left (node->left);
982 node = g_tree_node_rotate_right (node);
984 else if (node->balance > 1)
986 if (node->right->balance < 0)
987 node->right = g_tree_node_rotate_right (node->right);
988 node = g_tree_node_rotate_left (node);
995 g_tree_find_node (GTree *tree,
1007 cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1012 if (!node->left_child)
1019 if (!node->right_child)
1028 g_tree_node_pre_order (GTreeNode *node,
1029 GTraverseFunc traverse_func,
1032 if ((*traverse_func) (node->key, node->value, data))
1035 if (node->left_child)
1037 if (g_tree_node_pre_order (node->left, traverse_func, data))
1041 if (node->right_child)
1043 if (g_tree_node_pre_order (node->right, traverse_func, data))
1051 g_tree_node_in_order (GTreeNode *node,
1052 GTraverseFunc traverse_func,
1055 if (node->left_child)
1057 if (g_tree_node_in_order (node->left, traverse_func, data))
1061 if ((*traverse_func) (node->key, node->value, data))
1064 if (node->right_child)
1066 if (g_tree_node_in_order (node->right, traverse_func, data))
1074 g_tree_node_post_order (GTreeNode *node,
1075 GTraverseFunc traverse_func,
1078 if (node->left_child)
1080 if (g_tree_node_post_order (node->left, traverse_func, data))
1084 if (node->right_child)
1086 if (g_tree_node_post_order (node->right, traverse_func, data))
1090 if ((*traverse_func) (node->key, node->value, data))
1097 g_tree_node_search (GTreeNode *node,
1098 GCompareFunc search_func,
1108 dir = (* search_func) (node->key, data);
1113 if (!node->left_child)
1120 if (!node->right_child)
1129 g_tree_node_rotate_left (GTreeNode *node)
1135 right = node->right;
1137 if (right->left_child)
1138 node->right = right->left;
1141 node->right_child = FALSE;
1142 node->right = right;
1143 right->left_child = TRUE;
1147 a_bal = node->balance;
1148 b_bal = right->balance;
1153 right->balance = b_bal - 1;
1155 right->balance = a_bal + b_bal - 2;
1156 node->balance = a_bal - 1;
1161 right->balance = a_bal - 2;
1163 right->balance = b_bal - 1;
1164 node->balance = a_bal - b_bal - 1;
1171 g_tree_node_rotate_right (GTreeNode *node)
1179 if (left->right_child)
1180 node->left = left->right;
1183 node->left_child = FALSE;
1185 left->right_child = TRUE;
1189 a_bal = node->balance;
1190 b_bal = left->balance;
1195 left->balance = b_bal + 1;
1197 left->balance = a_bal + 2;
1198 node->balance = a_bal - b_bal + 1;
1203 left->balance = b_bal + 1;
1205 left->balance = a_bal + b_bal + 2;
1206 node->balance = a_bal + 1;
1214 g_tree_node_height (GTreeNode *node)
1224 if (node->left_child)
1225 left_height = g_tree_node_height (node->left);
1227 if (node->right_child)
1228 right_height = g_tree_node_height (node->right);
1230 return MAX (left_height, right_height) + 1;
1237 g_tree_node_check (GTreeNode *node)
1246 if (node->left_child)
1248 tmp = g_tree_node_previous (node);
1249 g_assert (tmp->right == node);
1252 if (node->right_child)
1254 tmp = g_tree_node_next (node);
1255 g_assert (tmp->left == node);
1261 if (node->left_child)
1262 left_height = g_tree_node_height (node->left);
1263 if (node->right_child)
1264 right_height = g_tree_node_height (node->right);
1266 balance = right_height - left_height;
1267 g_assert (balance == node->balance);
1269 if (node->left_child)
1270 g_tree_node_check (node->left);
1271 if (node->right_child)
1272 g_tree_node_check (node->right);
1277 g_tree_node_dump (GTreeNode *node,
1280 g_print ("%*s%c\n", indent, "", *(char *)node->key);
1282 if (node->left_child)
1283 g_tree_node_dump (node->left, indent + 2);
1284 else if (node->left)
1285 g_print ("%*s<%c\n", indent + 2, "", *(char *)node->left->key);
1287 if (node->right_child)
1288 g_tree_node_dump (node->right, indent + 2);
1289 else if (node->right)
1290 g_print ("%*s>%c\n", indent + 2, "", *(char *)node->right->key);
1295 g_tree_dump (GTree *tree)
1298 g_tree_node_dump (tree->root, 0);
1303 #define __G_TREE_C__
1304 #include "galiasdef.c"