Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!mit-eddie!think!ames!amdahl!drivax!holloway
From: holloway@drivax.UUCP
Newsgroups: net.sources
Subject: Path - find paths to UUCP sites
Message-ID: <1106@drivax.UUCP>
Date: Wed, 25-Mar-87 15:45:29 EST
Article-I.D.: drivax.1106
Posted: Wed Mar 25 15:45:29 1987
Date-Received: Sat, 28-Mar-87 00:49:48 EST
Reply-To: holloway@drivax.UUCP (Bruce Holloway)
Organization: Digitalis Research, Inc.
Lines: 868
Keywords: path finds UUCP paths and handles domains correctly.
Summary: Shortens Rnmail returns paths, too.

"path" is a quick utility to find paths from the local site to a remote
one. It uses pathalias to generate its database, which is incorporated into
the program in a highly compressed form.

Two utility programs massage the pathalias database before "path" gets hold
of it.

"pathfix" creates paths to certain domain gateways and leaf nodes in order
to facilitate the creation of the database, and

"walkdb" creates the ".c" files which make up the database. Ignore any
warnings from these two programs... they'll stop and tell you if there's
a serious problem.

"path" generates paths to sites, but it can also shorten those long
paths that "Rnmail" gets when you reply to netnews. The following
context diff illustrates this:

*** Rnmail.old	Thu Mar 12 12:06:07 1987
--- Rnmail	Thu Mar 12 14:58:56 1987
***************
*** 49,54
  cat=/bin/cat
  grep=/usr/ucb/grep
  rm=/bin/rm
  
  tmpart=/tmp/rnmail$$
  dotdir=${DOTDIR-${HOME-$LOGDIR}}

--- 49,56 -----
  cat=/bin/cat
  grep=/usr/ucb/grep
  rm=/bin/rm
+ mv=/bin/mv
+ lpath=/usr/local/bin/path
  
  tmpart=/tmp/rnmail$$
  dotdir=${DOTDIR-${HOME-$LOGDIR}}
***************
*** 59,64
  *)  case $1 in
      -h)
  	headerfile="$2"
  	case $# in
  	3) oldart=$3 ;;
  	esac

--- 61,71 -----
  *)  case $1 in
      -h)
  	headerfile="$2"
+ # cat $headerfile
+ 	$lpath -h <$headerfile >$tmpart
+ # cat $tmpart
+ 	$mv $tmpart $headerfile
+ # cat $headerfile
  	case $# in
  	3) oldart=$3 ;;
  	esac

#------------------------cut here-------------------------------------
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
#	README
#	Makefile
#	path.1
#	path.c
#	pathfix.c
#	walkdb.c
#	walkdb.h
# This archive created: Wed Mar 25 12:42:27 1987
# By:	Bruce Holloway (Digitalis Research, Inc.)
export PATH; PATH=/bin:/usr/bin:$PATH
echo shar: "extracting 'README'" '(1443 characters)'
if test -f 'README'
then
	echo shar: "will not over-write existing file 'README'"
else
cat << \SHAR_EOF > 'README'
"path" is a quick utility to find paths from the local site to a remote
one. It uses pathalias to generate its database, which is incorporated into
the program in a highly compressed form.

Two utility programs massage the pathalias database before "path" gets hold
of it.

"pathfix" creates paths to certain domain gateways and leaf nodes in order
to facilitate the creation of the database, and

"walkdb" creates the ".c" files which make up the database. Ignore any
warnings from these two programs... they'll stop and tell you if there's
a serious problem.

"path" generates paths to sites, but it can also shorten those long
paths that "Rnmail" gets when you reply to netnews. The following
context diff illustrates this:

*** Rnmail.old	Thu Mar 12 12:06:07 1987
--- Rnmail	Thu Mar 12 14:58:56 1987
***************
*** 49,54
  cat=/bin/cat
  grep=/usr/ucb/grep
  rm=/bin/rm
  
  tmpart=/tmp/rnmail$$
  dotdir=${DOTDIR-${HOME-$LOGDIR}}

