Restructuring for better separation of Tool packages.

[mirror_edk2.git] / Tools / CodeTools / TianoTools / Pccts / antlr / hash.c

/*\r
 * hash.c\r
 *\r
 * Manage hash tables.\r
 *\r
 * The following functions are visible:\r
 *\r
 *		char	*mystrdup(char *);		Make space and copy string\r
 *		Entry 	**newHashTable();		Create and return initialized hash table\r
 *		Entry	*hash_add(Entry **, char *, Entry *)\r
 *		Entry	*hash_get(Entry **, char *)\r
 *\r
 * SOFTWARE RIGHTS\r
 *\r
 * We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
 * Set (PCCTS) -- PCCTS is in the public domain.  An individual or\r
 * company may do whatever they wish with source code distributed with\r
 * PCCTS or the code generated by PCCTS, including the incorporation of\r
 * PCCTS, or its output, into commerical software.\r
 *\r
 * We encourage users to develop software with PCCTS.  However, we do ask\r
 * that credit is given to us for developing PCCTS.  By "credit",\r
 * we mean that if you incorporate our source code into one of your\r
 * programs (commercial product, research project, or otherwise) that you\r
 * acknowledge this fact somewhere in the documentation, research report,\r
 * etc...  If you like PCCTS and have developed a nice tool with the\r
 * output, please mention that you developed it using PCCTS.  In\r
 * addition, we ask that this header remain intact in our source code.\r
 * As long as these guidelines are kept, we expect to continue enhancing\r
 * this system and expect to make other tools available as they are\r
 * completed.\r
 *\r
 * ANTLR 1.33\r
 * Terence Parr\r
 * Parr Research Corporation\r
 * with Purdue University and AHPCRC, University of Minnesota\r
 * 1989-2001\r
 */\r
\r
#include <stdio.h>\r
#include "pcctscfg.h"\r
#include "hash.h"\r
\r
#ifdef __USE_PROTOS\r
#include <stdlib.h>\r
#else\r
#ifdef VAXC\r
#include <stdlib.h>\r
#else\r
#include <malloc.h>\r
#endif\r
#endif\r
#include <string.h>\r
\r
#define StrSame		0\r
\r
#define fatal(err)															\\r
			{fprintf(stderr, "%s(%d):", __FILE__, __LINE__);				\\r
			fprintf(stderr, " %s\n", err); exit(PCCTS_EXIT_FAILURE);}\r
#define require(expr, err) {if ( !(expr) ) fatal(err);}\r
\r
static unsigned size = HashTableSize;\r
static char *strings = NULL;\r
static char *strp;\r
static unsigned strsize = StrTableSize;\r
\r
/* create the hash table and string table for terminals (string table only once) */\r
Entry **\r
#ifdef __USE_PROTOS\r
newHashTable( void )\r
#else\r
newHashTable( )\r
#endif\r
{\r
	Entry **table;\r
	\r
	table = (Entry **) calloc(size, sizeof(Entry *));\r
	require( table != NULL, "cannot allocate hash table");\r
	if ( strings == NULL )\r
	{\r
		strings = (char *) calloc(strsize, sizeof(char));\r
		require( strings != NULL, "cannot allocate string table");\r
		strp = strings;\r
	}\r
	return table;\r
}\r
\r
void\r
#ifdef __USE_PROTOS\r
killHashTable( Entry **table )\r
#else\r
killHashTable( table )\r
Entry **table;\r
#endif\r
{\r
	/* for now, just free table, forget entries */\r
	free( (char *) table );     /* MR10 cast */\r
}\r
\r
/* Given a table, add 'rec' with key 'key' (add to front of list). return ptr to entry */\r
Entry *\r
#ifdef __USE_PROTOS\r
hash_add( Entry **table, char *key, Entry *rec )\r
#else\r
hash_add( table, key, rec )\r
Entry **table;\r
char *key;\r
Entry *rec;\r
#endif\r
{\r
	unsigned h=0;\r
	char *p=key;\r
	require(table!=NULL && key!=NULL && rec!=NULL, "add: invalid addition");\r
	\r
	Hash(p,h,size);\r
	rec->next = table[h];			/* Add to singly-linked list */\r
	table[h] = rec;\r
	return rec;\r
}\r
\r
/* Return ptr to 1st entry found in table under key (return NULL if none found) */\r
Entry *\r
#ifdef __USE_PROTOS\r
hash_get( Entry **table, char *key )\r
#else\r
hash_get( table, key )\r
Entry **table;\r
char *key;\r
#endif\r
{\r
	unsigned h=0;\r
	char *p=key;\r
	Entry *q;\r
/*	require(table!=NULL && key!=NULL, "get: invalid table and/or key");*/\r
	if ( !(table!=NULL && key!=NULL) ) *((char *) 34) = 3;\r
	\r
	Hash(p,h,size);\r
	for (q = table[h]; q != NULL; q = q->next)\r
	{\r
		if ( strcmp(key, q->str) == StrSame ) return( q );\r
	}\r
	return( NULL );\r
}\r
\r
#ifdef DEBUG_HASH\r
void\r
#ifdef __USE_PROTOS\r
hashStat( Entry **table )\r
#else\r
hashStat( table )\r
Entry **table;\r
#endif\r
{\r
	static unsigned short count[20];\r
	int i,n=0,low=0, hi=0;\r
	Entry **p;\r
	float avg=0.0;\r
	\r
	for (i=0; i<20; i++) count[i] = 0;\r
	for (p=table; p<&(table[size]); p++)\r
	{\r
		Entry *q = *p;\r
		int len;\r
		\r
		if ( q != NULL && low==0 ) low = p-table;\r
		len = 0;\r
		if ( q != NULL ) fprintf(stderr, "[%d]", p-table);\r
		while ( q != NULL )\r
		{\r
			len++;\r
			n++;\r
			fprintf(stderr, " %s", q->str);\r
			q = q->next;\r
			if ( q == NULL ) fprintf(stderr, "\n");\r
		}\r
		count[len]++;\r
		if ( *p != NULL ) hi = p-table;\r
	}\r
\r
	fprintf(stderr, "Storing %d recs used %d hash positions out of %d\n",\r
					n, size-count[0], size);\r
	fprintf(stderr, "%f %% utilization\n",\r
					((float)(size-count[0]))/((float)size));\r
	for (i=0; i<20; i++)\r
	{\r
		if ( count[i] != 0 )\r
		{\r
			avg += (((float)(i*count[i]))/((float)n)) * i;\r
			fprintf(stderr, "Bucket len %d == %d (%f %% of recs)\n",\r
							i, count[i], ((float)(i*count[i]))/((float)n));\r
		}\r
	}\r
	fprintf(stderr, "Avg bucket length %f\n", avg);\r
	fprintf(stderr, "Range of hash function: %d..%d\n", low, hi);\r
}\r
#endif\r
\r
/* Add a string to the string table and return a pointer to it.\r
 * Bump the pointer into the string table to next avail position.\r
 */\r
char *\r
#ifdef __USE_PROTOS\r
mystrdup( char *s )\r
#else\r
mystrdup( s )\r
char *s;\r
#endif\r
{\r
	char *start=strp;\r
	require(s!=NULL, "mystrdup: NULL string");\r
\r
	while ( *s != '\0' )\r
	{\r
		require( strp <= &(strings[strsize-2]),\r
				 "string table overflow\nIncrease StrTableSize in hash.h and recompile hash.c\n");\r
		*strp++ = *s++;\r
	}\r
	*strp++ = '\0';\r
\r
	return( start );\r
}\r