home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / jikepg12.zip / jikespg / src / partset.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-11-04  |  17.0 KB  |  378 lines
  1. /* $Id: partset.c,v 1.2 1999/11/04 14:02:23 shields Exp $ */
  2. /*
  3.  This software is subject to the terms of the IBM Jikes Compiler
  4.  License Agreement available at the following URL:
  5.  http://www.ibm.com/research/jikes.
  6.  Copyright (C) 1983, 1999, International Business Machines Corporation
  7.  and others.  All Rights Reserved.
  8.  You must accept the terms of that agreement to use this software.
  9. */
  10. static char hostfile[] = __FILE__;
  11.  
  12. #include "common.h"
  13. #include "header.h"
  14.  
  15. #define B_ASSIGN_SET(s1, dest, s2, source, bound) \
  16.     {   int j; \
  17.         for (j = 0; j < bound; j++) \
  18.              s1[dest * bound + j] = s2[source * bound + j]; \
  19.     }
  20.  
  21. #define B_SET_UNION(s1, dest, s2, source, bound) \
  22.     {   int j; \
  23.         for (j = 0; j < bound; j++) \
  24.             s1[dest * bound + j] |= s2[source * bound + j]; \
  25.     }
  26.  
  27. static BOOLEAN equal_sets(SET_PTR set1, int indx1,
  28.                           SET_PTR set2, int indx2, int bound);
  29.  
  30.  
  31. /*********************************************************************/
  32. /*                          PARTSET:                                 */
  33. /*********************************************************************/
  34. /* This procedure, PARTSET, is invoked to apply a heuristic of the   */
  35. /* Optimal Partitioning algorithm to a COLLECTION of subsets.  The   */
  36. /* size of each subset in COLLECTION is passed in a parallel vector: */
  37. /* ELEMENT_SIZE. Let SET_SIZE be the length of the bit_strings used  */
  38. /* to represent the subsets in COLLECTION, the universe of the       */
  39. /* subsets is the set of integers: [1..SET_SIZE].                    */
  40. /* The third argument, LIST, is a vector identifying the order in    */
  41. /* which the subsets in COLLECTION must be processed when they are   */
  42. /* output.                                                           */
  43. /* The last two arguments, START and STACK are output parameters.    */
  44. /* We recall that the output of Optimal Partitioning is two vectors: */
  45. /* a BASE vector and a RANGE vector...  START is the base vector.    */
  46. /* It is used to indicate the starting position in the range         */
  47. /* vector for each subset.  When a subset shares elements with       */
  48. /* another subset, this is indicated by in index in START being      */
  49. /* negative.  START also contains an extra "fence" element.  I.e.,   */
  50. /* it has one more element than COLLECTION.                          */
  51. /* STACK is a vector used to construct a partition of the elements   */
  52. /* of COLLECTION. That partition is used later (in ctabs or tabutil) */
  53. /* to output the final range vector...                               */
  54. /*                                                                   */
  55. /*********************************************************************/
  56. /*                                                                   */
  57. /* We first merge all sets that are identical.  A hash table is used */
  58. /* to keep track of subsets that have already been seen.             */
  59. /* DOMAIN_TABLE is used as the base of the hash table.  DOMAIN_LINK  */
  60. /* is used to link subsets that collided.                            */
  61. /*                                                                   */
  62. /* The next step is to partition the unique subsets in the hash      */
  63. /* table based on the number of elements they contain.  The vector   */
  64. /* PARTITION is used for that purpose.                               */
  65. /*                                                                   */
  66. /* Finally, we attempt to overlay as many subsets as possible by     */
  67. /* performing the following steps:                                   */
  68. /*                                                                   */
  69. /* 1) Choose a base set in the partition with the largest subsets    */
  70. /*    and push it into a stack. (using the vector STACK)             */
  71. /*                                                                   */
  72. /* 2) Iterate over the remaining non_empty elements of the partitions*/
  73. /*    in decreasing order of the size of the subsets contained in the*/
  74. /*    element in question. If there exists a subset in the element   */
  75. /*    which is a subset of the subset on top of the stack, currently */
  76. /*    being constructed, remove it from the partition, and push it   */
  77. /*    into the stack. Repeat step 2 until the partition is empty.    */
  78. /*                                                                   */
  79. /*********************************************************************/
  80. void partset(SET_PTR collection,
  81.              short *element_size, short *list,
  82.              short *start, short *stack, int set_size)
  83. {
  84.     unsigned long hash_address;
  85.  
  86.     int collection_size,
  87.         offset,
  88.         i,
  89.         previous,
  90.         base_set,
  91.         size_root,
  92.         next_size,
  93.         size,
  94.         bctype,
  95.         j,
  96.         index,
  97.         subset;
  98.  
  99.     short domain_table[STATE_TABLE_SIZE],
  100.          *domain_link,
  101.          *size_list,
  102.          *partition,
  103.          *next,
  104.          *head;
  105.  
  106.     BOOLEAN *is_a_base;
  107.  
  108.     SET_PTR temp_set;
  109.  
  110.     collection_size = num_states;
  111.     if (set_size == num_terminals)
  112.     {
  113.         bctype = term_set_size;
  114.         collection_size = num_states;
  115.     }
  116.     else if (set_size == num_non_terminals)
  117.     {
  118.         bctype = non_term_set_size;
  119.         collection_size = num_states;
  120.     }
  121.     else /* called from scope processing */
  122.     {
  123.         bctype = num_states / SIZEOF_BC
  124.                             + (num_states % SIZEOF_BC ? 1 : 0);
  125.         collection_size = set_size;
  126.         set_size = num_states;
  127.     }
  128.     size_list = Allocate_short_array(set_size + 1);
  129.     partition = Allocate_short_array(set_size + 1);
  130.     domain_link = Allocate_short_array(collection_size + 1);
  131.     head = Allocate_short_array(collection_size + 1);
  132.     next = Allocate_short_array(collection_size + 1);
  133.     is_a_base = Allocate_boolean_array(collection_size + 1);
  134.     temp_set = (SET_PTR)
  135.                calloc(1, bctype * sizeof(BOOLEAN_CELL));
  136.     if (temp_set == NULL)
  137.         nospace(__FILE__, __LINE__);
  138.  
  139.     /********************************************************************/
  140.     /* DOMAIN_TABLE is the base of a hash table used to compute the set */
  141.     /* of unique subsets in COLLECTION. Collisions are resolved by links*/
  142.     /* which are implemented in DOMAIN_LINK.                            */
  143.     /* HEAD is an array containing either the value OMEGA which         */
  144.     /* indicates that the corresponding subset in COLLECTION is         */
  145.     /* identical to another set, or it contains the "root" of a list of */
  146.     /* subsets that are identical.  The elements of the list are placed */
  147.     /* in the array NEXT.  When a state is at te root of a list, it is  */
  148.     /* used as a representative of that list.                           */
  149.     /********************************************************************/
  150.     for (i = 0; i <= STATE_TABLE_UBOUND; i++)
  151.         domain_table[i] = NIL;
  152.  
  153.     /*************************************************************/
  154.     /* We now iterate over the states and attempt to insert each */
  155.     /* domain set into the hash table...                         */
  156.     /*************************************************************/
  157.     for (index = 1; index <= collection_size; index++)
  158.     {
  159.         hash_address = 0;
  160.         for (i = 0; i < bctype; i++)
  161.             hash_address += collection[index * bctype + i];
  162.  
  163.         hash_address %= STATE_TABLE_SIZE;
  164.  
  165.         /***************************************************************/
  166.         /*  Next, we search the hash table to see if the subset was    */
  167.         /* already inserted in it. If we find such a subset, we simply */
  168.         /* add INDEX to a list associated with the subset found and    */
  169.         /* mark it as a duplicate by setting the head of its list to   */
  170.         /* OMEGA.  Otherwise, we have a new set...                     */
  171.         /***************************************************************/
  172.         for (i = domain_table[hash_address]; i != NIL; i = domain_link[i])
  173.         {
  174.             if (equal_sets(collection, index, collection, i, bctype))
  175.             {
  176.                 head[index] = OMEGA;
  177.                 next[index] = head[i];
  178.                 head[i] = index;
  179.                 goto continu;
  180.             }
  181.         }
  182.  
  183.         /*************************************************************/
  184.         /*  ...Subset indicated by INDEX not previously seen. Insert */
  185.         /* it into the hash table, and initialize a new list with it.*/
  186.         /*************************************************************/
  187.         domain_link[index] = domain_table[hash_address];
  188.         domain_table[hash_address] = index;
  189.         head[index] = NIL;  /* Start a new list */
  190. continu: ;
  191.    }
  192.  
  193.     /*************************************************************/
  194.     /* We now partition all the unique sets in the hash table    */
  195.     /* based on the number of elements they contain...           */
  196.     /* NEXT is also used to construct these lists.  Recall that  */
  197.     /* the unique elements are roots of lists. Hence, their      */
  198.     /* corresponding HEAD elements are used, but their           */
  199.     /* corresponding NEXT field is still unused.                 */
  200.     /*************************************************************/
  201.     for (i = 0; i <= set_size; i++)
  202.          partition[i] = NIL;
  203.  
  204.     for (index = 1; index <= collection_size; index++)
  205.     {
  206.         if (head[index] != OMEGA) /* Subset representative */
  207.         {
  208.             size = element_size[index];
  209.             next[index] = partition[size];
  210.             partition[size] = index;
  211.         }
  212.     }
  213.  
  214.     /*************************************************************/
  215.     /*     ...Construct a list of all the elements of PARTITION  */
  216.     /* that are not empty.  Only elements in this list will be   */
  217.     /* considered for subset merging later ...                   */
  218.     /* Note that since the elements of PARTITION are added to    */
  219.     /* the list in ascending order and in stack-fashion, the     */
  220.     /* resulting list will be sorted in descending order.        */
  221.     /*************************************************************/
  222.     size_root = NIL;
  223.     for (i = 0; i <= set_size; i++)
  224.     {
  225.         if (partition[i] != NIL)
  226.         {
  227.             size_list[i] = size_root;
  228.             size_root = i;
  229.         }
  230.     }
  231.  
  232.     /*************************************************************/
  233.     /* Merge subsets that are mergeable using heuristic described*/
  234.     /* above.  The vector IS_A_BASE is used to mark subsets      */
  235.     /* chosen as bases.                                          */
  236.     /*************************************************************/
  237.     for (i = 0; i <= collection_size; i++)
  238.         is_a_base[i] = FALSE;
  239.     for (size = size_root; size != NIL; size = size_list[size])
  240.     { /* For biggest partition there is */
  241.         for (base_set = partition[size];
  242.              base_set != NIL; base_set = next[base_set])
  243.         { /* For each set in it... */
  244.             /*****************************************************/
  245.             /* Mark the state as a base state, and initialize    */
  246.             /* its stack.  The list representing the stack will  */
  247.             /* be circular...                                    */
  248.             /*****************************************************/
  249.             is_a_base[base_set] = TRUE;
  250.             stack[base_set] = base_set;
  251.  
  252.             /**************************************************************/
  253.             /* For remaining elements in partitions in decreasing order...*/
  254.             /**************************************************************/
  255.  
  256.             for (next_size = size_list[size];
  257.                  next_size != NIL; next_size = size_list[next_size])
  258.             {
  259.                 previous = NIL;           /* mark head of list */
  260.  
  261.                 /**************************************************/
  262.                 /* Iterate over subsets in the partition until we */
  263.                 /* find one that is a subset of the subset on top */
  264.                 /* of the stack.  If none is found, we go on to   */
  265.                 /* the next element of the partition. Otherwise,  */
  266.                 /* we push the new subset on top of the stack and */
  267.                 /* go on to the next element of the partition.    */
  268.                 /* INDEX identifies the state currently on top    */
  269.                 /* of the stack.                                  */
  270.                 /**************************************************/
  271.                 for (subset = partition[next_size];
  272.                      subset != NIL;
  273.                      previous = subset, subset = next[subset])
  274.                 {
  275.                     index = stack[base_set];
  276.                     B_ASSIGN_SET(temp_set, 0, collection, index, bctype);
  277.                     B_SET_UNION(temp_set, 0, collection, subset, bctype);
  278.  
  279.                     /* SUBSET is a subset of INDEX?*/
  280.                     if (equal_sets(temp_set, 0, collection, index, bctype))
  281.                     {
  282.                         if (previous == NIL)
  283.                             partition[next_size] = next[subset];
  284.                         else
  285.                             next[previous] = next[subset];
  286.                         stack[subset] = stack[base_set];
  287.                         stack[base_set] = subset;
  288.                         break; /* for (subset = partition[next_size]... */
  289.                     }
  290.                 }
  291.             }
  292.         }
  293.     }
  294.  
  295.     /*************************************************************/
  296.     /* Iterate over the states in the order in which they are to */
  297.     /* be output, and assign an offset location to each state.   */
  298.     /* Notice that an extra element is added to the size of each */
  299.     /* base subset for the "fence" element.                      */
  300.     /*************************************************************/
  301.     offset = 1;
  302.     for (i= 1; i<= collection_size; i++)
  303.     {
  304.         base_set = list[i];
  305.         if (is_a_base[base_set])
  306.         {
  307.             start[base_set] = offset;
  308.             /***********************************************************/
  309.             /* Assign the same offset to each subset that is           */
  310.             /* identical to the BASE_SET subset in question. Also,     */
  311.             /* mark the fact that this is a copy by using the negative */
  312.             /* value of the OFFSET.                                    */
  313.             /***********************************************************/
  314.             for (index = head[base_set]; index != NIL; index = next[index])
  315.                 start[index] = - start[base_set];
  316.  
  317.             size = element_size[base_set] + 1;
  318.             offset += size;
  319.             SHORT_CHECK(offset);
  320.  
  321.             /*********************************************************/
  322.             /* Now, assign offset values to each subset of the       */
  323.             /* BASE_SET. Once again, we mark them as sharing elements*/
  324.             /* by using the negative value of the OFFSET.            */
  325.             /* Recall that the stack is constructed as a circular    */
  326.             /* list.  Therefore, its end is reached when we go back  */
  327.             /* to the root... In this case, the root is already      */
  328.             /* processed, so we stop when we reach it.               */
  329.             /*********************************************************/
  330.             for (index = stack[base_set];
  331.                  index != base_set; index = stack[index])
  332.             {
  333.                 size = element_size[index] + 1;
  334.                 start[index] = -(offset - size);
  335.  
  336.                 /*****************************************************/
  337.                 /* INDEX identifies a subset of BASE_SET. Assign the */
  338.                 /* same offset as INDEX to each subset j that is     */
  339.                 /* identical to the subset INDEX.                    */
  340.                 /*****************************************************/
  341.                 for (j = head[index]; j != NIL; j = next[j])
  342.                     start[j] = start[index];
  343.             }
  344.         }
  345.     }
  346.     start[collection_size+1] = offset;
  347.  
  348.     ffree(size_list);
  349.     ffree(partition);
  350.     ffree(domain_link);
  351.     ffree(head);
  352.     ffree(next);
  353.     ffree(is_a_base);
  354.     ffree(temp_set);
  355.  
  356.     return;
  357. }
  358.  
  359.  
  360. /****************************************************************************/
  361. /*                               EQUAL_SETS:                                */
  362. /****************************************************************************/
  363. /* EQUAL_SETS checks to see if two sets are equal and returns True or False */
  364. /****************************************************************************/
  365. static BOOLEAN equal_sets(SET_PTR set1, int indx1,
  366.                           SET_PTR set2, int indx2, int bound)
  367. {
  368.     register int i;
  369.  
  370.     for (i = 0; i < bound; i++)
  371.     {
  372.         if (set1[indx1 * bound + i] != set2[indx2 * bound + i])
  373.            return(0);
  374.     }
  375.  
  376.     return(TRUE);
  377. }
  378.