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