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 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 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 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 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 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 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 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 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 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