--- 49,56 -----
  cat=/bin/cat
  grep=/usr/ucb/grep
  rm=/bin/rm
+ mv=/bin/mv
+ lpath=/usr/local/bin/path
  
  tmpart=/tmp/rnmail$$
  dotdir=${DOTDIR-${HOME-$LOGDIR}}
***************
*** 59,64
  *)  case $1 in
      -h)
  	headerfile="$2"
  	case $# in
  	3) oldart=$3 ;;
  	esac

--- 61,71 -----
  *)  case $1 in
      -h)
  	headerfile="$2"
+ # cat $headerfile
+ 	$lpath -h <$headerfile >$tmpart
+ # cat $tmpart
+ 	$mv $tmpart $headerfile
+ # cat $headerfile
  	case $# in
  	3) oldart=$3 ;;
  	esac
SHAR_EOF
fi
echo shar: "extracting 'Makefile'" '(763 characters)'
if test -f 'Makefile'
then
	echo shar: "will not over-write existing file 'Makefile'"
else
cat << \SHAR_EOF > 'Makefile'
# Makefile for PATH - requires PATHALIAS and the Usenet MAP.
# 
# Should work on any Unix system, but I've only tried it on BSD4.2.
# 
# v1.0	03/25/87	Bruce Holloway (drivax!holloway)

pathalias = /usr/local/bin/pathalias
getopt = /usr/local/bin/getopt.o

# MAP describes the location of the Usenet MAP files.

MAP = *.map /scratch/map/u.* /scratch/map/d.*

all:	pathfix walkdb path

path:	pathmap.a path.o
	cc -o path -O path.o pathmap.a $(getopt)

pathmap.a: $(MAP)
	$(pathalias) $(MAP) >path.out
	pathfix <path.out >path.fix
	walkdb <path.fix
	cc -c *.map.c
	rm pathmap.a
	ar r pathmap.a master.map.o br*.map.o
	ranlib pathmap.a
	rm *.map.*

pathfix: pathfix.o
	cc -o pathfix -O pathfix.o

walkdb:	walkdb.o
	cc -o walkdb -O walkdb.o

path.o walkdb.o: walkdb.h
SHAR_EOF
fi
echo shar: "extracting 'path.1'" '(1555 characters)'
if test -f 'path.1'
then
	echo shar: "will not over-write existing file 'path.1'"
else
cat << \SHAR_EOF > 'path.1'
.TH PATH 1 "25 March 1987"
.UC 4
.SH NAME
path \- find the best path to a UUCP site
.SH SYNOPSIS
.B path
site [site...]
.PP
.B path
-s pattern
.PP
.B path
-h <mail-header
.PP
.B path
-r path [path...]
.SH DESCRIPTION
This is a handy program to have when you're trying to find a path to a
machine, when all you have is its name. Also nice for finding cheap paths
to a 
.I very
remote machine, like
.I ihnp4.
.PP
.I path
understands domains, and will generate paths to the correct domain gateway
if no more direct path was found.
.I path
also understands the special case of the
.I .UUCP
domain, and will try to route the path directly to the destination site
before it tries for the gateway.
.TP 5
.B  \-s
This searches for paths to all sites matching the regular expression
.I pattern.
.TP 5
.B  \-r
Takes the full path to a user at another site, and finds a shorter or
cheaper path to it. If the destination site is unknown,
.I path
tries to find a path to the previous site on the list, and so on, until
it reaches the beginning of the list. If it still hasn't found a correct
path, it will assume the one given is correct and return that.
.TP 5
.B  \-h
Takes a standard mail or news header from standard input, and replaces
each path in a
.B To:
line with a shorter one, as in the
.I \-r
option.
This allows
.I Rnmail
(with a little modification) to automatically find shorter and
more reliable sites through
which to return mail than the ones given by default.
.TP 5
.I  site
Any valid UUCP site name.
.SH AUTHOR
Bruce Holloway (holloway@drivax.UUCP)
SHAR_EOF
fi
echo shar: "extracting 'path.c'" '(5175 characters)'
if test -f 'path.c'
then
	echo shar: "will not over-write existing file 'path.c'"
