Path: seismo!harvard!talcott!panda!sources-request
From: sources-request@panda.UUCP
Newsgroups: mod.sources
Subject: New pathalias, part 2 of 2
Message-ID: <1332@panda.UUCP>
Date: 23 Jan 86 00:26:27 GMT
Sender: jpn@panda.UUCP
Lines: 2473
Approved: jpn@panda.UUCP

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