xref: /dragonfly/usr.bin/locate/locate/fastfind.c (revision 36a3d1d6) 
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  * $DragonFly: src/usr.bin/locate/locate/fastfind.c,v 1.3 2005/08/04 17:31:23 drhodus Exp $
39  */
40 
41 
42 #ifndef _LOCATE_STATISTIC_
43 #define _LOCATE_STATISTIC_
44 
45 void
46 statistic (fp, path_fcodes)
47 	FILE *fp;               /* open database */
48 	char *path_fcodes;  	/* for error message */
49 {
50 	int lines, chars, size, big, zwerg;
51 	u_char *p, *s;
52 	int c;
53 	int count, umlaut;
54 	u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
55 
56 	for (c = 0, p = bigram1, s = bigram2; c < NBG; c++) {
57 		p[c] = check_bigram_char(getc(fp));
58 		s[c] = check_bigram_char(getc(fp));
59 	}
60 
61 	lines = chars = big = zwerg = umlaut = 0;
62 	size = NBG + NBG;
63 
64 	for (c = getc(fp), count = 0; c != EOF; size++) {
65 		if (c == SWITCH) {
66 			count += getwf(fp) - OFFSET;
67 			size += sizeof(int);
68 			zwerg++;
69 		} else
70 			count += c - OFFSET;
71 
72 		for (p = path + count; (c = getc(fp)) > SWITCH; size++)
73 			if (c < PARITY) {
74 				if (c == UMLAUT) {
75 					c = getc(fp);
76 					size++;
77 					umlaut++;
78 				}
79 				p++;
80 			} else {
81 				/* bigram char */
82 				big++;
83 				p += 2;
84 			}
85 
86 		p++;
87 		lines++;
88 		chars += (p - path);
89 	}
90 
91 	(void)printf("\nDatabase: %s\n", path_fcodes);
92 	(void)printf("Compression: Front: %2.2f%%, ",
93 		     (size + big - (2 * NBG)) / (chars / (float)100));
94 	(void)printf("Bigram: %2.2f%%, ", (size - big) / (size / (float)100));
95 	(void)printf("Total: %2.2f%%\n",
96 		     (size - (2 * NBG)) / (chars / (float)100));
97 	(void)printf("Filenames: %d, ", lines);
98 	(void)printf("Characters: %d, ", chars);
99 	(void)printf("Database size: %d\n", size);
100 	(void)printf("Bigram characters: %d, ", big);
101 	(void)printf("Integers: %d, ", zwerg);
102 	(void)printf("8-Bit characters: %d\n", umlaut);
103 
104 }
105 #endif /* _LOCATE_STATISTIC_ */
106 
107 
108 void
109 #ifdef FF_MMAP
110 
111 
112 #ifdef FF_ICASE
113 fastfind_mmap_icase
114 #else
115 fastfind_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
128 fastfind_icase
129 #else
130 fastfind
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 	u_char *p, *s, *patend, *q, *foundchar;
143 	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 		/* overlay old path */
220 		p = path + count;
221 		foundchar = p - 1;
222 
223 #ifdef FF_MMAP
224 		for (; len > 0;) {
225 			c = (u_char)*paddr++;
226 		        len--;
227 #else
228 		for (;;) {
229 			c = getc(fp);
230 #endif /* FF_MMAP */
231 			/*
232 			 * == UMLAUT: 8 bit char followed
233 			 * <= SWITCH: offset
234 			 * >= PARITY: bigram
235 			 * rest:      single ascii char
236 			 *
237 			 * offset < SWITCH < UMLAUT < ascii < PARITY < bigram
238 			 */
239 			if (c < PARITY) {
240 				if (c <= UMLAUT) {
241 					if (c == UMLAUT) {
242 #ifdef FF_MMAP
243 						c = (u_char)*paddr++;
244 						len--;
245 #else
246 						c = getc(fp);
247 #endif /* FF_MMAP */
248 
249 					} else
250 						break; /* SWITCH */
251 				}
252 #ifdef FF_ICASE
253 				if (table[c])
254 #else
255 				if (c == cc)
256 #endif /* FF_ICASE */
257 					foundchar = p;
258 				*p++ = c;
259 			}
260 			else {
261 				/* bigrams are parity-marked */
262 				TO7BIT(c);
263 
264 #ifndef FF_ICASE
265 				if (bigram1[c] == cc ||
266 				    bigram2[c] == cc)
267 #else
268 
269 					if (table[bigram1[c]] ||
270 					    table[bigram2[c]])
271 #endif /* FF_ICASE */
272 						foundchar = p + 1;
273 
274 				*p++ = bigram1[c];
275 				*p++ = bigram2[c];
276 			}
277 		}
278 
279 		if (found) {                     /* previous line matched */
280 			cutoff = path;
281 			*p-- = '\0';
282 			foundchar = p;
283 		} else if (foundchar >= path + count) { /* a char matched */
284 			*p-- = '\0';
285 			cutoff = path + count;
286 		} else                           /* nothing to do */
287 			continue;
288 
289 		found = 0;
290 		for (s = foundchar; s >= cutoff; s--) {
291 			if (*s == cc
292 #ifdef FF_ICASE
293 			    || TOLOWER(*s) == cc
294 #endif /* FF_ICASE */
295 			    ) {	/* fast first char check */
296 				for (p = patend - 1, q = s - 1; *p != '\0';
297 				     p--, q--)
298 					if (*q != *p
299 #ifdef FF_ICASE
300 					    && TOLOWER(*q) != *p
301 #endif /* FF_ICASE */
302 					    )
303 						break;
304 				if (*p == '\0') {   /* fast match success */
305 					found = 1;
306 					if (!globflag ||
307 #ifndef FF_ICASE
308 					    !fnmatch(pathpart, path, 0))
309 #else
310 					    !fnmatch(pathpart, path,
311 						     FNM_CASEFOLD))
312 #endif /* !FF_ICASE */
313 					{
314 						if (f_silent)
315 							counter++;
316 						else if (f_limit) {
317 							counter++;
318 							if (f_limit >= counter)
319 								(void)puts(path);
320 							else
321 								errx(0, "[show only %d lines]", counter - 1);
322 						} else
323 							(void)puts(path);
324 					}
325 					break;
326 				}
327 			}
328 		}
329 	}
330 }
331