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

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

Defined functions

Defined macros