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 */ 6 7 #ifndef lint 8 static char sccsid[] = "@(#)symtab.c 5.1 (Berkeley) 06/06/85"; 9 #endif not lint 10 11 /* 12 * Symbol table implementation. 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 /* 22 * The symbol table structure is currently assumes no deletions. 23 */ 24 25 #define MAXHASHSIZE 1009 /* largest allowable hash table */ 26 27 struct symtab { 28 int size; 29 int hshsize; 30 SYM **symhsh; 31 SYM *symarray; 32 int symindex; 33 }; 34 35 /* 36 * Macro to hash a string. 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 { \ 45 register char *cp; \ 46 \ 47 h = 0; \ 48 for (cp = name; *cp != '\0'; cp++) { \ 49 h = (h << 1) | (*cp); \ 50 } \ 51 h %= st->hshsize; \ 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 { 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); 78 } 79 80 st_destroy(st) 81 SYMTAB *st; 82 { 83 dispose(st->symhsh); 84 dispose(st->symarray); 85 dispose(st); 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 { 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); 113 } 114 115 /* 116 * symbol lookup 117 */ 118 119 SYM *st_lookup(st, name) 120 SYMTAB *st; 121 char *name; 122 { 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; 133 } 134 } 135 return(s); 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 { 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'); 160 } 161 } 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 { 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; 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 { 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); 207 } 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 } 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 225 #define NSYMS_BACK 20 /* size of local context to try */ 226 227 LOCAL SYM *search(); 228 229 SYM *findtype(t) 230 SYM *t; 231 { 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); 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 { 256 register SYM *s; 257 258 for (s = first; s <= last; s++) { 259 if (s->class == TYPE && s->type == t && s->symbol != NIL) { 260 return(s); 261 } 262 } 263 return(NIL); 264 } 265