```   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:     }
```

#### Defined functions

NUM defined in line 115; used 8 times
SETNUM defined in line 122; used 1 times
exits defined in line 50; used 2 times
getreach defined in line 35; used 1 times
inspr defined in line 131; used 3 times
number defined in line 96; used 3 times

#### Defined variables

sccsid defined in line 2; never used

#### Defined struct's

pair defined in line 29; used 6 times
 Last modified: 1983-02-12 Generated: 2016-12-26 Generated by src2html V0.67 page hit count: 657  