2.9BSD - /usr/src/ucb/compact/tree.c

   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;
  82:             exch (t, ts, q . ch, r, rs);
  83:             exch (r, rs, s . ch, t, ts);
  84: 
  85:             qs = (rs ? RLEAF : LLEAF);
  86:             ss = (ts ? RLEAF : LLEAF);
  87:             if (((r -> fath . flags & qs) << rs) ^ ((t -> fath . flags & ss) << ts)) {
  88:                 r -> fath . flags ^= qs;
  89:                 t -> fath . flags ^= ss;
  90:             }
  91: 
  92:             (t -> count [ts])++;
  93:             (r -> count [rs])--;
  94:             (qt -> pt) += ts;
  95:             r = t;
  96:             rs = ts;
  97:         }
  98: 
  99:         if (rc == qc) {
 100:             r -> top [rs] = qt;
 101:             if (rc > sc + 1) {
 102:                 qt -> next = st;
 103: 
 104:                 /* dispose of rt */
 105: 
 106:                 rt -> next = flist;
 107:                 flist = rt;
 108:             }
 109:             else st -> pt = s . p;
 110:         }
 111: 
 112:         else if (rc == sc + 1) {
 113: 
 114:             /* create new index at rt */
 115: 
 116:             rt = NEW;
 117:             rt -> next = st;
 118:             rt -> pt = r;
 119:             qt -> next = rt;
 120:             if (st) st -> pt = s . p;
 121:             r -> top [rs] = rt;
 122:         }
 123: 
 124:         rs = r -> fath . flags & FBIT;
 125:         r = r -> fath . fp;
 126: 
 127:     } while (r);
 128:     dirp = head -> next;
 129:     dirq = dirp -> next;
 130: }
 131: 
 132: exch (v, vs, x, w, ws)
 133: struct node *v, *w;
 134: union treep x;
 135: int vs, ws;
 136: {
 137: 
 138:     if (v -> fath . flags & (vs ? RLEAF : LLEAF)) {
 139:         in [x . ch] . fp = w;
 140:         in [x . ch] . flags &= ~01;
 141:         if (ws) in [x . ch] . flags |= ws;
 142:     }
 143:     else {
 144:         (x . p) -> fath . fp = w;
 145:         (x . p) -> fath . flags &= ~01;
 146:         if (ws) (x . p) -> fath . flags |= ws;
 147:     }
 148: }

Defined functions