symboltable.c

decafc的源代码

/****************************************************************************
 * File name:	symbolTable.c						    *
 * Description: program defines a set of symbol table manipulation	    *
 *		functions						    *
 * Input:       none							    *
 * Output:      none							    *
 * Author:      Luojian Chen                                                *
 * Date:        April 16, 1997					    *
 ****************************************************************************/


#include "symbolTable.h"


/* global function prototypes */

SymbolTablePtr		NewSymbolTable(int);
SymbolTablePtr		DupSymbolTable(SymbolTablePtr);
ElementPtr		Lookup(SymbolTablePtr, String);
ElementPtr		Insert(SymbolTablePtr, String, int, ElementPtr);
void			Delete(SymbolTablePtr, String);
void			Difference(SymbolTablePtr, SymbolTablePtr);
int			Hash(String, int);
void			FreeSymbolTable(SymbolTablePtr);
void			DisplaySymbolTable(SymbolTablePtr);
void			NewSymbolTableStack(SymbolTableStackPtr);
void			FreeSymbolTableStack(SymbolTableStackPtr);
//void			Push(SymbolTableStackPtr, SymbolTablePtr);
void			Push(SymbolTableStackPtr, SymbolTablePtr, int);
// SymbolTablePtr		Pop(SymbolTableStackPtr);
void			Pop(SymbolTableStackPtr, SymbolTablePtr *, int *);
// SymbolTablePtr		Top(SymbolTableStackPtr);


/* local function prototypes */

static void	FreeHashTableEntry(HashTableEntry);
static void	FreeElement(ElementPtr);

/****************************************************************************
 Function name:		NewSymbolTable
 Description:		create a new symbol table
 Procedure:		1. allocate memory for the symbol table
			2. initialize the symbol table
 Return value:		pointer to the created symbol table
 Input parameter:	numberOfEntries	number of entries in the hash table
 Output parameter:	none
 ****************************************************************************/
SymbolTablePtr NewSymbolTable(int	numberOfEntries)
{
	SymbolTablePtr	symbolTablePtr = NULL;
	int		i;

	/* allocate memory for the symbol table itself */

	symbolTablePtr = (SymbolTablePtr)malloc(sizeof(SymbolTable));

	if (symbolTablePtr == NULL) {
		fprintf(stderr, "Out of memory\n");
		exit(1);
	}

	/* allocate memory for the hash table in the symbol table */

	symbolTablePtr->hashTable = (HashTable)malloc(
			       sizeof(HashTableEntry) * numberOfEntries);

	if (symbolTablePtr->hashTable == NULL) {
		fprintf(stderr, "Out of memory\n");
		exit(1);
	}

	/* initialize the symbol table */

	symbolTablePtr->numberOfEntries = numberOfEntries;

	for (i = 0; i < numberOfEntries; i ++) {
		(symbolTablePtr->hashTable)[i] = NULL;
	}

	/* return the pointer to the created symbol table */
	return(symbolTablePtr);
}

SymbolTablePtr	DupSymbolTable(SymbolTablePtr	symbolTablePtr)
{
	SymbolTablePtr	newSymbolTablePtr = NULL;
	int		i;
	int		numberOfEntries;
	ElementPtr	elementPtr = NULL;

	numberOfEntries = symbolTablePtr->numberOfEntries;

	/* allocate memory for the symbol table itself */

	newSymbolTablePtr = (SymbolTablePtr)malloc(sizeof(SymbolTable));

	if (newSymbolTablePtr == NULL) {
		fprintf(stderr, "Out of memory\n");
		exit(1);
	}

	/* allocate memory for the hash table in the symbol table */

	newSymbolTablePtr->hashTable = (HashTable)malloc(
				sizeof(HashTableEntry) * numberOfEntries);

	if (newSymbolTablePtr->hashTable == NULL) {
		fprintf(stderr, "Out of memory\n");
		exit(1);
	}

	/* initialize the symbol table */

	newSymbolTablePtr->numberOfEntries = numberOfEntries;

	for (i = 0; i < numberOfEntries; i ++) {
		(newSymbolTablePtr->hashTable)[i] = NULL;
		elementPtr = (symbolTablePtr->hashTable)[i];
		if (elementPtr != NULL) {
			do {
				Insert(newSymbolTablePtr,
				       elementPtr->id,
				       elementPtr->offset,
				       elementPtr->typePtr);
				elementPtr = elementPtr->next;
			} while (elementPtr != NULL);
		}
	}

	/* return the pointer to the created symbol table */
	return(newSymbolTablePtr);
}
	
