[project @ 1996-01-08 20:28:12 by partain]
[ghc.git] / ghc / compiler / yaccParser / id.c
1 /**********************************************************************
2 * *
3 * *
4 * Identifier Processing *
5 * *
6 * *
7 **********************************************************************/
8
9 #include <stdio.h>
10
11 #include "hspincl.h"
12 #include "constants.h"
13 #include "id.h"
14 #include "utils.h"
15
16 /* partain: special version for strings that may have NULs (etc) in them
17 */
18 long
19 get_hstring_len(hs)
20 hstring hs;
21 {
22 return(hs->len);
23 }
24
25 char *
26 get_hstring_bytes(hs)
27 hstring hs;
28 {
29 return(hs->bytes);
30 }
31
32 hstring
33 installHstring(length, s)
34 int length;
35 char *s;
36 {
37 char *p;
38 hstring str;
39 int i;
40
41 /* fprintf(stderr, "installHstring: %d, %s\n",length, s); */
42
43 if (length > 999999) { /* too long */
44 fprintf(stderr,"String length more than six digits\n");
45 exit(1);
46 } else if (length < 0) { /* too short */
47 fprintf(stderr,"String length < 0 !!\n");
48 abort();
49 }
50
51 /* alloc the struct and store the length */
52 str = (hstring) xmalloc(sizeof(Hstring));
53 str->len = length;
54
55 if (length == 0) {
56 str->bytes = NULL;
57
58 } else {
59 p = xmalloc(length);
60
61 /* now store the string */
62 for (i = 0; i < length; i++) {
63 p[i] = s[i];
64 }
65 str->bytes = p;
66 }
67 return str;
68 }
69
70
71 /**********************************************************************
72 * *
73 * *
74 * Hashed Identifiers *
75 * *
76 * *
77 **********************************************************************/
78
79
80 extern BOOLEAN hashIds; /* Whether to use hashed ids. */
81
82 unsigned hash_table_size = HASH_TABLE_SIZE;
83
84 static char **hashtab = NULL;
85
86 static unsigned max_hash_table_entries = 0;
87
88 void
89 hash_init()
90 {
91 if(!hashIds) {
92 /*NOTHING*/;
93
94 } else {
95
96 /* Create an initialised hash table */
97 hashtab = (char **) calloc( hash_table_size, sizeof(char *) );
98 if(hashtab == NULL)
99 {
100 fprintf(stderr,"Cannot allocate a hash table with %d entries -- insufficient memory\n",hash_table_size);
101 exit(1);
102 }
103 #ifdef HSP_DEBUG
104 fprintf(stderr,"hashtab = %x\n",hashtab);
105 #endif
106
107 /* Allow no more than 90% occupancy -- Divide first to avoid overflows with BIG tables! */
108 max_hash_table_entries = (hash_table_size / 10) * 9;
109 }
110 }
111
112 void
113 print_hash_table()
114 {
115 if(hashIds)
116 {
117 unsigned i;
118
119 printf("%u ",hash_table_size);
120
121 for(i=0; i < hash_table_size; ++i)
122 if(hashtab[i] != NULL)
123 printf("(%u,%s) ",i,hashtab[i]);
124 }
125 }
126
127
128 long int
129 hash_index(ident)
130 id ident;
131 {
132 return((char **) /* YURGH */ ident - hashtab);
133 }
134
135
136 /*
137 The hash function. Returns 0 for Null strings.
138 */
139
140 static unsigned hash_fn(ident)
141 char *ident;
142 {
143 unsigned len = (unsigned) strlen(ident);
144 unsigned res;
145
146 if(*ident == '\0')
147 return( 0 );
148
149 /* does not work well for hash tables with more than 35K elements */
150 res = (((unsigned)ident[0]*631)+((unsigned)ident[len/2-1]*217)+((unsigned)ident[len-1]*43)+len)
151 % hash_table_size;
152
153 #ifdef HSP_DEBUG
154 fprintf(stderr,"\"%s\" hashes to %d\n",ident,res);
155 #endif
156 return(res);
157 }
158
159
160 /*
161 Install a literal identifier, such as "+" in hsparser.
162 If we are not using hashing, just return the string.
163 */
164
165 id
166 install_literal(s)
167 char *s;
168 {
169 return( hashIds? installid(s): s);
170 }
171
172
173 char *
174 id_to_string(sp)
175 id sp;
176 {
177 return( hashIds? *(char **)sp: (char *)sp );
178 }
179
180 id
181 installid(s)
182 char *s;
183 {
184 unsigned hash, count;
185
186 if(!hashIds)
187 return(xstrdup(s));
188
189 for(hash = hash_fn(s),count=0; count<max_hash_table_entries; ++hash,++count)
190 {
191 if (hash >= hash_table_size) hash = 0;
192
193 if(hashtab[hash] == NULL)
194 {
195 hashtab[hash] = xstrdup(s);
196 #ifdef HSP_DEBUG
197 fprintf(stderr,"New Hash Entry %x\n",(char *)&hashtab[hash]);
198 #endif
199 if ( count >= 100 ) {
200 fprintf(stderr, "installid: %d collisions for %s\n", count, s);
201 }
202
203 return((char *)&hashtab[hash]);
204 }
205
206 if(strcmp(hashtab[hash],s) == 0)
207 {
208 #ifdef HSP_DEBUG
209 fprintf(stderr,"Old Hash Entry %x (%s)\n",(char *)&hashtab[hash],hashtab[hash]);
210 #endif
211 if ( count >= 100 ) {
212 fprintf(stderr, "installid: %d collisions for %s\n", count, s);
213 }
214
215 return((char *)&hashtab[hash]);
216 }
217 }
218 fprintf(stderr,"Hash Table Contains more than %d entries -- make larger?\n",max_hash_table_entries);
219 exit(1);
220 }
221
222
223 /**********************************************************************
224 * *
225 * *
226 * Memory Allocation *
227 * *
228 * *
229 **********************************************************************/
230
231 /* Malloc with error checking */
232
233 char *
234 xmalloc(length)
235 unsigned length;
236 {
237 char *stuff = malloc(length);
238
239 if (stuff == NULL) {
240 fprintf(stderr, "xmalloc failed on a request for %d bytes\n", length);
241 exit(1);
242 }
243 return (stuff);
244 }
245
246 char *
247 xrealloc(ptr, length)
248 char *ptr;
249 unsigned length;
250 {
251 char *stuff = realloc(ptr, length);
252
253 if (stuff == NULL) {
254 fprintf(stderr, "xrealloc failed on a request for %d bytes\n", length);
255 exit(1);
256 }
257 return (stuff);
258 }
259
260 /* Strdup with error checking */
261
262 char *
263 xstrdup(s)
264 char *s;
265 {
266 unsigned len = strlen(s);
267 return xstrndup(s, len);
268 }
269
270 /*
271 * Strdup for possibly unterminated strings (e.g. substrings of longer strings)
272 * with error checking. Handles NULs as well.
273 */
274
275 char *
276 xstrndup(s, len)
277 char *s;
278 unsigned len;
279 {
280 char *p = xmalloc(len + 1);
281
282 bcopy(s, p, len);
283 p[len] = '\0';
284
285 return (p);
286 }