4 * $Id: hash.c,v 1.3 95/10/05 11:57:07 parrt Exp $
9 * The following functions are visible:
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 *)
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.
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
38 * Parr Research Corporation
39 * with Purdue University and AHPCRC, University of Minnesota
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);}
69 static unsigned size = HashTableSize;
70 static char *strings = NULL;
72 static unsigned strsize = StrTableSize;
74 /* create the hash table and string table for terminals (string table only once) */
84 table = (Entry **) calloc(size, sizeof(Entry *));
85 require( table != NULL, "cannot allocate hash table");
86 if ( strings == NULL )
88 strings = (char *) calloc(strsize, sizeof(char));
89 require( strings != NULL, "cannot allocate string table");
97 killHashTable( Entry **table )
99 killHashTable( table )
103 /* for now, just free table, forget entries */
107 /* Given a table, add 'rec' with key 'key' (add to front of list). return ptr to entry */
110 hash_add( Entry **table, char *key, Entry *rec )
112 hash_add( table, key, rec )
120 extern Entry *Globals;
121 require(table!=NULL && key!=NULL && rec!=NULL, "add: invalid addition");
124 rec->next = table[h]; /* Add to singly-linked list */
129 /* Return ptr to 1st entry found in table under key (return NULL if none found) */
132 hash_get( Entry **table, char *key )
134 hash_get( table, key )
142 /* require(table!=NULL && key!=NULL, "get: invalid table and/or key");*/
143 if ( !(table!=NULL && key!=NULL) ) *((char *) 34) = 3;
146 for (q = table[h]; q != NULL; q = q->next)
148 if ( strcmp(key, q->str) == StrSame ) return( q );
156 hashStat( Entry **table )
162 static unsigned short count[20];
163 int i,n=0,low=0, hi=0;
167 for (i=0; i<20; i++) count[i] = 0;
168 for (p=table; p<&(table[size]); p++)
173 if ( q != NULL && low==0 ) low = p-table;
175 if ( q != NULL ) fprintf(stderr, "[%d]", p-table);
180 fprintf(stderr, " %s", q->str);
182 if ( q == NULL ) fprintf(stderr, "\n");
185 if ( *p != NULL ) hi = p-table;
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));
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));
201 fprintf(stderr, "Avg bucket length %f\n", avg);
202 fprintf(stderr, "Range of hash function: %d..%d\n", low, hi);
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.
218 require(s!=NULL, "mystrdup: NULL string");
222 require( strp <= &(strings[strsize-2]),
223 "string table overflow\nIncrease StrTableSize in hash.h and recompile hash.c\n");