projects / unix-history / blame
| 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 | } |