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