home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / struct / 2.head.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-01-10  |  2.5 KB  |  108 lines
  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.     }
  108.