hashtbl.c

< 虚拟机设计与实现> 的source code, linux版本

#include "hashtbl.h"

#include "strtbl.h"
#include "error.h"

char * SymTypeStr[] ={ "GLOBAL_VAR",
                       "PROC",
                        "PROC_RET", "PROC_ARG", "PROC_LOC", "PROC_LBL"};

struct HashTbl hashTbl[PRIME];

int hashpjw(unsigned char *s);

/*collision resolution BST routines*/
struct HashTbl* findNode(struct HashTbl* link, char *val);
int insertNode(struct HashTbl** link, char *val, U8 text, U1 type, U4 ind, U4 subInd, U4 line);
void printTree(struct HashTbl* link, int level);

void deleteAllNodes(struct HashTbl** link);

void HashTable_init()
{
	int i;
	
	for (i = 0; i < PRIME; i++)
	{ 
		hashTbl[i].empty = TRUE;
		hashTbl[i].text = 0;	
		hashTbl[i].left = NULL;
		hashTbl[i].right = NULL;
	}
	return;

}

void HashTable_free()
{
	int i;

	for (i = 0; i < PRIME; i++)
	{ 	
		deleteAllNodes( &(hashTbl[i].left) );
		deleteAllNodes( &(hashTbl[i].right) );
	}
	printf("HashTable freed.\n");
	return;

}

int addHashTblEntry(char * val, U8 text, U1 type, 
					    U4 ind,  U4 subInd, U4 line)
{
	struct HashTbl * ptr;
	int hash;

	hash = hashpjw((unsigned char*)val);
	
	if (hashTbl[hash].empty == TRUE)
	{ 
		hashTbl[hash].empty = FALSE;
		hashTbl[hash].text = text; 
		hashTbl[hash].type = type;
		hashTbl[hash].index = ind;
		hashTbl[hash].subIndex = subInd;
		hashTbl[hash].left = NULL;
		hashTbl[hash].right = NULL;
		return TRUE; 
	}

	ptr = &hashTbl[hash];
	return insertNode(&ptr, val, text, type, ind, subInd, line);

}

int insertNode(struct HashTbl** link, 
						   char * val, 
						   U8 text, 
						   U1 type, 
						   U4 ind, 
						   U4 subInd,
						   U4 line)
{
    if ( (*link) == NULL )
    {
        (*link) = (struct HashTbl *)malloc(sizeof(struct HashTbl));
		if ( (*link) == NULL)
		{
			ERROR0("hashtbl::insertNode() malloc failed.\n");
			return FALSE;
		}
		(*(*link)).empty	= FALSE;
		(*(*link)).text		= text;
		(*(*link)).type     = type;
		(*(*link)).index    = ind;
		(*(*link)).subIndex = subInd;
        (*(*link)).left		= NULL;
        (*(*link)).right	= NULL;
		return TRUE;
    }
    else if (strcmp(val, (char *)&(strtbl_text[(*(*link)).text])) == 0)
    {
		ERROR2("re-defined identifier %s on line %lu\n", val, line);
        return FALSE;
    }
	else if( strcmp(val, (char *)&(strtbl_text[(*(*link)).text])) < 0)
    {
        return insertNode( &((*(*link)).left), val, text, type, ind, subInd, line);
    }
    else
    {
        return insertNode( &((*(*link)).right), val, text, type, ind, subInd, line);
    }

}

int hashpjw(unsigned char *s)
{
	unsigned char * p;
	unsigned int h = 0;
	unsigned int g = 0;

	for (p = s; *p != '\0'; p = p + 1)
	{
		h = (h << 4) + (*p);
        g = (h & 0xf0000000);
		if (g)
		{
			h = h ^ (g >> 24);
			h = h ^ g;
		}
	}
	return h % PRIME;

}

/*
if symbol exists in hash table, we get a pointer to the node
if a symbol does not exist in the hash table, we get NULL
*/

struct HashTbl * queryHashTbl(char *str)
{
	int hash;

