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