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