glib/gtree.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 /*
  21  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  22  * file for a list of people on the GLib Team.  See the ChangeLog
  23  * files for a list of changes.  These files are distributed with
  24  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  25  */
  26
  27 /*
  28  * MT safe
  29  */
  30
  31 #include "config.h"
  32
  33 #include "glib.h"
  34 #include "galias.h"
  35
  36
  37 typedef struct _GTreeNode  GTreeNode;
  38
  39 struct _GTree
  40 {
  41   GTreeNode *root;
  42   GCompareDataFunc key_compare;
  43   GDestroyNotify   key_destroy_func;
  44   GDestroyNotify   value_destroy_func;
  45   gpointer         key_compare_data;
  46 };
  47
  48 struct _GTreeNode
  49 {
  50   gint balance;      /* height (left) - height (right) */
  51   GTreeNode *left;   /* left subtree */
  52   GTreeNode *right;  /* right subtree */
  53   gpointer key;      /* key for this node */
  54   gpointer value;    /* value stored at this node */
  55 };
  56
  57
  58 static GTreeNode* g_tree_node_new                   (gpointer          key,
  59                                                      gpointer          value);
  60 static void       g_tree_node_destroy               (GTreeNode        *node,
  61                                                      GDestroyNotify    key_destroy_func,
  62                                                      GDestroyNotify    value_destroy_func);
  63 static GTreeNode* g_tree_node_insert                (GTree            *tree,
  64                                                      GTreeNode        *node,
  65                                                      gpointer          key,
  66                                                      gpointer          value,
  67                                                      gboolean          replace,
  68                                                      gboolean         *inserted);
  69 static GTreeNode* g_tree_node_remove                (GTree            *tree,
  70                                                      GTreeNode        *node,
  71                                                      gconstpointer     key,
  72                                                      gboolean          notify,
  73                                                      gboolean         *removed);
  74 static GTreeNode* g_tree_node_balance               (GTreeNode        *node);
  75 static GTreeNode* g_tree_node_remove_leftmost       (GTreeNode        *node,
  76                                                      GTreeNode       **leftmost);
  77 static GTreeNode* g_tree_node_restore_left_balance  (GTreeNode        *node,
  78                                                      gint              old_balance);
  79 static GTreeNode* g_tree_node_restore_right_balance (GTreeNode        *node,
  80                                                      gint              old_balance);
  81 static GTreeNode* g_tree_node_lookup                (GTreeNode        *node,
  82                                                      GCompareDataFunc  compare,
  83                                                      gpointer          comp_data,
  84                                                      gconstpointer     key);
  85 static gint       g_tree_node_count                 (GTreeNode        *node);
  86 static gint       g_tree_node_pre_order             (GTreeNode        *node,
  87                                                      GTraverseFunc     traverse_func,
  88                                                      gpointer          data);
  89 static gint       g_tree_node_in_order              (GTreeNode        *node,
  90                                                      GTraverseFunc     traverse_func,
  91                                                      gpointer          data);
  92 static gint       g_tree_node_post_order            (GTreeNode        *node,
  93                                                      GTraverseFunc     traverse_func,
  94                                                      gpointer          data);
  95 static gpointer   g_tree_node_search                (GTreeNode        *node,
  96                                                      GCompareFunc      search_func,
  97                                                      gconstpointer     data);
  98 static gint       g_tree_node_height                (GTreeNode        *node);
  99 static GTreeNode* g_tree_node_rotate_left           (GTreeNode        *node);
 100 static GTreeNode* g_tree_node_rotate_right          (GTreeNode        *node);
 101 static void       g_tree_node_check                 (GTreeNode        *node);
 102
 103
 104 static GTreeNode*
 105 g_tree_node_new (gpointer key,
 106                  gpointer value)
 107 {
 108   GTreeNode *node = g_slice_new (GTreeNode);
 109
 110   node->balance = 0;
 111   node->left = NULL;
 112   node->right = NULL;
 113   node->key = key;
 114   node->value = value;
 115
 116   return node;
 117 }
 118
 119 static void
 120 g_tree_node_destroy (GTreeNode      *node,
 121                      GDestroyNotify  key_destroy_func,
 122                      GDestroyNotify  value_destroy_func)
 123 {
 124   if (node)
 125     {
 126       g_tree_node_destroy (node->right,
 127                            key_destroy_func, value_destroy_func);
 128       g_tree_node_destroy (node->left,
 129                            key_destroy_func, value_destroy_func);
 130
 131       if (key_destroy_func)
 132         key_destroy_func (node->key);
 133       if (value_destroy_func)
 134         value_destroy_func (node->value);
 135
 136 #ifdef ENABLE_GC_FRIENDLY
 137       node->left = NULL;
 138       node->key = NULL;
 139       node->value = NULL;
 140 #endif /* ENABLE_GC_FRIENDLY */
 141
 142       g_slice_free (GTreeNode, node);
 143    }
 144 }
 145
 146 /**
 147  * g_tree_new:
 148  * @key_compare_func: the function used to order the nodes in the #GTree.
 149  *   It should return values similar to the standard strcmp() function -
 150  *   0 if the two arguments are equal, a negative value if the first argument
 151  *   comes before the second, or a positive value if the first argument comes
 152  *   after the second.
 153  *
 154  * Creates a new #GTree.
 155  *
 156  * Return value: a new #GTree.
 157  **/
 158 GTree*
 159 g_tree_new (GCompareFunc key_compare_func)
 160 {
 161   g_return_val_if_fail (key_compare_func != NULL, NULL);
 162
 163   return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
 164                           NULL, NULL);
 165 }
 166
 167 /**
 168  * g_tree_new_with_data:
 169  * @key_compare_func: qsort()-style comparison function.
 170  * @key_compare_data: data to pass to comparison function.
 171  *
 172  * Creates a new #GTree with a comparison function that accepts user data.
 173  * See g_tree_new() for more details.
 174  *
 175  * Return value: a new #GTree.
 176  **/
 177 GTree*
 178 g_tree_new_with_data (GCompareDataFunc key_compare_func,
 179                       gpointer         key_compare_data)
 180 {
 181   g_return_val_if_fail (key_compare_func != NULL, NULL);
 182
 183   return g_tree_new_full (key_compare_func, key_compare_data,
 184                           NULL, NULL);
 185 }
 186
 187 /**
 188  * g_tree_new_full:
 189  * @key_compare_func: qsort()-style comparison function.
 190  * @key_compare_data: data to pass to comparison function.
 191  * @key_destroy_func: a function to free the memory allocated for the key
 192  *   used when removing the entry from the #GTree or %NULL if you don't
 193  *   want to supply such a function.
 194  * @value_destroy_func: a function to free the memory allocated for the
 195  *   value used when removing the entry from the #GTree or %NULL if you
 196  *   don't want to supply such a function.
 197  *
 198  * Creates a new #GTree like g_tree_new() and allows to specify functions
 199  * to free the memory allocated for the key and value that get called when
 200  * removing the entry from the #GTree.
 201  *
 202  * Return value: a new #GTree.
 203  **/
 204 GTree*
 205 g_tree_new_full (GCompareDataFunc key_compare_func,
 206                  gpointer         key_compare_data,
 207                  GDestroyNotify   key_destroy_func,
 208                  GDestroyNotify   value_destroy_func)
 209 {
 210   GTree *tree;
 211
 212   g_return_val_if_fail (key_compare_func != NULL, NULL);
 213
 214   tree = g_new (GTree, 1);
 215   tree->root               = NULL;
 216   tree->key_compare        = key_compare_func;
 217   tree->key_destroy_func   = key_destroy_func;
 218   tree->value_destroy_func = value_destroy_func;
 219   tree->key_compare_data   = key_compare_data;
 220
 221   return tree;
 222 }
 223
 224 /**
 225  * g_tree_destroy:
 226  * @tree: a #GTree.
 227  *
 228  * Destroys the #GTree. If keys and/or values are dynamically allocated, you
 229  * should either free them first or create the #GTree using g_tree_new_full().
 230  * In the latter case the destroy functions you supplied will be called on
 231  * all keys and values before destroying the #GTree.
 232  **/
 233 void
 234 g_tree_destroy (GTree *tree)
 235 {
 236   g_return_if_fail (tree != NULL);
 237
 238   g_tree_node_destroy (tree->root,
 239                        tree->key_destroy_func,
 240                        tree->value_destroy_func);
 241
 242   g_free (tree);
 243 }
 244
 245 /**
 246  * g_tree_insert:
 247  * @tree: a #GTree.
 248  * @key: the key to insert.
 249  * @value: the value corresponding to the key.
 250  *
 251  * Inserts a key/value pair into a #GTree. If the given key already exists
 252  * in the #GTree its corresponding value is set to the new value. If you
 253  * supplied a value_destroy_func when creating the #GTree, the old value is
 254  * freed using that function. If you supplied a @key_destroy_func when
 255  * creating the #GTree, the passed key is freed using that function.
 256  *
 257  * The tree is automatically 'balanced' as new key/value pairs are added,
 258  * so that the distance from the root to every leaf is as small as possible.
 259  **/
 260 void
 261 g_tree_insert (GTree    *tree,
 262                gpointer  key,
 263                gpointer  value)
 264 {
 265   gboolean   inserted;
 266
 267   g_return_if_fail (tree != NULL);
 268
 269   inserted = FALSE;
 270   tree->root = g_tree_node_insert (tree,
 271                                    tree->root,
 272                                    key, value,
 273                                    FALSE, &inserted);
 274 }
 275
 276 /**
 277  * g_tree_replace:
 278  * @tree: a #GTree.
 279  * @key: the key to insert.
 280  * @value: the value corresponding to the key.
 281  *
 282  * Inserts a new key and value into a #GTree similar to g_tree_insert().
 283  * The difference is that if the key already exists in the #GTree, it gets
 284  * replaced by the new key. If you supplied a @value_destroy_func when
 285  * creating the #GTree, the old value is freed using that function. If you
 286  * supplied a @key_destroy_func when creating the #GTree, the old key is
 287  * freed using that function.
 288  *
 289  * The tree is automatically 'balanced' as new key/value pairs are added,
 290  * so that the distance from the root to every leaf is as small as possible.
 291  **/
 292 void
 293 g_tree_replace (GTree    *tree,
 294                 gpointer  key,
 295                 gpointer  value)
 296 {
 297   gboolean   inserted;
 298
 299   g_return_if_fail (tree != NULL);
 300
 301   inserted = FALSE;
 302   tree->root = g_tree_node_insert (tree,
 303                                    tree->root,
 304                                    key, value,
 305                                    TRUE, &inserted);
 306 }
 307
 308 /**
 309  * g_tree_remove:
 310  * @tree: a #GTree.
 311  * @key: the key to remove.
 312  *
 313  * Removes a key/value pair from a #GTree.
 314  *
 315  * If the #GTree was created using g_tree_new_full(), the key and value
 316  * are freed using the supplied destroy functions, otherwise you have to
 317  * make sure that any dynamically allocated values are freed yourself.
 318  * If the key does not exist in the #GTree, the function does nothing.
 319  *
 320  * Returns: %TRUE if the key was found (prior to 2.8, this function returned nothing)
 321  **/
 322 gboolean
 323 g_tree_remove (GTree         *tree,
 324                gconstpointer  key)
 325 {
 326   gboolean removed;
 327
 328   g_return_val_if_fail (tree != NULL, FALSE);
 329
 330   tree->root = g_tree_node_remove (tree, tree->root, key, TRUE, &removed);
 331
 332   return removed;
 333 }
 334
 335 /**
 336  * g_tree_steal:
 337  * @tree: a #GTree.
 338  * @key: the key to remove.
 339  *
 340  * Removes a key and its associated value from a #GTree without calling
 341  * the key and value destroy functions.
 342  *
 343  * If the key does not exist in the #GTree, the function does nothing.
 344  *
 345  * Returns: %TRUE if the key was found (prior to 2.8, this function returned nothing)
 346  **/
 347 gboolean
 348 g_tree_steal (GTree         *tree,
 349               gconstpointer  key)
 350 {
 351   gboolean removed;
 352
 353   g_return_val_if_fail (tree != NULL, FALSE);
 354
 355   tree->root = g_tree_node_remove (tree, tree->root, key, FALSE, &removed);
 356
 357   return removed;
 358 }
 359
 360 /**
 361  * g_tree_lookup:
 362  * @tree: a #GTree.
 363  * @key: the key to look up.
 364  *
 365  * Gets the value corresponding to the given key. Since a #GTree is
 366  * automatically balanced as key/value pairs are added, key lookup is very
 367  * fast.
 368  *
 369  * Return value: the value corresponding to the key, or %NULL if the key was
 370  * not found.
 371  **/
 372 gpointer
 373 g_tree_lookup (GTree         *tree,
 374                gconstpointer  key)
 375 {
 376   GTreeNode *node;
 377
 378   g_return_val_if_fail (tree != NULL, NULL);
 379
 380   node = g_tree_node_lookup (tree->root,
 381                              tree->key_compare, tree->key_compare_data, key);
 382
 383   return node ? node->value : NULL;
 384 }
 385
 386 /**
 387  * g_tree_lookup_extended:
 388  * @tree: a #GTree.
 389  * @lookup_key: the key to look up.
 390  * @orig_key: returns the original key.
 391  * @value: returns the value associated with the key.
 392  *
 393  * Looks up a key in the #GTree, returning the original key and the
 394  * associated value and a #gboolean which is %TRUE if the key was found. This
 395  * is useful if you need to free the memory allocated for the original key,
 396  * for example before calling g_tree_remove().
 397  *
 398  * Return value: %TRUE if the key was found in the #GTree.
 399  **/
 400 gboolean
 401 g_tree_lookup_extended (GTree         *tree,
 402                         gconstpointer  lookup_key,
 403                         gpointer      *orig_key,
 404                         gpointer      *value)
 405 {
 406   GTreeNode *node;
 407
 408   g_return_val_if_fail (tree != NULL, FALSE);
 409
 410   node = g_tree_node_lookup (tree->root,
 411                              tree->key_compare, tree->key_compare_data, lookup_key);
 412
 413   if (node)
 414     {
 415       if (orig_key)
 416         *orig_key = node->key;
 417       if (value)
 418         *value = node->value;
 419       return TRUE;
 420     }
 421   else
 422     return FALSE;
 423 }
 424
 425 /**
 426  * g_tree_foreach:
 427  * @tree: a #GTree.
 428  * @func: the function to call for each node visited. If this function
 429  *   returns %TRUE, the traversal is stopped.
 430  * @user_data: user data to pass to the function.
 431  *
 432  * Calls the given function for each of the key/value pairs in the #GTree.
 433  * The function is passed the key and value of each pair, and the given
 434  * @data parameter. The tree is traversed in sorted order.
 435  *
 436  * The tree may not be modified while iterating over it (you can't
 437  * add/remove items). To remove all items matching a predicate, you need
 438  * to add each item to a list in your #GTraverseFunc as you walk over
 439  * the tree, then walk the list and remove each item.
 440  **/
 441 void
 442 g_tree_foreach (GTree         *tree,
 443                 GTraverseFunc  func,
 444                 gpointer       user_data)
 445 {
 446   g_return_if_fail (tree != NULL);
 447
 448   if (!tree->root)
 449     return;
 450
 451   g_tree_node_in_order (tree->root, func, user_data);
 452 }
 453
 454 /**
 455  * g_tree_traverse:
 456  * @tree: a #GTree.
 457  * @traverse_func: the function to call for each node visited. If this
 458  *   function returns %TRUE, the traversal is stopped.
 459  * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
 460  *   %G_PRE_ORDER and %G_POST_ORDER.
 461  * @user_data: user data to pass to the function.
 462  *
 463  * Calls the given function for each node in the #GTree.
 464  *
 465  * Deprecated: The order of a balanced tree is somewhat arbitrary. If you
 466  * just want to visit all nodes in sorted order, use g_tree_foreach()
 467  * instead. If you really need to visit nodes in a different order, consider
 468  * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
 469  **/
 470 void
 471 g_tree_traverse (GTree         *tree,
 472                  GTraverseFunc  traverse_func,
 473                  GTraverseType  traverse_type,
 474                  gpointer       user_data)
 475 {
 476   g_return_if_fail (tree != NULL);
 477
 478   if (!tree->root)
 479     return;
 480
 481   switch (traverse_type)
 482     {
 483     case G_PRE_ORDER:
 484       g_tree_node_pre_order (tree->root, traverse_func, user_data);
 485       break;
 486
 487     case G_IN_ORDER:
 488       g_tree_node_in_order (tree->root, traverse_func, user_data);
 489       break;
 490
 491     case G_POST_ORDER:
 492       g_tree_node_post_order (tree->root, traverse_func, user_data);
 493       break;
 494
 495     case G_LEVEL_ORDER:
 496       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
 497       break;
 498     }
 499 }
 500
 501 /**
 502  * g_tree_search:
 503  * @tree: a #GTree.
 504  * @search_func: a function used to search the #GTree.
 505  * @user_data: the data passed as the second argument to the @search_func
 506  * function.
 507  *
 508  * Searches a #GTree using @search_func.
 509  *
 510  * The @search_func is called with a pointer to the key of a key/value pair in the tree,
 511  * and the passed in @user_data. If @search_func returns 0 for a key/value pair, then
 512  * g_tree_search_func() will return the value of that pair. If @search_func returns -1,
 513  * searching will proceed among the key/value pairs that have a smaller key; if @search_func
 514  * returns 1, searching will proceed among the key/value pairs that have a larger key.
 515  *
 516  * Return value: the value corresponding to the found key, or %NULL if the key
 517  * was not found.
 518  **/
 519 gpointer
 520 g_tree_search (GTree         *tree,
 521                GCompareFunc   search_func,
 522                gconstpointer  user_data)
 523 {
 524   g_return_val_if_fail (tree != NULL, NULL);
 525
 526   if (tree->root)
 527     return g_tree_node_search (tree->root, search_func, user_data);
 528   else
 529     return NULL;
 530 }
 531
 532 /**
 533  * g_tree_height:
 534  * @tree: a #GTree.
 535  *
 536  * Gets the height of a #GTree.
 537  *
 538  * If the #GTree contains no nodes, the height is 0.
 539  * If the #GTree contains only one root node the height is 1.
 540  * If the root node has children the height is 2, etc.
 541  *
 542  * Return value: the height of the #GTree.
 543  **/
 544 gint
 545 g_tree_height (GTree *tree)
 546 {
 547   g_return_val_if_fail (tree != NULL, 0);
 548
 549   if (tree->root)
 550     return g_tree_node_height (tree->root);
 551   else
 552     return 0;
 553 }
 554
 555 /**
 556  * g_tree_nnodes:
 557  * @tree: a #GTree.
 558  *
 559  * Gets the number of nodes in a #GTree.
 560  *
 561  * Return value: the number of nodes in the #GTree.
 562  **/
 563 gint
 564 g_tree_nnodes (GTree *tree)
 565 {
 566   g_return_val_if_fail (tree != NULL, 0);
 567
 568   if (tree->root)
 569     return g_tree_node_count (tree->root);
 570   else
 571     return 0;
 572 }
 573
 574 static GTreeNode*
 575 g_tree_node_insert (GTree     *tree,
 576                     GTreeNode *node,
 577                     gpointer   key,
 578                     gpointer   value,
 579                     gboolean   replace,
 580                     gboolean  *inserted)
 581 {
 582   gint  old_balance;
 583   gint  cmp;
 584
 585   if (!node)
 586     {
 587       *inserted = TRUE;
 588       return g_tree_node_new (key, value);
 589     }
 590
 591   cmp = tree->key_compare (key, node->key, tree->key_compare_data);
 592   if (cmp == 0)
 593     {
 594       *inserted = FALSE;
 595
 596       if (tree->value_destroy_func)
 597         tree->value_destroy_func (node->value);
 598
 599       node->value = value;
 600
 601       if (replace)
 602         {
 603           if (tree->key_destroy_func)
 604             tree->key_destroy_func (node->key);
 605
 606           node->key = key;
 607         }
 608       else
 609         {
 610           /* free the passed key */
 611           if (tree->key_destroy_func)
 612             tree->key_destroy_func (key);
 613         }
 614
 615       return node;
 616     }
 617
 618   if (cmp < 0)
 619     {
 620       if (node->left)
 621         {
 622           old_balance = node->left->balance;
 623           node->left = g_tree_node_insert (tree,
 624                                            node->left,
 625                                            key, value,
 626                                            replace, inserted);
 627
 628           if ((old_balance != node->left->balance) && node->left->balance)
 629             node->balance -= 1;
 630         }
 631       else
 632         {
 633           *inserted = TRUE;
 634           node->left = g_tree_node_new (key, value);
 635           node->balance -= 1;
 636         }
 637     }
 638   else if (cmp > 0)
 639     {
 640       if (node->right)
 641         {
 642           old_balance = node->right->balance;
 643           node->right = g_tree_node_insert (tree,
 644                                             node->right,
 645                                             key, value,
 646                                             replace, inserted);
 647
 648           if ((old_balance != node->right->balance) && node->right->balance)
 649             node->balance += 1;
 650         }
 651       else
 652         {
 653           *inserted = TRUE;
 654           node->right = g_tree_node_new (key, value);
 655           node->balance += 1;
 656         }
 657     }
 658
 659   if (*inserted)
 660     {
 661       if ((node->balance < -1) || (node->balance > 1))
 662         node = g_tree_node_balance (node);
 663     }
 664
 665   return node;
 666 }
 667
 668 static GTreeNode*
 669 g_tree_node_remove (GTree         *tree,
 670                     GTreeNode     *node,
 671                     gconstpointer  key,
 672                     gboolean       notify,
 673                     gboolean      *removed)
 674 {
 675   GTreeNode *new_root;
 676   gint old_balance;
 677   gint cmp;
 678
 679   *removed = FALSE;
 680
 681   if (!node)
 682     return NULL;
 683
 684   cmp = tree->key_compare (key, node->key, tree->key_compare_data);
 685   if (cmp == 0)
 686     {
 687       GTreeNode *garbage;
 688
 689       garbage = node;
 690
 691       if (!node->right)
 692         {
 693           node = node->left;
 694         }
 695       else
 696         {
 697           old_balance = node->right->balance;
 698           node->right = g_tree_node_remove_leftmost (node->right, &new_root);
 699           new_root->left = node->left;
 700           new_root->right = node->right;
 701           new_root->balance = node->balance;
 702           node = g_tree_node_restore_right_balance (new_root, old_balance);
 703         }
 704
 705       if (notify)
 706         {
 707           if (tree->key_destroy_func)
 708             tree->key_destroy_func (garbage->key);
 709           if (tree->value_destroy_func)
 710             tree->value_destroy_func (garbage->value);
 711         }
 712
 713 #ifdef ENABLE_GC_FRIENDLY
 714       garbage->left = NULL;
 715       garbage->key = NULL;
 716       garbage->value = NULL;
 717 #endif /* ENABLE_GC_FRIENDLY */
 718
 719       g_slice_free (GTreeNode, garbage);
 720
 721       *removed = TRUE;
 722    }
 723   else if (cmp < 0)
 724     {
 725       if (node->left)
 726         {
 727           old_balance = node->left->balance;
 728           node->left = g_tree_node_remove (tree, node->left, key, notify, removed);
 729           node = g_tree_node_restore_left_balance (node, old_balance);
 730         }
 731     }
 732   else if (cmp > 0)
 733     {
 734       if (node->right)
 735         {
 736           old_balance = node->right->balance;
 737           node->right = g_tree_node_remove (tree, node->right, key, notify, removed);
 738           node = g_tree_node_restore_right_balance (node, old_balance);
 739         }
 740     }
 741
 742   return node;
 743 }
 744
 745 static GTreeNode*
 746 g_tree_node_balance (GTreeNode *node)
 747 {
 748   if (node->balance < -1)
 749     {
 750       if (node->left->balance > 0)
 751         node->left = g_tree_node_rotate_left (node->left);
 752       node = g_tree_node_rotate_right (node);
 753     }
 754   else if (node->balance > 1)
 755     {
 756       if (node->right->balance < 0)
 757         node->right = g_tree_node_rotate_right (node->right);
 758       node = g_tree_node_rotate_left (node);
 759     }
 760
 761   return node;
 762 }
 763
 764 static GTreeNode*
 765 g_tree_node_remove_leftmost (GTreeNode  *node,
 766                              GTreeNode **leftmost)
 767 {
 768   gint old_balance;
 769
 770   if (!node->left)
 771     {
 772       *leftmost = node;
 773       return node->right;
 774     }
 775
 776   old_balance = node->left->balance;
 777   node->left = g_tree_node_remove_leftmost (node->left, leftmost);
 778   return g_tree_node_restore_left_balance (node, old_balance);
 779 }
 780
 781 static GTreeNode*
 782 g_tree_node_restore_left_balance (GTreeNode *node,
 783                                   gint       old_balance)
 784 {
 785   if (!node->left)
 786     node->balance += 1;
 787   else if ((node->left->balance != old_balance) &&
 788            (node->left->balance == 0))
 789     node->balance += 1;
 790
 791   if (node->balance > 1)
 792     return g_tree_node_balance (node);
 793   return node;
 794 }
 795
 796 static GTreeNode*
 797 g_tree_node_restore_right_balance (GTreeNode *node,
 798                                    gint       old_balance)
 799 {
 800   if (!node->right)
 801     node->balance -= 1;
 802   else if ((node->right->balance != old_balance) &&
 803            (node->right->balance == 0))
 804     node->balance -= 1;
 805
 806   if (node->balance < -1)
 807     return g_tree_node_balance (node);
 808   return node;
 809 }
 810
 811 static GTreeNode *
 812 g_tree_node_lookup (GTreeNode        *node,
 813                     GCompareDataFunc  compare,
 814                     gpointer          compare_data,
 815                     gconstpointer     key)
 816 {
 817   gint cmp;
 818
 819   if (!node)
 820     return NULL;
 821
 822   cmp = (* compare) (key, node->key, compare_data);
 823   if (cmp == 0)
 824     return node;
 825
 826   if (cmp < 0)
 827     {
 828       if (node->left)
 829         return g_tree_node_lookup (node->left, compare, compare_data, key);
 830     }
 831   else if (cmp > 0)
 832     {
 833       if (node->right)
 834         return g_tree_node_lookup (node->right, compare, compare_data, key);
 835     }
 836
 837   return NULL;
 838 }
 839
 840 static gint
 841 g_tree_node_count (GTreeNode *node)
 842 {
 843   gint count;
 844
 845   count = 1;
 846   if (node->left)
 847     count += g_tree_node_count (node->left);
 848   if (node->right)
 849     count += g_tree_node_count (node->right);
 850
 851   return count;
 852 }
 853
 854 static gint
 855 g_tree_node_pre_order (GTreeNode     *node,
 856                        GTraverseFunc  traverse_func,
 857                        gpointer       data)
 858 {
 859   if ((*traverse_func) (node->key, node->value, data))
 860     return TRUE;
 861   if (node->left)
 862     {
 863       if (g_tree_node_pre_order (node->left, traverse_func, data))
 864         return TRUE;
 865     }
 866   if (node->right)
 867     {
 868       if (g_tree_node_pre_order (node->right, traverse_func, data))
 869         return TRUE;
 870     }
 871
 872   return FALSE;
 873 }
 874
 875 static gint
 876 g_tree_node_in_order (GTreeNode     *node,
 877                       GTraverseFunc  traverse_func,
 878                       gpointer       data)
 879 {
 880   if (node->left)
 881     {
 882       if (g_tree_node_in_order (node->left, traverse_func, data))
 883         return TRUE;
 884     }
 885   if ((*traverse_func) (node->key, node->value, data))
 886     return TRUE;
 887   if (node->right)
 888     {
 889       if (g_tree_node_in_order (node->right, traverse_func, data))
 890         return TRUE;
 891     }
 892
 893   return FALSE;
 894 }
 895
 896 static gint
 897 g_tree_node_post_order (GTreeNode     *node,
 898                         GTraverseFunc  traverse_func,
 899                         gpointer       data)
 900 {
 901   if (node->left)
 902     {
 903       if (g_tree_node_post_order (node->left, traverse_func, data))
 904         return TRUE;
 905     }
 906   if (node->right)
 907     {
 908       if (g_tree_node_post_order (node->right, traverse_func, data))
 909         return TRUE;
 910     }
 911   if ((*traverse_func) (node->key, node->value, data))
 912     return TRUE;
 913
 914   return FALSE;
 915 }
 916
 917 static gpointer
 918 g_tree_node_search (GTreeNode     *node,
 919                     GCompareFunc   search_func,
 920                     gconstpointer  data)
 921 {
 922   gint dir;
 923
 924   if (!node)
 925     return NULL;
 926
 927   do {
 928     dir = (* search_func) (node->key, data);
 929     if (dir == 0)
 930       return node->value;
 931
 932     if (dir < 0)
 933       node = node->left;
 934     else if (dir > 0)
 935       node = node->right;
 936   } while (node);
 937
 938   return NULL;
 939 }
 940
 941 static gint
 942 g_tree_node_height (GTreeNode *node)
 943 {
 944   gint left_height;
 945   gint right_height;
 946
 947   if (node)
 948     {
 949       left_height = 0;
 950       right_height = 0;
 951
 952       if (node->left)
 953         left_height = g_tree_node_height (node->left);
 954
 955       if (node->right)
 956         right_height = g_tree_node_height (node->right);
 957
 958       return MAX (left_height, right_height) + 1;
 959     }
 960
 961   return 0;
 962 }
 963
 964 static GTreeNode*
 965 g_tree_node_rotate_left (GTreeNode *node)
 966 {
 967   GTreeNode *right;
 968   gint a_bal;
 969   gint b_bal;
 970
 971   right = node->right;
 972
 973   node->right = right->left;
 974   right->left = node;
 975
 976   a_bal = node->balance;
 977   b_bal = right->balance;
 978
 979   if (b_bal <= 0)
 980     {
 981       if (a_bal >= 1)
 982         right->balance = b_bal - 1;
 983       else
 984         right->balance = a_bal + b_bal - 2;
 985       node->balance = a_bal - 1;
 986     }
 987   else
 988     {
 989       if (a_bal <= b_bal)
 990         right->balance = a_bal - 2;
 991       else
 992         right->balance = b_bal - 1;
 993       node->balance = a_bal - b_bal - 1;
 994     }
 995
 996   return right;
 997 }
 998
 999 static GTreeNode*
