BSD 4_3_Tahoe release

[unix-history] / usr / src / new / pathalias / mapaux.c

/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char     *sccsid = "@(#)mapaux.c 8.2 (down!honey) 86/01/26";
#endif lint

#include "def.h"

void    pack();

void
pack()
{
       long    hole, next;

       /* find first "hole " */
       for (hole = Tabsize - 1; hole >= 0 && Table[hole] != 0; --hole)
               ;

       /* repeatedly move next filled entry into last hole */
       for (next = hole - 1; next >= 0; --next) {
               if (Table[next] != 0) {
                       Table[hole] = Table[next];
                       Table[hole]->n_tloc = hole;
                       Table[next] = 0;
                       while (Table[--hole] != 0)      /* find next hole */
                               ;
               }
       }
       Hashpart = hole + 1;
}

FILE    *Gstream;

dumpgraph()
{
       long    i;
       node    *n;

       if ((Gstream = fopen(Graphout, "w")) == NULL) {
               fprintf(stderr, "%s: ", ProgName);
               perror(Graphout);
       }

       untangle();     /* untangle net cycles for proper output */

       for (i = Hashpart; i < Tabsize; i++) {
               n = Table[i];
               if (n == 0)
                       continue;       /* impossible, but ... */
               /* a minor optimization ... */
               if (n->n_link == 0)
                       continue;
               /* pathparse doesn't need these */
               if (n->n_flag & NNET)
                       continue;
               dumpnode(n);
       }
}

dumpnode(from)
node    *from;
{
       node    *to;
       link    *l;
       char    netbuf[BUFSIZ], *nptr = netbuf;

       for (l = from->n_link ; l; l = l->l_next) {
               to = l->l_to;
               if (from == to)
                       continue;       /* oops -- it's me! */

               if ((to->n_flag & NNET) == 0) {
                       /* host -> host -- print host>host */
                       if (l->l_cost == INF)
                               continue;       /* phoney link */
                       fputs(from->n_name, Gstream);
                       putc('>', Gstream);
                       fputs(to->n_name, Gstream);
                       putc('\n', Gstream);
               } else {
                       /* host -> net -- just cache it for now */
                       while (to->n_root && to != to->n_root)
                               to = to->n_root;
                       *nptr++ = ',';
                       strcpy(nptr, to->n_name);
                       nptr += strlen(nptr);
               }
       }

       /* dump nets */
       if (nptr != netbuf) {
               /* nets -- print host@\tnet,net, ... */
               *nptr = 0;
               fputs(from->n_name, Gstream);
               putc('@', Gstream);
               *netbuf = '\t'; /* insert tab by killing initial ',' */
               fputs(netbuf, Gstream); /* skip initial ',' */
               putc('\n', Gstream);
       }
}

/*
* remove cycles in net definitions. 
*
* depth-first search
*
* for each net, run dfs on its neighbors (nets only).  if we return to
* a visited node, that's a net cycle.  mark the cycle with a pointer
* in the n_root field (which gets us closer to the root of this
* portion of the dfs tree).
*/
untangle()
{
       long    i;
       node    *n;

       for (i = Hashpart; i < Tabsize; i++) {
               n = Table[i];
               if (n == 0 || (n->n_flag & NNET) == 0 || n->n_root)
                       continue;
               dfs(n);
       }
}

dfs(n)
node    *n;
{
       link    *l;
       node    *next;

       n->n_flag |= INDFS;
       n->n_root = n;
       for (l = n->n_link; l; l = l->l_next) {
               next = l->l_to;
               if ((next->n_flag & NNET) == 0)
                       continue;
               if ((next->n_flag & INDFS) == 0) {
                       dfs(next);
                       if (next->n_root != next)
                               n->n_root = next->n_root;
               } else
                       n->n_root = next->n_root;
       }
       n->n_flag &= ~INDFS;
}

showlinks() 
{
       link    *l;
       node    *n;
       long    i;
       FILE    *estream;

       if ((estream = fopen(Linkout, "w")) == 0)
               return;

       for (i = Hashpart; i < Tabsize; i++) {
               n = Table[i];
               if (n == 0)     /* impossible, but ... */
                       continue;
               if (l = n->n_link) {
                       fprintf(estream, "%s\t%s(%d)", n->n_name,
                               l->l_to->n_name,
                               l->l_cost ? l->l_cost : DEFCOST);
                       for (l = l->l_next; l; l = l->l_next)
                               fprintf(estream, ",\n\t%s(%d)", l->l_to->n_name,
                                       l->l_cost ? l->l_cost : DEFCOST);
                       fputc('\n', estream);
               }
       }
       (void) fclose(estream);
}

/*
* n is node in heap, newp is candidate for new parent.
* choose between newp and n->n_parent for parent.
* return 0 to use newp, non-zero o.w.
*/
#define NEWP 0
#define OLDP 1
tiebreaker(n, newp)
node    *n, *newp;
{
       register char   *opname, *npname, *name;
       node    *oldp;
       int     metric;

       oldp = n->n_parent;

       /*
        * given the choice, avoid gatewayed nets,
        * thereby placating the FCC or some such.
        */
       if (GATEWAYED(newp) && !GATEWAYED(oldp))
               return(OLDP);
       if (!GATEWAYED(newp) && GATEWAYED(oldp))
               return(NEWP);

       /* look at real parents, not nets */
       while (oldp->n_flag & NNET)
               oldp = oldp->n_parent;
       while (newp->n_flag & NNET)
               newp = newp->n_parent;

       /* use fewer hops, if possible */
       metric = height(oldp) - height(newp);
       if (metric < 0)
               return(OLDP);
       if (metric > 0)
               return(NEWP);

       /* compare names */
       opname = oldp->n_name;
       npname = newp->n_name;
       name = n->n_name;

       /* find point of departure */
       while (*opname == *npname && *npname == *name) {
               if (*name == 0) {
                       fprintf(stderr, "%s: error in tie breaker\n", ProgName);
                       badmagic(1);
               }
               opname++;
               npname++;
               name++;
       }

       /* use longest match, if appl. */
       if (*opname == *name || *opname == 0)
               return(OLDP);
       if (*npname == *name || *npname == 0)
               return(NEWP);

       /* use shorter host name, if appl. */
       metric = strlen(opname) - strlen(npname);
       if (metric < 0)
               return(OLDP);
       if (metric > 0)
               return(NEWP);

       /* use larger lexicographically (no reason) */
       metric = strcmp(opname, npname);
       if (metric < 0)
               return(NEWP);
       return(OLDP);
}

height(n)
register node   *n;
{
       register int i = 0;

       while ((n = n->n_parent) != 0)
               if ((n->n_flag & NNET) == 0)
                       i++;    /* should count domains too ... */
       return(i);
}