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, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 /*
  19  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  20  * file for a list of people on the GLib Team.  See the ChangeLog
  21  * files for a list of changes.  These files are distributed with
  22  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  23  */
  24
  25 /*
  26  * MT safe
  27  */
  28
  29 #include "config.h"
  30
  31 #include "gtree.h"
  32
  33 #include "gatomic.h"
  34 #include "gtestutils.h"
  35 #include "gslice.h"
  36
  37 /**
  38  * SECTION:trees-binary
  39  * @title: Balanced Binary Trees
  40  * @short_description: a sorted collection of key/value pairs optimized
  41  *                     for searching and traversing in order
  42  *
  43  * The #GTree structure and its associated functions provide a sorted
  44  * collection of key/value pairs optimized for searching and traversing
  45  * in order.
  46  *
  47  * To create a new #GTree use g_tree_new().
  48  *
  49  * To insert a key/value pair into a #GTree use g_tree_insert().
  50  *
  51  * To lookup the value corresponding to a given key, use
  52  * g_tree_lookup() and g_tree_lookup_extended().
  53  *
  54  * To find out the number of nodes in a #GTree, use g_tree_nnodes(). To
  55  * get the height of a #GTree, use g_tree_height().
  56  *
  57  * To traverse a #GTree, calling a function for each node visited in
  58  * the traversal, use g_tree_foreach().
  59  *
  60  * To remove a key/value pair use g_tree_remove().
  61  *
  62  * To destroy a #GTree, use g_tree_destroy().
  63  **/
  64
  65 #undef G_TREE_DEBUG
  66
  67 #define MAX_GTREE_HEIGHT 40
  68
  69 typedef struct _GTreeNode  GTreeNode;
  70
  71 /**
  72  * GTree:
  73  *
  74  * The #GTree-struct is an opaque data structure representing a <link
  75  * linkend="glib-Balanced-Binary-Trees">Balanced Binary Tree</link>.
  76  * It 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 (right) - height (left) */
  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 newly allocated #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 newly allocated #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 newly allocated #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.
 305  *
 306  * It is safe to call this function from any thread.
 307  *
 308  * Return value: the passed in #GTree
 309  *
 310  * Since: 2.22
 311  */
 312 GTree *
 313 g_tree_ref (GTree *tree)
 314 {
 315   g_return_val_if_fail (tree != NULL, NULL);
 316
 317   g_atomic_int_inc (&tree->ref_count);
 318
 319   return tree;
 320 }
 321
 322 /**
 323  * g_tree_unref:
 324  * @tree: a #GTree
 325  *
 326  * Decrements the reference count of @tree by one.
 327  * If the reference count drops to 0, all keys and values will
 328  * be destroyed (if destroy functions were specified) and all
 329  * memory allocated by @tree will be released.
 330  *
 331  * It is safe to call this function from any thread.
 332  *
 333  * Since: 2.22
 334  */
 335 void
 336 g_tree_unref (GTree *tree)
 337 {
 338   g_return_if_fail (tree != NULL);
 339
 340   if (g_atomic_int_dec_and_test (&tree->ref_count))
 341     {
 342       g_tree_remove_all (tree);
 343       g_slice_free (GTree, tree);
 344     }
 345 }
 346
 347 /**
 348  * g_tree_destroy:
 349  * @tree: a #GTree
 350  *
 351  * Removes all keys and values from the #GTree and decreases its
 352  * reference count by one. If keys and/or values are dynamically
 353  * allocated, you should either free them first or create the #GTree
 354  * using g_tree_new_full(). In the latter case the destroy functions
 355  * you supplied will be called on all keys and values before destroying
 356  * the #GTree.
 357  */
 358 void
 359 g_tree_destroy (GTree *tree)
 360 {
 361   g_return_if_fail (tree != NULL);
 362
 363   g_tree_remove_all (tree);
 364   g_tree_unref (tree);
 365 }
 366
 367 /**
 368  * g_tree_insert:
 369  * @tree: a #GTree
 370  * @key: the key to insert
 371  * @value: the value corresponding to the key
 372  *
 373  * Inserts a key/value pair into a #GTree.
 374  *
 375  * If the given key already exists in the #GTree its corresponding value
 376  * is set to the new value. If you supplied a @value_destroy_func when
 377  * creating the #GTree, the old value is freed using that function. If
 378  * you supplied a @key_destroy_func when creating the #GTree, the passed
 379  * 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    */
 529   while (1)
 530     {
 531       GTreeNode *bparent = path[--idx];
 532       gboolean left_node = (bparent && node == bparent->left);
 533       g_assert (!bparent || bparent->left == node || bparent->right == node);
 534
 535       if (node->balance < -1 || node->balance > 1)
 536         {
 537           node = g_tree_node_balance (node);
 538           if (bparent == NULL)
 539             tree->root = node;
 540           else if (left_node)
 541             bparent->left = node;
 542           else
 543             bparent->right = node;
 544         }
 545
 546       if (node->balance == 0 || bparent == NULL)
 547         break;
 548
 549       if (left_node)
 550         bparent->balance -= 1;
 551       else
 552         bparent->balance += 1;
 553
 554       node = bparent;
 555     }
 556 }
 557
 558 /**
 559  * g_tree_remove:
 560  * @tree: a #GTree
 561  * @key: the key to remove
 562  *
 563  * Removes a key/value pair from a #GTree.
 564  *
 565  * If the #GTree was created using g_tree_new_full(), the key and value
 566  * are freed using the supplied destroy functions, otherwise you have to
 567  * make sure that any dynamically allocated values are freed yourself.
 568  * If the key does not exist in the #GTree, the function does nothing.
 569  *
 570  * Returns: %TRUE if the key was found (prior to 2.8, this function
 571  *     returned nothing)
 572  */
 573 gboolean
 574 g_tree_remove (GTree         *tree,
 575                gconstpointer  key)
 576 {
 577   gboolean removed;
 578
 579   g_return_val_if_fail (tree != NULL, FALSE);
 580
 581   removed = g_tree_remove_internal (tree, key, FALSE);
 582
 583 #ifdef G_TREE_DEBUG
 584   g_tree_node_check (tree->root);
 585 #endif
 586
 587   return removed;
 588 }
 589
 590 /**
 591  * g_tree_steal:
 592  * @tree: a #GTree
 593  * @key: the key to remove
 594  *
 595  * Removes a key and its associated value from a #GTree without calling
 596  * the key and value destroy functions.
 597  *
 598  * If the key does not exist in the #GTree, the function does nothing.
 599  *
 600  * Returns: %TRUE if the key was found (prior to 2.8, this function
 601  *     returned nothing)
 602  */
 603 gboolean
 604 g_tree_steal (GTree         *tree,
 605               gconstpointer  key)
 606 {
 607   gboolean removed;
 608
 609   g_return_val_if_fail (tree != NULL, FALSE);
 610
 611   removed = g_tree_remove_internal (tree, key, TRUE);
 612
 613 #ifdef G_TREE_DEBUG
 614   g_tree_node_check (tree->root);
 615 #endif
 616
 617   return removed;
 618 }
 619
 620 /* internal remove routine */
 621 static gboolean
 622 g_tree_remove_internal (GTree         *tree,
 623                         gconstpointer  key,
 624                         gboolean       steal)
 625 {
 626   GTreeNode *node, *parent, *balance;
 627   GTreeNode *path[MAX_GTREE_HEIGHT];
 628   int idx;
 629   gboolean left_node;
 630
 631   g_return_val_if_fail (tree != NULL, FALSE);
 632
 633   if (!tree->root)
 634     return FALSE;
 635
 636   idx = 0;
 637   path[idx++] = NULL;
 638   node = tree->root;
 639
 640   while (1)
 641     {
 642       int cmp = tree->key_compare (key, node->key, tree->key_compare_data);
 643
 644       if (cmp == 0)
 645         break;
 646       else if (cmp < 0)
 647         {
 648           if (!node->left_child)
 649             return FALSE;
 650
 651           path[idx++] = node;
 652           node = node->left;
 653         }
 654       else
 655         {
 656           if (!node->right_child)
 657             return FALSE;
 658
 659           path[idx++] = node;
 660           node = node->right;
 661         }
 662     }
 663
 664   /* The following code is almost equal to g_tree_remove_node,
 665    * except that we do not have to call g_tree_node_parent.
 666    */
 667   balance = parent = path[--idx];
 668   g_assert (!parent || parent->left == node || parent->right == node);
 669   left_node = (parent && node == parent->left);
 670
 671   if (!node->left_child)
 672     {
 673       if (!node->right_child)
 674         {
 675           if (!parent)
 676             tree->root = NULL;
 677           else if (left_node)
 678             {
 679               parent->left_child = FALSE;
 680               parent->left = node->left;
 681               parent->balance += 1;
 682             }
 683           else
 684             {
 685               parent->right_child = FALSE;
 686               parent->right = node->right;
 687               parent->balance -= 1;
 688             }
 689         }
 690       else /* node has a right child */
 691         {
 692           GTreeNode *tmp = g_tree_node_next (node);
 693           tmp->left = node->left;
 694
 695           if (!parent)
 696             tree->root = node->right;
 697           else if (left_node)
 698             {
 699               parent->left = node->right;
 700               parent->balance += 1;
 701             }
 702           else
 703             {
 704               parent->right = node->right;
 705               parent->balance -= 1;
 706             }
 707         }
 708     }
 709   else /* node has a left child */
 710     {
 711       if (!node->right_child)
 712         {
 713           GTreeNode *tmp = g_tree_node_previous (node);
 714           tmp->right = node->right;
 715
 716           if (parent == NULL)
 717             tree->root = node->left;
 718           else if (left_node)
 719             {
 720               parent->left = node->left;
 721               parent->balance += 1;
 722             }
 723           else
 724             {
 725               parent->right = node->left;
 726               parent->balance -= 1;
 727             }
 728         }
 729       else /* node has a both children (pant, pant!) */
 730         {
 731           GTreeNode *prev = node->left;
 732           GTreeNode *next = node->right;
 733           GTreeNode *nextp = node;
 734           int old_idx = idx + 1;
 735           idx++;
 736
 737           /* path[idx] == parent */
 738           /* find the immediately next node (and its parent) */
 739           while (next->left_child)
 740             {
 741               path[++idx] = nextp = next;
 742               next = next->left;
 743             }
 744
 745           path[old_idx] = next;
 746           balance = path[idx];
 747
 748           /* remove 'next' from the tree */
 749           if (nextp != node)
 750             {
 751               if (next->right_child)
 752                 nextp->left = next->right;
 753               else
 754                 nextp->left_child = FALSE;
 755               nextp->balance += 1;
 756
 757               next->right_child = TRUE;
 758               next->right = node->right;
 759             }
 760           else
 761             node->balance -= 1;
 762
 763           /* set the prev to point to the right place */
 764           while (prev->right_child)
 765             prev = prev->right;
 766           prev->right = next;
 767
 768           /* prepare 'next' to replace 'node' */
 769           next->left_child = TRUE;
 770           next->left = node->left;
 771           next->balance = node->balance;
 772
 773           if (!parent)
 774             tree->root = next;
 775           else if (left_node)
 776             parent->left = next;
 777           else
 778             parent->right = next;
 779         }
 780     }
 781
 782   /* restore balance */
 783   if (balance)
 784     while (1)
 785       {
 786         GTreeNode *bparent = path[--idx];
 787         g_assert (!bparent || bparent->left == balance || bparent->right == balance);
 788         left_node = (bparent && balance == bparent->left);
 789
 790         if(balance->balance < -1 || balance->balance > 1)
 791           {
 792             balance = g_tree_node_balance (balance);
 793             if (!bparent)
 794               tree->root = balance;
 795             else if (left_node)
 796               bparent->left = balance;
 797             else
 798               bparent->right = balance;
 799           }
 800
 801         if (balance->balance != 0 || !bparent)
 802           break;
 803
 804         if (left_node)
 805           bparent->balance += 1;
 806         else
 807           bparent->balance -= 1;
 808
 809         balance = bparent;
 810       }
 811
 812   if (!steal)
 813     {
 814       if (tree->key_destroy_func)
 815         tree->key_destroy_func (node->key);
 816       if (tree->value_destroy_func)
 817         tree->value_destroy_func (node->value);
 818     }
 819
 820   g_slice_free (GTreeNode, node);
 821
 822   tree->nnodes--;
 823
 824   return TRUE;
 825 }
 826
 827 /**
 828  * g_tree_lookup:
 829  * @tree: a #GTree
 830  * @key: the key to look up
 831  *
 832  * Gets the value corresponding to the given key. Since a #GTree is
 833  * automatically balanced as key/value pairs are added, key lookup
 834  * is O(log n) (where n is the number of key/value pairs in the tree).
 835  *
 836  * Return value: the value corresponding to the key, or %NULL
 837  *     if the key was not found.
 838  */
 839 gpointer
 840 g_tree_lookup (GTree         *tree,
 841                gconstpointer  key)
 842 {
 843   GTreeNode *node;
 844
 845   g_return_val_if_fail (tree != NULL, NULL);
 846
 847   node = g_tree_find_node (tree, key);
 848
 849   return node ? node->value : NULL;
 850 }
 851
 852 /**
 853  * g_tree_lookup_extended:
 854  * @tree: a #GTree
 855  * @lookup_key: the key to look up
 856  * @orig_key: returns the original key
 857  * @value: returns the value associated with the key
 858  *
 859  * Looks up a key in the #GTree, returning the original key and the
 860  * associated value. This is useful if you need to free the memory
 861  * allocated for the original key, for example before calling
 862  * g_tree_remove().
 863  *
 864  * Return value: %TRUE if the key was found in the #GTree
 865  */
 866 gboolean
 867 g_tree_lookup_extended (GTree         *tree,
 868                         gconstpointer  lookup_key,
 869                         gpointer      *orig_key,
 870                         gpointer      *value)
 871 {
 872   GTreeNode *node;
 873
 874   g_return_val_if_fail (tree != NULL, FALSE);
 875
 876   node = g_tree_find_node (tree, lookup_key);
 877
 878   if (node)
 879     {
 880       if (orig_key)
 881         *orig_key = node->key;
 882       if (value)
 883         *value = node->value;
 884       return TRUE;
 885     }
 886   else
 887     return FALSE;
 888 }
 889
 890 /**
 891  * g_tree_foreach:
 892  * @tree: a #GTree
 893  * @func: the function to call for each node visited.
 894  *     If this function returns %TRUE, the traversal is stopped.
 895  * @user_data: user data to pass to the function
 896  *
 897  * Calls the given function for each of the key/value pairs in the #GTree.
 898  * The function is passed the key and value of each pair, and the given
 899  * @data parameter. The tree is traversed in sorted order.
 900  *
 901  * The tree may not be modified while iterating over it (you can't
 902  * add/remove items). To remove all items matching a predicate, you need
 903  * to add each item to a list in your #GTraverseFunc as you walk over
 904  * the tree, then walk the list and remove each item.
 905  */
 906 void
 907 g_tree_foreach (GTree         *tree,
 908                 GTraverseFunc  func,
 909                 gpointer       user_data)
 910 {
 911   GTreeNode *node;
 912
 913   g_return_if_fail (tree != NULL);
 914
 915   if (!tree->root)
 916     return;
 917
 918   node = g_tree_first_node (tree);
 919
 920   while (node)
 921     {
 922       if ((*func) (node->key, node->value, user_data))
 923         break;
 924
 925       node = g_tree_node_next (node);
 926     }
 927 }
 928
 929 /**
 930  * g_tree_traverse:
 931  * @tree: a #GTree
 932  * @traverse_func: the function to call for each node visited. If this
 933  *   function returns %TRUE, the traversal is stopped.
 934  * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
 935  *   %G_PRE_ORDER and %G_POST_ORDER
 936  * @user_data: user data to pass to the function
 937  *
 938  * Calls the given function for each node in the #GTree.
 939  *
 940  * Deprecated:2.2: The order of a balanced tree is somewhat arbitrary.
 941  *     If you just want to visit all nodes in sorted order, use
 942  *     g_tree_foreach() instead. If you really need to visit nodes in
 943  *     a different order, consider using an
 944  *     <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
 945  */
 946 /**
 947  * GTraverseFunc:
 948  * @key: a key of a #GTree node
 949  * @value: the value corresponding to the key
 950  * @data: user data passed to g_tree_traverse()
 951  *
 952  * Specifies the type of function passed to g_tree_traverse(). It is
 953  * passed the key and value of each node, together with the @user_data
 954  * parameter passed to g_tree_traverse(). If the function returns
 955  * %TRUE, the traversal is stopped.
 956  *
 957  * Returns: %TRUE to stop the traversal
 958  */
 959 void
 960 g_tree_traverse (GTree         *tree,
 961                  GTraverseFunc  traverse_func,
 962                  GTraverseType  traverse_type,
 963                  gpointer       user_data)
 964 {
 965   g_return_if_fail (tree != NULL);
 966
 967   if (!tree->root)
 968     return;
 969
 970   switch (traverse_type)
 971     {
 972     case G_PRE_ORDER:
 973       g_tree_node_pre_order (tree->root, traverse_func, user_data);
 974       break;
 975
 976     case G_IN_ORDER:
 977       g_tree_node_in_order (tree->root, traverse_func, user_data);
 978       break;
 979
 980     case G_POST_ORDER:
 981       g_tree_node_post_order (tree->root, traverse_func, user_data);
 982       break;
 983
 984     case G_LEVEL_ORDER:
 985       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
 986       break;
 987     }
 988 }
 989
 990 /**
 991  * g_tree_search:
 992  * @tree: a #GTree
 993  * @search_func: a function used to search the #GTree
 994  * @user_data: the data passed as the second argument to @search_func
 995  *
 996  * Searches a #GTree using @search_func.
 997  *
 998  * The @search_func is called with a pointer to the key of a key/value
 999  * pair in the tree, and the passed in @user_data. If @search_func returns
1000  * 0 for a key/value pair, then the corresponding value is returned as
1001  * the result of g_tree_search(). If @search_func returns -1, searching
1002  * will proceed among the key/value pairs that have a smaller key; if
1003  * @search_func returns 1, searching will proceed among the key/value
1004  * pairs that have a larger key.
1005  *
1006  * Return value: the value corresponding to the found key, or %NULL
1007  *     if the key was not found.
1008  */
1009 gpointer
1010 g_tree_search (GTree         *tree,
1011                GCompareFunc   search_func,
1012                gconstpointer  user_data)
1013 {
1014   g_return_val_if_fail (tree != NULL, NULL);
1015
1016   if (tree->root)
1017     return g_tree_node_search (tree->root, search_func, user_data);
1018   else
1019     return NULL;
1020 }
1021
1022 /**
1023  * g_tree_height:
1024  * @tree: a #GTree
1025  *
1026  * Gets the height of a #GTree.
1027  *
1028  * If the #GTree contains no nodes, the height is 0.
1029  * If the #GTree contains only one root node the height is 1.
1030  * If the root node has children the height is 2, etc.
1031  *
1032  * Return value: the height of @tree
1033  */
1034 gint
1035 g_tree_height (GTree *tree)
1036 {
1037   GTreeNode *node;
1038   gint height;
1039
1040   g_return_val_if_fail (tree != NULL, 0);
1041
1042   if (!tree->root)
1043     return 0;
1044
1045   height = 0;
1046   node = tree->root;
1047
1048   while (1)
1049     {
1050       height += 1 + MAX(node->balance, 0);
1051
1052       if (!node->left_child)
1053         return height;
1054
1055       node = node->left;
1056     }
1057 }
1058
1059 /**
1060  * g_tree_nnodes:
1061  * @tree: a #GTree
1062  *
1063  * Gets the number of nodes in a #GTree.
1064  *
1065  * Return value: the number of nodes in @tree
1066  */
1067 gint
1068 g_tree_nnodes (GTree *tree)
1069 {
1070   g_return_val_if_fail (tree != NULL, 0);
1071
1072   return tree->nnodes;
1073 }
1074
1075 static GTreeNode *
1076 g_tree_node_balance (GTreeNode *node)
1077 {
1078   if (node->balance < -1)
1079     {
1080       if (node->left->balance > 0)
1081         node->left = g_tree_node_rotate_left (node->left);
1082       node = g_tree_node_rotate_right (node);
1083     }
1084   else if (node->balance > 1)
1085     {
1086       if (node->right->balance < 0)
1087         node->right = g_tree_node_rotate_right (node->right);
1088       node = g_tree_node_rotate_left (node);
1089     }
1090
1091   return node;
1092 }
1093
1094 static GTreeNode *
1095 g_tree_find_node (GTree        *tree,
1096                   gconstpointer key)
1097 {
1098   GTreeNode *node;
1099   gint cmp;
1100
1101   node = tree->root;
1102   if (!node)
1103     return NULL;
1104
1105   while (1)
1106     {
1107       cmp = tree->key_compare (key, node->key, tree->key_compare_data);
1108       if (cmp == 0)
1109         return node;
1110       else if (cmp < 0)
1111         {
1112           if (!node->left_child)
1113             return NULL;
1114
1115           node = node->left;
1116         }
1117       else
1118         {
1119           if (!node->right_child)
1120             return NULL;
1121
1122           node = node->right;
1123         }
1124     }
1125 }
1126
1127 static gint
1128 g_tree_node_pre_order (GTreeNode     *node,
1129                        GTraverseFunc  traverse_func,
1130                        gpointer       data)
1131 {
1132   if ((*traverse_func) (node->key, node->value, data))
1133     return TRUE;
1134
1135   if (node->left_child)
1136     {
1137       if (g_tree_node_pre_order (node->left, traverse_func, data))
1138         return TRUE;
1139     }
1140
1141   if (node->right_child)
1142     {
1143       if (g_tree_node_pre_order (node->right, traverse_func, data))
1144         return TRUE;
1145     }
1146
1147   return FALSE;
1148 }
1149
1150 static gint
1151 g_tree_node_in_order (GTreeNode     *node,
1152                       GTraverseFunc  traverse_func,
1153                       gpointer       data)
1154 {
1155   if (node->left_child)
1156     {
1157       if (g_tree_node_in_order (node->left, traverse_func, data))
1158         return TRUE;
1159     }
1160
1161   if ((*traverse_func) (node->key, node->value, data))
1162     return TRUE;
1163
1164   if (node->right_child)
1165     {
1166       if (g_tree_node_in_order (node->right, traverse_func, data))
1167         return TRUE;
1168     }
1169
1170   return FALSE;
1171 }
1172
1173 static gint
1174 g_tree_node_post_order (GTreeNode     *node,
1175                         GTraverseFunc  traverse_func,
1176                         gpointer       data)
1177 {
1178   if (node->left_child)
1179     {
1180       if (g_tree_node_post_order (node->left, traverse_func, data))
1181         return TRUE;
1182     }
1183
1184   if (node->right_child)
1185     {
1186       if (g_tree_node_post_order (node->right, traverse_func, data))
1187         return TRUE;
1188     }
1189
1190   if ((*traverse_func) (node->key, node->value, data))
1191     return TRUE;
1192
1193   return FALSE;
1194 }
1195
1196 static gpointer
1197 g_tree_node_search (GTreeNode     *node,
1198                     GCompareFunc   search_func,
1199                     gconstpointer  data)
1200 {
1201   gint dir;
1202
1203   if (!node)
1204     return NULL;
1205
1206   while (1)
1207     {
1208       dir = (* search_func) (node->key, data);
1209       if (dir == 0)
1210         return node->value;
1211       else if (dir < 0)
1212         {
1213           if (!node->left_child)
1214             return NULL;
1215
1216           node = node->left;
1217         }
1218       else
1219         {
1220           if (!node->right_child)
1221             return NULL;
1222
1223           node = node->right;
1224         }
1225     }
1226 }
1227
1228 static GTreeNode *
1229 g_tree_node_rotate_left (GTreeNode *node)
1230 {
1231   GTreeNode *right;
1232   gint a_bal;
1233   gint b_bal;
1234
1235   right = node->right;
1236
1237   if (right->left_child)
1238     node->right = right->left;
1239   else
1240     {
1241       node->right_child = FALSE;
1242       right->left_child = TRUE;
1243     }
1244   right->left = node;
1245
1246   a_bal = node->balance;
1247   b_bal = right->balance;
1248
1249   if (b_bal <= 0)
1250     {
1251       if (a_bal >= 1)
1252         right->balance = b_bal - 1;
1253       else
1254         right->balance = a_bal + b_bal - 2;
1255       node->balance = a_bal - 1;
1256     }
1257   else
1258     {
1259       if (a_bal <= b_bal)
1260         right->balance = a_bal - 2;
1261       else
1262         right->balance = b_bal - 1;
1263       node->balance = a_bal - b_bal - 1;
1264     }
1265
1266   return right;
1267 }
1268
1269 static GTreeNode *
1270 g_tree_node_rotate_right (GTreeNode *node)
1271 {
1272   GTreeNode *left;
1273   gint a_bal;
1274   gint b_bal;
1275
1276   left = node->left;
1277
1278   if (left->right_child)
1279     node->left = left->right;
1280   else
1281     {
1282       node->left_child = FALSE;
1283       left->right_child = TRUE;
1284     }
1285   left->right = node;
1286
1287   a_bal = node->balance;
1288   b_bal = left->balance;
1289
1290   if (b_bal <= 0)
1291     {
1292       if (b_bal > a_bal)
1293         left->balance = b_bal + 1;
1294       else
1295         left->balance = a_bal + 2;
1296       node->balance = a_bal - b_bal + 1;
1297     }
1298   else
1299     {
1300       if (a_bal <= -1)
1301         left->balance = b_bal + 1;
1302       else
1303         left->balance = a_bal + b_bal + 2;
1304       node->balance = a_bal + 1;
1305     }
1306
1307   return left;
1308 }
1309
1310 #ifdef G_TREE_DEBUG
1311 static gint
1312 g_tree_node_height (GTreeNode *node)
1313 {
1314   gint left_height;
1315   gint right_height;
1316
1317   if (node)
1318     {
1319       left_height = 0;
1320       right_height = 0;
1321
1322       if (node->left_child)
1323         left_height = g_tree_node_height (node->left);
1324
1325       if (node->right_child)
1326         right_height = g_tree_node_height (node->right);
1327
1328       return MAX (left_height, right_height) + 1;
1329     }
1330
1331   return 0;
1332 }
1333
1334 static void
1335 g_tree_node_check (GTreeNode *node)
1336 {
1337   gint left_height;
1338   gint right_height;
1339   gint balance;
1340   GTreeNode *tmp;
1341
1342   if (node)
1343     {
1344       if (node->left_child)
1345         {
1346           tmp = g_tree_node_previous (node);
1347           g_assert (tmp->right == node);
1348         }
1349
1350       if (node->right_child)
1351         {
1352           tmp = g_tree_node_next (node);
1353           g_assert (tmp->left == node);
1354         }
1355
1356       left_height = 0;
1357       right_height = 0;
1358
1359       if (node->left_child)
1360         left_height = g_tree_node_height (node->left);
1361       if (node->right_child)
1362         right_height = g_tree_node_height (node->right);
1363
1364       balance = right_height - left_height;
1365       g_assert (balance == node->balance);
1366
1367       if (node->left_child)
1368         g_tree_node_check (node->left);
1369       if (node->right_child)
1370         g_tree_node_check (node->right);
1371     }
1372 }
1373
1374 static void
1375 g_tree_node_dump (GTreeNode *node,
1376                   gint       indent)
1377 {
1378   g_print ("%*s%c\n", indent, "", *(char *)node->key);
1379
1380   if (node->left_child)
1381     g_tree_node_dump (node->left, indent + 2);
1382   else if (node->left)
1383     g_print ("%*s<%c\n", indent + 2, "", *(char *)node->left->key);
1384
1385   if (node->right_child)
1386     g_tree_node_dump (node->right, indent + 2);
1387   else if (node->right)
1388     g_print ("%*s>%c\n", indent + 2, "", *(char *)node->right->key);
1389 }
1390
1391
1392 void
1393 g_tree_dump (GTree *tree)
1394 {
1395   if (tree->root)
1396     g_tree_node_dump (tree->root, 0);
1397 }
1398 #endif