else
cat << \SHAR_EOF > 'path.c'
#include <stdio.h>
#include "walkdb.h"

#undef	DEBUG

extern WALK *dbase[];
extern int strcmp();
extern char *rindex();
extern char *index();

int strccmp();

WALK *lastsite = 0;

char prgname[128];
char site[128];
int numsites = 2;
char xpath[512];
int fullpath = 0;

int main(acnt,avar)
int acnt;
char *avar[];
{
    char *s;
    int argc, i;
    extern int optind;
    extern char *optarg;

    if(s = rindex(avar[0],'/')) ++s;
    else s = avar[0];
    strcpy(prgname,s);

    if(acnt < 2){
	fprintf(stderr,"%s: usage: %s <site> {<site>...}\n",prgname,prgname);
	exit(3);
	}

    while((i=getopt(acnt,avar,"s:rh")) != EOF){
	switch(i){
	    case 's':				/* Search for map */
		ssearch(optarg);
		break;
	    case 'r':
		fullpath = 1;
		break;
	    case 'h':
		header();
		return(0);
	    }
	}

   numsites = acnt - optind;
   for(; optind < acnt; ++optind){
	if(fullpath) upath(1,avar[optind]);
	else{
	    strcpy(site,avar[optind]);
	    findsite(1,xpath);
	    }
	}
}

header(){
    char iline[256];
    extern char *gets();

    fullpath = 1;
    numsites = 1;
    while(gets(iline)){
	if(!strncmp(iline,"To: ",4)){
	    upath(0,&iline[4]);
	    strcpy(&iline[4],xpath);
	    }
	printf("%s\n",iline);
	}
}

upath(prnt,fpath)
int prnt;
char *fpath;
{
    char uname[256];
    char itsite[256];
    int numbang, i;
    char *s;

    for(s=fpath, i=0; *s; ++s) i += (*s == '!');
    if(i < 2){
	strcpy(xpath,fpath);
	if(prnt) printf("%s\n",fpath);
	return;
	}

    for(numbang=1;; ++numbang){
	strcpy(itsite,fpath);
	for(s = &itsite[strlen(itsite)], i=0; s != itsite &&
							i < numbang ; --s)
	    if(*s == '!') ++i;
	if(i != numbang){
	    fprintf(stderr,"%s: couldn't find a known site.\n",prgname);
	    break;
	    }
	++s;
	strcpy(uname,s+1);
	*s = 0;
	s = rindex(itsite,'!');
	if(!s) s = itsite; else ++s;
	strcpy(site,s);
	if(findsite(0,xpath)){
	    strcat(xpath,"!");
	    strcat(xpath,uname);
	    if(prnt) printf("%s\n",xpath);
	    break;
	    }
	}
}

findsite(prnt,pname)
int prnt;
char *pname;
{
#ifdef DEBUG
fprintf(stderr,"findsite(0x%02x,pname) - site = %s\n",prnt,site);
#endif

    if(!(prnt & 0x80) && index(site,'.')) return(dodomain(prnt,pname));
    else{
	*pname = 0;
	if(!search(site[0],site,strcmp,pname) &&
           !search(chlower(site[0]),site,strccmp,pname) &&
           !search(chupper(site[0]),site,strccmp,pname)){
	    if(!(prnt & 0x40) && !fullpath)
		fprintf(stderr,"%s: Can't find a path to %s\n",prgname,site);
	    return(0);
	    }
	else{
	    if(prnt & 0x1){
		printf("%s\n",pname);
		}
	    return(1);
	    }
	}
}

