• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * hash.c
3  *
4  * Manage hash tables.
5  *
6  * The following functions are visible:
7  *
8  *		char	*mystrdup(char *);		Make space and copy string
9  *		Entry 	**newHashTable();		Create and return initialized hash table
10  *		Entry	*hash_add(Entry **, char *, Entry *)
11  *		Entry	*hash_get(Entry **, char *)
12  *
13  * SOFTWARE RIGHTS
14  *
15  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
16  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
17  * company may do whatever they wish with source code distributed with
18  * PCCTS or the code generated by PCCTS, including the incorporation of
19  * PCCTS, or its output, into commerical software.
20  *
21  * We encourage users to develop software with PCCTS.  However, we do ask
22  * that credit is given to us for developing PCCTS.  By "credit",
23  * we mean that if you incorporate our source code into one of your
24  * programs (commercial product, research project, or otherwise) that you
25  * acknowledge this fact somewhere in the documentation, research report,
26  * etc...  If you like PCCTS and have developed a nice tool with the
27  * output, please mention that you developed it using PCCTS.  In
28  * addition, we ask that this header remain intact in our source code.
29  * As long as these guidelines are kept, we expect to continue enhancing
30  * this system and expect to make other tools available as they are
31  * completed.
32  *
33  * ANTLR 1.33
34  * Terence Parr
35  * Parr Research Corporation
36  * with Purdue University and AHPCRC, University of Minnesota
37  * 1989-2001
38  */
39 
40 #include <stdio.h>
41 #include "pcctscfg.h"
42 #include "hash.h"
43 
44 #ifdef __USE_PROTOS
45 #include <stdlib.h>
46 #else
47 #ifdef VAXC
48 #include <stdlib.h>
49 #else
50 #include <malloc.h>
51 #endif
52 #endif
53 #include <string.h>
54 
55 #define StrSame		0
56 
57 #define fatal(err)															\
58 			{fprintf(stderr, "%s(%d):", __FILE__, __LINE__);				\
59 			fprintf(stderr, " %s\n", err); exit(PCCTS_EXIT_FAILURE);}
60 #define require(expr, err) {if ( !(expr) ) fatal(err);}
61 
62 static unsigned size = HashTableSize;
63 static char *strings = NULL;
64 static char *strp;
65 static unsigned strsize = StrTableSize;
66 
67 /* create the hash table and string table for terminals (string table only once) */
68 Entry **
69 #ifdef __USE_PROTOS
newHashTable(void)70 newHashTable( void )
71 #else
72 newHashTable( )
73 #endif
74 {
75 	Entry **table;
76 
77 	table = (Entry **) calloc(size, sizeof(Entry *));
78 	require( table != NULL, "cannot allocate hash table");
79 	if ( strings == NULL )
80 	{
81 		strings = (char *) calloc(strsize, sizeof(char));
82 		require( strings != NULL, "cannot allocate string table");
83 		strp = strings;
84 	}
85 	return table;
86 }
87 
88 void
89 #ifdef __USE_PROTOS
killHashTable(Entry ** table)90 killHashTable( Entry **table )
91 #else
92 killHashTable( table )
93 Entry **table;
94 #endif
95 {
96 	/* for now, just free table, forget entries */
97 	free( (char *) table );     /* MR10 cast */
98 }
99 
100 /* Given a table, add 'rec' with key 'key' (add to front of list). return ptr to entry */
101 Entry *
102 #ifdef __USE_PROTOS
hash_add(Entry ** table,char * key,Entry * rec)103 hash_add( Entry **table, char *key, Entry *rec )
104 #else
105 hash_add( table, key, rec )
106 Entry **table;
107 char *key;
108 Entry *rec;
109 #endif
110 {
111 	unsigned h=0;
112 	char *p=key;
113 	require(table!=NULL && key!=NULL && rec!=NULL, "add: invalid addition");
114 
115 	Hash(p,h,size);
116 	rec->next = table[h];			/* Add to singly-linked list */
117 	table[h] = rec;
118 	return rec;
119 }
120 
121 /* Return ptr to 1st entry found in table under key (return NULL if none found) */
122 Entry *
123 #ifdef __USE_PROTOS
hash_get(Entry ** table,char * key)124 hash_get( Entry **table, char *key )
125 #else
126 hash_get( table, key )
127 Entry **table;
128 char *key;
129 #endif
130 {
131 	unsigned h=0;
132 	char *p=key;
133 	Entry *q;
134 /*	require(table!=NULL && key!=NULL, "get: invalid table and/or key");*/
135 	if ( !(table!=NULL && key!=NULL) ) *((char *) 34) = 3;
136 
137 	Hash(p,h,size);
138 	for (q = table[h]; q != NULL; q = q->next)
139 	{
140 		if ( strcmp(key, q->str) == StrSame ) return( q );
141 	}
142 	return( NULL );
143 }
144 
145 #ifdef DEBUG_HASH
146 void
147 #ifdef __USE_PROTOS
hashStat(Entry ** table)148 hashStat( Entry **table )
149 #else
150 hashStat( table )
151 Entry **table;
152 #endif
153 {
154 	static unsigned short count[20];
155 	int i,n=0,low=0, hi=0;
156 	Entry **p;
157 	float avg=0.0;
158 
159 	for (i=0; i<20; i++) count[i] = 0;
160 	for (p=table; p<&(table[size]); p++)
161 	{
162 		Entry *q = *p;
163 		int len;
164 
165 		if ( q != NULL && low==0 ) low = p-table;
166 		len = 0;
167 		if ( q != NULL ) fprintf(stderr, "[%d]", p-table);
168 		while ( q != NULL )
169 		{
170 			len++;
171 			n++;
172 			fprintf(stderr, " %s", q->str);
173 			q = q->next;
174 			if ( q == NULL ) fprintf(stderr, "\n");
175 		}
176 		count[len]++;
177 		if ( *p != NULL ) hi = p-table;
178 	}
179 
180 	fprintf(stderr, "Storing %d recs used %d hash positions out of %d\n",
181 					n, size-count[0], size);
182 	fprintf(stderr, "%f %% utilization\n",
183 					((float)(size-count[0]))/((float)size));
184 	for (i=0; i<20; i++)
185 	{
186 		if ( count[i] != 0 )
187 		{
188 			avg += (((float)(i*count[i]))/((float)n)) * i;
189 			fprintf(stderr, "Bucket len %d == %d (%f %% of recs)\n",
190 							i, count[i], ((float)(i*count[i]))/((float)n));
191 		}
192 	}
193 	fprintf(stderr, "Avg bucket length %f\n", avg);
194 	fprintf(stderr, "Range of hash function: %d..%d\n", low, hi);
195 }
196 #endif
197 
198 /* Add a string to the string table and return a pointer to it.
199  * Bump the pointer into the string table to next avail position.
200  */
201 char *
202 #ifdef __USE_PROTOS
mystrdup(char * s)203 mystrdup( char *s )
204 #else
205 mystrdup( s )
206 char *s;
207 #endif
208 {
209 	char *start=strp;
210 	require(s!=NULL, "mystrdup: NULL string");
211 
212 	while ( *s != '\0' )
213 	{
214 		require( strp <= &(strings[strsize-2]),
215 				 "string table overflow\nIncrease StrTableSize in hash.h and recompile hash.c\n");
216 		*strp++ = *s++;
217 	}
218 	*strp++ = '\0';
219 
220 	return( start );
221 }
222