Return to tree.c CVS log

Up to [CSRG BSD Unix] / 43BSD / old / compact

Annotation of 43BSD/old/compact/tree.c, revision 1.1

1.1     ! root        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: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.