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