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