gcc/et-forest.c

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