2.9BSD - /usr/src/cmd/struct/2.inarc.c

   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:     }

Defined functions