glib/gtree.c

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