More renames for Tool Packages

[mirror_edk2.git] / Tools / CodeTools / Source / Pccts / support / sym / sym.c

/*\r
 * Simple symbol table manager using coalesced chaining to resolve collisions\r
 *\r
 * Doubly-linked lists are used for fast removal of entries.\r
 *\r
 * 'sym.h' must have a definition for typedef "Sym".  Sym must include at\r
 * minimum the following fields:\r
 *\r
 *		...\r
 *		char *symbol;\r
 *		struct ... *next, *prev, **head, *scope;\r
 *		unsigned int hash;\r
 *		...\r
 *\r
 * 'template.h' can be used as a template to create a 'sym.h'.\r
 *\r
 * 'head' is &(table[hash(itself)]).\r
 * The hash table is not resizable at run-time.\r
 * The scope field is used to link all symbols of a current scope together.\r
 * Scope() sets the current scope (linked list) to add symbols to.\r
 * Any number of scopes can be handled.  The user passes the address of\r
 * a pointer to a symbol table\r
 * entry (INITIALIZED TO NULL first time).\r
 *\r
 * Available Functions:\r
 *\r
 *	zzs_init(s1,s2)	--	Create hash table with size s1, string table size s2.\r
 *	zzs_done()		--	Free hash and string table created with zzs_init().\r
 *	zzs_add(key,rec)--	Add 'rec' with key 'key' to the symbol table.\r
 *	zzs_newadd(key)	--	create entry; add using 'key' to the symbol table.\r
 *	zzs_get(key)	--	Return pointer to last record entered under 'key'\r
 *						Else return NULL\r
 *	zzs_del(p)		--	Unlink the entry associated with p.  This does\r
 *						NOT free 'p' and DOES NOT remove it from a scope\r
 *						list.  If it was a part of your intermediate code\r
 *						tree or another structure.  It will still be there.\r
 *			  			It is only removed from further consideration\r
 *						by the symbol table.\r
 *	zzs_keydel(s)	--	Unlink the entry associated with key s.\r
 *						Calls zzs_del(p) to unlink.\r
 *	zzs_scope(sc)	--	Specifies that everything added to the symbol\r
 *			   			table with zzs_add() is added to the list (scope)\r
 *						'sc'.  'sc' is of 'Sym **sc' type and must be\r
 *						initialized to NULL before trying to add anything\r
 *						to it (passing it to zzs_scope()).  Scopes can be\r
 *					    switched at any time and merely links a set of\r
 *						symbol table entries.  If a NULL pointer is\r
 *						passed, the current scope is returned.\r
 *	zzs_rmscope(sc)	--	Remove (zzs_del()) all elements of scope 'sc'\r
 *						from the symbol table.  The entries are NOT\r
 *						free()'d.  A pointer to the first\r
 *			   			element in the "scope" is returned.  The user\r
 *			   			can then manipulate the list as he/she chooses\r
 *			   			(such as freeing them all). NOTE that this\r
 *			   			function sets your scope pointer to NULL,\r
 *			   			but returns a pointer to the list for you to use.\r
 *	zzs_stat()		--	Print out the symbol table and some relevant stats.\r
 *	zzs_new(key)	--	Create a new record with calloc() of type Sym.\r
 *			   			Add 'key' to the string table and make the new\r
 *			   			records 'symbol' pointer point to it.\r
 *	zzs_strdup(s)	--	Add s to the string table and return a pointer\r
 *			   			to it.  Very fast allocation routine\r
 *						and does not require strlen() nor calloc().\r
 *\r
 * Example:\r
 *\r
 *	#include <stdio.h>\r
 *	#include "sym.h"\r
 *\r
 *	main()\r
 *	{\r
 *	    Sym *scope1=NULL, *scope2=NULL, *a, *p;\r
 *	\r
 *	    zzs_init(101, 100);\r
 *	\r
 *	    a = zzs_new("Apple");	zzs_add(a->symbol, a);	-- No scope\r
 *	    zzs_scope( &scope1 );	-- enter scope 1\r
 *	    a = zzs_new("Plum");	zzs_add(a->symbol, a);\r
 *	    zzs_scope( &scope2 );	-- enter scope 2\r
 *	    a = zzs_new("Truck");	zzs_add(a->symbol, a);\r
 *	\r
 *    	p = zzs_get("Plum");\r
 *    	if ( p == NULL ) fprintf(stderr, "Hmmm...Can't find 'Plum'\n");\r
 *	\r
 *    	p = zzs_rmscope(&scope1)\r
 *    	for (; p!=NULL; p=p->scope) {printf("Scope1:  %s\n", p->symbol);}\r
 *    	p = zzs_rmscope(&scope2)\r
 *    	for (; p!=NULL; p=p->scope) {printf("Scope2:  %s\n", p->symbol);}\r
 * }\r
 *\r
 * Terence Parr\r
 * Purdue University\r
 * February 1990\r
 *\r
 * CHANGES\r
 *\r
 *	Terence Parr\r
 *	May 1991\r
 *		Renamed functions to be consistent with ANTLR\r
 *		Made HASH macro\r
 *		Added zzs_keydel()\r
 *		Added zzs_newadd()\r
 *		Fixed up zzs_stat()\r
 *\r
 *	July 1991\r
 *		Made symbol table entry save its hash code for fast comparison\r
 *			during searching etc...\r
 */\r
