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