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