X-Git-Url: https://pd.if.org/git/?p=pccts;a=blobdiff_plain;f=antlr%2Fhash.c;fp=antlr%2Fhash.c;h=6e8a278d9ef0c3ddfae94331c66b7fe03c938d6e;hp=0000000000000000000000000000000000000000;hb=4c1585478dbadc88148f5417d75d6f58b8042c82;hpb=129ce0f1c9d43c04ed8198ac184bce8d8be0042e diff --git a/antlr/hash.c b/antlr/hash.c new file mode 100755 index 0000000..6e8a278 --- /dev/null +++ b/antlr/hash.c @@ -0,0 +1,229 @@ +/* + * hash.c + * + * $Id: hash.c,v 1.3 95/10/05 11:57:07 parrt Exp $ + * $Revision: 1.3 $ + * + * Manage hash tables. + * + * The following functions are visible: + * + * char *mystrdup(char *); Make space and copy string + * Entry **newHashTable(); Create and return initialized hash table + * Entry *hash_add(Entry **, char *, Entry *) + * Entry *hash_get(Entry **, char *) + * + * SOFTWARE RIGHTS + * + * We reserve no LEGAL rights to the Purdue Compiler Construction Tool + * Set (PCCTS) -- PCCTS is in the public domain. An individual or + * company may do whatever they wish with source code distributed with + * PCCTS or the code generated by PCCTS, including the incorporation of + * PCCTS, or its output, into commerical software. + * + * We encourage users to develop software with PCCTS. However, we do ask + * that credit is given to us for developing PCCTS. By "credit", + * we mean that if you incorporate our source code into one of your + * programs (commercial product, research project, or otherwise) that you + * acknowledge this fact somewhere in the documentation, research report, + * etc... If you like PCCTS and have developed a nice tool with the + * output, please mention that you developed it using PCCTS. In + * addition, we ask that this header remain intact in our source code. + * As long as these guidelines are kept, we expect to continue enhancing + * this system and expect to make other tools available as they are + * completed. + * + * ANTLR 1.33 + * Terence Parr + * Parr Research Corporation + * with Purdue University and AHPCRC, University of Minnesota + * 1989-1995 + */ + +#include +#include "config.h" +#ifdef __cplusplus +#ifndef __STDC__ +#define __STDC__ +#endif +#endif +#include "hash.h" +#ifdef __STDC__ +#include +#else +#ifdef VAXC +#include +#else +#include +#endif +#endif +#include + +#define StrSame 0 + +#define fatal(err) \ + {fprintf(stderr, "%s(%d):", __FILE__, __LINE__); \ + fprintf(stderr, " %s\n", err); exit(PCCTS_EXIT_FAILURE);} +#define require(expr, err) {if ( !(expr) ) fatal(err);} + +static unsigned size = HashTableSize; +static char *strings = NULL; +static char *strp; +static unsigned strsize = StrTableSize; + +/* create the hash table and string table for terminals (string table only once) */ +Entry ** +#ifdef __STDC__ +newHashTable( void ) +#else +newHashTable( ) +#endif +{ + Entry **table; + + table = (Entry **) calloc(size, sizeof(Entry *)); + require( table != NULL, "cannot allocate hash table"); + if ( strings == NULL ) + { + strings = (char *) calloc(strsize, sizeof(char)); + require( strings != NULL, "cannot allocate string table"); + strp = strings; + } + return table; +} + +void +#ifdef __STDC__ +killHashTable( Entry **table ) +#else +killHashTable( table ) +Entry **table; +#endif +{ + /* for now, just free table, forget entries */ + free( table ); +} + +/* Given a table, add 'rec' with key 'key' (add to front of list). return ptr to entry */ +Entry * +#ifdef __STDC__ +hash_add( Entry **table, char *key, Entry *rec ) +#else +hash_add( table, key, rec ) +Entry **table; +char *key; +Entry *rec; +#endif +{ + unsigned h=0; + char *p=key; + extern Entry *Globals; + require(table!=NULL && key!=NULL && rec!=NULL, "add: invalid addition"); + + Hash(p,h,size); + rec->next = table[h]; /* Add to singly-linked list */ + table[h] = rec; + return rec; +} + +/* Return ptr to 1st entry found in table under key (return NULL if none found) */ +Entry * +#ifdef __STDC__ +hash_get( Entry **table, char *key ) +#else +hash_get( table, key ) +Entry **table; +char *key; +#endif +{ + unsigned h=0; + char *p=key; + Entry *q; +/* require(table!=NULL && key!=NULL, "get: invalid table and/or key");*/ + if ( !(table!=NULL && key!=NULL) ) *((char *) 34) = 3; + + Hash(p,h,size); + for (q = table[h]; q != NULL; q = q->next) + { + if ( strcmp(key, q->str) == StrSame ) return( q ); + } + return( NULL ); +} + +#ifdef DEBUG_HASH +void +#ifdef __STDC__ +hashStat( Entry **table ) +#else +hashStat( table ) +Entry **table; +#endif +{ + static unsigned short count[20]; + int i,n=0,low=0, hi=0; + Entry **p; + float avg=0.0; + + for (i=0; i<20; i++) count[i] = 0; + for (p=table; p<&(table[size]); p++) + { + Entry *q = *p; + int len; + + if ( q != NULL && low==0 ) low = p-table; + len = 0; + if ( q != NULL ) fprintf(stderr, "[%d]", p-table); + while ( q != NULL ) + { + len++; + n++; + fprintf(stderr, " %s", q->str); + q = q->next; + if ( q == NULL ) fprintf(stderr, "\n"); + } + count[len]++; + if ( *p != NULL ) hi = p-table; + } + + fprintf(stderr, "Storing %d recs used %d hash positions out of %d\n", + n, size-count[0], size); + fprintf(stderr, "%f %% utilization\n", + ((float)(size-count[0]))/((float)size)); + for (i=0; i<20; i++) + { + if ( count[i] != 0 ) + { + avg += (((float)(i*count[i]))/((float)n)) * i; + fprintf(stderr, "Bucket len %d == %d (%f %% of recs)\n", + i, count[i], ((float)(i*count[i]))/((float)n)); + } + } + fprintf(stderr, "Avg bucket length %f\n", avg); + fprintf(stderr, "Range of hash function: %d..%d\n", low, hi); +} +#endif + +/* Add a string to the string table and return a pointer to it. + * Bump the pointer into the string table to next avail position. + */ +char * +#ifdef __STDC__ +mystrdup( char *s ) +#else +mystrdup( s ) +char *s; +#endif +{ + char *start=strp; + require(s!=NULL, "mystrdup: NULL string"); + + while ( *s != '\0' ) + { + require( strp <= &(strings[strsize-2]), + "string table overflow\nIncrease StrTableSize in hash.h and recompile hash.c\n"); + *strp++ = *s++; + } + *strp++ = '\0'; + + return( start ); +}