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