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