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 "et-forest.h"
  29
  30 struct et_forest_occurrence;
  31 typedef struct et_forest_occurrence* et_forest_occurrence_t;
  32
  33 /* The ET-forest type.  */
  34 struct 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  */
  43 struct 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.  */
  63 struct 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
  73 static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t));
  74 static void remove_all_occurrences PARAMS ((et_forest_node_t));
  75 static inline et_forest_occurrence_t find_leftmost_node
  76                                PARAMS ((et_forest_occurrence_t));
  77 static inline et_forest_occurrence_t find_rightmost_node
  78                                PARAMS ((et_forest_occurrence_t));
  79 static int calculate_value PARAMS ((et_forest_occurrence_t));
  80
  81 /* Return leftmost node present in the tree roted by OCC.  */
  82 static inline et_forest_occurrence_t
  83 find_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.  */
  93 static inline et_forest_occurrence_t
  94 find_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.  */
 104 static et_forest_occurrence_t
 105 splay (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.  */
 336 static void
 337 remove_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.  */
 412 static inline int
 413 calculate_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.  */
 433 et_forest_t
 434 et_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.  */
 446 void
 447 et_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.  */
 458 et_forest_node_t
 459 et_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.  */
 483 int
 484 et_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.  */
 528 void
 529 et_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.  */
 541 int
 542 et_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.  */
 581 et_forest_node_t
 582 et_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.  */
 597 et_forest_node_t
 598 et_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.  */
 643 void *
 644 et_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.  */
 656 int
 657 et_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 }