fastfind.c revision 18829 
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 * $Id: fastfind.c,v 1.1 1996/08/31 23:14:52 wosch Exp $
38 */
39
40
41#ifndef _LOCATE_STATISTIC_
42#define _LOCATE_STATISTIC_
43
44void
45statistic (fp, path_fcodes)
46	FILE *fp;               /* open database */
47	char *path_fcodes;  	/* for error message */
48{
49	register int lines, chars, size, big;
50	register u_char *p, *s;
51	register int c;
52	int count;
53	u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
54
55	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++) {
56		p[c] = check_bigram_char(getc(fp));
57		s[c] = check_bigram_char(getc(fp));
58	}
59
60	lines = chars = big = 0;
61	size = NBG + NBG;
62
63	for (c = getc(fp), count = 0; c != EOF; size++) {
64		if (c == SWITCH) {
65			count += getwf(fp) - OFFSET;
66			size += sizeof(int);
67		} else
68			count += c - OFFSET;
69
70		for (p = path + count; (c = getc(fp)) > SWITCH; size++)
71			if (c < PARITY)
72				p++;
73			else {
74				big++;
75				p += 2;
76			}
77
78		p++;
79		lines++;
80		chars += (p - path);
81	}
82
83	(void)printf("\nDatabase: %s\n", path_fcodes);
84	(void)printf("Compression: Front: %2.2f%%, ",
85		     (float)(100 * (size + big)) / chars);
86	(void)printf("Bigram: %2.2f%%, ", (float)(100 * (size - big)) / size);
87	(void)printf("Total: %2.2f%%\n", (float)(100 * size) / chars);
88	(void)printf("Filenames: %d, ", lines);
89	(void)printf("Chars: %d\n", chars);
90	(void)printf("Database size: %d, ", size);
91	(void)printf("Bigram chars: %d\n", big);
92
93}
94#endif /* _LOCATE_STATISTIC_ */
95
96
97void
98#ifdef FF_MMAP
99
100
101#ifdef FF_ICASE
102fastfind_mmap_icase
103#else
104fastfind_mmap
105#endif
106(pathpart, paddr, len, database)
107	char *pathpart; 	/* search string */
108	caddr_t paddr;  	/* mmap pointer */
109	int len;        	/* length of database */
110	char *database; 	/* for error message */
111
112
113#else /* MMAP */
114
115
116#ifdef FF_ICASE
117fastfind_icase
118#else /* !FF_ICASE */
119fastfind
120#endif /* FF_ICASE */
121
122(fp, pathpart, database)
123	FILE *fp;               /* open database */
124	char *pathpart;		/* search string */
125	char *database;		/* for error message */
126
127
128#endif /* MMAP */
129
130{
131	register u_char *p, *s, *patend, *q, *foundchar;
132	register int c, cc;
133	int count, found, globflag;
134	u_char *cutoff;
135	u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
136
137#ifdef FF_ICASE
138	/* use a lookup table for case insensitive search */
139	u_char table[UCHAR_MAX];
140
141	tolower_word(pathpart);
142#endif
143
144	/* init bigram table */
145#ifdef FF_MMAP
146	if (len < (2*NBG)) {
147		(void)fprintf(stderr, "database to small: %s\n", database);
148		exit(1);
149	}
150
151	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++, len-= 2) {
152		p[c] = check_bigram_char(*paddr++);
153		s[c] = check_bigram_char(*paddr++);
154	}
155#else
156	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++) {
157		p[c] = check_bigram_char(getc(fp));
158		s[c] = check_bigram_char(getc(fp));
159	}
160#endif
161
162	/* find optimal (last) char for searching */
163	for (p = pathpart; *p != '\0'; p++)
164		if (index(LOCATE_REG, *p) != NULL)
165			break;
166
167	if (*p == '\0')
168		globflag = 0;
169	else
170		globflag = 1;
171
172	p = pathpart;
173	patend = patprep(p);
174	cc = *patend;
175
176#ifdef FF_ICASE
177	/* set patend char to true */
178	table[TOLOWER(*patend)] = 1;
179	table[toupper(*patend)] = 1;
180#endif
181
182
183	/* main loop */
184	found = count = 0;
185	foundchar = 0;
186
187#ifdef FF_MMAP
188	for (c = (u_char)*paddr++; len-- > 0; ) {
189#else
190	for (c = getc(fp); c != EOF; ) {
191#endif
192
193		/* go forward or backward */
194		if (c == SWITCH) { /* big step, an integer */
195#ifdef FF_MMAP
196			count += getwm(paddr) - OFFSET;
197			len -= INTSIZE; paddr += INTSIZE;
198#else
199			count +=  getwf(fp) - OFFSET;
200#endif
201		} else {	   /* slow step, =< 14 chars */
202			count += c - OFFSET;
203		}
204
205		/* overlay old path */
206		p = path + count;
207		foundchar = p - 1;
208#ifdef FF_MMAP
209		for (; (c = (u_char)*paddr++) > SWITCH; len--)
210#else
211		for (; (c = getc(fp)) > SWITCH; )
212#endif
213
214			if (c < PARITY) {
215#ifdef FF_ICASE
216				if (table[c])
217#else
218				if (c == cc)
219#endif
220					foundchar = p;
221				*p++ = c;
222			}
223			else {
224				/* bigrams are parity-marked */
225				TO7BIT(c);
226
227#ifndef FF_ICASE
228				if (bigram1[c] == cc ||
229				    bigram2[c] == cc)
230#else
231
232					if (table[bigram1[c]] ||
233					    table[bigram2[c]])
234#endif
235						foundchar = p + 1;
236
237				*p++ = bigram1[c];
238				*p++ = bigram2[c];
239			}
240
241
242		if (found) {                     /* previous line matched */
243			cutoff = path;
244			*p-- = '\0';
245			foundchar = p;
246		} else if (foundchar >= path + count) { /* a char matched */
247			*p-- = '\0';
248			cutoff = path + count;
249		} else                           /* nothing to do */
250			continue;
251
252		found = 0;
253		for (s = foundchar; s >= cutoff; s--) {
254			if (*s == cc
255#ifdef FF_ICASE
256			    || TOLOWER(*s) == cc
257#endif
258			    ) {	/* fast first char check */
259				for (p = patend - 1, q = s - 1; *p != '\0';
260				     p--, q--)
261					if (*q != *p
262#ifdef FF_ICASE
263					    && TOLOWER(*q) != *p
264#endif
265					    )
266						break;
267				if (*p == '\0') {   /* fast match success */
268					found = 1;
269					if (!globflag || !fnmatch(pathpart, path, 0)) {
270						if (f_silent)
271							counter++;
272						else if (f_limit) {
273							counter++;
274							if (f_limit >= counter)
275								(void)puts(path);
276							else  {
277								(void)fprintf(stderr, "[show only %d lines]\n", counter - 1);
278								exit(0);
279							}
280						} else
281							(void)puts(path);
282					}
283					break;
284				}
285			}
286		}
287	}
288}
289