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 }