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