home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / TELECOM / palias10.lzh / BNU / PALIAS / mapaux.c < prev    next >
Text File  |  1993-06-07  |  10KB  |  464 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)mapaux.c    9.7 91/06/02";
  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. #ifdef BITNET
  32. STATIC int nodenum(), nodesum();
  33. STATIC Cost revpathcost(), costlookup();
  34. #endif
  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. #ifdef BITNET
  273.     metric = (long) (revpathcost(n) - (costlookup(n, newp) + revpathcost(newp)));
  274.     if (metric < 0)
  275.         return OLDP;
  276.     if (metric > 0)
  277.         return NEWP;
  278.  
  279.     metric = nodesum(oldp) - nodesum(newp);
  280.     if (metric < 0)
  281.         return OLDP;
  282.     if (metric > 0)
  283.         return NEWP;
  284. #endif
  285.  
  286.     /*
  287.      * compare names
  288.      */
  289.     opname = oldp->n_name;
  290.     npname = newp->n_name;
  291.     name = n->n_name;
  292.  
  293.     /* use longest common prefix with parent */
  294.     while (*opname == *name && *npname == *name && *name) {
  295.         opname++;
  296.         npname++;
  297.         name++;
  298.     }
  299.     if (*opname == *name)
  300.         return OLDP;
  301.     if (*npname == *name)
  302.         return NEWP;
  303.  
  304.     /* use shorter host name */
  305.     metric = strlen(opname) - strlen(npname);
  306.     if (metric < 0)
  307.         return OLDP;
  308.     if (metric > 0)
  309.         return NEWP;
  310.  
  311.     /* use larger lexicographically */
  312.     metric = strcmp(opname, npname);
  313.     if (metric < 0)
  314.         return NEWP;
  315.     return OLDP;
  316. }
  317.  
  318. STATIC int
  319. height(n)
  320.     register node *n;
  321. {    register int i = 0;
  322.  
  323.     if (n == 0)
  324.         return 0;
  325.     while ((n = n->n_parent) != 0)
  326.         if (ISADOMAIN(n) || !(n->n_flag & NNET))
  327.             i++;
  328.     return i;
  329. }
  330.     
  331. /*
  332.  * return a copy of n ( == l->l_to).  we rely on n and its copy
  333.  * pointing to the same name string, which is kludgey, but works
  334.  * because the name is non-volatile.
  335.  */
  336.  
  337. #define REUSABLE(n, l)    (((n)->n_flag & NTERMINAL) == 0 \
  338.               && ((n)->n_copy->n_flag & NTERMINAL) \
  339.               && !((n)->n_copy->n_flag & NALIAS) \
  340.               && !((l)->l_flag & LALIAS))
  341. node *
  342. ncopy(parent, l)
  343.     register node *parent;
  344.     register link *l;
  345. {    register node *n, *ncp;
  346.  
  347. #ifdef DEBUG
  348.     if (Vflag > 1)
  349.         vprintf(stderr, "<%s> <- %s\n", l->l_to->n_name, parent->n_name);
  350. #endif
  351.     n = l->l_to;
  352.     if (REUSABLE(n, l)) {
  353.         Nlink++;
  354.         return n->n_copy;    /* re-use */
  355.     }
  356.     NumNcopy++;
  357.     l->l_to = ncp = newnode();
  358.     ncp->n_name = n->n_name;    /* nonvolatile */
  359.     ncp->n_tloc = --Hashpart;    /* better not be > 20% of total ... */
  360.     if (Hashpart == Nheap)
  361.         die("too many terminal links");
  362.     Table[Hashpart] = ncp;
  363.     ncp->n_copy = n->n_copy;    /* circular list */
  364.     n->n_copy = ncp;
  365.     ncp->n_link = lcopy(parent, n);
  366.     ncp->n_flag = (n->n_flag & ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT)) | NTERMINAL;
  367.     return ncp;
  368. }
  369.  
  370. /*
  371.  * copy n's links but don't copy any terminal links
  372.  * since n is itself at the end of a terminal link.
  373.  *
  374.  * this is a little messier than it should be, because
  375.  * it wants to be recursive, but the recursion might be
  376.  * very deep (for a long link list), so it iterates.
  377.  *
  378.  * why copy any links other than aliases?  hmmm ...
  379.  */
  380. STATIC link *
  381. lcopy(parent, n)
  382.     register node *parent, *n;
  383. {    register link *l, *lcp;
  384.     link *first = 0, *last = 0;
  385.  
  386.     for (l = n->n_link; l != 0; l = l->l_next) {
  387.         /* skip if dest is already mapped */
  388.         if ((l->l_to->n_flag & MAPPED) != 0)
  389.             continue;
  390.         /* don't copy terminal links */
  391.         if ((l->l_flag & LTERMINAL) != 0)
  392.             continue;
  393.         /* comment needed */
  394.         if (ALTEREGO(l->l_to, parent))
  395.             continue;
  396. #ifdef DEBUG
  397.         if (Vflag > 1)
  398.             vprintf(stderr, "\t-> %s\n", l->l_to->n_name);
  399. #endif
  400.         NumLcopy++;
  401.         lcp = newlink();
  402.         *lcp = *l;    /* struct copy */
  403.         lcp->l_flag &= ~LTREE;
  404.         if (ISANET(n))
  405.             lcp->l_flag |= LTERMINAL;
  406.  
  407.         if (first == 0) {
  408.             first = last = lcp;
  409.         } else {
  410.             last->l_next = lcp;
  411.             last = lcp;
  412.         }
  413.     }
  414.     if (last)
  415.         last->l_next = 0;
  416.     return first;
  417. }
  418.  
  419. #ifdef BITNET
  420. STATIC Cost
  421. revpathcost(n)
  422.     node *n;
  423. {    Cost sum;
  424.  
  425.     for (sum = 0; n->n_parent != 0; n = n->n_parent)
  426.         sum += costlookup(n, n->n_parent);
  427.     return sum;
  428. }
  429.  
  430. STATIC Cost
  431. costlookup(n, p)
  432.     node *n, *p;
  433. {    link *l;
  434.     
  435.     for (l = n->n_link; l != 0; l = l->l_next)
  436.         if (l->l_to == p)
  437.             return l->l_cost;
  438.     return INF;
  439. }
  440.  
  441. STATIC int
  442. nodenum(n)
  443.     node *n;
  444. {    link *l;
  445.  
  446.     for (l = n->n_link; l != 0; l = l->l_next)
  447.         if ((l->l_flag & LALIAS) != 0 && strncmp(l->l_to, "node.", 5) == 0)
  448.             return atoi(l->l_to->n_name + 5);
  449.     return 0;
  450. }
  451.  
  452. STATIC int
  453. nodesum(n)
  454.     node *n;
  455. {    int sum = 0;
  456.  
  457.     do
  458.         sum += nodenum(n);
  459.     while ((n = n->n_parent) != 0);
  460.  
  461.     return sum;
  462. }
  463. #endif /*BITNET*/
  464.