spacetab.c

一个非常好的检索工具

/* $Id: spacetab.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 <string.h>
#include "common.h"
#include "space.h"
#include "header.h"

static struct node **new_state_element_reduce_nodes;

static long total_bytes,
            num_table_entries;

static int top,
           empty_root,
           single_root,
           multi_root;

static short *row_size,
             *frequency_symbol,
             *frequency_count;

static BOOLEAN *shift_on_error_symbol;

/****************************************************************************/
/*                            REMAP_NON_TERMINALS:                          */
/****************************************************************************/
/*  REMAP_NON_TERMINALS remaps the non-terminal symbols and states based on */
/* frequency of entries.                                                    */
/****************************************************************************/
static void remap_non_terminals(void)
{
    short *frequency_symbol,
          *frequency_count,
          *row_size;

    struct goto_header_type go_to;

    int i,
        state_no,
        symbol;

/**********************************************************************/
/*   The variable FREQUENCY_SYMBOL is used to hold the non-terminals  */
/* in the grammar, and  FREQUENCY_COUNT is used correspondingly to    */
/* hold the number of actions defined on each non-terminal.           */
/* ORDERED_STATE and ROW_SIZE are used in a similar fashion for states*/
/**********************************************************************/
    frequency_symbol = Allocate_short_array(num_non_terminals);
    frequency_symbol -= (num_terminals + 1);
    frequency_count = Allocate_short_array(num_non_terminals);
    frequency_count -= (num_terminals + 1);
    row_size = Allocate_short_array(num_states + 1);

    for ALL_NON_TERMINALS(i)
    {
        frequency_symbol[i] = i;
        frequency_count[i] = 0;
    }
    for ALL_STATES(state_no)
    {
        ordered_state[state_no] = state_no;
        row_size[state_no] = 0;
        go_to = statset[state_no].go_to;
        for (i = 1; i <= go_to.size; i++)
        {
            row_size[state_no]++;
            symbol = GOTO_SYMBOL(go_to, i);
            frequency_count[symbol]++;
        }
    }

    /**********************************************************************/
    /* The non-terminals are sorted in descending order based on the      */
    /* number of actions defined on then, and they are remapped based on  */
    /* the new arrangement obtained by the sorting.                       */
    /**********************************************************************/
    sortdes(frequency_symbol, frequency_count,
            num_terminals + 1, num_symbols, num_states);

    for ALL_NON_TERMINALS(i)
        symbol_map[frequency_symbol[i]] = i;

    /**********************************************************************/
    /*    All non-terminal entries in the state automaton are updated     */
    /* accordingly.  We further subtract NUM_TERMINALS from each          */
    /* non-terminal to make them fall in the range [1..NUM_NON_TERMINLS]  */
    /* instead of [NUM_TERMINALS+1..NUM_SYMBOLS].                         */
    /**********************************************************************/
    for ALL_STATES(state_no)
    {
        go_to = statset[state_no].go_to;
        for (i = 1; i <= go_to.size; i++)
           GOTO_SYMBOL(go_to, i) =
                symbol_map[GOTO_SYMBOL(go_to, i)] - num_terminals;
    }

    /**********************************************************************/
    /* If Goto-Default was requested, we find out how many non-terminals  */
    /* were eliminated as a result, and adjust the GOTO-DEFAULT map,      */
    /* based on the new mapping of the non-terminals.                     */
    /**********************************************************************/
    if (goto_default_bit)
    {
        short *temp_goto_default;

        temp_goto_default = Allocate_short_array(num_non_terminals);
        temp_goto_default -= (num_terminals + 1);

        for (last_symbol = num_symbols;
             last_symbol > num_terminals; last_symbol--)
             if (frequency_count[last_symbol] != 0)
                 break;
        last_symbol -= num_terminals;
        sprintf(msg_line, "Number of non-terminals eliminated: %d",
                          num_non_terminals - last_symbol);
        PRNT(msg_line);

        /**************************************************************/
        /* Remap the GOTO-DEFAULT map.                                */
        /* to hold the original map.                                  */
        /**************************************************************/
        for ALL_NON_TERMINALS(symbol)
            temp_goto_default[symbol_map[symbol]] = gotodef[symbol];
        gotodef += (num_terminals + 1);
        ffree(gotodef);
        gotodef = temp_goto_default;
    }
    else
        last_symbol = num_non_terminals;

    /**********************************************************************/
    /* The states are sorted in descending order based on the number of   */
    /* actions defined on them, and they are remapped based on the new    */
    /* arrangement obtained by the sorting.                               */
    /**********************************************************************/
    sortdes(ordered_state, row_size, 1, num_states, last_symbol);

    frequency_symbol += (num_terminals + 1);
    ffree(frequency_symbol);
    frequency_count += (num_terminals + 1);
    ffree(frequency_count);
    ffree(row_size);

    return;
}


