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