partset.c

一个非常好的检索工具

/* $Id: partset.c,v 1.2 1999/11/04 14:02:23 shields Exp $ */
/*
 This software is subject to the terms of the IBM Jikes Compiler
 License Agreement available at the following URL:
 http://www.ibm.com/research/jikes.
 Copyright (C) 1983, 1999, International Business Machines Corporation
 and others.  All Rights Reserved.
 You must accept the terms of that agreement to use this software.
*/
static char hostfile[] = __FILE__;

#include "common.h"
#include "header.h"

#define B_ASSIGN_SET(s1, dest, s2, source, bound) \
    {   int j; \
        for (j = 0; j < bound; j++) \
             s1[dest * bound + j] = s2[source * bound + j]; \
    }

#define B_SET_UNION(s1, dest, s2, source, bound) \
    {   int j; \
        for (j = 0; j < bound; j++) \
            s1[dest * bound + j] |= s2[source * bound + j]; \
    }

static BOOLEAN equal_sets(SET_PTR set1, int indx1,
                          SET_PTR set2, int indx2, int bound);


/*********************************************************************/
/*                          PARTSET:                                 */
/*********************************************************************/
/* This procedure, PARTSET, is invoked to apply a heuristic of the   */
/* Optimal Partitioning algorithm to a COLLECTION of subsets.  The   */
/* size of each subset in COLLECTION is passed in a parallel vector: */
/* ELEMENT_SIZE. Let SET_SIZE be the length of the bit_strings used  */
/* to represent the subsets in COLLECTION, the universe of the       */
/* subsets is the set of integers: [1..SET_SIZE].                    */
/* The third argument, LIST, is a vector identifying the order in    */
/* which the subsets in COLLECTION must be processed when they are   */
/* output.                                                           */
/* The last two arguments, START and STACK are output parameters.    */
/* We recall that the output of Optimal Partitioning is two vectors: */
/* a BASE vector and a RANGE vector...  START is the base vector.    */
/* It is used to indicate the starting position in the range         */
/* vector for each subset.  When a subset shares elements with       */
/* another subset, this is indicated by in index in START being      */
/* negative.  START also contains an extra "fence" element.  I.e.,   */
/* it has one more element than COLLECTION.                          */
/* STACK is a vector used to construct a partition of the elements   */
/* of COLLECTION. That partition is used later (in ctabs or tabutil) */
/* to output the final range vector...                               */
/*                                                                   */
/*********************************************************************/
/*                                                                   */
/* We first merge all sets that are identical.  A hash table is used */
/* to keep track of subsets that have already been seen.             */
/* DOMAIN_TABLE is used as the base of the hash table.  DOMAIN_LINK  */
/* is used to link subsets that collided.                            */
/*                                                                   */
/* The next step is to partition the unique subsets in the hash      */
/* table based on the number of elements they contain.  The vector   */
/* PARTITION is used for that purpose.                               */
/*                                                                   */
/* Finally, we attempt to overlay as many subsets as possible by     */
/* performing the following steps:                                   */
/*                                                                   */
/* 1) Choose a base set in the partition with the largest subsets    */
/*    and push it into a stack. (using the vector STACK)             */
/*                                                                   */
/* 2) Iterate over the remaining non_empty elements of the partitions*/
/*    in decreasing order of the size of the subsets contained in the*/
/*    element in question. If there exists a subset in the element   */
/*    which is a subset of the subset on top of the stack, currently */
/*    being constructed, remove it from the partition, and push it   */
/*    into the stack. Repeat step 2 until the partition is empty.    */
/*                                                                   */
/*********************************************************************/
void partset(SET_PTR collection,
             short *element_size, short *list,
             short *start, short *stack, int set_size)
{
    unsigned long hash_address;

    int collection_size,
        offset,
        i,
        previous,
        base_set,
        size_root,
        next_size,
        size,
        bctype,
        j,
        index,
        subset;

    short domain_table[STATE_TABLE_SIZE],
         *domain_link,
         *size_list,
         *partition,
         *next,
         *head;

    BOOLEAN *is_a_base;

    SET_PTR temp_set;

    collection_size = num_states;
    if (set_size == num_terminals)
    {
        bctype = term_set_size;
        collection_size = num_states;
    }
    else if (set_size == num_non_terminals)
    {
        bctype = non_term_set_size;
        collection_size = num_states;
    }
    else /* called from scope processing */
    {
        bctype = num_states / SIZEOF_BC
                            + (num_states % SIZEOF_BC ? 1 : 0);
        collection_size = set_size;
        set_size = num_states;
    }
    size_list = Allocate_short_array(set_size + 1);
    partition = Allocate_short_array(set_size + 1);
    domain_link = Allocate_short_array(collection_size + 1);
    head = Allocate_short_array(collection_size + 1);
    next = Allocate_short_array(collection_size + 1);
    is_a_base = Allocate_boolean_array(collection_size + 1);
    temp_set = (SET_PTR)
               calloc(1, bctype * sizeof(BOOLEAN_CELL));
    if (temp_set == NULL)
        nospace(__FILE__, __LINE__);

    /********************************************************************/
    /* DOMAIN_TABLE is the base of a hash table used to compute the set */
    /* of unique subsets in COLLECTION. Collisions are resolved by links*/
    /* which are implemented in DOMAIN_LINK.                            */
    /* HEAD is an array containing either the value OMEGA which         */
    /* indicates that the corresponding subset in COLLECTION is         */
    /* identical to another set, or it contains the "root" of a list of */
    /* subsets that are identical.  The elements of the list are placed */
    /* in the array NEXT.  When a state is at te root of a list, it is  */
    /* used as a representative of that list.                           */
    /********************************************************************/
    for (i = 0; i <= STATE_TABLE_UBOUND; i++)
        domain_table[i] = NIL;

    /*************************************************************/
    /* We now iterate over the states and attempt to insert each */
    /* domain set into the hash table...                         */
    /*************************************************************/
    for (index = 1; index <= collection_size; index++)
    {
        hash_address = 0;
        for (i = 0; i < bctype; i++)
            hash_address += collection[index * bctype + i];

        hash_address %= STATE_TABLE_SIZE;

        /***************************************************************/
        /*  Next, we search the hash table to see if the subset was    */
        /* already inserted in it. If we find such a subset, we simply */
        /* add INDEX to a list associated with the subset found and    */
        /* mark it as a duplicate by setting the head of its list to   */
        /* OMEGA.  Otherwise, we have a new set...                     */
        /***************************************************************/
        for (i = domain_table[hash_address]; i != NIL; i = domain_link[i])
        {
            if (equal_sets(collection, index, collection, i, bctype))
            {
                head[index] = OMEGA;
                next[index] = head[i];
                head[i] = index;
                goto continu;
            }
        }

        /*************************************************************/
        /*  ...Subset indicated by INDEX not previously seen. Insert */
        /* it into the hash table, and initialize a new list with it.*/
        /*************************************************************/
        domain_link[index] = domain_table[hash_address];
        domain_table[hash_address] = index;
        head[index] = NIL;  /* Start a new list */