]>
Commit | Line | Data |
---|---|---|
878ddf1f | 1 | /*\r |
2 | * Simple symbol table manager using coalesced chaining to resolve collisions\r | |
3 | *\r | |
4 | * Doubly-linked lists are used for fast removal of entries.\r | |
5 | *\r | |
6 | * 'sym.h' must have a definition for typedef "Sym". Sym must include at\r | |
7 | * minimum the following fields:\r | |
8 | *\r | |
9 | * ...\r | |
10 | * char *symbol;\r | |
11 | * struct ... *next, *prev, **head, *scope;\r | |
12 | * unsigned int hash;\r | |
13 | * ...\r | |
14 | *\r | |
15 | * 'template.h' can be used as a template to create a 'sym.h'.\r | |
16 | *\r | |
17 | * 'head' is &(table[hash(itself)]).\r | |
18 | * The hash table is not resizable at run-time.\r | |
19 | * The scope field is used to link all symbols of a current scope together.\r | |
20 | * Scope() sets the current scope (linked list) to add symbols to.\r | |
21 | * Any number of scopes can be handled. The user passes the address of\r | |
22 | * a pointer to a symbol table\r | |
23 | * entry (INITIALIZED TO NULL first time).\r | |
24 | *\r | |
25 | * Available Functions:\r | |
26 | *\r | |
27 | * zzs_init(s1,s2) -- Create hash table with size s1, string table size s2.\r | |
28 | * zzs_done() -- Free hash and string table created with zzs_init().\r | |
29 | * zzs_add(key,rec)-- Add 'rec' with key 'key' to the symbol table.\r | |
30 | * zzs_newadd(key) -- create entry; add using 'key' to the symbol table.\r | |
31 | * zzs_get(key) -- Return pointer to last record entered under 'key'\r | |
32 | * Else return NULL\r | |
33 | * zzs_del(p) -- Unlink the entry associated with p. This does\r | |
34 | * NOT free 'p' and DOES NOT remove it from a scope\r | |
35 | * list. If it was a part of your intermediate code\r | |
36 | * tree or another structure. It will still be there.\r | |
37 | * It is only removed from further consideration\r | |
38 | * by the symbol table.\r | |
39 | * zzs_keydel(s) -- Unlink the entry associated with key s.\r | |
40 | * Calls zzs_del(p) to unlink.\r | |
41 | * zzs_scope(sc) -- Specifies that everything added to the symbol\r | |
42 | * table with zzs_add() is added to the list (scope)\r | |
43 | * 'sc'. 'sc' is of 'Sym **sc' type and must be\r | |
44 | * initialized to NULL before trying to add anything\r | |
45 | * to it (passing it to zzs_scope()). Scopes can be\r | |
46 | * switched at any time and merely links a set of\r | |
47 | * symbol table entries. If a NULL pointer is\r | |
48 | * passed, the current scope is returned.\r | |
49 | * zzs_rmscope(sc) -- Remove (zzs_del()) all elements of scope 'sc'\r | |
50 | * from the symbol table. The entries are NOT\r | |
51 | * free()'d. A pointer to the first\r | |
52 | * element in the "scope" is returned. The user\r | |
53 | * can then manipulate the list as he/she chooses\r | |
54 | * (such as freeing them all). NOTE that this\r | |
55 | * function sets your scope pointer to NULL,\r | |
56 | * but returns a pointer to the list for you to use.\r | |
57 | * zzs_stat() -- Print out the symbol table and some relevant stats.\r | |
58 | * zzs_new(key) -- Create a new record with calloc() of type Sym.\r | |
59 | * Add 'key' to the string table and make the new\r | |
60 | * records 'symbol' pointer point to it.\r | |
61 | * zzs_strdup(s) -- Add s to the string table and return a pointer\r | |
62 | * to it. Very fast allocation routine\r | |
63 | * and does not require strlen() nor calloc().\r | |
64 | *\r | |
65 | * Example:\r | |
66 | *\r | |
67 | * #include <stdio.h>\r | |
68 | * #include "sym.h"\r | |
69 | *\r | |
70 | * main()\r | |
71 | * {\r | |
72 | * Sym *scope1=NULL, *scope2=NULL, *a, *p;\r | |
73 | * \r | |
74 | * zzs_init(101, 100);\r | |
75 | * \r | |
76 | * a = zzs_new("Apple"); zzs_add(a->symbol, a); -- No scope\r | |
77 | * zzs_scope( &scope1 ); -- enter scope 1\r | |
78 | * a = zzs_new("Plum"); zzs_add(a->symbol, a);\r | |
79 | * zzs_scope( &scope2 ); -- enter scope 2\r | |
80 | * a = zzs_new("Truck"); zzs_add(a->symbol, a);\r | |
81 | * \r | |
82 | * p = zzs_get("Plum");\r | |
83 | * if ( p == NULL ) fprintf(stderr, "Hmmm...Can't find 'Plum'\n");\r | |
84 | * \r | |
85 | * p = zzs_rmscope(&scope1)\r | |
86 | * for (; p!=NULL; p=p->scope) {printf("Scope1: %s\n", p->symbol);}\r | |
87 | * p = zzs_rmscope(&scope2)\r | |
88 | * for (; p!=NULL; p=p->scope) {printf("Scope2: %s\n", p->symbol);}\r | |
89 | * }\r | |
90 | *\r | |
91 | * Terence Parr\r | |
92 | * Purdue University\r | |
93 | * February 1990\r | |
94 | *\r | |
95 | * CHANGES\r | |
96 | *\r | |
97 | * Terence Parr\r | |
98 | * May 1991\r | |
99 | * Renamed functions to be consistent with ANTLR\r | |
100 | * Made HASH macro\r | |
101 | * Added zzs_keydel()\r | |
102 | * Added zzs_newadd()\r | |
103 | * Fixed up zzs_stat()\r | |
104 | *\r | |
105 | * July 1991\r | |
106 | * Made symbol table entry save its hash code for fast comparison\r | |
107 | * during searching etc...\r | |
108 | */\r | |
109 | \r | |
110 | #include <stdio.h>\r | |
111 | #if defined(__STDC__) || defined(__USE_PROTOS)\r | |
112 | #include <string.h>\r | |
113 | #include <stdlib.h>\r | |
114 | #else\r | |
115 | #include <malloc.h>\r | |
116 | #endif\r | |
117 | #include "sym.h"\r | |
118 | \r | |
119 | #define StrSame 0\r | |
120 | \r | |
121 | static Sym **CurScope = NULL;\r | |
122 | static unsigned size = 0;\r | |
123 | static Sym **table=NULL;\r | |
124 | static char *strings;\r | |
125 | static char *strp;\r | |
126 | static int strsize = 0;\r | |
127 | \r | |
128 | #ifdef __USE_PROTOS\r | |
129 | void zzs_init(int sz,int strs)\r | |
130 | #else\r | |
131 | void zzs_init(sz, strs)\r | |
132 | int sz, strs;\r | |
133 | #endif\r | |
134 | {\r | |
135 | if ( sz <= 0 || strs <= 0 ) return;\r | |
136 | table = (Sym **) calloc(sz, sizeof(Sym *));\r | |
137 | if ( table == NULL )\r | |
138 | {\r | |
139 | fprintf(stderr, "Cannot allocate table of size %d\n", sz);\r | |
140 | exit(1);\r | |
141 | }\r | |
142 | strings = (char *) calloc(strs, sizeof(char));\r | |
143 | if ( strings == NULL )\r | |
144 | {\r | |
145 | fprintf(stderr, "Cannot allocate string table of size %d\n", strs);\r | |
146 | exit(1);\r | |
147 | }\r | |
148 | size = sz;\r | |
149 | strsize = strs;\r | |
150 | strp = strings;\r | |
151 | }\r | |
152 | \r | |
153 | #ifdef __USE_PROTOS\r | |
154 | void zzs_done(void)\r | |
155 | #else\r | |
156 | void zzs_done()\r | |
157 | #endif\r | |
158 | {\r | |
159 | if ( table != NULL ) free( table );\r | |
160 | if ( strings != NULL ) free( strings );\r | |
161 | }\r | |
162 | \r | |
163 | #ifdef __USE_PROTOS\r | |
164 | void zzs_add(char *key,Sym rec)\r | |
165 | #else\r | |
166 | void zzs_add(key, rec)\r | |
167 | char *key;\r | |
168 | register Sym *rec;\r | |
169 | #endif\r | |
170 | {\r | |
171 | register unsigned int h=0;\r | |
172 | register char *p=key;\r | |
173 | \r | |
174 | HASH(p, h);\r | |
175 | rec->hash = h; /* save hash code for fast comp later */\r | |
176 | h %= size;\r | |
177 | \r | |
178 | if ( CurScope != NULL ) {rec->scope = *CurScope; *CurScope = rec;}\r | |
179 | rec->next = table[h]; /* Add to doubly-linked list */\r | |
180 | rec->prev = NULL;\r | |
181 | if ( rec->next != NULL ) (rec->next)->prev = rec;\r | |
182 | table[h] = rec;\r | |
183 | rec->head = &(table[h]);\r | |
184 | }\r | |
185 | \r | |
186 | #ifdef __USE_PROTOS\r | |
187 | Sym * zzs_get(char *key)\r | |
188 | #else\r | |
189 | Sym * zzs_get(key)\r | |
190 | char *key;\r | |
191 | #endif\r | |
192 | {\r | |
193 | register unsigned int h=0;\r | |
194 | register char *p=key;\r | |
195 | register Sym *q;\r | |
196 | \r | |
197 | HASH(p, h);\r | |
198 | \r | |
199 | for (q = table[h%size]; q != NULL; q = q->next)\r | |
200 | {\r | |
201 | if ( q->hash == h ) /* do we even have a chance of matching? */\r | |
202 | if ( strcmp(key, q->symbol) == StrSame ) return( q );\r | |
203 | }\r | |
204 | return( NULL );\r | |
205 | }\r | |
206 | \r | |
207 | /*\r | |
208 | * Unlink p from the symbol table. Hopefully, it's actually in the\r | |
209 | * symbol table.\r | |
210 | *\r | |
211 | * If p is not part of a bucket chain of the symbol table, bad things\r | |
212 | * will happen.\r | |
213 | *\r | |
214 | * Will do nothing if all list pointers are NULL\r | |
215 | */\r | |
216 | #ifdef __USE_PROTOS\r | |
217 | void zzs_del(Sym *p)\r | |
218 | #else\r | |
219 | void zzs_del(p)\r | |
220 | register Sym *p;\r | |
221 | #endif\r | |
222 | {\r | |
223 | if ( p == NULL ) {fprintf(stderr, "zzs_del(NULL)\n"); exit(1);}\r | |
224 | if ( p->prev == NULL ) /* Head of list */\r | |
225 | {\r | |
226 | register Sym **t = p->head;\r | |
227 | \r | |
228 | if ( t == NULL ) return; /* not part of symbol table */\r | |
229 | (*t) = p->next;\r | |
230 | if ( (*t) != NULL ) (*t)->prev = NULL;\r | |
231 | }\r | |
232 | else\r | |
233 | {\r | |
234 | (p->prev)->next = p->next;\r | |
235 | if ( p->next != NULL ) (p->next)->prev = p->prev;\r | |
236 | }\r | |
237 | p->next = p->prev = NULL; /* not part of symbol table anymore */\r | |
238 | p->head = NULL;\r | |
239 | }\r | |
240 | \r | |
241 | #ifdef __USE_PROTOS\r | |
242 | void zzs_keydel(char *key)\r | |
243 | #else\r | |
244 | void zzs_keydel(key)\r | |
245 | char *key;\r | |
246 | #endif\r | |
247 | {\r | |
248 | Sym *p = zzs_get(key);\r | |
249 | \r | |
250 | if ( p != NULL ) zzs_del( p );\r | |
251 | }\r | |
252 | \r | |
253 | /* S c o p e S t u f f */\r | |
254 | \r | |
255 | /* Set current scope to 'scope'; return current scope if 'scope' == NULL */\r | |
256 | \r | |
257 | #ifdef __USE_PROTOS\r | |
258 | Sym ** zzs_scope(Sym **scope)\r | |
259 | #else\r | |
260 | Sym ** zzs_scope(scope)\r | |
261 | Sym **scope;\r | |
262 | #endif\r | |
263 | {\r | |
264 | if ( scope == NULL ) return( CurScope );\r | |
265 | CurScope = scope;\r | |
266 | return( scope );\r | |
267 | }\r | |
268 | \r | |
269 | /* Remove a scope described by 'scope'. Return pointer to 1st element in scope */\r | |
270 | \r | |
271 | #ifdef __USE_PROTOS\r | |
272 | Sym * zzs_rmscope(Sym **scope)\r | |
273 | #else\r | |
274 | Sym * zzs_rmscope(scope)\r | |
275 | register Sym **scope;\r | |
276 | #endif\r | |
277 | {\r | |
278 | register Sym *p;\r | |
279 | Sym *start;\r | |
280 | \r | |
281 | if ( scope == NULL ) return(NULL);\r | |
282 | start = p = *scope;\r | |
283 | for (; p != NULL; p=p->scope) { zzs_del( p ); }\r | |
284 | *scope = NULL;\r | |
285 | return( start );\r | |
286 | }\r | |
287 | \r | |
288 | #ifdef __USE_PROTOS\r | |
289 | void zzs_stat(void)\r | |
290 | #else\r | |
291 | void zzs_stat()\r | |
292 | #endif\r | |
293 | {\r | |
294 | static unsigned short count[20];\r | |
295 | unsigned int i,n=0,low=0, hi=0;\r | |
296 | register Sym **p;\r | |
297 | float avg=0.0;\r | |
298 | \r | |
299 | for (i=0; i<20; i++) count[i] = 0;\r | |
300 | for (p=table; p<&(table[size]); p++)\r | |
301 | {\r | |
302 | register Sym *q = *p;\r | |
303 | unsigned int len;\r | |
304 | \r | |
305 | if ( q != NULL && low==0 ) low = p-table;\r | |
306 | len = 0;\r | |
307 | if ( q != NULL ) printf("[%d]", p-table);\r | |
308 | while ( q != NULL )\r | |
309 | {\r | |
310 | len++;\r | |
311 | n++;\r | |
312 | printf(" %s", q->symbol);\r | |
313 | q = q->next;\r | |
314 | if ( q == NULL ) printf("\n");\r | |
315 | }\r | |
316 | if ( len>=20 ) printf("zzs_stat: count table too small\n");\r | |
317 | else count[len]++;\r | |
318 | if ( *p != NULL ) hi = p-table;\r | |
319 | }\r | |
320 | \r | |
321 | printf("Storing %d recs used %d hash positions out of %d\n",\r | |
322 | n, size-count[0], size);\r | |
323 | printf("%f %% utilization\n",\r | |
324 | ((float)(size-count[0]))/((float)size));\r | |
325 | for (i=0; i<20; i++)\r | |
326 | {\r | |
327 | if ( count[i] != 0 )\r | |
328 | {\r | |
329 | avg += (((float)(i*count[i]))/((float)n)) * i;\r | |
330 | printf("Buckets of len %d == %d (%f %% of recs)\n",\r | |
331 | i, count[i], 100.0*((float)(i*count[i]))/((float)n));\r | |
332 | }\r | |
333 | }\r | |
334 | printf("Avg bucket length %f\n", avg);\r | |
335 | printf("Range of hash function: %d..%d\n", low, hi);\r | |
336 | }\r | |
337 | \r | |
338 | /*\r | |
339 | * Given a string, this function allocates and returns a pointer to a\r | |
340 | * symbol table record whose "symbol" pointer is reset to a position\r | |
341 | * in the string table.\r | |
342 | */\r | |
343 | \r | |
344 | #ifdef __USE_PROTOS\r | |
345 | Sym * zzs_new(char *text)\r | |
346 | #else\r | |
347 | Sym * zzs_new(text)\r | |
348 | char *text;\r | |
349 | #endif\r | |
350 | {\r | |
351 | Sym *p;\r | |
352 | \r | |
353 | if ( (p = (Sym *) calloc(1,sizeof(Sym))) == 0 )\r | |
354 | {\r | |
355 | fprintf(stderr,"Out of memory\n");\r | |
356 | exit(1);\r | |
357 | }\r | |
358 | p->symbol = zzs_strdup(text);\r | |
359 | \r | |
360 | return p;\r | |
361 | }\r | |
362 | \r | |
363 | /* create a new symbol table entry and add it to the symbol table */\r | |
364 | \r | |
365 | #ifdef __USE_PROTOS\r | |
366 | Sym * zzs_newadd(char *text)\r | |
367 | #else\r | |
368 | Sym * zzs_newadd(text)\r | |
369 | char *text;\r | |
370 | #endif\r | |
371 | {\r | |
372 | Sym *p = zzs_new(text);\r | |
373 | if ( p != NULL ) zzs_add(text, p);\r | |
374 | return p;\r | |
375 | }\r | |
376 | \r | |
377 | /* Add a string to the string table and return a pointer to it.\r | |
378 | * Bump the pointer into the string table to next avail position.\r | |
379 | */\r | |
380 | \r | |
381 | #ifdef __USE_PROTOS\r | |
382 | char * zzs_strdup(char *s)\r | |
383 | #else\r | |
384 | char * zzs_strdup(s)\r | |
385 | register char *s;\r | |
386 | #endif\r | |
387 | {\r | |
388 | register char *start=strp;\r | |
389 | \r | |
390 | while ( *s != '\0' )\r | |
391 | {\r | |
392 | if ( strp >= &(strings[strsize-2]) )\r | |
393 | {\r | |
394 | fprintf(stderr, "sym: string table overflow (%d chars)\n", strsize);\r | |
395 | exit(-1);\r | |
396 | }\r | |
397 | *strp++ = *s++;\r | |
398 | }\r | |
399 | *strp++ = '\0';\r | |
400 | \r | |
401 | return( start );\r | |
402 | }\r |