home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume12 / pathalias9 / part01 / printit.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-08  |  6.7 KB  |  324 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)printit.c    9.1 87/10/04";
  4. #endif
  5.  
  6. #include "def.h"
  7.  
  8. /*
  9.  * print the routes by traversing the shortest path tree in preorder.
  10.  * use lots of char bufs -- profiling indicates this costs about 5 kbytes
  11.  */
  12.  
  13. /* exports */
  14. extern void printit();
  15.  
  16. /* imports */
  17. extern int Cflag, Vflag, Dflag, Fflag;
  18. extern node *Home;
  19. extern char *Netchars;
  20. extern void die();
  21.  
  22. /* privates */
  23. static link *Ancestor;    /* for -f option */
  24. STATIC void preorder(), setpath(), printhost(), printdomain();
  25. STATIC char *hostpath();
  26.  
  27. /* in practice, even the longest paths are < 100 bytes */
  28. #define PATHSIZE 512
  29.  
  30. void
  31. printit()
  32. {    link *l;
  33.     char pbuf[PATHSIZE];
  34.  
  35.     /* print home */
  36.     if (Cflag)
  37.         printf("%ld\t", (long) Home->n_cost);
  38.     printf("%s\t%%s\n", Home->n_name);
  39.     
  40.     strcpy(pbuf, "%s");
  41.     for (l = Home->n_link; l; l = l->l_next) {
  42.         if (l->l_flag & LTREE) {
  43.             l->l_flag &= ~LTREE;
  44.             Ancestor = l;
  45.             preorder(l, pbuf);
  46.             strcpy(pbuf, "%s");
  47.         }
  48.     }
  49.     fflush(stdout);
  50.     fflush(stderr);
  51. }
  52.  
  53. /*
  54.  * preorder traversal of shortest path tree.
  55.  */
  56. STATIC void
  57. preorder(l, ppath)
  58.     register link *l;
  59.     char *ppath;
  60. {    register node *n;
  61.     node *ncp;        /* circular copy list */
  62.     Cost cost;
  63.     char npath[PATHSIZE];
  64.     short p_dir;        /* DIR bits of parent (for nets) */
  65.     char p_op;        /* net op of parent (for nets) */
  66.  
  67.     setpath(l, ppath, npath);
  68.     n = l->l_to;
  69.     if (printable(n)) {
  70.         if (Fflag)
  71.             cost = Ancestor->l_to->n_cost;
  72.         else
  73.             cost = n->n_cost;
  74.         if (ISADOMAIN(n))
  75.             printdomain(n, npath, cost);
  76.         else if (!(n->n_flag & NNET)) {
  77.             printhost(n, npath, cost);
  78.         }
  79.         n->n_flag |= PRINTED;
  80.         for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy)
  81.             ncp->n_flag |= PRINTED;
  82.     }
  83.  
  84.     /* prepare routing bits for domain members */
  85.     p_dir = l->l_flag & LDIR;
  86.     p_op = l->l_netop;
  87.  
  88.     /* recursion */
  89.     for (l = n->n_link; l; l = l->l_next) {
  90.         if (!(l->l_flag & LTREE))
  91.             continue;
  92.         /* network member inherits the routing syntax of its gateway */
  93.         if (ISANET(n)) {
  94.             l->l_flag = (l->l_flag & ~LDIR) | p_dir;
  95.             l->l_netop = p_op;
  96.         }
  97.         l->l_flag &= ~LTREE;
  98.         preorder(l, npath);
  99.     }
  100. }
  101.  
  102. STATIC int
  103. printable(n)
  104.     register node *n;
  105. {    node *ncp;
  106.     link *l;
  107.  
  108.     if (n->n_flag & PRINTED)
  109.         return 0;
  110.  
  111.     /* is there a cheaper copy? */
  112.     for (ncp = n->n_copy; n != ncp; ncp = ncp->n_copy) {
  113.         if (!(ncp->n_flag & MAPPED))
  114.             continue;    /* unmapped copy */
  115.  
  116.         if (n->n_cost > ncp->n_cost)
  117.             return 0;    /* cheaper copy */
  118.  
  119.         if (n->n_cost == ncp->n_cost && !(ncp->n_flag & NTERMINAL))
  120.             return 0;    /* synthetic copy */
  121.     }
  122.  
  123.     /* will a domain route suffice? */
  124.     if (Dflag && !ISANET(n) && ISADOMAIN(n->n_parent)) {
  125.         /*
  126.          * are there any interesting links?  a link
  127.          * is interesting if it doesn't point back
  128.          * to the parent, and is not an alias.
  129.          */
  130.  
  131.         /* check n */
  132.         for (l = n->n_link; l; l = l->l_next) {
  133.             if (l->l_to == n->n_parent)
  134.                 continue;
  135.             if ((!l->l_flag & LALIAS))
  136.                 return 1;
  137.         }
  138.  
  139.         /* check copies of n */
  140.         for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy) {
  141.             for (l = ncp->n_link; l; l = l->l_next) {
  142.                 if (l->l_to == n->n_parent)
  143.                     continue;
  144.                 if (!(l->l_flag & LALIAS))
  145.                     return 1;
  146.             }
  147.         }
  148.  
  149.         /* domain route suffices */
  150.         return 0;
  151.     }
  152.     return 1;
  153. }
  154.  
  155. STATIC void
  156. setpath(l, ppath, npath) 
  157.     link *l;
  158.     register char *ppath, *npath;
  159. {    register node *next, *parent;
  160.     char netchar;
  161.  
  162.     next = l->l_to;
  163.     parent = next->n_parent;
  164.     netchar = NETCHAR(l);
  165.  
  166.     /* for magic @->% conversion */
  167.     if (parent->n_flag & ATSIGN)
  168.         next->n_flag |= ATSIGN;
  169.  
  170.     /*
  171.      * i've noticed that distant gateways to domains frequently get
  172.      * ...!gateway!user@dom.ain wrong.  ...!gateway!user%dom.ain
  173.      * seems to work, so if next is a domain and the parent is
  174.      * not the local host, force a magic %->@ conversion.  in this
  175.      * context, "parent" is the nearest ancestor that is not a net.
  176.      */
  177.     while (ISANET(parent))
  178.         parent = parent->n_parent;
  179.     if (ISADOMAIN(next) && parent != Home)
  180.         next->n_flag |= ATSIGN;
  181.  
  182.     /*
  183.      * special handling for nets (including domains) and aliases.
  184.      * part of the trick is to treat aliases to domains as 0 cost
  185.      * links.  (the author believes they should be declared as such
  186.      * in the input, but the world disagrees).
  187.      */
  188.     if (ISANET(next) || ((l->l_flag & LALIAS) && !ISADOMAIN(parent))) {
  189.         strcpy(npath, ppath);
  190.         return;
  191.     }
  192.         
  193.     if (netchar == '@')
  194.         if (next->n_flag & ATSIGN)
  195.             netchar = '%';    /* shazam?  shaman? */
  196.         else
  197.             next->n_flag |= ATSIGN;
  198.  
  199.     /* remainder should be a sprintf -- foo on '%' as an operator */
  200.     for ( ; *npath = *ppath; ppath++) {
  201.         if (*ppath == '%') {
  202.             switch(ppath[1]) {
  203.             case 's':
  204.                 ppath++;
  205.                 npath = hostpath(npath, l, netchar);
  206.                 break;
  207.  
  208.             case '%':
  209.                 *++npath = *++ppath;
  210.                 npath++;
  211.                 break;
  212.  
  213.             default:
  214.                 die("unknown escape in setpath");
  215.                 break;
  216.             }
  217.         } else
  218.             npath++;
  219.     }
  220. }
  221.  
  222. STATIC char *
  223. hostpath(path, l, netchar)
  224.     register char *path;
  225.     register link *l;
  226.     char netchar;
  227. {    register node *prev;
  228.  
  229.     prev = l->l_to->n_parent;
  230.     if (NETDIR(l) == LLEFT) {
  231.         /* host!%s */
  232.         strcpy(path, l->l_to->n_name);
  233.         path += strlen(path);
  234.         while (ISADOMAIN(prev)) {
  235.             strcpy(path, prev->n_name);
  236.             path += strlen(path);
  237.             prev = prev->n_parent;
  238.         }
  239.         *path++ = netchar;
  240.         if (netchar == '%')
  241.             *path++ = '%';
  242.         *path++ = '%';
  243.         *path++ = 's';
  244.     } else {
  245.         /* %s@host */
  246.         *path++ = '%';
  247.         *path++ = 's';
  248.         *path++ = netchar;
  249.         if (netchar == '%')
  250.             *path++ = '%';
  251.         strcpy(path, l->l_to->n_name);
  252.         path += strlen(path);
  253.         while (ISADOMAIN(prev)) {
  254.             strcpy(path, prev->n_name);
  255.             path += strlen(path);
  256.             prev = prev->n_parent;
  257.         }
  258.     }
  259.     return path;
  260. }
  261.  
  262. STATIC void
  263. printhost(n, path, cost)
  264.     register node *n;
  265.     char *path;
  266.     Cost cost;
  267. {
  268.     if (n->n_flag & PRINTED)
  269.         die("printhost called twice");
  270.     n->n_flag |= PRINTED;
  271.     /* skip private hosts */
  272.     if ((n->n_flag & ISPRIVATE) == 0) {
  273.         if (Cflag)
  274.             printf("%ld\t", (long) cost);
  275.         fputs(n->n_name, stdout);
  276.         putchar('\t');
  277.         puts(path);
  278.     }
  279. }
  280.  
  281. STATIC void
  282. printdomain(n, path, cost)
  283.     register node *n;
  284.     char *path;
  285.     Cost cost;
  286. {    node *p;
  287.  
  288.     if (n->n_flag & PRINTED)
  289.         die("printdomain called twice");
  290.     n->n_flag |= PRINTED;
  291.  
  292.     /*
  293.      * print a route for dom.ain if it is a top-level domain, unless
  294.      * it is private.
  295.      *
  296.      * print a route for sub.dom.ain only if all its ancestor dom.ains
  297.      * are private and sub.dom.ain is not private.
  298.      */
  299.     if (!ISADOMAIN(n->n_parent)) {
  300.         /* top-level domain */
  301.         if (n->n_flag & ISPRIVATE) {
  302.             vprintf(stderr, "ignoring private top-level domain %s\n", n->n_name);
  303.             return;
  304.         }
  305.     } else {
  306.         /* subdomain */
  307.         for (p = n->n_parent; ISADOMAIN(p); p = p->n_parent)
  308.             if (!(p->n_flag & ISPRIVATE))
  309.                 return;
  310.         if (n->n_flag & ISPRIVATE)
  311.             return;
  312.     }
  313.  
  314.     /* print it (at last!) */
  315.     if (Cflag)
  316.         printf("%ld\t", (long) cost);
  317.     do {
  318.         fputs(n->n_name, stdout);
  319.         n = n->n_parent;
  320.     } while (ISADOMAIN(n));
  321.     putchar('\t');
  322.     puts(path);
  323. }
  324.