fastfind.c revision 190656 
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: head/usr.bin/locate/locate/fastfind.c 190656 2009-04-02 21:23:04Z delphij $
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, zwerg;
50	register u_char *p, *s;
51	register int c;
52	int count, umlaut;
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 = zwerg = umlaut = 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			zwerg++;
68		} else
69			count += c - OFFSET;
70
71		for (p = path + count; (c = getc(fp)) > SWITCH; size++)
72			if (c < PARITY) {
73				if (c == UMLAUT) {
74					c = getc(fp);
75					size++;
76					umlaut++;
77				}
78				p++;
79			} else {
80				/* bigram char */
81				big++;
82				p += 2;
83			}
84
85		p++;
86		lines++;
87		chars += (p - path);
88	}
89
90	(void)printf("\nDatabase: %s\n", path_fcodes);
91	(void)printf("Compression: Front: %2.2f%%, ",
92		     (size + big - (2 * NBG)) / (chars / (float)100));
93	(void)printf("Bigram: %2.2f%%, ", (size - big) / (size / (float)100));
94	(void)printf("Total: %2.2f%%\n",
95		     (size - (2 * NBG)) / (chars / (float)100));
96	(void)printf("Filenames: %d, ", lines);
97	(void)printf("Characters: %d, ", chars);
98	(void)printf("Database size: %d\n", size);
99	(void)printf("Bigram characters: %d, ", big);
100	(void)printf("Integers: %d, ", zwerg);
101	(void)printf("8-Bit characters: %d\n", umlaut);
102
103}
104#endif /* _LOCATE_STATISTIC_ */
105
106extern	char	separator;
107
108void
109#ifdef FF_MMAP
110
111
112#ifdef FF_ICASE
113fastfind_mmap_icase
114#else
115fastfind_mmap
116#endif /* FF_ICASE */
117(pathpart, paddr, len, database)
118	char *pathpart; 	/* search string */
119	caddr_t paddr;  	/* mmap pointer */
120	int len;        	/* length of database */
121	char *database; 	/* for error message */
122
123
124#else /* MMAP */
125
126
127#ifdef FF_ICASE
128fastfind_icase
129#else
130fastfind
131#endif /* FF_ICASE */
132
133(fp, pathpart, database)
134	FILE *fp;               /* open database */
135	char *pathpart;		/* search string */
136	char *database;		/* for error message */
137
138
139#endif /* MMAP */
140
141{
142	register u_char *p, *s, *patend, *q, *foundchar;
143	register int c, cc;
144	int count, found, globflag;
145	u_char *cutoff;
146	u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
147
148#ifdef FF_ICASE
149	/* use a lookup table for case insensitive search */
150	u_char table[UCHAR_MAX + 1];
151
152	tolower_word(pathpart);
153#endif /* FF_ICASE*/
154
155	/* init bigram table */
156#ifdef FF_MMAP
157	if (len < (2*NBG))
158		errx(1, "database too small: %s", database);
159
160	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++, len-= 2) {
161		p[c] = check_bigram_char(*paddr++);
162		s[c] = check_bigram_char(*paddr++);
163	}
164#else
165	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++) {
166		p[c] = check_bigram_char(getc(fp));
167		s[c] = check_bigram_char(getc(fp));
168	}
169#endif /* FF_MMAP */
170
171	/* find optimal (last) char for searching */
172	for (p = pathpart; *p != '\0'; p++)
173		if (index(LOCATE_REG, *p) != NULL)
174			break;
175
176	if (*p == '\0')
177		globflag = 0;
178	else
179		globflag = 1;
180
181	p = pathpart;
182	patend = patprep(p);
183	cc = *patend;
184
185#ifdef FF_ICASE
186	/* set patend char to true */
187        for (c = 0; c < UCHAR_MAX + 1; c++)
188                table[c] = 0;
189
190	table[TOLOWER(*patend)] = 1;
191	table[toupper(*patend)] = 1;
192#endif /* FF_ICASE */
193
194
195	/* main loop */
196	found = count = 0;
197	foundchar = 0;
198
199#ifdef FF_MMAP
200	c = (u_char)*paddr++; len--;
201	for (; len > 0; ) {
202#else
203	c = getc(fp);
204	for (; c != EOF; ) {
205#endif /* FF_MMAP */
206
207		/* go forward or backward */
208		if (c == SWITCH) { /* big step, an integer */
209#ifdef FF_MMAP
210			count += getwm(paddr) - OFFSET;
211			len -= INTSIZE; paddr += INTSIZE;
212#else
213			count +=  getwf(fp) - OFFSET;
214#endif /* FF_MMAP */
215		} else {	   /* slow step, =< 14 chars */
216			count += c - OFFSET;
217		}
218
219		if (count < 0 || count > MAXPATHLEN)
220			errx(1, "corrupted database: %s", database);
221		/* overlay old path */
222		p = path + count;
223		foundchar = p - 1;
224
225#ifdef FF_MMAP
226		for (; len > 0;) {
227			c = (u_char)*paddr++;
228		        len--;
229#else
230		for (;;) {
231			c = getc(fp);
232#endif /* FF_MMAP */
233			/*
234			 * == UMLAUT: 8 bit char followed
235			 * <= SWITCH: offset
236			 * >= PARITY: bigram
237			 * rest:      single ascii char
238			 *
239			 * offset < SWITCH < UMLAUT < ascii < PARITY < bigram
240			 */
241			if (c < PARITY) {
242				if (c <= UMLAUT) {
243					if (c == UMLAUT) {
244#ifdef FF_MMAP
245						c = (u_char)*paddr++;
246						len--;
247#else
248						c = getc(fp);
249#endif /* FF_MMAP */
250
251					} else
252						break; /* SWITCH */
253				}
254#ifdef FF_ICASE
255				if (table[c])
256#else
257				if (c == cc)
258#endif /* FF_ICASE */
259					foundchar = p;
260				*p++ = c;
261			}
262			else {
263				/* bigrams are parity-marked */
264				TO7BIT(c);
265
266#ifndef FF_ICASE
267				if (bigram1[c] == cc ||
268				    bigram2[c] == cc)
269#else
270
271					if (table[bigram1[c]] ||
272					    table[bigram2[c]])
273#endif /* FF_ICASE */
274						foundchar = p + 1;
275
276				*p++ = bigram1[c];
277				*p++ = bigram2[c];
278			}
279		}
280
281		if (found) {                     /* previous line matched */
282			cutoff = path;
283			*p-- = '\0';
284			foundchar = p;
285		} else if (foundchar >= path + count) { /* a char matched */
286			*p-- = '\0';
287			cutoff = path + count;
288		} else                           /* nothing to do */
289			continue;
290
291		found = 0;
292		for (s = foundchar; s >= cutoff; s--) {
293			if (*s == cc
294#ifdef FF_ICASE
295			    || TOLOWER(*s) == cc
296#endif /* FF_ICASE */
297			    ) {	/* fast first char check */
298				for (p = patend - 1, q = s - 1; *p != '\0';
299				     p--, q--)
300					if (*q != *p
301#ifdef FF_ICASE
302					    && TOLOWER(*q) != *p
303#endif /* FF_ICASE */
304					    )
305						break;
306				if (*p == '\0') {   /* fast match success */
307					found = 1;
308					if (!globflag ||
309#ifndef FF_ICASE
310					    !fnmatch(pathpart, path, 0))
311#else
312					    !fnmatch(pathpart, path,
313						     FNM_CASEFOLD))
314#endif /* !FF_ICASE */
315					{
316						if (f_silent)
317							counter++;
318						else if (f_limit) {
319							counter++;
320							if (f_limit >= counter)
321								(void)printf("%s%c",path,separator);
322							else
323								errx(0, "[show only %d lines]", counter - 1);
324						} else
325							(void)printf("%s%c",path,separator);
326					}
327					break;
328				}
329			}
330		}
331	}
332}
333