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