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