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