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
 321  *   nothing)
 322  **/
 323 gboolean
 324 g_tree_remove (GTree         *tree,
 325                gconstpointer  key)
 326 {
 327   gboolean removed;
 328
 329   g_return_val_if_fail (tree != NULL, FALSE);
 330
 331   tree->root = g_tree_node_remove (tree, tree->root, key, TRUE, &removed);
 332
 333   return removed;
 334 }
 335
 336 /**
 337  * g_tree_steal:
 338  * @tree: a #GTree.
 339  * @key: the key to remove.
 340  *
 341  * Removes a key and its associated value from a #GTree without calling
 342  * the key and value destroy functions.
 343  *
 344  * If the key does not exist in the #GTree, the function does nothing.
 345  *
 346  * Returns: %TRUE if the key was found (prior to 2.8, this function returned
 347  *    nothing)
 348  **/
 349 gboolean
 350 g_tree_steal (GTree         *tree,
 351               gconstpointer  key)
 352 {
 353   gboolean removed;
 354
 355   g_return_val_if_fail (tree != NULL, FALSE);
 356
 357   tree->root = g_tree_node_remove (tree, tree->root, key, FALSE, &removed);
 358
 359   return removed;
 360 }
 361
 362 /**
 363  * g_tree_lookup:
 364  * @tree: a #GTree.
 365  * @key: the key to look up.
 366  *
 367  * Gets the value corresponding to the given key. Since a #GTree is
 368  * automatically balanced as key/value pairs are added, key lookup is very
 369  * fast.
 370  *
 371  * Return value: the value corresponding to the key, or %NULL if the key was
 372  * not found.
 373  **/
 374 gpointer
 375 g_tree_lookup (GTree         *tree,
 376                gconstpointer  key)
 377 {
 378   GTreeNode *node;
 379
 380   g_return_val_if_fail (tree != NULL, NULL);
 381
 382   node = g_tree_node_lookup (tree->root,
 383                              tree->key_compare, tree->key_compare_data, key);
 384
 385   return node ? node->value : NULL;
 386 }
 387
 388 /**
 389  * g_tree_lookup_extended:
 390  * @tree: a #GTree.
 391  * @lookup_key: the key to look up.
 392  * @orig_key: returns the original key.
 393  * @value: returns the value associated with the key.
 394  *
 395  * Looks up a key in the #GTree, returning the original key and the
 396  * associated value and a #gboolean which is %TRUE if the key was found. This
 397  * is useful if you need to free the memory allocated for the original key,
 398  * for example before calling g_tree_remove().
 399  *
 400  * Return value: %TRUE if the key was found in the #GTree.
 401  **/
 402 gboolean
 403 g_tree_lookup_extended (GTree         *tree,
 404                         gconstpointer  lookup_key,
 405                         gpointer      *orig_key,
 406                         gpointer      *value)
 407 {
 408   GTreeNode *node;
 409
 410   g_return_val_if_fail (tree != NULL, FALSE);
 411
 412   node = g_tree_node_lookup (tree->root,
 413                              tree->key_compare, tree->key_compare_data, lookup_key);
 414
 415   if (node)
 416     {
 417       if (orig_key)
 418         *orig_key = node->key;
 419       if (value)
 420         *value = node->value;
 421       return TRUE;
 422     }
 423   else
 424     return FALSE;
 425 }
 426
 427 /**
 428  * g_tree_foreach:
 429  * @tree: a #GTree.
 430  * @func: the function to call for each node visited. If this function
 431  *   returns %TRUE, the traversal is stopped.
 432  * @user_data: user data to pass to the function.
 433  *
 434  * Calls the given function for each of the key/value pairs in the #GTree.
 435  * The function is passed the key and value of each pair, and the given
 436  * @data parameter. The tree is traversed in sorted order.
 437  *
 438  * The tree may not be modified while iterating over it (you can't
 439  * add/remove items). To remove all items matching a predicate, you need
 440  * to add each item to a list in your #GTraverseFunc as you walk over
 441  * the tree, then walk the list and remove each item.
 442  **/
 443 void
 444 g_tree_foreach (GTree         *tree,
 445                 GTraverseFunc  func,
 446                 gpointer       user_data)
 447 {
 448   g_return_if_fail (tree != NULL);
 449
 450   if (!tree->root)
 451     return;
 452
 453   g_tree_node_in_order (tree->root, func, user_data);
 454 }
 455
 456 /**
 457  * g_tree_traverse:
 458  * @tree: a #GTree.
 459  * @traverse_func: the function to call for each node visited. If this
 460  *   function returns %TRUE, the traversal is stopped.
 461  * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
 462  *   %G_PRE_ORDER and %G_POST_ORDER.
 463  * @user_data: user data to pass to the function.
 464  *
 465  * Calls the given function for each node in the #GTree.
 466  *
 467  * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary. If you
 468  * just want to visit all nodes in sorted order, use g_tree_foreach()
 469  * instead. If you really need to visit nodes in a different order, consider
 470  * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
 471  **/
 472 void
 473 g_tree_traverse (GTree         *tree,
 474                  GTraverseFunc  traverse_func,
 475                  GTraverseType  traverse_type,
 476                  gpointer       user_data)
 477 {
 478   g_return_if_fail (tree != NULL);
 479
 480   if (!tree->root)
 481     return;
 482
 483   switch (traverse_type)
 484     {
 485     case G_PRE_ORDER:
 486       g_tree_node_pre_order (tree->root, traverse_func, user_data);
 487       break;
 488
 489     case G_IN_ORDER:
 490       g_tree_node_in_order (tree->root, traverse_func, user_data);
 491       break;
 492
 493     case G_POST_ORDER:
 494       g_tree_node_post_order (tree->root, traverse_func, user_data);
 495       break;
 496
 497     case G_LEVEL_ORDER:
 498       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
 499       break;
 500     }
 501 }
 502
 503 /**
 504  * g_tree_search:
 505  * @tree: a #GTree.
 506  * @search_func: a function used to search the #GTree.
 507  * @user_data: the data passed as the second argument to the @search_func
 508  * function.
 509  *
 510  * Searches a #GTree using @search_func.
 511  *
 512  * The @search_func is called with a pointer to the key of a key/value pair in
 513  * the tree, and the passed in @user_data. If @search_func returns 0 for a
 514  * key/value pair, then g_tree_search_func() will return the value of that
 515  * pair. If @search_func returns -1,  searching will proceed among the
 516  * key/value pairs that have a smaller key; if @search_func returns 1,
 517  * searching will proceed among the key/value pairs that have a larger key.
 518  *
 519  * Return value: the value corresponding to the found key, or %NULL if the key
 520  * was not found.
 521  **/
 522 gpointer
 523 g_tree_search (GTree         *tree,
 524                GCompareFunc   search_func,
 525                gconstpointer  user_data)
 526 {
 527   g_return_val_if_fail (tree != NULL, NULL);
 528
 529   if (tree->root)
 530     return g_tree_node_search (tree->root, search_func, user_data);
 531   else
 532     return NULL;
 533 }
 534
 535 /**
 536  * g_tree_height:
 537  * @tree: a #GTree.
 538  *
 539  * Gets the height of a #GTree.
 540  *
 541  * If the #GTree contains no nodes, the height is 0.
 542  * If the #GTree contains only one root node the height is 1.
 543  * If the root node has children the height is 2, etc.
 544  *
 545  * Return value: the height of the #GTree.
 546  **/
 547 gint
 548 g_tree_height (GTree *tree)
 549 {
 550   g_return_val_if_fail (tree != NULL, 0);
 551
 552   if (tree->root)
 553     return g_tree_node_height (tree->root);
 554   else
 555     return 0;
 556 }
 557
 558 /**
 559  * g_tree_nnodes:
 560  * @tree: a #GTree.
 561  *
 562  * Gets the number of nodes in a #GTree.
 563  *
 564  * Return value: the number of nodes in the #GTree.
 565  **/
 566 gint
 567 g_tree_nnodes (GTree *tree)
 568 {
 569   g_return_val_if_fail (tree != NULL, 0);
 570
 571   if (tree->root)
 572     return g_tree_node_count (tree->root);
 573   else
 574     return 0;
 575 }
 576
 577 static GTreeNode*
 578 g_tree_node_insert (GTree     *tree,
 579                     GTreeNode *node,
 580                     gpointer   key,
 581                     gpointer   value,
 582                     gboolean   replace,
 583                     gboolean  *inserted)
 584 {
 585   gint  old_balance;
 586   gint  cmp;
 587
 588   if (!node)
 589     {
 590       *inserted = TRUE;
 591       return g_tree_node_new (key, value);
 592     }
 593
 594   cmp = tree->key_compare (key, node->key, tree->key_compare_data);
 595   if (cmp == 0)
 596     {
 597       *inserted = FALSE;
 598
 599       if (tree->value_destroy_func)
 600         tree->value_destroy_func (node->value);
 601
 602       node->value = value;
 603
 604       if (replace)
 605         {
 606           if (tree->key_destroy_func)
 607             tree->key_destroy_func (node->key);
 608
 609           node->key = key;
 610         }
 611       else
 612         {
 613           /* free the passed key */
 614           if (tree->key_destroy_func)
 615             tree->key_destroy_func (key);
 616         }
 617
 618       return node;
 619     }
 620
 621   if (cmp < 0)
 622     {
 623       if (node->left)
 624         {
 625           old_balance = node->left->balance;
 626           node->left = g_tree_node_insert (tree,
 627                                            node->left,
 628                                            key, value,
 629                                            replace, inserted);
 630
 631           if ((old_balance != node->left->balance) && node->left->balance)
 632             node->balance -= 1;
 633         }
 634       else
 635         {
 636           *inserted = TRUE;
 637           node->left = g_tree_node_new (key, value);
 638           node->balance -= 1;
 639         }
 640     }
 641   else if (cmp > 0)
 642     {
 643       if (node->right)
 644         {
 645           old_balance = node->right->balance;
 646           node->right = g_tree_node_insert (tree,
 647                                             node->right,
 648                                             key, value,
 649                                             replace, inserted);
 650
 651           if ((old_balance != node->right->balance) && node->right->balance)
 652             node->balance += 1;
 653         }
 654       else
 655         {
 656           *inserted = TRUE;
 657           node->right = g_tree_node_new (key, value);
 658           node->balance += 1;
 659         }
 660     }
 661
 662   if (*inserted)
 663     {
 664       if ((node->balance < -1) || (node->balance > 1))
 665         node = g_tree_node_balance (node);
 666     }
 667
 668   return node;
 669 }
 670
 671 static GTreeNode*
 672 g_tree_node_remove (GTree         *tree,
 673                     GTreeNode     *node,
 674                     gconstpointer  key,
 675                     gboolean       notify,
 676                     gboolean      *removed)
 677 {
 678   GTreeNode *new_root;
 679   gint old_balance;
 680   gint cmp;
 681
 682   *removed = FALSE;
 683
 684   if (!node)
 685     return NULL;
 686
 687   cmp = tree->key_compare (key, node->key, tree->key_compare_data);
 688   if (cmp == 0)
 689     {
 690       GTreeNode *garbage;
 691
 692       garbage = node;
 693
 694       if (!node->right)
 695         {
 696           node = node->left;
 697         }
 698       else
 699         {
 700           old_balance = node->right->balance;
 701           node->right = g_tree_node_remove_leftmost (node->right, &new_root);
 702           new_root->left = node->left;
 703           new_root->right = node->right;
 704           new_root->balance = node->balance;
 705           node = g_tree_node_restore_right_balance (new_root, old_balance);
 706         }
 707
 708       if (notify)
 709         {
 710           if (tree->key_destroy_func)
 711             tree->key_destroy_func (garbage->key);
 712           if (tree->value_destroy_func)
 713             tree->value_destroy_func (garbage->value);
 714         }
 715
 716 #ifdef ENABLE_GC_FRIENDLY
 717       garbage->left = NULL;
 718       garbage->key = NULL;
 719       garbage->value = NULL;
 720 #endif /* ENABLE_GC_FRIENDLY */
 721
 722       g_slice_free (GTreeNode, garbage);
 723
 724       *removed = TRUE;
 725    }
 726   else if (cmp < 0)
 727     {
 728       if (node->left)
 729         {
 730           old_balance = node->left->balance;
 731           node->left = g_tree_node_remove (tree, node->left, key, notify, removed);
 732           node = g_tree_node_restore_left_balance (node, old_balance);
 733         }
 734     }
 735   else if (cmp > 0)
 736     {
 737       if (node->right)
 738         {
 739           old_balance = node->right->balance;
 740           node->right = g_tree_node_remove (tree, node->right, key, notify, removed);
 741           node = g_tree_node_restore_right_balance (node, old_balance);
 742         }
 743     }
 744
 745   return node;
 746 }
 747
 748 static GTreeNode*
 749 g_tree_node_balance (GTreeNode *node)
 750 {
 751   if (node->balance < -1)
 752     {
 753       if (node->left->balance > 0)
 754         node->left = g_tree_node_rotate_left (node->left);
 755       node = g_tree_node_rotate_right (node);
 756     }
 757   else if (node->balance > 1)
 758     {
 759       if (node->right->balance < 0)
 760         node->right = g_tree_node_rotate_right (node->right);
 761       node = g_tree_node_rotate_left (node);
 762     }
 763
 764   return node;
 765 }
 766
 767 static GTreeNode*
 768 g_tree_node_remove_leftmost (GTreeNode  *node,
 769                              GTreeNode **leftmost)
 770 {
 771   gint old_balance;
 772
 773   if (!node->left)
 774     {
 775       *leftmost = node;
 776       return node->right;
 777     }
 778
 779   old_balance = node->left->balance;
 780   node->left = g_tree_node_remove_leftmost (node->left, leftmost);
 781   return g_tree_node_restore_left_balance (node, old_balance);
 782 }
 783
 784 static GTreeNode*
 785 g_tree_node_restore_left_balance (GTreeNode *node,
 786                                   gint       old_balance)
 787 {
 788   if (!node->left)
 789     node->balance += 1;
 790   else if ((node->left->balance != old_balance) &&
 791            (node->left->balance == 0))
 792     node->balance += 1;
 793
 794   if (node->balance > 1)
 795     return g_tree_node_balance (node);
 796   return node;
 797 }
 798
 799 static GTreeNode*
 800 g_tree_node_restore_right_balance (GTreeNode *node,
 801                                    gint       old_balance)
 802 {
 803   if (!node->right)
 804     node->balance -= 1;
 805   else if ((node->right->balance != old_balance) &&
 806            (node->right->balance == 0))
 807     node->balance -= 1;
 808
 809   if (node->balance < -1)
 810     return g_tree_node_balance (node);
 811   return node;
 812 }
 813
 814 static GTreeNode *
 815 g_tree_node_lookup (GTreeNode        *node,
 816                     GCompareDataFunc  compare,
 817                     gpointer          compare_data,
 818                     gconstpointer     key)
 819 {
 820   gint cmp;
 821
 822   if (!node)
 823     return NULL;
 824
 825   cmp = (* compare) (key, node->key, compare_data);
 826   if (cmp == 0)
 827     return node;
 828
 829   if (cmp < 0)
 830     {
 831       if (node->left)
 832         return g_tree_node_lookup (node->left, compare, compare_data, key);
 833     }
 834   else if (cmp > 0)
 835     {
 836       if (node->right)
 837         return g_tree_node_lookup (node->right, compare, compare_data, key);
 838     }
 839
 840   return NULL;
 841 }
 842
 843 static gint
 844 g_tree_node_count (GTreeNode *node)
 845 {
 846   gint count;
 847
 848   count = 1;
 849   if (node->left)
 850     count += g_tree_node_count (node->left);
 851   if (node->right)
 852     count += g_tree_node_count (node->right);
 853
 854   return count;
 855 }
 856
 857 static gint
 858 g_tree_node_pre_order (GTreeNode     *node,
 859                        GTraverseFunc  traverse_func,
 860                        gpointer       data)
 861 {
 862   if ((*traverse_func) (node->key, node->value, data))
 863     return TRUE;
 864   if (node->left)
 865     {
 866       if (g_tree_node_pre_order (node->left, traverse_func, data))
 867         return TRUE;
 868     }
 869   if (node->right)
 870     {
 871       if (g_tree_node_pre_order (node->right, traverse_func, data))
 872         return TRUE;
 873     }
 874
 875   return FALSE;
 876 }
 877
 878 static gint
 879 g_tree_node_in_order (GTreeNode     *node,
 880                       GTraverseFunc  traverse_func,
 881                       gpointer       data)
 882 {
 883   if (node->left)
 884     {
 885       if (g_tree_node_in_order (node->left, traverse_func, data))
 886         return TRUE;
 887     }
 888   if ((*traverse_func) (node->key, node->value, data))
 889     return TRUE;
 890   if (node->right)
 891     {
 892       if (g_tree_node_in_order (node->right, traverse_func, data))
 893         return TRUE;
 894     }
 895
 896   return FALSE;
 897 }
 898
 899 static gint
 900 g_tree_node_post_order (GTreeNode     *node,
 901                         GTraverseFunc  traverse_func,
 902                         gpointer       data)
 903 {
 904   if (node->left)
 905     {
 906       if (g_tree_node_post_order (node->left, traverse_func, data))
 907         return TRUE;
 908     }
 909   if (node->right)
 910     {
 911       if (g_tree_node_post_order (node->right, traverse_func, data))
 912         return TRUE;
 913     }
 914   if ((*traverse_func) (node->key, node->value, data))
 915     return TRUE;
 916
 917   return FALSE;
 918 }
 919
 920 static gpointer
 921 g_tree_node_search (GTreeNode     *node,
 922                     GCompareFunc   search_func,
 923                     gconstpointer  data)
 924 {
 925   gint dir;
 926
 927   if (!node)
 928     return NULL;
 929
 930   do {
 931     dir = (* search_func) (node->key, data);
 932     if (dir == 0)
 933       return node->value;
 934
 935     if (dir < 0)
 936       node = node->left;
 937     else if (dir > 0)
 938       node = node->right;
 939   } while (node);
 940
 941   return NULL;
 942 }
 943
 944 static gint
 945 g_tree_node_height (GTreeNode *node)
 946 {
 947   gint left_height;
 948   gint right_height;
 949
 950   if (node)
 951     {
 952       left_height = 0;
 953       right_height = 0;
 954
 955       if (node->left)
 956         left_height = g_tree_node_height (node->left);
 957
 958       if (node->right)
 959         right_height = g_tree_node_height (node->right);
 960
 961       return MAX (left_height, right_height) + 1;
 962     }
 963
 964   return 0;
 965 }
 966
 967 static GTreeNode*
 968 g_tree_node_rotate_left (GTreeNode *node)
 969 {
 970   GTreeNode *right;
 971   gint a_bal;
 972   gint b_bal;
 973
 974   right = node->right;
 975
 976   node->right = right->left;
 977   right->left = node;
 978
 979   a_bal = node->balance;
 980   b_bal = right->balance;
 981
 982   if (b_bal <= 0)
 983     {
 984       if (a_bal >= 1)
 985         right->balance = b_bal - 1;
 986       else
 987         right->balance = a_bal + b_bal - 2;
 988       node->balance = a_bal - 1;
 989     }
 990   else
 991     {
 992       if (a_bal <= b_bal)
 993         right->balance = a_bal - 2;
 994       else
 995         right->balance = b_bal - 1;
 996       node->balance = a_bal - b_bal - 1;
 997     }
 998
 999   return right;
1000 }
1001
1002 static GTreeNode*
1003 g_tree_node_rotate_right (GTreeNode *node)
1004 {
1005   GTreeNode *left;
1006   gint a_bal;
1007   gint b_bal;
1008
1009   left = node->left;
1010
1011   node->left = left->right;
1012   left->right = node;
1013
1014   a_bal = node->balance;
1015   b_bal = left->balance;
1016
1017   if (b_bal <= 0)
1018     {
1019       if (b_bal > a_bal)
1020         left->balance = b_bal + 1;
1021       else
1022         left->balance = a_bal + 2;
1023       node->balance = a_bal - b_bal + 1;
1024     }
1025   else
1026     {
1027       if (a_bal <= -1)
1028         left->balance = b_bal + 1;
1029       else
1030         left->balance = a_bal + b_bal + 2;
1031       node->balance = a_bal + 1;
1032     }
1033
1034   return left;
1035 }
1036
1037 static void
1038 g_tree_node_check (GTreeNode *node)
1039 {
1040   gint left_height;
1041   gint right_height;
1042   gint balance;
1043
1044   if (node)
1045     {
1046       left_height = 0;
1047       right_height = 0;
1048
1049       if (node->left)
1050         left_height = g_tree_node_height (node->left);
1051       if (node->right)
1052         right_height = g_tree_node_height (node->right);
1053
1054       balance = right_height - left_height;
1055       if (balance != node->balance)
1056         g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO,
1057                "g_tree_node_check: failed: %d ( %d )\n",
1058                balance, node->balance);
1059
1060       if (node->left)
1061         g_tree_node_check (node->left);
1062       if (node->right)
1063         g_tree_node_check (node->right);
1064     }
1065 }
1066
1067 #define __G_TREE_C__
1068 #include "galiasdef.c"