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 }