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