]>
Commit | Line | Data |
---|---|---|
878ddf1f | 1 | /*\r |
2 | * hash.c\r | |
3 | *\r | |
4 | * Manage hash tables.\r | |
5 | *\r | |
6 | * The following functions are visible:\r | |
7 | *\r | |
8 | * char *mystrdup(char *); Make space and copy string\r | |
9 | * Entry **newHashTable(); Create and return initialized hash table\r | |
10 | * Entry *hash_add(Entry **, char *, Entry *)\r | |
11 | * Entry *hash_get(Entry **, char *)\r | |
12 | *\r | |
13 | * SOFTWARE RIGHTS\r | |
14 | *\r | |
15 | * We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r | |
16 | * Set (PCCTS) -- PCCTS is in the public domain. An individual or\r | |
17 | * company may do whatever they wish with source code distributed with\r | |
18 | * PCCTS or the code generated by PCCTS, including the incorporation of\r | |
19 | * PCCTS, or its output, into commerical software.\r | |
20 | *\r | |
21 | * We encourage users to develop software with PCCTS. However, we do ask\r | |
22 | * that credit is given to us for developing PCCTS. By "credit",\r | |
23 | * we mean that if you incorporate our source code into one of your\r | |
24 | * programs (commercial product, research project, or otherwise) that you\r | |
25 | * acknowledge this fact somewhere in the documentation, research report,\r | |
26 | * etc... If you like PCCTS and have developed a nice tool with the\r | |
27 | * output, please mention that you developed it using PCCTS. In\r | |
28 | * addition, we ask that this header remain intact in our source code.\r | |
29 | * As long as these guidelines are kept, we expect to continue enhancing\r | |
30 | * this system and expect to make other tools available as they are\r | |
31 | * completed.\r | |
32 | *\r | |
33 | * ANTLR 1.33\r | |
34 | * Terence Parr\r | |
35 | * Parr Research Corporation\r | |
36 | * with Purdue University and AHPCRC, University of Minnesota\r | |
37 | * 1989-2001\r | |
38 | */\r | |
39 | \r | |
40 | #include <stdio.h>\r | |
41 | #include "pcctscfg.h"\r | |
42 | #include "hash.h"\r | |
43 | \r | |
44 | #ifdef __USE_PROTOS\r | |
45 | #include <stdlib.h>\r | |
46 | #else\r | |
47 | #ifdef VAXC\r | |
48 | #include <stdlib.h>\r | |
49 | #else\r | |
50 | #include <malloc.h>\r | |
51 | #endif\r | |
52 | #endif\r | |
53 | #include <string.h>\r | |
54 | \r | |
55 | #define StrSame 0\r | |
56 | \r | |
57 | #define fatal(err) \\r | |
58 | {fprintf(stderr, "%s(%d):", __FILE__, __LINE__); \\r | |
59 | fprintf(stderr, " %s\n", err); exit(PCCTS_EXIT_FAILURE);}\r | |
60 | #define require(expr, err) {if ( !(expr) ) fatal(err);}\r | |
61 | \r | |
62 | static unsigned size = HashTableSize;\r | |
63 | static char *strings = NULL;\r | |
64 | static char *strp;\r | |
65 | static unsigned strsize = StrTableSize;\r | |
66 | \r | |
67 | /* create the hash table and string table for terminals (string table only once) */\r | |
68 | Entry **\r | |
69 | #ifdef __USE_PROTOS\r | |
70 | newHashTable( void )\r | |
71 | #else\r | |
72 | newHashTable( )\r | |
73 | #endif\r | |
74 | {\r | |
75 | Entry **table;\r | |
76 | \r | |
77 | table = (Entry **) calloc(size, sizeof(Entry *));\r | |
78 | require( table != NULL, "cannot allocate hash table");\r | |
79 | if ( strings == NULL )\r | |
80 | {\r | |
81 | strings = (char *) calloc(strsize, sizeof(char));\r | |
82 | require( strings != NULL, "cannot allocate string table");\r | |
83 | strp = strings;\r | |
84 | }\r | |
85 | return table;\r | |
86 | }\r | |
87 | \r | |
88 | void\r | |
89 | #ifdef __USE_PROTOS\r | |
90 | killHashTable( Entry **table )\r | |
91 | #else\r | |
92 | killHashTable( table )\r | |
93 | Entry **table;\r | |
94 | #endif\r | |
95 | {\r | |
96 | /* for now, just free table, forget entries */\r | |
97 | free( (char *) table ); /* MR10 cast */\r | |
98 | }\r | |
99 | \r | |
100 | /* Given a table, add 'rec' with key 'key' (add to front of list). return ptr to entry */\r | |
101 | Entry *\r | |
102 | #ifdef __USE_PROTOS\r | |
103 | hash_add( Entry **table, char *key, Entry *rec )\r | |
104 | #else\r | |
105 | hash_add( table, key, rec )\r | |
106 | Entry **table;\r | |
107 | char *key;\r | |
108 | Entry *rec;\r | |
109 | #endif\r | |
110 | {\r | |
111 | unsigned h=0;\r | |
112 | char *p=key;\r | |
113 | require(table!=NULL && key!=NULL && rec!=NULL, "add: invalid addition");\r | |
114 | \r | |
115 | Hash(p,h,size);\r | |
116 | rec->next = table[h]; /* Add to singly-linked list */\r | |
117 | table[h] = rec;\r | |
118 | return rec;\r | |
119 | }\r | |
120 | \r | |
121 | /* Return ptr to 1st entry found in table under key (return NULL if none found) */\r | |
122 | Entry *\r | |
123 | #ifdef __USE_PROTOS\r | |
124 | hash_get( Entry **table, char *key )\r | |
125 | #else\r | |
126 | hash_get( table, key )\r | |
127 | Entry **table;\r | |
128 | char *key;\r | |
129 | #endif\r | |
130 | {\r | |
131 | unsigned h=0;\r | |
132 | char *p=key;\r | |
133 | Entry *q;\r | |
134 | /* require(table!=NULL && key!=NULL, "get: invalid table and/or key");*/\r | |
135 | if ( !(table!=NULL && key!=NULL) ) *((char *) 34) = 3;\r | |
136 | \r | |
137 | Hash(p,h,size);\r | |
138 | for (q = table[h]; q != NULL; q = q->next)\r | |
139 | {\r | |
140 | if ( strcmp(key, q->str) == StrSame ) return( q );\r | |
141 | }\r | |
142 | return( NULL );\r | |
143 | }\r | |
144 | \r | |
145 | #ifdef DEBUG_HASH\r | |
146 | void\r | |
147 | #ifdef __USE_PROTOS\r | |
148 | hashStat( Entry **table )\r | |
149 | #else\r | |
150 | hashStat( table )\r | |
151 | Entry **table;\r | |
152 | #endif\r | |
153 | {\r | |
154 | static unsigned short count[20];\r | |
155 | int i,n=0,low=0, hi=0;\r | |
156 | Entry **p;\r | |
157 | float avg=0.0;\r | |
158 | \r | |
159 | for (i=0; i<20; i++) count[i] = 0;\r | |
160 | for (p=table; p<&(table[size]); p++)\r | |
161 | {\r | |
162 | Entry *q = *p;\r | |
163 | int len;\r | |
164 | \r | |
165 | if ( q != NULL && low==0 ) low = p-table;\r | |
166 | len = 0;\r | |
167 | if ( q != NULL ) fprintf(stderr, "[%d]", p-table);\r | |
168 | while ( q != NULL )\r | |
169 | {\r | |
170 | len++;\r | |
171 | n++;\r | |
172 | fprintf(stderr, " %s", q->str);\r | |
173 | q = q->next;\r | |
174 | if ( q == NULL ) fprintf(stderr, "\n");\r | |
175 | }\r | |
176 | count[len]++;\r | |
177 | if ( *p != NULL ) hi = p-table;\r | |
178 | }\r | |
179 | \r | |
180 | fprintf(stderr, "Storing %d recs used %d hash positions out of %d\n",\r | |
181 | n, size-count[0], size);\r | |
182 | fprintf(stderr, "%f %% utilization\n",\r | |
183 | ((float)(size-count[0]))/((float)size));\r | |
184 | for (i=0; i<20; i++)\r | |
185 | {\r | |
186 | if ( count[i] != 0 )\r | |
187 | {\r | |
188 | avg += (((float)(i*count[i]))/((float)n)) * i;\r | |
189 | fprintf(stderr, "Bucket len %d == %d (%f %% of recs)\n",\r | |
190 | i, count[i], ((float)(i*count[i]))/((float)n));\r | |
191 | }\r | |
192 | }\r | |
193 | fprintf(stderr, "Avg bucket length %f\n", avg);\r | |
194 | fprintf(stderr, "Range of hash function: %d..%d\n", low, hi);\r | |
195 | }\r | |
196 | #endif\r | |
197 | \r | |
198 | /* Add a string to the string table and return a pointer to it.\r | |
199 | * Bump the pointer into the string table to next avail position.\r | |
200 | */\r | |
201 | char *\r | |
202 | #ifdef __USE_PROTOS\r | |
203 | mystrdup( char *s )\r | |
204 | #else\r | |
205 | mystrdup( s )\r | |
206 | char *s;\r | |
207 | #endif\r | |
208 | {\r | |
209 | char *start=strp;\r | |
210 | require(s!=NULL, "mystrdup: NULL string");\r | |
211 | \r | |
212 | while ( *s != '\0' )\r | |
213 | {\r | |
214 | require( strp <= &(strings[strsize-2]),\r | |
215 | "string table overflow\nIncrease StrTableSize in hash.h and recompile hash.c\n");\r | |
216 | *strp++ = *s++;\r | |
217 | }\r | |
218 | *strp++ = '\0';\r | |
219 | \r | |
220 | return( start );\r | |
221 | }\r |