Return to tree.c CVS log

Up to [CSRG BSD Unix] / 41BSD / cmd / compact

Annotation of 41BSD/cmd/compact/tree.c, revision 1.1

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

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