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