1755Speter /* Copyright (c) 1979 Regents of the University of California */ 2755Speter 3*14733Sthien #ifndef lint 4*14733Sthien static char sccsid[] = "@(#)hash.c 1.5 08/19/83"; 5*14733Sthien #endif 6755Speter 7755Speter #include "whoami.h" 8755Speter #include "0.h" 9*14733Sthien #include "tree_ty.h" /* must be included for yy.h */ 10755Speter #include "yy.h" 11755Speter 12755Speter /* 13755Speter * The definition for the segmented hash tables. 14755Speter */ 15755Speter struct ht { 16755Speter int *ht_low; 17755Speter int *ht_high; 18755Speter int ht_used; 19755Speter } htab[MAXHASH]; 20755Speter 21755Speter /* 22755Speter * This is the array of keywords and their 23755Speter * token values, which are hashed into the table 24755Speter * by inithash. 25755Speter */ 26755Speter struct kwtab yykey[] = { 27755Speter "and", YAND, 28755Speter "array", YARRAY, 29755Speter "begin", YBEGIN, 30755Speter "case", YCASE, 31755Speter "const", YCONST, 32755Speter "div", YDIV, 33755Speter "do", YDO, 34755Speter "downto", YDOWNTO, 35755Speter "else", YELSE, 36755Speter "end", YEND, 37755Speter "file", YFILE, 38755Speter "for", YFOR, 39755Speter "forward", YFORWARD, 40755Speter "function", YFUNCTION, 41755Speter "goto", YGOTO, 42755Speter "if", YIF, 43755Speter "in", YIN, 44755Speter "label", YLABEL, 45755Speter "mod", YMOD, 46755Speter "nil", YNIL, 47755Speter "not", YNOT, 48755Speter "of", YOF, 49755Speter "or", YOR, 50755Speter "packed", YPACKED, 51755Speter "procedure", YPROCEDURE, 52755Speter "program", YPROG, 53755Speter "record", YRECORD, 54755Speter "repeat", YREPEAT, 55755Speter "set", YSET, 56755Speter "then", YTHEN, 57755Speter "to", YTO, 58755Speter "type", YTYPE, 59755Speter "until", YUNTIL, 60755Speter "var", YVAR, 61755Speter "while", YWHILE, 62755Speter "with", YWITH, 637955Smckusick 0, 0, /* the following keywords are non-standard */ 647955Smckusick "oct", YOCT, 657955Smckusick "hex", YHEX, 667955Smckusick "external", YEXTERN, 67755Speter 0 68755Speter }; 69755Speter 707955Smckusick char *lastkey; 71755Speter 72755Speter /* 73755Speter * Inithash initializes the hash table routines 74755Speter * by allocating the first hash table segment using 75755Speter * an already existing memory slot. 76755Speter */ 77755Speter #ifndef PI0 78755Speter inithash() 79755Speter #else 80755Speter inithash(hshtab) 81755Speter int *hshtab; 82755Speter #endif 83755Speter { 84755Speter register int *ip; 85755Speter #ifndef PI0 86755Speter static int hshtab[HASHINC]; 87755Speter #endif 88755Speter 89755Speter htab[0].ht_low = hshtab; 90755Speter htab[0].ht_high = &hshtab[HASHINC]; 91*14733Sthien for (ip = ((int *)yykey); *ip; ip += 2) 92*14733Sthien hash((char *) ip[0], 0)[0] = ((int) ip); 937955Smckusick /* 947955Smckusick * If we are not running in "standard-only" mode, 957955Smckusick * we load the non-standard keywords. 967955Smckusick */ 977955Smckusick if (!opt('s')) 987955Smckusick for (ip += 2; *ip; ip += 2) 99*14733Sthien hash((char *) ip[0], 0)[0] = ((int) ip); 1007955Smckusick lastkey = (char *)ip; 101755Speter } 102755Speter 103755Speter /* 104755Speter * Hash looks up the s(ymbol) argument 105755Speter * in the string table, entering it if 106755Speter * it is not found. If save is 0, then 107755Speter * the argument string is already in 108755Speter * a safe place. Otherwise, if hash is 109755Speter * entering the symbol for the first time 110755Speter * it will save the symbol in the string 111755Speter * table using savestr. 112755Speter */ 113755Speter int *hash(s, save) 114755Speter char *s; 115755Speter int save; 116755Speter { 117755Speter register int *h; 118755Speter register i; 119755Speter register char *cp; 120755Speter int *sym; 121*14733Sthien struct cstruct *temp; 122755Speter struct ht *htp; 123755Speter int sh; 124755Speter 125755Speter /* 126755Speter * The hash function is a modular hash of 127755Speter * the sum of the characters with the sum 128755Speter * doubled before each successive character 129755Speter * is added. 130755Speter */ 131755Speter cp = s; 132755Speter if (cp == NIL) 133755Speter cp = token; /* default symbol to be hashed */ 134755Speter i = 0; 135755Speter while (*cp) 136755Speter i = i*2 + *cp++; 137755Speter sh = (i&077777) % HASHINC; 138755Speter cp = s; 139755Speter if (cp == NIL) 140755Speter cp = token; 141755Speter /* 142755Speter * There are as many as MAXHASH active 143755Speter * hash tables at any given point in time. 144755Speter * The search starts with the first table 145755Speter * and continues through the active tables 146755Speter * as necessary. 147755Speter */ 148755Speter for (htp = htab; htp < &htab[MAXHASH]; htp++) { 149755Speter if (htp->ht_low == NIL) { 150*14733Sthien cp = (char *) pcalloc(sizeof ( int * ), HASHINC); 1511833Speter if (cp == 0) { 152755Speter yerror("Ran out of memory (hash)"); 153755Speter pexit(DIED); 154755Speter } 155*14733Sthien htp->ht_low = ((int *)cp); 156755Speter htp->ht_high = htp->ht_low + HASHINC; 157755Speter cp = s; 158755Speter if (cp == NIL) 159755Speter cp = token; 160755Speter } 161755Speter h = htp->ht_low + sh; 162755Speter /* 163755Speter * quadratic rehash increment 164755Speter * starts at 1 and incremented 165755Speter * by two each rehash. 166755Speter */ 167755Speter i = 1; 168755Speter do { 169755Speter if (*h == 0) { 170755Speter if (htp->ht_used > (HASHINC * 3)/4) 171755Speter break; 172755Speter htp->ht_used++; 173755Speter if (save != 0) { 174755Speter *h = (int) savestr(cp); 175755Speter } else 176*14733Sthien *h = ((int) s); 177755Speter return (h); 178755Speter } 179*14733Sthien sym = ((int *) *h); 180*14733Sthien if (sym < ((int *) lastkey) && sym >= ((int *) yykey)) 181*14733Sthien sym = ((int *) *sym); 182*14733Sthien temp = ((struct cstruct *) sym); 183*14733Sthien if (temp->pchar == *cp && pstrcmp((char *) sym, cp) == 0) 184755Speter return (h); 185755Speter h += i; 186755Speter i += 2; 187755Speter if (h >= htp->ht_high) 188755Speter h -= HASHINC; 189755Speter } while (i < HASHINC); 190755Speter } 191755Speter yerror("Ran out of hash tables"); 192755Speter pexit(DIED); 193*14733Sthien return (NIL); 194*14733Sthien 195755Speter } 196