\r
#include <stdio.h>\r
#if defined(__STDC__) || defined(__USE_PROTOS)\r
#include <string.h>\r
#include <stdlib.h>\r
#else\r
#include <malloc.h>\r
#endif\r
#include "sym.h"\r
\r
#define StrSame		0\r
\r
static Sym **CurScope = NULL;\r
static unsigned size = 0;\r
static Sym **table=NULL;\r
static char *strings;\r
static char *strp;\r
static int strsize = 0;\r
\r
#ifdef __USE_PROTOS\r
void zzs_init(int sz,int strs)\r
#else\r
void zzs_init(sz, strs)\r
int sz, strs;\r
#endif\r
{\r
	if ( sz <= 0 || strs <= 0 ) return;\r
	table = (Sym **) calloc(sz, sizeof(Sym *));\r
	if ( table == NULL )\r
	{\r
		fprintf(stderr, "Cannot allocate table of size %d\n", sz);\r
		exit(1);\r
	}\r
	strings = (char *) calloc(strs, sizeof(char));\r
	if ( strings == NULL )\r
	{\r
		fprintf(stderr, "Cannot allocate string table of size %d\n", strs);\r
		exit(1);\r
	}\r
	size = sz;\r
	strsize = strs;\r
	strp = strings;\r
}\r
\r
#ifdef __USE_PROTOS\r
void zzs_done(void)\r
#else\r
void zzs_done()\r
#endif\r
{\r
	if ( table != NULL ) free( table );\r
	if ( strings != NULL ) free( strings );\r
}\r
\r
#ifdef __USE_PROTOS\r
void zzs_add(char *key,Sym rec)\r
#else\r
void zzs_add(key, rec)\r
char *key;\r
register Sym *rec;\r
#endif\r
{\r
	register unsigned int h=0;\r
	register char *p=key;\r
	\r
	HASH(p, h);\r
	rec->hash = h;					/* save hash code for fast comp later */\r
	h %= size;\r
	\r
	if ( CurScope != NULL ) {rec->scope = *CurScope; *CurScope = rec;}\r
	rec->next = table[h];			/* Add to doubly-linked list */\r
	rec->prev = NULL;\r
	if ( rec->next != NULL ) (rec->next)->prev = rec;\r
	table[h] = rec;\r
	rec->head = &(table[h]);\r
}\r
\r
#ifdef __USE_PROTOS\r
Sym * zzs_get(char *key)\r
#else\r
Sym * zzs_get(key)\r
char *key;\r
#endif\r
{\r
	register unsigned int h=0;\r
	register char *p=key;\r
	register Sym *q;\r
	\r
	HASH(p, h);\r
	\r
	for (q = table[h%size]; q != NULL; q = q->next)\r
	{\r
		if ( q->hash == h )		/* do we even have a chance of matching? */\r
			if ( strcmp(key, q->symbol) == StrSame ) return( q );\r
	}\r
	return( NULL );\r
}\r
\r
/*\r
 * Unlink p from the symbol table.  Hopefully, it's actually in the\r
 * symbol table.\r
 *\r
 * If p is not part of a bucket chain of the symbol table, bad things\r
 * will happen.\r
 *\r
 * Will do nothing if all list pointers are NULL\r
 */\r
