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 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 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 */ 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 119 NUM(v) 120 VERT v; 121 { 122 if (!DEFINED(v)) return(UNDEFINED); 123 return(REACH(v)); 124 } 125 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 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