dodomain(prnt,pname)
int prnt;
char *pname;
{
    char *s;
    char tsite[256];
    char tpath[256];

#ifdef DEBUG
fprintf(stderr,"dodomain(0x%02x,pname)\n",prnt);
#endif

    lastsite = 0;
    s = index(site,'.');
    strcpy(tsite,site);
    strcpy(site,s);
    if(!strccmp(site,".uucp")){
	strcpy(site,tsite);
	*s = 0;
	if(findsite(0xC0|prnt,pname)) return(1);
	strcpy(site,".uucp");
	}
    if(findsite(0xC0,tpath)){
	if(lastsite) strcpy(index(tsite,'.'),lastsite->wname);
	if((numsites > 1) && (s = index(tpath,':'))){
	    strcpy(pname,s);
	    strcpy(tpath,tsite);
	    strcat(tpath,pname);
	    }
	sprintf(pname,"%s!%s",tpath,tsite);
	if(prnt & 1) printf("%s\n",pname);
	return(1);
	}
    else{
	strcpy(site,tsite);
	return(findsite(prnt|0x80,pname));
	}
}

int chlower(ch)
int ch;
{
    return((ch >= 'A' && ch <= 'Z') ? ch-'A'+'a' : ch);
}

int chupper(ch)
int ch;
{
    return((ch >= 'a' && ch <= 'z') ? ch-'a'+'A' : ch);
}

int strccmp(s1,s2)
char *s1, *s2;
{
    while(*s1 && *s2 && chlower(*s1) == chlower(*s2)) ++s1, ++s2;
    return(chlower(*s1) - chlower(*s2));
}

ssearch(s)
char *s;
{
    register WALK *wr;
    register int j, i;
    int numfound = 0;
    char *e;
    extern char *re_comp();
    extern int re_exec();

    e = re_comp(s);
    if(e){
	fprintf(stderr,"%s: %s\n",prgname,e);
	return;
	}

    for(i=0; i<128; ++i){
	if(!(wr = dbase[i])) continue;
	for(j=0; wr; ++j, ++wr){
	    if(!(*(wr->wname))) break;
	    if(re_exec(wr->wname) == 1){
		strcpy(site,wr->wname);
		++numfound;
		findsite(1,xpath);
		}
	    }
	}
    if(!numfound)
	fprintf(stderr,"%s: Couldn't find any sites matching \"%s\".\n",
	    prgname,s);
}

int search(i,s,fn,pname)
int i;
char *s, *pname;
int (*fn)();
{
    register WALK *wr;
    register int j;

#ifdef DEBUG
fprintf(stderr,"search(0x%02x,\"%s\",fn,pname)\n",i,s);
#endif

    if(!(wr = dbase[i])) return(0);
    for(j=0; wr; ++j, ++wr){
	if(!(*(wr->wname))) break;
	if(!((*fn)(wr->wname,s))){
	    follow(i,j,pname);
	    return(1);
	    }
	}
    return(0);
}

follow(oi,oj,pname)
int oi, oj;
char *pname;
{
    int i, j;
    WALK *w;

    w = dbase[oi & 0x7F];
    w += oj;

    i = w->wflag;
    j = w->windex;

#ifdef DEBUG
fprintf(stderr,"%s: follow(0x%02x,0x%02x);\n",prgname,oi,oj);
fprintf(stderr,"\twname=\"%s\", wflag=0x%02x, windex=0x%02x.\n",
	w->wname,i,j);
#endif

    if((i & 0x7F) == oi && j == oj){
	if(numsites > 1) sprintf(pname+strlen(pname),"%s: ",site);
	strcat(pname,w->wname);
	return(1);
	}
    follow(i & 0x7F,j,pname);
    if(!(i & 0x80))
	sprintf(pname+strlen(pname),"!%s",w->wname);
    lastsite = w;
    return(0);
}
SHAR_EOF
fi
echo shar: "extracting 'pathfix.c'" '(1569 characters)'
if test -f 'pathfix.c'
then
	echo shar: "will not over-write existing file 'pathfix.c'"
else
cat << \SHAR_EOF > 'pathfix.c'
#include <stdio.h>

extern char *gets();
extern	char *malloc();
extern char *index(), *rindex();

char iline[256];

#define	PATH	struct _zap
PATH{
    PATH *next;
    char *site;
    char *path;
};

#define	newpath()	(PATH *)malloc(sizeof(PATH))

