lpgutil.c

一个非常好的检索工具

/*                            ALLOCATE_SHIFT_MAP:                           */
/****************************************************************************/
/*   This function allocates space for a shift map with "size" elements,    */
/* initializes and returns a shift header for that map. NOTE that after the */
/* map is successfully allocated, it is offset by one element. This is      */
/* to allow the array in question to be indexed from 1..size instead of     */
/* 0..(size-1).                                                             */
/****************************************************************************/
struct shift_header_type allocate_shift_map(int size,
                                            char *file, long line)
{
    struct shift_header_type sh;

    sh.size = size;
    sh.map = (struct shift_type *)
             galloc(size * sizeof(struct shift_type));
    if (sh.map == NULL)
        nospace(file, line);
    sh.map--;   /* map will be indexed in range 1..size */

    return(sh);
}


/****************************************************************************/
/*                             ALLOCATE_REDUCE_MAP:                         */
/****************************************************************************/
/*   This function allocates space for a REDUCE map with "size"+1 elements, */
/* initializes and returns a REDUCE header for that map. The 0th element of */
/* a reduce map is used for the default reduction.                          */
/****************************************************************************/
struct reduce_header_type allocate_reduce_map(int size,
                                              char *file, long line)
{
    struct reduce_header_type red;

    red.map = (struct reduce_type *)
              galloc((size + 1) * sizeof(struct reduce_type));
    if (red.map == NULL)
        nospace(file, line);
    red.size = size;

    return(red);
}


/**********************************************************************/
/*                        GLOBAL_SPACE_ALLOCATED:                     */
/**********************************************************************/
/* Return the total size of global space allocated.                   */
/**********************************************************************/
long global_space_allocated(void)
{
    return ((global_base_size * sizeof(cell **)) +
            (global_size * sizeof(cell)));
}


/**********************************************************************/
/*                           GLOBAL_SPACE_USED:                       */
/**********************************************************************/
/* Return the total size of global space used.                        */
/**********************************************************************/
long global_space_used(void)
{
    return (((global_size >> LOG_BLKSIZE) * sizeof(cell **)) +
             (global_top * sizeof(cell)));
}


/****************************************************************************/
/*                           ALLOCATE_INT_ARRAY:                            */
/****************************************************************************/
/*   This function allocates an array of size "size" of int integers.       */
/****************************************************************************/
int *allocate_int_array(long size, char *file, long line)
{
    int *p;

    p = (int *) calloc(size, sizeof(int));
    if (p == (int *) NULL)
        nospace(file, line);

    return(&p[0]);
}


/****************************************************************************/
/*                           ALLOCATE_SHORT_ARRAY:                          */
/****************************************************************************/
/*   This function allocates an array of size "size" of short integers.     */
/****************************************************************************/
short *allocate_short_array(long size, char *file, long line)
{
    short *p;

    p = (short *) calloc(size, sizeof(short));
    if (p == (short *) NULL)
        nospace(file, line);

    return(&p[0]);
}


/****************************************************************************/
/*                           ALLOCATE_BOOLEAN_ARRAY:                        */
/****************************************************************************/
/*   This function allocates an array of size "size" of type boolean.       */
/****************************************************************************/
BOOLEAN *allocate_boolean_array(long size, char *file, long line)
{
    BOOLEAN *p;

    p = (BOOLEAN *) calloc(size, sizeof(BOOLEAN));
    if (p == (BOOLEAN *) 0)
        nospace(file, line);

    return(&p[0]);
}


/*****************************************************************************/
/*                              FILL_IN:                                     */
/*****************************************************************************/
/* FILL_IN is a subroutine that pads a buffer, STRING,  with CHARACTER a     */
/* certain AMOUNT of times.                                                  */
/*****************************************************************************/
void fill_in(char string[], int amount, char character)
{
    int i;

    for (i = 0; i <= amount; i++)
        string[i] = character;
    string[i] = '\0';

    return;
}


/*****************************************************************************/
/*                                  QCKSRT:                                  */
/*****************************************************************************/
/* QCKSRT is a quicksort algorithm that takes as arguments an array of       */
/* integers, two numbers L and H that indicate the lower and upper bound     */
/* positions in ARRAY to be sorted.                                          */
/*****************************************************************************/
static void qcksrt(short array[], int l, int h)
{
    int lower,
        upper,
        top,
        i,
        j,
        pivot,
        lostack[14],  /* A stack of size 14 can sort an array of up to */
        histack[14];  /* 2 ** 15 - 1 elements                          */

    top = 1;
    lostack[top] = l;
    histack[top] = h;
    while (top != 0)
    {
        lower = lostack[top];
        upper = histack[top--];

        while (upper > lower)
        {
            i = lower;
            pivot = array[lower];
            for (j = lower + 1; j <= upper; j++)
            {
                if (array[j] < pivot)
                {
                    array[i] = array[j];
                    i++;
                    array[j] = array[i];
                }
            }
            array[i] = pivot;

            top++;
            if (i - lower < upper - i)
            {
                lostack[top] = i + 1;
                histack[top] = upper;
                upper = i - 1;
            }
            else
            {
                histack[top] = i - 1;
                lostack[top] = lower;
                lower = i + 1;
            }
        }
    }

    return;
}


