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 #ifdef HAVE_CONFIG_H
  32 #include <config.h>
  33 #endif
  34
  35 #include "glib.h"
  36
  37
  38 typedef struct _GRealTree  GRealTree;
  39 typedef struct _GTreeNode  GTreeNode;
  40
  41 struct _GRealTree
  42 {
  43   GTreeNode *root;
  44   GCompareDataFunc key_compare;
  45   gpointer key_compare_data;
  46 };
  47
  48 struct _GTreeNode
  49 {
  50   gint balance;      /* height (left) - height (right) */
  51   GTreeNode *left;   /* left subtree */
  52   GTreeNode *right;  /* right subtree */
  53   gpointer key;      /* key for this node */
  54   gpointer value;    /* value stored at this node */
  55 };
  56
  57
  58 static GTreeNode* g_tree_node_new                   (gpointer        key,
  59                                                      gpointer        value);
  60 static void       g_tree_node_destroy               (GTreeNode      *node);
  61 static GTreeNode* g_tree_node_insert                (GTreeNode      *node,
  62                                                      GCompareDataFunc compare,
  63                                                      gpointer        comp_data,
  64                                                      gpointer        key,
  65                                                      gpointer        value,
  66                                                      gint           *inserted);
  67 static GTreeNode* g_tree_node_remove                (GTreeNode      *node,
  68                                                      GCompareDataFunc compare,
  69                                                      gpointer        comp_data,
  70                                                      gconstpointer   key);
  71 static GTreeNode* g_tree_node_balance               (GTreeNode      *node);
  72 static GTreeNode* g_tree_node_remove_leftmost       (GTreeNode      *node,
  73                                                      GTreeNode     **leftmost);
  74 static GTreeNode* g_tree_node_restore_left_balance  (GTreeNode      *node,
  75                                                      gint            old_balance);
  76 static GTreeNode* g_tree_node_restore_right_balance (GTreeNode      *node,
  77                                                      gint            old_balance);
  78 static GTreeNode* g_tree_node_lookup                (GTreeNode      *node,
  79                                                      GCompareDataFunc compare,
  80                                                      gpointer        comp_data,
  81                                                      gconstpointer   key);
  82 static gint       g_tree_node_count                 (GTreeNode      *node);
  83 static gint       g_tree_node_pre_order             (GTreeNode      *node,
  84                                                      GTraverseFunc   traverse_func,
  85                                                      gpointer        data);
  86 static gint       g_tree_node_in_order              (GTreeNode      *node,
  87                                                      GTraverseFunc   traverse_func,
  88                                                      gpointer        data);
  89 static gint       g_tree_node_post_order            (GTreeNode      *node,
  90                                                      GTraverseFunc   traverse_func,
  91                                                      gpointer        data);
  92 static gpointer   g_tree_node_search                (GTreeNode      *node,
  93                                                      GCompareFunc    search_func,
  94                                                      gconstpointer   data);
  95 static gint       g_tree_node_height                (GTreeNode      *node);
  96 static GTreeNode* g_tree_node_rotate_left           (GTreeNode      *node);
  97 static GTreeNode* g_tree_node_rotate_right          (GTreeNode      *node);
  98 static void       g_tree_node_check                 (GTreeNode      *node);
  99
 100
 101 G_LOCK_DEFINE_STATIC (g_tree_global);
 102 static GMemChunk *node_mem_chunk = NULL;
 103 static GTreeNode *node_free_list = NULL;
 104
 105
 106 static GTreeNode*
 107 g_tree_node_new (gpointer key,
 108                  gpointer value)
 109 {
 110   GTreeNode *node;
 111
 112   G_LOCK (g_tree_global);
 113   if (node_free_list)
 114     {
 115       node = node_free_list;
 116       node_free_list = node->right;
 117     }
 118   else
 119     {
 120       if (!node_mem_chunk)
 121         node_mem_chunk = g_mem_chunk_new ("GLib GTreeNode mem chunk",
 122                                           sizeof (GTreeNode),
 123                                           1024,
 124                                           G_ALLOC_ONLY);
 125
 126       node = g_chunk_new (GTreeNode, node_mem_chunk);
 127    }
 128   G_UNLOCK (g_tree_global);
 129
 130   node->balance = 0;
 131   node->left = NULL;
 132   node->right = NULL;
 133   node->key = key;
 134   node->value = value;
 135
 136   return node;
 137 }
 138
 139 static void
 140 g_tree_node_destroy (GTreeNode *node)
 141 {
 142   if (node)
 143     {
 144       g_tree_node_destroy (node->right);
 145       g_tree_node_destroy (node->left);
 146
 147 #ifdef ENABLE_GC_FRIENDLY
 148       node->left = NULL;
 149       node->key = NULL;
 150       node->value = NULL;
 151 #endif /* ENABLE_GC_FRIENDLY */
 152
 153       G_LOCK (g_tree_global);
 154       node->right = node_free_list;
 155       node_free_list = node;
 156       G_UNLOCK (g_tree_global);
 157    }
 158 }
 159
 160 GTree*   g_tree_new_udata(GCompareDataFunc key_compare_func,
 161                           gpointer        key_compare_data)
 162 {
 163   GRealTree *rtree;
 164
 165   g_return_val_if_fail (key_compare_func != NULL, NULL);
 166
 167   rtree = g_new (GRealTree, 1);
 168   rtree->root = NULL;
 169   rtree->key_compare = key_compare_func;
 170   rtree->key_compare_data = key_compare_data;
 171
 172   return (GTree*) rtree;
 173 }
 174
 175 GTree*
 176 g_tree_new (GCompareFunc key_compare_func)
 177 {
 178   return g_tree_new_udata ((GCompareDataFunc) key_compare_func, NULL);
 179 }
 180
 181
 182 void
 183 g_tree_destroy (GTree *tree)
 184 {
 185   GRealTree *rtree;
 186
 187   g_return_if_fail (tree != NULL);
 188
 189   rtree = (GRealTree*) tree;
 190
 191   g_tree_node_destroy (rtree->root);
 192   g_free (rtree);
 193 }
 194
 195 void
 196 g_tree_insert (GTree    *tree,
 197                gpointer  key,
 198                gpointer  value)
 199 {
 200   GRealTree *rtree;
 201   gint inserted;
 202
 203   g_return_if_fail (tree != NULL);
 204
 205   rtree = (GRealTree*) tree;
 206
 207   inserted = FALSE;
 208   rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare,
 209                                     rtree->key_compare_data,
 210                                     key, value, &inserted);
 211 }
 212
 213 void
 214 g_tree_remove (GTree         *tree,
 215                gconstpointer  key)
 216 {
 217   GRealTree *rtree;
 218
 219   g_return_if_fail (tree != NULL);
 220
 221   rtree = (GRealTree*) tree;
 222
 223   rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare,
 224                                     rtree->key_compare_data, key);
 225 }
 226
 227 gpointer
 228 g_tree_lookup (GTree         *tree,
 229                gconstpointer  key)
 230 {
 231   GRealTree *rtree;
 232   GTreeNode *node;
 233
 234   g_return_val_if_fail (tree != NULL, NULL);
 235
 236   rtree = (GRealTree*) tree;
 237
 238   node = g_tree_node_lookup (rtree->root, rtree->key_compare,
 239                              rtree->key_compare_data, key);
 240
 241   return node ? node->value : NULL;
 242 }
 243
 244 gboolean
 245 g_tree_lookup_extended (GTree         *tree,
 246                         gconstpointer  lookup_key,
 247                         gpointer      *orig_key,
 248                         gpointer      *value)
 249 {
 250   GRealTree *rtree;
 251   GTreeNode *node;
 252
 253   g_return_val_if_fail (tree != NULL, FALSE);
 254
 255   rtree = (GRealTree*) tree;
 256
 257   node = g_tree_node_lookup (rtree->root,
 258                              rtree->key_compare,
 259                              rtree->key_compare_data,
 260                              lookup_key);
 261
 262   if (node)
 263     {
 264       if (orig_key)
 265         *orig_key = node->key;
 266       if (value)
 267         *value = node->value;
 268       return TRUE;
 269     }
 270   else
 271     return FALSE;
 272 }
 273
 274 void
 275 g_tree_traverse (GTree         *tree,
 276                  GTraverseFunc  traverse_func,
 277                  GTraverseType  traverse_type,
 278                  gpointer       data)
 279 {
 280   GRealTree *rtree;
 281
 282   g_return_if_fail (tree != NULL);
 283
 284   rtree = (GRealTree*) tree;
 285
 286   if (!rtree->root)
 287     return;
 288
 289   switch (traverse_type)
 290     {
 291     case G_PRE_ORDER:
 292       g_tree_node_pre_order (rtree->root, traverse_func, data);
 293       break;
 294
 295     case G_IN_ORDER:
 296       g_tree_node_in_order (rtree->root, traverse_func, data);
 297       break;
 298
 299     case G_POST_ORDER:
 300       g_tree_node_post_order (rtree->root, traverse_func, data);
 301       break;
 302
 303     case G_LEVEL_ORDER:
 304       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
 305       break;
 306     }
 307 }
 308
 309 gpointer
 310 g_tree_search (GTree            *tree,
 311                GCompareFunc      search_func,
 312                gconstpointer     data)
 313 {
 314   GRealTree *rtree;
 315
 316   g_return_val_if_fail (tree != NULL, NULL);
 317
 318   rtree = (GRealTree*) tree;
 319
 320   if (rtree->root)
 321     return g_tree_node_search (rtree->root, search_func, data);
 322   else
 323     return NULL;
 324 }
 325
 326 gint
 327 g_tree_height (GTree *tree)
 328 {
 329   GRealTree *rtree;
 330
 331   g_return_val_if_fail (tree != NULL, 0);
 332
 333   rtree = (GRealTree*) tree;
 334
 335   if (rtree->root)
 336     return g_tree_node_height (rtree->root);
 337   else
 338     return 0;
 339 }
 340
 341 gint
 342 g_tree_nnodes (GTree *tree)
 343 {
 344   GRealTree *rtree;
 345
 346   g_return_val_if_fail (tree != NULL, 0);
 347
 348   rtree = (GRealTree*) tree;
 349
 350   if (rtree->root)
 351     return g_tree_node_count (rtree->root);
 352   else
 353     return 0;
 354 }
 355
 356 static GTreeNode*
 357 g_tree_node_insert (GTreeNode      *node,
 358                     GCompareDataFunc compare,
 359                     gpointer        compare_data,
 360                     gpointer        key,
 361                     gpointer        value,
 362                     gint           *inserted)
 363 {
 364   gint old_balance;
 365   gint cmp;
 366
 367   if (!node)
 368     {
 369       *inserted = TRUE;
 370       return g_tree_node_new (key, value);
 371     }
 372
 373   cmp = (* compare) (key, node->key, compare_data);
 374   if (cmp == 0)
 375     {
 376       *inserted = FALSE;
 377       node->value = value;
 378       return node;
 379     }
 380
 381   if (cmp < 0)
 382     {
 383       if (node->left)
 384         {
 385           old_balance = node->left->balance;
 386           node->left = g_tree_node_insert (node->left, compare, compare_data,
 387                                            key, value, inserted);
 388
 389           if ((old_balance != node->left->balance) && node->left->balance)
 390             node->balance -= 1;
 391         }
 392       else
 393         {
 394           *inserted = TRUE;
 395           node->left = g_tree_node_new (key, value);
 396           node->balance -= 1;
 397         }
 398     }
 399   else if (cmp > 0)
 400     {
 401       if (node->right)
 402         {
 403           old_balance = node->right->balance;
 404           node->right = g_tree_node_insert (node->right, compare, compare_data,
 405                                             key, value, inserted);
 406
 407           if ((old_balance != node->right->balance) && node->right->balance)
 408             node->balance += 1;
 409         }
 410       else
 411         {
 412           *inserted = TRUE;
 413           node->right = g_tree_node_new (key, value);
 414           node->balance += 1;
 415         }
 416     }
 417
 418   if (*inserted)
 419     {
 420       if ((node->balance < -1) || (node->balance > 1))
 421         node = g_tree_node_balance (node);
 422     }
 423
 424   return node;
 425 }
 426
 427 static GTreeNode*
 428 g_tree_node_remove (GTreeNode      *node,
 429                     GCompareDataFunc compare,
 430                     gpointer        compare_data,
 431                     gconstpointer   key)
 432 {
 433   GTreeNode *new_root;
 434   gint old_balance;
 435   gint cmp;
 436
 437   if (!node)
 438     return NULL;
 439
 440   cmp = (* compare) (key, node->key, compare_data);
 441   if (cmp == 0)
 442     {
 443       GTreeNode *garbage;
 444
 445       garbage = node;
 446
 447       if (!node->right)
 448         {
 449           node = node->left;
 450         }
 451       else
 452         {
 453           old_balance = node->right->balance;
 454           node->right = g_tree_node_remove_leftmost (node->right, &new_root);
 455           new_root->left = node->left;
 456           new_root->right = node->right;
 457           new_root->balance = node->balance;
 458           node = g_tree_node_restore_right_balance (new_root, old_balance);
 459         }
 460
 461 #ifdef ENABLE_GC_FRIENDLY
 462       garbage->left = NULL;
 463       garbage->key = NULL;
 464       garbage->value = NULL;
 465 #endif /* ENABLE_GC_FRIENDLY */
 466
 467       G_LOCK (g_tree_global);
 468       garbage->right = node_free_list;
 469       node_free_list = garbage;
 470       G_UNLOCK (g_tree_global);
 471    }
 472   else if (cmp < 0)
 473     {
 474       if (node->left)
 475         {
 476           old_balance = node->left->balance;
 477           node->left = g_tree_node_remove (node->left, compare, compare_data, key);
 478           node = g_tree_node_restore_left_balance (node, old_balance);
 479         }
 480     }
 481   else if (cmp > 0)
 482     {
 483       if (node->right)
 484         {
 485           old_balance = node->right->balance;
 486           node->right = g_tree_node_remove (node->right, compare, compare_data, key);
 487           node = g_tree_node_restore_right_balance (node, old_balance);
 488         }
 489     }
 490
 491   return node;
 492 }
 493
 494 static GTreeNode*
 495 g_tree_node_balance (GTreeNode *node)
 496 {
 497   if (node->balance < -1)
 498     {
 499       if (node->left->balance > 0)
 500         node->left = g_tree_node_rotate_left (node->left);
 501       node = g_tree_node_rotate_right (node);
 502     }
 503   else if (node->balance > 1)
 504     {
 505       if (node->right->balance < 0)
 506         node->right = g_tree_node_rotate_right (node->right);
 507       node = g_tree_node_rotate_left (node);
 508     }
 509
 510   return node;
 511 }
 512
 513 static GTreeNode*
 514 g_tree_node_remove_leftmost (GTreeNode  *node,
 515                              GTreeNode **leftmost)
 516 {
 517   gint old_balance;
 518
 519   if (!node->left)
 520     {
 521       *leftmost = node;
 522       return node->right;
 523     }
 524
 525   old_balance = node->left->balance;
 526   node->left = g_tree_node_remove_leftmost (node->left, leftmost);
 527   return g_tree_node_restore_left_balance (node, old_balance);
 528 }
 529
 530 static GTreeNode*
 531 g_tree_node_restore_left_balance (GTreeNode *node,
 532                                   gint       old_balance)
 533 {
 534   if (!node->left)
 535     node->balance += 1;
 536   else if ((node->left->balance != old_balance) &&
 537            (node->left->balance == 0))
 538     node->balance += 1;
 539
 540   if (node->balance > 1)
 541     return g_tree_node_balance (node);
 542   return node;
 543 }
 544
 545 static GTreeNode*
 546 g_tree_node_restore_right_balance (GTreeNode *node,
 547                                    gint       old_balance)
 548 {
 549   if (!node->right)
 550     node->balance -= 1;
 551   else if ((node->right->balance != old_balance) &&
 552            (node->right->balance == 0))
 553     node->balance -= 1;
 554
 555   if (node->balance < -1)
 556     return g_tree_node_balance (node);
 557   return node;
 558 }
 559
 560 static GTreeNode *
 561 g_tree_node_lookup (GTreeNode      *node,
 562                     GCompareDataFunc compare,
 563                     gpointer        compare_data,
 564                     gconstpointer   key)
 565 {
 566   gint cmp;
 567
 568   if (!node)
 569     return NULL;
 570
 571   cmp = (* compare) (key, node->key, compare_data);
 572   if (cmp == 0)
 573     return node;
 574
 575   if (cmp < 0)
 576     {
 577       if (node->left)
 578         return g_tree_node_lookup (node->left, compare, compare_data, key);
 579     }
 580   else if (cmp > 0)
 581     {
 582       if (node->right)
 583         return g_tree_node_lookup (node->right, compare, compare_data, key);
 584     }
 585
 586   return NULL;
 587 }
 588
 589 static gint
 590 g_tree_node_count (GTreeNode *node)
 591 {
 592   gint count;
 593
 594   count = 1;
 595   if (node->left)
 596     count += g_tree_node_count (node->left);
 597   if (node->right)
 598     count += g_tree_node_count (node->right);
 599
 600   return count;
 601 }
 602
 603 static gint
 604 g_tree_node_pre_order (GTreeNode     *node,
 605                        GTraverseFunc  traverse_func,
 606                        gpointer       data)
 607 {
 608   if ((*traverse_func) (node->key, node->value, data))
 609     return TRUE;
 610   if (node->left)
 611     {
 612       if (g_tree_node_pre_order (node->left, traverse_func, data))
 613         return TRUE;
 614     }
 615   if (node->right)
 616     {
 617       if (g_tree_node_pre_order (node->right, traverse_func, data))
 618         return TRUE;
 619     }
 620
 621   return FALSE;
 622 }
 623
 624 static gint
 625 g_tree_node_in_order (GTreeNode     *node,
 626                       GTraverseFunc  traverse_func,
 627                       gpointer       data)
 628 {
 629   if (node->left)
 630     {
 631       if (g_tree_node_in_order (node->left, traverse_func, data))
 632         return TRUE;
 633     }
 634   if ((*traverse_func) (node->key, node->value, data))
 635     return TRUE;
 636   if (node->right)
 637     {
 638       if (g_tree_node_in_order (node->right, traverse_func, data))
 639         return TRUE;
 640     }
 641
 642   return FALSE;
 643 }
 644
 645 static gint
 646 g_tree_node_post_order (GTreeNode     *node,
 647                         GTraverseFunc  traverse_func,
 648                         gpointer       data)
 649 {
 650   if (node->left)
 651     {
 652       if (g_tree_node_post_order (node->left, traverse_func, data))
 653         return TRUE;
 654     }
 655   if (node->right)
 656     {
 657       if (g_tree_node_post_order (node->right, traverse_func, data))
 658         return TRUE;
 659     }
 660   if ((*traverse_func) (node->key, node->value, data))
 661     return TRUE;
 662
 663   return FALSE;
 664 }
 665
 666 static gpointer
 667 g_tree_node_search (GTreeNode     *node,
 668                     GCompareFunc   search_func,
 669                     gconstpointer  data)
 670 {
 671   gint dir;
 672
 673   if (!node)
 674     return NULL;
 675
 676   do {
 677     dir = (* search_func) (node->key, data);
 678     if (dir == 0)
 679       return node->value;
 680
 681     if (dir < 0)
 682       node = node->left;
 683     else if (dir > 0)
 684       node = node->right;
 685   } while (node);
 686
 687   return NULL;
 688 }
 689
 690 static gint
 691 g_tree_node_height (GTreeNode *node)
 692 {
 693   gint left_height;
 694   gint right_height;
 695
 696   if (node)
 697     {
 698       left_height = 0;
 699       right_height = 0;
 700
 701       if (node->left)
 702         left_height = g_tree_node_height (node->left);
 703
 704       if (node->right)
 705         right_height = g_tree_node_height (node->right);
 706
 707       return MAX (left_height, right_height) + 1;
 708     }
 709
 710   return 0;
 711 }
 712
 713 static GTreeNode*
 714 g_tree_node_rotate_left (GTreeNode *node)
 715 {
 716   GTreeNode *right;
 717   gint a_bal;
 718   gint b_bal;
 719
 720   right = node->right;
 721
 722   node->right = right->left;
 723   right->left = node;
 724
 725   a_bal = node->balance;
 726   b_bal = right->balance;
 727
 728   if (b_bal <= 0)
 729     {
 730       if (a_bal >= 1)
 731         right->balance = b_bal - 1;
 732       else
 733         right->balance = a_bal + b_bal - 2;
 734       node->balance = a_bal - 1;
 735     }
 736   else
 737     {
 738       if (a_bal <= b_bal)
 739         right->balance = a_bal - 2;
 740       else
 741         right->balance = b_bal - 1;
 742       node->balance = a_bal - b_bal - 1;
 743     }
 744
 745   return right;
 746 }
 747
 748 static GTreeNode*
 749 g_tree_node_rotate_right (GTreeNode *node)
 750 {
 751   GTreeNode *left;
 752   gint a_bal;
 753   gint b_bal;
 754
 755   left = node->left;
 756
 757   node->left = left->right;
 758   left->right = node;
 759
 760   a_bal = node->balance;
 761   b_bal = left->balance;
 762
 763   if (b_bal <= 0)
 764     {
 765       if (b_bal > a_bal)
 766         left->balance = b_bal + 1;
 767       else
 768         left->balance = a_bal + 2;
 769       node->balance = a_bal - b_bal + 1;
 770     }
 771   else
 772     {
 773       if (a_bal <= -1)
 774         left->balance = b_bal + 1;
 775       else
 776         left->balance = a_bal + b_bal + 2;
 777       node->balance = a_bal + 1;
 778     }
 779
 780   return left;
 781 }
 782
 783 static void
 784 g_tree_node_check (GTreeNode *node)
 785 {
 786   gint left_height;
 787   gint right_height;
 788   gint balance;
 789
 790   if (node)
 791     {
 792       left_height = 0;
 793       right_height = 0;
 794
 795       if (node->left)
 796         left_height = g_tree_node_height (node->left);
 797       if (node->right)
 798         right_height = g_tree_node_height (node->right);
 799
 800       balance = right_height - left_height;
 801       if (balance != node->balance)
 802         g_log (g_log_domain_glib, G_LOG_LEVEL_INFO,
 803                "g_tree_node_check: failed: %d ( %d )\n",
 804                balance, node->balance);
 805
 806       if (node->left)
 807         g_tree_node_check (node->left);
 808       if (node->right)
 809         g_tree_node_check (node->right);
 810     }
 811 }