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