1 /*
2 * Copyright (c) 2004 - 2010, Nils R. Weller
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 * POSSIBILITY OF SUCH DAMAGE.
26 */
27 /*
28 * This module contains a primitive function to build a linked list for
29 * symbols. Because every scope has its own symbol ``table'', speeding
30 * this stuff up, e.g. by using a skip list, would probably buy very
31 * little, maybe even make it slower. Implementing a unified lookup
32 * mechanism for all symbols might be a reasonable future goal though
33 */
34
35 #include "symlist.h"
36 #include <string.h>
37 #include <stdlib.h>
38 #include "misc.h"
39 #include "decl.h"
40 #include "type.h"
41 #include "scope.h"
42 #include "zalloc.h"
43 #include "debug.h"
44 #include "token.h"
45 #include "n_libc.h"
46
47 #define HASH_SYM_ENTRY 1
48
49 static int
hash_symbol(const char * name,int tabsize)50 hash_symbol(const char *name, int tabsize) {
51 int key = 0;
52
53 for (; *name != 0; ++name) {
54 key = (33 * key + *name) & (tabsize - 1);
55 }
56 return key;
57 }
58
59
60 void
new_make_hash_table(struct sym_hash_table * tab,int size)61 new_make_hash_table(struct sym_hash_table *tab, int size) {
62 int nbytes = size * sizeof *tab->hash_slots_head;
63
64 #if FAST_SYMBOL_LOOKUP
65 abort();
66 #endif
67 tab->n_hash_slots = size;
68
69 tab->hash_slots_head = n_xmalloc(nbytes);
70 tab->hash_slots_tail = n_xmalloc(nbytes);
71 memset(tab->hash_slots_head, 0, nbytes);
72 memset(tab->hash_slots_tail, 0, nbytes);
73 tab->used = 1;
74 }
75
76
77 void
dump_hash_table(struct sym_hash_table * htab)78 dump_hash_table(struct sym_hash_table *htab) {
79 int i;
80
81 printf(" === Dumping symbol hash table %p === \n", htab);
82 for (i = 0; i < htab->n_hash_slots; ++i) {
83 if (htab->hash_slots_head[i] != NULL) {
84 struct sym_entry *se;
85
86 printf(" Slot %d:\n", i);
87 for (se = htab->hash_slots_head[i];
88 se != NULL;
89 se = se->next) {
90 printf(" %p, %p = %s (prev = %p)\n",
91 se, se->dec, se->dec->dtype->name, se->prev);
92 }
93 }
94 }
95 }
96
97 void
new_put_hash_table(struct sym_hash_table * htab,struct sym_entry * item)98 new_put_hash_table(struct sym_hash_table *htab, struct sym_entry *item) {
99 int key = hash_symbol(item->name, htab->n_hash_slots);
100
101 #if FAST_SYMBOL_LOOKUP
102 abort();
103 #endif
104 /*
105 * CANOFWORMS 03/27/08: This was missing the prev assignments!
106 * Seems too obvious to be missed, so maybe this breaks something?
107 * But then unlinking hadn't been used before so maybe that's why
108 */
109 if (htab->hash_slots_head[key] == NULL) {
110 htab->hash_slots_head[key] = item;
111 htab->hash_slots_tail[key] = item;
112 item->prev = NULL;
113 } else {
114 item->prev = htab->hash_slots_tail[key];
115 htab->hash_slots_tail[key]->next = item;
116 htab->hash_slots_tail[key] = item;
117 }
118 }
119
120 struct sym_entry *
new_lookup_hash(struct sym_hash_table * htab,const char * name,size_t len)121 new_lookup_hash(struct sym_hash_table *htab, const char *name, size_t len) {
122 int key = hash_symbol(name, htab->n_hash_slots);
123 struct sym_entry *hp;
124
125 (void) len;
126
127 #if FAST_SYMBOL_LOOKUP
128 abort();
129 #endif
130
131 for (hp = htab->hash_slots_head[key]; hp != NULL; hp = hp->next) {
132 #if 0
133 if (hp->item->namelen == len) {
134 #endif
135 /* 04/08/08: Shadow declarations */
136 if (hp->inactive
137 || (hp->dec->invalid && !is_shadow_decl(hp->dec))) {
138 continue;
139 }
140 if (strcmp(hp->name, name) == 0) {
141 return hp;
142 }
143 }
144 return NULL;
145 }
146
147 struct sym_entry *
148 make_sym_entry(struct decl *dec) {
149 struct sym_entry *s;
150 static struct sym_entry nullentry;
151
152 s = n_xmalloc(sizeof *s);
153 *s = nullentry;
154 s->name = dec->dtype->name;
155 s->inactive = 0;
156 if (s->name != NULL) {
157 s->namelen = strlen(dec->dtype->name);
158 } else {
159 s->namelen = 0;
160 }
161 s->dec = dec;
162 s->next = NULL;
163 s->prev = NULL;
164 return s;
165 }
166
167
168 void
169 append_symlist(
170 struct scope *scope,
171 struct sym_entry **head,
172 struct sym_entry **tail,
173 struct decl *dec) {
174
175 struct sym_entry *s;
176
177 s = make_sym_entry(dec);
178 if (scope != NULL && scope->type != SCOPE_STRUCT) {
179 /* XXX this stuff does not belong here! it should go to
180 * new_scope() or something
181 */
182 #if ! FAST_SYMBOL_LOOKUP
183 if (!scope->sym_hash.used) {
184 if (scope == &global_scope) {
185 #if 0
186 scope->sym_hash = n_xmalloc(64 * sizeof *scope->sym_hash);
187 scope->n_hash_slots = 63;
188 memset(scope->sym_hash, 0, 64 * sizeof *scope->sym_hash);
189 #endif
190 new_make_hash_table(&scope->sym_hash,
191 SYM_HTAB_GLOBAL_SCOPE);
192 #if 0
193 } else if (scope->parent == NULL
194 || scope->parent->parent == NULL) {
195 new_make_hash_table(&scope->sym_hash,
196 SYM_HTAB_FUNC_TOP_BLOCK);
197 #endif
198 }
199 }
200 #endif
201 }
202
203 #if FAST_SYMBOL_LOOKUP
204 if (s->name != NULL) {
205 put_fast_sym_hash(scope, s, 0);
206 }
207 #endif
208 if (scope && scope->sym_hash.used) {
209 #if FAST_SYMBOL_LOOKUP
210 abort();
211 #endif
212 if (s->name != NULL) {
213 new_put_hash_table(&scope->sym_hash, s);
214 }
215 } else {
216 if (*head == NULL) {
217 *head = *tail = s;
218 } else {
219 (*tail)->next = s;
220 s->prev = *tail;
221 *tail = s;
222 }
223 }
224 }
225
226 void
227 remove_symlist(struct scope *s, struct sym_entry *se) {
228 if (se->next == NULL) {
229 /*
230 * 03/11/09: Removing tail. This missing assignment
231 * was probably not noticed because we use a hash
232 * table for the global scope
233 */
234 s->slist_tail = se->prev;
235 }
236
237 if (se->prev != NULL && !s->sym_hash.used) {
238 /* Symbol hash not used */
239 se->prev->next = se->next;
240 } else {
241 /* Is first in list! */
242 if (s->sym_hash.used) {
243 int key;
244 struct sym_hash_table *htab;
245
246 htab = &s->sym_hash;
247
248 /*
249 * 03/27/08: XXX VERY dangerous!!! We always have
250 * to hash with se->name instead of se->dec->dtype->name
251 * since in case of static variables, se->name may
252 * be ``foo'' whereas the other is ``_Static_foo0''. If
253 * we change this, remember that the append_symlist()
254 * takes place when se->dec->dtype->name has not been
255 * updated with that name mangling stuff yet
256 */
257 key = hash_symbol(se->name,
258 htab->n_hash_slots);
259 if (se->prev != NULL) {
260 se->prev->next = se->next;
261 } else {
262 /* Was first node */
263 htab->hash_slots_head[key] = se->next;
264 }
265
266 if (se->next != NULL) {
267 se->next->prev = se->prev;
268 } else {
269 /* Was last node */
270 htab->hash_slots_tail[key] = se->prev;
271 }
272 return;
273 } else {
274 s->slist = se->next;
275 }
276 }
277
278 if (se->next != NULL) {
279 se->next->prev = se->prev;
280 }
281 }
282
283 #if FAST_SYMBOL_LOOKUP
284
285 #define N_GLOBAL_FAST_TAB_ENTRIES 256
286 #define N_LOCAL_FAST_TAB_ENTRIES 64
287
288 static struct fast_sym_hash_entry *global_fast_sym_hash_head[N_GLOBAL_FAST_TAB_ENTRIES];
289 static struct fast_sym_hash_entry *global_fast_sym_hash_tail[N_GLOBAL_FAST_TAB_ENTRIES];
290 static struct fast_sym_hash_entry *local_fast_sym_hash_head[N_LOCAL_FAST_TAB_ENTRIES];
291 static struct fast_sym_hash_entry *local_fast_sym_hash_tail[N_LOCAL_FAST_TAB_ENTRIES];
292
293
294 static unsigned
295 hash_fast_sym_name_base(const char *name, int *len) {
296 const char *origname = name;
297 unsigned key = 0;
298
299 for (; *name != 0; ++name) {
300 key = key * 33 + *name;
301 }
302 *len = name - origname;
303 return key;
304 }
305
306
307
308 void
309 put_fast_sym_hash(struct scope *s, struct sym_entry *se, int is_typedef) {
310 struct fast_sym_hash_entry *ent;
311 unsigned idx;
312 int namelen;
313
314 if (s == &global_scope) {
315 /* Global identifier - persistent */
316 ent = n_xmalloc(sizeof *ent);
317 idx = hash_fast_sym_name_base(se->dec->dtype->name, &namelen);
318 idx &= (N_GLOBAL_FAST_TAB_ENTRIES - 1);
319 } else {
320 /* Local identifier - can be cleared at end of function */
321 ent = zalloc_buf(Z_FASTSYMHASH);
322 idx = hash_fast_sym_name_base(se->dec->dtype->name, &namelen);
323 idx &= (N_LOCAL_FAST_TAB_ENTRIES - 1);
324 }
325
326 ent->se = se;
327 ent->name = se->dec->dtype->name;
328 ent->namelen = namelen;
329 ent->scope = s;
330 ent->is_typedef = is_typedef;
331 ent->next = NULL;
332
333
334 /*
335 * XXX Currently this will get called twice for extern symbols - once for
336 * the per-scope list, and once for the global extern list. Do we really
337 * want that? Possibly we do if either of them is invalidated due to a
338 * redeclaration so it may be better to keep both around
339 */
340 if (s == &global_scope) {
341 if (global_fast_sym_hash_head[idx] == NULL) {
342 global_fast_sym_hash_head[idx]
343 = global_fast_sym_hash_tail[idx]
344 = ent;
345 } else {
346 global_fast_sym_hash_tail[idx]->next = ent;
347 global_fast_sym_hash_tail[idx] = ent;
348 }
349 } else {
350 if (local_fast_sym_hash_head[idx] == NULL) {
351 local_fast_sym_hash_head[idx]
352 = local_fast_sym_hash_tail[idx]
353 = ent;
354 } else {
355 local_fast_sym_hash_tail[idx]->next = ent;
356 local_fast_sym_hash_tail[idx] = ent;
357 }
358 }
359 }
360
361 void
362 reset_fast_sym_hash(void) {
363 memset(local_fast_sym_hash_head, 0, sizeof local_fast_sym_hash_head);
364 memset(local_fast_sym_hash_tail, 0, sizeof local_fast_sym_hash_tail);
365 }
366
367
368 static int
369 is_valid_match(struct sym_entry *se, int is_typedef, int want_typedef, int *err) {
370 if (err != NULL) {
371 *err = 0;
372 }
373 if (se->dec->invalid && !is_shadow_decl(se->dec)) {
374 return 0;
375 }
376 if (se->inactive) {
377 return 0;
378 }
379
380 if (want_typedef != is_typedef) {
381 /*
382 * We got a typedef but didn't
383 * want it or the other way
384 * around
385 */
386 if (err != NULL) {
387 *err = 0;
388 }
389 return 0;
390 }
391 return 1;
392 }
393
394
395 struct sym_entry *
396 fast_lookup_symbol_se(struct scope *s, const char *name, int nested, int want_typedef) {
397 unsigned idx;
398 unsigned local_idx;
399 unsigned global_idx;
400 int len;
401 int err;
402 struct scope *tempscope;
403 struct fast_sym_hash_entry *ent;
404
405 local_idx = global_idx = hash_fast_sym_name_base(name, &len);
406 local_idx &= (N_LOCAL_FAST_TAB_ENTRIES - 1);
407 global_idx &= (N_GLOBAL_FAST_TAB_ENTRIES - 1);
408
409 /*
410 * Try local list first - if we are looking up in a local scope
411 */
412 if (s != &global_scope && local_fast_sym_hash_head[local_idx] != NULL) {
413 struct fast_sym_hash_entry *matches[128];
414 int matchidx = 0;
415
416 /*
417 * First do a linear search for the current scope and
418 * record all matches of the same name. If we find a
419 * match in the current scope, we are done. If we
420 * don't, we only have to traverse the recorded
421 * matches for all parent scopes in order to find the
422 * first match
423 */
424 for (ent = local_fast_sym_hash_head[local_idx];
425 ent != NULL;
426 ent = ent->next) {
427 if (ent->namelen == len
428 && strcmp(ent->name, name) == 0) {
429 struct sym_entry *se = ent->se;
430
431 if (ent->scope == s) {
432 /* Perfect match? */
433 if (!is_valid_match(se,
434 ent->is_typedef,
435 want_typedef,
436 NULL)) {
437 return NULL;
438 }
439
440 /* Yes! */
441 return se;
442 } else {
443 /* Match in other scope */
444 matches[matchidx++] = ent;
445 }
446 }
447 }
448
449 if (nested == 0) {
450 /*
451 * We are only interested in a match for the
452 * current scope, and there's none
453 */
454 return NULL;
455 } else if (matchidx > 0) {
456 /*
457 * There are matches for parent scopes
458 */
459 int i;
460
461 while ((s = s->parent) != NULL /* XXX needed?!? */
462 && s != &global_scope) {
463 for (i = 0; i < matchidx; ++i) {
464 if (matches[i]->scope == s) {
465 if (!is_valid_match(
466 matches[i]->se,
467 matches[i]->is_typedef,
468 want_typedef,
469 NULL)) {
470 return NULL;
471 } else {
472 return matches[i]->se;
473 }
474 }
475 }
476 }
477 }
478 }
479 if (s != &global_scope && nested == 0) {
480 /*
481 * We are only interested in a match for the
482 * current scope, and there's none
483 */
484 return NULL;
485 }
486
487 /* No match in local scopes - fall back to global */
488 if (global_fast_sym_hash_head[global_idx] != NULL) {
489 for (ent = global_fast_sym_hash_head[global_idx];
490 ent != NULL;
491 ent = ent->next) {
492 if (ent->namelen == len
493 && strcmp(ent->name, name) == 0) {
494 struct sym_entry *se = ent->se;
495
496 if (!is_valid_match(se,
497 ent->is_typedef,
498 want_typedef,
499 &err)) {
500 if (!err) {
501 /*
502 * This may be an invalidated
503 * declaration, i.e. overridden
504 * by a subsequent tentative
505 * declaration. So continue
506 * searching
507 */
508 continue;
509 }
510 }
511 return se;
512 }
513 }
514 }
515 return NULL;
516 }
517
518 #endif
519
520 #if 0
521 struct sym_entry *
522 lookup_hash(struct hash_node **tab, size_t nslots,
523 const char *name, size_t len) {
524
525 struct hash_node *hn;
526 struct sym_entry *se;
527
528 if (len >= nslots) {
529 hn = tab[nslots];
530 } else {
531 hn = tab[len - 1];
532 }
533
534 if (hn == NULL) {
535 return NULL;
536 }
537 for (;;) {
538 se = hn->item;
539 if (se->name[0] != name[0]) {
540 hn = hn->skip;
541 } else if (strcmp(se->name, name) != 0) {
542 hn = hn->next;
543 } else {
544 /* Found */
545 return se;
546 }
547 if (hn == NULL) {
548 break;
549 }
550 }
551 /* NOTREACHED */
552 return NULL;
553 }
554 #endif
555
556