xref: /freebsd/usr.bin/locate/locate/fastfind.c (revision 380a989b3223d455375b4fae70fd0b9bdd43bafb)
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.10 1997/07/21 12:08:13 charnier Exp $
38  */
39 
40 
41 #ifndef _LOCATE_STATISTIC_
42 #define _LOCATE_STATISTIC_
43 
44 void
45 statistic (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 
106 
107 void
108 #ifdef FF_MMAP
109 
110 
111 #ifdef FF_ICASE
112 fastfind_mmap_icase
113 #else
114 fastfind_mmap
115 #endif /* FF_ICASE */
116 (pathpart, paddr, len, database)
117 	char *pathpart; 	/* search string */
118 	caddr_t paddr;  	/* mmap pointer */
119 	int len;        	/* length of database */
120 	char *database; 	/* for error message */
121 
122 
123 #else /* MMAP */
124 
125 
126 #ifdef FF_ICASE
127 fastfind_icase
128 #else
129 fastfind
130 #endif /* FF_ICASE */
131 
132 (fp, pathpart, database)
133 	FILE *fp;               /* open database */
134 	char *pathpart;		/* search string */
135 	char *database;		/* for error message */
136 
137 
138 #endif /* MMAP */
139 
140 {
141 	register u_char *p, *s, *patend, *q, *foundchar;
142 	register int c, cc;
143 	int count, found, globflag;
144 	u_char *cutoff;
145 	u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
146 
147 #ifdef FF_ICASE
148 	/* use a lookup table for case insensitive search */
149 	u_char table[UCHAR_MAX + 1];
150 
151 	tolower_word(pathpart);
152 #endif /* FF_ICASE*/
153 
154 	/* init bigram table */
155 #ifdef FF_MMAP
156 	if (len < (2*NBG))
157 		errx(1, "database too small: %s", database);
158 
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 (index(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 		/* overlay old path */
219 		p = path + count;
220 		foundchar = p - 1;
221 
222 		for (;;) {
223 #ifdef FF_MMAP
224 			c = (u_char)*paddr++;
225 		        len--;
226 #else
227 			c = getc(fp);
228 #endif /* FF_MMAP */
229 			/*
230 			 * == UMLAUT: 8 bit char followed
231 			 * <= SWITCH: offset
232 			 * >= PARITY: bigram
233 			 * rest:      single ascii char
234 			 *
235 			 * offset < SWITCH < UMLAUT < ascii < PARITY < bigram
236 			 */
237 			if (c < PARITY) {
238 				if (c <= UMLAUT) {
239 					if (c == UMLAUT) {
240 #ifdef FF_MMAP
241 						c = (u_char)*paddr++;
242 						len--;
243 #else
244 						c = getc(fp);
245 #endif /* FF_MMAP */
246 
247 					} else
248 						break; /* SWITCH */
249 				}
250 #ifdef FF_ICASE
251 				if (table[c])
252 #else
253 				if (c == cc)
254 #endif /* FF_ICASE */
255 					foundchar = p;
256 				*p++ = c;
257 			}
258 			else {
259 				/* bigrams are parity-marked */
260 				TO7BIT(c);
261 
262 #ifndef FF_ICASE
263 				if (bigram1[c] == cc ||
264 				    bigram2[c] == cc)
265 #else
266 
267 					if (table[bigram1[c]] ||
268 					    table[bigram2[c]])
269 #endif /* FF_ICASE */
270 						foundchar = p + 1;
271 
272 				*p++ = bigram1[c];
273 				*p++ = bigram2[c];
274 			}
275 		}
276 
277 		if (found) {                     /* previous line matched */
278 			cutoff = path;
279 			*p-- = '\0';
280 			foundchar = p;
281 		} else if (foundchar >= path + count) { /* a char matched */
282 			*p-- = '\0';
283 			cutoff = path + count;
284 		} else                           /* nothing to do */
285 			continue;
286 
287 		found = 0;
288 		for (s = foundchar; s >= cutoff; s--) {
289 			if (*s == cc
290 #ifdef FF_ICASE
291 			    || TOLOWER(*s) == cc
292 #endif /* FF_ICASE */
293 			    ) {	/* fast first char check */
294 				for (p = patend - 1, q = s - 1; *p != '\0';
295 				     p--, q--)
296 					if (*q != *p
297 #ifdef FF_ICASE
298 					    && TOLOWER(*q) != *p
299 #endif /* FF_ICASE */
300 					    )
301 						break;
302 				if (*p == '\0') {   /* fast match success */
303 					found = 1;
304 					if (!globflag ||
305 #ifndef FF_ICASE
306 					    !fnmatch(pathpart, path, 0))
307 #else
308 					    !fnmatch(pathpart, path,
309 						     FNM_CASEFOLD))
310 #endif /* !FF_ICASE */
311 					{
312 						if (f_silent)
313 							counter++;
314 						else if (f_limit) {
315 							counter++;
316 							if (f_limit >= counter)
317 								(void)puts(path);
318 							else
319 								errx(0, "[show only %d lines]", counter - 1);
320 						} else
321 							(void)puts(path);
322 					}
323 					break;
324 				}
325 			}
326 		}
327 	}
328 }
329