rsalz@uunet.UU.NET (Rich Salz) (10/10/87)
Submitted-by: honey@CITI.UMICH.EDU (Peter Honeyman)
Posting-number: Volume 12, Issue 1
Archive-name: pathalias9/part01
[ This is the latest and greatest pathalias, and other tools. It may
well be the last one peter ever works on, judging from his off-line
remarks... :-) This version has had several bugs fixed, and has
been tested on BSD, Sun, 3B, SysV, Mac, etc. MOST IMPORTANTLY:
it has several new features, and additions to the input syntax, that
you will need for all future UUCP maps. Finally, had I an
irrelevant axe to grind, I'd point out that this code has no
copyright and is in the public domain. --r$ ]
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 1 (of 2)."
# Contents: CHANGES MANIFEST Makefile README addlink.c arpa-privates
# config.h def.h local.c main.c make.honey makedb.c mapaux.c mem.c
# printit.c
# Wrapped by rsalz@uunet on Mon Oct 5 22:45:08 1987
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f CHANGES -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"CHANGES\"
else
echo shar: Extracting \"CHANGES\" \(941 characters\)
sed "s/^X//" >CHANGES <<'END_OF_CHANGES'
X-- mod.sources, 10/87 -- version 9
XTerminal edges and domains (<host> syntax and -D option).
XDead hosts and edges in the input stream.
XEmpty private list ends scope of privates.
XFirst hop cost in output (-f option).
XPenalize deprecated hosts (-a option).
X
X-- mod.sources, 4.3bsd, 1/86 -- version 8
XImproved alias treatment.
XRoutes to domain gateways.
XLeading dot in name implies domain.
XLink/host tracing (-t option).
XUse getopt().
X
X-- mod.sources, 8/85 -- version 7
XPrivate hosts documented.
XHomegrown scanner -- it was true what they said about lex.
XMakedb.
XDomains and gateways.
XDEAD back link.
X
X-- net.sources, 1/85 -- version 6
XNo ! in dbm key.
XNetwork character must be one of !@%: -- dot is dead.
XPrivate hosts.
XDiscourage hybrid addresses.
XMagic @ <-> % rule.
X
X-- 1983-1984 -- version 5
XReverse sense of the -c (cost) flag.
XUse cheapest among duplicate links.
XElide network names in output.
X
X-- epoch (smb version) -- versions 1-4
END_OF_CHANGES
if test 941 -ne `wc -c <CHANGES`; then
echo shar: \"CHANGES\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f MANIFEST -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"MANIFEST\"
else
echo shar: Extracting \"MANIFEST\" \(714 characters\)
sed "s/^X//" >MANIFEST <<'END_OF_MANIFEST'
X File Name Archive # Description
X-----------------------------------------------------------
X CHANGES 1
X MANIFEST 1 This shipping list
X Makefile 1
X README 1
X addlink.c 1
X addnode.c 2
X arpa-privates 1
X arpatxt.c 2
X config.h 1
X def.h 1
X local.c 1
X main.c 1
X make.honey 1
X makedb.c 1
X mapaux.c 1
X mapit.c 2
X mem.c 1
X parse.y 2
X pathalias.1 2
X printit.c 1
END_OF_MANIFEST
if test 714 -ne `wc -c <MANIFEST`; then
echo shar: \"MANIFEST\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f Makefile -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"Makefile\"
else
echo shar: Extracting \"Makefile\" \(1364 characters\)
sed "s/^X//" >Makefile <<'END_OF_Makefile'
X#!/bin/make -f
X# pathalias -- by steve bellovin, as told to peter honeyman
X
X### configuration section
X###
X# if you can't or don't intend to use dbm files,
X# don't bother with DBM or makedb
XDBM = -ldbm
X# or if you roll your own ...
X# DBM = dbm.o
X###
X# where is getopt (if not in the c library)?
X# GETOPT = getopt.o
X### end of configuration section
X
X
XCC = cc
XCFLAGS = -O -DSTATIC=static
XLDFLAGS = -s $(GETOPT)
XYFLAGS = -d
X
XOBJ = addlink.o addnode.o local.o main.o mapit.o mapaux.o mem.o parse.o printit.o
XHDRS = def.h config.h
XCSRC = addlink.c addnode.c local.c main.c mapit.c mapaux.c mem.c printit.c
XLSRC = $(CSRC) parse.c
XSRC = $(CSRC) parse.y makedb.c arpatxt.c
X
Xpathalias: $(OBJ)
X $(CC) $(OBJ) $(LDFLAGS) -o pathalias
X
Xall: pathalias makedb arpatxt
X
X$(OBJ): $(HDRS)
X
Xparse.c: parse.y $(HDRS)
X $(YACC) $(YFLAGS) parse.y
X mv y.tab.c parse.c
X
Xmakedb: makedb.o
X $(CC) makedb.o $(LDFLAGS) $(DBM) -o makedb
X
Xmakedb.o: config.h
X
Xarpatxt: arpatxt.o
X $(CC) arpatxt.o $(LDFLAGS) -o arpatxt
X
Xclean:
X rm -f *.o y.tab.? parse.c
X
Xclobber: clean
X rm -f pathalias makedb arpatxt
X
Xtags: $(SRC) $(HDRS)
X ctags -w $(HDRS) $(SRC)
X
Xbundle:
X @bundle README CHANGES pathalias.1 Makefile ${HDRS} ${SRC}
X
Xlint: $(LSRC)
X lint $(CFLAGS) $(LSRC)
X lint makedb.c
X lint arpatxt.c
X
Xinstall:
X @echo "install pathalias, makedb, arpatxt, and pathalias.1"
X @echo "according to local conventions"
END_OF_Makefile
if test 1364 -ne `wc -c <Makefile`; then
echo shar: \"Makefile\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f README -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"README\"
else
echo shar: Extracting \"README\" \(1073 characters\)
sed "s/^X//" >README <<'END_OF_README'
XFrom citi!honey Sun Oct 4 23:30 EDT 1987
XDate: 04 Oct 1987 23:30 EDT
XFrom: honey@citi.umich.edu
XTo: whom it may concern
XSubject: pathalias compilation instructions
X
Xedit config.h
Xmake
X
Xif getopt is undefined, obtain a copy from usenet group
Xcomp.sources.unix and adjust Makefile.
X
Xpathalias input is regularly published in usenet group comp.mail.maps.
X
X peter
X
Xps: pathalias, written by steve bellovin and peter honeyman, is in the
X public domain, and may be used by any person or organization, in
X any way and for any purpose.
X
Xpps: There is no warranty of merchantability nor any warranty of fit-
X ness for a particular purpose nor any other warranty, either ex-
X press or implied, as to the accuracy of the enclosed materials or
X as to their suitability for any particular purpose. Accordingly,
X the authors assume no responsibility for their use by the recipi-
X ent. Further, the authors assume no obligation to furnish any
X assistance of any kind whatsoever, or to furnish any additional
X information or documentation.
END_OF_README
if test 1073 -ne `wc -c <README`; then
echo shar: \"README\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f addlink.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"addlink.c\"
else
echo shar: Extracting \"addlink.c\" \(4693 characters\)
sed "s/^X//" >addlink.c <<'END_OF_addlink.c'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)addlink.c 9.1 87/10/04";
X#endif /* lint */
X
X#include "def.h"
X
X/* exports */
Xextern link *addlink();
Xextern void deadlink(), atrace();
Xextern int tracelink();
Xchar *Netchars = "!:@%"; /* sparse, but sufficient */
Xlong Lcount; /* how many edges? */
X
X
X/* imports */
Xextern int Tflag, Dflag;
Xextern link *newlink();
Xextern node *addnode();
Xextern void yyerror(), die();
X
X/* privates */
XSTATIC void netbits(), ltrace(), ltrprint();
Xstatic link *Trace[NTRACE];
Xstatic int Tracecount;
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 if (Tflag)
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 (!(l->l_flag & LDEAD))
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 l->l_cost = cost + from->n_cost; /* add penalty */
X if (netchar == 0) {
X netchar = DEFNET;
X netdir = DEFDIR;
X }
X netbits(l, netchar, netdir);
X if (Dflag && ISADOMAIN(from) && !ISADOMAIN(to))
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
XSTATIC void
Xltrace(from, to, cost, netchar, netdir)
X node *from, *to;
X Cost cost;
X char netchar, netdir;
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 && (from == (node *) l->l_from || to == (node *) l->l_from))
X || (from == (node *) l->l_from && to == l->l_to)
X || (to == (node *) l->l_from && from == l->l_to)) {
X ltrprint(from, to, cost, netchar, netdir);
X return;
X }
X }
X}
X
X/* print a trace item */
XSTATIC void
Xltrprint(from, to, cost, netchar, netdir)
X node *from, *to;
X Cost cost;
X char netchar;
X char netdir;
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)", cost);
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
X#define EQ(n1, n2) strcmp(n1->n_name, n2->n_name) == 0
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}
END_OF_addlink.c
if test 4693 -ne `wc -c <addlink.c`; then
echo shar: \"addlink.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f arpa-privates -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"arpa-privates\"
else
echo shar: Extracting \"arpa-privates\" \(4636 characters\)
sed "s/^X//" >arpa-privates <<'END_OF_arpa-privates'
X###
X#host map file ([map file ...] for unregistered hosts)
X#
Xabbott usa.ca
Xabel usa.ca
Xachilles usa.nj.a
Xacorn gbr
Xadam [usa.il.a]
Xadams swe
Xadmin [usa.ut]
Xads [usa.ca]
Xai gbr
Xalamo usa.tx
Xalpha usa.in
Xamc usa.wa
Xames usa.ca (amazingly ...)
Xamon swe
Xamos [usa.ca?]
Xanimal usa.nj.a
Xanubis usa.il
Xapollo usa.ma
Xaramis usa.nj
Xargus usa.nj
Xariadne grc
Xarthur [usa.oh]
Xasgard usa.or
Xastro [usa.ma]
Xathena usa.or
Xatlantis usa.nj.a
Xatlas usa.oh.a
Xaurora [usa.ca]
Xb21 deu
Xbach [usa.nc]
Xbalder [usa.oh]
Xbashful [usa.nc]
Xbeaver [usa.pa?]
Xbishop gbr
Xbluebell usa.ca
Xbluto [usa.tx?]
Xbonnie usa.nj.a
Xboojum usa.nj.a
Xbosco [esp]
Xbourbaki usa.il
Xbozo usa.nj.a
Xbrahms asia.japan
Xcalico usa.ny
Xcantor [usa.il]
Xcapella swe
Xcastor usa.nj.a
Xcdr [usa.mi]
Xcerberus [usa.il?]
Xchaos usa.ok
Xcirce usa.nj.a
Xclara usa.ny
Xclark usa.nj.a
Xcleo usa.nj.b
Xclutx [usa.fl?, usa.ny?]
Xcogito usa.nj.a
Xcolby usa.me
Xcomet usa.or
Xcondor usa.ma
Xcottage [gbr]
Xcsab [usa.il?]
Xcsd1 usa.ny
Xcsd2 usa.ny
Xcsvax [usa.mn]
Xcti usa.ca
Xdanger can.ab
Xdarwin can.on
Xdcn1 [usa.ca?]
Xdeimos [usa.il.a, usa.a]
Xdelphi ita
Xdev usa.md
Xdewey usa.nj.a
Xdickens [can.bc?]
Xdiomedes usa.nj.a
Xdoc [usa.nc]
Xdopey [usa.nc]
Xea usa.ok
Xearth usa.nj.a
Xed gbr
Xeddie [gbr]
Xedith [usa.oh]
Xeinstein usa.ny
Xelse [jpn]
Xems usa.mn
Xerc gbr
Xernie [usa.oh]
Xescher usa.ca
Xeuclid [gbr]
Xeuler usa.nj
Xeunice usa.fl
Xeuropa [usa.ri]
Xexcalibur usa.pa
Xfelix usa.ca
Xfermat usa.nj
Xfifi [usa.tx]
Xfisher usa.nj
Xflash [can.on]
Xfloyd usa.nj.a
Xfluke usa.wa
Xforest [usa.tx]
Xfred usa.co
Xfrog usa.ma
Xgalileo [usa.mo]
Xgamma usa.nj.b
Xgandalf can.on
Xgarfield can.nf
Xgateway usa.ny
Xgizmo [usa.ca?, usa.il?]
Xgodot usa.nc
Xgolem usa.ca
Xgonzo [usa.a?, usa.ca?]
Xgould usa.fl
Xgranite [usa.nh]
Xgreen usa.md
Xgrendel usa.nj.a
Xgrumpy [usa.ga.a, usa.il.a, usa.a, usa.nc]
Xhamlet [usa.nj.a]
Xhappy [usa.nc]
Xhaven usa.ct
Xhawaii usa.hi
Xhawk [usa.ca?
Xhelios [usa.ca]
Xhermes usa.il.a
Xhilbert usa.wa
Xhollywood [usa.ca?]
Xhorus [usa.ca?]
Xhottub [usa.ca]
Xhub [usa.tx]
Xhudson usa.nj.a
Xhuey usa.nj.a
Xicarus usa.nj.a
Xicsd usa.fl.a
Xindra usa.nj.b
Xintech [gbr]
Xio usa.nj.a
Xipac [usa.az?, usa.ca?]
Xiris usa.ri
Xisis usa.co
Xjack usa.ca
Xjaguar [usa.il.a]
Xjanus [usa.ca]
Xjason usa.ny
Xjenkins [usa.tx]
Xjim [usa.ga.a, usa.il.a]
Xjoey usa.pa.a
Xjove usa.ny
Xjuliet [usa.nj.a, usa.nj]
Xkaos [usa.il]
Xkermit usa.nj.a
Xkobold [usa.ca]
Xkronos grc
Xlafite usa.nj.b
Xlarry [usa.tx, usa.ma]
Xleg [fra]
Xlego dmk
Xleopard usa.nj.b
Xlilac kor
Xlinus usa.ma
Xlion usa.nj.b
Xlouie usa.nj.a
Xludwig usa.nj.a
Xlynx [usa.ca]
Xmadvax usa.ca
Xmagic [usa.mo, usa.nj.b]
Xmanx usa.nj
Xmariner usa.nj.a
Xmarvin gbr
Xmath [usa.or]
Xmaui usa.va
Xmax usa.nj.a
Xmaxwell usa.mo
Xmedea [[usa.mi]]
Xmegalon deu
Xmerlin usa.nj.a
Xmhuxc usa.nj.a
Xmickey [usa.nj]
Xmilo usa.md
Xminnie usa.co
Xmiranda usa.nj.a
Xnemesis [usa.ca]
Xnemo [usa.mo]
Xnetman usa.oh.a
Xnexus [can.ab, fra]
Xnyquist usa.nj.b
Xoac usa.nj.a
Xoak [usa.ct]
Xocean [usa.ca]
Xodin usa.nj.a
Xomega usa.nj.a
Xopus [usa.a, usa.ga, usa.il.a]
Xorion usa.nj.a
Xorville usa.ny
Xosiris usa.md
Xotto usa.nv
Xoz usa.wa
Xpallas usa.il
Xpandora usa.nj.b
Xpelican usa.ca
Xphobos usa.nj.a
Xphoenix usa.nj.a
Xphysics usa.nj.a
Xpilchuck usa.wa
Xpine kor
Xpioneer [usa.il.a]
Xplasma usa.pa.a
Xpluto usa.ny
Xpolaris usa.ny
Xpolya usa.nj.a
Xposeidon usa.nj.a
Xpostel nld
Xpresto usa.md
Xpriam [che]
Xprinceton usa.nj (stupid!)
Xprism usa.nj
Xprometheus usa.md
Xpsc usa.md
Xpsyche usa.nc
Xpuma gbr
Xqat [usa.tx]
Xra usa.ny
Xrainier swe
Xralph [usa.tx]
Xranger [usa.il.a]
Xredwood [usa.ca]
Xridge usa.ca
Xrigel usa.ny
Xrose usa.nj.a
Xrover [usa.ma]
Xrsch [usa.ma?]
Xsabre usa.nj.b
Xsal [swe]
Xsales usa.a
Xsamwise usa.nj.a
Xsaturn usa.oh.a
Xscience [usa.nj.b]
Xsds [usa.mn]
Xshark usa.or
Xshrike [usa.tx]
Xsimon [usa.il?]
Xsleepy [usa.nc]
Xsneezy [usa.wi]
Xsnoopy [gbr]
Xsol [usa.il.a, usa.ny, gbr]
Xsolar usa.nm
Xspam usa.nj
Xsphinx usa.il
Xstar [usa.ca?, usa.il.a?, usa.nj.b?]
Xstars can.ns
Xstc gbr
Xstuart [usa.md]
Xsunrise usa.nj
Xsuper usa.md
Xsurya usa.ca
Xtb usa.ok.a
Xterminus [usa.oh?, usa.wi?]
Xterra usa.ma
Xthor dmk
Xthunder can.on
Xthyme usa.ca
Xtiger usa.nj
Xtitan usa.ca
Xtrillian usa.nj.a
Xtriton [jpn, usa.or]
Xtut fin
Xubvax usa.ca
Xulysses usa.nj.a
Xunh usa.nh
Xunicorn usa.nj.a
Xunix [usa.or]
Xunix3 [usa.ga.a, usa.il.a]
Xusadhq2 [usa.ca?]
Xusafa [usa.co?, usa.fl?, usa.nh?]
Xvalid [usa.ca]
Xvax1 [gbr]
Xvax2 [gbr]
Xvega swe
Xvenice usa.ca.a
Xvictoria can.on
Xvortex usa.ca
Xvoyager [usa.il.a]
Xwang usa.ma
Xwayback usa.nj.a
Xwimsey usa.nj.a
Xwombat usa.nj.a
Xzaphod can.sk
Xzeta usa.nj.b
Xzorac can.on
END_OF_arpa-privates
if test 4636 -ne `wc -c <arpa-privates`; then
echo shar: \"arpa-privates\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f config.h -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"config.h\"
else
echo shar: Extracting \"config.h\" \(2061 characters\)
sed "s/^X//" >config.h <<'END_OF_config.h'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X
X#undef STRCHR /* have strchr -- system v and many others */
X
X#undef UNAME /* have uname() -- probably system v or 8th ed. */
X#undef MEMSET /* have memset() -- probably system v or 8th ed. */
X
X#define GETHOSTNAME /* have gethostname() -- probably bsd */
X#define BZERO /* have bzero() -- probably bsd */
X
X/* default place for dbm output of makedb (or use -o at run-time) */
X#define ALIASDB "/usr/local/lib/palias"
X
X
X
X/**************************************************************************
X * *
X * +--------------------------------------------------------------------+ *
X * | | *
X * | END OF CONFIGURATION SECTION | *
X * | | *
X * | EDIT NO MORE | *
X * | | *
X * +--------------------------------------------------------------------+ *
X * *
X **************************************************************************/
X
X#ifdef MAIN
X#ifndef lint
Xstatic char *c_sccsid = "@(#)config.h 9.1 87/10/04";
X#endif /*lint*/
X#endif /*MAIN*/
X
X/*
X * malloc/free fine tuned for pathalias.
X *
X * MYMALLOC should work everwhere, so it's not a configuration
X * option (anymore). nonetheless, if you're getting strange
X * core dumps (or panics!), comment out the following manifest,
X * and use the inferior C library malloc/free.
X *
X * please report problems to citi!honey or honey@citi.umich.edu.
X */
X#define MYMALLOC /**/
X
X#ifdef MYMALLOC
X#define malloc mymalloc
X#define calloc(n, s) malloc ((n)*(s))
X#define free(s)
X#define cfree(s)
Xextern char *memget();
X#else /* !MYMALLOC */
Xextern char *calloc();
X#endif /* MYMALLOC */
X
X#ifdef STRCHR
X#define index strchr
X#define rindex strrchr
X#else
X#define strchr index
X#define strrchr rindex
X#endif
X
X#ifdef BZERO
X#define strclear(s, n) ((void) bzero((s), (n)))
X#else /*!BZERO*/
X
X#ifdef MEMSET
Xextern char *memset();
X#define strclear(s, n) ((void) memset((s), 0, (n)))
X#else /*!MEMSET*/
Xextern void strclear();
X#endif /*MEMSET*/
X
X#endif /*BZERO*/
X
Xextern char *malloc();
Xextern char *strcpy(), *index(), *rindex();
END_OF_config.h
if test 2061 -ne `wc -c <config.h`; then
echo shar: \"config.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f def.h -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"def.h\"
else
echo shar: Extracting \"def.h\" \(4366 characters\)
sed "s/^X//" >def.h <<'END_OF_def.h'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X
X#ifndef lint
X#ifdef MAIN
Xstatic char *h_sccsid = "@(#)def.h 9.1 87/10/04";
X#endif /*MAIN*/
X#endif /*lint*/
X
X#include <stdio.h>
X#include <ctype.h>
X#include "config.h"
X
Xtypedef long Cost;
Xtypedef struct node node;
Xtypedef struct link link;
X
X#ifdef lint
X#define vprintf fprintf
X#else /*!lint -- this gives null effect warning*/
X/* because it's there ... */
X#define vprintf !Vflag ? 0 : fprintf
X#endif /*lint*/
X
X#define NTRACE 16 /* can trace up to NTRACE hosts/links */
X
X/* scanner states (yylex, parse) */
X#define OTHER 0
X#define COSTING 1
X#define NEWLINE 2
X
X/* flags for n_flag */
X#define ISPRIVATE 0x0001 /* invisible outside its definition file */
X#define NALIAS 0x0002 /* heaped as an alias */
X#define ATSIGN 0x0004 /* seen an at sign? used for magic @/% rules */
X#define MAPPED 0x0008 /* extracted from heap */
X#define NDEAD 0x0010 /* out links are dead */
X#define HASLEFT 0x0020 /* has a left side net character */
X#define HASRIGHT 0x0040 /* route has a right side net character */
X#define NNET 0x0080 /* network pseudo-host */
X#define INDFS 0x0100 /* used when removing net cycles (for -g) */
X#define DUMP 0x0200 /* we have dumped this net's edges (for -g) */
X#define PRINTED 0x0400 /* this host has been printed */
X#define NTERMINAL 0x0800 /* heaped as terminal edge (or alias thereto) */
X
X#define ISADOMAIN(n) ((n)->n_name[0] == '.')
X#define ISANET(n) (((n)->n_flag & NNET) || ISADOMAIN(n))
X#define DEADHOST(n) ((((n)->n_flag & (NNET | NDEAD)) == NDEAD) || (n->n_flag & NTERMINAL))
X#define GATEWAYED(n) (((n)->n_flag & (NNET | NDEAD)) == (NNET | NDEAD) || ISADOMAIN(n))
X
X#ifndef DEBUG
X/*
X * save some space in nodes -- there are > 10,000 allocated!
X */
X
X#define n_root un1.nu_root
X#define n_net un1.nu_net
X#define n_copy un1.nu_copy
X
X#define n_private un2.nu_priv
X#define n_parent un2.nu_par
X
X/* WARNING: if > 2^16 nodes, type of n_tloc must change */
Xstruct node {
X char *n_name; /* host name */
X link *n_link; /* adjacency list */
X Cost n_cost; /* cost to this host */
X union {
X node *nu_net; /* others in this network (parsing) */
X node *nu_root; /* root of net cycle (graph dumping) */
X node *nu_copy; /* circular copy list (mapping) */
X } un1;
X union {
X node *nu_priv; /* other privates in this file (parsing) */
X node *nu_par; /* parent in shortest path tree (mapping) */
X } un2;
X unsigned short n_tloc; /* back ptr to heap/hash table */
X unsigned short n_flag; /* see manifests above */
X};
X
X#endif /*DEBUG*/
X
X#define DEFNET '!' /* default network operator */
X#define DEFDIR LLEFT /* host on left is default */
X#define DEFCOST ((Cost) 4000) /* default cost of a link */
X#define INF ((Cost) 30000000) /* infinitely expensive link */
X#define DEFPENALTY ((Cost) 200) /* default avoidance cost */
X
X/* data structure for adjacency list representation */
X
X/* flags for l_dir */
X
X#define NETDIR(l) ((l)->l_flag & LDIR)
X#define NETCHAR(l) ((l)->l_netop)
X
X#define LDIR 0x0008 /* 0 for left, 1 for right */
X#define LRIGHT 0x0000 /* user@host style */
X#define LLEFT 0x0008 /* host!user style */
X
X#define LDEAD 0x0010 /* this link is dead */
X#define LALIAS 0x0020 /* this link is an alias */
X#define LTREE 0x0040 /* member of shortest path tree */
X#define LGATEWAY 0x0080 /* this link is a gateway */
X#define LTERMINAL 0x0100 /* this link is terminal */
X
X#ifndef DEBUG
X/*
X * borrow a field for link/node tracing. there's a shitload of
X * edges -- every word counts. only so much squishing is possible:
X * alignment dictates that the size be a multiple of four.
X */
X
X#define l_next un.lu_next
X#define l_from un.lu_from
X
Xstruct link {
X node *l_to; /* adjacent node */
X Cost l_cost; /* edge cost */
X union {
X link *lu_next; /* rest of adjacency list (not tracing) */
X node *lu_from; /* source node (tracing) */
X } un;
X short l_flag; /* right/left syntax, flags */
X char l_netop; /* network operator */
X};
X
X#endif /*DEBUG*/
X
X#ifdef DEBUG
X/*
X * flattening out the unions makes it easier
X * to debug (when pi is unavailable).
X */
Xstruct node {
X char *n_name;
X link *n_link;
X Cost n_cost;
X node *n_net;
X node *n_root;
X node *n_copy;
X node *n_private;
X node *n_parent;
X unsigned short n_tloc;
X unsigned short n_flag;
X};
Xstruct link {
X node *l_to;
X Cost l_cost;
X link *l_next;
X node *l_from;
X short l_flag;
X char l_netop;
X};
X#endif /*DEBUG*/
END_OF_def.h
if test 4366 -ne `wc -c <def.h`; then
echo shar: \"def.h\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f local.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"local.c\"
else
echo shar: Extracting \"local.c\" \(1420 characters\)
sed "s/^X//" >local.c <<'END_OF_local.c'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)local.c 9.1 87/10/04";
X#endif /* lint */
X
X#include <stdio.h>
X#include "config.h"
X
X#ifdef UNAME
X#include <sys/utsname.h>
X
Xchar *
Xlocal()
X{
X static struct utsname utsname;
X
X uname(&utsname);
X return(utsname.nodename);
X}
X
X#else /* !UNAME */
X
Xchar *
Xlocal()
X{
X static char lname[64];
X
X gethostname(lname, sizeof(lname));
X return(lname);
X}
X
X#ifndef GETHOSTNAME
X
Xstatic
Xgethostname(name, len)
Xchar *name;
X{
X FILE *whoami, *fopen(), *popen();
X char *ptr, *index();
X
X *name = '\0';
X
X /* try /etc/whoami */
X if ((whoami = fopen("/etc/whoami", "r")) != 0) {
X (void) fgets(name, len, whoami);
X (void) fclose(whoami);
X if ((ptr = index(name, '\n')) != 0)
X *ptr = '\0';
X }
X if (*name)
X return 0;
X
X /* try /usr/include/whoami.h */
X if ((whoami = fopen("/usr/include/whoami.h", "r")) != 0) {
X while (!feof(whoami)) {
X char buf[100];
X
X if (fgets(buf, 100, whoami) == 0)
X break;
X if (sscanf(buf, "#define sysname \"%[^\"]\"", name))
X break;
X }
X (void) fclose(whoami);
X if (*name)
X return 0;
X }
X
X /* ask uucp */
X if ((whoami = popen("uuname -l", "r")) != 0) {
X (void) fgets(name, len, whoami);
X (void) pclose(whoami);
X if ((ptr = index(name, '\n')) != 0)
X *ptr = '\0';
X }
X if (*name)
X return 0;
X
X /* aw hell, i give up! is this really unix? */
X return -1;
X}
X#endif /* GETHOSTNAME */
X#endif /* UNAME */
END_OF_local.c
if test 1420 -ne `wc -c <local.c`; then
echo shar: \"local.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f main.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"main.c\"
else
echo shar: Extracting \"main.c\" \(3978 characters\)
sed "s/^X//" >main.c <<'END_OF_main.c'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)main.c 9.1 87/10/04";
X#endif
X
X#define MAIN /* for sccsid in header files */
X
X#include "def.h"
X
X/* exports */
Xextern void die();
Xchar *Cfile; /* current input file */
Xchar *Graphout; /* file for dumping edges (-g option) */
Xchar *Linkout; /* file for dumping shortest path tree */
Xchar **Argv; /* external copy of argv (for input files) */
Xnode *Home; /* node for local host */
Xint Cflag; /* print costs (-c option) */
Xint Dflag; /* penalize routes beyond domains (-D option) */
Xint Iflag; /* ignore case (-i option) */
Xint Tflag; /* trace links (-t option) */
Xint Vflag; /* verbose (-v option) */
Xint Fflag; /* print cost of first hop */
Xint Lineno = 1; /* line number within current input file */
Xint Argc; /* external copy of argc (for input files) */
X
X/* imports */
Xextern long allocation();
Xextern void wasted(), mapit(), penalize(), hashanalyze(), deadlink();
Xextern char *local();
Xextern node *addnode();
Xextern char *optarg;
Xextern int optind;
Xextern long Lcount, Ncount;
X
X#define USAGE "usage: %s [-vciDf] [-l localname] [-d deadlink] [-t tracelink] [-g edgeout] [-s treeout] [-a avoid] [files ...]\n"
X
Xmain(argc, argv)
X register int argc;
X register char **argv;
X{ char *locname = 0, buf[32], *bang;
X register int c;
X int errflg = 0;
X
X setbuf(stderr, (char *) 0);
X (void) allocation(); /* initialize data space monitoring */
X Cfile = "[deadlinks]"; /* for tracing dead links */
X Argv = argv;
X Argc = argc;
X
X while ((c = getopt(argc, argv, "a:cd:Dfg:il:s:t:v")) != EOF)
X switch(c) {
X case 'a': /* adjust cost out of arg */
X penalize(optarg, DEFPENALTY);
X break;
X case 'c': /* print cost info */
X Cflag++;
X break;
X case 'd': /* dead host or link */
X if ((bang = index(optarg, '!')) != 0) {
X *bang++ = 0;
X deadlink(addnode(optarg), addnode(bang));
X } else
X deadlink(addnode(optarg), (node *) 0);
X break;
X case 'D': /* penalize routes beyond domains */
X Dflag++;
X break;
X case 'f': /* print cost of first hop */
X Cflag++;
X Fflag++;
X break;
X case 'g': /* graph output file */
X Graphout = optarg;
X break;
X case 'i': /* ignore case */
X Iflag++;
X break;
X case 'l': /* local name */
X locname = optarg;
X break;
X case 's': /* show shortest path tree */
X Linkout = optarg;
X break;
X case 't': /* trace this link */
X if (tracelink(optarg) < 0) {
X fprintf(stderr, "%s: can trace only %d links\n", Argv[0], NTRACE);
X exit(1);
X }
X Tflag = 1;
X break;
X case 'v': /* verbose stderr, mixed blessing */
X Vflag++;
X if (Vflag == 1) {
X /* v8 pi snarf, benign EBADF elsewhere */
X sprintf(buf, "/proc/%05d\n", getpid());
X write(3, buf, strlen(buf));
X }
X break;
X default:
X errflg++;
X }
X
X if (errflg) {
X fprintf(stderr, USAGE, Argv[0]);
X exit(1);
X }
X argv += optind; /* kludge for yywrap() */
X
X if (*argv)
X freopen("/dev/null", "r", stdin);
X else
X Cfile = "[stdin]";
X
X if (!locname)
X locname = local();
X if (*locname == 0) {
X locname = "lostinspace";
X fprintf(stderr, "%s: using \"%s\" for local name\n",
X Argv[0], locname);
X }
X
X Home = addnode(locname); /* add home node */
X Home->n_cost = 0; /* doesn't cost to get here */
X
X yyparse(); /* read in link info */
X
X if (Vflag > 1)
X hashanalyze();
X vprintf(stderr, "%d vertices, %d edges\n", Ncount, Lcount);
X vprintf(stderr, "allocation is %ldk after parsing\n", allocation());
X
X Cfile = "[backlinks]"; /* for tracing back links */
X Lineno = 0;
X
X /* compute shortest path tree */
X mapit();
X vprintf(stderr, "allocation is %ldk after mapping\n", allocation());
X
X /* traverse tree and print paths */
X printit();
X vprintf(stderr, "allocation is %ldk after printing\n", allocation());
X
X wasted(); /* how much was wasted in memory allocation? */
X
X return 0;
X}
X
Xvoid
Xdie(s)
X char *s;
X{
X fprintf(stderr, "%s: %s; notify the authorities\n", Argv[0], s);
X#ifdef DEBUG
X fflush(stdout);
X fflush(stderr);
X abort();
X#else
X exit(-1);
X#endif
X}
END_OF_main.c
if test 3978 -ne `wc -c <main.c`; then
echo shar: \"main.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f make.honey -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"make.honey\"
else
echo shar: Extracting \"make.honey\" \(2912 characters\)
sed "s/^X//" >make.honey <<'END_OF_make.honey'
X#!/bin/make -f
X# pathalias -- by steve bellovin, as told to peter honeyman
X
X### configuration section
X###
X# if you can't or don't intend to use dbm files,
X# don't bother with DBM or makedb
XDBM = -ldbm
X# or if you roll your own ...
X# DBM = dbm.o
X###
X# where is getopt (if not in the c library)?
X# GETOPT = -lgetopt
X### end of configuration section
X
XCC = cc -g
XCFLAGS = -DSTATIC=extern -DDEBUG
XLDFLAGS =
XYFLAGS = -d
X
XOBJ = addlink.o addnode.o local.o main.o mapit.o mapaux.o mem.o parse.o printit.o
XOFILES = addlink.O addnode.O local.O main.O mapit.O mapaux.O mem.O parse.O printit.O
XHDRS = def.h config.h
XCSRC = addlink.c addnode.c local.c main.c mapit.c mapaux.c mem.c printit.c
XLSRC = $(CSRC) parse.c
XSRC = $(CSRC) parse.y makedb.c arpatxt.c
X
Xpathalias: $(OBJ)
X $(CC) $(OBJ) $(LDFLAGS) -o pathalias
X
Xall: pathalias makedb arpatxt
X
X$(OBJ): $(HDRS)
X
Xparse.c: parse.y $(HDRS)
X $(YACC) $(YFLAGS) parse.y
X sed '/^# line/d' y.tab.c > parse.c
X
Xmakedb: makedb.o
X $(CC) makedb.o $(LDFLAGS) $(DBM) -o makedb
X
Xmakedb.o: config.h
X
Xarpatxt: arpatxt.o
X $(CC) arpatxt.o $(LDFLAGS) -o arpatxt
X
Xclean:
X rm -f *.o y.tab.? parse.c
X
Xtags: $(SRC) $(HDRS)
X ctags -w $(SRC) $(HDRS)
X
Xbundle: README CHANGES pathalias.1 Makefile ${HDRS} ${SRC} arpa-privates make.honey
X @bundle README CHANGES pathalias.1 Makefile ${HDRS} ${SRC} arpa-privates make.honey
X
Xbundle1: README CHANGES pathalias.1 Makefile ${HDRS}
X @bundle README CHANGES pathalias.1 Makefile ${HDRS}
X
Xbundle2: addlink.c addnode.c local.c main.c
X @bundle addlink.c addnode.c local.c main.c
X
Xbundle3: mapit.c mapaux.c
X @bundle mapit.c mapaux.c
X
Xbundle4: mem.c printit.c parse.y
X @bundle mem.c printit.c parse.y makedb.c
X
Xbundle5: makedb.c arpatxt.c arpa-privates make.honey
X @bundle makedb.c arpatxt.c arpa-privates make.honey
X
Xmake.honey: makefile
X @cp makefile make.honey
X
Xlint: $(LSRC)
X lint -hbau $(CFLAGS) $(LSRC)
X lint makedb.c
X
X
X# the remainder is site specific.
X
XPATHFILES = paths/* pp/* pm/*
X
Xpaths/internet: hosts.txt arpa-privates local.hosts
X arpatxt -fi -g citi -g umix -p arpa-privates local.hosts hosts.txt > paths/internet
X
XAVOID =
X
X# map output (input, really) to lower case; verbose; terminal domains
XARGS = -viD
X
XPARGS=$(ARGS) $(AVOID) $(PATHFILES)
Xdwon: paths/local paths/internet
X pathalias -l dwon $(PARGS) 2>ERRORS | sort -o dwon
X
X# desperation debugging -- examine the costs.
Xcosts:
X pathalias -icvvD ${PARGS} 2>error.costs | awk '{printf("%s\t%s\t%s\n", $$2, $$1, $$3)}' | sort -o pa.costs
X
X# make one BIG file. a BIG bad idea.
Xcat:
X for i in $(PATHFILES); do cat $$i; echo 'private {}'; done > CAT
X
X# make a pathparse database. -g is undocumented.
Xedges:
X pathalias -g edges $(PARGS) 2>ERRORS > edges.hosts
X# makedb edges pa
X
Xumich:
X pathalias -l umich $(PARGS) 2>umich.ERRORS | sort > umich
X
Xciti: paths/local paths/internet
X pathalias -l citi $(PARGS) 2>citi.ERRORS | sort > citi
X
Xumix:
X pathalias -l umix $(PARGS) 2>umix.ERRORS | sort > umix
END_OF_make.honey
if test 2912 -ne `wc -c <make.honey`; then
echo shar: \"make.honey\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f makedb.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"makedb.c\"
else
echo shar: Extracting \"makedb.c\" \(2342 characters\)
sed "s/^X//" >makedb.c <<'END_OF_makedb.c'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)makedb.c 9.1 87/10/04";
X#endif /* lint */
X
X#include <stdio.h>
X#include "config.h"
X
Xtypedef struct {
X char *dptr;
X int dsize;
X} datum;
X
Xchar *Ofile = ALIASDB, *ProgName;
X
X#define USAGE "%s [-o dbmname] [-a] [file ...]\n"
X
Xmain(argc, argv)
X char *argv[];
X{ char *ofptr;
X int c, append = 0;
X extern int optind;
X extern char *optarg;
X
X ProgName = argv[0];
X while ((c = getopt(argc, argv, "o:a")) != EOF)
X switch(c) {
X case 'o': /* dbm output file */
X Ofile = optarg;
X break;
X
X case 'a': /* append mode */
X append++;
X break;
X
X default:
X fprintf(stderr, USAGE, ProgName);
X exit(1);
X break;
X }
X
X
X if ((ofptr = rindex(Ofile, '/')) != 0)
X ofptr++;
X else
X ofptr = Ofile;
X if (strlen(ofptr) > 10) {
X ofptr[10] = 0;
X fprintf(stderr, "%s: using %s for dbm output\n", ProgName, Ofile);
X }
X
X if (append == 0 && dbfile(Ofile) != 0) {
X perror_(Ofile);
X exit(1);
X }
X
X if (dbminit(Ofile) < 0) {
X perror_(Ofile);
X exit(1);
X }
X
X if (optind == argc)
X makedb((char *) 0);
X else for ( ; optind < argc; optind++)
X makedb(argv[optind]);
X exit(0);
X}
X
Xdbfile(dbf)
X char *dbf;
X{
X return (dbcreat(dbf, "dir") != 0 || dbcreat(dbf, "pag") != 0);
X}
X
Xdbcreat(dbf, suffix)
X char *dbf, *suffix;
X{ char buf[BUFSIZ];
X int fd;
X
X (void) sprintf(buf, "%s.%s", dbf, suffix);
X if ((fd = creat(buf, 0666)) < 0)
X return(-1);
X (void) close(fd);
X return(0);
X}
X
X
Xmakedb(ifile)
X char *ifile;
X{ char line[BUFSIZ];
X datum key, val;
X
X if (ifile && (freopen(ifile, "r", stdin) == NULL)) {
X perror_(ifile);
X return;
X }
X
X /*
X * keys and values are 0 terminated. this wastes time and (disk) space,
X * but does lend simplicity and backwards compatibility.
X */
X key.dptr = line;
X while (fgets(line, sizeof(line), stdin) != NULL) {
X char *op, *end;
X
X end = line + strlen(line);
X end[-1] = 0; /* kill newline, stuff null terminator */
X op = index(line, '\t');
X if (op != 0) {
X *op++ = 0;
X key.dsize = op - line; /* 0 terminated */
X val.dptr = op;
X val.dsize = end - op; /* 0 terminated */
X } else {
X key.dsize = end - line; /* 0 terminated */
X val.dptr = "\0"; /* why must i do this? */
X val.dsize = 1;
X }
X if (store(key, val) < 0)
X perror_(Ofile);
X }
X}
X
Xperror_(str)
X char *str;
X{
X fprintf(stderr, "%s: ", ProgName);
X perror(str);
X}
END_OF_makedb.c
if test 2342 -ne `wc -c <makedb.c`; then
echo shar: \"makedb.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f mapaux.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"mapaux.c\"
else
echo shar: Extracting \"mapaux.c\" \(7110 characters\)
sed "s/^X//" >mapaux.c <<'END_OF_mapaux.c'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)mapaux.c 9.1 87/10/04";
X#endif /* lint */
X
X#include "def.h"
X
X/* imports */
Xextern long Nheap, Hashpart, Tabsize;
Xextern node **Table, *Home;
Xextern char *Graphout, *Linkout, *Netchars, **Argv;
Xextern void freelink(), die();
Xextern long pack();
Xextern link *newlink();
Xextern node *newnode();
Xextern char *strsave();
X
X/* exports */
Xlong pack();
Xvoid resetnodes(), dumpgraph(), showlinks();
Xint tiebreaker();
Xnode *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/* l is a terminal edge from n -> next; return a copy of next */
Xnode *
Xncopy(n)
X register node *n;
X{ register node *ncp;
X
X 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(n->n_link);
X ncp->n_flag = (n->n_flag & ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT)) | NTERMINAL;
X return ncp;
X}
X
XSTATIC link *
Xlcopy(l)
X register link *l;
X{ register link *lcp;
X
X if (l == 0)
X return 0;
X lcp = newlink();
X *lcp = *l;
X lcp->l_flag &= ~LTREE;
X lcp->l_next = lcopy(l->l_next);
X return lcp;
X}
END_OF_mapaux.c
if test 7110 -ne `wc -c <mapaux.c`; then
echo shar: \"mapaux.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f mem.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"mem.c\"
else
echo shar: Extracting \"mem.c\" \(4277 characters\)
sed "s/^X//" >mem.c <<'END_OF_mem.c'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)mem.c 9.1 87/10/04";
X#endif
X
X#include "def.h"
X
X/* exports */
Xextern void freelink(), wasted();
Xextern long allocation();
Xlong Ncount;
X
X/* imports */
Xextern char *sbrk();
Xextern char *Netchars;
Xextern int Vflag;
Xextern void die();
X
X/* privates */
XSTATIC void nomem();
Xstatic link *Lcache;
Xstatic unsigned int Memwaste;
X
Xlink *
Xnewlink()
X{ register link *rval;
X
X if (Lcache) {
X rval = Lcache;
X Lcache = Lcache->l_next;
X strclear((char *) rval, sizeof(link));
X } else if ((rval = (link * ) calloc(1, sizeof(link))) == 0)
X nomem();
X return rval;
X}
X
X/* caution: this destroys the contents of l_next */
Xvoid
Xfreelink(l)
X link *l;
X{
X l->l_next = Lcache;
X Lcache = l;
X}
X
Xnode *
Xnewnode()
X{ register node *rval;
X
X if ((rval = (node * ) calloc(1, sizeof(node))) == 0)
X nomem();
X Ncount++;
X return rval;
X}
X
Xchar *
Xstrsave(s)
X char *s;
X{ register char *r;
X
X if ((r = malloc((unsigned) strlen(s) + 1)) == 0)
X nomem();
X (void) strcpy(r, s);
X return r;
X}
X
X#ifndef strclear
Xvoid
Xstrclear(str, len)
X register char *str;
X register long len;
X{
X while (--len >= 0)
X *str++ = 0;
X}
X#endif /*strclear*/
X
Xnode **
Xnewtable(size)
X long size;
X{ register node **rval;
X
X if ((rval = (node **) calloc(1, (unsigned int) size * sizeof(node *))) == 0)
X nomem();
X return rval;
X}
X
Xfreetable(t, size)
X node **t;
X long size;
X{
X#ifdef MYMALLOC
X addtoheap((char *) t, size * sizeof(node *));
X#else
X free((char *) t);
X#endif
X}
X
XSTATIC void
Xnomem()
X{
X static char epitaph[128];
X
X sprintf(epitaph, "out of memory (%ldk allocated)", allocation());
X die(epitaph);
X}
X
X/* data space allocation -- main sets `dataspace' very early */
Xlong
Xallocation()
X{
X static char *dataspace;
X long rval;
X
X if (dataspace == 0) { /* first time */
X dataspace = sbrk(0); /* &end? */
X return 0;
X }
X rval = (sbrk(0) - dataspace)/1024;
X if (rval < 0) /* funny architecture? */
X rval = -rval;
X return rval;
X}
X
X/* how much memory has been wasted? */
Xvoid
Xwasted()
X{
X if (Memwaste == 0)
X return;
X vprintf(stderr, "memory allocator wasted %ld bytes\n", Memwaste);
X}
X
X#ifdef MYMALLOC
X
X/* use c library malloc/calloc here, and here only */
X#undef malloc
X#undef calloc
Xextern char *malloc(), *calloc();
X
X/* allocate in MBUFSIZ chunks. 4k works ok (less 16 for malloc quirks). */
X#define MBUFSIZ (4 * 1024 - 16)
X
X/*
X * mess with ALIGN at your peril. longword (== 0 mod 4)
X * alignment seems to work everywhere.
X */
X
X#define ALIGN 2
X
Xtypedef struct heap heap;
Xstruct heap {
X heap *h_next;
X long h_size;
X};
X
Xstatic heap *Mheap; /* not to be confused with a priority queue */
X
Xaddtoheap(p, size)
X char *p;
X long size;
X{ int adjustment;
X heap *pheap;
X
X /* p is aligned, but it doesn't hurt to check */
X adjustment = align(p);
X p += adjustment;
X size -= adjustment;
X
X if (size < 1024)
X return; /* can't happen */
X pheap = (heap *) p; /* pheap is shorthand */
X pheap->h_next = Mheap;
X pheap->h_size = size;
X Mheap = pheap;
X}
X
X/*
X * buffered malloc()
X * returns space initialized to 0. calloc isn't used, since
X * strclear can be faster.
X *
X * free is ignored, except for very large objects,
X * which are returned to the heap with addtoheap().
X */
X
Xchar *
Xmymalloc(n)
X register unsigned int n;
X{ static unsigned int size; /* how much do we have on hand? */
X static char *mstash; /* where is it? */
X register char *rval;
X
X if (n >= 1024) { /* for hash table */
X rval = malloc(n); /* aligned */
X if (rval)
X strclear(rval, n);
X return rval;
X }
X
X n += align((char *) n); /* keep everything aligned */
X
X if (n > size) {
X Memwaste += size; /* toss the fragment */
X /* look in the heap */
X if (Mheap) {
X mstash = (char *) Mheap; /* aligned */
X size = Mheap->h_size;
X Mheap = Mheap->h_next;
X } else {
X mstash = malloc(MBUFSIZ); /* aligned */
X if (mstash == 0) {
X size = 0;
X return 0;
X }
X size = MBUFSIZ;
X }
X strclear(mstash, size); /* what if size > 2^16? */
X }
X rval = mstash;
X mstash += n;
X size -= n;
X return rval;
X}
X
X/*
X * what's the (mis-)alignment of n? return the complement of
X * n mod 2^ALIGN
X */
Xalign(n)
X char *n;
X{ register int abits; /* misalignment bits in n */
X
X abits = (int) n & ~(0xff << ALIGN) & 0xff;
X if (abits == 0)
X return 0;
X return (1 << ALIGN) - abits;
X}
X
X#endif /*MYMALLOC*/
END_OF_mem.c
if test 4277 -ne `wc -c <mem.c`; then
echo shar: \"mem.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f printit.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"printit.c\"
else
echo shar: Extracting \"printit.c\" \(6855 characters\)
sed "s/^X//" >printit.c <<'END_OF_printit.c'
X/* pathalias -- by steve bellovin, as told to peter honeyman */
X#ifndef lint
Xstatic char *sccsid = "@(#)printit.c 9.1 87/10/04";
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();
X
X/* privates */
Xstatic link *Ancestor; /* for -f option */
XSTATIC void preorder(), setpath(), printhost(), printdomain();
XSTATIC char *hostpath();
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; 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_printit.c
if test 6855 -ne `wc -c <printit.c`; then
echo shar: \"printit.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of archive 1 \(of 2\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 2 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked both archives.
rm -f ark[1-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archiv.a]
X.a]
X