# to unbundle, sh this file (in an empty directory)
echo COPYRIGHT 1>&2
sed >COPYRIGHT <<'-------cut here----- COPYRIGHT' 's/^X//'
X/*
X * The author of this software is Eric Grosse <ehg@bell-labs.com>.
X * Copyright (c) 1996 by Bell Laboratories, Lucent Technologies.
X * Permission to use, copy, modify, and distribute this software for any
X * purpose without fee is hereby granted, provided that this entire notice
X * is included in all copies of any software which is or includes a copy
X * or modification of this software and in all copies of the supporting
X * documentation for such software.
X * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
X * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHOR NOR LUCENT MAKES ANY
X * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
X * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
X */
X
-------cut here----- COPYRIGHT
echo Depend 1>&2
sed >Depend <<'-------cut here----- Depend' 's/^X//'
X#!/bin/sh
Xcase $1 in
X
X
X-c)	#  creates ".depend" file for local directory, of the form
X	#	F file.c
X	#	D entrypoint1
X	#	R external1
X	#	R external2
X	> .depend
X	for FILE in *.[cefr];do
X		echo "F $FILE"
X		OBJ=`echo $FILE|sed 's/\..$/.o/'`
X		make $OBJ 1>&2
X		nm $OBJ |	# the following works for SGI IRIX 5.1.1
X		sed -n 's/^[^|]*|[^|]*|[^|]*|//
X			/|ref=[0-9]* *|Text/d
X			s/^Proc *| *|Undefined|/R/p
X			s/^Proc *|end.*|Text *|/D/p' |
X		skip_posix | sort -u
X		rm $OBJ
X		sed -n 's/^#[ 	]*include[ 	]*"\(.*\)" *$/R \1/p' $FILE
X		echo ""
X	done >> .depend
X	ls *.h* 2>/dev/null |
X		while read FILE;do echo "F $FILE";echo "";done >> .depend
X	;;
X
X-t)	# prints filenames covering routines in $* for libraries in $LIBS
X	shift # get rid of -t
X	case $* in
X	all)	# *** return all files ***
X		for i in $LIBS;do
X			sed -n 's;^F ;'$i'/;p' $i/.depend
X		done | tr '\012' ' '
X		echo;;
X	*)	# ***cat .depend files for all LIBS, then search ***
X		# subtlety: have to add dir to F, hence make D explicit first.
X		U=
X		for i in $*; do U="$U $i $i"_; done
X		(for i in $LIBS; do
X			(cd $i
X			if test -r .depend; then
X				sed 's;^F \(.*\);F '$i'/\1\
XD \1;
X				  s;^R \([^/]*\)\.h$;R '$i'/\1.h;' .depend
X			else
X				ls | sed '/index/d
X					/readme/d
X					/disclaimer/d
X					/depend/d
X					s;^;F '$i'/;'
X			fi)
X		done) | getdepend $U | tr '\012' ' '
X		echo;;
X	esac
X	;;
X
X-d) echo 'digraph G {'
X	grep -v '^[DR].*\.h$' .depend | depend2dot | sort -u
X	echo '}';;
X
X*)	echo $0 -c   ... to build .depend file for local directory
X	echo 'LIBS={directories} $0 -t {symbols}   ... for transitive closure'
X	echo $0 -d   ... to create input for dot
X	exit 1
X	;;
X
Xesac
Xexit 0
-------cut here----- Depend
chmod +x Depend
echo Makefile 1>&2
sed >Makefile <<'-------cut here----- Makefile' 's/^X//'
Xgetdepend: getdepend.c Malloc.c hash.c
X	cc -s -o getdepend -O getdepend.c Malloc.c hash.c
X
Xclean:
X	rm -f *.o *.x retadd nreply core
X
-------cut here----- Makefile
echo Malloc.c 1>&2
sed >Malloc.c <<'-------cut here----- Malloc.c' 's/^X//'
X#include <stdlib.h>
X#include <string.h>
X#include <stdio.h>
X#include <stdarg.h>
X#include "depend.h"
X
Xint Error_rc = 1;  /* rarely, caller of Error() may want to set this */
Xextern int errno;
X
Xint
XError(char *fmt, ...)
X{
X	va_list ap;
X	va_start(ap,fmt);
X	if(vfprintf(stderr,fmt,ap)<0)
X		fprintf(stderr,"<vfprintf error>");
X	fputc('\n',stderr);
X	va_end(ap);
X	if(errno) perror("<");	/* may or may not be relevant */
X	exit(Error_rc);
X	/* NOTREACHED */
X	return(0);  /* so caller can use  crunch() || Error("bad"); */
X}
X
Xvoid *
XMalloc(size_t n)
X{
X	void	*p;
X	if(n==0)
X		n=1;
X	if (!(p = malloc((size_t)n)))
X		Error("unable to allocate %d bytes",n);
X	return p;
X}
X
Xvoid *
XRealloc(void *ReallocP, int ReallocN)
X{
X	if(ReallocN == 0)
X		ReallocN = 1;
X	if(!ReallocP)
X		ReallocP = Malloc(ReallocN);
X	else if(!(ReallocP = realloc(ReallocP, ReallocN)))
X		Error("unable to allocate %d bytes",ReallocN);
X	return(ReallocP);
X}
X
Xchar*
XStrdup(char* s)
X{
X	int l;
X	if (!s)
X		return 0;
X	l = strlen(s)+1;
X	return strcpy((char *)Malloc((size_t)l), s);
X}
X
X/* returns pointer to start of null-terminated line, or NULL if EOF */
Xchar*
XFgets(char* buf, int bufl, FILE* fp)
X{
X        char* s;
X        int l;
X
X        s = fgets(buf, bufl, fp);
X        if (s==NULL)
X                return NULL;
X        if (ferror(fp))
X                Error("read error");
X        l = strlen(buf)-1;
X        if (buf[l] == '\n')
X                buf[l] = '\0';
X        else if (l == bufl)
X                Error("line longer than %d characters", bufl);
X        return s;
X}
X
-------cut here----- Malloc.c
echo depend.h 1>&2
sed >depend.h <<'-------cut here----- depend.h' 's/^X//'
Xstruct HashEntry {char* Key; int Code;};
Xtypedef struct HashEntry *HashTable;
Xextern char*	Fgets(char*,int,FILE*);
Xextern void	hashdel(HashTable*,int);
Xextern int	hashins(HashTable*,int,char*,int);
Xextern int	hashasu(char*,int);
Xextern int	hashpjw(char*,int);
Xextern int	hashsrch(HashTable*,char*);
Xextern void*	Malloc(size_t);
Xextern void*	Realloc(void*,int);
Xextern char*	Strdup(char*);
-------cut here----- depend.h
echo getdepend.c 1>&2
sed >getdepend.c <<'-------cut here----- getdepend.c' 's/^X//'
X/* read .depend file, compute transitive closure for request */
X/* Eric Grosse  9 Dec 1993;  cleaned for export 21 Mar 1994 */
X
X/* This reads from stdin a .depend file and builds 1) an array of
Xfiles, each with a list of symbols referenced, and 2) a hash table
Xmapping defined symbols into files.  Now, to compute the transitive
Xclosure of a list of symbols given as arguments on the command line,
Xkeep a stack of symbols yet to be resolved, a stack of files yet to be
Xexpanded, and a list of files processed.  */
X
X#include <string.h>
X#include <stdio.h>
X#include "depend.h"
X
Xtypedef struct{
X	char *name;
X	char **ref;	/* array of symbols referenced by this file */
X	int nref;
X	int done;	/* has this already been added to hit? */
X} File;
X
Xtypedef struct{
X	File *file;
X	int nfile;
X	HashTable Def;	/* symbol -> index of file defining it */
X} Dependencies;
X
Xstatic void
Xsave_refs(File *f, int nref, char **ref)
X{
X	f->ref = (char**)Malloc(nref*sizeof(*f->ref));
X	memcpy(f->ref,ref,nref*sizeof(*f->ref));
X	f->nref = nref;
X}
X
Xvoid
Xgetdepend(Dependencies *d)
X{
X	int i;	/* HashTable index */
X	int nf = 0;	/* index of file being read */
X	int maxf = 1000; /* guess at an upper bound for nf */
X	int nref, maxref = 5000; /* guess at an upper bound for nref */
X	int linelen;
X	char *name;
X	char line[1000];  /* surely 100 would be enough, but what the heck */
X	char **ref = Malloc(maxref*sizeof(*ref));
X	File *f = Malloc(maxf*sizeof(*f));
X	HashTable D = 0;
X
X	while(Fgets(line,sizeof(line),stdin)!=NULL){
X		if(line[0]==0 || line[0]=='#') continue;
X		linelen = strlen(line);
X		if(line[linelen-1]=='\n')
X			line[--linelen] = '\0';
X		name = Strdup(line+2);
X		switch(line[0]){
X		  case 'F':
X			if(nf>0)
X				save_refs(&f[nf],nref,ref);
X			nref = 0;
X			nf++;
X			if(nf>=maxf){
X				maxf *= 2;
X				f=Realloc(f,maxf*sizeof(*f));
X			}
X			f[nf].name = name;
X			f[nf].done = 0;
X			/* FALL THROUGH (file implicitly defines own name) */
X		  case 'D': i = hashsrch(&D,name);
X			if(i<0) hashins(&D,i,name,nf);
X			break;
X		  case 'R':
X			nref++;
X			if(nref>=maxref){
X				maxref *= 2;
X				ref=Realloc(ref,maxref*sizeof(*ref));
X			}
X			ref[nref-1] = name;
X			break;
X		  /* ignore other lines */
X		}
X	}
X	if(nf>0 && nref>0)
X		save_refs(&f[nf],nref,ref);
X	free(ref);
X	d->file = f;
X	d->nfile = nf;
X	d->Def = D;
X}
X
X
X
X
Xtypedef struct{
X	char **p;
X	int np, maxp;
X} stack;
X
Xstatic void
Xnew_stack(stack *s)
X{
X	s->maxp = 1000;
X	s->p = (char**)Malloc(s->maxp*sizeof(char*));
X	s->np = 0;
X}
X
Xstatic void
Xpush(char *p, stack *s)
X{
X	if(s->np==s->maxp){
X		s->maxp *= 2;
X		s->p = (char**)Realloc(s->p,s->maxp*sizeof(char*));
X	}
X	s->p[s->np++] = p;
X}
X
Xstatic char*
Xpop(stack *s)
X{
X	if(s->np==0) return 0;
X	return(s->p[--s->np]);
X}
X
X
X
Xstatic void
Xresolve(Dependencies *d, stack *hit, stack *need)
X{
X	int i, k;
X	char *r;
X	File *f;
X
X	while(r = pop(need)){
X		i = hashsrch(&d->Def,r);
X		if(i>0){
X			f = &d->file[d->Def[i].Code];
X			if(!f->done){
X				f->done = 1;
X				push(f->name,hit);
X				for(k = 0; k<f->nref; k++)
X					push(f->ref[k],need);
X			}
X		}  /* else unsatisfied external */
X	}
X}
X
Xstatic int
Xcmp(const void*a, const void*b)
X{
X	return(strcmp(*(char **)a,*(char **)b));
X}
X
Xvoid
Xmain(int argc, char**argv)
X{
X	Dependencies D;
X	stack hit, need;
X	int i;
X
X	new_stack(&hit);
X	new_stack(&need);
X	while(argc>1)
X		push(argv[--argc],&need);
X	getdepend(&D);
X	resolve(&D,&hit,&need);
X	/* hit isn't really a stack; now we prove it. */
X	qsort(hit.p,hit.np,sizeof(char*),cmp);
X	for(i = 0; i<hit.np; i++)
X		printf("%s\n",hit.p[i]);
X	exit(0);
X}
-------cut here----- getdepend.c
echo hash.c 1>&2
sed >hash.c <<'-------cut here----- hash.c' 's/^X//'
X/* version with Brent reorganization.    Eric Grosse <ehg@research.att.com>  */
X/* see Gonnet and Baeza-Yates, Handbook of Algorithms and Data Structures, 1991, p.63 */
X
X/*
XLet {\tt char* s} be a key,
Xlet {\tt int c} be a value to be associated with {\tt s},
Xlet {\tt HashTable H=0} be a symbol table,
Xand let {\tt int i=hashsrch(\&H,s)}.
XIf {\tt i<0}, then {\tt s}$\not\in${\tt H}, and the pair $(s,c)$
Xmay be inserted by
X{\tt hashins(\&H,i,Strdup(s),c)}. 
XOtherwise, {\tt s}$\in${\tt H} and
Xthe associated value is {\tt H[i].Code}.
XThe pair may be removed by {\tt hashdel(\&H,i)}.
XUse {\tt free(H)} to release the space allocated for {\tt H}
Xitself;  this does not free the individual keys.
XThe implementation uses open hashing, allocating a larger table
Xand rehashing when too many collisions occur.
X*/
X
X#include <string.h>
X#include <stdio.h>
X#include "depend.h"
X
X#define LENGTH (H[0].Code)
X#define DEAD ((char*)H)
X/* H[0] just holds the length n.  The hash table proper is H[1],...,H[n]. */
X
Xint 
Xhashpjw(char* key, int n)
X{
X	unsigned int g, h = 0;
X	while((unsigned char)*key!=0){
X		h = (h<<4)+(unsigned char)*key++;
X		if(g = h&15<<28){
X			h = h^g>>28;
X			h = h^g;
X		}
X	}
X	return h%n;
X}
X
Xint 
Xhashasu(char* key, int n)
X{
X	unsigned int h = 0;
X	while((unsigned char)*key!=0)
X		h = 65599*h+(unsigned char)*key++;
X	return h%n;
X}
X
Xstatic int	
Xrehash(HashTable*Hp)
X{
X	int i, j;
X	char* key;
X	static int level;	/* don't rehash in the middle of a rehash */
X	int m;	/* m and m-2 must both be prime! */
X	HashTable N, H = *Hp;
X	int n;
X
X	if(!H){
X		n = 211;
X		*Hp = H = (struct HashEntry*)Malloc((n+1)*sizeof(*H));
X		LENGTH = n;
X		for(j=1;j<=n;j++)
X			H[j].Key = 0;
X		level = 0;
X		return(1);
X	}
X	level++==0 || Error("rehash: recursive rehash"); /* maybe return(0)? */
X	n = LENGTH;
X	if(n == 211) { m = 1019;
X	} else if(n == 1019) { m = 5099;
X	} else if(n == 5099) { m = 25033;
X	} else if(n == 25033) { m = 100153;
X	} else if(n == 100153) { m = 500809;
X	} else if(n == 500809) { m = 2503183;
X	} else { m = 5007181; Error("HashTable overflowed");
X	}
X	N = (struct HashEntry*)Malloc((m+1)*sizeof(*N));
X	N[0].Code = m;  /* LENGTH */
X	for(j=1;j<=m;j++)
X		N[j].Key = 0;
X	for(i = 1; i <= n; i += 1  ) {
X		if((key = H[i].Key)!=0 && key!=DEAD) {
X			j = hashsrch(&N, key);
X			j<0 || Error("%s already in N in rehash!?",key);
X			hashins(&N, j, key, H[i].Code);
X		}
X	}
X	free(H);
X	*Hp = N;
X	level -= 1;
X	return(1);
X}
X
Xint 
Xhashsrch(HashTable*Hp, char* key)
X{
X	int i, inc, last, m;
X	char *HiKey;
X	HashTable H = *Hp;
X
X	key || Error("hashsrch: null key");
X	H || rehash(Hp); H = *Hp;
X	m = LENGTH;
X	i = hashpjw(key,m)+1;
X	HiKey = H[i].Key;
X	if(HiKey==0)
X		return(-i);
X	if(HiKey!=DEAD && HiKey[0]==key[0] && strcmp(HiKey+1,key+1)==0)
X		return(i);
X	inc = hashasu(key,m-2)+1;
X	last = (i-1+(m-1)*inc)%m+1;
X	while(1){
X		i = (i-1+inc)%m+1;
X		if(i==last) return(-i);
X		HiKey = H[i].Key;
X		if(HiKey==0) return(-i);
X		if(HiKey==DEAD) continue;
X		if(HiKey[0]==key[0] && strcmp(HiKey+1,key+1)==0) return(i);
X	}
X}
X
Xint	
Xhashins(HashTable*Hp, int j, char* key, int code)
X{
X	HashTable H = *Hp;
X	int init, inc, i, ii, jj, m = LENGTH;
X	char *HiKey;
X
X	j<0 || Error("hashins: Insert should follow unsuccessful Search");
X	/* search anyway, in case we can fill a DEAD slot */
X
X	init = hashpjw(key,m)+1;
X	HiKey = H[init].Key;
X	if( HiKey==0 || HiKey==DEAD){
X		H[init].Key = key;
X		H[init].Code = code;
X		return(init);
X	}
X
X	inc = hashasu(key,m-2)+1;	/* n-2 so probe offset is not zero */
X	for(i = 1; i<m; i++){
X	    j = i;
X		jj = (init-1+inc*i)%m + 1;
X		if(H[jj].Key==0 || H[jj].Key==DEAD){
X			H[jj].Key = key;   H[jj].Code = code;
X			goto finish;
X		}
X	    for(j = i-1; j>=0; j--){
X		jj = (init-1+inc*j)%m + 1;
X		ii = (jj-1+(hashasu(H[jj].Key,m-2)+1)*(i-j))%m+1;
X		if(H[ii].Key==0 || H[ii].Key==DEAD){ /* move record forward */
X			H[ii].Key = H[jj].Key;   H[ii].Code = H[jj].Code;
X			H[jj].Key = key;   H[jj].Code = code;
X			goto finish;
X		}
X	    }
X	}
X  finish:
X	/* if there were a lot of probes, rehash to speed future searches */
X	if((j>=5||(i-j)>5)&&m<1020 || (j>9||(i-j)>9)&&m<2500000){
X		rehash(Hp) || Error("hashsrch: new algorithm needed!");   H = *Hp;
X		jj = hashsrch(&H,key);
X		jj>0 || Error("hashins:can't");
X	}
X	return(jj);
X}
X
Xvoid	
Xhashdel(HashTable*Hp, int j)
X{
X	HashTable H = *Hp;
X	j>0 || Error("hashdel must follow successful Search");
X	H[j].Key = DEAD;
X}
X
X
-------cut here----- hash.c
echo skip_posix 1>&2
sed >skip_posix <<'-------cut here----- skip_posix' 's/^X//'
Xsed '/^R _/d
X/^R assert.h$/d
X/^R ctype.h$/d
X/^R fcntl.h$/d
X/^R float.h$/d
X/^R grp.h$/d
X/^R limits.h$/d
X/^R locale.h$/d
X/^R math.h$/d
X/^R pwd.h$/d
X/^R setjmp.h$/d
X/^R signal.h$/d
X/^R stdarg.h$/d
X/^R stddef.h$/d
X/^R stdio.h$/d
X/^R stdlib.h$/d
X/^R string.h$/d
X/^R sys\/times.h$/d
X/^R sys\/types.h$/d
X/^R sys\/utsname.h$/d
X/^R sys\/wait.h$/d
X/^R time.h$/d
X/^R unistd.h$/d
X/^R utime.h$/d
X/^R abs$/d
X/^R acos$/d
X/^R alarm$/d
X/^R asctime$/d
X/^R asin$/d
X/^R atan$/d
X/^R atan2$/d
X/^R atexit$/d
X/^R atof$/d
X/^R atoi$/d
X/^R atol$/d
X/^R bsearch$/d
X/^R ceil$/d
X/^R chdir$/d
X/^R chmod$/d
X/^R clearerr$/d
X/^R clock$/d
X/^R close$/d
X/^R closedir$/d
X/^R cos$/d
X/^R cosh$/d
X/^R ctermid$/d
X/^R cuserid$/d
X/^R difftime$/d
X/^R dup$/d
X/^R exit$/d
X/^R exp$/d
X/^R fabs$/d
X/^R fclose$/d
X/^R fdopen$/d
X/^R feof$/d
X/^R ferror$/d
X/^R fflush$/d
X/^R fgetc$/d
X/^R fgets$/d
X/^R fileno$/d
X/^R floor$/d
X/^R fmod$/d
X/^R fopen$/d
X/^R fprintf$/d
X/^R fputc$/d
X/^R fputs$/d
X/^R fread$/d
X/^R free$/d
X/^R freopen$/d
X/^R fscanf$/d
X/^R fseek$/d
X/^R fstat$/d
X/^R ftell$/d
X/^R fwrite$/d
X/^R getc$/d
X/^R getchar$/d
X/^R getenv$/d
X/^R getopt$/d
X/^R getpid$/d
X/^R gets$/d
X/^R gmtime$/d
X/^R isdigit$/d
X/^R isspace$/d
X/^R isupper$/d
X/^R labs$/d
X/^R localtime$/d
X/^R log$/d
X/^R log10$/d
X/^R lseek$/d
X/^R malloc$/d
X/^R memcpy$/d
X/^R memmove$/d
X/^R memset$/d
X/^R mkdir$/d
X/^R mkfifo$/d
X/^R mknod$/d
X/^R mktime$/d
X/^R modf$/d
X/^R opendir$/d
X/^R pause$/d
X/^R pclose$/d
X/^R perror$/d
X/^R pipe$/d
X/^R popen$/d
X/^R pow$/d
X/^R printf$/d
X/^R putc$/d
X/^R putchar$/d
X/^R puts$/d
X/^R qsort$/d
X/^R read$/d
X/^R readdir$/d
X/^R realloc$/d
X/^R remove$/d
X/^R rename$/d
X/^R rewind$/d
X/^R rewinddir$/d
X/^R scanf$/d
X/^R seekdir$/d
X/^R setbuf$/d
X/^R setvbuf$/d
X/^R sin$/d
X/^R sinh$/d
X/^R sleep$/d
X/^R sprintf$/d
X/^R sqrt$/d
X/^R sscanf$/d
X/^R strcat$/d
X/^R strchr$/d
X/^R strcmp$/d
X/^R strcpy$/d
X/^R strftime$/d
X/^R strlen$/d
X/^R strncmp$/d
X/^R strrchr$/d
X/^R strtod$/d
X/^R system$/d
X/^R tan$/d
X/^R tanh$/d
X/^R telldir$/d
X/^R time$/d
X/^R tmpfile$/d
X/^R tmpnam$/d
X/^R tolower$/d
X/^R tzset$/d
X/^R umask$/d
X/^R ungetc$/d
X/^R utime$/d
X/^R vfprintf$/d
X/^R vprintf$/d
X/^R vsprintf$/d
X/^R write$/d'
-------cut here----- skip_posix
chmod +x skip_posix