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