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  * SPDX-License-Identifier: LGPL-2.1-or-later
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  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 "gtree.h"
  34
  35 #include "gatomic.h"
  36 #include "gtestutils.h"
  37 #include "gslice.h"
  38
  39 /**
  40  * SECTION:trees-binary
  41  * @title: Balanced Binary Trees
  42  * @short_description: a sorted collection of key/value pairs optimized
  43  *                     for searching and traversing in order
  44  *
  45  * The #GTree structure and its associated functions provide a sorted
  46  * collection of key/value pairs optimized for searching and traversing
  47  * in order. This means that most of the operations  (access, search,
  48  * insertion, deletion, ...) on #GTree are O(log(n)) in average and O(n)
  49  * in worst case for time complexity. But, note that maintaining a
  50  * balanced sorted #GTree of n elements is done in time O(n log(n)).
  51  *
  52  * To create a new #GTree use g_tree_new().
  53  *
  54  * To insert a key/value pair into a #GTree use g_tree_insert()
  55  * (O(n log(n))).
  56  *
  57  * To remove a key/value pair use g_tree_remove() (O(n log(n))).
  58  *
  59  * To look up the value corresponding to a given key, use
  60  * g_tree_lookup() and g_tree_lookup_extended().
  61  *
  62  * To find out the number of nodes in a #GTree, use g_tree_nnodes(). To
  63  * get the height of a #GTree, use g_tree_height().
  64  *
  65  * To traverse a #GTree, calling a function for each node visited in
  66  * the traversal, use g_tree_foreach().
  67  *
  68  * To destroy a #GTree, use g_tree_destroy().
  69  **/
  70
  71 #define MAX_GTREE_HEIGHT 40
  72
  73 /**
  74  * GTree:
  75  *
  76  * The GTree struct is an opaque data structure representing a
  77  * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be
  78  * accessed only by using the following functions.
  79  */
  80 struct _GTree
  81 {
  82   GTreeNode        *root;
  83   GCompareDataFunc  key_compare;
  84   GDestroyNotify    key_destroy_func;
  85   GDestroyNotify    value_destroy_func;
  86   gpointer          key_compare_data;
  87   guint             nnodes;
  88   gint              ref_count;
  89 };
  90
  91 struct _GTreeNode
  92 {
  93   gpointer   key;         /* key for this node */
  94   gpointer   value;       /* value stored at this node */
  95   GTreeNode *left;        /* left subtree */
  96   GTreeNode *right;       /* right subtree */
  97   gint8      balance;     /* height (right) - height (left) */
  98   guint8     left_child;
  99   guint8     right_child;
 100 };
 101
 102
 103 static GTreeNode* g_tree_node_new                   (gpointer       key,
 104                                                      gpointer       value);
 105 static GTreeNode *g_tree_insert_internal (GTree *tree,
 106                                           gpointer key,
 107                                           gpointer value,
 108                                           gboolean replace);
 109 static gboolean   g_tree_remove_internal            (GTree         *tree,
 110                                                      gconstpointer  key,
 111                                                      gboolean       steal);
 112 static GTreeNode* g_tree_node_balance               (GTreeNode     *node);
 113 static GTreeNode *g_tree_find_node                  (GTree         *tree,
 114                                                      gconstpointer  key);
 115 static gint       g_tree_node_pre_order             (GTreeNode     *node,
 116                                                      GTraverseFunc  traverse_func,
 117                                                      gpointer       data);
 118 static gint       g_tree_node_in_order              (GTreeNode     *node,
 119                                                      GTraverseFunc  traverse_func,
 120                                                      gpointer       data);
 121 static gint       g_tree_node_post_order            (GTreeNode     *node,
 122                                                      GTraverseFunc  traverse_func,
 123                                                      gpointer       data);
 124 static GTreeNode *g_tree_node_search (GTreeNode *node,
 125                                       GCompareFunc search_func,
 126                                       gconstpointer data);
 127 static GTreeNode* g_tree_node_rotate_left           (GTreeNode     *node);
 128 static GTreeNode* g_tree_node_rotate_right          (GTreeNode     *node);
 129 #ifdef G_TREE_DEBUG
 130 static void       g_tree_node_check                 (GTreeNode     *node);
 131 #endif
 132
 133
 134 static GTreeNode*
 135 g_tree_node_new (gpointer key,
 136                  gpointer value)
 137 {
 138   GTreeNode *node = g_slice_new (GTreeNode);
 139
 140   node->balance = 0;
 141   node->left = NULL;
 142   node->right = NULL;
 143   node->left_child = FALSE;
 144   node->right_child = FALSE;
 145   node->key = key;
 146   node->value = value;
 147
 148   return node;
 149 }
 150
 151 /**
 152  * g_tree_new:
 153  * @key_compare_func: the function used to order the nodes in the #GTree.
 154  *   It should return values similar to the standard strcmp() function -
 155  *   0 if the two arguments are equal, a negative value if the first argument
 156  *   comes before the second, or a positive value if the first argument comes
 157  *   after the second.
 158  *
 159  * Creates a new #GTree.
 160  *
 161  * Returns: a newly allocated #GTree
 162  */
 163 GTree *
 164 g_tree_new (GCompareFunc key_compare_func)
 165 {
 166   g_return_val_if_fail (key_compare_func != NULL, NULL);
 167
 168   return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
 169                           NULL, NULL);
 170 }
 171
 172 /**
 173  * g_tree_new_with_data:
 174  * @key_compare_func: qsort()-style comparison function
 175  * @key_compare_data: data to pass to comparison function
 176  *
 177  * Creates a new #GTree with a comparison function that accepts user data.
 178  * See g_tree_new() for more details.
 179  *
 180  * Returns: a newly allocated #GTree
 181  */
 182 GTree *
 183 g_tree_new_with_data (GCompareDataFunc key_compare_func,
 184                       gpointer         key_compare_data)
 185 {
 186   g_return_val_if_fail (key_compare_func != NULL, NULL);
 187
 188   return g_tree_new_full (key_compare_func, key_compare_data,
 189                           NULL, NULL);
 190 }
 191
 192 /**
 193  * g_tree_new_full:
 194  * @key_compare_func: qsort()-style comparison function
 195  * @key_compare_data: data to pass to comparison function
 196  * @key_destroy_func: a function to free the memory allocated for the key
 197  *   used when removing the entry from the #GTree or %NULL if you don't
 198  *   want to supply such a function
 199  * @value_destroy_func: a function to free the memory allocated for the
 200  *   value used when removing the entry from the #GTree or %NULL if you
 201  *   don't want to supply such a function
 202  *
 203  * Creates a new #GTree like g_tree_new() and allows to specify functions
 204  * to free the memory allocated for the key and value that get called when
 205  * removing the entry from the #GTree.
 206  *
 207  * Returns: a newly allocated #GTree
 208  */
 209 GTree *
 210 g_tree_new_full (GCompareDataFunc key_compare_func,
 211                  gpointer         key_compare_data,
 212                  GDestroyNotify   key_destroy_func,
 213                  GDestroyNotify   value_destroy_func)
 214 {
 215   GTree *tree;
 216
 217   g_return_val_if_fail (key_compare_func != NULL, NULL);
 218
 219   tree = g_slice_new (GTree);
 220   tree->root               = NULL;
 221   tree->key_compare        = key_compare_func;
 222   tree->key_destroy_func   = key_destroy_func;
 223   tree->value_destroy_func = value_destroy_func;
 224   tree->key_compare_data   = key_compare_data;
 225   tree->nnodes             = 0;
 226   tree->ref_count          = 1;
 227
 228   return tree;
 229 }
 230
 231 /**
 232  * g_tree_node_first:
 233  * @tree: a #GTree
 234  *
 235  * Returns the first in-order node of the tree, or %NULL
 236  * for an empty tree.
 237  *
 238  * Returns: (nullable) (transfer none): the first node in the tree
 239  *
 240  * Since: 2.68
 241  */
 242 GTreeNode *
 243 g_tree_node_first (GTree *tree)
 244 {
 245   GTreeNode *tmp;
 246
 247   g_return_val_if_fail (tree != NULL, NULL);
 248
 249   if (!tree->root)
 250     return NULL;
 251
 252   tmp = tree->root;
 253
 254   while (tmp->left_child)
 255     tmp = tmp->left;
 256
 257   return tmp;
 258 }
 259
 260 /**
 261  * g_tree_node_last:
 262  * @tree: a #GTree
 263  *
 264  * Returns the last in-order node of the tree, or %NULL
 265  * for an empty tree.
 266  *
 267  * Returns: (nullable) (transfer none): the last node in the tree
 268  *
 269  * Since: 2.68
 270  */
 271 GTreeNode *
 272 g_tree_node_last (GTree *tree)
 273 {
 274   GTreeNode *tmp;
 275
 276   g_return_val_if_fail (tree != NULL, NULL);
 277
 278   if (!tree->root)
 279     return NULL;
 280
 281   tmp = tree->root;
 282
 283   while (tmp->right_child)
 284     tmp = tmp->right;
 285
 286   return tmp;
 287 }
 288
 289 /**
 290  * g_tree_node_previous
 291  * @node: a #GTree node
 292  *
 293  * Returns the previous in-order node of the tree, or %NULL
 294  * if the passed node was already the first one.
 295  *
 296  * Returns: (nullable) (transfer none): the previous node in the tree
 297  *
 298  * Since: 2.68
 299  */
 300 GTreeNode *
 301 g_tree_node_previous (GTreeNode *node)
 302 {
 303   GTreeNode *tmp;
 304
 305   g_return_val_if_fail (node != NULL, NULL);
 306
 307   tmp = node->left;
 308
 309   if (node->left_child)
 310     while (tmp->right_child)
 311       tmp = tmp->right;
 312
 313   return tmp;
 314 }
 315
 316 /**
 317  * g_tree_node_next
 318  * @node: a #GTree node
 319  *
 320  * Returns the next in-order node of the tree, or %NULL
 321  * if the passed node was already the last one.
 322  *
 323  * Returns: (nullable) (transfer none): the next node in the tree
 324  *
 325  * Since: 2.68
 326  */
 327 GTreeNode *
 328 g_tree_node_next (GTreeNode *node)
 329 {
 330   GTreeNode *tmp;
 331
 332   g_return_val_if_fail (node != NULL, NULL);
 333
 334   tmp = node->right;
 335
 336   if (node->right_child)
 337     while (tmp->left_child)
 338       tmp = tmp->left;
 339
 340   return tmp;
 341 }
 342
 343 /**
 344  * g_tree_remove_all:
 345  * @tree: a #GTree
 346  *
 347  * Removes all nodes from a #GTree and destroys their keys and values,
 348  * then resets the #GTree’s root to %NULL.
 349  *
 350  * Since: 2.70
 351  */
 352 void
 353 g_tree_remove_all (GTree *tree)
 354 {
 355   GTreeNode *node;
 356   GTreeNode *next;
 357
 358   g_return_if_fail (tree != NULL);
 359
 360   node = g_tree_node_first (tree);
 361
 362   while (node)
 363     {
 364       next = g_tree_node_next (node);
 365
 366       if (tree->key_destroy_func)
 367         tree->key_destroy_func (node->key);
 368       if (tree->value_destroy_func)
 369         tree->value_destroy_func (node->value);
 370       g_slice_free (GTreeNode, node);
 371
 372 #ifdef G_TREE_DEBUG
 373       g_assert (tree->nnodes > 0);
 374       tree->nnodes--;
 375 #endif
 376
 377       node = next;
 378     }
 379
 380 #ifdef G_TREE_DEBUG
 381   g_assert (tree->nnodes == 0);
 382 #endif
 383
 384   tree->root = NULL;
 385 #ifndef G_TREE_DEBUG
 386   tree->nnodes = 0;
 387 #endif
 388 }
 389
 390 /**
 391  * g_tree_ref:
 392  * @tree: a #GTree
 393  *
 394  * Increments the reference count of @tree by one.
 395  *
 396  * It is safe to call this function from any thread.
 397  *
 398  * Returns: the passed in #GTree
 399  *
 400  * Since: 2.22
 401  */
 402 GTree *
 403 g_tree_ref (GTree *tree)
 404 {
 405   g_return_val_if_fail (tree != NULL, NULL);
 406
 407   g_atomic_int_inc (&tree->ref_count);
 408
 409   return tree;
 410 }
 411
 412 /**
 413  * g_tree_unref:
 414  * @tree: a #GTree
 415  *
 416  * Decrements the reference count of @tree by one.
 417  * If the reference count drops to 0, all keys and values will
 418  * be destroyed (if destroy functions were specified) and all
 419  * memory allocated by @tree will be released.
 420  *
 421  * It is safe to call this function from any thread.
 422  *
 423  * Since: 2.22
 424  */
 425 void
 426 g_tree_unref (GTree *tree)
 427 {
 428   g_return_if_fail (tree != NULL);
 429
 430   if (g_atomic_int_dec_and_test (&tree->ref_count))
 431     {
 432       g_tree_remove_all (tree);
 433       g_slice_free (GTree, tree);
 434     }
 435 }
 436
 437 /**
 438  * g_tree_destroy:
 439  * @tree: a #GTree
 440  *
 441  * Removes all keys and values from the #GTree and decreases its
 442  * reference count by one. If keys and/or values are dynamically
 443  * allocated, you should either free them first or create the #GTree
 444  * using g_tree_new_full(). In the latter case the destroy functions
 445  * you supplied will be called on all keys and values before destroying
 446  * the #GTree.
 447  */
 448 void
 449 g_tree_destroy (GTree *tree)
 450 {
 451   g_return_if_fail (tree != NULL);
 452
 453   g_tree_remove_all (tree);
 454   g_tree_unref (tree);
 455 }
 456
 457 /**
 458  * g_tree_insert_node:
 459  * @tree: a #GTree
 460  * @key: the key to insert
 461  * @value: the value corresponding to the key
 462  *
 463  * Inserts a key/value pair into a #GTree.
 464  *
 465  * If the given key already exists in the #GTree its corresponding value
 466  * is set to the new value. If you supplied a @value_destroy_func when
 467  * creating the #GTree, the old value is freed using that function. If
 468  * you supplied a @key_destroy_func when creating the #GTree, the passed
 469  * key is freed using that function.
 470  *
 471  * The tree is automatically 'balanced' as new key/value pairs are added,
 472  * so that the distance from the root to every leaf is as small as possible.
 473  * The cost of maintaining a balanced tree while inserting new key/value
 474  * result in a O(n log(n)) operation where most of the other operations
 475  * are O(log(n)).
 476  *
 477  * Returns: (transfer none): the inserted (or set) node.
 478  *
 479  * Since: 2.68
 480  */
 481 GTreeNode *
 482 g_tree_insert_node (GTree    *tree,
 483                     gpointer  key,
 484                     gpointer  value)
 485 {
 486   GTreeNode *node;
 487
 488   g_return_val_if_fail (tree != NULL, NULL);
 489
 490   node = g_tree_insert_internal (tree, key, value, FALSE);
 491
 492 #ifdef G_TREE_DEBUG
 493   g_tree_node_check (tree->root);
 494 #endif
 495
 496   return node;
 497 }
 498
 499 /**
 500  * g_tree_insert:
 501  * @tree: a #GTree
 502  * @key: the key to insert
 503  * @value: the value corresponding to the key
 504  *
 505  * Inserts a key/value pair into a #GTree.
 506  *
 507  * Inserts a new key and value into a #GTree as g_tree_insert_node() does,
 508  * only this function does not return the inserted or set node.
 509  */
 510 void
 511 g_tree_insert (GTree    *tree,
 512                gpointer  key,
 513                gpointer  value)
 514 {
 515   g_tree_insert_node (tree, key, value);
 516 }
 517
 518 /**
 519  * g_tree_replace_node:
 520  * @tree: a #GTree
 521  * @key: the key to insert
 522  * @value: the value corresponding to the key
 523  *
 524  * Inserts a new key and value into a #GTree similar to g_tree_insert_node().
 525  * The difference is that if the key already exists in the #GTree, it gets
 526  * replaced by the new key. If you supplied a @value_destroy_func when
 527  * creating the #GTree, the old value is freed using that function. If you
 528  * supplied a @key_destroy_func when creating the #GTree, the old key is
 529  * freed using that function.
 530  *
 531  * The tree is automatically 'balanced' as new key/value pairs are added,
 532  * so that the distance from the root to every leaf is as small as possible.
 533  *
 534  * Returns: (transfer none): the inserted (or set) node.
 535  *
 536  * Since: 2.68
 537  */
 538 GTreeNode *
 539 g_tree_replace_node (GTree    *tree,
 540                      gpointer  key,
 541                      gpointer  value)
 542 {
 543   GTreeNode *node;
 544
 545   g_return_val_if_fail (tree != NULL, NULL);
 546
 547   node = g_tree_insert_internal (tree, key, value, TRUE);
 548
 549 #ifdef G_TREE_DEBUG
 550   g_tree_node_check (tree->root);
 551 #endif
 552
 553   return node;
 554 }
 555
 556 /**
 557  * g_tree_replace:
 558  * @tree: a #GTree
 559  * @key: the key to insert
 560  * @value: the value corresponding to the key
 561  *
 562  * Inserts a new key and value into a #GTree as g_tree_replace_node() does,
 563  * only this function does not return the inserted or set node.
 564  */
 565 void
 566 g_tree_replace (GTree    *tree,
 567                 gpointer  key,
 568                 gpointer  value)
 569 {
 570   g_tree_replace_node (tree, key, value);
 571 }
 572
 573 /* internal insert routine */
 574 static GTreeNode *
 575 g_tree_insert_internal (GTree    *tree,
 576                         gpointer  key,
 577                         gpointer  value,
 578                         gboolean  replace)
 579 {
 580   GTreeNode *node, *retnode;
 581   GTreeNode *path[MAX_GTREE_HEIGHT];
 582   int idx;
 583
 584   g_return_val_if_fail (tree != NULL, NULL);
 585
 586   if (!tree->root)
 587     {
 588       tree->root = g_tree_node_new (key, value);
 589       tree->nnodes++;
 590       return tree->root;
 591     }
 592
 593   idx = 0;
 594   path[idx++] = NULL;
 595   node = tree->root;
 596
 597   while (1)
 598     {
 599       int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
 600
 601       if (cmp == 0)
 602         {
 603           if (tree->value_destroy_func)
 604             tree->value_destroy_func (node->value);
 605
 606           node->value = value;
 607
 608           if (replace)
 609             {
 610               if (tree->key_destroy_func)
 611                 tree->key_destroy_func (node->key);
 612
 613               node->key = key;
 614             }
 615           else
 616             {
 617               /* free the passed key */
 618               if (tree->key_destroy_func)
 619                 tree->key_destroy_func (key);
 620             }
 621
 622           return node;
 623         }
 624       else if (cmp < 0)
 625         {
 626           if (node->left_child)
 627             {
 628               path[idx++] = node;
 629               node = node->left;
 630             }
 631           else
 632             {
 633               GTreeNode *child = g_tree_node_new (key, value);
 634
 635               child->left = node->left;
 636               child->right = node;
 637               node->left = child;
 638               node->left_child = TRUE;
 639               node->balance -= 1;
 640
 641               tree->nnodes++;
 642
 643               retnode = child;
 644               break;
 645             }
 646         }
 647       else
 648         {
 649           if (node->right_child)
 650             {
 651               path[idx++] = node;
 652               node = node->right;
 653             }
 654           else
 655             {
 656               GTreeNode *child = g_tree_node_new (key, value);
 657
 658               child->right = node->right;
 659               child->left = node;
 660               node->right = child;
 661               node->right_child = TRUE;
 662               node->balance += 1;
 663
 664               tree->nnodes++;
 665
 666               retnode = child;
 667               break;
 668             }
 669         }
 670     }
 671
 672   /* Restore balance. This is the goodness of a non-recursive
 673    * implementation, when we are done with balancing we 'break'
 674    * the loop and we are done.
 675    */
 676   while (1)
 677     {
 678       GTreeNode *bparent = path[--idx];
 679       gboolean left_node = (bparent && node == bparent->left);
 680       g_assert (!bparent || bparent->left == node || bparent->right == node);
 681
 682       if (node->balance < -1 || node->balance > 1)
 683         {
 684           node = g_tree_node_balance (node);
 685           if (bparent == NULL)
 686             tree->root = node;
 687           else if (left_node)
 688             bparent->left = node;
 689           else
 690             bparent->right = node;
 691         }
 692
 693       if (node->balance == 0 || bparent == NULL)
 694         break;
 695
 696       if (left_node)
 697         bparent->balance -= 1;
 698       else
 699         bparent->balance += 1;
 700
 701       node = bparent;
 702     }
 703
 704   return retnode;
 705 }
 706
 707 /**
 708  * g_tree_remove:
 709  * @tree: a #GTree
 710  * @key: the key to remove
 711  *
 712  * Removes a key/value pair from a #GTree.
 713  *
 714  * If the #GTree was created using g_tree_new_full(), the key and value
 715  * are freed using the supplied destroy functions, otherwise you have to
 716  * make sure that any dynamically allocated values are freed yourself.
 717  * If the key does not exist in the #GTree, the function does nothing.
 718  *
 719  * The cost of maintaining a balanced tree while removing a key/value
 720  * result in a O(n log(n)) operation where most of the other operations
 721  * are O(log(n)).
 722  *
 723  * Returns: %TRUE if the key was found (prior to 2.8, this function
 724  *     returned nothing)
 725  */
 726 gboolean
 727 g_tree_remove (GTree         *tree,
 728                gconstpointer  key)
 729 {
 730   gboolean removed;
 731
 732   g_return_val_if_fail (tree != NULL, FALSE);
 733
 734   removed = g_tree_remove_internal (tree, key, FALSE);
 735
 736 #ifdef G_TREE_DEBUG
 737   g_tree_node_check (tree->root);
 738 #endif
 739
 740   return removed;
 741 }
 742
 743 /**
 744  * g_tree_steal:
 745  * @tree: a #GTree
 746  * @key: the key to remove
 747  *
 748  * Removes a key and its associated value from a #GTree without calling
 749  * the key and value destroy functions.
 750  *
 751  * If the key does not exist in the #GTree, the function does nothing.
 752  *
 753  * Returns: %TRUE if the key was found (prior to 2.8, this function
 754  *     returned nothing)
 755  */
 756 gboolean
 757 g_tree_steal (GTree         *tree,
 758               gconstpointer  key)
 759 {
 760   gboolean removed;
 761
 762   g_return_val_if_fail (tree != NULL, FALSE);
 763
 764   removed = g_tree_remove_internal (tree, key, TRUE);
 765
 766 #ifdef G_TREE_DEBUG
 767   g_tree_node_check (tree->root);
 768 #endif
 769
 770   return removed;
 771 }
 772
 773 /* internal remove routine */
 774 static gboolean
 775 g_tree_remove_internal (GTree         *tree,
 776                         gconstpointer  key,
 777                         gboolean       steal)
 778 {
 779   GTreeNode *node, *parent, *balance;
 780   GTreeNode *path[MAX_GTREE_HEIGHT];
 781   int idx;
 782   gboolean left_node;
 783
 784   g_return_val_if_fail (tree != NULL, FALSE);
 785
 786   if (!tree->root)
 787     return FALSE;
 788
 789   idx = 0;
 790   path[idx++] = NULL;
 791   node = tree->root;
 792
 793   while (1)
 794     {
 795       int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
 796
 797       if (cmp == 0)
 798         break;
 799       else if (cmp < 0)
 800         {
 801           if (!node->left_child)
 802             return FALSE;
 803
 804           path[idx++] = node;
 805           node = node->left;
 806         }
 807       else
 808         {
 809           if (!node->right_child)
 810             return FALSE;
 811
 812           path[idx++] = node;
 813           node = node->right;
 814         }
 815     }
 816
 817   /* The following code is almost equal to g_tree_remove_node,
 818    * except that we do not have to call g_tree_node_parent.
 819    */
 820   balance = parent = path[--idx];
 821   g_assert (!parent || parent->left == node || parent->right == node);
 822   left_node = (parent && node == parent->left);
 823
 824   if (!node->left_child)
 825     {
 826       if (!node->right_child)
 827         {
 828           if (!parent)
 829             tree->root = NULL;
 830           else if (left_node)
 831             {
 832               parent->left_child = FALSE;
 833               parent->left = node->left;
 834               parent->balance += 1;
 835             }
 836           else
 837             {
 838               parent->right_child = FALSE;
 839               parent->right = node->right;
 840               parent->balance -= 1;
 841             }
 842         }
 843       else /* node has a right child */
 844         {
 845           GTreeNode *tmp = g_tree_node_next (node);
 846           tmp->left = node->left;
 847
 848           if (!parent)
 849             tree->root = node->right;
 850           else if (left_node)
 851             {
 852               parent->left = node->right;
 853               parent->balance += 1;
 854             }
 855           else
 856             {
 857               parent->right = node->right;
 858               parent->balance -= 1;
 859             }
 860         }
 861     }
 862   else /* node has a left child */
 863     {
 864       if (!node->right_child)
 865         {
 866           GTreeNode *tmp = g_tree_node_previous (node);
 867           tmp->right = node->right;
 868
 869           if (parent == NULL)
 870             tree->root = node->left;
 871           else if (left_node)
 872             {
 873               parent->left = node->left;
 874               parent->balance += 1;
 875             }
 876           else
 877             {
 878               parent->right = node->left;
 879               parent->balance -= 1;
 880             }
 881         }
 882       else /* node has a both children (pant, pant!) */
 883         {
 884           GTreeNode *prev = node->left;
 885           GTreeNode *next = node->right;
 886           GTreeNode *nextp = node;
 887           int old_idx = idx + 1;
 888           idx++;
 889
 890           /* path[idx] == parent */
 891           /* find the immediately next node (and its parent) */
 892           while (next->left_child)
 893             {
 894               path[++idx] = nextp = next;
 895               next = next->left;
 896             }
 897
 898           path[old_idx] = next;
 899           balance = path[idx];
 900
 901           /* remove 'next' from the tree */
 902           if (nextp != node)
 903             {
 904               if (next->right_child)
 905                 nextp->left = next->right;
 906               else
 907                 nextp->left_child = FALSE;
 908               nextp->balance += 1;
 909
 910               next->right_child = TRUE;
 911               next->right = node->right;
 912             }
 913           else
 914             node->balance -= 1;
 915
 916           /* set the prev to point to the right place */
 917           while (prev->right_child)
 918             prev = prev->right;
 919           prev->right = next;
 920
 921           /* prepare 'next' to replace 'node' */
 922           next->left_child = TRUE;
 923           next->left = node->left;
 924           next->balance = node->balance;
 925
 926           if (!parent)
 927             tree->root = next;
 928           else if (left_node)
 929             parent->left = next;
 930           else
 931             parent->right = next;
 932         }
 933     }
 934
 935   /* restore balance */
 936   if (balance)
 937     while (1)
 938       {
 939         GTreeNode *bparent = path[--idx];
 940         g_assert (!bparent || bparent->left == balance || bparent->right == balance);
 941         left_node = (bparent && balance == bparent->left);
 942
 943         if(balance->balance < -1 || balance->balance > 1)
 944           {
 945             balance = g_tree_node_balance (balance);
 946             if (!bparent)
 947               tree->root = balance;
 948             else if (left_node)
 949               bparent->left = balance;
 950             else
 951               bparent->right = balance;
 952           }
 953
 954         if (balance->balance != 0 || !bparent)
 955           break;
 956
 957         if (left_node)
 958           bparent->balance += 1;
 959         else
 960           bparent->balance -= 1;
 961
 962         balance = bparent;
 963       }
 964
 965   if (!steal)
 966     {
 967       if (tree->key_destroy_func)
 968         tree->key_destroy_func (node->key);
 969       if (tree->value_destroy_func)
 970         tree->value_destroy_func (node->value);
 971     }
 972
 973   g_slice_free (GTreeNode, node);
 974
 975   tree->nnodes--;
 976
 977   return TRUE;
 978 }
 979
 980 /**
 981  * g_tree_node_key:
 982  * @node: a #GTree node
 983  *
 984  * Gets the key stored at a particular tree node.
 985  *
 986  * Returns: (nullable) (transfer none): the key at the node.
 987  *
 988  * Since: 2.68
 989  */
 990 gpointer
 991 g_tree_node_key (GTreeNode *node)
 992 {
 993   g_return_val_if_fail (node != NULL, NULL);
 994
 995   return node->key;
 996 }
 997
 998 /**
 999  * g_tree_node_value:
1000  * @node: a #GTree node
1001  *
1002  * Gets the value stored at a particular tree node.
1003  *
1004  * Returns: (nullable) (transfer none): the value at the node.
1005  *
1006  * Since: 2.68
1007  */
1008 gpointer
1009 g_tree_node_value (GTreeNode *node)
1010 {
1011   g_return_val_if_fail (node != NULL, NULL);
1012
1013   return node->value;
1014 }
1015
1016 /**
1017  * g_tree_lookup_node:
1018  * @tree: a #GTree
1019  * @key: the key to look up
1020  *
1021  * Gets the tree node corresponding to the given key. Since a #GTree is
1022  * automatically balanced as key/value pairs are added, key lookup
1023  * is O(log n) (where n is the number of key/value pairs in the tree).
1024  *
1025  * Returns: (nullable) (transfer none): the tree node corresponding to
1026  *          the key, or %NULL if the key was not found
1027  *
1028  * Since: 2.68
1029  */
1030 GTreeNode *
1031 g_tree_lookup_node (GTree         *tree,
1032                     gconstpointer  key)
1033 {
1034   g_return_val_if_fail (tree != NULL, NULL);
1035
1036   return g_tree_find_node (tree, key);
1037 }
1038
1039 /**
1040  * g_tree_lookup:
1041  * @tree: a #GTree
1042  * @key: the key to look up
1043  *
1044  * Gets the value corresponding to the given key. Since a #GTree is
1045  * automatically balanced as key/value pairs are added, key lookup
1046  * is O(log n) (where n is the number of key/value pairs in the tree).
1047  *
1048  * Returns: the value corresponding to the key, or %NULL
1049  *     if the key was not found
1050  */
1051 gpointer
1052 g_tree_lookup (GTree         *tree,
1053                gconstpointer  key)
1054 {
1055   GTreeNode *node;
1056
1057   node = g_tree_lookup_node (tree, key);
1058
1059   return node ? node->value : NULL;
1060 }
1061
1062 /**
1063  * g_tree_lookup_extended:
1064  * @tree: a #GTree
1065  * @lookup_key: the key to look up
1066  * @orig_key: (out) (optional) (nullable): returns the original key
1067  * @value: (out) (optional) (nullable): returns the value associated with the key
1068  *
1069  * Looks up a key in the #GTree, returning the original key and the
1070  * associated value. This is useful if you need to free the memory
1071  * allocated for the original key, for example before calling
1072  * g_tree_remove().
1073  *
1074  * Returns: %TRUE if the key was found in the #GTree
1075  */
1076 gboolean
1077 g_tree_lookup_extended (GTree         *tree,
1078                         gconstpointer  lookup_key,
1079                         gpointer      *orig_key,
1080                         gpointer      *value)
1081 {
1082   GTreeNode *node;
1083
1084   g_return_val_if_fail (tree != NULL, FALSE);
1085
1086   node = g_tree_find_node (tree, lookup_key);
1087
1088   if (node)
1089     {
1090       if (orig_key)
1091         *orig_key = node->key;
1092       if (value)
1093         *value = node->value;
1094       return TRUE;
1095     }
1096   else
1097     return FALSE;
1098 }
1099
1100 /**
1101  * g_tree_foreach:
1102  * @tree: a #GTree
1103  * @func: the function to call for each node visited.
1104  *     If this function returns %TRUE, the traversal is stopped.
1105  * @user_data: user data to pass to the function
1106  *
1107  * Calls the given function for each of the key/value pairs in the #GTree.
1108  * The function is passed the key and value of each pair, and the given
1109  * @data parameter. The tree is traversed in sorted order.
1110  *
1111  * The tree may not be modified while iterating over it (you can't
1112  * add/remove items). To remove all items matching a predicate, you need
1113  * to add each item to a list in your #GTraverseFunc as you walk over
1114  * the tree, then walk the list and remove each item.
1115  */
1116 void
1117 g_tree_foreach (GTree         *tree,
1118                 GTraverseFunc  func,
1119                 gpointer       user_data)
1120 {
1121   GTreeNode *node;
1122
1123   g_return_if_fail (tree != NULL);
1124
1125   if (!tree->root)
1126     return;
1127
1128   node = g_tree_node_first (tree);
1129
1130   while (node)
1131     {
1132       if ((*func) (node->key, node->value, user_data))
1133         break;
1134
1135       node = g_tree_node_next (node);
1136     }
1137 }
1138
1139 /**
1140  * g_tree_foreach_node:
1141  * @tree: a #GTree
1142  * @func: the function to call for each node visited.
1143  *     If this function returns %TRUE, the traversal is stopped.
1144  * @user_data: user data to pass to the function
1145  *
1146  * Calls the given function for each of the nodes in the #GTree.
1147  * The function is passed the pointer to the particular node, and the given
1148  * @data parameter. The tree traversal happens in-order.
1149  *
1150  * The tree may not be modified while iterating over it (you can't
1151  * add/remove items). To remove all items matching a predicate, you need
1152  * to add each item to a list in your #GTraverseFunc as you walk over
1153  * the tree, then walk the list and remove each item.
1154  *
1155  * Since: 2.68
1156  */
1157 void
1158 g_tree_foreach_node (GTree             *tree,
1159                      GTraverseNodeFunc  func,
1160                      gpointer           user_data)
1161 {
1162   GTreeNode *node;
1163
1164   g_return_if_fail (tree != NULL);
1165
1166   if (!tree->root)
1167     return;
1168
1169   node = g_tree_node_first (tree);
1170
1171   while (node)
1172     {
1173       if ((*func) (node, user_data))
1174         break;
1175
1176       node = g_tree_node_next (node);
1177     }
1178 }
1179
1180 /**
1181  * g_tree_traverse:
1182  * @tree: a #GTree
1183  * @traverse_func: the function to call for each node visited. If this
1184  *   function returns %TRUE, the traversal is stopped.
1185  * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
1186  *   %G_PRE_ORDER and %G_POST_ORDER
1187  * @user_data: user data to pass to the function
1188  *
1189  * Calls the given function for each node in the #GTree.
1190  *
1191  * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary.
1192  *     If you just want to visit all nodes in sorted order, use
1193  *     g_tree_foreach() instead. If you really need to visit nodes in
1194  *     a different order, consider using an [n-ary tree][glib-N-ary-Trees].
1195  */
1196 /**
1197  * GTraverseFunc:
1198  * @key: a key of a #GTree node
1199  * @value: the value corresponding to the key
1200  * @user_data: user data passed to g_tree_traverse()
1201  *
1202  * Specifies the type of function passed to g_tree_traverse(). It is
1203  * passed the key and value of each node, together with the @user_data
1204  * parameter passed to g_tree_traverse(). If the function returns
1205  * %TRUE, the traversal is stopped.
1206  *
1207  * Returns: %TRUE to stop the traversal
1208  */
1209 void
1210 g_tree_traverse (GTree         *tree,
1211                  GTraverseFunc  traverse_func,
1212                  GTraverseType  traverse_type,
1213                  gpointer       user_data)
1214 {
1215   g_return_if_fail (tree != NULL);
1216
1217   if (!tree->root)
1218     return;
1219
1220   switch (traverse_type)
1221     {
1222     case G_PRE_ORDER:
1223       g_tree_node_pre_order (tree->root, traverse_func, user_data);
1224       break;
1225
1226     case G_IN_ORDER:
1227       g_tree_node_in_order (tree->root, traverse_func, user_data);
1228       break;
1229
1230     case G_POST_ORDER:
1231       g_tree_node_post_order (tree->root, traverse_func, user_data);
1232       break;
1233
1234     case G_LEVEL_ORDER:
1235       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
1236       break;
1237     }
1238 }
1239
1240 /**
1241  * g_tree_search_node:
1242  * @tree: a #GTree
1243  * @search_func: a function used to search the #GTree
1244  * @user_data: the data passed as the second argument to @search_func
1245  *
1246  * Searches a #GTree using @search_func.
1247  *
1248  * The @search_func is called with a pointer to the key of a key/value
1249  * pair in the tree, and the passed in @user_data. If @search_func returns
1250  * 0 for a key/value pair, then the corresponding node is returned as
1251  * the result of g_tree_search(). If @search_func returns -1, searching
1252  * will proceed among the key/value pairs that have a smaller key; if
1253  * @search_func returns 1, searching will proceed among the key/value
1254  * pairs that have a larger key.
1255  *
1256  * Returns: (nullable) (transfer none): the node corresponding to the
1257  *          found key, or %NULL if the key was not found
1258  *
1259  * Since: 2.68
1260  */
1261 GTreeNode *
1262 g_tree_search_node (GTree         *tree,
1263                     GCompareFunc   search_func,
1264                     gconstpointer  user_data)
1265 {
1266   g_return_val_if_fail (tree != NULL, NULL);
1267
1268   if (!tree->root)
1269     return NULL;
1270
1271   return g_tree_node_search (tree->root, search_func, user_data);
1272 }
1273
1274 /**
1275  * g_tree_search:
1276  * @tree: a #GTree
1277  * @search_func: a function used to search the #GTree
1278  * @user_data: the data passed as the second argument to @search_func
1279  *
1280  * Searches a #GTree using @search_func.
1281  *
1282  * The @search_func is called with a pointer to the key of a key/value
1283  * pair in the tree, and the passed in @user_data. If @search_func returns
1284  * 0 for a key/value pair, then the corresponding value is returned as
1285  * the result of g_tree_search(). If @search_func returns -1, searching
1286  * will proceed among the key/value pairs that have a smaller key; if
1287  * @search_func returns 1, searching will proceed among the key/value
1288  * pairs that have a larger key.
1289  *
1290  * Returns: the value corresponding to the found key, or %NULL
1291  *     if the key was not found
1292  */
1293 gpointer
1294 g_tree_search (GTree         *tree,
1295                GCompareFunc   search_func,
1296                gconstpointer  user_data)
1297 {
1298   GTreeNode *node;
1299
1300   node = g_tree_search_node (tree, search_func, user_data);
1301
1302   return node ? node->value : NULL;
1303 }
1304
1305 /**
1306  * g_tree_lower_bound:
1307  * @tree: a #GTree
1308  * @key: the key to calculate the lower bound for
1309  *
1310  * Gets the lower bound node corresponding to the given key,
1311  * or %NULL if the tree is empty or all the nodes in the tree
1312  * have keys that are strictly lower than the searched key.
1313  *
1314  * The lower bound is the first node that has its key greater
1315  * than or equal to the searched key.
1316  *
1317  * Returns: (nullable) (transfer none): the tree node corresponding to
1318  *          the lower bound, or %NULL if the tree is empty or has only
1319  *          keys strictly lower than the searched key.
1320  *
1321  * Since: 2.68
1322  */
1323 GTreeNode *
1324 g_tree_lower_bound (GTree         *tree,
1325                     gconstpointer  key)
1326 {
1327   GTreeNode *node, *result;
1328   gint cmp;
1329
1330   g_return_val_if_fail (tree != NULL, NULL);
1331
1332   node = tree->root;
1333   if (!node)
1334     return NULL;
1335
1336   result = NULL;
1337   while (1)
1338     {
1339       cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1340       if (cmp <= 0)
1341         {
1342           result = node;
1343
1344           if (!node->left_child)
1345             return result;
1346
1347           node = node->left;
1348         }
1349       else
1350         {
1351           if (!node->right_child)
1352             return result;
1353
1354           node = node->right;
1355         }
1356     }
1357 }
1358
1359 /**
1360  * g_tree_upper_bound:
1361  * @tree: a #GTree
1362  * @key: the key to calculate the upper bound for
1363  *
1364  * Gets the upper bound node corresponding to the given key,
1365  * or %NULL if the tree is empty or all the nodes in the tree
1366  * have keys that are lower than or equal to the searched key.
1367  *
1368  * The upper bound is the first node that has its key strictly greater
1369  * than the searched key.
1370  *
1371  * Returns: (nullable) (transfer none): the tree node corresponding to the
1372  *          upper bound, or %NULL if the tree is empty or has only keys
1373  *          lower than or equal to the searched key.
1374  *
1375  * Since: 2.68
1376  */
1377 GTreeNode *
1378 g_tree_upper_bound (GTree         *tree,
1379                     gconstpointer  key)
1380 {
1381   GTreeNode *node, *result;
1382   gint cmp;
1383
1384   g_return_val_if_fail (tree != NULL, NULL);
1385
1386   node = tree->root;
1387   if (!node)
1388     return NULL;
1389
1390   result = NULL;
1391   while (1)
1392     {
1393       cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1394       if (cmp < 0)
1395         {
1396           result = node;
1397
1398           if (!node->left_child)
1399             return result;
1400
1401           node = node->left;
1402         }
1403       else
1404         {
1405           if (!node->right_child)
1406             return result;
1407
1408           node = node->right;
1409         }
1410     }
1411 }
1412
1413 /**
1414  * g_tree_height:
1415  * @tree: a #GTree
1416  *
1417  * Gets the height of a #GTree.
1418  *
1419  * If the #GTree contains no nodes, the height is 0.
1420  * If the #GTree contains only one root node the height is 1.
1421  * If the root node has children the height is 2, etc.
1422  *
1423  * Returns: the height of @tree
1424  */
1425 gint
1426 g_tree_height (GTree *tree)
1427 {
1428   GTreeNode *node;
1429   gint height;
1430
1431   g_return_val_if_fail (tree != NULL, 0);
1432
1433   if (!tree->root)
1434     return 0;
1435
1436   height = 0;
1437   node = tree->root;
1438
1439   while (1)
1440     {
1441       height += 1 + MAX(node->balance, 0);
1442
1443       if (!node->left_child)
1444         return height;
1445
1446       node = node->left;
1447     }
1448 }
1449
1450 /**
1451  * g_tree_nnodes:
1452  * @tree: a #GTree
1453  *
1454  * Gets the number of nodes in a #GTree.
1455  *
1456  * Returns: the number of nodes in @tree
1457  */
1458 gint
1459 g_tree_nnodes (GTree *tree)
1460 {
1461   g_return_val_if_fail (tree != NULL, 0);
1462
1463   return tree->nnodes;
1464 }
1465
1466 static GTreeNode *
1467 g_tree_node_balance (GTreeNode *node)
1468 {
1469   if (node->balance < -1)
1470     {
1471       if (node->left->balance > 0)
1472         node->left = g_tree_node_rotate_left (node->left);
1473       node = g_tree_node_rotate_right (node);
1474     }
1475   else if (node->balance > 1)
1476     {
1477       if (node->right->balance < 0)
1478         node->right = g_tree_node_rotate_right (node->right);
1479       node = g_tree_node_rotate_left (node);
1480     }
1481
1482   return node;
1483 }
1484
1485 static GTreeNode *
1486 g_tree_find_node (GTree        *tree,
1487                   gconstpointer key)
1488 {
1489   GTreeNode *node;
1490   gint cmp;
1491
1492   node = tree->root;
1493   if (!node)
1494     return NULL;
1495
1496   while (1)
1497     {
1498       cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1499       if (cmp == 0)
1500         return node;
1501       else if (cmp < 0)
1502         {
1503           if (!node->left_child)
1504             return NULL;
1505
1506           node = node->left;
1507         }
1508       else
1509         {
1510           if (!node->right_child)
1511             return NULL;
1512
1513           node = node->right;
1514         }
1515     }
1516 }
1517
1518 static gint
1519 g_tree_node_pre_order (GTreeNode     *node,
1520                        GTraverseFunc  traverse_func,
1521                        gpointer       data)
1522 {
1523   if ((*traverse_func) (node->key, node->value, data))
1524     return TRUE;
1525
1526   if (node->left_child)
1527     {
1528       if (g_tree_node_pre_order (node->left, traverse_func, data))
1529         return TRUE;
1530     }
1531
1532   if (node->right_child)
1533     {
1534       if (g_tree_node_pre_order (node->right, traverse_func, data))
1535         return TRUE;
1536     }
1537
1538   return FALSE;
1539 }
1540
1541 static gint
1542 g_tree_node_in_order (GTreeNode     *node,
1543                       GTraverseFunc  traverse_func,
1544                       gpointer       data)
1545 {
1546   if (node->left_child)
1547     {
1548       if (g_tree_node_in_order (node->left, traverse_func, data))
1549         return TRUE;
1550     }
1551
1552   if ((*traverse_func) (node->key, node->value, data))
1553     return TRUE;
1554
1555   if (node->right_child)
1556     {
1557       if (g_tree_node_in_order (node->right, traverse_func, data))
1558         return TRUE;
1559     }
1560
1561   return FALSE;
1562 }
1563
1564 static gint
1565 g_tree_node_post_order (GTreeNode     *node,
1566                         GTraverseFunc  traverse_func,
1567                         gpointer       data)
1568 {
1569   if (node->left_child)
1570     {
1571       if (g_tree_node_post_order (node->left, traverse_func, data))
1572         return TRUE;
1573     }
1574
1575   if (node->right_child)
1576     {
1577       if (g_tree_node_post_order (node->right, traverse_func, data))
1578         return TRUE;
1579     }
1580
1581   if ((*traverse_func) (node->key, node->value, data))
1582     return TRUE;
1583
1584   return FALSE;
1585 }
1586
1587 static GTreeNode *
1588 g_tree_node_search (GTreeNode     *node,
1589                     GCompareFunc   search_func,
1590                     gconstpointer  data)
1591 {
1592   gint dir;
1593
1594   if (!node)
1595     return NULL;
1596
1597   while (1)
1598     {
1599       dir = (* search_func) (node->key, data);
1600       if (dir == 0)
1601         return node;
1602       else if (dir < 0)
1603         {
1604           if (!node->left_child)
1605             return NULL;
1606
1607           node = node->left;
1608         }
1609       else
1610         {
1611           if (!node->right_child)
1612             return NULL;
1613
1614           node = node->right;
1615         }
1616     }
1617 }
1618
1619 static GTreeNode *
1620 g_tree_node_rotate_left (GTreeNode *node)
1621 {
1622   GTreeNode *right;
1623   gint a_bal;
1624   gint b_bal;
1625
1626   right = node->right;
1627
1628   if (right->left_child)
1629     node->right = right->left;
1630   else
1631     {
1632       node->right_child = FALSE;
1633       right->left_child = TRUE;
1634     }
1635   right->left = node;
1636
1637   a_bal = node->balance;
1638   b_bal = right->balance;
1639
1640   if (b_bal <= 0)
1641     {
1642       if (a_bal >= 1)
1643         right->balance = b_bal - 1;
1644       else
1645         right->balance = a_bal + b_bal - 2;
1646       node->balance = a_bal - 1;
1647     }
1648   else
1649     {
1650       if (a_bal <= b_bal)
1651         right->balance = a_bal - 2;
1652       else
1653         right->balance = b_bal - 1;
1654       node->balance = a_bal - b_bal - 1;
1655     }
1656
1657   return right;
1658 }
1659
1660 static GTreeNode *
1661 g_tree_node_rotate_right (GTreeNode *node)
1662 {
1663   GTreeNode *left;
1664   gint a_bal;
1665   gint b_bal;
1666
1667   left = node->left;
1668
1669   if (left->right_child)
1670     node->left = left->right;
1671   else
1672     {
1673       node->left_child = FALSE;
1674       left->right_child = TRUE;
1675     }
1676   left->right = node;
1677
1678   a_bal = node->balance;
1679   b_bal = left->balance;
1680
1681   if (b_bal <= 0)
1682     {
1683       if (b_bal > a_bal)
1684         left->balance = b_bal + 1;
1685       else
1686         left->balance = a_bal + 2;
1687       node->balance = a_bal - b_bal + 1;
1688     }
1689   else
1690     {
1691       if (a_bal <= -1)
1692         left->balance = b_bal + 1;
1693       else
1694         left->balance = a_bal + b_bal + 2;
1695       node->balance = a_bal + 1;
1696     }
1697
1698   return left;
1699 }
1700
1701 #ifdef G_TREE_DEBUG
1702 static gint
1703 g_tree_node_height (GTreeNode *node)
1704 {
1705   gint left_height;
1706   gint right_height;
1707
1708   if (node)
1709     {
1710       left_height = 0;
1711       right_height = 0;
1712
1713       if (node->left_child)
1714         left_height = g_tree_node_height (node->left);
1715
1716       if (node->right_child)
1717         right_height = g_tree_node_height (node->right);
1718
1719       return MAX (left_height, right_height) + 1;
1720     }
1721
1722   return 0;
1723 }
1724
1725 static void
1726 g_tree_node_check (GTreeNode *node)
1727 {
1728   gint left_height;
1729   gint right_height;
1730   gint balance;
1731   GTreeNode *tmp;
1732
1733   if (node)
1734     {
1735       if (node->left_child)
1736         {
1737           tmp = g_tree_node_previous (node);
1738           g_assert (tmp->right == node);
1739         }
1740
1741       if (node->right_child)
1742         {
1743           tmp = g_tree_node_next (node);
1744           g_assert (tmp->left == node);
1745         }
1746
1747       left_height = 0;
1748       right_height = 0;
1749
1750       if (node->left_child)
1751         left_height = g_tree_node_height (node->left);
1752       if (node->right_child)
1753         right_height = g_tree_node_height (node->right);
1754
1755       balance = right_height - left_height;
1756       g_assert (balance == node->balance);
1757
1758       if (node->left_child)
1759         g_tree_node_check (node->left);
1760       if (node->right_child)
1761         g_tree_node_check (node->right);
1762     }
1763 }
1764
1765 static void
1766 g_tree_node_dump (GTreeNode *node,
1767                   gint       indent)
1768 {
1769   g_print ("%*s%c\n", indent, "", *(char *)node->key);
1770
1771   if (node->left_child)
1772     {
1773       g_print ("%*sLEFT\n", indent, "");
1774       g_tree_node_dump (node->left, indent + 2);
1775     }
1776   else if (node->left)
1777     g_print ("%*s<%c\n", indent + 2, "", *(char *)node->left->key);
1778
1779   if (node->right_child)
1780     {
1781       g_print ("%*sRIGHT\n", indent, "");
1782       g_tree_node_dump (node->right, indent + 2);
1783     }
1784   else if (node->right)
1785     g_print ("%*s>%c\n", indent + 2, "", *(char *)node->right->key);
1786 }
1787
1788 void
1789 g_tree_dump (GTree *tree)
1790 {
1791   if (tree->root)
1792     g_tree_node_dump (tree->root, 0);
1793 }
1794 #endif