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
inithash()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 */
hash(s,save)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