xref: /illumos-gate/usr/src/contrib/ast/src/lib/libast/misc/fastfind.c (revision b30d1939)

#pragma prototyped
/*
 * original code
 *
 *  	James A. Woods, Informatics General Corporation,
 *	NASA Ames Research Center, 6/81.
 *	Usenix ;login:, February/March, 1983, p. 8.
 *
 * discipline/method interface
 *
 *	Glenn Fowler
 *	AT&T Research
 *	modified from the original BSD source
 *
 * 'fastfind' scans a file list for the full pathname of a file
 * given only a piece of the name.  The list is 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%.
 *
 * there are 4 methods:
 *
 *	FF_old	original with 7 bit bigram encoding (no magic)
 *	FF_gnu	8 bit clean front compression (FF_gnu_magic)
 *	FF_dir	FF_gnu with sfgetl/sfputl and trailing / on dirs (FF_dir_magic)
 *	FF_typ	FF_dir with (mime) types (FF_typ_magic)
 *
 * the bigram encoding steals the eighth bit (that's why its FF_old)
 * maybe one day we'll limit it to readonly:
 *
 * 0-2*FF_OFF	 likeliest differential counts + offset to make nonnegative
 * FF_ESC	 4 byte big-endian out-of-range count+FF_OFF follows
 * FF_MIN-FF_MAX ascii residue
 * >=FF_MAX	 bigram codes
 *
 * a two-tiered string search technique is employed
 *
 * a metacharacter-free subpattern and partial pathname is matched
 * backwards to avoid full expansion of the pathname list
 *
 * then the actual shell glob-style regular expression (if in this form)
 * is matched against the candidate pathnames using the slower regexec()
 *
 * The original BSD code is covered by the BSD license:
 *
 * Copyright (c) 1985, 1993, 1999
 *	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. 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.
 */

static const char id[] = "\n@(#)$Id: fastfind (AT&T Research) 2002-10-02 $\0\n";

static const char lib[] = "libast:fastfind";

#include "findlib.h"

#define FIND_MATCH	"*/(find|locate)/*"

/*
 * this db could be anywhere
 * findcodes[] directories are checked for findnames[i]
 */

static char*		findcodes[] =
{
	0,
	0,
	FIND_CODES,
	"/usr/local/share/lib",
	"/usr/local/lib",
	"/usr/share/lib",
	"/usr/lib",
	"/var/spool",
	"/usr/local/var",
	"/var/lib",
	"/var/lib/slocate",
	"/var/db",
};

static char*		findnames[] =
{
	"find/codes",
	"find/find.codes",
	"locate/locatedb",
	"locatedb",
	"locate.database",
	"slocate.db",
};

/*
 * convert t to lower case and drop leading x- and x- after /
 * converted value copied to b of size n
 */

char*
typefix(char* buf, size_t n, register const char* t)
{
	register int	c;
	register char*	b = buf;

	if ((*t == 'x' || *t == 'X') && *(t + 1) == '-')
		t += 2;
	while (c = *t++)
	{
		if (isupper(c))
			c = tolower(c);
		if ((*b++ = c) == '/' && (*t == 'x' || *t == 'X') && *(t + 1) == '-')
			t += 2;
	}
	*b = 0;
	return buf;
}

/*
 * return a fastfind stream handle for pattern
 */

