[dragonfly.git] / usr.bin / locate / locate / fastfind.c

/*
 * Copyright (c) 1995 Wolfram Schneider <wosch@FreeBSD.org>. Berlin.
 * Copyright (c) 1989, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * James A. Woods.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * $FreeBSD: src/usr.bin/locate/locate/fastfind.c,v 1.12.2.1 2001/02/22 13:28:52 wosch Exp $
 */


#ifndef _LOCATE_STATISTIC_
#define _LOCATE_STATISTIC_

void 
statistic (FILE *fp, char *path_fcodes)
{
	int lines, chars, size, big, zwerg;
	u_char *p, *s;
	int c;
	int count, umlaut;
	u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];

	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++) {
		p[c] = check_bigram_char(getc(fp));
		s[c] = check_bigram_char(getc(fp));
	}

	lines = chars = big = zwerg = umlaut = 0;
	size = NBG + NBG;

	for (c = getc(fp), count = 0; c != EOF; size++) {
		if (c == SWITCH) {
			count += getwf(fp) - OFFSET;
			size += sizeof(int);
			zwerg++;
		} else
			count += c - OFFSET;
		
		for (p = path + count; (c = getc(fp)) > SWITCH; size++)
			if (c < PARITY) {
				if (c == UMLAUT) {
					c = getc(fp);
					size++;
					umlaut++;
				}
				p++;
			} else {
				/* bigram char */
				big++;
				p += 2;
			}

		p++;
		lines++;
		chars += (p - path);
	}

	(void)printf("\nDatabase: %s\n", path_fcodes);
	(void)printf("Compression: Front: %2.2f%%, ",
		     (size + big - (2 * NBG)) / (chars / (float)100));
	(void)printf("Bigram: %2.2f%%, ", (size - big) / (size / (float)100));
	(void)printf("Total: %2.2f%%\n", 
		     (size - (2 * NBG)) / (chars / (float)100));
	(void)printf("Filenames: %d, ", lines);
	(void)printf("Characters: %d, ", chars);
	(void)printf("Database size: %d\n", size);
	(void)printf("Bigram characters: %d, ", big);
	(void)printf("Integers: %d, ", zwerg);
	(void)printf("8-Bit characters: %d\n", umlaut);

}
#endif /* _LOCATE_STATISTIC_ */


void
#ifdef FF_MMAP


#ifdef FF_ICASE
fastfind_mmap_icase
#else
fastfind_mmap
#endif /* FF_ICASE */
(char *pathpart, caddr_t paddr, int len, char *database)


#else /* MMAP */


#ifdef FF_ICASE
fastfind_icase
#else
fastfind
#endif /* FF_ICASE */

(FILE *fp, char *pathpart, char *database)


#endif /* MMAP */

{
	u_char *p, *s, *patend, *q, *foundchar;
	int c, cc;
	int count, found, globflag;
	u_char *cutoff;
	u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];

#ifdef FF_ICASE
	/* use a lookup table for case insensitive search */
	u_char table[UCHAR_MAX + 1];

	tolower_word(pathpart);
#endif /* FF_ICASE*/

	/* init bigram table */
#ifdef FF_MMAP
	if (len < (2*NBG))
		errx(1, "database too small: %s", database);
	
	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++, len-= 2) {
		p[c] = check_bigram_char(*paddr++);
		s[c] = check_bigram_char(*paddr++);
	}
#else
	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++) {
		p[c] = check_bigram_char(getc(fp));
		s[c] = check_bigram_char(getc(fp));
	}
#endif /* FF_MMAP */

	/* find optimal (last) char for searching */
	for (p = pathpart; *p != '\0'; p++)
		if (index(LOCATE_REG, *p) != NULL)
			break;

	if (*p == '\0')
		globflag = 0;
	else
		globflag = 1;

	p = pathpart;
	patend = patprep(p);
	cc = *patend;

#ifdef FF_ICASE
	/* set patend char to true */
        for (c = 0; c < UCHAR_MAX + 1; c++)
                table[c] = 0;

	table[TOLOWER(*patend)] = 1;
	table[toupper(*patend)] = 1;
#endif /* FF_ICASE */


	/* main loop */
	found = count = 0;
	foundchar = 0;

