diff options
Diffstat (limited to '')
| -rw-r--r-- | misc-utils/look.c | 376 |
1 files changed, 376 insertions, 0 deletions
diff --git a/misc-utils/look.c b/misc-utils/look.c new file mode 100644 index 0000000..d2699bf --- /dev/null +++ b/misc-utils/look.c @@ -0,0 +1,376 @@ +/*- + * Copyright (c) 1991, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * David Hitz of Auspex Systems, Inc. + * + * 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. + */ + + /* 1999-02-22 Arkadiusz Miśkiewicz <misiek@pld.ORG.PL> + * - added Native Language Support + */ + +/* + * look -- find lines in a sorted list. + * + * The man page said that TABs and SPACEs participate in -d comparisons. + * In fact, they were ignored. This implements historic practice, not + * the manual page. + */ + +#include <sys/mman.h> +#include <sys/stat.h> +#include <errno.h> +#include <fcntl.h> +#include <stdio.h> +#include <stdlib.h> +#include <stddef.h> +#include <string.h> +#include <ctype.h> +#include <getopt.h> + +#include "nls.h" +#include "xalloc.h" +#include "pathnames.h" +#include "closestream.h" + +#define EQUAL 0 +#define GREATER 1 +#define LESS (-1) + +static int dflag, fflag; +/* uglified the source a bit with globals, so that we only need + to allocate comparbuf once */ +static int stringlen; +static char *string; +static char *comparbuf; + +static char *binary_search (char *, char *); +static int compare (char *, char *); +static char *linear_search (char *, char *); +static int look (char *, char *); +static void print_from (char *, char *); +static void __attribute__((__noreturn__)) usage(void); + +int +main(int argc, char *argv[]) +{ + struct stat sb; + int ch, fd, termchar; + char *back, *file, *front, *p; + + static const struct option longopts[] = { + {"alternative", no_argument, NULL, 'a'}, + {"alphanum", no_argument, NULL, 'd'}, + {"ignore-case", no_argument, NULL, 'f'}, + {"terminate", required_argument, NULL, 't'}, + {"version", no_argument, NULL, 'V'}, + {"help", no_argument, NULL, 'h'}, + {NULL, 0, NULL, 0} + }; + + setlocale(LC_ALL, ""); + bindtextdomain(PACKAGE, LOCALEDIR); + textdomain(PACKAGE); + atexit(close_stdout); + + setlocale(LC_ALL, ""); + + if ((file = getenv("WORDLIST")) && !access(file, R_OK)) + /* use the WORDLIST */; + else + file = _PATH_WORDS; + + termchar = '\0'; + string = NULL; /* just for gcc */ + + while ((ch = getopt_long(argc, argv, "adft:Vh", longopts, NULL)) != -1) + switch(ch) { + case 'a': + file = _PATH_WORDS_ALT; + break; + case 'd': + dflag = 1; + break; + case 'f': + fflag = 1; + break; + case 't': + termchar = *optarg; + break; + case 'V': + printf(UTIL_LINUX_VERSION); + return EXIT_SUCCESS; + case 'h': + usage(); + default: + errtryhelp(EXIT_FAILURE); + } + argc -= optind; + argv += optind; + + switch (argc) { + case 2: /* Don't set -df for user. */ + string = *argv++; + file = *argv; + break; + case 1: /* But set -df by default. */ + dflag = fflag = 1; + string = *argv; + break; + default: + warnx(_("bad usage")); + errtryhelp(EXIT_FAILURE); + } + + if (termchar != '\0' && (p = strchr(string, termchar)) != NULL) + *++p = '\0'; + + if ((fd = open(file, O_RDONLY, 0)) < 0 || fstat(fd, &sb)) + err(EXIT_FAILURE, "%s", file); + front = mmap(NULL, (size_t) sb.st_size, PROT_READ, + MAP_SHARED, fd, (off_t) 0); + if +#ifdef MAP_FAILED + (front == MAP_FAILED) +#else + ((void *)(front) <= (void *)0) +#endif + err(EXIT_FAILURE, "%s", file); + back = front + sb.st_size; + return look(front, back); +} + +static int +look(char *front, char *back) +{ + int ch; + char *readp, *writep; + + /* Reformat string to avoid doing it multiple times later. */ + if (dflag) { + for (readp = writep = string; (ch = *readp++) != 0;) { + if (isalnum(ch) || isblank(ch)) + *(writep++) = ch; + } + *writep = '\0'; + stringlen = writep - string; + } else + stringlen = strlen(string); + + comparbuf = xmalloc(stringlen+1); + + front = binary_search(front, back); + front = linear_search(front, back); + + if (front) + print_from(front, back); + + free(comparbuf); + + return (front ? 0 : 1); +} + + +/* + * Binary search for "string" in memory between "front" and "back". + * + * This routine is expected to return a pointer to the start of a line at + * *or before* the first word matching "string". Relaxing the constraint + * this way simplifies the algorithm. + * + * Invariants: + * front points to the beginning of a line at or before the first + * matching string. + * + * back points to the beginning of a line at or after the first + * matching line. + * + * Advancing the Invariants: + * + * p = first newline after halfway point from front to back. + * + * If the string at "p" is not greater than the string to match, + * p is the new front. Otherwise it is the new back. + * + * Termination: + * + * The definition of the routine allows it return at any point, + * since front is always at or before the line to print. + * + * In fact, it returns when the chosen "p" equals "back". This + * implies that there exists a string is least half as long as + * (back - front), which in turn implies that a linear search will + * be no more expensive than the cost of simply printing a string or two. + * + * Trying to continue with binary search at this point would be + * more trouble than it's worth. + */ +#define SKIP_PAST_NEWLINE(p, back) \ + while (p < back && *p++ != '\n') + +static char * +binary_search(char *front, char *back) +{ + char *p; + + p = front + (back - front) / 2; + SKIP_PAST_NEWLINE(p, back); + + /* + * If the file changes underneath us, make sure we don't + * infinitely loop. + */ + while (p < back && back > front) { + if (compare(p, back) == GREATER) + front = p; + else + back = p; + p = front + (back - front) / 2; + SKIP_PAST_NEWLINE(p, back); + } + return (front); +} + +/* + * Find the first line that starts with string, linearly searching from front + * to back. + * + * Return NULL for no such line. + * + * This routine assumes: + * + * o front points at the first character in a line. + * o front is before or at the first line to be printed. + */ +static char * +linear_search(char *front, char *back) +{ + while (front < back) { + switch (compare(front, back)) { + case EQUAL: /* Found it. */ + return (front); + case LESS: /* No such string. */ + return (NULL); + case GREATER: /* Keep going. */ + break; + } + SKIP_PAST_NEWLINE(front, back); + } + return (NULL); +} + +/* + * Print as many lines as match string, starting at front. + */ +static void +print_from(char *front, char *back) +{ + int eol; + + while (front < back && compare(front, back) == EQUAL) { + if (compare(front, back) == EQUAL) { + eol = 0; + while (front < back && !eol) { + if (putchar(*front) == EOF) + err(EXIT_FAILURE, "stdout"); + if (*front++ == '\n') + eol = 1; + } + } else + SKIP_PAST_NEWLINE(front, back); + } +} + +/* + * Return LESS, GREATER, or EQUAL depending on how string compares with + * string2 (s1 ??? s2). + * + * o Matches up to len(s1) are EQUAL. + * o Matches up to len(s2) are GREATER. + * + * Compare understands about the -f and -d flags, and treats comparisons + * appropriately. + * + * The string "string" is null terminated. The string "s2" is '\n' terminated + * (or "s2end" terminated). + * + * We use strcasecmp etc, since it knows how to ignore case also + * in other locales. + */ +static int +compare(char *s2, char *s2end) { + int i; + char *p; + + /* copy, ignoring things that should be ignored */ + p = comparbuf; + i = stringlen; + while(s2 < s2end && *s2 != '\n' && i) { + if (!dflag || isalnum(*s2) || isblank(*s2)) + { + *p++ = *s2; + i--; + } + s2++; + } + *p = 0; + + /* and compare */ + if (fflag) + i = strncasecmp(comparbuf, string, stringlen); + else + i = strncmp(comparbuf, string, stringlen); + + return ((i > 0) ? LESS : (i < 0) ? GREATER : EQUAL); +} + +static void __attribute__((__noreturn__)) usage(void) +{ + FILE *out = stdout; + fputs(USAGE_HEADER, out); + fprintf(out, _(" %s [options] <string> [<file>...]\n"), program_invocation_short_name); + + fputs(USAGE_SEPARATOR, out); + fputs(_("Display lines beginning with a specified string.\n"), out); + + fputs(USAGE_OPTIONS, out); + fputs(_(" -a, --alternative use the alternative dictionary\n"), out); + fputs(_(" -d, --alphanum compare only blanks and alphanumeric characters\n"), out); + fputs(_(" -f, --ignore-case ignore case differences when comparing\n"), out); + fputs(_(" -t, --terminate <char> define the string-termination character\n"), out); + + fputs(USAGE_SEPARATOR, out); + printf(USAGE_HELP_OPTIONS(26)); + printf(USAGE_MAN_TAIL("look(1)")); + + exit(EXIT_SUCCESS); +} |