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