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 gboolean
 242 g_tree_lookup_extended (GTree         *tree,
 243                         gconstpointer  lookup_key,
 244                         gpointer      *orig_key,
 245                         gpointer      *value)
 246 {
 247   GRealTree *rtree;
 248   GTreeNode *node;
 249
 250   g_return_val_if_fail (tree != NULL, FALSE);
 251
 252   rtree = (GRealTree*) tree;
 253
 254   node = g_tree_node_lookup (rtree->root,
 255                              rtree->key_compare,
 256                              rtree->key_compare_data,
 257                              lookup_key);
 258
 259   if (node)
 260     {
 261       if (orig_key)
 262         *orig_key = node->key;
 263       if (value)
 264         *value = node->value;
 265       return TRUE;
 266     }
 267   else
 268     return FALSE;
 269 }
 270
 271 void
 272 g_tree_traverse (GTree         *tree,
 273                  GTraverseFunc  traverse_func,
 274                  GTraverseType  traverse_type,
 275                  gpointer       data)
 276 {
 277   GRealTree *rtree;
 278
 279   g_return_if_fail (tree != NULL);
 280
 281   rtree = (GRealTree*) tree;
 282
 283   if (!rtree->root)
 284     return;
 285
 286   switch (traverse_type)
 287     {
 288     case G_PRE_ORDER:
 289       g_tree_node_pre_order (rtree->root, traverse_func, data);
 290       break;
 291
 292     case G_IN_ORDER:
 293       g_tree_node_in_order (rtree->root, traverse_func, data);
 294       break;
 295
 296     case G_POST_ORDER:
 297       g_tree_node_post_order (rtree->root, traverse_func, data);
 298       break;
 299
 300     case G_LEVEL_ORDER:
 301       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
 302       break;
 303     }
 304 }
 305
 306 gpointer
 307 g_tree_search (GTree            *tree,
 308                GCompareFunc      search_func,
 309                gconstpointer     data)
 310 {
 311   GRealTree *rtree;
 312
 313   g_return_val_if_fail (tree != NULL, NULL);
 314
 315   rtree = (GRealTree*) tree;
 316
 317   if (rtree->root)
 318     return g_tree_node_search (rtree->root, search_func, data);
 319   else
 320     return NULL;
 321 }
 322
 323 gint
 324 g_tree_height (GTree *tree)
 325 {
 326   GRealTree *rtree;
 327
 328   g_return_val_if_fail (tree != NULL, 0);
 329
 330   rtree = (GRealTree*) tree;
 331
 332   if (rtree->root)
 333     return g_tree_node_height (rtree->root);
 334   else
 335     return 0;
 336 }
 337
 338 gint
 339 g_tree_nnodes (GTree *tree)
 340 {
 341   GRealTree *rtree;
 342
 343   g_return_val_if_fail (tree != NULL, 0);
 344
 345   rtree = (GRealTree*) tree;
 346
 347   if (rtree->root)
 348     return g_tree_node_count (rtree->root);
 349   else
 350     return 0;
 351 }
 352
 353 static GTreeNode*
 354 g_tree_node_insert (GTreeNode      *node,
 355                     GCompareDataFunc compare,
 356                     gpointer        compare_data,
 357                     gpointer        key,
 358                     gpointer        value,
 359                     gint           *inserted)
 360 {
 361   gint old_balance;
 362   gint cmp;
 363
 364   if (!node)
 365     {
 366       *inserted = TRUE;
 367       return g_tree_node_new (key, value);
 368     }
 369
 370   cmp = (* compare) (key, node->key, compare_data);
 371   if (cmp == 0)
 372     {
 373       *inserted = FALSE;
 374       node->value = value;
 375       return node;
 376     }
 377
 378   if (cmp < 0)
 379     {
 380       if (node->left)
 381         {
 382           old_balance = node->left->balance;
 383           node->left = g_tree_node_insert (node->left, compare, compare_data,
 384                                            key, value, inserted);
 385
 386           if ((old_balance != node->left->balance) && node->left->balance)
 387             node->balance -= 1;
 388         }
 389       else
 390         {
 391           *inserted = TRUE;
 392           node->left = g_tree_node_new (key, value);
 393           node->balance -= 1;
 394         }
 395     }
 396   else if (cmp > 0)
 397     {
 398       if (node->right)
 399         {
 400           old_balance = node->right->balance;
 401           node->right = g_tree_node_insert (node->right, compare, compare_data,
 402                                             key, value, inserted);
 403
 404           if ((old_balance != node->right->balance) && node->right->balance)
 405             node->balance += 1;
 406         }
 407       else
 408         {
 409           *inserted = TRUE;
 410           node->right = g_tree_node_new (key, value);
 411           node->balance += 1;
 412         }
 413     }
 414
 415   if (*inserted)
 416     {
 417       if ((node->balance < -1) || (node->balance > 1))
 418         node = g_tree_node_balance (node);
 419     }
 420
 421   return node;
 422 }
 423
 424 static GTreeNode*
 425 g_tree_node_remove (GTreeNode      *node,
 426                     GCompareDataFunc compare,
 427                     gpointer        compare_data,
 428                     gconstpointer   key)
 429 {
 430   GTreeNode *new_root;
 431   gint old_balance;
 432   gint cmp;
 433
 434   if (!node)
 435     return NULL;
 436
 437   cmp = (* compare) (key, node->key, compare_data);
 438   if (cmp == 0)
 439     {
 440       GTreeNode *garbage;
 441
 442       garbage = node;
 443
 444       if (!node->right)
 445         {
 446           node = node->left;
 447         }
 448       else
 449         {
 450           old_balance = node->right->balance;
 451           node->right = g_tree_node_remove_leftmost (node->right, &new_root);
 452           new_root->left = node->left;
 453           new_root->right = node->right;
 454           new_root->balance = node->balance;
 455           node = g_tree_node_restore_right_balance (new_root, old_balance);
 456         }
 457
 458 #ifdef ENABLE_GC_FRIENDLY
 459       garbage->left = NULL;
 460       garbage->key = NULL;
 461       garbage->value = NULL;
 462 #endif /* ENABLE_GC_FRIENDLY */
 463
 464       G_LOCK (g_tree_global);
 465       garbage->right = node_free_list;
 466       node_free_list = garbage;
 467       G_UNLOCK (g_tree_global);
 468    }
 469   else if (cmp < 0)
 470     {
 471       if (node->left)
 472         {
 473           old_balance = node->left->balance;
 474           node->left = g_tree_node_remove (node->left, compare, compare_data, key);
 475           node = g_tree_node_restore_left_balance (node, old_balance);
 476         }
 477     }
 478   else if (cmp > 0)
 479     {
 480       if (node->right)
 481         {
 482           old_balance = node->right->balance;
 483           node->right = g_tree_node_remove (node->right, compare, compare_data, key);
 484           node = g_tree_node_restore_right_balance (node, old_balance);
 485         }
 486     }
 487
 488   return node;
 489 }
 490
 491 static GTreeNode*
 492 g_tree_node_balance (GTreeNode *node)
 493 {
 494   if (node->balance < -1)
 495     {
 496       if (node->left->balance > 0)
 497         node->left = g_tree_node_rotate_left (node->left);
 498       node = g_tree_node_rotate_right (node);
 499     }
 500   else if (node->balance > 1)
 501     {
 502       if (node->right->balance < 0)
 503         node->right = g_tree_node_rotate_right (node->right);
 504       node = g_tree_node_rotate_left (node);
 505     }
 506
 507   return node;
 508 }
 509
 510 static GTreeNode*
 511 g_tree_node_remove_leftmost (GTreeNode  *node,
 512                              GTreeNode **leftmost)
 513 {
 514   gint old_balance;
 515
 516   if (!node->left)
 517     {
 518       *leftmost = node;
 519       return node->right;
 520     }
 521
 522   old_balance = node->left->balance;
 523   node->left = g_tree_node_remove_leftmost (node->left, leftmost);
 524   return g_tree_node_restore_left_balance (node, old_balance);
 525 }
 526
 527 static GTreeNode*
 528 g_tree_node_restore_left_balance (GTreeNode *node,
 529                                   gint       old_balance)
 530 {
 531   if (!node->left)
 532     node->balance += 1;
 533   else if ((node->left->balance != old_balance) &&
 534            (node->left->balance == 0))
 535     node->balance += 1;
 536
 537   if (node->balance > 1)
 538     return g_tree_node_balance (node);
 539   return node;
 540 }
 541
 542 static GTreeNode*
 543 g_tree_node_restore_right_balance (GTreeNode *node,
 544                                    gint       old_balance)
 545 {
 546   if (!node->right)
 547     node->balance -= 1;
 548   else if ((node->right->balance != old_balance) &&
 549            (node->right->balance == 0))
 550     node->balance -= 1;
 551
 552   if (node->balance < -1)
 553     return g_tree_node_balance (node);
 554   return node;
 555 }
 556
 557 static gpointer
 558 g_tree_node_lookup (GTreeNode      *node,
 559                     GCompareDataFunc compare,
 560                     gpointer        compare_data,
 561                     gconstpointer   key)
 562 {
 563   gint cmp;
 564
 565   if (!node)
 566     return NULL;
 567
 568   cmp = (* compare) (key, node->key, compare_data);
 569   if (cmp == 0)
 570     return node->value;
 571
 572   if (cmp < 0)
 573     {
 574       if (node->left)
 575         return g_tree_node_lookup (node->left, compare, compare_data, key);
 576     }
 577   else if (cmp > 0)
 578     {
 579       if (node->right)
 580         return g_tree_node_lookup (node->right, compare, compare_data, key);
 581     }
 582
 583   return NULL;
 584 }
 585
 586 static gint
 587 g_tree_node_count (GTreeNode *node)
 588 {
 589   gint count;
 590
 591   count = 1;
 592   if (node->left)
 593     count += g_tree_node_count (node->left);
 594   if (node->right)
 595     count += g_tree_node_count (node->right);
 596
 597   return count;
 598 }
 599
 600 static gint
 601 g_tree_node_pre_order (GTreeNode     *node,
 602                        GTraverseFunc  traverse_func,
 603                        gpointer       data)
 604 {
 605   if ((*traverse_func) (node->key, node->value, data))
 606     return TRUE;
 607   if (node->left)
 608     {
 609       if (g_tree_node_pre_order (node->left, traverse_func, data))
 610         return TRUE;
 611     }
 612   if (node->right)
 613     {
 614       if (g_tree_node_pre_order (node->right, traverse_func, data))
 615         return TRUE;
 616     }
 617
 618   return FALSE;
 619 }
 620
 621 static gint
 622 g_tree_node_in_order (GTreeNode     *node,
 623                       GTraverseFunc  traverse_func,
 624                       gpointer       data)
 625 {
 626   if (node->left)
 627     {
 628       if (g_tree_node_in_order (node->left, traverse_func, data))
 629         return TRUE;
 630     }
 631   if ((*traverse_func) (node->key, node->value, data))
 632     return TRUE;
 633   if (node->right)
 634     {
 635       if (g_tree_node_in_order (node->right, traverse_func, data))
 636         return TRUE;
 637     }
 638
 639   return FALSE;
 640 }
 641
 642 static gint
 643 g_tree_node_post_order (GTreeNode     *node,
 644                         GTraverseFunc  traverse_func,
 645                         gpointer       data)
 646 {
 647   if (node->left)
 648     {
 649       if (g_tree_node_post_order (node->left, traverse_func, data))
 650         return TRUE;
 651     }
 652   if (node->right)
 653     {
 654       if (g_tree_node_post_order (node->right, traverse_func, data))
 655         return TRUE;
 656     }
 657   if ((*traverse_func) (node->key, node->value, data))
 658     return TRUE;
 659
 660   return FALSE;
 661 }
 662
 663 static gpointer
 664 g_tree_node_search (GTreeNode     *node,
 665                     GCompareFunc   search_func,
 666                     gconstpointer  data)
 667 {
 668   gint dir;
 669
 670   if (!node)
 671     return NULL;
 672
 673   do {
 674     dir = (* search_func) (node->key, data);
 675     if (dir == 0)
 676       return node->value;
 677
 678     if (dir < 0)
 679       node = node->left;
 680     else if (dir > 0)
 681       node = node->right;
 682   } while (node);
 683
 684   return NULL;
 685 }
 686
 687 static gint
 688 g_tree_node_height (GTreeNode *node)
 689 {
 690   gint left_height;
 691   gint right_height;
 692
 693   if (node)
 694     {
 695       left_height = 0;
 696       right_height = 0;
 697
 698       if (node->left)
 699         left_height = g_tree_node_height (node->left);
 700
 701       if (node->right)
 702         right_height = g_tree_node_height (node->right);
 703
 704       return MAX (left_height, right_height) + 1;
 705     }
 706
 707   return 0;
 708 }
 709
 710 static GTreeNode*
 711 g_tree_node_rotate_left (GTreeNode *node)
 712 {
 713   GTreeNode *right;
 714   gint a_bal;
 715   gint b_bal;
 716
 717   right = node->right;
 718
 719   node->right = right->left;
 720   right->left = node;
 721
 722   a_bal = node->balance;
 723   b_bal = right->balance;
 724
 725   if (b_bal <= 0)
 726     {
 727       if (a_bal >= 1)
 728         right->balance = b_bal - 1;
 729       else
 730         right->balance = a_bal + b_bal - 2;
 731       node->balance = a_bal - 1;
 732     }
 733   else
 734     {
 735       if (a_bal <= b_bal)
 736         right->balance = a_bal - 2;
 737       else
 738         right->balance = b_bal - 1;
 739       node->balance = a_bal - b_bal - 1;
 740     }
 741
 742   return right;
 743 }
 744
 745 static GTreeNode*
 746 g_tree_node_rotate_right (GTreeNode *node)
 747 {
 748   GTreeNode *left;
 749   gint a_bal;
 750   gint b_bal;
 751
 752   left = node->left;
 753
 754   node->left = left->right;
 755   left->right = node;
 756
 757   a_bal = node->balance;
 758   b_bal = left->balance;
 759
 760   if (b_bal <= 0)
 761     {
 762       if (b_bal > a_bal)
 763         left->balance = b_bal + 1;
 764       else
 765         left->balance = a_bal + 2;
 766       node->balance = a_bal - b_bal + 1;
 767     }
 768   else
 769     {
 770       if (a_bal <= -1)
 771         left->balance = b_bal + 1;
 772       else
 773         left->balance = a_bal + b_bal + 2;
 774       node->balance = a_bal + 1;
 775     }
 776
 777   return left;
 778 }
 779
 780 static void
 781 g_tree_node_check (GTreeNode *node)
 782 {
 783   gint left_height;
 784   gint right_height;
 785   gint balance;
 786
 787   if (node)
 788     {
 789       left_height = 0;
 790       right_height = 0;
 791
 792       if (node->left)
 793         left_height = g_tree_node_height (node->left);
 794       if (node->right)
 795         right_height = g_tree_node_height (node->right);
 796
 797       balance = right_height - left_height;
 798       if (balance != node->balance)
 799         g_log (g_log_domain_glib, G_LOG_LEVEL_INFO,
 800                "g_tree_node_check: failed: %d ( %d )\n",
 801                balance, node->balance);
 802
 803       if (node->left)
 804         g_tree_node_check (node->left);
 805       if (node->right)
 806         g_tree_node_check (node->right);
 807     }
 808 }