2.11BSD#431 - /usr/src/ucb/pascal/pxp/hash.c

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

Defined functions

Defined variables

Defined struct's