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