Return to node.c CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / new / B / src / bed

Annotation of 43BSDTahoe/new/B/src/bed/node.c, revision 1.1

1.1     ! root        1: /* Copyright (c) Stichting Mathematisch Centrum, Amsterdam, 1984. */
        !             2: static char rcsid[] = "$Header: node.c,v 2.4 85/08/22 16:05:27 timo Exp $";
        !             3: 
        !             4: /*
        !             5:  * B editor -- Parse tree and Focus stack.
        !             6:  */
        !             7: 
        !             8: #include "b.h"
        !             9: #include "bobj.h"
        !            10: 
        !            11: #include "node.h"
        !            12: 
        !            13: #define Register register
        !            14:        /* Used for registers 4-6.  Define as empty macro on PDP */
        !            15: 
        !            16: 
        !            17: /*
        !            18:  * Lowest level routines for 'node' data type.
        !            19:  */
        !            20: 
        !            21: #define Isnode(n) ((n) && (n)->type == Nod)
        !            22: 
        !            23: #define Nchildren(n) ((n)->len)
        !            24: #define Symbol(n) ((n)->n_symbol)
        !            25: #define Child(n, i) ((n)->n_child[(i)-1])
        !            26: #define Marks(n) ((n)->n_marks)
        !            27: #define Width(n) ((n)->n_width)
        !            28: 
        !            29: 
        !            30: /*
        !            31:  * Routines which are macros for the compiler but real functions for lint,
        !            32:  * so it will check the argument types more strictly.
        !            33:  */
        !            34: 
        !            35: #ifdef lint
        !            36: node
        !            37: nodecopy(n)
        !            38:        node n;
        !            39: {
        !            40:        return (node) copy((value) n);
        !            41: }
        !            42: 
        !            43: noderelease(n)
        !            44:        node n;
        !            45: {
        !            46:        release((value)n);
        !            47: }
        !            48: 
        !            49: nodeuniql(pn)
        !            50:        node *pn;
        !            51: {
        !            52:        uniql((value*)pn);
        !            53: }
        !            54: #endif lint
        !            55: 
        !            56: 
        !            57: /*
        !            58:  * Allocate a new node.
        !            59:  */
        !            60: 
        !            61: Visible node
        !            62: newnode(nch, sym, children)
        !            63:        register int nch;
        !            64:        Register int sym;
        !            65:        register node children[];
        !            66: {
        !            67:        register node n = (node) grab_node(nch); /* Must preset with zeros! */
        !            68: 
        !            69:        Symbol(n) = sym;
        !            70:        for (; nch > 0; --nch)
        !            71:                Child(n, nch) = children[nch-1];
        !            72:        Width(n) = evalwidth(n);
        !            73:        return n;
        !            74: }
        !            75: 
        !            76: 
        !            77: /*
        !            78:  * Macros to change the fields of a node.
        !            79:  */
        !            80: 
        !            81: #define Locchild(pn, i) \
        !            82:        (Refcnt(*(pn)) == 1 || nodeuniql(pn), &Child(*(pn), i))
        !            83: #define Setmarks(pn, x) \
        !            84:        (Refcnt(*(pn)) == 1 || nodeuniql(pn), Marks(*(pn))=(x))
        !            85: #define Setwidth(pn, w) (Refcnt(*(pn)) == 1 || nodeuniql(pn), Width(*(pn))=w)
        !            86: 
        !            87: 
        !            88: /*
        !            89:  * Change a child of a node.
        !            90:  * Like replace(), it does not increase the reference count of n.
        !            91:  */
        !            92: 
        !            93: Visible Procedure
        !            94: setchild(pn, i, n)
        !            95:        register node *pn;
        !            96:        register int i;
        !            97:        Register node n;
        !            98: {
        !            99:        register node *pch;
        !           100:        register node oldchild;
        !           101: 
        !           102:        Assert(Isnode(*pn));
        !           103:        pch = Locchild(pn, i);
        !           104:        oldchild = *pch;
        !           105:        *pch = n;
        !           106:        repwidth(pn, oldchild, n);
        !           107:        noderelease(oldchild);
        !           108: }
        !           109: 
        !           110: 
        !           111: /*
        !           112:  * Lowest level routines for 'path' data type.
        !           113:  */
        !           114: 
        !           115: #define NPATHFIELDS 6
        !           116: 
        !           117: #define Parent(p) ((p)->p_parent)
        !           118: #define Tree(p) ((p)->p_tree)
        !           119: #define Ichild(p) ((p)->p_ichild)
        !           120: #define Ycoord(p) ((p)->p_ycoord)
        !           121: #define Xcoord(p) ((p)->p_xcoord)
        !           122: #define Level(p) ((p)->p_level)
        !           123: 
        !           124: 
        !           125: /*
        !           126:  * Routines which are macros for the compiler but real functions for lint,
        !           127:  * so it will check the argument types more strictly.
        !           128:  */
        !           129: 
        !           130: #ifdef lint
        !           131: Visible path
        !           132: pathcopy(p)
        !           133:        path p;
        !           134: {
        !           135:        return (path) copy((value) p);
        !           136: }
        !           137: 
        !           138: Visible Procedure
        !           139: pathrelease(p)
        !           140:        path p;
        !           141: {
        !           142:        release((value)p);
        !           143: }
        !           144: 
        !           145: Visible Procedure
        !           146: pathuniql(pp)
        !           147:        path *pp;
        !           148: {
        !           149:        uniql((value*)pp);
        !           150: }
        !           151: #endif lint
        !           152: 
        !           153: 
        !           154: /*
        !           155:  * Allocate a new path entry.
        !           156:  */
        !           157: 
        !           158: Visible path
        !           159: newpath(pa, n, i)
        !           160:        register path pa;
        !           161:        register node n;
        !           162:        Register int i;
        !           163: {
        !           164:        register path p = (path) grab_path();
        !           165: 
        !           166:        Parent(p) = pa;
        !           167:        Tree(p) = n;
        !           168:        Ichild(p) = i;
        !           169:        Ycoord(p) = Xcoord(p) = Level(p) = 0;
        !           170:        return p;
        !           171: }
        !           172: 
        !           173: 
        !           174: /*
        !           175:  * Macros to change the fields of a path entry.
        !           176:  */
        !           177: 
        !           178: #define Uniqp(pp) (Refcnt(*(pp)) == 1 || pathuniql(pp))
        !           179: 
        !           180: #define Setcoord(pp, y, x, level) (Uniqp(pp), \
        !           181:        (*(pp))->p_ycoord = y, (*(pp))->p_xcoord = x, (*(pp))->p_level = level)
        !           182: 
        !           183: #define Locparent(pp) (Uniqp(pp), &Parent(*(pp)))
        !           184: 
        !           185: #define Loctree(pp) (Uniqp(pp), &Tree(*(pp)))
        !           186: 
        !           187: #define Addmarks(pp, x) (Uniqp(pp), \
        !           188:        (*(pp))->p_addmarks |= (x), (*(pp))->p_delmarks &= ~(x))
        !           189: 
        !           190: #define Delmarks(pp, x) (Uniqp(pp), \
        !           191:        (*(pp))->p_delmarks |= (x), (*(pp))->p_addmarks &= ~(x))
        !           192: 
        !           193: 
        !           194: Hidden Procedure
        !           195: connect(pp)
        !           196:        path *pp;
        !           197: {
        !           198:        register path p = *pp;
        !           199:        register path pa = Parent(p);
        !           200:        register path *ppa;
        !           201:        register node n;
        !           202:        register node npa;
        !           203:        register node *pn;
        !           204:        node oldchild;
        !           205:        node *pnpa;
        !           206:        int i;
        !           207:        markbits add;
        !           208:        markbits del;
        !           209: 
        !           210:        if (!pa)
        !           211:                return;
        !           212:        i = ichild(p);
        !           213:        n = Tree(p);
        !           214:        if (Child(Tree(pa), i) == n)
        !           215:                return; /* Still connected */
        !           216: 
        !           217:        n = nodecopy(n);
        !           218:        ppa = Locparent(pp);
        !           219:        pnpa = Loctree(ppa);
        !           220:        pn = Locchild(pnpa, i);
        !           221:        oldchild = *pn;
        !           222:        *pn = n;
        !           223:        repwidth(pnpa, oldchild, n);
        !           224:        noderelease(oldchild);
        !           225: 
        !           226:        add = p->p_addmarks;
        !           227:        del = p->p_delmarks;
        !           228:        if (add|del) {
        !           229:                p = *pp;
        !           230:                p->p_addmarks = 0;
        !           231:                p->p_delmarks = 0;
        !           232:                if (add)
        !           233:                        Addmarks(ppa, add);
        !           234:                npa = *pnpa;
        !           235:                if (del) {
        !           236:                        for (i = Nchildren(npa); i > 0; --i)
        !           237:                                if (i != ichild(p))
        !           238:                                        del &= ~marks(Child(npa, i));
        !           239:                        Delmarks(ppa, del);
        !           240:                }
        !           241:                Setmarks(pnpa, Marks(npa)&~del|add);
        !           242:        }
        !           243: }
        !           244: 
        !           245: 
        !           246: /*
        !           247:  * The following procedure sets the new width of node *pn when child
        !           248:  * oldchild is replaced by child newchild.
        !           249:  * This was added because the original call to evalwidth seemed to
        !           250:  * be the major caller of noderepr() and fwidth().
        !           251:  */
        !           252: 
        !           253: Hidden Procedure
        !           254: repwidth(pn, old, new)
        !           255:        register node *pn;
        !           256:        Register node old;
        !           257:        Register node new;
        !           258: {
        !           259:        register int w = Width(*pn);
        !           260:        register int oldwidth = width(old);
        !           261:        register int newwidth = width(new);
        !           262: 
        !           263:        if (w < 0) {
        !           264:                if (oldwidth > 0)
        !           265:                        oldwidth = 0;
        !           266:                if (newwidth > 0)
        !           267:                        newwidth = 0;
        !           268:        }
        !           269:        else {
        !           270:                Assert(oldwidth >= 0);
        !           271:                if (newwidth < 0) {
        !           272:                        Setwidth(pn, newwidth);
        !           273:                        return;
        !           274:                }
        !           275:        }
        !           276:        newwidth -= oldwidth;
        !           277:        if (newwidth)
        !           278:                Setwidth(pn, w + newwidth);
        !           279: }
        !           280: 
        !           281: 
        !           282: Visible Procedure
        !           283: markpath(pp, new)
        !           284:        register path *pp;
        !           285:        register markbits new;
        !           286: {
        !           287:        register node *pn;
        !           288:        register markbits old;
        !           289: 
        !           290:        Assert(Type(Tree(*pp)) == Nod);
        !           291:        old = Marks(Tree(*pp));
        !           292:        if ((old|new) == old)
        !           293:                return; /* Bits already set */
        !           294: 
        !           295:        pn = Loctree(pp);
        !           296:        Setmarks(pn, old|new);
        !           297:        Addmarks(pp, new&~old);
        !           298: }
        !           299: 
        !           300: 
        !           301: Visible Procedure
        !           302: unmkpath(pp, del)
        !           303:        register path *pp;
        !           304:        register int del;
        !           305: {
        !           306:        register node *pn;
        !           307:        register markbits old;
        !           308: 
        !           309:        Assert(Type(Tree(*pp)) == Nod);
        !           310:        old = Marks(Tree(*pp));
        !           311:        if ((old&~del) == del)
        !           312:                return;
        !           313: 
        !           314:        pn = Loctree(pp);
        !           315:        Setmarks(pn, old&~del);
        !           316:        Delmarks(pp, del&old);
        !           317: }
        !           318: 
        !           319: 
        !           320: Hidden Procedure
        !           321: clearmarks(pn)
        !           322:        register node *pn;
        !           323: {
        !           324:        register int i;
        !           325: 
        !           326:        if (!Marks(*pn))
        !           327:                return;
        !           328:        if (Isnode(*pn)) {
        !           329:                Setmarks(pn, 0);
        !           330:                for (i = Nchildren(*pn); i > 0; --i)
        !           331:                        clearmarks(Locchild(pn, i));
        !           332:        }
        !           333: }
        !           334: 
        !           335: 
        !           336: /*
        !           337:  * Replace the focus' tree by a new node.
        !           338:  * WARNING: n's reference count is not increased!
        !           339:  * You can also think of this as: replace(pp, n) implies noderelease(n).
        !           340:  * Mark bits are copied from the node being replaced.
        !           341:  */
        !           342: 
        !           343: Visible Procedure
        !           344: replace(pp, n)
        !           345:        register path *pp;
        !           346:        register node n;
        !           347: {
        !           348:        register node *pn;
        !           349:        register markbits old;
        !           350: 
        !           351:        pn = Loctree(pp);
        !           352:        if (Type(*pn) == Nod)
        !           353:                old = Marks(*pn);
        !           354:        else
        !           355:                old = 0;
        !           356:        noderelease(*pn);
        !           357:        *pn = n;
        !           358:        if (Type(n) == Nod) {
        !           359:                clearmarks(pn);
        !           360:                if (old)
        !           361:                        Setmarks(pn, old);
        !           362:        }
        !           363:        else if (old)
        !           364:                Addmarks(pp, old);
        !           365: }
        !           366: 
        !           367: 
        !           368: Visible bool
        !           369: up(pp)
        !           370:        register path *pp;
        !           371: {
        !           372:        register path p = *pp;
        !           373: 
        !           374:        if (!Parent(p))
        !           375:                return No;
        !           376: 
        !           377:        connect(pp);
        !           378:        p = pathcopy(Parent(*pp));
        !           379:        pathrelease(*pp);
        !           380:        *pp = p;
        !           381:        return Yes;
        !           382: }
        !           383: 
        !           384: 
        !           385: Visible bool
        !           386: downi(pp, i)
        !           387:        register path *pp;
        !           388:        register int i;
        !           389: {
        !           390:        register node n;
        !           391:        auto int y;
        !           392:        auto int x;
        !           393:        auto int level;
        !           394: 
        !           395:        n = Tree(*pp);
        !           396:        if (!Isnode(n) || i < 1 || i > Nchildren(n))
        !           397:                return No;
        !           398: 
        !           399:        y = Ycoord(*pp);
        !           400:        x = Xcoord(*pp);
        !           401:        level = Level(*pp);
        !           402:        *pp = newpath(*pp, nodecopy(Child(n, i)), i);
        !           403:        evalcoord(n, i, &y, &x, &level);
        !           404:        Setcoord(pp, y, x, level);
        !           405:        return Yes;
        !           406: }
        !           407: 
        !           408: 
        !           409: Visible bool
        !           410: downrite(pp)
        !           411:        register path *pp;
        !           412: {
        !           413:        if (!Isnode(Tree(*pp)))
        !           414:                return No;
        !           415:        return downi(pp, Nchildren(Tree(*pp)));
        !           416: }
        !           417: 
        !           418: 
        !           419: Visible bool
        !           420: left(pp)
        !           421:        register path *pp;
        !           422: {
        !           423:        register int i;
        !           424: 
        !           425:        i = ichild(*pp) - 1;
        !           426:        if (i <= 0)
        !           427:                return No;
        !           428:        if (!up(pp))
        !           429:                return No;
        !           430:        return downi(pp, i);
        !           431: }
        !           432: 
        !           433: 
        !           434: Visible bool
        !           435: rite(pp)
        !           436:        register path *pp;
        !           437: {
        !           438:        register int i;
        !           439:        register path pa = Parent(*pp);
        !           440: 
        !           441:        i = ichild(*pp) + 1;
        !           442:        if (!pa || i > Nchildren(Tree(pa)))
        !           443:                return No;
        !           444:        if (!up(pp))
        !           445:                return No;
        !           446:        return downi(pp, i);
        !           447: }
        !           448: 
        !           449: 
        !           450: /*
        !           451:  * Highest level: small utilities.
        !           452:  *
        !           453:  * WARNING: Several of the following routines may change their argument
        !           454:  * even if they return No.
        !           455:  * HINT: Some of these routines are not used; they are included for
        !           456:  * completeness of the provided set of operators only.  If you have
        !           457:  * space problems (as, e.g., on a PDP-11), you can delete the superfluous
        !           458:  * ones (lint will tell you which they are).
        !           459:  */
        !           460: 
        !           461: Visible Procedure
        !           462: top(pp)
        !           463:        register path *pp;
        !           464: {
        !           465:        while (up(pp))
        !           466:                ;
        !           467: }
        !           468: 
        !           469: 
        !           470: Visible bool
        !           471: nextnode(pp)
        !           472:        register path *pp;
        !           473: {
        !           474:        while (!rite(pp)) {
        !           475:                if (!up(pp))
        !           476:                        return No;
        !           477:        }
        !           478:        return Yes;
        !           479: }
        !           480: 
        !           481: 
        !           482: Visible Procedure
        !           483: firstleaf(pp)
        !           484:        register path *pp;
        !           485: {
        !           486:        while (down(pp))
        !           487:                ;
        !           488: }
        !           489: 
        !           490: #if NOT_USED
        !           491: 
        !           492: Visible bool
        !           493: nextleaf(pp)
        !           494:        register path *pp;
        !           495: {
        !           496:        if (!nextnode(pp))
        !           497:                return No;
        !           498:        firstleaf(pp);
        !           499:        return Yes;
        !           500: }
        !           501: 
        !           502: #endif NOT_USED
        !           503: 
        !           504: Visible bool
        !           505: prevnode(pp)
        !           506:        register path *pp;
        !           507: {
        !           508:        while (!left(pp)) {
        !           509:                if (!up(pp))
        !           510:                        return No;
        !           511:        }
        !           512:        return Yes;
        !           513: }
        !           514: 
        !           515: Visible Procedure
        !           516: lastleaf(pp)
        !           517:        register path *pp;
        !           518: {
        !           519:        while (downrite(pp))
        !           520:                        ;
        !           521: }
        !           522: 
        !           523: #ifdef NOT_USED
        !           524: 
        !           525: Visible bool
        !           526: prevleaf(pp)
        !           527:        register path *pp;
        !           528: {
        !           529:        if (!prevnode(pp))
        !           530:                return No;
        !           531:        lastleaf(pp);
        !           532:        return Yes;
        !           533: }
        !           534: 
        !           535: 
        !           536: Visible bool
        !           537: nextmarked(pp, x)
        !           538:        register path *pp;
        !           539:        register markbits x;
        !           540: {
        !           541:        do {
        !           542:                if (!nextnode(pp))
        !           543:                        return No;
        !           544:        } while (!marked(*pp, x));
        !           545:        while (down(pp)) {
        !           546:                while (!marked(*pp, x)) {
        !           547:                        if (!rite(pp)) {
        !           548:                                up(pp) || Abort();
        !           549:                                return Yes;
        !           550:                        }
        !           551:                }
        !           552:        }
        !           553:        return Yes;
        !           554: }
        !           555: 
        !           556: #endif NOT_UED
        !           557: 
        !           558: Visible bool
        !           559: firstmarked(pp, x)
        !           560:        register path *pp;
        !           561:        register markbits x;
        !           562: {
        !           563:        while (!marked(*pp, x)) {
        !           564:                if (!up(pp))
        !           565:                        return No;
        !           566:        }
        !           567:        while (down(pp)) {
        !           568:                while (Type(tree(*pp)) == Tex || !marked(*pp, x)) {
        !           569:                        if (!rite(pp)) {
        !           570:                                up(pp) || Abort();
        !           571:                                return Yes;
        !           572:                        }
        !           573:                }
        !           574:        }
        !           575:        return Yes;
        !           576: }
        !           577: 
        !           578: 
        !           579: Visible bool
        !           580: prevmarked(pp, x)
        !           581:        register path *pp;
        !           582:        register markbits x;
        !           583: {
        !           584:        do {
        !           585:                if (!prevnode(pp))
        !           586:                        return No;
        !           587:        } while (!marked(*pp, x));
        !           588:        while (downrite(pp)) {
        !           589:                while (!marked(*pp, x)) {
        !           590:                        if (!left(pp)) {
        !           591:                                up(pp) || Abort();
        !           592:                                return Yes;
        !           593:                        }
        !           594:                }
        !           595:        }
        !           596:        return Yes;
        !           597: }
        !           598: 
        !           599: 
        !           600: /*
        !           601:  * Deliver the path length to the root.
        !           602:  */
        !           603: 
        !           604: 
        !           605: Visible Procedure
        !           606: pathlength(p)
        !           607:        register path p;
        !           608: {
        !           609:        register int n;
        !           610: 
        !           611:        for (n = 0; p; ++n)
        !           612:                p = parent(p);
        !           613:        return n;
        !           614: }
        !           615: 
        !           616: 
        !           617: /*
        !           618:  * Put a C string in a trimmed location (this name should change,
        !           619:  * the 'official' routine of this name has quite different parameters).
        !           620:  */
        !           621: 
        !           622: 
        !           623: Visible Procedure
        !           624: putintrim(pn, head, tail, str)
        !           625:        register value *pn;
        !           626:        register int head;
        !           627:        Register int tail;
        !           628:        Register string str;
        !           629: {
        !           630:        register value v = *pn; 
        !           631:        value w = head == 0 ? mk_text("") :
        !           632:                head == Length(v) ? copy(v) : trim(v, 0, Length(v) - head);
        !           633: 
        !           634:        Assert(head >= 0 && tail >= 0 && head + tail <= Length(v));
        !           635:        if (*str)
        !           636:                concato(&w, str);
        !           637:        if (tail > 0)
        !           638:                concato(&w, Str(v)+(Length(v) - tail));
        !           639:        release(v);
        !           640:        *pn = w;
        !           641: }
        !           642: 
        !           643: 
        !           644: /*
        !           645:  * Touch the node in focus.
        !           646:  */
        !           647: 
        !           648: Visible Procedure
        !           649: touchpath(pp)
        !           650:        register path *pp;
        !           651: {
        !           652:        nodeuniql(Loctree(pp));
        !           653: }

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