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