Commit | Line | Data |
---|---|---|
505bf312 KB |
1 | /*- |
2 | * Copyright (c) 1980 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * %sccs.include.redist.c% | |
3cd5310a | 6 | */ |
f5632b7a | 7 | |
3cd5310a | 8 | #ifndef lint |
505bf312 KB |
9 | static char sccsid[] = "@(#)symtab.c 5.3 (Berkeley) %G%"; |
10 | #endif /* not lint */ | |
f5632b7a ML |
11 | |
12 | /* | |
91955a86 | 13 | * Symbol table implementation. |
f5632b7a ML |
14 | */ |
15 | ||
16 | #include "defs.h" | |
17 | #include "symtab.h" | |
18 | #include "sym.h" | |
19 | #include "sym/classes.h" | |
20 | #include "sym/sym.rep" | |
21 | ||
22 | /* | |
91955a86 | 23 | * The symbol table structure is currently assumes no deletions. |
f5632b7a ML |
24 | */ |
25 | ||
91955a86 | 26 | #define MAXHASHSIZE 1009 /* largest allowable hash table */ |
f5632b7a ML |
27 | |
28 | struct symtab { | |
91955a86 ML |
29 | int size; |
30 | int hshsize; | |
31 | SYM **symhsh; | |
32 | SYM *symarray; | |
33 | int symindex; | |
f5632b7a ML |
34 | }; |
35 | ||
36 | /* | |
91955a86 | 37 | * Macro to hash a string. |
f5632b7a ML |
38 | * |
39 | * The hash value is returned through the "h" parameter which should | |
40 | * an unsigned integer. The other parameters are the symbol table, "st", | |
41 | * and a pointer to the string to be hashed, "name". | |
42 | */ | |
43 | ||
44 | #define hash(h, st, name) \ | |
45 | { \ | |
91955a86 | 46 | register char *cp; \ |
f5632b7a | 47 | \ |
91955a86 ML |
48 | h = 0; \ |
49 | for (cp = name; *cp != '\0'; cp++) { \ | |
50 | h = (h << 1) | (*cp); \ | |
51 | } \ | |
52 | h %= st->hshsize; \ | |
f5632b7a ML |
53 | } |
54 | ||
55 | /* | |
56 | * To create a symbol table, we allocate space for the symbols and | |
57 | * for a hash table that's twice as big (+1 to make it odd). | |
58 | */ | |
59 | ||
60 | SYMTAB *st_creat(size) | |
61 | int size; | |
62 | { | |
91955a86 ML |
63 | register SYMTAB *st; |
64 | register int i; | |
65 | ||
66 | st = alloc(1, SYMTAB); | |
67 | st->size = size; | |
68 | st->hshsize = 2*size + 1; | |
69 | if (st->hshsize > MAXHASHSIZE) { | |
70 | st->hshsize = MAXHASHSIZE; | |
71 | } | |
72 | st->symhsh = alloc(st->hshsize, SYM *); | |
73 | st->symarray = alloc(st->size, SYM); | |
74 | st->symindex = 0; | |
75 | for (i = 0; i < st->hshsize; i++) { | |
76 | st->symhsh[i] = NIL; | |
77 | } | |
78 | return(st); | |
f5632b7a ML |
79 | } |
80 | ||
81 | st_destroy(st) | |
82 | SYMTAB *st; | |
83 | { | |
91955a86 ML |
84 | dispose(st->symhsh); |
85 | dispose(st->symarray); | |
86 | dispose(st); | |
f5632b7a ML |
87 | } |
88 | ||
89 | /* | |
90 | * insert a symbol into a table | |
91 | */ | |
92 | ||
93 | SYM *st_insert(st, name) | |
94 | register SYMTAB *st; | |
95 | char *name; | |
96 | { | |
91955a86 ML |
97 | register SYM *s; |
98 | register unsigned int h; | |
99 | static SYM zerosym; | |
100 | ||
101 | if (st == NIL) { | |
102 | panic("tried to insert into NIL table"); | |
103 | } | |
104 | if (st->symindex >= st->size) { | |
105 | panic("too many symbols"); | |
106 | } | |
107 | hash(h, st, name); | |
108 | s = &(st->symarray[st->symindex++]); | |
109 | *s = zerosym; | |
110 | s->symbol = name; | |
111 | s->next_sym = st->symhsh[h]; | |
112 | st->symhsh[h] = s; | |
113 | return(s); | |
f5632b7a ML |
114 | } |
115 | ||
116 | /* | |
117 | * symbol lookup | |
118 | */ | |
119 | ||
120 | SYM *st_lookup(st, name) | |
121 | SYMTAB *st; | |
122 | char *name; | |
123 | { | |
91955a86 ML |
124 | register SYM *s; |
125 | register unsigned int h; | |
126 | ||
127 | if (st == NIL) { | |
128 | panic("tried to lookup in NIL table"); | |
129 | } | |
130 | hash(h, st, name); | |
131 | for (s = st->symhsh[h]; s != NIL; s = s->next_sym) { | |
132 | if (strcmp(s->symbol, name) == 0) { | |
133 | break; | |
f5632b7a | 134 | } |
91955a86 ML |
135 | } |
136 | return(s); | |
f5632b7a ML |
137 | } |
138 | ||
139 | /* | |
140 | * Dump out all the variables associated with the given | |
141 | * procedure, function, or program at the given recursive level. | |
142 | * | |
143 | * This is quite inefficient. We traverse the entire symbol table | |
144 | * each time we're called. The assumption is that this routine | |
145 | * won't be called frequently enough to merit improved performance. | |
146 | */ | |
147 | ||
148 | dumpvars(f, frame) | |
149 | SYM *f; | |
150 | FRAME *frame; | |
151 | { | |
91955a86 ML |
152 | register SYM *s; |
153 | SYM *first, *last; | |
154 | ||
155 | first = symtab->symarray; | |
156 | last = first + symtab->symindex - 1; | |
157 | for (s = first; s <= last; s++) { | |
158 | if (should_print(s, f)) { | |
159 | printv(s, frame); | |
160 | putchar('\n'); | |
f5632b7a | 161 | } |
91955a86 | 162 | } |
f5632b7a ML |
163 | } |
164 | ||
165 | /* | |
166 | * Create an alias for a command. | |
167 | * | |
168 | * We put it into the given table with block 1, which is how it | |
169 | * is distinguished for printing purposes. | |
170 | */ | |
171 | ||
172 | enter_alias(table, new, old) | |
173 | SYMTAB *table; | |
174 | char *new, *old; | |
175 | { | |
91955a86 ML |
176 | SYM *s, *t; |
177 | ||
178 | if ((s = st_lookup(table, old)) == NIL) { | |
179 | error("%s is not a known command", old); | |
180 | } | |
181 | if (st_lookup(table, new) != NIL) { | |
182 | error("cannot alias command names"); | |
183 | } | |
184 | make_keyword(table, new, s->symvalue.token.toknum); | |
185 | t = st_insert(table, new); | |
186 | t->blkno = 1; | |
187 | t->symvalue.token.toknum = s->symvalue.token.toknum; | |
188 | t->type = s; | |
f5632b7a ML |
189 | } |
190 | ||
191 | /* | |
192 | * Print out the currently active aliases. | |
193 | * The kludge is that the type pointer for an alias points to the | |
194 | * symbol it is aliased to. | |
195 | */ | |
196 | ||
197 | print_alias(table, name) | |
198 | SYMTAB *table; | |
199 | char *name; | |
200 | { | |
82d3cd01 | 201 | SYM *s; |
91955a86 ML |
202 | SYM *first, *last; |
203 | ||
204 | if (name != NIL) { | |
205 | s = st_lookup(table, name); | |
206 | if (s == NIL) { | |
207 | error("\"%s\" is not an alias", name); | |
f5632b7a | 208 | } |
91955a86 ML |
209 | printf("%s\n", s->type->symbol); |
210 | } else { | |
211 | first = table->symarray; | |
212 | last = first + table->symindex - 1; | |
213 | for (s = first; s <= last; s++) { | |
214 | if (s->blkno == 1) { | |
215 | printf("%s\t%s\n", s->symbol, s->type->symbol); | |
216 | } | |
217 | } | |
218 | } | |
f5632b7a ML |
219 | } |
220 | ||
221 | /* | |
222 | * Find a named type that points to t; return NIL if there is none. | |
223 | * This is necessary because of the way pi keeps symbols. | |
224 | */ | |
225 | ||
91955a86 | 226 | #define NSYMS_BACK 20 /* size of local context to try */ |
f5632b7a ML |
227 | |
228 | LOCAL SYM *search(); | |
229 | ||
230 | SYM *findtype(t) | |
231 | SYM *t; | |
232 | { | |
91955a86 ML |
233 | SYM *s; |
234 | SYM *first, *last; | |
235 | SYM *lower; | |
236 | ||
237 | first = symtab->symarray; | |
238 | last = first + symtab->symindex - 1; | |
239 | if ((lower = t - NSYMS_BACK) < first) { | |
240 | lower = first; | |
241 | } | |
242 | if ((s = search(t, lower, last)) == NIL) { | |
243 | s = search(t, first, last); | |
244 | } | |
245 | return(s); | |
f5632b7a ML |
246 | } |
247 | ||
248 | /* | |
249 | * Search the symbol table from first to last, looking for a | |
250 | * named type pointing to the given type symbol. | |
251 | */ | |
252 | ||
253 | LOCAL SYM *search(t, first, last) | |
254 | SYM *t; | |
255 | register SYM *first, *last; | |
256 | { | |
91955a86 | 257 | register SYM *s; |
f5632b7a | 258 | |
91955a86 ML |
259 | for (s = first; s <= last; s++) { |
260 | if (s->class == TYPE && s->type == t && s->symbol != NIL) { | |
261 | return(s); | |
f5632b7a | 262 | } |
91955a86 ML |
263 | } |
264 | return(NIL); | |
f5632b7a | 265 | } |