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