et-forest.c revision 117395
1/* ET-trees datastructure implementation. 2 Contributed by Pavel Nejedly 3 Copyright (C) 2002 Free Software Foundation, Inc. 4 5This file is part of the libiberty library. 6Libiberty is free software; you can redistribute it and/or 7modify it under the terms of the GNU Library General Public 8License as published by the Free Software Foundation; either 9version 2 of the License, or (at your option) any later version. 10 11Libiberty is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14Library General Public License for more details. 15 16You should have received a copy of the GNU Library General Public 17License along with libiberty; see the file COPYING.LIB. If 18not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, 19Boston, MA 02111-1307, USA. 20 21 The ET-forest structure is described in: 22 D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. 23 J. G'omput. System Sci., 26(3):362 381, 1983. 24*/ 25 26#include "config.h" 27#include "system.h" 28#include "et-forest.h" 29 30struct et_forest_occurrence; 31typedef struct et_forest_occurrence* et_forest_occurrence_t; 32 33/* The ET-forest type. */ 34struct et_forest 35{ 36 /* Linked list of nodes is used to destroy the structure. */ 37 int nnodes; 38}; 39 40/* Single occurrence of node in ET-forest. 41 A single node may have multiple occurrences. 42 */ 43struct et_forest_occurrence 44{ 45 /* Parent in the splay-tree. */ 46 et_forest_occurrence_t parent; 47 48 /* Children in the splay-tree. */ 49 et_forest_occurrence_t left, right; 50 51 /* Counts of vertices in the two splay-subtrees. */ 52 int count_left, count_right; 53 54 /* Next occurrence of this node in the sequence. */ 55 et_forest_occurrence_t next; 56 57 /* The node, which this occurrence is of. */ 58 et_forest_node_t node; 59}; 60 61 62/* ET-forest node. */ 63struct et_forest_node 64{ 65 et_forest_t forest; 66 void *value; 67 68 /* First and last occurrence of this node in the sequence. */ 69 et_forest_occurrence_t first, last; 70}; 71 72 73static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t)); 74static void remove_all_occurrences PARAMS ((et_forest_node_t)); 75static inline et_forest_occurrence_t find_leftmost_node 76 PARAMS ((et_forest_occurrence_t)); 77static inline et_forest_occurrence_t find_rightmost_node 78 PARAMS ((et_forest_occurrence_t)); 79static int calculate_value PARAMS ((et_forest_occurrence_t)); 80 81/* Return leftmost node present in the tree roted by OCC. */ 82static inline et_forest_occurrence_t 83find_leftmost_node (occ) 84 et_forest_occurrence_t occ; 85{ 86 while (occ->left) 87 occ = occ->left; 88 89 return occ; 90} 91 92/* Return rightmost node present in the tree roted by OCC. */ 93static inline et_forest_occurrence_t 94find_rightmost_node (occ) 95 et_forest_occurrence_t occ; 96{ 97 while (occ->right) 98 occ = occ->right; 99 return occ; 100} 101 102 103/* Operation splay for splay tree structure representing ocuurences. */ 104static et_forest_occurrence_t 105splay (node) 106 et_forest_occurrence_t node; 107{ 108 et_forest_occurrence_t parent; 109 et_forest_occurrence_t grandparent; 110 111 while (1) 112 { 113 parent = node->parent; 114 115 if (! parent) 116 return node; /* node == root. */ 117 118 grandparent = parent->parent; 119 120 if (! grandparent) 121 break; 122 123 /* Now there are four possible combinations: */ 124 125 if (node == parent->left) 126 { 127 if (parent == grandparent->left) 128 { 129 et_forest_occurrence_t node1, node2; 130 int count1, count2; 131 132 node1 = node->right; 133 count1 = node->count_right; 134 node2 = parent->right; 135 count2 = parent->count_right; 136 137 grandparent->left = node2; 138 grandparent->count_left = count2; 139 if (node2) 140 node2->parent = grandparent; 141 parent->left = node1; 142 parent->count_left = count1; 143 if (node1) 144 node1->parent = parent; 145 parent->right = grandparent; 146 parent->count_right = count2 + grandparent->count_right + 1; 147 node->right = parent; 148 node->count_right = count1 + parent->count_right + 1; 149 150 node->parent = grandparent->parent; 151 parent->parent = node; 152 grandparent->parent = parent; 153 154 if (node->parent) 155 { 156 if (node->parent->left == grandparent) 157 node->parent->left = node; 158 else 159 node->parent->right = node; 160 } 161 } 162 else 163 { 164 /* parent == grandparent->right && node == parent->left*/ 165 et_forest_occurrence_t node1, node2; 166 int count1, count2; 167 168 node1 = node->left; 169 count1 = node->count_left; 170 node2 = node->right; 171 count2 = node->count_right; 172 173 grandparent->right = node1; 174 grandparent->count_right = count1; 175 if (node1) 176 node1->parent = grandparent; 177 parent->left = node2; 178 parent->count_left = count2; 179 if (node2) 180 node2->parent = parent; 181 node->left = grandparent; 182 node->count_left = grandparent->count_left + count1 + 1; 183 node->right = parent; 184 node->count_right = parent->count_right + count2 + 1; 185 186 node->parent = grandparent->parent; 187 parent->parent = node; 188 grandparent->parent = node; 189 190 if (node->parent) 191 { 192 if (node->parent->left == grandparent) 193 node->parent->left = node; 194 else 195 node->parent->right = node; 196 } 197 } 198 } 199 else 200 { 201 /* node == parent->right. */ 202 if (parent == grandparent->left) 203 { 204 et_forest_occurrence_t node1, node2; 205 int count1, count2; 206 207 node1 = node->left; 208 count1 = node->count_left; 209 node2 = node->right; 210 count2 = node->count_right; 211 212 parent->right = node1; 213 parent->count_right = count1; 214 if (node1) 215 node1->parent = parent; 216 grandparent->left = node2; 217 grandparent->count_left = count2; 218 if (node2) 219 node2->parent = grandparent; 220 node->left = parent; 221 node->count_left = parent->count_left + count1 + 1; 222 node->right = grandparent; 223 node->count_right = grandparent->count_right + count2 + 1; 224 225 node->parent = grandparent->parent; 226 parent->parent = node; 227 grandparent->parent = node; 228 229 if (node->parent) 230 { 231 if (node->parent->left == grandparent) 232 node->parent->left = node; 233 else 234 node->parent->right = node; 235 } 236 } 237 else 238 { 239 /* parent == grandparent->right && node == parent->right*/ 240 et_forest_occurrence_t node1, node2; 241 int count1, count2; 242 243 node1 = node->left; 244 count1 = node->count_left; 245 node2 = parent->left; 246 count2 = parent->count_left; 247 248 grandparent->right = node2; 249 grandparent->count_right = count2; 250 if (node2) 251 node2->parent = grandparent; 252 parent->right = node1; 253 parent->count_right = count1; 254 if (node1) 255 node1->parent = parent; 256 parent->left = grandparent; 257 parent->count_left = count2 + grandparent->count_left + 1; 258 node->left = parent; 259 node->count_left = count1 + parent->count_left + 1; 260 261 node->parent = grandparent->parent; 262 parent->parent = node; 263 grandparent->parent = parent; 264 265 if (node->parent) 266 { 267 if (node->parent->left == grandparent) 268 node->parent->left = node; 269 else 270 node->parent->right = node; 271 } 272 } 273 } 274 275 } 276 277 /* parent == root. */ 278 /* There are two possible combinations: */ 279 280 if (node == parent->left) 281 { 282 et_forest_occurrence_t node1; 283 int count1; 284 285 node1 = node->right; 286 count1 = node->count_right; 287 288 parent->left = node1; 289 parent->count_left = count1; 290 if (node1) 291 node1->parent = parent; 292 node->right = parent; 293 node->count_right = parent->count_right + 1 + count1; 294 node->parent = parent->parent; /* the same as = 0; */ 295 parent->parent = node; 296 297 if (node->parent) 298 { 299 if (node->parent->left == parent) 300 node->parent->left = node; 301 else 302 node->parent->right = node; 303 } 304 } 305 else 306 { 307 /* node == parent->right. */ 308 et_forest_occurrence_t node1; 309 int count1; 310 311 node1 = node->left; 312 count1 = node->count_left; 313 314 parent->right = node1; 315 parent->count_right = count1; 316 if (node1) 317 node1->parent = parent; 318 node->left = parent; 319 node->count_left = parent->count_left + 1 + count1; 320 node->parent = parent->parent; /* the same as = 0; */ 321 parent->parent = node; 322 323 if (node->parent) 324 { 325 if (node->parent->left == parent) 326 node->parent->left = node; 327 else 328 node->parent->right = node; 329 } 330 } 331 332 return node; 333} 334 335/* Remove all occurences of the given node before destroying the node. */ 336static void 337remove_all_occurrences (forest_node) 338 et_forest_node_t forest_node; 339{ 340 et_forest_occurrence_t first = forest_node->first; 341 et_forest_occurrence_t last = forest_node->last; 342 et_forest_occurrence_t node; 343 344 splay (first); 345 346 if (first->left) 347 first->left->parent = 0; 348 if (first->right) 349 first->right->parent = 0; 350 351 if (last != first) 352 { 353 splay (last); 354 355 if (last->left) 356 last->left->parent = 0; 357 if (last->right) 358 last->right->parent = 0; 359 } 360 361 if (last->right && first->left) /* actually, first->left would suffice. */ 362 { 363 /* Need to join them. */ 364 et_forest_occurrence_t prev_node, next_node; 365 366 prev_node = splay (find_rightmost_node (first->left)); 367 next_node = splay (find_leftmost_node (last->right)); 368 /* prev_node and next_node are consecutive occurencies 369 of the same node. */ 370 if (prev_node->next != next_node) 371 abort (); 372 373 prev_node->right = next_node->right; 374 prev_node->count_right = next_node->count_right; 375 prev_node->next = next_node->next; 376 if (prev_node->right) 377 prev_node->right->parent = prev_node; 378 379 if (prev_node->node->last == next_node) 380 prev_node->node->last = prev_node; 381 382 free (next_node); 383 } 384 385 if (first != last) 386 { 387 node = first->next; 388 389 while (node != last) 390 { 391 et_forest_occurrence_t next_node; 392 393 splay (node); 394 395 if (node->left) 396 node->left->parent = 0; 397 if (node->right) 398 node->right->parent = 0; 399 400 next_node = node->next; 401 free (node); 402 node = next_node; 403 } 404 } 405 406 free (first); 407 if (first != last) 408 free (last); 409} 410 411/* Calculate ET value of the given node. */ 412static inline int 413calculate_value (node) 414 et_forest_occurrence_t node; 415{ 416 int value = node->count_left; 417 418 while (node->parent) 419 { 420 if (node == node->parent->right) 421 value += node->parent->count_left + 1; 422 423 node = node->parent; 424 } 425 426 return value; 427} 428 429 430 431 432/* Create ET-forest structure. */ 433et_forest_t 434et_forest_create () 435{ 436 437 et_forest_t forest = xmalloc (sizeof (struct et_forest)); 438 439 forest->nnodes = 0; 440 return forest; 441} 442 443 444 445/* Deallocate the structure. */ 446void 447et_forest_delete (forest) 448 et_forest_t forest; 449{ 450 if (forest->nnodes) 451 abort (); 452 453 free (forest); 454} 455 456/* Create new node with VALUE and return the edge. 457 Return NULL when memory allocation failed. */ 458et_forest_node_t 459et_forest_add_node (forest, value) 460 et_forest_t forest; 461 void *value; 462{ 463 /* Create node with one occurrence. */ 464 et_forest_node_t node; 465 et_forest_occurrence_t occ; 466 467 node = xmalloc (sizeof (struct et_forest_node)); 468 occ = xmalloc (sizeof (struct et_forest_occurrence)); 469 470 node->first = node->last = occ; 471 node->value = value; 472 forest->nnodes++; 473 474 occ->node = node; 475 occ->left = occ->right = occ->parent = 0; 476 occ->next = 0; 477 occ->count_left = occ->count_right = 0; 478 return node; 479} 480 481/* Add new edge to the tree, return 1 if succesfull. 482 0 indicates that creation of the edge will close the cycle in graph. */ 483int 484et_forest_add_edge (forest, parent_node, child_node) 485 et_forest_t forest ATTRIBUTE_UNUSED; 486 et_forest_node_t parent_node; 487 et_forest_node_t child_node; 488{ 489 et_forest_occurrence_t new_occ, parent_occ, child_occ; 490 491 if (! parent_node || ! child_node) 492 abort (); 493 494 parent_occ = parent_node->first; 495 child_occ = child_node->first; 496 497 splay (parent_occ); 498 splay (child_occ); 499 500 if (parent_occ->parent) 501 return 0; /* Both child and parent are in the same tree. */ 502 503 if (child_occ->left) 504 abort (); /* child must be root of its containing tree. */ 505 506 new_occ = xmalloc (sizeof (struct et_forest_occurrence)); 507 508 new_occ->node = parent_node; 509 new_occ->left = child_occ; 510 new_occ->count_left = child_occ->count_right + 1; /* count_left is 0. */ 511 new_occ->right = parent_occ->right; 512 new_occ->count_right = parent_occ->count_right; 513 new_occ->parent = parent_occ; 514 new_occ->next = parent_occ->next; 515 child_occ->parent = new_occ; 516 parent_occ->right = new_occ; 517 parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1; 518 parent_occ->next = new_occ; 519 if (new_occ->right) 520 new_occ->right->parent = new_occ; 521 522 if (parent_node->last == parent_occ) 523 parent_node->last = new_occ; 524 return 1; 525} 526 527/* Remove NODE from the tree and all connected edges. */ 528void 529et_forest_remove_node (forest, node) 530 et_forest_t forest; 531 et_forest_node_t node; 532{ 533 remove_all_occurrences (node); 534 forest->nnodes--; 535 536 free (node); 537} 538 539/* Remove edge from the tree, return 1 if sucesfull, 540 0 indicates nonexisting edge. */ 541int 542et_forest_remove_edge (forest, parent_node, child_node) 543 et_forest_t forest ATTRIBUTE_UNUSED; 544 et_forest_node_t parent_node; 545 et_forest_node_t child_node; 546{ 547 et_forest_occurrence_t parent_pre_occ, parent_post_occ; 548 549 splay (child_node->first); 550 551 if (! child_node->first->left) 552 return 0; 553 554 parent_pre_occ = find_rightmost_node (child_node->first->left); 555 if (parent_pre_occ->node != parent_node) 556 abort (); 557 558 splay (parent_pre_occ); 559 parent_pre_occ->right->parent = 0; 560 561 parent_post_occ = parent_pre_occ->next; 562 splay (parent_post_occ); 563 564 parent_post_occ->left->parent = 0; 565 566 parent_pre_occ->right = parent_post_occ->right; 567 parent_pre_occ->count_right = parent_post_occ->count_right; 568 if (parent_post_occ->right) 569 parent_post_occ->right->parent = parent_pre_occ; 570 571 parent_pre_occ->next = parent_post_occ->next; 572 573 if (parent_post_occ == parent_node->last) 574 parent_node->last = parent_pre_occ; 575 576 free (parent_post_occ); 577 return 1; 578} 579 580/* Return the parent of the NODE if any, NULL otherwise. */ 581et_forest_node_t 582et_forest_parent (forest, node) 583 et_forest_t forest ATTRIBUTE_UNUSED; 584 et_forest_node_t node; 585{ 586 splay (node->first); 587 588 if (node->first->left) 589 return find_rightmost_node (node->first->left)->node; 590 else 591 return 0; 592} 593 594 595/* Return nearest common ancestor of NODE1 and NODE2. 596 Return NULL of they are in different trees. */ 597et_forest_node_t 598et_forest_common_ancestor (forest, node1, node2) 599 et_forest_t forest ATTRIBUTE_UNUSED; 600 et_forest_node_t node1; 601 et_forest_node_t node2; 602{ 603 int value1, value2, max_value; 604 et_forest_node_t ancestor; 605 606 if (node1 == node2) 607 return node1; 608 609 if (! node1 || ! node2) 610 abort (); 611 612 splay (node1->first); 613 splay (node2->first); 614 615 if (! node1->first->parent) /* The two vertices are in different trees. */ 616 return 0; 617 618 value2 = calculate_value (node2->first); 619 value1 = calculate_value (node1->first); 620 621 if (value1 < value2) 622 { 623 ancestor = node1; 624 max_value = value2; 625 } 626 else 627 { 628 ancestor = node2; 629 max_value = value1; 630 } 631 632 while (calculate_value (ancestor->last) < max_value) 633 { 634 /* Find parent node. */ 635 splay (ancestor->first); 636 ancestor = find_rightmost_node (ancestor->first->left) ->node; 637 } 638 639 return ancestor; 640} 641 642/* Return the value pointer of node set during it's creation. */ 643void * 644et_forest_node_value (forest, node) 645 et_forest_t forest ATTRIBUTE_UNUSED; 646 et_forest_node_t node; 647{ 648 /* Alloc threading NULL as a special node of the forest. */ 649 if (!node) 650 return NULL; 651 return node->value; 652} 653 654/* Find all sons of NODE and store them into ARRAY allocated by the caller. 655 Return number of nodes found. */ 656int 657et_forest_enumerate_sons (forest, node, array) 658 et_forest_t forest ATTRIBUTE_UNUSED; 659 et_forest_node_t node; 660 et_forest_node_t *array; 661{ 662 int n = 0; 663 et_forest_occurrence_t occ = node->first, stop = node->last, occ1; 664 665 /* Parent is the rightmost node of the left successor. 666 Look for all occurences having no right succesor 667 and lookup the sons. */ 668 while (occ != stop) 669 { 670 splay (occ); 671 if (occ->right) 672 { 673 occ1 = find_leftmost_node (occ->right); 674 if (occ1->node->first == occ1) 675 array[n++] = occ1->node; 676 } 677 occ = occ->next; 678 } 679 return n; 680} 681