pd.if.org Git - pccts/blob - antlr/hash.c

   1 /*
   2  * hash.c
   3  *
   4  * $Id: hash.c,v 1.3 95/10/05 11:57:07 parrt Exp $
   5  * $Revision: 1.3 $
   6  *
   7  * Manage hash tables.
   8  *
   9  * The following functions are visible:
  10  *
  11  *              char    *mystrdup(char *);              Make space and copy string
  12  *              Entry   **newHashTable();               Create and return initialized hash table
  13  *              Entry   *hash_add(Entry **, char *, Entry *)
  14  *              Entry   *hash_get(Entry **, char *)
  15  *
  16  * SOFTWARE RIGHTS
  17  *
  18  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  19  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  20  * company may do whatever they wish with source code distributed with
  21  * PCCTS or the code generated by PCCTS, including the incorporation of
  22  * PCCTS, or its output, into commerical software.
  23  *
  24  * We encourage users to develop software with PCCTS.  However, we do ask
  25  * that credit is given to us for developing PCCTS.  By "credit",
  26  * we mean that if you incorporate our source code into one of your
  27  * programs (commercial product, research project, or otherwise) that you
  28  * acknowledge this fact somewhere in the documentation, research report,
  29  * etc...  If you like PCCTS and have developed a nice tool with the
  30  * output, please mention that you developed it using PCCTS.  In
  31  * addition, we ask that this header remain intact in our source code.
  32  * As long as these guidelines are kept, we expect to continue enhancing
  33  * this system and expect to make other tools available as they are
  34  * completed.
  35  *
  36  * ANTLR 1.33
  37  * Terence Parr
  38  * Parr Research Corporation
  39  * with Purdue University and AHPCRC, University of Minnesota
  40  * 1989-1995
  41  */
  42
  43 #include <stdio.h>
  44 #include "config.h"
  45 #ifdef __cplusplus
  46 #ifndef __STDC__
  47 #define __STDC__
  48 #endif
  49 #endif
  50 #include "hash.h"
  51 #ifdef __STDC__
  52 #include <stdlib.h>
  53 #else
  54 #ifdef VAXC
  55 #include <stdlib.h>
  56 #else
  57 #include <malloc.h>
  58 #endif
  59 #endif
  60 #include <string.h>
  61
  62 #define StrSame         0
  63
  64 #define fatal(err)                                                                                                                      \
  65                         {fprintf(stderr, "%s(%d):", __FILE__, __LINE__);                                \
  66                         fprintf(stderr, " %s\n", err); exit(PCCTS_EXIT_FAILURE);}
  67 #define require(expr, err) {if ( !(expr) ) fatal(err);}
  68
  69 static unsigned size = HashTableSize;
  70 static char *strings = NULL;
  71 static char *strp;
  72 static unsigned strsize = StrTableSize;
  73
  74 /* create the hash table and string table for terminals (string table only once) */
  75 Entry **
  76 #ifdef __STDC__
  77 newHashTable( void )
  78 #else
  79 newHashTable( )
  80 #endif
  81 {
  82         Entry **table;
  83
  84         table = (Entry **) calloc(size, sizeof(Entry *));
  85         require( table != NULL, "cannot allocate hash table");
  86         if ( strings == NULL )
  87         {
  88                 strings = (char *) calloc(strsize, sizeof(char));
  89                 require( strings != NULL, "cannot allocate string table");
  90                 strp = strings;
  91         }
  92         return table;
  93 }
  94
  95 void
  96 #ifdef __STDC__
  97 killHashTable( Entry **table )
  98 #else
  99 killHashTable( table )
 100 Entry **table;
 101 #endif
 102 {
 103         /* for now, just free table, forget entries */
 104         free( table );
 105 }
 106
 107 /* Given a table, add 'rec' with key 'key' (add to front of list). return ptr to entry */
 108 Entry *
 109 #ifdef __STDC__
 110 hash_add( Entry **table, char *key, Entry *rec )
 111 #else
 112 hash_add( table, key, rec )
 113 Entry **table;
 114 char *key;
 115 Entry *rec;
 116 #endif
 117 {
 118         unsigned h=0;
 119         char *p=key;
 120         extern Entry *Globals;
 121         require(table!=NULL && key!=NULL && rec!=NULL, "add: invalid addition");
 122
 123         Hash(p,h,size);
 124         rec->next = table[h];                   /* Add to singly-linked list */
 125         table[h] = rec;
 126         return rec;
 127 }
 128
 129 /* Return ptr to 1st entry found in table under key (return NULL if none found) */
 130 Entry *
 131 #ifdef __STDC__
 132 hash_get( Entry **table, char *key )
 133 #else
 134 hash_get( table, key )
 135 Entry **table;
 136 char *key;
 137 #endif
 138 {
 139         unsigned h=0;
 140         char *p=key;
 141         Entry *q;
 142 /*      require(table!=NULL && key!=NULL, "get: invalid table and/or key");*/
 143         if ( !(table!=NULL && key!=NULL) ) *((char *) 34) = 3;
 144
 145         Hash(p,h,size);
 146         for (q = table[h]; q != NULL; q = q->next)
 147         {
 148                 if ( strcmp(key, q->str) == StrSame ) return( q );
 149         }
 150         return( NULL );
 151 }
 152
 153 #ifdef DEBUG_HASH
 154 void
 155 #ifdef __STDC__
 156 hashStat( Entry **table )
 157 #else
 158 hashStat( table )
 159 Entry **table;
 160 #endif
 161 {
 162         static unsigned short count[20];
 163         int i,n=0,low=0, hi=0;
 164         Entry **p;
 165         float avg=0.0;
 166
 167         for (i=0; i<20; i++) count[i] = 0;
 168         for (p=table; p<&(table[size]); p++)
 169         {
 170                 Entry *q = *p;
 171                 int len;
 172
 173                 if ( q != NULL && low==0 ) low = p-table;
 174                 len = 0;
 175                 if ( q != NULL ) fprintf(stderr, "[%d]", p-table);
 176                 while ( q != NULL )
 177                 {
 178                         len++;
 179                         n++;
 180                         fprintf(stderr, " %s", q->str);
 181                         q = q->next;
 182                         if ( q == NULL ) fprintf(stderr, "\n");
 183                 }
 184                 count[len]++;
 185                 if ( *p != NULL ) hi = p-table;
 186         }
 187
 188         fprintf(stderr, "Storing %d recs used %d hash positions out of %d\n",
 189                                         n, size-count[0], size);
 190         fprintf(stderr, "%f %% utilization\n",
 191                                         ((float)(size-count[0]))/((float)size));
 192         for (i=0; i<20; i++)
 193         {
 194                 if ( count[i] != 0 )
 195                 {
 196                         avg += (((float)(i*count[i]))/((float)n)) * i;
 197                         fprintf(stderr, "Bucket len %d == %d (%f %% of recs)\n",
 198                                                         i, count[i], ((float)(i*count[i]))/((float)n));
 199                 }
 200         }
 201         fprintf(stderr, "Avg bucket length %f\n", avg);
 202         fprintf(stderr, "Range of hash function: %d..%d\n", low, hi);
 203 }
 204 #endif
 205
 206 /* Add a string to the string table and return a pointer to it.
 207  * Bump the pointer into the string table to next avail position.
 208  */
 209 char *
 210 #ifdef __STDC__
 211 mystrdup( char *s )
 212 #else
 213 mystrdup( s )
 214 char *s;
 215 #endif
 216 {
 217         char *start=strp;
 218         require(s!=NULL, "mystrdup: NULL string");
 219
 220         while ( *s != '\0' )
 221         {
 222                 require( strp <= &(strings[strsize-2]),
 223                                  "string table overflow\nIncrease StrTableSize in hash.h and recompile hash.c\n");
 224                 *strp++ = *s++;
 225         }
 226         *strp++ = '\0';
 227
 228         return( start );
 229 }