projects / unix-history / blame
| Commit | Line | Data |
|---|---|---|
| 42d6e430 BJ |
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 | } |