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

   1: #ifndef lint
   2: static char sccsid[] = "@(#)2.head.c	4.1	(Berkeley)	2/11/83";
   3: #endif not lint
   4: 
   5: #include <stdio.h>
   6: #
   7: /*
   8: set head[v] to ITERVX heading smallest loop containing v, for each v
   9: */
  10: #include "def.h"
  11: #include "2.def.h"
  12: 
  13: /* define ANC(v,w) true if v == w or v is ancestor of w */
  14: #define ANC(v,w)    (ntobef[v] <= ntobef[w] && ntoaft[v] <= ntoaft[w])  /* reflexive ancestor */
  15: 
  16: 
  17: gethead(head)
  18: VERT *head;
  19:     {
  20:     VERT v, w, adj; int i, j;
  21:     /* search nodes in reverse of after numbering so that all paths from
  22: 		a node to an ancestor are searched before the node */
  23:     /* at any point, the current value of head allows chains of nodes
  24: 		to be reached from any node v by taking head[v], head[head[v]], etc.
  25: 		until an UNDEFINED value is reached.  Upon searching each arc,
  26: 		the appropriate chains must be merged to avoid losing information.
  27: 		For example, from one path out of a node v it may be known that
  28: 		 v is in a loop headed by z, while from another
  29: 		it may be known that v is in a loop headed by w.
  30: 		Thus, head[v] must be set to whichever of z,w is the closer ancestor,
  31: 		and the fact that this node is in a loop headed by the other must be
  32: 		recorded in head. 	*/
  33:     for (v = 0; v < nodenum; ++v)
  34:         head[v] = UNDEFINED;
  35:     for (i = accessnum -1; i >= 0; --i)
  36:         {
  37:         v = after[i];
  38:         for (j = 0; j < ARCNUM(v); ++j)
  39:             {
  40:             adj = ARC(v,j);
  41:             if (!DEFINED(adj)) continue;
  42:             if (ntoaft[adj] < i)        /* back edge */
  43:                 merge(v,adj,head);
  44:             else if (ANC(v,adj))        /* not back edge or cross edge */
  45:                 {
  46:                 /* need to do only tree edges - must not do edge (v,adj)
  47: 					when head[adj] is not ANC of v */
  48:                 if (DEFINED(head[adj]) && ANC(head[adj],v))
  49:                     merge(v,head[adj],head);
  50:                 }
  51:             else                /* cross edge */
  52:                 {
  53:                 w = lowanc(adj,v,head);
  54:                 if (DEFINED(w))
  55:                     merge(w,v,head);
  56:                 }
  57:             }
  58:         if (NTYPE(v) == LOOPVX || NTYPE(v) == DOVX)
  59:             head[ARC(v,0)] = head[v];   /* head of ITERVX must be different ITERVX */
  60:         }
  61:     }
  62: 
  63: 
  64: lowanc(y,z,head)        /* find the first node in chain of y which is anc of z, if it exists */
  65: VERT y,z, *head;
  66:     {
  67:     while (y != -1 && !ANC(y,z))
  68:         y = head[y];
  69:     return(y);
  70:     }
  71: 
  72: 
  73: merge(w,y,head)     /* merge chains of w and y according to ANC relation */
  74: VERT w,y, *head;
  75:     {
  76:     VERT t, min;
  77:     if (w == y) return;
  78: 
  79:     if (ANC(w,y))       /* set t to min of w,y */
  80:         {
  81:         t = y;
  82:          y = head[y];
  83:         }
  84:     else
  85:         {
  86:         t = w;
  87:          w = head[w];
  88:         }
  89: 
  90:     while (w != -1 && y != -1)      /* construct chain at t by adding min of remaining elts */
  91:         {
  92:         if (ANC(w,y))
  93:             {
  94:             min = y;
  95:             y = head[y];
  96:             }
  97:         else
  98:             {
  99:             min = w;
 100:             w = head[w];
 101:             }
 102:         if (t != min)
 103:             {
 104:             head[t] = min;
 105:             t = min;
 106:             }
 107:         }
 108:     if (w == -1)  min = y;  else  min = w;
 109:     if (t != min)  head[t] = min;
 110: 
 111:     }

Defined functions

Defined variables

Defined macros