Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/unix/volume12/pathalias9/part01/addlink.c

C/C++ Source or Header | 1987-10-08 | 4.6 KB | 231 lines

/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char    *sccsid = "@(#)addlink.c    9.1 87/10/04";
#endif /* lint */

#include "def.h"

/* exports */
extern link *addlink();
extern void deadlink(), atrace();
extern int tracelink();
char *Netchars = "!:@%";    /* sparse, but sufficient */
long Lcount;            /* how many edges? */


/* imports */
extern int Tflag, Dflag;
extern link *newlink();
extern node *addnode();
extern void yyerror(), die();

/* privates */
STATIC void netbits(), ltrace(), ltrprint();
static link    *Trace[NTRACE];
static int    Tracecount;

link *
addlink(from, to, cost, netchar, netdir)
    node *from;
    register node *to;
    Cost cost;
    char netchar, netdir;
{    register link *l, *prev = 0;

    if (Tflag)
        ltrace(from, to, cost, netchar, netdir);
    /*
     * maintain uniqueness for dead links (only).
     */
    for (l = from->n_link; l; l = l->l_next) {
        if (!(l->l_flag & LDEAD))
            break;
        if (to == l->l_to) {
            /* what the hell, use cheaper dead cost */
            if (cost < l->l_cost) {
                l->l_cost = cost;
                netbits(l, netchar, netdir);
            }
            return l;
        }
        prev = l;
    }


    /* allocate and link in the new link struct */
    l = newlink();
    if (cost != INF)    /* ignore back links */
        Lcount++;
    if (prev) {
        l->l_next = prev->l_next;
        prev->l_next = l;
    } else {
        l->l_next = from->n_link;
        from->n_link = l;
    }

    l->l_to = to;
    l->l_cost = cost + from->n_cost;    /* add penalty */
    if (netchar == 0) {
        netchar = DEFNET;
        netdir = DEFDIR;
    }
    netbits(l, netchar, netdir);
    if (Dflag && ISADOMAIN(from) && !ISADOMAIN(to))
        l->l_flag |= LTERMINAL;

    return l;
}

void
deadlink(nleft, nright)
    node *nleft, *nright;
{    link *l, *lhold = 0, *lprev, *lnext;

    /* DEAD host */
    if (nright == 0) {
        nleft->n_flag |= NDEAD;        /* DEAD host */
        return;
    }

    /* DEAD link */

    /* grab <nleft, nright> instances at head of nleft adjacency list */
    while ((l = nleft->n_link) != 0 && l->l_to == nright) {
        nleft->n_link = l->l_next;    /* disconnect */
        l->l_next = lhold;        /* terminate */
        lhold = l;            /* add to lhold */
    }

    /* move remaining <nleft, nright> instances */
    for (lprev = nleft->n_link; lprev && lprev->l_next; lprev = lprev->l_next) {
        if (lprev->l_next->l_to == nright) {
            l = lprev->l_next;
            lprev->l_next = l->l_next;    /* disconnect */
            l->l_next = lhold;        /* terminate */
            lhold = l;
        }
    }

    /* check for emptiness */
    if (lhold == 0) {
        addlink(nleft, nright, INF / 2, DEFNET, DEFDIR)->l_flag |= LDEAD;
        return;
    }

    /* reinsert deleted edges as DEAD links */
    for (l = lhold; l; l = lnext) {
        lnext = l->l_next;
        addlink(nleft, nright, l->l_cost, NETCHAR(l), NETDIR(l))->l_flag |= LDEAD;
        freelink(l);
    }
}

STATIC void
netbits(l, netchar, netdir)
    register link *l;
    char netchar, netdir;
{
    l->l_flag &= ~LDIR;
    l->l_flag |= netdir;
    l->l_netop = netchar;
}

int
tracelink(arg)
    char *arg;
{    char *bang;
    link *l;

    if (Tracecount >= NTRACE)
        return -1;
    l = newlink();
    bang = index(arg, '!');
    if (bang) {
        *bang = 0;
        l->l_to = addnode(bang+1);
    } else
        l->l_to = 0;

    l->l_from = addnode(arg);
    Trace[Tracecount++] = l;
    return 0;
}

STATIC void
ltrace(from, to, cost, netchar, netdir)
    node *from, *to;
    Cost cost;
    char netchar, netdir;
{    link *l;
    int i;

    for (i = 0; i < Tracecount; i++) {
        l = Trace[i];
        /* overkill, but you asked for it! */
        if ((l->l_to == 0
          && (from == (node *) l->l_from || to == (node *) l->l_from))
         || (from == (node *) l->l_from && to == l->l_to)
         || (to == (node *) l->l_from && from == l->l_to)) {
            ltrprint(from, to, cost, netchar, netdir);
            return;
        }
    }
}

/* print a trace item */
STATIC void
ltrprint(from, to, cost, netchar, netdir)
    node *from, *to;
    Cost cost;
    char netchar;
    char netdir;
{    char buf[256], *bptr = buf;

    strcpy(bptr, from->n_name);
    bptr += strlen(bptr);
    *bptr++ = ' ';
    if (netdir == LRIGHT)            /* @% */
        *bptr++ = netchar;
    strcpy(bptr, to->n_name);
    bptr += strlen(bptr);
    if (netdir == LLEFT)            /* !: */
        *bptr++ = netchar;
    sprintf(bptr, "(%ld)", cost);
    yyerror(buf);
}

void
atrace(n1, n2)
    node *n1, *n2;
{    link *l;
    int i;
    char buf[256];

    for (i = 0; i < Tracecount; i++) {
        l = Trace[i];
        if (l->l_to == 0 && ((node *) l->l_from == n1 || (node *) l->l_from == n2)) {
            sprintf(buf, "%s = %s", n1->n_name, n2->n_name);
            yyerror(buf);
            return;
        }
    }
}

#define EQ(n1, n2) strcmp(n1->n_name, n2->n_name) == 0
maptrace(from, to)
    register node *from, *to;
{    register link *l;
    register int i;

    for (i = 0; i < Tracecount; i++) {
        l = Trace[i];
        if (l->l_to == 0) {
            if (EQ(from, l->l_from) || EQ(to, l->l_from))
                return 1;
        } else if (EQ(from, l->l_from) && EQ(to, l->l_to))
                return 1;
    }
    return 0;
}