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