home *** CD-ROM | disk | FTP | other *** search
/ back2roots/padua / padua.7z / padua / uucp / auucp+-1.02 / fuucp_plus_src.lzh / pathalias / mapit.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-06-10  |  15.3 KB  |  680 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)mapit.c    9.13 88/06/12";
  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.  * bizarro special case.  this merits comment.
  187.  * 
  188.  * n is a terminal node just sucked out of the heap, next is an alias
  189.  * for n.  because n is terminal, it must have one or more "copies."
  190.  * if next is one of those copies, don't put next in the heap.
  191.  *
  192.  * does that clear things up?
  193.  */
  194. STATIC int
  195. skipterminalalias(n, next)
  196.     node *n, *next;
  197. {
  198.  
  199.     while (n->n_flag & NALIAS) {
  200.         n = n->n_parent;
  201.         if (ALTEREGO(n, next))
  202.             return 1;
  203.     }
  204.     return 0;
  205. }
  206.  
  207. /*
  208.  * return 1 if we definitely don't want want this link in the
  209.  * shortest path tree, 0 if we might want it, i.e., best so far.
  210.  *
  211.  * if tracing is turned on, report only if this node is being skipped.
  212.  */
  213. STATIC int
  214. skiplink(l, parent, cost, trace)
  215.     link *l;        /* new link to this node */
  216.     node *parent;        /* (potential) new parent of this node */
  217.     register Cost cost;    /* new cost to this node */
  218.     int trace;        /* trace this link? */
  219. {    register node *n;    /* this node */
  220.     register link *lheap;        /* old link to this node */
  221.  
  222.     n = l->l_to;
  223.  
  224.     /* first time we've reached this node? */
  225.     if (n->n_tloc >= Hashpart)
  226.         return 0;
  227.  
  228.     lheap = Heap[n->n_tloc];
  229.  
  230.     /* examine links to nets that require gateways */
  231.     if (GATEWAYED(n)) {
  232.         /* if exactly one is a gateway, use it */
  233.         if ((lheap->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY)) {
  234.             if (trace)
  235.                 mtracereport(parent, l, "-\told gateway");
  236.             return 1;    /* old is gateway */
  237.         }
  238.         if (!(lheap->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY))
  239.             return 0;    /* new is gateway */
  240.  
  241.         /* no gateway or both gateways;  resolve in standard way ... */
  242.     }
  243.  
  244.     /* examine dup link (sanity check) */
  245.     if (n->n_parent == parent && (DEADLINK(lheap) || DEADLINK(l)))
  246.         die("dup dead link");
  247.  
  248.     /*  examine cost */
  249.     if (cost < n->n_cost)
  250.         return 0;
  251.     if (cost > n->n_cost) {
  252.         if (trace)
  253.             mtracereport(parent, l, "-\tcheaper");
  254.         return 1;
  255.     }
  256.  
  257.     /* all other things being equal, ask the oracle */
  258.     if (tiebreaker(n, parent)) {
  259.         if (trace)
  260.             mtracereport(parent, l, "-\ttiebreaker");
  261.         return 1;
  262.     }
  263.     return 0;
  264. }
  265.  
  266. /* compute cost to l->l_to via parent */
  267. STATIC Cost
  268. costof(prev, l)
  269.     register node *prev;
  270.     register link *l;
  271. {    register node *next;
  272.     register Cost cost;
  273.  
  274.     if (l->l_flag & LALIAS)
  275.         return prev->n_cost;    /* by definition */
  276.  
  277.     next = l->l_to;
  278.     cost = prev->n_cost + l->l_cost;    /* basic cost */
  279.  
  280.     /*
  281.      * heuristics:
  282.      *    charge for a dead link.
  283.      *    charge for getting past a terminal host
  284.      *        or getting out of a dead host.
  285.      *    charge for getting into a gatewayed net (except at a gateway).
  286.      *    discourage mixing of syntax (when prev is a host).
  287.      *
  288.      * life was simpler when pathalias computed true shortest paths.
  289.      */
  290.     if (DEADLINK(l))
  291.         cost += INF;                /* dead link */
  292.     if (DEADHOST(prev))
  293.         cost += INF;                /* dead parent */
  294.     if (GATEWAYED(next) && !(l->l_flag & LGATEWAY))
  295.         cost += INF;                /* not gateway */
  296.     if (!ISANET(prev)) {
  297.         if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
  298.          || (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
  299.             cost += INF;            /* mixed syntax */
  300.     }
  301.  
  302.     return cost;
  303. }
  304.  
  305. /* binary heap implementation of priority queue */
  306.  
  307. STATIC void
  308. insert(l)
  309.     link *l;
  310. {    register node *n;
  311.  
  312.     n = l->l_to;
  313.     if (n->n_flag & MAPPED)
  314.         die("insert mapped node");
  315.  
  316.     Heap[n->n_tloc] = 0;
  317.     if (Heap[Nheap+1] != 0)
  318.         die("heap error in insert");
  319.     if (Nheap++ == 0) {
  320.         Heap[1] = l;
  321.         n->n_tloc = 1;
  322.         return;
  323.     }
  324.     if (Vflag && Nheap > Heaphighwater)
  325.         Heaphighwater = Nheap;    /* diagnostics */
  326.  
  327.     /* insert at the end.  caller must heapup(l). */
  328.     Heap[Nheap] = l;
  329.     n->n_tloc = Nheap;
  330. }
  331.  
  332. /*
  333.  * "percolate" up the heap by exchanging with the parent.  as in
  334.  * min_node(), give tiebreaker() a chance to produce better, stable
  335.  * routes by moving nets and domains close to the root, nets closer
  336.  * than domains.
  337.  *
  338.  * i know this seems obscure, but it's harmless and cheap.  trust me.
  339.  */
  340. STATIC void
  341. heapup(l)
  342.     link *l;
  343. {    register long cindx, pindx;    /* child, parent indices */
  344.     register Cost cost;
  345.     register node *child, *parent;
  346.  
  347.     child = l->l_to;
  348.  
  349.     cost = child->n_cost;
  350.     for (cindx = child->n_tloc; cindx > 1; cindx = pindx) {
  351.         pindx = cindx / 2;
  352.         if (Heap[pindx] == 0)    /* sanity check */
  353.             die("impossible error in heapup");
  354.         parent = Heap[pindx]->l_to;
  355.         if (cost > parent->n_cost)
  356.             return;
  357.  
  358.         /* net/domain heuristic */
  359.         if (cost == parent->n_cost) {
  360.             if (!ISANET(child))
  361.                 return;
  362.             if (!ISADOMAIN(parent))
  363.                 return;
  364.             if (ISADOMAIN(child))
  365.                 return;
  366.         }
  367.         heapswap(cindx, pindx);
  368.     }
  369. }
  370.  
  371. /* extract min (== Heap[1]) from heap */
  372. STATIC link    *
  373. min_node()
  374. {    link *rval, *lastlink;
  375.     register link **rheap;
  376.  
  377.     if (Nheap == 0)
  378.         return 0;
  379.  
  380.     rheap = Heap;        /* in register -- heavily used */
  381.     rval = rheap[1];    /* return this one */
  382.  
  383.     /* move last entry into root and reheap */
  384.     lastlink = rheap[Nheap];
  385.     rheap[Nheap] = 0;
  386.  
  387.     if (--Nheap) {
  388.         rheap[1] = lastlink;
  389.         lastlink->l_to->n_tloc = 1;
  390.         heapdown(lastlink);    /* restore heap property */
  391.     }
  392.  
  393.     return rval;
  394. }
  395.  
  396. /*
  397.  * swap Heap[i] with smaller child, iteratively down the tree.
  398.  *
  399.  * given the opportunity, attempt to place nets and domains
  400.  * near the root.  this helps tiebreaker() shun domain routes.
  401.  */
  402.  
  403. STATIC void
  404. heapdown(l)
  405.     link *l;
  406. {    register long pindx, cindx;
  407.     register link **rheap = Heap;    /* in register -- heavily used */
  408.     node *child, *rchild, *parent;
  409.  
  410.     pindx = l->l_to->n_tloc;
  411.     parent = rheap[pindx]->l_to;    /* invariant */
  412.     for ( ; (cindx = pindx * 2) <= Nheap; pindx = cindx) {
  413.         /* pick lhs or rhs child */
  414.         child = rheap[cindx]->l_to;
  415.         if (cindx < Nheap) {
  416.             /* compare with rhs child */
  417.             rchild = rheap[cindx+1]->l_to;
  418.             /*
  419.              * use rhs child if smaller than lhs child.
  420.              * if equal, use rhs if net or domain.
  421.              */
  422.             if (child->n_cost > rchild->n_cost) {
  423.                 child = rchild;
  424.                 cindx++;
  425.             } else if (child->n_cost == rchild->n_cost)
  426.                 if (ISANET(rchild)) {
  427.                     child = rchild;
  428.                     cindx++;
  429.                 }
  430.         }
  431.  
  432.         /* child is the candidate for swapping */
  433.         if (parent->n_cost < child->n_cost)
  434.             break;
  435.  
  436.         /*
  437.          * heuristics:
  438.          *    move nets/domains up
  439.          *    move nets above domains
  440.          */
  441.         if (parent->n_cost == child->n_cost) {
  442.             if (!ISANET(child))
  443.                 break;
  444.             if (ISANET(parent) && ISADOMAIN(child))
  445.                 break;
  446.         }
  447.  
  448.         heapswap(pindx, cindx);
  449.     }
  450. }
  451.  
  452. /* exchange Heap[i] and Heap[j] pointers */
  453. STATIC void
  454. heapswap(i, j)
  455.     long i, j;
  456. {    register link *temp, **rheap;
  457.  
  458.     rheap = Heap;    /* heavily used -- put in register */
  459.     temp = rheap[i];
  460.     rheap[i] = rheap[j];
  461.     rheap[j] = temp;
  462.     rheap[j]->l_to->n_tloc = j;
  463.     rheap[i]->l_to->n_tloc = i;
  464. }
  465.  
  466. /* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
  467. STATIC int
  468. dehash(n)
  469.     register node *n;
  470. {
  471.     if (n->n_tloc < Hashpart)
  472.         return 1;
  473.  
  474.     /* swap with entry in Table[Hashpart] */
  475.     Table[Hashpart]->n_tloc = n->n_tloc;
  476.     Table[n->n_tloc] = Table[Hashpart];
  477.     Table[Hashpart] = n;
  478.  
  479.     n->n_tloc = Hashpart++;
  480.     return 0;
  481. }
  482.  
  483. /*
  484.  * everything reachable has been mapped.  what to do about any
  485.  * unreachable hosts?  the sensible thing to do is to dump them on
  486.  * stderr and be done with it.  unfortunately, there are hundreds of
  487.  * such hosts in the usenet maps.  so we take the low road: for each
  488.  * unreachable host, we add a back link from its cheapest mapped child,
  489.  * in the faint that a reverse path works.
  490.  *
  491.  * beats me why people want their error output in their map databases.
  492.  */
  493. STATIC void
  494. backlinks()
  495. {    register link *l;
  496.     register node *n, *child;
  497.     node *nomap;
  498.     long i;
  499.  
  500.     /* hosts from Hashpart to Tabsize are unreachable */
  501.     for (i = Hashpart; i < Tabsize; i++) {
  502.         nomap = Table[i];
  503.         /* if a copy has been mapped, we're ok */
  504.         if (nomap->n_copy != nomap) {
  505.             dehash(nomap);
  506.             Table[nomap->n_tloc] = 0;
  507.             nomap->n_tloc = 0;
  508.             continue;
  509.         }
  510.  
  511.         /* TODO: simplify this */        
  512.         /* add back link from minimal cost child */
  513.         child = 0;
  514.         for (l = nomap->n_link; l; l = l->l_next) {
  515.             n = l->l_to;
  516.             /* never ever ever crawl out of a domain */
  517.             if (ISADOMAIN(n))
  518.                 continue;
  519.             if ((n = mappedcopy(n)) == 0)
  520.                 continue;
  521.             if (child == 0) {
  522.                 child = n;
  523.                 continue;
  524.             }
  525.             if (n->n_cost > child->n_cost)
  526.                 continue;
  527.             if (n->n_cost == child->n_cost) {
  528.                 nomap->n_parent = child; /* for tiebreaker */
  529.                 if (tiebreaker(nomap, n))
  530.                     continue;
  531.             }
  532.             child = n;
  533.         }
  534.         if (child == 0)
  535.             continue;
  536.         (void) dehash(nomap);
  537.         l = addlink(child, nomap, INF, DEFNET, DEFDIR);    /* INF cost */
  538.         nomap->n_parent = child;
  539.         nomap->n_cost = costof(child, l);
  540.         insert(l);
  541.         heapup(l);
  542.         if (Vflag > 1)
  543.             fprintf(stderr, "backlink: %s <- %s\n", nomap->n_name, child->n_name);
  544.     }
  545.     vprintf(stderr, "%d backlinks\n", Nheap);
  546. }
  547.  
  548. /* find a mapped copy of n if it exists */
  549. STATIC node *
  550. mappedcopy(n)
  551.     register node *n;
  552. {    register node *ncp;
  553.  
  554.     if (n->n_flag & MAPPED)
  555.         return n;
  556.     for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy)
  557.         if (ncp->n_flag & MAPPED)
  558.             return ncp;
  559.     return 0;
  560. }
  561.  
  562. /*
  563.  * l has just been added or changed in the heap,
  564.  * so reset the state bits for l->l_to.
  565.  */
  566. STATIC void
  567. setheapbits(l)
  568.     register link *l;
  569. {    register node *n;
  570.     register node *parent;
  571.  
  572.     n = l->l_to;
  573.     parent = n->n_parent;
  574.     n->n_flag &= ~(NALIAS|HASLEFT|HASRIGHT);    /* reset */
  575.  
  576.     /* record whether link is an alias */
  577.     if (l->l_flag & LALIAS) {
  578.         n->n_flag |= NALIAS;
  579.         /* TERMINALity is inherited by the alias */
  580.         if (parent->n_flag & NTERMINAL)
  581.             n->n_flag |= NTERMINAL;
  582.     }
  583.  
  584.     /* set left/right bits */
  585.     if (NETDIR(l) == LLEFT || (parent->n_flag & HASLEFT))
  586.         n->n_flag |= HASLEFT;
  587.     if (NETDIR(l) == LRIGHT || (parent->n_flag & HASRIGHT))
  588.         n->n_flag |= HASRIGHT;
  589. }
  590.  
  591. STATIC void
  592. mtracereport(from, l, excuse)
  593.     node *from;
  594.     link *l;
  595.     char *excuse;
  596. {    node *to = l->l_to;
  597.  
  598.     fprintf(stderr, "%-16s ", excuse);
  599.     trprint(stderr, from);
  600.     fputs(" -> ", stderr);
  601.     trprint(stderr, to);
  602.     fprintf(stderr, " (%ld, %ld, %ld) ", from->n_cost, l->l_cost, to->n_cost);
  603.     if (to->n_parent) {
  604.         trprint(stderr, to->n_parent);
  605.         fprintf(stderr, " (%ld)", to->n_parent->n_cost);
  606.     }
  607.     putc('\n', stderr);
  608. }
  609.  
  610. STATIC void
  611. otracereport(n)
  612.     node *n;
  613. {
  614.     if (n->n_parent)
  615.         trprint(stderr, n->n_parent);
  616.     else
  617.         fputs("[root]", stderr);
  618.     fputs(" -> ", stderr);
  619.     trprint(stderr, n);
  620.     fputs(" mapped\n", stderr);
  621. }
  622.     
  623. #if 0
  624. /* extremely time consuming, exhaustive check of heap sanity. */
  625. chkheap(i)
  626. {    int lhs, rhs;
  627.  
  628.     lhs = i * 2;
  629.     rhs = lhs + 1;
  630.  
  631.     if (lhs <= Nheap) {
  632.         if (Heap[i]->l_to->n_cost > Heap[lhs]->l_to->n_cost)
  633.             die("chkheap failure on lhs");
  634.         chkheap(lhs);
  635.     }
  636.     if (rhs <= Nheap) {
  637.         if (Heap[i]->l_to->n_cost > Heap[rhs]->l_to->n_cost)
  638.             die("chkheap failure on rhs");
  639.         chkheap(rhs);
  640.     }
  641. #if 00
  642.     /* this hasn't been used for years */
  643.     for (i = 1; i < Nheap; i++) {
  644.         link *l;
  645.  
  646.         vprintf(stderr, "%5d %-16s", i, Heap[i]->l_to->n_name);
  647.         if ((l = Heap[i]->l_to->n_link) != 0) do {
  648.             vprintf(stderr, "%-16s", l->l_to->n_name);
  649.         } while ((l = l->l_next) != 0);
  650.         vprintf(stderr, "\n");
  651.     }
  652.     for (i = Hashpart; i < Tabsize; i++) {
  653.         link *l;
  654.         node *n;
  655.  
  656.         vprintf(stderr, "%5d %-16s", i, Table[i]->n_name);
  657.         if ((l = Table[i]->n_link) != 0) do {
  658.             vprintf(stderr, "%-16s", l->l_to->n_name);
  659.         } while ((l = l->l_next) != 0);
  660.         vprintf(stderr, "\n");
  661.     }
  662. #endif /*00*/
  663.         
  664. }
  665. #endif /*0*/
  666.  
  667. /* this isn't much use */
  668. #if 0
  669. STATIC int
  670. chkgap()
  671. {    static int gap = -1;
  672.     int newgap;
  673.  
  674.     newgap = Hashpart - Nheap;
  675.     if (gap == -1 || newgap < gap)
  676.         gap = newgap;
  677.     return gap;
  678. }
  679. #endif /*0*/
  680.