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