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