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.
27 typedef struct _GRealTree GRealTree
;
28 typedef struct _GTreeNode GTreeNode
;
33 GCompareFunc key_compare
;
38 gint balance
; /* height (left) - height (right) */
39 GTreeNode
*left
; /* left subtree */
40 GTreeNode
*right
; /* right subtree */
41 gpointer key
; /* key for this node */
42 gpointer value
; /* value stored at this node */
46 static GTreeNode
* g_tree_node_new (gpointer key
,
48 static void g_tree_node_destroy (GTreeNode
*node
);
49 static GTreeNode
* g_tree_node_insert (GTreeNode
*node
,
54 static GTreeNode
* g_tree_node_remove (GTreeNode
*node
,
57 static GTreeNode
* g_tree_node_balance (GTreeNode
*node
);
58 static GTreeNode
* g_tree_node_remove_leftmost (GTreeNode
*node
,
59 GTreeNode
**leftmost
);
60 static GTreeNode
* g_tree_node_restore_left_balance (GTreeNode
*node
,
62 static GTreeNode
* g_tree_node_restore_right_balance (GTreeNode
*node
,
64 static gpointer
g_tree_node_lookup (GTreeNode
*node
,
67 static gint
g_tree_node_count (GTreeNode
*node
);
68 static gint
g_tree_node_pre_order (GTreeNode
*node
,
69 GTraverseFunc traverse_func
,
71 static gint
g_tree_node_in_order (GTreeNode
*node
,
72 GTraverseFunc traverse_func
,
74 static gint
g_tree_node_post_order (GTreeNode
*node
,
75 GTraverseFunc traverse_func
,
77 static gpointer
g_tree_node_search (GTreeNode
*node
,
78 GSearchFunc search_func
,
80 static gint
g_tree_node_height (GTreeNode
*node
);
81 static GTreeNode
* g_tree_node_rotate_left (GTreeNode
*node
);
82 static GTreeNode
* g_tree_node_rotate_right (GTreeNode
*node
);
83 static void g_tree_node_check (GTreeNode
*node
);
86 G_LOCK_DECLARE_STATIC (g_tree_global
);
87 static GMemChunk
*node_mem_chunk
= NULL
;
88 static GTreeNode
*node_free_list
= NULL
;
92 g_tree_node_new (gpointer key
,
97 G_LOCK (g_tree_global
);
100 node
= node_free_list
;
101 node_free_list
= node
->right
;
106 node_mem_chunk
= g_mem_chunk_new ("GLib GTreeNode mem chunk",
111 node
= g_chunk_new (GTreeNode
, node_mem_chunk
);
113 G_UNLOCK (g_tree_global
);
125 g_tree_node_destroy (GTreeNode
*node
)
129 g_tree_node_destroy (node
->right
);
130 g_tree_node_destroy (node
->left
);
131 G_LOCK (g_tree_global
);
132 node
->right
= node_free_list
;
133 node_free_list
= node
;
134 G_UNLOCK (g_tree_global
);
140 g_tree_new (GCompareFunc key_compare_func
)
144 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
146 rtree
= g_new (GRealTree
, 1);
148 rtree
->key_compare
= key_compare_func
;
150 return (GTree
*) rtree
;
154 g_tree_destroy (GTree
*tree
)
158 g_return_if_fail (tree
!= NULL
);
160 rtree
= (GRealTree
*) tree
;
162 g_tree_node_destroy (rtree
->root
);
167 g_tree_insert (GTree
*tree
,
174 g_return_if_fail (tree
!= NULL
);
176 rtree
= (GRealTree
*) tree
;
179 rtree
->root
= g_tree_node_insert (rtree
->root
, rtree
->key_compare
,
180 key
, value
, &inserted
);
184 g_tree_remove (GTree
*tree
,
189 g_return_if_fail (tree
!= NULL
);
191 rtree
= (GRealTree
*) tree
;
193 rtree
->root
= g_tree_node_remove (rtree
->root
, rtree
->key_compare
, key
);
197 g_tree_lookup (GTree
*tree
,
202 g_return_val_if_fail (tree
!= NULL
, NULL
);
204 rtree
= (GRealTree
*) tree
;
206 return g_tree_node_lookup (rtree
->root
, rtree
->key_compare
, key
);
210 g_tree_traverse (GTree
*tree
,
211 GTraverseFunc traverse_func
,
212 GTraverseType traverse_type
,
217 g_return_if_fail (tree
!= NULL
);
219 rtree
= (GRealTree
*) tree
;
224 switch (traverse_type
)
227 g_tree_node_pre_order (rtree
->root
, traverse_func
, data
);
231 g_tree_node_in_order (rtree
->root
, traverse_func
, data
);
235 g_tree_node_post_order (rtree
->root
, traverse_func
, data
);
239 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
245 g_tree_search (GTree
*tree
,
246 GSearchFunc search_func
,
251 g_return_val_if_fail (tree
!= NULL
, NULL
);
253 rtree
= (GRealTree
*) tree
;
256 return g_tree_node_search (rtree
->root
, search_func
, data
);
262 g_tree_height (GTree
*tree
)
266 g_return_val_if_fail (tree
!= NULL
, 0);
268 rtree
= (GRealTree
*) tree
;
271 return g_tree_node_height (rtree
->root
);
277 g_tree_nnodes (GTree
*tree
)
281 g_return_val_if_fail (tree
!= NULL
, 0);
283 rtree
= (GRealTree
*) tree
;
286 return g_tree_node_count (rtree
->root
);
292 g_tree_node_insert (GTreeNode
*node
,
293 GCompareFunc compare
,
304 return g_tree_node_new (key
, value
);
307 cmp
= (* compare
) (key
, node
->key
);
319 old_balance
= node
->left
->balance
;
320 node
->left
= g_tree_node_insert (node
->left
, compare
, key
, value
, inserted
);
322 if ((old_balance
!= node
->left
->balance
) && node
->left
->balance
)
328 node
->left
= g_tree_node_new (key
, value
);
336 old_balance
= node
->right
->balance
;
337 node
->right
= g_tree_node_insert (node
->right
, compare
, key
, value
, inserted
);
339 if ((old_balance
!= node
->right
->balance
) && node
->right
->balance
)
345 node
->right
= g_tree_node_new (key
, value
);
352 if ((node
->balance
< -1) || (node
->balance
> 1))
353 node
= g_tree_node_balance (node
);
360 g_tree_node_remove (GTreeNode
*node
,
361 GCompareFunc compare
,
371 cmp
= (* compare
) (key
, node
->key
);
384 old_balance
= node
->right
->balance
;
385 node
->right
= g_tree_node_remove_leftmost (node
->right
, &new_root
);
386 new_root
->left
= node
->left
;
387 new_root
->right
= node
->right
;
388 new_root
->balance
= node
->balance
;
389 node
= g_tree_node_restore_right_balance (new_root
, old_balance
);
392 G_LOCK (g_tree_global
);
393 garbage
->right
= node_free_list
;
394 node_free_list
= garbage
;
395 G_UNLOCK (g_tree_global
);
401 old_balance
= node
->left
->balance
;
402 node
->left
= g_tree_node_remove (node
->left
, compare
, key
);
403 node
= g_tree_node_restore_left_balance (node
, old_balance
);
410 old_balance
= node
->right
->balance
;
411 node
->right
= g_tree_node_remove (node
->right
, compare
, key
);
412 node
= g_tree_node_restore_right_balance (node
, old_balance
);
420 g_tree_node_balance (GTreeNode
*node
)
422 if (node
->balance
< -1)
424 if (node
->left
->balance
> 0)
425 node
->left
= g_tree_node_rotate_left (node
->left
);
426 node
= g_tree_node_rotate_right (node
);
428 else if (node
->balance
> 1)
430 if (node
->right
->balance
< 0)
431 node
->right
= g_tree_node_rotate_right (node
->right
);
432 node
= g_tree_node_rotate_left (node
);
439 g_tree_node_remove_leftmost (GTreeNode
*node
,
440 GTreeNode
**leftmost
)
450 old_balance
= node
->left
->balance
;
451 node
->left
= g_tree_node_remove_leftmost (node
->left
, leftmost
);
452 return g_tree_node_restore_left_balance (node
, old_balance
);
456 g_tree_node_restore_left_balance (GTreeNode
*node
,
461 else if ((node
->left
->balance
!= old_balance
) &&
462 (node
->left
->balance
== 0))
465 if (node
->balance
> 1)
466 return g_tree_node_balance (node
);
471 g_tree_node_restore_right_balance (GTreeNode
*node
,
476 else if ((node
->right
->balance
!= old_balance
) &&
477 (node
->right
->balance
== 0))
480 if (node
->balance
< -1)
481 return g_tree_node_balance (node
);
486 g_tree_node_lookup (GTreeNode
*node
,
487 GCompareFunc compare
,
495 cmp
= (* compare
) (key
, node
->key
);
502 return g_tree_node_lookup (node
->left
, compare
, key
);
507 return g_tree_node_lookup (node
->right
, compare
, key
);
514 g_tree_node_count (GTreeNode
*node
)
520 count
+= g_tree_node_count (node
->left
);
522 count
+= g_tree_node_count (node
->right
);
528 g_tree_node_pre_order (GTreeNode
*node
,
529 GTraverseFunc traverse_func
,
532 if ((*traverse_func
) (node
->key
, node
->value
, data
))
536 if (g_tree_node_pre_order (node
->left
, traverse_func
, data
))
541 if (g_tree_node_pre_order (node
->right
, traverse_func
, data
))
549 g_tree_node_in_order (GTreeNode
*node
,
550 GTraverseFunc traverse_func
,
555 if (g_tree_node_in_order (node
->left
, traverse_func
, data
))
558 if ((*traverse_func
) (node
->key
, node
->value
, data
))
562 if (g_tree_node_in_order (node
->right
, traverse_func
, data
))
570 g_tree_node_post_order (GTreeNode
*node
,
571 GTraverseFunc traverse_func
,
576 if (g_tree_node_post_order (node
->left
, traverse_func
, data
))
581 if (g_tree_node_post_order (node
->right
, traverse_func
, data
))
584 if ((*traverse_func
) (node
->key
, node
->value
, data
))
591 g_tree_node_search (GTreeNode
*node
,
592 GSearchFunc search_func
,
601 dir
= (* search_func
) (node
->key
, data
);
609 } while (node
&& (dir
!= 0));
615 g_tree_node_height (GTreeNode
*node
)
626 left_height
= g_tree_node_height (node
->left
);
629 right_height
= g_tree_node_height (node
->right
);
631 return MAX (left_height
, right_height
) + 1;
638 g_tree_node_rotate_left (GTreeNode
*node
)
648 node
->right
= right
->left
;
651 a_bal
= node
->balance
;
652 b_bal
= right
->balance
;
657 right
->balance
= b_bal
- 1;
659 right
->balance
= a_bal
+ b_bal
- 2;
660 node
->balance
= a_bal
- 1;
665 right
->balance
= a_bal
- 2;
667 right
->balance
= b_bal
- 1;
668 node
->balance
= a_bal
- b_bal
- 1;
675 g_tree_node_rotate_right (GTreeNode
*node
)
685 node
->left
= left
->right
;
688 a_bal
= node
->balance
;
689 b_bal
= left
->balance
;
694 left
->balance
= b_bal
+ 1;
696 left
->balance
= a_bal
+ 2;
697 node
->balance
= a_bal
- b_bal
+ 1;
702 left
->balance
= b_bal
+ 1;
704 left
->balance
= a_bal
+ b_bal
+ 2;
705 node
->balance
= a_bal
+ 1;
712 g_tree_node_check (GTreeNode
*node
)
724 left_height
= g_tree_node_height (node
->left
);
726 right_height
= g_tree_node_height (node
->right
);
728 balance
= right_height
- left_height
;
729 if (balance
!= node
->balance
)
730 g_log (g_log_domain_glib
, G_LOG_LEVEL_INFO
,
731 "g_tree_node_check: failed: %d ( %d )\n",
732 balance
, node
->balance
);
735 g_tree_node_check (node
->left
);
737 g_tree_node_check (node
->right
);