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