#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)