honey@down.FUN (code 101) (01/21/85)
# To unbundle, sh this file
sed 's/.//' >README <<'//GO.SYSIN DD README'
-From down!honey Mon Jan 21 11:52:45 EST 1985
-To: whom it may concern
-Subject: new pathalias instructions
-
-cat CHANGES
-edit config.h
-edit Makefile
- peter
//GO.SYSIN DD README
sed 's/.//' >CHANGES <<'//GO.SYSIN DD CHANGES'
-"Dead nets" for nets that require gateways. See man page.
-By popular request, no ! in dbm output file.
-Network character must be one of !@%: -- dot is dead.
-Private hosts. (Undocumented, but see lex.l if you're interested. Goal
- is to support host name collisions.))
-Discourage mixing of left- (@) and right-associative (!) operators.
-Magic @ <--> % rule in paths involving multiple @'s.
-
-Use cheapest among duplicate links.
-Pure directed graph model.
-Reverse the sense of the -c (cost) flag.
-Don't list duplicate links -- they're normal.
-No network names in the output.
//GO.SYSIN DD CHANGES
sed 's/.//' >pathalias.1 <<'//GO.SYSIN DD pathalias.1'
-.TH PATHALIAS 1
-.SH NAME
-pathalias \- compute shortest paths
-.SH SYNOPSIS
-.B pathalias
-[
-.B \-vcibp
-] [
-.B \-l
-host] [
-.B \-d
-link] [
-.ig
-.\" the -g option is for pathparse. it's not really used by pathalias.
-file] [
-..
-.B \-P
-file] [inputfiles ...]
-.SH DESCRIPTION
-.I Pathalias
-computes the shortest paths and corresponding routes from one
-host to all other known, reachable hosts.
-\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.
-.PP
-For example,
-.RS
-.nf
-down princeton!(DEDICATED)
-princeton topaz!(DEMAND+LOW)
-topaz @rutgers(LOCAL)
-.fi
-.RE
-Costs may be arbitrary
-arithmetic expressions involving numbers, parentheses, '+', '\-', '*',
-and '/'. Several symbolic numbers are
-defined, as follows:
-.PP
-.RS
-.nf
-.ta 10m 20m
-LOCAL 25 (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
-In addition,
-DEAD is a very large number (effectively infinite),
-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 the output.
-.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, princeton, panic}!(LOCAL)
-ARPA = @{sri-unix, mit-ai, su-score}(DEDICATED)
-.fi
-.RE
-.PP
-Anything following # on an input line is ignored. A line that begins with white
-space is taken as a continuation of the previous line.
-.PP
-The output, which appears on the standard output,
-is a list of host\-route pairs,
-where route is a string appropriate for use with
-\fIprintf\fP(3), e.g.
-.RS
-.nf
-.ta 10m 20m
-rutgers princeton!topaz!%s@rutgers
-.fi
-.RE
-The ``%s'' in the route string should be replaced by the
-user name at the destination host.
-(This task is normally performed by a mailer.)
-.PP
-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
-Options:
-.TP 6
-.B \-i
-Map all host names to lower case.
-.TP 6
-.B \-b
-Create a \fIdbm\fP(3) 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.
-.ig
-.\" the -g option is for pathparse. it's not really used by pathalias.
-.TP 6
-.BR \-g " file\^"
-Dump the edges of the graph into the named file.
-..
-.TP 6
-.BR \-l " host\^"
-Use host as local host name.
-.TP 6
-.BR \-P " file\^"
-Use ``file'' as the name of the \fIdbm(3)\fP database.
-The database key is host name, the stored
-value is a (null-terminated) path.
-.TP 6
-.BR \-d " link\^"
-Declares a dead link, host, or network.
-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.
-If link is a single host name, that
-host is treated as dead and will be used as an intermediate host of
-last resort on any path.
-If link is a network name, the network requires a gateway.
-.PP
-\fBGateways.\fP
-Normally, a network is represented by a pseudo-host with bidirectional
-links to network members.
-The links from pseudo-host to the members have the weight given in
-the input (or the default cost), while
-the links from the members to the pseudo-host
-have zero cost.
-Networks that are declared dead on the command line show these
-latter weights as very expensive links,
-effectively prohibiting paths within the network.
-In this case,
-the input should also show a link from some member(s) to the network;
-these hosts will act as gateways for the network.
-E.g., if CSNET is declared dead on the command line (with
-the -d flag) and the input contains
-.RS
-.nf
-CSNET = {...}
-csnet-relay CSNET
-.fi
-.RE
-then routes to CSNET hosts will use csnet-relay as a gateway,
-rather than some other csnet host that may not
-be able to act as a gateway.
-.SH FILES
-.ta \w'/usr/local/lib/palias.{dir,pag} 'u
-/usr/local/lib/palias.{dir,pag} default dbm output
-.SH COMPILE-TIME
-Edit config.h to accommodate \s-2UNIX\s0 variants.
-.SH AUTHORS
-Steve Bellovin (ulysses!smb)
-.br
-Peter Honeyman (princeton!honey)
//GO.SYSIN DD pathalias.1
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 -g
-CFLAGS =
-LDFLAGS =
-YFLAGS = -d
-OBJ = addlink.o addnode.o gethostnam.o lex.o local.o main.o mapit.o mem.o parse.o
-HDRS = def.h config.h
-SRC = addlink.c addnode.c gethostnam.c lex.l local.c main.c mapit.c mem.c parse.y
-CSRC = addlink.c addnode.c gethostnam.c lex.c local.c main.c mapit.c mem.c parse.c
-
-pathalias: $(OBJ)
- $(CC) $(LDFLAGS) $(OBJ) $(LIBE) -o pathalias
-
-
-tags: $(SRC) $(HDRS)
- ctags -w $(HDRS) $(SRC)
-
-bundle:
- @bundle README CHANGES pathalias.1 Makefile ${HDRS} ${SRC}
-
-$(OBJ): def.h
-
-def.h: config.h
- touch def.h
-# get -s sccs/s.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}
-PATHFILES = paths/[^.]* paths.sites/[^.]* paths.bell/[^.]* path.map/[^.]*
-DEAD = -d harpo -d zeppo -d chico -d gummo -d tucc -d fortune!analog -d CSNET -d BITNET -d ARPANET -d purdue -d pur-ee -d uiucdcs!uokmet -d hogpc
-# EDGES = -g /usr/local/lib/mail/edges
-ARGS = -ci $(NODES) $(DEAD)
-
-paths: ${SITES}
-
-${LOCAL}: paths/princeton
- pathalias -v ${ARGS} -l $@ $(EDGES) $(PATHFILES) > $@.new 2>ERRORS
- cut -f2- $@.new | sort >$@
-# rm $@.new
-
-# NEIGHBOR hosts have exactly the same links as LOCAL
-# turn
-# down %s
-# up up!%s
-# into
-# up %s
-# down down!%s
-${NEIGHBORS}: ${LOCAL}.new
- sed \
- -e "s/ ${LOCAL} %s$$/ $@ %s/" \
- -e "s/ $@ $@!%s$$/ ${LOCAL} ${LOCAL}!%s/" \
- ${LOCAL}.new > $@
-
-sendit: paths
- for i in $(NEIGHBORS); do\
- uucp -ga $$i $$i!/usr/local/lib/pathaliases;\
- uux -z -gb -a$$USER $$i!newaliases;\
- done
- touch sendit
-
-cat:
- cat $(PATHFILES) > CAT
-
-# reorder the output for princeton/sendmail/uubang
-princeton:
- pathalias ${ARGS} -l $@ $(PATHFILES)> $@.new 2>ERRORS
- sed -e 's/\([^ ]*\) \([^ ]*\) \([^ ]*\)/\2 \1 \3/' $@.new > $@
- rm $@.new
-
-edges:
- pathalias -ib -l princeton -P palias -g edges $(PATHFILES) > edges
//GO.SYSIN DD Makefile
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 6.1 (down!honey) 85/01/21";
-#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 0x001 /* this node invisible outside its definition file */
-#define DEHASH 0x002 /* removed from hash table yet? */
-#define ATSIGN 0x004 /* seen an at sign? used for magic @/% rules */
-#define MAPPED 0x008 /* done mapping this node */
-#define NDEAD 0x010 /* node is dead */
-#define HASLEFT 0x020 /* route has a left side net character */
-#define HASRIGHT 0x040 /* route has a right side net character */
-#define NNET 0x080 /* node is a network name */
-#define INDFS 0x100 /* used when removing net cycles */
-#define DUMP 0x200 /* we have dumped this net's edges */
-
-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; /* other private nodes in this file */
- node *n_root; /* root of net cycle */
- char *n_path; /* path to this host */
- Cost n_cost; /* cost to this host */
- short n_tloc; /* back ptr to heap/hash table */
- short 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 0x3
-#define LBANG 0x0
-#define LCOLON 0x1
-#define LAT 0x2
-#define LPERCENT 0x3
-
-#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 Cflag;
-extern int Bflag;
-extern int Pflag;
-extern int Iflag;
-extern int Ncount;
-extern int Lcount;
-extern char *Pathout;
-extern char *Graphout;
-extern int Netid;
-extern node *Private;
//GO.SYSIN DD def.h
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 6.1 (down!honey) 85/01/21";
-#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 ALIASDB "/usr/local/lib/palias" /* 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 pointer?
- * i am told that 68000 based systems want ALIGN to be 1.
- */
-/* #define ALIGN 1 /* */
//GO.SYSIN DD config.h
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 6.1 (down!honey) 85/01/21";
-#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)) {
- /*
- * use new cost if cheaper.
- * exception: if the existing link is a zero
- * cost link to a dead network, use this cost.
- */
- if ((cost < l->l_cost)
- || (l->l_cost == 0
- && (to->n_flag & (NNET | NDEAD)) == (NNET | NDEAD))) {
- 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", ProgName, c);
- badmagic(1);
- /*NOTREACHED*/
-}
//GO.SYSIN DD addlink.c
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 6.1 (down!honey) 85/01/21";
-#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, 2039, 3067, 4093, 5113, 6133, 7159, 8179, 9209,
- 10223, 11261, 12281, 13309, 14327, 15349, 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) {
- char buf[BUFSIZ];
-
- sprintf(buf, "warning: alias redeclaration: %s = %s",
- parent->n_name, parent->n_name);
- yyerror(buf);
- return; /* caused by redeclaration of alias */
- }
-
- /* avoid alias loops, force many-to-one */
- /* can't happen -- wish it could ... */
- if (parent->n_alias || child->n_alias) {
- yyerror("can't nest aliases");
- 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->n_link = 0;
- 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 */
-#define HASH1(n) ((n) % Tabsize);
-#define HASH2(n) (((n) % (Tabsize - 2)) + 1)
-
-/*
- * at 75% full, probes per access is about 2.
- */
-#define HIGHWATER 75
-#define LOWWATER 50
-#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;
-
- if (Tabindex < 0) { /* first time */
- Tabindex = 0;
- Tabsize = Primes[0];
- Table = newtable(Tabsize);
- } else if (isfull(Ncount, Tabsize)) { /* too full -- rehash */
- register 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", ProgName,
- 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 < 0)
- probe += Tabsize;
- }
- return(probe);
-}
-
-STATIC
-fold(s)
-register char *s;
-{
- register sum = 0;
-
- while (*s) {
- sum <<= 2;
- sum += *s++;
- }
- if (sum < 0)
- sum = -sum;
- return(sum);
-}
-
-/* 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;
- /* private hosts too hard to account for ... */
- if (index(Table[i]->n_name, '!'))
- continue;
- count = 1;
- probe = fold(Table[i]->n_name);
- /* don't change the order of the next two lines */
- hash2 = HASH2(probe);
- probe = HASH1(probe);
- /* thank you! */
- while (Table[probe] != 0
- && strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
- count++;
- probe -= hash2;
- if (probe < 0)
- probe += Tabsize;
- }
- if (Table[probe] == 0) {
- fprintf(stderr, "%s: impossible hash error for %s\n",
- ProgName, Table[i]->n_name);
- 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
sed 's/.//' >gethostnam.c <<'//GO.SYSIN DD gethostnam.c'
-#ifndef lint
-static char *sccsid = "@(#)gethostnam.c 6.1 (down!honey) 85/01/21";
-#endif lint
-
-#ifndef GETHOSTNAME
-#include <stdio.h>
-
-void
-gethostname(name, len)
-char *name;
-{
- FILE *whoami, *fopen(), *popen();
- char *ptr, *index();
-
- *name = '\0';
-
- /* try /etc/whoami */
- if ((whoami = fopen("/etc/whoami", "r")) != 0) {
- (void) fgets(name, len, whoami);
- (void) fclose(whoami);
- if ((ptr = index(name, '\n')) != 0)
- *ptr = '\0';
- }
- if (*name)
- return;
-
- /* try /usr/include/whoami.h */
- if ((whoami = fopen("/usr/include/whoami.h", "r")) != 0) {
- while (!feof(whoami)) {
- char buf[100];
-
- if (fgets(buf, 100, whoami) == 0)
- break;
- if (sscanf(buf, "#define sysname \"%[^\"]\"", name))
- break;
- }
- (void) fclose(whoami);
- if (*name)
- return;
- }
-
- /* ask uucp */
- if ((whoami = popen("uuname -l", "r")) != 0) {
- (void) fgets(name, len, whoami);
- (void) pclose(whoami);
- if ((ptr = index(name, '\n')) != 0)
- *ptr = '\0';
- }
- if (*name)
- return;
-
- /* aw hell, i give up! is this a real unix? */
- return;
-}
-#endif GETHOSTNAME
//GO.SYSIN DD gethostnam.c
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 6.1 (down!honey) 85/01/21";
-#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", 25},
- {"HOURLY", 500},
- {"EVENING", 1800},
- {"WEEKLY", 30000},
- {"ARPA", 100},
- {"HIGH", -5}, /* baud rate bonus */
- {"LOW", 5}, /* baud rate penalty */
- {"DEAD", INF/2},
- {"POLLED", 5000},
- {"A", 300},
- {"B", 500},
- {"C", 1800},
- {"D", 5000},
- {"E", 30000},
- {"F", INF/2},
- {"DED", 95},
- {"DIALED", 300},
- 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, errbuf[128];
-
- 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);
- }
- sprintf(errbuf, "unknown cost (%s), using default cost", yytext);
- yyerror(errbuf);
- yylval.y_cost = DEFCOST;
- return(COST);
- } 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
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 6.1 (down!honey) 85/01/21";
-#endif lint
-
-#include <stdio.h>
-#include "config.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
-}
//GO.SYSIN DD local.c
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 6.1 (down!honey) 85/01/21";
-#endif lint
-
-#include "def.h"
-
-node *Home;
-int Fcnt = -1;
-char *Cfile;
-char **Ifiles;
-char *ProgName;
-int Vflag;
-int Cflag;
-int Bflag;
-int Pflag;
-int Iflag;
-int Lineno = 1;
-char *Netchars = "!:@%"; /* sparse, but sufficient */
-int Ncount;
-int Lcount;
-char *Pathout = ALIASDB;
-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 '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 '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();
- if (*locname == 0) {
- locname = "lostinspace";
- fprintf(stderr, "%s: using \"%s\" for local name\n",
- ProgName, locname);
- }
-
- Home = addnode(locname, 0); /* add home node */
- Home->n_cost = 0; /* doesn't cost to get here */
-
- yyparse(); /* read in link info */
-
- hashanalyze();
-
- while (Home->n_alias)
- Home = Home->n_alias; /* bad practice, but conceivable */
-
- mapit(); /* compute shortest paths */
-
-#ifdef SHOWLINK
- showall();
-#endif SHOWLINK
-
- exit(0);
-}
-
-badmagic(n)
-{
-#ifdef DEBUG
- abort();
-#else !DEBUG
- exit(n);
-#endif DEBUG
-}
//GO.SYSIN DD main.c
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 6.1 (down!honey) 85/01/21";
-#endif lint
-
-#include "def.h"
-
-void reheap(), insert(), setpath(), pack(), swap();
-node *min_node();
-
-static int Hashpart, Nheap;
-
-#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;
- while (next->n_alias)
- 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; /* dead host */
- if (((next->n_flag & (NNET | NDEAD)) == (NNET | NDEAD))
- && (l->l_cost == 0))
- cost += INF/2; /* dead net */
- if (l->l_flag & LDEAD)
- cost += INF/2; /* dead link */
- if ((n->n_flag & HASLEFT) && (NETDIR(l) == LRIGHT))
- cost += DEFCOST; /* mix */
- if ((n->n_flag & HASRIGHT) && (NETDIR(l) == LLEFT))
- cost += DEFCOST; /* mix */
-
- 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 (Nheap != 0) {
- fprintf(stderr, "%s: null entry found in heap\n", ProgName);
- badmagic(1);
- }
-
- 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 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
-wdb(name, path)
-char *name, *path;
-{
- datum dbkey, dbpath;
-
- dbkey.dptr = name;
- dbkey.dsize = strlen(name)+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;
-{
- for ( ; *buf = *path; path++) {
- if (*path == '%') {
- switch(path[1]) {
- case 's':
- strcpy(buf, host);
- buf += strlen(buf);
- path++;
- break;
- case '%':
- *++buf = *++path;
- break;
- }
- } else
- buf++;
- }
-}
-
-amerge()
-{
- node *n, *a;
- int i;
-
- for (i = Hashpart; i < Tabsize; i++) {
- n = Table[i];
- if (n == 0) /* impossible, but ... */
- continue;
- for (a = n->n_alias; a; a = a->n_alias) {
- a->n_link = lmerge(a->n_link, n->n_link);
- n->n_link = 0;
- n = a;
- }
- }
-}
-
-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;
- long seekstart, seekend;
- node *n;
- char edges[256], blocks[256], command[256];
- FILE *bstream, *fopen(), *popen();
-
- untangle();
- sprintf(edges, "%s.e", Graphout);
- sprintf(blocks, "%s.b", Graphout);
- if ((estream = fopen(edges, "w")) == NULL) {
- fprintf(stderr, "%s: ", ProgName);
- perror(edges);
- return;
- }
- sprintf(command, "sort -o %s", blocks);
- if ((bstream = popen(command, "w")) == NULL) {
- fprintf(stderr, "%s: ", ProgName);
- perror(command);
- fclose(bstream);
- return;
- }
-
- seekstart = 0;
- for (i = Hashpart; i < Tabsize; i++) {
- n = Table[i];
- if (n == 0)
- continue; /* impossible, but ... */
- if (n->n_alias)
- continue;
- /* a minor optimization ... */
- if (n->n_link == 0)
- continue;
- /* special treatment for nets */
- if ((n->n_flag & NNET) && n->n_root != n)
- continue;
- fprintf(bstream, "%s\t%d", n->n_name, seekstart);
- fprintf(estream, "!%s\n", n->n_name);
- dumplist(n);
- seekend = ftell(estream);
- fprintf(bstream, "\t%d\n", seekend - seekstart);
- seekstart = seekend;
- }
- fclose(estream);
- pclose(bstream);
-}
-
-dumplist(n)
-node *n;
-{
- node *nxt, *r0, *r1;
- link *l;
-
- if ((n->n_flag & (DUMP | NNET)) == (DUMP | NNET))
- return;
- if (n->n_flag & NNET) {
- n->n_flag |= DUMP;
- /* get to root of n */
- for (r0 = n->n_root; r0 && r0 != r0->n_root; r0 = r0->n_root)
- ;
- }
- for (l = n->n_link ; l; l = l->l_next) {
- nxt = l->l_to;
- while (nxt->n_alias)
- nxt = nxt->n_alias;
- if (n == nxt)
- continue;
- if (nxt->n_flag & NNET) {
- /* get to root of nxt */
- for (r1 = nxt->n_root;
- r1 && r1 != r1->n_root;
- r1 = r1->n_root)
- ;
- /* are nxt and n nets on a common cycle? */
- if ((n->n_flag & NNET) && r0 == r1) {
- dumplist(nxt);
- continue;
- }
-
- putc('#', estream);
- fputs(r1->n_name, estream);
- } else
- fputs(nxt->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;
- }
-}
-
-/*
- * remove cycles in net definitions.
- *
- * strategy: well, let's see, we've used a priority queue,
- * a heap, several hash strategies, binary search, bipartite
- * matching ... what's left?
- *
- * depth-first search, of course! for each net, run
- * dfs on its neighbors (nets only). if we return to
- * a visited node, that's a net cycle. mark the cycle with
- * a pointer in the n_root field (which gets us closer to
- * the root of this portion of the dfs tree).
- */
-untangle()
-{
- int i;
- node *n;
-
- for (i = Hashpart; i < Tabsize; i++) {
- n = Table[i];
- if (n == 0 || (n->n_flag & NNET) == 0 || n->n_root)
- continue;
- dfs(n);
- }
-}
-
-dfs(n)
-node *n;
-{
- link *l;
- node *next;
-
- n->n_flag |= INDFS;
- n->n_root = n;
- for (l = n->n_link; l; l = l->l_next) {
- next = l->l_to;
- if ((next->n_flag & NNET) == 0)
- continue;
- if ((next->n_flag & INDFS) == 0) {
- dfs(next);
- if (next->n_root != next)
- n->n_root = next->n_root;
- } else
- n->n_root = next->n_root;
- }
- n->n_flag &= ~INDFS;
-}
//GO.SYSIN DD mapit.c
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 6.1 (down!honey) 85/01/21";
-#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
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 6.1 (down!honey) 85/01/21";
-#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.
- * later, in fixnet(), we will adjust the
- * cost and add a 0 cost member -> network
- */
- 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;
-{
- /* a concession to ucb's error(1) */
- if (Cfile)
- fprintf(stderr, "\"%s\", ", Cfile);
- else
- fprintf(stderr, "%s: ", ProgName);
- 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