4.3BSD - /usr/src/ucb/pascal/pdx/symtab/symtab.c

   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) 6/6/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: }

Defined functions

Defined variables

Defined struct's

Defined macros