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