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

Defined functions

Defined variables

Defined struct's