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