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