campbell@maynard.BSW.COM (Larry Campbell) (12/15/86)
#! /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:
# addlink.c
# addnode.c
# extern.c
# local.c
# main.c
# mapit.c
# mapaux.c
# mem.c
# putnode.c
# parse.y
# makedb.c
# This archive created: Sun Dec 14 23:58:29 1986
export PATH; PATH=/bin:/usr/bin:$PATH
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 long Trace[NTRACE];
static int Tracecount;
int
addlink(ofrom, oto, cost, netchar, netdir)
int ofrom;
register int oto;
Cost cost;
char netchar;
char netdir;
{
register link *l, *ltmp;
node *ntmp;
node *from;
int prev = 0;
/* if (Tflag)
ltrace(from, to, cost, netchar, netdir);
*/
/* maintain uniqueness for dead links (only) */
from = getnode(ofrom);
freenode(from);
for (l = getlink(from->n_link); l->l_offset && l->l_flag & LDEAD;
l = getlink(l->l_next)) {
if (oto == l->l_to) {
/* what the hell, use cheaper cost */
if (cost < l->l_cost) {
l->l_cost = cost;
netbits(l, netchar, netdir);
}
putlink(l);
return(l->l_offset);
}
prev = l->l_offset;
freelink(l);
}
freelink(l);
/* allocate and link in the new link struct */
l = newlink();
if (cost != INF) /* ignore back links */
Lcount++;
if (prev) {
ltmp = getlink(prev);
l->l_next = ltmp->l_next;
ltmp->l_next = l->l_offset;
putlink(ltmp);
} else {
ntmp = getnode(ofrom);
l->l_next = ntmp->n_link;
ntmp->n_link = l->l_offset;
putnode(ntmp);
}
l->l_to = oto;
l->l_cost = cost;
if (netchar == 0) {
netchar = DEFNET;
netdir = DEFDIR;
}
netbits(l, netchar, netdir);
putlink(l);
return(l->l_offset);
}
int
addgateway(ofrom, oto, cost, netchar, netdir)
int ofrom;
int oto;
Cost cost;
char netchar;
char netdir;
{
register link *l;
l = getlink(addlink(ofrom, oto, cost, netchar, netdir));
l->l_flag |= LGATEWAY;
putlink(l);
return(l->l_offset);
}
deadlink(s)
char *s;
{
char *t, c;
link *l;
node *n;
t = index(s, '!');
if (t) {
c = *t;
*t = 0;
l = getlink(addlink(addnode(s), addnode(t + 1), INF / 2, c,
DEFDIR));
l->l_flag |= LDEAD;
putlink(l);
} else
n = getnode(addnode(s));
n->n_flag |= NDEAD;
putnode(n);
}
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);
}
#ifdef FORGET_IT
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);
}
#endif
#ifdef FORGET_IT
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;
}
}
}
#endif
#ifdef FORGET_IT
/* 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);
}
#endif
#ifdef FORGET_IT
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;
}
}
}
#endif
SHAR_EOF
fi
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 int isprivate();
extern long hash();
extern nodecount, linkcount;
/*
* 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
*/
21499, 0
};
static int Tabindex = -1;
static int Collision; /* mark host name collisions in hash() */
int
addnode(name)
register char *name;
{
register i;
register node *n;
if (Iflag)
lowercase(name);
/* is it a private host? */
i = isprivate(name);
if (i)
return(i);
i = hash(name, 0);
if (Table[i])
return(Table[i]);
n = newnode();
if (strlen(name) >= MAXNAME) {
fprintf(stderr, "Name too long: %s\n", name);
badmagic(1);
}
strcpy(n->n_name, name);
Table[i] = n->n_offset;
n->n_tloc = i; /* essentially a back link to the table */
if (Collision)
n->n_flag |= COLLISION; /* name collision with private host */
putnode(n);
return(n->n_offset);
}
alias(n1, n2)
int n1, n2;
{
link *l;
extern int addlink();
l = getlink(addlink(n1, n2, (Cost) 0, DEFNET, DEFDIR));
l->l_flag |= LALIAS;
putlink(l);
l = getlink(addlink(n2, n1, (Cost) 0, DEFNET, DEFDIR));
l->l_flag |= LALIAS;
putlink(l);
/* 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 (Table[probe] != 0) {
n = getnode(Table[probe]);
if (strcmp(n->n_name, name) == 0) {
if (unique) {
n->n_flag |= COLLISION;
putnode(n);
}
else if (n->n_flag & ISPRIVATE) {
freenode(n);
Collision++;
}
else {
putnode(n);
break; /* this is it! */
}
}
else
freenode(n);
probe -= hash2;
if (probe < 0)
probe += Tabsize;
}
return(probe);
}
STATIC void
rehash()
{
register int *otable, *optr;
node *n;
register long probe;
#ifdef DEBUG
hashanalyze();
#endif
optr = Table + Tabsize - 1; /* ptr to last */
otable = Table;
Tabsize = Primes[++Tabindex];
if (Tabsize == 0) { /* need more prime numbers */
fprintf(stderr, "%s: > %d hosts\n", ProgName, Primes[Tabindex-1]);
badmagic(1);
}
Table = newtable(Tabsize);
do {
if (*optr == 0)
continue; /* empty slot in old table */
n = getnode(*optr);
probe = hash(n->n_name, n->n_flag & ISPRIVATE);
if (Table[probe] != 0) {
fprintf(stderr, "%s: rehash error\n", ProgName);
badmagic(1);
}
Table[probe] = *optr;
regetnode(n);
n->n_tloc = probe;
putnode(n);
} while (optr-- > otable);
freetable(otable);
}
hashanalyze()
{
#ifdef FORGET_IT
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);
#endif
}
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 int
isprivate(name)
register char *name;
{
register node *n;
for (n = getnode(Private); n->n_offset != 0;
n = getnode(n->n_private)) {
if (strcmp(name, n->n_name) == 0) {
freenode(n);
return(n->n_offset);
}
freenode(n);
}
freenode(n);
return(0);
}
fixprivate()
{
node *n, *next;
register int i;
for (n = getnode(Private); n->n_offset != 0; n = next) {
n->n_flag |= ISPRIVATE; /* overkill, but safe */
putnode(n);
n = getnode(n->n_offset);
i = hash(n->n_name, 1);
regetnode(n);
if (Table[i] != 0) {
fprintf(stderr, "%s: impossible private node error on %s\n",
ProgName, n->n_name);
badmagic(1);
}
Table[i] = n->n_offset;
n->n_tloc = i; /* essentially a back link to the table */
next = getnode(n->n_private);
n->n_private = 0; /* clear for later use */
putnode(n);
}
freenode(n);
Private = 0;
}
int
addprivate(name)
register char *name;
{
register node *n;
if (Iflag)
lowercase(name);
n = getnode(isprivate(name));
freenode(n);
if (n->n_offset != 0)
return(n->n_offset);
n = newnode();
if (strlen(name) >= MAXNAME) {
fprintf(stderr, "Name too long: %s\n", name);
badmagic(1);
}
strcpy(n->n_name, name);
n->n_private = Private;
Private = n->n_offset;
putnode(n);
return(n->n_offset);
}
SHAR_EOF
fi
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"
int Home;
char *Cfile;
char **Ifiles;
char *ProgName;
int fdnode, fdlink; /* File descriptors for temporary files */
int nodecount, linkcount;
int Vflag;
int Cflag;
int Iflag;
int Tflag;
int Lineno = 1;
char *Netchars = "!:@%"; /* sparse, but sufficient */
int Ncount;
int Lcount;
char *Graphout;
char *Linkout;
int *Table; /* hash table + priority queue */
long Tabsize; /* size of Table */
int Private; /* list of private nodes in this file */
long Hashpart; /* used while mapping -- above is heap */
int Scanstate = NEWLINE; /* scanner (yylex) state */
SHAR_EOF
fi
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
fi
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"
extern nodecount, linkcount;
main(argc, argv)
int argc;
char *argv[];
{
node *Homenode;
char *locname = 0;
int c, errflg = 0;
int pstat;
ProgName = argv[0];
(void) allocation(); /* initialize data space monitoring */
Cfile = "[deadlinks]"; /* for tracing dead links */
meminit();
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 */
Homenode = getnode(Home);
Homenode->n_cost = 0; /* doesn't cost to get here */
putnode(Homenode);
yyparse(); /* read in link info */
vprintf(stderr, "yyparse ends with %d, %d\n", nodecount, linkcount);
if (Vflag > 1)
hashanalyze();
vprintf(stderr, "%d vertices, %d edges\n", Ncount, Lcount);
vprintf(stderr, "allocation is %uk after parsing\n", allocation());
vprintf(stderr, "hashanalyze ends with %d, %d\n", nodecount,
linkcount);
Cfile = "[backlinks]"; /* for tracing back links */
Lineno = 0;
mapit(); /* compute shortest path tree */
vprintf(stderr, " mapit ends with %d, %d\n", nodecount, linkcount);
vprintf(stderr, "allocation is %uk after mapping\n", allocation());
/* traverse tree and print paths */
if (Cflag)
pstat = system(PRINTITC);
else
pstat = system(PRINTIT);
vprintf(stderr, "printit ends with status %d\n", pstat);
#ifndef DEBUG
unlink(NTEMPFILE);
unlink(LTEMPFILE);
#endif
exit(0);
}
SHAR_EOF
fi
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 int min_node(), rmlink();
extern Cost costof();
extern int nodecount, linkcount;
static int Nheap;
static long Heaphighwater;
static int *Heap;
/* transform the graph to a shortest-path tree by marking tree edges */
mapit()
{
register node *n, *next;
register link *l;
int olnext;
int ol;
int next_offset, olprev;
Cost cost;
/*
* re-use the hash table space for the heap.
*/
Heap = (int *) 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);
putlink(l);
insert(l->l_offset);
/* main mapping loop */
remap:
Heaphighwater = Nheap;
while ((ol = min_node()) != 0) {
l = tmpgetlink(ol);
l->l_flag |= LTREE;
n = getnode(l->l_to);
n->n_flag |= MAPPED;
putnode(n);
putlink(l);
n = tmpgetnode(l->l_to);
/* add children to heap */
olprev = 0;
for (l = tmpgetlink(n->n_link); l->l_offset != 0;
l = tmpgetlink(olnext)) {
next_offset = l->l_to;
next = getnode(l->l_to); /* neighboring node */
if (next->n_flag & MAPPED) {
olnext = rmlink(l->l_offset, olprev,
n->n_offset);
freenode(next);
continue;
}
freenode(next);
cost = costof(n->n_offset, l->l_offset);
if (skiplink(l->l_offset, n->n_offset, cost)) {
olnext = rmlink(l->l_offset, olprev,
n->n_offset);
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.
*/
next = getnode(next_offset);
if (dehash(next_offset) == 0) { /* first time in heap */
insert(l->l_offset); /* insert at end */
regetnode(next);
}
else {
regetnode(next);
/* replace heaped link by this one */
if (cost > next->n_cost) { /* gateway */
/* move old link to end of heap */
heapswap((int) next->n_tloc, Nheap);
regetnode(next);
next->n_tloc = Nheap;
}
Heap[next->n_tloc] = l->l_offset;
}
next->n_cost = cost;
next->n_parent = n->n_offset;
putnode(next);
reheap(l->l_offset); /* 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 = getnode(next_offset);
next->n_flag &= ~GATEWAYIN;
n = tmpgetnode(n->n_offset);
l = tmpgetlink(l->l_offset);
if (l->l_flag & LALIAS)
next->n_flag |= (n->n_flag & GATEWAYIN);
else if (GATEWAYED(n))
next->n_flag |= GATEWAYIN;
putnode(next);
olprev = l->l_offset; /* this link's a keeper */
olnext = 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",
tmpgetnode(Table[Hashpart])->n_name);
if (tmpgetnode(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(ol, oparent, cost)
int ol; /* new link to this node */
int oparent; /* new parent of this node */
Cost cost; /* new cost to this node */
{
link *l, *ltmp;
node *parent;
node *n; /* this node */
int lheap; /* existing link to this node */
l = getlink(ol);
n = getnode(l->l_to);
/* first time we've reached this node? */
if (n->n_tloc >= Hashpart) {
freelink(l);
freenode(n);
return(0);
}
lheap = Heap[n->n_tloc];
ltmp = getlink(lheap);
/* examine links to nets that require gateways */
if (GATEWAYED(n)) {
/* if exactly one is a gateway, use it */
if ((ltmp->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY)) {
freenode(n);
freelink(l);
freelink(ltmp);
return(1); /* old is gateway */
}
if (!(ltmp->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY)) {
freenode(n);
freelink(l);
freelink(ltmp);
return(0); /* new is gateway */
}
/* no gateway or both gateways; resolve in standard way ... */
}
/* examine dup link (sanity check) */
parent = getnode(oparent);
if (n->n_parent == oparent && ((ltmp->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);
}
freenode(parent);
freelink(ltmp);
/* examine cost */
if (cost < n->n_cost) {
freenode(n);
freelink(l);
return(0);
}
if (cost > n->n_cost) {
freenode(n);
freelink(l);
return(1);
}
/* all other things being equal, consult the oracle */
freelink(l);
freenode(n);
return(tiebreaker(n->n_offset, oparent));
}
STATIC Cost
costof(oprev, ol)
register int oprev;
register int ol;
{
link *l;
node *prev;
register node *next;
register Cost cost;
l = getlink(ol);
next = getnode(l->l_to);
prev = getnode(oprev);
if (l->l_flag & LALIAS) {
/* copy left/right bits */
next->n_flag &= ~(HASLEFT|HASRIGHT);
next->n_flag |= (prev->n_flag & (HASLEFT|HASRIGHT));
putnode(next);
freelink(l);
freenode(prev);
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;
putnode(next);
freenode(prev);
freelink(l);
return(cost);
}
STATIC int
rmlink(ol, olprev, on)
int ol, olprev;
int on;
{
node *n;
link *l, *lprev;
l = getlink(ol);
n = getnode(on);
if (olprev) {
lprev = getlink(olprev);
lprev->l_next = l->l_next;
putlink(lprev);
freenode(n);
}
else {
n->n_link = l->l_next;
putnode(n);
}
freelink(l);
return(l->l_next);
}
/*
* 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(ol)
int ol;
{
link *l;
register node *n;
l = getlink(ol);
n = getnode(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->l_offset;
n->n_tloc = 1;
freelink(l);
putnode(n);
return;
}
if (Vflag && Nheap > Heaphighwater)
Heaphighwater = Nheap; /* diagnostics */
/* insert at the end. caller must reheap(). */
Heap[Nheap] = l->l_offset;
n->n_tloc = Nheap;
freelink(l);
putnode(n);
}
/*
* replace existing link in heap by this one, then
* "percolate" up the heap by exchanging with the parent
*/
STATIC void
reheap(ol)
int ol;
{
link *l, *ltmp;
register int loc, parent;
register Cost cost;
register node *n, *np;
l = getlink(ol);
n = getnode(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);
}
ltmp = getlink(Heap[parent]);
np = getnode(ltmp->l_to);
freelink(ltmp);
if (cost > np->n_cost) {
freenode(np);
freenode(n);
freelink(l);
return;
}
/* move nets below hosts for output stability */
if (cost == np->n_cost && ((n->n_flag & NNET)
|| !(np->n_flag & NNET))) {
freenode(np);
freenode(n);
freelink(l);
return;
}
freenode(np);
heapswap(loc, parent);
regetlink(l);
regetnode(n);
}
freenode(n);
freelink(l);
}
/* extract min (== Heap[1]) from heap */
STATIC int
min_node()
{
link *ltmp, *ltmp1;
int orval;
node *ntmp, *ntmp1;
register int *regheap;
register int i, child;
if (Nheap == 0)
return(0);
regheap = Heap; /* in register -- heavily used */
orval = regheap[1]; /* return this one */
/* move last entry into root, percolate down */
regheap[1] = regheap[Nheap];
ltmp = getlink(regheap[1]);
ntmp = getnode(ltmp->l_to);
ntmp->n_tloc = 1;
putnode(ntmp);
freelink(ltmp);
regheap[Nheap] = 0;
if (--Nheap == 0)
return(orval);
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(orval);
/* use rhs child if smaller than lhs child */
ltmp = getlink(regheap[child]);
ntmp = getnode(ltmp->l_to);
ltmp1 = getlink(regheap[child+1]);
ntmp1 = getnode(ltmp1->l_to);
if (ntmp->n_cost > ntmp1->n_cost
|| (ntmp->n_cost == ntmp1->n_cost
&& !ISANET(ntmp1)))
child++;
freenode(ntmp1);
freelink(ltmp1);
freenode(ntmp);
freelink(ltmp);
ltmp = getlink(regheap[child]);
ntmp = getnode(ltmp->l_to);
ltmp1 = getlink(regheap[i]);
ntmp1 = getnode(ltmp1->l_to);
if (ntmp1->n_cost < ntmp->n_cost) {
freenode(ntmp1);
freelink(ltmp1);
freenode(ntmp);
freelink(ltmp);
return(orval);
}
/* move nets below hosts for output stability */
if (ntmp1->n_cost == ntmp->n_cost
&& (!ISANET(ntmp1) || ISANET(ntmp))) {
freenode(ntmp1);
freelink(ltmp1);
freenode(ntmp);
freelink(ltmp);
return(orval);
}
freenode(ntmp1);
freelink(ltmp1);
freenode(ntmp);
freelink(ltmp);
heapswap(i, child);
i = child;
}
/*NOTREACHED*/
}
/* exchange Heap[i] and Heap[j] pointers */
STATIC void
heapswap(i, j)
int i, j;
{
register int temp;
int *regheap;
node *ntmp;
link *ltmp;
regheap = Heap; /* heavily used -- put in register */
temp = regheap[i];
regheap[i] = regheap[j];
regheap[j] = temp;
ltmp = getlink(regheap[j]);
ntmp = getnode(ltmp->l_to);
ntmp->n_tloc = j;
putnode(ntmp);
freelink(ltmp);
ltmp = getlink(regheap[i]);
ntmp = getnode(ltmp->l_to);
ntmp->n_tloc = i;
putnode(ntmp);
freelink(ltmp);
}
/* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
dehash(on)
register int on;
{
node *n, *ntmp;
n = getnode(on);
if (n->n_tloc < Hashpart) {
freenode(n);
return(1);
}
/* swap with entry in Table[Hashpart] */
ntmp = getnode(Table[Hashpart]);
ntmp->n_tloc = n->n_tloc;
putnode(ntmp);
Table[n->n_tloc] = Table[Hashpart];
Table[Hashpart] = n->n_offset;
n->n_tloc = Hashpart++;
putnode(n);
return(0);
}
backlinks()
{
link *l;
node *n, *parent, *nomap;
int i, ol;
long tcost;
for (i = Hashpart; i < Tabsize; i++) {
nomap = getnode(Table[i]);
parent = getnode(0);
for (l = getlink(nomap->n_link); l->l_offset;
l = getlink(l->l_next)) {
n = getnode(l->l_to);
if (!(n->n_flag & MAPPED)) {
freenode(n);
freelink(l);
continue;
}
if (parent->n_offset == 0) {
freenode(parent);
parent = n;
freelink(l);
continue;
}
if (n->n_cost > parent->n_cost) {
freenode(n);
freelink(l);
continue;
}
if (n->n_cost == parent->n_cost) {
nomap->n_parent = parent->n_offset;
putnode(nomap);
nomap = getnode(nomap->n_offset);
if (tiebreaker(nomap->n_offset, n->n_offset))
{
freenode(n);
freelink(l);
continue;
}
}
freenode(parent);
parent = n;
freelink(l);
}
freelink(l);
if (parent->n_offset == 0) {
freenode(parent);
freenode(nomap);
continue;
}
(void) dehash(nomap->n_offset);
ol = addlink(parent->n_offset, nomap->n_offset, INF,
DEFNET, DEFDIR);
regetnode(nomap);
regetnode(parent);
nomap->n_parent = parent->n_offset;
putnode(nomap);
nomap = getnode(nomap->n_offset);
tcost = costof(parent->n_offset, ol);
regetnode(nomap);
nomap->n_cost = tcost;
putnode(nomap);
freenode(parent);
insert(ol);
reheap(ol);
}
vprintf(stderr, "%d backlinks\n", Nheap);
}
SHAR_EOF
fi
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.2 (down!honey) 86/01/26";
#endif lint
#include "def.h"
void pack();
void
pack()
{
int hole, next;
node *n;
/* 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];
n = getnode(Table[hole]);
n->n_tloc = hole;
putnode(n);
Table[next] = 0;
while (Table[--hole] != 0) /* find next hole */
;
}
}
Hashpart = hole + 1;
}
FILE *Gstream;
dumpgraph()
{
int 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 = getnode(Table[i]);
if (n->n_offset == 0) {
freenode(n);
continue; /* impossible, but ... */
}
/* a minor optimization ... */
if (n->n_link == 0) {
freenode(n);
continue;
}
/* pathparse doesn't need these */
if (n->n_flag & NNET) {
freenode(n);
continue;
}
dumpnode(n->n_offset);
freenode(n);
}
}
dumpnode(ofrom)
int ofrom;
{
link *l;
node *from;
node *to;
char netbuf[BUFSIZ], *nptr = netbuf;
from = getnode(ofrom);
for (l = tmpgetlink(from->n_link) ; l->l_offset;
l = tmpgetlink(l->l_next)) {
if (ofrom == l->l_to)
continue; /* oops -- it's me! */
to = tmpgetnode(l->l_to);
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->n_offset != to->n_root)
to = tmpgetnode(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);
}
freenode(from);
}
/*
* 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()
{
int i;
node *n;
for (i = Hashpart; i < Tabsize; i++) {
n = tmpgetnode(Table[i]);
if (n->n_offset == 0 || (n->n_flag & NNET) == 0 || n->n_root)
continue;
dfs(n->n_offset);
}
}
dfs(o)
int o;
{
link *l;
node *n, *next;
n = getnode(o);
n->n_flag |= INDFS;
n->n_root = n->n_offset;
putnode(n);
n = getnode(n->n_offset);
for (l = getlink(n->n_link); l->l_offset; l = getlink(l->l_next)) {
next = getnode(l->l_to);
if ((next->n_flag & NNET) == 0) {
freenode(next);
freelink(l);
continue;
}
if ((next->n_flag & INDFS) == 0) {
dfs(next->n_offset);
regetnode(next);
if (next->n_root != next->n_offset) {
regetnode(n);
n->n_root = next->n_root;
putnode(n);
n = getnode(n->n_offset);
}
}
else {
regetnode(n);
n->n_root = next->n_root;
putnode(n);
n = getnode(n->n_offset);
}
freenode(next);
freelink(l);
}
freelink(l);
regetnode(n);
n->n_flag &= ~INDFS;
putnode(n);
}
showlinks()
{
link *l;
node *n;
int i;
FILE *estream;
if ((estream = fopen(Linkout, "w")) == 0)
return;
for (i = Hashpart; i < Tabsize; i++) {
n = getnode(Table[i]);
if (n->n_offset == 0) { /* impossible, but ... */
freenode(n);
continue;
}
l = tmpgetlink(n->n_link);
if (l->l_offset) {
fprintf(estream, "%s\t%s(%d)", n->n_name,
tmpgetnode(l->l_to)->n_name,
l->l_cost ? l->l_cost : DEFCOST);
for (l = tmpgetlink(l->l_next); l->l_offset;
l = tmpgetlink(l->l_next))
fprintf(estream, ",\n\t%s(%d)",
tmpgetnode(l->l_to)->n_name,
l->l_cost ? l->l_cost : DEFCOST);
fputc('\n', estream);
}
freenode(n);
}
(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(o, onewp)
int o, onewp;
{
register char *opname, *npname, *name;
node *n, *newp, *oldp;
int metric;
n = getnode(o);
newp = getnode(onewp);
oldp = getnode(n->n_parent);
/*
* given the choice, avoid gatewayed nets,
* thereby placating the FCC or some such.
*/
if (GATEWAYED(newp) && !GATEWAYED(oldp)) {
freenode(n);
freenode(newp);
freenode(oldp);
return(OLDP);
}
if (!GATEWAYED(newp) && GATEWAYED(oldp)) {
freenode(n);
freenode(newp);
freenode(oldp);
return(NEWP);
}
/* look at real parents, not nets */
while (oldp->n_flag & NNET) {
freenode(oldp);
oldp = getnode(oldp->n_parent);
}
while (newp->n_flag & NNET) {
freenode(newp);
newp = getnode(newp->n_parent);
}
/* use fewer hops, if possible */
metric = height(oldp->n_offset) - height(newp->n_offset);
if (metric < 0) {
freenode(oldp);
freenode(newp);
freenode(n);
return(OLDP);
}
if (metric > 0) {
freenode(oldp);
freenode(newp);
freenode(n);
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) {
freenode(oldp);
freenode(newp);
freenode(n);
return(OLDP);
}
if (*npname == *name || *npname == 0) {
freenode(oldp);
freenode(newp);
freenode(n);
return(NEWP);
}
/* use shorter host name, if appl. */
metric = strlen(opname) - strlen(npname);
if (metric < 0) {
freenode(oldp);
freenode(newp);
freenode(n);
return(OLDP);
}
if (metric > 0) {
freenode(oldp);
freenode(newp);
freenode(n);
return(NEWP);
}
/* use larger lexicographically (no reason) */
metric = strcmp(opname, npname);
freenode(oldp);
freenode(newp);
freenode(n);
if (metric < 0)
return(NEWP);
return(OLDP);
}
height(o)
register int o;
{
node *n;
register int i = 0;
n = getnode(o);
freenode(n);
n = getnode(n->n_parent);
while (n->n_offset != 0) {
if ((n->n_flag & NNET) == 0)
i++; /* should count domains too ... */
freenode(n);
n = getnode(n->n_parent);
}
freenode(n);
return(i);
}
SHAR_EOF
fi
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"
long lseek();
extern int fdlink, fdnode;
extern int nodecount, linkcount;
static nlinks, nnodes;
/* imported */
extern char *sbrk();
link *
newlink()
{
link *rval;
int offset;
if ((rval = (link * ) calloc(1, sizeof(link))) == 0)
nomem();
linkcount++;
nlinks++;
offset = lseek(fdlink, 0l, 2) / sizeof(link);
rval->l_next_from = 0;
rval->l_offset = offset;
rval->l_to = 0;
rval->l_cost = 0;
rval->l_flag = '\0';
if (write(fdlink, rval, sizeof(link)) == -1) {
fprintf(stderr, "Temp file write error\n");
badmagic(1);
}
return(rval);
}
node *
newnode()
{
node *rval;
int offset;
if ((rval = (node * ) calloc(1, sizeof(node))) == 0)
nomem();
nodecount++;
nnodes++;
offset = lseek(fdnode, 0l, 2) / sizeof(node);
rval->n_name[0] = '\0';
rval->n_offset = offset;
rval->n_link = 0;
rval->n_net_root = 0;
rval->n_prvparent = 0;
rval->n_cost = 0;
rval->n_tloc = 0;
rval->n_flag = 0;
if (write(fdnode, rval, sizeof(node)) == -1) {
fprintf(stderr, "Temp file write error\n");
badmagic(1);
}
Ncount++;
return(rval);
}
#ifndef strclear
void
strclear(dst, len)
register char *dst;
register int len;
{
while (--len >= 0)
*dst++ = 0;
}
#endif /*strclear*/
int *
newtable(size)
long size;
{
int *rval;
if ((rval = (int *) calloc(1, (unsigned int) (size * sizeof(*rval)))) == 0)
nomem();
return(rval);
}
freetable(t)
int *t;
{
free((char *) t);
}
nomem()
{
fprintf(stderr, "%s: Out of memory (%uk allocated)\n",
ProgName, allocation());
fprintf(stderr, "nodecount was %d, linkcount was %d\n", nodecount, linkcount);
fprintf(stderr, "total nodes found %d, total links found %d\n", nnodes, nlinks);
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);
}
SHAR_EOF
fi
if test -f 'putnode.c'
then
echo shar: "will not over-write existing file 'putnode.c'"
else
cat << \SHAR_EOF > 'putnode.c'
/* putnode -- store node and link structrures temporarily in a disk file */
#include "def.h"
long lseek();
extern int fdnode, fdlink;
extern int nodecount, linkcount;
static node tmpnode;
static node nullnode;
static link nulllink;
static link tmplink;
/* Opens temporary file */
meminit()
{
nodecount = 0;
linkcount = 0;
fdnode = creat(NTEMPFILE, 0600);
close(fdnode);
fdnode = open(NTEMPFILE, 2);
if (fdnode < 0) {
fprintf(stderr, "meminit: temporary node file open error\n");
badmagic(1);
}
fdlink = creat(LTEMPFILE, 0600);
close(fdlink);
fdlink = open(LTEMPFILE, 2);
if (fdlink < 0) {
fprintf(stderr, "meminit: temporary link file open error\n");
badmagic(1);
}
nullnode.n_name[0] = '\0';
nullnode.n_offset = 0;
nullnode.n_link = 0;
nullnode.n_net_root = 0;
nullnode.n_prvparent = 0;
nullnode.n_cost = 0;
nullnode.n_tloc = 0;
nullnode.n_flag = 0;
write(fdnode, &nullnode, sizeof(nullnode));
nulllink.l_next_from = 0;
nulllink.l_offset = 0;
nulllink.l_to = 0;
nulllink.l_cost = 0;
nulllink.l_flag = '\0';
write(fdlink, &nulllink, sizeof(nulllink));
}
/* Frees memory and stores node in temp file; takes pointer to node */
putnode(n)
register node *n;
{
if (n->n_offset != 0) {
lseek(fdnode, (long) (((long) n->n_offset) * sizeof(node)), 0);
if (write(fdnode, n, sizeof(*n)) == -1) {
fprintf(stderr, "putnode: temporary file write error\n");
badmagic(1);
}
}
if (n != &tmpnode) {
free((char *) n);
nodecount--;
}
}
/* Frees memory without rewriting into temp file; takes pointer to node */
freenode(n)
register node *n;
{
if (n != &tmpnode) {
free((char *) n);
nodecount--;
}
}
/* Frees memory and stores link in temp file; takes pointer to link */
putlink(l)
register link *l;
{
if (l->l_offset != 0) {
lseek(fdlink, (long) (((long) l->l_offset) * sizeof(link)), 0);
if (write(fdlink, l, sizeof(*l)) == -1) {
fprintf(stderr, "putlink: temporary file write error\n");
badmagic(1);
}
}
if (l != &tmplink) {
free((char *) l);
linkcount--;
}
}
/* Frees memory without rewriting into temp file; takes pointer to link */
freelink(l)
register link *l;
{
if (l != &tmplink) {
free((char *) l);
linkcount--;
}
}
/* Refreshes node from possibly modified disk image */
regetnode(oldnode)
register node *oldnode;
{
long offset;
if (oldnode->n_offset == 0)
offset = nullnode.n_offset;
else
offset = oldnode->n_offset;
lseek(fdnode, offset * sizeof(node), 0);
if (read(fdnode, oldnode, sizeof(node)) <= 0) {
fprintf(stderr, "regetnode: temporary file read error\n");
badmagic(1);
}
}
/* Returns pointer to node; takes long constant offset */
node *
getnode(offset)
register int offset;
{
node *tnode;
if (offset == 0)
offset = nullnode.n_offset;
lseek(fdnode, (long) (((long) offset) * sizeof(node)), 0);
if ((tnode = (node * ) calloc(1, sizeof(node))) == 0)
nomem();
nodecount++;
if (read(fdnode, tnode, sizeof(tmpnode)) <= 0) {
fprintf(stderr, "getnode: temporary file read error\n");
badmagic(1);
}
return(tnode);
}
/* Returns pointer to node; takes long constant offset */
/* Puts node in a temporary location */
node *
tmpgetnode(offset)
register int offset;
{
if (offset == 0)
offset = nullnode.n_offset;
lseek(fdnode, (long) (((long) offset) * sizeof(node)), 0);
if (read(fdnode, &tmpnode, sizeof(tmpnode)) <= 0) {
fprintf(stderr, "tmpgetnode: temporary file read error\n");
badmagic(1);
}
return(&tmpnode);
}
/* Returns pointer to link; takes long constant offset */
link *
getlink(offset)
register int offset;
{
link *tlink;
if (offset == 0)
offset = nulllink.l_offset;
lseek(fdlink, (long) (((long) offset) * sizeof(link)), 0);
if ((tlink = (link * ) calloc(1, sizeof(link))) == 0)
nomem();
linkcount++;
if (read(fdlink, tlink, sizeof(tmplink)) <= 0) {
fprintf(stderr, "getlink: temporary file read error\n");
badmagic(1);
}
return(tlink);
}
/* Refreshes link from possibly modified disk image */
regetlink(oldlink)
register link *oldlink;
{
long offset;
if (oldlink->l_offset == 0)
offset = nulllink.l_offset;
else
offset = oldlink->l_offset;
lseek(fdlink, offset * sizeof(link), 0);
if (read(fdlink, oldlink, sizeof(link)) <= 0) {
fprintf(stderr, "regetlink: temporary file read error\n");
badmagic(1);
}
}
/* Returns pointer to link; takes long constant offset */
/* Puts link in a temporary location */
link *
tmpgetlink(offset)
register int offset;
{
if (offset == 0)
offset = nulllink.l_offset;
lseek(fdlink, (long) (((long) offset) * sizeof(link)), 0);
if (read(fdlink, &tmplink, sizeof(tmplink)) <= 0) {
fprintf(stderr, "tmpgetlink: temporary file read error\n");
badmagic(1);
}
return(&tmplink);
}
badmagic(n)
{
if (n) {
fprintf(stderr, "%s: cannot recover!\n", ProgName);
#ifdef DEBUG
abort();
#else
exit(n);
#endif
}
}
SHAR_EOF
fi
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.2 (down!honey) 86/01/29";
#endif lint
#include "def.h"
/* I thank Paul Haahr and Greg Noel for helping to clean this up. */
node *ntmp;
%}
%union {
int y_node;
Cost y_cost;
char y_net;
char *y_name;
struct {
int 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 {
ntmp = getnode($2.ys_node);
if (GATEWAYED(ntmp)) {
freenode(ntmp);
addgateway($1, $2.ys_node, $3, $2.ys_net, $2.ys_dir);
}
else {
freenode(ntmp);
addlink($1, $2.ys_node, $3, $2.ys_net, $2.ys_dir);
}
}
| links ',' site cost {
ntmp = getnode($3.ys_node);
if (GATEWAYED(ntmp)) {
freenode(ntmp);
addgateway($1, $3.ys_node, $4, $3.ys_net, $3.ys_dir);
}
else {
freenode(ntmp);
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 { ntmp = getnode($1);
ntmp->n_flag |= ISPRIVATE;
putnode(ntmp);
}
| plist ',' Psite {ntmp = getnode($3);
ntmp->n_flag |= ISPRIVATE;
putnode(ntmp);
}
| plist ',' /* permit this benign error */
;
nlist : Site
| nlist ',' Site {
ntmp = tmpgetnode($3);
if (ntmp->n_net == 0) {
ntmp->n_net = $1;
putnode(ntmp);
$$ = $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 network;
int nlist;
Cost cost;
char netchar, netdir;
{
register int member, nextnet;
node *nnetwork, *ntmp;
nnetwork = getnode(network);
nnetwork->n_flag |= NNET;
putnode(nnetwork);
/* now insert the links */
for (member = nlist ; member; member = nextnet) {
nnetwork = getnode(network);
ntmp = getnode(member);
/* network -> member, cost is 0 */
if (GATEWAYED(nnetwork) && GATEWAYED(ntmp)) {
freenode(nnetwork);
freenode(ntmp);
(void) addgateway(network, member, (Cost) 0,
netchar, netdir);
}
else {
freenode(nnetwork);
freenode(ntmp);
(void) addlink(network, member, (Cost) 0,
netchar, netdir);
}
/* member -> network, cost is parameter */
(void) addlink(member, network, cost, netchar, netdir);
ntmp = getnode(member);
nextnet = ntmp->n_net;
ntmp->n_net = 0; /* clear for later use */
putnode(ntmp);
}
}
/* scanner */
#define LBRACE '{'
#define RBRACE '}'
#define LPAREN '('
#define RPAREN ')'
#define QUOTE '"'
Cost isacost();
yylex()
{
register int c;
Cost cost;
char errbuf[128];
static char buf[128]; /* for return to yacc part */
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
fi
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
fi
exit 0
# End of shell archive
--
Larry Campbell The Boston Software Works, Inc.
Internet: campbell@maynard.bsw.com 120 Fulton Street, Boston MA 02109
uucp: {alliant,wjh12}!maynard!campbell +1 617 367 6846
ARPA: campbell%maynard.uucp@harvisr.harvard.edu MCI: LCAMPBELL