home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / struct / 2.inarc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-01-10  |  1.5 KB  |  70 lines
  1. #include <stdio.h>
  2. #
  3. /* find forward in-arcs for each node, pretending that arcs which jump into a loop 
  4.     jump to the head of the largest such loop instead, based on the
  5.     depth first search tree */
  6. #include "def.h"
  7. #include "2.def.h"
  8.  
  9. getinarc(inarc,head)        /* construct array "inarc" containing in arcs for each node */
  10. struct list **inarc;
  11. VERT *head;
  12.     {
  13.     VERT v,adj,x;
  14.     int i, j;
  15.  
  16.     for (v=0; v < nodenum; ++v) inarc[v] = 0;
  17.  
  18.     /* fill in inarc nodes */
  19.  
  20.     for (i = 0; i < accessnum; ++i)
  21.         {
  22.         v = after[i];
  23.         for (j = 0; j < ARCNUM(v); ++j)
  24.             {
  25.             adj = ARC(v,j);
  26.             if (!DEFINED(adj))
  27.                 continue;
  28.             if (ntoaft[adj] > ntoaft[v])        /* not a back edge */
  29.                 /* if edge jumps into loop, pretend jumps to head of
  30.                     largest loop jumped into */
  31.                 {
  32.                 x = maxentry(v,adj,head);
  33.                 if (!DEFINED(x)) x = adj;
  34.                 else x = FATH(x);
  35.  
  36.                 inarc[x] = consls(v,inarc[x]);    /* insert v in list inarc[x] */
  37.                 }
  38.             }
  39.         }
  40.     }
  41.  
  42.  
  43.  
  44. maxentry(x,y,head)    /* return z if z is ITERVX of largest loop containing y but not x, UNDEFINED otherwise */
  45. VERT x,y, *head;
  46.     {
  47.     if (head[y] == UNDEFINED)  return(UNDEFINED);
  48.     if (loomem(x,head[y], head)) return (UNDEFINED);
  49.     y = head[y];
  50.     while (head[y] != UNDEFINED)
  51.         {
  52.         if (loomem(x,head[y],head))  return(y);
  53.         y = head[y];
  54.         }
  55.     return(y);
  56.     }
  57.  
  58.  
  59.  
  60. loomem(x,y,head)            /* return TRUE if x is in loop headed by y, FALSE otherwise */
  61. VERT x,y, *head;
  62.     {
  63.     VERT w;
  64.     if (!DEFINED(y)) return(TRUE);
  65.     ASSERT(NTYPE(y) == ITERVX, loomem);
  66.     for (w = (NTYPE(x) == ITERVX) ? x : head[x]; DEFINED(w); w = head[w])
  67.         if (w == y)  return (TRUE);
  68.     return(FALSE);
  69.     }
  70.