#ifdef __USE_PROTOS\r
void zzs_del(Sym *p)\r
#else\r
void zzs_del(p)\r
register Sym *p;\r
#endif\r
{\r
	if ( p == NULL ) {fprintf(stderr, "zzs_del(NULL)\n"); exit(1);}\r
	if ( p->prev == NULL )	/* Head of list */\r
	{\r
		register Sym **t = p->head;\r
		\r
		if ( t == NULL ) return;	/* not part of symbol table */\r
		(*t) = p->next;\r
		if ( (*t) != NULL ) (*t)->prev = NULL;\r
	}\r
	else\r
	{\r
		(p->prev)->next = p->next;\r
		if ( p->next != NULL ) (p->next)->prev = p->prev;\r
	}\r
	p->next = p->prev = NULL;	/* not part of symbol table anymore */\r
	p->head = NULL;\r
}\r
\r
#ifdef __USE_PROTOS\r
void zzs_keydel(char *key)\r
#else\r
void zzs_keydel(key)\r
char *key;\r
#endif\r
{\r
	Sym *p = zzs_get(key);\r
\r
	if ( p != NULL ) zzs_del( p );\r
}\r
\r
/* S c o p e  S t u f f */\r
\r
/* Set current scope to 'scope'; return current scope if 'scope' == NULL */\r
\r
#ifdef __USE_PROTOS\r
Sym ** zzs_scope(Sym **scope)\r
#else\r
Sym ** zzs_scope(scope)\r
Sym **scope;\r
#endif\r
{\r
	if ( scope == NULL ) return( CurScope );\r
	CurScope = scope;\r
	return( scope );\r
}\r
\r
/* Remove a scope described by 'scope'.  Return pointer to 1st element in scope */\r
\r
#ifdef __USE_PROTOS\r
Sym * zzs_rmscope(Sym **scope)\r
#else\r
Sym * zzs_rmscope(scope)\r
register Sym **scope;\r
#endif\r
{\r
	register Sym *p;\r
	Sym *start;\r
\r
	if ( scope == NULL ) return(NULL);\r
	start = p = *scope;\r
	for (; p != NULL; p=p->scope) { zzs_del( p ); }\r
	*scope = NULL;\r
	return( start );\r
}\r
\r
#ifdef __USE_PROTOS\r
void zzs_stat(void)\r
#else\r
void zzs_stat()\r
#endif\r
{\r
	static unsigned short count[20];\r
	unsigned int i,n=0,low=0, hi=0;\r
	register Sym **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
		register Sym *q = *p;\r
		unsigned int len;\r
		\r
		if ( q != NULL && low==0 ) low = p-table;\r
		len = 0;\r
		if ( q != NULL ) printf("[%d]", p-table);\r
		while ( q != NULL )\r
		{\r
			len++;\r
			n++;\r
			printf(" %s", q->symbol);\r
			q = q->next;\r
			if ( q == NULL ) printf("\n");\r
		}\r
		if ( len>=20 ) printf("zzs_stat: count table too small\n");\r
		else count[len]++;\r
		if ( *p != NULL ) hi = p-table;\r
	}\r
\r
	printf("Storing %d recs used %d hash positions out of %d\n",\r
			n, size-count[0], size);\r
	printf("%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
			printf("Buckets of len %d == %d (%f %% of recs)\n",\r
					i, count[i], 100.0*((float)(i*count[i]))/((float)n));\r
		}\r
	}\r
	printf("Avg bucket length %f\n", avg);\r
	printf("Range of hash function: %d..%d\n", low, hi);\r
}\r
\r
/*\r
 * Given a string, this function allocates and returns a pointer to a\r
 * symbol table record whose "symbol" pointer is reset to a position\r
 * in the string table.\r
 */\r
\r
#ifdef __USE_PROTOS\r
Sym * zzs_new(char *text)\r
#else\r
Sym * zzs_new(text)\r
char *text;\r
#endif\r
{\r
	Sym *p;\r
	\r
	if ( (p = (Sym *) calloc(1,sizeof(Sym))) == 0 )\r
	{\r
		fprintf(stderr,"Out of memory\n");\r
		exit(1);\r
	}\r
	p->symbol = zzs_strdup(text);\r
	\r
	return p;\r
}\r
\r
/* create a new symbol table entry and add it to the symbol table */\r
\r
#ifdef __USE_PROTOS\r
Sym * zzs_newadd(char *text)\r
#else\r
Sym * zzs_newadd(text)\r
char *text;\r
#endif\r
{\r
	Sym *p = zzs_new(text);\r
	if ( p != NULL ) zzs_add(text, p);\r
	return p;\r
}\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
\r
#ifdef __USE_PROTOS\r
char * zzs_strdup(char *s)\r
#else\r
char * zzs_strdup(s)\r
register char *s;\r
#endif\r
{\r
	register char *start=strp;\r
\r
	while ( *s != '\0' )\r
	{\r
		if ( strp >= &(strings[strsize-2]) )\r
		{\r
			fprintf(stderr, "sym: string table overflow (%d chars)\n", strsize);\r
			exit(-1);\r
		}\r
		*strp++ = *s++;\r
	}\r
	*strp++ = '\0';\r
\r
	return( start );\r
}\r