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