glib/gtree.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 /*
  21  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  22  * file for a list of people on the GLib Team.  See the ChangeLog
  23  * files for a list of changes.  These files are distributed with
  24  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  25  */
  26
  27 /*
  28  * MT safe
  29  */
  30
  31 #include "config.h"
  32
  33 #include "glib.h"
  34
  35 /**
  36  * SECTION: trees-binary
  37  * @title: Balanced Binary Trees
  38  * @short_description: a sorted collection of key/value pairs optimized
  39  *                     for searching and traversing in order
  40  *
  41  * The #GTree structure and its associated functions provide a sorted
  42  * collection of key/value pairs optimized for searching and traversing
  43  * in order.
  44  *
  45  * To create a new #GTree use g_tree_new().
  46  *
  47  * To insert a key/value pair into a #GTree use g_tree_insert().
  48  *
  49  * To lookup the value corresponding to a given key, use
  50  * g_tree_lookup() and g_tree_lookup_extended().
  51  *
  52  * To find out the number of nodes in a #GTree, use g_tree_nnodes(). To
  53  * get the height of a #GTree, use g_tree_height().
  54  *
  55  * To traverse a #GTree, calling a function for each node visited in
  56  * the traversal, use g_tree_foreach().
  57  *
  58  * To remove a key/value pair use g_tree_remove().
  59  *
  60  * To destroy a #GTree, use g_tree_destroy().
  61  **/
  62
  63 #undef G_TREE_DEBUG
  64
  65 #define MAX_GTREE_HEIGHT 40
  66
  67 typedef struct _GTreeNode  GTreeNode;
  68
  69 /**
  70  * GTree:
  71  *
  72  * The <structname>GTree</structname> struct is an opaque data
  73  * structure representing a <link
  74  * linkend="glib-Balanced-Binary-Trees">Balanced Binary Tree</link>. It
  75  * should be accessed only by using the following functions.
  76  **/
  77 struct _GTree
  78 {
  79   GTreeNode        *root;
  80   GCompareDataFunc  key_compare;
  81   GDestroyNotify    key_destroy_func;
  82   GDestroyNotify    value_destroy_func;
  83   gpointer          key_compare_data;
  84   guint             nnodes;
  85   gint              ref_count;
  86 };
  87
  88 struct _GTreeNode
  89 {
  90   gpointer   key;         /* key for this node */
  91   gpointer   value;       /* value stored at this node */
  92   GTreeNode *left;        /* left subtree */
  93   GTreeNode *right;       /* right subtree */
  94   gint8      balance;     /* height (left) - height (right) */
  95   guint8     left_child;
  96   guint8     right_child;
  97 };
  98
  99
 100 static GTreeNode* g_tree_node_new                   (gpointer       key,
 101                                                      gpointer       value);
 102 static void       g_tree_insert_internal            (GTree         *tree,
 103                                                      gpointer       key,
 104                                                      gpointer       value,
 105                                                      gboolean       replace);
 106 static gboolean   g_tree_remove_internal            (GTree         *tree,
 107                                                      gconstpointer  key,
 108                                                      gboolean       steal);
 109 static GTreeNode* g_tree_node_balance               (GTreeNode     *node);
 110 static GTreeNode *g_tree_find_node                  (GTree         *tree,
 111                                                      gconstpointer  key);
 112 static gint       g_tree_node_pre_order             (GTreeNode     *node,
 113                                                      GTraverseFunc  traverse_func,
 114                                                      gpointer       data);
 115 static gint       g_tree_node_in_order              (GTreeNode     *node,
 116                                                      GTraverseFunc  traverse_func,
 117                                                      gpointer       data);
 118 static gint       g_tree_node_post_order            (GTreeNode     *node,
 119                                                      GTraverseFunc  traverse_func,
 120                                                      gpointer       data);
 121 static gpointer   g_tree_node_search                (GTreeNode     *node,
 122                                                      GCompareFunc   search_func,
 123                                                      gconstpointer  data);
 124 static GTreeNode* g_tree_node_rotate_left           (GTreeNode     *node);
 125 static GTreeNode* g_tree_node_rotate_right          (GTreeNode     *node);
 126 #ifdef G_TREE_DEBUG
 127 static void       g_tree_node_check                 (GTreeNode     *node);
 128 #endif
 129
 130
 131 static GTreeNode*
 132 g_tree_node_new (gpointer key,
 133                  gpointer value)
 134 {
 135   GTreeNode *node = g_slice_new (GTreeNode);
 136
 137   node->balance = 0;
 138   node->left = NULL;
 139   node->right = NULL;
 140   node->left_child = FALSE;
 141   node->right_child = FALSE;
 142   node->key = key;
 143   node->value = value;
 144
 145   return node;
 146 }
 147
 148 /**
 149  * g_tree_new:
 150  * @key_compare_func: the function used to order the nodes in the #GTree.
 151  *   It should return values similar to the standard strcmp() function -
 152  *   0 if the two arguments are equal, a negative value if the first argument
 153  *   comes before the second, or a positive value if the first argument comes
 154  *   after the second.
 155  *
 156  * Creates a new #GTree.
 157  *
 158  * Return value: a new #GTree.
 159  **/
 160 GTree*
 161 g_tree_new (GCompareFunc key_compare_func)
 162 {
 163   g_return_val_if_fail (key_compare_func != NULL, NULL);
 164
 165   return g_tree_new_full ((GCompareDataFunc) key_compare_func, NULL,
 166                           NULL, NULL);
 167 }
 168
 169 /**
 170  * g_tree_new_with_data:
 171  * @key_compare_func: qsort()-style comparison function.
 172  * @key_compare_data: data to pass to comparison function.
 173  *
 174  * Creates a new #GTree with a comparison function that accepts user data.
 175  * See g_tree_new() for more details.
 176  *
 177  * Return value: a new #GTree.
 178  **/
 179 GTree*
 180 g_tree_new_with_data (GCompareDataFunc key_compare_func,
 181                       gpointer         key_compare_data)
 182 {
 183   g_return_val_if_fail (key_compare_func != NULL, NULL);
 184
 185   return g_tree_new_full (key_compare_func, key_compare_data,
 186                           NULL, NULL);
 187 }
 188
 189 /**
 190  * g_tree_new_full:
 191  * @key_compare_func: qsort()-style comparison function.
 192  * @key_compare_data: data to pass to comparison function.
 193  * @key_destroy_func: a function to free the memory allocated for the key
 194  *   used when removing the entry from the #GTree or %NULL if you don't
 195  *   want to supply such a function.
 196  * @value_destroy_func: a function to free the memory allocated for the
 197  *   value used when removing the entry from the #GTree or %NULL if you
 198  *   don't want to supply such a function.
 199  *
 200  * Creates a new #GTree like g_tree_new() and allows to specify functions
 201  * to free the memory allocated for the key and value that get called when
 202  * removing the entry from the #GTree.
 203  *
 204  * Return value: a new #GTree.
 205  **/
 206 GTree*
 207 g_tree_new_full (GCompareDataFunc key_compare_func,
 208                  gpointer         key_compare_data,
 209                  GDestroyNotify   key_destroy_func,
 210                  GDestroyNotify   value_destroy_func)
 211 {
 212   GTree *tree;
 213
 214   g_return_val_if_fail (key_compare_func != NULL, NULL);
 215
 216   tree = g_slice_new (GTree);
 217   tree->root               = NULL;
 218   tree->key_compare        = key_compare_func;
 219   tree->key_destroy_func   = key_destroy_func;
 220   tree->value_destroy_func = value_destroy_func;
 221   tree->key_compare_data   = key_compare_data;
 222   tree->nnodes             = 0;
 223   tree->ref_count          = 1;
 224
 225   return tree;
 226 }
 227
 228 static inline GTreeNode *
 229 g_tree_first_node (GTree *tree)
 230 {
 231   GTreeNode *tmp;
 232
 233   if (!tree->root)
 234     return NULL;
 235
 236   tmp = tree->root;
 237
 238   while (tmp->left_child)
 239     tmp = tmp->left;
 240
 241   return tmp;
 242 }
 243
 244 static inline GTreeNode *
 245 g_tree_node_previous (GTreeNode *node)
 246 {
 247   GTreeNode *tmp;
 248
 249   tmp = node->left;
 250
 251   if (node->left_child)
 252     while (tmp->right_child)
 253       tmp = tmp->right;
 254
 255   return tmp;
 256 }
 257
 258 static inline GTreeNode *
 259 g_tree_node_next (GTreeNode *node)
 260 {
 261   GTreeNode *tmp;
 262
 263   tmp = node->right;
 264
 265   if (node->right_child)
 266     while (tmp->left_child)
 267       tmp = tmp->left;
 268
 269   return tmp;
 270 }
 271
 272 static void
 273 g_tree_remove_all (GTree *tree)
 274 {
 275   GTreeNode *node;
 276   GTreeNode *next;
 277
 278   g_return_if_fail (tree != NULL);
 279
 280   node = g_tree_first_node (tree);
 281
 282   while (node)
 283     {
 284       next = g_tree_node_next (node);
 285
 286       if (tree->key_destroy_func)
 287         tree->key_destroy_func (node->key);
 288       if (tree->value_destroy_func)
 289         tree->value_destroy_func (node->value);
 290       g_slice_free (GTreeNode, node);
 291
 292       node = next;
 293     }
 294
 295   tree->root = NULL;
 296   tree->nnodes = 0;
 297 }
 298
 299 /**
 300  * g_tree_ref:
 301  * @tree: a #GTree.
 302  *
 303  * Increments the reference count of @tree by one.  It is safe to call
 304  * this function from any thread.
 305  *
 306  * Return value: the passed in #GTree.
 307  *
 308  * Since: 2.22
 309  **/
 310 GTree *
 311 g_tree_ref (GTree *tree)
 312 {
 313   g_return_val_if_fail (tree != NULL, NULL);
 314
 315   g_atomic_int_inc (&tree->ref_count);
 316
 317   return tree;
 318 }
 319
 320 /**
 321  * g_tree_unref:
 322  * @tree: a #GTree.
 323  *
 324  * Decrements the reference count of @tree by one.  If the reference count
 325  * drops to 0, all keys and values will be destroyed (if destroy
 326  * functions were specified) and all memory allocated by @tree will be
 327  * released.
 328  *
 329  * It is safe to call this function from any thread.
 330  *
 331  * Since: 2.22
 332  **/
 333 void
 334 g_tree_unref (GTree *tree)
 335 {
 336   g_return_if_fail (tree != NULL);
 337
 338   if (g_atomic_int_dec_and_test (&tree->ref_count))
 339     {
 340       g_tree_remove_all (tree);
 341       g_slice_free (GTree, tree);
 342     }
 343 }
 344
 345 /**
 346  * g_tree_destroy:
 347  * @tree: a #GTree.
 348  *
 349  * Removes all keys and values from the #GTree and decreases its
 350  * reference count by one. If keys and/or values are dynamically
 351  * allocated, you should either free them first or create the #GTree
 352  * using g_tree_new_full().  In the latter case the destroy functions
 353  * you supplied will be called on all keys and values before destroying
 354  * the #GTree.
 355  **/
 356 void
 357 g_tree_destroy (GTree *tree)
 358 {
 359   g_return_if_fail (tree != NULL);
 360
 361   g_tree_remove_all (tree);
 362   g_tree_unref (tree);
 363 }
 364
 365 /**
 366  * g_tree_insert:
 367  * @tree: a #GTree.
 368  * @key: the key to insert.
 369  * @value: the value corresponding to the key.
 370  *
 371  * Inserts a key/value pair into a #GTree. If the given key already exists
 372  * in the #GTree its corresponding value is set to the new value. If you
 373  * supplied a value_destroy_func when creating the #GTree, the old value is
 374  * freed using that function. If you supplied a @key_destroy_func when
 375  * creating the #GTree, the passed key is freed using that function.
 376  *
 377  * The tree is automatically 'balanced' as new key/value pairs are added,
 378  * so that the distance from the root to every leaf is as small as possible.
 379  **/
 380 void
 381 g_tree_insert (GTree    *tree,
 382                gpointer  key,
 383                gpointer  value)
 384 {
 385   g_return_if_fail (tree != NULL);
 386
 387   g_tree_insert_internal (tree, key, value, FALSE);
 388
 389 #ifdef G_TREE_DEBUG
 390   g_tree_node_check (tree->root);
 391 #endif
 392 }
 393
 394 /**
 395  * g_tree_replace:
 396  * @tree: a #GTree.
 397  * @key: the key to insert.
 398  * @value: the value corresponding to the key.
 399  *
 400  * Inserts a new key and value into a #GTree similar to g_tree_insert().
 401  * The difference is that if the key already exists in the #GTree, it gets
 402  * replaced by the new key. If you supplied a @value_destroy_func when
 403  * creating the #GTree, the old value is freed using that function. If you
 404  * supplied a @key_destroy_func when creating the #GTree, the old key is
 405  * freed using that function.
 406  *
 407  * The tree is automatically 'balanced' as new key/value pairs are added,
 408  * so that the distance from the root to every leaf is as small as possible.
 409  **/
 410 void
 411 g_tree_replace (GTree    *tree,
 412                 gpointer  key,
 413                 gpointer  value)
 414 {
 415   g_return_if_fail (tree != NULL);
 416
 417   g_tree_insert_internal (tree, key, value, TRUE);
 418
 419 #ifdef G_TREE_DEBUG
 420   g_tree_node_check (tree->root);
 421 #endif
 422 }
 423
 424 /* internal insert routine */
 425 static void
 426 g_tree_insert_internal (GTree    *tree,
 427                         gpointer  key,
 428                         gpointer  value,
 429                         gboolean  replace)
 430 {
 431   GTreeNode *node;
 432   GTreeNode *path[MAX_GTREE_HEIGHT];
 433   int idx;
 434
 435   g_return_if_fail (tree != NULL);
 436
 437   if (!tree->root)
 438     {
 439       tree->root = g_tree_node_new (key, value);
 440       tree->nnodes++;
 441       return;
 442     }
 443
 444   idx = 0;
 445   path[idx++] = NULL;
 446   node = tree->root;
 447
 448   while (1)
 449     {
 450       int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
 451
 452       if (cmp == 0)
 453         {
 454           if (tree->value_destroy_func)
 455             tree->value_destroy_func (node->value);
 456
 457           node->value = value;
 458
 459           if (replace)
 460             {
 461               if (tree->key_destroy_func)
 462                 tree->key_destroy_func (node->key);
 463
 464               node->key = key;
 465             }
 466           else
 467             {
 468               /* free the passed key */
 469               if (tree->key_destroy_func)
 470                 tree->key_destroy_func (key);
 471             }
 472
 473           return;
 474         }
 475       else if (cmp < 0)
 476         {
 477           if (node->left_child)
 478             {
 479               path[idx++] = node;
 480               node = node->left;
 481             }
 482           else
 483             {
 484               GTreeNode *child = g_tree_node_new (key, value);
 485
 486               child->left = node->left;
 487               child->right = node;
 488               node->left = child;
 489               node->left_child = TRUE;
 490               node->balance -= 1;
 491
 492               tree->nnodes++;
 493
 494               break;
 495             }
 496         }
 497       else
 498         {
 499           if (node->right_child)
 500             {
 501               path[idx++] = node;
 502               node = node->right;
 503             }
 504           else
 505             {
 506               GTreeNode *child = g_tree_node_new (key, value);
 507
 508               child->right = node->right;
 509               child->left = node;
 510               node->right = child;
 511               node->right_child = TRUE;
 512               node->balance += 1;
 513
 514               tree->nnodes++;
 515
 516               break;
 517             }
 518         }
 519     }
 520
 521   /* restore balance. This is the goodness of a non-recursive
 522      implementation, when we are done with balancing we 'break'
 523      the loop and we are done. */
 524   while (1)
 525     {
 526       GTreeNode *bparent = path[--idx];
 527       gboolean left_node = (bparent && node == bparent->left);
 528       g_assert (!bparent || bparent->left == node || bparent->right == node);
 529
 530       if (node->balance < -1 || node->balance > 1)
 531         {
 532           node = g_tree_node_balance (node);
 533           if (bparent == NULL)
 534             tree->root = node;
 535           else if (left_node)
 536             bparent->left = node;
 537           else
 538             bparent->right = node;
 539         }
 540
 541       if (node->balance == 0 || bparent == NULL)
 542         break;
 543
 544       if (left_node)
 545         bparent->balance -= 1;
 546       else
 547         bparent->balance += 1;
 548
 549       node = bparent;
 550     }
 551 }
 552
 553 /**
 554  * g_tree_remove:
 555  * @tree: a #GTree.
 556  * @key: the key to remove.
 557  *
 558  * Removes a key/value pair from a #GTree.
 559  *
 560  * If the #GTree was created using g_tree_new_full(), the key and value
 561  * are freed using the supplied destroy functions, otherwise you have to
 562  * make sure that any dynamically allocated values are freed yourself.
 563  * If the key does not exist in the #GTree, the function does nothing.
 564  *
 565  * Returns: %TRUE if the key was found (prior to 2.8, this function returned
 566  *   nothing)
 567  **/
 568 gboolean
 569 g_tree_remove (GTree         *tree,
 570                gconstpointer  key)
 571 {
 572   gboolean removed;
 573
 574   g_return_val_if_fail (tree != NULL, FALSE);
 575
 576   removed = g_tree_remove_internal (tree, key, FALSE);
 577
 578 #ifdef G_TREE_DEBUG
 579   g_tree_node_check (tree->root);
 580 #endif
 581
 582   return removed;
 583 }
 584
 585 /**
 586  * g_tree_steal:
 587  * @tree: a #GTree.
 588  * @key: the key to remove.
 589  *
 590  * Removes a key and its associated value from a #GTree without calling
 591  * the key and value destroy functions.
 592  *
 593  * If the key does not exist in the #GTree, the function does nothing.
 594  *
 595  * Returns: %TRUE if the key was found (prior to 2.8, this function returned
 596  *    nothing)
 597  **/
 598 gboolean
 599 g_tree_steal (GTree         *tree,
 600               gconstpointer  key)
 601 {
 602   gboolean removed;
 603
 604   g_return_val_if_fail (tree != NULL, FALSE);
 605
 606   removed = g_tree_remove_internal (tree, key, TRUE);
 607
 608 #ifdef G_TREE_DEBUG
 609   g_tree_node_check (tree->root);
 610 #endif
 611
 612   return removed;
 613 }
 614
 615 /* internal remove routine */
 616 static gboolean
 617 g_tree_remove_internal (GTree         *tree,
 618                         gconstpointer  key,
 619                         gboolean       steal)
 620 {
 621   GTreeNode *node, *parent, *balance;
 622   GTreeNode *path[MAX_GTREE_HEIGHT];
 623   int idx;
 624   gboolean left_node;
 625
 626   g_return_val_if_fail (tree != NULL, FALSE);
 627
 628   if (!tree->root)
 629     return FALSE;
 630
 631   idx = 0;
 632   path[idx++] = NULL;
 633   node = tree->root;
 634
 635   while (1)
 636     {
 637       int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
 638
 639       if (cmp == 0)
 640         break;
 641       else if (cmp < 0)
 642         {
 643           if (!node->left_child)
 644             return FALSE;
 645
 646           path[idx++] = node;
 647           node = node->left;
 648         }
 649       else
 650         {
 651           if (!node->right_child)
 652             return FALSE;
 653
 654           path[idx++] = node;
 655           node = node->right;
 656         }
 657     }
 658
 659   /* the following code is almost equal to g_tree_remove_node,
 660      except that we do not have to call g_tree_node_parent. */
 661   balance = parent = path[--idx];
 662   g_assert (!parent || parent->left == node || parent->right == node);
 663   left_node = (parent && node == parent->left);
 664
 665   if (!node->left_child)
 666     {
 667       if (!node->right_child)
 668         {
 669           if (!parent)
 670             tree->root = NULL;
 671           else if (left_node)
 672             {
 673               parent->left_child = FALSE;
 674               parent->left = node->left;
 675               parent->balance += 1;
 676             }
 677           else
 678             {
 679               parent->right_child = FALSE;
 680               parent->right = node->right;
 681               parent->balance -= 1;
 682             }
 683         }
 684       else /* node has a right child */
 685         {
 686           GTreeNode *tmp = g_tree_node_next (node);
 687           tmp->left = node->left;
 688
 689           if (!parent)
 690             tree->root = node->right;
 691           else if (left_node)
 692             {
 693               parent->left = node->right;
 694               parent->balance += 1;
 695             }
 696           else
 697             {
 698               parent->right = node->right;
 699               parent->balance -= 1;
 700             }
 701         }
 702     }
 703   else /* node has a left child */
 704     {
 705       if (!node->right_child)
 706         {
 707           GTreeNode *tmp = g_tree_node_previous (node);
 708           tmp->right = node->right;
 709
 710           if (parent == NULL)
 711             tree->root = node->left;
 712           else if (left_node)
 713             {
 714               parent->left = node->left;
 715               parent->balance += 1;
 716             }
 717           else
 718             {
 719               parent->right = node->left;
 720               parent->balance -= 1;
 721             }
 722         }
 723       else /* node has a both children (pant, pant!) */
 724         {
 725           GTreeNode *prev = node->left;
 726           GTreeNode *next = node->right;
 727           GTreeNode *nextp = node;
 728           int old_idx = idx + 1;
 729           idx++;
 730
 731           /* path[idx] == parent */
 732           /* find the immediately next node (and its parent) */
 733           while (next->left_child)
 734             {
 735               path[++idx] = nextp = next;
 736               next = next->left;
 737             }
 738
 739           path[old_idx] = next;
 740           balance = path[idx];
 741
 742           /* remove 'next' from the tree */
 743           if (nextp != node)
 744             {
 745               if (next->right_child)
 746                 nextp->left = next->right;
 747               else
 748                 nextp->left_child = FALSE;
 749               nextp->balance += 1;
 750
 751               next->right_child = TRUE;
 752               next->right = node->right;
 753             }
 754           else
 755             node->balance -= 1;
 756
 757           /* set the prev to point to the right place */
 758           while (prev->right_child)
 759             prev = prev->right;
 760           prev->right = next;
 761
 762           /* prepare 'next' to replace 'node' */
 763           next->left_child = TRUE;
 764           next->left = node->left;
 765           next->balance = node->balance;
 766
 767           if (!parent)
 768             tree->root = next;
 769           else if (left_node)
 770             parent->left = next;
 771           else
 772             parent->right = next;
 773         }
 774     }
 775
 776   /* restore balance */
 777   if (balance)
 778     while (1)
 779       {
 780         GTreeNode *bparent = path[--idx];
 781         g_assert (!bparent || bparent->left == balance || bparent->right == balance);
 782         left_node = (bparent && balance == bparent->left);
 783
 784         if(balance->balance < -1 || balance->balance > 1)
 785           {
 786             balance = g_tree_node_balance (balance);
 787             if (!bparent)
 788               tree->root = balance;
 789             else if (left_node)
 790               bparent->left = balance;
 791             else
 792               bparent->right = balance;
 793           }
 794
 795         if (balance->balance != 0 || !bparent)
 796           break;
 797
 798         if (left_node)
 799           bparent->balance += 1;
 800         else
 801           bparent->balance -= 1;
 802
 803         balance = bparent;
 804       }
 805
 806   if (!steal)
 807     {
 808       if (tree->key_destroy_func)
 809         tree->key_destroy_func (node->key);
 810       if (tree->value_destroy_func)
 811         tree->value_destroy_func (node->value);
 812     }
 813
 814   g_slice_free (GTreeNode, node);
 815
 816   tree->nnodes--;
 817
 818   return TRUE;
 819 }
 820
 821 /**
 822  * g_tree_lookup:
 823  * @tree: a #GTree.
 824  * @key: the key to look up.
 825  *
 826  * Gets the value corresponding to the given key. Since a #GTree is
 827  * automatically balanced as key/value pairs are added, key lookup is very
 828  * fast.
 829  *
 830  * Return value: the value corresponding to the key, or %NULL if the key was
 831  * not found.
 832  **/
 833 gpointer
 834 g_tree_lookup (GTree         *tree,
 835                gconstpointer  key)
 836 {
 837   GTreeNode *node;
 838
 839   g_return_val_if_fail (tree != NULL, NULL);
 840
 841   node = g_tree_find_node (tree, key);
 842
 843   return node ? node->value : NULL;
 844 }
 845
 846 /**
 847  * g_tree_lookup_extended:
 848  * @tree: a #GTree.
 849  * @lookup_key: the key to look up.
 850  * @orig_key: returns the original key.
 851  * @value: returns the value associated with the key.
 852  *
 853  * Looks up a key in the #GTree, returning the original key and the
 854  * associated value and a #gboolean which is %TRUE if the key was found. This
 855  * is useful if you need to free the memory allocated for the original key,
 856  * for example before calling g_tree_remove().
 857  *
 858  * Return value: %TRUE if the key was found in the #GTree.
 859  **/
 860 gboolean
 861 g_tree_lookup_extended (GTree         *tree,
 862                         gconstpointer  lookup_key,
 863                         gpointer      *orig_key,
 864                         gpointer      *value)
 865 {
 866   GTreeNode *node;
 867
 868   g_return_val_if_fail (tree != NULL, FALSE);
 869
 870   node = g_tree_find_node (tree, lookup_key);
 871
 872   if (node)
 873     {
 874       if (orig_key)
 875         *orig_key = node->key;
 876       if (value)
 877         *value = node->value;
 878       return TRUE;
 879     }
 880   else
 881     return FALSE;
 882 }
 883
 884 /**
 885  * g_tree_foreach:
 886  * @tree: a #GTree.
 887  * @func: the function to call for each node visited. If this function
 888  *   returns %TRUE, the traversal is stopped.
 889  * @user_data: user data to pass to the function.
 890  *
 891  * Calls the given function for each of the key/value pairs in the #GTree.
 892  * The function is passed the key and value of each pair, and the given
 893  * @data parameter. The tree is traversed in sorted order.
 894  *
 895  * The tree may not be modified while iterating over it (you can't
 896  * add/remove items). To remove all items matching a predicate, you need
 897  * to add each item to a list in your #GTraverseFunc as you walk over
 898  * the tree, then walk the list and remove each item.
 899  **/
 900 void
 901 g_tree_foreach (GTree         *tree,
 902                 GTraverseFunc  func,
 903                 gpointer       user_data)
 904 {
 905   GTreeNode *node;
 906
 907   g_return_if_fail (tree != NULL);
 908
 909   if (!tree->root)
 910     return;
 911
 912   node = g_tree_first_node (tree);
 913
 914   while (node)
 915     {
 916       if ((*func) (node->key, node->value, user_data))
 917         break;
 918
 919       node = g_tree_node_next (node);
 920     }
 921 }
 922
 923 /**
 924  * g_tree_traverse:
 925  * @tree: a #GTree.
 926  * @traverse_func: the function to call for each node visited. If this
 927  *   function returns %TRUE, the traversal is stopped.
 928  * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
 929  *   %G_PRE_ORDER and %G_POST_ORDER.
 930  * @user_data: user data to pass to the function.
 931  *
 932  * Calls the given function for each node in the #GTree.
 933  *
 934  * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary. If you
 935  * just want to visit all nodes in sorted order, use g_tree_foreach()
 936  * instead. If you really need to visit nodes in a different order, consider
 937  * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
 938  **/
 939 /**
 940  * GTraverseFunc:
 941  * @key: a key of a #GTree node.
 942  * @value: the value corresponding to the key.
 943  * @data: user data passed to g_tree_traverse().
 944  * @Returns: %TRUE to stop the traversal.
 945  *
 946  * Specifies the type of function passed to g_tree_traverse(). It is
 947  * passed the key and value of each node, together with the @user_data
 948  * parameter passed to g_tree_traverse(). If the function returns
 949  * %TRUE, the traversal is stopped.
 950  **/
 951 /**
 952  * GTraverseType:
 953  * @G_IN_ORDER: vists a node's left child first, then the node itself,
 954  *              then its right child. This is the one to use if you
 955  *              want the output sorted according to the compare
 956  *              function.
 957  * @G_PRE_ORDER: visits a node, then its children.
 958  * @G_POST_ORDER: visits the node's children, then the node itself.
 959  * @G_LEVEL_ORDER: is not implemented for <link
 960  *                 linkend="glib-Balanced-Binary-Trees">Balanced Binary
 961  *                 Trees</link>.  For <link
 962  *                 linkend="glib-N-ary-Trees">N-ary Trees</link>, it
 963  *                 vists the root node first, then its children, then
 964  *                 its grandchildren, and so on. Note that this is less
 965  *                 efficient than the other orders.
 966  *
 967  * Specifies the type of traveral performed by g_tree_traverse(),
 968  * g_node_traverse() and g_node_find().
 969  **/
 970 void
 971 g_tree_traverse (GTree         *tree,
 972                  GTraverseFunc  traverse_func,
 973                  GTraverseType  traverse_type,
 974                  gpointer       user_data)
 975 {
 976   g_return_if_fail (tree != NULL);
 977
 978   if (!tree->root)
 979     return;
 980
 981   switch (traverse_type)
 982     {
 983     case G_PRE_ORDER:
 984       g_tree_node_pre_order (tree->root, traverse_func, user_data);
 985       break;
 986
 987     case G_IN_ORDER:
 988       g_tree_node_in_order (tree->root, traverse_func, user_data);
 989       break;
 990
 991     case G_POST_ORDER:
 992       g_tree_node_post_order (tree->root, traverse_func, user_data);
 993       break;
 994
 995     case G_LEVEL_ORDER:
 996       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
 997       break;
 998     }
 999 }
