root/user/grep.c

DEFINITIONS

1. grep
2. main
3. match
4. matchhere
5. matchstar

   1 // Simple grep.  Only supports ^ . * $ operators.
   2 
   3 #include "kernel/types.h"
   4 #include "kernel/stat.h"
   5 #include "kernel/fcntl.h"
   6 #include "user/user.h"
   7 
   8 char buf[1024];
   9 int match(char *, char *);
  10 
  11 void
  12 grep(char *pattern, int fd)
  13 {
  14   int n, m;
  15   char *p, *q;
  16 
  17   m = 0;
  18   while ((n = read(fd, buf + m, sizeof(buf) - m - 1)) > 0) {
  19     m += n;
  20     buf[m] = '\0';
  21     p = buf;
  22     while ((q = strchr(p, '\n')) != 0) {
  23       *q = 0;
  24       if (match(pattern, p)) {
  25         *q = '\n';
  26         write(1, p, q + 1 - p);
  27       }
  28       p = q + 1;
  29     }
  30     if (m > 0) {
  31       m -= p - buf;
  32       memmove(buf, p, m);
  33     }
  34   }
  35 }
  36 
  37 int
  38 main(int argc, char *argv[])
  39 {
  40   int fd, i;
  41   char *pattern;
  42 
  43   if (argc <= 1) {
  44     fprintf(2, "usage: grep pattern [file ...]\n");
  45     exit(1);
  46   }
  47   pattern = argv[1];
  48 
  49   if (argc <= 2) {
  50     grep(pattern, 0);
  51     exit(0);
  52   }
  53 
  54   for (i = 2; i < argc; i++) {
  55     if ((fd = open(argv[i], O_RDONLY)) < 0) {
  56       printf("grep: cannot open %s\n", argv[i]);
  57       exit(1);
  58     }
  59     grep(pattern, fd);
  60     close(fd);
  61   }
  62   exit(0);
  63 }
  64 
  65 // Regexp matcher from Kernighan & Pike,
  66 // The Practice of Programming, Chapter 9, or
  67 // https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html
  68 
  69 int matchhere(char *, char *);
  70 int matchstar(int, char *, char *);
  71 
  72 int
  73 match(char *re, char *text)
  74 {
  75   if (re[0] == '^')
  76     return matchhere(re + 1, text);
  77   do { // must look at empty string
  78     if (matchhere(re, text))
  79       return 1;
  80   } while (*text++ != '\0');
  81   return 0;
  82 }
  83 
  84 // matchhere: search for re at beginning of text
  85 int
  86 matchhere(char *re, char *text)
  87 {
  88   if (re[0] == '\0')
  89     return 1;
  90   if (re[1] == '*')
  91     return matchstar(re[0], re + 2, text);
  92   if (re[0] == '$' && re[1] == '\0')
  93     return *text == '\0';
  94   if (*text != '\0' && (re[0] == '.' || re[0] == *text))
  95     return matchhere(re + 1, text + 1);
  96   return 0;
  97 }
  98 
  99 // matchstar: search for c*re at beginning of text
 100 int
 101 matchstar(int c, char *re, char *text)
 102 {
 103   do { // a * matches zero or more instances
 104     if (matchhere(re, text))
 105       return 1;
 106   } while (*text != '\0' && (*text++ == c || c == '.'));
 107   return 0;
 108 }