BSD 4.4 Lite Usr.bin Sources

11 files changed, 757 insertions, 0 deletions

diff --git a/usr.bin/locate/Makefile b/usr.bin/locate/Makefile
new file mode 100644
index 0000000..bc55dab
--- /dev/null
+++ b/usr.bin/locate/Makefile
@@ -0,0 +1,5 @@
+#	@(#)Makefile	8.1 (Berkeley) 6/6/93
+
+SUBDIR=	bigram code locate
+
+.include <bsd.subdir.mk>
diff --git a/usr.bin/locate/bigram/Makefile b/usr.bin/locate/bigram/Makefile
new file mode 100644
index 0000000..d7d4348
--- /dev/null
+++ b/usr.bin/locate/bigram/Makefile
@@ -0,0 +1,7 @@
+#	@(#)Makefile	8.1 (Berkeley) 6/6/93
+
+PROG=	locate.bigram
+NOMAN=	noman
+BINDIR=	/usr/libexec
+
+.include <bsd.prog.mk>
diff --git a/usr.bin/locate/bigram/locate.bigram.c b/usr.bin/locate/bigram/locate.bigram.c
new file mode 100644
index 0000000..b58fac4
--- /dev/null
+++ b/usr.bin/locate/bigram/locate.bigram.c
@@ -0,0 +1,84 @@
+/*
+ * Copyright (c) 1989, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * James A. Woods.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef lint
+static char copyright[] =
+"@(#) Copyright (c) 1989, 1993\n\
+	The Regents of the University of California.  All rights reserved.\n";
+#endif /* not lint */
+
+#ifndef lint
+static char sccsid[] = "@(#)locate.bigram.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*
+ *  bigram < text > bigrams
+ * 
+ * List bigrams for 'updatedb' script.
+ * Use 'code' to encode a file using this output.
+ */
+
+#include <stdio.h>
+#include <sys/param.h>			/* for MAXPATHLEN */
+
+char buf1[MAXPATHLEN] = " ";	
+char buf2[MAXPATHLEN];
+
+main ( )
+{
+  	register char *cp;
+	register char *oldpath = buf1, *path = buf2;
+
+     	while ( fgets ( path, sizeof(buf2), stdin ) != NULL ) {
+
+		/* skip longest common prefix */
+		for ( cp = path; *cp == *oldpath; cp++, oldpath++ )
+			if ( *oldpath == NULL )
+				break;
+		/*
+		 * output post-residue bigrams only
+		 */
+		while ( *cp != NULL && *(cp + 1) != NULL ) {
+			putchar ( *cp++ );
+			putchar ( *cp++ );
+			putchar ( '\n' );
+		}
+		if ( path == buf1 )		/* swap pointers */
+			path = buf2, oldpath = buf1;
+		else
+			path = buf1, oldpath = buf2;
+   	}
+}
diff --git a/usr.bin/locate/code/Makefile b/usr.bin/locate/code/Makefile
new file mode 100644
index 0000000..743e968
--- /dev/null
+++ b/usr.bin/locate/code/Makefile
@@ -0,0 +1,8 @@
+#	@(#)Makefile	8.1 (Berkeley) 6/6/93
+
+PROG=	locate.code
+CFLAGS+=-I${.CURDIR}/../locate
+NOMAN=	noman
+BINDIR=	/usr/libexec
+
+.include <bsd.prog.mk>
diff --git a/usr.bin/locate/code/locate.code.c b/usr.bin/locate/code/locate.code.c
new file mode 100644
index 0000000..d3ec29f
--- /dev/null
+++ b/usr.bin/locate/code/locate.code.c
@@ -0,0 +1,212 @@
+/*
+ * Copyright (c) 1989, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * James A. Woods.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef lint
+static char copyright[] =
+"@(#) Copyright (c) 1989, 1993\n\
+	The Regents of the University of California.  All rights reserved.\n";
+#endif /* not lint */
+
+#ifndef lint
+static char sccsid[] = "@(#)locate.code.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*
+ * PURPOSE:	sorted list compressor (works with a modified 'find'
+ *		to encode/decode a filename database)
+ *
+ * USAGE:	bigram < list > bigrams
+ *		process bigrams (see updatedb) > common_bigrams
+ *		code common_bigrams < list > squozen_list
+ *
+ * METHOD:	Uses 'front compression' (see ";login:", Volume 8, Number 1
+ *		February/March 1983, p. 8).  Output format is, per line, an
+ *		offset differential count byte followed by a partially bigram-
+ *		encoded ascii residue.  A bigram is a two-character sequence,
+ *		the first 128 most common of which are encoded in one byte.
+ *
+ * EXAMPLE:	For simple front compression with no bigram encoding,
+ *		if the input is...		then the output is...
+ *
+ *		/usr/src			 0 /usr/src
+ *		/usr/src/cmd/aardvark.c		 8 /cmd/aardvark.c
+ *		/usr/src/cmd/armadillo.c	14 armadillo.c
+ *		/usr/tmp/zoo			 5 tmp/zoo
+ *
+ *	The codes are:
+ *
+ *	0-28	likeliest differential counts + offset to make nonnegative
+ *	30	switch code for out-of-range count to follow in next word
+ *	128-255 bigram codes (128 most common, as determined by 'updatedb')
+ *	32-127  single character (printable) ascii residue (ie, literal)
+ *
+ * SEE ALSO:	updatedb.csh, bigram.c
+ *
+ * AUTHOR:	James A. Woods, Informatics General Corp.,
+ *		NASA Ames Research Center, 10/82
+ */
+
+#include <sys/param.h>
+#include <err.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include "locate.h"
+
+#define	BGBUFSIZE	(NBG * 2)	/* size of bigram buffer */
+
+char buf1[MAXPATHLEN] = " ";	
+char buf2[MAXPATHLEN];
+char bigrams[BGBUFSIZE + 1] = { 0 };
+
+int	bgindex __P((char *));
+void	usage __P((void));
+
+int
+main(argc, argv)
+	int argc;
+	char *argv[];
+{
+	register char *cp, *oldpath, *path;
+	int ch, code, count, diffcount, oldcount;
+	FILE *fp;
+
+	while ((ch = getopt(argc, argv, "")) != EOF)
+		switch(ch) {
+		case '?':
+		default:
+			usage();
+		}
+	argc -= optind;
+	argv += optind;
+
+	if (argc != 1)
+		usage();
+
+	if ((fp = fopen(argv[0], "r")) == NULL)
+		err(1, "%s", argv[0]);
+
+	/* First copy bigram array to stdout. */
+	(void)fgets(bigrams, BGBUFSIZE + 1, fp);
+	if (fwrite(bigrams, 1, BGBUFSIZE, stdout) != BGBUFSIZE)
+		err(1, "stdout");
+	(void)fclose(fp);
+
+	oldpath = buf1;
+	path = buf2;
+	oldcount = 0;
+	while (fgets(path, sizeof(buf2), stdin) != NULL) {
+		/* Truncate newline. */
+		cp = path + strlen(path) - 1;
+		if (cp > path && *cp == '\n')
+			*cp = '\0';
+
+		/* Squelch characters that would botch the decoding. */
+		for (cp = path; *cp != NULL; cp++) {
+			if ((u_char)*cp >= PARITY)
+				*cp &= PARITY-1;
+			else if (*cp <= SWITCH)
+				*cp = '?';
+		}
+
+		/* Skip longest common prefix. */
+		for (cp = path; *cp == *oldpath; cp++, oldpath++)
+			if (*oldpath == NULL)
+				break;
+		count = cp - path;
+		diffcount = count - oldcount + OFFSET;
+		oldcount = count;
+		if (diffcount < 0 || diffcount > 2 * OFFSET) {
+			if (putchar(SWITCH) == EOF ||
+			    putw(diffcount, stdout) == EOF)
+				err(1, "stdout");
+		} else
+			if (putchar(diffcount) == EOF)
+				err(1, "stdout");
+
+		while (*cp != NULL) {
+			if (*(cp + 1) == NULL) {
+				if (putchar(*cp) == EOF)
+					err(1, "stdout");
+				break;
+			}
+			if ((code = bgindex(cp)) < 0) {
+				if (putchar(*cp++) == EOF ||
+				    putchar(*cp++) == EOF)
+					err(1, "stdout");
+			} else {
+				/* Found, so mark byte with parity bit. */
+				if (putchar((code / 2) | PARITY) == EOF)
+					err(1, "stdout");
+				cp += 2;
+			}
+		}
+		if (path == buf1) {		/* swap pointers */
+			path = buf2;
+			oldpath = buf1;
+		} else {
+			path = buf1;
+			oldpath = buf2;
+		}
+	}
+	/* Non-zero status if there were errors */
+	if (fflush(stdout) != 0 || ferror(stdout))
+		exit(1);
+	exit(0);
+}
+
+int
+bgindex(bg)			/* Return location of bg in bigrams or -1. */
+	char *bg;
+{
+	register char bg0, bg1, *p;
+
+	bg0 = bg[0];
+	bg1 = bg[1];
+	for (p = bigrams; *p != NULL; p++)
+		if (*p++ == bg0 && *p == bg1)
+			break;
+	return (*p == NULL ? -1 : --p - bigrams);
+}
+
+void
+usage()
+{
+	(void)fprintf(stderr,
+	    "usage: locate.code common_bigrams < list > squozen_list\n");
+	exit(1);
+}
diff --git a/usr.bin/locate/locate/Makefile b/usr.bin/locate/locate/Makefile
new file mode 100644
index 0000000..2e6c696
--- /dev/null
+++ b/usr.bin/locate/locate/Makefile
@@ -0,0 +1,10 @@
+#	@(#)Makefile	8.1 (Berkeley) 6/6/93
+
+PROG=	locate
+
+beforeinstall:
+	install -c -o ${BINOWN} -g ${BINGRP} -m ${BINMODE} \
+	    ${.CURDIR}/updatedb.csh ${DESTDIR}/usr/libexec/locate.updatedb
+
+.include "../../Makefile.inc"
+.include <bsd.prog.mk>
diff --git a/usr.bin/locate/locate/locate.1 b/usr.bin/locate/locate/locate.1
new file mode 100644
index 0000000..89cc2e8
--- /dev/null
+++ b/usr.bin/locate/locate/locate.1
@@ -0,0 +1,81 @@
+.\" Copyright (c) 1990, 1993
+.\"	The Regents of the University of California.  All rights reserved.
+.\"
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\"    notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\"    notice, this list of conditions and the following disclaimer in the
+.\"    documentation and/or other materials provided with the distribution.
+.\" 3. All advertising materials mentioning features or use of this software
+.\"    must display the following acknowledgement:
+.\"	This product includes software developed by the University of
+.\"	California, Berkeley and its contributors.
+.\" 4. Neither the name of the University nor the names of its contributors
+.\"    may be used to endorse or promote products derived from this software
+.\"    without specific prior written permission.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+.\" SUCH DAMAGE.
+.\"
+.\"	@(#)locate.1	8.1 (Berkeley) 6/6/93
+.\"
+.Dd June 6, 1993
+.Dt LOCATE 1
+.Os BSD 4.4
+.Sh NAME
+.Nm locate
+.Nd find files
+.Sh SYNOPSIS
+.Ar locate
+pattern
+.Sh DESCRIPTION
+.Nm Locate
+searches a database for all pathnames which match the specified
+.Ar pattern  .
+The database is recomputed periodically, and contains the pathnames
+of all files which are publicly accessible.
+.Pp
+Shell globbing and quoting characters (``*'', ``?'', ``\e'', ``[''
+and ``]'')
+may be used in
+.Ar pattern  ,
+although they will have to be escaped from the shell.
+Preceding any character with a backslash (``\e'') eliminates any special
+meaning which it may have.
+The matching differs in that no characters must be matched explicitly,
+including slashes (``/'').
+.Pp
+As a special case, a pattern containing no globbing characters (``foo'')
+is matched as though it were ``*foo*''.
+.Sh FILES
+.Bl -tag -width /var/db/locate.database -compact
+.It Pa /var/db/locate.database
+.El
+.Sh SEE ALSO
+.Xr find 1 ,
+.Xr fnmatch 3
+.Rs
+.%A Woods, James A.
+.%D 1983
+.%T "Finding Files Fast"
+.%J ";login"
+.%V 8:1
+.%P pp. 8-10
+.Re
+.Sh HISTORY
+The
+.Nm locate
+command appears in
+.Bx 4.4 .
diff --git a/usr.bin/locate/locate/locate.c b/usr.bin/locate/locate/locate.c
new file mode 100644
index 0000000..ea43872
--- /dev/null
+++ b/usr.bin/locate/locate/locate.c
@@ -0,0 +1,196 @@
+/*
+ * Copyright (c) 1989, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * James A. Woods.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef lint
+static char copyright[] =
+"@(#) Copyright (c) 1989, 1993\n\
+	The Regents of the University of California.  All rights reserved.\n";
+#endif /* not lint */
+
+#ifndef lint
+static char sccsid[] = "@(#)locate.c	8.1 (Berkeley) 6/6/93";
+#endif /* not lint */
+
+/*
+ * Ref: Usenix ;login:, Vol 8, No 1, February/March, 1983, p. 8.
+ *
+ * Locate scans a file list for the full pathname of a file given only part
+ * of the name.  The list has been processed with with "front-compression"
+ * and bigram coding.  Front compression reduces space by a factor of 4-5,
+ * bigram coding by a further 20-25%.
+ *
+ * The codes are:
+ * 
+ * 	0-28	likeliest differential counts + offset to make nonnegative
+ *	30	switch code for out-of-range count to follow in next word
+ *	128-255 bigram codes (128 most common, as determined by 'updatedb')
+ *	32-127  single character (printable) ascii residue (ie, literal)
+ * 
+ * A novel two-tiered string search technique is employed:
+ * 
+ * First, a metacharacter-free subpattern and partial pathname is matched
+ * BACKWARDS to avoid full expansion of the pathname list.  The time savings
+ * is 40-50% over forward matching, which cannot efficiently handle
+ * overlapped search patterns and compressed path residue.
+ * 
+ * Then, the actual shell glob-style regular expression (if in this form) is
+ * matched against the candidate pathnames using the slower routines provided
+ * in the standard 'find'.
+ */
+
+#include <sys/param.h>
+
+#include <fnmatch.h>
+#include <unistd.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "locate.h"
+#include "pathnames.h"
+
+FILE *fp;
+
+int
+main(argc, argv)
+	int argc;
+	char *argv[];
+{
+	if (argc != 2) {
+		(void)fprintf(stderr, "usage: locate pattern\n");
+		exit(1);
+	}
+	if (!(fp = fopen(_PATH_FCODES, "r"))) {
+		(void)fprintf(stderr, "locate: no database file %s.\n",
+		    _PATH_FCODES);
+		exit(1);
+	}
+	while (*++argv)
+		fastfind(*argv);
+	exit(0);
+}
+
+fastfind(pathpart)
+	char *pathpart;
+{
+	register char *p, *s;
+	register int c;
+	int count, found, globflag;
+	char *cutoff, *patend, *q, *patprep();
+	char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
+
+	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++)
+		p[c] = getc(fp), s[c] = getc(fp);
+
+	p = pathpart;
+	globflag = index(p, '*') || index(p, '?') || index(p, '[');
+	patend = patprep(p);
+
+	found = 0;
+	for (c = getc(fp), count = 0; c != EOF;) {
+		count += ((c == SWITCH) ? getw(fp) : c) - OFFSET;
+		/* overlay old path */
+		for (p = path + count; (c = getc(fp)) > SWITCH;)
+			if (c < PARITY)
+				*p++ = c;
+			else {		/* bigrams are parity-marked */
+				c &= PARITY - 1;
+				*p++ = bigram1[c], *p++ = bigram2[c];
+			}
+		*p-- = NULL;
+		cutoff = (found ? path : path + count);
+		for (found = 0, s = p; s >= cutoff; s--)
+			if (*s == *patend) {	/* fast first char check */
+				for (p = patend - 1, q = s - 1; *p != NULL;
+				    p--, q--)
+					if (*q != *p)
+						break;
+				if (*p == NULL) {	/* fast match success */
+					found = 1;
+					if (!globflag ||
+					    !fnmatch(pathpart, path, 0))
+						(void)printf("%s\n", path);
+					break;
+				}
+			}
+	}
+}
+
+/*
+ * extract last glob-free subpattern in name for fast pre-match; prepend
+ * '\0' for backwards match; return end of new pattern
+ */
+static char globfree[100];
+
+char *
+patprep(name)
+	char *name;
+{
+	register char *endmark, *p, *subp;
+
+	subp = globfree;
+	*subp++ = '\0';
+	p = name + strlen(name) - 1;
+	/* skip trailing metacharacters (and [] ranges) */
+	for (; p >= name; p--)
+		if (index("*?", *p) == 0)
+			break;
+	if (p < name)
+		p = name;
+	if (*p == ']')
+		for (p--; p >= name; p--)
+			if (*p == '[') {
+				p--;
+				break;
+			}
+	if (p < name)
+		p = name;
+	/*
+	 * if pattern has only metacharacters, check every path (force '/'
+	 * search)
+	 */
+	if ((p == name) && index("?*[]", *p) != 0)
+		*subp++ = '/';
+	else {
+		for (endmark = p; p >= name; p--)
+			if (index("]*?", *p) != 0)
+				break;
+		for (++p;
+		    (p <= endmark) && subp < (globfree + sizeof(globfree));)
+			*subp++ = *p++;
+	}
+	*subp = '\0';
+	return(--subp);
+}
diff --git a/usr.bin/locate/locate/locate.h b/usr.bin/locate/locate/locate.h
new file mode 100644
index 0000000..fe4da28
--- /dev/null
+++ b/usr.bin/locate/locate/locate.h
@@ -0,0 +1,41 @@
+/*
+ * Copyright (c) 1989, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *	@(#)locate.h	8.1 (Berkeley) 6/6/93
+ */
+
+/* Symbolic constants shared by locate.c and code.c */
+
+#define	NBG		128		/* number of bigrams considered */
+#define	OFFSET		14		/* abs value of max likely diff */
+#define	PARITY		0200		/* parity bit */
+#define	SWITCH		30		/* switch code */
diff --git a/usr.bin/locate/locate/pathnames.h b/usr.bin/locate/locate/pathnames.h
new file mode 100644
index 0000000..8fb0e8c
--- /dev/null
+++ b/usr.bin/locate/locate/pathnames.h
@@ -0,0 +1,36 @@
+/*
+ * Copyright (c) 1989, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *	@(#)pathnames.h	8.1 (Berkeley) 6/6/93
+ */
+
+#define	_PATH_FCODES	"/var/db/locate.database"
diff --git a/usr.bin/locate/locate/updatedb.csh b/usr.bin/locate/locate/updatedb.csh
new file mode 100644
index 0000000..574d52a
--- /dev/null
+++ b/usr.bin/locate/locate/updatedb.csh
@@ -0,0 +1,77 @@
+#!/bin/csh -f
+#
+# Copyright (c) 1989, 1993
+#	The Regents of the University of California.  All rights reserved.
+#
+# This code is derived from software contributed to Berkeley by
+# James A. Woods.
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions
+# are met:
+# 1. Redistributions of source code must retain the above copyright
+#    notice, this list of conditions and the following disclaimer.
+# 2. Redistributions in binary form must reproduce the above copyright
+#    notice, this list of conditions and the following disclaimer in the
+#    documentation and/or other materials provided with the distribution.
+# 3. All advertising materials mentioning features or use of this software
+#    must display the following acknowledgement:
+#	This product includes software developed by the University of
+#	California, Berkeley and its contributors.
+# 4. Neither the name of the University nor the names of its contributors
+#    may be used to endorse or promote products derived from this software
+#    without specific prior written permission.
+#
+# THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+# ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+# OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+# OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+# SUCH DAMAGE.
+#
+#	@(#)updatedb.csh	8.3 (Berkeley) 3/19/94
+#
+
+set SRCHPATHS = "/"			# directories to be put in the database
+set LIBDIR = /usr/libexec		# for subprograms
+					# for temp files
+if (! $?TMPDIR) setenv TMPDIR = /var/tmp
+set FCODES = /var/db/locate.database	# the database
+
+set path = ( /bin /usr/bin )
+set bigrams = $TMPDIR/locate.bigrams.$$
+set filelist = $TMPDIR/locate.list.$$
+set errs = $TMPDIR/locate.errs.$$
+
+# Make a file list and compute common bigrams.
+# Alphabetize '/' before any other char with 'tr'.
+# If the system is very short of sort space, 'bigram' can be made
+# smarter to accumulate common bigrams directly without sorting
+# ('awk', with its associative memory capacity, can do this in several
+# lines, but is too slow, and runs out of string space on small machines).
+
+# search locally or everything
+# find ${SRCHPATHS} -print | \
+find ${SRCHPATHS} \! -fstype local -prune -or -print | \
+	tr '/' '\001' | \
+	(sort -T $TMPDIR -f; echo $status > $errs) | tr '\001' '/' > $filelist
+
+$LIBDIR/locate.bigram < $filelist | \
+	(sort -T /$TMPDIR; echo $status >> $errs) | \
+	uniq -c | sort -T /$TMPDIR -nr | \
+	awk '{ if (NR <= 128) print $2 }' | tr -d '\012' > $bigrams
+
+# code the file list
+
+if { grep -s -v 0 $errs } then
+	printf 'locate: updatedb failed\n\n'
+else
+	$LIBDIR/locate.code $bigrams < $filelist > $FCODES
+	chmod 644 $FCODES
+	rm $bigrams $filelist $errs
+endif