glib/gtree.c

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