home *** CD-ROM | disk | FTP | other *** search
/ back2roots/padua / padua.7z / padua / uucp / pathalias_V10.lzh / addlink.c next >
C/C++ Source or Header  |  1992-01-23  |  6KB  |  288 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)addlink.c    9.7 88/06/10";
  4. #endif /* lint */
  5.  
  6. #include "def.h"
  7.  
  8. /* exports */
  9. extern link *addlink();
  10. extern void deadlink(), atrace(), freelink();
  11. extern int tracelink(), maptrace();
  12. char *Netchars = "!:@%";    /* sparse, but sufficient */
  13. long Lcount;            /* how many edges? */
  14.  
  15. /* imports */
  16. extern int Tflag, Dflag;
  17. extern link *newlink();
  18. extern node *addnode();
  19. extern void yyerror(), die();
  20. extern int strcmp(), strlen();
  21.  
  22. /* privates */
  23. STATIC void netbits(), ltrace(), ltrprint();
  24. static link    *Trace[NTRACE];
  25. static int    Tracecount;
  26.  
  27. #define EQ(n1, n2)    (strcmp((n1)->n_name, (n2)->n_name) == 0)
  28. #define LTRACE        if (Tflag) ltrace
  29.  
  30. link *
  31. addlink(from, to, cost, netchar, netdir)
  32.     node *from;
  33.     register node *to;
  34.     Cost cost;
  35.     char netchar, netdir;
  36. {    register link *l, *prev = 0;
  37.  
  38.     LTRACE(from, to, cost, netchar, netdir, "");
  39.     /*
  40.      * maintain uniqueness for dead links (only).
  41.      */
  42.     for (l = from->n_link; l; l = l->l_next) {
  43.         if (!DEADLINK(l))
  44.             break;
  45.         if (to == l->l_to) {
  46.             /* what the hell, use cheaper dead cost */
  47.             if (cost < l->l_cost) {
  48.                 l->l_cost = cost;
  49.                 netbits(l, netchar, netdir);
  50.             }
  51.             return l;
  52.         }
  53.         prev = l;
  54.     }
  55.     
  56.  
  57.     /* allocate and link in the new link struct */
  58.     l = newlink();
  59.     if (cost != INF)    /* ignore back links */
  60.         Lcount++;
  61.     if (prev) {
  62.         l->l_next = prev->l_next;
  63.         prev->l_next = l;
  64.     } else {
  65.         l->l_next = from->n_link;
  66.         from->n_link = l;
  67.     }
  68.  
  69.     l->l_to = to;
  70.     /* add penalty */
  71.     if ((l->l_cost = cost + from->n_cost) < 0) {
  72.         char buf[100];
  73.  
  74.         l->l_flag |= LDEAD;
  75.         sprintf(buf, "link to %s ignored with negative cost", to->n_name);
  76.         yyerror(buf);
  77.     }
  78.     if (netchar == 0) {
  79.         netchar = DEFNET;
  80.         netdir = DEFDIR;
  81.     }
  82.     netbits(l, netchar, netdir);
  83.     if (Dflag && ISADOMAIN(from))
  84.         l->l_flag |= LTERMINAL;
  85.  
  86.     return l;
  87. }
  88.  
  89. void
  90. deadlink(nleft, nright) 
  91.     node *nleft, *nright;
  92. {    link *l, *lhold = 0, *lprev, *lnext;
  93.  
  94.     /* DEAD host */
  95.     if (nright == 0) {
  96.         nleft->n_flag |= NDEAD;        /* DEAD host */
  97.         return;
  98.     }
  99.  
  100.     /* DEAD link */
  101.  
  102.     /* grab <nleft, nright> instances at head of nleft adjacency list */
  103.     while ((l = nleft->n_link) != 0 && l->l_to == nright) {
  104.         nleft->n_link = l->l_next;    /* disconnect */
  105.         l->l_next = lhold;        /* terminate */
  106.         lhold = l;            /* add to lhold */
  107.     }
  108.  
  109.     /* move remaining <nleft, nright> instances */
  110.     for (lprev = nleft->n_link; lprev && lprev->l_next; lprev = lprev->l_next) {
  111.         if (lprev->l_next->l_to == nright) {
  112.             l = lprev->l_next;
  113.             lprev->l_next = l->l_next;    /* disconnect */
  114.             l->l_next = lhold;        /* terminate */
  115.             lhold = l;
  116.         }
  117.     }
  118.  
  119.     /* check for emptiness */
  120.     if (lhold == 0) {
  121.         addlink(nleft, nright, INF / 2, DEFNET, DEFDIR)->l_flag |= LDEAD;
  122.         return;
  123.     }
  124.  
  125.     /* reinsert deleted edges as DEAD links */
  126.     for (l = lhold; l; l = lnext) {
  127.         lnext = l->l_next;
  128.         addlink(nleft, nright, l->l_cost, NETCHAR(l), NETDIR(l))->l_flag |= LDEAD;
  129.         freelink(l);
  130.     }
  131. }
  132.  
  133. STATIC void
  134. netbits(l, netchar, netdir)
  135.     register link *l;
  136.     char netchar, netdir;
  137. {
  138.     l->l_flag &= ~LDIR;
  139.     l->l_flag |= netdir;
  140.     l->l_netop = netchar;
  141. }
  142.  
  143. int
  144. tracelink(arg) 
  145.     char *arg;
  146. {    char *bang;
  147.     link *l;
  148.  
  149.     if (Tracecount >= NTRACE)
  150.         return -1;
  151.     l = newlink();
  152.     bang = index(arg, '!');
  153.     if (bang) {
  154.         *bang = 0;
  155.         l->l_to = addnode(bang+1);
  156.     } else 
  157.         l->l_to = 0;
  158.  
  159.     l->l_from = addnode(arg);
  160.     Trace[Tracecount++] = l;
  161.     return 0;
  162. }
  163.  
  164. /*
  165.  * the obvious choice for testing equality is to compare struct
  166.  * addresses, but that misses private nodes, so we use strcmp().
  167.  */
  168.  
  169. STATIC void
  170. ltrace(from, to, cost, netchar, netdir, message)
  171.     node *from, *to;
  172.     Cost cost;
  173.     char netchar, netdir, *message;
  174. {    link *l;
  175.     int i;
  176.  
  177.     for (i = 0; i < Tracecount; i++) {
  178.         l = Trace[i];
  179.         /* overkill, but you asked for it! */
  180.         if (l->l_to == 0) {
  181.             if (EQ(from, l->l_from) || EQ(to, l->l_from))
  182.                 break;
  183.         } else if (EQ(from, l->l_from) && EQ(to, l->l_to))
  184.             break;
  185.         else if (EQ(from, l->l_to) && EQ(to, l->l_from))
  186.             break;    /* potential dead backlink */
  187.     }
  188.     if (i < Tracecount)
  189.         ltrprint(from, to, cost, netchar, netdir, message);
  190. }
  191.  
  192. /* print a trace item */
  193. STATIC void
  194. ltrprint(from, to, cost, netchar, netdir, message)
  195.     node *from, *to;
  196.     Cost cost;
  197.     char netchar, netdir, *message;
  198. {    char buf[256], *bptr = buf;
  199.  
  200.     strcpy(bptr, from->n_name);
  201.     bptr += strlen(bptr);
  202.     *bptr++ = ' ';
  203.     if (netdir == LRIGHT)            /* @% */
  204.         *bptr++ = netchar;
  205.     strcpy(bptr, to->n_name);
  206.     bptr += strlen(bptr);
  207.     if (netdir == LLEFT)            /* !: */
  208.         *bptr++ = netchar;
  209.     sprintf(bptr, "(%ld) %s", cost, message);
  210.     yyerror(buf);
  211. }
  212.  
  213. void
  214. atrace(n1, n2)
  215.     node *n1, *n2;
  216. {    link *l;
  217.     int i;
  218.     char buf[256];
  219.  
  220.     for (i = 0; i < Tracecount; i++) {
  221.         l = Trace[i];
  222.         if (l->l_to == 0 && ((node *) l->l_from == n1 || (node *) l->l_from == n2)) {
  223.             sprintf(buf, "%s = %s", n1->n_name, n2->n_name);
  224.             yyerror(buf);
  225.             return;
  226.         }
  227.     }
  228. }
  229.  
  230. int
  231. maptrace(from, to)
  232.     register node *from, *to;
  233. {    register link *l;
  234.     register int i;
  235.  
  236.     for (i = 0; i < Tracecount; i++) {
  237.         l = Trace[i];
  238.         if (l->l_to == 0) {
  239.             if (EQ(from, l->l_from) || EQ(to, l->l_from))
  240.                 return 1;
  241.         } else if (EQ(from, l->l_from) && EQ(to, l->l_to))
  242.                 return 1;
  243.     }
  244.     return 0;
  245. }
  246.  
  247. void
  248. deletelink(from, to)
  249.     node *from;
  250.     node *to;
  251. {    register link *l, *lnext;
  252.  
  253.     l = from->n_link;
  254.  
  255.     /* delete all neighbors of from */
  256.     if (to == 0) {
  257.         while (l) {
  258.             LTRACE(from, l->l_to, l->l_cost, NETCHAR(l), NETDIR(l), "DELETED");
  259.             lnext = l->l_next;
  260.             freelink(l);
  261.             l = lnext;
  262.         }
  263.         from->n_link = 0;
  264.         return;
  265.     }
  266.  
  267.     /* delete from head of list */
  268.     while (l && EQ(to, l->l_to)) {
  269.         LTRACE(from, to, l->l_cost, NETCHAR(l), NETDIR(l), "DELETED");
  270.         lnext = l->l_next;
  271.         freelink(l);
  272.         l = from->n_link = lnext;
  273.     }
  274.  
  275.     /* delete from interior of list */
  276.     if (l == 0)
  277.         return;
  278.     for (lnext = l->l_next; lnext; lnext = l->l_next) {
  279.         if (EQ(to, lnext->l_to)) {
  280.             LTRACE(from, to, l->l_cost, NETCHAR(l), NETDIR(l), "DELETED");
  281.             l->l_next = lnext->l_next;
  282.             freelink(lnext);
  283.             /* continue processing this link */
  284.         } else
  285.             l = lnext;    /* next link */
  286.     }
  287. }
  288.