1 #ifndef lint
2 static char sccsid[] = "@(#)2.inarc.c	4.1	(Berkeley)	02/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] = 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 	}
74