[net.sources] build and access database of paths to systems on map

steiny@scc.UUCP (Don Steiny) (09/23/84)

***

	These utilities make a database of system name - path pairs.
	For historic reasons, the database, by default, is:

	/usr/lib/uucp/alpath

	The utility "mkalpath" reads through your map directory (be sure and
modify this shell script), makes a graph based on the "Mail: " fields
of the entries and produces a list of paths from the local machine
to each machine on the map.   The README, manual pages, and comments
in the code go into more detail.  The paths are as short as possible,
there are no shorter paths, though there might be other paths as short.

No weight is given to one path over an other.   While it might be
a good idea to weight the edges with cost, polling frequency
or some such thing, right now just knowing most of the paths
is a lot to ask for.

	I have run this program on a 750 with 4.1bsd and on in
Interdata 8/32 with Wollongong V7 UNIX.

Don Steiny - Personetics @ (408) 425-0382
109 Torrey Pine Terr.
Santa Cruz, Calif. 95060
ihnp4!pesnta  -\
fortune!idsvax -> scc!steiny
ucbvax!twg    -/
	
---------------------- Cut Here ---------------------------------------------
: This is a shar archieve.  Extract with sh, not csh.
: The rest of this file will extract:
: README mkalpath.8 findp.8 mkmls.8 alpath.5 makefile findp.c adjm.c que.c getpos.c mkmls.c defs.h edefs.h mkalpath prpath.c prpath.1 creatdb.c creatdb.8
echo extracting - README
sed 's/^X//' > README << '~FUNKY STUFF~'
XThese programs and shell scripts make a database of all the
Xsystems in the usenet map paired with the path from the local
Xmachine to the machine.
X
XThe utility "prpath" takes an address in the form user@machine
Xand prints the full address of the user (useful in ` expantions).
X
XTo make the alpath database, modify the shell script
X"mkalpath" and the makefile for your system.  There are some
Xcomments to hint at what you might want to change.
X
XRun "make" to make the utilities the shell script uses.
X
XRun "make install" to install the executable files.
X
XChange into a scratch directory and execute mkalpath.
X
XThe "mkmls" utility reads through maps and pairs systems with
Xthe systems that are in the "Mail" field of the entry.
XIt outputs a list with system name on the first line and
Xall of the systems in the Mail field of the entry on the 
Xrest of the line.  It is best to do this with the entire map.
XIt deletes systems with only a path back to themselves known.
X
XIt then takes all of the systems breaks them up with tr, sorts them with
X-u and generates a list of the unique systems with mail pathways.
X
XThese two files are opened by "findp".  Findp loops through all
Xof the systems and finds the path from the current system
X(determined by "whoami.h" or by an argument) to each of the
Xsystems with on the list.   On our system it was 1187. (note,
Xthis was the last time, now there are 1235).
X
XThe way the alogrithm works is first it searches all the paths
Xof length one for the target system. Then all the paths of
Xlength two and so on.  When it finds a path, there can be no
Xshorter path.  This program stops looking, so there may be other
Xpaths as short.  
X
XBe extra careful to make sure that all the important entries
Xfor machines near you are filled out in the map.  
X
XThe data base should be regenerated every month when the new maps come.  
XIt takes about 10 minutes.   Between the last map and the most current
Xone (must be for August) there are 50 new machines.  Often connections
Xare made from one month to the next that considerably shorten the
Xdistance to many machines.
X
XA simple modification to readnews.c and readr.c make the return
Xaddresses on news items reflect the shortest mail path.
X
XI will do it with linked lists instead of an array someday.
X
XDon Steiny	September 1984
~FUNKY STUFF~
echo extracting - mkalpath.8
sed 's/^X//' > mkalpath.8 << '~FUNKY STUFF~'
X.TH mkalpath 8 LOCAL
X.SH NAME
Xmkalpath - make the alpath data base.
X.SH SYNOPSIS
Xmkalpath
X.SH DESCRIPTION
X.PP
X.I Mkalpath
Xis a shell script that calls the the utilities
X.I findp(8),
X.I mkmls(8),
Xand
X.I creatdb(8).
X.PP
X.I Mkmls
Xmakes a file.  Each line of the file is a system name
Xwith the systems that are in the "Mail" field of its 
Xmap entry on the line. 
XA sorted list of the individual systems is prepared
Xin a separate file. 
X.PP
XThe utility
X.I findp,
Xreads through the two files and generates a path
Xwith minimum hops to each of the systems found in 
Xthe maps. 
X.PP
XThe utility
X.I creatdb
Xcreates a database from the file.
X.PP
XThis shell script is for system adminsinstration.
XIt should be run each month by root as soon as the
Xnew usenet maps are installed in the map directory.
XThe superuser should cd into /tmp or some temporary working
Xarea and run this shell script. 
XThe old version of the database is saved in the uucp lib
Xdirectory and named "alpath.old".  The dbm files,
Xalpath.dir and alpath.pag are destroyed.
X.SH FILES
X/usr/lib/uucp/alpath
X.br
X/usr/lib/uucp/mkalpath
X.SH SEE ALSO
Xprpath(1), mkmls(8), findp(8), alpath(5)
X.SH DIAGNOSTICS
X.SH BUGS
X.SH AUTHOR
XDon Steiny  - September 1984
~FUNKY STUFF~
echo extracting - findp.8
sed 's/^X//' > findp.8 << '~FUNKY STUFF~'
X.TH findp 8 LOCAL
X.SH NAME
Xfindp - find paths.
X.SH SYNOPSIS
Xfindp [sys]
X.SH DESCRIPTION
X.PP
X.I Findp
Xreads a file of system names and with lines of systems and the
Xmachines they exchange mail with and makes a list
Xof paths from the current system to the remote systems.
XBy default, it reads the files MACH and MAIL in the current
Xdirectory.  These files are created by 
X.I mkalpath(8)
Xand
X.I mkmls(8).
X.PP
X.I Findp
Xoptionally takes an argument.
XThe argument is a system to find paths from instead 
Xof the current system.
X.SH FILES
X/usr/lib/uucp/alpaths
X.SH SEE ALSO
Xprpath(1), alpath(5), mkalpath(8), mkmls(8)
X.SH DIAGNOSTICS
X.SH BUGS
X.PP
XThe whole thing takes a long time.
XI used a matrix of bits to represent the graph and it 
Xis possible that in a few years the number of machines
Xwill be so large that the array will be too big for 
Xour Interdata 8/32.
X.SH AUTHOR
XDon Steiny - September 1984
~FUNKY STUFF~
echo extracting - mkmls.8
sed 's/^X//' > mkmls.8 << '~FUNKY STUFF~'
X.TH mkmls 8 LOCAL
X.SH NAME
Xmkmls - make mail list.
X.SH SYNOPSIS
Xmkmls map_file ... 
X.SH DESCRIPTION
X.PP
X.I Mkmls
Xreads through 
X.I usenet
Xmap files and outputs each system 
Xwith the systems that it exchanges mail with.
XIt finds the name from the "Name" field of the
Xmap file and the mail from the "Mail" field.
XThe file is intendended to be input to 
X.i findp(8).
X.SH FILES
X.SH SEE ALSO
Xfindp(8), mkalpath(8), mkmls(8), alpath(5), prpath(1)
X.SH DIAGNOSTICS
X.SH BUGS
X.SH AUTHOR
XDon Steiny - September	1984
~FUNKY STUFF~
echo extracting - alpath.5
sed 's/^X//' > alpath.5 << '~FUNKY STUFF~'
X.TH alpath 5 LOCAL
X.SH NAME
X/usr/lib/uucp/alpath
X.SH SYNOPSIS
X.SH DESCRIPTION
X.PP
X.I /usr/lib/uucp/alpath
Xis a file of system name - path pairs.
XThe path to all the systems on the map is computed by 
X.I mkalpath(8)
Xand the datafile is prepared.
X.PP
XTwo 
X.I dbm(3)
Xfiles are created in the lib directory,
X.ul
Xalpath.dir
Xand
X.ul
Xalpath.pag.
X.PP
XThis database should be updated monthly when new maps come in.
X.SH FILES
X/usr/lib/uucp/alpath
X.br
X/usr/lib/uucp/alpath.dir
X.br
X/usr/lib/uucp/alpath.pag
X.SH SEE ALSO
X.SH DIAGNOSTICS
X.SH BUGS
X.SH AUTHOR
XDon Steiny	September, 1984
~FUNKY STUFF~
echo extracting - makefile
sed 's/^X//' > makefile << '~FUNKY STUFF~'
X# these are for the Interdata 8/32.  The -m is to compile the dbm stuff
X# the 64 k is maximum stack size.  Probably unnecessarily big.
X# Don Steiny	September, 1984
XLD1 = -k 64k
XLD2 = -k 32k
XCPE  = -m
XCFLAGS = -O $(CPE)
X
X# data base library
XDBM = -ldbm
XUULIB = /usr/lib/uucp
XLIB = strsave.o strbrk.o
XBIN = /usr/local
XMAN = /usr/man
Xall: findp mkmls prpath creatdb
X
Xfindp: findp.o adjm.o que.o getpos.o $(LIB)
X	cc -o findp findp.o adjm.o que.o getpos.o $(LD1) $(LIB)
Xfindp.o: findp.c defs.h
Xque.o: defs.h que.c
Xadjm.o: adjm.c defs.h 
X
Xmkmls: mkmls.o $(LIB)
X	cc $(LD2) -o mkmls mkmls.o $(LIB)
X
Xprpath: prpath.o $(LIB) 
X	cc -o prpath prpath.o $(LIB) $(DBM)
X
Xcreatdb: creatdb.o $(LIB)
X	cc -o creatdb creatdb.o $(LIB) $(DBM)
X
Xclean:
X	-rm -f *.o mkmls findp core prpath creatdb 
X
Xinstall: install_exec install_man
X
Xinstall_exec:
X	-cp mkmls $(UULIB)/mkmls
X	-chmod 0755 $(UULIB)/mkmls
X	-chown news $(UULIB)/mkmls
X	-cp findp $(UULIB)/findp
X	-chmod 0755 $(UULIB)/findp
X	-chown news $(UULIB)/findp
X	-cp creatdb $(UULIB)/creatdb
X	-chmod 0755 $(UULIB)/creatdb
X	-chown news $(UULIB)/creatdb
X	-cp prpath $(BIN)
X	-chmod 0755 $(BIN)/prpath
X	-chown bin $(BIN)/prpath
X
Xinstall_man:
X	-cp prpath.1 $(MAN)/man1/prpath.1
X	-chmod 0644 $(MAN)/man1/prpath.1
X	-chown bin $(MAN)/man1/prpath.1
X	-cp mkalpath.8 $(MAN)/man8/mkalpath.8
X	-chmod 0644 $(MAN)/man8/mkalpath.8
X	-chown bin $(MAN)/man8/mkalpath.8
X	-cp findp.8 $(MAN)/man8/findp.8
X	-chmod 0644 $(MAN)/man8/findp.8
X	-chown bin $(MAN)/man8/findp.8
X	-cp mkmls.8 $(MAN)/man8/mkmls.8
X	-chmod 0644 $(MAN)/man8/mkmls.8
X	-chown bin $(MAN)/man8/mkmls.8
X	-cp alpath.5 $(MAN)/man5/alpath.5
X	-chmod 0644 $(MAN)/man5/alpath.5
X	-chown bin $(MAN)/man5/alpath.5
X	-cp creatdb.8 $(MAN)/man8/creatdb.8
X	-chmod 0644 $(MAN)/man8/creatdb.8
X	-chown bin $(MAN)/man8/creatdb.8
X
Xmkshar:
X	shar README mkalpath.8 findp.8 mkmls.8 alpath.5 makefile findp.c \
Xadjm.c que.c getpos.c mkmls.c defs.h edefs.h mkalpath prpath.c prpath.1 \
Xcreatdb.c creatdb.8 > alpath.shar
~FUNKY STUFF~
echo extracting - findp.c
sed 's/^X//' > findp.c << '~FUNKY STUFF~'
X/* findp.c - read through file of system names and mail and
X   construct a file of lines of the form:
X
X   system_name path_to_system
X
X   Don Steiny	September 1984
X*/
X#include <stdio.h>
X#include <whoami.h>
X#ifndef SYSNAME
X#define SYSNAME sysname
X#endif
X#include "defs.h"
X#include "edefs.h"
X
X/* file generated by "mkmls" and file of sorted names of 
X   systems from "mkmls"
X */ 
X#define	MAIL "./MAIL"
X#define MACH "./MACH"
X
Xmain(ac,av)
Xchar **av;
X{
X	char	*sys;		/* name of starting system */
X	int	to = 0;		/* # of system that path is to */
X	int	from = 0;	/* # of system thhat path if from */
X	SET	*edges = 0; 	/* set of connected edges of graph */
X	SET	*bfs();		/* breadth first search */
X
X	if(ac < 2)		
X		sys = SYSNAME;	/* default system name in "whoami.h" */
X	else
X		sys = *++av;	/* system name on command line */
X	minit(MAIL,MACH);	/* initilize from prepared files */
X	from = getpos(sys);	/* get numeric value of from system */
X	if(from < 0)	/* can't find starting sys */
X	{	/* can't go on if this happens */
X		fprintf(stderr,"Can't find %s.\n",sys);
X		exit(1);
X	}
X	edges = bfs(from,edges);	/* make list of edges */
X	for(to=0;to<iht;to++)		/* for each system */
X	{
X		printf("%s ",index[to]);/* print system name */
X		prpath(edges,from,to);	/* print path to system */
X	}
X}
~FUNKY STUFF~
echo extracting - adjm.c
sed 's/^X//' > adjm.c << '~FUNKY STUFF~'
X/* adjm.c - routines to manipulate an adjacancy matrix 
X   	representation of a graph.
X
X	Don Steiny, September 1984
X*/
X#include <stdio.h>
X
X#include "defs.h"
Xunsigned short adjm[WIDTH*16][WIDTH];	/* adjency matrix for graph */
Xchar	*index[WIDTH*16];		/* index of system names */
Xint	iht = 0;			/* count of systems */
Xextern errno;
X
X/* minit - initalize adjacency matrix.
X
X   This routine takes two file names as arguments.
X   The first is a list of the systems.
X   The second is a file of system names with all the systems they
X   exchange mail with on the same line.  This file is prepared
X   by the utility "mkmls" (make map list).  The first file is
X   prepared from the map list file by breaking it into words and
X   sorting and deleting duplicates.  
X*/
Xminit(sysf,mailf)
Xchar *sysf, *mailf;
X{
X	register i, j;
X	FILE *f, *fopen();
X	char buf[256];
X	char *args[256];
X	int  nargs = 0;
X	int  to = 0, from = 0;
X
X    	/* make list of system names */
X	f = fopen(sysf,"r");
X	if(!f)
X		perror(sysf), exit(errno);
X	while(fgets(buf,256,f))
X	{
X		buf[strlen(buf)-1] = 0;
X		index[iht++] = (char *) strsave(buf);
X	}
X	index[iht] = (char *) 0;
X	fclose(f);
X	f = fopen(mailf,"r");
X	if(!f)
X		perror(mailf), exit(errno);
X	/* read through file of mail names */
X	while(fgets(buf,256,f))
X	{
X		nargs = strbrk(buf,args,0); 	/* break up line */
X		from = getpos(args[0]);		/* from first arg */
X		if(from<0)			/* not on list of systems */
X			continue;		/* keep going, don't complain */
X		for(i=1;i<nargs;i++)	/* to each of the others */
X		{
X			if(!*args[i] || !strcmp(args[0],args[i]))
X				continue;
X			to = getpos(args[i]);	/* get number value of arg */
X			if(to<0)		/* can't find it */
X				continue;	/* keep going */
X			SETB(from,to);		/* set bit in adjm */
X			SETB(to,from);		/* paths are both ways */
X		}
X	}
X	fclose(f);	/* close this file too */
X}
X/* for debugging only.  Prints adjancy matrix 
X */
Xpradjm()
X{
X	register i, j;
X
X	for(i=0;i<iht;i++)
X	{
X		printf("%-16s",index[i]);
X		for(j=0;j<iht;j++)
X			if(IFBIT(i,j))
X				printf("%s ",index[j]);
X		printf("\n");
X	}
X}
X/* bfs - breadth first search.
X   from each vertex, v search each vertex that is one distant,
Xeach that is two distant and so on.  Make a set of edges.
XThe set data structure contains vertex pairs that represent a
Xconnected edge of the graph.
X 
X   This came straight out of "Data Structures and Algorithms by
X   Aho, Hopcraft, and Ullman.  p. 243
X*/
Xint 	visited[WIDTH*16];	/* so only visit each node once */
X
XSET *bfs(v,edges)
XSET *edges;
X{
X	register i;		/* an index */
X	QUEUE	*q = 0;		/* queue of unvisited verticies */
X	QUEUE	*makenull();	/* null queue */
X	QUEUE	*dequeue();	/* remove from queue */
X	QUEUE	*enqueue();	/* add to queue */
X	SET	*insert();	/* add to edge set */
X	int	x = 0;		/* current vertex */
X
X	edges = (SET *) 0;	/* initialize edge set to null */
X	visited[v] = 1;		/* mark this vertex visited */
X	q = makenull(q);	/* make null queue - q */
X	q = enqueue(v,q);	/* put this vertex in the queue */
X	while(!empty(q))	/* while the queue is not empty */
X	{
X		x = front(q);	/* find value of first cell in queue */
X		q = dequeue(q);	/* remove cell from queue */
X		for(i=0;i<iht;i++)	/* look at matrix for unvisited */
X		{			/* verticies that are connected */
X			if(!visited[i] && IFBIT(x,i))
X			{
X				visited[i] = 1;		/* mark as visited */
X				q = enqueue(i,q);	/* add to queue */	
X				edges = insert(edges,x,i,0); /* add edge */
X							/* previous: 0 */
X			}
X		}
X	}
X	return(edges);	/* return the collected edge set */
X}
X/* for debugging */
Xprls(s)
XSET *s;
X{
X	if(s)
X	{
X		printf("%s %s\n",index[s->v1],index[s->v2]);
X		prls(s->s_next);
X	}
X}
X/* for debugging */
Xbprls(s)
XSET  *s;
X{
X	if(s)
X	{
X		printf("%s %s\n",index[s->v1],index[s->v2]);
X		bprls(s->s_pre);
X	}
X}
X/* recover path by tracking backwards through edges 
X */
Xchar	*stack[64];
Xint	sp = 0;
Xprpath(set,from,to)
XSET *set;
X{
X	SET   *s, *tail();
X	char	*pop(), *p;
X	int	pos = 0, cnt = 0;
X
X	pos = to;
X	push(index[to]);
X	for(s = tail(set);s;s=s->s_pre)
X	{
X		if(s->v2 == pos)
X		{
X			pos = s->v1;
X			if(pos == from)			
X				break;
X			push(index[pos]);
X		}
X	}
X	while(p = pop())
X	{
X		if(!cnt)
X			++cnt;
X		else
X			printf("!");
X		printf("%s",p);
X	}
X	printf("\n");
X}
XSET *tail(set)
XSET *set;
X{
X	SET *s;
X
X	for(s=set;s->s_next;s=s->s_next)
X		;
X	return(s);
X}
Xpush(str)
Xchar *str;
X{
X	stack[sp++] = (char *) strsave(str);
X	stack[sp] = (char *) 0;
X}
Xchar *pop()
X{
X	char *o;
X
X	--sp;
X	if(sp < 0)
X	{
X		sp = 0;
X		return((char *) 0);
X	}
X	o = (char *) strsave(stack[sp]);
X	if(stack[sp])
X		free(stack[sp]);
X	stack[sp] = (char *) 0;
X	return(o);
X}
~FUNKY STUFF~
echo extracting - que.c
sed 's/^X//' > que.c << '~FUNKY STUFF~'
X/* routines to maintain a queue 
X
X   Don Steiny  September 1984
X*/
X#include <stdio.h>
X#include "defs.h"
X#include "edefs.h"
X/* makenull - make an empty queue
X */
Xmakenull(q)
XQUEUE *q;
X{
X	q = (QUEUE *) malloc(sizeof(QUEUE));
X	q->front = q->rear = (CELL *) 0;
X	return(q);
X}
X/* empty - 1 if queue is empty, 0 if not
X */
Xempty(q)
XQUEUE *q;
X{
X	if(q->front == q->rear)
X		return(1);
X	return(0);
X}
X/* front - return value of first element of queue 
X */
Xfront(q)
X{
X	if(empty(q))
X		return(0);
X	else
X		return(q->front->c_next->c_el);
X}
X/* enqueue - add n to queue q and return new queue
X */
XQUEUE	*enqueue(n,q)
XQUEUE	*q;
X{
X	q->rear->c_next = (CELL *) malloc(sizeof(QUEUE));
X	q->rear = q->rear->c_next;
X	q->rear->c_el = n;
X	q->rear->c_next = (CELL *) 0;
X	return(q);
X}
X/* dequeue - remove first item from queue q
X */
XQUEUE *dequeue(q)
XQUEUE *q;
X{
X	if(empty(q))
X		return((QUEUE *)0);
X	else
X		q->front = q->front->c_next;
X	return(q);
X}
X/* insert path from j to k into set of edges and return new set.
X */
XSET *insert(s,j,k,spre)
XSET *s, *spre;
X{
X	if(!s)	/* found end of list */
X	{	/* make new node */
X		s = (SET *) malloc(sizeof(SET));
X		s->v1 = j;
X		s->v2 = k;
X		s->s_pre = spre;	/* pointer to previous node */
X		s->s_next = (SET *) 0;
X		return(s);
X	}
X	else
X		s->s_next = insert(s->s_next,j,k,s);	/* keep looking */
X	return(s);
X}
~FUNKY STUFF~
echo extracting - getpos.c
sed 's/^X//' > getpos.c << '~FUNKY STUFF~'
X/* getpos - do binary search on array to get position of
X   system in index array.
X  
X   Don Steiny	September 1984
X */
Xextern char *index[];	/* names of systems */
Xextern iht;		/* count - number of systems */
X
Xgetpos(str)
Xchar *str;
X{
X	int top = 0;	/* top of partition */
X	int bot = 0;	/* bottom of partition */
X	int mid = 0;	/* middle of partition */
X	int val = 0; 	/* value returned from strcmp */
X
X	top = iht;
X	while(bot <= top)
X	{
X		mid = (top + bot) / 2;
X		val = strcmp(str,index[mid]);
X		if(!val)
X			return(mid);
X		else if(val < 0)
X			top = mid - 1;
X		else 
X			bot = mid + 1;
X	}
X	return(-1);
X}
~FUNKY STUFF~
echo extracting - mkmls.c
sed 's/^X//' > mkmls.c << '~FUNKY STUFF~'
X/* mkmls - make map list
X   This reads though the argument files, assumed to be usenet
Xmaps and makes a file with each system and the systems it exchanges
Xmail with on a line.
X
X   Don Steiny	September 1984
X*/
X#include <stdio.h>
Xextern errno;
X
Xmain(ac,av)
Xchar **av;
X{
X	char    buf[4096], *p;
X	char	obuf[8192];
X	char    curname[32];
X	int     state = 0;
X	int	fd = 0;
X
X	while(--ac)
X	{
X		++av;
X		fd = open(*av,0);
X		if(fd<0)
X			continue;
X		while(getline(fd,buf))
X		{
X			switch(state)
X			{
X			case 0:
X				if(!strncmp(buf,"Name:",5))
X				{
X					strcpy(curname,&buf[6]);
X					curname[strlen(buf)-6] = 0;
X					state = 1;
X				}
X				break;
X			case 1:
X				if(!strncmp(buf,"Mail:",5))
X				{
X					write(1,curname,strlen(curname));
X					if(!buf[5])
X					{
X						write(1,"\n",1);
X						state = 0;
X					}
X					else
X					{
X						write(1," ",1);
X						state = 2;
X					}
X					strcpy(obuf,&buf[6]);
X					strcpy(curname,"");
X				}
X				break;
X			case 2:
X				if(blank(buf) || !strncmp(buf,"Comment",7))
X				{
X					write(1,obuf,strlen(obuf));
X					write(1,"\n",1);
X					state = 0;
X					break;
X				}
X				strcat(obuf," ");
X				if(*buf == '\t')
X					strcat(obuf,&buf[1]);
X				else
X					strcat(obuf,buf);
X				break;
X			}
X		}
X		close(fd);
X	}
X}
Xgetline(fd,line_b)
Xchar *line_b;
X{
X	register char ch = 0; 
X	register char *lp;
X	char *strsave(), lgetc();
X
X	lp = line_b;
X	while((ch = lgetc(fd))>0)
X	{
X		if(ch == '\n')
X		{
X			*lp = 0;
X			return(1);
X		}
X		*lp++ = ch;
X	}
X	*lp = 0;
X	return(0);
X}
Xchar lgetc(fd)
X{
X	static char  buf[512];
X	static char  *bp = buf;
X	static int   n = 0;
X	
X	if(n == 0)
X	{
X		n = read(fd,buf,512);
X		if(n <= 0)
X			return((char *) 0);
X		bp = buf;
X	}
X	return((--n >= 0) ? *bp++ & 0377 : (char) 0);
X}
X#define ISSPACE(x) (x==' '||x=='\t'||x=='\n')
Xblank(str)
Xchar *str;
X{
X	register char *s;
X
X	for(s=str;*s;s++)
X		if(!ISSPACE(*s))
X			return(0);
X	return(1);
X}
~FUNKY STUFF~
echo extracting - defs.h
sed 's/^X//' > defs.h << '~FUNKY STUFF~'
X/* definitions 
X   Don Steiny	September 	1984
X */
X#ifndef WIDTH		/* maximum machines == WIDTH * 16 */
X#define WIDTH 96	/* 96 * 16 == 1536 systems in matrix */
X#endif
X/* macros to test and set bit
X */
X#define IFBIT(x,y) ((adjm[x][y/16])&(01<<(y%16)))
X#define SETB(x,y) adjm[x][y/16] |= (01<<(y%16)&0xffff)
X/* typedef for cell of queue 
X */
Xtypedef struct cell_ {
X	int	c_el;
X	struct	cell_  *c_next;
X} CELL;
X/* typedef for queue
X */
Xtypedef struct que_ {
X	CELL	*front;
X	CELL	*rear;
X} QUEUE;
X/* typedef for set of edges 
X   doubly linked.
X */
Xtypedef struct set_ {
X	int	v1;
X	int	v2;
X	struct set_ *s_next;
X	struct set_ *s_pre;
X} SET;
XSET *insert(); /* routine to insert new edge in edge set */
~FUNKY STUFF~
echo extracting - edefs.h
sed 's/^X//' > edefs.h << '~FUNKY STUFF~'
X/* data available globally 
X   Don Steiny	September 1984
X*/
Xextern unsigned short *adjm[];	/* adjancy matrix */
Xextern char *index[];		/* names of systems */
Xextern iht;			/* number of systems */
Xextern errno;
~FUNKY STUFF~
echo extracting - mkalpath
sed 's/^X//' > mkalpath << '~FUNKY STUFF~'
X: 'Shell script to make alpath database'
X: Don Steiny - Sept. 1984
XMAPDIR=/usr/news/maps
XLIBDIR=/usr/lib/uucp
XFILES=*.*
X: make file of system/mail pairs
Xecho run this as root.;
Xecho 'making system/mail data file from map files'
X: fix for west 44, not sure why it did this or if it still does
X$LIBDIR/mkmls $MAPDIR/*.* | sort -u | sed 's/west 44/west44/'| grep ' ' > MACH;
Xecho 'making index of system names'
Xtr -cs '\@A-Za-z0-9-' '\012' < MACH | sort -u > MAIL;
Xecho 'making alpath file'
X$LIBDIR/findp > alpath;
Xecho 'making data base of paths'
X$LIBDIR/creatdb alpath;
Xecho 'alpath, alpath.dir, and alpath.pag are created - run "make install" to install'
X: 'script to install database';
XLIBDIR=/usr/lib/uucp;
Xecho making database;
X$LIBDIR/creatdb $LIBDIR/alpath;
Xecho installing $LIBDIR/alpath;
Xcp alpath $LIBDIR/alpath;
Xchmod 0644 $LIBDIR/alpath;
Xchown news $LIBDIR/alpath;
Xecho installing $LIBDIR/alpath.dir;
Xcp alpath.dir $LIBDIR/alpath.dir;
Xchmod 0644 $LIBDIR/alpath.dir;
Xchown news $LIBDIR/alpath.dir;
Xecho installing $LIBDIR/alpath.pag;
Xcp alpath.pag $LIBDIR/alpath.pag;
Xchmod 0644 $LIBDIR/alpath.pag;
Xchown news $LIBDIR/alpath.pag;
Xecho new alpath database is installed, removing unnecessary files.;
Xcp $LIBDIR/alpath $LIBDIR/alpath.old;
Xrm -f alpath* MACH MAIL;
~FUNKY STUFF~
echo extracting - prpath.c
sed 's/^X//' > prpath.c << '~FUNKY STUFF~'
X#include "alpath.h"
X#include <dbm.h>
Xmain(ac,av)
Xchar **av;
X{
X	datum	fetch(), d, key;
X	char	*args[4];
X	int  	nargs = 0;
X
X	dbminit(ALPATH);
X	while(--ac)
X	{
X		++av;
X		nargs = strbrk(*av,args,'@');
X		if(nargs == 1)
X		{
X			key.dptr = args[0];
X			key.dsize = strlen(args[0]);
X			d = fetch(key);
X			if(*d.dptr)
X				printf("%s\n",d.dptr);
X		}
X		else
X		{
X			key.dptr = args[1];
X			key.dsize = strlen(args[1]);
X			d = fetch(key);
X			if(*d.dptr)
X				printf("%s!%s\n",d.dptr,args[0]);
X		}
X	}
X}
~FUNKY STUFF~
echo extracting - prpath.1
sed 's/^X//' > prpath.1 << '~FUNKY STUFF~'
X.TH prpath 1 LOCAL
X.SH NAME
Xprpath - find path to system(s)
X.SH SYNOPSIS
Xprpath system ...
X.SH DESCRIPTION
X.PP
XArguments to
X.I prpath
Xare either the name of a system or the name of
Xa user at (@) a system.
XIt returns the full path of the user or the system relative
Xto the current machine.
X.PP
XThe line "alucero@visivax" returns "idsvax!fortune!visivax!alucero",
Xwhen executed on Santa Cruz Computer's computer.
X.PP
X.SH FILES
X/usr/lib/uucp/alpath
X.br
X/usr/lib/uucp/alpath.dir
X.br
X/usr/lib/uucp/alpath.pag
X.SH SEE ALSO
Xmkmls(8), findp(8), alpath(5)
X.SH DIAGNOSTICS
XTells you if it does not know the system.
X.SH BUGS
X.SH AUTHOR
XDon Steiny - September 1984
~FUNKY STUFF~
echo extracting - creatdb.c
sed 's/^X//' > creatdb.c << '~FUNKY STUFF~'
X#include <dbm.h>
X#ifdef NULL
X#undef NULL
X#endif
X#include <stdio.h>
X#include "alpath.h"
Xextern errno;
X
Xmain(ac,av)
Xchar **av;
X{
X	datum   d, key;
X	char    *args[4];
X	char	buf[256];
X	int	len = 0;
X	int	nargs = 0;
X	FILE	*f, *fopen();
X	char	dbname[64];
X
X	++av;
X	f = fopen(*av,"r");
X	if(!f)
X		perror(*av), exit(errno);
X	sprintf(dbname,"%s.dir",*av);
X	close(creat(dbname,0644));
X	sprintf(dbname,"%s.pag",*av);
X	close(creat(dbname,0644));
X	dbminit(*av);
X	while(fgets(buf,256,f))
X	{
X		nargs = strbrk(buf,args,0);
X		key.dptr = args[0];
X		key.dsize = strlen(args[0]);
X		d.dptr = args[1];
X		d.dsize = strlen(args[1]) + 1;
X		store(key,d);
X		if(args[0])
X			free(args[0]);
X		if(args[1])
X			free(args[1]);
X	}
X}
~FUNKY STUFF~
echo extracting - creatdb.8
sed 's/^X//' > creatdb.8 << '~FUNKY STUFF~'
X.TH creatdb 8 LOCAL
X.SH NAME
Xcreatdb - create alpath database.
X.SH SYNOPSIS
Xcreatdb database_name
X.SH DESCRIPTION
X.PP
X.I Creatdb
Xcreates a database.
XIt is made to work on name, pathname pairs in a file
Xgenerated by 
X.I mkalpath.
XIt is called by the shell script
X.I mkalpath
Xand is not intended as a human interface.
X.SH FILES
X/usr/lib/uucp/creatdb
X.SH SEE ALSO
Xprpath(1), mkalpath(8), mkmls(8), findp(8)
X.SH DIAGNOSTICS
X.SH BUGS
X.SH AUTHOR
XDon Steiny	September, 1984
~FUNKY STUFF~
exit 0;
-- 
Don Steiny - Personetics @ (408) 425-0382
109 Torrey Pine Terr.
Santa Cruz, Calif. 95060
ihnp4!pesnta  -\
fortune!idsvax -> scc!steiny
ucbvax!twg    -/

piet@mcvax.UUCP (Piet Beertema) (10/10/84)

<...>

For what it's worth...

I haven't seen the "mkmls" source, but from what I infer from the 165@terak
(ng net.sources.bugs) it does about the same as the following program. It's
a preprocessor for Jeff Donelly's buildmap (pathalias) program, taking as its
input the Usenet maps and giving for each site all the sites with which it is
linked; the links are taken from both the "News:" and the "Mail:" lines.
The program uses dynamically allocated memory only for building the connect
table. An adapted version of it takes the new uucpmap(s) as input.
The connect table is built in the form of a forward/backward linked list of
sites, each site linked to a forward/backward linked list of connections. Thus
it can quite easily be modified for other purposes, e.g. to completely replace
the buildmap program (haven't done that yet).

-----------------------------------------------------------------------------

/*
 * mkcon:
 *	make links list from USENET map data
 *
 * Author: Piet Beertema, CWI, Aug 1983
 */

#include <stdio.h>

#define SAME		0

struct site {
    char name[16];
    struct site	*prev;
    struct site	*next;
    struct con	*con;
};

struct con {
    struct site *consite;
    struct con	*prev;
    struct con	*next;
};

struct site *first = (struct site *)0;
FILE *ifd;

main(argc, argv)
int argc;
char **argv;
{
    register char *lp;
    register int v, gotline;
    register struct site *sitep;
    register struct con *conp;
    char line[100], verbose;
    struct site *cursite;
    struct con *curcon;
    extern struct site *newsite();

    verbose = 0;
    while (--argc) {
	if (argv[1][0] == '-') {
	    switch(argv[1][1]) {
		case 'v':
		    verbose++;
		    break;
		default:
		    error("bad key: %c\n", argv[1][1]);
	    }
	    argv++;
	    continue;
	}
	if ((ifd = fopen(*++argv, "r")) == 0)
	    error("Cannot open %s\n", *argv);
	if (verbose)
	    fprintf(stderr, "%s... ", *argv);
	while (gotline || readline(line)) {
	    gotline = 0;
	    lp = line;
	    if (strncmp(lp, "Name:", 5) == SAME) {
		while (*lp++);
		if (*lp == '\0')
			continue;
		if (first == (struct site *)0)
		    sitep = first = newsite(first, lp);
		else
		for (sitep = first; ; sitep = sitep->next) {
		    if ((v = strcmp(lp, sitep->name)) == SAME)
			break;
		    if (v < 0 || sitep->next == (struct site *)0) {
			sitep = newsite(sitep, lp, v < 0);
			break;
		    }
		}
		continue;
	    }
	    if (strncmp(lp, "News:", 5) == SAME ||
		strncmp(lp, "Mail:", 5) == SAME) {
		while (*lp++);
		setcon(sitep, lp);
		while (gotline = readline(line)) {
		    if (*(lp = line) != '*')
			break;
		    setcon(sitep, ++lp);
		}
	    }
	}
	if (verbose)
	    fprintf(stderr, "done\n");
	fclose(ifd);
    }
    for (sitep = first; sitep; sitep = sitep->next) {
	printf("%s\t", sitep->name);
	for (conp = sitep->con; conp; conp = conp->next)
		printf("%s ", conp->consite->name);
	printf("\n");
    }
}

readline(line)
char *line;
{
    register char *rlp;
    register int c;

    rlp = line;
    while (1) {
	while ((c = fgetc(ifd)) == '\n');
	if (c != ' ' && c != '\t')
	    break;
	while ((c = fgetc(ifd)) == ' ' || c == '\t');
	if (c != '\n') {
	    *rlp++ = '*';
	    break;
	}
    }
    if (c == EOF)
	return 0;
    do {
	*rlp++ = (c == ' ' || c == '\t') ? '\0' : c;
    } while ((c = fgetc(ifd)) != '\n');
    *rlp++ = '\0';
    *rlp++ = '\0';
    return 1;
}

struct site *
newsite(siteptr, name, insert)
register struct site *siteptr;
register char *name;
char insert;
{
    register struct site *cursite;

    cursite = (struct site *)malloc(sizeof (struct site));
    if (siteptr == (struct site *)0)
	cursite->prev = cursite->next = (struct site *)0;
    else
    if (insert) {
	cursite->next = siteptr;
	if (siteptr->prev)
	    siteptr->prev->next = cursite;
	cursite->prev = siteptr->prev;
	siteptr->prev = cursite;
	if (siteptr == first)
	    first = cursite;
    }
    else {
	siteptr->next = cursite;
	cursite->next = (struct site *)0;
	cursite->prev = siteptr;
    }
    cursite->con = (struct con *)0;
    strncpy(cursite->name, name, 15);
    return cursite;
}

struct con *
newcon(conptr, siteptr, insert)
register struct con *conptr;
register struct site *siteptr;
char insert;
{
    register struct con *curcon;

    curcon = (struct con *)malloc(sizeof (struct con));
    if (conptr == (struct con *)0)
	curcon->prev = curcon->next = (struct con *)0;
    else
    if (insert) {
	curcon->next = conptr;
	if (conptr->prev)
	    conptr->prev->next = curcon;
	curcon->prev = conptr->prev;
	conptr->prev = curcon;
    }
    else {
	conptr->next = curcon;
	curcon->next = (struct con *)0;
	curcon->prev = conptr;
    }
    curcon->consite = siteptr;
    return curcon;
}

setcon(siteptr, np)
register struct site *siteptr;
register char *np;
{
    register struct site *sitep;
    register struct con *conptr;
    register int v;
    extern struct site *newsite(), *findsite();
    extern struct con *newcon();

    while (*np != '\0') {
	for (sitep = first; ; sitep = sitep->next) {
	    if ((v = strcmp(np, sitep->name)) == SAME) {
		if ((conptr = sitep->con) == (struct con *)0)
		    sitep->con = newcon(conptr, siteptr, 0);
		else
		for (; ; conptr = conptr->next) {
		    if ((v = strcmp(siteptr->name, conptr->consite->name))
			== SAME)
			break;
		    if (v < 0 || conptr->next == (struct con *)0) {
			if (v < 0 && conptr == sitep->con)
		 	   sitep->con = newcon(conptr, siteptr, v < 0);
			else
			   newcon(conptr, siteptr, v < 0);
			break;
		    }
		}
		break;
	    }
	    if (v < 0 || sitep->next == (struct site *)0) {
		sitep = newsite(sitep, np, v < 0);
		sitep->con = newcon(sitep->con, siteptr, v < 0);
		break;
	    }
	}
	if ((conptr = siteptr->con) == (struct con *)0)
	    siteptr->con = newcon(conptr, findsite(np), 0);
	else {
	    for (; ; conptr = conptr->next) {
		if ((v = strcmp(np, conptr->consite->name)) == SAME)
		    break;
		if (v < 0 || conptr->next == (struct con *)0) {
		    if (v < 0 && conptr == siteptr->con)
			siteptr->con = newcon(conptr, findsite(np), v < 0);
		    else
			newcon(conptr, findsite(np), v < 0);
		    break;
		}
	    }
	}
	while (*np++);
    }
}

struct site *
findsite(name)
{
    register struct site *sitep;

    for (sitep = first; sitep; sitep = sitep->next) {
	if (strcmp(name, sitep->name) == SAME)
	    return sitep;
    }
    fprintf(stderr, "Can't find site %s\n", name);
    exit(1);
}

error(fmt, arg)
{
    fprintf(stderr, fmt, arg);
    exit(1);
}
---------------------------------------------------------------------------- 
	Piet Beertema, CWI, Amsterdam
	...{decvax,philabs}!mcvax!piet