	hash = hashpjw((unsigned char *)str);
	if (hashTbl[hash].empty == TRUE)
	    return NULL;
	return findNode(&(hashTbl[hash]), str);

}

struct HashTbl * findNode(struct HashTbl * link, char *val)
{
    if (link == NULL)
        return NULL; 
    else if (strcmp(val, (char *)&(strtbl_text[(*link).text])) == 0)
    { 
        return link; 
    }
    else if (strcmp(val, (char *)&(strtbl_text[(*link).text])) >0)
    { 
        return findNode((*link).right, val); 
    }
    else
    {
        return findNode((*link).left, val);
    }
}

void deleteAllNodes(struct HashTbl** link)
{
	if (*link == NULL)
		return;
	
	deleteAllNodes( &(*(*link)).left );
	deleteAllNodes( &(*(*link)).right );

	free(*link);
	*link = NULL;
	return;

}

void printHashTbl()
{
	int i;

	printf("\nHASH TABLE--------------\n");
	for (i = 0; i < PRIME; i++)
	{ 
		if (hashTbl[i].empty == FALSE)
		{
			printf("Hash Slot %d)------\n", i);
			printTree(&(hashTbl[i]), 0);
			printf("\n");
		}
	}
	printf("\n");
	return;

}

void printTree(struct HashTbl* link, int level)
{
    int i;

    if (link == NULL)
        return;

    printTree((*link).right, level + 1);
    for (i = 0; i < level; i++)
	    printf("-");

    printf("id =%s\t", &(strtbl_text[(*link).text]));
	printf("type=%s\t", SymTypeStr[(*link).type]);
	printf("(i,si)=(%d,%d)\n", (*link).index, (*link).subIndex);

    printTree((*link).left, level + 1);
    return;

}

void test_HashTbl()
{
	U8 i;
	char name[20];

	i = strtbl_iStr;
	addStrTbl("harold"); 
	addHashTblEntry("harold", i, 0, 0, 0, 0);

	i = strtbl_iStr;
	addStrTbl("andrew"); 
	addHashTblEntry("andrew", i, 0, 0, 0, 0);

	i = strtbl_iStr;
	addStrTbl("jake"); 
	addHashTblEntry("jake", i, 0, 0, 0, 0);

	i = strtbl_iStr;
	addStrTbl("bart"); 
	addHashTblEntry("bart", i, 0, 0, 0, 0);

	i = strtbl_iStr;
	addStrTbl("xavier"); 
	addHashTblEntry("xavier", i, 0, 0, 0, 0);

	i = strtbl_iStr;
	addStrTbl("randall"); 
	addHashTblEntry("randall", i, 0, 0, 0, 0);

	i = strtbl_iStr;
	addStrTbl("earl"); 
	addHashTblEntry("earl", i, 0, 0, 0, 0);

	i = strtbl_iStr;
	addStrTbl("greg"); 
	addHashTblEntry("greg", i, 0, 0, 0, 0);

	i = strtbl_iStr;
	addStrTbl("damien"); 
	addHashTblEntry("damien", i, 0, 0, 0, 0);
	
	strcpy(name,"randall");
	if ((queryHashTbl(name)) != NULL)
	{ 
		printf("found %s\n", name); 
	}
	else
	{ 
		printf("NOT find %s\n", name); 
	}

	strcpy(name,"herb");
	if ((queryHashTbl(name)) != NULL)
	{ 
		printf("found %s\n", name); 
	}
	else
	{ 
		printf("NOT find %s\n", name); 
	}
	
	strcpy(name,"earl");
	if ((queryHashTbl(name)) != NULL)
	{ 
		printf("found %s\n", name); 
	}
	else
	{ 
		printf("NOT find %s\n", name); 
	}
	
	strcpy(name, "pearl");
	if ((queryHashTbl(name)) != NULL)
	{ 
		printf("found %s\n", name); 
	}
	else
	{ 
		printf("NOT find %s\n", name); 
	}

	printHashTbl();
	return;

}