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