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