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