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  *
 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  * Returns: %TRUE to stop the traversal.
 955  **/
 956 /**
 957  * GTraverseType:
 958  * @G_IN_ORDER: vists a node's left child first, then the node itself,
 959  *              then its right child. This is the one to use if you
 960  *              want the output sorted according to the compare
 961  *              function.
 962  * @G_PRE_ORDER: visits a node, then its children.
 963  * @G_POST_ORDER: visits the node's children, then the node itself.
 964  * @G_LEVEL_ORDER: is not implemented for <link
 965  *                 linkend="glib-Balanced-Binary-Trees">Balanced Binary
 966  *                 Trees</link>.  For <link
 967  *                 linkend="glib-N-ary-Trees">N-ary Trees</link>, it
 968  *                 vists the root node first, then its children, then
 969  *                 its grandchildren, and so on. Note that this is less
 970  *                 efficient than the other orders.
 971  *
 972  * Specifies the type of traveral performed by g_tree_traverse(),
 973  * g_node_traverse() and g_node_find().
 974  **/
 975 void
 976 g_tree_traverse (GTree         *tree,
 977                  GTraverseFunc  traverse_func,
 978                  GTraverseType  traverse_type,
 979                  gpointer       user_data)
 980 {
 981   g_return_if_fail (tree != NULL);
 982
 983   if (!tree->root)
 984     return;
 985
 986   switch (traverse_type)
 987     {
 988     case G_PRE_ORDER:
 989       g_tree_node_pre_order (tree->root, traverse_func, user_data);
 990       break;
 991
 992     case G_IN_ORDER:
 993       g_tree_node_in_order (tree->root, traverse_func, user_data);
 994       break;
 995
 996     case G_POST_ORDER:
 997       g_tree_node_post_order (tree->root, traverse_func, user_data);
 998       break;
 999
1000     case G_LEVEL_ORDER:
1001       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
1002       break;
1003     }
1004 }
1005
1006 /**
1007  * g_tree_search:
1008  * @tree: a #GTree
1009  * @search_func: a function used to search the #GTree
1010  * @user_data: the data passed as the second argument to @search_func
1011  *
1012  * Searches a #GTree using @search_func.
1013  *
1014  * The @search_func is called with a pointer to the key of a key/value
1015  * pair in the tree, and the passed in @user_data. If @search_func returns
1016  * 0 for a key/value pair, then the corresponding value is returned as
1017  * the result of g_tree_search(). If @search_func returns -1, searching
1018  * will proceed among the key/value pairs that have a smaller key; if
1019  * @search_func returns 1, searching will proceed among the key/value
1020  * pairs that have a larger key.
1021  *
1022  * Return value: the value corresponding to the found key, or %NULL if
1023  * the key was not found.
1024  */
1025 gpointer
1026 g_tree_search (GTree         *tree,
1027                GCompareFunc   search_func,
1028                gconstpointer  user_data)
1029 {
1030   g_return_val_if_fail (tree != NULL, NULL);
1031
1032   if (tree->root)
1033     return g_tree_node_search (tree->root, search_func, user_data);
1034   else
1035     return NULL;
1036 }
1037
1038 /**
1039  * g_tree_height:
1040  * @tree: a #GTree.
1041  *
1042  * Gets the height of a #GTree.
1043  *
1044  * If the #GTree contains no nodes, the height is 0.
1045  * If the #GTree contains only one root node the height is 1.
1046  * If the root node has children the height is 2, etc.
1047  *
1048  * Return value: the height of the #GTree.
1049  **/
1050 gint
1051 g_tree_height (GTree *tree)
1052 {
1053   GTreeNode *node;
1054   gint height;
1055
1056   g_return_val_if_fail (tree != NULL, 0);
1057
1058   if (!tree->root)
1059     return 0;
1060
1061   height = 0;
1062   node = tree->root;
1063
1064   while (1)
1065     {
1066       height += 1 + MAX(node->balance, 0);
1067
1068       if (!node->left_child)
1069         return height;
1070
1071       node = node->left;
1072     }
1073 }
1074
1075 /**
1076  * g_tree_nnodes:
1077  * @tree: a #GTree.
1078  *
1079  * Gets the number of nodes in a #GTree.
1080  *
1081  * Return value: the number of nodes in the #GTree.
1082  **/
1083 gint
1084 g_tree_nnodes (GTree *tree)
1085 {
1086   g_return_val_if_fail (tree != NULL, 0);
1087
1088   return tree->nnodes;
1089 }
1090
1091 static GTreeNode*
1092 g_tree_node_balance (GTreeNode *node)
1093 {
1094   if (node->balance < -1)
1095     {
1096       if (node->left->balance > 0)
1097         node->left = g_tree_node_rotate_left (node->left);
1098       node = g_tree_node_rotate_right (node);
1099     }
1100   else if (node->balance > 1)
1101     {
1102       if (node->right->balance < 0)
1103         node->right = g_tree_node_rotate_right (node->right);
1104       node = g_tree_node_rotate_left (node);
1105     }
1106
1107   return node;
1108 }
1109
1110 static GTreeNode *
1111 g_tree_find_node (GTree        *tree,
1112                   gconstpointer key)
1113 {
1114   GTreeNode *node;
1115   gint cmp;
1116
1117   node = tree->root;
1118   if (!node)
1119     return NULL;
1120
1121   while (1)
1122     {
1123       cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1124       if (cmp == 0)
1125         return node;
1126       else if (cmp < 0)
1127         {
1128           if (!node->left_child)
1129             return NULL;
1130
1131           node = node->left;
1132         }
1133       else
1134         {
1135           if (!node->right_child)
1136             return NULL;
1137
1138           node = node->right;
1139         }
1140     }
1141 }
1142
1143 static gint
1144 g_tree_node_pre_order (GTreeNode     *node,
1145                        GTraverseFunc  traverse_func,
1146                        gpointer       data)
1147 {
1148   if ((*traverse_func) (node->key, node->value, data))
1149     return TRUE;
1150
1151   if (node->left_child)
1152     {
1153       if (g_tree_node_pre_order (node->left, traverse_func, data))
1154         return TRUE;
1155     }
1156
1157   if (node->right_child)
1158     {
1159       if (g_tree_node_pre_order (node->right, traverse_func, data))
1160         return TRUE;
1161     }
1162
1163   return FALSE;
1164 }
1165
1166 static gint
1167 g_tree_node_in_order (GTreeNode     *node,
1168                       GTraverseFunc  traverse_func,
1169                       gpointer       data)
1170 {
1171   if (node->left_child)
1172     {
1173       if (g_tree_node_in_order (node->left, traverse_func, data))
1174         return TRUE;
1175     }
1176
1177   if ((*traverse_func) (node->key, node->value, data))
1178     return TRUE;
1179
1180   if (node->right_child)
1181     {
1182       if (g_tree_node_in_order (node->right, traverse_func, data))
1183         return TRUE;
1184     }
1185
1186   return FALSE;
1187 }
1188
1189 static gint
1190 g_tree_node_post_order (GTreeNode     *node,
1191                         GTraverseFunc  traverse_func,
1192                         gpointer       data)
1193 {
1194   if (node->left_child)
1195     {
1196       if (g_tree_node_post_order (node->left, traverse_func, data))
1197         return TRUE;
1198     }
1199
1200   if (node->right_child)
1201     {
1202       if (g_tree_node_post_order (node->right, traverse_func, data))
1203         return TRUE;
1204     }
1205
1206   if ((*traverse_func) (node->key, node->value, data))
1207     return TRUE;
1208
1209   return FALSE;
1210 }
1211
1212 static gpointer
1213 g_tree_node_search (GTreeNode     *node,
1214                     GCompareFunc   search_func,
1215                     gconstpointer  data)
1216 {
1217   gint dir;
1218
1219   if (!node)
1220     return NULL;
1221
1222   while (1)
1223     {
1224       dir = (* search_func) (node->key, data);
1225       if (dir == 0)
1226         return node->value;
1227       else if (dir < 0)
1228         {
1229           if (!node->left_child)
1230             return NULL;
1231
1232           node = node->left;
1233         }
1234       else
1235         {
1236           if (!node->right_child)
1237             return NULL;
1238
1239           node = node->right;
1240         }
1241     }
1242 }
1243
1244 static GTreeNode*
1245 g_tree_node_rotate_left (GTreeNode *node)
1246 {
1247   GTreeNode *right;
1248   gint a_bal;
1249   gint b_bal;
1250
1251   right = node->right;
1252
1253   if (right->left_child)
1254     node->right = right->left;
1255   else
1256     {
1257       node->right_child = FALSE;
1258       right->left_child = TRUE;
1259     }
1260   right->left = node;
1261
1262   a_bal = node->balance;
1263   b_bal = right->balance;
1264
1265   if (b_bal <= 0)
1266     {
1267       if (a_bal >= 1)
1268         right->balance = b_bal - 1;
1269       else
1270         right->balance = a_bal + b_bal - 2;
1271       node->balance = a_bal - 1;
1272     }
1273   else
1274     {
1275       if (a_bal <= b_bal)
1276         right->balance = a_bal - 2;
1277       else
1278         right->balance = b_bal - 1;
1279       node->balance = a_bal - b_bal - 1;
1280     }
1281
1282   return right;
1283 }
1284
1285 static GTreeNode*
1286 g_tree_node_rotate_right (GTreeNode *node)
1287 {
1288   GTreeNode *left;
1289   gint a_bal;
1290   gint b_bal;
1291
1292   left = node->left;
1293
1294   if (left->right_child)
1295     node->left = left->right;
1296   else
1297     {
1298       node->left_child = FALSE;
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