#ifdef FF_MMAP
	c = (u_char)*paddr++; len--;
	for (; len > 0; ) {
#else
	c = getc(fp);
	for (; c != EOF; ) {
#endif /* FF_MMAP */

		/* go forward or backward */
		if (c == SWITCH) { /* big step, an integer */
#ifdef FF_MMAP
			count += getwm(paddr) - OFFSET;
			len -= INTSIZE; paddr += INTSIZE;
#else
			count +=  getwf(fp) - OFFSET;
#endif /* FF_MMAP */
		} else {	   /* slow step, =< 14 chars */
			count += c - OFFSET;
		}

		/* overlay old path */
		p = path + count;
		foundchar = p - 1;

#ifdef FF_MMAP
		for (; len > 0;) {
			c = (u_char)*paddr++; 
		        len--;
#else
		for (;;) {
			c = getc(fp);
#endif /* FF_MMAP */
			/*
			 * == UMLAUT: 8 bit char followed
			 * <= SWITCH: offset
			 * >= PARITY: bigram
			 * rest:      single ascii char
			 *
			 * offset < SWITCH < UMLAUT < ascii < PARITY < bigram
			 */
			if (c < PARITY) {
				if (c <= UMLAUT) {
					if (c == UMLAUT) {
#ifdef FF_MMAP
						c = (u_char)*paddr++;
						len--;
#else
						c = getc(fp);
#endif /* FF_MMAP */
						
					} else
						break; /* SWITCH */
				}
#ifdef FF_ICASE
				if (table[c])
#else
				if (c == cc)
#endif /* FF_ICASE */
					foundchar = p;
				*p++ = c;
			}
			else {		
				/* bigrams are parity-marked */
				TO7BIT(c);

#ifndef FF_ICASE
				if (bigram1[c] == cc ||
				    bigram2[c] == cc)
#else

					if (table[bigram1[c]] ||
					    table[bigram2[c]])
#endif /* FF_ICASE */
						foundchar = p + 1;

				*p++ = bigram1[c];
				*p++ = bigram2[c];
			}
		}
		
		if (found) {                     /* previous line matched */
			cutoff = path;
			*p-- = '\0';
			foundchar = p;
		} else if (foundchar >= path + count) { /* a char matched */
			*p-- = '\0';
			cutoff = path + count;
		} else                           /* nothing to do */
			continue;

		found = 0;
		for (s = foundchar; s >= cutoff; s--) {
			if (*s == cc
#ifdef FF_ICASE
			    || TOLOWER(*s) == cc
#endif /* FF_ICASE */
			    ) {	/* fast first char check */
				for (p = patend - 1, q = s - 1; *p != '\0';
				     p--, q--)
					if (*q != *p
#ifdef FF_ICASE
					    && TOLOWER(*q) != *p
#endif /* FF_ICASE */
					    )
						break;
				if (*p == '\0') {   /* fast match success */
					found = 1;
					if (!globflag || 
#ifndef FF_ICASE
					    !fnmatch(pathpart, path, 0)) 
#else 
					    !fnmatch(pathpart, path, 
						     FNM_CASEFOLD))
#endif /* !FF_ICASE */						
					{
						if (f_silent)
							counter++;
						else if (f_limit) {
							counter++;
							if (f_limit >= counter)
								(void)puts(path);
							else 
								errx(0, "[show only %d lines]", counter - 1);
						} else
							(void)puts(path);
					}
					break;
				}
			}
		}
	}
}
Commit	Line	Data
984263bc MD	1	/*
	2	* Copyright (c) 1995 Wolfram Schneider <wosch@FreeBSD.org>. Berlin.
	3	* Copyright (c) 1989, 1993
	4	* The Regents of the University of California. All rights reserved.
	5	*
	6	* This code is derived from software contributed to Berkeley by
	7	* James A. Woods.
	8	*
	9	* Redistribution and use in source and binary forms, with or without
	10	* modification, are permitted provided that the following conditions
	11	* are met:
	12	* 1. Redistributions of source code must retain the above copyright
	13	* notice, this list of conditions and the following disclaimer.
	14	* 2. Redistributions in binary form must reproduce the above copyright
	15	* notice, this list of conditions and the following disclaimer in the
	16	* documentation and/or other materials provided with the distribution.
	17	* 3. All advertising materials mentioning features or use of this software
	18	* must display the following acknowledgement:
	19	* This product includes software developed by the University of
	20	* California, Berkeley and its contributors.
	21	* 4. Neither the name of the University nor the names of its contributors
	22	* may be used to endorse or promote products derived from this software
	23	* without specific prior written permission.
	24	*
	25	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	26	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	27	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	28	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	29	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	30	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	31	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	32	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	33	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	34	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	35	* SUCH DAMAGE.
	36	*
	37	* $FreeBSD: src/usr.bin/locate/locate/fastfind.c,v 1.12.2.1 2001/02/22 13:28:52 wosch Exp $
	38	*/
	39
	40
	41	#ifndef _LOCATE_STATISTIC_
	42	#define _LOCATE_STATISTIC_
	43
	44	void
