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