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