1 /* GLIB - Library of useful routines for C programming

     2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald

     3  * Portions copyright (c) 2006 Nokia Corporation.  All rights reserved.

     4  *

     5  * This library is free software; you can redistribute it and/or

     6  * modify it under the terms of the GNU Lesser General Public

     7  * License as published by the Free Software Foundation; either

     8  * version 2 of the License, or (at your option) any later version.

     9  *

    10  * This library is distributed in the hope that it will be useful,

    11  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    13  * Lesser General Public License for more details.

    14  *

    15  * You should have received a copy of the GNU Lesser General Public

    16  * License along with this library; if not, write to the

    17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,

    18  * Boston, MA 02111-1307, USA.

    19  */

    20 

    21 /*

    22  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS

    23  * file for a list of people on the GLib Team.  See the ChangeLog

    24  * files for a list of changes.  These files are distributed with

    25  * GLib at ftp://ftp.gtk.org/pub/gtk/. 

    26  */

    27 

    28 /* 

    29  * MT safe

    30  */

    31 

    32 #include "config.h"

    33 

    34 #include "glib.h"

    35 #include "galias.h"

    36 

    37 #undef G_TREE_DEBUG

    38 

    39 #define MAX_GTREE_HEIGHT 40

    40 

    41 typedef struct _GTreeNode  GTreeNode;

    42 

    43 struct _GTree

    44 {

    45   GTreeNode        *root;

    46   GCompareDataFunc  key_compare;

    47   GDestroyNotify    key_destroy_func;

    48   GDestroyNotify    value_destroy_func;

    49   gpointer          key_compare_data;

    50   guint             nnodes;

    51 };

    52 

    53 struct _GTreeNode

    54 {

    55   gpointer   key;         /* key for this node */

    56   gpointer   value;       /* value stored at this node */

    57   GTreeNode *left;        /* left subtree */

    58   GTreeNode *right;       /* right subtree */

    59   gint8      balance;     /* height (left) - height (right) */

    60   guint8     left_child;  

    61   guint8     right_child;

    62 };

    63 

    64 

    65 static GTreeNode* g_tree_node_new                   (gpointer       key,

    66 						     gpointer       value);

    67 static void       g_tree_insert_internal            (GTree         *tree,

    68 						     gpointer       key,

    69 						     gpointer       value,

    70 						     gboolean       replace);

    71 static gboolean   g_tree_remove_internal            (GTree         *tree,

    72 						     gconstpointer  key,

    73 						     gboolean       steal);

    74 static GTreeNode* g_tree_node_balance               (GTreeNode     *node);

    75 static GTreeNode *g_tree_find_node                  (GTree         *tree,

    76 						     gconstpointer  key);

    77 static gint       g_tree_node_pre_order             (GTreeNode     *node,

    78 						     GTraverseFunc  traverse_func,

    79 						     gpointer       data);

    80 static gint       g_tree_node_in_order              (GTreeNode     *node,

    81 						     GTraverseFunc  traverse_func,

    82 						     gpointer       data);

    83 static gint       g_tree_node_post_order            (GTreeNode     *node,

    84 						     GTraverseFunc  traverse_func,

    85 						     gpointer       data);

    86 static gpointer   g_tree_node_search                (GTreeNode     *node,

    87 						     GCompareFunc   search_func,

    88 						     gconstpointer  data);

    89 static GTreeNode* g_tree_node_rotate_left           (GTreeNode     *node);

    90 static GTreeNode* g_tree_node_rotate_right          (GTreeNode     *node);

    91 #ifdef G_TREE_DEBUG

    92 static void       g_tree_node_check                 (GTreeNode     *node);

    93 #endif

    94 

    95 

    96 static GTreeNode*

    97 g_tree_node_new (gpointer key,

    98 		 gpointer value)

    99 {

   100   GTreeNode *node = g_slice_new (GTreeNode);

   101   

   102   node->balance = 0;

   103   node->left = NULL;

   104   node->right = NULL;

   105   node->left_child = FALSE;

   106   node->right_child = FALSE;

   107   node->key = key;

   108   node->value = value;

   109 

   110   return node;

   111 }

   112 

   113 /**

   114  * g_tree_new:

   115  * @key_compare_func: the function used to order the nodes in the #GTree.

   116  *   It should return values similar to the standard strcmp() function -

   117  *   0 if the two arguments are equal, a negative value if the first argument 

   118  *   comes before the second, or a positive value if the first argument comes 

   119  *   after the second.

   120  * 

   121  * Creates a new #GTree.

   122  * 

   123  * Return value: a new #GTree.

   124  **/

   125 EXPORT_C GTree*

   126 g_tree_new (GCompareFunc key_compare_func)

   127 {

   128   g_return_val_if_fail (key_compare_func != NULL, NULL);

   129 

   130   return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,

   131                           NULL, NULL);

   132 }

   133 

   134 /**

   135  * g_tree_new_with_data:

   136  * @key_compare_func: qsort()-style comparison function.

   137  * @key_compare_data: data to pass to comparison function.

   138  * 

   139  * Creates a new #GTree with a comparison function that accepts user data.

   140  * See g_tree_new() for more details.

   141  * 

   142  * Return value: a new #GTree.

   143  **/

   144 EXPORT_C GTree*

   145 g_tree_new_with_data (GCompareDataFunc key_compare_func,

   146  		      gpointer         key_compare_data)

   147 {

   148   g_return_val_if_fail (key_compare_func != NULL, NULL);

   149   

   150   return g_tree_new_full (key_compare_func, key_compare_data, 

   151  			  NULL, NULL);

   152 }

   153 

   154 /**

   155  * g_tree_new_full:

   156  * @key_compare_func: qsort()-style comparison function.

   157  * @key_compare_data: data to pass to comparison function.

   158  * @key_destroy_func: a function to free the memory allocated for the key 

   159  *   used when removing the entry from the #GTree or %NULL if you don't

   160  *   want to supply such a function.

   161  * @value_destroy_func: a function to free the memory allocated for the 

   162  *   value used when removing the entry from the #GTree or %NULL if you 

   163  *   don't want to supply such a function.

   164  * 

   165  * Creates a new #GTree like g_tree_new() and allows to specify functions 

   166  * to free the memory allocated for the key and value that get called when 

   167  * removing the entry from the #GTree.

   168  * 

   169  * Return value: a new #GTree.

   170  **/

   171 EXPORT_C GTree*	 

   172 g_tree_new_full (GCompareDataFunc key_compare_func,

   173  		 gpointer         key_compare_data, 		 

   174                  GDestroyNotify   key_destroy_func,

   175  		 GDestroyNotify   value_destroy_func)

   176 {

   177   GTree *tree;

   178   

   179   g_return_val_if_fail (key_compare_func != NULL, NULL);

   180   tree = g_new (GTree, 1);

   181   tree->root               = NULL;

   182   tree->key_compare        = key_compare_func;

   183   tree->key_destroy_func   = key_destroy_func;

   184   tree->value_destroy_func = value_destroy_func;

   185   tree->key_compare_data   = key_compare_data;

   186   tree->nnodes             = 0;

   187   

   188   return tree;

   189 }

   190 

   191 static inline GTreeNode *

   192 g_tree_first_node (GTree *tree)

   193 {

   194   GTreeNode *tmp;

   195 

   196   if (!tree->root)

   197     return NULL;

   198 

   199   tmp = tree->root;

   200 

   201   while (tmp->left_child)

   202     tmp = tmp->left;

   203 

   204   return tmp;

   205 } 

   206 

   207 static inline GTreeNode *

   208 g_tree_node_previous (GTreeNode *node)

   209 {

   210   GTreeNode *tmp;

   211 

   212   tmp = node->left;

   213 

   214   if (node->left_child)

   215     while (tmp->right_child)

   216       tmp = tmp->right;

   217 

   218   return tmp;

   219 }

   220 		  

   221 static inline GTreeNode *

   222 g_tree_node_next (GTreeNode *node)

   223 {

   224   GTreeNode *tmp;

   225 

   226   tmp = node->right;

   227 

   228   if (node->right_child)

   229     while (tmp->left_child)

   230       tmp = tmp->left;

   231 

   232   return tmp;

   233 }

   234 		  

   235 /**

   236  * g_tree_destroy:

   237  * @tree: a #GTree.

   238  * 

   239  * Destroys the #GTree. If keys and/or values are dynamically allocated, you 

   240  * should either free them first or create the #GTree using g_tree_new_full().

   241  * In the latter case the destroy functions you supplied will be called on 

   242  * all keys and values before destroying the #GTree.

   243  **/

   244 EXPORT_C void

   245 g_tree_destroy (GTree *tree)

   246 {

   247   GTreeNode *node;

   248   GTreeNode *next;

   249 

   250   g_return_if_fail (tree != NULL);

   251 

   252   node = g_tree_first_node (tree);

   253   

   254   while (node)

   255     {

   256       next = g_tree_node_next (node);

   257 

   258       if (tree->key_destroy_func)

   259 	tree->key_destroy_func (node->key);

   260       if (tree->value_destroy_func)

   261 	tree->value_destroy_func (node->value);

   262       g_slice_free (GTreeNode, node);

   263 

   264       node = next;

   265     }

   266 

   267   g_free (tree);

   268 }

   269 

   270 /**

   271  * g_tree_insert:

   272  * @tree: a #GTree.

   273  * @key: the key to insert.

   274  * @value: the value corresponding to the key.

   275  * 

   276  * Inserts a key/value pair into a #GTree. If the given key already exists 

   277  * in the #GTree its corresponding value is set to the new value. If you 

   278  * supplied a value_destroy_func when creating the #GTree, the old value is 

   279  * freed using that function. If you supplied a @key_destroy_func when 

   280  * creating the #GTree, the passed key is freed using that function.

   281  *

   282  * The tree is automatically 'balanced' as new key/value pairs are added,

   283  * so that the distance from the root to every leaf is as small as possible.

   284  **/

   285 EXPORT_C void

   286 g_tree_insert (GTree    *tree,

   287 	       gpointer  key,

   288 	       gpointer  value)

   289 {

   290   g_return_if_fail (tree != NULL);

   291 

   292   g_tree_insert_internal (tree, key, value, FALSE);

   293 

   294 #ifdef G_TREE_DEBUG

   295   g_tree_node_check (tree->root);

   296 #endif

   297 }

   298 

   299 /**

   300  * g_tree_replace:

   301  * @tree: a #GTree.

   302  * @key: the key to insert.

   303  * @value: the value corresponding to the key.

   304  * 

   305  * Inserts a new key and value into a #GTree similar to g_tree_insert(). 

   306  * The difference is that if the key already exists in the #GTree, it gets 

   307  * replaced by the new key. If you supplied a @value_destroy_func when 

   308  * creating the #GTree, the old value is freed using that function. If you 

   309  * supplied a @key_destroy_func when creating the #GTree, the old key is 

   310  * freed using that function. 

   311  *

   312  * The tree is automatically 'balanced' as new key/value pairs are added,

   313  * so that the distance from the root to every leaf is as small as possible.

   314  **/

   315 EXPORT_C void

   316 g_tree_replace (GTree    *tree,

   317 		gpointer  key,

   318 		gpointer  value)

   319 {

   320   g_return_if_fail (tree != NULL);

   321 

   322   g_tree_insert_internal (tree, key, value, TRUE);

   323 

   324 #ifdef G_TREE_DEBUG

   325   g_tree_node_check (tree->root);

   326 #endif

   327 }

   328 

   329 /* internal insert routine */

   330 static void

   331 g_tree_insert_internal (GTree    *tree,

   332                         gpointer  key,

   333                         gpointer  value,

   334                         gboolean  replace)

   335 {

   336   GTreeNode *node;

   337   GTreeNode *path[MAX_GTREE_HEIGHT];

   338   int idx;

   339 

   340   g_return_if_fail (tree != NULL);

   341 

   342   if (!tree->root)

   343     {

   344       tree->root = g_tree_node_new (key, value);

   345       tree->nnodes++;

   346       return;

   347     }

   348 

   349   idx = 0;

   350   path[idx++] = NULL;

   351   node = tree->root;

   352 

   353   while (1)

   354     {

   355       int cmp = tree->key_compare (key, node->key, tree->key_compare_data);

   356       

   357       if (cmp == 0)

   358         {

   359           if (tree->value_destroy_func)

   360             tree->value_destroy_func (node->value);

   361 

   362           node->value = value;

   363 

   364           if (replace)

   365             {

   366               if (tree->key_destroy_func)

   367                 tree->key_destroy_func (node->key);

   368 

   369               node->key = key;

   370             }

   371           else

   372             {

   373               /* free the passed key */

   374               if (tree->key_destroy_func)

   375                 tree->key_destroy_func (key);

   376             }

   377 

   378           return;

   379         }

   380       else if (cmp < 0)

   381         {

   382           if (node->left_child)

   383             {

   384               path[idx++] = node;

   385               node = node->left;

   386             }

   387           else

   388             {

   389               GTreeNode *child = g_tree_node_new (key, value);

   390 

   391               child->left = node->left;

   392               child->right = node;

   393               node->left = child;

   394               node->left_child = TRUE;

   395               node->balance -= 1;

   396 

   397 	      tree->nnodes++;

   398 

   399               break;

   400             }

   401         }

   402       else

   403         {

   404           if (node->right_child)

   405             {

   406               path[idx++] = node;

   407               node = node->right;

   408             }

   409           else

   410             {

   411               GTreeNode *child = g_tree_node_new (key, value);

   412 

   413               child->right = node->right;

   414               child->left = node;

   415               node->right = child;

   416               node->right_child = TRUE;

   417               node->balance += 1;

   418 

   419 	      tree->nnodes++;

   420 

   421               break;

   422             }

   423         }

   424     }

   425 

   426   /* restore balance. This is the goodness of a non-recursive

   427      implementation, when we are done with balancing we 'break'

   428      the loop and we are done. */

   429   while (1)

   430     {

   431       GTreeNode *bparent = path[--idx];

   432       gboolean left_node = (bparent && node == bparent->left);

   433       g_assert (!bparent || bparent->left == node || bparent->right == node);

   434 

   435       if (node->balance < -1 || node->balance > 1)

   436         {

   437           node = g_tree_node_balance (node);

   438           if (bparent == NULL)

   439             tree->root = node;

   440           else if (left_node)

   441             bparent->left = node;

   442           else

   443             bparent->right = node;

   444         }

   445 

   446       if (node->balance == 0 || bparent == NULL)

   447         break;

   448       

   449       if (left_node)

   450         bparent->balance -= 1;

   451       else

   452         bparent->balance += 1;

   453 

   454       node = bparent;

   455     }

   456 }

   457 

   458 /**

   459  * g_tree_remove:

   460  * @tree: a #GTree.

   461  * @key: the key to remove.

   462  * 

   463  * Removes a key/value pair from a #GTree.

   464  *

   465  * If the #GTree was created using g_tree_new_full(), the key and value 

   466  * are freed using the supplied destroy functions, otherwise you have to 

   467  * make sure that any dynamically allocated values are freed yourself.

   468  * If the key does not exist in the #GTree, the function does nothing.

   469  *

   470  * Returns: %TRUE if the key was found (prior to 2.8, this function returned 

   471  *   nothing)

   472  **/

   473 EXPORT_C gboolean

   474 g_tree_remove (GTree         *tree,

   475 	       gconstpointer  key)

   476 {

   477   gboolean removed;

   478 

   479   g_return_val_if_fail (tree != NULL, FALSE);

   480 

   481   removed = g_tree_remove_internal (tree, key, FALSE);

   482 

   483 #ifdef G_TREE_DEBUG

   484   g_tree_node_check (tree->root);

   485 #endif

   486 

   487   return removed;

   488 }

   489 

   490 /**

   491  * g_tree_steal:

   492  * @tree: a #GTree.

   493  * @key: the key to remove.

   494  * 

   495  * Removes a key and its associated value from a #GTree without calling 

   496  * the key and value destroy functions.

   497  *

   498  * If the key does not exist in the #GTree, the function does nothing.

   499  *

   500  * Returns: %TRUE if the key was found (prior to 2.8, this function returned 

   501  *    nothing)

   502  **/

   503 EXPORT_C gboolean

   504 g_tree_steal (GTree         *tree,

   505               gconstpointer  key)

   506 {

   507   gboolean removed;

   508 

   509   g_return_val_if_fail (tree != NULL, FALSE);

   510 

   511   removed = g_tree_remove_internal (tree, key, TRUE);

   512 

   513 #ifdef G_TREE_DEBUG

   514   g_tree_node_check (tree->root);

   515 #endif

   516 

   517   return removed;

   518 }

   519 

   520 /* internal remove routine */

   521 static gboolean

   522 g_tree_remove_internal (GTree         *tree,

   523                         gconstpointer  key,

   524                         gboolean       steal)

   525 {

   526   GTreeNode *node, *parent, *balance;

   527   GTreeNode *path[MAX_GTREE_HEIGHT];

   528   int idx;

   529   gboolean left_node;

   530 

   531   g_return_val_if_fail (tree != NULL, FALSE);

   532 

   533   if (!tree->root)

   534     return FALSE;

   535 

   536   idx = 0;

   537   path[idx++] = NULL;

   538   node = tree->root;

   539 

   540   while (1)

   541     {

   542       int cmp = tree->key_compare (key, node->key, tree->key_compare_data);

   543       

   544       if (cmp == 0)

   545         break;

   546       else if (cmp < 0)

   547         {

   548           if (!node->left_child)

   549             return FALSE;

   550 	  

   551 	  path[idx++] = node;

   552 	  node = node->left;

   553         }

   554       else

   555         {

   556           if (!node->right_child)

   557             return FALSE;

   558 	  

   559 	  path[idx++] = node;

   560 	  node = node->right;

   561         }

   562     }

   563 

   564   /* the following code is almost equal to g_tree_remove_node,

   565      except that we do not have to call g_tree_node_parent. */

   566   balance = parent = path[--idx];

   567   g_assert (!parent || parent->left == node || parent->right == node);

   568   left_node = (parent && node == parent->left);

   569 

   570   if (!node->left_child)

   571     {

   572       if (!node->right_child)

   573         {

   574           if (!parent)

   575             tree->root = NULL;

   576           else if (left_node)

   577             {

   578               parent->left_child = FALSE;

   579               parent->left = node->left;

   580               parent->balance += 1;

   581             }

   582           else

   583             {

   584               parent->right_child = FALSE;

   585               parent->right = node->right;

   586               parent->balance -= 1;

   587             }

   588         }

   589       else /* node has a right child */

   590         {

   591           GTreeNode *tmp = g_tree_node_next (node);

   592 	  tmp->left = node->left;

   593 

   594           if (!parent)

   595             tree->root = node->right;

   596           else if (left_node)

   597             {

   598               parent->left = node->right;

   599               parent->balance += 1;

   600             }

   601           else

   602             {

   603               parent->right = node->right;

   604               parent->balance -= 1;

   605             }

   606         }

   607     }

   608   else /* node has a left child */

   609     {

   610       if (!node->right_child)

   611         {

   612           GTreeNode *tmp = g_tree_node_previous (node);

   613           tmp->right = node->right;

   614 	  

   615           if (parent == NULL)

   616             tree->root = node->left;

   617           else if (left_node)

   618             {

   619               parent->left = node->left;

   620               parent->balance += 1;

   621             }

   622           else

   623             {

   624               parent->right = node->left;

   625               parent->balance -= 1;

   626             }

   627         }

   628       else /* node has a both children (pant, pant!) */

   629         {

   630 	  GTreeNode *prev = node->left;

   631 	  GTreeNode *next = node->right;

   632 	  GTreeNode *nextp = node;

   633 	  int old_idx = idx + 1;

   634 	  idx++;

   635 	  

   636 	  /* path[idx] == parent */

   637 	  /* find the immediately next node (and its parent) */

   638 	  while (next->left_child)

   639             {

   640 	      path[++idx] = nextp = next;

   641 	      next = next->left;

   642             }

   643  	  

   644 	  path[old_idx] = next;

   645 	  balance = path[idx];

   646 	  

   647 	  /* remove 'next' from the tree */

   648 	  if (nextp != node)

   649 	    {

   650 	      if (next->right_child)

   651 		nextp->left = next->right;

   652 	      else

   653 		nextp->left_child = FALSE;

   654 	      nextp->balance += 1;

   655 	      

   656 	      next->right_child = TRUE;

   657 	      next->right = node->right;

   658 	    }

   659 	  else

   660 	    node->balance -= 1;

   661 	    

   662 	  /* set the prev to point to the right place */

   663 	  while (prev->right_child)

   664 	    prev = prev->right;

   665 	  prev->right = next;

   666 	    

   667 	  /* prepare 'next' to replace 'node' */

   668 	  next->left_child = TRUE;

   669 	  next->left = node->left;

   670 	  next->balance = node->balance;

   671 	  

   672 	  if (!parent)

   673 	    tree->root = next;

   674 	  else if (left_node)

   675 	    parent->left = next;

   676 	  else

   677 	    parent->right = next;

   678         }

   679     }

   680   

   681   /* restore balance */

   682   if (balance)

   683     while (1)

   684       {

   685 	GTreeNode *bparent = path[--idx];

   686 	g_assert (!bparent || bparent->left == balance || bparent->right == balance);

   687 	left_node = (bparent && balance == bparent->left);

   688 			      

   689 	if(balance->balance < -1 || balance->balance > 1)

   690 	  {

   691 	    balance = g_tree_node_balance (balance);

   692 	    if (!bparent)

   693 	      tree->root = balance;

   694 	    else if (left_node)

   695 	      bparent->left = balance;

   696 	    else

   697 	      bparent->right = balance;

   698 	  }

   699 	

   700 	if (balance->balance != 0 || !bparent)

   701 	  break;

   702 	

   703 	if (left_node)

   704 	  bparent->balance += 1;

   705 	else

   706 	  bparent->balance -= 1;

   707 	

   708 	balance = bparent;

   709       }

   710   

   711   if (!steal)

   712     {

   713       if (tree->key_destroy_func)

   714         tree->key_destroy_func (node->key);

   715       if (tree->value_destroy_func)

   716         tree->value_destroy_func (node->value);

   717     }

   718 

   719   g_slice_free (GTreeNode, node);

   720 

   721   tree->nnodes--;

   722 

   723   return TRUE;

   724 }

   725 

   726 /**

   727  * g_tree_lookup:

   728  * @tree: a #GTree.

   729  * @key: the key to look up.

   730  * 

   731  * Gets the value corresponding to the given key. Since a #GTree is 

   732  * automatically balanced as key/value pairs are added, key lookup is very 

   733  * fast.

   734  *

   735  * Return value: the value corresponding to the key, or %NULL if the key was

   736  * not found.

   737  **/

   738 EXPORT_C gpointer

   739 g_tree_lookup (GTree         *tree,

   740 	       gconstpointer  key)

   741 {

   742   GTreeNode *node;

   743 

   744   g_return_val_if_fail (tree != NULL, NULL);

   745 

   746   node = g_tree_find_node (tree, key);

   747   

   748   return node ? node->value : NULL;

   749 }

   750 

   751 /**

   752  * g_tree_lookup_extended:

   753  * @tree: a #GTree.

   754  * @lookup_key: the key to look up.

   755  * @orig_key: returns the original key.

   756  * @value: returns the value associated with the key.

   757  * 

   758  * Looks up a key in the #GTree, returning the original key and the

   759  * associated value and a #gboolean which is %TRUE if the key was found. This 

   760  * is useful if you need to free the memory allocated for the original key, 

   761  * for example before calling g_tree_remove().

   762  * 

   763  * Return value: %TRUE if the key was found in the #GTree.

   764  **/

   765 EXPORT_C gboolean

   766 g_tree_lookup_extended (GTree         *tree,

   767                         gconstpointer  lookup_key,

   768                         gpointer      *orig_key,

   769                         gpointer      *value)

   770 {

   771   GTreeNode *node;

   772   

   773   g_return_val_if_fail (tree != NULL, FALSE);

   774   

   775   node = g_tree_find_node (tree, lookup_key);

   776   

   777   if (node)

   778     {

   779       if (orig_key)

   780         *orig_key = node->key;

   781       if (value)

   782         *value = node->value;

   783       return TRUE;

   784     }

   785   else

   786     return FALSE;

   787 }

   788 

   789 /**

   790  * g_tree_foreach:

   791  * @tree: a #GTree.

   792  * @func: the function to call for each node visited. If this function

   793  *   returns %TRUE, the traversal is stopped.

   794  * @user_data: user data to pass to the function.

   795  * 

   796  * Calls the given function for each of the key/value pairs in the #GTree.

   797  * The function is passed the key and value of each pair, and the given

   798  * @data parameter. The tree is traversed in sorted order.

   799  *

   800  * The tree may not be modified while iterating over it (you can't 

   801  * add/remove items). To remove all items matching a predicate, you need 

   802  * to add each item to a list in your #GTraverseFunc as you walk over 

   803  * the tree, then walk the list and remove each item.

   804  **/

   805 EXPORT_C void

   806 g_tree_foreach (GTree         *tree,

   807                 GTraverseFunc  func,

   808                 gpointer       user_data)

   809 {

   810   GTreeNode *node;

   811 

   812   g_return_if_fail (tree != NULL);

   813   

   814   if (!tree->root)

   815     return;

   816 

   817   node = g_tree_first_node (tree);

   818   

   819   while (node)

   820     {

   821       if ((*func) (node->key, node->value, user_data))

   822 	break;

   823       

   824       node = g_tree_node_next (node);

   825     }

   826 }

   827 

   828 /**

   829  * g_tree_traverse:

   830  * @tree: a #GTree.

   831  * @traverse_func: the function to call for each node visited. If this 

   832  *   function returns %TRUE, the traversal is stopped.

   833  * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,

   834  *   %G_PRE_ORDER and %G_POST_ORDER.

   835  * @user_data: user data to pass to the function.

   836  * 

   837  * Calls the given function for each node in the #GTree. 

   838  *

   839  * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary. If you 

   840  * just want to visit all nodes in sorted order, use g_tree_foreach() 

   841  * instead. If you really need to visit nodes in a different order, consider

   842  * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.

   843  **/

   844 EXPORT_C void

   845 g_tree_traverse (GTree         *tree,

   846 		 GTraverseFunc  traverse_func,

   847 		 GTraverseType  traverse_type,

   848 		 gpointer       user_data)

   849 {

   850   g_return_if_fail (tree != NULL);

   851 

   852   if (!tree->root)

   853     return;

   854 

   855   switch (traverse_type)

   856     {

   857     case G_PRE_ORDER:

   858       g_tree_node_pre_order (tree->root, traverse_func, user_data);

   859       break;

   860 

   861     case G_IN_ORDER:

   862       g_tree_node_in_order (tree->root, traverse_func, user_data);

   863       break;

   864 

   865     case G_POST_ORDER:

   866       g_tree_node_post_order (tree->root, traverse_func, user_data);

   867       break;

   868     

   869     case G_LEVEL_ORDER:

   870       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");

   871       break;

   872     }

   873 }

   874 

   875 /**

   876  * g_tree_search:

   877  * @tree: a #GTree.

   878  * @search_func: a function used to search the #GTree. 

   879  * @user_data: the data passed as the second argument to the @search_func 

   880  * function.

   881  * 

   882  * Searches a #GTree using @search_func.

   883  *

   884  * The @search_func is called with a pointer to the key of a key/value pair in 

   885  * the tree, and the passed in @user_data. If @search_func returns 0 for a 

   886  * key/value pair, then g_tree_search_func() will return the value of that 

   887  * pair. If @search_func returns -1,  searching will proceed among the 

   888  * key/value pairs that have a smaller key; if @search_func returns 1, 

   889  * searching will proceed among the key/value pairs that have a larger key.

   890  *

   891  * Return value: the value corresponding to the found key, or %NULL if the key 

   892  * was not found.

   893  **/

   894 EXPORT_C gpointer

   895 g_tree_search (GTree         *tree,

   896 	       GCompareFunc   search_func,

   897 	       gconstpointer  user_data)

   898 {

   899   g_return_val_if_fail (tree != NULL, NULL);

   900 

   901   if (tree->root)

   902     return g_tree_node_search (tree->root, search_func, user_data);

   903   else

   904     return NULL;

   905 }

   906 

   907 /**

   908  * g_tree_height:

   909  * @tree: a #GTree.

   910  * 

   911  * Gets the height of a #GTree.

   912  *

   913  * If the #GTree contains no nodes, the height is 0.

   914  * If the #GTree contains only one root node the height is 1.

   915  * If the root node has children the height is 2, etc.

   916  * 

   917  * Return value: the height of the #GTree.

   918  **/

   919 EXPORT_C gint

   920 g_tree_height (GTree *tree)

   921 {

   922   GTreeNode *node;

   923   gint height;

   924 

   925   g_return_val_if_fail (tree != NULL, 0);

   926 

   927   if (!tree->root)

   928     return 0;

   929 

   930   height = 0;

   931   node = tree->root;

   932 

   933   while (1)

   934     {

   935       height += 1 + MAX(node->balance, 0);

   936 

   937       if (!node->left_child)

   938 	return height;

   939       

   940       node = node->left;

   941     }

   942 }

   943 

   944 /**

   945  * g_tree_nnodes:

   946  * @tree: a #GTree.

   947  * 

   948  * Gets the number of nodes in a #GTree.

   949  * 

   950  * Return value: the number of nodes in the #GTree.

   951  **/

   952 EXPORT_C gint

   953 g_tree_nnodes (GTree *tree)

   954 {

   955   g_return_val_if_fail (tree != NULL, 0);

   956 

   957   return tree->nnodes;

   958 }

   959 

   960 static GTreeNode*

   961 g_tree_node_balance (GTreeNode *node)

   962 {

   963   if (node->balance < -1)

   964     {

   965       if (node->left->balance > 0)

   966 	node->left = g_tree_node_rotate_left (node->left);

   967       node = g_tree_node_rotate_right (node);

   968     }

   969   else if (node->balance > 1)

   970     {

   971       if (node->right->balance < 0)

   972 	node->right = g_tree_node_rotate_right (node->right);

   973       node = g_tree_node_rotate_left (node);

   974     }

   975 

   976   return node;

   977 }

   978 

   979 static GTreeNode *

   980 g_tree_find_node (GTree        *tree,

   981 		  gconstpointer key)

   982 {

   983   GTreeNode *node;

   984   gint cmp;

   985 

   986   node = tree->root;

   987   if (!node)

   988     return NULL;

   989 

   990   while (1)

   991     {

   992       cmp = tree->key_compare (key, node->key, tree->key_compare_data);

   993       if (cmp == 0)

   994 	return node;

   995       else if (cmp < 0)

   996 	{

   997 	  if (!node->left_child)

   998 	    return NULL;

   999 

  1000 	  node = node->left;

  1001 	}

  1002       else

  1003 	{

  1004 	  if (!node->right_child)

  1005 	    return NULL;

  1006 

  1007 	  node = node->right;

  1008 	}

  1009     }

  1010 }

  1011 

  1012 static gint

  1013 g_tree_node_pre_order (GTreeNode     *node,

  1014 		       GTraverseFunc  traverse_func,

  1015 		       gpointer       data)

  1016 {

  1017   if ((*traverse_func) (node->key, node->value, data))

  1018     return TRUE;

  1019 

  1020   if (node->left_child)

  1021     {

  1022       if (g_tree_node_pre_order (node->left, traverse_func, data))

  1023 	return TRUE;

  1024     }

  1025 

  1026   if (node->right_child)

  1027     {

  1028       if (g_tree_node_pre_order (node->right, traverse_func, data))

  1029 	return TRUE;

  1030     }

  1031 

  1032   return FALSE;

  1033 }

  1034 

  1035 static gint

  1036 g_tree_node_in_order (GTreeNode     *node,

  1037 		      GTraverseFunc  traverse_func,

  1038 		      gpointer       data)

  1039 {

  1040   if (node->left_child)

  1041     {

  1042       if (g_tree_node_in_order (node->left, traverse_func, data))

  1043 	return TRUE;

  1044     }

  1045 

  1046   if ((*traverse_func) (node->key, node->value, data))

  1047     return TRUE;

  1048 

  1049   if (node->right_child)

  1050     {

  1051       if (g_tree_node_in_order (node->right, traverse_func, data))

  1052 	return TRUE;

  1053     }

  1054   

  1055   return FALSE;

  1056 }

  1057 

  1058 static gint

  1059 g_tree_node_post_order (GTreeNode     *node,

  1060 			GTraverseFunc  traverse_func,

  1061 			gpointer       data)

  1062 {

  1063   if (node->left_child)

  1064     {

  1065       if (g_tree_node_post_order (node->left, traverse_func, data))

  1066 	return TRUE;

  1067     }

  1068 

  1069   if (node->right_child)

  1070     {

  1071       if (g_tree_node_post_order (node->right, traverse_func, data))

  1072 	return TRUE;

  1073     }

  1074 

  1075   if ((*traverse_func) (node->key, node->value, data))

  1076     return TRUE;

  1077 

  1078   return FALSE;

  1079 }

  1080 

  1081 static gpointer

  1082 g_tree_node_search (GTreeNode     *node,

  1083 		    GCompareFunc   search_func,

  1084 		    gconstpointer  data)

  1085 {

  1086   gint dir;

  1087 

  1088   if (!node)

  1089     return NULL;

  1090 

  1091   while (1) 

  1092     {

  1093       dir = (* search_func) (node->key, data);

  1094       if (dir == 0)

  1095 	return node->value;

  1096       else if (dir < 0) 

  1097 	{ 

  1098 	  if (!node->left_child)

  1099 	    return NULL;

  1100 

  1101 	  node = node->left;

  1102 	}

  1103       else

  1104 	{

  1105 	  if (!node->right_child)

  1106 	    return NULL;

  1107 	  

  1108 	  node = node->right;

  1109 	}

  1110     }

  1111 }

  1112 

  1113 static GTreeNode*

  1114 g_tree_node_rotate_left (GTreeNode *node)

  1115 {

  1116   GTreeNode *right;

  1117   gint a_bal;

  1118   gint b_bal;

  1119 

  1120   right = node->right;

  1121 

  1122   if (right->left_child)

  1123     node->right = right->left;

  1124   else

  1125     {

  1126       node->right_child = FALSE;

  1127       node->right = right;

  1128       right->left_child = TRUE;

  1129     }

  1130   right->left = node;

  1131 

  1132   a_bal = node->balance;

  1133   b_bal = right->balance;

  1134