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 Library 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 * Library General Public License for more details.
14 * You should have received a copy of the GNU Library 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.
22 typedef struct _GRealTree GRealTree;
23 typedef struct _GTreeNode GTreeNode;
28 GCompareFunc key_compare;
33 gint balance; /* height (left) - height (right) */
34 GTreeNode *left; /* left subtree */
35 GTreeNode *right; /* right subtree */
36 gpointer key; /* key for this node */
37 gpointer value; /* value stored at this node */
41 static GTreeNode* g_tree_node_new (gpointer key,
43 static void g_tree_node_destroy (GTreeNode *node);
44 static GTreeNode* g_tree_node_insert (GTreeNode *node,
49 static GTreeNode* g_tree_node_remove (GTreeNode *node,
52 static GTreeNode* g_tree_node_balance (GTreeNode *node);
53 static GTreeNode* g_tree_node_remove_leftmost (GTreeNode *node,
54 GTreeNode **leftmost);
55 static GTreeNode* g_tree_node_restore_left_balance (GTreeNode *node,
57 static GTreeNode* g_tree_node_restore_right_balance (GTreeNode *node,
59 static gpointer g_tree_node_lookup (GTreeNode *node,
62 static gint g_tree_node_count (GTreeNode *node);
63 static gint g_tree_node_pre_order (GTreeNode *node,
64 GTraverseFunc traverse_func,
66 static gint g_tree_node_in_order (GTreeNode *node,
67 GTraverseFunc traverse_func,
69 static gint g_tree_node_post_order (GTreeNode *node,
70 GTraverseFunc traverse_func,
72 static gpointer g_tree_node_search (GTreeNode *node,
73 GSearchFunc search_func,
75 static gint g_tree_node_height (GTreeNode *node);
76 static GTreeNode* g_tree_node_rotate_left (GTreeNode *node);
77 static GTreeNode* g_tree_node_rotate_right (GTreeNode *node);
78 static void g_tree_node_check (GTreeNode *node);
81 static GMemChunk *node_mem_chunk = NULL;
82 static GSList *node_free_list = NULL;
86 g_tree_new (GCompareFunc key_compare_func)
90 g_return_val_if_fail (key_compare_func != NULL, NULL);
92 rtree = g_new (GRealTree, 1);
94 rtree->key_compare = key_compare_func;
96 return (GTree*) rtree;
100 g_tree_destroy (GTree *tree)
104 g_return_if_fail (tree != NULL);
106 rtree = (GRealTree*) tree;
108 g_tree_node_destroy (rtree->root);
113 g_tree_insert (GTree *tree,
120 g_return_if_fail (tree != NULL);
122 rtree = (GRealTree*) tree;
125 rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare,
126 key, value, &inserted);
130 g_tree_remove (GTree *tree,
135 g_return_if_fail (tree != NULL);
137 rtree = (GRealTree*) tree;
139 rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare, key);
143 g_tree_lookup (GTree *tree,
148 g_return_val_if_fail (tree != NULL, NULL);
150 rtree = (GRealTree*) tree;
152 return g_tree_node_lookup (rtree->root, rtree->key_compare, key);
156 g_tree_traverse (GTree *tree,
157 GTraverseFunc traverse_func,
158 GTraverseType traverse_type,
163 g_return_if_fail (tree != NULL);
165 rtree = (GRealTree*) tree;
167 g_return_if_fail (rtree->root != NULL);
169 switch (traverse_type)
172 g_tree_node_pre_order (rtree->root, traverse_func, data);
176 g_tree_node_in_order (rtree->root, traverse_func, data);
180 g_tree_node_post_order (rtree->root, traverse_func, data);
184 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
190 g_tree_search (GTree *tree,
191 GSearchFunc search_func,
196 g_return_val_if_fail (tree != NULL, NULL);
198 rtree = (GRealTree*) tree;
201 return g_tree_node_search (rtree->root, search_func, data);
206 g_tree_height (GTree *tree)
210 g_return_val_if_fail (tree != NULL, 0);
212 rtree = (GRealTree*) tree;
215 return g_tree_node_height (rtree->root);
220 g_tree_nnodes (GTree *tree)
224 g_return_val_if_fail (tree != NULL, 0);
226 rtree = (GRealTree*) tree;
229 return g_tree_node_count (rtree->root);
235 g_tree_node_new (gpointer key,
243 tmp_list = node_free_list;
244 node_free_list = node_free_list->next;
246 node = tmp_list->data;
249 GListAllocator *tmp_allocator = g_list_set_allocator (NULL);
250 g_slist_free_1 (tmp_list);
251 g_list_set_allocator (tmp_allocator);
257 node_mem_chunk = g_mem_chunk_new ("tree node mem chunk", sizeof (GTreeNode), 1024, G_ALLOC_ONLY);
259 node = g_chunk_new (GTreeNode, node_mem_chunk);
272 g_tree_node_destroy (GTreeNode *node)
276 node_free_list = g_slist_prepend (node_free_list, node);
277 g_tree_node_destroy (node->right);
278 g_tree_node_destroy (node->left);
283 g_tree_node_insert (GTreeNode *node,
284 GCompareFunc compare,
295 return g_tree_node_new (key, value);
298 cmp = (* compare) (key, node->key);
310 old_balance = node->left->balance;
311 node->left = g_tree_node_insert (node->left, compare, key, value, inserted);
313 if ((old_balance != node->left->balance) && node->left->balance)
319 node->left = g_tree_node_new (key, value);
327 old_balance = node->right->balance;
328 node->right = g_tree_node_insert (node->right, compare, key, value, inserted);
330 if ((old_balance != node->right->balance) && node->right->balance)
336 node->right = g_tree_node_new (key, value);
343 if ((node->balance < -1) || (node->balance > 1))
344 node = g_tree_node_balance (node);
351 g_tree_node_remove (GTreeNode *node,
352 GCompareFunc compare,
363 cmp = (* compare) (key, node->key);
374 old_balance = node->right->balance;
375 node->right = g_tree_node_remove_leftmost (node->right, &new_root);
376 new_root->left = node->left;
377 new_root->right = node->right;
378 new_root->balance = node->balance;
379 node = g_tree_node_restore_right_balance (new_root, old_balance);
382 node_free_list = g_slist_prepend (node_free_list, garbage);
388 old_balance = node->left->balance;
389 node->left = g_tree_node_remove (node->left, compare, key);
390 node = g_tree_node_restore_left_balance (node, old_balance);
397 old_balance = node->right->balance;
398 node->right = g_tree_node_remove (node->right, compare, key);
399 node = g_tree_node_restore_right_balance (node, old_balance);
407 g_tree_node_balance (GTreeNode *node)
409 if (node->balance < -1)
411 if (node->left->balance > 0)
412 node->left = g_tree_node_rotate_left (node->left);
413 node = g_tree_node_rotate_right (node);
415 else if (node->balance > 1)
417 if (node->right->balance < 0)
418 node->right = g_tree_node_rotate_right (node->right);
419 node = g_tree_node_rotate_left (node);
426 g_tree_node_remove_leftmost (GTreeNode *node,
427 GTreeNode **leftmost)
437 old_balance = node->left->balance;
438 node->left = g_tree_node_remove_leftmost (node->left, leftmost);
439 return g_tree_node_restore_left_balance (node, old_balance);
443 g_tree_node_restore_left_balance (GTreeNode *node,
448 else if ((node->left->balance != old_balance) &&
449 (node->left->balance == 0))
452 if (node->balance > 1)
453 return g_tree_node_balance (node);
458 g_tree_node_restore_right_balance (GTreeNode *node,
463 else if ((node->right->balance != old_balance) &&
464 (node->right->balance == 0))
467 if (node->balance < -1)
468 return g_tree_node_balance (node);
473 g_tree_node_lookup (GTreeNode *node,
474 GCompareFunc compare,
482 cmp = (* compare) (key, node->key);
489 return g_tree_node_lookup (node->left, compare, key);
494 return g_tree_node_lookup (node->right, compare, key);
501 g_tree_node_count (GTreeNode *node)
507 count += g_tree_node_count (node->left);
509 count += g_tree_node_count (node->right);
515 g_tree_node_pre_order (GTreeNode *node,
516 GTraverseFunc traverse_func,
519 if ((*traverse_func) (node->key, node->value, data))
523 if (g_tree_node_pre_order (node->left, traverse_func, data))
528 if (g_tree_node_pre_order (node->right, traverse_func, data))
536 g_tree_node_in_order (GTreeNode *node,
537 GTraverseFunc traverse_func,
542 if (g_tree_node_in_order (node->left, traverse_func, data))
545 if ((*traverse_func) (node->key, node->value, data))
549 if (g_tree_node_in_order (node->right, traverse_func, data))
557 g_tree_node_post_order (GTreeNode *node,
558 GTraverseFunc traverse_func,
563 if (g_tree_node_post_order (node->left, traverse_func, data))
568 if (g_tree_node_post_order (node->right, traverse_func, data))
571 if ((*traverse_func) (node->key, node->value, data))
578 g_tree_node_search (GTreeNode *node,
579 GSearchFunc search_func,
588 dir = (* search_func) (node->key, data);
596 } while (node && (dir != 0));
602 g_tree_node_height (GTreeNode *node)
613 left_height = g_tree_node_height (node->left);
616 right_height = g_tree_node_height (node->right);
618 return MAX (left_height, right_height) + 1;
625 g_tree_node_rotate_left (GTreeNode *node)
635 node->right = right->left;
638 a_bal = node->balance;
639 b_bal = right->balance;
644 right->balance = b_bal - 1;
646 right->balance = a_bal + b_bal - 2;
647 node->balance = a_bal - 1;
652 right->balance = a_bal - 2;
654 right->balance = b_bal - 1;
655 node->balance = a_bal - b_bal - 1;
662 g_tree_node_rotate_right (GTreeNode *node)
672 node->left = left->right;
675 a_bal = node->balance;
676 b_bal = left->balance;
681 left->balance = b_bal + 1;
683 left->balance = a_bal + 2;
684 node->balance = a_bal - b_bal + 1;
689 left->balance = b_bal + 1;
691 left->balance = a_bal + b_bal + 2;
692 node->balance = a_bal + 1;
699 g_tree_node_check (GTreeNode *node)
711 left_height = g_tree_node_height (node->left);
713 right_height = g_tree_node_height (node->right);
715 balance = right_height - left_height;
716 if (balance != node->balance)
717 g_log (g_log_domain_glib, G_LOG_LEVEL_INFO,
718 "g_tree_node_check: failed: %d ( %d )\n",
719 balance, node->balance);
722 g_tree_node_check (node->left);
724 g_tree_node_check (node->right);