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

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.