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