Commit | Line | Data |
---|---|---|
4b9ccde7 | 1 | static char *sccsid = "@(#)tree.c 1.1 (Berkeley) 3/2/81"; |
d19f16dd BJ |
2 | /* Copyright (c) 1979 Regents of the University of California */ |
3 | # | |
4 | /* | |
5 | * pi - Pascal interpreter code translator | |
6 | * | |
7 | * Charles Haley, Bill Joy UCB | |
8 | * Version 1.1 February 1978 | |
9 | * | |
10 | * | |
11 | * pxp - Pascal execution profiler | |
12 | * | |
13 | * Bill Joy UCB | |
14 | * Version 1.1 February 1978 | |
15 | */ | |
16 | ||
17 | #include "0.h" | |
18 | ||
19 | /* | |
20 | * TREE SPACE DECLARATIONS | |
21 | */ | |
22 | struct tr { | |
23 | int *tr_low; | |
24 | int *tr_high; | |
25 | } ttab[MAXTREE], *tract; | |
26 | ||
27 | /* | |
28 | * The variable space is the | |
29 | * absolute base of the tree segments. | |
30 | * (exactly the same as ttab[0].tr_low) | |
31 | * Spacep is maintained to point at the | |
32 | * beginning of the next tree slot to | |
33 | * be allocated for use by the grammar. | |
34 | * Spacep is used "extern" by the semantic | |
35 | * actions in pas.y. | |
36 | * The variable tract is maintained to point | |
37 | * at the tree segment out of which we are | |
38 | * allocating (the active segment). | |
39 | */ | |
40 | int *space, *spacep; | |
41 | ||
42 | /* | |
43 | * TREENMAX is the maximum width | |
44 | * in words that any tree node | |
45 | * due to the way in which the parser uses | |
46 | * the pointer spacep. | |
47 | */ | |
48 | #define TREENMAX 6 | |
49 | ||
50 | int trspace[ITREE]; | |
51 | int *space = trspace; | |
52 | int *spacep = trspace; | |
53 | struct tr *tract = ttab; | |
54 | ||
55 | /* | |
56 | * Inittree allocates the first tree slot | |
57 | * and sets up the first segment descriptor. | |
58 | * A lot of this work is actually done statically | |
59 | * above. | |
60 | */ | |
61 | inittree() | |
62 | { | |
63 | ||
64 | ttab[0].tr_low = space; | |
65 | ttab[0].tr_high = &space[ITREE]; | |
66 | } | |
67 | ||
68 | /* | |
69 | * Tree builds the nodes in the | |
70 | * parse tree. It is rarely called | |
71 | * directly, rather calls are made | |
72 | * to tree[12345] which supplies the | |
73 | * first argument to save space in | |
74 | * the code. Tree also guarantees | |
75 | * that spacep points to the beginning | |
76 | * of the next slot it will return, | |
77 | * a property required by the parser | |
78 | * which was always true before we | |
79 | * segmented the tree space. | |
80 | */ | |
81 | int *tree(cnt, a) | |
82 | int cnt; | |
83 | { | |
84 | register int *p, *q; | |
85 | register int i; | |
86 | ||
87 | i = cnt; | |
88 | p = spacep; | |
89 | q = &a; | |
90 | do | |
91 | *p++ = *q++; | |
92 | while (--i); | |
93 | q = spacep; | |
94 | spacep = p; | |
95 | if (p+TREENMAX >= tract->tr_high) | |
96 | /* | |
97 | * this peek-ahead should | |
98 | * save a great number of calls | |
99 | * to tralloc. | |
100 | */ | |
101 | tralloc(TREENMAX); | |
102 | return (q); | |
103 | } | |
104 | ||
105 | /* | |
106 | * Tralloc preallocates enough | |
107 | * space in the tree to allow | |
108 | * the grammar to use the variable | |
109 | * spacep, as it did before the | |
110 | * tree was segmented. | |
111 | */ | |
112 | tralloc(howmuch) | |
113 | { | |
114 | register char *cp; | |
115 | register i; | |
116 | ||
117 | if (spacep + howmuch >= tract->tr_high) { | |
118 | i = TRINC; | |
119 | cp = malloc(i * sizeof ( int )); | |
120 | if (cp == -1) { | |
121 | yerror("Ran out of memory (tralloc)"); | |
122 | pexit(DIED); | |
123 | } | |
124 | spacep = cp; | |
125 | tract++; | |
126 | if (tract >= &ttab[MAXTREE]) { | |
127 | yerror("Ran out of tree tables"); | |
128 | pexit(DIED); | |
129 | } | |
130 | tract->tr_low = cp; | |
131 | tract->tr_high = tract->tr_low+i; | |
132 | } | |
133 | } | |
134 | ||
135 | extern int yylacnt; | |
136 | extern bottled; | |
137 | #ifdef PXP | |
138 | #endif | |
139 | /* | |
140 | * Free up the tree segments | |
141 | * at the end of a block. | |
142 | * If there is scanner lookahead, | |
143 | * i.e. if yylacnt != 0 or there is bottled output, then we | |
144 | * cannot free the tree space. | |
145 | * This happens only when errors | |
146 | * occur and the forward move extends | |
147 | * across "units". | |
148 | */ | |
149 | trfree() | |
150 | { | |
151 | ||
152 | if (yylacnt != 0 || bottled != NIL) | |
153 | return; | |
154 | #ifdef PXP | |
155 | if (needtree()) | |
156 | return; | |
157 | #endif | |
158 | spacep = space; | |
159 | while (tract->tr_low > spacep || tract->tr_high <= spacep) { | |
160 | free(tract->tr_low); | |
161 | tract->tr_low = NIL; | |
162 | tract->tr_high = NIL; | |
163 | tract--; | |
164 | if (tract < ttab) | |
165 | panic("ttab"); | |
166 | } | |
167 | #ifdef PXP | |
168 | packtree(); | |
169 | #endif | |
170 | } | |
171 | ||
172 | /* | |
173 | * Copystr copies a token from | |
174 | * the "token" buffer into the | |
175 | * tree space. | |
176 | */ | |
177 | copystr(token) | |
178 | register char *token; | |
179 | { | |
180 | register char *cp; | |
181 | register int i; | |
182 | ||
183 | i = (strlen(token) + sizeof ( int )) & ~( ( sizeof ( int ) ) - 1 ); | |
184 | tralloc(i / sizeof ( int )); | |
185 | strcpy(spacep, token); | |
186 | cp = spacep; | |
187 | spacep = cp + i; | |
188 | tralloc(TREENMAX); | |
189 | return (cp); | |
190 | } |