# 2.11BSD#431 - /usr/src/usr.bin/struct/2.head.c

##### Functions

    gethead           X
    lowanc            X
    merge             X

##### Macros

    ANC               X

       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

gethead defined in line 17; used 1 times

- in /usr/src/usr.bin/struct/2.main.c line 27

lowanc defined in line 64; used 1 times

- in line 53

merge defined in line 73; used 3 times

- in line 43, 49, 55

#### Defined variables

sccsid defined in line 2; never used

#### Defined macros

ANC defined in line 14; used 5 times

- in line 44-48(2), 67, 79, 92

Last modified: 1987-02-17 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 494 |