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