1 /* Copyright (c) 1979 Regents of the University of California */ 2 3 static char sccsid[] = "@(#)hash.c 1.4 08/29/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 0, 0, /* the following keywords are non-standard */ 61 "oct", YOCT, 62 "hex", YHEX, 63 "external", YEXTERN, 64 0 65 }; 66 67 char *lastkey; 68 69 /* 70 * Inithash initializes the hash table routines 71 * by allocating the first hash table segment using 72 * an already existing memory slot. 73 */ 74 #ifndef PI0 75 inithash() 76 #else 77 inithash(hshtab) 78 int *hshtab; 79 #endif 80 { 81 register int *ip; 82 #ifndef PI0 83 static int hshtab[HASHINC]; 84 #endif 85 86 htab[0].ht_low = hshtab; 87 htab[0].ht_high = &hshtab[HASHINC]; 88 for (ip = yykey; *ip; ip += 2) 89 hash(ip[0], 0)[0] = ip; 90 /* 91 * If we are not running in "standard-only" mode, 92 * we load the non-standard keywords. 93 */ 94 if (!opt('s')) 95 for (ip += 2; *ip; ip += 2) 96 hash(ip[0], 0)[0] = ip; 97 lastkey = (char *)ip; 98 } 99 100 /* 101 * Hash looks up the s(ymbol) argument 102 * in the string table, entering it if 103 * it is not found. If save is 0, then 104 * the argument string is already in 105 * a safe place. Otherwise, if hash is 106 * entering the symbol for the first time 107 * it will save the symbol in the string 108 * table using savestr. 109 */ 110 int *hash(s, save) 111 char *s; 112 int save; 113 { 114 register int *h; 115 register i; 116 register char *cp; 117 int *sym; 118 struct ht *htp; 119 int sh; 120 121 /* 122 * The hash function is a modular hash of 123 * the sum of the characters with the sum 124 * doubled before each successive character 125 * is added. 126 */ 127 cp = s; 128 if (cp == NIL) 129 cp = token; /* default symbol to be hashed */ 130 i = 0; 131 while (*cp) 132 i = i*2 + *cp++; 133 sh = (i&077777) % HASHINC; 134 cp = s; 135 if (cp == NIL) 136 cp = token; 137 /* 138 * There are as many as MAXHASH active 139 * hash tables at any given point in time. 140 * The search starts with the first table 141 * and continues through the active tables 142 * as necessary. 143 */ 144 for (htp = htab; htp < &htab[MAXHASH]; htp++) { 145 if (htp->ht_low == NIL) { 146 cp = (char *) calloc(sizeof ( int * ), HASHINC); 147 if (cp == 0) { 148 yerror("Ran out of memory (hash)"); 149 pexit(DIED); 150 } 151 htp->ht_low = cp; 152 htp->ht_high = htp->ht_low + HASHINC; 153 cp = s; 154 if (cp == NIL) 155 cp = token; 156 } 157 h = htp->ht_low + sh; 158 /* 159 * quadratic rehash increment 160 * starts at 1 and incremented 161 * by two each rehash. 162 */ 163 i = 1; 164 do { 165 if (*h == 0) { 166 if (htp->ht_used > (HASHINC * 3)/4) 167 break; 168 htp->ht_used++; 169 if (save != 0) { 170 *h = (int) savestr(cp); 171 } else 172 *h = s; 173 return (h); 174 } 175 sym = *h; 176 if (sym < lastkey && sym >= yykey) 177 sym = *sym; 178 if (sym->pchar == *cp && strcmp(sym, cp) == 0) 179 return (h); 180 h += i; 181 i += 2; 182 if (h >= htp->ht_high) 183 h -= HASHINC; 184 } while (i < HASHINC); 185 } 186 yerror("Ran out of hash tables"); 187 pexit(DIED); 188 } 189