projects / unix-history / blobdiff
? search:
summary | tags | clone url | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
BSD 4_3_Reno release
[unix-history] / usr / src / old / compact / common_source / tree.c
diff --git a/usr/src/old/compact/common_source/tree.c b/usr/src/old/compact/common_source/tree.c
index 5b75205..08e3e11 100644 (file)
--- a/usr/src/old/compact/common_source/tree.c
+++ b/usr/src/old/compact/common_source/tree.c
@@ -1,153 +1,157 @@
 #ifndef lint
 #ifndef lint
-static char sccsid[] = "@(#)tree.c     4.2 (Berkeley) %G%";
+static char sccsid[] = "@(#)tree.c     4.4 (Berkeley) 8/25/84";
 #endif
 
 #include "compact.h"
 
 #endif
 
 #include "compact.h"
 
-
-insert (ch)
-int ch;
+insert(ch)
+       int ch;
 {
        register struct node *pp;
 {
        register struct node *pp;
-       register int c;
+       register struct son *pson, *bson;
        union cio d;
        union cio d;
-       register struct index *qt, *wt;
+       register struct index *wt;
 
 
-       c = ch;
        wt = NEW;
        pp = bottom++;
        wt = NEW;
        pp = bottom++;
-       bottom -> fath . fp = pp;
-       in [c] . flags = (SEEN | FBIT);
-       d . integ = bottom -> sp [0] . ch = pp -> sp [1] . ch;
-       in [c] . fp = in [d . integ] . fp = pp -> sp [1] . p = wt -> pt = bottom;
-       bottom -> fath . flags = (LLEAF | RLEAF | FBIT);
-       pp -> fath . flags &= ~RLEAF;
-       in [d . integ] . flags = SEEN;
-
-       bottom -> count [0] = pp -> count [1];
-       qt = pp -> top [1];
-       bottom -> top [0] = qt;
-       bottom -> sp [1] . ch = c;
-       bottom -> count [1] = 0;
-       bottom -> top [1] = qt -> next = wt;
-       wt -> next = NULL;
+       pson = &pp->sons[RIGHT];
+       bson = &bottom->sons[LEFT];
+       bottom->fath.fp = pp;
+       in[ch].flags = (SEEN | FBIT);
+       d.integ = bson->sp.ch = pson->sp.ch;
+       in[ch].fp = in[d.integ].fp = pson->sp.p = wt->pt = bottom;
+       bottom->fath.flags = (LLEAF | RLEAF | FBIT);
+       pp->fath.flags &= ~RLEAF;
+       in[d.integ].flags = SEEN;
+
+       bson->count = pson->count;
+       bson->top = pson->top;
+       bson++;
+       bson->sp.ch = ch;
+       bson->count = 0;
+       bson->top = pson->top->next = wt;
+       wt->next = NULL;
 }
 
 }
 
