Return to tree.c CVS log

Up to [Research Unix] / researchv10dc / cmd / compact

Annotation of researchv10dc/cmd/compact/tree.c, revision 1.1.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.