1 /*-
2 * %sccs.include.proprietary.c%
3 */
4
5 #ifndef lint
6 static char sccsid[] = "@(#)3.reach.c 8.1 (Berkeley) 06/06/93";
7 #endif /* not lint */
8
9 #include <stdio.h>
10 #
11 /*
12 set REACH[v] = w if w is only node outside subtree of v which is reached from within
13 subtree of v, REACH[v] = UNDEFINED otherwise
14 */
15 #include "def.h"
16
17 /* strategy in obtaining REACH(v) for each node v:
18 Since only need to know whether there is exactly one exit from subtree of v,
19 need keep track only of 2 farthest exits from each subtree rather than all exits.
20 The first may be the unique exit, while the second is used when the children
21 of a node has the same first exit.
22 To obtain 2 farthest exits of v, look at 2 farthest exits of children of v and
23 the nodes entered by arcs from v. Farthest exits are identified by numbering
24 the nodes from -2 to -(accessnum-2) starting at the bottom left corner of tree
25 using procedure number(). The farthest exit from the subtree of v is the one
26 with the least number according NUM to this numbering. If a node w is an exit from the
27 subtree of v, then NUM(w) < NUM(v). The negative numbers allow NUM(v) to be stored
28 in the same location as REACH(v). REACH(w) may already be set when an arc (v,w) to a child
29 is searched, but the negative numbering is consistent, i.e. NUM(v) < NUM(w) in this case
30 as in other cases where w is not an exit from the subtree of v.
31 */
32
33 struct pair {
34 int smallest;
35 int second;
36 };
37
38
getreach()39 getreach() /* obtain REACH(v) for each node v */
40 {
41 VERT v;
42 struct pair *pr;
43 for (v = 0; v < nodenum; ++v)
44 REACH(v) = UNDEFINED;
45 number(START);
46 for (v = START; DEFINED(v); v = RSIB(v))
47 {
48 pr = exits(v); /* need to free the space for pr */
49 chfree(pr,sizeof(*pr));
50 }
51 }
52
53
exits(v)54 exits(v) /* set REACH(v) = w if w is only node outside subtree of v which is reached from within
55 subtree of v, leave REACH(v) UNDEFINED otherwise */
56 VERT v;
57 {
58 struct pair *vpair, *chpair;
59 VERT w,t;
60 int i;
61 vpair = challoc(sizeof(*vpair));
62 vpair ->smallest = vpair ->second = UNDEFINED;
63 for (i = 0; i < CHILDNUM(v); ++i)
64 {
65 w = LCHILD(v,i);
66 if (!DEFINED(w)) continue;
67 for (t = w; DEFINED(t); t = RSIB(t))
68 {
69 chpair = exits(t);
70
71 /* set vpair->smallest,second to two smallest of vpair->smallest,second,
72 chpair->smallest,second */
73 if (inspr(chpair->smallest,vpair))
74 inspr(chpair->second,vpair);
75 chfree(chpair, sizeof(*chpair));
76 }
77 }
78 for (i = 0; i < ARCNUM(v); ++i)
79 {
80 w = ARC(v,i);
81 if (!DEFINED(w)) continue;
82 inspr(w,vpair);
83 }
84 /* throw out nodes in subtree of v */
85 if (NUM(vpair->second) >= NUM(v))
86 {
87 vpair->second = UNDEFINED;
88 if (NUM(vpair->smallest) >= NUM(v))
89 vpair->smallest = UNDEFINED;
90 }
91 if (vpair->second == UNDEFINED)
92 REACH(v) = vpair->smallest; /* vpair->smallest possibly UNDEFINED */
93 else
94 REACH(v) = UNDEFINED;
95 return(vpair);
96 }
97
98
99 /* number nodes from -2 to -(accessnum+2) starting at bottom left corner of tree */
number(v)100 number(v)
101 VERT v;
102 {
103 int i;
104 VERT w;
105 static int count;
106 for (i = 0; i < CHILDNUM(v); ++i)
107 {
108 w = LCHILD(v,i);
109 if (DEFINED(w))
110 number(w);
111 }
112 SETNUM(v,count-2);
113 --count;
114 if (DEFINED(RSIB(v)))
115 number(RSIB(v));
116 }
117
118
NUM(v)119 NUM(v)
120 VERT v;
121 {
122 if (!DEFINED(v)) return(UNDEFINED);
123 return(REACH(v));
124 }
125
SETNUM(v,count)126 SETNUM(v,count)
127 VERT v; int count;
128 {
129 /* this reuses REACH to save space;
130 /* appears to be no conflict with setting true value of REACH later */
131 REACH(v) = count;
132 }
133
134
inspr(w,pr)135 LOGICAL inspr(w,pr) /* insert w in order in pr, return TRUE if <= smaller of pr */
136 /* don't insert duplicates */
137 VERT w;
138 struct pair *pr;
139 {
140 if (w == pr-> smallest) return(TRUE);
141 if (NUM(w) < NUM(pr->smallest))
142 {
143 pr->second = pr->smallest;
144 pr->smallest = w;
145 return(TRUE);
146 }
147 if (w == pr->second) return(FALSE);
148 if (NUM(w) < NUM(pr->second))
149 pr->second = w;
150 return(FALSE);
151 }
152