usr.bin/locate/locate/fastfind.c

   1 /*
   2  * SPDX-License-Identifier: BSD-4-Clause
   3  *
   4  * Copyright (c) 1995 Wolfram Schneider <wosch@FreeBSD.org>. Berlin.
   5  * Copyright (c) 1989, 1993
   6  *      The Regents of the University of California.  All rights reserved.
   7  *
   8  * This code is derived from software contributed to Berkeley by
   9  * James A. Woods.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. All advertising materials mentioning features or use of this software
  20  *    must display the following acknowledgement:
  21  *      This product includes software developed by the University of
  22  *      California, Berkeley and its contributors.
  23  * 4. Neither the name of the University nor the names of its contributors
  24  *    may be used to endorse or promote products derived from this software
  25  *    without specific prior written permission.
  26  *
  27  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  28  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  29  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  30  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  31  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  32  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  33  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  34  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  35  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  36  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  37  * SUCH DAMAGE.
  38  *
  39  * $FreeBSD$
  40  */
  41
  42
  43 #ifndef _LOCATE_STATISTIC_
  44 #define _LOCATE_STATISTIC_
  45
  46 void
  47 statistic (fp, path_fcodes)
  48         FILE *fp;               /* open database */
  49         char *path_fcodes;      /* for error message */
  50 {
  51         register int lines, chars, size, big, zwerg;
  52         register u_char *p, *s;
  53         register int c;
  54         int count, umlaut;
  55         u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
  56
  57         for (c = 0, p = bigram1, s = bigram2; c < NBG; c++) {
  58                 p[c] = check_bigram_char(getc(fp));
  59                 s[c] = check_bigram_char(getc(fp));
  60         }
  61
  62         lines = chars = big = zwerg = umlaut = 0;
  63         size = NBG + NBG;
  64
  65         for (c = getc(fp), count = 0; c != EOF; size++) {
  66                 if (c == SWITCH) {
  67                         count += getwf(fp) - OFFSET;
  68                         size += sizeof(int);
  69                         zwerg++;
  70                 } else
  71                         count += c - OFFSET;
  72
  73                 for (p = path + count; (c = getc(fp)) > SWITCH; size++)
  74                         if (c < PARITY) {
  75                                 if (c == UMLAUT) {
  76                                         c = getc(fp);
  77                                         size++;
  78                                         umlaut++;
  79                                 }
  80                                 p++;
  81                         } else {
  82                                 /* bigram char */
  83                                 big++;
  84                                 p += 2;
  85                         }
  86
  87                 p++;
  88                 lines++;
  89                 chars += (p - path);
  90         }
  91
  92         (void)printf("\nDatabase: %s\n", path_fcodes);
  93         (void)printf("Compression: Front: %2.2f%%, ",
  94                      (size + big - (2 * NBG)) / (chars / (float)100));
  95         (void)printf("Bigram: %2.2f%%, ", (size - big) / (size / (float)100));
  96         (void)printf("Total: %2.2f%%\n",
  97                      (size - (2 * NBG)) / (chars / (float)100));
  98         (void)printf("Filenames: %d, ", lines);
  99         (void)printf("Characters: %d, ", chars);
 100         (void)printf("Database size: %d\n", size);
 101         (void)printf("Bigram characters: %d, ", big);
 102         (void)printf("Integers: %d, ", zwerg);
 103         (void)printf("8-Bit characters: %d\n", umlaut);
 104
 105 }
 106 #endif /* _LOCATE_STATISTIC_ */
 107
 108 extern  char    separator;
 109
 110 void
 111 #ifdef FF_MMAP
 112
 113
 114 #ifdef FF_ICASE
 115 fastfind_mmap_icase
 116 #else
 117 fastfind_mmap
 118 #endif /* FF_ICASE */
 119 (pathpart, paddr, len, database)
 120         char *pathpart;         /* search string */
 121         caddr_t paddr;          /* mmap pointer */
 122         int len;                /* length of database */
 123         char *database;         /* for error message */
 124
 125
 126 #else /* MMAP */
 127
 128
 129 #ifdef FF_ICASE
 130 fastfind_icase
 131 #else
 132 fastfind
 133 #endif /* FF_ICASE */
 134
 135 (fp, pathpart, database)
 136         FILE *fp;               /* open database */
 137         char *pathpart;         /* search string */
 138         char *database;         /* for error message */
 139
 140
 141 #endif /* MMAP */
 142
 143 {
 144         register u_char *p, *s, *patend, *q, *foundchar;
 145         register int c, cc;
 146         int count, found, globflag;
 147         u_char *cutoff;
 148         u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
 149
 150 #ifdef FF_ICASE
 151         /* use a lookup table for case insensitive search */
 152         u_char table[UCHAR_MAX + 1];
 153
 154         tolower_word(pathpart);
 155 #endif /* FF_ICASE*/
 156
 157         /* init bigram table */
 158 #ifdef FF_MMAP
 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 (strchr(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                 if (count < 0 || count > MAXPATHLEN)
 219                         errx(1, "corrupted database: %s", database);
 220                 /* overlay old path */
 221                 p = path + count;
 222                 foundchar = p - 1;
 223
 224 #ifdef FF_MMAP
 225                 for (; len > 0;) {
 226                         c = (u_char)*paddr++;
 227                         len--;
 228 #else
 229                 for (;;) {
 230                         c = getc(fp);
 231 #endif /* FF_MMAP */
 232                         /*
 233                          * == UMLAUT: 8 bit char followed
 234                          * <= SWITCH: offset
 235                          * >= PARITY: bigram
 236                          * rest:      single ascii char
 237                          *
 238                          * offset < SWITCH < UMLAUT < ascii < PARITY < bigram
 239                          */
 240                         if (c < PARITY) {
 241                                 if (c <= UMLAUT) {
 242                                         if (c == UMLAUT) {
 243 #ifdef FF_MMAP
 244                                                 c = (u_char)*paddr++;
 245                                                 len--;
 246 #else
 247                                                 c = getc(fp);
 248 #endif /* FF_MMAP */
 249
 250                                         } else
 251                                                 break; /* SWITCH */
 252                                 }
 253 #ifdef FF_ICASE
 254                                 if (table[c])
 255 #else
 256                                 if (c == cc)
 257 #endif /* FF_ICASE */
 258                                         foundchar = p;
 259                                 *p++ = c;
 260                         }
 261                         else {
 262                                 /* bigrams are parity-marked */
 263                                 TO7BIT(c);
 264
 265 #ifndef FF_ICASE
 266                                 if (bigram1[c] == cc ||
 267                                     bigram2[c] == cc)
 268 #else
 269
 270                                         if (table[bigram1[c]] ||
 271                                             table[bigram2[c]])
 272 #endif /* FF_ICASE */
 273                                                 foundchar = p + 1;
 274
 275                                 *p++ = bigram1[c];
 276                                 *p++ = bigram2[c];
 277                         }
 278                 }
 279
 280                 if (found) {                     /* previous line matched */
 281                         cutoff = path;
 282                         *p-- = '\0';
 283                         foundchar = p;
 284                 } else if (foundchar >= path + count) { /* a char matched */
 285                         *p-- = '\0';
 286                         cutoff = path + count;
 287                 } else                           /* nothing to do */
 288                         continue;
 289
 290                 found = 0;
 291                 for (s = foundchar; s >= cutoff; s--) {
 292                         if (*s == cc
 293 #ifdef FF_ICASE
 294                             || TOLOWER(*s) == cc
 295 #endif /* FF_ICASE */
 296                             ) { /* fast first char check */
 297                                 for (p = patend - 1, q = s - 1; *p != '\0';
 298                                      p--, q--)
 299                                         if (*q != *p
 300 #ifdef FF_ICASE
 301                                             && TOLOWER(*q) != *p
 302 #endif /* FF_ICASE */
 303                                             )
 304                                                 break;
 305                                 if (*p == '\0') {   /* fast match success */
 306                                         found = 1;
 307                                         if (!globflag ||
 308 #ifndef FF_ICASE
 309                                             !fnmatch(pathpart, path, 0))
 310 #else
 311                                             !fnmatch(pathpart, path,
 312                                                      FNM_CASEFOLD))
 313 #endif /* !FF_ICASE */
 314                                         {
 315                                                 if (f_silent)
 316                                                         counter++;
 317                                                 else if (f_limit) {
 318                                                         counter++;
 319                                                         if (f_limit >= counter)
 320                                                                 (void)printf("%s%c",path,separator);
 321                                                         else
 322                                                                 errx(0, "[show only %d lines]", counter - 1);
 323                                                 } else
 324                                                         (void)printf("%s%c",path,separator);
 325                                         }
 326                                         break;
 327                                 }
 328                         }
 329                 }
 330         }
 331 }