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