1000
1001 /**
1002  * g_tree_search:
1003  * @tree: a #GTree.
1004  * @search_func: a function used to search the #GTree.
1005  * @user_data: the data passed as the second argument to the @search_func
1006  * function.
1007  *
1008  * Searches a #GTree using @search_func.
1009  *
1010  * The @search_func is called with a pointer to the key of a key/value pair in
1011  * the tree, and the passed in @user_data. If @search_func returns 0 for a
1012  * key/value pair, then g_tree_search_func() will return the value of that
1013  * pair. If @search_func returns -1,  searching will proceed among the
1014  * key/value pairs that have a smaller key; if @search_func returns 1,
1015  * searching will proceed among the key/value pairs that have a larger key.
1016  *
1017  * Return value: the value corresponding to the found key, or %NULL if the key
1018  * was not found.
1019  **/
1020 gpointer
1021 g_tree_search (GTree         *tree,
1022                GCompareFunc   search_func,
1023                gconstpointer  user_data)
1024 {
1025   g_return_val_if_fail (tree != NULL, NULL);
1026
1027   if (tree->root)
1028     return g_tree_node_search (tree->root, search_func, user_data);
1029   else
1030     return NULL;
1031 }
1032
1033 /**
1034  * g_tree_height:
1035  * @tree: a #GTree.
1036  *
1037  * Gets the height of a #GTree.
1038  *
1039  * If the #GTree contains no nodes, the height is 0.
1040  * If the #GTree contains only one root node the height is 1.
1041  * If the root node has children the height is 2, etc.
1042  *
1043  * Return value: the height of the #GTree.
1044  **/
1045 gint
1046 g_tree_height (GTree *tree)
1047 {
1048   GTreeNode *node;
1049   gint height;
1050
1051   g_return_val_if_fail (tree != NULL, 0);
1052
1053   if (!tree->root)
1054     return 0;
1055
1056   height = 0;
1057   node = tree->root;
1058
1059   while (1)
1060     {
1061       height += 1 + MAX(node->balance, 0);
1062
1063       if (!node->left_child)
1064         return height;
1065
1066       node = node->left;
1067     }
1068 }
1069
1070 /**
1071  * g_tree_nnodes:
1072  * @tree: a #GTree.
1073  *
1074  * Gets the number of nodes in a #GTree.
1075  *
1076  * Return value: the number of nodes in the #GTree.
1077  **/
1078 gint
1079 g_tree_nnodes (GTree *tree)
1080 {
1081   g_return_val_if_fail (tree != NULL, 0);
1082
1083   return tree->nnodes;
1084 }
1085
1086 static GTreeNode*
1087 g_tree_node_balance (GTreeNode *node)
1088 {
1089   if (node->balance < -1)
1090     {
1091       if (node->left->balance > 0)
1092         node->left = g_tree_node_rotate_left (node->left);
1093       node = g_tree_node_rotate_right (node);
1094     }
1095   else if (node->balance > 1)
1096     {
1097       if (node->right->balance < 0)
1098         node->right = g_tree_node_rotate_right (node->right);
1099       node = g_tree_node_rotate_left (node);
1100     }
1101
1102   return node;
1103 }
1104
1105 static GTreeNode *
1106 g_tree_find_node (GTree        *tree,
1107                   gconstpointer key)
1108 {
1109   GTreeNode *node;
1110   gint cmp;
1111
1112   node = tree->root;
1113   if (!node)
1114     return NULL;
1115
1116   while (1)
1117     {
1118       cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1119       if (cmp == 0)
1120         return node;
1121       else if (cmp < 0)
1122         {
1123           if (!node->left_child)
1124             return NULL;
1125
1126           node = node->left;
1127         }
1128       else
1129         {
1130           if (!node->right_child)
1131             return NULL;
1132
1133           node = node->right;
1134         }
1135     }
1136 }
1137
1138 static gint
1139 g_tree_node_pre_order (GTreeNode     *node,
1140                        GTraverseFunc  traverse_func,
1141                        gpointer       data)
1142 {
1143   if ((*traverse_func) (node->key, node->value, data))
1144     return TRUE;
1145
1146   if (node->left_child)
1147     {
1148       if (g_tree_node_pre_order (node->left, traverse_func, data))
1149         return TRUE;
1150     }
1151
1152   if (node->right_child)
1153     {
1154       if (g_tree_node_pre_order (node->right, traverse_func, data))
1155         return TRUE;
1156     }
1157
1158   return FALSE;
1159 }
1160
1161 static gint
1162 g_tree_node_in_order (GTreeNode     *node,
1163                       GTraverseFunc  traverse_func,
1164                       gpointer       data)
1165 {
1166   if (node->left_child)
1167     {
1168       if (g_tree_node_in_order (node->left, traverse_func, data))
1169         return TRUE;
1170     }
1171
1172   if ((*traverse_func) (node->key, node->value, data))
1173     return TRUE;
1174
1175   if (node->right_child)
1176     {
1177       if (g_tree_node_in_order (node->right, traverse_func, data))
1178         return TRUE;
1179     }
1180
1181   return FALSE;
1182 }
1183
1184 static gint
1185 g_tree_node_post_order (GTreeNode     *node,
1186                         GTraverseFunc  traverse_func,
1187                         gpointer       data)
1188 {
1189   if (node->left_child)
1190     {
1191       if (g_tree_node_post_order (node->left, traverse_func, data))
1192         return TRUE;
1193     }
1194
1195   if (node->right_child)
1196     {
1197       if (g_tree_node_post_order (node->right, traverse_func, data))
1198         return TRUE;
1199     }
1200
1201   if ((*traverse_func) (node->key, node->value, data))
1202     return TRUE;
1203
1204   return FALSE;
1205 }
1206
1207 static gpointer
1208 g_tree_node_search (GTreeNode     *node,
1209                     GCompareFunc   search_func,
1210                     gconstpointer  data)
1211 {
1212   gint dir;
1213
1214   if (!node)
1215     return NULL;
1216
1217   while (1)
1218     {
1219       dir = (* search_func) (node->key, data);
1220       if (dir == 0)
1221         return node->value;
1222       else if (dir < 0)
1223         {
1224           if (!node->left_child)
1225             return NULL;
1226
1227           node = node->left;
1228         }
1229       else
1230         {
1231           if (!node->right_child)
1232             return NULL;
1233
1234           node = node->right;
1235         }
1236     }
1237 }
1238
1239 static GTreeNode*
1240 g_tree_node_rotate_left (GTreeNode *node)
1241 {
1242   GTreeNode *right;
1243   gint a_bal;
1244   gint b_bal;
1245
1246   right = node->right;
1247
1248   if (right->left_child)
1249     node->right = right->left;
1250   else
1251     {
1252       node->right_child = FALSE;
1253       node->right = right;
1254       right->left_child = TRUE;
1255     }
1256   right->left = node;
1257
1258   a_bal = node->balance;
1259   b_bal = right->balance;
1260
1261   if (b_bal <= 0)
1262     {
1263       if (a_bal >= 1)
1264         right->balance = b_bal - 1;
1265       else
1266         right->balance = a_bal + b_bal - 2;
1267       node->balance = a_bal - 1;
1268     }
1269   else
1270     {
1271       if (a_bal <= b_bal)
1272         right->balance = a_bal - 2;
1273       else
1274         right->balance = b_bal - 1;
1275       node->balance = a_bal - b_bal - 1;
1276     }
1277
1278   return right;
1279 }
1280
1281 static GTreeNode*
1282 g_tree_node_rotate_right (GTreeNode *node)
1283 {
1284   GTreeNode *left;
1285   gint a_bal;
1286   gint b_bal;
1287
1288   left = node->left;
1289
1290   if (left->right_child)
1291     node->left = left->right;
1292   else
1293     {
1294       node->left_child = FALSE;
1295       node->left = left;
1296       left->right_child = TRUE;
1297     }
1298   left->right = node;
1299
1300   a_bal = node->balance;
1301   b_bal = left->balance;
1302
1303   if (b_bal <= 0)
1304     {
1305       if (b_bal > a_bal)
1306         left->balance = b_bal + 1;
1307       else
1308         left->balance = a_bal + 2;
1309       node->balance = a_bal - b_bal + 1;
1310     }
1311   else
1312     {
1313       if (a_bal <= -1)
1314         left->balance = b_bal + 1;
1315       else
1316         left->balance = a_bal + b_bal + 2;
1317       node->balance = a_bal + 1;
1318     }
1319
1320   return left;
1321 }
1322
1323 #ifdef G_TREE_DEBUG
1324 static gint
1325 g_tree_node_height (GTreeNode *node)
1326 {
1327   gint left_height;
1328   gint right_height;
1329
1330   if (node)
1331     {
1332       left_height = 0;
1333       right_height = 0;
1334
1335       if (node->left_child)
1336         left_height = g_tree_node_height (node->left);
1337
1338       if (node->right_child)
1339         right_height = g_tree_node_height (node->right);
1340
1341       return MAX (left_height, right_height) + 1;
1342     }
1343
1344   return 0;
1345 }
1346
1347 static void
1348 g_tree_node_check (GTreeNode *node)
1349 {
1350   gint left_height;
1351   gint right_height;
1352   gint balance;
1353   GTreeNode *tmp;
1354
1355   if (node)
1356     {
1357       if (node->left_child)
1358         {
1359           tmp = g_tree_node_previous (node);
1360           g_assert (tmp->right == node);
1361         }
1362
1363       if (node->right_child)
1364         {
1365           tmp = g_tree_node_next (node);
1366           g_assert (tmp->left == node);
1367         }
1368
1369       left_height = 0;
1370       right_height = 0;
1371
1372       if (node->left_child)
1373         left_height = g_tree_node_height (node->left);
1374       if (node->right_child)
1375         right_height = g_tree_node_height (node->right);
1376
1377       balance = right_height - left_height;
1378       g_assert (balance == node->balance);
1379
1380       if (node->left_child)
1381         g_tree_node_check (node->left);
1382       if (node->right_child)
1383         g_tree_node_check (node->right);
1384     }
1385 }
1386
1387 static void
1388 g_tree_node_dump (GTreeNode *node,
1389                   gint       indent)
1390 {
1391   g_print ("%*s%c\n", indent, "", *(char *)node->key);
1392
1393   if (node->left_child)
1394     g_tree_node_dump (node->left, indent + 2);
1395   else if (node->left)
1396     g_print ("%*s<%c\n", indent + 2, "", *(char *)node->left->key);
1397
1398   if (node->right_child)
1399     g_tree_node_dump (node->right, indent + 2);
1400   else if (node->right)
1401     g_print ("%*s>%c\n", indent + 2, "", *(char *)node->right->key);
1402 }
1403
1404
1405 void
1406 g_tree_dump (GTree *tree)
1407 {
1408   if (tree->root)
1409     g_tree_node_dump (tree->root, 0);
1410 }
1411 #endif