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