Return to tree.c CVS log

Up to [CSRG BSD Unix] / 42BSD / ucb / compact

Annotation of 42BSD/ucb/compact/tree.c, revision 1.1

1.1     ! root        1: #ifndef lint
        !             2: static char sccsid[] = "@(#)tree.c     4.2 (Berkeley) 8/11/83";
        !             3: #endif
        !             4: 
        !             5: #include "compact.h"
        !             6: 
        !             7: 
        !             8: insert (ch)
        !             9: int ch;
        !            10: {
        !            11:        register struct node *pp;
        !            12:        register int c;
        !            13:        union cio d;
        !            14:        register struct index *qt, *wt;
        !            15: 
        !            16:        c = ch;
        !            17:        wt = NEW;
        !            18:        pp = bottom++;
        !            19:        bottom -> fath . fp = pp;
        !            20:        in [c] . flags = (SEEN | FBIT);
        !            21:        d . integ = bottom -> sp [0] . ch = pp -> sp [1] . ch;
        !            22:        in [c] . fp = in [d . integ] . fp = pp -> sp [1] . p = wt -> pt = bottom;
        !            23:        bottom -> fath . flags = (LLEAF | RLEAF | FBIT);
        !            24:        pp -> fath . flags &= ~RLEAF;
        !            25:        in [d . integ] . flags = SEEN;
        !            26: 
        !            27:        bottom -> count [0] = pp -> count [1];
        !            28:        qt = pp -> top [1];
        !            29:        bottom -> top [0] = qt;
        !            30:        bottom -> sp [1] . ch = c;
        !            31:        bottom -> count [1] = 0;
        !            32:        bottom -> top [1] = qt -> 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, qs, ss, ts;
        !            42:        longint rc, qc, sc;
        !            43:        struct node *t;
        !            44:        register struct index *rt, *qt, *st;
        !            45: 
        !            46:        r = in [ch] . fp;
        !            47:        rs = in [ch] . flags & FBIT;
        !            48: 
        !            49:        do {
        !            50:                (r -> count [rs])++;
        !            51:                rc = r -> count [rs];
        !            52:                rt = r -> top [rs];
        !            53:        
        !            54:                for ( ; ; ) {
        !            55:                        qs = ss = 1 - rs;
        !            56:                        s . p = r + rs;
        !            57:                        sc = (s . p) -> count [ss];
        !            58:                        st = (s . p) -> top [ss];
        !            59:        
        !            60:                        if (rs)
        !            61:                                if (r == bottom) {
        !            62:                                        sc = rc - 2;
        !            63:                                        st = NULL;
        !            64:                                }
        !            65:                                else;
        !            66:                        else if (r == dict) {
        !            67:                                qc = rc + 1;
        !            68:                                qt = head;
        !            69:                                break;
        !            70:                        }
        !            71: 
        !            72:                        q . p = r - qs;
        !            73:                        qc = (q . p) -> count [qs];
        !            74:                        qt = (q . p) -> top [qs];
        !            75:                        if (rc <= qc) break;
        !            76: 
        !            77:                        t = qt -> pt;
        !            78:                        ts = (rc <= t -> count [0] ? 1 : 0);
        !            79: 
        !            80:                        /* exchange pointers of (t, ts) and (r, rs) */
        !            81: 
        !            82:                        q . ch = t -> sp [ts] . ch;     /*  {                                   */
        !            83:                        s . ch = r -> sp [rs] . ch;     /*  {                                   */
        !            84:                        t -> sp [ts] . ch = s . ch;     /*  {                                   */
        !            85:                        r -> sp [rs] . ch = q . ch;     /*  { change code when Cory gets v. 7   */
        !            86:                                                        /*  {                                   */
        !            87:                        exch (t, ts, q . ch, r, rs);    /*  {                                   */
        !            88:                        exch (r, rs, s . ch, t, ts);    /*  {                                   */
        !            89: 
        !            90:                        qs = (rs ? RLEAF : LLEAF);
        !            91:                        ss = (ts ? RLEAF : LLEAF);
        !            92:                        if (((r -> fath . flags & qs) << rs) ^ ((t -> fath . flags & ss) << ts)) {
        !            93:                                r -> fath . flags ^= qs;
        !            94:                                t -> fath . flags ^= ss;
        !            95:                        }
        !            96: 
        !            97:                        (t -> count [ts])++;
        !            98:                        (r -> count [rs])--;
        !            99:                        (qt -> pt) += ts;
        !           100:                        r = t;
        !           101:                        rs = ts;
        !           102:                }
        !           103: 
        !           104:                if (rc == qc) {
        !           105:                        r -> top [rs] = qt;
        !           106:                        if (rc > sc + 1) {
        !           107:                                qt -> next = st;
        !           108: 
        !           109:                                /* dispose of rt */
        !           110: 
        !           111:                                rt -> next = flist;
        !           112:                                flist = rt;
        !           113:                        }
        !           114:                        else st -> pt = s . p;
        !           115:                }
        !           116: 
        !           117:                else if (rc == sc + 1) {
        !           118: 
        !           119:                        /* create new index at rt */
        !           120: 
        !           121:                        rt = NEW;
        !           122:                        rt -> next = st;
        !           123:                        rt -> pt = r;
        !           124:                        qt -> next = rt;
        !           125:                        if (st) st -> pt = s . p;
        !           126:                        r -> top [rs] = rt;
        !           127:                }
        !           128: 
        !           129:                rs = r -> fath . flags & FBIT;
        !           130:                r = r -> fath . fp;
        !           131: 
        !           132:        } while (r);
        !           133:        dirp = head -> next;
        !           134:        dirq = dirp -> next;
        !           135: }
        !           136: 
        !           137: exch (v, vs, x, w, ws)
        !           138: struct node *v, *w;
        !           139: union treep x;
        !           140: int vs, ws;
        !           141: {
        !           142: 
        !           143:        if (v -> fath . flags & (vs ? RLEAF : LLEAF)) {
        !           144:                in [x . ch] . fp = w;
        !           145:                in [x . ch] . flags &= ~01;
        !           146:                if (ws) in [x . ch] . flags |= ws;
        !           147:        }
        !           148:        else {
        !           149:                (x . p) -> fath . fp = w;
        !           150:                (x . p) -> fath . flags &= ~01;
        !           151:                if (ws) (x . p) -> fath . flags |= ws;
        !           152:        }
        !           153: }

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