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