4.3BSD - /usr/src/new/B/src/bed/node.c

   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: }

Defined functions

Defined variables

Defined macros