4.3BSD - /usr/src/old/compact/tree.c

   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: }

Defined functions

Defined variables