/****************************************************************************
 Function name:		Lookup
 Description:		lookup a symbol in the symbol table
 Procedure:		1. calculate the entry index of the symbol in the
			   hash table
			2. search the element list in this entry
			3. if the symbol is found in the list
				return the element pointer
			   else
				return NULL	
 Return value:		pointer to the element containing the symbol, if the
			symbol is found in the hash table
			NULL, if the symbol is not found in the hash table
 Input parameter:	symbolTablePtr	pointer to the symbol table
			Id		id of the symbol
 Output parameter:	none
 ****************************************************************************/
ElementPtr Lookup(SymbolTablePtr	symbolTablePtr,
		  String		id)
{
	int		entryIndex;
	ElementPtr	elementPtr;

	/* printf("***Lookup %s\n", id); */
	/* calculate the entry index of the symbol in the hash table */

	entryIndex = Hash(id, symbolTablePtr->numberOfEntries);
	elementPtr = (symbolTablePtr->hashTable)[entryIndex];

	/* if there is no element in this entry, the symbol does not exist,
	   return NULL*/
	
	if (elementPtr == NULL) {
		return(NULL);
	}

	/* search the list of elements in this entry and return the index
	   if the symbol is found in the list */

	while (elementPtr != NULL) {
		if (strcmp(elementPtr->id, id) == 0) {
			return(elementPtr);
		}
		elementPtr = elementPtr->next;
	}

	/* the symbol is not found in the list, return NULL */
	return(NULL);
}

/****************************************************************************
 Function name:		Insert
 Description:		insert a symbol into the symbol table
 Procedure:		1. calculate the entry index of the symbol in the
			   hash table
			2. allocate memory for the symbol
			3. store information of the symbol
			4. insert the symbol into the hash table
 Return value:		pointer to the element
 Input parameter:	symbolTablePtr	pointer to the symbol table
			id		id of the symbol
			offset		offset of the symbol
			typePtr		pointer to the type of the symbol
 Output parameter:	none
 ****************************************************************************/
ElementPtr	Insert(SymbolTablePtr	symbolTablePtr,
		       String		id,
		       int		offset,
		       ElementPtr	typePtr)
{
	int		entryIndex;
	ElementPtr	elementPtr;

	/* calculate the entry index of the symbol in the hash table */

	entryIndex = Hash(id, symbolTablePtr->numberOfEntries);

	/* allocate memory for the symbol */

	elementPtr = (ElementPtr)malloc(sizeof(Element));

	if (elementPtr == NULL) {
		fprintf(stderr, "Out of memory\n");
		exit(1);
	}

	elementPtr->id = (String)malloc(strlen(id) + 1);

	if (elementPtr->id == NULL) {
		fprintf(stderr, "Out of memory\n");
		exit(1);
	}

	/* store information of the symbol */

	strcpy(elementPtr->id, id);
	elementPtr->offset = offset; 
	elementPtr->typePtr = typePtr; 

	/* insert the symbol into the hash table */

	elementPtr->next = (symbolTablePtr->hashTable)[entryIndex];
	(symbolTablePtr->hashTable)[entryIndex] = elementPtr;

	return(elementPtr);
}

/****************************************************************************
 Function name:		Delete
 Description:		delete a symbol from the symbol table
 Procedure:		1. calculate the entry index of the symbol in the
			   hash table
			2. find the symbol in the list in this entry
			3. delete the symbol from the list
 Return value:		none
 Input parameter:	symbolTablePtr	pointer to the symbol table
			id		id of the symbol
 Output parameter:	none
 ****************************************************************************/
void Delete(SymbolTablePtr	symbolTablePtr,
	    String		id)
{
	int		entryIndex;
	ElementPtr	elementPtr;
	ElementPtr	tempElementPtr;

	/* calculate the entry index of the symbol in the hash table */

	entryIndex = Hash(id, symbolTablePtr->numberOfEntries);

	/* check if the symbol is the first one in the list of symbols in
	   this entry */
	if (strcmp(((symbolTablePtr->hashTable)[entryIndex])->id, id) == 0) {

		/* delete the symbol from the list */

		tempElementPtr = (symbolTablePtr->hashTable)[entryIndex];
		(symbolTablePtr->hashTable)[entryIndex] =
		  (symbolTablePtr->hashTable)[entryIndex]->next;
		free(tempElementPtr->id);
		free(tempElementPtr);
		return;
	}
		
	/* the symbol is not the first one in the list, search the list */

	elementPtr = (symbolTablePtr->hashTable)[entryIndex];
	while (elementPtr->next != NULL) {