home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume3 / pathalias2 / part2 / mapaux.c < prev    next >
Encoding:
C/C++ Source or Header  |  1986-11-30  |  5.0 KB  |  258 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)mapaux.c    8.1 (down!honey) 86/01/19";
  4. #endif lint
  5.  
  6. #include "def.h"
  7.  
  8. void    pack();
  9.  
  10. void
  11. pack()
  12. {
  13.     long    hole, next;
  14.  
  15.     /* find first "hole " */
  16.     for (hole = Tabsize - 1; hole >= 0 && Table[hole] != 0; --hole)
  17.         ;
  18.  
  19.     /* repeatedly move next filled entry into last hole */
  20.     for (next = hole - 1; next >= 0; --next) {
  21.         if (Table[next] != 0) {
  22.             Table[hole] = Table[next];
  23.             Table[hole]->n_tloc = hole;
  24.             Table[next] = 0;
  25.             while (Table[--hole] != 0)    /* find next hole */
  26.                 ;
  27.         }
  28.     }
  29.     Hashpart = hole + 1;
  30. }
  31.  
  32. FILE    *Gstream;
  33.  
  34. dumpgraph()
  35. {
  36.     long    i;
  37.     node    *n;
  38.  
  39.     if ((Gstream = fopen(Graphout, "w")) == NULL) {
  40.         fprintf(stderr, "%s: ", ProgName);
  41.         perror(Graphout);
  42.     }
  43.  
  44.     untangle();    /* untangle net cycles for proper output */
  45.  
  46.     for (i = Hashpart; i < Tabsize; i++) {
  47.         n = Table[i];
  48.         if (n == 0)
  49.             continue;    /* impossible, but ... */
  50.         /* a minor optimization ... */
  51.         if (n->n_link == 0)
  52.             continue;
  53.         /* pathparse doesn't need these */
  54.         if (n->n_flag & NNET)
  55.             continue;
  56.         dumpnode(n);
  57.     }
  58. }
  59.  
  60. dumpnode(from)
  61. node    *from;
  62. {
  63.     node    *to;
  64.     link    *l;
  65.     char    netbuf[BUFSIZ], *nptr = netbuf;
  66.  
  67.     for (l = from->n_link ; l; l = l->l_next) {
  68.         to = l->l_to;
  69.         if (from == to)
  70.             continue;    /* oops -- it's me! */
  71.  
  72.         if ((to->n_flag & NNET) == 0) {
  73.             /* host -> host -- print host>host */
  74.             if (l->l_cost == INF)
  75.                 continue;    /* phoney link */
  76.             fputs(from->n_name, Gstream);
  77.             putc('>', Gstream);
  78.             fputs(to->n_name, Gstream);
  79.             putc('\n', Gstream);
  80.         } else {
  81.             /* host -> net -- just cache it for now */
  82.             while (to->n_root && to != to->n_root)
  83.                 to = to->n_root;
  84.             *nptr++ = ',';
  85.             strcpy(nptr, to->n_name);
  86.             nptr += strlen(nptr);
  87.         }
  88.     }
  89.  
  90.     /* dump nets */
  91.     if (nptr != netbuf) {
  92.         /* nets -- print host@\tnet,net, ... */
  93.         *nptr = 0;
  94.         fputs(from->n_name, Gstream);
  95.         putc('@', Gstream);
  96.         *netbuf = '\t';    /* insert tab by killing initial ',' */
  97.         fputs(netbuf, Gstream);    /* skip initial ',' */
  98.         putc('\n', Gstream);
  99.     }
  100. }
  101.  
  102. /*
  103.  * remove cycles in net definitions. 
  104.  *
  105.  * depth-first search
  106.  *
  107.  * for each net, run dfs on its neighbors (nets only).  if we return to
  108.  * a visited node, that's a net cycle.  mark the cycle with a pointer
  109.  * in the n_root field (which gets us closer to the root of this
  110.  * portion of the dfs tree).
  111.  */
  112. untangle()
  113. {
  114.     long    i;
  115.     node    *n;
  116.  
  117.     for (i = Hashpart; i < Tabsize; i++) {
  118.         n = Table[i];
  119.         if (n == 0 || (n->n_flag & NNET) == 0 || n->n_root)
  120.             continue;
  121.         dfs(n);
  122.     }
  123. }
  124.  
  125. dfs(n)
  126. node    *n;
  127. {
  128.     link    *l;
  129.     node    *next;
  130.  
  131.     n->n_flag |= INDFS;
  132.     n->n_root = n;
  133.     for (l = n->n_link; l; l = l->l_next) {
  134.         next = l->l_to;
  135.         if ((next->n_flag & NNET) == 0)
  136.             continue;
  137.         if ((next->n_flag & INDFS) == 0) {
  138.             dfs(next);
  139.             if (next->n_root != next)
  140.                 n->n_root = next->n_root;
  141.         } else
  142.             n->n_root = next->n_root;
  143.     }
  144.     n->n_flag &= ~INDFS;
  145. }
  146.  
  147. showlinks() 
  148. {
  149.     link    *l;
  150.     node    *n;
  151.     long    i;
  152.     FILE    *estream;
  153.  
  154.     if ((estream = fopen(Linkout, "w")) == 0)
  155.         return;
  156.  
  157.     for (i = Hashpart; i < Tabsize; i++) {
  158.         n = Table[i];
  159.         if (n == 0)    /* impossible, but ... */
  160.             continue;
  161.         if (l = n->n_link) {
  162.             fprintf(estream, "%s\t%s(%d)", n->n_name,
  163.                 l->l_to->n_name,
  164.                 l->l_cost ? l->l_cost : DEFCOST);
  165.             for (l = l->l_next; l; l = l->l_next)
  166.                 fprintf(estream, ",\n\t%s(%d)", l->l_to->n_name,
  167.                     l->l_cost ? l->l_cost : DEFCOST);
  168.             fputc('\n', estream);
  169.         }
  170.     }
  171.     (void) fclose(estream);
  172. }
  173.  
  174. /*
  175.  * n is node in heap, newp is candidate for new parent.
  176.  * choose between newp and n->n_parent for parent.
  177.  * return 0 to use newp, non-zero o.w.
  178.  */
  179. #define NEWP 0
  180. #define OLDP 1
  181. tiebreaker(n, newp)
  182. node    *n, *newp;
  183. {
  184.     register char    *opname, *npname, *name;
  185.     node    *oldp;
  186.     int    metric;
  187.  
  188.     oldp = n->n_parent;
  189.  
  190.     /*
  191.      * given the choice of going through a gatewayed not or not,
  192.      * choose the latter, placating the FCC or whatever.
  193.      */
  194.     if (GATEWAYED(newp) && !GATEWAYED(oldp))
  195.         return(oldp);
  196.     if (!GATEWAYED(newp) && GATEWAYED(oldp))
  197.         return(newp);
  198.  
  199.     /* look at real parents, not nets */
  200.     while (oldp->n_flag & NNET)
  201.         oldp = oldp->n_parent;
  202.     while (newp->n_flag & NNET)
  203.         newp = newp->n_parent;
  204.  
  205.     /* use fewer hops, if possible */
  206.     metric = height(oldp) - height(newp);
  207.     if (metric < 0)
  208.         return(OLDP);
  209.     if (metric > 0)
  210.         return(NEWP);
  211.  
  212.     /* compare names */
  213.     opname = oldp->n_name;
  214.     npname = newp->n_name;
  215.     name = n->n_name;
  216.  
  217.     /* find point of departure */
  218.     while (*opname == *npname && *npname == *name) {
  219.         if (*name == 0) {
  220.             fprintf(stderr, "%s: error in tie breaker\n", ProgName);
  221.             badmagic(1);
  222.         }
  223.         opname++;
  224.         npname++;
  225.         name++;
  226.     }
  227.  
  228.     /* use longest match, if appl. */
  229.     if (*opname == *name || *opname == 0)
  230.         return(OLDP);
  231.     if (*npname == *name || *npname == 0)
  232.         return(NEWP);
  233.  
  234.     /* use shorter host name, if appl. */
  235.     metric = strlen(opname) - strlen(npname);
  236.     if (metric < 0)
  237.         return(OLDP);
  238.     if (metric > 0)
  239.         return(NEWP);
  240.  
  241.     /* use larger lexicographically (no reason) */
  242.     metric = strcmp(opname, npname);
  243.     if (metric < 0)
  244.         return(NEWP);
  245.     return(OLDP);
  246. }
  247.  
  248. height(n)
  249. register node    *n;
  250. {
  251.     register int i = 0;
  252.  
  253.     while ((n = n->n_parent) != 0)
  254.         if ((n->n_flag & NNET) == 0)
  255.             i++;    /* should count domains too ... */
  256.     return(i);
  257. }
  258.