www.pudn.com > HEC-linux.zip > hashtbl.cpp

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 
+                                                                   + 
+ hashtbl.cpp - the hash table                                      + 
+                                                                   + 
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ 
 
/* 
	The hash table is the gateway to the entire process of creating 
	a symbol table and resolving indentifiers during assembly 
 
	During Pass1 ( directives populate Proc and GlobVar arrays ) 
	------------ 
	 
	1) encounter a identifier declaration 
	2) take hash and query hash table 
		2a) if exists ( query proc returns non-NULL )  
			print error, redefinition 
		2b) if does not exist ( query proc returns NULL ) 
			add entry to string table 
			add entry to symbol table 
			add entry to hash table 
 
	During Pass2 ( gen. bytecode ) 
	------------ 
	 
	1) encounter a identifier in an instruction 
	2) take hash and query hash table 
		2a) if exists ( query proc returns non-NULL )  
			generate bytecode 
		2b) if does not exist ( query proc returns NULL ) 
			print error, referencing non-existent identifier 
*/ 
 
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 
+ macros                                                            + 
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ 
 
/*hash table type*/ 
 
#define GLOBAL_VAR	0	 
#define PROC		1 
#define PROC_RET	2 
#define PROC_ARG	3 
#define PROC_LOC	4 
#define PROC_LBL	5 
 
char *SymTypeStr[]={"GLOBAL_VAR", 
                    "PROC", 
                    "PROC_RET","PROC_ARG","PROC_LOC","PROC_LBL"}; 
 
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 
+ declaration                                                       + 
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ 
 
struct HashTbl 
{ 
	U1 empty;		/*indicates if entry is used or not*/ 
    U8 text;		/*index to strTbl*/ 
	U1 type;		/*GLOBAL_VAR -> PROC_LBL*/ 
	U4 index;		/*index to globVar, proc arrays in symbTbl*/ 
	U4 subIndex;	/*subindex for PROC_RET, ... , PROC_LBL*/ 
    struct HashTbl *left; 
    struct HashTbl *right; 
}; 
 
#define PRIME 547 
//#define PRIME 5 
 
class HashTable 
{ 
	StringTable *strTbl; 
 
	int hashpjw(unsigned char *s); 
 
	/*collision resolution BST routines*/ 
	struct HashTbl* findNode(struct HashTbl* link, char *val); 
	void 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); 
 
	public: 
	struct HashTbl hashTbl[PRIME]; 
 
	HashTable(StringTable *st); 
	~HashTable(); 
 
	/*hash table routine calls corresponding BST rotuine*/ 
	struct HashTbl* queryHashTbl(char *str); 
	void addHashTblEntry(char *val, U8 text, U1 type, U4 ind, U4 subInd, U4 line ); 
	void printHashTbl(); 
 
	void test(); 
}; 
 
/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 
+ definitions                                                        + 
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ 
 
HashTable::HashTable(StringTable *st) 
{ 
	int i; 
	for(i=0;i> 24); 
			h = h ^ g; 
		} 
	} 
 
	return h % PRIME; 
 
}/*end hashpjw*/ 
 
/*-----------------------------------------------------------------*/ 
 
struct HashTbl* HashTable::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)); 
    } 
 
}/*end findNode*/ 
 
/*-----------------------------------------------------------------*/ 
 
void HashTable::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)); 
		(*(*link)).empty	= FALSE; 
		(*(*link)).text		= text; 
		(*(*link)).type     = type; 
		(*(*link)).index    = ind; 
		(*(*link)).subIndex = subInd; 
        (*(*link)).left		= NULL; 
        (*(*link)).right	= NULL; 
    } 
    else if( strcmp(val,(char*)&((*strTbl).text[(*(*link)).text])) == 0 ) 
    { 
		ERROR2("re-defined identifier %s on line %lu\n",val,line); 
        return; 
    } 
	else if( strcmp(val,(char*)&((*strTbl).text[(*(*link)).text])) < 0 ) 
    { 
        insertNode( &((*(*link)).left) , val, text, type, ind, subInd, line); 
    } 
    else 
    { 
        insertNode( &((*(*link)).right) ,val, text, type, ind, subInd, line); 
    } 
    return; 
 
}/*end insertNode*/ 
 
/*-----------------------------------------------------------------*/ 
 
void HashTable::deleteAllNodes(struct HashTbl** link) 
{ 
	if(*link==NULL){ return; } 
	 
	deleteAllNodes(&(*(*link)).left); 
	deleteAllNodes(&(*(*link)).right); 
 
	//printf("freeing node %s\n",&((*strTbl).text[(*(*link)).text])); 
	free(*link); 
	*link=NULL; 
 
	return; 
 
}/*end deleteAllNodes*/ 
 
/*-----------------------------------------------------------------*/ 
 
/* 
print tree by giving root to node and zero as args 
*/ 
 
void HashTable::printTree(struct HashTbl* link, int level) 
{ 
    int i; 
    if(link==NULL) 
    { 
        return; 
    } 
    printTree((*link).right,level+1); 
    for(i=0;i