home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume12 / pathalias9 / part01 / mapaux.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-08  |  6.9 KB  |  344 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)mapaux.c    9.1 87/10/04";
  4. #endif /* lint */
  5.  
  6. #include "def.h"
  7.  
  8. /* imports */
  9. extern long Nheap, Hashpart, Tabsize;
  10. extern node **Table, *Home;
  11. extern char *Graphout, *Linkout, *Netchars, **Argv;
  12. extern void freelink(), die();
  13. extern long pack();
  14. extern link *newlink();
  15. extern node *newnode();
  16. extern char *strsave();
  17.  
  18. /* exports */
  19. long pack();
  20. void resetnodes(), dumpgraph(), showlinks();
  21. int tiebreaker();
  22. node *ncopy();
  23.  
  24. /* privates */
  25. static FILE *Gstream;    /* for dumping graph */
  26. STATIC void dumpnode(), untangle(), dfs();
  27. STATIC int height();
  28. STATIC link *lcopy();
  29.  
  30.  
  31. /*
  32.  * slide everything from Table[low] to Table[high]
  33.  * up toward the high end.  make room!  make room!
  34.  */
  35. long
  36. pack(low, high)
  37.     long low, high;
  38. {    long hole, next;
  39.  
  40.     /* find first "hole " */
  41.     for (hole = high; hole >= low && Table[hole] != 0; --hole)
  42.         ;
  43.  
  44.     /* repeatedly move next filled entry into last hole */
  45.     for (next = hole - 1; next >= low; --next) {
  46.         if (Table[next] != 0) {
  47.             Table[hole] = Table[next];
  48.             Table[hole]->n_tloc = hole;
  49.             Table[next] = 0;
  50.             while (Table[--hole] != 0)    /* find next hole */
  51.                 ;
  52.         }
  53.     }
  54.     return hole + 1;
  55. }
  56.  
  57. void
  58. resetnodes()
  59. {    register long i;
  60.     register node *n;
  61.  
  62.     for (i = Hashpart; i < Tabsize; i++)
  63.         if ((n = Table[i]) != 0) {
  64.             n->n_cost = (Cost) 0;
  65.             n->n_flag &= ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT|NTERMINAL);
  66.             n->n_copy = n;
  67.         }
  68.         
  69.     Home->n_cost = (Cost) 0;
  70.     Home->n_flag &= ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT|NTERMINAL);
  71.     Home->n_copy = Home;
  72. }
  73.  
  74. void    
  75. dumpgraph()
  76. {    register long i;
  77.     register node *n;
  78.  
  79.     if ((Gstream = fopen(Graphout, "w")) == NULL) {
  80.         fprintf(stderr, "%s: ", Argv[0]);
  81.         perror(Graphout);
  82.         return;
  83.     }
  84.  
  85.     untangle();    /* untangle net cycles for proper output */
  86.  
  87.     for (i = Hashpart; i < Tabsize; i++) {
  88.         n = Table[i];
  89.         if (n == 0)
  90.             continue;    /* impossible, but ... */
  91.         /* a minor optimization ... */
  92.         if (n->n_link == 0)
  93.             continue;
  94.         /* pathparse doesn't need these */
  95.         if (n->n_flag & NNET)
  96.             continue;
  97.         dumpnode(n);
  98.     }
  99. }
  100.  
  101. STATIC void
  102. dumpnode(from)
  103.     register node *from;
  104. {    register node *to;
  105.     register link *l;
  106.     link *lnet = 0, *ll, *lnext;
  107.  
  108.     for (l = from->n_link ; l; l = l->l_next) {
  109.         to = l->l_to;
  110.         if (from == to)
  111.             continue;    /* oops -- it's me! */
  112.  
  113.         if ((to->n_flag & NNET) == 0) {
  114.             /* host -> host -- print host>host */
  115.             if (l->l_cost == INF)
  116.                 continue;    /* phoney link */
  117.             fputs(from->n_name, Gstream);
  118.             putc('>', Gstream);
  119.             fputs(to->n_name, Gstream);
  120.             putc('\n', Gstream);
  121.         } else {
  122.             /*
  123.              * host -> net -- just cache it for now.
  124.              * first check for dups.  (quadratic, but
  125.              * n is small here.)
  126.              */
  127.             while (to->n_root && to != to->n_root)
  128.                 to = to->n_root;
  129.             for (ll = lnet; ll; ll = ll->l_next)
  130.                 if (strcmp(ll->l_to->n_name, to->n_name) == 0)
  131.                     break;
  132.             if (ll)
  133.                 continue;    /* dup */
  134.             ll = newlink();
  135.             ll->l_next = lnet;
  136.             ll->l_to = to;
  137.             lnet = ll;
  138.         }
  139.     }
  140.  
  141.     /* dump nets */
  142.     if (lnet) {
  143.         /* nets -- print host@\tnet,net, ... */
  144.         fputs(from->n_name, Gstream);
  145.         putc('@', Gstream);
  146.         putc('\t', Gstream);
  147.         for (ll = lnet; ll; ll = lnext) {
  148.             lnext = ll->l_next;
  149.             fputs(ll->l_to->n_name, Gstream);
  150.             if (lnext)
  151.                 fputc(',', Gstream);
  152.             freelink(ll);
  153.         }
  154.         putc('\n', Gstream);
  155.     }
  156. }
  157.  
  158. /*
  159.  * remove cycles in net definitions. 
  160.  *
  161.  * depth-first search
  162.  *
  163.  * for each net, run dfs on its neighbors (nets only).  if we return to
  164.  * a visited node, that's a net cycle.  mark the cycle with a pointer
  165.  * in the n_root field (which gets us closer to the root of this
  166.  * portion of the dfs tree).
  167.  */
  168. STATIC void
  169. untangle()
  170. {    register long i;
  171.     register node *n;
  172.  
  173.     for (i = Hashpart; i < Tabsize; i++) {
  174.         n = Table[i];
  175.         if (n == 0 || (n->n_flag & NNET) == 0 || n->n_root)
  176.             continue;
  177.         dfs(n);
  178.     }
  179. }
  180.  
  181. STATIC void
  182. dfs(n)
  183.     register node *n;
  184. {    register link *l;
  185.     register node *next;
  186.  
  187.     n->n_flag |= INDFS;
  188.     n->n_root = n;
  189.     for (l = n->n_link; l; l = l->l_next) {
  190.         next = l->l_to;
  191.         if ((next->n_flag & NNET) == 0)
  192.             continue;
  193.         if ((next->n_flag & INDFS) == 0) {
  194.             dfs(next);
  195.             if (next->n_root != next)
  196.                 n->n_root = next->n_root;
  197.         } else
  198.             n->n_root = next->n_root;
  199.     }
  200.     n->n_flag &= ~INDFS;
  201. }
  202.  
  203. void
  204. showlinks() 
  205. {    register link *l;
  206.     register node *n;
  207.     register long i;
  208.     FILE    *estream;
  209.  
  210.     if ((estream = fopen(Linkout, "w")) == 0)
  211.         return;
  212.  
  213.     for (i = Hashpart; i < Tabsize; i++) {
  214.         n = Table[i];
  215.         if (n == 0 || n->n_link == 0)
  216.             continue;
  217.         for (l = n->n_link; l; l = l->l_next) {
  218.             fputs(n->n_name, estream);
  219.             putc('\t', estream);
  220.             if (NETDIR(l) == LRIGHT)
  221.                 putc(NETCHAR(l), estream);
  222.             fputs(l->l_to->n_name, estream);
  223.             if (NETDIR(l) == LLEFT)
  224.                 putc(NETCHAR(l), estream);
  225.             fprintf(estream, "(%d)\n", l->l_cost);
  226.         }
  227.     }
  228.     (void) fclose(estream);
  229. }
  230.  
  231. /*
  232.  * n is node in heap, newp is candidate for new parent.
  233.  * choose between newp and n->n_parent for parent.
  234.  * return 0 to use newp, non-zero o.w.
  235.  */
  236. #define NEWP 0
  237. #define OLDP 1
  238. int
  239. tiebreaker(n, newp)
  240.     node *n;
  241.     register node *newp;
  242. {    register char *opname, *npname, *name;
  243.     register node *oldp;
  244.     int metric;
  245.  
  246.     oldp = n->n_parent;
  247.  
  248.     /* given the choice, avoid gatewayed nets */
  249.     if (GATEWAYED(newp) && !GATEWAYED(oldp))
  250.         return OLDP;
  251.     if (!GATEWAYED(newp) && GATEWAYED(oldp))
  252.         return NEWP;
  253.  
  254.     /* look at real parents, not nets */
  255.     while ((oldp->n_flag & NNET) && oldp->n_parent)
  256.         oldp = oldp->n_parent;
  257.     while ((newp->n_flag & NNET) && newp->n_parent)
  258.         newp = newp->n_parent;
  259.  
  260.     /* use fewer hops, if possible */
  261.     metric = height(oldp) - height(newp);
  262.     if (metric < 0)
  263.         return OLDP;
  264.     if (metric > 0)
  265.         return NEWP;
  266.  
  267.     /*
  268.      * compare names
  269.      */
  270.     opname = oldp->n_name;
  271.     npname = newp->n_name;
  272.     name = n->n_name;
  273.  
  274.     /* use longest common prefix with parent */
  275.     while (*opname == *name && *npname == *name && *name) {
  276.         opname++;
  277.         npname++;
  278.         name++;
  279.     }
  280.     if (*opname == *name)
  281.         return OLDP;
  282.     if (*npname == *name)
  283.         return NEWP;
  284.  
  285.     /* use shorter host name */
  286.     metric = strlen(opname) - strlen(npname);
  287.     if (metric < 0)
  288.         return OLDP;
  289.     if (metric > 0)
  290.         return NEWP;
  291.  
  292.     /* use larger lexicographically */
  293.     metric = strcmp(opname, npname);
  294.     if (metric < 0)
  295.         return NEWP;
  296.     return OLDP;
  297. }
  298.  
  299. STATIC int
  300. height(n)
  301.     register node *n;
  302. {    register int i = 0;
  303.  
  304.     if (n == 0)
  305.         return 0;
  306.     while ((n = n->n_parent) != 0)
  307.         if (ISADOMAIN(n) || !(n->n_flag & NNET))
  308.             i++;
  309.     return i;
  310. }
  311.     
  312. /* l is a terminal edge from n -> next; return a copy of next */
  313. node *
  314. ncopy(n)
  315.     register node *n;
  316. {    register node *ncp;
  317.  
  318.     ncp = newnode();
  319.     ncp->n_name = n->n_name;    /* nonvolatile */
  320.     ncp->n_tloc = --Hashpart;    /* better not be > 20% of total ... */
  321.     if (Hashpart == Nheap)
  322.         die("too many terminal links");
  323.     Table[Hashpart] = ncp;
  324.     ncp->n_copy = n->n_copy;    /* circular list */
  325.     n->n_copy = ncp;
  326.     ncp->n_link = lcopy(n->n_link);
  327.     ncp->n_flag = (n->n_flag & ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT)) | NTERMINAL;
  328.     return ncp;
  329. }
  330.  
  331. STATIC link *
  332. lcopy(l)
  333.     register link *l;
  334. {    register link *lcp;
  335.  
  336.     if (l == 0)
  337.         return 0;
  338.     lcp = newlink();
  339.     *lcp = *l;
  340.     lcp->l_flag &= ~LTREE;
  341.     lcp->l_next = lcopy(l->l_next);
  342.     return lcp;
  343. }
  344.