-uptree (ch)
-int ch;
+uptree(ch)
+       int ch;
 {
        register struct node *r;
        union treep q, s;
 {
        register struct node *r;
        union treep q, s;
-       int rs, qs, ss, ts;
+       int rs, ts, rflags, tflags;
        longint rc, qc, sc;
        struct node *t;
        longint rc, qc, sc;
        struct node *t;
+       register struct son *rson, *tson;
        register struct index *rt, *qt, *st;
 
        register struct index *rt, *qt, *st;
 
-       r = in [ch] . fp;
-       rs = in [ch] . flags & FBIT;
+       r = in[ch].fp;
+       rs = in[ch].flags & FBIT;
 
        do {
 
        do {
-               (r -> count [rs])++;
-               rc = r -> count [rs];
-               rt = r -> top [rs];
-       
-               for ( ; ; ) {
-                       qs = ss = 1 - rs;
-                       s . p = r + rs;
-                       sc = (s . p) -> count [ss];
-                       st = (s . p) -> top [ss];
-       
-                       if (rs)
+               rson = &r->sons[rs];
+               rc = ++rson->count;
+               rt = rson->top;
+               for (;;) {
+                       if (rs) {
+                               s.p = r + 1;
                                if (r == bottom) {
                                        sc = rc - 2;
                                        st = NULL;
                                if (r == bottom) {
                                        sc = rc - 2;
                                        st = NULL;
+                               } else {
+                                       sc = (r+1)->sons[LEFT].count;
+                                       st = (r+1)->sons[LEFT].top;
+                               }
+                               qc = r->sons[LEFT].count;
+                               qt = r->sons[LEFT].top;
+                       } else {
+                               s.p = r;
+                               sc = r->sons[RIGHT].count;
+                               st = r->sons[RIGHT].top;
+                               if (r == dict) {
+                                       qc = rc + 1;
+                                       qt = head;
+                                       break;
+                               } else {
+                                       qc = (r-1)->sons[RIGHT].count;
+                                       qt = (r-1)->sons[RIGHT].top;
                                }
                                }
-                               else;
-                       else if (r == dict) {
-                               qc = rc + 1;
-                               qt = head;
-                               break;
                        }
                        }
+                       if (rc <= qc)
+                               break;
 
 
-                       q . p = r - qs;
-                       qc = (q . p) -> count [qs];
-                       qt = (q . p) -> top [qs];
-                       if (rc <= qc) break;
-
-                       t = qt -> pt;
-                       ts = (rc <= t -> count [0] ? 1 : 0);
+                       t = qt->pt;
+                       ts = LEFT;
+                       tson = &t->sons[LEFT];
+                       if (rc <= tson->count) {
+                               tson++;
+                               ts++;
+                       }
 
                        /* exchange pointers of (t, ts) and (r, rs) */
 
                        /* exchange pointers of (t, ts) and (r, rs) */
-
-                       q . ch = t -> sp [ts] . ch;     /*  {                                   */
-                       s . ch = r -> sp [rs] . ch;     /*  {                                   */
-                       t -> sp [ts] . ch = s . ch;     /*  {                                   */
-                       r -> sp [rs] . ch = q . ch;     /*  { change code when Cory gets v. 7   */
-                                                       /*  {                                   */
-                       exch (t, ts, q . ch, r, rs);    /*  {                                   */
-                       exch (r, rs, s . ch, t, ts);    /*  {                                   */
-
-                       qs = (rs ? RLEAF : LLEAF);
-                       ss = (ts ? RLEAF : LLEAF);
-                       if (((r -> fath . flags & qs) << rs) ^ ((t -> fath . flags & ss) << ts)) {
-                               r -> fath . flags ^= qs;
-                               t -> fath . flags ^= ss;
+                       q.ch = tson->sp.ch;
+                       s.ch = rson->sp.ch;
+                       tson->sp.ch = s.ch;
+                       rson->sp.ch = q.ch;
+                       exch(t, ts, q.ch, r, rs);
+                       exch(r, rs, s.ch, t, ts);
+
+                       rflags = (rs ? RLEAF : LLEAF);
+                       tflags = (ts ? RLEAF : LLEAF);
+                       if (((r->fath.flags & rflags) << rs) ^ ((t->fath.flags & tflags) << ts)) {
+                               r->fath.flags ^= rflags;
+                               t->fath.flags ^= tflags;
                        }
 
                        }
 
-                       (t -> count [ts])++;
-                       (r -> count [rs])--;
-                       (qt -> pt) += ts;
+                       tson->count++;
+                       rson->count--;
+                       if (ts)
+                               qt->pt++;
                        r = t;
                        rs = ts;
                        r = t;
                        rs = ts;
+                       rson = tson;
                }
 
                if (rc == qc) {
                }
 
                if (rc == qc) {
-                       r -> top [rs] = qt;
+                       rson->top = qt;
                        if (rc > sc + 1) {
                        if (rc > sc + 1) {
-                               qt -> next = st;
-
+                               qt->next = st;
                                /* dispose of rt */
                                /* dispose of rt */
-
-                               rt -> next = flist;
+                               rt->next = flist;
                                flist = rt;
                                flist = rt;
-                       }
-                       else st -> pt = s . p;
-               }
-
-               else if (rc == sc + 1) {
-
+                       } else
+                               st->pt = s.p;
+               } else if (rc == sc + 1) {
                        /* create new index at rt */
                        /* create new index at rt */
-
                        rt = NEW;
                        rt = NEW;
-                       rt -> next = st;
-                       rt -> pt = r;
-                       qt -> next = rt;
-                       if (st) st -> pt = s . p;
-                       r -> top [rs] = rt;
+                       rt->next = st;
+                       rt->pt = r;
+                       qt->next = rt;
+                       if (st)
+                               st->pt = s.p;
+                       rson->top = rt;
                }
                }
-
-               rs = r -> fath . flags & FBIT;
-               r = r -> fath . fp;
-
+               rs = r->fath.flags & FBIT;
+               r = r->fath.fp;
        } while (r);
        } while (r);
-       dirp = head -> next;
-       dirq = dirp -> next;
+       dirp = head->next;
+       dirq = dirp->next;
 }
 
 }
 
-exch (v, vs, x, w, ws)
-struct node *v, *w;
-union treep x;
-int vs, ws;
+exch(v, vs, x, w, ws)
+       struct node *v, *w;
+       union treep x;
+       int vs, ws;
 {
 
 {
 
-       if (v -> fath . flags & (vs ? RLEAF : LLEAF)) {
-               in [x . ch] . fp = w;
-               in [x . ch] . flags &= ~01;
-               if (ws) in [x . ch] . flags |= ws;
-       }
-       else {
-               (x . p) -> fath . fp = w;
-               (x . p) -> fath . flags &= ~01;
-               if (ws) (x . p) -> fath . flags |= ws;
+       if (v->fath.flags & (vs ? RLEAF : LLEAF)) {
+               in[x.ch].fp = w;
+               in[x.ch].flags &= ~01;
+               if (ws)
+                       in[x.ch].flags |= ws;
+       } else {
+               x.p->fath.fp = w;
+               x.p->fath.flags &= ~01;
+               if (ws)
+                       x.p->fath.flags |= ws;
        }
 }
        }
 }
Continuous source code history from original PDP-7 UNIX to FreeBSD 2, the first fully unencumbered FreeBSD release.