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