1 #ifndef lint
2 static char sccsid[] = "@(#)tree.c 4.4 (Berkeley) 08/25/84";
3 #endif
4
5 #include "compact.h"
6
insert(ch)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
uptree(ch)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