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 GCompareFuncData 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 GCompareFuncData compare
,
67 static GTreeNode
* g_tree_node_remove (GTreeNode
*node
,
68 GCompareFuncData 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 GCompareFuncData 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(GCompareFuncData 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 ((GCompareFuncData
) 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_traverse (GTree
*tree
,
243 GTraverseFunc traverse_func
,
244 GTraverseType traverse_type
,
249 g_return_if_fail (tree
!= NULL
);
251 rtree
= (GRealTree
*) tree
;
256 switch (traverse_type
)
259 g_tree_node_pre_order (rtree
->root
, traverse_func
, data
);
263 g_tree_node_in_order (rtree
->root
, traverse_func
, data
);
267 g_tree_node_post_order (rtree
->root
, traverse_func
, data
);
271 g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
277 g_tree_search (GTree
*tree
,
278 GCompareFunc search_func
,
283 g_return_val_if_fail (tree
!= NULL
, NULL
);
285 rtree
= (GRealTree
*) tree
;
288 return g_tree_node_search (rtree
->root
, search_func
, data
);
294 g_tree_height (GTree
*tree
)
298 g_return_val_if_fail (tree
!= NULL
, 0);
300 rtree
= (GRealTree
*) tree
;
303 return g_tree_node_height (rtree
->root
);
309 g_tree_nnodes (GTree
*tree
)
313 g_return_val_if_fail (tree
!= NULL
, 0);
315 rtree
= (GRealTree
*) tree
;
318 return g_tree_node_count (rtree
->root
);
324 g_tree_node_insert (GTreeNode
*node
,
325 GCompareFuncData compare
,
326 gpointer compare_data
,
337 return g_tree_node_new (key
, value
);
340 cmp
= (* compare
) (key
, node
->key
, compare_data
);
352 old_balance
= node
->left
->balance
;
353 node
->left
= g_tree_node_insert (node
->left
, compare
, compare_data
,
354 key
, value
, inserted
);
356 if ((old_balance
!= node
->left
->balance
) && node
->left
->balance
)
362 node
->left
= g_tree_node_new (key
, value
);
370 old_balance
= node
->right
->balance
;
371 node
->right
= g_tree_node_insert (node
->right
, compare
, compare_data
,
372 key
, value
, inserted
);
374 if ((old_balance
!= node
->right
->balance
) && node
->right
->balance
)
380 node
->right
= g_tree_node_new (key
, value
);
387 if ((node
->balance
< -1) || (node
->balance
> 1))
388 node
= g_tree_node_balance (node
);
395 g_tree_node_remove (GTreeNode
*node
,
396 GCompareFuncData compare
,
397 gpointer compare_data
,
407 cmp
= (* compare
) (key
, node
->key
, compare_data
);
420 old_balance
= node
->right
->balance
;
421 node
->right
= g_tree_node_remove_leftmost (node
->right
, &new_root
);
422 new_root
->left
= node
->left
;
423 new_root
->right
= node
->right
;
424 new_root
->balance
= node
->balance
;
425 node
= g_tree_node_restore_right_balance (new_root
, old_balance
);
428 #ifdef ENABLE_GC_FRIENDLY
429 garbage
->left
= NULL
;
431 garbage
->value
= NULL
;
432 #endif /* ENABLE_GC_FRIENDLY */
434 G_LOCK (g_tree_global
);
435 garbage
->right
= node_free_list
;
436 node_free_list
= garbage
;
437 G_UNLOCK (g_tree_global
);
443 old_balance
= node
->left
->balance
;
444 node
->left
= g_tree_node_remove (node
->left
, compare
, compare_data
, key
);
445 node
= g_tree_node_restore_left_balance (node
, old_balance
);
452 old_balance
= node
->right
->balance
;
453 node
->right
= g_tree_node_remove (node
->right
, compare
, compare_data
, key
);
454 node
= g_tree_node_restore_right_balance (node
, old_balance
);
462 g_tree_node_balance (GTreeNode
*node
)
464 if (node
->balance
< -1)
466 if (node
->left
->balance
> 0)
467 node
->left
= g_tree_node_rotate_left (node
->left
);
468 node
= g_tree_node_rotate_right (node
);
470 else if (node
->balance
> 1)
472 if (node
->right
->balance
< 0)
473 node
->right
= g_tree_node_rotate_right (node
->right
);
474 node
= g_tree_node_rotate_left (node
);
481 g_tree_node_remove_leftmost (GTreeNode
*node
,
482 GTreeNode
**leftmost
)
492 old_balance
= node
->left
->balance
;
493 node
->left
= g_tree_node_remove_leftmost (node
->left
, leftmost
);
494 return g_tree_node_restore_left_balance (node
, old_balance
);
498 g_tree_node_restore_left_balance (GTreeNode
*node
,
503 else if ((node
->left
->balance
!= old_balance
) &&
504 (node
->left
->balance
== 0))
507 if (node
->balance
> 1)
508 return g_tree_node_balance (node
);
513 g_tree_node_restore_right_balance (GTreeNode
*node
,
518 else if ((node
->right
->balance
!= old_balance
) &&
519 (node
->right
->balance
== 0))
522 if (node
->balance
< -1)
523 return g_tree_node_balance (node
);
528 g_tree_node_lookup (GTreeNode
*node
,
529 GCompareFuncData compare
,
530 gpointer compare_data
,
538 cmp
= (* compare
) (key
, node
->key
, compare_data
);
545 return g_tree_node_lookup (node
->left
, compare
, compare_data
, key
);
550 return g_tree_node_lookup (node
->right
, compare
, compare_data
, key
);
557 g_tree_node_count (GTreeNode
*node
)
563 count
+= g_tree_node_count (node
->left
);
565 count
+= g_tree_node_count (node
->right
);
571 g_tree_node_pre_order (GTreeNode
*node
,
572 GTraverseFunc traverse_func
,
575 if ((*traverse_func
) (node
->key
, node
->value
, data
))
579 if (g_tree_node_pre_order (node
->left
, traverse_func
, data
))
584 if (g_tree_node_pre_order (node
->right
, traverse_func
, data
))
592 g_tree_node_in_order (GTreeNode
*node
,
593 GTraverseFunc traverse_func
,
598 if (g_tree_node_in_order (node
->left
, traverse_func
, data
))
601 if ((*traverse_func
) (node
->key
, node
->value
, data
))
605 if (g_tree_node_in_order (node
->right
, traverse_func
, data
))
613 g_tree_node_post_order (GTreeNode
*node
,
614 GTraverseFunc traverse_func
,
619 if (g_tree_node_post_order (node
->left
, traverse_func
, data
))
624 if (g_tree_node_post_order (node
->right
, traverse_func
, data
))
627 if ((*traverse_func
) (node
->key
, node
->value
, data
))
634 g_tree_node_search (GTreeNode
*node
,
635 GCompareFunc search_func
,
644 dir
= (* search_func
) (node
->key
, data
);
652 } while (node
&& (dir
!= 0));
658 g_tree_node_height (GTreeNode
*node
)
669 left_height
= g_tree_node_height (node
->left
);
672 right_height
= g_tree_node_height (node
->right
);
674 return MAX (left_height
, right_height
) + 1;
681 g_tree_node_rotate_left (GTreeNode
*node
)
689 node
->right
= right
->left
;
692 a_bal
= node
->balance
;
693 b_bal
= right
->balance
;
698 right
->balance
= b_bal
- 1;
700 right
->balance
= a_bal
+ b_bal
- 2;
701 node
->balance
= a_bal
- 1;
706 right
->balance
= a_bal
- 2;
708 right
->balance
= b_bal
- 1;
709 node
->balance
= a_bal
- b_bal
- 1;
716 g_tree_node_rotate_right (GTreeNode
*node
)
724 node
->left
= left
->right
;
727 a_bal
= node
->balance
;
728 b_bal
= left
->balance
;
733 left
->balance
= b_bal
+ 1;
735 left
->balance
= a_bal
+ 2;
736 node
->balance
= a_bal
- b_bal
+ 1;
741 left
->balance
= b_bal
+ 1;
743 left
->balance
= a_bal
+ b_bal
+ 2;
744 node
->balance
= a_bal
+ 1;
751 g_tree_node_check (GTreeNode
*node
)
763 left_height
= g_tree_node_height (node
->left
);
765 right_height
= g_tree_node_height (node
->right
);
767 balance
= right_height
- left_height
;
768 if (balance
!= node
->balance
)
769 g_log (g_log_domain_glib
, G_LOG_LEVEL_INFO
,
770 "g_tree_node_check: failed: %d ( %d )\n",
771 balance
, node
->balance
);
774 g_tree_node_check (node
->left
);
776 g_tree_node_check (node
->right
);