From 67e0b05818557e26741c42cb852dfa0cdf9e9e53 Mon Sep 17 00:00:00 2001 From: Alan Cox Date: Mon, 29 Dec 2014 22:23:24 +0000 Subject: [PATCH] utils: add fgrep --- Applications/util/Makefile | 1 + Applications/util/fgrep.c | 351 +++++++++++++++++++++++++++++++++++++ 2 files changed, 352 insertions(+) create mode 100644 Applications/util/fgrep.c diff --git a/Applications/util/Makefile b/Applications/util/Makefile index 6f473333..95b634b7 100644 --- a/Applications/util/Makefile +++ b/Applications/util/Makefile @@ -37,6 +37,7 @@ SRCS = banner.c \ ed.c \ false.c \ fdisk.c \ + fgrep.c \ fsck.c \ grep.c \ id.c \ diff --git a/Applications/util/fgrep.c b/Applications/util/fgrep.c new file mode 100644 index 00000000..55836908 --- /dev/null +++ b/Applications/util/fgrep.c @@ -0,0 +1,351 @@ +/* fgrep - fast grep Author: Bert Gijsbers */ + +/* Copyright (c) 1991 by Bert Gijsbers. All rights reserved. + * Permission to use and redistribute this software is hereby granted provided + * that this copyright notice remains intact and that any modifications are + * clearly marked as such. + * + * syntax: + * fgrep -chlnsv <[-e string] ... [-f file] ... | string> [file] ... + * options: + * -c : print the number of matching lines + * -h : don't print file name headers if more than one file + * -l : print only the file names of the files containing a match + * -n : print line numbers + * -s : don't print, return status only + * -v : reverse, lines not containing one of the strings match + * -e string : search for this string + * -f file : file contains strings to search for + * notes: + * Options are processed by getopt(3). + * Multiple strings per command line are supported, eg. + * fgrep -e str1 -e str2 *.c + * Instead of a filename - is allowed, meaning standard input. + * + * ANSIfied Alan Cox to make it pass sdcc + */ + +/* #include */ +#include +#include +#include +#include +#include +#include + +#define MAX_STR_LEN 256 /* maximum length of strings to search for */ +#define BYTE 0xFF /* convert from char to int */ +#define READ_SIZE 4096 /* read() request size */ +#define BUF_SIZE (2*READ_SIZE) /* size of buffer */ + +typedef struct test_str { + struct test_str *next; /* linked list */ + char *str; /* string to be found */ + char *str_end; /* points to last character */ + int len; /* string length */ + char *bufp; /* pointer into input buffer */ + unsigned char table[256]; /* table for Boyer-Moore algorithm */ +} test_str; + +test_str *strings; +char *prog_name; +int cflag, hflag, lflag, nflag, sflag, vflag; +unsigned line_num; /* line number in current file */ + +int fd_in, eof_seen; /* file descriptor for input and eof status */ +char input_buffer[BUF_SIZE + 2];/* buffer + sentinel margin */ +#define buffer (&input_buffer[2]) + +/* Pointers into the input buffer */ +char *input; /* points to current input char */ +char *max_input; /* points to first invalid char */ +char *buf_end; /* points to first char not read */ + +/* Error messages */ +char no_mem[] = "not enough memory"; +char no_arg[] = "argument missing"; + +extern char *optarg; +extern int optind; + +int main(int argc, char *argv[]); +char *search_str(test_str *ts); +int fill_buffer(void); +void usage(void); +void failure(const char *mesg); +void file_open(void); +char *get_line(void); +void string_file(void); +void add_string(char *str); + +int main(int argc, char *argv[]) +{ + char *line; + int c; + unsigned count; /* number of matching lines in current file */ + unsigned found_one = 0; /* was there any match in any file at all ? */ + +#ifdef noperprintf + noperprintf(stdout); +#else + static char outbuf[BUFSIZ]; + + setvbuf(stdout, outbuf, _IOFBF, sizeof outbuf); +#endif + + prog_name = argv[0]; + if (argc == 1) usage(); + while ((c = getopt(argc, argv, "ce:f:hlnsv")) != EOF) { + switch (c) { + case 'c': cflag++; break; + case 'e': add_string(optarg); break; + case 'f': string_file(); break; + case 'h': hflag++; break; + case 'l': lflag++; break; + case 'n': nflag++; break; + case 's': sflag++; break; + case 'v': vflag++; break; + default: usage(); break; + } + } + + /* If no -e or -f option is used take a string from the command line. */ + if (strings == (test_str *) NULL) { + if (optind == argc) failure(no_arg); + add_string(argv[optind++]); + } + if (argc - optind < 2) + hflag++; /* don't print filenames if less than two + * files */ + + /* Handle every matching line according to the flags. */ + do { + optarg = argv[optind]; + file_open(); + count = 0; + while ((line = get_line()) != (char *) NULL) { + count++; + if (sflag) return 0; + if (lflag) { + printf("%s\n", optarg); + fflush(stdout); + break; + } + if (cflag) continue; + if (hflag == 0) printf("%s:", optarg); + if (nflag) printf("%u:", line_num); + do { + putchar(*line); + } while (++line < input); + fflush(stdout); + } + found_one |= count; + if (cflag) { + if (hflag == 0) printf("%s: ", optarg); + printf("%u\n", count); + fflush(stdout); + } + close(fd_in); + } while (++optind < argc); + + /* Exit nonzero if no match is found. */ + return found_one ? 0 : 1; +} + +void usage(void) +{ + fprintf(stderr, + "Usage: %s -chlnsv <[-e string] ... [-f file] ... | string> [file] ...\n", + prog_name); + exit(2); +} + +void failure(const char *mesg) +{ + fprintf(stderr, "%s: %s\n", prog_name, mesg); + exit(1); +} + +/* Add a string to search for to the global linked list `strings'. */ +void add_string(char *str) +{ + test_str *ts; + int len; + + if (str == (char *) NULL || (len = strlen(str)) == 0) return; + if (len > MAX_STR_LEN) failure("string too long"); + if ((ts = (test_str *) malloc(sizeof(*ts))) == (test_str *) NULL) + failure(no_mem); + + /* Initialize Boyer-Moore table. */ + memset(ts->table, len, sizeof(ts->table)); + ts->len = len; + ts->str = str; + ts->str_end = str + len - 1; + for (; --len >= 0; str++) ts->table[*str & BYTE] = len; + + /* Put it on the list */ + ts->next = strings; + strings = ts; +} + +/* Open a file for reading. Initialize input buffer pointers. */ +void file_open(void) +{ + /* Use stdin if no file arguments are given on the command line. */ + if (optarg == (char *) NULL || strcmp(optarg, "-") == 0) { + fd_in = 0; + optarg = "stdin"; + } else if ((fd_in = open(optarg, O_RDONLY)) == -1) { + fprintf(stderr, "%s: can't open %s\n", prog_name, optarg); + exit(1); + } + input = max_input = buf_end = buffer; + buffer[-1] = '\n'; /* sentinel */ + eof_seen = 0; + line_num = 0; +} + +/* Move any leftover characters to the head of the buffer. + * Read characters into the rest of the buffer. + * Round off the available input to whole lines. + * Return the number of valid input characters. + */ +int fill_buffer(void) +{ + char *bufp; + int size; + + if (eof_seen) return 0; + + size = buf_end - max_input; + memmove(buffer, max_input, size); + bufp = &buffer[size]; + + do { + if ((size = read(fd_in, bufp, READ_SIZE)) <= 0) { + if (size != 0) failure("read error"); + eof_seen++; + if (bufp == buffer) /* no input left */ + return 0; + /* Make sure the last char of a file is '\n'. */ + *bufp++ = '\n'; + break; + } + bufp += size; + } while (bufp - buffer < READ_SIZE && bufp[-1] != '\n'); + + buf_end = bufp; + while (*--bufp != '\n'); + if (++bufp == buffer) { + /* Line too long. */ + *buf_end++ = '\n'; + bufp = buf_end; + } + max_input = bufp; + input = buffer; + + return max_input - buffer; +} + +/* Read strings from a file. Give duplicates to add_string(). */ +void string_file(void) +{ + char *str, *p; + + file_open(); + while (input < max_input || fill_buffer() > 0) { + p = (char *) memchr(input, '\n', BUF_SIZE); + *p++ = '\0'; + if ((str = (char *) malloc(p - input)) == (char *) NULL) + failure(no_mem); + memcpy(str, input, p - input); + add_string(str); + input = p; + } + close(fd_in); +} + +/* Scan the rest of the available input for a string using Boyer-Moore. + * Return a pointer to the match or a pointer beyond end of input if no match. + * Record how far the input is scanned. + */ +char *search_str(test_str *ts) +{ + char *bufp, *prevbufp, *s; + + bufp = input + ts->len - 1; + while (bufp < max_input) { + prevbufp = bufp; + bufp += ts->table[*bufp & BYTE]; + if (bufp > prevbufp) continue; + s = ts->str_end; + do { + if (s == ts->str) { /* match found */ + ts->bufp = bufp; + return bufp; + } + } while (*--bufp == *--s); + bufp = prevbufp + 1; + } + ts->bufp = bufp; + + return bufp; +} + +/* Return the next line in which one of the strings occurs. + * Or, if the -v option is used, the next line without a match. + * Or NULL on EOF. + */ +char *get_line(void) +{ + test_str *ts; + char *match, *line; + + /* Loop until a line is found. */ + while (1) { + if (input >= max_input && fill_buffer() == 0) { /* EOF */ + line = (char *) NULL; + break; + } + + /* If match is still equal to max_input after the next loop + * then no match is found. */ + match = max_input; + ts = strings; + do { + if (input == buffer) { + if (search_str(ts) < match) match = ts->bufp; + } else if (ts->bufp < match) { + if (ts->bufp >= input || search_str(ts) < match) + match = ts->bufp; + } + } while ((ts = ts->next) != (test_str *) NULL); + + /* Determine if and in what line a match is found. Only do + * line number counting if it is necessary or very easy. */ + if (vflag) { + line_num++; + line = input; + input = 1 + (char *) memchr(line, '\n', BUF_SIZE); + if (input <= match) break; /* no match in current line */ + } else if (nflag) { + do { + line_num++; + line = input; + input = 1 + (char *) memchr(line, '\n', BUF_SIZE); + } while (input < match || + (input == match && match < max_input)); + if (match < max_input) break; /* match found */ + } else if (match < max_input) { + /* Match found. */ + for (line = match; *--line != '\n';); + line++; + input = 1 + (char *) memchr(match, '\n', BUF_SIZE); + break; + } else + input = max_input; + } + + return line; +} -- 2.34.1