1 /*-
2 * Copyright (c) 1980, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * %sccs.include.redist.c%
6 */
7
8 #ifndef lint
9 static char sccsid[] = "@(#)symtab.c 8.1 (Berkeley) 06/06/93";
10 #endif /* not lint */
11
12 /*
13 * Symbol table implementation.
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 /*
23 * The symbol table structure is currently assumes no deletions.
24 */
25
26 #define MAXHASHSIZE 1009 /* largest allowable hash table */
27
28 struct symtab {
29 int size;
30 int hshsize;
31 SYM **symhsh;
32 SYM *symarray;
33 int symindex;
34 };
35
36 /*
37 * Macro to hash a string.
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 { \
46 register char *cp; \
47 \
48 h = 0; \
49 for (cp = name; *cp != '\0'; cp++) { \
50 h = (h << 1) | (*cp); \
51 } \
52 h %= st->hshsize; \
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
st_creat(size)60 SYMTAB *st_creat(size)
61 int size;
62 {
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);
79 }
80
st_destroy(st)81 st_destroy(st)
82 SYMTAB *st;
83 {
84 dispose(st->symhsh);
85 dispose(st->symarray);
86 dispose(st);
87 }
88
89 /*
90 * insert a symbol into a table
91 */
92
st_insert(st,name)93 SYM *st_insert(st, name)
94 register SYMTAB *st;
95 char *name;
96 {
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);
114 }
115
116 /*
117 * symbol lookup
118 */
119
st_lookup(st,name)120 SYM *st_lookup(st, name)
121 SYMTAB *st;
122 char *name;
123 {
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;
134 }
135 }
136 return(s);
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
dumpvars(f,frame)148 dumpvars(f, frame)
149 SYM *f;
150 FRAME *frame;
151 {
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');
161 }
162 }
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
enter_alias(table,new,old)172 enter_alias(table, new, old)
173 SYMTAB *table;
174 char *new, *old;
175 {
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;
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
print_alias(table,name)197 print_alias(table, name)
198 SYMTAB *table;
199 char *name;
200 {
201 SYM *s;
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);
208 }
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 }
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
226 #define NSYMS_BACK 20 /* size of local context to try */
227
228 LOCAL SYM *search();
229
findtype(t)230 SYM *findtype(t)
231 SYM *t;
232 {
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);
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
search(t,first,last)253 LOCAL SYM *search(t, first, last)
254 SYM *t;
255 register SYM *first, *last;
256 {
257 register SYM *s;
258
259 for (s = first; s <= last; s++) {
260 if (s->class == TYPE && s->type == t && s->symbol != NIL) {
261 return(s);
262 }
263 }
264 return(NIL);
265 }
266