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