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   et_forest_t forest = xmalloc (sizeof (struct et_forest));
 443
 444   forest->nnodes = 0;
 445   forest->occur_pool = create_alloc_pool ("et_forest_occurrence pool", sizeof (struct et_forest_occurrence), 300);
 446   forest->node_pool = create_alloc_pool ("et_forest_node pool", sizeof (struct et_forest_node), 300);
 447   return forest;
 448 }
 449
 450
 451
 452 /* Deallocate the structure.  */
 453 void
 454 et_forest_delete (forest)
 455      et_forest_t forest;
 456 {
 457   if (forest->nnodes)
 458     abort ();
 459   free_alloc_pool (forest->occur_pool);
 460   free_alloc_pool (forest->node_pool);
 461   free (forest);
 462 }
 463
 464 /* Create new node with VALUE and return the edge.
 465    Return NULL when memory allocation failed.  */
 466 et_forest_node_t
 467 et_forest_add_node (forest, value)
 468      et_forest_t forest;
 469      void *value;
 470 {
 471   /* Create node with one occurrence.  */
 472   et_forest_node_t node;
 473   et_forest_occurrence_t occ;
 474
 475   node = pool_alloc (forest->node_pool);
 476   occ = pool_alloc (forest->occur_pool);
 477
 478   node->first = node->last = occ;
 479   node->value = value;
 480   forest->nnodes++;
 481
 482   occ->node = node;
 483   occ->left = occ->right = occ->parent = 0;
 484   occ->next = 0;
 485   occ->count_left = occ->count_right = 0;
 486   return node;
 487 }
 488
 489 /* Add new edge to the tree, return 1 if successful.
 490    0 indicates that creation of the edge will close the cycle in graph.  */
 491 int
 492 et_forest_add_edge (forest, parent_node, child_node)
 493      et_forest_t forest ATTRIBUTE_UNUSED;
 494      et_forest_node_t parent_node;
 495      et_forest_node_t child_node;
 496 {
 497   et_forest_occurrence_t new_occ, parent_occ, child_occ;
 498
 499   if (! parent_node || ! child_node)
 500     abort ();
 501
 502   parent_occ = parent_node->first;
 503   child_occ = child_node->first;
 504
 505   splay (parent_occ);
 506   splay (child_occ);
 507
 508   if (parent_occ->parent)
 509     return 0; /* Both child and parent are in the same tree.  */
 510
 511   if (child_occ->left)
 512     abort ();  /* child must be root of its containing tree.  */
 513
 514   new_occ = pool_alloc (forest->occur_pool);
 515
 516   new_occ->node = parent_node;
 517   new_occ->left = child_occ;
 518   new_occ->count_left = child_occ->count_right + 1; /* count_left is 0.  */
 519   new_occ->right = parent_occ->right;
 520   new_occ->count_right = parent_occ->count_right;
 521   new_occ->parent = parent_occ;
 522   new_occ->next = parent_occ->next;
 523   child_occ->parent = new_occ;
 524   parent_occ->right = new_occ;
 525   parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1;
 526   parent_occ->next = new_occ;
 527   if (new_occ->right)
 528     new_occ->right->parent = new_occ;
 529
 530   if (parent_node->last == parent_occ)
 531     parent_node->last = new_occ;
 532   return 1;
 533 }
 534
 535 /* Remove NODE from the tree and all connected edges.  */
 536 void
 537 et_forest_remove_node (forest, node)
 538      et_forest_t forest;
 539      et_forest_node_t node;
 540 {
 541   remove_all_occurrences (forest, node);
 542   forest->nnodes--;
 543
 544   pool_free (forest->node_pool, node);
 545 }
 546
 547 /* Remove edge from the tree, return 1 if successful,
 548    0 indicates nonexisting edge.  */
 549 int
 550 et_forest_remove_edge (forest, parent_node, child_node)
 551      et_forest_t forest ATTRIBUTE_UNUSED;
 552      et_forest_node_t parent_node;
 553      et_forest_node_t child_node;
 554 {
 555   et_forest_occurrence_t parent_pre_occ, parent_post_occ;
 556
 557   splay (child_node->first);
 558
 559   if (! child_node->first->left)
 560     return 0;
 561
 562   parent_pre_occ = find_rightmost_node (child_node->first->left);
 563   if (parent_pre_occ->node != parent_node)
 564     abort ();
 565
 566   splay (parent_pre_occ);
 567   parent_pre_occ->right->parent = 0;
 568
 569   parent_post_occ = parent_pre_occ->next;
 570   splay (parent_post_occ);
 571
 572   parent_post_occ->left->parent = 0;
 573
 574   parent_pre_occ->right = parent_post_occ->right;
 575   parent_pre_occ->count_right = parent_post_occ->count_right;
 576   if (parent_post_occ->right)
 577     parent_post_occ->right->parent = parent_pre_occ;
 578
 579   parent_pre_occ->next = parent_post_occ->next;
 580
 581   if (parent_post_occ == parent_node->last)
 582     parent_node->last = parent_pre_occ;
 583
 584   pool_free (forest->occur_pool, parent_post_occ);
 585   return 1;
 586 }
 587
 588 /* Return the parent of the NODE if any, NULL otherwise.  */
 589 et_forest_node_t
 590 et_forest_parent (forest, node)
 591      et_forest_t forest ATTRIBUTE_UNUSED;
 592      et_forest_node_t node;
 593 {
 594   splay (node->first);
 595
 596   if (node->first->left)
 597     return find_rightmost_node (node->first->left)->node;
 598   else
 599     return 0;
 600 }
 601
 602
 603 /* Return nearest common ancestor of NODE1 and NODE2.
 604    Return NULL of they are in different trees.  */
 605 et_forest_node_t
 606 et_forest_common_ancestor (forest, node1, node2)
 607      et_forest_t forest ATTRIBUTE_UNUSED;
 608      et_forest_node_t node1;
 609      et_forest_node_t node2;
 610 {
 611   int value1, value2, max_value;
 612   et_forest_node_t ancestor;
 613
 614   if (node1 == node2)
 615     return node1;
 616
 617   if (! node1 || ! node2)
 618     abort ();
 619
 620   splay (node1->first);
 621   splay (node2->first);
 622
 623   if (! node1->first->parent)  /* The two vertices are in different trees.  */
 624     return 0;
 625
 626   value2 = calculate_value (node2->first);
 627   value1 = calculate_value (node1->first);
 628
 629   if (value1 < value2)
 630     {
 631       ancestor = node1;
 632       max_value = value2;
 633     }
 634   else
 635     {
 636       ancestor = node2;
 637       max_value = value1;
 638     }
 639
 640   while (calculate_value (ancestor->last) < max_value)
 641     {
 642       /* Find parent node.  */
 643       splay (ancestor->first);
 644       ancestor = find_rightmost_node (ancestor->first->left) ->node;
 645     }
 646
 647   return ancestor;
 648 }
 649
 650 /* Return the value pointer of node set during it's creation.  */
 651 void *
 652 et_forest_node_value (forest, node)
 653      et_forest_t forest ATTRIBUTE_UNUSED;
 654      et_forest_node_t node;
 655 {
 656   /* Alloc threading NULL as a special node of the forest.  */
 657   if (!node)
 658     return NULL;
 659   return node->value;
 660 }
 661
 662 /* Find all sons of NODE and store them into ARRAY allocated by the caller.
 663    Return number of nodes found.  */
 664 int
 665 et_forest_enumerate_sons (forest, node, array)
 666      et_forest_t forest ATTRIBUTE_UNUSED;
 667      et_forest_node_t node;
 668      et_forest_node_t *array;
 669 {
 670   int n = 0;
 671   et_forest_occurrence_t occ = node->first, stop = node->last, occ1;
 672
 673   /* Parent is the rightmost node of the left successor.
 674      Look for all occurrences having no right successor
 675      and lookup the sons.  */
 676   while (occ != stop)
 677     {
 678       splay (occ);
 679       if (occ->right)
 680         {
 681           occ1 = find_leftmost_node (occ->right);
 682           if (occ1->node->first == occ1)
 683             array[n++] = occ1->node;
 684         }
 685       occ = occ->next;
 686     }
 687   return n;
 688 }