1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
/*
* hash.c -- Manage hash tables.
*
* SOFTWARE RIGHTS
*
* We reserve no LEGAL rights to SORCERER -- SORCERER is in the public
* domain. An individual or company may do whatever they wish with
* source code distributed with SORCERER or the code generated by
* SORCERER, including the incorporation of SORCERER, or its output, into
* commerical software.
*
* We encourage users to develop software with SORCERER. However, we do
* ask that credit is given to us for developing SORCERER. 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 SORCERER and have developed a nice tool with the
* output, please mention that you developed it using SORCERER. 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.
*
* SORCERER 1.00B
* Terence Parr
* AHPCRC, University of Minnesota
* 1992-1994
*/
#include <stdio.h>
#ifdef __cplusplus
#ifndef __STDC__
#define __STDC__
#endif
#endif
#include "hash.h"
#ifdef __STDC__
#include <stdlib.h>
#else
#ifdef VAXC
#include <stdlib.h>
#else
#include <malloc.h>
#endif
#endif
#include <string.h>
#define StrSame 0
#define fatal(err) \
{fprintf(stderr, "%s(%d):", __FILE__, __LINE__); \
fprintf(stderr, " %s\n", err); exit(1);}
#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;
}
/* 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");
Hash(p,h,size);
for (q = table[h]; q != NULL; q = q->next)
{
if ( strcmp(key, q->str) == StrSame ) return( q );
}
return( NULL );
}
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);
}
/* 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 );
}
|