sources-request@panda.UUCP (01/23/86)
Mod.sources: Volume 3, Issue 93
Submitted by: princeton!down!honey (Peter Honeyman)
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
# addlink.c
# addnode.c
# extern.c
# local.c
# main.c
# makedb.c
# mapaux.c
# mapit.c
# mem.c
# printit.c
# parse.y
# This archive created: Wed Jan 22 18:53:16 1986
export PATH; PATH=/bin:$PATH
echo shar: extracting "'addlink.c'" '(3358 characters)'
if test -f 'addlink.c'
then
echo shar: will not over-write existing file "'addlink.c'"
else
cat << \SHAR_EOF > 'addlink.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)addlink.c 8.1 (down!honey) 86/01/19";
#endif lint
#include "def.h"
static link *Trace[NTRACE];
static int Tracecount;
link *
addlink(from, to, cost, netchar, netdir)
node *from;
register node *to;
Cost cost;
char netchar;
char 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_flag & LDEAD; l = l->l_next) {
if (to == l->l_to) {
/* what the hell, use cheaper 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;
if (netchar == 0) {
netchar = DEFNET;
netdir = DEFDIR;
}
netbits(l, netchar, netdir);
return(l);
}
link *
addgateway(from, to, cost, netchar, netdir)
node *from;
node *to;
Cost cost;
char netchar;
char netdir;
{
register link *l;
l = addlink(from, to, cost, netchar, netdir);
l->l_flag |= LGATEWAY;
return(l);
}
deadlink(s)
char *s;
{
char *t, c;
link *l;
t = index(s, '!');
if (t) {
c = *t;
*t = 0;
l = addlink(addnode(s), addnode(t + 1), INF / 2, c, DEFDIR);
l->l_flag |= LDEAD;
} else
addnode(s)->n_flag |= NDEAD;
}
netbits(l, netchar, netdir)
link *l;
char netchar, netdir;
{
char *nptr;
if ((nptr = index(Netchars, netchar)) == 0) {
fprintf(stderr, "%s: unknown network operator: %c\n",
ProgName, netchar);
badmagic(1);
}
l->l_flag &= ~(LNETCHARS|LDIR);
l->l_flag |= (nptr - Netchars) | dirbits(netdir);
}
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 = (link *) addnode(arg);
Trace[Tracecount++] = l;
return(0);
}
STATIC
ltrace(from, to, cost, netchar, netdir)
node *from, *to;
Cost cost;
char netchar;
char netdir;
{
link *l;
int i;
for (i = 0; i < Tracecount; i++) {
l = Trace[i];
/* overkill -- 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
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);
}
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;
}
}
}
SHAR_EOF
if test 3358 -ne "`wc -c < 'addlink.c'`"
then
echo shar: error transmitting "'addlink.c'" '(should have been 3358 characters)'
fi
fi
echo shar: extracting "'addnode.c'" '(6585 characters)'
if test -f 'addnode.c'
then
echo shar: will not over-write existing file "'addnode.c'"
else
cat << \SHAR_EOF > 'addnode.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)addnode.c 8.1 (down!honey) 86/01/19";
#endif
#include "def.h"
extern void lowercase(), rehash();
extern node *isprivate();
extern long hash();
/*
* these numbers are chosen because:
* -> they are prime,
* -> they are monotonic increasing,
* -> each is a tad smaller than a multiple of 1024,
* -> they form a fibonacci sequence (almost).
* the first point yields good hash functions, the second is used for the
* standard re-hashing implementation of open addressing, the third
* optimizes for quirks in some mallocs i have seen, and the fourth simply
* appeals to me.
*/
static int Primes[] = {
#ifndef SQUANDER
1021, 2039, 3067, 5113, 8179,
#endif
13309, 21499, 0
};
static int Tabindex = -1;
static int Collision; /* mark host name collisions in hash() */
node *
addnode(name)
register char *name;
{
register long i;
register node *n;
if (Iflag)
lowercase(name);
/* is it a private host? */
n = isprivate(name);
if (n)
return(n);
i = hash(name, 0);
if (Table[i])
return(Table[i]);
n = newnode();
n->n_name = strsave(name);
Table[i] = n;
n->n_tloc = i; /* essentially a back link to the table */
if (Collision)
n->n_flag |= COLLISION; /* name collision with private host */
return(n);
}
alias(n1, n2)
node *n1, *n2;
{
link *l;
extern link *addlink();
l = addlink(n1, n2, (Cost) 0, DEFNET, DEFDIR);
l->l_flag |= LALIAS;
l = addlink(n2, n1, (Cost) 0, DEFNET, DEFDIR);
l->l_flag |= LALIAS;
if (Tflag)
atrace(n1, n2);
}
/*
* fold a string into a long int. this algorithm ignores all but the last
* eight bytes, which affects < 15% of all host names, many of which have
* common prefixes anyway.
*/
STATIC long
fold(str)
register char *str;
{
register long sum;
sum = *str++;
while (*str) {
sum <<= 4;
sum += *str++;
}
if (sum < 0)
sum = -sum;
return(sum);
}
#define HASH1(n) ((n) % Tabsize);
#define HASH2(n) (Tabsize - 2 - ((n) % (Tabsize-2))) /* princeton!rs */
/*
* with a 0.75 high water mark, probes per access should be 1.84.
* use long constant to force promotion.
*/
#define HIGHWATER 75L
#define isfull(n, size) ((n) > ((size) * HIGHWATER) / 100)
STATIC long
hash(name, unique)
char *name;
{
register long probe, hash2;
register node *n;
if (Tabindex < 0) { /* first time */
Tabindex = 0;
Tabsize = Primes[0];
Table = newtable(Tabsize);
} else if (isfull(Ncount, Tabsize))
rehash(); /* more, more! */
probe = fold(name);
/* don't change the order of the next two lines */
hash2 = HASH2(probe);
probe = HASH1(probe);
/* thank you! */
/*
* probe the hash table.
* if unique is set, we require a fresh slot.
* otherwise, use double hashing to find either
* (1) an empty slot, or
* (2) a non-private copy of this host name
*
* as a side effect, if we notice a collision with a private host
* we mark the other so that it is skipped at output time.
*/
Collision = 0;
while ((n = Table[probe]) != 0) {
if (strcmp(n->n_name, name) == 0) {
if (unique)
n->n_flag |= COLLISION;
else if (n->n_flag & ISPRIVATE)
Collision++;
else
break; /* this is it! */
}
probe -= hash2;
if (probe < 0)
probe += Tabsize;
}
return(probe);
}
STATIC void
rehash()
{
register node **otable, **optr;
register long probe;
long osize;
#ifdef DEBUG
hashanalyze();
#endif
optr = Table + Tabsize - 1; /* ptr to last */
otable = Table;
osize = Tabsize;
Tabsize = Primes[++Tabindex];
if (Tabsize == 0) { /* need more prime numbers */
fprintf(stderr, "%s: > %d hosts\n", ProgName, Primes[Tabindex-1]);
badmagic(1);
}
vprintf(stderr, "rehash into %d\n", Tabsize);
Table = newtable(Tabsize);
do {
if (*optr == 0)
continue; /* empty slot in old table */
probe = hash((*optr)->n_name, (*optr)->n_flag & ISPRIVATE);
if (Table[probe] != 0) {
fprintf(stderr, "%s: rehash error\n", ProgName);
badmagic(1);
}
Table[probe] = *optr;
(*optr)->n_tloc = probe;
} while (optr-- > otable);
freetable(otable, osize);
}
hashanalyze()
{
long probe, hash2;
int count, i, collision[8];
int longest = 0, total = 0, slots = 0;
int nslots = sizeof(collision)/sizeof(collision[0]);
if (!Vflag)
return;
strclear((char *) collision, sizeof(collision));
for (i = 0; i < Tabsize; i++) {
if (Table[i] == 0)
continue;
/* private hosts too hard to account for ... */
if (Table[i]->n_flag & ISPRIVATE)
continue;
count = 1;
probe = fold(Table[i]->n_name);
/* don't change the order of the next two lines */
hash2 = HASH2(probe);
probe = HASH1(probe);
/* thank you! */
while (Table[probe] != 0
&& strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
count++;
probe -= hash2;
if (probe < 0)
probe += Tabsize;
}
if (Table[probe] == 0) {
fprintf(stderr, "%s: impossible hash error for %s\n",
ProgName, Table[i]->n_name);
badmagic(1);
}
total += count;
slots++;
if (count > longest)
longest = count;
if (count >= nslots)
count = 0;
collision[count]++;
}
for (i = 1; i < nslots; i++)
if (collision[i])
fprintf(stderr, "%d chains: %d (%ld%%)\n",
i, collision[i], (collision[i] * 100L)/ slots);
if (collision[0])
fprintf(stderr, "> %d chains: %d (%ld%%)\n",
nslots - 1, collision[0],
(collision[0] * 100L)/ slots);
fprintf(stderr, "%2.2f probes per access, longest chain: %d\n",
(double) total / slots, longest);
}
STATIC void
lowercase(s)
register char *s;
{
do {
if (isupper(*s))
*s -= 'A' - 'a'; /* assumes ASCII */
} while (*s++);
}
/*
* this might have to be recoded for performance if privates catch on
*/
STATIC node *
isprivate(name)
register char *name;
{
register node *n;
for (n = Private; n != 0; n = n->n_private)
if (strcmp(name, n->n_name) == 0)
return(n);
return(0);
}
fixprivate()
{
register node *n, *next;
register long i;
for (n = Private; n != 0; n = next) {
n->n_flag |= ISPRIVATE; /* overkill, but safe */
i = hash(n->n_name, 1);
if (Table[i] != 0) {
fprintf(stderr, "%s: impossible private node error on %s\n",
ProgName, n->n_name);
badmagic(1);
}
Table[i] = n;
n->n_tloc = i; /* essentially a back link to the table */
next = n->n_private;
n->n_private = 0; /* clear for later use */
}
Private = 0;
}
node *
addprivate(name)
register char *name;
{
register node *n;
if (Iflag)
lowercase(name);
if ((n = isprivate(name)) != 0)
return(n);
n = newnode();
n->n_name = strsave(name);
n->n_private = Private;
Private = n;
return(n);
}
SHAR_EOF
if test 6585 -ne "`wc -c < 'addnode.c'`"
then
echo shar: error transmitting "'addnode.c'" '(should have been 6585 characters)'
fi
fi
echo shar: extracting "'extern.c'" '(650 characters)'
if test -f 'extern.c'
then
echo shar: will not over-write existing file "'extern.c'"
else
cat << \SHAR_EOF > 'extern.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)extern.c 8.1 (down!honey) 86/01/19";
#endif lint
#include "def.h"
node *Home;
char *Cfile;
char **Ifiles;
char *ProgName;
int Vflag;
int Cflag;
int Iflag;
int Tflag;
int Lineno = 1;
char *Netchars = "!:@%"; /* sparse, but sufficient */
int Ncount;
int Lcount;
char *Graphout;
char *Linkout;
node **Table; /* hash table + priority queue */
long Tabsize; /* size of Table */
node *Private; /* list of private nodes in this file */
long Hashpart; /* used while mapping -- above is heap */
int Scanstate = NEWLINE; /* scanner (yylex) state */
SHAR_EOF
if test 650 -ne "`wc -c < 'extern.c'`"
then
echo shar: error transmitting "'extern.c'" '(should have been 650 characters)'
fi
fi
echo shar: extracting "'local.c'" '(1426 characters)'
if test -f 'local.c'
then
echo shar: will not over-write existing file "'local.c'"
else
cat << \SHAR_EOF > 'local.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)local.c 8.1 (down!honey) 86/01/19";
#endif lint
#include <stdio.h>
#include "config.h"
#ifdef UNAME
#include <sys/utsname.h>
char *
local()
{
static struct utsname utsname;
uname(&utsname);
return(utsname.nodename);
}
#else !UNAME
char *
local()
{
static char lname[64];
void gethostname();
gethostname(lname, sizeof(lname));
return(lname);
}
#ifndef GETHOSTNAME
static void
gethostname(name, len)
char *name;
{
FILE *whoami, *fopen(), *popen();
char *ptr, *index();
*name = '\0';
/* try /etc/whoami */
if ((whoami = fopen("/etc/whoami", "r")) != 0) {
(void) fgets(name, len, whoami);
(void) fclose(whoami);
if ((ptr = index(name, '\n')) != 0)
*ptr = '\0';
}
if (*name)
return;
/* try /usr/include/whoami.h */
if ((whoami = fopen("/usr/include/whoami.h", "r")) != 0) {
while (!feof(whoami)) {
char buf[100];
if (fgets(buf, 100, whoami) == 0)
break;
if (sscanf(buf, "#define sysname \"%[^\"]\"", name))
break;
}
(void) fclose(whoami);
if (*name)
return;
}
/* ask uucp */
if ((whoami = popen("uuname -l", "r")) != 0) {
(void) fgets(name, len, whoami);
(void) pclose(whoami);
if ((ptr = index(name, '\n')) != 0)
*ptr = '\0';
}
if (*name)
return;
/* aw hell, i give up! is this a real unix? */
return;
}
#endif GETHOSTNAME
#endif UNAME
SHAR_EOF
if test 1426 -ne "`wc -c < 'local.c'`"
then
echo shar: error transmitting "'local.c'" '(should have been 1426 characters)'
fi
fi
echo shar: extracting "'main.c'" '(2362 characters)'
if test -f 'main.c'
then
echo shar: will not over-write existing file "'main.c'"
else
cat << \SHAR_EOF > 'main.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)main.c 8.1 (down!honey) 86/01/19";
#endif
#define MAIN /* for sccsid in header files */
#include "def.h"
#define USAGE "usage: %s [-vci] [-l localname] [-d deadlink] [-t tracelink] [-g file] [-s file]\n"
main(argc, argv)
int argc;
char *argv[];
{
char *locname = 0;
int c, errflg = 0;
ProgName = argv[0];
(void) allocation(); /* initialize data space monitoring */
Cfile = "[deadlinks]"; /* for tracing dead links */
while ((c = getopt(argc, argv, "cd:g:il:s:t:v")) != EOF)
switch(c) {
case 'c': /* print cost info */
Cflag++;
break;
case 'd': /* dead host or link */
deadlink(optarg);
break;
case 'g': /* graph output file */
Graphout = optarg;
break;
case 'i': /* ignore case */
Iflag++;
break;
case 'l': /* local name */
locname = optarg;
break;
case 's': /* show shortest path tree */
Linkout = optarg;
break;
case 't': /* trace this link */
if (tracelink(optarg) < 0) {
fprintf(stderr, "%s: can trace only %d links\n", ProgName, NTRACE);
exit(1);
}
Tflag = 1;
break;
case 'v': /* verbose stderr, mixed blessing */
Vflag++;
break;
default:
errflg++;
}
if (errflg) {
fprintf(stderr, USAGE, ProgName);
exit(1);
}
argv += optind; /* kludge for yywrap() */
if (*argv) {
Ifiles = argv;
freopen("/dev/null", "r", stdin);
}
if (!locname)
locname = local();
if (*locname == 0) {
locname = "lostinspace";
fprintf(stderr, "%s: using \"%s\" for local name\n",
ProgName, locname);
}
Home = addnode(locname); /* add home node */
Home->n_cost = 0; /* doesn't cost to get here */
yyparse(); /* read in link info */
if (Vflag > 1)
hashanalyze();
vprintf(stderr, "%d vertices, %d edges\n", Ncount, Lcount);
vprintf(stderr, "allocation is %ldk after parsing\n", allocation());
Cfile = "[backlinks]"; /* for tracing back links */
Lineno = 0;
mapit(); /* compute shortest path tree */
vprintf(stderr, "allocation is %ldk after mapping\n", allocation());
printit(); /* traverse tree and print paths */
vprintf(stderr, "allocation is %ldk after printing\n", allocation());
exit(0);
}
badmagic(n)
{
if (n) {
fprintf(stderr, "%s: cannot recover!\n", ProgName);
#ifdef DEBUG
abort();
#else
exit(n);
#endif
}
}
SHAR_EOF
if test 2362 -ne "`wc -c < 'main.c'`"
then
echo shar: error transmitting "'main.c'" '(should have been 2362 characters)'
fi
fi
echo shar: extracting "'makedb.c'" '(2348 characters)'
if test -f 'makedb.c'
then
echo shar: will not over-write existing file "'makedb.c'"
else
cat << \SHAR_EOF > 'makedb.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)makedb.c 8.1 (down!honey) 86/01/19";
#endif lint
#include <stdio.h>
#include "config.h"
typedef struct {
char *dptr;
int dsize;
} datum;
char *Ofile = ALIASDB, *ProgName;
#define USAGE "%s [-o dbmname] [-a] [file ...]"
main(argc, argv)
char *argv[];
{ char *ofptr;
int c, append = 0;
extern int optind;
extern char *optarg;
ProgName = argv[0];
while ((c = getopt(argc, argv, "o:av")) != EOF)
switch(c) {
case 'o': /* dbm output file */
Ofile = optarg;
break;
case 'a': /* append mode */
append++;
break;
default:
fprintf(stderr, USAGE, ProgName);
exit(1);
break;
}
if ((ofptr = rindex(Ofile, '/')) != 0)
ofptr++;
else
ofptr = Ofile;
if (strlen(ofptr) > 10) {
ofptr[10] = 0;
fprintf(stderr, "%s: using %s for dbm output\n", ProgName, Ofile);
}
if (append == 0 && dbfile(Ofile) != 0) {
perror_(Ofile);
exit(1);
}
if (dbminit(Ofile) < 0) {
perror_(Ofile);
exit(1);
}
if (optind == argc)
makedb((char *) 0);
else for ( ; optind < argc; optind++)
makedb(argv[optind]);
exit(0);
}
dbfile(dbf)
char *dbf;
{
return (dbcreat(dbf, "dir") != 0 || dbcreat(dbf, "pag") != 0);
}
dbcreat(dbf, suffix)
char *dbf, *suffix;
{ char buf[BUFSIZ];
int fd;
(void) sprintf(buf, "%s.%s", dbf, suffix);
if ((fd = creat(buf, 0666)) < 0)
return(-1);
(void) close(fd);
return(0);
}
makedb(ifile)
char *ifile;
{ char line[BUFSIZ];
datum key, val;
if (ifile && (freopen(ifile, "r", stdin) == NULL)) {
perror_(ifile);
return;
}
/*
* keys and values are 0 terminated. this wastes time and (disk) space,
* but does lend simplicity and backwards compatibility.
*/
key.dptr = line;
while (fgets(line, sizeof(line), stdin) != NULL) {
char *op, *end;
end = line + strlen(line);
end[-1] = 0; /* kill newline, stuff null terminator */
op = index(line, '\t');
if (op != 0) {
*op++ = 0;
key.dsize = op - line; /* 0 terminated */
val.dptr = op;
val.dsize = end - op; /* 0 terminated */
} else {
key.dsize = end - line; /* 0 terminated */
val.dptr = "\0"; /* why must i do this? */
val.dsize = 1;
}
if (store(key, val) < 0)
perror_(Ofile);
}
}
perror_(str)
char *str;
{
fprintf(stderr, "%s: ", ProgName);
perror(str);
}
SHAR_EOF
if test 2348 -ne "`wc -c < 'makedb.c'`"
then
echo shar: error transmitting "'makedb.c'" '(should have been 2348 characters)'
fi
fi
echo shar: extracting "'mapaux.c'" '(5168 characters)'
if test -f 'mapaux.c'
then
echo shar: will not over-write existing file "'mapaux.c'"
else
cat << \SHAR_EOF > 'mapaux.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)mapaux.c 8.1 (down!honey) 86/01/19";
#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 of going through a gatewayed not or not,
* choose the latter, placating the FCC or whatever.
*/
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);
}
SHAR_EOF
if test 5168 -ne "`wc -c < 'mapaux.c'`"
then
echo shar: error transmitting "'mapaux.c'" '(should have been 5168 characters)'
fi
fi
echo shar: extracting "'mapit.c'" '(10469 characters)'
if test -f 'mapit.c'
then
echo shar: will not over-write existing file "'mapit.c'"
else
cat << \SHAR_EOF > 'mapit.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)mapit.c 8.1 (down!honey) 86/01/19";
#endif
#include "def.h"
/* privates */
extern void reheap(), insert(), heapswap();
extern link *min_node(), *rmlink();
extern Cost costof();
static long Nheap;
static long Heaphighwater;
static link **Heap;
/* transform the graph to a shortest-path tree by marking tree edges */
mapit()
{
register node *n, *next;
register link *l;
link *lprev, *lnext;
Cost cost;
/*
* re-use the hash table space for the heap.
*/
Heap = (link **) Table;
pack(); /* remove holes in the Table */
if (Linkout && *Linkout) /* dump cheapest links */
showlinks();
if (Graphout && *Graphout) /* dump the edge list */
dumpgraph();
/* invent and insert a link for Home to get things started */
l = newlink();
l->l_to = Home;
(void) dehash(Home);
insert(l);
/* main mapping loop */
remap:
Heaphighwater = Nheap;
while ((l = min_node()) != 0) {
l->l_flag |= LTREE;
n = l->l_to;
n->n_flag |= MAPPED;
/* add children to heap */
lprev = 0;
for (l = n->n_link; l != 0; l = lnext) {
next = l->l_to; /* neighboring node */
if (next->n_flag & MAPPED) {
lnext = rmlink(l, lprev, n);
continue;
}
cost = costof(n, l);
if (skiplink(l, n, cost)) {
lnext = rmlink(l, lprev, n);
continue;
}
/*
* put this link in the heap, in a place where it may
* percolate up, but not down. if new, or if cost is
* being increased, move to end. otherwise, cost is
* same or less, so leave it where it is. unfortunately,
* freeing a link already in the heap is too costly at
* this point.
*
* TODO: avoid heaping aliases and network members.
*/
if (dehash(next) == 0) /* first time in heap */
insert(l); /* insert at end */
else {
/* replace heaped link by this one */
if (cost > next->n_cost) { /* gateway */
/* move old link to end of heap */
heapswap((long) (next->n_tloc), Nheap);
next->n_tloc = Nheap;
}
Heap[next->n_tloc] = l;
}
next->n_cost = cost;
next->n_parent = n;
reheap(l); /* restore heap property */
/*
* note whether we got here via a gatewayed net.
* domains are presumed to require gateways.
* aliases inherit parent's gateway status.
*/
next->n_flag &= ~GATEWAYIN;
if (l->l_flag & LALIAS)
next->n_flag |= (n->n_flag & GATEWAYIN);
else if (GATEWAYED(n))
next->n_flag |= GATEWAYIN;
lprev = l; /* this link's a keeper */
lnext = l->l_next;
}
}
vprintf(stderr, "heap high water mark was %d\n", Heaphighwater);
/* sanity check on implementation */
if (Nheap != 0) {
fprintf(stderr, "%s: null entry found in heap\n", ProgName);
badmagic(1);
}
if (Hashpart < Tabsize) {
/*
* add back links from unreachable hosts to reachable
* neighbors, then remap. asymptotically, this is
* quadratic. in practice, this is done exactly once.
*/
backlinks();
if (Nheap)
goto remap;
}
if (Hashpart < Tabsize) {
fputs("You can't get there from here:\n", stderr);
for ( ; Hashpart < Tabsize; Hashpart++) {
fprintf(stderr, "\t%s", Table[Hashpart]->n_name);
if (Table[Hashpart]->n_flag & (ISPRIVATE|COLLISION))
fputs(" (private)", stderr);
putc('\n', stderr);
}
}
}
/*
* can this link be ignored? if yes, return 1, o.w. 0.
* a link can be skipped if it is not in the shortest path tree.
*/
STATIC int
skiplink(l, parent, cost)
link *l; /* new link to this node */
node *parent; /* new parent of this node */
Cost cost; /* new cost to this node */
{
node *n; /* this node */
link *lheap; /* existing link to this node */
n = l->l_to;
/* first time we've reached this node? */
if (n->n_tloc >= Hashpart)
return(0);
lheap = Heap[n->n_tloc];
/* examine links to nets that require gateways */
if (GATEWAYED(n)) {
/* if exactly one is a gateway, use it */
if ((lheap->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY))
return(1); /* old is gateway */
if (!(lheap->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY))
return(0); /* new is gateway */
/* no gateway or both gateways; resolve in standard way ... */
}
/* examine dup link (sanity check) */
if (n->n_parent == parent && ((lheap->l_flag & LDEAD) || (l->l_flag & LDEAD))) {
fprintf(stderr, "%s: dup dead link not eliminated: %s -> %s\n",
ProgName, parent->n_name, n->n_name);
badmagic(1);
}
/* examine cost */
if (cost < n->n_cost)
return(0);
if (cost > n->n_cost)
return(1);
/* all other things being equal, consult the oracle */
return(tiebreaker(n, parent));
}
STATIC Cost
costof(prev, l)
register node *prev;
register link *l;
{
register node *next;
register Cost cost;
next = l->l_to;
if (l->l_flag & LALIAS) {
/* copy left/right bits */
next->n_flag &= ~(HASLEFT|HASRIGHT);
next->n_flag |= (prev->n_flag & (HASLEFT|HASRIGHT));
return(prev->n_cost); /* by definition */
}
cost = prev->n_cost + l->l_cost; /* basic cost */
/*
* heuristics:
* charge for a dead link.
* charge for getting out of a dead host.
* charge for getting into a gatewayed net (except at a gateway).
* discourage mixing of left and right syntax when next is a host.
* charge for leaving a gatewayed net.
*
* life was simpler when pathalias computed true shortest paths.
*/
if (l->l_flag & LDEAD) /* dead link */
cost += INF/2;
if (DEADHOST(prev)) /* dead host */
cost += INF/2;
if (GATEWAYED(next) && !(l->l_flag & LGATEWAY)) /* not gateway */
cost += INF/2;
if (!ISANET(next)) {
/* charge for mixed syntax here */
if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
|| (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
cost += DEFCOST;
}
/*
* if reached by a gatewayed net, discourage further links.
* this has some relevance to common carriers and the FCC ...
* the penalty inheres to hosts, not aliases, nets, or domains.
*/
if ((prev->n_flag & GATEWAYIN) && !ISADOMAIN(prev) && !(prev->n_flag & NNET))
cost += INF/2; /* heavyweight, but appropriate */
/* set left/right bits */
next->n_flag &= ~(HASLEFT|HASRIGHT);
if (NETDIR(l) == LLEFT || (prev->n_flag & HASLEFT))
next->n_flag |= HASLEFT;
if (NETDIR(l) == LRIGHT || (prev->n_flag & HASRIGHT))
next->n_flag |= HASRIGHT;
return(cost);
}
STATIC link *
rmlink(l, lprev, n)
link *l, *lprev;
node *n;
{
link *lnext;
lnext = l->l_next;
if (lprev)
lprev->l_next = l->l_next;
else
n->n_link = l->l_next;
free((char *) l);
return(lnext);
}
/*
* binary heap implementation of priority queue.
* TODO: make the heap smaller by giving inserting a placeholder
* for net members when the net is extracted. this requires storing the
* cost of a net in the net node itself -- yuck. is it worth it?
*/
STATIC void
insert(l)
link *l;
{
register node *n;
n = l->l_to;
Heap[n->n_tloc] = 0;
if (Heap[Nheap+1] != 0) {
fprintf(stderr, "%s: heap error in insert\n", ProgName);
badmagic(1);
}
if (Nheap++ == 0) {
Heap[1] = l;
n->n_tloc = 1;
return;
}
if (Vflag && Nheap > Heaphighwater)
Heaphighwater = Nheap; /* diagnostics */
/* insert at the end. caller must reheap(). */
Heap[Nheap] = l;
n->n_tloc = Nheap;
}
/*
* replace existing link in heap by this one, then
* "percolate" up the heap by exchanging with the parent
*/
STATIC void
reheap(l)
link *l;
{
register long loc, parent;
register Cost cost;
register node *n, *np;
n = l->l_to;
cost = n->n_cost;
for (loc = n->n_tloc; loc > 1; loc = parent) {
parent = loc / 2;
/* sanity check on implementation */
if (Heap[parent] == 0) {
fprintf(stderr, "%s: heap error in insert\n", ProgName);
badmagic(1);
}
np = Heap[parent]->l_to;
if (cost > np->n_cost)
return;
/* move nets below hosts for output stability */
if (cost == np->n_cost && ((n->n_flag & NNET) || !(np->n_flag & NNET)))
return;
heapswap(loc, parent);
}
}
/* extract min (== Heap[1]) from heap */
STATIC link *
min_node()
{
link *rval;
register link **regheap;
register long i, child;
if (Nheap == 0)
return(0);
regheap = Heap; /* in register -- heavily used */
rval = regheap[1]; /* return this one */
/* move last entry into root, percolate down */
regheap[1] = regheap[Nheap];
regheap[1]->l_to->n_tloc = 1;
regheap[Nheap] = 0;
if (--Nheap == 0)
return(rval);
i = 1;
for (;;) {
/* swap with smaller child down the tree */
child = i * 2; /* lhs child is 2i, rhs is 2i+1. */
if (child >= Nheap)
return(rval);
/* use rhs child if smaller than lhs child */
if (regheap[child]->l_to->n_cost > regheap[child+1]->l_to->n_cost
|| (regheap[child]->l_to->n_cost == regheap[child+1]->l_to->n_cost
&& !ISANET(regheap[child+1]->l_to)))
child++;
if (regheap[i]->l_to->n_cost < regheap[child]->l_to->n_cost)
return(rval);
/* move nets below hosts for output stability */
if (regheap[i]->l_to->n_cost == regheap[child]->l_to->n_cost
&& (!ISANET(regheap[i]->l_to) || ISANET(regheap[child]->l_to)))
return(rval);
heapswap(i, child);
i = child;
}
/*NOTREACHED*/
}
/* exchange Heap[i] and Heap[j] pointers */
STATIC void
heapswap(i, j)
long i, j;
{
register link *temp, **regheap;
regheap = Heap; /* heavily used -- put in register */
temp = regheap[i];
regheap[i] = regheap[j];
regheap[j] = temp;
regheap[j]->l_to->n_tloc = j;
regheap[i]->l_to->n_tloc = i;
}
/* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
dehash(n)
register node *n;
{
if (n->n_tloc < Hashpart)
return(1);
/* swap with entry in Table[Hashpart] */
Table[Hashpart]->n_tloc = n->n_tloc;
Table[n->n_tloc] = Table[Hashpart];
Table[Hashpart] = n;
n->n_tloc = Hashpart++;
return(0);
}
backlinks()
{
link *l;
node *n, *parent, *nomap;
long i;
for (i = Hashpart; i < Tabsize; i++) {
nomap = Table[i];
parent = 0;
for (l = nomap->n_link; l; l = l->l_next) {
n = l->l_to;
if (!(n->n_flag & MAPPED))
continue;
if (parent == 0) {
parent = n;
continue;
}
if (n->n_cost > parent->n_cost)
continue;
if (n->n_cost == parent->n_cost) {
nomap->n_parent = parent;
if (tiebreaker(nomap, n))
continue;
}
parent = n;
}
if (parent == 0)
continue;
(void) dehash(nomap);
l = addlink(parent, nomap, INF, DEFNET, DEFDIR);
nomap->n_parent = parent;
nomap->n_cost = costof(parent, l);
insert(l);
reheap(l);
}
vprintf(stderr, "%d backlinks\n", Nheap);
}
SHAR_EOF
if test 10469 -ne "`wc -c < 'mapit.c'`"
then
echo shar: error transmitting "'mapit.c'" '(should have been 10469 characters)'
fi
fi
echo shar: extracting "'mem.c'" '(3448 characters)'
if test -f 'mem.c'
then
echo shar: will not over-write existing file "'mem.c'"
else
cat << \SHAR_EOF > 'mem.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)mem.c 8.1 (down!honey) 86/01/19";
#endif
#include "def.h"
/* imported */
extern char *sbrk();
link *
newlink()
{
link *rval;
if ((rval = (link * ) calloc(1, sizeof(link))) == 0)
nomem();
return(rval);
}
node *
newnode()
{
node *rval;
if ((rval = (node * ) calloc(1, sizeof(node))) == 0)
nomem();
Ncount++;
return(rval);
}
char *
strsave(s)
char *s;
{
char *r;
if ((r = malloc((unsigned int) strlen(s) + 1)) == 0)
nomem();
(void) strcpy(r, s);
return(r);
}
#ifndef strclear
void
strclear(dst, len)
register char *dst;
register int len;
{
while (--len >= 0)
*dst++ = 0;
}
#endif /*strclear*/
node **
newtable(size)
long size;
{
node **rval;
if ((rval = (node **) calloc(1, (unsigned int) (size * sizeof(*rval)))) == 0)
nomem();
return(rval);
}
freetable(t, size)
node **t;
long size;
{
#ifdef MYMALLOC
addtoheap((char *) t, (long) (size * sizeof(*t)));
#else
free((char *) t);
#endif
}
nomem()
{
fprintf(stderr, "%s: Out of memory (%ldk allocated)\n",
ProgName, allocation());
badmagic(1);
}
/* data space allocation -- main sets End very early */
allocation()
{
static char *dataspace;
if (dataspace == 0) { /* first time */
dataspace = sbrk(0); /* &end? */
return(0);
}
return((sbrk(0) - dataspace)/1024);
}
#ifdef MYMALLOC
/* use c library malloc/calloc here, and here only */
#undef malloc
#undef calloc
extern char *malloc(), *calloc();
/* allocate in MBUFSIZ chunks. 4k works ok (less 16 for malloc quirks). */
#define MBUFSIZ (4 * 1024 - 16)
/*
* mess with ALIGN at your peril. longword (== 0 mod 4)
* alignment seems to work everywhere.
*/
#define ALIGN 2
typedef struct heap heap;
struct heap {
heap *h_next;
long h_size;
};
static heap *Mheap; /* not to be confused with a priority queue */
addtoheap(p, size)
char *p;
long size;
{
int adjustment;
heap *pheap;
/* p is aligned, but it doesn't hurt to check */
adjustment = align(p);
p += adjustment;
size -= adjustment;
if (size < 1024)
return; /* can't happen */
pheap = (heap *) p; /* pheap is shorthand */
pheap->h_next = Mheap;
pheap->h_size = size;
Mheap = pheap;
}
/*
* buffered malloc()
* returns space initialized to 0. calloc isn't used, since
* strclear can be faster.
*
* free is ignored, except for very large objects,
* which are returned to the heap with addtoheap().
*/
char *
mymalloc(n)
register unsigned int n;
{
static long size; /* how much do we have on hand? */
static char *mstash; /* where is it? (kept aligned) */
register char *rval;
n += align((char *) n); /* keep everything aligned */
if (n >= 1024) { /* from hash table */
rval = malloc(n); /* aligned */
strclear(rval, n);
return(rval);
}
if (n > size) {
/* look in the heap (already aligned) */
if (Mheap) {
mstash = (char *) Mheap;
size = Mheap->h_size;
Mheap = Mheap->h_next;
} else {
mstash = malloc(MBUFSIZ); /* aligned */
if (mstash == 0) {
size = 0;
return(0);
}
size = MBUFSIZ;
}
strclear(mstash, size);
}
rval = mstash;
mstash += n;
size -= n;
return(rval);
}
/* what's the (mis-)alignment of n? return the complement of (n mod 2^ALIGN) */
align(n)
char *n;
{
int abits; /* misalignment bits in n */
abits = (int) n & ~(0xff << ALIGN) & 0xff;
if (abits == 0)
return(0);
return((1 << ALIGN) - abits);
}
#endif /*MYMALLOC*/
SHAR_EOF
if test 3448 -ne "`wc -c < 'mem.c'`"
then
echo shar: error transmitting "'mem.c'" '(should have been 3448 characters)'
fi
fi
echo shar: extracting "'printit.c'" '(3713 characters)'
if test -f 'printit.c'
then
echo shar: will not over-write existing file "'printit.c'"
else
cat << \SHAR_EOF > 'printit.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)printit.c 8.1 (down!honey) 86/01/19";
#endif
#include "def.h"
/* use lots of char bufs -- profiling indicates this costs about 5 kbytes */
/* in practice, even the longest paths are < 100 bytes */
#define PSIZE 512
printit()
{ link *l;
char pbuf[PSIZE];
/* print home */
if (Cflag)
printf("%ld\t", (long) Home->n_cost);
printf("%s\t%%s\n", Home->n_name);
strcpy(pbuf, "%s");
for (l = Home->n_link; l; l = l->l_next) {
if (l->l_flag & LTREE) {
preorder(l, pbuf);
strcpy(pbuf, "%s");
}
}
}
/* preorder traversal of shortest path tree */
preorder(l, ppath)
register link *l;
char *ppath;
{
register node *n;
char npath[PSIZE];
setpath(l, ppath, npath);
n = l->l_to;
if ((n->n_flag & NNET) || ISADOMAIN(n))
printnet(n, npath, n->n_cost);
else
printhost(n, npath, n->n_cost);
for (l = n->n_link; l; l = l->l_next)
if (l->l_flag & LTREE)
preorder(l, npath);
}
setpath(l, ppath, npath)
link *l;
register char *ppath, *npath;
{
register node *next;
char netchar;
extern char *hostpath();
next = l->l_to;
/*
* for magic @-% conversion.
* assume that gateways to domains want no @'s
*/
if (next->n_parent->n_flag & ATSIGN || ISADOMAIN(next))
next->n_flag |= ATSIGN;
/* special handling for aliases , domains, and nets */
if ((l->l_flag & LALIAS) || (next->n_flag & NNET) || ISADOMAIN(next)) {
strcpy(npath, ppath);
return;
}
netchar = NETCHAR(l);
if (netchar == '@')
if (next->n_flag & ATSIGN)
netchar = '%'; /* shazam? shaman? */
else
next->n_flag |= ATSIGN;
/* remainder should be a sprintf -- foo on '%' as an operator */
for ( ; *npath = *ppath; ppath++) {
if (*ppath == '%') {
switch(ppath[1]) {
case 's':
ppath++;
npath = hostpath(npath, l, netchar);
break;
case '%':
*++npath = *++ppath;
npath++;
break;
default:
fprintf(stderr, "%s: %%%c found in setpath\n",
ProgName, ppath[1]);
badmagic(1);
break;
}
} else
npath++;
}
}
char *
hostpath(path, l, netchar)
register char *path;
register link *l;
char netchar;
{
register node *prev;
prev = l->l_to->n_parent;
if (NETDIR(l) == LLEFT) {
/* host!user */
strcpy(path, l->l_to->n_name);
path += strlen(path);
while (ISADOMAIN(prev)) {
strcpy(path, prev->n_name);
path += strlen(path);
prev = prev->n_parent;
}
*path++ = netchar;
if (netchar == '%')
*path++ = '%';
*path++ = '%';
*path++ = 's';
} else {
/* %s@host */
*path++ = '%';
*path++ = 's';
*path++ = netchar;
if (netchar == '%')
*path++ = '%';
strcpy(path, l->l_to->n_name);
path += strlen(path);
while (ISADOMAIN(prev)) {
strcpy(path, prev->n_name);
path += strlen(path);
prev = prev->n_parent;
}
}
return(path);
}
STATIC
printhost(n, path, cost)
node *n;
char *path;
Cost cost;
{
/* for collisions, print the domained name only */
if ((n->n_flag & (ISPRIVATE|COLLISION)) == 0) {
if (Cflag)
printf("%ld\t", (long) cost);
fputs(n->n_name, stdout);
putchar('\t');
puts(path);
} else if (ISADOMAIN(n->n_parent))
printdomain(n, path, cost); /* print fully qualified name */
}
STATIC
printnet(n, path, cost)
node *n;
char *path;
Cost cost;
{
/* print gateways */
if (!ISADOMAIN(n))
return;
/* if it's private, print only if qualifed */
if ((n->n_flag & (ISPRIVATE|COLLISION)) && !ISADOMAIN(n->n_parent))
return;
printdomain(n, path, cost);
}
STATIC
printdomain(n, path, cost)
node *n;
char *path;
Cost cost;
{
if (Cflag)
printf("%ld\t", (long) cost);
do {
fputs(n->n_name, stdout);
n = n->n_parent;
} while (ISADOMAIN(n));
putchar('\t');
puts(path);
}
SHAR_EOF
if test 3713 -ne "`wc -c < 'printit.c'`"
then
echo shar: error transmitting "'printit.c'" '(should have been 3713 characters)'
fi
fi
echo shar: extracting "'parse.y'" '(7502 characters)'
if test -f 'parse.y'
then
echo shar: will not over-write existing file "'parse.y'"
else
cat << \SHAR_EOF > 'parse.y'
%{
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)parse.y 8.1 (down!honey) 86/01/19";
#endif lint
#include "def.h"
/* I thank Paul Haahr and Greg Noel for helping to clean this up. */
%}
%union {
node *y_node;
Cost y_cost;
char y_net;
char *y_name;
struct {
node *ys_node;
Cost ys_cost;
char ys_net;
char ys_dir;
} y_s;
}
%type <y_s> site
%type <y_node> links aliases plist network nlist host Psite Site
%type <y_cost> cost cexpr
%token <y_name> SITE HOST
%token <y_cost> COST
%token <y_net> NET
%token NL PRIVATE
%left '+' '-'
%left '*' '/'
%%
map : /* empty */
| map NL
| map links NL
| map aliases NL
| map network NL
| map private NL
| error NL
;
links : host site cost {
if (GATEWAYED($2.ys_node))
addgateway($1, $2.ys_node, $3, $2.ys_net, $2.ys_dir);
else
addlink($1, $2.ys_node, $3, $2.ys_net, $2.ys_dir);
}
| links ',' site cost {
if (GATEWAYED($3.ys_node))
addgateway($1, $3.ys_node, $4, $3.ys_net, $3.ys_dir);
else
addlink($1, $3.ys_node, $4, $3.ys_net, $3.ys_dir);
}
| links ',' /* permit this benign error */
;
aliases : host '=' Site {alias($1, $3);}
| aliases ',' Site {alias($1, $3);}
| aliases ',' /* permit this benign error */
;
network : host '=' '{' nlist '}' cost {fixnet($1, $4, $6, DEFNET, DEFDIR);}
| host '=' NET '{' nlist '}' cost {fixnet($1, $5, $7, $3, LRIGHT);}
| host '=' '{' nlist '}' NET cost {fixnet($1, $4, $7, $6, LLEFT);}
;
private : PRIVATE '{' plist '}' ;
host : HOST {$$ = addnode($1);}
| PRIVATE {$$ = addnode("private");}
;
Site : SITE {$$ = addnode($1);} ;
site : Site {
$$.ys_node = $1;
$$.ys_net = DEFNET;
$$.ys_dir = DEFDIR;
}
| NET Site {
$$.ys_node = $2;
$$.ys_net = $1;
$$.ys_dir = LRIGHT;
}
| Site NET {
$$.ys_node = $1;
$$.ys_net = $2;
$$.ys_dir = LLEFT;
}
;
Psite : SITE {$$ = addprivate($1);} ;
plist : Psite {$1->n_flag |= ISPRIVATE;}
| plist ',' Psite {$3->n_flag |= ISPRIVATE;}
| plist ',' /* permit this benign error */
;
nlist : Site
| nlist ',' Site {
if ($3->n_net == 0) {
$3->n_net = $1;
$$ = $3;
}
}
| nlist ',' /* permit this benign error */
;
cost : {$$ = DEFCOST; /* empty -- cost is always optional */}
| '(' {Scanstate = COSTING;} cexpr {Scanstate = OTHER;} ')'
{$$ = $3;}
;
cexpr : COST
| '(' cexpr ')' {$$ = $2;}
| cexpr '+' cexpr {$$ = $1 + $3;}
| cexpr '-' cexpr {$$ = $1 - $3;}
| cexpr '*' cexpr {$$ = $1 * $3;}
| cexpr '/' cexpr {
if ($3 == 0)
yyerror("zero divisor\n");
else
$$ = $1 / $3;
}
;
%%
yyerror(s)
char *s;
{
/* a concession to bsd error(1) */
if (Cfile)
fprintf(stderr, "\"%s\", ", Cfile);
else
fprintf(stderr, "%s: ", ProgName);
fprintf(stderr, "line %d: %s\n", Lineno, s);
}
/*
* patch in the costs of getting on/off the network.
*
* for each network member on netlist, add links:
* network -> member cost = 0;
* member -> network cost = parameter.
*
* if network and member both require gateways, assume network
* is a gateway to member (but not v.v., to avoid such travesties
* as topaz!seismo.css.gov.edu.rutgers).
*
* note that members can have varying costs to a network, by suitable
* multiple declarations. this is a feechur, albeit a useless one.
*/
fixnet(network, nlist, cost, netchar, netdir)
register node *network;
node *nlist;
Cost cost;
char netchar, netdir;
{
register node *member, *nextnet;
link *l;
network->n_flag |= NNET;
/* now insert the links */
for (member = nlist ; member; member = nextnet) {
/* network -> member, cost is 0 */
if (GATEWAYED(network) && GATEWAYED(member))
(void) addgateway(network, member, (Cost) 0, netchar, netdir);
else
(void) addlink(network, member, (Cost) 0, netchar, netdir);
/* member -> network, cost is parameter */
(void) addlink(member, network, cost, netchar, netdir);
nextnet = member->n_net;
member->n_net = 0; /* clear for later use */
}
}
/* scanner */
#define LBRACE '{'
#define RBRACE '}'
#define LPAREN '('
#define RPAREN ')'
#define QUOTE '"'
Cost isacost();
yylex()
{
register int c;
Cost cost;
char buf[BUFSIZ], errbuf[128];
tailrecursion:
if (feof(stdin) && yywrap())
return(EOF);
if ((c = getchar()) == EOF)
goto tailrecursion;
while (c == ' ' || c == '\t')
c = getchar();
if (c == '\n') {
Lineno++;
c = getchar();
if (c == ' ' || c == '\t')
goto tailrecursion;
ungetc(c, stdin);
Scanstate = NEWLINE;
return(NL);
}
if (c == '#') {
while ((c = getchar()) != '\n')
if (c == EOF)
goto tailrecursion;
ungetc(c, stdin);
goto tailrecursion;
}
ungetc(c, stdin);
switch(Scanstate) {
case COSTING:
if (isdigit(c)) {
cost = 0;
for (c = getchar(); isdigit(c); c = getchar())
cost = (cost * 10) + c - '0';
ungetc(c, stdin);
yylval.y_cost = cost;
return(COST);
}
if (getword(buf) == 0) {
if ((yylval.y_cost = isacost(buf)) == 0) {
sprintf(errbuf, "unknown cost (%s), using default", buf);
yyerror(errbuf);
yylval.y_cost = DEFCOST;
}
return(COST);
}
return(getchar()); /* can't be EOF */
case NEWLINE:
Scanstate = OTHER;
if (getword(buf) != 0)
return(getchar()); /* can't be EOF */
/* `private' (but not `"private"')? */
if (c == 'p' && strcmp(buf, "private") == 0)
return(PRIVATE);
yylval.y_name = buf;
return(HOST);
}
if (getword(buf) == 0) {
yylval.y_name = buf;
return(SITE);
}
c = getchar(); /* can't be EOF */
if (index(Netchars, c)) {
yylval.y_net = c;
return(NET);
}
return(c);
}
/*
* fill str with the next word in [0-9A-Za-z][-._0-9A-Za-z]+ or a quoted
* string that contains no newline. return -1 on failure or EOF, 0 o.w.
*/
getword(str)
register char *str;
{
register int c;
c = getchar();
if (c == QUOTE) {
for ( ; (*str = getchar()) != '"'; str++) {
if (*str == '\n') {
yyerror("newline in quoted string\n");
ungetc('\n', stdin);
return(-1);
}
}
*str = 0;
return(0);
}
/* host name must start with alphanumeric or `.' */
if (!isalnum(c) && c != '.') {
ungetc(c, stdin);
return(-1);
}
yymore:
do {
*str++ = c;
c = getchar();
} while (isalnum(c) || c == '.' || c == '_');
if (c == '-' && Scanstate != COSTING)
goto yymore;
ungetc(c, stdin);
*str = 0;
return(0);
}
static struct ctable {
char *cname;
Cost cval;
} ctable[] = {
/*
* this list is searched sequentially (with strcmps!).
* it is too long. (they are ordered by frequency of
* appearance in a "typical" dataset.)
*
* adding a 0 cost token breaks isacost(). don't do it.
*/
{"DEMAND", 300},
{"DAILY", 5000},
{"DIRECT", 200},
{"EVENING", 1800},
{"LOCAL", 25},
{"LOW", 5}, /* baud rate penalty */
{"HOURLY", 500},
{"POLLED", 5000},
{"DEDICATED", 95},
{"WEEKLY", 30000},
{"DEAD", INF/2},
{"HIGH", -5}, /* baud rate bonus */
/* the remainder are reviled */
{"ARPA", 100},
{"DIALED", 300},
{"A", 300},
{"B", 500},
{"C", 1800},
{"D", 5000},
{"E", 30000},
{"F", INF/2},
0
};
STATIC Cost
isacost(buf)
register char *buf;
{
register struct ctable *ct;
for (ct = ctable; ct->cname; ct++)
if (strcmp(buf, ct->cname) == 0)
return(ct->cval);
return((Cost) 0);
}
yywrap()
{
char errbuf[100];
fixprivate(); /* munge private host definitions */
if (Ifiles == 0)
return(1);
fclose(stdin);
while (*Ifiles) {
Lineno = 1;
if (fopen((Cfile = *Ifiles++), "r"))
return(0);
sprintf(errbuf, "%s: %s", ProgName, Cfile);
perror(errbuf);
}
return(1);
}
SHAR_EOF
if test 7502 -ne "`wc -c < 'parse.y'`"
then
echo shar: error transmitting "'parse.y'" '(should have been 7502 characters)'
fi
fi
exit 0
# End of shell archive