gcc/et-forest.c

   1 /* ET-trees data structure implementation.
   2    Contributed by Pavel Nejedly
   3    Copyright (C) 2002, 2003 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 (et_forest_occurrence_t);
  79 static void remove_all_occurrences (et_forest_t, et_forest_node_t);
  80 static inline et_forest_occurrence_t find_leftmost_node
  81   (et_forest_occurrence_t);
  82 static inline et_forest_occurrence_t find_rightmost_node
  83   (et_forest_occurrence_t);
  84 static int calculate_value (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 (et_forest_occurrence_t occ)
  89 {
  90   while (occ->left)
  91     occ = occ->left;
  92
  93   return occ;
  94 }
  95
  96 /* Return rightmost node present in the tree roted by OCC.  */
  97 static inline et_forest_occurrence_t
  98 find_rightmost_node (et_forest_occurrence_t occ)
  99 {
 100   while (occ->right)
 101     occ = occ->right;
 102   return occ;
 103 }
 104
 105
 106 /* Operation splay for splay tree structure representing occurrences.  */
 107 static et_forest_occurrence_t
 108 splay (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 occurrences of the given node before destroying the node.  */
 338 static void
 339 remove_all_occurrences (et_forest_t forest, et_forest_node_t forest_node)
 340 {
 341   et_forest_occurrence_t first = forest_node->first;
 342   et_forest_occurrence_t last = forest_node->last;
 343   et_forest_occurrence_t node;
 344
 345   splay (first);
 346
 347   if (first->left)
 348     first->left->parent = 0;
 349   if (first->right)
 350     first->right->parent = 0;
 351
 352   if (last != first)
 353     {
 354       splay (last);
 355
 356       if (last->left)
 357         last->left->parent = 0;
 358       if (last->right)
 359         last->right->parent = 0;
 360     }
 361
 362   if (last->right && first->left) /* actually, first->left would suffice.  */
 363     {
 364       /* Need to join them.  */
 365       et_forest_occurrence_t prev_node, next_node;
 366
 367       prev_node = splay (find_rightmost_node (first->left));
 368       next_node = splay (find_leftmost_node (last->right));
 369       /* prev_node and next_node are consecutive occurrences
 370          of the same node.  */
 371       if (prev_node->next != next_node)
 372         abort ();
 373
 374       prev_node->right = next_node->right;
 375       prev_node->count_right = next_node->count_right;
 376       prev_node->next = next_node->next;
 377       if (prev_node->right)
 378         prev_node->right->parent = prev_node;
 379
 380       if (prev_node->node->last == next_node)
 381         prev_node->node->last = prev_node;
 382
 383       pool_free (forest->occur_pool, next_node);
 384     }
 385
 386   if (first != last)
 387     {
 388       node = first->next;
 389
 390       while (node != last)
 391         {
 392           et_forest_occurrence_t next_node;
 393
 394           splay (node);
 395
 396           if (node->left)
 397             node->left->parent = 0;
 398           if (node->right)
 399             node->right->parent = 0;
 400
 401           next_node = node->next;
 402           pool_free (forest->occur_pool, node);
 403           node = next_node;
 404         }
 405     }
 406
 407   pool_free (forest->occur_pool, first);
 408   if (first != last)
 409     pool_free (forest->occur_pool, last);
 410 }
 411
 412 /* Calculate ET value of the given node.  */
 413 static inline int
 414 calculate_value (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 (void)
 435 {
 436   et_forest_t forest = xmalloc (sizeof (struct et_forest));
 437
 438   forest->nnodes = 0;
 439   forest->occur_pool = create_alloc_pool ("et_forest_occurrence pool", sizeof (struct et_forest_occurrence), 300);
 440   forest->node_pool = create_alloc_pool ("et_forest_node pool", sizeof (struct et_forest_node), 300);
 441   return forest;
 442 }
 443
 444
 445
 446 /* Deallocate the structure.  */
 447 void
 448 et_forest_delete (et_forest_t forest)
 449 {
 450   if (forest->nnodes)
 451     abort ();
 452   free_alloc_pool (forest->occur_pool);
 453   free_alloc_pool (forest->node_pool);
 454   free (forest);
 455 }
 456
 457 /* Create new node with VALUE and return the edge.
 458    Return NULL when memory allocation failed.  */
 459 et_forest_node_t
 460 et_forest_add_node (et_forest_t forest, void *value)
 461 {
 462   /* Create node with one occurrence.  */
 463   et_forest_node_t node;
 464   et_forest_occurrence_t occ;
 465
 466   node = pool_alloc (forest->node_pool);
 467   occ = pool_alloc (forest->occur_pool);
 468
 469   node->first = node->last = occ;
 470   node->value = value;
 471   forest->nnodes++;
 472
 473   occ->node = node;
 474   occ->left = occ->right = occ->parent = 0;
 475   occ->next = 0;
 476   occ->count_left = occ->count_right = 0;
 477   return node;
 478 }
 479
 480 /* Add new edge to the tree, return 1 if successful.
 481    0 indicates that creation of the edge will close the cycle in graph.  */
 482 int
 483 et_forest_add_edge (et_forest_t forest ATTRIBUTE_UNUSED,
 484                     et_forest_node_t parent_node, et_forest_node_t child_node)
 485 {
 486   et_forest_occurrence_t new_occ, parent_occ, child_occ;
 487
 488   if (! parent_node || ! child_node)
 489     abort ();
 490
 491   parent_occ = parent_node->first;
 492   child_occ = child_node->first;
 493
 494   splay (parent_occ);
 495   splay (child_occ);
 496
 497   if (parent_occ->parent)
 498     return 0; /* Both child and parent are in the same tree.  */
 499
 500   if (child_occ->left)
 501     abort ();  /* child must be root of its containing tree.  */
 502
 503   new_occ = pool_alloc (forest->occur_pool);
 504
 505   new_occ->node = parent_node;
 506   new_occ->left = child_occ;
 507   new_occ->count_left = child_occ->count_right + 1; /* count_left is 0.  */
 508   new_occ->right = parent_occ->right;
 509   new_occ->count_right = parent_occ->count_right;
 510   new_occ->parent = parent_occ;
 511   new_occ->next = parent_occ->next;
 512   child_occ->parent = new_occ;
 513   parent_occ->right = new_occ;
 514   parent_occ->count_right = new_occ->count_left + new_occ->count_right + 1;
 515   parent_occ->next = new_occ;
 516   if (new_occ->right)
 517     new_occ->right->parent = new_occ;
 518
 519   if (parent_node->last == parent_occ)
 520     parent_node->last = new_occ;
 521   return 1;
 522 }
 523
 524 /* Remove NODE from the tree and all connected edges.  */
 525 void
 526 et_forest_remove_node (et_forest_t forest, et_forest_node_t node)
 527 {
 528   remove_all_occurrences (forest, node);
 529   forest->nnodes--;
 530
 531   pool_free (forest->node_pool, node);
 532 }
 533
 534 /* Remove edge from the tree, return 1 if successful,
 535    0 indicates nonexisting edge.  */
 536 int
 537 et_forest_remove_edge (et_forest_t forest ATTRIBUTE_UNUSED,
 538                        et_forest_node_t parent_node,
 539                        et_forest_node_t child_node)
 540 {
 541   et_forest_occurrence_t parent_pre_occ, parent_post_occ;
 542
 543   splay (child_node->first);
 544
 545   if (! child_node->first->left)
 546     return 0;
 547
 548   parent_pre_occ = find_rightmost_node (child_node->first->left);
 549   if (parent_pre_occ->node != parent_node)
 550     abort ();
 551
 552   splay (parent_pre_occ);
 553   parent_pre_occ->right->parent = 0;
 554
 555   parent_post_occ = parent_pre_occ->next;
 556   splay (parent_post_occ);
 557
 558   parent_post_occ->left->parent = 0;
 559
 560   parent_pre_occ->right = parent_post_occ->right;
 561   parent_pre_occ->count_right = parent_post_occ->count_right;
 562   if (parent_post_occ->right)
 563     parent_post_occ->right->parent = parent_pre_occ;
 564
 565   parent_pre_occ->next = parent_post_occ->next;
 566
 567   if (parent_post_occ == parent_node->last)
 568     parent_node->last = parent_pre_occ;
 569
 570   pool_free (forest->occur_pool, parent_post_occ);
 571   return 1;
 572 }
 573
 574 /* Return the parent of the NODE if any, NULL otherwise.  */
 575 et_forest_node_t
 576 et_forest_parent (et_forest_t forest ATTRIBUTE_UNUSED, et_forest_node_t node)
 577 {
 578   splay (node->first);
 579
 580   if (node->first->left)
 581     return find_rightmost_node (node->first->left)->node;
 582   else
 583     return 0;
 584 }
 585
 586
 587 /* Return nearest common ancestor of NODE1 and NODE2.
 588    Return NULL of they are in different trees.  */
 589 et_forest_node_t
 590 et_forest_common_ancestor (et_forest_t forest ATTRIBUTE_UNUSED,
 591                            et_forest_node_t node1, et_forest_node_t node2)
 592 {
 593   int value1, value2, max_value;
 594   et_forest_node_t ancestor;
 595
 596   if (node1 == node2)
 597     return node1;
 598
 599   if (! node1 || ! node2)
 600     abort ();
 601
 602   splay (node1->first);
 603   splay (node2->first);
 604
 605   if (! node1->first->parent)  /* The two vertices are in different trees.  */
 606     return 0;
 607
 608   value2 = calculate_value (node2->first);
 609   value1 = calculate_value (node1->first);
 610
 611   if (value1 < value2)
 612     {
 613       ancestor = node1;
 614       max_value = value2;
 615     }
 616   else
 617     {
 618       ancestor = node2;
 619       max_value = value1;
 620     }
 621
 622   while (calculate_value (ancestor->last) < max_value)
 623     {
 624       /* Find parent node.  */
 625       splay (ancestor->first);
 626       ancestor = find_rightmost_node (ancestor->first->left) ->node;
 627     }
 628
 629   return ancestor;
 630 }
 631
 632 /* Return the value pointer of node set during it's creation.  */
 633 void *
 634 et_forest_node_value (et_forest_t forest ATTRIBUTE_UNUSED,
 635                       et_forest_node_t node)
 636 {
 637   /* Alloc threading NULL as a special node of the forest.  */
 638   if (!node)
 639     return NULL;
 640   return node->value;
 641 }
 642
 643 /* Find all sons of NODE and store them into ARRAY allocated by the caller.
 644    Return number of nodes found.  */
 645 int
 646 et_forest_enumerate_sons (et_forest_t forest ATTRIBUTE_UNUSED,
 647                           et_forest_node_t node, et_forest_node_t *array)
 648 {
 649   int n = 0;
 650   et_forest_occurrence_t occ = node->first, stop = node->last, occ1;
 651
 652   /* Parent is the rightmost node of the left successor.
 653      Look for all occurrences having no right successor
 654      and lookup the sons.  */
 655   while (occ != stop)
 656     {
 657       splay (occ);
 658       if (occ->right)
 659         {
 660           occ1 = find_leftmost_node (occ->right);
 661           if (occ1->node->first == occ1)
 662             array[n++] = occ1->node;
 663         }
 664       occ = occ->next;
 665     }
 666   return n;
 667 }