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