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