# 2.11BSD#431 - /usr/src/old/compact/tree.c

##### Functions

    exch              X
    insert            X
    uptree            X

       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

exch defined in line 140; used 2 times

- in line 95-96(2)

insert defined in line 7; used 2 times

- in /usr/src/old/compact/compact.c line 240
- in /usr/src/old/compact/uncompact.c line 151

uptree defined in line 36; used 4 times

- in /usr/src/old/compact/compact.c line 239, 259
- in /usr/src/old/compact/uncompact.c line 140, 153

#### Defined variables

sccsid defined in line 2; never used

Last modified: 1984-08-26 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1156 |