1 #ifndef lint 2 static char sccsid[] = "@(#)3.reach.c 4.1 (Berkeley) 02/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 } 148