PATH *paths = 0;

main(){
    while(gets(iline)){
	addpath();
	}
    fixpaths();
    writepaths();
}

addpath(){
    char *s;
    char *s1;
    char *s2, *s3;
    PATH *p;

    s = index(iline,'\t');
    if(!s){
	fprintf(stderr,"No tab in path - \"%s\".\n",iline);
	return;
	}
    *s = 0;
    s1 = s+1;
    s = rindex(s1,'!');
    if(!s){
	fprintf(stderr,"No bang in path - \"%s\t%s\".\n",iline,s1);
	s = s1;
	}
    *s = 0;

    p = newpath();
    if(!p) outofmem();
    s2 = malloc(strlen(iline)+1);
    if(!s2) outofmem();
    s3 = malloc(strlen(s1)+1);
    if(!s3) outofmem();
    p->next = paths;
    paths = p;
    strcpy(s2,iline);
    strcpy(s3,s1);
    p->site = s2;
    p->path = s3;
}

outofmem(){
    fprintf(stderr,"Out of memory.\n");
    exit(1);
}

fixpaths(){
    register PATH *p1, *p2;
    register char *s;

    for(p1=paths; p1; p1=p1->next){
	s = rindex(p1->path,'!');
	if(!s) continue;
	++s;
	if(!strcmp(s,p1->site)) continue;
	for(p2=paths; p2; p2=p2->next){
	    if(!strcmp(s,p2->site)) goto cmain;
	    }
	sprintf(iline,"%s\t%s!%%s",s,p1->path);
	fprintf(stderr,"Adding line: \"%s\".\n",iline);
	addpath();
cmain: ;
	}
}

writepaths(){
    register PATH *p;

    for(p=paths; p; p=p->next){
	if(*(p->path))
	    printf("%s\t%s!%%s\n",p->site,p->path);
	else
	    printf("%s\t%%s\n",p->site);
	}
}
SHAR_EOF
fi
echo shar: "extracting 'walkdb.c'" '(3754 characters)'
if test -f 'walkdb.c'
then
	echo shar: "will not over-write existing file 'walkdb.c'"
else
cat << \SHAR_EOF > 'walkdb.c'
#include <stdio.h>

extern char *gets();
extern char *malloc();
extern char *index();
extern char *rindex();

char *zalloc();

#define	node	struct _node

node {
    node *nnext;
    char *myname;
    char *rname;
    char *lname;
    };

char msg_string[] = "string";
char msg_node[] = "node";

node *leaf[128];

char iline[1024];

#define	newstr(s)	zalloc(msg_string,strlen(s)+1)
#define	newnode()	(node *)zalloc(msg_node,sizeof(node))

main(){
    int i;

    for(i=0; i<128;) leaf[i++] = (node *)0;

    while(gets(iline)) addnode();
    writenode();
}

addnode(){
    int i;
    node *n;
    char *s, *s1, *s2;
    char *dstnode, *leafnode, *rootnode;
    static char zap[] = "!!";
    static char zip[] = "!!";

    dstnode = leafnode = rootnode = 0;

    s = index(iline,'\t');
    if(!s){
	fprintf(stderr,"warning: no tab in \"%s\".\n",iline);
	return;
	}
    dstnode = iline;
    *s = 0; s1 = s+1;
    s = rindex(s1,'!');
    if(!s){
	fprintf(stderr,"warning: better be host name \"%s\".\n",iline);
	return;
	}
    *s = 0;
    s2 = rindex(s1,'!');
    if(!s2){
	leafnode = s1;
	fprintf(stderr,"warning: better be direct link \"%s\".\n",iline);
	s2 = &zip[1];
	strcpy(zip,zap);
	}
    else leafnode = s2+1;
    *s2 = 0;
    s2 = rindex(s1,'!');
    if(!s2) s2 = s1;
    else ++s2;
    rootnode = s2;

    if(strcmp(dstnode,leafnode)) rootnode = 0;
    else leafnode = 0;    
#if 0
    if(rootnode)
	fprintf(stderr,"parent of %s is %s\n",dstnode,rootnode);
    else
	fprintf(stderr,"alias  of %s is %s\n",dstnode,leafnode);
#endif
    n = newnode();
    n->myname = newstr(dstnode);
    strcpy(n->myname,dstnode);
    if(rootnode){
	n->rname = newstr(rootnode);
	strcpy(n->rname,rootnode);
	}
    else n->rname = 0;
    if(leafnode){
	n->lname = newstr(leafnode);
	strcpy(n->lname,leafnode);
	}
    else n->lname = 0;
    i = *dstnode;
    n->nnext = leaf[i];
    leaf[i] = n;
}

