lpgutil.c

一个非常好的检索工具

/* $Id: lpgutil.c,v 1.2 1999/11/04 14:02:22 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 <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "common.h"
#include "header.h"

/**********************************************************************/
/* The following are global variables and constants used to manage a  */
/* pool of temporary space. Externally, the user invokes the function */
/* "talloc" just as he would invoke "malloc".                         */
/**********************************************************************/
#ifdef DOS
#define LOG_BLKSIZE 12
#else
#define LOG_BLKSIZE 14
#endif

#define BLKSIZE (1 << LOG_BLKSIZE)
#define BASE_INCREMENT 64

typedef long cell;

static cell **temp_base = NULL;
static long temp_top = 0,
            temp_size = 0,
            temp_base_size = 0;

/**********************************************************************/
/*                          ALLOCATE_MORE_SPACE:                      */
/**********************************************************************/
/* This procedure obtains more TEMPORARY space.                       */
/**********************************************************************/
static BOOLEAN allocate_more_space(cell ***base, long *size, long *base_size)
{
    int k;

/**********************************************************************/
/* The variable size always indicates the maximum number of cells     */
/* that has been allocated and reserved for the storage pool.         */
/* Initially, size should be set to 0 to indicate that no space has   */
/* yet been allocated. The pool of cells available is divided into    */
/* segments of size 2**LOG_BLKSIZE each and each segment is pointer   */
/* to by a slot in the array base.                                    */
/*                                                                    */
/* By dividing "size" by the size of the segment we obtain the        */
/* index for the next segment in base. If base is already full, it is */
/* reallocated.                                                       */
/*                                                                    */
/**********************************************************************/
    k = (*size) >> LOG_BLKSIZE; /* which segment? */
    if (k == (*base_size))      /* base overflow? reallocate */
    {
        register int i = (*base_size);

        (*base_size) += BASE_INCREMENT;
        (*base) = (cell **)
                  ((*base) == NULL ?
                   malloc(sizeof(cell *) * (*base_size)) :
                   realloc((*base), sizeof(cell *) * (*base_size)));
        if ((*base) == (cell **) NULL)
            return FALSE;

        for (i = i; i < (*base_size); i++)
            (*base)[i] = NULL;
    }

/**********************************************************************/
/* If the Ast slot "k" does not already contain a segment, We try to  */
/* allocate one and place its address in (*base)[k].                  */
/* If the allocation was not successful, we terminate;                */
/* otherwise, we adjust the address in (*base)[k] so as to allow us   */
/* to index the segment directly, instead of having to perform a      */
/* subtraction for each reference. Finally, we update size.           */
/*                                                                    */
/* Finally, we set the block to zeros.                                */
/**********************************************************************/
    if ((*base)[k] == NULL)
    {
        (*base)[k] = (cell *) malloc(sizeof(cell) << LOG_BLKSIZE);
        if ((*base)[k] == (cell *) NULL)
            return FALSE;
        (*base)[k] -= (*size);
    }

    memset((void *)((*base)[k] + (*size)), 0, sizeof(cell) << LOG_BLKSIZE);
    (*size) += BLKSIZE;

    return TRUE;
}


/**********************************************************************/
/*                         RESET_TEMPORARY_SPACE:                     */
/**********************************************************************/
/* This procedure resets the temporary space already allocated so     */
/* that it can be reused before new blocks are allocated.             */
/**********************************************************************/
void reset_temporary_space(void)
{
    temp_top = 0;         /* index of next usable elemt */
    temp_size = 0;

    return;
}


/**********************************************************************/
/*                         FREE_TEMPORARY_SPACE:                      */
/**********************************************************************/
/* This procedure frees all allocated temporary space.                */
/**********************************************************************/
void free_temporary_space(void)
{
    int k;

    for (k = 0; k < temp_base_size && temp_base[k] != NULL; k++)
    {
        temp_base[k] += (k * BLKSIZE);
        ffree(temp_base[k]);
    }

    if (temp_base != NULL)
    {
        ffree(temp_base);
        temp_base = NULL;
    }

    temp_base_size = 0;
    temp_top = 0;
    temp_size = 0;

    return;
}


/**********************************************************************/
/*                                TALLOC:                             */
/**********************************************************************/
/* talloc allocates an object of size "size" in temporary space and   */
/* returns a pointer to it.                                           */
/**********************************************************************/
void *talloc(long size)
{
    long i;

    i = temp_top;
    temp_top += ((size + sizeof(cell) - 1) / sizeof(cell));
    if (temp_top > temp_size)
    {
        i = temp_size;
        temp_top = temp_size +
                   ((size + sizeof(cell) - 1) / sizeof(cell));
        if (! allocate_more_space(&temp_base, &temp_size, &temp_base_size))
        {
            temp_top = temp_size;
            return NULL;
        }
    }

    return ((void *) &(temp_base[i >> LOG_BLKSIZE] [i]));
}


