b9e23a45bd64f3c3f50260ffb220d604ec3dc1b2
[dragonfly.git] / usr.bin / locate / locate / fastfind.c
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 }