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