1*10920Sshannon /* tree.c 4.1 83/02/11 */ 2*10920Sshannon 3*10920Sshannon #include "compact.h" 4*10920Sshannon 5*10920Sshannon 6*10920Sshannon insert (ch) 7*10920Sshannon int ch; 8*10920Sshannon { 9*10920Sshannon register struct node *pp; 10*10920Sshannon register int c; 11*10920Sshannon union cio d; 12*10920Sshannon register struct index *qt, *wt; 13*10920Sshannon 14*10920Sshannon c = ch; 15*10920Sshannon wt = NEW; 16*10920Sshannon pp = bottom++; 17*10920Sshannon bottom -> fath . fp = pp; 18*10920Sshannon in [c] . flags = (SEEN | FBIT); 19*10920Sshannon d . integ = bottom -> sp [0] . ch = pp -> sp [1] . ch; 20*10920Sshannon in [c] . fp = in [d . integ] . fp = pp -> sp [1] . p = wt -> pt = bottom; 21*10920Sshannon bottom -> fath . flags = (LLEAF | RLEAF | FBIT); 22*10920Sshannon pp -> fath . flags &= ~RLEAF; 23*10920Sshannon in [d . integ] . flags = SEEN; 24*10920Sshannon 25*10920Sshannon bottom -> count [0] = pp -> count [1]; 26*10920Sshannon qt = pp -> top [1]; 27*10920Sshannon bottom -> top [0] = qt; 28*10920Sshannon bottom -> sp [1] . ch = c; 29*10920Sshannon bottom -> count [1] = 0; 30*10920Sshannon bottom -> top [1] = qt -> next = wt; 31*10920Sshannon wt -> next = NULL; 32*10920Sshannon } 33*10920Sshannon 34*10920Sshannon uptree (ch) 35*10920Sshannon int ch; 36*10920Sshannon { 37*10920Sshannon register struct node *r; 38*10920Sshannon union treep q, s; 39*10920Sshannon int rs, qs, ss, ts; 40*10920Sshannon longint rc, qc, sc; 41*10920Sshannon struct node *t; 42*10920Sshannon register struct index *rt, *qt, *st; 43*10920Sshannon 44*10920Sshannon r = in [ch] . fp; 45*10920Sshannon rs = in [ch] . flags & FBIT; 46*10920Sshannon 47*10920Sshannon do { 48*10920Sshannon (r -> count [rs])++; 49*10920Sshannon rc = r -> count [rs]; 50*10920Sshannon rt = r -> top [rs]; 51*10920Sshannon 52*10920Sshannon for ( ; ; ) { 53*10920Sshannon qs = ss = 1 - rs; 54*10920Sshannon s . p = r + rs; 55*10920Sshannon sc = (s . p) -> count [ss]; 56*10920Sshannon st = (s . p) -> top [ss]; 57*10920Sshannon 58*10920Sshannon if (rs) 59*10920Sshannon if (r == bottom) { 60*10920Sshannon sc = rc - 2; 61*10920Sshannon st = NULL; 62*10920Sshannon } 63*10920Sshannon else; 64*10920Sshannon else if (r == dict) { 65*10920Sshannon qc = rc + 1; 66*10920Sshannon qt = head; 67*10920Sshannon break; 68*10920Sshannon } 69*10920Sshannon 70*10920Sshannon q . p = r - qs; 71*10920Sshannon qc = (q . p) -> count [qs]; 72*10920Sshannon qt = (q . p) -> top [qs]; 73*10920Sshannon if (rc <= qc) break; 74*10920Sshannon 75*10920Sshannon t = qt -> pt; 76*10920Sshannon ts = (rc <= t -> count [0] ? 1 : 0); 77*10920Sshannon 78*10920Sshannon /* exchange pointers of (t, ts) and (r, rs) */ 79*10920Sshannon 80*10920Sshannon q . ch = t -> sp [ts] . ch; /* { */ 81*10920Sshannon s . ch = r -> sp [rs] . ch; /* { */ 82*10920Sshannon t -> sp [ts] . ch = s . ch; /* { */ 83*10920Sshannon r -> sp [rs] . ch = q . ch; /* { change code when Cory gets v. 7 */ 84*10920Sshannon /* { */ 85*10920Sshannon exch (t, ts, q . ch, r, rs); /* { */ 86*10920Sshannon exch (r, rs, s . ch, t, ts); /* { */ 87*10920Sshannon 88*10920Sshannon qs = (rs ? RLEAF : LLEAF); 89*10920Sshannon ss = (ts ? RLEAF : LLEAF); 90*10920Sshannon if (((r -> fath . flags & qs) << rs) ^ ((t -> fath . flags & ss) << ts)) { 91*10920Sshannon r -> fath . flags ^= qs; 92*10920Sshannon t -> fath . flags ^= ss; 93*10920Sshannon } 94*10920Sshannon 95*10920Sshannon (t -> count [ts])++; 96*10920Sshannon (r -> count [rs])--; 97*10920Sshannon (qt -> pt) += ts; 98*10920Sshannon r = t; 99*10920Sshannon rs = ts; 100*10920Sshannon } 101*10920Sshannon 102*10920Sshannon if (rc == qc) { 103*10920Sshannon r -> top [rs] = qt; 104*10920Sshannon if (rc > sc + 1) { 105*10920Sshannon qt -> next = st; 106*10920Sshannon 107*10920Sshannon /* dispose of rt */ 108*10920Sshannon 109*10920Sshannon rt -> next = flist; 110*10920Sshannon flist = rt; 111*10920Sshannon } 112*10920Sshannon else st -> pt = s . p; 113*10920Sshannon } 114*10920Sshannon 115*10920Sshannon else if (rc == sc + 1) { 116*10920Sshannon 117*10920Sshannon /* create new index at rt */ 118*10920Sshannon 119*10920Sshannon rt = NEW; 120*10920Sshannon rt -> next = st; 121*10920Sshannon rt -> pt = r; 122*10920Sshannon qt -> next = rt; 123*10920Sshannon if (st) st -> pt = s . p; 124*10920Sshannon r -> top [rs] = rt; 125*10920Sshannon } 126*10920Sshannon 127*10920Sshannon rs = r -> fath . flags & FBIT; 128*10920Sshannon r = r -> fath . fp; 129*10920Sshannon 130*10920Sshannon } while (r); 131*10920Sshannon dirp = head -> next; 132*10920Sshannon dirq = dirp -> next; 133*10920Sshannon } 134*10920Sshannon 135*10920Sshannon exch (v, vs, x, w, ws) 136*10920Sshannon struct node *v, *w; 137*10920Sshannon union treep x; 138*10920Sshannon int vs, ws; 139*10920Sshannon { 140*10920Sshannon 141*10920Sshannon if (v -> fath . flags & (vs ? RLEAF : LLEAF)) { 142*10920Sshannon in [x . ch] . fp = w; 143*10920Sshannon in [x . ch] . flags &= ~01; 144*10920Sshannon if (ws) in [x . ch] . flags |= ws; 145*10920Sshannon } 146*10920Sshannon else { 147*10920Sshannon (x . p) -> fath . fp = w; 148*10920Sshannon (x . p) -> fath . flags &= ~01; 149*10920Sshannon if (ws) (x . p) -> fath . flags |= ws; 150*10920Sshannon } 151*10920Sshannon } 152