mark@cbosgd.UUCP (Mark Horton) (10/09/84)
# To unbundle, sh this file
echo README 1>&2
sed 's/.//' >README <<'//GO.SYSIN DD README'
-From down!honey Sun Sep 30 00:45:53 EDT 1984
-To: whom it may concern
-Subject: new pathalias instructions
-
-cat CHANGES
-edit config.h
-edit Makefile
- peter
-
-Note from Mark Horton: Peter Honeyman's version of pathalias,
-contained herein, is reputed to be the best currently available.
-It still gets huge, and won't run on a 16 bit machine. Virtual
-memory or lots of RAM is suggested.
-
-You can run pathalias on the data as distributed last month.
-Note, however, that not all the data has been distributed; two
-pieces are yet to go out: AT&T and Canada+MN+MI+WI+NY+ND+SD.
-
-There were a number of minor syntax
-errors in the data, the corrections will be self evident from
-the diagnostics from pathalias. Note that costs A, B, C, D, and E
-were used in some data; these costs were intended to represent
-relative quality, A connections are excellent, C average, E terrible.
-Pathalias does not understand these names (or other names, such as
-NIGHTLY, not documented in the manual page) so you'll have to convert
-them to some names that seem reasonable to you.
-
-We view the first distribution as being a very rough cut, and you're
-bound to find problems. Don't bother to tell us about syntax errors
-that pathalias will find, as we'll find these ourselves. Please do
-tell us of errors in the data, of data we don't have, and any suggestions
-you have for improving things. We're still getting this off the ground,
-but expect to do another (better) posting of data in a few months.
//GO.SYSIN DD README
echo CHANGES 1>&2
sed 's/.//' >CHANGES <<'//GO.SYSIN DD CHANGES'
-Network character must be one of "!@%^.:" (I regret it already.)
-
-Use cheapest among duplicate links.
-
-Get rid of the "oneway" stuff -- it was a bad idea.
-
-Reverse the sense of the -c (cost) flag.
-
-Don't list duplicate links on stderr unless forced to (by -D).
-
-Support links to aliases, support and sub-aliases.
-
-Don't put network names in the output.
-
-Use the magic %-@ rule in paths involving multiple @-links.
-
-Address the naming problem by allowing declarations of private hosts.
-(Dbm doesn't support multiple keys, so don't use the private
-declaration yet.)
-
-Discourage mixing of left-binding and right-binding connectors.
-
-Use "dead nets" for nets that require gateways.
//GO.SYSIN DD CHANGES
echo pathalias.1 1>&2
sed 's/.//' >pathalias.1 <<'//GO.SYSIN DD pathalias.1'
-.TH PATHALIAS 1
-.SH NAME
-pathalias \- compute shortest paths
-.SH SYNOPSIS
-.B pathalias
-[
-.B \-Dvcib
-] [
-.B \-l
-host] [
-.B \-d
-link] [
-.B \-N
-number] [
-.B \-g
-file] [
-.B \-P
-file] [inputfiles ...]
-.SH DESCRIPTION
-.I Pathalias
-computes the shortest paths and corresponding network addresses from one
-site to all other known, reachable sites.
-\fIPathalias\fP expects as input a sequence of host-to-host connectivity
-information, with
-a host name in column 1, followed by white space, followed by
-a comma-separated list of links (also host names),
-denoting a connection from the host to the links.
-Connections are assumed to be unidirectional.
-A link-name may be preceded or followed by a network character to use
-in the path name.
-Valid network characters are '!', '@', ':', '.', '^', and '%'.
-The link-name (and network character, if present) may be
-followed by a ``cost'' in parentheses. Costs may be arbitrary
-arithmetic expressions involving numbers, parentheses, '+', '\-', '*',
-and '/'. Several symbolic numbers are
-defined, as follows:
-.RS
-.nf
-.ta 10m 15m
-LOCAL 10 (local-area network connection)
-DEDICATED 95 (high speed dedicated link)
-DIRECT 200 (local call)
-DEMAND 300 (normal call)
-HOURLY 500 (hourly poll)
-EVENING 1800 (time restricted call)
-DAILY 5000 (daily poll)
-WEEKLY 30000 (irregular poll)
-.fi
-.RE
-.PP
-For example,
-.RS
-.nf
-down princeton!(LOCAL)
-princeton astrovax!(DIRECT)
-princeton ulysses!(DEMAND)
-.fi
-.RE
-.PP
-In addition, ARPA is either a very large number or a very small one,
-depending on whether the local site is on the \s-2ARPANET\s0,
-DEAD is a very large number, and HIGH and LOW are \-5 and +5 respectively,
-for baud-rate or quality bonuses/penalties.
-.PP
-The numbers are intended to represent frequency
-of connection, which seems to be far more important than baud
-rates for this type of traffic. There is an assumed
-high overhead for each hop; thus, e.g., HOURLY is far more than
-DAILY / 24.
-.PP
-Aliases may be indicated by including lines of the form
-.RS
-name = alias [ , alias...]
-.RE
-The primary name is used in all expansions.
-.PP
-Fully connected networks, such as the ARPAnet or a LAN,
-are indicated by
-.RS
-net = {host, host, ...}
-.RE
-The host-list may be preceded or followed by a routing
-character, and may be followed by a cost:
-.RS
-.nf
-PrincetonCable = {up, down, yoyo, flakey, quirky, tilt, princeton}!(LOCAL)
-ARPA = @{sri-unix, mit-ai}(ARPA)
-.fi
-.RE
-.PP
-The network name is treated as a pseudo-host that has bidirectional
-links to each member host; network names do
-not appear in the output.
-The cost from a member to the net
-pseudo-host is 0; the cost specified is used for the link
-to each member. The name of a network is never used in
-expansions; thus, in the above example, sri-unix's path to
-mit-ai would be '%s@mit-ai', not '%s@ARPA@mit-ai'.
-.PP
-Anything following # on an input line is ignored. A line may be continued by
-starting the next line with white space.
-.PP
-Options:
-.TP 6
-.B \-D
-Report duplicate link declarations. Given the haphazard way data are
-collected, this is not advised.
-.TP 6
-.B \-i
-Map all host names to lower case.
-.TP 6
-.B \-b
-Create a dbm database as output.
-.TP 6
-.B \-p
-Print output on stdout even if \-b is specified.
-.TP 6
-.B \-c
-Print the costs of paths.
-.TP 6
-.B \-v
-Report some statistics on stderr.
-.TP 6
-.BR \-g file
-Dump the edges of the graph into the named file.
-This has been known to generate 10 megabytes of output.
-.TP 6
-.BR \-l host
-Use host as local host name.
-.TP 6
-.BR \-d link
-Declares a dead host or link; if link is a host name, that
-site is treated as dead and will be used as an intermediate host of
-last resort on any path.
-If link is of the form host1!host2, the link from host1 to host2
-is treated as an extremely high cost (i.e., dead) link.
-.TP 6
-.BR \-N number
-Use ``number'' as an approximation of the number of hosts
-in the database.
-Although
-not critical, a good approximation makes \fIpathalias\fP run faster.
-.TP 6
-.BR \-P file
-Use ``file'' as the name of the \fIdbm(3)\fP database.
-Default is ``palias''.
-.SH COMPILE-TIME
-Edit config.h to accommodate \s-2UNIX\s0 variants.
-.SH AUTHORS
-Steve Bellovin (ulysses!smb)
-.br
-Peter Honeyman (down!honey)
//GO.SYSIN DD pathalias.1
echo Makefile 1>&2
sed 's/.//' >Makefile <<'//GO.SYSIN DD Makefile'
-# pathalias -- by steve bellovin, as told to peter honeyman
-
-# if you don't have -ldbm, edit config.h and edit the next line
-LIBE = -ll -ldbm
-
-CC=cc
-
-CFLAGS =
-LDFLAGS =
-YFLAGS = -d
-OBJ = addlink.o addnode.o lex.o local.o main.o mapit.o mem.o parse.o
-HDRS = def.h config.h
-SRC = addlink.c addnode.c lex.l local.c main.c mapit.c mem.c parse.y
-CSRC = addlink.c addnode.c lex.c local.c main.c mapit.c mem.c parse.c
-PATHFILES = paths/* paths.sites/* paths.std/* path.map/.CAT
-
-all: pathalias
-
-pathalias: $(OBJ)
- $(CC) $(LDFLAGS) $(OBJ) $(LIBE) -o pathalias
-
-pathparse: pathparse.o
- $(CC) $(LDFLAGS) $@.o -o pathparse
-
-tags: $(SRC) $(HDSR)
- ctags -w $(HDRS) ${SRC}
-
-bundle:
- @bundle README CHANGES pathalias.1 Makefile ${HDRS} ${SRC}
-
-cat:
- cat $(PATHFILES) > CAT
-
-$(OBJ): def.h
-
-#def.h: config.h
-# get -s sccs/s.def.h
-# touch def.h
-
-parse.c: parse.y def.h
- $(YACC) $(YFLAGS) parse.y
- mv y.tab.c parse.c
-
-lex.o: parse.c lex.c
-
-lex.c: def.h lex.l
- lex lex.l
- sed "s/define YYLMAX 200/define YYLMAX 512/" lex.yy.c >lex.c
- rm -f lex.yy.c
-
-lint: $(CSRC)
- lint $(CFLAGS) $(CSRC)
-
-clean:
- rm -f *.o pa y.tab.c y.tab.h lex.c parse.c core
-
-# the remainder is site specific -- here's how i do it
-
-LOCAL = down
-
-NEIGHBORS = yoyo tilt up quirky flakey
-
-SITES = ${LOCAL} ${NEIGHBORS}
-
-paths: ${SITES}
-
-DEAD = -d harpo -d zeppo -d chico -d gummo -d tucc -d allegra!teklabs -d allegra!ism780 -d vax135!imagen -d allegra!brandeis -d fortune!analog -d CSNET -d BITNET -d ARPANET
-DBFILE = /usr/local/lib/mail/paths
-# EDGES = -g EDGES
-NODES = -N 4314
-ARGS = -ci
-PATHALIAS = pathalias $(ARGS) $(NODES) $(DEAD)
-
-${LOCAL}: paths/princeton
- ${PATHALIAS} -v -l $@ $(EDGES) $(PATHFILES) > $@.new 2>ERRORS
- mv $@.new $@
-
-${NEIGHBORS}: paths/princeton
- $(PATHALIAS) -l $@ $(PATHFILES)> $@.new 2>ERRORS
- mv $@.new $@
-
-install: paths
- for i in $(NEIGHBORS); do\
- uucp -ga $$i $$i!/usr/local/lib/pathaliases;\
- uux -z -gb -a$$USER $$i!newaliases;\
- done
-
-test: TestPaths
- ${PATHALIAS} -vc -g test.edges TestPaths > test 2>test.2
-
-seismo:
- $(PATHALIAS) -l $@ $(PATHFILES)> $@.new 2>ERRORS
- mv $@.new $@
//GO.SYSIN DD Makefile
echo def.h 1>&2
sed 's/.//' >def.h <<'//GO.SYSIN DD def.h'
-/* pathalias -- by steve bellovin, as told to peter honeyman */
-#ifndef lint
-static char *h_sccsid = "@(#)def.h 5.7 (down!honey) 84/09/29";
-#endif lint
-
-#include <stdio.h>
-#include <ctype.h>
-#include "config.h"
-
-typedef long Cost;
-typedef struct node node;
-typedef struct link link;
-
-#ifdef MYMALLOC
-#define malloc mymalloc
-#define free myfree
-char *sbrk();
-
-#ifdef ALIGN
-
-#if ALIGN == 0
-#undef ALIGN
-#endif ALIGN == 0
-
-#endif ALIGN
-
-#ifndef ALIGN
-#define memget sbrk
-#else ALIGN
-char *memget();
-#endif ALIGN
-
-#endif MYMALLOC
-
-#ifdef ATTSV
-#ifndef UNAME
-#define UNAME
-#endif
-#define index strchr
-#define rindex strrchr
-#endif ATTSV
-
-#define STATIC /* static */ /* when i'm done profiling ... */
-
-#ifdef lint
-#define vprintf fprintf
-#else !lint -- this gives null effect warning
-/* because it's there ... */
-#define vprintf !Vflag ? 0 : fprintf
-#endif lint
-
-#define isnetc(c) ((c)=='!' || (c)=='.' || (c)==':' || (c)=='^' || \
- (c)=='@' || (c)=='%')
-
-#define dirbits(c) (c)
-
-#define NAME(x) ((x)->n_alias ? (x)->n_alias->n_name : (x)->n_name)
-
-/* flags for n_flag */
-#define ISPRIVATE 0x1 /* this node invisible outside its definition file */
-#define DEHASH 0x2 /* removed from hash table yet? */
-#define ATSIGN 0x4 /* seen an at sign? used for magic @/% rules */
-#define MAPPED 0x8 /* done mapping this node */
-#define NDEAD 0x10 /* node is dead */
-#define HASLEFT 0x20 /* route has a left side net character */
-#define HASRIGHT 0x40 /* route has a right side net character */
-#define NNET 0x80 /* node is a network name */
-
-/* TODO: merge n_link and n_aliaslink into a union */
-struct node {
- char *n_name; /* host name */
- link *n_link; /* head of adjacency list */
- node *n_alias; /* real node (when this node is an alias) */
- node *n_aliaslink; /* other aliases for this node */
- node *n_private; /* othger private nodes in this file */
- char *n_path; /* path to this host */
- Cost n_cost; /* cost to this host */
- short n_tloc; /* back ptr to heap/hash table */
- char n_flag; /* see manifests above */
-};
-
-#define DEFNET '!' /* default network character */
-#define DEFDIR LLEFT /* host on left in default net */
-#define DEFCOST ((Cost) 4000) /* default cost of a link */
-#define INF ((Cost) 30000000) /* infinitely expensive link */
-
-#define NETDIR(l) ((l)->l_flag & LDIR)
-#define NETCHAR(l) (Netchars[(l)->l_flag & LNETCHARS])
-
-/* data structure for adjacency list representation */
-/* flags for l_dir */
-
-/*
- * there's an ugly dependency between these manifests and the string
- * Netchars = "!.:^@%", defined in main.c
- * this saves 2 bytes per link (of which there are often > 20000)
- */
-#define LNETCHARS 0x7
-#define LBANG 0x0
-#define LDOT 0x1
-#define LCOLON 0x2
-#define LCARAT 0x3
-#define LAT 0x4
-#define LPERCENT 0x5
-
-#define LDIR 0x8 /* 0 for left, 1 for right */
-#define LRIGHT 0x0 /* user@host style */
-#define LLEFT 0x8 /* host!user style */
-
-#define LDEAD 0x10 /* this link is dead */
-
-struct link {
- link *l_next; /* rest of adjacency list */
- node *l_to; /* adjacent node */
- Cost l_cost; /* edge cost */
- char l_flag; /* right/left syntax */
- char l_lnet; /* network number ??? */
-};
-
-node *addnode();
-link *addlink();
-link *lmerge();
-char *strsave();
-char *local();
-link *newlink();
-node *newnode();
-node **newtable();
-void strclear();
-void setpath();
-
-long atol();
-char *malloc();
-char *index();
-char *rindex();
-FILE *popen();
-char *strcpy();
-
-extern node *Home;
-extern char *Cfile;
-extern int Fcnt;
-extern int Netid;
-extern char **Ifiles;
-extern char *ProgName;
-extern int Lineno;
-extern node **Table;
-extern int Tabsize;
-extern char *Netchars;
-extern int Vflag;
-extern int Dflag;
-extern int Cflag;
-extern int Bflag;
-extern int Pflag;
-extern int Iflag;
-extern int Ncount;
-extern int Lcount;
-extern int Nhosts;
-extern char *Pathout;
-extern char *Graphout;
-extern int Netid;
-extern node *Private;
//GO.SYSIN DD def.h
echo config.h 1>&2
sed 's/.//' >config.h <<'//GO.SYSIN DD config.h'
-/* pathalias -- by steve bellovin, as told to peter honeyman */
-#ifndef lint
-static char *c_sccsid = "@(#)config.h 5.7 (down!honey) 84/09/29";
-#endif lint
-
-#define DBM /* include code to generate dbm(3) database */
-
-/* #define ATTSV /* System III or System V */
-
-/* #define UNAME /* have uname() */
-
-/* #define GETHOSTNAME /* have gethostname() */
-
-#define PATHALIAS "/usr/local/lib/paliases" /* default dbm output */
-
-/*
- * after much profiling, i finally found a good malloc/free
- * remove the next line if you disagree
- */
-#define MYMALLOC /**/
-
-/*
- * how many trailing 0's needed in an ponter?
- * i am told that 68000 based systems want ALIGN to be 1.
- */
-/* #define ALIGN 1 /* */
//GO.SYSIN DD config.h
echo addlink.c 1>&2
sed 's/.//' >addlink.c <<'//GO.SYSIN DD addlink.c'
-/* pathalias -- by steve bellovin, as told to peter honeyman */
-#ifndef lint
-static char *sccsid = "@(#)addlink.c 5.4 (down!honey) 84/09/29";
-#endif lint
-
-#include "def.h"
-link *
-addlink(from, to, cost, netchar, netdir)
-node *from;
-register node *to;
-Cost cost;
-char netchar;
-char netdir;
-{
- register link *l, *prev = 0;
-
- /* link chains are sorted by host struct address, largest to smallest */
- for (l = from->n_link; l; l = l->l_next) {
- if (to >= l->l_to)
- break;
- prev = l;
- }
- if (l && (to == l->l_to)) {
- if (Dflag) {
- yyerror("duplicate link");
- fprintf(stderr, "%s %s(%d)",
- from->n_name, to->n_name, cost);
- if (cost < l->l_cost)
- fprintf(stderr, ", cost was %d\n\n", l->l_cost);
- else if (cost > l->l_cost)
- fprintf(stderr, ", using old cost (%d)\n\n",
- l->l_cost);
- else
- fputs("\n\n", stderr);
-
- }
- /*
- * use new cost if cheaper.
- * exception: if the existing link is a zero
- * cost link to a network, use this cost.
- */
- if ((cost < l->l_cost)
- || ((to->n_flag & NNET) && l->l_cost == 0)) {
- l->l_cost = cost;
- l->l_flag &= (~LNETCHARS|LDIR);
- l->l_flag |= netbits(netchar) | dirbits(netdir);
- }
- return(l);
- }
-
- l = newlink();
-
- if (prev) {
- l->l_next = prev->l_next;
- prev->l_next = l;
- } else {
- l->l_next = from->n_link;
- from->n_link = l;
- }
-
- l->l_to = to;
- l->l_cost = cost;
- if (netchar == 0)
- netchar = DEFNET;
- l->l_flag |= netbits(netchar) | dirbits(netdir);
-
- return(l);
-}
-
-deadlink(s)
-char *s;
-{
- char *t, c;
- link *l;
-
- for (t = s; !isnetc(*t); t++)
- if (*t == 0)
- break;
- if ((c = *t) != 0) {
- *t = 0;
- l = addlink(addnode(s, 0), addnode(t + 1, 0), INF / 2, c, DEFDIR);
- l->l_flag |= LDEAD;
- } else
- addnode(s, 0)->n_flag |= NDEAD;
-}
-
-#ifdef SHOWLINK
-showlink(n)
-register node *n;
-{
- register link *l;
-
- fprintf(stderr, "%s\t", NAME(n));
- for (l = n->n_link; l; l = l->l_next)
- fputs(NAME(l->l_to), stderr);
- putc('\n', stderr);
-}
-#endif SHOWLINK
-
-netbits(c)
-char c;
-{
- char *nptr;
-
- if ((nptr = index(Netchars, c)) != 0)
- return(nptr - Netchars);
- fprintf(stderr, "%s: invalid network character: %c\n", c);
- badmagic(1);
- /*NOTREACHED*/
-}
//GO.SYSIN DD addlink.c
echo addnode.c 1>&2
sed 's/.//' >addnode.c <<'//GO.SYSIN DD addnode.c'
-/* pathalias -- by steve bellovin, as told to peter honeyman */
-#ifndef lint
-static char *sccsid = "@(#)addnode.c 5.3 (down!honey) 84/09/29";
-#endif lint
-
-#include "def.h"
-
-void lowercase();
-node *isprivate();
-
-/*
- * these numbers are chosen because:
- * -> they are prime,
- * -> they are monotonic increasing,
- * -> each is a tad smaller than a multiple of 1024.
- * the first point yields good hash functions, the second is used for the
- * standard re-hashing implementation of open addressing, and the third
- * optimizes for quirks in some mallocs i have seen.
- */
-static int Primes[] = {
- 1021, 2045, 3069, 4093, 5117, 6141, 7165, 8189, 9213,
- 10237, 11261, 12285, 13309, 14333, 15357, 16381, 0
-};
-static int Tabindex = -1;
-int Tabsize;
-node **Table;
-
-node *
-addnode(name, privatenode)
-char *name;
-{
- int i;
- register node *n;
-
- if (Iflag)
- lowercase(name);
-
- /* is it a private host */
- n = isprivate(name);
- if (n != 0) {
- while (n->n_alias)
- n = n->n_alias;
- return(n);
- }
-
- i = hash(name, privatenode);
- if (Table[i] != 0) {
- n = Table[i];
- while (n->n_alias)
- n = n->n_alias;
- return(n);
- }
-
- n = newnode();
- n->n_name = strsave(name);
- Table[i] = n;
- n->n_tloc = i; /* essentially a back link to the table */
-
- return(n);
-}
-
-alias(parent, child)
-node *parent; /* real node */
-node *child; /* alias node */
-{
- node *root; /* root of this alias tree */
- if (parent == child)
- return; /* caused by redeclaration of alias */
-
- /* avoid alias loops, force many-to-one */
- if (parent->n_alias || child->n_alias) {
- yyerror("can't nest aliases\n");
- return;
- }
-
- /* merge links from parent(s) to root, point parent at root */
- for (root = parent->n_alias; root; root = root->n_alias) {
- root->n_link = lmerge(root->n_link, parent->n_link);
- parent = root;
- }
-
- /* merge child links into parent (now root) */
- parent->n_link = lmerge(parent->n_link, child->n_link);
-
- /* set up the alias pointers */
- child->n_alias = parent;
- child->n_aliaslink = parent->n_aliaslink;
- parent->n_aliaslink = child;
-}
-
-/* double hashing -- 101 is arbitrary (but has special meaning to me) */
-#define HASH1(n) ((n) % Tabsize);
-#define HASH2(n) (((n) % 101) + 1)
-
-/*
- * at 75% full, probes per access is about 2.
- */
-#define HIGHWATER 75
-#define LOWWATER 55
-#define isfull(n, size) ((n) > (((size) * HIGHWATER) / 100))
-#define isempty(n, size) ((n) < (((size) * LOWWATER) / 100))
-
-STATIC int
-hash(n, privatenode)
-register char *n;
-{
- register int probe, hash2;
-
- /* rehash if table too full */
- if (Tabindex < 0) { /* first time */
- if (Nhosts)
- do
- Tabsize = Primes[++Tabindex];
- while (isfull(Nhosts, Tabsize));
- else
- Tabsize = Primes[++Tabindex];
- vprintf(stderr, "use %d for initial hash table\n", Tabsize);
- Table = newtable(Tabsize);
- } else if (isfull(Ncount, Tabsize)) { /* rehash */
- node **oldTable, **optr;
-
- hashanalyze();
- optr = Table + Tabsize - 1; /* ptr to last */
- oldTable = Table;
-
- do
- Tabsize = Primes[++Tabindex];
- while (!isempty(Ncount, Tabsize))
- ;
- vprintf(stderr, "rehash into %d\n", Tabsize);
- if (Tabsize == 0) {
- fprintf(stderr, "%s: > %d hosts\n", Primes[Tabindex-1]);
- badmagic(1);
- }
- Table = newtable(Tabsize);
-
- do {
- if (*optr == 0)
- continue;
- probe = hash((*optr)->n_name,
- (*optr)->n_flag & ISPRIVATE);
- if (Table[probe] != 0) {
- fprintf(stderr, "%s: rehash error\n", ProgName);
- badmagic(1);
- }
- Table[probe] = *optr;
- (*optr)->n_tloc = probe;
- } while (optr-- > oldTable);
- free((char *) oldTable);
- }
-
- probe = fold(n);
- /* don't change the order of the next two lines */
- hash2 = HASH2(probe);
- probe = HASH1(probe);
- /* thank you! */
-
- /*
- * probe the hash table until we find either
- * (1) an empty slot, or
- * (2) this host name,
- * unless we require a fresh slot (privatenode != 0)
- */
- while ((Table[probe] != 0)
- && ((privatenode != 0) || (strcmp(Table[probe]->n_name, n) != 0))) {
- probe += hash2;
- if (probe >= Tabsize)
- probe -= Tabsize;
- }
- return(probe);
-}
-
-fold(s)
-char *s;
-{
- int h = 0;
-
- while (*s) {
- h <<= 2;
- h += *s++;
- }
- if (h < 0)
- h = -h;
- return(h);
-}
-
-/* merge the l2 list into the l1 list */
-link *
-lmerge(l1, l2)
-link *l1, *l2;
-{
- link *rval, *ltmp;
-
- if (l1 == 0)
- return(l2);
-
- if (l2 == 0)
- return(l1);
-
- if (l1->l_to > l2->l_to) {
- ltmp = rval = l1;
- l1 = l1->l_next;
- } else if (l1->l_to < l2->l_to) {
- ltmp = rval = l2;
- l2 = l2->l_next;
- } else if (l1->l_cost <= l2->l_cost) {
- ltmp = rval = l1;
- l1 = l1->l_next;
- free((char *) l2);
- l2 = l2->l_next;
- } else {
- ltmp = rval = l2;
- l2 = l2->l_next;
- free((char *) l1);
- l1 = l1->l_next;
- }
-
- while (l1 && l2) {
- if (l1->l_to > l2->l_to) {
- ltmp->l_next = l1;
- ltmp = l1;
- l1 = l1->l_next;
- } else if (l1->l_to < l2->l_to) {
- ltmp->l_next = l2;
- ltmp = l2;
- l2 = l2->l_next;
- } else if (l1->l_cost <= l2->l_cost) { /* use cheaper link */
- ltmp->l_next = l1;
- ltmp = l1;
- l1 = l1->l_next;
- free((char *) l2);
- l2 = l2->l_next;
- } else {
- ltmp->l_next = l2;
- ltmp = l2;
- l2 = l2->l_next;
- free((char *) l1);
- l1 = l1->l_next;
- }
- }
- if (l1)
- ltmp->l_next = l1;
- else
- ltmp->l_next = l2;
-
- return(rval);
-}
-
-hashanalyze()
-{
- int probe, hash2, count, i, collision[5];
- int longest = 0, total = 0, slots = 0;
- int nslots = sizeof(collision)/sizeof(collision[0]);
-
- if (!Vflag)
- return;
-
- strclear((char *) collision, sizeof(collision));
- for (i = 0; i < Tabsize; i++) {
- if (Table[i] == 0)
- continue;
- count = 1;
- probe = fold(Table[i]->n_name);
- /* don't change the order of the next two lines */
- hash2 = HASH2(probe);
- probe = HASH1(probe);
- /* thank you! */
- while (Table[probe] != 0
- && strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
- count++;
- probe += hash2;
- if (probe >= Tabsize)
- probe -= Tabsize;
- }
- if (Table[probe] == 0) {
- fprintf(stderr, "impossible hash error for %s\n", Table[i]->n_name);
- continue;
- }
-
- total += count;
- slots++;
- if (count > longest)
- longest = count;
- if (count >= nslots)
- count = 0;
- collision[count]++;
- }
- for (i = 1; i < nslots; i++)
- if (collision[i])
- fprintf(stderr, "%d chains: %d (%d%%)\n",
- i, collision[i], (collision[i] * 100)/ slots);
- if (collision[0])
- fprintf(stderr, "> %d chains: %d (%d%%)\n",
- nslots - 1, collision[0],
- (collision[0] * 100)/ slots);
- fprintf(stderr, "%2.2f probes per access, longest chain: %d\n",
- (double) total / slots, longest);
-}
-
-STATIC void
-lowercase(s)
-char *s;
-{
- do
- *s = isupper(*s) ? tolower(*s) : *s;
- while (*s++);
-}
-
-STATIC node *
-isprivate(name)
-char *name;
-{
- node *n;
-
- for (n = Private; n != 0; n = n->n_private)
- if (strcmp(name, n->n_name) == 0)
- return(n);
- return(0);
-}
-
-fixprivate()
-{
- node *n;
- char buf[BUFSIZ];
-
- for (n = Private; n != 0; n = n->n_private) {
- sprintf(buf, "%s!%s", n->n_name, Cfile);
-
- /*
- * can't handle repeated input file containing
- * private definitions.
- * continue anyway, generating duplicate output.
- */
- if (Table[hash(buf, 0)] != 0)
- fprintf(stderr, "%s: input file %s used twice\n",
- ProgName, Cfile);
-
- free(n->n_name);
- n->n_name = strsave(buf);
- }
- Private = 0;
-}
//GO.SYSIN DD addnode.c
echo lex.l 1>&2
sed 's/.//' >lex.l <<'//GO.SYSIN DD lex.l'
-%{
-/* pathalias -- by steve bellovin, as told to peter honeyman */
-#ifndef lint
-static char *sccsid = "@(#)lex.l 5.5 (down!honey) 84/09/30";
-#endif lint
-
-#include "def.h"
-#include "y.tab.h"
-
-extern YYSTYPE yylval;
-
-static costing = 0;
-static private = 0;
-static struct ctable {
- char *cname;
- Cost cval;
-} ctable[] = {
- /*
- * this list is searched sequentially (with strcmps!).
- * it is too long.
- */
- {"DEMAND", 300},
- {"DAILY", 5000},
- {"DIRECT", 200},
- {"DEDICATED", 95},
- {"DIAL", 300},
- {"LOCAL", 10},
- {"HOURLY", 500},
- {"EVENING", 1800},
- {"WEEKLY", 30000},
- {"ARPA", 100},
- {"HIGH", -5}, /* baud rate bonus */
- {"LOW", 5}, /* baud rate penalty */
- {"DEAD", INF/2},
- {"A", 300},
- {"B", 500},
- {"C", 1800},
- {"D", 5000},
- {"E", 30000},
- {"F", INF/2},
- {"DED", 95},
- {"DEDICATED", 95},
- {"DIALED", 300},
- {"POLLED", 5000},
- 0
-};
-
-%}
-
-WS [ \t]+
-NET [!^.:@%]
-ALPHA [a-zA-Z_0-9]
-SALPHA [-+a-zA-Z_0-9]
-
-%%
-"#".*\n{WS} {Lineno++;}
-"#".*\n {Lineno++; return(NL);}
-{WS} ;
-^"private"{WS}"{" {
- private++;
- return(PRIVATE);
- }
-^{SALPHA}+ {
- yylval.y_node = addnode(yytext, private);
- return(HOST);
- }
-[0-9]+ {
- if (costing) {
- yylval.y_cost = (Cost) atol(yytext);
- return(COST);
- }
- REJECT;
- }
-\n{WS} {Lineno++;}
-\n {costing = 0; Lineno++; return(NL);}
-{NET} {
- yylval.y_ind = yytext[0];
- return(NET);
- }
-\'.\' {
- yylval.y_ind = yytext[1];
- return(NET);
- }
-{ALPHA}+ {
- register struct ctable *ct;
- char c;
- c = input(); unput(c);
- if (costing) {
- for (ct = ctable; ct->cname; ct++)
- if (strcmp(ct->cname, yytext) == 0) {
- yylval.y_cost = ct->cval;
- return(COST);
- }
- yylval.y_node = addnode(yytext, private);
- return(SITE);
- } else if (c=='-' || c=='+')
- yymore();
- else {
- yylval.y_node = addnode(yytext, private);
- return(SITE);
- }
- }
-\"[^"]* {
- if (yytext[yyleng-1] == '\\')
- yymore();
- else {
- yylval.y_node = addnode(yytext+1, private);
- input();
- return(SITE);
- }
- }
-
-"{" {
- costing = 0;
- yylval.y_s.ys_ind = '\0';
- yylval.y_s.ys_dir = DEFDIR;
- return(LNET);
- }
-{NET}"{" {
- costing = 0;
- yylval.y_s.ys_ind = yytext[0];
- yylval.y_s.ys_dir = LRIGHT;
- return(LNET);
- }
-"}" {
- private = costing = 0;
- yylval.y_s.ys_ind = '\0';
- yylval.y_s.ys_dir = DEFDIR;
- return(RBRACE);
- }
-"}"{NET} {
- private = costing = 0;
- yylval.y_s.ys_ind = yytext[1];
- yylval.y_s.ys_dir = LLEFT;
- return(RBRACE);
- }
-
-"(" {costing++; return(LPAREN);}
-")" {costing--; return(RPAREN);}
-"," {costing = 0; return(COMMA);}
-"=" {costing = 0; return(EQUALS);}
-"+" {if (yyleng > 1) yymore(); else return(PLUS);}
-"-" {if (yyleng > 1) yymore(); else return(MINUS);}
-"*" {return(TIMES);}
-"/" {return(DIVIDE);}
-. {return(yytext[0]);}
-%%
-yywrap()
-{
- char errbuf[100];
-
- fixprivate(); /* munge private host definitions */
-
- if (Ifiles == 0)
- return(1);
-
- fclose(stdin);
- while (*Ifiles) {
- Lineno = 1;
- Fcnt++;
- if (fopen((Cfile = *Ifiles++), "r"))
- return(0);
- sprintf(errbuf, "%s: %s", ProgName, Cfile);
- perror(errbuf);
- }
- return(1);
-}
//GO.SYSIN DD lex.l
echo local.c 1>&2
sed 's/.//' >local.c <<'//GO.SYSIN DD local.c'
-/* pathalias -- by steve bellovin, as told to peter honeyman */
-#ifndef lint
-static char *sccsid = "@(#)local.c 5.2 (down!honey) 84/09/30";
-#endif lint
-
-#include "def.h"
-
-#ifdef UNAME
-#include <sys/utsname.h>
-struct utsname utsname;
-#endif UNAME
-
-char *
-local()
-{
-#ifdef UNAME
- uname(&utsname);
- return(utsname.nodename);
-#else !UNAME
- static char lname[64];
- void gethostname();
-
- gethostname(lname, sizeof(lname));
- return(lname);
-#endif UNAME
-}
-
-#ifndef GETHOSTNAME
-void
-gethostname(name, len)
-char *name;
-{
- FILE *whoami;
- char *ptr;
-
- *name = '\0';
-
- /* try /etc/whoami */
- if ((whoami = fopen("/etc/whoami", "r")) != 0) {
- (void) fgets(name, len, whoami);
- if ((ptr = index(name, '\n')) != 0)
- *ptr = '\0';
- }
- (void) fclose(whoami);
- if (*name)
- return;
-
- /* try /usr/include/whoami.h */
- if ((whoami = fopen("/usr/include/whoami.h", "r")) != 0) {
- while (!feof(whoami)) {
- char buf[100];
-
- if (fgets(buf, 100, whoami) == 0)
- break;
- if (sscanf(buf, "#define sysname \"%[^\"]\"", name))
- break;
- }
- (void) fclose(whoami);
- if (*name)
- return;
- }
-
- /* ask uucp */
- if ((whoami = popen("uuname -l", "r")) != 0) {
- (void) fgets(name, len, whoami);
- if ((ptr = index(name, '\n')) != 0)
- *ptr = '\0';
- }
- (void) pclose(whoami);
- if (*name)
- return;
-
- /* aw hell, i give up! is this a real unix? */
- (void) strcpy(name, "lostinspace");
- fprintf(stderr, "%s: using %s for local name\n", ProgName, name);
- return;
-}
-#endif GETHOSTNAME
//GO.SYSIN DD local.c
echo main.c 1>&2
sed 's/.//' >main.c <<'//GO.SYSIN DD main.c'
-/* pathalias -- by steve bellovin, as told to peter honeyman */
-#ifndef lint
-static char *sccsid = "@(#)main.c 5.3 (down!honey) 84/09/13";
-#endif lint
-
-#include "def.h"
-
-node *Home;
-int Fcnt = -1;
-char *Cfile;
-char **Ifiles;
-char *ProgName;
-int Vflag;
-int Dflag;
-int Cflag;
-int Bflag;
-int Pflag;
-int Iflag;
-int Lineno = 1;
-char *Netchars = "!.:^@%";
-int Ncount;
-int Lcount;
-int Nhosts;
-char *Pathout = PATHALIAS;
-char *Graphout = 0;
-int Netid;
-node *Private = 0; /* list of private nodes in this file */
-
-main(argc, argv)
-int argc;
-char *argv[];
-{
- char *locname = 0, *pptr;
-
-#ifdef lint
- argc = argc;
-#endif lint
-
- ProgName = argv[0];
- while (*++argv && **argv == '-') {
- (*argv)++;
- switch(**argv) {
-
- case 'l': /* local name */
- locname = *++argv;
- if (!*locname) {
- fprintf(stderr, "%s: -l requires host name\n",
- ProgName);
- exit(1);
- }
- break;
-
- case 'd': /* dead host or link */
- if (!*++argv) {
- fprintf(stderr, "%s: -d requires host name\n",
- ProgName);
- exit(1);
- }
- deadlink(*argv);
- break;
-
- case 'N': /* approximate number of hosts */
- Nhosts = atoi(*++argv);
- if (Nhosts == 0) {
- fprintf(stderr, "%s: -N requires non-zero arg\n",
- ProgName);
- exit(1);
- }
- break;
-
- case 'P': /* dbm output file */
- Pathout = *++argv;
- if (!*Pathout) {
- fprintf(stderr, "%s: -P requires output file name\n",
- ProgName);
- exit(1);
- }
- if ((pptr = rindex(Pathout, '/')) != 0)
- pptr++;
- else
- pptr = Pathout;
- if (strlen(pptr) > 10) {
- pptr[10] = 0;
- fprintf(stderr, "%s: using %s for db output\n",
- ProgName, Pathout);
- }
- break;
-
- case 'g': /* graph output file */
- Graphout = *++argv;
- if (!*Graphout) {
- fprintf(stderr, "%s: -g requires output file name\n",
- ProgName);
- exit(1);
- }
- break;
-
- case 0:
- break; /* ignore naked '-' */
-
- default:
- while (**argv) switch (*((*argv)++)) {
-
- case 'D': /* report duplicates (deprecated) */
- Dflag++;
- break;
-
- case 'v': /* verbose stderr, somewhat boring */
- Vflag++;
- break;
-
- case 'c': /* print cost info */
- Cflag++;
- break;
-
- case 'i': /* ignore case */
- Iflag++;
- break;
-
- case 'b': /* make a dbm database */
-#ifdef DBM
- Bflag++;
-#else !DBM
- fprintf(stderr, "%s: not compiled for dbm (warning)\n",
- ProgName);
-#endif DBM
- break;
-
- case 'p': /* print, even if -b */
- Pflag++;
- break;
-
- default:
- fprintf(stderr, "%s: %s: unknown flag\n", ProgName,
- *argv);
- exit(1);
- }
- }
- }
-
- Fcnt++;
- if (*argv) {
- Ifiles = argv;
- freopen("/dev/null", "r", stdin);
- }
-
- if (!locname)
- locname = local();
-
- Home = addnode(locname, 0); /* add home node */
- if (Home->n_alias)
- Home = Home->n_alias;
- Home->n_cost = 0; /* doesn't cost to get here */
-
- /* read in link info */
- yyparse();
-
- hashanalyze();
-
- /* compute shortest paths */
- mapit();
-
-#ifdef SHOWLINK
- showall();
-#endif SHOWLINK
-
- exit(0);
-}
-
-badmagic(n)
-{
-#ifdef DEBUG
- abort();
-#else !DEBUG
- exit(n);
-#endif DEBUG
-}
//GO.SYSIN DD main.c
echo mapit.c 1>&2
sed 's/.//' >mapit.c <<'//GO.SYSIN DD mapit.c'
-/* pathalias -- by steve bellovin, as told to peter honeyman */
-#ifndef lint
-static char *sccsid = "@(#)mapit.c 5.5 (down!honey) 84/09/29";
-#endif lint
-
-#include "def.h"
-
-void reheap(), insert(), setpath(), pack(), swap();
-node *min_node();
-
-static int Hashpart;
-
-#ifdef DBM
-typedef struct {char *dptr; int dsize;} datum;
-#endif DBM
-
-mapit()
-{
- node *n, *next;
- link *l;
- Cost cost;
-#ifdef DBM
- char alif[200];
-#endif
- char *sbrk();
-
- vprintf(stderr, "%d vertices, %d edges\n", Ncount, Lcount);
- vprintf(stderr, "break is %d after parsing\n", sbrk(0));
-
-#ifdef DBM
- if (Bflag) {
- sprintf(alif, "%s.dir", Pathout);
- if (close(creat(alif,0644)) < 0) {
- fprintf(stderr, "%s: ", ProgName);
- perror(alif);
- Bflag = 0; /* print to stdout */
- }
- sprintf(alif, "%s.pag", Pathout);
- if (close(creat(alif,0644)) < 0) {
- fprintf(stderr, "%s: ", ProgName);
- perror(alif);
- Bflag = 0; /* print to stdout */
- }
- if (Bflag)
- dbminit(Pathout);
- }
-#endif
- /* use the hash Table for the heap */
- /* TODO: coalesce the following functions into a single one */
- pack(); /* remove holes in the Table */
- rename(); /* restore private names to standard form */
- amerge(); /* merge all alias links once and for all */
- if (Graphout && *Graphout) /* dump the edge list */
- dumpgraph();
-
- dehash(Home);
- Home->n_path = strsave("%s");
- insert(Home);
-
- while ((n = min_node()) != 0) {
- printit(n);
-
- for (l = n->n_link; l != 0; l = l->l_next) {
- next = l->l_to;
- if (next->n_alias) {
- if (next->n_link) {
- fprintf(stderr,
- "%s: alias %s has links\n",
- ProgName, next->n_name);
- badmagic(1);
- }
- next = next->n_alias;
- }
- if (next->n_flag & MAPPED)
- continue;
- dehash(next);
- cost = n->n_cost + l->l_cost;
- /*
- * heuristics:
- * charge for getting out of a dead host.
- * charge for getting in to a dead net
- * unless the link cost is non-zero (gateway).
- * charge for a dead link.
- * discourage mixing of left and right syntax.
- */
- if ((n->n_flag & (NNET | NDEAD)) == NDEAD)
- cost += INF/2;
- if (((next->n_flag & (NNET | NDEAD)) == (NNET | NDEAD))
- && (l->l_cost == 0))
- cost += INF/2;
- if (l->l_flag & LDEAD)
- cost += INF/2;
- if ((n->n_flag & HASLEFT) && (NETDIR(l) == LRIGHT))
- cost += DEFCOST;
- if ((n->n_flag & HASRIGHT) && (NETDIR(l) == LLEFT))
- cost += DEFCOST;
-
- if (next->n_cost == 0) {
- next->n_cost = cost;
- insert(next);
- } else if (cost < next->n_cost) {
- next->n_cost = cost;
- reheap(next);
- } else
- continue;
-
- setpath(next, n, NETCHAR(l), NETDIR(l));
-
- free((char *) l);
- }
- free((char *) n->n_path);
- free((char *) n->n_name);
- for (next = n->n_aliaslink; next; next = next->n_aliaslink) {
- /* expunge aliases */
- dehash(next);
- Table[next->n_tloc] = 0;
- next->n_tloc = 0;
- free((char *) next->n_name);
- }
- }
- vprintf(stderr, "break is %d at after mapping\n", sbrk(0));
-
- if (Hashpart < Tabsize) {
- fprintf(stderr, "You can't get there from here:\n");
- while (Hashpart < Tabsize) {
- n = Table[Hashpart++];
- if (n->n_alias)
- continue; /* primary hosts only */
- fprintf(stderr, "\t%s", n->n_name);
- if (n->n_aliaslink) {
- fprintf(stderr, " (alias %s", n->n_aliaslink->n_name);
- n = n->n_aliaslink;
- while (n = n->n_aliaslink)
- fprintf(stderr, ", %s", n->n_name);
- putc(')', stderr);
- }
- putc('\n', stderr);
- }
- }
-}
-
-/*
- * heap implementation of priority queue.
- */
-
-static int Nheap;
-
-STATIC void
-insert(n)
-node *n;
-{
- int i, parent;
-
- Table[n->n_tloc] = 0;
- if (Table[Nheap+1] != 0) {
- fprintf(stderr, "%s: heap error in insert\n", ProgName);
- badmagic(1);
- }
- if (Nheap++ == 0) {
- Table[1] = n;
- n->n_tloc = 1;
- return;
- }
-
- /* insert at the end and percolate up */
- Table[Nheap] = n;
- n->n_tloc = Nheap;
- for (i = Nheap; i > 1; i = parent) {
- if (Table[i] == 0) {
- fprintf(stderr, "%s: heap error in insert\n", ProgName);
- badmagic(1);
- }
- parent = i / 2;
- if (Table[i]->n_cost < Table[parent]->n_cost)
- swap(i, parent);
- }
- return;
-}
-
-STATIC node *
-min_node()
-{
- node *rval;
- int i;
-
- if (Nheap == 0)
- return(0);
-
- rval = Table[1]; /* return this one */
-
- /* move last entry into root, percolate down */
- Table[1] = Table[Nheap];
- Table[1]->n_tloc = 1;
- Table[Nheap] = 0;
- if (--Nheap == 0)
- return(rval);
-
- i = 1;
- for (;;) {
- /* swap with smaller child (if larger than same) */
- int child;
-
- child = i * 2;
- if (child > Nheap)
- break;
- if (child + 1 < Nheap) /* right child exists? */
- if (Table[child]->n_cost > Table[child+1]->n_cost)
- child++;
-
- if (Table[i]->n_cost > Table[child]->n_cost)
- swap(i, child);
- i = child;
- }
-
- return(rval);
-}
-
-STATIC void
-swap(i, j)
-{
- node *temp;
-
- temp = Table[i];
- Table[i] = Table[j];
- Table[j] = temp;
- Table[j]->n_tloc = j;
- Table[i]->n_tloc = i;
-}
-
-
-/* "percolate" node n up the heap by exchanging with the parent */
-STATIC void
-reheap(n)
-node *n;
-{
- int loc, parent;
- Cost cost;
-
- cost = n->n_cost;
- for (loc = n->n_tloc; loc != 1; loc = parent) {
- parent = loc / 2;
- if (cost >= Table[parent]->n_cost)
- return;
- swap(loc, parent);
- }
-}
-
-STATIC void
-setpath(n, prev, netchar, netdir)
-node *n, *prev;
-char netchar, netdir;
-{
- char pathbuf[BUFSIZ], hostbuf[BUFSIZ], *name, *hptr;
-
- /* undo settings from earlier calls */
- if (n->n_path)
- free((char *) n->n_path);
-
- if (prev->n_flag & ATSIGN)
- n->n_flag |= ATSIGN;
- else
- n->n_flag &= ~ATSIGN;
-
- if (prev->n_flag & HASLEFT)
- n->n_flag |= HASLEFT;
- else
- n->n_flag &= ~HASLEFT;
-
- if (prev->n_flag & HASRIGHT)
- n->n_flag |= HASRIGHT;
- else
- n->n_flag &= ~HASRIGHT;
-
- if (n->n_flag & NNET) {
- n->n_path = strsave(prev->n_path);
- return;
- }
-
- name = NAME(n);
-
- /* do it by hand instead of sprintf-ing -- foo on '%' */
- if (netdir == LLEFT) {
- /* e.g., host!%s */
- n->n_flag |= HASLEFT;
- strcpy(hostbuf, name);
- hptr = hostbuf + strlen(hostbuf);
- *hptr++ = netchar;
- if (netchar == '%')
- *hptr++ = netchar;
- *hptr++ = '%';
- *hptr++ = 's';
- *hptr = 0;
- } else {
- /* e.g., %s@host, but watch out for the magic @-% conversion */
- n->n_flag |= HASRIGHT;
- if (netchar == '@') {
- n->n_flag |= ATSIGN;
- if (prev->n_flag & ATSIGN)
- netchar = '%'; /* shazam? shaman? */
- }
- hptr = hostbuf;
- *hptr++ = '%';
- *hptr++ = 's';
- *hptr++ = netchar;
- if (netchar == '%')
- *hptr++ = netchar;
- strcpy(hptr, name);
- }
- /* this would be an sprintf were it not for the %'s. feh. */
- pathprintf(pathbuf, prev->n_path, hostbuf);
- n->n_path = strsave(pathbuf);
-}
-
-
-dehash(n)
-node *n;
-{
- if (n->n_flag & DEHASH)
- return;
- Table[Hashpart]->n_tloc = n->n_tloc;
- Table[n->n_tloc] = Table[Hashpart];
- Table[Hashpart] = n;
- n->n_flag |= DEHASH;
- n->n_tloc = Hashpart++;
-}
-
-STATIC void
-pack()
-{
- int hole, next;
-
- /* find first "hole " */
- for (hole = Tabsize - 1; hole >= 0 && Table[hole] != 0; --hole)
- ;
-
- /* repeatedly move next filled entry into last hole */
- for (next = hole - 1; next >= 0; --next) {
- if (Table[next] != 0) {
- Table[hole] = Table[next];
- Table[hole]->n_tloc = hole;
- Table[next] = 0;
- while (Table[--hole] != 0) /* find next hole */
- ;
- }
- }
- Hashpart = hole + 1;
-}
-
-#ifdef DBM
-static char *pbuf = 0;
-static int psize = -1;
-
-wdb(name, path)
-char *name, *path;
-{
- datum dbkey, dbpath;
-
- /* this ugliness lets us tack a ! onto the end of name. ugly. */
- if (strlen(name)+2 > psize) {
- psize = 2 * (strlen(name) + 2);
- if (pbuf)
- free(pbuf);
- if ((pbuf = malloc(psize)) == 0)
- nomem();
- }
- sprintf(pbuf, "%s%c", name, DEFNET);
-
- dbkey.dptr = pbuf;
- dbkey.dsize = strlen(pbuf)+1;
- dbpath.dptr = path;
- dbpath.dsize = strlen(path)+1;
- if (store(dbkey, dbpath))
- fprintf(stderr, "%s: dbm error at %s->%s\n",
- ProgName, name, path);
-}
-#endif DBM
-
-pathprintf(buf, path, host)
-char *buf, *path, *host;
-{
- char *ptr;
-
- for (ptr = path; *buf = *ptr; ptr++) {
- if (*ptr == '%') {
- if (ptr[1] == 's') {
- strcpy(buf, host);
- buf += strlen(buf);
- ptr++;
- }
- } else
- buf++;
- }
-}
-
-amerge()
-{
- node *n, *a;
- int i;
-
- for (i = Hashpart; i < Tabsize; i++) {
- n = Table[i];
- if (n == 0)
- continue; /* impossible, but ... */
- if (a = n->n_alias) {
- a->n_link = lmerge(a->n_link, n->n_link);
- n->n_link = 0;
- }
- }
-}
-
-printit(n)
-node *n;
-{
- char *path = n->n_path;
- Cost cost = n->n_cost;
-
- for ( ; n; n = n->n_aliaslink) {
- n->n_flag |= MAPPED;
- if (n->n_flag & NNET)
- continue;
-#ifdef DBM
- if (Bflag)
- wdb(n->n_name, path);
- if (Pflag || !Bflag)
-#endif
- {
- if (Cflag)
- printf("%ld\t", (long) cost);
- printf("%s\t%s\n", n->n_name, path);
- }
- }
-}
-
-static FILE *estream;
-
-dumpgraph()
-{
- int i, qcmp();
- long seekstart, seekend;
- node *n;
- char edges[256], blocks[256], command[256];
- FILE *bstream, *fopen(), *popen();
-
- sprintf(edges, "%s.e", Graphout);
- sprintf(blocks, "%s.b", Graphout);
- if ((estream = fopen(edges, "w")) == NULL) {
- fprintf("%s: ", ProgName);
- perror(edges);
- return;
- }
- sprintf(command, "sort -o %s", blocks);
- if ((bstream = popen(command, "w")) == NULL) {
- fprintf("%s: ", ProgName);
- perror(command);
- fclose(bstream);
- return;
- }
-
- seekstart = 0;
- for (i = Hashpart; i < Tabsize; i++) {
- n = Table[i];
- if (n == 0)
- continue; /* impossible, but ... */
- n->n_tloc = i; /* necessary because of qsort() */
- if (n->n_alias)
- continue;
- /* a minor optimization ... */
- if (n->n_link == 0)
- continue;
- fprintf(bstream, "%s\t%d", n->n_name, seekstart);
- fprintf(estream, "!%s\n", n->n_name);
- dumplist(n, n->n_link);
- seekend = ftell(estream);
- fprintf(bstream, "\t%d\n", seekend - seekstart);
- seekstart = seekend;
- }
- fclose(estream);
- pclose(bstream);
-}
-
-dumplist(n, l)
-node *n;
-link *l;
-{
- node *next;
-
- for ( ; l; l = l->l_next) {
- next = l->l_to;
- if (next->n_alias)
- next = next->n_alias;
- if (n != next) {
- if (next->n_flag & NNET)
- putc('#', estream);
- fputs(next->n_name, estream);
- putc('\n', estream);
- }
- }
-}
-
-rename()
-{
- char *bang;
- node *n;
- int i;
-
- for (i = Hashpart; i < Tabsize; i++) {
- n = Table[i];
- if (n == 0 || (n->n_flag & ISPRIVATE) == 0)
- continue;
- if ((bang = index(n->n_name, '!')) == 0)
- fprintf(stderr,
- "%s: internal error on private host %s\n",
- ProgName, n->n_name);
- else
- *bang = 0;
- }
-}
//GO.SYSIN DD mapit.c
echo mem.c 1>&2
sed 's/.//' >mem.c <<'//GO.SYSIN DD mem.c'
-/* pathalias -- by steve bellovin, as told to peter honeyman */
-#ifndef lint
-static char *sccsid = "@(#)mem.c 5.3 (down!honey) 84/09/29";
-#endif lint
-
-#include "def.h"
-
-link *
-newlink()
-{
- link *rval;
-
- if ((rval = (link * ) malloc(sizeof(link))) == 0)
- nomem();
- strclear((char *) rval, sizeof(link)); /* fresh as a daisy */
- Lcount++;
- return(rval);
-}
-
-node *
-newnode()
-{
- node *rval;
-
- if ((rval = (node * ) malloc(sizeof(node))) == 0)
- nomem();
- strclear((char *) rval, sizeof(node)); /* fresh as a daisy */
- Ncount++;
- return(rval);
-}
-
-char *
-strsave(s)
-char *s;
-{
- char *r;
-
- if ((r = malloc(strlen(s) + 1)) == 0)
- nomem();
- (void) strcpy(r, s);
- return(r);
-}
-
-void
-strclear(dst, len)
-char *dst;
-int len;
-{
-#ifdef lint
- dst = dst;
- len = len;
-#endif lint
-
-#ifdef vax
- asm("movc5 $0,*4(ap),$0,8(ap),*4(ap)");
-#else !vax
- while (--len >= 0)
- *dst++ = 0;
-#endif vax
-}
-
-node **
-newtable(size)
-int size;
-{
- node **rval;
-
- if ((rval = (node **) malloc(size * sizeof(*rval))) == 0)
- nomem();
- strclear((char *) rval, size * sizeof(*rval));
- return(rval);
-}
-
-nomem()
-{
- fprintf(stderr, "%s: Out of memory\n", ProgName);
- badmagic(1);
-}
-
-#ifdef MYMALLOC
-char *
-mymalloc(n)
-register int n;
-{
- static int size;
- static char *mem;
- register char *rval;
-
- if (n > BUFSIZ)
- rval = memget(n);
- else {
-#ifdef ALIGN
- int adjustment;
-
- adjustment = align(mem);
- mem += adjustment;
- size -= adjustment;
-#endif ALIGN
- if (n > size) {
- mem = memget(BUFSIZ);
- size = BUFSIZ;
- }
- rval = mem;
- mem += n;
- size -= n;
- }
- return(rval);
-}
-
-myfree(s)
-char *s;
-{
-#ifdef lint
- s = s;
-#endif lint
-}
-
-#ifdef ALIGN
-char *
-memget(n)
-int n;
-{
- char *rval;
- int abits; /* alignment bits */
- int adjustment = 0;
-
- adjustment = align(sbrk(0));
- rval = sbrk(n + adjustment);
- if (rval <= 0)
- return(0);
- return(rval + adjustment);
-}
-
-align(n)
-char *n;
-{
- int abits; /* alignment bits */
- int adjustment = 0;
- int foo;
-
- abits = (long) n & ~(0xff << ALIGN) & 0xff;
- if (abits != 0)
- adjustment = (1 << ALIGN) - abits;
- return(adjustment);
-}
-#endif ALIGN
-
-#endif MYMALLOC
//GO.SYSIN DD mem.c
echo parse.y 1>&2
sed 's/.//' >parse.y <<'//GO.SYSIN DD parse.y'
-%{
-/* pathalias -- by steve bellovin, as told to peter honeyman */
-#ifndef lint
-static char *sccsid = "@(#)parse.y 5.4 (down!honey) 84/09/13";
-#endif lint
-
-#include "def.h"
-
-%}
-
-%union {
- node *y_node;
- Cost y_cost;
- char y_ind;
- struct y_s {
- node *ys_node;
- Cost ys_cost;
- char ys_ind;
- char ys_dir;
- } y_s;
-}
-
-%type <y_s> site sitenet lnetl
-%type <y_node> links aliases plist
-%type <y_cost> cost
-
-%token <y_node> HOST SITE
-%token <y_cost> COST
-%token <y_ind> NET
-%token <y_s> LNET RBRACE
-%token LPAREN RPAREN COMMA EQUALS NL PRIVATE
-
-%left PLUS MINUS
-%left TIMES DIVIDE
-
-%%
-map : /* empty */
- | map NL
- | map links NL
- | map aliases NL
- | map lnet NL
- | map private NL
- | error NL
- ;
-
-private : PRIVATE plist RBRACE =
- {
- if ($3.ys_ind != 0)
- yyerror("cost ignored on private definition (warning)\n");
- Private = $2;
- }
- ;
-
-plist : SITE =
- {
- if (($1->n_flag & ISPRIVATE) != 0) {
- /* we can live with this */
- yyerror("warning: redefinition of private node ");
- fprintf(stderr, "%s\n", $1->n_name);
- }
- $1->n_flag |= ISPRIVATE;
- }
- | plist COMMA SITE =
- {
- if (($3->n_flag & ISPRIVATE) != 0) {
- /* we can live with this */
- yyerror("warning: redefinition of private node ");
- fprintf(stderr, "%s\n", $3->n_name);
- }
- $3->n_private = $1;
- $3->n_flag |= ISPRIVATE;
- $$ = $3;
- }
- ;
-
-lnet : lnetl RBRACE =
- {
- fixnet($1.ys_node, &$1, &$2, DEFCOST, Netid);
- }
- | lnetl RBRACE LPAREN cost RPAREN =
- {
- fixnet($1.ys_node, &$1, &$2, $4, Netid);
- }
- ;
-
-lnetl : HOST EQUALS LNET SITE =
- {
-#ifdef notdef
- /* this doesn't work. should it? */
- if ($1->n_flag & NNET) {
- yyerror("redefinition of network: ");
- fprintf(stderr, "%s\n", $1->n_name);
- YYERROR;
- }
- if ($1->n_link) {
- yyerror("host/network conflict: ");
- fprintf(stderr, "%s\n", $1->n_name);
- YYERROR;
- }
-#endif notdef
- Netid++;
- $1->n_flag |= NNET;
- /*
- * set up 0 cost network -> member now,
- * member -> network will come in fixnet()
- * with appropriate cost.
- */
- addlink($1, $4, (Cost) 0, $3.ys_ind,
- $3.ys_dir)->l_lnet = Netid;
- $3.ys_node = $1;
- $$ = $3;
- }
- | lnetl COMMA SITE =
- {
- /* see comment above */
- addlink($1.ys_node, $3, (Cost) 0, $1.ys_ind,
- $1.ys_dir)->l_lnet=Netid;
- }
- ;
-
-aliases : HOST EQUALS SITE =
- {
- alias($1, $3);
- }
- | aliases COMMA SITE =
- {
- alias($1, $3);
- }
- ;
-
-links : HOST site =
- {
-#ifdef notdef
- /* this doesn't work. should it? */
- if ($1->n_flag & NNET) {
- yyerror("host/network conflict\n");
- YYERROR;
- }
-#endif notdef
- addlink($1, $2.ys_node, $2.ys_cost, $2.ys_ind, $2.ys_dir);
- }
- | links COMMA site =
- {
- addlink($1, $3.ys_node, $3.ys_cost, $3.ys_ind, $3.ys_dir);
- }
- ;
-
-site : sitenet =
- {
- $$.ys_cost = DEFCOST;
- }
- | sitenet LPAREN cost RPAREN =
- {
- $$.ys_cost =$3;
- }
- ;
-
-sitenet : NET SITE =
- {
- $$.ys_node = $2;
- $$.ys_ind = $1;
- $$.ys_dir = LRIGHT;
- }
- | SITE NET =
- {
- $$.ys_node = $1;
- $$.ys_ind = $2;
- $$.ys_dir = LLEFT;
- }
- | SITE =
- {
- $$.ys_node=$1;
- $$.ys_ind=DEFNET;
- $$.ys_dir=DEFDIR;
- }
- ;
-
-cost : COST
- | LPAREN cost RPAREN =
- {
- $$ = $2;
- }
- | cost PLUS cost =
- {
- $$ = $1 + $3;
- }
- | cost MINUS cost =
- {
- $$ = $1 - $3;
- }
- | cost TIMES cost =
- {
- $$ = $1 * $3;
- }
- | cost DIVIDE cost =
- {
- if ($3 == 0)
- yyerror("zero term in divison\n");
- else
- $$ = $1 / $3;
- }
- ;
-
-%%
-
-yyerror(s) char *s;
-{
- fprintf(stderr, "%s: ", ProgName);
- if (Cfile)
- fprintf(stderr, "\"%s\", ", Cfile);
- fprintf(stderr, "line %d: %s\n", Lineno, s);
-}
-
-fixnet(n, yl, yr, cost, netid)
-node *n;
-YYSTYPE *yl, *yr;
-Cost cost;
-int netid;
-{
- link *l;
- char netdir;
- char netchar;
-
- if (yl->y_s.ys_ind && yr->y_s.ys_ind) {
- yyerror("two net indicators\n");
- netchar = DEFNET;
- netdir = DEFDIR;
- } else if (yl->y_s.ys_ind) {
- netchar = yl->y_s.ys_ind;
- netdir = yl->y_s.ys_dir;
- } else if (yr->y_s.ys_ind) {
- netchar = yr->y_s.ys_ind;
- netdir = yr->y_s.ys_dir;
- } else {
- netchar = DEFNET;
- netdir = DEFDIR;
- }
-
- for (l = n->n_link; l; l = l->l_next)
- if (l->l_lnet == netid) {
- l->l_flag &= (~LNETCHARS|LDIR);
- l->l_flag |= netbits(netchar) | dirbits(netdir);
- l->l_cost = cost;
- (void) addlink(l->l_to, n, (Cost) 0, netchar, netdir);
- }
-}
//GO.SYSIN DD parse.y
exit