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 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 #ifdef FF_MMAP
 223                 for (; len > 0;) {
 224                         c = (u_char)*paddr++;
 225                         len--;
 226 #else
 227                 for (;;) {
 228                         c = getc(fp);
 229 #endif /* FF_MMAP */
 230                         /*
 231                          * == UMLAUT: 8 bit char followed
 232                          * <= SWITCH: offset
 233                          * >= PARITY: bigram
 234                          * rest:      single ascii char
 235                          *
 236                          * offset < SWITCH < UMLAUT < ascii < PARITY < bigram
 237                          */
 238                         if (c < PARITY) {
 239                                 if (c <= UMLAUT) {
 240                                         if (c == UMLAUT) {
 241 #ifdef FF_MMAP
 242                                                 c = (u_char)*paddr++;
 243                                                 len--;
 244 #else
 245                                                 c = getc(fp);
 246 #endif /* FF_MMAP */
 247
 248                                         } else
 249                                                 break; /* SWITCH */
 250                                 }
 251 #ifdef FF_ICASE
 252                                 if (table[c])
 253 #else
 254                                 if (c == cc)
 255 #endif /* FF_ICASE */
 256                                         foundchar = p;
 257                                 *p++ = c;
 258                         }
 259                         else {
 260                                 /* bigrams are parity-marked */
 261                                 TO7BIT(c);
 262
 263 #ifndef FF_ICASE
 264                                 if (bigram1[c] == cc ||
 265                                     bigram2[c] == cc)
 266 #else
 267
 268                                         if (table[bigram1[c]] ||
 269                                             table[bigram2[c]])
 270 #endif /* FF_ICASE */
 271                                                 foundchar = p + 1;
 272
 273                                 *p++ = bigram1[c];
 274                                 *p++ = bigram2[c];
 275                         }
 276                 }
 277
 278                 if (found) {                     /* previous line matched */
 279                         cutoff = path;
 280                         *p-- = '\0';
 281                         foundchar = p;
 282                 } else if (foundchar >= path + count) { /* a char matched */
 283                         *p-- = '\0';
 284                         cutoff = path + count;
 285                 } else                           /* nothing to do */
 286                         continue;
 287
 288                 found = 0;
 289                 for (s = foundchar; s >= cutoff; s--) {
 290                         if (*s == cc
 291 #ifdef FF_ICASE
 292                             || TOLOWER(*s) == cc
 293 #endif /* FF_ICASE */
 294                             ) { /* fast first char check */
 295                                 for (p = patend - 1, q = s - 1; *p != '\0';
 296                                      p--, q--)
 297                                         if (*q != *p
 298 #ifdef FF_ICASE
 299                                             && TOLOWER(*q) != *p
 300 #endif /* FF_ICASE */
 301                                             )
 302                                                 break;
 303                                 if (*p == '\0') {   /* fast match success */
 304                                         found = 1;
 305                                         if (!globflag ||
 306 #ifndef FF_ICASE
 307                                             !fnmatch(pathpart, path, 0))
 308 #else
 309                                             !fnmatch(pathpart, path,
 310                                                      FNM_CASEFOLD))
 311 #endif /* !FF_ICASE */
 312                                         {
 313                                                 if (f_silent)
 314                                                         counter++;
 315                                                 else if (f_limit) {
 316                                                         counter++;
 317                                                         if (f_limit >= counter)
 318                                                                 (void)puts(path);
 319                                                         else
 320                                                                 errx(0, "[show only %d lines]", counter - 1);
 321                                                 } else
 322                                                         (void)puts(path);
 323                                         }
 324                                         break;
 325                                 }
 326                         }
 327                 }
 328         }
 329 }