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