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