2.9BSD - /usr/src/ucb/pascal/pi/hash.c

   1: /*	@(#)hash.c	2.3	SCCS id keyword	*/
   2: /* Copyright (c) 1979 Regents of the University of California */
   3: #
   4: /*
   5:  * pi - Pascal interpreter code translator
   6:  *
   7:  * Charles Haley, Bill Joy UCB
   8:  * Version 1.2 November 1978
   9:  *
  10:  *
  11:  * pxp - Pascal execution profiler
  12:  *
  13:  * Bill Joy UCB
  14:  * Version 1.2 November 1978
  15:  */
  16: 
  17: #include "whoami"
  18: #include "0.h"
  19: #include "yy.h"
  20: 
  21: /*
  22:  * The definition for the segmented hash tables.
  23:  */
  24: struct ht {
  25:     int *ht_low;
  26:     int *ht_high;
  27:     int ht_used;
  28: } htab[MAXHASH];
  29: 
  30: /*
  31:  * This is the array of keywords and their
  32:  * token values, which are hashed into the table
  33:  * by inithash.
  34:  */
  35: struct kwtab yykey[] = {
  36:     "and",      YAND,
  37:     "array",    YARRAY,
  38:     "assert",   YASSERT,
  39:     "begin",    YBEGIN,
  40:     "case",     YCASE,
  41:     "const",    YCONST,
  42:     "div",      YDIV,
  43:     "do",       YDO,
  44:     "downto",   YDOWNTO,
  45:     "else",     YELSE,
  46:     "end",      YEND,
  47:     "file",     YFILE,
  48:     "for",      YFOR,
  49:     "forward",  YFORWARD,
  50:     "function", YFUNCTION,
  51:     "goto",     YGOTO,
  52:     "if",       YIF,
  53:     "in",       YIN,
  54:     "label",    YLABEL,
  55:     "mod",      YMOD,
  56:     "nil",      YNIL,
  57:     "not",      YNOT,
  58:     "of",       YOF,
  59:     "or",       YOR,
  60:     "packed",   YPACKED,
  61:     "procedure",    YPROCEDURE,
  62:     "program",  YPROG,
  63:     "record",   YRECORD,
  64:     "repeat",   YREPEAT,
  65:     "set",      YSET,
  66:     "then",     YTHEN,
  67:     "to",       YTO,
  68:     "type",     YTYPE,
  69:     "until",    YUNTIL,
  70:     "var",      YVAR,
  71:     "while",    YWHILE,
  72:     "with",     YWITH,
  73:     "oct",      YOCT,    /* non-standard Pascal */
  74:     "hex",      YHEX,    /* non-standard Pascal */
  75:     0
  76: };
  77: 
  78: char    *lastkey    = &yykey[sizeof yykey/sizeof yykey[0]];
  79: 
  80: /*
  81:  * Inithash initializes the hash table routines
  82:  * by allocating the first hash table segment using
  83:  * an already existing memory slot.
  84:  */
  85: #ifndef PI0
  86: inithash()
  87: #else
  88: inithash(hshtab)
  89:     int *hshtab;
  90: #endif
  91: {
  92:     register int *ip;
  93: #ifndef PI0
  94:     static int hshtab[HASHINC];
  95: #endif
  96: 
  97:     htab[0].ht_low = hshtab;
  98:     htab[0].ht_high = &hshtab[HASHINC];
  99:     for (ip = yykey; *ip; ip += 2)
 100:         hash(ip[0], 0)[0] = ip;
 101: }
 102: 
 103: /*
 104:  * Hash looks up the s(ymbol) argument
 105:  * in the string table, entering it if
 106:  * it is not found. If save is 0, then
 107:  * the argument string is already in
 108:  * a safe place. Otherwise, if hash is
 109:  * entering the symbol for the first time
 110:  * it will save the symbol in the string
 111:  * table using savestr.
 112:  */
 113: int *hash(s, save)
 114:     char *s;
 115:     int save;
 116: {
 117:     register int *h;
 118:     register i;
 119:     register char *cp;
 120:     int *sym;
 121:     struct ht *htp;
 122:     int sh;
 123: 
 124:     /*
 125: 	 * The hash function is a modular hash of
 126: 	 * the sum of the characters with the sum
 127: 	 * doubled before each successive character
 128: 	 * is added.
 129: 	 */
 130:     cp = s;
 131:     if (cp == NIL)
 132:         cp = token; /* default symbol to be hashed */
 133:     i = 0;
 134:     while (*cp)
 135:         i = i*2 + *cp++;
 136:     sh = (i&077777) % HASHINC;
 137:     cp = s;
 138:     if (cp == NIL)
 139:         cp = token;
 140:     /*
 141: 	 * There are as many as MAXHASH active
 142: 	 * hash tables at any given point in time.
 143: 	 * The search starts with the first table
 144: 	 * and continues through the active tables
 145: 	 * as necessary.
 146: 	 */
 147:     for (htp = htab; htp < &htab[MAXHASH]; htp++) {
 148:         if (htp->ht_low == NIL) {
 149:             cp = (char *) calloc(sizeof ( int * ), HASHINC);
 150:             if (cp == 0) {
 151:                 yerror("Ran out of memory (hash)");
 152:                 pexit(DIED);
 153:             }
 154:             htp->ht_low = cp;
 155:             htp->ht_high = htp->ht_low + HASHINC;
 156:             cp = s;
 157:             if (cp == NIL)
 158:                 cp = token;
 159:         }
 160:         h = htp->ht_low + sh;
 161:         /*
 162: 		 * quadratic rehash increment
 163: 		 * starts at 1 and incremented
 164: 		 * by two each rehash.
 165: 		 */
 166:         i = 1;
 167:         do {
 168:             if (*h == 0) {
 169:                 if (htp->ht_used > (HASHINC * 3)/4)
 170:                     break;
 171:                 htp->ht_used++;
 172:                 if (save != 0) {
 173:                     *h = (int) savestr(cp);
 174:                 } else
 175:                     *h = s;
 176:                 return (h);
 177:             }
 178:             sym = *h;
 179:             if (sym < lastkey && sym >= yykey)
 180:                 sym = *sym;
 181:             if (sym->pchar == *cp && strcmp(sym, cp) == 0)
 182:                 return (h);
 183:             h += i;
 184:             i += 2;
 185:             if (h >= htp->ht_high)
 186:                 h -= HASHINC;
 187:         } while (i < HASHINC);
 188:     }
 189:     yerror("Ran out of hash tables");
 190:     pexit(DIED);
 191: }

Defined functions

Defined variables

Defined struct's