4.3BSD - /usr/src/usr.bin/struct/2.tree.c

   1: #ifndef lint
   2: static char sccsid[] = "@(#)2.tree.c	4.1	(Berkeley)	2/11/83";
   3: #endif not lint
   4: 
   5: #include <stdio.h>
   6: #
   7: /* use inarc, dom, and head to build tree representing structure of program.
   8: 	Each node v has CHILDNUM(v) children denoted by
   9: 	LCHILD(v,0), LCHILD(v,1),...
  10: 	RSIB((v) is right sibling of v or UNDEFINED;
  11: 	RSIB(v) represents code following v at the same level of nesting,
  12: 	while LCHILD(v,i) represents code nested within v
  13: */
  14: #include "def.h"
  15: #include "2.def.h"
  16: 
  17: gettree(inarc,dom,head)     /* build tree */
  18: struct list **inarc;
  19: VERT *dom, *head;
  20:     {
  21:     VERT v,u,from;
  22:     int i;
  23:     for ( v = 0; v < nodenum; ++v)
  24:         {
  25:         RSIB(v) = UNDEFINED;
  26:         for (i = 0; i < CHILDNUM(v); ++i)
  27:             LCHILD(v,i) = UNDEFINED;
  28:         }
  29:     for (i = accessnum-1; i > 0; --i)
  30:         {
  31:         v = after[i];
  32:         from = oneelt(inarc[v]);    /* the unique elt of inarc[v] or UNDEFINED */
  33:         if (DEFINED(from))
  34:             if (NTYPE(from) == IFVX && (head[v] == head[from] || asoc(v,exitsize) != -1) )
  35:                 /* place in clause of IFVX if in smallest loop containing it
  36: 				or if size of code for v is <= exitsize */
  37:                 if (ARC(from,THEN) == v)
  38:                     {
  39:                     LCHILD(from,THEN) = v;
  40:                     continue;
  41:                     }
  42:                 else
  43:                     {
  44:                     ASSERT(ARC(from,ELSE) == v,gettree);
  45:                     LCHILD(from,ELSE) = v;
  46:                     continue;
  47:                     }
  48:             else if (NTYPE(v) == ITERVX || NTYPE(from) == ITERVX )
  49:                 /* LOOPVX -> ITERVX ->vert always in same loop*/
  50:                 {
  51:                 LCHILD(from,0) = v;
  52:                 continue;
  53:                 }
  54:             else if (NTYPE(from) == SWCHVX)
  55:                 {
  56:                 ASSERT(0 < ARCNUM(v),gettree);
  57:                 if (ARC(from,0) == v)
  58:                     LCHILD(from,0) = v;
  59:                 else
  60:                     {
  61:                     int j;
  62:                     for (j = 1; j < ARCNUM(from); ++j)
  63:                         if (ARC(from,j) == v)
  64:                             {insib(ARC(from,j-1),v);
  65:                             break;
  66:                             }
  67:                     }
  68:                 continue;
  69:                 }
  70:             else if (NTYPE(from) == ICASVX && (head[v] == head[from] || asoc(v,exitsize) != -1))
  71:                 {
  72:                 LCHILD(from,0) = v;
  73:                 continue;
  74:                 }
  75:             else if (NTYPE(from) == DUMVX && ARC(from,0) == v)
  76:                 {
  77:                 LCHILD(from,0) = v;
  78:                 continue;
  79:                 }
  80:         if (loomem(v,head[dom[v]],head))
  81:                 /* v is in smallest loop containing dom[v] */
  82:             insib(dom[v],v);
  83:         else
  84:             {
  85:                 /* make v follow LOOPVX heading largest loop
  86: 					containing DOM[v] but not v */
  87:             ASSERT(DEFINED(head[dom[v]]),gettree);
  88:             for (u = head[dom[v]]; head[u] != head[v]; u = head[u])
  89:                 ASSERT(DEFINED(head[u]),gettree);
  90:             ASSERT(NTYPE(u) == ITERVX,gettree);
  91:             insib(FATH(u),v);
  92:             }
  93:         }
  94:     }
  95: 
  96: 
  97: 
  98: 
  99: insib(w,v)      /* make RSIB(w) = v, and make RSIB(rightmost sib of v) = old RSIB(w) */
 100: VERT w,v;
 101:     {
 102:     VERT u, temp;
 103:     temp = RSIB(w);
 104:     RSIB(w) = v;
 105:     for (u = v; DEFINED(RSIB(u)); u = RSIB(u))
 106:         ;
 107:     RSIB(u) = temp;
 108:     }
 109: 
 110: 
 111: asoc(v,n)       /* return # of nodes associated with v if <= n, -1 otherwise */
 112: VERT v;
 113: int n;
 114:     {
 115:     int count,i,temp;
 116:     VERT w;
 117:     count = (NTYPE(v) == STLNVX) ? CODELINES(v) : 1;
 118:     for (i = 0; i < CHILDNUM(v); ++i)
 119:         {
 120:         w = LCHILD(v,i);
 121:         if (!DEFINED(w)) continue;
 122:         temp = asoc(w,n-count);
 123:         if (temp == -1) return(-1);
 124:         count += temp;
 125:         if (count > n) return(-1);
 126:         }
 127:     if (DEFINED(RSIB(v)))
 128:         {
 129:         temp = asoc(RSIB(v),n-count);
 130:         if (temp == -1) return(-1);
 131:         count += temp;
 132:         }
 133:     if (count > n) return(-1);
 134:     else return(count);
 135:     }

Defined functions

Defined variables