1000 g_tree_node_rotate_right (GTreeNode *node)
1001 {
1002   GTreeNode *left;
1003   gint a_bal;
1004   gint b_bal;
1005
1006   left = node->left;
1007
1008   node->left = left->right;
1009   left->right = node;
1010
1011   a_bal = node->balance;
1012   b_bal = left->balance;
1013
1014   if (b_bal <= 0)
1015     {
1016       if (b_bal > a_bal)
1017         left->balance = b_bal + 1;
1018       else
1019         left->balance = a_bal + 2;
1020       node->balance = a_bal - b_bal + 1;
1021     }
1022   else
1023     {
1024       if (a_bal <= -1)
1025         left->balance = b_bal + 1;
1026       else
1027         left->balance = a_bal + b_bal + 2;
1028       node->balance = a_bal + 1;
1029     }
1030
1031   return left;
1032 }
1033
1034 static void
1035 g_tree_node_check (GTreeNode *node)
1036 {
1037   gint left_height;
1038   gint right_height;
1039   gint balance;
1040
1041   if (node)
1042     {
1043       left_height = 0;
1044       right_height = 0;
1045
1046       if (node->left)
1047         left_height = g_tree_node_height (node->left);
1048       if (node->right)
1049         right_height = g_tree_node_height (node->right);
1050
1051       balance = right_height - left_height;
1052       if (balance != node->balance)
1053         g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO,
1054                "g_tree_node_check: failed: %d ( %d )\n",
1055                balance, node->balance);
1056
1057       if (node->left)
1058         g_tree_node_check (node->left);
1059       if (node->right)
1060         g_tree_node_check (node->right);
1061     }
1062 }
1063
1064 #define __G_TREE_C__
1065 #include "galiasdef.c"