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