home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / usr.bin / pascal / src / tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-16  |  5.3 KB  |  215 lines
  1. /*-
  2.  * Copyright (c) 1980 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #ifndef lint
  35. static char sccsid[] = "@(#)tree.c    5.2 (Berkeley) 4/16/91";
  36. #endif /* not lint */
  37.  
  38. #include "whoami.h"
  39. #include "0.h"
  40.  
  41. /*
  42.  * TREE SPACE DECLARATIONS
  43.  */
  44. struct tr {
  45.     int    *tr_low;
  46.     int    *tr_high;
  47. } ttab[MAXTREE], *tract;
  48.  
  49. /*
  50.  * The variable space is the
  51.  * absolute base of the tree segments.
  52.  * (exactly the same as ttab[0].tr_low)
  53.  * Spacep is maintained to point at the
  54.  * beginning of the next tree slot to
  55.  * be allocated for use by the grammar.
  56.  * Spacep is used "extern" by the semantic
  57.  * actions in pas.y.
  58.  * The variable tract is maintained to point
  59.  * at the tree segment out of which we are
  60.  * allocating (the active segment).
  61.  */
  62. int    *space, *spacep;
  63.  
  64. /*
  65.  * TREENMAX is the maximum width
  66.  * in words that any tree node 
  67.  * due to the way in which the parser uses
  68.  * the pointer spacep.
  69.  */
  70. #define    TREENMAX    6
  71.  
  72. int    trspace[ITREE];
  73. int    *space    = trspace;
  74. int    *spacep    = trspace;
  75. struct    tr *tract    = ttab;
  76.  
  77. /*
  78.  * Inittree allocates the first tree slot
  79.  * and sets up the first segment descriptor.
  80.  * A lot of this work is actually done statically
  81.  * above.
  82.  */
  83. inittree()
  84. {
  85.  
  86.     ttab[0].tr_low = space;
  87.     ttab[0].tr_high = &space[ITREE];
  88. }
  89.  
  90. /*
  91.  * Tree builds the nodes in the
  92.  * parse tree. It is rarely called
  93.  * directly, rather calls are made
  94.  * to tree[12345] which supplies the
  95.  * first argument to save space in
  96.  * the code. Tree also guarantees
  97.  * that spacep points to the beginning
  98.  * of the next slot it will return,
  99.  * a property required by the parser
  100.  * which was always true before we
  101.  * segmented the tree space.
  102.  */
  103. /*VARARGS1*/
  104. struct tnode *
  105. tree(cnt, a)
  106.     int cnt;
  107. {
  108.     register int *p, *q;
  109.     register int i;
  110.  
  111.     i = cnt;
  112.     p = spacep;
  113.     q = &a;
  114.     do
  115.         *p++ = *q++;
  116.     while (--i);
  117.     q = spacep;
  118.     spacep = p;
  119.     if (p+TREENMAX >= tract->tr_high)
  120.         /*
  121.          * this peek-ahead should
  122.          * save a great number of calls
  123.          * to tralloc.
  124.          */
  125.         tralloc(TREENMAX);
  126.     return ((struct tnode *) q);
  127. }
  128.  
  129. /*
  130.  * Tralloc preallocates enough
  131.  * space in the tree to allow
  132.  * the grammar to use the variable
  133.  * spacep, as it did before the
  134.  * tree was segmented.
  135.  */
  136. tralloc(howmuch)
  137. {
  138.     register char *cp;
  139.     register i;
  140.  
  141.     if (spacep + howmuch >= tract->tr_high) {
  142.         i = TRINC;
  143.         cp = malloc((unsigned) (i * sizeof ( int )));
  144.         if (cp == 0) {
  145.             yerror("Ran out of memory (tralloc)");
  146.             pexit(DIED);
  147.         }
  148.         spacep = (int *) cp;
  149.         tract++;
  150.         if (tract >= &ttab[MAXTREE]) {
  151.             yerror("Ran out of tree tables");
  152.             pexit(DIED);
  153.         }
  154.         tract->tr_low = (int *) cp;
  155.         tract->tr_high = tract->tr_low+i;
  156.     }
  157. }
  158.  
  159. extern    int yylacnt;
  160. extern    struct B *bottled;
  161. #ifdef PXP
  162. #endif
  163. /*
  164.  * Free up the tree segments
  165.  * at the end of a block.
  166.  * If there is scanner lookahead,
  167.  * i.e. if yylacnt != 0 or there is bottled output, then we
  168.  * cannot free the tree space.
  169.  * This happens only when errors
  170.  * occur and the forward move extends
  171.  * across "units".
  172.  */
  173. trfree()
  174. {
  175.  
  176.     if (yylacnt != 0 || bottled != NIL)
  177.         return;
  178. #ifdef PXP
  179.     if (needtree())
  180.         return;
  181. #endif
  182.     spacep = space;
  183.     while (tract->tr_low > spacep || tract->tr_high <= spacep) {
  184.         free((char *) tract->tr_low);
  185.         tract->tr_low = NIL;
  186.         tract->tr_high = NIL;
  187.         tract--;
  188.         if (tract < ttab)
  189.             panic("ttab");
  190.     }
  191. #ifdef PXP
  192.     packtree();
  193. #endif
  194. }
  195.  
  196. /*
  197.  * Copystr copies a token from
  198.  * the "token" buffer into the
  199.  * tree space.
  200.  */
  201. copystr(token)
  202.     register char *token;
  203. {
  204.     register char *cp;
  205.     register int i;
  206.  
  207.     i = (strlen(token) + sizeof ( int )) & ~( ( sizeof ( int ) ) - 1 );
  208.     tralloc(i / sizeof ( int ));
  209.     (void) pstrcpy((char *) spacep, token);
  210.     cp = (char *) spacep;
  211.     spacep = ((int *) cp + i);
  212.     tralloc(TREENMAX);
  213.     return ((int) cp);
  214. }
  215.