1 /********************************************
2 hash.c
3 copyright 2008-2010,2012, Thomas E. Dickey
4 copyright 1991-1993,1994, Michael D. Brennan
5
6 This is a source file for mawk, an implementation of
7 the AWK programming language.
8
9 Mawk is distributed without warranty under the terms of
10 the GNU General Public License, version 2, 1991.
11 ********************************************/
12
13 /*
14 * $MawkId: hash.c,v 1.19 2012/11/02 00:39:27 tom Exp $
15 * @Log: hash.c,v @
16 * Revision 1.3 1994/10/08 19:15:43 mike
17 * remove SM_DOS
18 *
19 * Revision 1.2 1993/07/16 00:17:35 mike
20 * cleanup
21 *
22 * Revision 1.1.1.1 1993/07/03 18:58:14 mike
23 * move source to cvs
24 *
25 * Revision 5.1 1991/12/05 07:56:05 brennan
26 * 1.1 pre-release
27 *
28 */
29
30 /* hash.c */
31
32 #include "mawk.h"
33 #include "memory.h"
34 #include "symtype.h"
35
36 #ifdef NO_LEAKS
37 #include "bi_vars.h"
38 #endif
39
40 /*
41 * FNV-1 hash function
42 * http://www.isthe.com/chongo/tech/comp/fnv/index.html
43 */
44 unsigned
hash(const char * s)45 hash(const char *s)
46 {
47 /* FNV-1 */
48 register unsigned h = 2166136261U;
49
50 while (*s) {
51 h ^= (UChar) (*s++);
52 h *= 16777619U;
53 }
54 return h;
55 }
56
57 unsigned
hash2(const char * s,size_t len)58 hash2(const char *s, size_t len)
59 {
60 /* FNV-1 */
61 register unsigned h = 2166136261U;
62
63 while (len-- != 0) {
64 h ^= (UChar) (*s++);
65 h *= 16777619U;
66 }
67 return h;
68 }
69
70 typedef struct hash {
71 struct hash *link;
72 SYMTAB symtab;
73 } HASHNODE;
74
75 static HASHNODE *hash_table[HASH_PRIME];
76
77 #ifdef NO_LEAKS
78 static void free_hashnode(HASHNODE *);
79 #else
80 #define free_hashnode(p) zfree(delete(p->symtab.name), sizeof(HASHNODE))
81 #endif
82
83 /*
84 insert a string in the symbol table.
85 Caller knows the symbol is not there
86 -- used for initialization
87 */
88
89 SYMTAB *
insert(const char * s)90 insert(const char *s)
91 {
92 register HASHNODE *p = ZMALLOC(HASHNODE);
93 register unsigned h;
94
95 p->link = hash_table[h = hash(s) % HASH_PRIME];
96 p->symtab.name = s;
97 #ifdef NO_LEAKS
98 p->symtab.free_name = 0;
99 #endif
100 hash_table[h] = p;
101 return &p->symtab;
102 }
103
104 /* Find s in the symbol table,
105 if not there insert it, s must be dup'ed */
106
107 SYMTAB *
find(const char * s)108 find(const char *s)
109 {
110 register HASHNODE *p;
111 HASHNODE *q;
112 unsigned h;
113
114 p = hash_table[h = hash(s) % HASH_PRIME];
115 q = (HASHNODE *) 0;
116 while (1) {
117 if (!p) {
118 p = ZMALLOC(HASHNODE);
119 p->symtab.type = ST_NONE;
120 p->symtab.name = strcpy(zmalloc(strlen(s) + 1), s);
121 #ifdef NO_LEAKS
122 p->symtab.free_name = 1;
123 #endif
124 break;
125 }
126
127 if (strcmp(p->symtab.name, s) == 0) /* found */
128 {
129 if (!q) /* already at the front */
130 return &p->symtab;
131 else { /* delete from the list */
132 q->link = p->link;
133 break;
134 }
135 }
136
137 q = p;
138 p = p->link;
139 }
140 /* put p on front of the list */
141 p->link = hash_table[h];
142 hash_table[h] = p;
143 return &p->symtab;
144 }
145
146 /* remove a node from the hash table
147 return a ptr to the node */
148
149 static unsigned last_hash;
150
151 static HASHNODE *
delete(const char * s)152 delete(const char *s)
153 {
154 register HASHNODE *p;
155 HASHNODE *q = (HASHNODE *) 0;
156 unsigned h;
157
158 p = hash_table[last_hash = h = hash(s) % HASH_PRIME];
159 while (p) {
160 if (strcmp(p->symtab.name, s) == 0) /* found */
161 {
162 if (q)
163 q->link = p->link;
164 else
165 hash_table[h] = p->link;
166 return p;
167 } else {
168 q = p;
169 p = p->link;
170 }
171 }
172
173 #ifdef DEBUG /* we should not ever get here */
174 bozo("delete");
175 #endif
176 return (HASHNODE *) 0;
177 }
178
179 /* when processing user functions, global ids which are
180 replaced by local ids are saved on this list */
181
182 static HASHNODE *save_list;
183
184 /* store a global id on the save list,
185 return a ptr to the local symtab */
186 SYMTAB *
save_id(const char * s)187 save_id(const char *s)
188 {
189 HASHNODE *p, *q;
190 unsigned h;
191
192 p = delete(s);
193 q = ZMALLOC(HASHNODE);
194 q->symtab.type = ST_LOCAL_NONE;
195 q->symtab.name = p->symtab.name;
196 /* put q in the hash table */
197 q->link = hash_table[h = last_hash];
198 hash_table[h] = q;
199
200 /* save p */
201 p->link = save_list;
202 save_list = p;
203
204 return &q->symtab;
205 }
206
207 /* restore all global identifiers */
208 void
restore_ids(void)209 restore_ids(void)
210 {
211 register HASHNODE *p, *q;
212 register unsigned h;
213
214 q = save_list;
215 save_list = (HASHNODE *) 0;
216 while (q) {
217 p = q;
218 q = q->link;
219 free_hashnode(p);
220 p->link = hash_table[h = last_hash];
221 hash_table[h] = p;
222 }
223 }
224
225 /* search the symbol table backwards for the
226 disassembler. This is slow -- so what
227 */
228
229 const char *
reverse_find(int type,PTR ptr)230 reverse_find(int type, PTR ptr)
231 {
232 CELL *cp = 0;
233 ARRAY array = 0;
234 static char uk[] = "unknown";
235
236 int i;
237 HASHNODE *p;
238
239 switch (type) {
240 case ST_VAR:
241 case ST_FIELD:
242 cp = *(CELL **) ptr;
243 break;
244
245 case ST_ARRAY:
246 array = *(ARRAY *) ptr;
247 break;
248
249 default:
250 return uk;
251 }
252
253 for (i = 0; i < HASH_PRIME; i++) {
254 p = hash_table[i];
255 while (p) {
256 if (p->symtab.type == type) {
257 switch (type) {
258 case ST_VAR:
259 case ST_FIELD:
260 if (cp == p->symtab.stval.cp)
261 return p->symtab.name;
262 break;
263
264 case ST_ARRAY:
265 if (array == p->symtab.stval.array)
266 return p->symtab.name;
267 break;
268 }
269 }
270
271 p = p->link;
272 }
273 }
274 return uk;
275 }
276
277 #ifdef NO_LEAKS
278 static void
free_symtab_name(HASHNODE * p)279 free_symtab_name(HASHNODE * p)
280 {
281 if (p->symtab.free_name) {
282 zfree((PTR) (p->symtab.name), strlen(p->symtab.name) + 1);
283 }
284 }
285
286 static void
free_hashnode(HASHNODE * p)287 free_hashnode(HASHNODE * p)
288 {
289 CELL *cp;
290
291 TRACE(("...deleting hash %p (%p) %s %d\n",
292 (void *) p,
293 (void *) &(p->symtab),
294 p->symtab.name, p->symtab.type));
295 p = delete(p->symtab.name);
296 switch (p->symtab.type) {
297 case ST_FUNCT:
298 free_codes(p->symtab.name,
299 p->symtab.stval.fbp->code,
300 p->symtab.stval.fbp->size);
301 if (p->symtab.stval.fbp->nargs)
302 zfree(p->symtab.stval.fbp->typev, p->symtab.stval.fbp->nargs);
303 zfree(p->symtab.stval.fbp, sizeof(FBLOCK));
304 break;
305 case ST_NONE:
306 break;
307 case ST_VAR:
308 cp = p->symtab.stval.cp;
309 if (cp != 0
310 && (cp < bi_vars || cp > bi_vars + NUM_BI_VAR)) {
311 switch (cp->type) {
312 case C_STRING:
313 case C_STRNUM:
314 case C_MBSTRN:
315 free_STRING(string(cp));
316 break;
317 }
318 zfree(cp, sizeof(CELL));
319 }
320 break;
321 default:
322 break;
323 }
324 free_symtab_name(p);
325 zfree(p, sizeof(HASHNODE));
326 }
327
328 void
hash_leaks(void)329 hash_leaks(void)
330 {
331 int i;
332 HASHNODE *p;
333
334 TRACE(("hash_leaks\n"));
335 for (i = 0; i < HASH_PRIME; i++) {
336 while ((p = hash_table[i]) != 0) {
337 free_hashnode(p);
338 }
339 }
340 }
341 #endif
342