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