Tools/CodeTools/TianoTools/Pccts/antlr/hash.c

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