89a89091	45	statistic (FILE fp, char path_fcodes)
984263bc	46	{
6bd457ed DR	47	int lines, chars, size, big, zwerg;
	48	u_char p, s;
	49	int c;
984263bc MD	50	int count, umlaut;
	51	u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
	52
	53	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++) {
	54	p[c] = check_bigram_char(getc(fp));
	55	s[c] = check_bigram_char(getc(fp));
	56	}
	57
	58	lines = chars = big = zwerg = umlaut = 0;
	59	size = NBG + NBG;
	60
	61	for (c = getc(fp), count = 0; c != EOF; size++) {
	62	if (c == SWITCH) {
	63	count += getwf(fp) - OFFSET;
	64	size += sizeof(int);
	65	zwerg++;
	66	} else
	67	count += c - OFFSET;
	68
	69	for (p = path + count; (c = getc(fp)) > SWITCH; size++)
	70	if (c < PARITY) {
	71	if (c == UMLAUT) {
	72	c = getc(fp);
	73	size++;
	74	umlaut++;
	75	}
	76	p++;
	77	} else {
	78	/* bigram char */
	79	big++;
	80	p += 2;
	81	}
	82
	83	p++;
	84	lines++;
	85	chars += (p - path);
	86	}
	87
	88	(void)printf("\nDatabase: %s\n", path_fcodes);
	89	(void)printf("Compression: Front: %2.2f%%, ",
	90	(size + big - (2 * NBG)) / (chars / (float)100));
	91	(void)printf("Bigram: %2.2f%%, ", (size - big) / (size / (float)100));
	92	(void)printf("Total: %2.2f%%\n",
	93	(size - (2 * NBG)) / (chars / (float)100));
	94	(void)printf("Filenames: %d, ", lines);
	95	(void)printf("Characters: %d, ", chars);
	96	(void)printf("Database size: %d\n", size);
	97	(void)printf("Bigram characters: %d, ", big);
	98	(void)printf("Integers: %d, ", zwerg);
	99	(void)printf("8-Bit characters: %d\n", umlaut);
	100
	101	}
	102	#endif /* _LOCATE_STATISTIC_ */
	103
	104
	105	void
	106	#ifdef FF_MMAP
	107
	108
	109	#ifdef FF_ICASE
	110	fastfind_mmap_icase
	111	#else
	112	fastfind_mmap
	113	#endif /* FF_ICASE */
89a89091	114	(char pathpart, caddr_t paddr, int len, char database)
984263bc MD	115
	116
	117	#else /* MMAP */
	118
	119
	120	#ifdef FF_ICASE
	121	fastfind_icase
	122	#else
	123	fastfind
	124	#endif /* FF_ICASE */
	125
