home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Distributions / ucb / spencer_2bsd.tar.gz / 2bsd.tar / src / pi0 / tree.c < prev    next >
C/C++ Source or Header  |  1980-02-17  |  5KB  |  300 lines
  1. /* Copyright (c) 1979 Regents of the University of California */
  2. #
  3. /*
  4.  * pi - Pascal interpreter code translator
  5.  *
  6.  * Charles Haley, Bill Joy UCB
  7.  */
  8.  
  9. #include "tree.h"
  10. #include "0.h"
  11.  
  12. /*
  13.  * TREE SPACE DECLARATIONS
  14.  */
  15. struct tr {
  16.     int    *tr_low;
  17.     int    *tr_high;
  18. } ttab[MAXTREE], *tract;
  19.  
  20. static    int *ltsnt;
  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. #ifndef PI0
  46. int    trspace[ITREE];
  47. int    *space    trspace;
  48. int    *spacep    trspace;
  49. #endif
  50. struct    tr *tract    ttab;
  51.  
  52. int    treemax;
  53.  
  54. /*
  55.  * Inittree allocates the first tree slot
  56.  * and sets up the first segment descriptor.
  57.  * A lot of this work is actually done statically
  58.  * above.
  59.  */
  60. #ifndef PI0
  61. inittree()
  62. #else
  63. inittree(trspace)
  64.     int *trspace;
  65. #endif
  66. {
  67.  
  68. #ifdef PI0
  69.     space = spacep = trspace;
  70. #endif
  71.     ttab[0].tr_low = space;
  72.     ttab[0].tr_high = &space[ITREE - 1];
  73. #ifndef PI1
  74.     ltsnt = space;
  75. #endif
  76.     treemax = ITREE;
  77.     *spacep = 0;
  78. }
  79.  
  80. #ifndef PI1
  81. /*
  82.  * Tree builds the nodes in the
  83.  * parse tree. It is rarely called
  84.  * directly, rather calls are made
  85.  * to tree[12345] which supplies the
  86.  * first argument to save space in
  87.  * the code. Tree also guarantees
  88.  * that spacep points to the beginning
  89.  * of the next slot it will return,
  90.  * a property required by the parser
  91.  * which was always true before we
  92.  * segmented the tree space.
  93.  */
  94. int *
  95. tree(cnt, a)
  96.     int cnt;
  97. {
  98.     register int *p, *q;
  99.     register int i;
  100.  
  101.     i = cnt;
  102.     p = spacep;
  103.     q = &a;
  104.     do
  105.         *p++ = *q++;
  106.     while (--i);
  107.     *p = 0;
  108.     q = spacep;
  109.     spacep = p;
  110.     if (p+TREENMAX >= tract->tr_high)
  111.         /*
  112.          * this peek-ahead should
  113.          * save a great number of calls
  114.          * to tralloc.
  115.          */
  116.         tralloc(TREENMAX);
  117.     return (q);
  118. }
  119. #else
  120. treev(i, q)
  121.     register int i, *q;
  122. {
  123.     register int *p;
  124.  
  125.     p = spacep;
  126.     do
  127.         *p++ = *q++;
  128.     while (--i);
  129.     *p = 0;
  130.     q = spacep;
  131.     spacep = p;
  132.     if (p+TREENMAX >= tract->tr_high)
  133.         tralloc(TREENMAX);
  134.     return (q);
  135. }
  136. #endif
  137. /*
  138.  * Tralloc preallocates enough
  139.  * space in the tree to allow
  140.  * the grammar to use the variable
  141.  * spacep, as it did before the
  142.  * tree was segmented.
  143.  */
  144. tralloc(howmuch)
  145. {
  146.     register char *cp;
  147.     register i;
  148.  
  149.     if (spacep + howmuch >= tract->tr_high) {
  150.         talloc(++tract);
  151.         spacep = tract->tr_low;
  152.         *spacep = 0;
  153.     }
  154. }
  155.  
  156. talloc(tp)
  157.     register struct tr *tp;
  158. {
  159.     register char *cp;
  160.     register int i;
  161.  
  162.     if (tp >= &ttab[MAXTREE]) {
  163.         yerror("Ran out of tree tables");
  164.         pexit(DIED);
  165.     }
  166.     if (tp->tr_low != NIL)
  167.         return;
  168.     cp = alloc(TRINC * 2);
  169.     if (cp == -1) {
  170.         yerror("Ran out of memory (talloc)");
  171.         pexit(DIED);
  172.     }
  173.     tp->tr_low = cp;
  174.     tp->tr_high = tp->tr_low + (TRINC - 1);
  175.     i = (tp - ttab + 1) * TRINC;
  176.     if (i > treemax)
  177.         treemax = i;
  178. }
  179. #ifndef PI1
  180. extern    int yylacnt;
  181. extern    bottled;
  182. #endif
  183. /*
  184.  * Free up the tree segments
  185.  * at the end of a block.
  186.  * If there is scanner lookahead,
  187.  * i.e. if yylacnt != 0 or there is bottled output, then we
  188.  * cannot free the tree space.
  189.  * This happens only when errors
  190.  * occur and the forward move extends
  191.  * across "units".
  192.  */
  193. trfree()
  194. {
  195.  
  196. #ifndef PI1
  197.     if (yylacnt != 0 || bottled != NIL)
  198.         return;
  199. #endif
  200. #ifndef PI1
  201.     send(RTRFREE);
  202.     ltsnt = space;
  203. #endif
  204.     spacep = space;
  205.     while (tract->tr_low > spacep || tract->tr_high <= spacep) {
  206.         free(tract->tr_low);
  207.         tract->tr_low = NIL;
  208.         tract->tr_high = NIL;
  209.         tract--;
  210.         if (tract < ttab)
  211.             panic("ttab");
  212.     }
  213.     treemax = ITREE;
  214. }
  215.  
  216. /*
  217.  * Copystr copies a token from
  218.  * the "token" buffer into the
  219.  * tree space.
  220.  */
  221. copystr(token)
  222.     register char *token;
  223. {
  224.     register char *cp;
  225.     register int i;
  226.  
  227.     i = (strlen(token) + 4) & ~1;
  228.     tralloc(i >> 1);
  229.     *spacep++ = T_COPSTR;
  230.     i =- 2;
  231.     strcpy(spacep, token);
  232.     cp = spacep;
  233.     spacep = cp + i;
  234.     *spacep = 0;
  235.     tralloc(TREENMAX);
  236.     return (cp);
  237. }
  238.  
  239. /* actually needed in PI1 only if DEBUG... */
  240. toffset(ap)
  241.     register int *ap;
  242. {
  243.     register struct tr *tp;
  244.     register int i;
  245.  
  246.     if (ap == 0)
  247.         return (0);
  248.     i = TRINC;
  249.     for (tp = ttab; tp->tr_low != NIL && tp < &ttab[MAXTREE]; tp++) {
  250.         if (ap >= tp->tr_low && ap < tp->tr_high)
  251.             return (i + (ap - tp->tr_low));
  252.         i =+ TRINC;
  253.     }
  254.     return (-soffset(ap));
  255. }
  256.  
  257. #ifndef PI1
  258. tsend()
  259. {
  260.     register struct tr *trp;
  261.     register int *ap;
  262.  
  263.     ap = ltsnt;
  264.     for (trp = &ttab[(toffset(ltsnt) / TRINC) - 1]; trp <= tract; trp++) {
  265.         while (ap < trp->tr_high && *ap)
  266.             ap = send(RTREE, ap);
  267.         ltsnt = ap;
  268.         ap = trp[1].tr_low;
  269.     }
  270. #ifdef DEBUG
  271.     send(RTRCHK, toffset(ltsnt));
  272. #endif
  273. }
  274. #endif
  275. #ifdef PI1
  276. treloc(i)
  277.     register int i;
  278. {
  279.  
  280.     if (i == 0)
  281.         return (0);
  282.     if (i < TRINC)
  283.         return (sreloc(-i));
  284.     i =- TRINC;
  285.     if (i >= treemax)
  286.         trmax(i);
  287.     return (ttab[i / TRINC].tr_low + i % TRINC);
  288. }
  289.  
  290. trmax(i)
  291.     register int i;
  292. {
  293.     register struct tr *tp;
  294.  
  295.     i = (i + TRINC) / TRINC;
  296.     for (tp = ttab; i > 0; tp++, i--)
  297.         talloc(tp);
  298. }
  299. #endif
  300.