commands/simple/fgrep.c

   1 /* fgrep - fast grep                    Author: Bert Gijsbers */
   2
   3 /* Copyright (c) 1991 by Bert Gijsbers.  All rights reserved.
   4  * Permission to use and redistribute this software is hereby granted provided
   5  * that this copyright notice remains intact and that any modifications are
   6  * clearly marked as such.
   7  *
   8  * syntax:
   9  *      fgrep -chlnsv <[-e string] ... [-f file] ... | string> [file] ...
  10  * options:
  11  *      -c : print the number of matching lines
  12  *      -h : don't print file name headers if more than one file
  13  *      -l : print only the file names of the files containing a match
  14  *      -n : print line numbers
  15  *      -s : don't print, return status only
  16  *      -v : reverse, lines not containing one of the strings match
  17  *      -e string : search for this string
  18  *      -f file : file contains strings to search for
  19  * notes:
  20  *      Options are processed by getopt(3).
  21  *      Multiple strings per command line are supported, eg.
  22  *              fgrep -e str1 -e str2 *.c
  23  *      Instead of a filename - is allowed, meaning standard input.
  24  */
  25
  26 /* #include <ansi.h> */
  27 #include <sys/types.h>
  28 #include <unistd.h>
  29 #include <fcntl.h>
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <stdio.h>
  33
  34 #define MAX_STR_LEN      256    /* maximum length of strings to search for */
  35 #define BYTE            0xFF    /* convert from char to int */
  36 #define READ_SIZE       4096    /* read() request size */
  37 #define BUF_SIZE (2*READ_SIZE)  /* size of buffer */
  38
  39 typedef struct test_str {
  40   struct test_str *next;        /* linked list */
  41   char *str;                    /* string to be found */
  42   char *str_end;                /* points to last character */
  43   int len;                      /* string length */
  44   char *bufp;                   /* pointer into input buffer */
  45   unsigned char table[256];     /* table for Boyer-Moore algorithm */
  46 } test_str;
  47
  48 test_str *strings;
  49 char *prog_name;
  50 int cflag, hflag, lflag, nflag, sflag, vflag;
  51 unsigned line_num;              /* line number in current file */
  52
  53 int fd_in, eof_seen;            /* file descriptor for input and eof status */
  54 char input_buffer[BUF_SIZE + 2];/* buffer + sentinel margin */
  55 #define buffer  (&input_buffer[2])
  56
  57 /* Pointers into the input buffer */
  58 char *input;                    /* points to current input char */
  59 char *max_input;                /* points to first invalid char */
  60 char *buf_end;                  /* points to first char not read */
  61
  62 /* Error messages */
  63 char no_mem[] = "not enough memory";
  64 char no_arg[] = "argument missing";
  65
  66 extern char *optarg;
  67 extern int optind;
  68
  69 _PROTOTYPE(int main, (int argc, char **argv));
  70 _PROTOTYPE(char *search_str, (test_str * ts));
  71 _PROTOTYPE(int fill_buffer, (void));
  72 _PROTOTYPE(void failure, (char *mesg));
  73 _PROTOTYPE(void file_open, (void));
  74 _PROTOTYPE(void usage, (void));
  75 _PROTOTYPE(char *get_line, (void));
  76 _PROTOTYPE(void string_file, (void));
  77 _PROTOTYPE(void add_string, (char *str));
  78
  79 int main(argc, argv)
  80 int argc;
  81 char **argv;
  82 {
  83   char *line;
  84   int c;
  85   unsigned count;               /* number of matching lines in current file */
  86   unsigned found_one = 0;       /* was there any match in any file at all ? */
  87
  88 #ifdef noperprintf
  89   noperprintf(stdout);
  90 #else
  91   static char outbuf[BUFSIZ];
  92
  93   setvbuf(stdout, outbuf, _IOFBF, sizeof outbuf);
  94 #endif
  95
  96   prog_name = argv[0];
  97   if (argc == 1) usage();
  98   while ((c = getopt(argc, argv, "ce:f:hlnsv")) != EOF) {
  99         switch (c) {
 100             case 'c':   cflag++;        break;
 101             case 'e':   add_string(optarg);     break;
 102             case 'f':   string_file();  break;
 103             case 'h':   hflag++;        break;
 104             case 'l':   lflag++;        break;
 105             case 'n':   nflag++;        break;
 106             case 's':   sflag++;        break;
 107             case 'v':   vflag++;        break;
 108             default:    usage();        break;
 109         }
 110   }
 111
 112   /* If no -e or -f option is used take a string from the command line. */
 113   if (strings == (test_str *) NULL) {
 114         if (optind == argc) failure(no_arg);
 115         add_string(argv[optind++]);
 116   }
 117   if (argc - optind < 2)
 118         hflag++;                /* don't print filenames if less than two
 119                          * files */
 120
 121   /* Handle every matching line according to the flags. */
 122   do {
 123         optarg = argv[optind];
 124         file_open();
 125         count = 0;
 126         while ((line = get_line()) != (char *) NULL) {
 127                 count++;
 128                 if (sflag) return 0;
 129                 if (lflag) {
 130                         printf("%s\n", optarg);
 131                         fflush(stdout);
 132                         break;
 133                 }
 134                 if (cflag) continue;
 135                 if (hflag == 0) printf("%s:", optarg);
 136                 if (nflag) printf("%u:", line_num);
 137                 do {
 138                         putchar(*line);
 139                 } while (++line < input);
 140                 fflush(stdout);
 141         }
 142         found_one |= count;
 143         if (cflag) {
 144                 if (hflag == 0) printf("%s: ", optarg);
 145                 printf("%u\n", count);
 146                 fflush(stdout);
 147         }
 148         close(fd_in);
 149   } while (++optind < argc);
 150
 151   /* Exit nonzero if no match is found. */
 152   return found_one ? 0 : 1;
 153 }
 154
 155 void usage()
 156 {
 157   fprintf(stderr,
 158         "Usage: %s -chlnsv <[-e string] ... [-f file] ... | string> [file] ...\n",
 159         prog_name);
 160   exit(2);
 161 }
 162
 163 void failure(mesg)
 164 char *mesg;
 165 {
 166   fprintf(stderr, "%s: %s\n", prog_name, mesg);
 167   exit(1);
 168 }
 169
 170 /* Add a string to search for to the global linked list `strings'. */
 171 void add_string(str)
 172 char *str;
 173 {
 174   test_str *ts;
 175   int len;
 176
 177   if (str == (char *) NULL || (len = strlen(str)) == 0) return;
 178   if (len > MAX_STR_LEN) failure("string too long");
 179   if ((ts = (test_str *) malloc(sizeof(*ts))) == (test_str *) NULL)
 180         failure(no_mem);
 181
 182   /* Initialize Boyer-Moore table. */
 183   memset(ts->table, len, sizeof(ts->table));
 184   ts->len = len;
 185   ts->str = str;
 186   ts->str_end = str + len - 1;
 187   for (; --len >= 0; str++) ts->table[*str & BYTE] = len;
 188
 189   /* Put it on the list */
 190   ts->next = strings;
 191   strings = ts;
 192 }
 193
 194 /* Open a file for reading.  Initialize input buffer pointers. */
 195 void file_open()
 196 {
 197   /* Use stdin if no file arguments are given on the command line. */
 198   if (optarg == (char *) NULL || strcmp(optarg, "-") == 0) {
 199         fd_in = 0;
 200         optarg = "stdin";
 201   } else if ((fd_in = open(optarg, O_RDONLY)) == -1) {
 202         fprintf(stderr, "%s: can't open %s\n", prog_name, optarg);
 203         exit(1);
 204   }
 205   input = max_input = buf_end = buffer;
 206   buffer[-1] = '\n';            /* sentinel */
 207   eof_seen = 0;
 208   line_num = 0;
 209 }
 210
 211 /* Move any leftover characters to the head of the buffer.
 212  * Read characters into the rest of the buffer.
 213  * Round off the available input to whole lines.
 214  * Return the number of valid input characters.
 215  */
 216 int fill_buffer()
 217 {
 218   char *bufp;
 219   int size;
 220
 221   if (eof_seen) return 0;
 222
 223   size = buf_end - max_input;
 224   memmove(buffer, max_input, size);
 225   bufp = &buffer[size];
 226
 227   do {
 228         if ((size = read(fd_in, bufp, READ_SIZE)) <= 0) {
 229                 if (size != 0) failure("read error");
 230                 eof_seen++;
 231                 if (bufp == buffer)     /* no input left */
 232                         return 0;
 233                 /* Make sure the last char of a file is '\n'. */
 234                 *bufp++ = '\n';
 235                 break;
 236         }
 237         bufp += size;
 238   } while (bufp - buffer < READ_SIZE && bufp[-1] != '\n');
 239
 240   buf_end = bufp;
 241   while (*--bufp != '\n');
 242   if (++bufp == buffer) {
 243         /* Line too long. */
 244         *buf_end++ = '\n';
 245         bufp = buf_end;
 246   }
 247   max_input = bufp;
 248   input = buffer;
 249
 250   return max_input - buffer;
 251 }
 252
 253 /* Read strings from a file.  Give duplicates to add_string(). */
 254 void string_file()
 255 {
 256   char *str, *p;
 257
 258   file_open();
 259   while (input < max_input || fill_buffer() > 0) {
 260         p = (char *) memchr(input, '\n', BUF_SIZE);
 261         *p++ = '\0';
 262         if ((str = (char *) malloc(p - input)) == (char *) NULL)
 263                 failure(no_mem);
 264         memcpy(str, input, p - input);
 265         add_string(str);
 266         input = p;
 267   }
 268   close(fd_in);
 269 }
 270
 271 /* Scan the rest of the available input for a string using Boyer-Moore.
 272  * Return a pointer to the match or a pointer beyond end of input if no match.
 273  * Record how far the input is scanned.
 274  */
 275 char *search_str(ts)
 276 test_str *ts;
 277 {
 278   char *bufp, *prevbufp, *s;
 279
 280   bufp = input + ts->len - 1;
 281   while (bufp < max_input) {
 282         prevbufp = bufp;
 283         bufp += ts->table[*bufp & BYTE];
 284         if (bufp > prevbufp) continue;
 285         s = ts->str_end;
 286         do {
 287                 if (s == ts->str) {     /* match found */
 288                         ts->bufp = bufp;
 289                         return bufp;
 290                 }
 291         } while (*--bufp == *--s);
 292         bufp = prevbufp + 1;
 293   }
 294   ts->bufp = bufp;
 295
 296   return bufp;
 297 }
 298
 299 /* Return the next line in which one of the strings occurs.
 300  * Or, if the -v option is used, the next line without a match.
 301  * Or NULL on EOF.
 302  */
 303 char *get_line()
 304 {
 305   test_str *ts;
 306   char *match, *line;
 307
 308   /* Loop until a line is found. */
 309   while (1) {
 310         if (input >= max_input && fill_buffer() == 0) { /* EOF */
 311                 line = (char *) NULL;
 312                 break;
 313         }
 314
 315         /* If match is still equal to max_input after the next loop
 316          * then no match is found. */
 317         match = max_input;
 318         ts = strings;
 319         do {
 320                 if (input == buffer) {
 321                         if (search_str(ts) < match) match = ts->bufp;
 322                 } else if (ts->bufp < match) {
 323                         if (ts->bufp >= input || search_str(ts) < match)
 324                                 match = ts->bufp;
 325                 }
 326         } while ((ts = ts->next) != (test_str *) NULL);
 327
 328         /* Determine if and in what line a match is found. Only do
 329          * line number counting if it is necessary or very easy. */
 330         if (vflag) {
 331                 line_num++;
 332                 line = input;
 333                 input = 1 + (char *) memchr(line, '\n', BUF_SIZE);
 334                 if (input <= match) break;      /* no match in current line */
 335         } else if (nflag) {
 336                 do {
 337                         line_num++;
 338                         line = input;
 339                         input = 1 + (char *) memchr(line, '\n', BUF_SIZE);
 340                 } while (input < match ||
 341                          (input == match && match < max_input));
 342                 if (match < max_input) break;   /* match found */
 343         } else if (match < max_input) {
 344                 /* Match found. */
 345                 for (line = match; *--line != '\n';);
 346                 line++;
 347                 input = 1 + (char *) memchr(match, '\n', BUF_SIZE);
 348                 break;
 349         } else
 350                 input = max_input;
 351   }
 352
 353   return line;
 354 }