+/*
+ * Copyright (c) 1995 Wolfram Schneider <wosch@FreeBSD.org>. Berlin.
+ * Copyright (c) 1989, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * James A. Woods.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by the University of
+ * California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD: src/usr.bin/locate/locate/fastfind.c,v 1.14 2005/12/07 12:22:46 des Exp $
+ */
+
+
+#ifndef _LOCATE_STATISTIC_
+#define _LOCATE_STATISTIC_
+
+void
+statistic (fp, path_fcodes)
+ FILE *fp; /* open database */
+ char *path_fcodes; /* for error message */
+{
+ register int lines, chars, size, big, zwerg;
+ register u_char *p, *s;
+ register int c;
+ int count, umlaut;
+ u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
+
+ for (c = 0, p = bigram1, s = bigram2; c < NBG; c++) {
+ p[c] = check_bigram_char(getc(fp));
+ s[c] = check_bigram_char(getc(fp));
+ }
+
+ lines = chars = big = zwerg = umlaut = 0;
+ size = NBG + NBG;
+
+ for (c = getc(fp), count = 0; c != EOF; size++) {
+ if (c == SWITCH) {
+ count += getwf(fp) - OFFSET;
+ size += sizeof(int);
+ zwerg++;
+ } else
+ count += c - OFFSET;
+
+ for (p = path + count; (c = getc(fp)) > SWITCH; size++)
+ if (c < PARITY) {
+ if (c == UMLAUT) {
+ c = getc(fp);
+ size++;
+ umlaut++;
+ }
+ p++;
+ } else {
+ /* bigram char */
+ big++;
+ p += 2;
+ }
+
+ p++;
+ lines++;
+ chars += (p - path);
+ }
+
+ (void)printf("\nDatabase: %s\n", path_fcodes);
+ (void)printf("Compression: Front: %2.2f%%, ",
+ (size + big - (2 * NBG)) / (chars / (float)100));
+ (void)printf("Bigram: %2.2f%%, ", (size - big) / (size / (float)100));
+ (void)printf("Total: %2.2f%%\n",
+ (size - (2 * NBG)) / (chars / (float)100));
+ (void)printf("Filenames: %d, ", lines);
+ (void)printf("Characters: %d, ", chars);
+ (void)printf("Database size: %d\n", size);
+ (void)printf("Bigram characters: %d, ", big);
+ (void)printf("Integers: %d, ", zwerg);
+ (void)printf("8-Bit characters: %d\n", umlaut);
+
+}
+#endif /* _LOCATE_STATISTIC_ */
+
+extern char separator;
+
+void
+#ifdef FF_MMAP
+
+
+#ifdef FF_ICASE
+fastfind_mmap_icase
+#else
+fastfind_mmap
+#endif /* FF_ICASE */
+(pathpart, paddr, len, database)
+ char *pathpart; /* search string */
+ caddr_t paddr; /* mmap pointer */
+ int len; /* length of database */
+ char *database; /* for error message */
+
+
+#else /* MMAP */
+
+
+#ifdef FF_ICASE
+fastfind_icase
+#else
+fastfind
+#endif /* FF_ICASE */
+
+(fp, pathpart, database)
+ FILE *fp; /* open database */
+ char *pathpart; /* search string */
+ char *database; /* for error message */
+
+
+#endif /* MMAP */
+
+{
+ register u_char *p, *s, *patend, *q, *foundchar;
+ register int c, cc;
+ int count, found, globflag;
+ u_char *cutoff;
+ u_char bigram1[NBG], bigram2[NBG], path[MAXPATHLEN];
+
+#ifdef FF_ICASE
+ /* use a lookup table for case insensitive search */
+ u_char table[UCHAR_MAX + 1];
+
+ tolower_word(pathpart);
+#endif /* FF_ICASE*/
+
+ /* init bigram table */
+#ifdef FF_MMAP
+ if (len < (2*NBG))
+ errx(1, "database too small: %s", database);
+
+ for (c = 0, p = bigram1, s = bigram2; c < NBG; c++, len-= 2) {
+ p[c] = check_bigram_char(*paddr++);
+ s[c] = check_bigram_char(*paddr++);
+ }
+#else
+ for (c = 0, p = bigram1, s = bigram2; c < NBG; c++) {
+ p[c] = check_bigram_char(getc(fp));
+ s[c] = check_bigram_char(getc(fp));
+ }
+#endif /* FF_MMAP */
+
+ /* find optimal (last) char for searching */
+ for (p = pathpart; *p != '\0'; p++)
+ if (index(LOCATE_REG, *p) != NULL)
+ break;
+
+ if (*p == '\0')
+ globflag = 0;
+ else
+ globflag = 1;
+
+ p = pathpart;
+ patend = patprep(p);
+ cc = *patend;
+
+#ifdef FF_ICASE
+ /* set patend char to true */
+ for (c = 0; c < UCHAR_MAX + 1; c++)
+ table[c] = 0;
+
+ table[TOLOWER(*patend)] = 1;
+ table[toupper(*patend)] = 1;
+#endif /* FF_ICASE */
+
+
+ /* main loop */
+ found = count = 0;
+ foundchar = 0;
+
+#ifdef FF_MMAP
+ c = (u_char)*paddr++; len--;
+ for (; len > 0; ) {
+#else
+ c = getc(fp);
+ for (; c != EOF; ) {
+#endif /* FF_MMAP */
+
+ /* go forward or backward */
+ if (c == SWITCH) { /* big step, an integer */
+#ifdef FF_MMAP
+ count += getwm(paddr) - OFFSET;
+ len -= INTSIZE; paddr += INTSIZE;
+#else
+ count += getwf(fp) - OFFSET;
+#endif /* FF_MMAP */
+ } else { /* slow step, =< 14 chars */
+ count += c - OFFSET;
+ }
+
+ /* overlay old path */
+ p = path + count;
+ foundchar = p - 1;
+
+#ifdef FF_MMAP
+ for (; len > 0;) {
+ c = (u_char)*paddr++;
+ len--;
+#else
+ for (;;) {
+ c = getc(fp);
+#endif /* FF_MMAP */
+ /*
+ * == UMLAUT: 8 bit char followed
+ * <= SWITCH: offset
+ * >= PARITY: bigram
+ * rest: single ascii char
+ *
+ * offset < SWITCH < UMLAUT < ascii < PARITY < bigram
+ */
+ if (c < PARITY) {
+ if (c <= UMLAUT) {
+ if (c == UMLAUT) {
+#ifdef FF_MMAP
+ c = (u_char)*paddr++;
+ len--;
+#else
+ c = getc(fp);
+#endif /* FF_MMAP */
+
+ } else
+ break; /* SWITCH */
+ }
+#ifdef FF_ICASE
+ if (table[c])
+#else
+ if (c == cc)
+#endif /* FF_ICASE */
+ foundchar = p;
+ *p++ = c;
+ }
+ else {
+ /* bigrams are parity-marked */
+ TO7BIT(c);
+
+#ifndef FF_ICASE
+ if (bigram1[c] == cc ||
+ bigram2[c] == cc)
+#else
+
+ if (table[bigram1[c]] ||
+ table[bigram2[c]])
+#endif /* FF_ICASE */
+ foundchar = p + 1;
+
+ *p++ = bigram1[c];
+ *p++ = bigram2[c];
+ }
+ }
+
+ if (found) { /* previous line matched */
+ cutoff = path;
+ *p-- = '\0';
+ foundchar = p;
+ } else if (foundchar >= path + count) { /* a char matched */
+ *p-- = '\0';
+ cutoff = path + count;
+ } else /* nothing to do */
+ continue;
+
+ found = 0;
+ for (s = foundchar; s >= cutoff; s--) {
+ if (*s == cc
+#ifdef FF_ICASE
+ || TOLOWER(*s) == cc
+#endif /* FF_ICASE */
+ ) { /* fast first char check */
+ for (p = patend - 1, q = s - 1; *p != '\0';
+ p--, q--)
+ if (*q != *p
+#ifdef FF_ICASE
+ && TOLOWER(*q) != *p
+#endif /* FF_ICASE */
+ )
+ break;
+ if (*p == '\0') { /* fast match success */
+ found = 1;
+ if (!globflag ||
+#ifndef FF_ICASE
+ !fnmatch(pathpart, path, 0))
+#else
+ !fnmatch(pathpart, path,
+ FNM_CASEFOLD))
+#endif /* !FF_ICASE */
+ {
+ if (f_silent)
+ counter++;
+ else if (f_limit) {
+ counter++;
+ if (f_limit >= counter)
+ (void)printf("%s%c",path,separator);
+ else
+ errx(0, "[show only %d lines]", counter - 1);
+ } else
+ (void)printf("%s%c",path,separator);
+ }
+ break;
+ }
+ }
+ }
+ }
+}
projects / apple / shell_cmds.git / commitdiff
