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/.
34 typedef struct _GRealTree GRealTree
;
35 typedef struct _GTreeNode GTreeNode
;
40 GCompareFunc key_compare
;
45 gint balance
; /* height (left) - height (right) */
46 GTreeNode
*left
; /* left subtree */
47 GTreeNode
*right
; /* right subtree */
48 gpointer key
; /* key for this node */
49 gpointer value
; /* value stored at this node */
53 static GTreeNode
* g_tree_node_new (gpointer key
,
55 static void g_tree_node_destroy (GTreeNode
*node
);
56 static GTreeNode
* g_tree_node_insert (GTreeNode
*node
,
61 static GTreeNode
* g_tree_node_remove (GTreeNode
*node
,
64 static GTreeNode
* g_tree_node_balance (GTreeNode
*node
);
65 static GTreeNode
* g_tree_node_remove_leftmost (GTreeNode
*node
,
66 GTreeNode
**leftmost
);
67 static GTreeNode
* g_tree_node_restore_left_balance (GTreeNode
*node
,
69 static GTreeNode
* g_tree_node_restore_right_balance (GTreeNode
*node
,
71 static gpointer
g_tree_node_lookup (GTreeNode
*node
,
74 static gint
g_tree_node_count (GTreeNode
*node
);
75 static gint
g_tree_node_pre_order (GTreeNode
*node
,
76 GTraverseFunc traverse_func
,
78 static gint
g_tree_node_in_order (GTreeNode
*node
,
79 GTraverseFunc traverse_func
,
81 static gint
g_tree_node_post_order (GTreeNode
*node
,
82 GTraverseFunc traverse_func
,
84 static gpointer
g_tree_node_search (GTreeNode
*node
,
85 GCompareFunc search_func
,
87 static gint
g_tree_node_height (GTreeNode
*node
);
88 static GTreeNode
* g_tree_node_rotate_left (GTreeNode
*node
);
89 static GTreeNode
* g_tree_node_rotate_right (GTreeNode
*node
);
90 static void g_tree_node_check (GTreeNode
*node
);
93 G_LOCK_DEFINE_STATIC (g_tree_global
);
94 static GMemChunk
*node_mem_chunk
= NULL
;
95 static GTreeNode
*node_free_list
= NULL
;
99 g_tree_node_new (gpointer key
,
104 G_LOCK (g_tree_global
);
107 node
= node_free_list
;
108 node_free_list
= node
->right
;
113 node_mem_chunk
= g_mem_chunk_new ("GLib GTreeNode mem chunk",
118 node
= g_chunk_new (GTreeNode
, node_mem_chunk
);
120 G_UNLOCK (g_tree_global
);
132 g_tree_node_destroy (GTreeNode
*node
)
136 g_tree_node_destroy (node
->right
);
137 g_tree_node_destroy (node
->left
);
139 #ifdef ENABLE_GC_FRIENDLY
143 #endif /* ENABLE_GC_FRIENDLY */
145 G_LOCK (g_tree_global
);
146 node
->right
= node_free_list
;
147 node_free_list
= node
;
148 G_UNLOCK (g_tree_global
);
154 g_tree_new (GCompareFunc key_compare_func
)
158 g_return_val_if_fail (key_compare_func
!= NULL
, NULL
);
160 rtree
= g_new (GRealTree
, 1);
162 rtree
->key_compare
= key_compare_func
;
164 return (GTree
*) rtree
;
168 g_tree_destroy (GTree
*tree
)
172 g_return_if_fail (tree
!= NULL
);
174 rtree
= (GRealTree
*) tree
;
176 g_tree_node_destroy (rtree
->root
);
181 g_tree_insert (GTree
*tree
,
188 g_return_if_fail (tree
!= NULL
);
190 rtree
= (GRealTree
*) tree
;
193 rtree
->root
= g_tree_node_insert (rtree
->root
, rtree
->key_compare
,
194 key
, value
, &inserted
);
198 g_tree_remove (GTree
*tree
,
203 g_return_if_fail (tree
!= NULL
);
205 rtree
= (GRealTree
*) tree
;
207 rtree
->root
= g_tree_node_remove (rtree
->root
, rtree
->key_compare
, key
);
211 g_tree_lookup (GTree
*tree
,
216 g_return_val_if_fail (tree
!= NULL
, NULL
);
218 rtree
= (GRealTree
*) tree
;
220 return g_tree_node_lookup (rtree
->root
, rtree
->key_compare
, key
);
224 g_tree_traverse (GTree
*tree
,
225 GTraverseFunc traverse_func
,
226 GTraverseType traverse_type
,
231 g_return_if_fail (tree
!= NULL
);
233 rtree
= (GRealTree
*) tree
;
238 switch (traverse_type
)
241 g_tree_node_pre_order (rtree
->root
, traverse_func
, data
);
245 g_tree_node_in_order (rtree
->root
, traverse_func
, data
);
249 g_tree_node_post_order (rtree
->root
, traverse_func
, data
);
253 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
259 g_tree_search (GTree
*tree
,
260 GCompareFunc search_func
,
265 g_return_val_if_fail (tree
!= NULL
, NULL
);
267 rtree
= (GRealTree
*) tree
;
270 return g_tree_node_search (rtree
->root
, search_func
, data
);
276 g_tree_height (GTree
*tree
)
280 g_return_val_if_fail (tree
!= NULL
, 0);
282 rtree
= (GRealTree
*) tree
;
285 return g_tree_node_height (rtree
->root
);
291 g_tree_nnodes (GTree
*tree
)
295 g_return_val_if_fail (tree
!= NULL
, 0);
297 rtree
= (GRealTree
*) tree
;
300 return g_tree_node_count (rtree
->root
);
306 g_tree_node_insert (GTreeNode
*node
,
307 GCompareFunc compare
,
318 return g_tree_node_new (key
, value
);
321 cmp
= (* compare
) (key
, node
->key
);
333 old_balance
= node
->left
->balance
;
334 node
->left
= g_tree_node_insert (node
->left
, compare
, key
, value
, inserted
);
336 if ((old_balance
!= node
->left
->balance
) && node
->left
->balance
)
342 node
->left
= g_tree_node_new (key
, value
);
350 old_balance
= node
->right
->balance
;
351 node
->right
= g_tree_node_insert (node
->right
, compare
, key
, value
, inserted
);
353 if ((old_balance
!= node
->right
->balance
) && node
->right
->balance
)
359 node
->right
= g_tree_node_new (key
, value
);
366 if ((node
->balance
< -1) || (node
->balance
> 1))
367 node
= g_tree_node_balance (node
);
374 g_tree_node_remove (GTreeNode
*node
,
375 GCompareFunc compare
,
385 cmp
= (* compare
) (key
, node
->key
);
398 old_balance
= node
->right
->balance
;
399 node
->right
= g_tree_node_remove_leftmost (node
->right
, &new_root
);
400 new_root
->left
= node
->left
;
401 new_root
->right
= node
->right
;
402 new_root
->balance
= node
->balance
;
403 node
= g_tree_node_restore_right_balance (new_root
, old_balance
);
406 #ifdef ENABLE_GC_FRIENDLY
407 garbage
->left
= NULL
;
409 garbage
->value
= NULL
;
410 #endif /* ENABLE_GC_FRIENDLY */
412 G_LOCK (g_tree_global
);
413 garbage
->right
= node_free_list
;
414 node_free_list
= garbage
;
415 G_UNLOCK (g_tree_global
);
421 old_balance
= node
->left
->balance
;
422 node
->left
= g_tree_node_remove (node
->left
, compare
, key
);
423 node
= g_tree_node_restore_left_balance (node
, old_balance
);
430 old_balance
= node
->right
->balance
;
431 node
->right
= g_tree_node_remove (node
->right
, compare
, key
);
432 node
= g_tree_node_restore_right_balance (node
, old_balance
);
440 g_tree_node_balance (GTreeNode
*node
)
442 if (node
->balance
< -1)
444 if (node
->left
->balance
> 0)
445 node
->left
= g_tree_node_rotate_left (node
->left
);
446 node
= g_tree_node_rotate_right (node
);
448 else if (node
->balance
> 1)
450 if (node
->right
->balance
< 0)
451 node
->right
= g_tree_node_rotate_right (node
->right
);
452 node
= g_tree_node_rotate_left (node
);
459 g_tree_node_remove_leftmost (GTreeNode
*node
,
460 GTreeNode
**leftmost
)
470 old_balance
= node
->left
->balance
;
471 node
->left
= g_tree_node_remove_leftmost (node
->left
, leftmost
);
472 return g_tree_node_restore_left_balance (node
, old_balance
);
476 g_tree_node_restore_left_balance (GTreeNode
*node
,
481 else if ((node
->left
->balance
!= old_balance
) &&
482 (node
->left
->balance
== 0))
485 if (node
->balance
> 1)
486 return g_tree_node_balance (node
);
491 g_tree_node_restore_right_balance (GTreeNode
*node
,
496 else if ((node
->right
->balance
!= old_balance
) &&
497 (node
->right
->balance
== 0))
500 if (node
->balance
< -1)
501 return g_tree_node_balance (node
);
506 g_tree_node_lookup (GTreeNode
*node
,
507 GCompareFunc compare
,
515 cmp
= (* compare
) (key
, node
->key
);
522 return g_tree_node_lookup (node
->left
, compare
, key
);
527 return g_tree_node_lookup (node
->right
, compare
, key
);
534 g_tree_node_count (GTreeNode
*node
)
540 count
+= g_tree_node_count (node
->left
);
542 count
+= g_tree_node_count (node
->right
);
548 g_tree_node_pre_order (GTreeNode
*node
,
549 GTraverseFunc traverse_func
,
552 if ((*traverse_func
) (node
->key
, node
->value
, data
))
556 if (g_tree_node_pre_order (node
->left
, traverse_func
, data
))
561 if (g_tree_node_pre_order (node
->right
, traverse_func
, data
))
569 g_tree_node_in_order (GTreeNode
*node
,
570 GTraverseFunc traverse_func
,
575 if (g_tree_node_in_order (node
->left
, traverse_func
, data
))
578 if ((*traverse_func
) (node
->key
, node
->value
, data
))
582 if (g_tree_node_in_order (node
->right
, traverse_func
, data
))
590 g_tree_node_post_order (GTreeNode
*node
,
591 GTraverseFunc traverse_func
,
596 if (g_tree_node_post_order (node
->left
, traverse_func
, data
))
601 if (g_tree_node_post_order (node
->right
, traverse_func
, data
))
604 if ((*traverse_func
) (node
->key
, node
->value
, data
))
611 g_tree_node_search (GTreeNode
*node
,
612 GCompareFunc search_func
,
621 dir
= (* search_func
) (node
->key
, data
);
629 } while (node
&& (dir
!= 0));
635 g_tree_node_height (GTreeNode
*node
)
646 left_height
= g_tree_node_height (node
->left
);
649 right_height
= g_tree_node_height (node
->right
);
651 return MAX (left_height
, right_height
) + 1;
658 g_tree_node_rotate_left (GTreeNode
*node
)
666 node
->right
= right
->left
;
669 a_bal
= node
->balance
;
670 b_bal
= right
->balance
;
675 right
->balance
= b_bal
- 1;
677 right
->balance
= a_bal
+ b_bal
- 2;
678 node
->balance
= a_bal
- 1;
683 right
->balance
= a_bal
- 2;
685 right
->balance
= b_bal
- 1;
686 node
->balance
= a_bal
- b_bal
- 1;
693 g_tree_node_rotate_right (GTreeNode
*node
)
701 node
->left
= left
->right
;
704 a_bal
= node
->balance
;
705 b_bal
= left
->balance
;
710 left
->balance
= b_bal
+ 1;
712 left
->balance
= a_bal
+ 2;
713 node
->balance
= a_bal
- b_bal
+ 1;
718 left
->balance
= b_bal
+ 1;
720 left
->balance
= a_bal
+ b_bal
+ 2;
721 node
->balance
= a_bal
+ 1;
728 g_tree_node_check (GTreeNode
*node
)
740 left_height
= g_tree_node_height (node
->left
);
742 right_height
= g_tree_node_height (node
->right
);
744 balance
= right_height
- left_height
;
745 if (balance
!= node
->balance
)
746 g_log (g_log_domain_glib
, G_LOG_LEVEL_INFO
,
747 "g_tree_node_check: failed: %d ( %d )\n",
748 balance
, node
->balance
);
751 g_tree_node_check (node
->left
);
753 g_tree_node_check (node
->right
);