89a89091	126	(FILE fp, char pathpart, char *database)
984263bc MD	127
	128
	129	#endif /* MMAP */
	130
	131	{
6bd457ed DR	132	u_char p, s, patend, q, *foundchar;
6bd457ed DR	133	int c, cc;
984263bc MD	134	int count, found, globflag;
	135	u_char *cutoff;
	136	u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
	137
	138	#ifdef FF_ICASE
	139	/* use a lookup table for case insensitive search */
	140	u_char table[UCHAR_MAX + 1];
	141
	142	tolower_word(pathpart);
	143	#endif /* FF_ICASE*/
	144
	145	/* init bigram table */
	146	#ifdef FF_MMAP
	147	if (len < (2*NBG))
	148	errx(1, "database too small: %s", database);
	149
	150	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++, len-= 2) {
	151	p[c] = check_bigram_char(*paddr++);
	152	s[c] = check_bigram_char(*paddr++);
	153	}
	154	#else
	155	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++) {
	156	p[c] = check_bigram_char(getc(fp));
	157	s[c] = check_bigram_char(getc(fp));
	158	}
	159	#endif /* FF_MMAP */
	160
	161	/* find optimal (last) char for searching */
	162	for (p = pathpart; *p != '\0'; p++)
	163	if (index(LOCATE_REG, *p) != NULL)
	164	break;
	165
	166	if (*p == '\0')
	167	globflag = 0;
	168	else
	169	globflag = 1;
	170
	171	p = pathpart;
	172	patend = patprep(p);
	173	cc = *patend;
	174
	175	#ifdef FF_ICASE
	176	/* set patend char to true */
	177	for (c = 0; c < UCHAR_MAX + 1; c++)
	178	table[c] = 0;
	179
	180	table[TOLOWER(*patend)] = 1;
	181	table[toupper(*patend)] = 1;
	182	#endif /* FF_ICASE */
	183
	184
	185	/* main loop */
	186	found = count = 0;
	187	foundchar = 0;
	188
	189	#ifdef FF_MMAP
	190	c = (u_char)*paddr++; len--;
	191	for (; len > 0; ) {
	192	#else
	193	c = getc(fp);
	194	for (; c != EOF; ) {
	195	#endif /* FF_MMAP */
	196
	197	/* go forward or backward */
198	if (c == SWITCH) { /* big step, an integer */
199	#ifdef FF_MMAP
200	count += getwm(paddr) - OFFSET;
201	len -= INTSIZE; paddr += INTSIZE;
202	#else
203	count += getwf(fp) - OFFSET;
204	#endif /* FF_MMAP */
205	} else { /* slow step, =< 14 chars */
206	count += c - OFFSET;
207	}
208
209	/* overlay old path */
210	p = path + count;
211	foundchar = p - 1;
212
213	#ifdef FF_MMAP
214	for (; len > 0;) {
215	c = (u_char)*paddr++;
216	len--;
217	#else
218	for (;;) {
219	c = getc(fp);
220	#endif /* FF_MMAP */
221	/*
222	* == UMLAUT: 8 bit char followed
223	* <= SWITCH: offset
224	* >= PARITY: bigram
225	* rest: single ascii char
226	*
227	* offset < SWITCH < UMLAUT < ascii < PARITY < bigram
228	*/
229	if (c < PARITY) {
230	if (c <= UMLAUT) {
231	if (c == UMLAUT) {
232	#ifdef FF_MMAP
233	c = (u_char)*paddr++;
234	len--;
235	#else
236	c = getc(fp);
237	#endif /* FF_MMAP */
238
239	} else
240	break; /* SWITCH */
241	}
242	#ifdef FF_ICASE
243	if (table[c])
244	#else
245	if (c == cc)
246	#endif /* FF_ICASE */
247	foundchar = p;
248	*p++ = c;
249	}
250	else {
251	/* bigrams are parity-marked */
252	TO7BIT(c);
253
254	#ifndef FF_ICASE
255	if (bigram1[c] == cc \|\|
256	bigram2[c] == cc)
257	#else
258
259	if (table[bigram1[c]] \|\|
260	table[bigram2[c]])
261	#endif /* FF_ICASE */
262	foundchar = p + 1;
263
264	*p++ = bigram1[c];
265	*p++ = bigram2[c];
266	}
267	}
268
269	if (found) { /* previous line matched */
270	cutoff = path;
271	*p-- = '\0';
272	foundchar = p;
273	} else if (foundchar >= path + count) { /* a char matched */
274	*p-- = '\0';
275	cutoff = path + count;
276	} else /* nothing to do */
277	continue;
278
279	found = 0;
280	for (s = foundchar; s >= cutoff; s--) {
281	if (*s == cc
282	#ifdef FF_ICASE
283	\|\| TOLOWER(*s) == cc
284	#endif /* FF_ICASE */
285	) { /* fast first char check */
286	for (p = patend - 1, q = s - 1; *p != '\0';
287	p--, q--)
288	if (q != p
289	#ifdef FF_ICASE
290	&& TOLOWER(q) != p
291	#endif /* FF_ICASE */
292	)
293	break;
294	if (p == '\0') { / fast match success */
295	found = 1;
296	if (!globflag \|\|
297	#ifndef FF_ICASE
298	!fnmatch(pathpart, path, 0))
299	#else
300	!fnmatch(pathpart, path,
301	FNM_CASEFOLD))
302	#endif /* !FF_ICASE */
303	{
304	if (f_silent)
305	counter++;
306	else if (f_limit) {
307	counter++;
308	if (f_limit >= counter)
309	(void)puts(path);
310	else
311	errx(0, "[show only %d lines]", counter - 1);
312	} else
313	(void)puts(path);
314	}
315	break;
316	}
317	}
318	}
319	}
320	}