/*****************************************************************************/
/*                               NUMBER_LEN:                                 */
/*****************************************************************************/
/* NUMBER_LEN takes a state number and returns the number of digits in that  */
/* number.                                                                   */
/*****************************************************************************/
int number_len(int state_no)
{
    int num = 0;

    do
    {
        state_no /= 10;
        num++;
    }   while (state_no != 0);

    return num;
}


/*************************************************************************/
/*                            RESTORE_SYMBOL:                            */
/*************************************************************************/
/* This procedure takes two character strings as arguments: IN and OUT.  */
/* IN identifies a grammar symbol or name that is checked as to whether  */
/* or not it needs to be quoted. If so, the necessary quotes are added   */
/* as IN is copied into the space identified by OUT.                     */
/* NOTE that it is assumed that IN and OUT do not overlap each other.    */
/*************************************************************************/
void restore_symbol(char *out, char *in)
{
    int  len;

    len = strlen(in);
    if (len > 0)
    {
        if ((len == 1 && in[0] == ormark) ||
            (in[0] == escape)             ||
            (in[0] == '\'')               ||
            (in[len - 1] == '\'')         ||
            (strchr(in, ' ') != NULL &&
            (in[0] != '<' || in[len - 1] != '>')))
        {
            *(out++) = '\'';
            while(*in != '\0')
            {
                if (*in == '\'')
                    *(out++) = *in;
                *(out++) = *(in++);
            }
            *(out++) = '\'';
            *out = '\0';

            return;
        }
    }

    strcpy(out, in);

    if (out[0] == '\n')   /* one of the special grammar symbols? */
        out[0] = escape;

    return;
}


/*****************************************************************************/
/*                          PRINT_LARGE_TOKEN:                               */
/*****************************************************************************/
/* PRINT_LARGE_TOKEN generates code to print a token that may exceed the     */
/* limit of its field.  The argument are LINE which is the symbol a varying  */
/* length character string, TOKEN which is the symbol to be printed, INDENT  */
/* which is a character string to be used as an initial prefix to indent the */
/* output line, and LEN which indicates the maximum number of characters that*/
/* can be printed on a given line.  At the end of this process, LINE will    */
/* have the value of the remaining substring that can fit on the output line.*/
/* If a TOKEN is too large to be indented in a line, but not too large for   */
/* the whole line, we forget the indentation, and printed it. Otherwise, it  */
/* is "chapped up" and printed in pieces that are each indented.             */
/*****************************************************************************/
void print_large_token(char *line, char *token, char *indent, int len)
{
    int toklen;

    char temp[SYMBOL_SIZE + 1];

    toklen = strlen(token);

    if (toklen > len && toklen <= PRINT_LINE_SIZE-1)
    {
        fprintf(syslis, "\n%s", token);
        ENDPAGE_CHECK;
        token = "";
        strcpy(line,indent);
    }
    else
    {
        for (; toklen > len; toklen = strlen(temp))
        {
            memcpy(temp, token, len);
            temp[len] = '\0';
            fprintf(syslis, "\n%s",temp);
            ENDPAGE_CHECK;
            strcpy(temp, token+len + 1);
            token = temp;
        }
        strcpy(line,indent);
        strcat(line,token);
    }

    return;
}


/*****************************************************************************/
/*                                PRINT_ITEM:                                */
/*****************************************************************************/
/* PRINT_ITEM takes as parameter an ITEM_NO which it prints.                 */
/*****************************************************************************/
void print_item(int item_no)
{
    int rule_no,
        symbol,
        len,
        offset,
        i,
        k;

    char tempstr[PRINT_LINE_SIZE + 1],
         line[PRINT_LINE_SIZE + 1],
         tok[SYMBOL_SIZE + 1];

    /*********************************************************************/
    /* We first print the left hand side of the rule, leaving at least   */
    /* 5 spaces in the output line to accomodate the equivalence symbol  */
    /* "::=" surrounded by blanks on both sides.  Then, we print all the */
    /* terminal symbols in the right hand side up to but not including   */
    /* the dot symbol.                                                   */
    /*********************************************************************/

    rule_no = item_table[item_no].rule_number;
    symbol = rules[rule_no].lhs;

    restore_symbol(tok, RETRIEVE_STRING(symbol));