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  */
  39
  40
  41 #ifndef _LOCATE_STATISTIC_
  42 #define _LOCATE_STATISTIC_
  43
  44 static void
  45 statistic (FILE *fp, char *path_fcodes)
  46 {
  47         int lines, chars, size, big, zwerg;
  48         u_char *p, *s;
  49         int c;
  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
 105 static void
 106 #ifdef FF_MMAP
 107
 108
 109 #ifdef FF_ICASE
 110 fastfind_mmap_icase
 111 #else
 112 fastfind_mmap
 113 #endif /* FF_ICASE */
 114 (char *pathpart, caddr_t paddr, int len, char *database)
 115
 116
 117 #else /* MMAP */
 118
 119
 120 #ifdef FF_ICASE
 121 fastfind_icase
 122 #else
 123 fastfind
 124 #endif /* FF_ICASE */
 125
 126 (FILE *fp, char *pathpart, char *database)
 127
 128
 129 #endif /* MMAP */
 130
 131 {
 132         u_char *p, *s, *patend, *q, *foundchar;
 133         int c, cc;
 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 }