home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume3 / pathalias2 / part2 / mapit.c < prev    next >
Encoding:
C/C++ Source or Header  |  1986-11-30  |  10.2 KB  |  441 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)mapit.c    8.1 (down!honey) 86/01/19";
  4. #endif
  5.  
  6. #include "def.h"
  7.  
  8. /* privates */
  9. extern void    reheap(), insert(), heapswap();
  10. extern link    *min_node(), *rmlink();
  11. extern Cost    costof();
  12.  
  13. static long    Nheap;
  14. static long    Heaphighwater;
  15. static link    **Heap;
  16.  
  17.  
  18. /* transform the graph to a shortest-path tree by marking tree edges */
  19.  
  20. mapit()
  21. {
  22.     register node *n, *next;
  23.     register link *l;
  24.     link    *lprev, *lnext;
  25.     Cost cost;
  26.  
  27.     /*
  28.      * re-use the hash table space for the heap.
  29.      */
  30.     Heap = (link **) Table;
  31.  
  32.     pack();        /* remove holes in the Table */
  33.     if (Linkout && *Linkout)    /* dump cheapest links */
  34.         showlinks();
  35.     if (Graphout && *Graphout)    /* dump the edge list */
  36.         dumpgraph();
  37.  
  38.     /* invent and insert a link for Home to get things started */
  39.     l = newlink();
  40.     l->l_to = Home;
  41.     (void) dehash(Home);
  42.     insert(l);
  43.  
  44.     /* main mapping loop */
  45. remap:
  46.     Heaphighwater = Nheap;
  47.     while ((l = min_node()) != 0) {
  48.         l->l_flag |= LTREE;
  49.         n = l->l_to;
  50.         n->n_flag |= MAPPED;
  51.  
  52.         /* add children to heap */
  53.         lprev = 0;
  54.         for (l = n->n_link; l != 0; l = lnext) {
  55.  
  56.             next = l->l_to;        /* neighboring node */
  57.             if (next->n_flag & MAPPED) {
  58.                 lnext = rmlink(l, lprev, n);
  59.                 continue;
  60.             }
  61.             cost = costof(n, l);
  62.  
  63.             if (skiplink(l, n, cost)) {
  64.                 lnext = rmlink(l, lprev, n);
  65.                 continue;
  66.             }
  67.  
  68.             /*
  69.              * put this link in the heap, in a place where it may
  70.              * percolate up, but not down.  if new, or if cost is
  71.              * being increased, move to end.  otherwise, cost is
  72.              * same or less, so leave it where it is.  unfortunately,
  73.              * freeing a link already in the heap is too costly at
  74.              * this point.
  75.              *
  76.              * TODO: avoid heaping aliases and network members.
  77.              */
  78.             if (dehash(next) == 0)    /* first time in heap */
  79.                 insert(l);    /* insert at end */
  80.             else {
  81.                 /* replace heaped link by this one */
  82.                 if (cost > next->n_cost) {    /* gateway */
  83.                     /* move old link to end of heap */
  84.                     heapswap((long) (next->n_tloc), Nheap);
  85.                     next->n_tloc = Nheap;
  86.                 }
  87.                 Heap[next->n_tloc] = l;
  88.             }
  89.                 
  90.             next->n_cost = cost;
  91.             next->n_parent = n;
  92.             reheap(l);        /* restore heap property */
  93.  
  94.             /*
  95.              * note whether we got here via a gatewayed net.
  96.              * domains are presumed to require gateways.
  97.              * aliases inherit parent's gateway status.
  98.              */
  99.             next->n_flag &= ~GATEWAYIN;
  100.             if (l->l_flag & LALIAS)
  101.                 next->n_flag |= (n->n_flag & GATEWAYIN);
  102.             else if (GATEWAYED(n))
  103.                 next->n_flag |= GATEWAYIN;
  104.             lprev = l;    /* this link's a keeper */
  105.             lnext = l->l_next;
  106.         }
  107.  
  108.     }
  109.     vprintf(stderr, "heap high water mark was %d\n", Heaphighwater);
  110.  
  111.     /* sanity check on implementation */
  112.     if (Nheap != 0) {
  113.         fprintf(stderr, "%s: null entry found in heap\n", ProgName);
  114.         badmagic(1);
  115.     }
  116.  
  117.     if (Hashpart < Tabsize) {
  118.         /*
  119.          * add back links from unreachable hosts to reachable
  120.          * neighbors, then remap.  asymptotically, this is
  121.          * quadratic.  in practice, this is done exactly once.
  122.          */
  123.         backlinks();
  124.         if (Nheap)
  125.             goto remap;
  126.     }
  127.     if (Hashpart < Tabsize) {
  128.         fputs("You can't get there from here:\n", stderr);
  129.         for ( ; Hashpart < Tabsize; Hashpart++) {
  130.             fprintf(stderr, "\t%s", Table[Hashpart]->n_name);
  131.             if (Table[Hashpart]->n_flag & (ISPRIVATE|COLLISION))
  132.                 fputs(" (private)", stderr);
  133.             putc('\n', stderr);
  134.         }
  135.     }
  136. }
  137.  
  138. /*
  139.  * can this link be ignored?  if yes, return 1, o.w. 0.
  140.  * a link can be skipped if it is not in the shortest path tree.
  141.  */
  142. STATIC int
  143. skiplink(l, parent, cost)
  144. link    *l;            /* new link to this node */
  145. node    *parent;        /* new parent of this node */
  146. Cost    cost;            /* new cost to this node */
  147. {
  148.     node    *n;        /* this node */
  149.     link    *lheap;        /* existing link to this node */
  150.  
  151.     n = l->l_to;
  152.  
  153.     /* first time we've reached this node? */
  154.     if (n->n_tloc >= Hashpart)
  155.         return(0);
  156.  
  157.     lheap = Heap[n->n_tloc];
  158.  
  159.     /* examine links to nets that require gateways */
  160.     if (GATEWAYED(n)) {
  161.         /* if exactly one is a gateway, use it */
  162.         if ((lheap->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY))
  163.             return(1);    /* old is gateway */
  164.         if (!(lheap->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY))
  165.             return(0);    /* new is gateway */
  166.  
  167.         /* no gateway or both gateways;  resolve in standard way ... */
  168.     }
  169.  
  170.     /* examine dup link (sanity check) */
  171.     if (n->n_parent == parent && ((lheap->l_flag & LDEAD) || (l->l_flag & LDEAD))) {
  172.         fprintf(stderr, "%s: dup dead link not eliminated: %s -> %s\n",
  173.             ProgName, parent->n_name, n->n_name);
  174.         badmagic(1);
  175.     }
  176.  
  177.  
  178.     /*  examine cost */
  179.     if (cost < n->n_cost)
  180.         return(0);
  181.     if (cost > n->n_cost)
  182.         return(1);
  183.  
  184.     /* all other things being equal, consult the oracle */
  185.     return(tiebreaker(n, parent));
  186. }
  187.  
  188. STATIC Cost
  189. costof(prev, l)
  190. register node    *prev;
  191. register link    *l;
  192. {
  193.     register node    *next;
  194.     register Cost    cost;
  195.  
  196.     next = l->l_to;
  197.  
  198.     if (l->l_flag & LALIAS) {
  199.         /* copy left/right bits */
  200.         next->n_flag &= ~(HASLEFT|HASRIGHT);
  201.         next->n_flag |= (prev->n_flag & (HASLEFT|HASRIGHT));
  202.         return(prev->n_cost);    /* by definition */
  203.     }
  204.  
  205.         
  206.     cost = prev->n_cost + l->l_cost;    /* basic cost */
  207.  
  208.     /*
  209.      * heuristics:
  210.      *    charge for a dead link.
  211.      *    charge for getting out of a dead host.
  212.      *    charge for getting into a gatewayed net (except at a gateway).
  213.      *    discourage mixing of left and right syntax when next is a host.
  214.      *    charge for leaving a gatewayed net.
  215.      *
  216.      * life was simpler when pathalias computed true shortest paths.
  217.      */
  218.     if (l->l_flag & LDEAD)        /* dead link */
  219.         cost += INF/2;
  220.     if (DEADHOST(prev))        /* dead host */
  221.         cost += INF/2;
  222.     if (GATEWAYED(next) && !(l->l_flag & LGATEWAY))    /* not gateway */
  223.         cost += INF/2;
  224.     if (!ISANET(next)) {
  225.         /* charge for mixed syntax here */
  226.         if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
  227.          || (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
  228.             cost += DEFCOST;
  229.     }
  230.     /*
  231.      * if reached by a gatewayed net, discourage further links.
  232.      * this has some relevance to common carriers and the FCC ...
  233.      * the penalty inheres to hosts, not aliases, nets, or domains.
  234.      */
  235.     if ((prev->n_flag & GATEWAYIN) && !ISADOMAIN(prev) && !(prev->n_flag & NNET))
  236.         cost += INF/2;    /* heavyweight, but appropriate */
  237.  
  238.     /* set left/right bits */
  239.     next->n_flag &= ~(HASLEFT|HASRIGHT);
  240.     if (NETDIR(l) == LLEFT || (prev->n_flag & HASLEFT))
  241.         next->n_flag |= HASLEFT;
  242.     if (NETDIR(l) == LRIGHT || (prev->n_flag & HASRIGHT))
  243.         next->n_flag |= HASRIGHT;
  244.  
  245.     return(cost);
  246. }
  247.  
  248. STATIC link *
  249. rmlink(l, lprev, n)
  250. link    *l, *lprev;
  251. node    *n;
  252. {
  253.     link    *lnext;
  254.  
  255.     lnext = l->l_next;
  256.     if (lprev)
  257.         lprev->l_next = l->l_next;
  258.     else
  259.         n->n_link = l->l_next;
  260.     free((char *) l);
  261.     return(lnext);
  262. }
  263.  
  264. /*
  265.  * binary heap implementation of priority queue.
  266.  * TODO: make the heap smaller by giving inserting a placeholder
  267.  * for net members when the net is extracted.  this requires storing the
  268.  * cost of a net in the net node itself -- yuck.  is it worth it?
  269.  */
  270.  
  271. STATIC void
  272. insert(l)
  273. link    *l;
  274. {
  275.     register node    *n;
  276.  
  277.     n = l->l_to;
  278.     Heap[n->n_tloc] = 0;
  279.     if (Heap[Nheap+1] != 0) {
  280.         fprintf(stderr, "%s: heap error in insert\n", ProgName);
  281.         badmagic(1);
  282.     }
  283.     if (Nheap++ == 0) {
  284.         Heap[1] = l;
  285.         n->n_tloc = 1;
  286.         return;
  287.     }
  288.     if (Vflag && Nheap > Heaphighwater)
  289.         Heaphighwater = Nheap;    /* diagnostics */
  290.  
  291.     /* insert at the end.  caller must reheap(). */
  292.     Heap[Nheap] = l;
  293.     n->n_tloc = Nheap;
  294. }
  295.  
  296. /*
  297.  * replace existing link in heap by this one, then
  298.  * "percolate" up the heap by exchanging with the parent
  299.  */
  300. STATIC void
  301. reheap(l)
  302. link    *l;
  303. {
  304.     register long    loc, parent;
  305.     register Cost    cost;
  306.     register node    *n, *np;
  307.  
  308.     n = l->l_to;
  309.  
  310.     cost = n->n_cost;
  311.     for (loc = n->n_tloc; loc > 1; loc = parent) {
  312.         parent = loc / 2;
  313.         /* sanity check on implementation */
  314.         if (Heap[parent] == 0) {
  315.             fprintf(stderr, "%s: heap error in insert\n", ProgName);
  316.             badmagic(1);
  317.         }
  318.         np = Heap[parent]->l_to;
  319.         if (cost > np->n_cost)
  320.             return;
  321.         /* move nets below hosts for output stability */
  322.         if (cost == np->n_cost && ((n->n_flag & NNET) || !(np->n_flag & NNET)))
  323.             return;
  324.         heapswap(loc, parent);
  325.     }
  326. }
  327.  
  328. /* extract min (== Heap[1]) from heap */
  329. STATIC link    *
  330. min_node()
  331. {
  332.     link *rval;
  333.     register link **regheap;
  334.     register long    i, child;
  335.     
  336.     if (Nheap == 0)
  337.         return(0);
  338.  
  339.     regheap = Heap;        /* in register -- heavily used */
  340.     rval = regheap[1];    /* return this one */
  341.             
  342.     /* move last entry into root, percolate down */
  343.     regheap[1] = regheap[Nheap];
  344.     regheap[1]->l_to->n_tloc = 1;
  345.     regheap[Nheap] = 0;
  346.     if (--Nheap == 0)
  347.         return(rval);
  348.  
  349.     i = 1;
  350.     for (;;) {
  351.         /* swap with smaller child down the tree */
  352.         child = i * 2;    /* lhs child is 2i, rhs is 2i+1. */
  353.         if (child >= Nheap)
  354.             return(rval);
  355.         /* use rhs child if smaller than lhs child */
  356.         if (regheap[child]->l_to->n_cost > regheap[child+1]->l_to->n_cost
  357.          || (regheap[child]->l_to->n_cost == regheap[child+1]->l_to->n_cost
  358.           && !ISANET(regheap[child+1]->l_to)))
  359.             child++;
  360.             
  361.         if (regheap[i]->l_to->n_cost < regheap[child]->l_to->n_cost)
  362.             return(rval);
  363.         /* move nets below hosts for output stability */
  364.         if (regheap[i]->l_to->n_cost == regheap[child]->l_to->n_cost
  365.          && (!ISANET(regheap[i]->l_to) || ISANET(regheap[child]->l_to)))
  366.             return(rval);
  367.         heapswap(i, child);
  368.         i = child;
  369.     }
  370.     /*NOTREACHED*/
  371. }
  372.  
  373. /* exchange Heap[i] and Heap[j] pointers */
  374. STATIC void
  375. heapswap(i, j)
  376. long    i, j;
  377. {
  378.     register link    *temp, **regheap;
  379.  
  380.     regheap = Heap;    /* heavily used -- put in register */
  381.     temp = regheap[i];
  382.     regheap[i] = regheap[j];
  383.     regheap[j] = temp;
  384.     regheap[j]->l_to->n_tloc = j;
  385.     regheap[i]->l_to->n_tloc = i;
  386. }
  387.  
  388. /* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
  389. dehash(n)
  390. register node    *n;
  391. {
  392.     if (n->n_tloc < Hashpart)
  393.         return(1);
  394.  
  395.     /* swap with entry in Table[Hashpart] */
  396.     Table[Hashpart]->n_tloc = n->n_tloc;
  397.     Table[n->n_tloc] = Table[Hashpart];
  398.     Table[Hashpart] = n;
  399.  
  400.     n->n_tloc = Hashpart++;
  401.     return(0);
  402. }
  403.  
  404. backlinks()
  405. {
  406.     link *l;
  407.     node *n, *parent, *nomap;
  408.     long i;
  409.  
  410.     for (i = Hashpart; i < Tabsize; i++) {
  411.         nomap = Table[i];
  412.         parent = 0;
  413.         for (l = nomap->n_link; l; l = l->l_next) {
  414.             n = l->l_to;
  415.             if (!(n->n_flag & MAPPED))
  416.                 continue;
  417.             if (parent == 0) {
  418.                 parent = n;
  419.                 continue;
  420.             }
  421.             if (n->n_cost > parent->n_cost)
  422.                 continue;
  423.             if (n->n_cost == parent->n_cost) {
  424.                 nomap->n_parent = parent;
  425.                 if (tiebreaker(nomap, n))
  426.                     continue;
  427.             }
  428.             parent = n;
  429.         }
  430.         if (parent == 0)
  431.             continue;
  432.         (void) dehash(nomap);
  433.         l = addlink(parent, nomap, INF, DEFNET, DEFDIR);
  434.         nomap->n_parent = parent;
  435.         nomap->n_cost = costof(parent, l);
  436.         insert(l);
  437.         reheap(l);
  438.     }
  439.     vprintf(stderr, "%d backlinks\n", Nheap);
  440. }
  441.