rsalz@uunet.uu.net (Rich Salz) (06/08/90)
Submitted-by: peter honeyman <honey@citi.umich.edu>
Posting-number: Volume 22, Issue 110
Archive-name: pathalias10/part02
#! /bin/sh
# This is a shell archive. Remove anything before this line, then feed it
# into a shell via "sh file" or similar. To overwrite existing files,
# type "sh file -c".
# The tool that generated this appeared in the comp.sources.unix newsgroup;
# send mail to comp-sources-unix@uunet.uu.net if you want that tool.
# Contents: addlink.c addnode.c arpa-privates mapaux.c parse.y
# printit.c
# Wrapped by rsalz@litchi.bbn.com on Fri Jun 8 09:25:21 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
echo If this archive is complete, you will see the following message:
echo ' "shar: End of archive 2 (of 3)."'
if test -f 'addlink.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'addlink.c'\"
else
echo shar: Extracting \"'addlink.c'\" \(6001 characters\)
sed "s/^X//" >'addlink.c' <<'END_OF_FILE'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)addlink.c 9.7 88/06/10";
X#endif /* lint */
X
X#include "def.h"
X
X/* exports */
Xextern link *addlink();
Xextern void deadlink(), atrace(), freelink();
Xextern int tracelink(), maptrace();
Xchar *Netchars = "!:@%"; /* sparse, but sufficient */
Xlong Lcount; /* how many edges? */
X
X/* imports */
Xextern int Tflag, Dflag;
Xextern link *newlink();
Xextern node *addnode();
Xextern void yyerror(), die();
Xextern int strcmp(), strlen();
X
X/* privates */
XSTATIC void netbits(), ltrace(), ltrprint();
Xstatic link *Trace[NTRACE];
Xstatic int Tracecount;
X
X#define EQ(n1, n2) (strcmp((n1)->n_name, (n2)->n_name) == 0)
X#define LTRACE if (Tflag) ltrace
X
Xlink *
Xaddlink(from, to, cost, netchar, netdir)
X node *from;
X register node *to;
X Cost cost;
X char netchar, netdir;
X{ register link *l, *prev = 0;
X
X LTRACE(from, to, cost, netchar, netdir, "");
X /*
X * maintain uniqueness for dead links (only).
X */
X for (l = from->n_link; l; l = l->l_next) {
X if (!DEADLINK(l))
X break;
X if (to == l->l_to) {
X /* what the hell, use cheaper dead cost */
X if (cost < l->l_cost) {
X l->l_cost = cost;
X netbits(l, netchar, netdir);
X }
X return l;
X }
X prev = l;
X }
X
X
X /* allocate and link in the new link struct */
X l = newlink();
X if (cost != INF) /* ignore back links */
X Lcount++;
X if (prev) {
X l->l_next = prev->l_next;
X prev->l_next = l;
X } else {
X l->l_next = from->n_link;
X from->n_link = l;
X }
X
X l->l_to = to;
X /* add penalty */
X if ((l->l_cost = cost + from->n_cost) < 0) {
X char buf[100];
X
X l->l_flag |= LDEAD;
X sprintf(buf, "link to %s ignored with negative cost", to->n_name);
X yyerror(buf);
X }
X if (netchar == 0) {
X netchar = DEFNET;
X netdir = DEFDIR;
X }
X netbits(l, netchar, netdir);
X if (Dflag && ISADOMAIN(from))
X l->l_flag |= LTERMINAL;
X
X return l;
X}
X
Xvoid
Xdeadlink(nleft, nright)
X node *nleft, *nright;
X{ link *l, *lhold = 0, *lprev, *lnext;
X
X /* DEAD host */
X if (nright == 0) {
X nleft->n_flag |= NDEAD; /* DEAD host */
X return;
X }
X
X /* DEAD link */
X
X /* grab <nleft, nright> instances at head of nleft adjacency list */
X while ((l = nleft->n_link) != 0 && l->l_to == nright) {
X nleft->n_link = l->l_next; /* disconnect */
X l->l_next = lhold; /* terminate */
X lhold = l; /* add to lhold */
X }
X
X /* move remaining <nleft, nright> instances */
X for (lprev = nleft->n_link; lprev && lprev->l_next; lprev = lprev->l_next) {
X if (lprev->l_next->l_to == nright) {
X l = lprev->l_next;
X lprev->l_next = l->l_next; /* disconnect */
X l->l_next = lhold; /* terminate */
X lhold = l;
X }
X }
X
X /* check for emptiness */
X if (lhold == 0) {
X addlink(nleft, nright, INF / 2, DEFNET, DEFDIR)->l_flag |= LDEAD;
X return;
X }
X
X /* reinsert deleted edges as DEAD links */
X for (l = lhold; l; l = lnext) {
X lnext = l->l_next;
X addlink(nleft, nright, l->l_cost, NETCHAR(l), NETDIR(l))->l_flag |= LDEAD;
X freelink(l);
X }
X}
X
XSTATIC void
Xnetbits(l, netchar, netdir)
X register link *l;
X char netchar, netdir;
X{
X l->l_flag &= ~LDIR;
X l->l_flag |= netdir;
X l->l_netop = netchar;
X}
X
Xint
Xtracelink(arg)
X char *arg;
X{ char *bang;
X link *l;
X
X if (Tracecount >= NTRACE)
X return -1;
X l = newlink();
X bang = index(arg, '!');
X if (bang) {
X *bang = 0;
X l->l_to = addnode(bang+1);
X } else
X l->l_to = 0;
X
X l->l_from = addnode(arg);
X Trace[Tracecount++] = l;
X return 0;
X}
X
X/*
X * the obvious choice for testing equality is to compare struct
X * addresses, but that misses private nodes, so we use strcmp().
X */
X
XSTATIC void
Xltrace(from, to, cost, netchar, netdir, message)
X node *from, *to;
X Cost cost;
X char netchar, netdir, *message;
X{ link *l;
X int i;
X
X for (i = 0; i < Tracecount; i++) {
X l = Trace[i];
X /* overkill, but you asked for it! */
X if (l->l_to == 0) {
X if (EQ(from, l->l_from) || EQ(to, l->l_from))
X break;
X } else if (EQ(from, l->l_from) && EQ(to, l->l_to))
X break;
X else if (EQ(from, l->l_to) && EQ(to, l->l_from))
X break; /* potential dead backlink */
X }
X if (i < Tracecount)
X ltrprint(from, to, cost, netchar, netdir, message);
X}
X
X/* print a trace item */
XSTATIC void
Xltrprint(from, to, cost, netchar, netdir, message)
X node *from, *to;
X Cost cost;
X char netchar, netdir, *message;
X{ char buf[256], *bptr = buf;
X
X strcpy(bptr, from->n_name);
X bptr += strlen(bptr);
X *bptr++ = ' ';
X if (netdir == LRIGHT) /* @% */
X *bptr++ = netchar;
X strcpy(bptr, to->n_name);
X bptr += strlen(bptr);
X if (netdir == LLEFT) /* !: */
X *bptr++ = netchar;
X sprintf(bptr, "(%ld) %s", cost, message);
X yyerror(buf);
X}
X
Xvoid
Xatrace(n1, n2)
X node *n1, *n2;
X{ link *l;
X int i;
X char buf[256];
X
X for (i = 0; i < Tracecount; i++) {
X l = Trace[i];
X if (l->l_to == 0 && ((node *) l->l_from == n1 || (node *) l->l_from == n2)) {
X sprintf(buf, "%s = %s", n1->n_name, n2->n_name);
X yyerror(buf);
X return;
X }
X }
X}
X
Xint
Xmaptrace(from, to)
X register node *from, *to;
X{ register link *l;
X register int i;
X
X for (i = 0; i < Tracecount; i++) {
X l = Trace[i];
X if (l->l_to == 0) {
X if (EQ(from, l->l_from) || EQ(to, l->l_from))
X return 1;
X } else if (EQ(from, l->l_from) && EQ(to, l->l_to))
X return 1;
X }
X return 0;
X}
X
Xvoid
Xdeletelink(from, to)
X node *from;
X node *to;
X{ register link *l, *lnext;
X
X l = from->n_link;
X
X /* delete all neighbors of from */
X if (to == 0) {
X while (l) {
X LTRACE(from, l->l_to, l->l_cost, NETCHAR(l), NETDIR(l), "DELETED");
X lnext = l->l_next;
X freelink(l);
X l = lnext;
X }
X from->n_link = 0;
X return;
X }
X
X /* delete from head of list */
X while (l && EQ(to, l->l_to)) {
X LTRACE(from, to, l->l_cost, NETCHAR(l), NETDIR(l), "DELETED");
X lnext = l->l_next;
X freelink(l);
X l = from->n_link = lnext;
X }
X
X /* delete from interior of list */
X if (l == 0)
X return;
X for (lnext = l->l_next; lnext; lnext = l->l_next) {
X if (EQ(to, lnext->l_to)) {
X LTRACE(from, to, l->l_cost, NETCHAR(l), NETDIR(l), "DELETED");
X l->l_next = lnext->l_next;
X freelink(lnext);
X /* continue processing this link */
X } else
X l = lnext; /* next link */
X }
X}
END_OF_FILE
if test 6001 -ne `wc -c <'addlink.c'`; then
echo shar: \"'addlink.c'\" unpacked with wrong size!
fi
# end of 'addlink.c'
fi
if test -f 'addnode.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'addnode.c'\"
else
echo shar: Extracting \"'addnode.c'\" \(8979 characters\)
sed "s/^X//" >'addnode.c' <<'END_OF_FILE'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)addnode.c 9.6 89/05/05";
X#endif
X
X#include "def.h"
X
X#define EQ(n, s) (*(n)->n_name == *(s) && strcmp((n)->n_name, (s)) == 0)
X
X/* exports */
Xnode *addnode(), *addprivate();
Xvoid alias(), hashanalyze(), fixprivate();
Xnode **Table; /* hash table ^ priority queue */
Xlong Tabsize; /* size of Table */
X
X/* imports */
Xextern link *addlink();
Xextern node *newnode(), **newtable();
Xextern char *strsave();
Xextern int Iflag, Tflag, Vflag;
Xextern node **Table;
Xextern long Ncount, Tabsize;
Xextern char **Argv;
Xextern void atrace(), die(), freetable();
Xextern int strcmp();
X
X/* privates */
XSTATIC void crcinit(), rehash(), lowercase();
XSTATIC long fold();
XSTATIC long hash();
XSTATIC node *isprivate();
Xstatic node *Private; /* list of private nodes in current input file */
X/*
X * these numbers are chosen because:
X * -> they are prime,
X * -> they are monotonic increasing,
X * -> each is a tad smaller than a multiple of 1024,
X * -> they form a fibonacci sequence (almost).
X * the first point yields good hash functions, the second is used for the
X * standard re-hashing implementation of open addressing, the third
X * optimizes for quirks in some mallocs i have seen, and the fourth simply
X * appeals to me.
X */
Xstatic long Primes[] = {
X 1021, 2039, 3067, 5113, 8179, 13309, 21499, 34807, 56311, 0
X};
X
Xstatic int Tabindex;
Xstatic long Tab128; /* Tabsize * 128 */
X
Xnode *
Xaddnode(name)
X register char *name;
X{ register long i;
X register node *n;
X
X if (Iflag)
X lowercase(name);
X
X /* is it a private host? */
X n = isprivate(name);
X if (n)
X return n;
X
X i = hash(name, 0);
X if (Table[i])
X return Table[i];
X
X n = newnode();
X n->n_name = strsave(name);
X Table[i] = n;
X n->n_tloc = i; /* essentially a back link to the table */
X
X return n;
X}
X
Xvoid
Xalias(n1, n2)
X node *n1, *n2;
X{
X link *l;
X
X if (ISADOMAIN(n1) && ISADOMAIN(n2)) {
X fprintf(stderr, "%s: domain alias %s = %s is illegal\n", Argv[0], n1->n_name, n2->n_name);
X return;
X }
X l = addlink(n1, n2, (Cost) 0, DEFNET, DEFDIR);
X l->l_flag |= LALIAS;
X l = addlink(n2, n1, (Cost) 0, DEFNET, DEFDIR);
X l->l_flag |= LALIAS;
X if (Tflag)
X atrace(n1, n2);
X}
X
X/*
X * fold a string into a long int. 31 bit crc (from andrew appel).
X * the crc table is computed at run time by crcinit() -- we could
X * precompute, but it takes 1 clock tick on a 750.
X *
X * This fast table calculation works only if POLY is a prime polynomial
X * in the field of integers modulo 2. Since the coefficients of a
X * 32-bit polynomail won't fit in a 32-bit word, the high-order bit is
X * implicit. IT MUST ALSO BE THE CASE that the coefficients of orders
X * 31 down to 25 are zero. Happily, we have candidates, from
X * E. J. Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
X * x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
X * x^31 + x^3 + x^0
X *
X * We reverse the bits to get:
X * 111101010000000000000000000000001 but drop the last 1
X * f 5 0 0 0 0 0 0
X * 010010000000000000000000000000001 ditto, for 31-bit crc
X * 4 8 0 0 0 0 0 0
X */
X
X#define POLY32 0xf5000000 /* 32-bit polynomial */
X#define POLY31 0x48000000 /* 31-bit polynomial */
X#define POLY POLY31 /* use 31-bit to avoid sign problems */
X
Xstatic long CrcTable[128];
X
XSTATIC void
Xcrcinit()
X{ register int i,j;
X register long sum;
X
X for (i = 0; i < 128; i++) {
X sum = 0;
X for (j = 7-1; j >= 0; --j)
X if (i & (1 << j))
X sum ^= POLY >> j;
X CrcTable[i] = sum;
X }
X}
X
XSTATIC long
Xfold(s)
X register char *s;
X{ register long sum = 0;
X register int c;
X
X while ((c = *s++) != 0)
X sum = (sum >> 7) ^ CrcTable[(sum ^ c) & 0x7f];
X return sum;
X}
X
X
X#define HASH1(n) ((n) % Tabsize);
X#define HASH2(n) (Tabsize - 2 - ((n) % (Tabsize-2))) /* sedgewick */
X
X/*
X * when alpha is 0.79, there should be 2 probes per access (gonnet).
X * use long constant to force promotion. Tab128 biases HIGHWATER by
X * 128/100 for reduction in strength in isfull().
X */
X#define HIGHWATER 79L
X#define isfull(n) ((n) * 128 >= Tab128)
X
XSTATIC long
Xhash(name, unique)
X char *name;
X int unique;
X{ register long probe;
X register long hash2;
X register node *n;
X
X if (isfull(Ncount)) {
X if (Tabsize == 0) { /* first time */
X crcinit();
X Tabindex = 0;
X Tabsize = Primes[0];
X Table = newtable(Tabsize);
X Tab128 = (HIGHWATER * Tabsize * 128L)/100L;
X } else
X rehash(); /* more, more! */
X }
X
X probe = fold(name);
X hash2 = HASH2(probe);
X probe = HASH1(probe);
X
X /*
X * probe the hash table.
X * if unique is set, we require a fresh slot.
X * otherwise, use double hashing to find either
X * (1) an empty slot, or
X * (2) a non-private copy of this host name
X *
X * this is an "inner loop."
X */
X while ((n = Table[probe]) != 0) {
X if (EQ(n, name) && !(n->n_flag & ISPRIVATE) && !unique)
X return probe; /* this is it! */
X
X probe -= hash2; /* double hashing */
X if (probe < 0)
X probe += Tabsize;
X }
X return probe; /* brand new */
X}
X
XSTATIC void
Xrehash()
X{ register node **otable, **optr;
X register long probe;
X long osize;
X
X#ifdef DEBUG
X hashanalyze();
X#endif
X optr = Table + Tabsize - 1; /* ptr to last */
X otable = Table;
X osize = Tabsize;
X Tabsize = Primes[++Tabindex];
X if (Tabsize == 0)
X die("too many hosts"); /* need more prime numbers */
X vprintf(stderr, "rehash into %d\n", Tabsize);
X Table = newtable(Tabsize);
X Tab128 = (HIGHWATER * Tabsize * 128L)/100L;
X
X do {
X if (*optr == 0)
X continue; /* empty slot in old table */
X probe = hash((*optr)->n_name,
X ((*optr)->n_flag & ISPRIVATE) != 0);
X if (Table[probe] != 0)
X die("rehash error");
X Table[probe] = *optr;
X (*optr)->n_tloc = probe;
X } while (optr-- > otable);
X freetable(otable, osize);
X}
X
Xvoid
Xhashanalyze()
X#if 0
X{ long probe, hash2;
X int count, i, collision[8];
X int longest = 0, total = 0, slots = 0, longprobe = 0;
X int nslots = sizeof(collision)/sizeof(collision[0]);
X
X if (!Vflag)
X return;
X
X strclear((char *) collision, sizeof(collision));
X for (i = 0; i < Tabsize; i++) {
X if (Table[i] == 0)
X continue;
X /* private hosts too hard to account for ... */
X if (Table[i]->n_flag & ISPRIVATE)
X continue;
X count = 1;
X probe = fold(Table[i]->n_name);
X /* don't change the order of the next two lines */
X hash2 = HASH2(probe);
X probe = HASH1(probe);
X /* thank you! */
X while (Table[probe] != 0
X && strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
X count++;
X probe -= hash2;
X if (probe < 0)
X probe += Tabsize;
X }
X if (Table[probe] == 0)
X die("impossible hash error");
X
X total += count;
X slots++;
X if (count > longest) {
X longest = count;
X longprobe = i;
X }
X if (count >= nslots)
X count = 0;
X collision[count]++;
X }
X for (i = 1; i < nslots; i++)
X if (collision[i])
X fprintf(stderr, "%d chains: %d (%ld%%)\n",
X i, collision[i], (collision[i] * 100L)/ slots);
X if (collision[0])
X fprintf(stderr, "> %d chains: %d (%ld%%)\n",
X nslots - 1, collision[0],
X (collision[0] * 100L)/ slots);
X fprintf(stderr, "%2.2f probes per access, longest chain: %d, %s\n",
X (double) total / slots, longest, Table[longprobe]->n_name);
X if (Vflag < 2)
X return;
X probe = fold(Table[longprobe]->n_name);
X hash2 = HASH2(probe);
X probe = HASH1(probe);
X while (Table[probe] != 0
X && strcmp(Table[probe]->n_name, Table[longprobe]->n_name) != 0) {
X fprintf(stderr, "%5d %s\n", probe, Table[probe]->n_name);
X probe -= hash2;
X if (probe < 0)
X probe += Tabsize;
X }
X fprintf(stderr, "%5d %s\n", probe, Table[probe]->n_name);
X
X}
X#else
X{
X /* the hash algorithms are perfect -- leave them alone */
X}
X#endif
X
X/* convert to lower case in place */
XSTATIC void
Xlowercase(s)
X register char *s;
X{
X do {
X if (isupper(*s))
X *s -= 'A' - 'a'; /* ASCII */
X } while (*s++);
X}
X
X/*
X * this might need change if privates catch on
X */
XSTATIC node *
Xisprivate(name)
X register char *name;
X{ register node *n;
X
X for (n = Private; n != 0; n = n->n_private)
X if (strcmp(name, n->n_name) == 0)
X return n;
X return 0;
X}
X
X/* Add a private node so private that nobody can find it. */
Xnode *
Xaddhidden(name)
X register char *name;
X{ register node *n;
X register int i;
X if (Iflag)
X lowercase(name);
X
X n = newnode();
X n->n_name = strsave(name);
X n->n_flag = ISPRIVATE;
X i = hash(n->n_name, 1);
X if (Table[i] != 0)
X die("impossible hidden node error");
X Table[i] = n;
X n->n_tloc = i;
X n->n_private = 0;
X return n;
X}
X
Xvoid
Xfixprivate()
X{ register node *n, *next;
X register long i;
X
X for (n = Private; n != 0; n = next) {
X n->n_flag |= ISPRIVATE; /* overkill, but safe */
X i = hash(n->n_name, 1);
X if (Table[i] != 0)
X die("impossible private node error");
X
X Table[i] = n;
X n->n_tloc = i; /* essentially a back link to the table */
X next = n->n_private;
X n->n_private = 0; /* clear for later use */
X }
X Private = 0;
X}
X
Xnode *
Xaddprivate(name)
X register char *name;
X{ register node *n;
X
X if (Iflag)
X lowercase(name);
X if ((n = isprivate(name)) != 0)
X return n;
X
X n = newnode();
X n->n_name = strsave(name);
X n->n_private = Private;
X Private = n;
X return n;
X}
END_OF_FILE
if test 8979 -ne `wc -c <'addnode.c'`; then
echo shar: \"'addnode.c'\" unpacked with wrong size!
fi
# end of 'addnode.c'
fi
if test -f 'arpa-privates' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'arpa-privates'\"
else
echo shar: Extracting \"'arpa-privates'\" \(7927 characters\)
sed "s/^X//" >'arpa-privates' <<'END_OF_FILE'
X#################################################################
X# arpa-privates file for arpatxt/pathalias #
X# #
X# updated from hosts.txt ver. 750 and the #
X# UUCP Project map data as of 17-Jun-88 #
X#################################################################
X# "master" file is available for anonymous ftp at: #
X# swan.ulowell.edu:~ftp/hosts/arpa-privates #
X# citi.umich.edu:~ftp/pub/honey/arpa-privates #
X# #
X# Send updates to postmaster at one of above sites. #
X#################################################################
X# format: #
X# host map.file (for registered UUCP hosts) #
X# host [map.file] (for unregistered UUCP hosts) #
X# Everything after white space is ignored, and is #
X# primarily intended to keep the file easier to update. #
X# Order does not matter, but case does. #
X#################################################################
Xa usa.ca
Xaardvark usa.or
Xabbott usa.ca
Xac1 [usa.ca] nsc
Xac6 [usa.ca] cerebus, esl
Xachilles [att]
Xacorn gbr
Xadam swe
Xadams swe
Xadmin usa.ca
Xalamo usa.tx
Xalex usa.va
Xalf [usa.az] ellymae
Xalgedi [usa.wa] pilchuck
Xalien usa.ca
Xalpha usa.in
Xaltair [usa.tx] juniper
Xamc usa.wa
Xamos [usa.ca] suntan
Xandy [att]
Xantares usa.nj
Xanubis usa.il
Xapollo usa.ma
Xaqua usa.ma
Xarc usa.ca
Xares swe
Xargon usa.nj
Xargus usa.nj
Xariadne grc
Xariel [usa.oh] mtune-isn
Xaris grc
Xarthur [usa.mo] wuphys
Xasgard usa.or
Xastro [usa.tx] milano
Xathena [usa.ca] daisy
Xatlas [att]
Xatt
Xb21 deu
Xbacchus usa.nc
Xbert usa.ca
Xbezier [usa.oh] bgsuvax
Xblue jpn
Xbluto [usa.tx] im4u
Xbobcat [usa.ca] vortex
Xboojum [att]
Xboole [att]
Xbosco [esp]
Xbounty [usa.az] ellymae
Xbourbaki usa.il
Xbridge [usa.il] richp1
Xbugs [usa.ca] cuschico
Xbull usa.ca
Xcac usa.ma
Xcad dmk (ibt)
Xcalico usa.ny
Xcallisto usa.in
Xcalvin [usa.ca] ucdavis
Xcantor [usa.il] gargoyle, luccpud
Xcarl swe
Xcarmel [usa.az] verde
Xcarrara [usa.ma] talcott
Xcasper usa.or
Xcastor [att]
Xccb [kor] kaist
Xccd usa.fl (pd1)
Xccs [usa.tx] convex
Xcerberus usa.ca
Xchaos usa.ok
Xcheetah usa.oh
Xchem usa.ca
Xcheops [usa.ca] esl
Xchip usa.ca
Xchiron usa.ny
Xchopin [att]
Xcims1 usa.ga
Xcip ita
Xcirce [att]
Xclara usa.ny
Xclover usa.ca
Xcls [usa.nh] sii
Xclutx [usa.fl] gould
Xcmr usa.fl
Xcogito [att]
Xcognac usa.pa
Xcolby usa.me
Xcondor usa.ma
Xcookie usa.ne
Xcoral usa.ca
Xcortex [usa.tx] CNLNET/soma
Xcottage gbr
Xcrash usa.ca
Xcs1 usa.ca
Xcsab [usa.va] xanth, [usa.il] uiucdcs
Xcsc can.on
Xcsd1 [usa.ny] cmcl2
Xcsd2 [usa.ny] cmcl2
Xcssun [usa.ny] albanycs
Xcsun1 usa.ga
Xcsun2 usa.ga
Xcti usa.ca
Xcurie usa.tx
Xcygnus usa.ny
Xdalek usa.ca
Xdali [esp] goya
Xdarwin can.on
Xdavid usa.oh
Xdcn1 [usa.ca] scgvaxd
Xdeimos [usa.oh] codas
Xdelphi ita
Xdeneb [can.bc] ubc-cs
Xdescartes [usa.ca] nosc
Xdevvax usa.ny (until Larry fixes news path on jpl-devvax)
Xdewey [usa.ca] hpda
Xdipl usa.ca
Xdisc [usa.ca] ucdavis
Xdorothy usa.ca
Xdraco [usa.tx] petro
Xea usa.ok
Xeagle [usa.ca] ames
Xearth [att]
Xeast fra
Xecn nld
Xed gbr
Xedam [att]
Xedith [usa.oh] mtune
Xeli usa.dc
Xelse jpn
Xelvira [usa.dc] sundc
Xemily [usa.nj] althea
Xems usa.mn
Xernie usa.ca
Xescher usa.ca
Xetl [usa.va] potomac
Xeunice usa.fl
Xeuropa usa.ri
Xevans [usa.ca] ucbvax
Xeve [usa.ny] clara
Xewok [usa.nc] suntri
Xfalcon [usa.nc] suntri
Xfaraday usa.ny
Xfaust usa.ma
Xfenway usa.ga
Xfergvax [usa.ne] upba
Xfisher usa.nj
Xflight [usa.or] argent
Xfluke usa.wa
Xfoobar usa.or
Xforest [usa.tx] hal6000
Xforty2 che
Xfred usa.co
Xfrisbee usa.co
Xfrog usa.ma
Xgaia usa.co
Xgalaxy usa.nj
Xgamma [usa.oh] codas
Xgandalf can.on
Xgarfield can.nf
Xgateway [usa.ut] pedro
Xgemini usa.ca
Xgeorge usa.tx
Xgilbert [usa.wa] pilchuck
Xgizmo [usa.ca] sun
Xgodot usa.nc
Xgodzilla [att]
Xgolem usa.ca
Xgort [usa.ok] romed
Xgould usa.fl
Xgranite [usa.nh] decvax
Xgreen [usa.md] jhunix
Xgrendel [usa.oh] mtune
Xgrinch usa.ca
Xgroucho [att]
Xgrumpy [usa.oh] codas
Xgull usa.tx
Xhal usa.oh
Xhamster [usa.ca] qantel
Xhappy usa.ca
Xhawk [usa.ca] nosc
Xhector [att]
Xhelios can.on
Xhermes [att]
Xhollywood [usa.ca] fortune
Xhottub usa.ca
Xhq sgp
Xhub [usa.ca] comdesign
Xhugo usa.va
Xhydra usa.nj
Xhydro [usa.ca] csustan
Xibd [att]
Xibis usa.tx
Xicarus [usa.ri] brunix
Xice usa.wi
Ximagen usa.ca
Xindra [usa.oh] codas
Xintrepid usa.ar
Xio [usa.oh] mtune
Xipac [usa.az] noao, [usa.ca] csula-ps
Xircam fra
Xiris usa.ri
Xisi usa.ca
Xisis usa.co
Xisland usa.ca
Xjack usa.ca
Xjanus usa.ca
Xjhereg [usa.mn] bungia
Xjuniper usa.tx
Xkaos usa.ma
Xkiwi bel
Xkontiki dmk
Xkronos grc
Xlafite [usa.nh] decvax
Xlassen usa.ca
Xlaura deu
Xleg [fra] geocub
Xlego dmk
Xleopard [att]
Xlilac kor
Xlinus usa.ma
Xlion [att]
Xlola [usa.oh] codas
Xlono usa.ca
Xlynx usa.ca
Xmacom1 usa.md
Xmagic [usa.ca] idi
Xmanatee usa.fl
Xmanta usa.pa
Xmarge usa.ca
Xmars usa.nj
Xmaui usa.va
Xmax [att]
Xmaxwell usa.mo
Xmcl can.sk
Xmcs usa.md
Xmedusa usa.nj
Xmegalon deu
Xmercury [usa.ma] interlan
Xmerlin [usa.ma] masscomp
Xmickey usa.ca
Xmimas nld
Xminnie usa.co
Xmiranda [usa.oh] mtune
Xmirage gbr
Xmoe [usa.nv] jimi
Xmojave usa.ca
Xmoses [usa.mi] umich
Xmouse usa.de
Xmozart usa.ny
Xmruxd [att]
Xms can.on
Xmycroft [usa.ca] hplabs
Xmyrddin [usa.ca] amdahl-bartender
Xnetman [att]
Xnewton [can.bc] ubc-cs
Xnexus usa.dc
Xnirvana usa.va
Xnoether [usa.ny] mozart
Xnova usa.ok
Xoac [att]
Xnps [usa.il] cerl
Xnyquiest [att]
Xoahu [usa.nj] hjuxa
Xoak [usa.ct] clunker
Xoasis usa.ca (precautionary. llnl clashes with oasis.sait.ko.kr)
Xocean [usa.ca] ucsbcsl
Xodin [att]
Xopus [att]
Xorbit usa.mn
Xorca [usa.az] ellymae
Xorcas usa.wa
Xoregon usa.or {believe it or not}
Xorion [att]
Xorville usa.ny
Xoscar [usa.oh] bcd-dyn
Xosiris usa.md
Xoz usa.wa
Xpallas usa.il
Xpandora [usa.ma] harv-net
Xpegasus [att]
Xpercival usa.or
Xphobos usa.vt
Xphoebus gbr
Xphoenix [att]
Xphysics [usa.ny] ccnysci
Xpicasso [esp] goya
Xpilchuck usa.wa
Xpioneer usa.md
Xpixar usa.ca
Xplasma usa.ca
Xplato usa.ca
Xpluto usa.ny
Xpokey [usa.va] men2a
Xpolaris [usa.wa] camco
Xpollux usa.tx
Xpostel nld
Xpresto usa.md
Xpriam [che] cernvax
Xprime usa.ma
Xprism usa.nj
Xprodigal usa.pa
Xprometheus usa.md
Xpsc usa.md
Xpsych [aus]
Xpsyche usa.nc
Xpuppy usa.ny
Xqat [usa.tx] techsup
Xquark [usa.ca] csuchico
Xra [can.bc] ubc-cs
Xrainier swe
Xralph usa.la
Xrdm usa.ga
Xreason usa.ny
Xrebel usa.ga
Xred jpn
Xredwood [usa.ca] amdcad
Xridge usa.ca
Xrobin [usa.oh] bgsuvax [usa.ma] linus
Xrodan usa.or
Xrome usa.ok
Xrosetta [usa.tx] rice
Xrover [usa.az] ellymae
Xrsch [usa.ma] harvard
Xsable [usa.ca] pyramid
Xsabre [usa.oh] codas
Xsal swe
Xsam usa.il
Xsandy [usa.tx] woton
Xsas [usa.nc] rti
Xsaturn [kor] ketri
Xscarecrow [usa.pa] lehi3b15
Xscooter usa.ca
Xselect nld
Xservice gbr
Xshamash usa.mn
Xshaw [att]
Xshockeye usa.pa
Xshrike [usa.tx] MBIRNET
Xshrimp usa.tx
Xsierra usa.ca
Xsimon usa.il
Xsirius [usa.nh] dartvax
Xsmith [can.ab] edm
Xsnark usa.pa
Xsnucom kor
Xsol usa.nh
Xsolar usa.nm
Xsoleil usa.nj
Xspam usa.nj
Xsparky [usa.oh] codas
Xsphinx usa.il
Xspike usa.la
Xspock usa.ct
Xsri aus.qld
Xssi usa.wi
Xstar [usa.oh] codas
Xstars [can.ns] dalcs
Xstuart [usa.md] prometheus
Xstymie [usa.ma] harvard
Xsuna [usa.mn] mscunx
Xsunburn usa.az
Xsunrise usa.nj
Xsunspot usa.nm
Xsuntan usa.ca
Xsunup usa.wa
Xsuper usa.md
Xsvc [usa.md] epiwrl
Xswamp [usa.ca] amdahl
Xswan usa.tx
Xtaurus isr
Xte gbr
Xterminus [att]
Xthermo [usa.nv] stride1
Xthor dmk
Xthunder can.on
Xtiger usa.nj
Xtinman usa.ca
Xtitan usa.ca
Xtrantor usa.ca
Xtut fin
Xubvax usa.ca
Xunh usa.nh
Xunix usa.wa
Xusafa [usa.co] winfree, [usa.fl] gould, [usa.nh] trixie
Xvalhalla [usa.mi] edsr
Xvax2 [usa.md] elsie
Xvector usa.tx
Xvice [usa.or] enky, budda, loop
Xvideo [att]
Xvilya [att]
Xviper [usa.mn] bungia, mmm, pwcs, quest
Xvista usa.ca
Xvlsi1 [usa.ut] byuopus
Xvlsi2 [usa.ut] byuopus
Xvlsi3 [usa.ut] byuopus
Xvolt usa.ca
Xvoodoo usa.wa
Xwang usa.ma
Xwayback [att]
Xwombat usa.ca
Xwotan usa.ca
Xxyzzy usa.nc
Xyoda usa.co (UCARNET)
Xyogi [usa.nj] bellcore-micom, pyrnj
Xz usa.ca
Xzap can.qc
Xzaphod can.sk
Xzeta [usa.md] cp1
Xzeus can.bc
Xzip usa.oh
Xzorac can.on
END_OF_FILE
if test 7927 -ne `wc -c <'arpa-privates'`; then
echo shar: \"'arpa-privates'\" unpacked with wrong size!
fi
# end of 'arpa-privates'
fi
if test -f 'mapaux.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'mapaux.c'\"
else
echo shar: Extracting \"'mapaux.c'\" \(8512 characters\)
sed "s/^X//" >'mapaux.c' <<'END_OF_FILE'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)mapaux.c 9.4 89/03/01";
X#endif /* lint */
X
X#include "def.h"
X
X/* imports */
Xextern long Nheap, Hashpart, Tabsize, NumNcopy, Nlink, NumLcopy;
Xextern node **Table, *Home;
Xextern char *Graphout, *Linkout, *Netchars, **Argv;
Xextern int Vflag;
Xextern void freelink(), die();
Xextern long pack();
Xextern link *newlink();
Xextern node *newnode();
Xextern char *strsave();
Xextern int strcmp(), strlen();
X
X/* exports */
Xextern long pack();
Xextern void resetnodes(), dumpgraph(), showlinks(), terminalnet();
Xextern int tiebreaker();
Xextern node *ncopy();
X
X/* privates */
Xstatic FILE *Gstream; /* for dumping graph */
XSTATIC void dumpnode(), untangle(), dfs();
XSTATIC int height();
XSTATIC link *lcopy();
X
X
X/*
X * slide everything from Table[low] to Table[high]
X * up toward the high end. make room! make room!
X */
Xlong
Xpack(low, high)
X long low, high;
X{ long hole, next;
X
X /* find first "hole " */
X for (hole = high; hole >= low && Table[hole] != 0; --hole)
X ;
X
X /* repeatedly move next filled entry into last hole */
X for (next = hole - 1; next >= low; --next) {
X if (Table[next] != 0) {
X Table[hole] = Table[next];
X Table[hole]->n_tloc = hole;
X Table[next] = 0;
X while (Table[--hole] != 0) /* find next hole */
X ;
X }
X }
X return hole + 1;
X}
X
Xvoid
Xresetnodes()
X{ register long i;
X register node *n;
X
X for (i = Hashpart; i < Tabsize; i++)
X if ((n = Table[i]) != 0) {
X n->n_cost = (Cost) 0;
X n->n_flag &= ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT|NTERMINAL);
X n->n_copy = n;
X }
X
X Home->n_cost = (Cost) 0;
X Home->n_flag &= ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT|NTERMINAL);
X Home->n_copy = Home;
X}
X
Xvoid
Xdumpgraph()
X{ register long i;
X register node *n;
X
X if ((Gstream = fopen(Graphout, "w")) == NULL) {
X fprintf(stderr, "%s: ", Argv[0]);
X perror(Graphout);
X return;
X }
X
X untangle(); /* untangle net cycles for proper output */
X
X for (i = Hashpart; i < Tabsize; i++) {
X n = Table[i];
X if (n == 0)
X continue; /* impossible, but ... */
X /* a minor optimization ... */
X if (n->n_link == 0)
X continue;
X /* pathparse doesn't need these */
X if (n->n_flag & NNET)
X continue;
X dumpnode(n);
X }
X}
X
XSTATIC void
Xdumpnode(from)
X register node *from;
X{ register node *to;
X register link *l;
X link *lnet = 0, *ll, *lnext;
X
X for (l = from->n_link ; l; l = l->l_next) {
X to = l->l_to;
X if (from == to)
X continue; /* oops -- it's me! */
X
X if ((to->n_flag & NNET) == 0) {
X /* host -> host -- print host>host */
X if (l->l_cost == INF)
X continue; /* phoney link */
X fputs(from->n_name, Gstream);
X putc('>', Gstream);
X fputs(to->n_name, Gstream);
X putc('\n', Gstream);
X } else {
X /*
X * host -> net -- just cache it for now.
X * first check for dups. (quadratic, but
X * n is small here.)
X */
X while (to->n_root && to != to->n_root)
X to = to->n_root;
X for (ll = lnet; ll; ll = ll->l_next)
X if (strcmp(ll->l_to->n_name, to->n_name) == 0)
X break;
X if (ll)
X continue; /* dup */
X ll = newlink();
X ll->l_next = lnet;
X ll->l_to = to;
X lnet = ll;
X }
X }
X
X /* dump nets */
X if (lnet) {
X /* nets -- print host@\tnet,net, ... */
X fputs(from->n_name, Gstream);
X putc('@', Gstream);
X putc('\t', Gstream);
X for (ll = lnet; ll; ll = lnext) {
X lnext = ll->l_next;
X fputs(ll->l_to->n_name, Gstream);
X if (lnext)
X fputc(',', Gstream);
X freelink(ll);
X }
X putc('\n', Gstream);
X }
X}
X
X/*
X * remove cycles in net definitions.
X *
X * depth-first search
X *
X * for each net, run dfs on its neighbors (nets only). if we return to
X * a visited node, that's a net cycle. mark the cycle with a pointer
X * in the n_root field (which gets us closer to the root of this
X * portion of the dfs tree).
X */
XSTATIC void
Xuntangle()
X{ register long i;
X register node *n;
X
X for (i = Hashpart; i < Tabsize; i++) {
X n = Table[i];
X if (n == 0 || (n->n_flag & NNET) == 0 || n->n_root)
X continue;
X dfs(n);
X }
X}
X
XSTATIC void
Xdfs(n)
X register node *n;
X{ register link *l;
X register node *next;
X
X n->n_flag |= INDFS;
X n->n_root = n;
X for (l = n->n_link; l; l = l->l_next) {
X next = l->l_to;
X if ((next->n_flag & NNET) == 0)
X continue;
X if ((next->n_flag & INDFS) == 0) {
X dfs(next);
X if (next->n_root != next)
X n->n_root = next->n_root;
X } else
X n->n_root = next->n_root;
X }
X n->n_flag &= ~INDFS;
X}
X
Xvoid
Xshowlinks()
X{ register link *l;
X register node *n;
X register long i;
X FILE *estream;
X
X if ((estream = fopen(Linkout, "w")) == 0)
X return;
X
X for (i = Hashpart; i < Tabsize; i++) {
X n = Table[i];
X if (n == 0 || n->n_link == 0)
X continue;
X for (l = n->n_link; l; l = l->l_next) {
X fputs(n->n_name, estream);
X putc('\t', estream);
X if (NETDIR(l) == LRIGHT)
X putc(NETCHAR(l), estream);
X fputs(l->l_to->n_name, estream);
X if (NETDIR(l) == LLEFT)
X putc(NETCHAR(l), estream);
X fprintf(estream, "(%d)\n", l->l_cost);
X }
X }
X (void) fclose(estream);
X}
X
X/*
X * n is node in heap, newp is candidate for new parent.
X * choose between newp and n->n_parent for parent.
X * return 0 to use newp, non-zero o.w.
X */
X#define NEWP 0
X#define OLDP 1
Xint
Xtiebreaker(n, newp)
X node *n;
X register node *newp;
X{ register char *opname, *npname, *name;
X register node *oldp;
X int metric;
X
X oldp = n->n_parent;
X
X /* given the choice, avoid gatewayed nets */
X if (GATEWAYED(newp) && !GATEWAYED(oldp))
X return OLDP;
X if (!GATEWAYED(newp) && GATEWAYED(oldp))
X return NEWP;
X
X /* look at real parents, not nets */
X while ((oldp->n_flag & NNET) && oldp->n_parent)
X oldp = oldp->n_parent;
X while ((newp->n_flag & NNET) && newp->n_parent)
X newp = newp->n_parent;
X
X /* use fewer hops, if possible */
X metric = height(oldp) - height(newp);
X if (metric < 0)
X return OLDP;
X if (metric > 0)
X return NEWP;
X
X /*
X * compare names
X */
X opname = oldp->n_name;
X npname = newp->n_name;
X name = n->n_name;
X
X /* use longest common prefix with parent */
X while (*opname == *name && *npname == *name && *name) {
X opname++;
X npname++;
X name++;
X }
X if (*opname == *name)
X return OLDP;
X if (*npname == *name)
X return NEWP;
X
X /* use shorter host name */
X metric = strlen(opname) - strlen(npname);
X if (metric < 0)
X return OLDP;
X if (metric > 0)
X return NEWP;
X
X /* use larger lexicographically */
X metric = strcmp(opname, npname);
X if (metric < 0)
X return NEWP;
X return OLDP;
X}
X
XSTATIC int
Xheight(n)
X register node *n;
X{ register int i = 0;
X
X if (n == 0)
X return 0;
X while ((n = n->n_parent) != 0)
X if (ISADOMAIN(n) || !(n->n_flag & NNET))
X i++;
X return i;
X}
X
X/*
X * return a copy of n ( == l->l_to). we rely on n and its copy
X * pointing to the same name string, which is kludgey, but works
X * because the name is non-volatile.
X */
X
X#define REUSABLE(n, l) (((n)->n_flag & NTERMINAL) == 0 \
X && ((n)->n_copy->n_flag & NTERMINAL) \
X && !((n)->n_copy->n_flag & NALIAS) \
X && !((l)->l_flag & LALIAS))
Xnode *
Xncopy(parent, l)
X register node *parent;
X register link *l;
X{ register node *n, *ncp;
X
X#ifdef DEBUG
X if (Vflag > 1)
X vprintf(stderr, "<%s> <- %s\n", l->l_to->n_name, parent->n_name);
X#endif
X n = l->l_to;
X if (REUSABLE(n, l)) {
X Nlink++;
X return n->n_copy; /* re-use */
X }
X NumNcopy++;
X l->l_to = ncp = newnode();
X ncp->n_name = n->n_name; /* nonvolatile */
X ncp->n_tloc = --Hashpart; /* better not be > 20% of total ... */
X if (Hashpart == Nheap)
X die("too many terminal links");
X Table[Hashpart] = ncp;
X ncp->n_copy = n->n_copy; /* circular list */
X n->n_copy = ncp;
X ncp->n_link = lcopy(parent, n);
X ncp->n_flag = (n->n_flag & ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT)) | NTERMINAL;
X return ncp;
X}
X
X/*
X * copy l, but don't include any links to parent.
X *
X * this is a little messier than it should be, because
X * of the funny test for ancestry, and because it wants
X * to be recursive, but the recursion might be very deep
X * (for a long link list), so it's done iteratively.
X */
XSTATIC link *
Xlcopy(parent, n)
X register node *parent, *n;
X{ register link *l, *lcp;
X link *first = 0, *last = 0;
X
X for (l = n->n_link; l != 0; l = l->l_next) {
X /* avoid vestigial descendants */
X if ((l->l_to->n_flag & MAPPED) != 0
X || ALTEREGO(l->l_to, parent))
X continue;
X#ifdef DEBUG
X if (Vflag > 1)
X vprintf(stderr, "\t-> %s\n", l->l_to->n_name);
X#endif
X NumLcopy++;
X lcp = newlink();
X *lcp = *l; /* struct copy */
X lcp->l_flag &= ~LTREE;
X if (ISANET(n))
X lcp->l_flag |= LTERMINAL;
X
X if (first == 0) {
X first = last = lcp;
X } else {
X last->l_next = lcp;
X last = lcp;
X }
X }
X if (last)
X last->l_next = 0;
X return first;
X}
END_OF_FILE
if test 8512 -ne `wc -c <'mapaux.c'`; then
echo shar: \"'mapaux.c'\" unpacked with wrong size!
fi
# end of 'mapaux.c'
fi
if test -f 'parse.y' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'parse.y'\"
else
echo shar: Extracting \"'parse.y'\" \(10671 characters\)
sed "s/^X//" >'parse.y' <<'END_OF_FILE'
X%{
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)parse.y 9.10 88/09/07";
X#endif /* lint */
X
X#include "def.h"
X
X/* scanner states (yylex, parse) */
X#define OTHER 0
X#define COSTING 1
X#define NEWLINE 2
X#define FILENAME 3
X
X/* exports */
Xlong Tcount;
Xextern void yyerror();
X
X/* imports */
Xextern node *addnode(), *addprivate();
Xextern void fixprivate(), alias(), deadlink(), deletelink();
Xextern link *addlink();
Xextern int strcmp();
Xextern char *strsave();
Xextern int optind;
Xextern char *Cfile, *Netchars, **Argv;
Xextern int Lineno, Argc;
X
X/* privates */
XSTATIC void fixnet(), adjust();
XSTATIC int yylex(), yywrap(), getword();
Xstatic int Scanstate = NEWLINE; /* scanner (yylex) state */
X
X/* flags for ys_flags */
X#define TERMINAL 1
X%}
X
X%union {
X node *y_node;
X Cost y_cost;
X char y_net;
X char *y_name;
X struct {
X node *ys_node;
X Cost ys_cost;
X short ys_flag;
X char ys_net;
X char ys_dir;
X } y_s;
X}
X
X%type <y_s> site asite
X%type <y_node> links aliases plist network nlist host nhost
X%type <y_node> usite delem dlist
X%type <y_cost> cost cexpr
X
X%token <y_name> SITE HOST STRING
X%token <y_cost> COST
X%token <y_net> NET
X%token EOL PRIVATE DEAD DELETE FILETOK ADJUST
X
X%left '+' '-'
X%left '*' '/'
X
X%%
Xmap : /* empty */
X | map EOL
X | map links EOL
X | map aliases EOL
X | map network EOL
X | map private EOL
X | map dead EOL
X | map delete EOL
X | map file EOL
X | map adjust EOL
X | error EOL
X ;
X
Xlinks : host site cost {
X struct link *l;
X
X l = addlink($1, $2.ys_node, $3, $2.ys_net, $2.ys_dir);
X if (GATEWAYED($2.ys_node))
X l->l_flag |= LGATEWAY;
X if ($2.ys_flag & TERMINAL)
X l->l_flag |= LTERMINAL;
X }
X | links ',' site cost {
X struct link *l;
X
X l = addlink($1, $3.ys_node, $4, $3.ys_net, $3.ys_dir);
X if (GATEWAYED($3.ys_node))
X l->l_flag |= LGATEWAY;
X if ($3.ys_flag & TERMINAL)
X l->l_flag |= LTERMINAL;
X }
X | links ',' /* benign error */
X ;
X
Xhost : HOST {$$ = addnode($1);}
X | PRIVATE {$$ = addnode("private");}
X | DEAD {$$ = addnode("dead");}
X | DELETE {$$ = addnode("delete");}
X | FILETOK {$$ = addnode("file");}
X | ADJUST {$$ = addnode("adjust");}
X ;
X
Xsite : asite {
X $$ = $1;
X $$.ys_net = DEFNET;
X $$.ys_dir = DEFDIR;
X }
X | NET asite {
X $$ = $2;
X $$.ys_net = $1;
X $$.ys_dir = LRIGHT;
X }
X | asite NET {
X $$ = $1;
X $$.ys_net = $2;
X $$.ys_dir = LLEFT;
X }
X ;
X
Xasite : SITE {
X $$.ys_node = addnode($1);
X $$.ys_flag = 0;
X }
X | '<' SITE '>' {
X Tcount++;
X $$.ys_node = addnode($2);
X $$.ys_flag = TERMINAL;
X }
X ;
X
Xaliases : host '=' SITE {alias($1, addnode($3));}
X | aliases ',' SITE {alias($1, addnode($3));}
X | aliases ',' /* benign error */
X ;
X
Xnetwork : nhost '{' nlist '}' cost {fixnet($1, $3, $5, DEFNET, DEFDIR);}
X | nhost NET '{' nlist '}' cost {fixnet($1, $4, $6, $2, LRIGHT);}
X | nhost '{' nlist '}' NET cost {fixnet($1, $3, $6, $5, LLEFT);}
X ;
X
Xnhost : '=' {$$ = 0; /* anonymous net */}
X | host '=' {$$ = $1; /* named net */}
X ;
X
Xnlist : SITE {$$ = addnode($1);}
X | nlist ',' SITE {
X node *n;
X
X n = addnode($3);
X if (n->n_net == 0) {
X n->n_net = $1;
X $$ = n;
X }
X }
X | nlist ',' /* benign error */
X ;
X
Xprivate : PRIVATE '{' plist '}' /* list of privates */
X | PRIVATE '{' '}' {fixprivate();} /* end scope of privates */
X ;
X
Xplist : SITE {addprivate($1)->n_flag |= ISPRIVATE;}
X | plist ',' SITE {addprivate($3)->n_flag |= ISPRIVATE;}
X | plist ',' /* benign error */
X ;
X
Xdead : DEAD '{' dlist '}';
X
Xdlist : delem
X | dlist ',' delem
X | dlist ',' /* benign error */
X ;
X
Xdelem : SITE {deadlink(addnode($1), (node *) 0);}
X | usite NET usite {deadlink($1, $3);}
X ;
X
Xusite : SITE {$$ = addnode($1);} ; /* necessary unit production */
X
Xdelete : DELETE '{' dellist '}';
X
Xdellist : delelem
X | dellist ',' delelem
X | dellist ',' /* benign error */
X ;
X
Xdelelem : SITE {
X node *n;
X
X n = addnode($1);
X deletelink(n, (node *) 0);
X n->n_flag |= ISPRIVATE;
X }
X | usite NET usite {deletelink($1, $3);}
X ;
X
Xfile : FILETOK '{' {Scanstate = FILENAME;} STRING {Scanstate = OTHER;} '}' {
X Lineno = 0;
X Cfile = strsave($4);
X }
X
Xadjust : ADJUST '{' adjlist '}' ;
X
Xadjlist : adjelem
X | adjlist ',' adjelem
X | adjlist ',' /* benign error */
X ;
X
Xadjelem : usite cost {adjust($1, $2);} ;
X
Xcost : {$$ = DEFCOST; /* empty -- cost is always optional */}
X | '(' {Scanstate = COSTING;} cexpr {Scanstate = OTHER;} ')'
X {$$ = $3;}
X ;
X
Xcexpr : COST
X | '-' cexpr {$$ = -$2;}
X | '(' cexpr ')' {$$ = $2;}
X | cexpr '+' cexpr {$$ = $1 + $3;}
X | cexpr '-' cexpr {$$ = $1 - $3;}
X | cexpr '*' cexpr {$$ = $1 * $3;}
X | cexpr '/' cexpr {
X if ($3 == 0)
X yyerror("zero divisor\n");
X else
X $$ = $1 / $3;
X }
X ;
X%%
X
Xvoid
X#ifdef YYDEBUG
X/*VARARGS1*/
Xyyerror(fmt, arg)
X char *fmt, *arg;
X#else
Xyyerror(s)
X char *s;
X#endif
X{
X /* a concession to bsd error(1) */
X fprintf(stderr, "\"%s\", ", Cfile);
X#ifdef YYDEBUG
X fprintf(stderr, "line %d: ", Lineno);
X fprintf(stderr, fmt, arg);
X putc('\n', stderr);
X#else
X fprintf(stderr, "line %d: %s\n", Lineno, s);
X#endif
X}
X
X/*
X * patch in the costs of getting on/off the network.
X *
X * for each network member on netlist, add links:
X * network -> member cost = 0;
X * member -> network cost = parameter.
X *
X * if network and member both require gateways, assume network
X * is a gateway to member (but not v.v., to avoid such travesties
X * as topaz!seismo.css.gov.edu.rutgers).
X *
X * note that members can have varying costs to a network, by suitable
X * multiple declarations. this is a feechur, albeit a useless one.
X */
XSTATIC void
Xfixnet(network, nlist, cost, netchar, netdir)
X register node *network;
X node *nlist;
X Cost cost;
X char netchar, netdir;
X{ register node *member, *nextnet;
X link *l;
X static int netanon = 0;
X char anon[25];
X
X if (network == 0) {
X sprintf(anon, "[unnamed net %d]", netanon++);
X network = addnode(anon);
X }
X network->n_flag |= NNET;
X
X /* insert the links */
X for (member = nlist ; member; member = nextnet) {
X
X /* network -> member, cost is 0 */
X l = addlink(network, member, (Cost) 0, netchar, netdir);
X if (GATEWAYED(network) && GATEWAYED(member))
X l->l_flag |= LGATEWAY;
X
X /* member -> network, cost is parameter */
X /* never ever ever crawl up from a domain*/
X if (!ISADOMAIN(network))
X (void) addlink(member, network, cost, netchar, netdir);
X
X nextnet = member->n_net;
X member->n_net = 0; /* clear for later use */
X }
X}
X
X/* scanner */
X
X#define QUOTE '"'
X#define STR_EQ(s1, s2) (s1[2] == s2[2] && strcmp(s1, s2) == 0)
X#define NLRETURN() {Scanstate = NEWLINE; return EOL;}
X
Xstatic struct ctable {
X char *cname;
X Cost cval;
X} ctable[] = {
X /* ordered by frequency of appearance in a "typical" dataset */
X {"DIRECT", 200},
X {"DEMAND", 300},
X {"DAILY", 5000},
X {"HOURLY", 500},
X {"DEDICATED", 100},
X {"EVENING", 2000},
X {"LOCAL", 25},
X {"LOW", 5}, /* baud rate, quality penalty */
X {"DEAD", MILLION},
X {"POLLED", 5000},
X {"WEEKLY", 30000},
X {"HIGH", -5}, /* baud rate, quality bonus */
X {"FAST", -80}, /* high speed (>= 9.6 kbps) modem */
X /* deprecated */
X {"ARPA", 100},
X {"DIALED", 300},
X {0, 0}
X};
X
XSTATIC int
Xyylex()
X{ static char retbuf[128]; /* for return to yacc part */
X register int c;
X register char *buf = retbuf;
X register struct ctable *ct;
X register Cost cost;
X char errbuf[128];
X
X if (feof(stdin) && yywrap())
X return EOF;
X
X /* count lines, skip over space and comments */
X if ((c = getchar()) == EOF)
X NLRETURN();
X
Xcontinuation:
X while (c == ' ' || c == '\t')
X if ((c = getchar()) == EOF)
X NLRETURN();
X
X if (c == '#')
X while ((c = getchar()) != '\n')
X if (c == EOF)
X NLRETURN();
X
X /* scan token */
X if (c == '\n') {
X Lineno++;
X if ((c = getchar()) != EOF) {
X if (c == ' ' || c == '\t')
X goto continuation;
X ungetc(c, stdin);
X }
X NLRETURN();
X }
X
X switch(Scanstate) {
X case COSTING:
X if (isdigit(c)) {
X cost = c - '0';
X for (c = getchar(); isdigit(c); c = getchar())
X cost = (cost * 10) + c - '0';
X ungetc(c, stdin);
X yylval.y_cost = cost;
X return COST;
X }
X
X if (getword(buf, c) == 0) {
X for (ct = ctable; ct->cname; ct++)
X if (STR_EQ(buf, ct->cname)) {
X yylval.y_cost = ct->cval;
X return COST;
X }
X sprintf(errbuf, "unknown cost (%s), using default", buf);
X yyerror(errbuf);
X yylval.y_cost = DEFCOST;
X return COST;
X }
X
X return c; /* pass the buck */
X
X case NEWLINE:
X Scanstate = OTHER;
X if (getword(buf, c) != 0)
X return c;
X /*
X * special purpose tokens.
X *
X * the "switch" serves the dual-purpose of recognizing
X * unquoted tokens only.
X */
X switch(c) {
X case 'p':
X if (STR_EQ(buf, "private"))
X return PRIVATE;
X break;
X case 'd':
X if (STR_EQ(buf, "dead"))
X return DEAD;
X if (STR_EQ(buf, "delete"))
X return DELETE;
X break;
X case 'f':
X if (STR_EQ(buf, "file"))
X return FILETOK;
X break;
X case 'a':
X if (STR_EQ(buf, "adjust"))
X return ADJUST;
X break;
X }
X
X yylval.y_name = buf;
X return HOST;
X
X case FILENAME:
X while (c != EOF && isprint(c)) {
X if (c == ' ' || c == '\t' || c == '\n' || c == '}')
X break;
X *buf++ = c;
X c = getchar();
X }
X if (c != EOF)
X ungetc(c, stdin);
X *buf = 0;
X yylval.y_name = retbuf;
X return STRING;
X }
X
X if (getword(buf, c) == 0) {
X yylval.y_name = buf;
X return SITE;
X }
X
X if (index(Netchars, c)) {
X yylval.y_net = c;
X return NET;
X }
X
X return c;
X}
X
X/*
X * fill str with the next word in [0-9A-Za-z][-._0-9A-Za-z]+ or a quoted
X * string that contains no newline. return -1 on failure or EOF, 0 o.w.
X */
XSTATIC int
Xgetword(str, c)
X register char *str;
X register int c;
X{
X if (c == QUOTE) {
X while ((c = getchar()) != QUOTE) {
X if (c == '\n') {
X yyerror("newline in quoted string\n");
X ungetc(c, stdin);
X return -1;
X }
X if (c == EOF) {
X yyerror("EOF in quoted string\n");
X return -1;
X }
X *str++ = c;
X }
X *str = 0;
X return 0;
X }
X
X /* host name must start with alphanumeric or `.' */
X if (!isalnum(c) && c != '.')
X return -1;
X
Xyymore:
X do {
X *str++ = c;
X c = getchar();
X } while (isalnum(c) || c == '.' || c == '_');
X
X if (c == '-' && Scanstate != COSTING)
X goto yymore;
X
X ungetc(c, stdin);
X *str = 0;
X return 0;
X}
X
XSTATIC int
Xyywrap()
X{ char errbuf[100];
X
X fixprivate(); /* munge private host definitions */
X Lineno = 1;
X while (optind < Argc) {
X if (freopen((Cfile = Argv[optind++]), "r", stdin) != 0)
X return 0;
X sprintf(errbuf, "%s: %s", Argv[0], Cfile);
X perror(errbuf);
X }
X freopen("/dev/null", "r", stdin);
X return -1;
X}
X
XSTATIC void
Xadjust(n, cost)
X node *n;
X Cost cost;
X{ link *l;
X
X n->n_cost += cost; /* cumulative */
X
X /* hit existing links */
X for (l = n->n_link; l; l = l->l_next) {
X if ((l->l_cost += cost) < 0) {
X char buf[100];
X
X l->l_flag |= LDEAD;
X sprintf(buf, "link to %s deleted with negative cost",
X l->l_to->n_name);
X yyerror(buf);
X }
X }
X}
END_OF_FILE
if test 10671 -ne `wc -c <'parse.y'`; then
echo shar: \"'parse.y'\" unpacked with wrong size!
fi
# end of 'parse.y'
fi
if test -f 'printit.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'printit.c'\"
else
echo shar: Extracting \"'printit.c'\" \(6907 characters\)
sed "s/^X//" >'printit.c' <<'END_OF_FILE'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)printit.c 9.4 89/02/07";
X#endif
X
X#include "def.h"
X
X/*
X * print the routes by traversing the shortest path tree in preorder.
X * use lots of char bufs -- profiling indicates this costs about 5 kbytes
X */
X
X/* exports */
Xextern void printit();
X
X/* imports */
Xextern int Cflag, Vflag, Dflag, Fflag;
Xextern node *Home;
Xextern char *Netchars;
Xextern void die();
Xextern int strlen();
X
X/* privates */
Xstatic link *Ancestor; /* for -f option */
XSTATIC void preorder(), setpath(), printhost(), printdomain();
XSTATIC char *hostpath();
XSTATIC int printable();
X
X/* in practice, even the longest paths are < 100 bytes */
X#define PATHSIZE 512
X
Xvoid
Xprintit()
X{ link *l;
X char pbuf[PATHSIZE];
X
X /* print home */
X if (Cflag)
X printf("%ld\t", (long) Home->n_cost);
X printf("%s\t%%s\n", Home->n_name);
X
X strcpy(pbuf, "%s");
X for (l = Home->n_link; l; l = l->l_next) {
X if (l->l_flag & LTREE) {
X l->l_flag &= ~LTREE;
X Ancestor = l;
X preorder(l, pbuf);
X strcpy(pbuf, "%s");
X }
X }
X fflush(stdout);
X fflush(stderr);
X}
X
X/*
X * preorder traversal of shortest path tree.
X */
XSTATIC void
Xpreorder(l, ppath)
X register link *l;
X char *ppath;
X{ register node *n;
X node *ncp; /* circular copy list */
X Cost cost;
X char npath[PATHSIZE];
X short p_dir; /* DIR bits of parent (for nets) */
X char p_op; /* net op of parent (for nets) */
X
X setpath(l, ppath, npath);
X n = l->l_to;
X if (printable(n)) {
X if (Fflag)
X cost = Ancestor->l_to->n_cost;
X else
X cost = n->n_cost;
X if (ISADOMAIN(n))
X printdomain(n, npath, cost);
X else if (!(n->n_flag & NNET)) {
X printhost(n, npath, cost);
X }
X n->n_flag |= PRINTED;
X for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy)
X ncp->n_flag |= PRINTED;
X }
X
X /* prepare routing bits for domain members */
X p_dir = l->l_flag & LDIR;
X p_op = l->l_netop;
X
X /* recursion */
X for (l = n->n_link; l; l = l->l_next) {
X if (!(l->l_flag & LTREE))
X continue;
X /* network member inherits the routing syntax of its gateway */
X if (ISANET(n)) {
X l->l_flag = (l->l_flag & ~LDIR) | p_dir;
X l->l_netop = p_op;
X }
X l->l_flag &= ~LTREE;
X preorder(l, npath);
X }
X}
X
XSTATIC int
Xprintable(n)
X register node *n;
X{ node *ncp;
X link *l;
X
X if (n->n_flag & PRINTED)
X return 0;
X
X /* is there a cheaper copy? */
X for (ncp = n->n_copy; n != ncp; ncp = ncp->n_copy) {
X if (!(ncp->n_flag & MAPPED))
X continue; /* unmapped copy */
X
X if (n->n_cost > ncp->n_cost)
X return 0; /* cheaper copy */
X
X if (n->n_cost == ncp->n_cost && !(ncp->n_flag & NTERMINAL))
X return 0; /* synthetic copy */
X }
X
X /* will a domain route suffice? */
X if (Dflag && !ISANET(n) && ISADOMAIN(n->n_parent)) {
X /*
X * are there any interesting links? a link
X * is interesting if it doesn't point back
X * to the parent, and is not an alias.
X */
X
X /* check n */
X for (l = n->n_link; l; l = l->l_next) {
X if (l->l_to == n->n_parent)
X continue;
X if (!(l->l_flag & LALIAS))
X return 1;
X }
X
X /* check copies of n */
X for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy) {
X for (l = ncp->n_link; l; l = l->l_next) {
X if (l->l_to == n->n_parent)
X continue;
X if (!(l->l_flag & LALIAS))
X return 1;
X }
X }
X
X /* domain route suffices */
X return 0;
X }
X return 1;
X}
X
XSTATIC void
Xsetpath(l, ppath, npath)
X link *l;
X register char *ppath, *npath;
X{ register node *next, *parent;
X char netchar;
X
X next = l->l_to;
X parent = next->n_parent;
X netchar = NETCHAR(l);
X
X /* for magic @->% conversion */
X if (parent->n_flag & ATSIGN)
X next->n_flag |= ATSIGN;
X
X /*
X * i've noticed that distant gateways to domains frequently get
X * ...!gateway!user@dom.ain wrong. ...!gateway!user%dom.ain
X * seems to work, so if next is a domain and the parent is
X * not the local host, force a magic %->@ conversion. in this
X * context, "parent" is the nearest ancestor that is not a net.
X */
X while (ISANET(parent))
X parent = parent->n_parent;
X if (ISADOMAIN(next) && parent != Home)
X next->n_flag |= ATSIGN;
X
X /*
X * special handling for nets (including domains) and aliases.
X * part of the trick is to treat aliases to domains as 0 cost
X * links. (the author believes they should be declared as such
X * in the input, but the world disagrees).
X */
X if (ISANET(next) || ((l->l_flag & LALIAS) && !ISADOMAIN(parent))) {
X strcpy(npath, ppath);
X return;
X }
X
X if (netchar == '@')
X if (next->n_flag & ATSIGN)
X netchar = '%'; /* shazam? shaman? */
X else
X next->n_flag |= ATSIGN;
X
X /* remainder should be a sprintf -- foo on '%' as an operator */
X for ( ; (*npath = *ppath) != 0; ppath++) {
X if (*ppath == '%') {
X switch(ppath[1]) {
X case 's':
X ppath++;
X npath = hostpath(npath, l, netchar);
X break;
X
X case '%':
X *++npath = *++ppath;
X npath++;
X break;
X
X default:
X die("unknown escape in setpath");
X break;
X }
X } else
X npath++;
X }
X}
X
XSTATIC char *
Xhostpath(path, l, netchar)
X register char *path;
X register link *l;
X char netchar;
X{ register node *prev;
X
X prev = l->l_to->n_parent;
X if (NETDIR(l) == LLEFT) {
X /* host!%s */
X strcpy(path, l->l_to->n_name);
X path += strlen(path);
X while (ISADOMAIN(prev)) {
X strcpy(path, prev->n_name);
X path += strlen(path);
X prev = prev->n_parent;
X }
X *path++ = netchar;
X if (netchar == '%')
X *path++ = '%';
X *path++ = '%';
X *path++ = 's';
X } else {
X /* %s@host */
X *path++ = '%';
X *path++ = 's';
X *path++ = netchar;
X if (netchar == '%')
X *path++ = '%';
X strcpy(path, l->l_to->n_name);
X path += strlen(path);
X while (ISADOMAIN(prev)) {
X strcpy(path, prev->n_name);
X path += strlen(path);
X prev = prev->n_parent;
X }
X }
X return path;
X}
X
XSTATIC void
Xprinthost(n, path, cost)
X register node *n;
X char *path;
X Cost cost;
X{
X if (n->n_flag & PRINTED)
X die("printhost called twice");
X n->n_flag |= PRINTED;
X /* skip private hosts */
X if ((n->n_flag & ISPRIVATE) == 0) {
X if (Cflag)
X printf("%ld\t", (long) cost);
X fputs(n->n_name, stdout);
X putchar('\t');
X puts(path);
X }
X}
X
XSTATIC void
Xprintdomain(n, path, cost)
X register node *n;
X char *path;
X Cost cost;
X{ node *p;
X
X if (n->n_flag & PRINTED)
X die("printdomain called twice");
X n->n_flag |= PRINTED;
X
X /*
X * print a route for dom.ain if it is a top-level domain, unless
X * it is private.
X *
X * print a route for sub.dom.ain only if all its ancestor dom.ains
X * are private and sub.dom.ain is not private.
X */
X if (!ISADOMAIN(n->n_parent)) {
X /* top-level domain */
X if (n->n_flag & ISPRIVATE) {
X vprintf(stderr, "ignoring private top-level domain %s\n", n->n_name);
X return;
X }
X } else {
X /* subdomain */
X for (p = n->n_parent; ISADOMAIN(p); p = p->n_parent)
X if (!(p->n_flag & ISPRIVATE))
X return;
X if (n->n_flag & ISPRIVATE)
X return;
X }
X
X /* print it (at last!) */
X if (Cflag)
X printf("%ld\t", (long) cost);
X do {
X fputs(n->n_name, stdout);
X n = n->n_parent;
X } while (ISADOMAIN(n));
X putchar('\t');
X puts(path);
X}
END_OF_FILE
if test 6907 -ne `wc -c <'printit.c'`; then
echo shar: \"'printit.c'\" unpacked with wrong size!
fi
# end of 'printit.c'
fi
echo shar: End of archive 2 \(of 3\).
cp /dev/null ark2isdone
MISSING=""
for I in 1 2 3 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked all 3 archives.
rm -f ark[1-9]isdone
else
echo You still must unpack the following archives:
echo " " ${MISSING}
fi
exit 0
exit 0 # Just in case...
--
Please send comp.sources.unix-related mail to rsalz@uunet.uu.net.
Use a domain-based address or give alternate paths, or you may lose out.