Find_t*
findopen(const char* file, const char* pattern, const char* type, Finddisc_t* disc)
{
	register Find_t*	fp;
	register char*		p;
	register char*		s;
	register char*		b;
	register int		i;
	register int		j;
	char*			path;
	int			brace = 0;
	int			paren = 0;
	int			k;
	int			q;
	int			fd;
	int			uid;
	Vmalloc_t*		vm;
	Type_t*			tp;
	struct stat		st;


	if (!(vm = vmopen(Vmdcheap, Vmbest, 0)))
		goto nospace;

	/*
	 * NOTE: searching for FIND_CODES would be much simpler if we
	 *       just stuck with our own, but we also support GNU
	 *	 locate codes and have to search for the one of a
	 *	 bazillion possible names for that file
	 */

	if (!findcodes[1])
		findcodes[1] = getenv(FIND_CODES_ENV);
	if (disc->flags & FIND_GENERATE)
	{
		if (!(fp = (Find_t*)vmnewof(vm, 0, Find_t, 1, sizeof(Encode_t) - sizeof(Code_t))))
			goto nospace;
		fp->vm = vm;
		fp->id = lib;
		fp->disc = disc;
		fp->generate = 1;
		if (file && (!*file || streq(file, "-")))
			file = 0;
		uid = geteuid();
		j = (findcodes[0] = (char*)file) && *file == '/' ? 1 : elementsof(findcodes);

		/*
		 * look for the codes file, but since it may not exist yet,
		 * also look for the containing directory if i<2 or if
		 * it is sufficiently qualified (FIND_MATCH)
		 */

		for (i = 0; i < j; i++)
			if (path = findcodes[i])
			{
				if (*path == '/')
				{
					if (!stat(path, &st))
					{
						if (S_ISDIR(st.st_mode))
						{
							for (k = 0; k < elementsof(findnames); k++)
							{
								sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s/%s", path, findnames[k]);
								if (!eaccess(fp->encode.file, R_OK|W_OK))
								{
									path = fp->encode.file;
									break;
								}
								if (strchr(findnames[k], '/') && (b = strrchr(fp->encode.file, '/')))
								{
									*b = 0;
									if (!stat(fp->encode.file, &st) && st.st_uid == uid && (st.st_mode & S_IWUSR))
									{
										*b = '/';
										path = fp->encode.file;
										break;
									}
								}
							}
							if (k < elementsof(findnames))
								break;
						}
						else if (st.st_uid == uid && (st.st_mode & S_IWUSR))
						{
							sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s", path);
							path = fp->encode.file;
							break;
						}
					}
					else if (i < 2 || strmatch(path, FIND_MATCH))
					{
						sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s", path);
						if (b = strrchr(fp->encode.file, '/'))
						{
							*b = 0;
							if (!stat(fp->encode.file, &st) && st.st_uid == uid && (st.st_mode & S_IWUSR))
							{
								*b = '/';
								path = fp->encode.file;
								break;
							}
						}
					}
				}
				else if (pathpath(path, "", PATH_REGULAR|PATH_READ|PATH_WRITE, fp->encode.file, sizeof(fp->encode.file)))
				{
					path = fp->encode.file;
					break;
				}
				else if (b = strrchr(path, '/'))
				{
					sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%-.*s", b - path, path);
					if (pathpath(fp->encode.file, "", PATH_EXECUTE|PATH_READ|PATH_WRITE, fp->encode.temp, sizeof(fp->encode.temp)) &&
					    !stat(fp->encode.temp, &st) && st.st_uid == uid && (st.st_mode & S_IWUSR))
					{
						sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s%s", fp->encode.temp, b);
						path = fp->encode.file;
						break;
					}
				}
			}
		if (i >= j)
		{
			if (fp->disc->errorf)
				(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot locate codes", file ? file : findcodes[2]);
			goto drop;
		}
		if (fp->disc->flags & FIND_OLD)
		{
			/*
			 * FF_old generates temp data that is read
			 * in a second pass to generate the real codes
			 */

			fp->method = FF_old;
			if (!(fp->fp = sftmp(32 * PATH_MAX)))
			{
				if (fp->disc->errorf)
					(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "cannot create tmp file");
				goto drop;
			}
		}
		else
		{
			/*
			 * the rest generate into a temp file that
			 * is simply renamed on completion
			 */

			if (s = strrchr(path, '/'))
			{
				*s = 0;
				p = path;
			}
			else
				p = ".";
			if (!pathtemp(fp->encode.temp, sizeof(fp->encode.temp), p, "ff", &fd))
			{
				if (fp->disc->errorf)
					(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "%s: cannot create tmp file in this directory", p ? p : ".");
				goto drop;
			}
			if (s)
				*s = '/';
			if (!(fp->fp = sfnew(NiL, NiL, (size_t)SF_UNBOUND, fd, SF_WRITE)))
			{
				if (fp->disc->errorf)
					(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "%s: cannot open tmp file", fp->encode.temp);
				close(fd);
				goto drop;
			}
			if (fp->disc->flags & FIND_TYPE)
			{
				fp->method = FF_typ;
				fp->encode.namedisc.key = offsetof(Type_t, name);
				fp->encode.namedisc.link = offsetof(Type_t, byname);
				fp->encode.indexdisc.key = offsetof(Type_t, index);
				fp->encode.indexdisc.size = sizeof(unsigned long);
				fp->encode.indexdisc.link = offsetof(Type_t, byindex);
				s = "system/dir";
				if (!(fp->encode.namedict = dtopen(&fp->encode.namedisc, Dtoset)) || !(fp->encode.indexdict = dtopen(&fp->encode.indexdisc, Dtoset)) || !(tp = newof(0, Type_t, 1, strlen(s) + 1)))
				{
					if (fp->encode.namedict)
						dtclose(fp->encode.namedict);
					if (fp->disc->errorf)
						(*fp->disc->errorf)(fp, fp->disc, 2, "cannot allocate type table");
					goto drop;
				}

				/*
				 * type index 1 is always system/dir
				 */

				tp->index = ++fp->types;
				strcpy(tp->name, s);
				dtinsert(fp->encode.namedict, tp);
				dtinsert(fp->encode.indexdict, tp);
			}
			else if (fp->disc->flags & FIND_GNU)
			{
				fp->method = FF_gnu;
				sfputc(fp->fp, 0);
				sfputr(fp->fp, FF_gnu_magic, 0);
			}
			else
			{
				fp->method = FF_dir;
				sfputc(fp->fp, 0);
				sfputr(fp->fp, FF_dir_magic, 0);
			}
		}
	}
	else
	{
		i = sizeof(Decode_t) + sizeof(Code_t);
		if (!pattern || !*pattern)
			pattern = "*";
		i += (j = 2 * (strlen(pattern) + 1));
		if (!(fp = (Find_t*)vmnewof(vm, 0, Find_t, 1, i)))
		{
			vmclose(vm);
			return 0;
		}
		fp->vm = vm;
		fp->id = lib;
		fp->disc = disc;
		if (disc->flags & FIND_ICASE)
			fp->decode.ignorecase = 1;
		j = (findcodes[0] = (char*)file) && *file == '/' ? 1 : elementsof(findcodes);
		for (i = 0; i < j; i++)
			if (path = findcodes[i])
			{
				if (*path == '/')
				{
					if (!stat(path, &st))
					{
						if (S_ISDIR(st.st_mode))
						{
							for (k = 0; k < elementsof(findnames); k++)
							{
								sfsprintf(fp->decode.path, sizeof(fp->decode.path), "%s/%s", path, findnames[k]);
								if (fp->fp = sfopen(NiL, fp->decode.path, "r"))
								{
									path = fp->decode.path;
									break;
								}
							}
							if (fp->fp)
								break;
						}
						else if (fp->fp = sfopen(NiL, path, "r"))
							break;
					}
				}
				else if ((path = pathpath(path, "", PATH_REGULAR|PATH_READ, fp->decode.path, sizeof(fp->decode.path))) && (fp->fp = sfopen(NiL, path, "r")))
					break;
			}
		if (!fp->fp)
		{
			if (fp->disc->errorf)
				(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot locate codes", file ? file : findcodes[2]);
			goto drop;
		}
		if (fstat(sffileno(fp->fp), &st))
		{
			if (fp->disc->errorf)
				(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot stat codes", path);
			goto drop;
		}
		if (fp->secure = ((st.st_mode & (S_IRGRP|S_IROTH)) == S_IRGRP) && st.st_gid == getegid() && getegid() != getgid())
			setgid(getgid());
		fp->stamp = st.st_mtime;
		b = (s = fp->decode.temp) + 1;
		for (i = 0; i < elementsof(fp->decode.bigram1); i++)
		{
			if ((j = sfgetc(fp->fp)) == EOF)
				goto invalid;
			if (!(*s++ = fp->decode.bigram1[i] = j) && i)
			{
				i = -i;
				break;
			}
			if ((j = sfgetc(fp->fp)) == EOF)
				goto invalid;
			if (!(*s++ = fp->decode.bigram2[i] = j) && (i || fp->decode.bigram1[0] >= '0' && fp->decode.bigram1[0] <= '1'))
				break;
		}
		if (streq(b, FF_typ_magic))
		{
			if (type)
			{
				type = (const char*)typefix(fp->decode.bigram2, sizeof(fp->decode.bigram2), type);
				memset(fp->decode.bigram1, 0, sizeof(fp->decode.bigram1));
			}
			fp->method = FF_typ;
			for (j = 0, i = 1;; i++)
			{
				if (!(s = sfgetr(fp->fp, 0, 0)))
					goto invalid;
				if (!*s)
					break;
				if (type && strmatch(s, type))
				{
					FF_SET_TYPE(fp, i);
					j++;
				}
			}
			if (type && !j)
				goto drop;
			fp->types = j;
		}
		else if (streq(b, FF_dir_magic))
			fp->method = FF_dir;
		else if (streq(b, FF_gnu_magic))
			fp->method = FF_gnu;
		else if (!*b && *--b >= '0' && *b <= '1')
		{
			fp->method = FF_gnu;
			while (j = sfgetc(fp->fp))
			{
				if (j == EOF || fp->decode.count >= sizeof(fp->decode.path))
					goto invalid;
				fp->decode.path[fp->decode.count++] = j;
			}
		}
		else
		{
			fp->method = FF_old;
			if (i < 0)
			{
				if ((j = sfgetc(fp->fp)) == EOF)
					goto invalid;
				fp->decode.bigram2[i = -i] = j;
			}
			while (++i < elementsof(fp->decode.bigram1))
			{
				if ((j = sfgetc(fp->fp)) == EOF)
					goto invalid;
				fp->decode.bigram1[i] = j;
				if ((j = sfgetc(fp->fp)) == EOF)
					goto invalid;
				fp->decode.bigram2[i] = j;
			}
			if ((fp->decode.peek = sfgetc(fp->fp)) != FF_OFF)
				goto invalid;
		}

		/*
		 * set up the physical dir table
		 */

		if (disc->version >= 19980301L)
		{
			fp->verifyf = disc->verifyf;
			if (disc->dirs && *disc->dirs)
			{
				for (k = 0; disc->dirs[k]; k++);
				if (k == 1 && streq(disc->dirs[0], "/"))
					k = 0;
				if (k)
				{
					if (!(fp->dirs = vmnewof(fp->vm, 0, char*, 2 * k + 1, 0)))
						goto drop;
					if (!(fp->lens = vmnewof(fp->vm, 0, int, 2 * k, 0)))
						goto drop;
					p = 0;
					b = fp->decode.temp;
					j = fp->method == FF_old || fp->method == FF_gnu;

					/*
					 * fill the dir list with logical and
					 * physical names since we don't know
					 * which way the db was encoded (it
					 * could be *both* ways)
					 */

					for (i = q = 0; i < k; i++)
					{
						if (*(s = disc->dirs[i]) == '/')
							sfsprintf(b, sizeof(fp->decode.temp) - 1, "%s", s);
						else if (!p && !(p = getcwd(fp->decode.path, sizeof(fp->decode.path))))
							goto nospace;
						else
							sfsprintf(b, sizeof(fp->decode.temp) - 1, "%s/%s", p, s);
						s = pathcanon(b, sizeof(fp->decode.temp), 0);
						*s = '/';
						*(s + 1) = 0;
						if (!(fp->dirs[q] = vmstrdup(fp->vm, b)))
							goto nospace;
						if (j)
							(fp->dirs[q])[s - b] = 0;
						q++;
						*s = 0;
						s = pathcanon(b, sizeof(fp->decode.temp), PATH_PHYSICAL);
						*s = '/';
						*(s + 1) = 0;
						if (!strneq(b, fp->dirs[q - 1], s - b))
						{
							if (!(fp->dirs[q] = vmstrdup(fp->vm, b)))
								goto nospace;
							if (j)
								(fp->dirs[q])[s - b] = 0;
							q++;
						}
					}
					strsort(fp->dirs, q, strcasecmp);
					for (i = 0; i < q; i++)
						fp->lens[i] = strlen(fp->dirs[i]);
				}
			}
		}
		if (fp->verifyf || (disc->flags & FIND_VERIFY))
		{
			if (fp->method != FF_dir && fp->method != FF_typ)
			{
				if (fp->disc->errorf)
					(*fp->disc->errorf)(fp, fp->disc, 2, "%s: %s code format does not support directory verification", path, fp->method == FF_gnu ? FF_gnu_magic : "OLD-BIGRAM");
				goto drop;
			}
			fp->verify = 1;
		}

		/*
		 * extract last glob-free subpattern in name for fast pre-match
		 * prepend 0 for backwards match
		 */

		if (p = s = (char*)pattern)
		{
			b = fp->decode.pattern;
			for (;;)
			{
				switch (*b++ = *p++)
				{
				case 0:
					break;
				case '\\':
					s = p;
					if (!*p++)
						break;
					continue;
				case '[':
					if (!brace)
					{
						brace++;
						if (*p == ']')
							p++;
					}
					continue;
				case ']':
					if (brace)
					{
						brace--;
						s = p;
					}
					continue;
				case '(':
					if (!brace)
						paren++;
					continue;
				case ')':
					if (!brace && paren > 0 && !--paren)
						s = p;
					continue;
				case '|':
				case '&':
					if (!brace && !paren)
					{
						s = "";
						break;
					}
					continue;
				case '*':
				case '?':
					s = p;
					continue;
				default:
					continue;
				}
				break;
			}
			if (s != pattern && !streq(pattern, "*"))
			{
				fp->decode.match = 1;
				if (i = regcomp(&fp->decode.re, pattern, REG_SHELL|REG_AUGMENTED|(fp->decode.ignorecase?REG_ICASE:0)))
				{
					if (disc->errorf)
					{
						regerror(i, &fp->decode.re, fp->decode.temp, sizeof(fp->decode.temp));
						(*fp->disc->errorf)(fp, fp->disc, 2, "%s: %s", pattern, fp->decode.temp);
					}
					goto drop;
				}
			}
			if (*s)
			{
				*b++ = 0;
				while (i = *s++)
					*b++ = i;
				*b-- = 0;
				fp->decode.end = b;
				if (fp->decode.ignorecase)
					for (s = fp->decode.pattern; s <= b; s++)
						if (isupper(*s))
							*s = tolower(*s);
			}
		}
	}
	return fp;
 nospace:
	if (disc->errorf)
		(*fp->disc->errorf)(fp, fp->disc, 2, "out of space");
	if (!vm)
		return 0;
	if (!fp)
	{
		vmclose(vm);
		return 0;
	}
	goto drop;
 invalid:
	if (fp->disc->errorf)
		(*fp->disc->errorf)(fp, fp->disc, 2, "%s: invalid codes", path);
 drop:
	if (!fp->generate && fp->decode.match)
		regfree(&fp->decode.re);
	if (fp->fp)
		sfclose(fp->fp);
	vmclose(fp->vm);
	return 0;
}

/*
 * return the next fastfind path
 * 0 returned when list exhausted
 */

char*
findread(register Find_t* fp)
{
	register char*		p;
	register char*		q;
	register char*		s;
	register char*		b;
	register char*		e;
	register int		c;
	register int		n;
	register int		m;
	int			ignorecase;
	int			t;
	unsigned char		w[4];
	struct stat		st;

	if (fp->generate)
		return 0;
	if (fp->decode.restore)
	{
		*fp->decode.restore = '/';
		fp->decode.restore = 0;
	}
	ignorecase = fp->decode.ignorecase ? STR_ICASE : 0;
	c = fp->decode.peek;
 next:
	for (;;)
	{
		switch (fp->method)
		{
		case FF_dir:
			t = 0;
			n = sfgetl(fp->fp);
			goto grab;
		case FF_gnu:
			if ((c = sfgetc(fp->fp)) == EOF)
				return 0;
			if (c == 0x80)
			{
				if ((c = sfgetc(fp->fp)) == EOF)
					return 0;
				n = c << 8;
				if ((c = sfgetc(fp->fp)) == EOF)
					return 0;
				n |= c;
				if (n & 0x8000)
					n = (n - 0xffff) - 1;
			}
			else if ((n = c) & 0x80)
				n = (n - 0xff) - 1;
			t = 0;
			goto grab;
		case FF_typ:
			t = sfgetu(fp->fp);
			n = sfgetl(fp->fp);
		grab:
			p = fp->decode.path + (fp->decode.count += n);
			do
			{
				if ((c = sfgetc(fp->fp)) == EOF)
					return 0;
			} while (*p++ = c);
			p -= 2;
			break;
		case FF_old:
			if (c == EOF)
			{
				fp->decode.peek = c;
				return 0;
			}
			if (c == FF_ESC)
			{
				if (sfread(fp->fp, w, sizeof(w)) != sizeof(w))
					return 0;
				if (fp->decode.swap >= 0)
				{
					c = (int32_t)((w[0] << 24) | (w[1] << 16) | (w[2] << 8) | w[3]);
					if (!fp->decode.swap)
					{
						/*
						 * the old format uses machine
						 * byte order; this test uses
						 * the smallest magnitude of
						 * both byte orders on the
						 * first encoded path motion
						 * to determine the original
						 * byte order
						 */

						m = c;
						if (m < 0)
							m = -m;
						n = (int32_t)((w[3] << 24) | (w[2] << 16) | (w[1] << 8) | w[0]);
						if (n < 0)
							n = -n;
						if (m < n)
							fp->decode.swap = 1;
						else
						{
							fp->decode.swap = -1;
							c = (int32_t)((w[3] << 24) | (w[2] << 16) | (w[1] << 8) | w[0]);
						}
					}
				}
				else
					c = (int32_t)((w[3] << 24) | (w[2] << 16) | (w[1] << 8) | w[0]);
			}
			fp->decode.count += c - FF_OFF;
			for (p = fp->decode.path + fp->decode.count; (c = sfgetc(fp->fp)) > FF_ESC;)
				if (c & (1<<(CHAR_BIT-1)))
				{
					*p++ = fp->decode.bigram1[c & ((1<<(CHAR_BIT-1))-1)];
					*p++ = fp->decode.bigram2[c & ((1<<(CHAR_BIT-1))-1)];
				}
				else
					*p++ = c;
			*p-- = 0;
			t = 0;
			break;
		}
		b = fp->decode.path;
		if (fp->decode.found)
			fp->decode.found = 0;
		else
			b += fp->decode.count;
		if (fp->dirs)
			for (;;)
			{
				if (!*fp->dirs)
					return 0;

				/*
				 * use the ordering and lengths to prune
				 * comparison function calls
				 * (*fp->dirs)[*fp->lens]=='/' if its
				 * already been matched
				 */

				if ((n = p - fp->decode.path + 1) > (m = *fp->lens))
				{
					if (!(*fp->dirs)[m])
						goto next;
					if (!strncasecmp(*fp->dirs, fp->decode.path, m))
						break;
				}
				else if (n == m)
				{
					if (!(*fp->dirs)[m])
					{
						if (!(n = strcasecmp(*fp->dirs, fp->decode.path)) && (ignorecase || !strcmp(*fp->dirs, fp->decode.path)))
						{
							if (m > 0)
							{
								(*fp->dirs)[m] = '/';
								if ((*fp->dirs)[m - 1] != '/')
									(*fp->dirs)[++(*fp->lens)] = '/';
							}
							break;
						}
						if (n >= 0)
							goto next;
					}
				}
				else if (!(*fp->dirs)[m])
					goto next;
				fp->dirs++;
				fp->lens++;
			}
		if (fp->verify && (*p == '/' || t == 1))
		{
			if ((n = p - fp->decode.path))
				*p = 0;
			else
				n = 1;
			if (fp->verifyf)
				n = (*fp->verifyf)(fp, fp->decode.path, n, fp->disc);
			else if (stat(fp->decode.path, &st))
				n = -1;
			else if ((unsigned long)st.st_mtime > fp->stamp)
				n = 1;
			else
				n = 0;
			*p = '/';

			/*
			 * n<0	skip this subtree
			 * n==0 keep as is
			 * n>0	read this dir now
			 */

			/* NOT IMPLEMENTED YET */
		}
		if (FF_OK_TYPE(fp, t))
		{
			if (fp->decode.end)
			{
				if (*(s = p) == '/')
					s--;
				if (*fp->decode.pattern == '/' && b > fp->decode.path)
					b--;
				for (; s >= b; s--)
					if (*s == *fp->decode.end || ignorecase && tolower(*s) == *fp->decode.end)
					{
						if (ignorecase)
							for (e = fp->decode.end - 1, q = s - 1; *e && (*q == *e || tolower(*q) == *e); e--, q--);
						else
							for (e = fp->decode.end - 1, q = s - 1; *e && *q == *e; e--, q--);
						if (!*e)
						{
							fp->decode.found = 1;
							if (!fp->decode.match || strgrpmatch(fp->decode.path, fp->decode.pattern, NiL, 0, STR_MAXIMAL|STR_LEFT|STR_RIGHT|ignorecase))
							{
								fp->decode.peek = c;
								if (*p == '/')
									*(fp->decode.restore = p) = 0;
								if (!fp->secure || !access(fp->decode.path, F_OK))
									return fp->decode.path;
							}
							break;
						}
					}
			}
			else if (!fp->decode.match || !(n = regexec(&fp->decode.re, fp->decode.path, 0, NiL, 0)))
			{
				fp->decode.peek = c;
				if (*p == '/' && p > fp->decode.path)
					*(fp->decode.restore = p) = 0;
				if (!fp->secure || !access(fp->decode.path, F_OK))
					return fp->decode.path;
			}
			else if (n != REG_NOMATCH)
			{
				if (fp->disc->errorf)
				{
					regerror(n, &fp->decode.re, fp->decode.temp, sizeof(fp->decode.temp));
					(*fp->disc->errorf)(fp, fp->disc, 2, "%s: %s", fp->decode.pattern, fp->decode.temp);
				}
				return 0;
			}
		}
	}
}

/*
 * add path to the code table
 * paths are assumed to be in sort order
 */

int
findwrite(register Find_t* fp, const char* path, size_t len, const char* type)
{
	register unsigned char*	s;
	register unsigned char*	e;
	register unsigned char*	p;
	register int		n;
	register int		d;
	register Type_t*	x;
	register unsigned long	u;

	if (!fp->generate)
		return -1;
	if (type && fp->method == FF_dir)
	{
		len = sfsprintf(fp->encode.mark, sizeof(fp->encode.mark), "%-.*s/", len, path);
		path = fp->encode.mark;
	}
	s = (unsigned char*)path;
	if (len <= 0)
		len = strlen(path);
	if (len < sizeof(fp->encode.path))
		e = s + len++;
	else
	{
		len = sizeof(fp->encode.path) - 1;
		e = s + len;
	}
	p = (unsigned char*)fp->encode.path;
	while (s < e)
	{
		if (*s != *p++)
			break;
		s++;
	}
	n = s - (unsigned char*)path;
	switch (fp->method)
	{
	case FF_gnu:
		d = n - fp->encode.prefix;
		if (d >= -127 && d <= 127)
			sfputc(fp->fp, d & 0xff);
		else
		{
			sfputc(fp->fp, 0x80);
			sfputc(fp->fp, (d >> 8) & 0xff);
			sfputc(fp->fp, d & 0xff);
		}
		fp->encode.prefix = n;
		sfputr(fp->fp, (char*)s, 0);
		break;
	case FF_old:
		sfprintf(fp->fp, "%ld", n - fp->encode.prefix + FF_OFF);
		fp->encode.prefix = n;
		sfputc(fp->fp, ' ');
		p = s;
		while (s < e)
		{
			n = *s++;
			if (s >= e)
				break;
			fp->encode.code[n][*s++]++;
		}
		while (p < e)
		{
			if ((n = *p++) < FF_MIN || n >= FF_MAX)
				n = '?';
			sfputc(fp->fp, n);
		}
		sfputc(fp->fp, 0);
		break;
	case FF_typ:
		if (type)
		{
			type = (const char*)typefix((char*)fp->encode.bigram, sizeof(fp->encode.bigram), type);
			if (x = (Type_t*)dtmatch(fp->encode.namedict, type))
				u = x->index;
			else if (!(x = newof(0, Type_t, 1, strlen(type) + 1)))
				u = 0;
			else
			{
				u = x->index = ++fp->types;
				strcpy(x->name, type);
				dtinsert(fp->encode.namedict, x);
				dtinsert(fp->encode.indexdict, x);
			}
		}
		else
			u = 0;
		sfputu(fp->fp, u);
		/*FALLTHROUGH...*/
	case FF_dir:
		d = n - fp->encode.prefix;
		sfputl(fp->fp, d);
		fp->encode.prefix = n;
		sfputr(fp->fp, (char*)s, 0);
		break;
	}
	memcpy(fp->encode.path, path, len);
	return 0;
}

/*
 * findsync() helper
 */

static int
finddone(register Find_t* fp)
{
	int	r;

	if (sfsync(fp->fp))
	{
		if (fp->disc->errorf)
			(*fp->disc->errorf)(fp, fp->disc, 2, "%s: write error [sfsync]", fp->encode.file);
		return -1;
	}
	if (sferror(fp->fp))
	{
		if (fp->disc->errorf)
			(*fp->disc->errorf)(fp, fp->disc, 2, "%s: write error [sferror]", fp->encode.file);
		return -1;
	}
	r = sfclose(fp->fp);
	fp->fp = 0;
	if (r)
	{
		if (fp->disc->errorf)
			(*fp->disc->errorf)(fp, fp->disc, 2, "%s: write error [sfclose]", fp->encode.file);
		return -1;
	}
	return 0;
}

/*
 * finish the code table
 */

static int
findsync(register Find_t* fp)
{
	register char*		s;
	register int		n;
	register int		m;
	register int		d;
	register Type_t*	x;
	char*			t;
	int			b;
	long			z;
	Sfio_t*			sp;

	switch (fp->method)
	{
	case FF_dir:
	case FF_gnu:
		/*
		 * replace the real file with the temp file
		 */

		if (finddone(fp))
			goto bad;
		remove(fp->encode.file);
		if (rename(fp->encode.temp, fp->encode.file))
		{
			if (fp->disc->errorf)
				(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "%s: cannot rename from tmp file %s", fp->encode.file, fp->encode.temp);
			remove(fp->encode.temp);
			return -1;
		}
		break;
	case FF_old:
		/*
		 * determine the top FF_MAX bigrams
		 */

		for (n = 0; n < FF_MAX; n++)
			for (m = 0; m < FF_MAX; m++)
				fp->encode.hits[fp->encode.code[n][m]]++;
		fp->encode.hits[0] = 0;
		m = 1;
		for (n = USHRT_MAX; n >= 0; n--)
			if (d = fp->encode.hits[n])
			{
				fp->encode.hits[n] = m;
				if ((m += d) > FF_MAX)
					break;
			}
		while (--n >= 0)
			fp->encode.hits[n] = 0;
		for (n = FF_MAX - 1; n >= 0; n--)
			for (m = FF_MAX - 1; m >= 0; m--)
				if (fp->encode.hits[fp->encode.code[n][m]])
				{
					d = fp->encode.code[n][m];
					b = fp->encode.hits[d] - 1;
					fp->encode.code[n][m] = b + FF_MAX;
					if (fp->encode.hits[d]++ >= FF_MAX)
						fp->encode.hits[d] = 0;
					fp->encode.bigram[b *= 2] = n;
					fp->encode.bigram[b + 1] = m;
				}
				else
					fp->encode.code[n][m] = 0;

		/*
		 * commit the real file
		 */

		if (sfseek(fp->fp, (Sfoff_t)0, SEEK_SET))
		{
			if (fp->disc->errorf)
				(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "cannot rewind tmp file");
			return -1;
		}
		if (!(sp = sfopen(NiL, fp->encode.file, "w")))
			goto badcreate;

		/*
		 * dump the bigrams
		 */

		sfwrite(sp, fp->encode.bigram, sizeof(fp->encode.bigram));

		/*
		 * encode the massaged paths
		 */

		while (s = sfgetr(fp->fp, 0, 0))
		{
			z = strtol(s, &t, 0);
			s = t;
			if (z < 0 || z > 2 * FF_OFF)
			{
				sfputc(sp, FF_ESC);
				sfputc(sp, (z >> 24));
				sfputc(sp, (z >> 16));
				sfputc(sp, (z >> 8));
				sfputc(sp, z);
			}
			else
				sfputc(sp, z);
			while (n = *s++)
			{
				if (!(m = *s++))
				{
					sfputc(sp, n);
					break;
				}
				if (d = fp->encode.code[n][m])
					sfputc(sp, d);
				else
				{
					sfputc(sp, n);
					sfputc(sp, m);
				}
			}
		}
		sfclose(fp->fp);
		fp->fp = sp;
		if (finddone(fp))
			goto bad;
		break;
	case FF_typ:
		if (finddone(fp))
			goto bad;
		if (!(fp->fp = sfopen(NiL, fp->encode.temp, "r")))
		{
			if (fp->disc->errorf)
				(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "%s: cannot read tmp file", fp->encode.temp);
			remove(fp->encode.temp);
			return -1;
		}

		/*
		 * commit the output file
		 */

		if (!(sp = sfopen(NiL, fp->encode.file, "w")))
			goto badcreate;

		/*
		 * write the header magic
		 */

		sfputc(sp, 0);
		sfputr(sp, FF_typ_magic, 0);

		/*
		 * write the type table in index order starting with 1
		 */

		for (x = (Type_t*)dtfirst(fp->encode.indexdict); x; x = (Type_t*)dtnext(fp->encode.indexdict, x))
			sfputr(sp, x->name, 0);
		sfputc(sp, 0);

		/*
		 * append the front compressed strings
		 */

		if (sfmove(fp->fp, sp, SF_UNBOUND, -1) < 0 || !sfeof(fp->fp))
		{
			sfclose(sp);
			if (fp->disc->errorf)
				(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot append codes", fp->encode.file);
			goto bad;
		}
		sfclose(fp->fp);
		fp->fp = sp;
		if (finddone(fp))
			goto bad;
		remove(fp->encode.temp);
		break;
	}
	return 0;
 badcreate:
	if (fp->disc->errorf)
		(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot write codes", fp->encode.file);
 bad:
	if (fp->fp)
	{
		sfclose(fp->fp);
		fp->fp = 0;
	}
	remove(fp->encode.temp);
	return -1;
}

/*
 * close an open fastfind stream
 */

int
findclose(register Find_t* fp)
{
	int	n = 0;

	if (!fp)
		return -1;
	if (fp->generate)
	{
		n = findsync(fp);
		if (fp->encode.indexdict)
			dtclose(fp->encode.indexdict);
		if (fp->encode.namedict)
			dtclose(fp->encode.namedict);
	}
	else
	{
		if (fp->decode.match)
			regfree(&fp->decode.re);
		n = 0;
	}
	if (fp->fp)
		sfclose(fp->fp);
	vmclose(fp->vm);
	return n;
}