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