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