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