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

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

Defined functions

Defined variables