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