File indexing completed on 2025-02-23 04:46:18
0001 /* 0002 * Simple symbol table manager using coalesced chaining to resolve collisions 0003 * 0004 * Doubly-linked lists are used for fast removal of entries. 0005 * 0006 * 'sym.h' must have a definition for typedef "Sym". Sym must include at 0007 * minimum the following fields: 0008 * 0009 * ... 0010 * char *symbol; 0011 * struct ... *next, *prev, **head, *scope; 0012 * unsigned int hash; 0013 * ... 0014 * 0015 * 'template.h' can be used as a template to create a 'sym.h'. 0016 * 0017 * 'head' is &(table[hash(itself)]). 0018 * The hash table is not resizable at run-time. 0019 * The scope field is used to link all symbols of a current scope together. 0020 * Scope() sets the current scope (linked list) to add symbols to. 0021 * Any number of scopes can be handled. The user passes the address of 0022 * a pointer to a symbol table 0023 * entry (INITIALIZED TO NULL first time). 0024 * 0025 * Available Functions: 0026 * 0027 * zzs_init(s1,s2) -- Create hash table with size s1, string table size s2. 0028 * zzs_done() -- Free hash and string table created with zzs_init(). 0029 * zzs_add(key,rec)-- Add 'rec' with key 'key' to the symbol table. 0030 * zzs_newadd(key) -- create entry; add using 'key' to the symbol table. 0031 * zzs_get(key) -- Return pointer to last record entered under 'key' 0032 * Else return NULL 0033 * zzs_del(p) -- Unlink the entry associated with p. This does 0034 * NOT free 'p' and DOES NOT remove it from a scope 0035 * list. If it was a part of your intermediate code 0036 * tree or another structure. It will still be there. 0037 * It is only removed from further consideration 0038 * by the symbol table. 0039 * zzs_keydel(s) -- Unlink the entry associated with key s. 0040 * Calls zzs_del(p) to unlink. 0041 * zzs_scope(sc) -- Specifies that everything added to the symbol 0042 * table with zzs_add() is added to the list (scope) 0043 * 'sc'. 'sc' is of 'Sym **sc' type and must be 0044 * initialized to NULL before trying to add anything 0045 * to it (passing it to zzs_scope()). Scopes can be 0046 * switched at any time and merely links a set of 0047 * symbol table entries. If a NULL pointer is 0048 * passed, the current scope is returned. 0049 * zzs_rmscope(sc) -- Remove (zzs_del()) all elements of scope 'sc' 0050 * from the symbol table. The entries are NOT 0051 * free()'d. A pointer to the first 0052 * element in the "scope" is returned. The user 0053 * can then manipulate the list as he/she chooses 0054 * (such as freeing them all). NOTE that this 0055 * function sets your scope pointer to NULL, 0056 * but returns a pointer to the list for you to use. 0057 * zzs_stat() -- Print out the symbol table and some relevant stats. 0058 * zzs_new(key) -- Create a new record with calloc() of type Sym. 0059 * Add 'key' to the string table and make the new 0060 * records 'symbol' pointer point to it. 0061 * zzs_strdup(s) -- Add s to the string table and return a pointer 0062 * to it. Very fast allocation routine 0063 * and does not require strlen() nor calloc(). 0064 * 0065 * Example: 0066 * 0067 * #include <stdio.h> 0068 * #include "sym.h" 0069 * 0070 * main() 0071 * { 0072 * Sym *scope1=NULL, *scope2=NULL, *a, *p; 0073 * 0074 * zzs_init(101, 100); 0075 * 0076 * a = zzs_new("Apple"); zzs_add(a->symbol, a); -- No scope 0077 * zzs_scope( &scope1 ); -- enter scope 1 0078 * a = zzs_new("Plum"); zzs_add(a->symbol, a); 0079 * zzs_scope( &scope2 ); -- enter scope 2 0080 * a = zzs_new("Truck"); zzs_add(a->symbol, a); 0081 * 0082 * p = zzs_get("Plum"); 0083 * if ( p == NULL ) fprintf(stderr, "Hmmm...Can't find 'Plum'\n"); 0084 * 0085 * p = zzs_rmscope(&scope1) 0086 * for (; p!=NULL; p=p->scope) {printf("Scope1: %s\n", p->symbol);} 0087 * p = zzs_rmscope(&scope2) 0088 * for (; p!=NULL; p=p->scope) {printf("Scope2: %s\n", p->symbol);} 0089 * } 0090 * 0091 * Terence Parr 0092 * Purdue University 0093 * February 1990 0094 * 0095 * CHANGES 0096 * 0097 * Terence Parr 0098 * May 1991 0099 * Renamed functions to be consistent with ANTLR 0100 * Made HASH macro 0101 * Added zzs_keydel() 0102 * Added zzs_newadd() 0103 * Fixed up zzs_stat() 0104 * 0105 * July 1991 0106 * Made symbol table entry save its hash code for fast comparison 0107 * during searching etc... 0108 */ 0109 0110 /*#include "bt_config.h"*/ 0111 #include <stdio.h> 0112 #include <string.h> 0113 #include <stdlib.h> 0114 #ifdef MEMCHK 0115 #include "trax.h" 0116 #endif 0117 #include "sym.h" 0118 /*#include "my_dmalloc.h"*/ 0119 0120 #define StrSame 0 0121 0122 static Sym **CurScope = NULL; 0123 static unsigned size = 0; 0124 static Sym **table=NULL; 0125 static char *strings; 0126 static char *strp; 0127 static int strsize = 0; 0128 0129 void 0130 zzs_init(int sz, int strs) 0131 { 0132 if ( sz <= 0 || strs <= 0 ) return; 0133 table = (Sym **) calloc(sz, sizeof(Sym *)); 0134 if ( table == NULL ) 0135 { 0136 fprintf(stderr, "Cannot allocate table of size %d\n", sz); 0137 exit(1); 0138 } 0139 strings = (char *) calloc(strs, sizeof(char)); 0140 if ( strings == NULL ) 0141 { 0142 fprintf(stderr, "Cannot allocate string table of size %d\n", strs); 0143 exit(1); 0144 } 0145 size = sz; 0146 strsize = strs; 0147 strp = strings; 0148 } 0149 0150 0151 void 0152 zzs_free(void) 0153 { 0154 unsigned i; 0155 Sym *cur, *next; 0156 0157 for (i = 0; i < size; i++) 0158 { 0159 cur = table[i]; 0160 while (cur != NULL) 0161 { 0162 next = cur->next; 0163 free (cur); 0164 cur = next; 0165 } 0166 } 0167 } 0168 0169 0170 void 0171 zzs_done(void) 0172 { 0173 if ( table != NULL ) free( table ); 0174 if ( strings != NULL ) free( strings ); 0175 } 0176 0177 void 0178 zzs_add(const char *key, register Sym *rec) 0179 { 0180 register unsigned int h=0; 0181 const char *p=key; 0182 0183 HASH_FUN(p, h); 0184 rec->hash = h; /* save hash code for fast comp later */ 0185 h %= size; 0186 0187 if ( CurScope != NULL ) {rec->scope = *CurScope; *CurScope = rec;} 0188 rec->next = table[h]; /* Add to doubly-linked list */ 0189 rec->prev = NULL; 0190 if ( rec->next != NULL ) (rec->next)->prev = rec; 0191 table[h] = rec; 0192 rec->head = &(table[h]); 0193 } 0194 0195 Sym * 0196 zzs_get(const char *key) 0197 { 0198 register unsigned int h=0; 0199 const char *p=key; 0200 register Sym *q; 0201 0202 HASH_FUN(p, h); 0203 0204 for (q = table[h%size]; q != NULL; q = q->next) 0205 { 0206 if ( q->hash == h ) /* do we even have a chance of matching? */ 0207 if ( strcasecmp(key, q->symbol) == StrSame ) return( q ); 0208 } 0209 return( NULL ); 0210 } 0211 0212 /* 0213 * Unlink p from the symbol table. Hopefully, it's actually in the 0214 * symbol table. 0215 * 0216 * If p is not part of a bucket chain of the symbol table, bad things 0217 * will happen. 0218 * 0219 * Will do nothing if all list pointers are NULL 0220 */ 0221 void 0222 zzs_del(register Sym *p) 0223 { 0224 if ( p == NULL ) {fprintf(stderr, "zzs_del(NULL)\n"); exit(1);} 0225 if ( p->prev == NULL ) /* Head of list */ 0226 { 0227 register Sym **t = p->head; 0228 0229 if ( t == NULL ) return; /* not part of symbol table */ 0230 (*t) = p->next; 0231 if ( (*t) != NULL ) (*t)->prev = NULL; 0232 } 0233 else 0234 { 0235 (p->prev)->next = p->next; 0236 if ( p->next != NULL ) (p->next)->prev = p->prev; 0237 } 0238 p->next = p->prev = NULL; /* not part of symbol table anymore */ 0239 p->head = NULL; 0240 } 0241 0242 void 0243 zzs_keydel(char *key) 0244 { 0245 Sym *p = zzs_get(key); 0246 0247 if ( p != NULL ) zzs_del( p ); 0248 } 0249 0250 /* S c o p e S t u f f */ 0251 0252 /* Set current scope to 'scope'; return current scope if 'scope' == NULL */ 0253 Sym ** 0254 zzs_scope(Sym **scope) 0255 { 0256 if ( scope == NULL ) return( CurScope ); 0257 CurScope = scope; 0258 return( scope ); 0259 } 0260 0261 /* Remove a scope described by 'scope'. Return pointer to 1st element in scope */ 0262 Sym * 0263 zzs_rmscope(register Sym **scope) 0264 { 0265 register Sym *p; 0266 Sym *start; 0267 0268 if ( scope == NULL ) return(NULL); 0269 start = p = *scope; 0270 for (; p != NULL; p=p->scope) { zzs_del( p ); } 0271 *scope = NULL; 0272 return( start ); 0273 } 0274 0275 void 0276 zzs_stat(void) 0277 { 0278 static unsigned short count[20]; 0279 unsigned int i,n=0,low=0, hi=0; 0280 register Sym **p; 0281 float avg=0.0; 0282 0283 for (i=0; i<20; i++) count[i] = 0; 0284 for (p=table; p<&(table[size]); p++) 0285 { 0286 register Sym *q = *p; 0287 unsigned int len; 0288 0289 if ( q != NULL && low==0 ) low = p-table; 0290 len = 0; 0291 if ( q != NULL ) printf("[%ld]", p-table); 0292 while ( q != NULL ) 0293 { 0294 len++; 0295 n++; 0296 printf(" %s", q->symbol); 0297 q = q->next; 0298 if ( q == NULL ) printf("\n"); 0299 } 0300 if ( len>=20 ) printf("zzs_stat: count table too small\n"); 0301 else count[len]++; 0302 if ( *p != NULL ) hi = p-table; 0303 } 0304 0305 printf("Storing %d recs used %d hash positions out of %d\n", 0306 n, size-count[0], size); 0307 printf("%f %% utilization\n", 0308 ((float)(size-count[0]))/((float)size)); 0309 for (i=0; i<20; i++) 0310 { 0311 if ( count[i] != 0 ) 0312 { 0313 avg += (((float)(i*count[i]))/((float)n)) * i; 0314 printf("Buckets of len %d == %d (%f %% of recs)\n", 0315 i, count[i], 100.0*((float)(i*count[i]))/((float)n)); 0316 } 0317 } 0318 printf("Avg bucket length %f\n", avg); 0319 printf("Range of hash function: %d..%d\n", low, hi); 0320 } 0321 0322 /* 0323 * Given a string, this function allocates and returns a pointer to a 0324 * symbol table record whose "symbol" pointer is reset to a position 0325 * in the string table. 0326 */ 0327 Sym * 0328 zzs_new(const char *text) 0329 { 0330 Sym *p; 0331 0332 if ( (p = (Sym *) calloc(1,sizeof(Sym))) == 0 ) 0333 { 0334 fprintf(stderr,"Out of memory\n"); 0335 exit(1); 0336 } 0337 p->symbol = zzs_strdup(text); 0338 0339 return p; 0340 } 0341 0342 /* create a new symbol table entry and add it to the symbol table */ 0343 Sym * 0344 zzs_newadd(const char *text) 0345 { 0346 Sym *p = zzs_new(text); 0347 if ( p != NULL ) zzs_add(text, p); 0348 return p; 0349 } 0350 0351 /* Add a string to the string table and return a pointer to it. 0352 * Bump the pointer into the string table to next avail position. 0353 */ 0354 char * 0355 zzs_strdup(const char *s) 0356 { 0357 register char *start=strp; 0358 0359 while ( *s != '\0' ) 0360 { 0361 if ( strp >= &(strings[strsize-2]) ) 0362 { 0363 fprintf(stderr, "sym: string table overflow (%d chars)\n", strsize); 0364 exit(-1); 0365 } 0366 *strp++ = *s++; 0367 } 0368 *strp++ = '\0'; 0369 0370 return( start ); 0371 }