xref: /onnv-gate/usr/src/lib/libast/common/misc/fastfind.c (revision 12068:08a39a083754)
14887Schin /***********************************************************************
24887Schin *                                                                      *
34887Schin *               This software is part of the ast package               *
4*12068SRoger.Faulkner@Oracle.COM *          Copyright (c) 1985-2010 AT&T Intellectual Property          *
54887Schin *                      and is licensed under the                       *
64887Schin *                  Common Public License, Version 1.0                  *
78462SApril.Chin@Sun.COM *                    by AT&T Intellectual Property                     *
84887Schin *                                                                      *
94887Schin *                A copy of the License is available at                 *
104887Schin *            http://www.opensource.org/licenses/cpl1.0.txt             *
114887Schin *         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
124887Schin *                                                                      *
134887Schin *              Information and Software Systems Research               *
144887Schin *                            AT&T Research                             *
154887Schin *                           Florham Park NJ                            *
164887Schin *                                                                      *
174887Schin *                 Glenn Fowler <gsf@research.att.com>                  *
184887Schin *                  David Korn <dgk@research.att.com>                   *
194887Schin *                   Phong Vo <kpv@research.att.com>                    *
204887Schin *                                                                      *
214887Schin ***********************************************************************/
224887Schin #pragma prototyped
234887Schin /*
244887Schin  * original code
254887Schin  *
264887Schin  *  	James A. Woods, Informatics General Corporation,
274887Schin  *	NASA Ames Research Center, 6/81.
284887Schin  *	Usenix ;login:, February/March, 1983, p. 8.
294887Schin  *
304887Schin  * discipline/method interface
314887Schin  *
324887Schin  *	Glenn Fowler
334887Schin  *	AT&T Research
344887Schin  *	modified from the original BSD source
354887Schin  *
364887Schin  * 'fastfind' scans a file list for the full pathname of a file
374887Schin  * given only a piece of the name.  The list is processed with
384887Schin  * with "front-compression" and bigram coding.  Front compression reduces
394887Schin  * space by a factor of 4-5, bigram coding by a further 20-25%.
404887Schin  *
414887Schin  * there are 4 methods:
424887Schin  *
434887Schin  *	FF_old	original with 7 bit bigram encoding (no magic)
444887Schin  *	FF_gnu	8 bit clean front compression (FF_gnu_magic)
454887Schin  *	FF_dir	FF_gnu with sfgetl/sfputl and trailing / on dirs (FF_dir_magic)
464887Schin  *	FF_typ	FF_dir with (mime) types (FF_typ_magic)
474887Schin  *
484887Schin  * the bigram encoding steals the eighth bit (that's why its FF_old)
494887Schin  * maybe one day we'll limit it to readonly:
504887Schin  *
514887Schin  * 0-2*FF_OFF	 likeliest differential counts + offset to make nonnegative
524887Schin  * FF_ESC	 4 byte big-endian out-of-range count+FF_OFF follows
534887Schin  * FF_MIN-FF_MAX ascii residue
544887Schin  * >=FF_MAX	 bigram codes
554887Schin  *
564887Schin  * a two-tiered string search technique is employed
574887Schin  *
584887Schin  * a metacharacter-free subpattern and partial pathname is matched
594887Schin  * backwards to avoid full expansion of the pathname list
604887Schin  *
614887Schin  * then the actual shell glob-style regular expression (if in this form)
624887Schin  * is matched against the candidate pathnames using the slower regexec()
634887Schin  *
644887Schin  * The original BSD code is covered by the BSD license:
654887Schin  *
664887Schin  * Copyright (c) 1985, 1993, 1999
674887Schin  *	The Regents of the University of California.  All rights reserved.
684887Schin  *
694887Schin  * Redistribution and use in source and binary forms, with or without
704887Schin  * modification, are permitted provided that the following conditions
714887Schin  * are met:
724887Schin  * 1. Redistributions of source code must retain the above copyright
734887Schin  *    notice, this list of conditions and the following disclaimer.
744887Schin  * 2. Redistributions in binary form must reproduce the above copyright
754887Schin  *    notice, this list of conditions and the following disclaimer in the
764887Schin  *    documentation and/or other materials provided with the distribution.
774887Schin  * 3. Neither the name of the University nor the names of its contributors
784887Schin  *    may be used to endorse or promote products derived from this software
794887Schin  *    without specific prior written permission.
804887Schin  *
814887Schin  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
824887Schin  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
834887Schin  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
844887Schin  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
854887Schin  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
864887Schin  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
874887Schin  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
884887Schin  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
894887Schin  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
904887Schin  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
914887Schin  * SUCH DAMAGE.
924887Schin  */
934887Schin 
944887Schin static const char id[] = "\n@(#)$Id: fastfind (AT&T Research) 2002-10-02 $\0\n";
954887Schin 
964887Schin static const char lib[] = "libast:fastfind";
974887Schin 
984887Schin #include "findlib.h"
994887Schin 
1004887Schin #define FIND_MATCH	"*/(find|locate)/*"
1014887Schin 
1024887Schin /*
1034887Schin  * this db could be anywhere
1044887Schin  * findcodes[] directories are checked for findnames[i]
1054887Schin  */
1064887Schin 
1074887Schin static char*		findcodes[] =
1084887Schin {
1094887Schin 	0,
1104887Schin 	0,
1114887Schin 	FIND_CODES,
1124887Schin 	"/usr/local/share/lib",
1134887Schin 	"/usr/local/lib",
1144887Schin 	"/usr/share/lib",
1154887Schin 	"/usr/lib",
1164887Schin 	"/var/spool",
1174887Schin 	"/usr/local/var",
1184887Schin 	"/var/lib",
1194887Schin 	"/var/lib/slocate",
1204887Schin 	"/var/db",
1214887Schin };
1224887Schin 
1234887Schin static char*		findnames[] =
1244887Schin {
1254887Schin 	"find/codes",
1264887Schin 	"find/find.codes",
1274887Schin 	"locate/locatedb",
1284887Schin 	"locatedb",
1294887Schin 	"locate.database",
1304887Schin 	"slocate.db",
1314887Schin };
1324887Schin 
1334887Schin /*
1344887Schin  * convert t to lower case and drop leading x- and x- after /
1354887Schin  * converted value copied to b of size n
1364887Schin  */
1374887Schin 
1384887Schin char*
typefix(char * buf,size_t n,register const char * t)1394887Schin typefix(char* buf, size_t n, register const char* t)
1404887Schin {
1414887Schin 	register int	c;
1424887Schin 	register char*	b = buf;
1434887Schin 
1444887Schin 	if ((*t == 'x' || *t == 'X') && *(t + 1) == '-')
1454887Schin 		t += 2;
1464887Schin 	while (c = *t++)
1474887Schin 	{
1484887Schin 		if (isupper(c))
1494887Schin 			c = tolower(c);
1504887Schin 		if ((*b++ = c) == '/' && (*t == 'x' || *t == 'X') && *(t + 1) == '-')
1514887Schin 			t += 2;
1524887Schin 	}
1534887Schin 	*b = 0;
1544887Schin 	return buf;
1554887Schin }
1564887Schin 
1574887Schin /*
1584887Schin  * return a fastfind stream handle for pattern
1594887Schin  */
1604887Schin 
1614887Schin Find_t*
findopen(const char * file,const char * pattern,const char * type,Finddisc_t * disc)1624887Schin findopen(const char* file, const char* pattern, const char* type, Finddisc_t* disc)
1634887Schin {
1644887Schin 	register Find_t*	fp;
1654887Schin 	register char*		p;
1664887Schin 	register char*		s;
1674887Schin 	register char*		b;
1684887Schin 	register int		i;
1694887Schin 	register int		j;
1704887Schin 	char*			path;
1714887Schin 	int			brace = 0;
1724887Schin 	int			paren = 0;
1734887Schin 	int			k;
1744887Schin 	int			q;
1754887Schin 	int			fd;
1764887Schin 	int			uid;
1774887Schin 	Vmalloc_t*		vm;
1784887Schin 	Type_t*			tp;
1794887Schin 	struct stat		st;
1804887Schin 
1814887Schin 
1824887Schin 	if (!(vm = vmopen(Vmdcheap, Vmbest, 0)))
1834887Schin 		goto nospace;
1844887Schin 
1854887Schin 	/*
1864887Schin 	 * NOTE: searching for FIND_CODES would be much simpler if we
1874887Schin 	 *       just stuck with our own, but we also support GNU
1884887Schin 	 *	 locate codes and have to search for the one of a
1894887Schin 	 *	 bazillion possible names for that file
1904887Schin 	 */
1914887Schin 
1924887Schin 	if (!findcodes[1])
1934887Schin 		findcodes[1] = getenv(FIND_CODES_ENV);
1944887Schin 	if (disc->flags & FIND_GENERATE)
1954887Schin 	{
1964887Schin 		if (!(fp = (Find_t*)vmnewof(vm, 0, Find_t, 1, sizeof(Encode_t) - sizeof(Code_t))))
1974887Schin 			goto nospace;
1984887Schin 		fp->vm = vm;
1994887Schin 		fp->id = lib;
2004887Schin 		fp->disc = disc;
2014887Schin 		fp->generate = 1;
2024887Schin 		if (file && (!*file || streq(file, "-")))
2034887Schin 			file = 0;
2044887Schin 		uid = geteuid();
2054887Schin 		j = (findcodes[0] = (char*)file) && *file == '/' ? 1 : elementsof(findcodes);
2064887Schin 
2074887Schin 		/*
2084887Schin 		 * look for the codes file, but since it may not exist yet,
2094887Schin 		 * also look for the containing directory if i<2 or if
2104887Schin 		 * it is sufficiently qualified (FIND_MATCH)
2114887Schin 		 */
2124887Schin 
2134887Schin 		for (i = 0; i < j; i++)
2144887Schin 			if (path = findcodes[i])
2154887Schin 			{
2164887Schin 				if (*path == '/')
2174887Schin 				{
2184887Schin 					if (!stat(path, &st))
2194887Schin 					{
2204887Schin 						if (S_ISDIR(st.st_mode))
2214887Schin 						{
2224887Schin 							for (k = 0; k < elementsof(findnames); k++)
2234887Schin 							{
2244887Schin 								sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s/%s", path, findnames[k]);
2254887Schin 								if (!eaccess(fp->encode.file, R_OK|W_OK))
2264887Schin 								{
2274887Schin 									path = fp->encode.file;
2284887Schin 									break;
2294887Schin 								}
2304887Schin 								if (strchr(findnames[k], '/') && (b = strrchr(fp->encode.file, '/')))
2314887Schin 								{
2324887Schin 									*b = 0;
2334887Schin 									if (!stat(fp->encode.file, &st) && st.st_uid == uid && (st.st_mode & S_IWUSR))
2344887Schin 									{
2354887Schin 										*b = '/';
2364887Schin 										path = fp->encode.file;
2374887Schin 										break;
2384887Schin 									}
2394887Schin 								}
2404887Schin 							}
2414887Schin 							if (k < elementsof(findnames))
2424887Schin 								break;
2434887Schin 						}
2444887Schin 						else if (st.st_uid == uid && (st.st_mode & S_IWUSR))
2454887Schin 						{
2464887Schin 							sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s", path);
2474887Schin 							path = fp->encode.file;
2484887Schin 							break;
2494887Schin 						}
2504887Schin 					}
2514887Schin 					else if (i < 2 || strmatch(path, FIND_MATCH))
2524887Schin 					{
2534887Schin 						sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s", path);
2544887Schin 						if (b = strrchr(fp->encode.file, '/'))
2554887Schin 						{
2564887Schin 							*b = 0;
2574887Schin 							if (!stat(fp->encode.file, &st) && st.st_uid == uid && (st.st_mode & S_IWUSR))
2584887Schin 							{
2594887Schin 								*b = '/';
2604887Schin 								path = fp->encode.file;
2614887Schin 								break;
2624887Schin 							}
2634887Schin 						}
2644887Schin 					}
2654887Schin 				}
2664887Schin 				else if (pathpath(fp->encode.file, path, "", PATH_REGULAR|PATH_READ|PATH_WRITE))
2674887Schin 				{
2684887Schin 					path = fp->encode.file;
2694887Schin 					break;
2704887Schin 				}
2714887Schin 				else if (b = strrchr(path, '/'))
2724887Schin 				{
2734887Schin 					sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%-.*s", b - path, path);
2744887Schin 					if (pathpath(fp->encode.temp, fp->encode.file, "", PATH_EXECUTE|PATH_READ|PATH_WRITE) &&
2754887Schin 					    !stat(fp->encode.temp, &st) && st.st_uid == uid && (st.st_mode & S_IWUSR))
2764887Schin 					{
2774887Schin 						sfsprintf(fp->encode.file, sizeof(fp->encode.file), "%s%s", fp->encode.temp, b);
2784887Schin 						path = fp->encode.file;
2794887Schin 						break;
2804887Schin 					}
2814887Schin 				}
2824887Schin 			}
2834887Schin 		if (i >= j)
2844887Schin 		{
2854887Schin 			if (fp->disc->errorf)
2864887Schin 				(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot locate codes", file ? file : findcodes[2]);
2874887Schin 			goto drop;
2884887Schin 		}
2894887Schin 		if (fp->disc->flags & FIND_OLD)
2904887Schin 		{
2914887Schin 			/*
2924887Schin 			 * FF_old generates temp data that is read
2934887Schin 			 * in a second pass to generate the real codes
2944887Schin 			 */
2954887Schin 
2964887Schin 			fp->method = FF_old;
2974887Schin 			if (!(fp->fp = sftmp(32 * PATH_MAX)))
2984887Schin 			{
2994887Schin 				if (fp->disc->errorf)
3004887Schin 					(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "cannot create tmp file");
3014887Schin 				goto drop;
3024887Schin 			}
3034887Schin 		}
3044887Schin 		else
3054887Schin 		{
3064887Schin 			/*
3074887Schin 			 * the rest generate into a temp file that
3084887Schin 			 * is simply renamed on completion
3094887Schin 			 */
3104887Schin 
3114887Schin 			if (s = strrchr(path, '/'))
3124887Schin 			{
3134887Schin 				*s = 0;
3144887Schin 				p = path;
3154887Schin 			}
3164887Schin 			else
3174887Schin 				p = ".";
3184887Schin 			if (!pathtemp(fp->encode.temp, sizeof(fp->encode.temp), p, "ff", &fd))
3194887Schin 			{
3204887Schin 				if (fp->disc->errorf)
3214887Schin 					(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "%s: cannot create tmp file in this directory", p ? p : ".");
3224887Schin 				goto drop;
3234887Schin 			}
3244887Schin 			if (s)
3254887Schin 				*s = '/';
3264887Schin 			if (!(fp->fp = sfnew(NiL, NiL, (size_t)SF_UNBOUND, fd, SF_WRITE)))
3274887Schin 			{
3284887Schin 				if (fp->disc->errorf)
3294887Schin 					(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "%s: cannot open tmp file", fp->encode.temp);
3304887Schin 				close(fd);
3314887Schin 				goto drop;
3324887Schin 			}
3334887Schin 			if (fp->disc->flags & FIND_TYPE)
3344887Schin 			{
3354887Schin 				fp->method = FF_typ;
3364887Schin 				fp->encode.namedisc.key = offsetof(Type_t, name);
3374887Schin 				fp->encode.namedisc.link = offsetof(Type_t, byname);
3384887Schin 				fp->encode.indexdisc.key = offsetof(Type_t, index);
3394887Schin 				fp->encode.indexdisc.size = sizeof(unsigned long);
3404887Schin 				fp->encode.indexdisc.link = offsetof(Type_t, byindex);
3414887Schin 				s = "system/dir";
3424887Schin 				if (!(fp->encode.namedict = dtopen(&fp->encode.namedisc, Dttree)) || !(fp->encode.indexdict = dtopen(&fp->encode.indexdisc, Dttree)) || !(tp = newof(0, Type_t, 1, strlen(s) + 1)))
3434887Schin 				{
3444887Schin 					if (fp->encode.namedict)
3454887Schin 						dtclose(fp->encode.namedict);
3464887Schin 					if (fp->disc->errorf)
3474887Schin 						(*fp->disc->errorf)(fp, fp->disc, 2, "cannot allocate type table");
3484887Schin 					goto drop;
3494887Schin 				}
3504887Schin 
3514887Schin 				/*
3524887Schin 				 * type index 1 is always system/dir
3534887Schin 				 */
3544887Schin 
3554887Schin 				tp->index = ++fp->types;
3564887Schin 				strcpy(tp->name, s);
3574887Schin 				dtinsert(fp->encode.namedict, tp);
3584887Schin 				dtinsert(fp->encode.indexdict, tp);
3594887Schin 			}
3604887Schin 			else if (fp->disc->flags & FIND_GNU)
3614887Schin 			{
3624887Schin 				fp->method = FF_gnu;
3634887Schin 				sfputc(fp->fp, 0);
3644887Schin 				sfputr(fp->fp, FF_gnu_magic, 0);
3654887Schin 			}
3664887Schin 			else
3674887Schin 			{
3684887Schin 				fp->method = FF_dir;
3694887Schin 				sfputc(fp->fp, 0);
3704887Schin 				sfputr(fp->fp, FF_dir_magic, 0);
3714887Schin 			}
3724887Schin 		}
3734887Schin 	}
3744887Schin 	else
3754887Schin 	{
3764887Schin 		i = sizeof(Decode_t) + sizeof(Code_t);
3774887Schin 		if (!pattern || !*pattern)
3784887Schin 			pattern = "*";
3794887Schin 		i += (j = 2 * (strlen(pattern) + 1));
3804887Schin 		if (!(fp = (Find_t*)vmnewof(vm, 0, Find_t, 1, i)))
3814887Schin 		{
3824887Schin 			vmclose(vm);
3834887Schin 			return 0;
3844887Schin 		}
3854887Schin 		fp->vm = vm;
3864887Schin 		fp->id = lib;
3874887Schin 		fp->disc = disc;
3884887Schin 		if (disc->flags & FIND_ICASE)
3894887Schin 			fp->decode.ignorecase = 1;
3904887Schin 		j = (findcodes[0] = (char*)file) && *file == '/' ? 1 : elementsof(findcodes);
3914887Schin 		for (i = 0; i < j; i++)
3924887Schin 			if (path = findcodes[i])
3934887Schin 			{
3944887Schin 				if (*path == '/')
3954887Schin 				{
3964887Schin 					if (!stat(path, &st))
3974887Schin 					{
3984887Schin 						if (S_ISDIR(st.st_mode))
3994887Schin 						{
4004887Schin 							for (k = 0; k < elementsof(findnames); k++)
4014887Schin 							{
4024887Schin 								sfsprintf(fp->decode.path, sizeof(fp->decode.path), "%s/%s", path, findnames[k]);
4034887Schin 								if (fp->fp = sfopen(NiL, fp->decode.path, "r"))
4044887Schin 								{
4054887Schin 									path = fp->decode.path;
4064887Schin 									break;
4074887Schin 								}
4084887Schin 							}
4094887Schin 							if (fp->fp)
4104887Schin 								break;
4114887Schin 						}
4124887Schin 						else if (fp->fp = sfopen(NiL, path, "r"))
4134887Schin 							break;
4144887Schin 					}
4154887Schin 				}
4164887Schin 				else if ((path = pathpath(fp->decode.path, path, "", PATH_REGULAR|PATH_READ)) && (fp->fp = sfopen(NiL, path, "r")))
4174887Schin 					break;
4184887Schin 			}
4194887Schin 		if (!fp->fp)
4204887Schin 		{
4214887Schin 			if (fp->disc->errorf)
4224887Schin 				(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot locate codes", file ? file : findcodes[2]);
4234887Schin 			goto drop;
4244887Schin 		}
4254887Schin 		if (fstat(sffileno(fp->fp), &st))
4264887Schin 		{
4274887Schin 			if (fp->disc->errorf)
4284887Schin 				(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot stat codes", path);
4294887Schin 			goto drop;
4304887Schin 		}
4314887Schin 		if (fp->secure = ((st.st_mode & (S_IRGRP|S_IROTH)) == S_IRGRP) && st.st_gid == getegid() && getegid() != getgid())
4324887Schin 			setgid(getgid());
4334887Schin 		fp->stamp = st.st_mtime;
4344887Schin 		b = (s = fp->decode.temp) + 1;
4354887Schin 		for (i = 0; i < elementsof(fp->decode.bigram1); i++)
4364887Schin 		{
4374887Schin 			if ((j = sfgetc(fp->fp)) == EOF)
4384887Schin 				goto invalid;
4394887Schin 			if (!(*s++ = fp->decode.bigram1[i] = j) && i)
4404887Schin 			{
4414887Schin 				i = -i;
4424887Schin 				break;
4434887Schin 			}
4444887Schin 			if ((j = sfgetc(fp->fp)) == EOF)
4454887Schin 				goto invalid;
4464887Schin 			if (!(*s++ = fp->decode.bigram2[i] = j) && (i || fp->decode.bigram1[0] >= '0' && fp->decode.bigram1[0] <= '1'))
4474887Schin 				break;
4484887Schin 		}
4494887Schin 		if (streq(b, FF_typ_magic))
4504887Schin 		{
4514887Schin 			if (type)
4524887Schin 			{
4534887Schin 				type = (const char*)typefix(fp->decode.bigram2, sizeof(fp->decode.bigram2), type);
4544887Schin 				memset(fp->decode.bigram1, 0, sizeof(fp->decode.bigram1));
4554887Schin 			}
4564887Schin 			fp->method = FF_typ;
4574887Schin 			for (j = 0, i = 1;; i++)
4584887Schin 			{
4594887Schin 				if (!(s = sfgetr(fp->fp, 0, 0)))
4604887Schin 					goto invalid;
4614887Schin 				if (!*s)
4624887Schin 					break;
4634887Schin 				if (type && strmatch(s, type))
4644887Schin 				{
4654887Schin 					FF_SET_TYPE(fp, i);
4664887Schin 					j++;
4674887Schin 				}
4684887Schin 			}
4694887Schin 			if (type && !j)
4704887Schin 				goto drop;
4714887Schin 			fp->types = j;
4724887Schin 		}
4734887Schin 		else if (streq(b, FF_dir_magic))
4744887Schin 			fp->method = FF_dir;
4754887Schin 		else if (streq(b, FF_gnu_magic))
4764887Schin 			fp->method = FF_gnu;
4774887Schin 		else if (!*b && *--b >= '0' && *b <= '1')
4784887Schin 		{
4794887Schin 			fp->method = FF_gnu;
4804887Schin 			while (j = sfgetc(fp->fp))
4814887Schin 			{
4824887Schin 				if (j == EOF || fp->decode.count >= sizeof(fp->decode.path))
4834887Schin 					goto invalid;
4844887Schin 				fp->decode.path[fp->decode.count++] = j;
4854887Schin 			}
4864887Schin 		}
4874887Schin 		else
4884887Schin 		{
4894887Schin 			fp->method = FF_old;
4904887Schin 			if (i < 0)
4914887Schin 			{
4924887Schin 				if ((j = sfgetc(fp->fp)) == EOF)
4934887Schin 					goto invalid;
4944887Schin 				fp->decode.bigram2[i = -i] = j;
4954887Schin 			}
4964887Schin 			while (++i < elementsof(fp->decode.bigram1))
4974887Schin 			{
4984887Schin 				if ((j = sfgetc(fp->fp)) == EOF)
4994887Schin 					goto invalid;
5004887Schin 				fp->decode.bigram1[i] = j;
5014887Schin 				if ((j = sfgetc(fp->fp)) == EOF)
5024887Schin 					goto invalid;
5034887Schin 				fp->decode.bigram2[i] = j;
5044887Schin 			}
5054887Schin 			if ((fp->decode.peek = sfgetc(fp->fp)) != FF_OFF)
5064887Schin 				goto invalid;
5074887Schin 		}
5084887Schin 
5094887Schin 		/*
5104887Schin 		 * set up the physical dir table
5114887Schin 		 */
5124887Schin 
5134887Schin 		if (disc->version >= 19980301L)
5144887Schin 		{
5154887Schin 			fp->verifyf = disc->verifyf;
5164887Schin 			if (disc->dirs && *disc->dirs)
5174887Schin 			{
5184887Schin 				for (k = 0; disc->dirs[k]; k++);
5194887Schin 				if (k == 1 && streq(disc->dirs[0], "/"))
5204887Schin 					k = 0;
5214887Schin 				if (k)
5224887Schin 				{
5234887Schin 					if (!(fp->dirs = vmnewof(fp->vm, 0, char*, 2 * k + 1, 0)))
5244887Schin 						goto drop;
5254887Schin 					if (!(fp->lens = vmnewof(fp->vm, 0, int, 2 * k, 0)))
5264887Schin 						goto drop;
5274887Schin 					p = 0;
5284887Schin 					b = fp->decode.temp;
5294887Schin 					j = fp->method == FF_old || fp->method == FF_gnu;
5304887Schin 
5314887Schin 					/*
5324887Schin 					 * fill the dir list with logical and
5334887Schin 					 * physical names since we don't know
5344887Schin 					 * which way the db was encoded (it
5354887Schin 					 * could be *both* ways)
5364887Schin 					 */
5374887Schin 
5384887Schin 					for (i = q = 0; i < k; i++)
5394887Schin 					{
5404887Schin 						if (*(s = disc->dirs[i]) == '/')
5414887Schin 							sfsprintf(b, sizeof(fp->decode.temp) - 1, "%s", s);
5424887Schin 						else if (!p && !(p = getcwd(fp->decode.path, sizeof(fp->decode.path))))
5434887Schin 							goto nospace;
5444887Schin 						else
5454887Schin 							sfsprintf(b, sizeof(fp->decode.temp) - 1, "%s/%s", p, s);
5464887Schin 						s = pathcanon(b, 0);
5474887Schin 						*s = '/';
5484887Schin 						*(s + 1) = 0;
5494887Schin 						if (!(fp->dirs[q] = vmstrdup(fp->vm, b)))
5504887Schin 							goto nospace;
5514887Schin 						if (j)
5524887Schin 							(fp->dirs[q])[s - b] = 0;
5534887Schin 						q++;
5544887Schin 						*s = 0;
5554887Schin 						s = pathcanon(b, PATH_PHYSICAL);
5564887Schin 						*s = '/';
5574887Schin 						*(s + 1) = 0;
5584887Schin 						if (!strneq(b, fp->dirs[q - 1], s - b))
5594887Schin 						{
5604887Schin 							if (!(fp->dirs[q] = vmstrdup(fp->vm, b)))
5614887Schin 								goto nospace;
5624887Schin 							if (j)
5634887Schin 								(fp->dirs[q])[s - b] = 0;
5644887Schin 							q++;
5654887Schin 						}
5664887Schin 					}
5674887Schin 					strsort(fp->dirs, q, strcasecmp);
5684887Schin 					for (i = 0; i < q; i++)
5694887Schin 						fp->lens[i] = strlen(fp->dirs[i]);
5704887Schin 				}
5714887Schin 			}
5724887Schin 		}
5734887Schin 		if (fp->verifyf || (disc->flags & FIND_VERIFY))
5744887Schin 		{
5754887Schin 			if (fp->method != FF_dir && fp->method != FF_typ)
5764887Schin 			{
5774887Schin 				if (fp->disc->errorf)
5784887Schin 					(*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");
5794887Schin 				goto drop;
5804887Schin 			}
5814887Schin 			fp->verify = 1;
5824887Schin 		}
5834887Schin 
5844887Schin 		/*
5854887Schin 		 * extract last glob-free subpattern in name for fast pre-match
5864887Schin 		 * prepend 0 for backwards match
5874887Schin 		 */
5884887Schin 
5894887Schin 		if (p = s = (char*)pattern)
5904887Schin 		{
5914887Schin 			b = fp->decode.pattern;
5924887Schin 			for (;;)
5934887Schin 			{
5944887Schin 				switch (*b++ = *p++)
5954887Schin 				{
5964887Schin 				case 0:
5974887Schin 					break;
5984887Schin 				case '\\':
5994887Schin 					s = p;
6004887Schin 					if (!*p++)
6014887Schin 						break;
6024887Schin 					continue;
6034887Schin 				case '[':
6044887Schin 					if (!brace)
6054887Schin 					{
6064887Schin 						brace++;
6074887Schin 						if (*p == ']')
6084887Schin 							p++;
6094887Schin 					}
6104887Schin 					continue;
6114887Schin 				case ']':
6124887Schin 					if (brace)
6134887Schin 					{
6144887Schin 						brace--;
6154887Schin 						s = p;
6164887Schin 					}
6174887Schin 					continue;
6184887Schin 				case '(':
6194887Schin 					if (!brace)
6204887Schin 						paren++;
6214887Schin 					continue;
6224887Schin 				case ')':
6234887Schin 					if (!brace && paren > 0 && !--paren)
6244887Schin 						s = p;
6254887Schin 					continue;
6264887Schin 				case '|':
6274887Schin 				case '&':
6284887Schin 					if (!brace && !paren)
6294887Schin 					{
6304887Schin 						s = "";
6314887Schin 						break;
6324887Schin 					}
6334887Schin 					continue;
6344887Schin 				case '*':
6354887Schin 				case '?':
6364887Schin 					s = p;
6374887Schin 					continue;
6384887Schin 				default:
6394887Schin 					continue;
6404887Schin 				}
6414887Schin 				break;
6424887Schin 			}
6434887Schin 			if (s != pattern && !streq(pattern, "*"))
6444887Schin 			{
6454887Schin 				fp->decode.match = 1;
6464887Schin 				if (i = regcomp(&fp->decode.re, pattern, REG_SHELL|REG_AUGMENTED|(fp->decode.ignorecase?REG_ICASE:0)))
6474887Schin 				{
6484887Schin 					if (disc->errorf)
6494887Schin 					{
6504887Schin 						regerror(i, &fp->decode.re, fp->decode.temp, sizeof(fp->decode.temp));
6514887Schin 						(*fp->disc->errorf)(fp, fp->disc, 2, "%s: %s", pattern, fp->decode.temp);
6524887Schin 					}
6534887Schin 					goto drop;
6544887Schin 				}
6554887Schin 			}
6564887Schin 			if (*s)
6574887Schin 			{
6584887Schin 				*b++ = 0;
6594887Schin 				while (i = *s++)
6604887Schin 					*b++ = i;
6614887Schin 				*b-- = 0;
6624887Schin 				fp->decode.end = b;
6634887Schin 				if (fp->decode.ignorecase)
6644887Schin 					for (s = fp->decode.pattern; s <= b; s++)
6654887Schin 						if (isupper(*s))
6664887Schin 							*s = tolower(*s);
6674887Schin 			}
6684887Schin 		}
6694887Schin 	}
6704887Schin 	return fp;
6714887Schin  nospace:
6724887Schin 	if (disc->errorf)
6734887Schin 		(*fp->disc->errorf)(fp, fp->disc, 2, "out of space");
6744887Schin 	if (!vm)
6754887Schin 		return 0;
6764887Schin 	if (!fp)
6774887Schin 	{
6784887Schin 		vmclose(vm);
6794887Schin 		return 0;
6804887Schin 	}
6814887Schin 	goto drop;
6824887Schin  invalid:
6834887Schin 	if (fp->disc->errorf)
6844887Schin 		(*fp->disc->errorf)(fp, fp->disc, 2, "%s: invalid codes", path);
6854887Schin  drop:
6864887Schin 	if (!fp->generate && fp->decode.match)
6874887Schin 		regfree(&fp->decode.re);
6884887Schin 	if (fp->fp)
6894887Schin 		sfclose(fp->fp);
6904887Schin 	vmclose(fp->vm);
6914887Schin 	return 0;
6924887Schin }
6934887Schin 
6944887Schin /*
6954887Schin  * return the next fastfind path
6964887Schin  * 0 returned when list exhausted
6974887Schin  */
6984887Schin 
6994887Schin char*
findread(register Find_t * fp)7004887Schin findread(register Find_t* fp)
7014887Schin {
7024887Schin 	register char*		p;
7034887Schin 	register char*		q;
7044887Schin 	register char*		s;
7054887Schin 	register char*		b;
7064887Schin 	register char*		e;
7074887Schin 	register int		c;
7084887Schin 	register int		n;
7094887Schin 	register int		m;
7104887Schin 	int			ignorecase;
7114887Schin 	int			t;
7124887Schin 	unsigned char		w[4];
7134887Schin 	struct stat		st;
7144887Schin 
7154887Schin 	if (fp->generate)
7164887Schin 		return 0;
7174887Schin 	if (fp->decode.restore)
7184887Schin 	{
7194887Schin 		*fp->decode.restore = '/';
7204887Schin 		fp->decode.restore = 0;
7214887Schin 	}
7224887Schin 	ignorecase = fp->decode.ignorecase ? STR_ICASE : 0;
7234887Schin 	c = fp->decode.peek;
7244887Schin  next:
7254887Schin 	for (;;)
7264887Schin 	{
7274887Schin 		switch (fp->method)
7284887Schin 		{
7294887Schin 		case FF_dir:
7304887Schin 			t = 0;
7314887Schin 			n = sfgetl(fp->fp);
7324887Schin 			goto grab;
7334887Schin 		case FF_gnu:
7344887Schin 			if ((c = sfgetc(fp->fp)) == EOF)
7354887Schin 				return 0;
7364887Schin 			if (c == 0x80)
7374887Schin 			{
7384887Schin 				if ((c = sfgetc(fp->fp)) == EOF)
7394887Schin 					return 0;
7404887Schin 				n = c << 8;
7414887Schin 				if ((c = sfgetc(fp->fp)) == EOF)
7424887Schin 					return 0;
7434887Schin 				n |= c;
7444887Schin 				if (n & 0x8000)
7454887Schin 					n = (n - 0xffff) - 1;
7464887Schin 			}
7474887Schin 			else if ((n = c) & 0x80)
7484887Schin 				n = (n - 0xff) - 1;
7494887Schin 			t = 0;
7504887Schin 			goto grab;
7514887Schin 		case FF_typ:
7524887Schin 			t = sfgetu(fp->fp);
7534887Schin 			n = sfgetl(fp->fp);
7544887Schin 		grab:
7554887Schin 			p = fp->decode.path + (fp->decode.count += n);
7564887Schin 			do
7574887Schin 			{
7584887Schin 				if ((c = sfgetc(fp->fp)) == EOF)
7594887Schin 					return 0;
7604887Schin 			} while (*p++ = c);
7614887Schin 			p -= 2;
7624887Schin 			break;
7634887Schin 		case FF_old:
7644887Schin 			if (c == EOF)
7654887Schin 			{
7664887Schin 				fp->decode.peek = c;
7674887Schin 				return 0;
7684887Schin 			}
7694887Schin 			if (c == FF_ESC)
7704887Schin 			{
7714887Schin 				if (sfread(fp->fp, w, sizeof(w)) != sizeof(w))
7724887Schin 					return 0;
7734887Schin 				if (fp->decode.swap >= 0)
7744887Schin 				{
7754887Schin 					c = (int32_t)((w[0] << 24) | (w[1] << 16) | (w[2] << 8) | w[3]);
7764887Schin 					if (!fp->decode.swap)
7774887Schin 					{
7784887Schin 						/*
7794887Schin 						 * the old format uses machine
7804887Schin 						 * byte order; this test uses
7814887Schin 						 * the smallest magnitude of
7824887Schin 						 * both byte orders on the
7834887Schin 						 * first encoded path motion
7844887Schin 						 * to determine the original
7854887Schin 						 * byte order
7864887Schin 						 */
7874887Schin 
7884887Schin 						m = c;
7894887Schin 						if (m < 0)
7904887Schin 							m = -m;
7914887Schin 						n = (int32_t)((w[3] << 24) | (w[2] << 16) | (w[1] << 8) | w[0]);
7924887Schin 						if (n < 0)
7934887Schin 							n = -n;
7944887Schin 						if (m < n)
7954887Schin 							fp->decode.swap = 1;
7964887Schin 						else
7974887Schin 						{
7984887Schin 							fp->decode.swap = -1;
7994887Schin 							c = (int32_t)((w[3] << 24) | (w[2] << 16) | (w[1] << 8) | w[0]);
8004887Schin 						}
8014887Schin 					}
8024887Schin 				}
8034887Schin 				else
8044887Schin 					c = (int32_t)((w[3] << 24) | (w[2] << 16) | (w[1] << 8) | w[0]);
8054887Schin 			}
8064887Schin 			fp->decode.count += c - FF_OFF;
8074887Schin 			for (p = fp->decode.path + fp->decode.count; (c = sfgetc(fp->fp)) > FF_ESC;)
8084887Schin 				if (c & (1<<(CHAR_BIT-1)))
8094887Schin 				{
8104887Schin 					*p++ = fp->decode.bigram1[c & ((1<<(CHAR_BIT-1))-1)];
8114887Schin 					*p++ = fp->decode.bigram2[c & ((1<<(CHAR_BIT-1))-1)];
8124887Schin 				}
8134887Schin 				else
8144887Schin 					*p++ = c;
8154887Schin 			*p-- = 0;
8164887Schin 			t = 0;
8174887Schin 			break;
8184887Schin 		}
8194887Schin 		b = fp->decode.path;
8204887Schin 		if (fp->decode.found)
8214887Schin 			fp->decode.found = 0;
8224887Schin 		else
8234887Schin 			b += fp->decode.count;
8244887Schin 		if (fp->dirs)
8254887Schin 			for (;;)
8264887Schin 			{
8274887Schin 				if (!*fp->dirs)
8284887Schin 					return 0;
8294887Schin 
8304887Schin 				/*
8314887Schin 				 * use the ordering and lengths to prune
8324887Schin 				 * comparison function calls
8334887Schin 				 * (*fp->dirs)[*fp->lens]=='/' if its
8344887Schin 				 * already been matched
8354887Schin 				 */
8364887Schin 
8374887Schin 				if ((n = p - fp->decode.path + 1) > (m = *fp->lens))
8384887Schin 				{
8394887Schin 					if (!(*fp->dirs)[m])
8404887Schin 						goto next;
8414887Schin 					if (!strncasecmp(*fp->dirs, fp->decode.path, m))
8424887Schin 						break;
8434887Schin 				}
8444887Schin 				else if (n == m)
8454887Schin 				{
8464887Schin 					if (!(*fp->dirs)[m])
8474887Schin 					{
8484887Schin 						if (!(n = strcasecmp(*fp->dirs, fp->decode.path)) && (ignorecase || !strcmp(*fp->dirs, fp->decode.path)))
8494887Schin 						{
8504887Schin 							if (m > 0)
8514887Schin 							{
8524887Schin 								(*fp->dirs)[m] = '/';
8534887Schin 								if ((*fp->dirs)[m - 1] != '/')
8544887Schin 									(*fp->dirs)[++(*fp->lens)] = '/';
8554887Schin 							}
8564887Schin 							break;
8574887Schin 						}
8584887Schin 						if (n >= 0)
8594887Schin 							goto next;
8604887Schin 					}
8614887Schin 				}
8624887Schin 				else if (!(*fp->dirs)[m])
8634887Schin 					goto next;
8644887Schin 				fp->dirs++;
8654887Schin 				fp->lens++;
8664887Schin 			}
8674887Schin 		if (fp->verify && (*p == '/' || t == 1))
8684887Schin 		{
8694887Schin 			if ((n = p - fp->decode.path))
8704887Schin 				*p = 0;
8714887Schin 			else
8724887Schin 				n = 1;
8734887Schin 			if (fp->verifyf)
8744887Schin 				n = (*fp->verifyf)(fp, fp->decode.path, n, fp->disc);
8754887Schin 			else if (stat(fp->decode.path, &st))
8764887Schin 				n = -1;
8774887Schin 			else if ((unsigned long)st.st_mtime > fp->stamp)
8784887Schin 				n = 1;
8794887Schin 			else
8804887Schin 				n = 0;
8814887Schin 			*p = '/';
8824887Schin 
8834887Schin 			/*
8844887Schin 			 * n<0	skip this subtree
8854887Schin 			 * n==0 keep as is
8864887Schin 			 * n>0	read this dir now
8874887Schin 			 */
8884887Schin 
8894887Schin 			/* NOT IMPLEMENTED YET */
8904887Schin 		}
8914887Schin 		if (FF_OK_TYPE(fp, t))
8924887Schin 		{
8934887Schin 			if (fp->decode.end)
8944887Schin 			{
8954887Schin 				if (*(s = p) == '/')
8964887Schin 					s--;
8974887Schin 				if (*fp->decode.pattern == '/' && b > fp->decode.path)
8984887Schin 					b--;
8994887Schin 				for (; s >= b; s--)
9004887Schin 					if (*s == *fp->decode.end || ignorecase && tolower(*s) == *fp->decode.end)
9014887Schin 					{
9024887Schin 						if (ignorecase)
9034887Schin 							for (e = fp->decode.end - 1, q = s - 1; *e && (*q == *e || tolower(*q) == *e); e--, q--);
9044887Schin 						else
9054887Schin 							for (e = fp->decode.end - 1, q = s - 1; *e && *q == *e; e--, q--);
9064887Schin 						if (!*e)
9074887Schin 						{
9084887Schin 							fp->decode.found = 1;
9094887Schin 							if (!fp->decode.match || strgrpmatch(fp->decode.path, fp->decode.pattern, NiL, 0, STR_MAXIMAL|STR_LEFT|STR_RIGHT|ignorecase))
9104887Schin 							{
9114887Schin 								fp->decode.peek = c;
9124887Schin 								if (*p == '/')
9134887Schin 									*(fp->decode.restore = p) = 0;
9144887Schin 								if (!fp->secure || !access(fp->decode.path, F_OK))
9154887Schin 									return fp->decode.path;
9164887Schin 							}
9174887Schin 							break;
9184887Schin 						}
9194887Schin 					}
9204887Schin 			}
9214887Schin 			else if (!fp->decode.match || !(n = regexec(&fp->decode.re, fp->decode.path, 0, NiL, 0)))
9224887Schin 			{
9234887Schin 				fp->decode.peek = c;
9244887Schin 				if (*p == '/' && p > fp->decode.path)
9254887Schin 					*(fp->decode.restore = p) = 0;
9264887Schin 				if (!fp->secure || !access(fp->decode.path, F_OK))
9274887Schin 					return fp->decode.path;
9284887Schin 			}
9294887Schin 			else if (n != REG_NOMATCH)
9304887Schin 			{
9314887Schin 				if (fp->disc->errorf)
9324887Schin 				{
9334887Schin 					regerror(n, &fp->decode.re, fp->decode.temp, sizeof(fp->decode.temp));
9344887Schin 					(*fp->disc->errorf)(fp, fp->disc, 2, "%s: %s", fp->decode.pattern, fp->decode.temp);
9354887Schin 				}
9364887Schin 				return 0;
9374887Schin 			}
9384887Schin 		}
9394887Schin 	}
9404887Schin }
9414887Schin 
9424887Schin /*
9434887Schin  * add path to the code table
9444887Schin  * paths are assumed to be in sort order
9454887Schin  */
9464887Schin 
9474887Schin int
findwrite(register Find_t * fp,const char * path,size_t len,const char * type)9484887Schin findwrite(register Find_t* fp, const char* path, size_t len, const char* type)
9494887Schin {
9504887Schin 	register unsigned char*	s;
9514887Schin 	register unsigned char*	e;
9524887Schin 	register unsigned char*	p;
9534887Schin 	register int		n;
9544887Schin 	register int		d;
9554887Schin 	register Type_t*	x;
9564887Schin 	register unsigned long	u;
9574887Schin 
9584887Schin 	if (!fp->generate)
9594887Schin 		return -1;
9604887Schin 	if (type && fp->method == FF_dir)
9614887Schin 	{
9624887Schin 		len = sfsprintf(fp->encode.mark, sizeof(fp->encode.mark), "%-.*s/", len, path);
9634887Schin 		path = fp->encode.mark;
9644887Schin 	}
9654887Schin 	s = (unsigned char*)path;
9664887Schin 	if (len <= 0)
9674887Schin 		len = strlen(path);
9684887Schin 	if (len < sizeof(fp->encode.path))
9694887Schin 		e = s + len++;
9704887Schin 	else
9714887Schin 	{
9724887Schin 		len = sizeof(fp->encode.path) - 1;
9734887Schin 		e = s + len;
9744887Schin 	}
9754887Schin 	p = (unsigned char*)fp->encode.path;
9764887Schin 	while (s < e)
9774887Schin 	{
9784887Schin 		if (*s != *p++)
9794887Schin 			break;
9804887Schin 		s++;
9814887Schin 	}
9824887Schin 	n = s - (unsigned char*)path;
9834887Schin 	switch (fp->method)
9844887Schin 	{
9854887Schin 	case FF_gnu:
9864887Schin 		d = n - fp->encode.prefix;
9874887Schin 		if (d >= -127 && d <= 127)
9884887Schin 			sfputc(fp->fp, d & 0xff);
9894887Schin 		else
9904887Schin 		{
9914887Schin 			sfputc(fp->fp, 0x80);
9924887Schin 			sfputc(fp->fp, (d >> 8) & 0xff);
9934887Schin 			sfputc(fp->fp, d & 0xff);
9944887Schin 		}
9954887Schin 		fp->encode.prefix = n;
9964887Schin 		sfputr(fp->fp, (char*)s, 0);
9974887Schin 		break;
9984887Schin 	case FF_old:
9994887Schin 		sfprintf(fp->fp, "%ld", n - fp->encode.prefix + FF_OFF);
10004887Schin 		fp->encode.prefix = n;
10014887Schin 		sfputc(fp->fp, ' ');
10024887Schin 		p = s;
10034887Schin 		while (s < e)
10044887Schin 		{
10054887Schin 			n = *s++;
10064887Schin 			if (s >= e)
10074887Schin 				break;
10084887Schin 			fp->encode.code[n][*s++]++;
10094887Schin 		}
10104887Schin 		while (p < e)
10114887Schin 		{
10124887Schin 			if ((n = *p++) < FF_MIN || n >= FF_MAX)
10134887Schin 				n = '?';
10144887Schin 			sfputc(fp->fp, n);
10154887Schin 		}
10164887Schin 		sfputc(fp->fp, 0);
10174887Schin 		break;
10184887Schin 	case FF_typ:
10194887Schin 		if (type)
10204887Schin 		{
10214887Schin 			type = (const char*)typefix((char*)fp->encode.bigram, sizeof(fp->encode.bigram), type);
10224887Schin 			if (x = (Type_t*)dtmatch(fp->encode.namedict, type))
10234887Schin 				u = x->index;
10244887Schin 			else if (!(x = newof(0, Type_t, 1, strlen(type) + 1)))
10254887Schin 				u = 0;
10264887Schin 			else
10274887Schin 			{
10284887Schin 				u = x->index = ++fp->types;
10294887Schin 				strcpy(x->name, type);
10304887Schin 				dtinsert(fp->encode.namedict, x);
10314887Schin 				dtinsert(fp->encode.indexdict, x);
10324887Schin 			}
10334887Schin 		}
10344887Schin 		else
10354887Schin 			u = 0;
10364887Schin 		sfputu(fp->fp, u);
10374887Schin 		/*FALLTHROUGH...*/
10384887Schin 	case FF_dir:
10394887Schin 		d = n - fp->encode.prefix;
10404887Schin 		sfputl(fp->fp, d);
10414887Schin 		fp->encode.prefix = n;
10424887Schin 		sfputr(fp->fp, (char*)s, 0);
10434887Schin 		break;
10444887Schin 	}
10454887Schin 	memcpy(fp->encode.path, path, len);
10464887Schin 	return 0;
10474887Schin }
10484887Schin 
10494887Schin /*
10504887Schin  * findsync() helper
10514887Schin  */
10524887Schin 
10534887Schin static int
finddone(register Find_t * fp)10544887Schin finddone(register Find_t* fp)
10554887Schin {
10564887Schin 	int	r;
10574887Schin 
10584887Schin 	if (sfsync(fp->fp))
10594887Schin 	{
10604887Schin 		if (fp->disc->errorf)
10614887Schin 			(*fp->disc->errorf)(fp, fp->disc, 2, "%s: write error [sfsync]", fp->encode.file);
10624887Schin 		return -1;
10634887Schin 	}
10644887Schin 	if (sferror(fp->fp))
10654887Schin 	{
10664887Schin 		if (fp->disc->errorf)
10674887Schin 			(*fp->disc->errorf)(fp, fp->disc, 2, "%s: write error [sferror]", fp->encode.file);
10684887Schin 		return -1;
10694887Schin 	}
10704887Schin 	r = sfclose(fp->fp);
10714887Schin 	fp->fp = 0;
10724887Schin 	if (r)
10734887Schin 	{
10744887Schin 		if (fp->disc->errorf)
10754887Schin 			(*fp->disc->errorf)(fp, fp->disc, 2, "%s: write error [sfclose]", fp->encode.file);
10764887Schin 		return -1;
10774887Schin 	}
10784887Schin 	return 0;
10794887Schin }
10804887Schin 
10814887Schin /*
10824887Schin  * finish the code table
10834887Schin  */
10844887Schin 
10854887Schin static int
findsync(register Find_t * fp)10864887Schin findsync(register Find_t* fp)
10874887Schin {
10884887Schin 	register char*		s;
10894887Schin 	register int		n;
10904887Schin 	register int		m;
10914887Schin 	register int		d;
10924887Schin 	register Type_t*	x;
10934887Schin 	char*			t;
10944887Schin 	int			b;
10954887Schin 	long			z;
10964887Schin 	Sfio_t*			sp;
10974887Schin 
10984887Schin 	switch (fp->method)
10994887Schin 	{
11004887Schin 	case FF_dir:
11014887Schin 	case FF_gnu:
11024887Schin 		/*
11034887Schin 		 * replace the real file with the temp file
11044887Schin 		 */
11054887Schin 
11064887Schin 		if (finddone(fp))
11074887Schin 			goto bad;
11084887Schin 		remove(fp->encode.file);
11094887Schin 		if (rename(fp->encode.temp, fp->encode.file))
11104887Schin 		{
11114887Schin 			if (fp->disc->errorf)
11124887Schin 				(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "%s: cannot rename from tmp file %s", fp->encode.file, fp->encode.temp);
11134887Schin 			remove(fp->encode.temp);
11144887Schin 			return -1;
11154887Schin 		}
11164887Schin 		break;
11174887Schin 	case FF_old:
11184887Schin 		/*
11194887Schin 		 * determine the top FF_MAX bigrams
11204887Schin 		 */
11214887Schin 
11224887Schin 		for (n = 0; n < FF_MAX; n++)
11234887Schin 			for (m = 0; m < FF_MAX; m++)
11244887Schin 				fp->encode.hits[fp->encode.code[n][m]]++;
11254887Schin 		fp->encode.hits[0] = 0;
11264887Schin 		m = 1;
11274887Schin 		for (n = USHRT_MAX; n >= 0; n--)
11284887Schin 			if (d = fp->encode.hits[n])
11294887Schin 			{
11304887Schin 				fp->encode.hits[n] = m;
11314887Schin 				if ((m += d) > FF_MAX)
11324887Schin 					break;
11334887Schin 			}
11344887Schin 		while (--n >= 0)
11354887Schin 			fp->encode.hits[n] = 0;
11364887Schin 		for (n = FF_MAX - 1; n >= 0; n--)
11374887Schin 			for (m = FF_MAX - 1; m >= 0; m--)
11384887Schin 				if (fp->encode.hits[fp->encode.code[n][m]])
11394887Schin 				{
11404887Schin 					d = fp->encode.code[n][m];
11414887Schin 					b = fp->encode.hits[d] - 1;
11424887Schin 					fp->encode.code[n][m] = b + FF_MAX;
11434887Schin 					if (fp->encode.hits[d]++ >= FF_MAX)
11444887Schin 						fp->encode.hits[d] = 0;
11454887Schin 					fp->encode.bigram[b *= 2] = n;
11464887Schin 					fp->encode.bigram[b + 1] = m;
11474887Schin 				}
11484887Schin 				else
11494887Schin 					fp->encode.code[n][m] = 0;
11504887Schin 
11514887Schin 		/*
11524887Schin 		 * commit the real file
11534887Schin 		 */
11544887Schin 
11554887Schin 		if (sfseek(fp->fp, (Sfoff_t)0, SEEK_SET))
11564887Schin 		{
11574887Schin 			if (fp->disc->errorf)
11584887Schin 				(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "cannot rewind tmp file");
11594887Schin 			return -1;
11604887Schin 		}
11614887Schin 		if (!(sp = sfopen(NiL, fp->encode.file, "w")))
11624887Schin 			goto badcreate;
11634887Schin 
11644887Schin 		/*
11654887Schin 		 * dump the bigrams
11664887Schin 		 */
11674887Schin 
11684887Schin 		sfwrite(sp, fp->encode.bigram, sizeof(fp->encode.bigram));
11694887Schin 
11704887Schin 		/*
11714887Schin 		 * encode the massaged paths
11724887Schin 		 */
11734887Schin 
11744887Schin 		while (s = sfgetr(fp->fp, 0, 0))
11754887Schin 		{
11764887Schin 			z = strtol(s, &t, 0);
11774887Schin 			s = t;
11784887Schin 			if (z < 0 || z > 2 * FF_OFF)
11794887Schin 			{
11804887Schin 				sfputc(sp, FF_ESC);
11814887Schin 				sfputc(sp, (z >> 24));
11824887Schin 				sfputc(sp, (z >> 16));
11834887Schin 				sfputc(sp, (z >> 8));
11844887Schin 				sfputc(sp, z);
11854887Schin 			}
11864887Schin 			else
11874887Schin 				sfputc(sp, z);
11884887Schin 			while (n = *s++)
11894887Schin 			{
11904887Schin 				if (!(m = *s++))
11914887Schin 				{
11924887Schin 					sfputc(sp, n);
11934887Schin 					break;
11944887Schin 				}
11954887Schin 				if (d = fp->encode.code[n][m])
11964887Schin 					sfputc(sp, d);
11974887Schin 				else
11984887Schin 				{
11994887Schin 					sfputc(sp, n);
12004887Schin 					sfputc(sp, m);
12014887Schin 				}
12024887Schin 			}
12034887Schin 		}
12044887Schin 		sfclose(fp->fp);
12054887Schin 		fp->fp = sp;
12064887Schin 		if (finddone(fp))
12074887Schin 			goto bad;
12084887Schin 		break;
12094887Schin 	case FF_typ:
12104887Schin 		if (finddone(fp))
12114887Schin 			goto bad;
12124887Schin 		if (!(fp->fp = sfopen(NiL, fp->encode.temp, "r")))
12134887Schin 		{
12144887Schin 			if (fp->disc->errorf)
12154887Schin 				(*fp->disc->errorf)(fp, fp->disc, ERROR_SYSTEM|2, "%s: cannot read tmp file", fp->encode.temp);
12164887Schin 			remove(fp->encode.temp);
12174887Schin 			return -1;
12184887Schin 		}
12194887Schin 
12204887Schin 		/*
12214887Schin 		 * commit the output file
12224887Schin 		 */
12234887Schin 
12244887Schin 		if (!(sp = sfopen(NiL, fp->encode.file, "w")))
12254887Schin 			goto badcreate;
12264887Schin 
12274887Schin 		/*
12284887Schin 		 * write the header magic
12294887Schin 		 */
12304887Schin 
12314887Schin 		sfputc(sp, 0);
12324887Schin 		sfputr(sp, FF_typ_magic, 0);
12334887Schin 
12344887Schin 		/*
12354887Schin 		 * write the type table in index order starting with 1
12364887Schin 		 */
12374887Schin 
12384887Schin 		for (x = (Type_t*)dtfirst(fp->encode.indexdict); x; x = (Type_t*)dtnext(fp->encode.indexdict, x))
12394887Schin 			sfputr(sp, x->name, 0);
12404887Schin 		sfputc(sp, 0);
12414887Schin 
12424887Schin 		/*
12434887Schin 		 * append the front compressed strings
12444887Schin 		 */
12454887Schin 
12464887Schin 		if (sfmove(fp->fp, sp, SF_UNBOUND, -1) < 0 || !sfeof(fp->fp))
12474887Schin 		{
12484887Schin 			sfclose(sp);
12494887Schin 			if (fp->disc->errorf)
12504887Schin 				(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot append codes", fp->encode.file);
12514887Schin 			goto bad;
12524887Schin 		}
12534887Schin 		sfclose(fp->fp);
12544887Schin 		fp->fp = sp;
12554887Schin 		if (finddone(fp))
12564887Schin 			goto bad;
12574887Schin 		remove(fp->encode.temp);
12584887Schin 		break;
12594887Schin 	}
12604887Schin 	return 0;
12614887Schin  badcreate:
12624887Schin 	if (fp->disc->errorf)
12634887Schin 		(*fp->disc->errorf)(fp, fp->disc, 2, "%s: cannot write codes", fp->encode.file);
12644887Schin  bad:
12654887Schin 	if (fp->fp)
12664887Schin 	{
12674887Schin 		sfclose(fp->fp);
12684887Schin 		fp->fp = 0;
12694887Schin 	}
12704887Schin 	remove(fp->encode.temp);
12714887Schin 	return -1;
12724887Schin }
12734887Schin 
12744887Schin /*
12754887Schin  * close an open fastfind stream
12764887Schin  */
12774887Schin 
12784887Schin int
findclose(register Find_t * fp)12794887Schin findclose(register Find_t* fp)
12804887Schin {
12814887Schin 	int	n = 0;
12824887Schin 
12834887Schin 	if (!fp)
12844887Schin 		return -1;
12854887Schin 	if (fp->generate)
12864887Schin 	{
12874887Schin 		n = findsync(fp);
12884887Schin 		if (fp->encode.indexdict)
12894887Schin 			dtclose(fp->encode.indexdict);
12904887Schin 		if (fp->encode.namedict)
12914887Schin 			dtclose(fp->encode.namedict);
12924887Schin 	}
12934887Schin 	else
12944887Schin 	{
12954887Schin 		if (fp->decode.match)
12964887Schin 			regfree(&fp->decode.re);
12974887Schin 		n = 0;
12984887Schin 	}
12994887Schin 	if (fp->fp)
13004887Schin 		sfclose(fp->fp);
13014887Schin 	vmclose(fp->vm);
13024887Schin 	return n;
13034887Schin }
1304