pd.if.org Git - pccts/blob - support/sym/sym.c

   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 __STDC__ == 1
 112 #include <string.h>
 113 #include <stdlib.h>
 114 #else
 115 #include "malloc.h"
 116 #endif
 117 #ifdef MEMCHK
 118 #include "trax.h"
 119 #endif
 120 #include "sym.h"
 121
 122 #define StrSame         0
 123
 124 static Sym **CurScope = NULL;
 125 static unsigned size = 0;
 126 static Sym **table=NULL;
 127 static char *strings;
 128 static char *strp;
 129 static int strsize = 0;
 130
 131 void
 132 zzs_init(sz, strs)
 133 int sz, strs;
 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 void
 154 zzs_done()
 155 {
 156         if ( table != NULL ) free( table );
 157         if ( strings != NULL ) free( strings );
 158 }
 159
 160 void
 161 zzs_add(key, rec)
 162 char *key;
 163 register Sym *rec;
 164 {
 165         register unsigned int h=0;
 166         register char *p=key;
 167         extern Sym *Globals;
 168
 169         HASH(p, h);
 170         rec->hash = h;                                  /* save hash code for fast comp later */
 171         h %= size;
 172
 173         if ( CurScope != NULL ) {rec->scope = *CurScope; *CurScope = rec;}
 174         rec->next = table[h];                   /* Add to doubly-linked list */
 175         rec->prev = NULL;
 176         if ( rec->next != NULL ) (rec->next)->prev = rec;
 177         table[h] = rec;
 178         rec->head = &(table[h]);
 179 }
 180
 181 Sym *
 182 zzs_get(key)
 183 char *key;
 184 {
 185         register unsigned int h=0;
 186         register char *p=key;
 187         register Sym *q;
 188
 189         HASH(p, h);
 190
 191         for (q = table[h%size]; q != NULL; q = q->next)
 192         {
 193                 if ( q->hash == h )             /* do we even have a chance of matching? */
 194                         if ( strcmp(key, q->symbol) == StrSame ) return( q );
 195         }
 196         return( NULL );
 197 }
 198
 199 /*
 200  * Unlink p from the symbol table.  Hopefully, it's actually in the
 201  * symbol table.
 202  *
 203  * If p is not part of a bucket chain of the symbol table, bad things
 204  * will happen.
 205  *
 206  * Will do nothing if all list pointers are NULL
 207  */
 208 void
 209 zzs_del(p)
 210 register Sym *p;
 211 {
 212         if ( p == NULL ) {fprintf(stderr, "zzs_del(NULL)\n"); exit(1);}
 213         if ( p->prev == NULL )  /* Head of list */
 214         {
 215                 register Sym **t = p->head;
 216
 217                 if ( t == NULL ) return;        /* not part of symbol table */
 218                 (*t) = p->next;
 219                 if ( (*t) != NULL ) (*t)->prev = NULL;
 220         }
 221         else
 222         {
 223                 (p->prev)->next = p->next;
 224                 if ( p->next != NULL ) (p->next)->prev = p->prev;
 225         }
 226         p->next = p->prev = NULL;       /* not part of symbol table anymore */
 227         p->head = NULL;
 228 }
 229
 230 void
 231 zzs_keydel(key)
 232 char *key;
 233 {
 234         Sym *p = zzs_get(key);
 235
 236         if ( p != NULL ) zzs_del( p );
 237 }
 238
 239 /* S c o p e  S t u f f */
 240
 241 /* Set current scope to 'scope'; return current scope if 'scope' == NULL */
 242 Sym **
 243 zzs_scope(scope)
 244 Sym **scope;
 245 {
 246         if ( scope == NULL ) return( CurScope );
 247         CurScope = scope;
 248         return( scope );
 249 }
 250
 251 /* Remove a scope described by 'scope'.  Return pointer to 1st element in scope */
 252 Sym *
 253 zzs_rmscope(scope)
 254 register Sym **scope;
 255 {
 256         register Sym *p;
 257         Sym *start;
 258
 259         if ( scope == NULL ) return(NULL);
 260         start = p = *scope;
 261         for (; p != NULL; p=p->scope) { zzs_del( p ); }
 262         *scope = NULL;
 263         return( start );
 264 }
 265
 266 void
 267 zzs_stat()
 268 {
 269         static unsigned short count[20];
 270         unsigned int i,n=0,low=0, hi=0;
 271         register Sym **p;
 272         float avg=0.0;
 273
 274         for (i=0; i<20; i++) count[i] = 0;
 275         for (p=table; p<&(table[size]); p++)
 276         {
 277                 register Sym *q = *p;
 278                 unsigned int len;
 279
 280                 if ( q != NULL && low==0 ) low = p-table;
 281                 len = 0;
 282                 if ( q != NULL ) printf("[%d]", p-table);
 283                 while ( q != NULL )
 284                 {
 285                         len++;
 286                         n++;
 287                         printf(" %s", q->symbol);
 288                         q = q->next;
 289                         if ( q == NULL ) printf("\n");
 290                 }
 291                 if ( len>=20 ) printf("zzs_stat: count table too small\n");
 292                 else count[len]++;
 293                 if ( *p != NULL ) hi = p-table;
 294         }
 295
 296         printf("Storing %d recs used %d hash positions out of %d\n",
 297                         n, size-count[0], size);
 298         printf("%f %% utilization\n",
 299                         ((float)(size-count[0]))/((float)size));
 300         for (i=0; i<20; i++)
 301         {
 302                 if ( count[i] != 0 )
 303                 {
 304                         avg += (((float)(i*count[i]))/((float)n)) * i;
 305                         printf("Buckets of len %d == %d (%f %% of recs)\n",
 306                                         i, count[i], 100.0*((float)(i*count[i]))/((float)n));
 307                 }
 308         }
 309         printf("Avg bucket length %f\n", avg);
 310         printf("Range of hash function: %d..%d\n", low, hi);
 311 }
 312
 313 /*
 314  * Given a string, this function allocates and returns a pointer to a
 315  * symbol table record whose "symbol" pointer is reset to a position
 316  * in the string table.
 317  */
 318 Sym *
 319 zzs_new(text)
 320 char *text;
 321 {
 322         Sym *p;
 323         char *zzs_strdup();
 324
 325         if ( (p = (Sym *) calloc(1,sizeof(Sym))) == 0 )
 326         {
 327                 fprintf(stderr,"Out of memory\n");
 328                 exit(1);
 329         }
 330         p->symbol = zzs_strdup(text);
 331
 332         return p;
 333 }
 334
 335 /* create a new symbol table entry and add it to the symbol table */
 336 Sym *
 337 zzs_newadd(text)
 338 char *text;
 339 {
 340         Sym *p = zzs_new(text);
 341         if ( p != NULL ) zzs_add(text, p);
 342         return p;
 343 }
 344
 345 /* Add a string to the string table and return a pointer to it.
 346  * Bump the pointer into the string table to next avail position.
 347  */
 348 char *
 349 zzs_strdup(s)
 350 register char *s;
 351 {
 352         register char *start=strp;
 353
 354         while ( *s != '\0' )
 355         {
 356                 if ( strp >= &(strings[strsize-2]) )
 357                 {
 358                         fprintf(stderr, "sym: string table overflow (%d chars)\n", strsize);
 359                         exit(-1);
 360                 }
 361                 *strp++ = *s++;
 362         }
 363         *strp++ = '\0';
 364
 365         return( start );
 366 }