![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to tree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDTahoe / old / compact|
Return to tree.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / old / compact |
1.1 root 1: #ifndef lint
2: static char sccsid[] = "@(#)tree.c 4.4 (Berkeley) 8/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: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.