1: /* pathalias -- by steve bellovin, as told to peter honeyman */
   2: #ifndef lint
   3: static char *sccsid = "@(#)mapit.c	9.1 87/10/04";
   4: #endif
   5: 
   6: #include "def.h"
   7: 
   8: #define chkheap(i)  /* void */
   9: 
  10: /* exports */
  11: /* invariant while mapping: Nheap < Hashpart */
  12: long Hashpart;      /* start of unreached nodes */
  13: long Nheap;     /* end of heap */
  14: 
  15: void mapit();
  16: 
  17: /* imports */
  18: extern long Nheap, Hashpart, Tabsize;
  19: extern int Tflag, Vflag;
  20: extern p_node *Table;
  21: extern p_node Home;
  22: #ifndef TMPFILES
  23: #define getnode(x) x
  24: #define getlink(y) y
  25: #else  /*TMPFILES*/
  26: extern node *getnode();
  27: extern link *getlink();
  28: #endif /*TMPFILES*/
  29: extern char *Linkout, *Graphout;
  30: 
  31: extern void freelink(), resetnodes(), printit(), dumpgraph();
  32: extern void showlinks(), die();
  33: extern long pack(), allocation();
  34: extern p_link newlink();
  35: extern p_link addlink();
  36: extern int maptrace();
  37: extern p_node ncopy();
  38: 
  39: 
  40: /* privates */
  41: static long Heaphighwater;
  42: static p_link   *Heap;
  43: 
  44: STATIC void insert(), heapup(), heapdown(), heapswap(), backlinks();
  45: STATIC void setheapbits(), mtracereport(), heapchildren();
  46: STATIC p_link min_node();
  47: STATIC int dehash(), skiplink(), skipterminalalias();
  48: STATIC Cost costof();
  49: 
  50: /* transform the graph to a shortest-path tree by marking tree edges */
  51: void
  52: mapit()
  53: {   register p_node n;
  54:     register p_link l;
  55:     p_link lparent;
  56:     static int firsttime = 0;
  57: 
  58:     vprintf(stderr, "*** mapping\n");
  59:     Tflag = Tflag && Vflag;     /* tracing here only if verbose */
  60:     /* re-use the hash table space for the heap */
  61:     Heap = (p_link *) Table;
  62:     Hashpart = pack(0L, Tabsize - 1);
  63: 
  64:     /* expunge penalties from -a option and make circular copy lists */
  65:     resetnodes();
  66: 
  67:     if (firsttime++) {
  68:         if (Linkout && *Linkout)    /* dump cheapest links */
  69:             showlinks();
  70:         if (Graphout && *Graphout)  /* dump the edge list */
  71:             dumpgraph();
  72:     }
  73: 
  74:     /* insert Home to get things started */
  75:     l = newlink();      /* link to get things started */
  76:     getlink(l)->l_to = Home;
  77:     (void) dehash(Home);
  78:     insert(l);
  79: 
  80:     /* main mapping loop */
  81: remap:
  82:     Heaphighwater = Nheap;
  83:     while ((lparent = min_node()) != 0) {
  84:         chkheap(1);
  85:         getlink(lparent)->l_flag |= LTREE;
  86:         n = getlink(lparent)->l_to;
  87:         if (Tflag && maptrace(n, n))
  88:             fprintf(stderr, "%s -> %s mapped\n",
  89:                 getnode(getnode(n)->n_parent)->n_name,
  90:                 getnode(n)->n_name);
  91:         if (getnode(n)->n_flag & MAPPED)
  92:             die("mapped node in heap");
  93:         getnode(n)->n_flag |= MAPPED;
  94: 
  95:         /* add children to heap */
  96:         heapchildren(n);
  97:     }
  98:     vprintf(stderr, "heap high water mark was %ld\n", Heaphighwater);
  99: 
 100:     /* sanity check on implementation */
 101:     if (Nheap != 0)
 102:         die("null entry in heap");
 103: 
 104:     if (Hashpart < Tabsize) {
 105:         /*
 106: 		 * add back links from unreachable hosts to
 107: 		 * reachable neighbors, then remap.
 108: 		 *
 109: 		 * asymptotically, this is quadratic; in
 110: 		 * practice, this is done once or twice.
 111: 		 */
 112:         backlinks();
 113:         if (Nheap)
 114:             goto remap;
 115:     }
 116:     if (Hashpart < Tabsize) {
 117:         fputs("You can't get there from here:\n", stderr);
 118:         for ( ; Hashpart < Tabsize; Hashpart++) {
 119:             fprintf(stderr, "\t%s", getnode(Table[Hashpart])->n_name);
 120:             if (getnode(Table[Hashpart])->n_flag & ISPRIVATE)
 121:                 fputs(" (private)", stderr);
 122:             putc('\n', stderr);
 123:         }
 124:     }
 125: }
 126: 
 127: STATIC void
 128: heapchildren(n)
 129:     register p_node n;
 130: {   register p_link l;
 131:     register p_node next;
 132:     register int mtrace;
 133:     register Cost cost;
 134: 
 135:     for (l = getnode(n)->n_link; l; l = getlink(l)->l_next) {
 136: 
 137:         next = getlink(l)->l_to;    /* neighboring node */
 138:         mtrace = Tflag && maptrace(n, next);
 139: 
 140:         if (getnode(next)->n_flag & MAPPED) {
 141:             if (mtrace)
 142:                 mtracereport(n, l, "-\talready mapped");
 143:             continue;
 144:         }
 145:         if (getlink(l)->l_flag & LTREE)
 146:             continue;
 147: 
 148:         if (getlink(l)->l_flag & LTERMINAL) {
 149:             next = ncopy(next);
 150:             getlink(l)->l_to = next;
 151:         }
 152: 
 153:         if ((getnode(n)->n_flag & NTERMINAL)
 154:              && (getlink(l)->l_flag & LALIAS))
 155:             if (skipterminalalias(n, next))
 156:                 continue;
 157:             else {
 158:                 next = ncopy(next);
 159:                 getlink(l)->l_to = next;
 160:             }
 161: 
 162:         cost = costof(n, l);
 163: 
 164:         if (skiplink(l, n, cost, mtrace))
 165:             continue;
 166: 
 167:         /*
 168: 		 * put this link in the heap and restore the
 169: 		 * heap property.
 170: 		 */
 171:         if (mtrace) {
 172:             if (getnode(next)->n_parent)
 173:                 mtracereport(getnode(next)->n_parent, l, "*\tdrop");
 174:             mtracereport(n, l, "+\tadd");
 175:         }
 176:         getnode(next)->n_parent = n;
 177:         if (dehash(next) == 0) {  /* first time */
 178:             getnode(next)->n_cost = cost;
 179:             insert(l);    /* insert at end */
 180:             heapup(l);
 181:         } else {
 182:             /* replace inferior path */
 183:             Heap[getnode(next)->n_tloc] = l;
 184:             if (cost > getnode(next)->n_cost) {
 185:                 /* increase cost (gateway) */
 186:                 getnode(next)->n_cost = cost;
 187:                 heapdown(l);
 188:             } else if (cost < getnode(next)->n_cost) {
 189:                 /* cheaper route */
 190:                 getnode(next)->n_cost = cost;
 191: 
 192:                 heapup(l);
 193:             }
 194:         }
 195:         setheapbits(l);
 196:         chkheap(1);
 197: 
 198:     }
 199: }
 200: 
 201: /* bizarro special case */
 202: STATIC
 203: skipterminalalias(n, next)
 204:     p_node n;
 205:     p_node next;
 206: {   p_node ncp;
 207: 
 208:     while (getnode(n)->n_flag & NALIAS) {
 209:         n = getnode(n)->n_parent;
 210:         for (ncp = getnode(n)->n_copy; ncp != n; ncp = getnode(ncp)->n_copy)
 211:             if (next == ncp)
 212:                 return 1;
 213:     }
 214:     return 0;
 215: }
 216: 
 217: /*
 218:  * return 1 if we definitely don't want want this link in the
 219:  * shortest path tree, 0 if we might want it, i.e., best so far.
 220:  *
 221:  * if tracing is turned on, report only if this node is being skipped.
 222:  */
 223: STATIC int
 224: skiplink(l, parent, cost, trace)
 225:     p_link l;       /* new link to this node */
 226:     p_node parent;      /* (potential) new parent of this node */
 227:     register Cost cost; /* new cost to this node */
 228:     int trace;      /* trace this link? */
 229: {   register p_node n;  /* this node */
 230:     register p_link lheap;      /* old link to this node */
 231: 
 232:     n = getlink(l)->l_to;
 233: 
 234:     /* first time we've reached this node? */
 235:     if (getnode(n)->n_tloc >= Hashpart)
 236:         return 0;
 237: 
 238:     lheap = Heap[getnode(n)->n_tloc];
 239: 
 240:     /* examine links to nets that require gateways */
 241:     if (GATEWAYED(getnode(n))) {
 242:         /* if exactly one is a gateway, use it */
 243:         if ((getlink(lheap)->l_flag & LGATEWAY)
 244:              && !(getlink(l)->l_flag & LGATEWAY)) {
 245:             if (trace)
 246:                 mtracereport(parent, l, "-\told gateway");
 247:             return 1;   /* old is gateway */
 248:         }
 249:         if (!(getlink(lheap)->l_flag & LGATEWAY)
 250:               && (getlink(l)->l_flag & LGATEWAY))
 251:             return 0;   /* new is gateway */
 252: 
 253:         /* no gateway or both gateways;  resolve in standard way ... */
 254:     }
 255: 
 256:     /* examine dup link (sanity check) */
 257:     if (getnode(n)->n_parent == parent && ((getlink(lheap)->l_flag & LDEAD)
 258:         || (getlink(l)->l_flag & LDEAD)))
 259:         die("dup dead link");
 260: 
 261:     /*  examine cost */
 262:     if (cost < getnode(n)->n_cost)
 263:         return 0;
 264:     if (cost > getnode(n)->n_cost) {
 265:         if (trace)
 266:             mtracereport(parent, l, "-\tcheaper");
 267:         return 1;
 268:     }
 269: 
 270:     /* all other things being equal, ask the oracle */
 271:     if (tiebreaker(n, parent)) {
 272:         if (trace)
 273:             mtracereport(parent, l, "-\ttiebreaker");
 274:         return 1;
 275:     }
 276:     return 0;
 277: }
 278: 
 279: STATIC Cost
 280: costof(prev, l)
 281:     register p_node prev;
 282:     register p_link l;
 283: {   register p_node next;
 284:     register Cost cost;
 285: 
 286:     if (getlink(l)->l_flag & LALIAS)
 287:         return getnode(prev)->n_cost;   /* by definition */
 288: 
 289:     next = getlink(l)->l_to;
 290:     cost = getnode(prev)->n_cost + getlink(l)->l_cost; /* basic cost */
 291: 
 292:     /*
 293: 	 * heuristics:
 294: 	 *    charge for a dead link.
 295: 	 *    charge for getting past a terminal edge.
 296: 	 *    charge for getting out of a dead host.
 297: 	 *    charge for getting into a gatewayed net (except at a gateway).
 298: 	 *    discourage mixing of left and right syntax when prev is a host.
 299: 	 *
 300: 	 * life was simpler when pathalias computed true shortest paths.
 301: 	 */
 302:     if (getlink(l)->l_flag & LDEAD)         /* dead link */
 303:         cost += INF;
 304:     if (getnode(prev)->n_flag & NTERMINAL)      /* terminal parent */
 305:         cost += INF;
 306:     if (DEADHOST(getnode(prev)))            /* dead host */
 307:         cost += INF;
 308:     if (GATEWAYED(getnode(next)) && !(getlink(l)->l_flag & LGATEWAY))
 309:         cost += INF;                /* not gateway */
 310:     if (!ISANET(getnode(prev))) {           /* mixed syntax? */
 311:         if ((NETDIR(getlink(l)) == LLEFT
 312:              && (getnode(prev)->n_flag & HASRIGHT))
 313:          || (NETDIR(getlink(l)) == LRIGHT
 314:              && (getnode(prev)->n_flag & HASLEFT)))
 315:             cost += INF;
 316:     }
 317: 
 318:     return cost;
 319: }
 320: 
 321: /* binary heap implementation of priority queue */
 322: 
 323: STATIC void
 324: insert(l)
 325:     p_link l;
 326: {   register p_node n;
 327: 
 328:     n = getlink(l)->l_to;
 329:     if (getnode(n)->n_flag & MAPPED)
 330:         die("insert mapped node");
 331: 
 332:     Heap[getnode(n)->n_tloc] = 0;
 333:     if (Heap[Nheap+1] != 0)
 334:         die("heap error in insert");
 335:     if (Nheap++ == 0) {
 336:         Heap[1] = l;
 337:         getnode(n)->n_tloc = 1;
 338:         return;
 339:     }
 340:     if (Vflag && Nheap > Heaphighwater)
 341:         Heaphighwater = Nheap;  /* diagnostics */
 342: 
 343:     /* insert at the end.  caller must heapup(l). */
 344:     Heap[Nheap] = l;
 345:     getnode(n)->n_tloc = Nheap;
 346: }
 347: 
 348: /*
 349:  * "percolate" up the heap by exchanging with the parent.  as in
 350:  * min_node(), give tiebreaker() a chance to produce better, stable
 351:  * routes by moving nets and domains close to the root, nets closer
 352:  * than domains.
 353:  *
 354:  * i know this seems obscure, but it's harmless and cheap.  trust me.
 355:  */
 356: STATIC void
 357: heapup(l)
 358:     p_link l;
 359: {   register long cindx, pindx; /* child, parent indices */
 360:     register Cost cost;
 361:     register p_node child;
 362:     register p_node parent;
 363: 
 364:     child = getlink(l)->l_to;
 365: 
 366:     cost = getnode(child)->n_cost;
 367:     for (cindx = getnode(child)->n_tloc; cindx > 1; cindx = pindx) {
 368:         pindx = cindx / 2;
 369:         if (Heap[pindx] == 0)   /* sanity check */
 370:             die("impossible error in heapup");
 371:         parent = getlink(Heap[pindx])->l_to;
 372:         if (cost > getnode(parent)->n_cost)
 373:             return;
 374: 
 375:         /* net/domain heuristic */
 376:         if (cost == getnode(parent)->n_cost) {
 377:             if (!ISANET(getnode(child)))
 378:                 return;
 379:             if (!ISADOMAIN(getnode(parent)))
 380:                 return;
 381:             if (ISADOMAIN(getnode(child)))
 382:                 return;
 383:         }
 384:         heapswap(cindx, pindx);
 385:     }
 386: }
 387: 
 388: /* extract min (== Heap[1]) from heap */
 389: STATIC p_link
 390: min_node()
 391: {   p_link rval;
 392:     p_link lastlink;
 393:     register p_link *rheap;
 394: 
 395:     if (Nheap == 0)
 396:         return 0;
 397: 
 398:     rheap = Heap;       /* in register -- heavily used */
 399:     rval = rheap[1];    /* return this one */
 400: 
 401:     /* move last entry into root and reheap */
 402:     lastlink = rheap[Nheap];
 403:     rheap[Nheap] = 0;
 404: 
 405:     if (--Nheap) {
 406:         rheap[1] = lastlink;
 407:         getnode(getlink(lastlink)->l_to)->n_tloc = 1;
 408:         heapdown(lastlink); /* restore heap property */
 409:     }
 410: 
 411:     return rval;
 412: }
 413: 
 414: /*
 415:  * swap Heap[i] with smaller child, iteratively down the tree.
 416:  *
 417:  * given the opportunity, attempt to place nets and domains
 418:  * near the root.  this helps tiebreaker() shun domain routes.
 419:  */
 420: 
 421: STATIC void
 422: heapdown(l)
 423:     p_link l;
 424: {   register long pindx, cindx;
 425:     register p_link *rheap = Heap;  /* in register -- heavily used */
 426:     p_node child;
 427:     p_node rchild;
 428:     p_node parent;
 429: 
 430:     pindx = getnode(getlink(l)->l_to)->n_tloc;
 431:     parent = getlink(rheap[pindx])->l_to;   /* invariant */
 432:     for ( ; (cindx = pindx * 2) <= Nheap; pindx = cindx) {
 433:         /* pick lhs or rhs child */
 434:         child = getlink(rheap[cindx])->l_to;
 435:         if (cindx < Nheap) {
 436:             /* compare with rhs child */
 437:             rchild = getlink(rheap[cindx+1])->l_to;
 438:             /*
 439: 			 * use rhs child if smaller than lhs child.
 440: 			 * if equal, use rhs if net or domain.
 441: 			 */
 442:             if (getnode(child)->n_cost > getnode(rchild)->n_cost) {
 443:                 child = rchild;
 444:                 cindx++;
 445:             } else if (getnode(child)->n_cost == getnode(rchild)->n_cost)
 446:                 if (ISANET(getnode(rchild))) {
 447:                     child = rchild;
 448:                     cindx++;
 449:                 }
 450:         }
 451: 
 452:         /* child is the candidate for swapping */
 453:         if (getnode(parent)->n_cost < getnode(child)->n_cost)
 454:             break;
 455: 
 456:         /*
 457: 		 * heuristics:
 458: 		 *	move nets/domains up
 459: 		 *	move nets above domains
 460: 		 */
 461:         if (getnode(parent)->n_cost == getnode(child)->n_cost) {
 462:             if (!ISANET(getnode(child)))
 463:                 break;
 464:             if (ISANET(getnode(parent)) && ISADOMAIN(getnode(child)))
 465:                 break;
 466:         }
 467: 
 468:         heapswap(pindx, cindx);
 469:     }
 470: }
 471: 
 472: /* exchange Heap[i] and Heap[j] pointers */
 473: STATIC void
 474: heapswap(i, j)
 475:     long i, j;
 476: {   register p_link temp;
 477:     register p_link *rheap;
 478: 
 479:     rheap = Heap;   /* heavily used -- put in register */
 480:     temp = rheap[i];
 481:     rheap[i] = rheap[j];
 482:     rheap[j] = temp;
 483:     getnode(getlink(rheap[j])->l_to)->n_tloc = j;
 484:     getnode(getlink(rheap[i])->l_to)->n_tloc = i;
 485: }
 486: 
 487: /* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
 488: STATIC int
 489: dehash(n)
 490:     register p_node n;
 491: {
 492:     if (getnode(n)->n_tloc < Hashpart)
 493:         return 1;
 494: 
 495:     /* swap with entry in Table[Hashpart] */
 496:     getnode(Table[Hashpart])->n_tloc = getnode(n)->n_tloc;
 497:     Table[getnode(n)->n_tloc] = Table[Hashpart];
 498:     Table[Hashpart] = n;
 499: 
 500:     getnode(n)->n_tloc = Hashpart++;
 501:     return 0;
 502: }
 503: 
 504: STATIC void
 505: backlinks()
 506: {   register p_link l;
 507:     register p_node n;
 508:     register p_node parent;
 509:     p_node nomap;
 510:     p_node ncp;
 511:     long i;
 512: 
 513:     for (i = Hashpart; i < Tabsize; i++) {
 514:         nomap = Table[i];
 515:         for (ncp = getnode(nomap)->n_copy; ncp != nomap;
 516:              ncp = getnode(ncp)->n_copy) {
 517:             if (getnode(ncp)->n_flag & MAPPED) {
 518:                 (void) dehash(nomap);
 519:                 Table[getnode(nomap)->n_tloc] = 0;
 520:                 getnode(nomap)->n_tloc = 0;
 521:                 goto nexti;
 522:             }
 523:         }
 524: 
 525:         /* TODO: simplify this */
 526:         parent = 0;
 527:         for (l = getnode(nomap)->n_link; l; l = getlink(l)->l_next) {
 528:             n = getlink(l)->l_to;
 529:             if (!(getnode(n)->n_flag & MAPPED))
 530:                 continue;
 531:             if (parent == 0) {
 532:                 parent = n;
 533:                 continue;
 534:             }
 535:             if (getnode(n)->n_cost > getnode(parent)->n_cost)
 536:                 continue;
 537:             if (getnode(n)->n_cost == getnode(parent)->n_cost) {
 538:                 getnode(nomap)->n_parent = parent;
 539:                 if (tiebreaker(nomap, n))
 540:                     continue;
 541:             }
 542:             parent = n;
 543:         }
 544:         if (parent == 0)
 545:             continue;
 546:         (void) dehash(nomap);
 547:         l = addlink(parent, nomap, INF, DEFNET, DEFDIR);
 548:         getnode(nomap)->n_parent = parent;
 549:         getnode(nomap)->n_cost = costof(parent, l);
 550:         insert(l);
 551:         heapup(l);
 552: nexti:
 553:         ;
 554:     }
 555:     vprintf(stderr, "%ld backlinks\n", Nheap);
 556: }
 557: 
 558: STATIC void
 559: setheapbits(l)
 560:     register p_link l;
 561: {   register p_node n;
 562:     register p_node parent;
 563: 
 564:     n = getlink(l)->l_to;
 565:     parent = getnode(n)->n_parent;
 566:     getnode(n)->n_flag &= ~(NALIAS|HASLEFT|HASRIGHT);   /* reset */
 567: 
 568:     /* record whether link is an alias */
 569:     if (getlink(l)->l_flag & LALIAS) {
 570:         getnode(n)->n_flag |= NALIAS;
 571:         if (getnode(parent)->n_flag & NTERMINAL)
 572:             getnode(n)->n_flag |= NTERMINAL;
 573:     }
 574: 
 575:     /* set left/right bits */
 576:     if (NETDIR(getlink(l)) == LLEFT || (getnode(parent)->n_flag & HASLEFT))
 577:         getnode(n)->n_flag |= HASLEFT;
 578:     if (NETDIR(getlink(l)) == LRIGHT || (getnode(parent)->n_flag & HASRIGHT))
 579:         getnode(n)->n_flag |= HASRIGHT;
 580: }
 581: 
 582: STATIC void
 583: mtracereport(from, l, excuse)
 584:     p_node from;
 585:     p_link l;
 586:     char *excuse;
 587: {   p_node to = getlink(l)->l_to;
 588: 
 589:     fprintf(stderr, "%-16s ", excuse);
 590:     fputs(getnode(from)->n_name, stderr);
 591:     if (getnode(from)->n_flag & NTERMINAL)
 592:         putc('\'', stderr);
 593:     fputs(" -> ", stderr);
 594:     fputs(getnode(to)->n_name, stderr);
 595:     if (getnode(to)->n_flag & NTERMINAL)
 596:         putc('\'', stderr);
 597:     fprintf(stderr, " (%ld, %ld, %ld) ", getnode(from)->n_cost,
 598:         getlink(l)->l_cost, getnode(to)->n_cost);
 599:     if (getnode(to)->n_parent) {
 600:         fputs(getnode(getnode(to)->n_parent)->n_name, stderr);
 601:         if (getnode(getnode(to)->n_parent)->n_flag & NTERMINAL)
 602:             putc('\'', stderr);
 603:         fprintf(stderr, " (%ld)", getnode(getnode(to)->n_parent)->n_cost);
 604:     }
 605:     putc('\n', stderr);
 606: }
 607: 
 608: #if 0
 609: chkheap(i)
 610: {   int lhs, rhs;
 611: 
 612:     lhs = i * 2;
 613:     rhs = lhs + 1;
 614: 
 615:     if (lhs <= Nheap) {
 616:         if (getnode(getlink(Heap[i])->l_to)->n_cost
 617:             > getnode(getlink(Heap[lhs])->l_to)->n_cost)
 618:             die("chkheap failure on lhs");
 619:         chkheap(lhs);
 620:     }
 621:     if (rhs <= Nheap) {
 622:         if (getnode(getlink(Heap[i])->l_to)->n_cost
 623:              > getnode(getlink(Heap[rhs])->l_to)->n_cost)
 624:             die("chkheap failure on rhs");
 625:         chkheap(rhs);
 626:     }
 627: #if 00
 628:     for (i = 1; i < Nheap; i++) {
 629:         p_link l;
 630: 
 631:         vprintf(stderr, "%5d %-16s", i, getnode(getlink(Heap[i])->l_to)->n_name);
 632:         if ((l = getnode(getlink(Heap[i])->l_to)->n_link) != 0) do {
 633:             vprintf(stderr, "%-16s", getnode(getlink(l)->l_to)->n_name);
 634:         } while ((l = getlink(l)->l_next) != 0);
 635:         vprintf(stderr, "\n");
 636:     }
 637:     for (i = Hashpart; i < Tabsize; i++) {
 638:         p_link l;
 639:         p_node n;
 640: 
 641:         vprintf(stderr, "%5d %-16s", i, getnode(Table[i])->n_name);
 642:         if ((l = getnode(Table[i])->n_link) != 0) do {
 643:             vprintf(stderr, "%-16s", getnode(getlink(l)->l_to)->n_name);
 644:         } while ((l = getlink(l)->l_next) != 0);
 645:         vprintf(stderr, "\n");
 646:     }
 647: #endif /*00*/
 648: 
 649: }
 650: #endif /*0*/

Defined functions

backlinks defined in line 504; used 2 times
chkheap defined in line 609; never used
costof defined in line 279; used 3 times
dehash defined in line 488; used 5 times
heapchildren defined in line 127; used 2 times
heapdown defined in line 421; used 3 times
heapswap defined in line 473; used 3 times
heapup defined in line 356; used 4 times
insert defined in line 323; used 4 times
mapit defined in line 51; used 3 times
min_node defined in line 389; used 2 times
mtracereport defined in line 582; used 7 times
setheapbits defined in line 558; used 2 times
skiplink defined in line 223; used 2 times
skipterminalalias defined in line 202; used 2 times

Defined variables

Hashpart declared in line 18; defined in line 12; used 22 times
Heaphighwater defined in line 41; used 4 times
Nheap declared in line 18; defined in line 13; used 20 times
STATIC defined in line 558; used 16 times
sccsid defined in line 3; never used

Defined macros

chkheap defined in line 8; used 4 times
getlink defined in line 24; used 53 times
getnode defined in line 23; used 116 times
Last modified: 1988-03-13
Generated: 2016-12-26
Generated by src2html V0.67
page hit count: 4037
Valid CSS Valid XHTML 1.0 Strict