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 } 222
