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