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 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 static GTreeNode* g_tree_node_insert (GTreeNode *node,
62 GCompareDataFunc compare,
67 static GTreeNode* g_tree_node_remove (GTreeNode *node,
68 GCompareDataFunc compare,
71 static GTreeNode* g_tree_node_balance (GTreeNode *node);
72 static GTreeNode* g_tree_node_remove_leftmost (GTreeNode *node,
73 GTreeNode **leftmost);
74 static GTreeNode* g_tree_node_restore_left_balance (GTreeNode *node,
76 static GTreeNode* g_tree_node_restore_right_balance (GTreeNode *node,
78 static gpointer g_tree_node_lookup (GTreeNode *node,
79 GCompareDataFunc compare,
82 static gint g_tree_node_count (GTreeNode *node);
83 static gint g_tree_node_pre_order (GTreeNode *node,
84 GTraverseFunc traverse_func,
86 static gint g_tree_node_in_order (GTreeNode *node,
87 GTraverseFunc traverse_func,
89 static gint g_tree_node_post_order (GTreeNode *node,
90 GTraverseFunc traverse_func,
92 static gpointer g_tree_node_search (GTreeNode *node,
93 GCompareFunc search_func,
95 static gint g_tree_node_height (GTreeNode *node);
96 static GTreeNode* g_tree_node_rotate_left (GTreeNode *node);
97 static GTreeNode* g_tree_node_rotate_right (GTreeNode *node);
98 static void g_tree_node_check (GTreeNode *node);
101 G_LOCK_DEFINE_STATIC (g_tree_global);
102 static GMemChunk *node_mem_chunk = NULL;
103 static GTreeNode *node_free_list = NULL;
107 g_tree_node_new (gpointer key,
112 G_LOCK (g_tree_global);
115 node = node_free_list;
116 node_free_list = node->right;
121 node_mem_chunk = g_mem_chunk_new ("GLib GTreeNode mem chunk",
126 node = g_chunk_new (GTreeNode, node_mem_chunk);
128 G_UNLOCK (g_tree_global);
140 g_tree_node_destroy (GTreeNode *node)
144 g_tree_node_destroy (node->right);
145 g_tree_node_destroy (node->left);
147 #ifdef ENABLE_GC_FRIENDLY
151 #endif /* ENABLE_GC_FRIENDLY */
153 G_LOCK (g_tree_global);
154 node->right = node_free_list;
155 node_free_list = node;
156 G_UNLOCK (g_tree_global);
160 GTree* g_tree_new_udata(GCompareDataFunc key_compare_func,
161 gpointer key_compare_data)
165 g_return_val_if_fail (key_compare_func != NULL, NULL);
167 rtree = g_new (GRealTree, 1);
169 rtree->key_compare = key_compare_func;
170 rtree->key_compare_data = key_compare_data;
172 return (GTree*) rtree;
176 g_tree_new (GCompareFunc key_compare_func)
178 return g_tree_new_udata ((GCompareDataFunc) key_compare_func, NULL);
183 g_tree_destroy (GTree *tree)
187 g_return_if_fail (tree != NULL);
189 rtree = (GRealTree*) tree;
191 g_tree_node_destroy (rtree->root);
196 g_tree_insert (GTree *tree,
203 g_return_if_fail (tree != NULL);
205 rtree = (GRealTree*) tree;
208 rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare,
209 rtree->key_compare_data,
210 key, value, &inserted);
214 g_tree_remove (GTree *tree,
219 g_return_if_fail (tree != NULL);
221 rtree = (GRealTree*) tree;
223 rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare,
224 rtree->key_compare_data, key);
228 g_tree_lookup (GTree *tree,
233 g_return_val_if_fail (tree != NULL, NULL);
235 rtree = (GRealTree*) tree;
237 return g_tree_node_lookup (rtree->root, rtree->key_compare,
238 rtree->key_compare_data, key);
242 g_tree_lookup_extended (GTree *tree,
243 gconstpointer lookup_key,
250 g_return_val_if_fail (tree != NULL, FALSE);
252 rtree = (GRealTree*) tree;
254 node = g_tree_node_lookup (rtree->root,
256 rtree->key_compare_data,
262 *orig_key = node->key;
264 *value = node->value;
272 g_tree_traverse (GTree *tree,
273 GTraverseFunc traverse_func,
274 GTraverseType traverse_type,
279 g_return_if_fail (tree != NULL);
281 rtree = (GRealTree*) tree;
286 switch (traverse_type)
289 g_tree_node_pre_order (rtree->root, traverse_func, data);
293 g_tree_node_in_order (rtree->root, traverse_func, data);
297 g_tree_node_post_order (rtree->root, traverse_func, data);
301 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
307 g_tree_search (GTree *tree,
308 GCompareFunc search_func,
313 g_return_val_if_fail (tree != NULL, NULL);
315 rtree = (GRealTree*) tree;
318 return g_tree_node_search (rtree->root, search_func, data);
324 g_tree_height (GTree *tree)
328 g_return_val_if_fail (tree != NULL, 0);
330 rtree = (GRealTree*) tree;
333 return g_tree_node_height (rtree->root);
339 g_tree_nnodes (GTree *tree)
343 g_return_val_if_fail (tree != NULL, 0);
345 rtree = (GRealTree*) tree;
348 return g_tree_node_count (rtree->root);
354 g_tree_node_insert (GTreeNode *node,
355 GCompareDataFunc compare,
356 gpointer compare_data,
367 return g_tree_node_new (key, value);
370 cmp = (* compare) (key, node->key, compare_data);
382 old_balance = node->left->balance;
383 node->left = g_tree_node_insert (node->left, compare, compare_data,
384 key, value, inserted);
386 if ((old_balance != node->left->balance) && node->left->balance)
392 node->left = g_tree_node_new (key, value);
400 old_balance = node->right->balance;
401 node->right = g_tree_node_insert (node->right, compare, compare_data,
402 key, value, inserted);
404 if ((old_balance != node->right->balance) && node->right->balance)
410 node->right = g_tree_node_new (key, value);
417 if ((node->balance < -1) || (node->balance > 1))
418 node = g_tree_node_balance (node);
425 g_tree_node_remove (GTreeNode *node,
426 GCompareDataFunc compare,
427 gpointer compare_data,
437 cmp = (* compare) (key, node->key, compare_data);
450 old_balance = node->right->balance;
451 node->right = g_tree_node_remove_leftmost (node->right, &new_root);
452 new_root->left = node->left;
453 new_root->right = node->right;
454 new_root->balance = node->balance;
455 node = g_tree_node_restore_right_balance (new_root, old_balance);
458 #ifdef ENABLE_GC_FRIENDLY
459 garbage->left = NULL;
461 garbage->value = NULL;
462 #endif /* ENABLE_GC_FRIENDLY */
464 G_LOCK (g_tree_global);
465 garbage->right = node_free_list;
466 node_free_list = garbage;
467 G_UNLOCK (g_tree_global);
473 old_balance = node->left->balance;
474 node->left = g_tree_node_remove (node->left, compare, compare_data, key);
475 node = g_tree_node_restore_left_balance (node, old_balance);
482 old_balance = node->right->balance;
483 node->right = g_tree_node_remove (node->right, compare, compare_data, key);
484 node = g_tree_node_restore_right_balance (node, old_balance);
492 g_tree_node_balance (GTreeNode *node)
494 if (node->balance < -1)
496 if (node->left->balance > 0)
497 node->left = g_tree_node_rotate_left (node->left);
498 node = g_tree_node_rotate_right (node);
500 else if (node->balance > 1)
502 if (node->right->balance < 0)
503 node->right = g_tree_node_rotate_right (node->right);
504 node = g_tree_node_rotate_left (node);
511 g_tree_node_remove_leftmost (GTreeNode *node,
512 GTreeNode **leftmost)
522 old_balance = node->left->balance;
523 node->left = g_tree_node_remove_leftmost (node->left, leftmost);
524 return g_tree_node_restore_left_balance (node, old_balance);
528 g_tree_node_restore_left_balance (GTreeNode *node,
533 else if ((node->left->balance != old_balance) &&
534 (node->left->balance == 0))
537 if (node->balance > 1)
538 return g_tree_node_balance (node);
543 g_tree_node_restore_right_balance (GTreeNode *node,
548 else if ((node->right->balance != old_balance) &&
549 (node->right->balance == 0))
552 if (node->balance < -1)
553 return g_tree_node_balance (node);
558 g_tree_node_lookup (GTreeNode *node,
559 GCompareDataFunc compare,
560 gpointer compare_data,
568 cmp = (* compare) (key, node->key, compare_data);
575 return g_tree_node_lookup (node->left, compare, compare_data, key);
580 return g_tree_node_lookup (node->right, compare, compare_data, key);
587 g_tree_node_count (GTreeNode *node)
593 count += g_tree_node_count (node->left);
595 count += g_tree_node_count (node->right);
601 g_tree_node_pre_order (GTreeNode *node,
602 GTraverseFunc traverse_func,
605 if ((*traverse_func) (node->key, node->value, data))
609 if (g_tree_node_pre_order (node->left, traverse_func, data))
614 if (g_tree_node_pre_order (node->right, traverse_func, data))
622 g_tree_node_in_order (GTreeNode *node,
623 GTraverseFunc traverse_func,
628 if (g_tree_node_in_order (node->left, traverse_func, data))
631 if ((*traverse_func) (node->key, node->value, data))
635 if (g_tree_node_in_order (node->right, traverse_func, data))
643 g_tree_node_post_order (GTreeNode *node,
644 GTraverseFunc traverse_func,
649 if (g_tree_node_post_order (node->left, traverse_func, data))
654 if (g_tree_node_post_order (node->right, traverse_func, data))
657 if ((*traverse_func) (node->key, node->value, data))
664 g_tree_node_search (GTreeNode *node,
665 GCompareFunc search_func,
674 dir = (* search_func) (node->key, data);
688 g_tree_node_height (GTreeNode *node)
699 left_height = g_tree_node_height (node->left);
702 right_height = g_tree_node_height (node->right);
704 return MAX (left_height, right_height) + 1;
711 g_tree_node_rotate_left (GTreeNode *node)
719 node->right = right->left;
722 a_bal = node->balance;
723 b_bal = right->balance;
728 right->balance = b_bal - 1;
730 right->balance = a_bal + b_bal - 2;
731 node->balance = a_bal - 1;
736 right->balance = a_bal - 2;
738 right->balance = b_bal - 1;
739 node->balance = a_bal - b_bal - 1;
746 g_tree_node_rotate_right (GTreeNode *node)
754 node->left = left->right;
757 a_bal = node->balance;
758 b_bal = left->balance;
763 left->balance = b_bal + 1;
765 left->balance = a_bal + 2;
766 node->balance = a_bal - b_bal + 1;
771 left->balance = b_bal + 1;
773 left->balance = a_bal + b_bal + 2;
774 node->balance = a_bal + 1;
781 g_tree_node_check (GTreeNode *node)
793 left_height = g_tree_node_height (node->left);
795 right_height = g_tree_node_height (node->right);
797 balance = right_height - left_height;
798 if (balance != node->balance)
799 g_log (g_log_domain_glib, G_LOG_LEVEL_INFO,
800 "g_tree_node_check: failed: %d ( %d )\n",
801 balance, node->balance);
804 g_tree_node_check (node->left);
806 g_tree_node_check (node->right);