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