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