char *zalloc(reason,size)
char *reason;
unsigned size;
{
    char *s;

    s = malloc(size);
    if(!s){
	fprintf(stderr,"Couldn't allocate %d bytes for a %s.\n",size,reason);
	exit(1);
	}
    return(s);
}

writenode(){
    int i, j;
    register node *n;
    FILE *ochan;
    char zap[50];

fprintf(stderr,"writing nodes now.\n");

    for(i=0; i<128; ++i)
	if(n=leaf[i]){
	    sprintf(zap,"br%d.map.c",i);
	    ochan = fopen(zap,"w");
	    if(!ochan){
		fprintf(stderr,"Couldn't open %s for writing.\n",zap);
		exit(2);
		}
	    fprintf(ochan,"#include \"walkdb.h\"\n\n");
	    for(j=0; n; ++j, n=n->nnext);
	    ++j;
	    fprintf(ochan,"WALK br%d[%d] = {\n",i,j);
	    for(n=leaf[i]; n; n=n->nnext){
		fprintf(ochan,"    { \"%s\", 0x", n->myname);
		if(n->rname){
		    fprintf(ochan,"%02x, ",*(n->rname));
		    j = lookfor(n->rname);
		    }
		else{
		    fprintf(ochan,"%02x, ",*(n->lname) + 0x80);
		    j = lookfor(n->lname);
		    }
		fprintf(ochan,"%d },\n",j);
		}
	    fprintf(ochan,"    { \"\", 0, 0 }\n};\n\n");
	    fclose(ochan);
	    }
    ochan = fopen("master.map.c","w");
    if(!ochan){
	fprintf(stderr,"Couldn't open master.map.c for writing.\n");
	exit(3);
	}
    fprintf(ochan,"#include \"walkdb.h\"\n\n");
    for(i=0; i<128; ++i)
	if(leaf[i])
	    fprintf(ochan,"extern WALK br%d[];\n",i);
    fprintf(ochan,"\n\nWALK *dbase[129] = {\n");
    for(i=0; i<128; ++i){
	if(leaf[i]) fprintf(ochan,"    br%d,\n",i);
	else fprintf(ochan,"    0,\n");
	}
    fprintf(ochan,"    0\n};\n");
    fclose(ochan);
}

lookfor(s)
char *s;
{
    register int i, j;
    register node *n;
    char *e;

    i = *s;
    n = leaf[i];
    if(!n){ e = "bad initial character"; goto error; }
    for(j=0; n; ++j, n=n->nnext){
	if(!strcmp(s,n->myname))
	    return(j);
	}
    e = "node not in leaf";
error:
fprintf(stderr,"lookfor(%s) - %s.\n",s,e);
    return(-1);
}
SHAR_EOF
fi
echo shar: "extracting 'walkdb.h'" '(85 characters)'
if test -f 'walkdb.h'
then
	echo shar: "will not over-write existing file 'walkdb.h'"
else
cat << \SHAR_EOF > 'walkdb.h'
#define	WALK	struct _walk

WALK {
    char *wname;
    int wflag;
    int windex;
};
SHAR_EOF
fi
exit 0
#	End of shell archive
-- 
Bruce Holloway - Relapsed Newsaholic
{seismo,hplabs,sun,ihnp4}!amdahl!drivax!holloway
Put the power of RANDOM NUMBERS to work FOR YOU!