/**********************************************************************/
/*                      TEMPORARY_SPACE_ALLOCATED:                    */
/**********************************************************************/
/* Return the total size of temporary space allocated.                */
/**********************************************************************/
long temporary_space_allocated(void)
{
    return ((temp_base_size * sizeof(cell **)) +
            (temp_size * sizeof(cell)));
}


/**********************************************************************/
/*                         TEMPORARY_SPACE_USED:                      */
/**********************************************************************/
/* Return the total size of temporary space used.                     */
/**********************************************************************/
long temporary_space_used(void)
{
    return (((temp_size >> LOG_BLKSIZE) * sizeof(cell **)) +
             (temp_top * sizeof(cell)));
}


/**********************************************************************/
/*                                                                    */
/* The following are global variables and constants used to manage a  */
/* pool of global space. Externally, the user invokes one of the      */
/* functions:                                                         */
/*                                                                    */
/*    ALLOCATE_NODE                                                   */
/*    ALLOCATE_GOTO_MAP                                               */
/*    ALLOCATE_SHIFT_MAP                                              */
/*    ALLOCATE_REDUCE_MAP                                             */
/*                                                                    */
/* These functions allocate space from the global pool in the same    */
/* using the function "galloc" below.                                 */
/*                                                                    */
/**********************************************************************/
static cell **global_base = NULL;
static long global_top = 0,
            global_size = 0,
            global_base_size = 0;

static struct node *node_pool = NULL;

/**********************************************************************/
/*                          PROCESS_GLOBAL_WASTE:                     */
/**********************************************************************/
/* This function is invoked when the space left in a segment is not   */
/* enough for GALLOC to allocate a requested object. Rather than      */
/* waste the space, as many NODE structures as possible are allocated */
/* in that space and stacked up in the NODE_POOL list.                */
/**********************************************************************/
static void process_global_waste(long top)
{
    struct node *p;
    long i;

    while (TRUE)
    {
        i = top;
        top += ((sizeof(struct node) + sizeof(cell) - 1) / sizeof(cell));
        if (top > global_size)
            break;
        p = (struct node *) &(global_base[i >> LOG_BLKSIZE] [i]);
        p -> next = node_pool;
        node_pool = p;
    }

    return;
}

/**********************************************************************/
/*                                GALLOC:                             */
/**********************************************************************/
/* galloc allocates an object of size "size" in global space and      */
/* returns a pointer to it. It is analoguous to "talloc", but it      */
/* is a local (static) routine that is only invoked in this file by   */
/* other more specialized routines.                                   */
/**********************************************************************/
static void *galloc(long size)
{
    long i;

    i = global_top;
    global_top += ((size + sizeof(cell) - 1) / sizeof(cell));
    if (global_top > global_size)
    {
        process_global_waste(i);
        i = global_size;
        global_top = global_size +
                     ((size + sizeof(cell) - 1) / sizeof(cell));
        if (! allocate_more_space(&global_base,
                                  &global_size, &global_base_size))
        {
            global_top = global_size;
            return NULL;
        }
    }

    return ((void *) &(global_base[i >> LOG_BLKSIZE] [i]));
}


/****************************************************************************/
/*                              ALLOCATE_NODE:                              */
/****************************************************************************/
/*   This function allocates a node structure and returns a pointer to it.  */
/* it there are nodes in the free pool, one of them is returned. Otherwise, */
/* a new node is allocated from the global storage pool.                    */
/****************************************************************************/
struct node *allocate_node(char *file, long line)
{
    struct node *p;

    p = node_pool;
    if (p != NULL)  /* is free list not empty? */
         node_pool = p -> next;
    else
    {
        p = (struct node *) galloc(sizeof(struct node));
        if (p == NULL)
            nospace(file, line);
    }

    return(p);
}


/****************************************************************************/
/*                             FREE_NODES:                                  */
/****************************************************************************/
/*  This function frees a linked list of nodes by adding them to the free   */
/* list.  Head points to head of linked list and tail to the end.           */
/****************************************************************************/
void free_nodes(struct node *head, struct node *tail)
{
    tail -> next = node_pool;
    node_pool = head;

    return;
}


/****************************************************************************/
/*                             ALLOCATE_GOTO_MAP:                           */
/****************************************************************************/
/*   This function allocates space for a goto map with "size" elements,     */
/* initializes and returns a goto 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 goto_header_type allocate_goto_map(int size, char *file, long line)
{
    struct goto_header_type go_to;

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

    return(go_to);
}


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