1: #ifndef lint
2: static char sccsid[] = "@(#)2.inarc.c 4.1 (Berkeley) 2/11/83";
3: #endif not lint
4:
5: #include <stdio.h>
6: #
7: /* find forward in-arcs for each node, pretending that arcs which jump into a loop
8: jump to the head of the largest such loop instead, based on the
9: depth first search tree */
10: #include "def.h"
11: #include "2.def.h"
12:
13: getinarc(inarc,head) /* construct array "inarc" containing in arcs for each node */
14: struct list **inarc;
15: VERT *head;
16: {
17: VERT v,adj,x;
18: int i, j;
19:
20: for (v=0; v < nodenum; ++v) inarc[v] = 0;
21:
22: /* fill in inarc nodes */
23:
24: for (i = 0; i < accessnum; ++i)
25: {
26: v = after[i];
27: for (j = 0; j < ARCNUM(v); ++j)
28: {
29: adj = ARC(v,j);
30: if (!DEFINED(adj))
31: continue;
32: if (ntoaft[adj] > ntoaft[v]) /* not a back edge */
33: /* if edge jumps into loop, pretend jumps to head of
34: largest loop jumped into */
35: {
36: x = maxentry(v,adj,head);
37: if (!DEFINED(x)) x = adj;
38: else x = FATH(x);
39:
40: inarc[x] = (struct list *)consls(v,inarc[x]); /* insert v in list inarc[x] */
41: }
42: }
43: }
44: }
45:
46:
47:
48: maxentry(x,y,head) /* return z if z is ITERVX of largest loop containing y but not x, UNDEFINED otherwise */
49: VERT x,y, *head;
50: {
51: if (head[y] == UNDEFINED) return(UNDEFINED);
52: if (loomem(x,head[y], head)) return (UNDEFINED);
53: y = head[y];
54: while (head[y] != UNDEFINED)
55: {
56: if (loomem(x,head[y],head)) return(y);
57: y = head[y];
58: }
59: return(y);
60: }
61:
62:
63:
64: loomem(x,y,head) /* return TRUE if x is in loop headed by y, FALSE otherwise */
65: VERT x,y, *head;
66: {
67: VERT w;
68: if (!DEFINED(y)) return(TRUE);
69: ASSERT(NTYPE(y) == ITERVX, loomem);
70: for (w = (NTYPE(x) == ITERVX) ? x : head[x]; DEFINED(w); w = head[w])
71: if (w == y) return (TRUE);
72: return(FALSE);
73: }
Defined functions
Defined variables
sccsid
defined in line
2;
never used