/****************************************************************************/
/*                           OVERLAP_NT_ROWS:                               */
/****************************************************************************/
/* We now overlap the non-terminal table, or more precisely, we compute the */
/* starting position in a vector where each of its rows may be placed       */
/* without clobbering elements in another row.  The starting positions are  */
/* stored in the vector STATE_INDEX.                                        */
/****************************************************************************/
static void overlap_nt_rows(void)
{
    struct goto_header_type go_to;

    int max_indx,
        indx,
        k,
        j,
        i,
        k_bytes,
        percentage,
        state_no,
        symbol;

    long num_bytes;

    num_table_entries = num_gotos + num_goto_reduces + num_states;
    increment_size = MAX((num_table_entries / 100 * increment),
                         (last_symbol + 1));
    table_size = MIN((num_table_entries + increment_size), MAX_TABLE_SIZE);

    /*************************************************************************/
    /* Allocate space for table, and initlaize the AVAIL_POOL list.  The     */
    /* variable FIRST_INDEX keeps track of the first element in the doubly-  */
    /* linked list, and LAST_ELEMENT keeps track of the last element in the  */
    /* list.                                                                 */
    /*   The variable MAX_INDX is used to keep track of the maximum starting */
    /* position for a row that has been used.                                */
    /*************************************************************************/
    next = Allocate_int_array(table_size + 1);
    previous = Allocate_int_array(table_size + 1);

    first_index = 1;
    previous[first_index] = NIL;
    next[first_index] = first_index + 1;
    for (indx = 2; indx < (int) table_size; indx++)
    {
        next[indx] = indx + 1;
        previous[indx] = indx - 1;
    }
    last_index = table_size;
    previous[last_index] = last_index - 1;
    next[last_index] = NIL;

    max_indx = first_index;

    /*******************************************************************/
    /* We now iterate over all the states in their new sorted order as */
    /* indicated by the variable STATE_NO, and determine an "overlap"  */
    /* position for them.                                              */
    /*******************************************************************/
    for ALL_STATES(k)
    {
        state_no = ordered_state[k];

        /****************************************************************/
        /* INDX is set to the beginning of the list of available slots  */
        /* and we try to determine if it might be a valid starting      */
        /* position.  If not, INDX is moved to the next element, and we */
        /* repeat the process until a valid position is found.          */
        /****************************************************************/
        go_to = statset[state_no].go_to;
        indx = first_index;

look_for_match_in_base_table:
        if (indx == NIL)
            indx = table_size + 1;
        if (indx + last_symbol > table_size)
            reallocate();
        for (i = 1; i <= go_to.size; i++)
        {
            if (next[indx + GOTO_SYMBOL(go_to, i)] == OMEGA)
            {
                indx = next[indx];
                goto look_for_match_in_base_table;
            }
        }

        /*****************************************************************/
        /* At this stage, a position(INDX), was found to overlay the row */
        /* in question.  Remove elements associated with all positions   */
        /* that will be taken by row from the doubly-linked list.        */
        /* NOTE tha since SYMBOLs start at 1, the first index can never  */
        /* be a candidate (==> I = INDX + SYMBOL) in this loop.          */
        /*****************************************************************/
        for (j = 1; j <= go_to.size; j++)
        {
            symbol = GOTO_SYMBOL(go_to, j);
            i = indx + symbol;
            if (i == last_index)
            {
                last_index = previous[last_index];
                next[last_index] = NIL;
            }
            else
            {
                next[previous[i]] = next[i];
                previous[next[i]] = previous[i];
            }
            next[i] = OMEGA;
        }

        if (first_index == last_index)
            first_index = NIL;
        else if (indx == first_index)
        {
            first_index = next[first_index];
            previous[first_index] = NIL;
        }
        else if (indx == last_index)
        {
            last_index = previous[last_index];
            next[last_index] = NIL;
        }
        else
        {
            next[previous[indx]] = next[indx];
            previous[next[indx]] = previous[indx];
        }
        next[indx] = OMEGA;
        if (indx > max_indx)
            max_indx = indx;
        state_index[state_no] =  indx;
    }

    if (goto_default_bit || nt_check_bit)
        check_size = max_indx + num_non_terminals;
    else
        check_size = 0;

    for (action_size = max_indx + last_symbol;
         action_size >= max_indx; action_size--)
        if (next[action_size] == OMEGA)
            break;

    accept_act = max_indx + num_rules + 1;
    error_act = accept_act + 1;

    printf("\n");
    if (goto_default_bit || nt_check_bit)
    {
        sprintf(msg_line,"Length of base Check Table: %d", check_size);
        PRNT(msg_line);
    }

    sprintf(msg_line,"Length of base Action Table: %ld", action_size);
    PRNT(msg_line);

    sprintf(msg_line,"Number of entries in base Action Table: %d",
            num_table_entries);
    PRNT(msg_line);

    percentage = ((action_size - num_table_entries) * 1000)
                   / num_table_entries;
    sprintf(msg_line, "Percentage of increase: %d.%d%%",
                      percentage / 10, percentage % 10);
    PRNT(msg_line);

    if (byte_bit)
    {
        num_bytes = 2 * action_size + check_size;
        if (goto_default_bit || nt_check_bit)
        {
            if (last_symbol > 255)
                num_bytes += check_size;
        }
    }
    else
        num_bytes = 2 * (action_size + check_size);

    if (goto_default_bit)
        num_bytes += ((long) 2 * num_non_terminals);
    total_bytes = num_bytes;

    k_bytes = (num_bytes / 1024) + 1;

    sprintf(msg_line,"Storage required for base Tables: %ld Bytes, %dK",
            num_bytes, k_bytes);
    PRNT(msg_line);
    num_bytes = (long) 4 * num_rules;
    if (byte_bit)
    {
        num_bytes -= num_rules;
        if (num_non_terminals < 256)
            num_bytes -= num_rules;
    }
    sprintf(msg_line, "Storage required for Rules: %ld Bytes", num_bytes);
    PRNT(msg_line);

    return;
}


/*********************************************************************/