Merge remote branch 'gvdb/master'
[platform/upstream/glib.git] / glib / gtree.c
1 /* GLIB - Library of useful routines for C programming
2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
3  *
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.
8  *
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.
13  *
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.
18  */
19
20 /*
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/. 
25  */
26
27 /* 
28  * MT safe
29  */
30
31 #include "config.h"
32
33 #include "glib.h"
34 #include "galias.h"
35
36 /**
37  * SECTION: trees-binary
38  * @title: Balanced Binary Trees
39  * @short_description: a sorted collection of key/value pairs optimized
40  *                     for searching and traversing in order
41  *
42  * The #GTree structure and its associated functions provide a sorted
43  * collection of key/value pairs optimized for searching and traversing
44  * in order.
45  *
46  * To create a new #GTree use g_tree_new().
47  *
48  * To insert a key/value pair into a #GTree use g_tree_insert().
49  *
50  * To lookup the value corresponding to a given key, use
51  * g_tree_lookup() and g_tree_lookup_extended().
52  *
53  * To find out the number of nodes in a #GTree, use g_tree_nnodes(). To
54  * get the height of a #GTree, use g_tree_height().
55  *
56  * To traverse a #GTree, calling a function for each node visited in
57  * the traversal, use g_tree_foreach().
58  *
59  * To remove a key/value pair use g_tree_remove().
60  *
61  * To destroy a #GTree, use g_tree_destroy().
62  **/
63
64 #undef G_TREE_DEBUG
65
66 #define MAX_GTREE_HEIGHT 40
67
68 typedef struct _GTreeNode  GTreeNode;
69
70 /**
71  * GTree:
72  *
73  * The <structname>GTree</structname> struct is an opaque data
74  * structure representing a <link
75  * linkend="glib-Balanced-Binary-Trees">Balanced Binary Tree</link>. It
76  * should be accessed only by using the following functions.
77  **/
78 struct _GTree
79 {
80   GTreeNode        *root;
81   GCompareDataFunc  key_compare;
82   GDestroyNotify    key_destroy_func;
83   GDestroyNotify    value_destroy_func;
84   gpointer          key_compare_data;
85   guint             nnodes;
86   gint              ref_count;
87 };
88
89 struct _GTreeNode
90 {
91   gpointer   key;         /* key for this node */
92   gpointer   value;       /* value stored at this node */
93   GTreeNode *left;        /* left subtree */
94   GTreeNode *right;       /* right subtree */
95   gint8      balance;     /* height (left) - height (right) */
96   guint8     left_child;  
97   guint8     right_child;
98 };
99
100
101 static GTreeNode* g_tree_node_new                   (gpointer       key,
102                                                      gpointer       value);
103 static void       g_tree_insert_internal            (GTree         *tree,
104                                                      gpointer       key,
105                                                      gpointer       value,
106                                                      gboolean       replace);
107 static gboolean   g_tree_remove_internal            (GTree         *tree,
108                                                      gconstpointer  key,
109                                                      gboolean       steal);
110 static GTreeNode* g_tree_node_balance               (GTreeNode     *node);
111 static GTreeNode *g_tree_find_node                  (GTree         *tree,
112                                                      gconstpointer  key);
113 static gint       g_tree_node_pre_order             (GTreeNode     *node,
114                                                      GTraverseFunc  traverse_func,
115                                                      gpointer       data);
116 static gint       g_tree_node_in_order              (GTreeNode     *node,
117                                                      GTraverseFunc  traverse_func,
118                                                      gpointer       data);
119 static gint       g_tree_node_post_order            (GTreeNode     *node,
120                                                      GTraverseFunc  traverse_func,
121                                                      gpointer       data);
122 static gpointer   g_tree_node_search                (GTreeNode     *node,
123                                                      GCompareFunc   search_func,
124                                                      gconstpointer  data);
125 static GTreeNode* g_tree_node_rotate_left           (GTreeNode     *node);
126 static GTreeNode* g_tree_node_rotate_right          (GTreeNode     *node);
127 #ifdef G_TREE_DEBUG
128 static void       g_tree_node_check                 (GTreeNode     *node);
129 #endif
130
131
132 static GTreeNode*
133 g_tree_node_new (gpointer key,
134                  gpointer value)
135 {
136   GTreeNode *node = g_slice_new (GTreeNode);
137
138   node->balance = 0;
139   node->left = NULL;
140   node->right = NULL;
141   node->left_child = FALSE;
142   node->right_child = FALSE;
143   node->key = key;
144   node->value = value;
145
146   return node;
147 }
148
149 /**
150  * g_tree_new:
151  * @key_compare_func: the function used to order the nodes in the #GTree.
152  *   It should return values similar to the standard strcmp() function -
153  *   0 if the two arguments are equal, a negative value if the first argument 
154  *   comes before the second, or a positive value if the first argument comes 
155  *   after the second.
156  * 
157  * Creates a new #GTree.
158  * 
159  * Return value: a new #GTree.
160  **/
161 GTree*
162 g_tree_new (GCompareFunc key_compare_func)
163 {
164   g_return_val_if_fail (key_compare_func != NULL, NULL);
165
166   return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
167                           NULL, NULL);
168 }
169
170 /**
171  * g_tree_new_with_data:
172  * @key_compare_func: qsort()-style comparison function.
173  * @key_compare_data: data to pass to comparison function.
174  * 
175  * Creates a new #GTree with a comparison function that accepts user data.
176  * See g_tree_new() for more details.
177  * 
178  * Return value: a new #GTree.
179  **/
180 GTree*
181 g_tree_new_with_data (GCompareDataFunc key_compare_func,
182                       gpointer         key_compare_data)
183 {
184   g_return_val_if_fail (key_compare_func != NULL, NULL);
185   
186   return g_tree_new_full (key_compare_func, key_compare_data, 
187                           NULL, NULL);
188 }
189
190 /**
191  * g_tree_new_full:
192  * @key_compare_func: qsort()-style comparison function.
193  * @key_compare_data: data to pass to comparison function.
194  * @key_destroy_func: a function to free the memory allocated for the key 
195  *   used when removing the entry from the #GTree or %NULL if you don't
196  *   want to supply such a function.
197  * @value_destroy_func: a function to free the memory allocated for the 
198  *   value used when removing the entry from the #GTree or %NULL if you 
199  *   don't want to supply such a function.
200  * 
201  * Creates a new #GTree like g_tree_new() and allows to specify functions 
202  * to free the memory allocated for the key and value that get called when 
203  * removing the entry from the #GTree.
204  * 
205  * Return value: a new #GTree.
206  **/
207 GTree*   
208 g_tree_new_full (GCompareDataFunc key_compare_func,
209                  gpointer         key_compare_data,              
210                  GDestroyNotify   key_destroy_func,
211                  GDestroyNotify   value_destroy_func)
212 {
213   GTree *tree;
214   
215   g_return_val_if_fail (key_compare_func != NULL, NULL);
216   
217   tree = g_slice_new (GTree);
218   tree->root               = NULL;
219   tree->key_compare        = key_compare_func;
220   tree->key_destroy_func   = key_destroy_func;
221   tree->value_destroy_func = value_destroy_func;
222   tree->key_compare_data   = key_compare_data;
223   tree->nnodes             = 0;
224   tree->ref_count          = 1;
225   
226   return tree;
227 }
228
229 static inline GTreeNode *
230 g_tree_first_node (GTree *tree)
231 {
232   GTreeNode *tmp;
233
234   if (!tree->root)
235     return NULL;
236
237   tmp = tree->root;
238
239   while (tmp->left_child)
240     tmp = tmp->left;
241
242   return tmp;
243
244
245 static inline GTreeNode *
246 g_tree_node_previous (GTreeNode *node)
247 {
248   GTreeNode *tmp;
249
250   tmp = node->left;
251
252   if (node->left_child)
253     while (tmp->right_child)
254       tmp = tmp->right;
255
256   return tmp;
257 }
258                   
259 static inline GTreeNode *
260 g_tree_node_next (GTreeNode *node)
261 {
262   GTreeNode *tmp;
263
264   tmp = node->right;
265
266   if (node->right_child)
267     while (tmp->left_child)
268       tmp = tmp->left;
269
270   return tmp;
271 }
272
273 static void
274 g_tree_remove_all (GTree *tree)
275 {
276   GTreeNode *node;
277   GTreeNode *next;
278
279   g_return_if_fail (tree != NULL);
280
281   node = g_tree_first_node (tree);
282
283   while (node)
284     {
285       next = g_tree_node_next (node);
286
287       if (tree->key_destroy_func)
288         tree->key_destroy_func (node->key);
289       if (tree->value_destroy_func)
290         tree->value_destroy_func (node->value);
291       g_slice_free (GTreeNode, node);
292
293       node = next;
294     }
295
296   tree->root = NULL;
297   tree->nnodes = 0;
298 }
299
300 /**
301  * g_tree_ref:
302  * @tree: a #GTree.
303  *
304  * Increments the reference count of @tree by one.  It is safe to call
305  * this function from any thread.
306  *
307  * Return value: the passed in #GTree.
308  *
309  * Since: 2.22
310  **/
311 GTree *
312 g_tree_ref (GTree *tree)
313 {
314   g_return_val_if_fail (tree != NULL, NULL);
315
316   g_atomic_int_inc (&tree->ref_count);
317
318   return tree;
319 }
320
321 /**
322  * g_tree_unref:
323  * @tree: a #GTree.
324  *
325  * Decrements the reference count of @tree by one.  If the reference count
326  * drops to 0, all keys and values will be destroyed (if destroy
327  * functions were specified) and all memory allocated by @tree will be
328  * released.
329  *
330  * It is safe to call this function from any thread.
331  *
332  * Since: 2.22
333  **/
334 void
335 g_tree_unref (GTree *tree)
336 {
337   g_return_if_fail (tree != NULL);
338
339   if (g_atomic_int_dec_and_test (&tree->ref_count))
340     {
341       g_tree_remove_all (tree);
342       g_slice_free (GTree, tree);
343     }
344 }
345
346 /**
347  * g_tree_destroy:
348  * @tree: a #GTree.
349  * 
350  * Removes all keys and values from the #GTree and decreases its
351  * reference count by one. If keys and/or values are dynamically
352  * allocated, you should either free them first or create the #GTree
353  * using g_tree_new_full().  In the latter case the destroy functions
354  * you supplied will be called on all keys and values before destroying
355  * the #GTree.
356  **/
357 void
358 g_tree_destroy (GTree *tree)
359 {
360   g_return_if_fail (tree != NULL);
361
362   g_tree_remove_all (tree);
363   g_tree_unref (tree);
364 }
365
366 /**
367  * g_tree_insert:
368  * @tree: a #GTree.
369  * @key: the key to insert.
370  * @value: the value corresponding to the key.
371  * 
372  * Inserts a key/value pair into a #GTree. If the given key already exists 
373  * in the #GTree its corresponding value is set to the new value. If you 
374  * supplied a value_destroy_func when creating the #GTree, the old value is 
375  * freed using that function. If you supplied a @key_destroy_func when 
376  * creating the #GTree, the passed key is freed using that function.
377  *
378  * The tree is automatically 'balanced' as new key/value pairs are added,
379  * so that the distance from the root to every leaf is as small as possible.
380  **/
381 void
382 g_tree_insert (GTree    *tree,
383                gpointer  key,
384                gpointer  value)
385 {
386   g_return_if_fail (tree != NULL);
387
388   g_tree_insert_internal (tree, key, value, FALSE);
389
390 #ifdef G_TREE_DEBUG
391   g_tree_node_check (tree->root);
392 #endif
393 }
394
395 /**
396  * g_tree_replace:
397  * @tree: a #GTree.
398  * @key: the key to insert.
399  * @value: the value corresponding to the key.
400  * 
401  * Inserts a new key and value into a #GTree similar to g_tree_insert(). 
402  * The difference is that if the key already exists in the #GTree, it gets 
403  * replaced by the new key. If you supplied a @value_destroy_func when 
404  * creating the #GTree, the old value is freed using that function. If you 
405  * supplied a @key_destroy_func when creating the #GTree, the old key is 
406  * freed using that function. 
407  *
408  * The tree is automatically 'balanced' as new key/value pairs are added,
409  * so that the distance from the root to every leaf is as small as possible.
410  **/
411 void
412 g_tree_replace (GTree    *tree,
413                 gpointer  key,
414                 gpointer  value)
415 {
416   g_return_if_fail (tree != NULL);
417
418   g_tree_insert_internal (tree, key, value, TRUE);
419
420 #ifdef G_TREE_DEBUG
421   g_tree_node_check (tree->root);
422 #endif
423 }
424
425 /* internal insert routine */
426 static void
427 g_tree_insert_internal (GTree    *tree,
428                         gpointer  key,
429                         gpointer  value,
430                         gboolean  replace)
431 {
432   GTreeNode *node;
433   GTreeNode *path[MAX_GTREE_HEIGHT];
434   int idx;
435
436   g_return_if_fail (tree != NULL);
437
438   if (!tree->root)
439     {
440       tree->root = g_tree_node_new (key, value);
441       tree->nnodes++;
442       return;
443     }
444
445   idx = 0;
446   path[idx++] = NULL;
447   node = tree->root;
448
449   while (1)
450     {
451       int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
452       
453       if (cmp == 0)
454         {
455           if (tree->value_destroy_func)
456             tree->value_destroy_func (node->value);
457
458           node->value = value;
459
460           if (replace)
461             {
462               if (tree->key_destroy_func)
463                 tree->key_destroy_func (node->key);
464
465               node->key = key;
466             }
467           else
468             {
469               /* free the passed key */
470               if (tree->key_destroy_func)
471                 tree->key_destroy_func (key);
472             }
473
474           return;
475         }
476       else if (cmp < 0)
477         {
478           if (node->left_child)
479             {
480               path[idx++] = node;
481               node = node->left;
482             }
483           else
484             {
485               GTreeNode *child = g_tree_node_new (key, value);
486
487               child->left = node->left;
488               child->right = node;
489               node->left = child;
490               node->left_child = TRUE;
491               node->balance -= 1;
492
493               tree->nnodes++;
494
495               break;
496             }
497         }
498       else
499         {
500           if (node->right_child)
501             {
502               path[idx++] = node;
503               node = node->right;
504             }
505           else
506             {
507               GTreeNode *child = g_tree_node_new (key, value);
508
509               child->right = node->right;
510               child->left = node;
511               node->right = child;
512               node->right_child = TRUE;
513               node->balance += 1;
514
515               tree->nnodes++;
516
517               break;
518             }
519         }
520     }
521
522   /* restore balance. This is the goodness of a non-recursive
523      implementation, when we are done with balancing we 'break'
524      the loop and we are done. */
525   while (1)
526     {
527       GTreeNode *bparent = path[--idx];
528       gboolean left_node = (bparent && node == bparent->left);
529       g_assert (!bparent || bparent->left == node || bparent->right == node);
530
531       if (node->balance < -1 || node->balance > 1)
532         {
533           node = g_tree_node_balance (node);
534           if (bparent == NULL)
535             tree->root = node;
536           else if (left_node)
537             bparent->left = node;
538           else
539             bparent->right = node;
540         }
541
542       if (node->balance == 0 || bparent == NULL)
543         break;
544       
545       if (left_node)
546         bparent->balance -= 1;
547       else
548         bparent->balance += 1;
549
550       node = bparent;
551     }
552 }
553
554 /**
555  * g_tree_remove:
556  * @tree: a #GTree.
557  * @key: the key to remove.
558  * 
559  * Removes a key/value pair from a #GTree.
560  *
561  * If the #GTree was created using g_tree_new_full(), the key and value 
562  * are freed using the supplied destroy functions, otherwise you have to 
563  * make sure that any dynamically allocated values are freed yourself.
564  * If the key does not exist in the #GTree, the function does nothing.
565  *
566  * Returns: %TRUE if the key was found (prior to 2.8, this function returned 
567  *   nothing)
568  **/
569 gboolean
570 g_tree_remove (GTree         *tree,
571                gconstpointer  key)
572 {
573   gboolean removed;
574
575   g_return_val_if_fail (tree != NULL, FALSE);
576
577   removed = g_tree_remove_internal (tree, key, FALSE);
578
579 #ifdef G_TREE_DEBUG
580   g_tree_node_check (tree->root);
581 #endif
582
583   return removed;
584 }
585
586 /**
587  * g_tree_steal:
588  * @tree: a #GTree.
589  * @key: the key to remove.
590  * 
591  * Removes a key and its associated value from a #GTree without calling 
592  * the key and value destroy functions.
593  *
594  * If the key does not exist in the #GTree, the function does nothing.
595  *
596  * Returns: %TRUE if the key was found (prior to 2.8, this function returned 
597  *    nothing)
598  **/
599 gboolean
600 g_tree_steal (GTree         *tree,
601               gconstpointer  key)
602 {
603   gboolean removed;
604
605   g_return_val_if_fail (tree != NULL, FALSE);
606
607   removed = g_tree_remove_internal (tree, key, TRUE);
608
609 #ifdef G_TREE_DEBUG
610   g_tree_node_check (tree->root);
611 #endif
612
613   return removed;
614 }
615
616 /* internal remove routine */
617 static gboolean
618 g_tree_remove_internal (GTree         *tree,
619                         gconstpointer  key,
620                         gboolean       steal)
621 {
622   GTreeNode *node, *parent, *balance;
623   GTreeNode *path[MAX_GTREE_HEIGHT];
624   int idx;
625   gboolean left_node;
626
627   g_return_val_if_fail (tree != NULL, FALSE);
628
629   if (!tree->root)
630     return FALSE;
631
632   idx = 0;
633   path[idx++] = NULL;
634   node = tree->root;
635
636   while (1)
637     {
638       int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
639       
640       if (cmp == 0)
641         break;
642       else if (cmp < 0)
643         {
644           if (!node->left_child)
645             return FALSE;
646           
647           path[idx++] = node;
648           node = node->left;
649         }
650       else
651         {
652           if (!node->right_child)
653             return FALSE;
654           
655           path[idx++] = node;
656           node = node->right;
657         }
658     }
659
660   /* the following code is almost equal to g_tree_remove_node,
661      except that we do not have to call g_tree_node_parent. */
662   balance = parent = path[--idx];
663   g_assert (!parent || parent->left == node || parent->right == node);
664   left_node = (parent && node == parent->left);
665
666   if (!node->left_child)
667     {
668       if (!node->right_child)
669         {
670           if (!parent)
671             tree->root = NULL;
672           else if (left_node)
673             {
674               parent->left_child = FALSE;
675               parent->left = node->left;
676               parent->balance += 1;
677             }
678           else
679             {
680               parent->right_child = FALSE;
681               parent->right = node->right;
682               parent->balance -= 1;
683             }
684         }
685       else /* node has a right child */
686         {
687           GTreeNode *tmp = g_tree_node_next (node);
688           tmp->left = node->left;
689
690           if (!parent)
691             tree->root = node->right;
692           else if (left_node)
693             {
694               parent->left = node->right;
695               parent->balance += 1;
696             }
697           else
698             {
699               parent->right = node->right;
700               parent->balance -= 1;
701             }
702         }
703     }
704   else /* node has a left child */
705     {
706       if (!node->right_child)
707         {
708           GTreeNode *tmp = g_tree_node_previous (node);
709           tmp->right = node->right;
710           
711           if (parent == NULL)
712             tree->root = node->left;
713           else if (left_node)
714             {
715               parent->left = node->left;
716               parent->balance += 1;
717             }
718           else
719             {
720               parent->right = node->left;
721               parent->balance -= 1;
722             }
723         }
724       else /* node has a both children (pant, pant!) */
725         {
726           GTreeNode *prev = node->left;
727           GTreeNode *next = node->right;
728           GTreeNode *nextp = node;
729           int old_idx = idx + 1;
730           idx++;
731           
732           /* path[idx] == parent */
733           /* find the immediately next node (and its parent) */
734           while (next->left_child)
735             {
736               path[++idx] = nextp = next;
737               next = next->left;
738             }
739           
740           path[old_idx] = next;
741           balance = path[idx];
742           
743           /* remove 'next' from the tree */
744           if (nextp != node)
745             {
746               if (next->right_child)
747                 nextp->left = next->right;
748               else
749                 nextp->left_child = FALSE;
750               nextp->balance += 1;
751               
752               next->right_child = TRUE;
753               next->right = node->right;
754             }
755           else
756             node->balance -= 1;
757             
758           /* set the prev to point to the right place */
759           while (prev->right_child)
760             prev = prev->right;
761           prev->right = next;
762             
763           /* prepare 'next' to replace 'node' */
764           next->left_child = TRUE;
765           next->left = node->left;
766           next->balance = node->balance;
767           
768           if (!parent)
769             tree->root = next;
770           else if (left_node)
771             parent->left = next;
772           else
773             parent->right = next;
774         }
775     }
776   
777   /* restore balance */
778   if (balance)
779     while (1)
780       {
781         GTreeNode *bparent = path[--idx];
782         g_assert (!bparent || bparent->left == balance || bparent->right == balance);
783         left_node = (bparent && balance == bparent->left);
784                               
785         if(balance->balance < -1 || balance->balance > 1)
786           {
787             balance = g_tree_node_balance (balance);
788             if (!bparent)
789               tree->root = balance;
790             else if (left_node)
791               bparent->left = balance;
792             else
793               bparent->right = balance;
794           }
795         
796         if (balance->balance != 0 || !bparent)
797           break;
798         
799         if (left_node)
800           bparent->balance += 1;
801         else
802           bparent->balance -= 1;
803         
804         balance = bparent;
805       }
806   
807   if (!steal)
808     {
809       if (tree->key_destroy_func)
810         tree->key_destroy_func (node->key);
811       if (tree->value_destroy_func)
812         tree->value_destroy_func (node->value);
813     }
814
815   g_slice_free (GTreeNode, node);
816
817   tree->nnodes--;
818
819   return TRUE;
820 }
821
822 /**
823  * g_tree_lookup:
824  * @tree: a #GTree.
825  * @key: the key to look up.
826  * 
827  * Gets the value corresponding to the given key. Since a #GTree is 
828  * automatically balanced as key/value pairs are added, key lookup is very 
829  * fast.
830  *
831  * Return value: the value corresponding to the key, or %NULL if the key was
832  * not found.
833  **/
834 gpointer
835 g_tree_lookup (GTree         *tree,
836                gconstpointer  key)
837 {
838   GTreeNode *node;
839
840   g_return_val_if_fail (tree != NULL, NULL);
841
842   node = g_tree_find_node (tree, key);
843   
844   return node ? node->value : NULL;
845 }
846
847 /**
848  * g_tree_lookup_extended:
849  * @tree: a #GTree.
850  * @lookup_key: the key to look up.
851  * @orig_key: returns the original key.
852  * @value: returns the value associated with the key.
853  * 
854  * Looks up a key in the #GTree, returning the original key and the
855  * associated value and a #gboolean which is %TRUE if the key was found. This 
856  * is useful if you need to free the memory allocated for the original key, 
857  * for example before calling g_tree_remove().
858  * 
859  * Return value: %TRUE if the key was found in the #GTree.
860  **/
861 gboolean
862 g_tree_lookup_extended (GTree         *tree,
863                         gconstpointer  lookup_key,
864                         gpointer      *orig_key,
865                         gpointer      *value)
866 {
867   GTreeNode *node;
868   
869   g_return_val_if_fail (tree != NULL, FALSE);
870   
871   node = g_tree_find_node (tree, lookup_key);
872   
873   if (node)
874     {
875       if (orig_key)
876         *orig_key = node->key;
877       if (value)
878         *value = node->value;
879       return TRUE;
880     }
881   else
882     return FALSE;
883 }
884
885 /**
886  * g_tree_foreach:
887  * @tree: a #GTree.
888  * @func: the function to call for each node visited. If this function
889  *   returns %TRUE, the traversal is stopped.
890  * @user_data: user data to pass to the function.
891  * 
892  * Calls the given function for each of the key/value pairs in the #GTree.
893  * The function is passed the key and value of each pair, and the given
894  * @data parameter. The tree is traversed in sorted order.
895  *
896  * The tree may not be modified while iterating over it (you can't 
897  * add/remove items). To remove all items matching a predicate, you need 
898  * to add each item to a list in your #GTraverseFunc as you walk over 
899  * the tree, then walk the list and remove each item.
900  **/
901 void
902 g_tree_foreach (GTree         *tree,
903                 GTraverseFunc  func,
904                 gpointer       user_data)
905 {
906   GTreeNode *node;
907
908   g_return_if_fail (tree != NULL);
909   
910   if (!tree->root)
911     return;
912
913   node = g_tree_first_node (tree);
914   
915   while (node)
916     {
917       if ((*func) (node->key, node->value, user_data))
918         break;
919       
920       node = g_tree_node_next (node);
921     }
922 }
923
924 /**
925  * g_tree_traverse:
926  * @tree: a #GTree.
927  * @traverse_func: the function to call for each node visited. If this 
928  *   function returns %TRUE, the traversal is stopped.
929  * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
930  *   %G_PRE_ORDER and %G_POST_ORDER.
931  * @user_data: user data to pass to the function.
932  * 
933  * Calls the given function for each node in the #GTree. 
934  *
935  * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary. If you 
936  * just want to visit all nodes in sorted order, use g_tree_foreach() 
937  * instead. If you really need to visit nodes in a different order, consider
938  * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
939  **/
940 /**
941  * GTraverseFunc:
942  * @key: a key of a #GTree node.
943  * @value: the value corresponding to the key.
944  * @data: user data passed to g_tree_traverse().
945  * @Returns: %TRUE to stop the traversal.
946  *
947  * Specifies the type of function passed to g_tree_traverse(). It is
948  * passed the key and value of each node, together with the @user_data
949  * parameter passed to g_tree_traverse(). If the function returns
950  * %TRUE, the traversal is stopped.
951  **/
952 /**
953  * GTraverseType:
954  * @G_IN_ORDER: vists a node's left child first, then the node itself,
955  *              then its right child. This is the one to use if you
956  *              want the output sorted according to the compare
957  *              function.
958  * @G_PRE_ORDER: visits a node, then its children.
959  * @G_POST_ORDER: visits the node's children, then the node itself.
960  * @G_LEVEL_ORDER: is not implemented for <link
961  *                 linkend="glib-Balanced-Binary-Trees">Balanced Binary
962  *                 Trees</link>.  For <link
963  *                 linkend="glib-N-ary-Trees">N-ary Trees</link>, it
964  *                 vists the root node first, then its children, then
965  *                 its grandchildren, and so on. Note that this is less
966  *                 efficient than the other orders.
967  *
968  * Specifies the type of traveral performed by g_tree_traverse(),
969  * g_node_traverse() and g_node_find().
970  **/
971 void
972 g_tree_traverse (GTree         *tree,
973                  GTraverseFunc  traverse_func,
974                  GTraverseType  traverse_type,
975                  gpointer       user_data)
976 {
977   g_return_if_fail (tree != NULL);
978
979   if (!tree->root)
980     return;
981
982   switch (traverse_type)
983     {
984     case G_PRE_ORDER:
985       g_tree_node_pre_order (tree->root, traverse_func, user_data);
986       break;
987
988     case G_IN_ORDER:
989       g_tree_node_in_order (tree->root, traverse_func, user_data);
990       break;
991
992     case G_POST_ORDER:
993       g_tree_node_post_order (tree->root, traverse_func, user_data);
994       break;
995     
996     case G_LEVEL_ORDER:
997       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
998       break;
999     }
1000 }
1001
1002 /**
1003  * g_tree_search:
1004  * @tree: a #GTree.
1005  * @search_func: a function used to search the #GTree. 
1006  * @user_data: the data passed as the second argument to the @search_func 
1007  * function.
1008  * 
1009  * Searches a #GTree using @search_func.
1010  *
1011  * The @search_func is called with a pointer to the key of a key/value pair in 
1012  * the tree, and the passed in @user_data. If @search_func returns 0 for a 
1013  * key/value pair, then g_tree_search_func() will return the value of that 
1014  * pair. If @search_func returns -1,  searching will proceed among the 
1015  * key/value pairs that have a smaller key; if @search_func returns 1, 
1016  * searching will proceed among the key/value pairs that have a larger key.
1017  *
1018  * Return value: the value corresponding to the found key, or %NULL if the key 
1019  * was not found.
1020  **/
1021 gpointer
1022 g_tree_search (GTree         *tree,
1023                GCompareFunc   search_func,
1024                gconstpointer  user_data)
1025 {
1026   g_return_val_if_fail (tree != NULL, NULL);
1027
1028   if (tree->root)
1029     return g_tree_node_search (tree->root, search_func, user_data);
1030   else
1031     return NULL;
1032 }
1033
1034 /**
1035  * g_tree_height:
1036  * @tree: a #GTree.
1037  * 
1038  * Gets the height of a #GTree.
1039  *
1040  * If the #GTree contains no nodes, the height is 0.
1041  * If the #GTree contains only one root node the height is 1.
1042  * If the root node has children the height is 2, etc.
1043  * 
1044  * Return value: the height of the #GTree.
1045  **/
1046 gint
1047 g_tree_height (GTree *tree)
1048 {
1049   GTreeNode *node;
1050   gint height;
1051
1052   g_return_val_if_fail (tree != NULL, 0);
1053
1054   if (!tree->root)
1055     return 0;
1056
1057   height = 0;
1058   node = tree->root;
1059
1060   while (1)
1061     {
1062       height += 1 + MAX(node->balance, 0);
1063
1064       if (!node->left_child)
1065         return height;
1066       
1067       node = node->left;
1068     }
1069 }
1070
1071 /**
1072  * g_tree_nnodes:
1073  * @tree: a #GTree.
1074  * 
1075  * Gets the number of nodes in a #GTree.
1076  * 
1077  * Return value: the number of nodes in the #GTree.
1078  **/
1079 gint
1080 g_tree_nnodes (GTree *tree)
1081 {
1082   g_return_val_if_fail (tree != NULL, 0);
1083
1084   return tree->nnodes;
1085 }
1086
1087 static GTreeNode*
1088 g_tree_node_balance (GTreeNode *node)
1089 {
1090   if (node->balance < -1)
1091     {
1092       if (node->left->balance > 0)
1093         node->left = g_tree_node_rotate_left (node->left);
1094       node = g_tree_node_rotate_right (node);
1095     }
1096   else if (node->balance > 1)
1097     {
1098       if (node->right->balance < 0)
1099         node->right = g_tree_node_rotate_right (node->right);
1100       node = g_tree_node_rotate_left (node);
1101     }
1102
1103   return node;
1104 }
1105
1106 static GTreeNode *
1107 g_tree_find_node (GTree        *tree,
1108                   gconstpointer key)
1109 {
1110   GTreeNode *node;
1111   gint cmp;
1112
1113   node = tree->root;
1114   if (!node)
1115     return NULL;
1116
1117   while (1)
1118     {
1119       cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1120       if (cmp == 0)
1121         return node;
1122       else if (cmp < 0)
1123         {
1124           if (!node->left_child)
1125             return NULL;
1126
1127           node = node->left;
1128         }
1129       else
1130         {
1131           if (!node->right_child)
1132             return NULL;
1133
1134           node = node->right;
1135         }
1136     }
1137 }
1138
1139 static gint
1140 g_tree_node_pre_order (GTreeNode     *node,
1141                        GTraverseFunc  traverse_func,
1142                        gpointer       data)
1143 {
1144   if ((*traverse_func) (node->key, node->value, data))
1145     return TRUE;
1146
1147   if (node->left_child)
1148     {
1149       if (g_tree_node_pre_order (node->left, traverse_func, data))
1150         return TRUE;
1151     }
1152
1153   if (node->right_child)
1154     {
1155       if (g_tree_node_pre_order (node->right, traverse_func, data))
1156         return TRUE;
1157     }
1158
1159   return FALSE;
1160 }
1161
1162 static gint
1163 g_tree_node_in_order (GTreeNode     *node,
1164                       GTraverseFunc  traverse_func,
1165                       gpointer       data)
1166 {
1167   if (node->left_child)
1168     {
1169       if (g_tree_node_in_order (node->left, traverse_func, data))
1170         return TRUE;
1171     }
1172
1173   if ((*traverse_func) (node->key, node->value, data))
1174     return TRUE;
1175
1176   if (node->right_child)
1177     {
1178       if (g_tree_node_in_order (node->right, traverse_func, data))
1179         return TRUE;
1180     }
1181   
1182   return FALSE;
1183 }
1184
1185 static gint
1186 g_tree_node_post_order (GTreeNode     *node,
1187                         GTraverseFunc  traverse_func,
1188                         gpointer       data)
1189 {
1190   if (node->left_child)
1191     {
1192       if (g_tree_node_post_order (node->left, traverse_func, data))
1193         return TRUE;
1194     }
1195
1196   if (node->right_child)
1197     {
1198       if (g_tree_node_post_order (node->right, traverse_func, data))
1199         return TRUE;
1200     }
1201
1202   if ((*traverse_func) (node->key, node->value, data))
1203     return TRUE;
1204
1205   return FALSE;
1206 }
1207
1208 static gpointer
1209 g_tree_node_search (GTreeNode     *node,
1210                     GCompareFunc   search_func,
1211                     gconstpointer  data)
1212 {
1213   gint dir;
1214
1215   if (!node)
1216     return NULL;
1217
1218   while (1) 
1219     {
1220       dir = (* search_func) (node->key, data);
1221       if (dir == 0)
1222         return node->value;
1223       else if (dir < 0) 
1224         { 
1225           if (!node->left_child)
1226             return NULL;
1227
1228           node = node->left;
1229         }
1230       else
1231         {
1232           if (!node->right_child)
1233             return NULL;
1234           
1235           node = node->right;
1236         }
1237     }
1238 }
1239
1240 static GTreeNode*
1241 g_tree_node_rotate_left (GTreeNode *node)
1242 {
1243   GTreeNode *right;
1244   gint a_bal;
1245   gint b_bal;
1246
1247   right = node->right;
1248
1249   if (right->left_child)
1250     node->right = right->left;
1251   else
1252     {
1253       node->right_child = FALSE;
1254       node->right = right;
1255       right->left_child = TRUE;
1256     }
1257   right->left = node;
1258
1259   a_bal = node->balance;
1260   b_bal = right->balance;
1261
1262   if (b_bal <= 0)
1263     {
1264       if (a_bal >= 1)
1265         right->balance = b_bal - 1;
1266       else
1267         right->balance = a_bal + b_bal - 2;
1268       node->balance = a_bal - 1;
1269     }
1270   else
1271     {
1272       if (a_bal <= b_bal)
1273         right->balance = a_bal - 2;
1274       else
1275         right->balance = b_bal - 1;
1276       node->balance = a_bal - b_bal - 1;
1277     }
1278
1279   return right;
1280 }
1281
1282 static GTreeNode*
1283 g_tree_node_rotate_right (GTreeNode *node)
1284 {
1285   GTreeNode *left;
1286   gint a_bal;
1287   gint b_bal;
1288
1289   left = node->left;
1290
1291   if (left->right_child)
1292     node->left = left->right;
1293   else
1294     {
1295       node->left_child = FALSE;
1296       node->left = left;
1297       left->right_child = TRUE;
1298     }
1299   left->right = node;
1300
1301   a_bal = node->balance;
1302   b_bal = left->balance;
1303
1304   if (b_bal <= 0)
1305     {
1306       if (b_bal > a_bal)
1307         left->balance = b_bal + 1;
1308       else
1309         left->balance = a_bal + 2;
1310       node->balance = a_bal - b_bal + 1;
1311     }
1312   else
1313     {
1314       if (a_bal <= -1)
1315         left->balance = b_bal + 1;
1316       else
1317         left->balance = a_bal + b_bal + 2;
1318       node->balance = a_bal + 1;
1319     }
1320
1321   return left;
1322 }
1323
1324 #ifdef G_TREE_DEBUG
1325 static gint
1326 g_tree_node_height (GTreeNode *node)
1327 {
1328   gint left_height;
1329   gint right_height;
1330
1331   if (node)
1332     {
1333       left_height = 0;
1334       right_height = 0;
1335
1336       if (node->left_child)
1337         left_height = g_tree_node_height (node->left);
1338
1339       if (node->right_child)
1340         right_height = g_tree_node_height (node->right);
1341
1342       return MAX (left_height, right_height) + 1;
1343     }
1344
1345   return 0;
1346 }
1347
1348 static void
1349 g_tree_node_check (GTreeNode *node)
1350 {
1351   gint left_height;
1352   gint right_height;
1353   gint balance;
1354   GTreeNode *tmp;
1355
1356   if (node)
1357     {
1358       if (node->left_child)
1359         {
1360           tmp = g_tree_node_previous (node);
1361           g_assert (tmp->right == node);
1362         }
1363
1364       if (node->right_child)
1365         {
1366           tmp = g_tree_node_next (node);
1367           g_assert (tmp->left == node);
1368         }
1369
1370       left_height = 0;
1371       right_height = 0;
1372       
1373       if (node->left_child)
1374         left_height = g_tree_node_height (node->left);
1375       if (node->right_child)
1376         right_height = g_tree_node_height (node->right);
1377       
1378       balance = right_height - left_height;
1379       g_assert (balance == node->balance);
1380       
1381       if (node->left_child)
1382         g_tree_node_check (node->left);
1383       if (node->right_child)
1384         g_tree_node_check (node->right);
1385     }
1386 }
1387
1388 static void
1389 g_tree_node_dump (GTreeNode *node, 
1390                   gint       indent)
1391 {
1392   g_print ("%*s%c\n", indent, "", *(char *)node->key);
1393
1394   if (node->left_child)
1395     g_tree_node_dump (node->left, indent + 2);
1396   else if (node->left)
1397     g_print ("%*s<%c\n", indent + 2, "", *(char *)node->left->key);
1398
1399   if (node->right_child)
1400     g_tree_node_dump (node->right, indent + 2);
1401   else if (node->right)
1402     g_print ("%*s>%c\n", indent + 2, "", *(char *)node->right->key);
1403 }
1404
1405
1406 void
1407 g_tree_dump (GTree *tree)
1408 {
1409   if (tree->root)
1410     g_tree_node_dump (tree->root, 0);
1411 }
1412 #endif
1413
1414
1415 #define __G_TREE_C__
1416 #include "galiasdef.c"
1417